Products of Differences over Arbitrary Finite Fields
Products of Differences over Arbitrary Finite Fields, Discrete Analysis 2018:18, 42 pp.
A central problem in arithmetic combinatorics is the Erdős-Szemerédi sum-product problem, which asks whether it is true that if A is a finite set of integers, then either the sumset A+A or the product set A.A must have size at least |A|2−o(1). Erdős and Szemerédi obtained a lower bound (for the size of the larger of the sumset and the product set) of |A|1+c for a small positive constant c. For a long time, the record was held by Solymosi, who obtained a bound of n4/3−o(1) with a beautifully simple argument. The 4/3 barrier was finally broken by Konyagin and Shkredov in 2015, and the current record, which stands at 4/3+5/5277, is held by George Shakan. In general, the notion that it is not easy for a set to have both a small sumset and a small product set is referred to as the sum-product phenomenon.
A solution to the Erdős-Szemerédi problem still appears to require a major new idea, but there are a number of related questions for which progress is being made. An interesting variant of the problem, with many applications, concerns the sum-product phenomenon for subsets of finite fields. Here one must be careful with formulating conjectures, since a finite field can have proper subfields, and for those the sum-product phenomenon clearly does not occur. However, important results have been proved under the assumptions on the cardinality of the subset that rule out these obvious counterexamples.
A general class of questions, intimately connected with the sum-product phenomenon in finite fields, is the following. Given a fixed multivariable polynomial P in k variables and a subset A of a finite field Fq, define the image P(A) of A to be the set of all P(a1,…,ak) such that the ai belong to A. Then if A has cardinality m, what can be said about the size of P(A)? For example, if P is the polynomial xy+zw, then this is asking for the size of the set A.A+A.A, which consists of all xy+zw such that x,y,z,w∈A. The relationship with the sum-product phenomenon is obvious.
Of particular interest is to determine how large A has to be in order to guarantee that P(A) to have size at least cq for some absolute constant q. (One might consider asking for even more – that P(A) is almost all of Fq, but as the authors show with an example, this significantly increases the size of the bound one can hope for.) The authors concentrate in particular on the polynomial (x−y)(z−w), so they are studying the product set of the difference set.
Since Fq does not have a subfield of cardinality greater than q1/2, a natural condition to place on m is that it should be safely larger than q1/2. However, except when q is a prime, the exponent 2/3 has proved to be a rather stubborn barrier. The main result of this paper is to get past it: the authors show that the condition m≥q2/3−1/13542+o(1) suffices. The main novelty of the proof is a precise description of pairs of sets A,X⊂Fq with the property that |A+XA| is almost as small as possible, which constitutes the “structure part” of an argument that works via a structure/randomness dichotomy.
When q is prime, the best known exponent is 3/5: another result of the paper is that this bound suffices even for the off-diagonal case of sets of the form (A−B).(C−D).