Difference sets are not multiplicatively closed

Difference sets are not multiplicatively closed, Discrete Analysis 2016:17, 20pp.

The famous sum-product problem of Erdős and Szemerédi asks the following. Let \(A\) be a set of \(n\) real numbers. Define the sumset \(A+A\) of \(A\) to be the set \(\{x+y:x,y\in A\}\) and the product set \(A.A\) to be the set \(\{xy:x,y\in A\}\). Must at least one of \(A+A\) and \(A.A\) have size \(n^{2-o(1)}\)? Since neither set can have size greater than \(n^2\), this is saying that the only way of making one of them a little smaller is to make the other one have almost maximal size. In particular, arithmetic progressions have very large product sets and geometric progressions have very large sumsets. Until recently the best known bound was \(n^{4/3}\), up to logarithmic factors [3], though the exponent has now been very slightly improved [2].

More generally, the sum-product phenomenon is a collection of statements that say that in various senses it is not possible for a set to be additively structured and multiplicatively structured at the same time. For example, an important result of Bourgain, Katz and Tao states that if \(A\) is a subset of a finite field \({\mathbb F}_p\) and \(p^{\delta} < |A| < p^{1-\delta}\), then one of \(A+A\) and \(A.A\) must have size at least \(n^{1+\epsilon}\) for some \(\epsilon\) that depends on \(\delta\) only. An extra difficulty here is that finite fields can have nontrivial subfields, so somehow the proof has to use the fact that \(\mathbb F_p\) does not.

This paper gives an interesting twist on the sum-product phenomenon. The underlying philosophy is still that a set with additive structure cannot be too multiplicatively structured at the same time. However, the notion of additive structure is different. Instead of assuming that the set has a small sumset, Shkredov assumes that it is a difference set of another set. This is a genuinely different assumption, since if \(A\) has a large difference set \(D=A-A\), it is perfectly possible for \(D+D\) to be much bigger than \(D\). Nevertheless, when \(A\) is a set of real numbers, it still implies, as the main result of the paper shows, that the product set \(D.D\) has size at least \(|D|^{1+c}\), where \(c>0\) is an absolute constant. The same is true of the quotient set \(D/D\).

The paper also proves a result of a similar kind in the finite field \(\mathbb F_p\) provided that \(D\) is not too big. Since multiplicative subgroups have, by definition, very small product sets, this result implies in particular that a multiplicative subgroup \(H\) of \(\mathbb F_p\) that is not too large is not the difference set of any subset of \(\mathbb F_p\). (The precise assumption required is that \(H\) has order at most \(p^{4/5-\epsilon}\).)

[1] Jean Bourgain, Nets Katz and Terence Tao, A sum-product estimate in finite fields, and applications, GAFA, 14 (2004), 27-57, also available at arxiv:0301343

[2] Sergei Konyagin and Ilya D, Shkredov, On sum sets of sets, having small product set, arxiv:1503.05771

[3] Jozsef Solymosi, Bounding multiplicative energy by the sumset , Adv. in Math, 222 (2009), 402-408, also available at arxiv:0806.1040

^{_{Article image by Lee Coursey}}