You are currently browsing the tag archive for the ‘sum-product theorems’ tag.
In the previous set of notes, we saw that one could derive expansion of Cayley graphs from three ingredients: non-concentration, product theorems, and quasirandomness. Quasirandomness was discussed in Notes 3. In the current set of notes, we discuss product theorems. Roughly speaking, these theorems assert that in certain circumstances, a finite subset of a group either exhibits expansion (in the sense that , say, is significantly larger than ), or is somehow “close to” or “trapped” by a genuine group.
- (Expansion) One has .
- (Close to ) One has .
- (Trapping) is contained in a proper subgroup of .
We will prove this theorem (which was proven first in the cases for fields of prime order by Helfgott, and then for and general by Dinai, and finally to general and independently by Pyber-Szabo and by Breuillard-Green-Tao) later in this notes. A more qualitative version of this proposition was also previously obtained by Hrushovski. There are also generalisations of the product theorem of importance to number theory, in which the field is replaced by a cyclic ring (with not necessarily prime); this was achieved first for and square-free by Bourgain, Gamburd, and Sarnak, by Varju for general and square-free, and finally by this paper of Bourgain and Varju for arbitrary and .
Exercise 1 (Girth bound) Assuming Theorem 1, show that whenever is a symmetric set of generators of for some finite field and some , then any element of can be expressed as the product of elements from . (Equivalently, if we add the identity element to , then for some .) This is a special case of a conjecture of Babai and Seress, who conjectured that the bound should hold uniformly for all finite simple groups (in particular, the implied constants here should not actually depend on . The methods used to handle the case can handle other finite groups of Lie type of bounded rank, but at present we do not have bounds that are independent of the rank. On the other hand, a recent paper of Helfgott and Seress has almost resolved the conjecture for the permutation groups .
A key tool to establish product theorems is an argument which is sometimes referred to as the pivot argument. To illustrate this argument, let us first discuss a much simpler (and older) theorem, essentially due to Freiman, which has a much weaker conclusion but is valid in any group :
- (Expansion) One has .
- (Close to a subgroup) is contained in a left-coset of a group with .
To prove this theorem, we suppose that the first conclusion does not hold, thus . Our task is then to place inside the left-coset of a fairly small group .
To do this, we take a group element , and consider the intersection . A priori, the size of this set could range from anywhere from to . However, we can use the hypothesis to obtain an important dichotomy, reminiscent of the classical fact that two cosets of a subgroup of are either identical or disjoint:
- (Non-involved case) is empty.
- (Involved case) .
Proof: Suppose we are not in the pivot case, so that is non-empty. Let be an element of , then and both lie in . The sets and then both lie in . As these sets have cardinality and lie in , which has cardinality less than , we conclude from the inclusion-exclusion formula that
But the left-hand side is equal to , and the claim follows.
The above proposition provides a clear separation between two types of elements : the “non-involved” elements, which have nothing to do with (in the sense that , and the “involved” elements, which have a lot to do with (in the sense that . The key point is that there is a significant “gap” between the non-involved and involved elements; there are no elements that are only “slightly involved”, in that and intersect a little but not a lot. It is this gap that will allow us to upgrade approximate structure to exact structure. Namely,
Proposition 4 The set of involved elements is a finite group, and is equal to .
Proof: It is clear that the identity element is involved, and that if is involved then so is (since . Now suppose that are both involved. Then and have cardinality greater than and are both subsets of , and so have non-empty intersection. In particular, is non-empty, and so is non-empty. By Proposition 3, this makes involved. It is then clear that is a group.
If , then is non-empty, and so from Proposition 3 is involved. Conversely, if is involved, then . Thus we have as claimed. In particular, is finite.
Now we can quickly wrap up the proof of Theorem 2. By construction, for all ,which by double counting shows that . As , we see that is contained in a right coset of ; setting , we conclude that is contained in a left coset of . is a conjugate of , and so . If , then and both lie in and have cardinality , so must overlap; and so . Thus , and so , and Theorem 2 follows.
Exercise 2 Show that the constant in Theorem 2 cannot be replaced by any larger constant.
Exercise 3 Let be a finite non-empty set such that . Show that . (Hint: If , show that for some .)
Exercise 4 Let be a finite non-empty set such that . Show that there is a finite group with and a group element such that and .
Below the fold, we give further examples of the pivot argument in other group-like situations, including Theorem 2 and also the “sum-product theorem” of Bourgain-Katz-Tao and Bourgain-Glibichuk-Konyagin.
I’ve uploaded a new paper to the arXiv entitled “The sum-product phenomenon in arbitrary rings“, and submitted to Contributions to Discrete Mathematics. The sum-product phenomenon asserts, very roughly speaking, that given a finite non-empty set A in a ring R, then either the sum set or the product set will be significantly larger than A, unless A is somehow very close to being a subring of R, or if A is highly degenerate (for instance, containing a lot of zero divisors). For instance, in the case of the integers , which has no non-trivial finite subrings, a long-standing conjecture of Erdös and Szemerédi asserts that for every finite non-empty and every . (The current best result on this problem is a very recent result of Solymosi, who shows that the conjecture holds for any greater than 2/3.) In recent years, many other special rings have been studied intensively, most notably finite fields and cyclic groups, but also the complex numbers, quaternions, and other division algebras, and continuous counterparts in which A is now (for instance) a collection of intervals on the real line. I will not try to summarise all the work on sum-product estimates and their applications (which range from number theory to graph theory to ergodic theory to computer science) here, but I discuss this in the introduction to my paper, which has over 50 references to this literature (and I am probably still missing out on a few).
I was recently asked the question as to what could be said about the sum-product phenomenon in an arbitrary ring R, which need not be commutative or contain a multiplicative identity. Once one makes some assumptions to avoid the degenerate case when A (or related sets, such as A-A) are full of zero-divisors, it turns out that there is in fact quite a bit one can say, using only elementary methods from additive combinatorics (in particular, the Plünnecke-Ruzsa sum set theory). Roughly speaking, the main results of the paper assert that in an arbitrary ring, a set A which is non-degenerate and has small sum set and product set must be mostly contained inside a subring of R of comparable size to A, or a dilate of such a subring, though in the absence of invertible elements one sometimes has to enlarge the ambient ring R slightly before one can find the subring. At the end of the paper I specialise these results to specific rings, such as division algebras or products of division algebras, cyclic groups, or finite-dimensional algebras over fields. Generally speaking, the methods here give very good results when the set of zero divisors is sparse and easily describable, but poor results otherwise. (In particular, the sum-product theory in cyclic groups, as worked out by Bourgain and coauthors, is only recovered for groups which are the product of a bounded number of primes; the case of cyclic groups whose order has many factors seems to require a more multi-scale analysis which I did not attempt to perform in this paper.)
Read the rest of this entry »