Let be a field. A definable set over
is a set of the form
where is a natural number, and
is a predicate involving the ring operations
of
, the equality symbol
, an arbitrary number of constants and free variables in
, the quantifiers
, boolean operators such as
, and parentheses and colons, where the quantifiers are always understood to be over the field
. Thus, for instance, the set of quadratic residues
is definable over , and any algebraic variety over
is also a definable set over
. Henceforth we will abbreviate “definable over
” simply as “definable”.
If is a finite field, then every subset of
is definable, since finite sets are automatically definable. However, we can obtain a more interesting notion in this case by restricting the complexity of a definable set. We say that
is a definable set of complexity at most
if
, and
can be written in the form (1) for some predicate
of length at most
(where all operators, quantifiers, relations, variables, constants, and punctuation symbols are considered to have unit length). Thus, for instance, a hypersurface in
dimensions of degree
would be a definable set of complexity
. We will then be interested in the regime where the complexity remains bounded, but the field size (or field characteristic) becomes large.
In a recent paper, I established (in the large characteristic case) the following regularity lemma for dense definable graphs, which significantly strengthens the Szemerédi regularity lemma in this context, by eliminating “bad” pairs, giving a polynomially strong regularity, and also giving definability of the cells:
Lemma 1 (Algebraic regularity lemma) Let
be a finite field, let
be definable non-empty sets of complexity at most
, and let
also be definable with complexity at most
. Assume that the characteristic of
is sufficiently large depending on
. Then we may partition
and
with
, with the following properties:
My original proof of this lemma was quite complicated, based on an explicit calculation of the “square”
of using the Lang-Weil bound and some facts about the étale fundamental group. It was the reliance on the latter which was the main reason why the result was restricted to the large characteristic setting. (I then applied this lemma to classify expanding polynomials over finite fields of large characteristic, but I will not discuss these applications here; see this previous blog post for more discussion.)
Recently, Anand Pillay and Sergei Starchenko (and independently, Udi Hrushovski) have observed that the theory of the étale fundamental group is not necessary in the argument, and the lemma can in fact be deduced from quite general model theoretic techniques, in particular using (a local version of) the concept of stability. One of the consequences of this new proof of the lemma is that the hypothesis of large characteristic can be omitted; the lemma is now known to be valid for arbitrary finite fields (although its content is trivial if the field is not sufficiently large depending on the complexity at most
).
Inspired by this, I decided to see if I could find yet another proof of the algebraic regularity lemma, again avoiding the theory of the étale fundamental group. It turns out that the spectral proof of the Szemerédi regularity lemma (discussed in this previous blog post) adapts very nicely to this setting. The key fact needed about definable sets over finite fields is that their cardinality takes on an essentially discrete set of values. More precisely, we have the following fundamental result of Chatzidakis, van den Dries, and Macintyre:
Proposition 2 Let
be a finite field, and let
.
- (Discretised cardinality) If
is a non-empty definable set of complexity at most
, then one has
where
is a natural number, and
is a positive rational number with numerator and denominator
. In particular, we have
.
- (Definable cardinality) Assume
is sufficiently large depending on
. If
, and
are definable sets of complexity at most
, so that
can be viewed as a definable subset of
that is definably parameterised by
, then for each natural number
and each positive rational
with numerator and denominator
, the set
is definable with complexity
, where the implied constants in the asymptotic notation used to define (4) are the same as those that appearing in (3). (Informally: the “dimension”
and “measure”
of
depends definably on
.)
We will take this proposition as a black box; a proof can be obtained by combining the description of definable sets over pseudofinite fields (discussed in this previous post) with the Lang-Weil bound (discussed in this previous post). (The former fact is phrased using nonstandard analysis, but one can use standard compactness-and-contradiction arguments to convert such statements to statements in standard analysis, as discussed in this post.)
The above proposition places severe restrictions on the cardinality of definable sets; for instance, it shows that one cannot have a definable set of complexity at most and cardinality
, if
is sufficiently large depending on
. If
are definable sets of complexity at most
, it shows that
for some rational
with numerator and denominator
; furthermore, if
, we may improve this bound to
. In particular, we obtain the following “self-improving” properties:
- If
are definable of complexity at most
and
for some
, then (if
is sufficiently small depending on
and
is sufficiently large depending on
) this forces
.
- If
are definable of complexity at most
and
for some
and positive rational
, then (if
is sufficiently small depending on
and
is sufficiently large depending on
) this forces
.
It turns out that these self-improving properties can be applied to the coefficients of various matrices (basically powers of the adjacency matrix associated to ) that arise in the spectral proof of the regularity lemma to significantly improve the bounds in that lemma; we describe how this is done below the fold. We also make some connections to the stability-based proofs of Pillay-Starchenko and Hrushovski.
— 1. The regularity lemma —
We begin with proving a slightly weaker version of the lemma, in which the bound is weakened to
; we will later use the self-improving properties mentioned previously to upgrade this bound. In other words, we begin by showing
Lemma 3 (Algebraic regularity lemma, weak version) Let
be a finite field, let
be definable non-empty sets of complexity at most
, and let
also be definable with complexity at most
. Then we may partition
and
with
, with the following properties:
- (Definability) Each of the
are definable of complexity
.
- (Size) We have
and
for all
and
.
- (Regularity) We have
for all
,
,
, and
, where
is a rational number in
with numerator and denominator
.
We now prove this lemma, by combining spectral theory with an (iterated) method. We may assume that
is sufficiently large depending on
, as the claim is trivial otherwise (just take
). We consider the probability spaces
,
with the uniform probability measures
on
; we abbreviate
as
for
, and similarly define
(we work exclusively with real-valued functions here). The set
then defines a linear operator
by the formula
thus is the operator with integral kernel
. We can then compute the adjoint operator
as
From the Cauchy-Schwarz inequality we observe the bounds
for all .
Now we apply the singular value decomposition (which is easily justified as ,
are finite dimensional) to write
and
for some finite sequence of singular values, the
are an orthonormal system in
, and the
are an orthonormal system in
. Observe that operator
can be diagonalised as
and hence
On the other hand, direct calculation shows that
and so we have the Frobenius norm (or Hilbert-Schmidt norm) bound
Next, from the identities
and (5), (6) we obtain sup-norm bounds on the eigenfunctions:
We now use these bounds to obtain a low rank approximation to the sixth power . This operator may be diagonalised as
We let be a small quantity (depending only on
) to be chosen later, and split
where is a low rank operator
and is the error term
Observe from the triangle inequality, Hölder’s inequality and (8), (7) that
for any . In other words, the integral kernel of
is bounded pointwise by
. As for
, we use (8) to discretise
, where
takes on at most
values (say), and
is bounded in magnitude by
. We can then split
, where
and the error term can easily be shown (by arguments similar to before) to have a bound of the form
(with many powers of to spare). We have thus written
, where
has integral kernel bounded pointwise by
.
Now from (7), the number of summands in the definition of
is at most
. If we then partition
using the level sets of the corresponding
(removing any empty cells to ensure the
are non-empty), then we have
and the integral kernel of is constant on each
. Thus, the integral kernel of
fluctuates by at most
on each
.
Thus far, we have not used the definability of . Now we will do so in order to take advantage of self-improving properties. The integral kernel
of
can be evaluated explicitly as
where is the set
Clearly, is a definable set of complexity
. From Proposition 2 we thus have the discretisation bounds
where is a non-negative rational number with numerator and denominator
. The set of such rationals is finite (basically a portion of the Farey sequence), and thus are separated from each other by some separation
. If we combine this fact with the local near-constancy of
on
, we can thus (if
is small enough) self-improve this near-constancy to the bound
for all , all
,
, and some non-negative rational
depending only on
with numerator and denominator
.
Note that as is symmetric,
will be symmetric too. If two
are indistinguishable in the sense that
for all
, then we may concatenate
and
(reducing
by one), so we may assume that elements of
are pairwise distinguishable. From Proposition 2 we see that for each
and rational
, the set
is definable with complexity
. Taking boolean combinations and using distinguishability, we conclude that each
is also definable with complexity
. In particular, we either have
or
.
Now let be supported on
with mean zero for some
. From (10) we see that
On the other hand, from (9) we have
while from Bessel’s inequality we have
and thus by Hölder’s inequality
The left-hand side is just , so we conclude that
whenever is supported on one of the
with mean zero.
In a similar vein, we may find a partition into definable sets of complexity
with
with the property that
whenever is supported on one of the
with mean zero.
Let and
with
and
. From the above estimates and Cauchy-Schwarz, we see that
whenever are supported on
respectively, with at least one of
having mean zero. If
,
, then by decomposing
and
into mean-zero and constant components on
respectively, we conclude that
On the other hand, we have
so by Proposition 2, for some rational
with numerator and denominator
. Also
and
for some further rational
with numerator and denominator
. This proves Lemma 3, except that we have some “small”
and
with
and
that we have not yet dealt with. However we may simply concatenate these small cells onto one of the larger cells, as this does not significantly affect the definability or regularity properties of the large cells, and we are done.
Now we improve the bound to
. Let
be large cells as in the preceding argument. Let
be the restriction of
to
and
(associated to the set
), giving
,
uniform probability measure, then we have
whenever at least one of ,
have mean zero. Thus, we may split
where
is a constant,
is the rank one operator
and has operator norm
. By computing
as before, we see that we may take
to be a rational with numerator and denominator
.
Recall that has a Hilbert-Schmidt norm of
, and so by the triangle inequality
does also. If we square, we conclude that
, where
has Hilbert-Schmidt norm
. Thus, if
is the integral kernel of
, then
On the other hand, we have
so by Proposition 2, we have either
or
for each . Furthermore, the set of pairs
for which the latter occurs is a definable subset of
with complexity
. On the other hand, from (11) and Chebyshev’s inequality, this set has cardinality
. By Proposition 2, we may self-improve this to
. Integrating, we self-improve (11) to
so by Cauchy-Schwarz we have
whenever has mean zero, thus
whenever has mean zero. By repeating the final steps of the proof of Lemma 3 we conclude (2) as required.
— 2. Stability —
The following stability result was established by Hrushovski (see Proposition 2.25 of this paper)
Proposition 4 (Stability) Let
be real numbers, and suppose that there are measurable subsets
of a probability space
with the property that
and
for
. Then we have
.
In the language of stability theory, this proposition asserts that the relation is stable. This proposition was the key input used by Pillay-Starchenko and by Hrushovski (together with the discretisation results of Proposition 2) to give an alternate proof of the algebraic regularity lemma.
Let us first sketch Hrushovski’s proof of this lemma. If the claim failed, then by a compactness argument one can construct infinite sequences of measurable subsets of a probability space
with the property that
for all . Next, by Ramsey theory (for directed graphs), for any given
, we may pass to an infinite subsequence such that
for any and
, and by further compactness we may eliminate the
error, so that
for any and
. More generally, (using Ramsey’s theorem for directed hypergraphs and more compactness) we may assume the order-indiscernibility property
for any and
, and any
. This implies (by a variant of de Finetti’s theorem, proven in Hrushovski’s paper via the Krein-Milman theorem) that
is exchangeable, which among other things implies that
for any ; but this contradicts (12), (13).
Now we give a spectral proof of the above proposition. Let be a matrix to be chosen later, and consider the expression
We can rewrite this expression as
For any , the vectors
and
have an
norm of at most
. Thus, we can bound the preceding expression by
where is the operator norm of
; thus we have
We apply this inequality to the discrete Hilbert transform matrix, in which for
and
. This matrix has an operator norm of at most
(this is Hilbert’s inequality). Thus
But by (12), (13), the left-hand side is at least , and the claim follows (with a bound of the form
).
5 comments
Comments feed for this article
29 October, 2013 at 11:13 pm
Michael
A union symbol seems to be missing in the partition of V in Lemma 3.
There seems to be a cutoff at the end of the paragraph before the paragraph beginning with “Clearly, G_(w,w’).” Similarly for the double integral that references (10).
[Corrected, thanks – T.]
30 October, 2013 at 12:18 am
gowers
I’m having trouble understanding the definition of complexity because I don’t see how M relates to the definability definition. There must clearly be some condition on M other than its being at least n, but I can’t find it. Is it to do with the length of the formula?
[Oops, yes, I had omitted the length condition. It’s in place now – T.]
30 October, 2013 at 4:54 am
omar aboura
In the proof of Lemma 3:
After “Observe from the triangle inequality…”, the sums in the inequality should be $\sigma_i<\epsilon$ instead of $\sigma_i\geq\epsilon$.
In the sentence "We can then split…" $E$ should be $E'$ (three times).
[Corrected, thanks – T.]
31 October, 2013 at 5:57 am
John Mangual
“Beautiful” formulas tend to take the shape, A = B where A and B have similar complexity. We also seems to like Σ A = B where by averaging A, we get object of lower complexity B.
Your notion of “definable” makes sense. How else are we going to define subsets of finite fields? We have some starting objects and a finite number of operations we can do to them and construct more objects.
One could imagine writing a program to test membership in the set A. If A is too complex, the program has to be very long. Maybe, due to this regularity lemma, I could write a random algorithm that does almost the same thing.
I don’t write a lot of programs over finite fields – I won’t think about that!
7 November, 2013 at 9:34 pm
JSE
“avoiding the theory of the étale fundamental group”
You say that like it’s a _good_ thing!