A recent breakthrough due to Croot, Lev and Pach, recycled by Ellenberg-Gijswijt and streamlined by Tao on this blog post, revolutionised the landscape of Roth’s type problems in vector spaces over finite fields. Indeed, Ellenberg-Gijswijt obtained that a set free of triple satisfying
can have at most
elements out of the
out there. Here we show the same method can deal with sets free of solutions to various other equations in any
(given that if
, we have
as a vector space, there’s no point in considering general
) and we make explicit the dependence on
of the resulting bound. We refer in the sequel mostly to Tao’s symmetric proof instead of the original articles. One great merit of this exposition is to reveal, thanks to the extension of the notion of rank from matrices (seen as functions of two variables) to functions of more variables, how the scope of the method can be extended.
Other linear equations
In fact the bound found for the sets without 3-term arithmetic progressions is also valid
for a set having no non-trivial solutions to
where are three linear automorphisms of
summing to 0. Indeed,
we can then still write
Even more generally, for any integer , if
are
automorphisms of
which sum to 0, and if
does not have any non-trivial solution to the equation
, we can still write
The right-hand side is still a function on of rank
. Meanwhile, the left-hand side may still be expanded using the formula
valid for all
, which implies that the LHS equals
where means the
-th coordinate of
; it is
thus a linear polynomial. This implies that the whole expression is a polynomial of degree . The treatment shown by Tao on his blog to bound the rank of this expression can thus be applied here too.
Roth’s theorem is simply the case where and
for
, or more generally
and
.
The more variables, the smaller the bound becomes. For instance, a set without any solution to the equation
, in particular without any 3-APs, has size at most
, less than the bound for sets without 3-APS which is
.
Even non-linear equations
Upon scrutinizing the polynomial method at work in Ellenberg-Gijswijt, one can be struck by the fact that the translation-invariance of the equation is not even used. In Meshulam’s theorem, as in all form of density increment strategy, we crucially use the fact that if
is a solution and if
is any constant, then
is a solution too. What is used in the polynomial strategy is that any constant tuple
is a solution, which is vastly weaker (though it is synonymous for linear patterns). Thus if
are any bounded-degree polynomial maps
(i.e. maps whose coordinates are polynomials of degree at most
) summing to 0, then the method should, in principle, spit out a bound for the maximal size of a set
free of solutions to
, depending on the degree. The only thing that changes in Tao’s write-up is that the polynomial
whose rank we try to bound is now of degree up to . Thus the parameter of relevance and which determines whether the method will succeed or not is
. It has to be significantly less than
. Otherwise, the method requiring a good bound (exponential if possible) on
where are independent, identically distributed variable on
, we are hopeless.
Thus, considering , we need
variables.
Equations in a polynomial ring
As advocated by Tom Bloom (for instance in this paper), it might be of interest to ask for analogues of theorems in polynomial ring. However, a relation of the form among three polynomials over
of degree less than
is simply a relation among three vectors, the vectors of their coefficients. But we can form much more general equations, such as
Dependence on
Let’s return to the case of Roth’s theorem.
Following Tao, one gets a bound of the form
where is the maximum of
under the constraints
It could be interesting to know how evolves with
.
Using the help of a computer to compute for
upto
, I got the feeling that
. This would mean that a subset
free of 3-term arithmetic progressions necessarily satisfies
.
We now proceed to show that the empirically conjectured behaviour of is indeed the true one.
The constrained extrema theorem implies that the maximum of is attained on a point where
belongs to . This condition amounts to the existence of
so that
for all indices
. So we have only two degrees of freedom for the tuple
. And because we have two equations
there should be a unique such tuple.
Putting , we transform the first constraint in
thus the second one amounts to
Here the LHS equals
Thus the equation to solve is
in other words
It clearly imposes that as , we must have
, for if it remains bounded away from 1, the left-hand side is asymptotic to
, which is not asymptotic to
, the right-hand side.
We now rearrange the equation as
that is
Let us introduce and determine the behaviour of
, or equivalently of
. One can prove by contradiction that
cannot tend to 0. Indeed, supposing it did, one could write
Thus
and comparing the term in we see an absurdity.
It can’t either tend to . If it has a limit point
, it has to be a solution to
The computer declares that the solution to this equations equals 2.149125799907062 (which is very close, fortunately enough, to values observed for for large
). Thus
tends to
.
Injecting the expression for the in terms of
, the optimum is
which we can equate, remembering earlier formulae, to
.
So let us derive an asymptotic expression for and
. We quickly obtain
.
So the maximum we are after equals
This implies that
Injecting the value we found for , the computer spits out 0.84, as guessed.
Laisser un commentaire
Comments feed for this article