The rectification principle in arithmetic combinatorics asserts, roughly speaking, that very small subsets (or, alternatively, small structured subsets) of an additive group or a field of large characteristic can be modeled (for the purposes of arithmetic combinatorics) by subsets of a group or field of zero characteristic, such as the integers or the complex numbers
. The additive form of this principle is known as the Freiman rectification principle; it has several formulations, going back of course to the original work of Freiman. Here is one formulation as given by Bilu, Lev, and Ruzsa:
Proposition 1 (Additive rectification) Let
be a subset of the additive group
for some prime
, and let
be an integer. Suppose that
. Then there exists a map
into a subset
of the integers which is a Freiman isomorphism of order
in the sense that for any
, one has
if and only if
Furthermore
is a right-inverse of the obvious projection homomorphism from
to
.
The original version of the rectification principle allowed the sets involved to be substantially larger in size (cardinality up to a small constant multiple of ), but with the additional hypothesis of bounded doubling involved; see the above-mentioned papers, as well as this later paper of Green and Ruzsa, for further discussion.
The proof of Proposition 1 is quite short (see Theorem 3.1 of Bilu-Lev-Ruzsa); the main idea is to use Minkowski’s theorem to find a non-trivial dilate of
that is contained in a small neighbourhood of the origin in
, at which point the rectification map
can be constructed by hand.
Very recently, Codrut Grosu obtained an arithmetic analogue of the above theorem, in which the rectification map preserves both additive and multiplicative structure:
Theorem 2 (Arithmetic rectification) Let
be a subset of the finite field
for some prime
, and let
be an integer. Suppose that
. Then there exists a map
into a subset
of the complex numbers which is a Freiman field isomorphism of order
in the sense that for any
and any polynomial
of degree at most
and integer coefficients of magnitude summing to at most
, one has
if and only if
Note that it is necessary to use an algebraically closed field such as for this theorem, in contrast to the integers used in Proposition 1, as
can contain objects such as square roots of
which can only map to
in the complex numbers (once
is at least
).
Using Theorem 2, one can transfer results in arithmetic combinatorics (e.g. sum-product or Szemerédi-Trotter type theorems) regarding finite subsets of to analogous results regarding sufficiently small subsets of
; see the paper of Grosu for several examples of this. This should be compared with the paper of Vu, Wood, and Wood, which introduces a converse principle that embeds finite subsets of
(or more generally, a characteristic zero integral domain) in a Freiman field-isomorphic fashion into finite subsets of
for arbitrarily large primes
, allowing one to transfer arithmetic combinatorical facts from the latter setting to the former.
Grosu’s argument uses some quantitative elimination theory, and in particular a quantitative variant of a lemma of Chang that was discussed previously on this blog. In that previous blog post, it was observed that (an ineffective version of) Chang’s theorem could be obtained using only qualitative algebraic geometry (as opposed to quantitative algebraic geometry tools such as elimination theory results with explicit bounds) by means of nonstandard analysis (or, in what amounts to essentially the same thing in this context, the use of ultraproducts). One can then ask whether one can similarly establish an ineffective version of Grosu’s result by nonstandard means. The purpose of this post is to record that this can indeed be done without much difficulty, though the result obtained, being ineffective, is somewhat weaker than that in Theorem 2. More precisely, we obtain
Theorem 3 (Ineffective arithmetic rectification) Let
. Then if
is a field of characteristic at least
for some
depending on
, and
is a subset of
of cardinality
, then there exists a map
into a subset
of the complex numbers which is a Freiman field isomorphism of order
.
Our arguments will not provide any effective bound on the quantity (though one could in principle eventually extract such a bound by deconstructing the proof of Proposition 4 below), making this result weaker than Theorem 2 (save for the minor generalisation that it can handle fields of prime power order as well as fields of prime order as long as the characteristic remains large).
Following the principle that ultraproducts can be used as a bridge to connect quantitative and qualitative results (as discussed in these previous blog posts), we will deduce Theorem 3 from the following (well-known) qualitative version:
Proposition 4 (Baby Lefschetz principle) Let
be a field of characteristic zero that is finitely generated over the rationals. Then there is an isomorphism
from
to a subfield
of
.
This principle (first laid out in an appendix of Lefschetz’s book), among other things, often allows one to use the methods of complex analysis (e.g. Riemann surface theory) to study many other fields of characteristic zero. There are many variants and extensions of this principle; see for instance this MathOverflow post for some discussion of these. I used this baby version of the Lefschetz principle recently in a paper on expanding polynomial maps.
Proof: We give two proofs of this fact, one using transcendence bases and the other using Hilbert’s nullstellensatz.
We begin with the former proof. As is finitely generated over
, it has finite transcendence degree, thus one can find algebraically independent elements
of
over
such that
is a finite extension of
, and in particular by the primitive element theorem
is generated by
and an element
which is algebraic over
. (Here we use the fact that characteristic zero fields are separable.) If we then define
by first mapping
to generic (and thus algebraically independent) complex numbers
, and then setting
to be a complex root of of the minimal polynomial for
over
after replacing each
with the complex number
, we obtain a field isomorphism
with the required properties.
Now we give the latter proof. Let be elements of
that generate that field over
, but which are not necessarily algebraically independent. Our task is then equivalent to that of finding complex numbers
with the property that, for any polynomial
with rational coefficients, one has
if and only if
Let be the collection of all polynomials
with rational coefficients with
, and
be the collection of all polynomials
with rational coefficients with
. The set
is the intersection of countably many algebraic sets and is thus also an algebraic set (by the Hilbert basis theorem or the Noetherian property of algebraic sets). If the desired claim failed, then could be covered by the algebraic sets
for
. By decomposing into irreducible varieties and observing (e.g. from the Baire category theorem) that a variety of a given dimension over
cannot be covered by countably many varieties of smaller dimension, we conclude that
must in fact be covered by a finite number of such sets, thus
for some . By the nullstellensatz, we thus have an identity of the form
for some natural numbers , polynomials
, and polynomials
with coefficients in
. In particular, this identity also holds in the algebraic closure
of
. Evaluating this identity at
we see that the right-hand side is zero but the left-hand side is non-zero, a contradiction, and the claim follows.
From Proposition 4 one can now deduce Theorem 3 by a routine ultraproduct argument (the same one used in these previous blog posts). Suppose for contradiction that Theorem 3 fails. Then there exists natural numbers , a sequence of finite fields
of characteristic at least
, and subsets
of
of cardinality
such that for each
, there does not exist a Freiman field isomorphism of order
from
to the complex numbers. Now we select a non-principal ultrafilter
, and construct the ultraproduct
of the finite fields
. This is again a field (and is a basic example of what is known as a pseudo-finite field); because the characteristic of
goes to infinity as
, it is easy to see (using Los’s theorem) that
has characteristic zero and can thus be viewed as an extension of the rationals
.
Now let be the ultralimit of the
, so that
is the ultraproduct of the
, then
is a subset of
of cardinality
. In particular, if
is the field generated by
and
, then
is a finitely generated extension of the rationals and thus, by Proposition 4 there is an isomorphism
from
to a subfield
of the complex numbers. In particular,
are complex numbers, and for any polynomial
with integer coefficients, one has
if and only if
By Los’s theorem, we then conclude that for all sufficiently close to
, one has for all polynomials
of degree at most
and whose coefficients are integers whose magnitude sums up to
, one has
if and only if
But this gives a Freiman field isomorphism of order between
and
, contradicting the construction of
, and Theorem 3 follows.
5 comments
Comments feed for this article
14 March, 2013 at 5:09 pm
g
I like the condition p>=3 in the statement of Theorem 2. I mean, for the result to be nontrivial we need s>=2 and |A|>=1, in which case we have 1 8^(4^(2^2)) = 8^256 = 2^768. Just as well you specified that p>=3!
(For the other conditions to be possible, even if trivial, we need s>=1 and |A|>=0, in which case we have 0 2^(2^(2^1)) = 16.)
15 March, 2013 at 3:16 am
Anonymous
Just a typo – Codrut’s surname is Grosu.
[Corrected, thanks – T.]
15 March, 2013 at 9:21 am
murphmath
In the last few paragraphs there’s a limit taken as i–>p and Los’s theorem is applied for i sufficiently close to p — should it be alpha instead of p?
[Corrected, thanks – T.]
23 March, 2013 at 3:12 pm
Curious
Dear prof Tao, do you think discreetness in nature is an emergent property? Or are continuus objects derived from discrete objects? Riemann zeta function is a continuous function which encodes the property of the primes, but mathematics and physics (even string theory) itself is formulated using finite discrete symbols.
25 March, 2013 at 4:23 am
Pierre
Dear Terry,
I discussed this question with Udi Hrushovski a few months ago.
If I am not mistaken, one can use constructive Nullstellensatz to obtain a similar result. In fact, Theorem 1 of this paper: Sharp estimates for the arithmetic Nullstellensatz (T. Krick, L.M. Pardo, M. Sombra)
seems to give better bounds of the form |A| << log(log(p)) to some power depending on s, where p is the characteristic of the finite field.