You are currently browsing the monthly archive for juillet 2016.

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.

## Commentaires récents