Mathematics
Mathematics is the study of numbers, shapes, and patterns.
Mathematics is the study of numbers, shapes, and patterns.
Organizer:
- Organized by
-
-
Sumsets and entropy revisited
-
Sumsets and entropy revisited
Ben Green, Freddie Manners and I have just uploaded to the arXiv our preprint “Sumsets and entropy revisited“. This paper uses entropy methods to attack the Polynomial Freiman-Ruzsa (PFR) conjecture, which we study in the following two forms:
Conjecture 1 (Weak PFR over ) Let be a finite non-empty set whose doubling constant is at most . Then there is a subset of of density that has affine dimension (i.e., it is contained in an affine space of dimension ).
Conjecture 2 (PFR over ) Let be a non-empty set whose doubling constant is at most . Then can be covered by cosets of a subspace of cardinality at most .
Our main results are then as follows.
Theorem 3 If with , then
(i) There is a subset of of density of “skew-dimension” (or “query complexity”) . (ii) There is a subset of of density of affine dimension (where goes to zero as ). (iii) If Conjecture 2 holds, then There is a subset of of density of affine dimension . In other words, Conjecture 2 implies Conjecture 1.
The skew-dimension of a set is a quantity smaller than the affine dimension which is defined recursively; the precise definition is given in the paper, but suffice to say that singleton sets have dimension , and a set whose projection to has skew-dimension at most , and whose fibers in have skew-dimension at most for any , will have skew-dimension at most . (In fact, the skew-dimension is basically the largest quantity which obeys all of these properties.)
Part (i) of this theorem was implicitly proven by Pálvölgi and Zhelezov by a different method. Part (ii) with replaced by was established by Manners. To our knowledge, part (iii) is completely new.
Our proof strategy is to establish these combinatorial additive combinatorics results by using entropic additive combinatorics, in which we replace sets with random variables , and cardinality with (the exponential of) Shannon entropy. This is in order to take advantage of some superior features of entropic additive combinatorics, most notably good behavior with respect to homomorphisms.
For instance, the analogue of the combinatorial doubling constant of a finite non-empty subset of an abelian group , is the entropy doubling constant
of a finitely-valued random variable in , where are independent copies of and denotes Shannon entropy. There is also an analogue of the Ruzsa distance
between two finite non-empty subsets of , namely the entropic Ruzsa distance
where are independent copies of respectively. (Actually, one thing we show in our paper is that the independence hypothesis can be dropped, and this only affects the entropic Ruzsa distance by a factor of three at worst.) Many of the results about sumsets and Ruzsa distance have entropic analogues, but the entropic versions are slightly better behaved; for instance, we have a contraction property
whenever is a homomorphism. In fact we have a refinement of this inequality in which the gap between these two quantities can be used to control the entropic distance between “fibers” of (in which one conditions and to be fixed). On the other hand, there are direct connections between the combinatorial and entropic sumset quantities. For instance, if is a random variable drawn uniformly from , then
Thus if has small doubling, then has small entropic doubling. In the converse direction, if has small entropic doubling, then is close (in entropic Ruzsa distance) to a uniform random variable drawn from a set of small doubling; a version of this statement was proven in an old paper of myself, but we establish here a quantitatively efficient version, established by rewriting the entropic Ruzsa distance in terms of certain Kullback-Liebler divergences.
Our first main result is a “99% inverse theorem” for entropic Ruzsa distance: if is sufficiently small, then there exists a finite subgroup of such that
This result uses the results just mentioned to relate to a set of small doubling, which can then be related to a subgroup by standard inverse theorems; this gives a weak version of (1) (roughly speaking losing a square root in the bound), and some additional analysis is needed to bootstrap this initial estimate back to (1).
We now sketch how these tools are used to prove our main theorem. For (i), we reduce matters to establishing the following bilinear entropic analogue: given two non-empty finite subsets of , one can find subsets , with
such that have skew-dimension at most , for some absolute constant . This can be shown by an induction on (say). One applies a non-trivial coordinate projection to . If and are very close in entropic Ruzsa distance, then the 99% inverse theorem shows that these random variables must each concentrate at a point (because has no non-trivial finite subgroups), and can pass to a fiber of these points and use the induction hypothesis. If instead and are far apart, then by the behavior of entropy under projections one can show that the fibers of and under are closer on average in entropic Ruzsa distance of and themselves, and one can again proceed using the induction hypothesis.
For parts (ii) and (iii), we first use an entropic version of an observation of Manners that sets of small doubling in must be irregularly distributed modulo . A clean formulation of this in entropic language is the inequality
whenever take values in a torsion-free abelian group such as ; this turns out to follow from two applications of the entropy submodularity inequality. One corollary of this (and the behavior of entropy under projections) is that
This is the key link between the and worlds that is used to prove (ii), (iii): while (iii) relies on the still unproven PFR conjecture over , (ii) uses the unconditional progress on PFR by Konyagin, as detailed in this survey of Sanders. The argument has a similar inductive structure to that used to establish (i) (and if one is willing to replace by then the argument is in fact relatively straightforward and does not need any deep partial results on the PFR).
As one byproduct of our analysis we also obtain an appealing entropic reformulation of Conjecture 2, namely that if is an -valued random variable then there exists a subspace of such that
Right now the best result in this direction is
for any , by using Konyagin’s partial result towards the PFR.
What’s new • Read More
-
0 Replies
Sorry, there were no replies found.
Log in to reply.