Tag Archive

You are currently browsing the tag archive for the ‘Freddie Manners’ tag.

An abridged proof of Marton’s conjecture

22 June, 2024 in expository, math.CO | Tags: Ben Green, Freddie Manners, Luca Trevisan, Polynomial Freiman-Ruzsa conjecture, Shannon entropy, Timothy Gowers | by Terence Tao | 18 comments

[This post is dedicated to Luca Trevisan, who recently passed away due to cancer. Though far from his most significant contribution to the field, I would like to mention that, as with most of my other blog posts on this site, this page was written with the assistance of Luca’s LaTeX to WordPress converter. Mathematically, his work and insight on pseudorandomness in particular have greatly informed how I myself think about the concept. – T.]

Recently, Timothy Gowers, Ben Green, Freddie Manners, and I were able to establish the following theorem:

Theorem 1 (Marton’s conjecture) Let ${A \subset {\bf F}_2^n}$ be non-empty with ${|A+A| \leq K|A|}$ . Then there exists a subgroup ${H}$ of ${{\bf F}_2^n}$ with ${|H| \leq |A|}$ such that ${A}$ is covered by at most ${2K^C}$ translates of ${H}$ , for some absolute constant ${C}$ .

We established this result with ${C=12}$ , although it has since been improved to ${C=9}$ by Jyun-Jie Liao.

Our proof was written in order to optimize the constant ${C}$ as much as possible; similarly for the more detailed blueprint of the proof that was prepared in order to formalize the result in Lean. I have been asked a few times whether it is possible to present a streamlined and more conceptual version of the proof in which one does not try to establish an explicit constant ${C}$ , but just to show that the result holds for some constant ${C}$ . This is what I will attempt to do in this post, though some of the more routine steps will be outsourced to the aforementioned blueprint.

The key concept here is that of the entropic Ruzsa distance ${d[X;Y]}$ between two random variables ${X,Y}$ taking values ${{\bf F}_2^n}$ , defined as

$\displaystyle d[X;Y] := {\mathbf H}[X'+Y'] - \frac{1}{2} {\mathbf H}[X] - \frac{1}{2} {\mathbf H}[Y]$

where ${X',Y'}$ are independent copies of ${X,Y}$ , and ${{\mathbf H}[X]}$ denotes the Shannon entropy of ${X}$ . This distance is symmetric and non-negative, and obeys the triangle inequality

$\displaystyle d[X;Z] \leq d[X;Y] + d[Y;Z]$

for any random variables ${X,Y,Z}$ ; see the blueprint for a proof. The above theorem then follows from an entropic analogue:

Theorem 2 (Entropic Marton’s conjecture) Let ${X}$ be a ${{\bf F}_2^n}$ -valued random variable with ${d[X;X] \leq \log K}$ . Then there exists a uniform random variable ${U_H}$ on a subgroup ${H}$ of ${{\bf F}_2^n}$ such that ${d[X; U_H] \leq C \log K}$ for some absolute constant ${C}$ .

We were able to establish Theorem 2 with ${C=11}$ , which implies Theorem 1 with ${C=12}$ by fairly standard additive combinatorics manipulations (such as the Ruzsa covering lemma); see the blueprint for details.

The key proposition needed to establish Theorem 2 is the following distance decrement property:

Proposition 3 (Distance decrement) If ${X,Y}$ are ${{\bf F}_2^n}$ -valued random variables, then one can find ${{\bf F}_2^n}$ -valued random variables ${X',Y'}$ such that
$\displaystyle d[X';Y'] \leq (1-\eta) d[X;Y]$
and
$\displaystyle d[X;X'], d[Y,Y'] \leq C d[X;Y]$
for some absolute constants ${C, \eta > 0}$ .

Indeed, suppose this proposition held. Starting with ${X,Y}$ both equal to ${X}$ and iterating, one can then find sequences of random variables ${X_n, Y_n}$ with ${X_0=Y_0=X}$ ,

$\displaystyle d[X_n;Y_n] \leq (1-\eta)^n d[X;X],$

and

$\displaystyle d[X_{n+1};X_n], d[Y_{n+1};Y_n] \leq C (1-\eta)^n d[X;X].$

In particular, from the triangle inequality and geometric series

$\displaystyle d[X_n;X], d[Y_n;X] \leq \frac{C}{\eta} d[X;X].$

By weak compactness, some subsequence of the ${X_n}$ , ${Y_n}$ converge to some limiting random variables ${X_\infty, Y_\infty}$ , and by some simple continuity properties of entropic Ruzsa distance, we conclude that

$\displaystyle d[X_\infty;Y_\infty] = 0$

and

$\displaystyle d[X_\infty;X], d[Y_\infty;X] \leq \frac{C}{\eta} d[X;X].$

Theorem 2 then follows from the “100% inverse theorem” for entropic Ruzsa distance; see the blueprint for details.

To prove Proposition 3, we can reformulate it as follows:

Proposition 4 (Lack of distance decrement implies vanishing) If ${X,Y}$ are ${{\bf F}_2^n}$ -valued random variables, with the property that
$\displaystyle d[X';Y'] > d[X;Y] - \eta ( d[X;Y] + d[X';X] + d[Y',Y] ) \ \ \ \ \ (1)$
for all ${{\bf F}_2^n}$ -valued random variables ${X',Y'}$ and some sufficiently small absolute constant ${\eta > 0}$ , then one can derive a contradiction.

Indeed, we may assume from the above proposition that

$\displaystyle d[X';Y'] \leq d[X;Y] - \eta ( d[X; Y] + d[X';X] + d[Y',Y] )$

for some ${X',Y'}$ , which will imply Proposition 3 with ${C = 1/\eta}$ .

The entire game is now to use Shannon entropy inequalities and “entropic Ruzsa calculus” to deduce a contradiction from (1) for ${\eta}$ small enough. This we will do below the fold, but before doing so, let us first make some adjustments to (1) that will make it more useful for our purposes. Firstly, because conditional entropic Ruzsa distance (see blueprint for definitions) is an average of unconditional entropic Ruzsa distance, we can automatically upgrade (1) to the conditional version

$\displaystyle d[X'|Z;Y'|W] \geq d[X;Y] - \eta ( d[X;Y] + d[X'|Z;X] + d[Y'|W;Y] )$

for any random variables ${Z,W}$ that are possibly coupled with ${X',Y'}$ respectively. In particular, if we define a “relevant” random variable ${X'}$ (conditioned with respect to some auxiliary data ${Z}$ ) to be a random variable for which

$\displaystyle d[X'|Z;X] = O( d[X;Y] )$

or equivalently (by the triangle inequality)

$\displaystyle d[X'|Z;Y] = O( d[X;Y] )$

then we have the useful lower bound

$\displaystyle d[X'|Z;Y'|W] \geq (1-O(\eta)) d[X;Y] \ \ \ \ \ (2)$

whenever ${X'}$ and ${Y'}$ are relevant conditioning on ${Z, W}$ respectively. This is quite a useful bound, since the laws of “entropic Ruzsa calculus” will tell us, roughly speaking, that virtually any random variable that we can create from taking various sums of copies of ${X,Y}$ and conditioning against other sums, will be relevant. (Informally: the space of relevant random variables is ${(1-O(\eta))d[X;Y]}$ -separated with respect to the entropic Ruzsa distance.)

— 1. Main argument —

Now we derive more and more consequences of (2) – at some point crucially using the hypothesis that we are in characteristic two – before we reach a contradiction.

Right now, our hypothesis (2) only supplies lower bounds on entropic distances. The crucial ingredient that allows us to proceed is what we call the fibring identity, which lets us convert these lower bounds into useful upper bounds as well, which in fact match up very nicely when ${\eta}$ is small. Informally, the fibring identity captures the intuitive fact that the doubling constant of a set ${A}$ should be at least as large as the doubling constant of the image ${\pi(A)}$ of that set under a homomorphism, times the doubling constant of a typical fiber ${A \cap \pi^{-1}(\{z\})}$ of that homomorphism; and furthermore, one should only be close to equality if the fibers “line up” in some sense.

Here is the fibring identity:

Proposition 5 (Fibring identity) Let ${\pi: G \rightarrow H}$ be a homomorphism. Then for any independent ${G}$ -valued random variables ${X, Y}$ , one has
$\displaystyle d[X;Y] = d[\pi(X); \pi(Y)] + d[X|\pi(X); Y|\pi(Y)]$

$\displaystyle + I[X-Y : \pi(X),\pi(Y) | \pi(X)-\pi(Y) ].$

The proof is of course in the blueprint, but given that it is a central pillar of the argument, I reproduce it here.

Proof: Expanding out the definition of Ruzsa distance, and using the conditional entropy chain rule

$\displaystyle {\mathbf H}[X] = {\mathbf H}[\pi(X)] + {\mathbf H}[X|\pi(X)]$

and

$\displaystyle {\mathbf H}[Y] = {\mathbf H}[\pi(Y)] + {\mathbf H}[Y|\pi(Y)],$

it suffices to establish the identity

$\displaystyle {\mathbf H}[X-Y] = {\mathbf H}[\pi(X)-\pi(Y)] + {\mathbf H}[X - Y|\pi(X), \pi(Y)]$

$\displaystyle + I[X-Y : \pi(X),\pi(Y) | \pi(X)-(Y) ].$

But from the chain rule again we have

$\displaystyle {\mathbf H}[X-Y] = {\mathbf H}[\pi(X)-\pi(Y)] + {\mathbf H}[X - Y|\pi(X)-\pi(Y)]$

and from the definition of conditional mutual information (using the fact that ${\pi(X)-\pi(Y)}$ is determined both by ${X-Y}$ and by ${(\pi(X),\pi(Y))}$ ) one has

$\displaystyle {\mathbf H}[X - Y|\pi(X)-\pi(Y)] = {\mathbf H}[X - Y|\pi(X), \pi(Y)]$

$\displaystyle + I[X-Y : \pi(X),\pi(Y) | \pi(X)-(Y) ]$

giving the claim. $\Box$

We will only care about the characteristic ${2}$ setting here, so we will now assume that all groups involved are ${2}$ -torsion, so that we can replace all subtractions with additions. If we specialize the fibring identity to the case where ${G = {\bf F}_2^n \times {\bf F}_2^n}$ , ${H = {\bf F}_2^n}$ , ${\pi: G \rightarrow H}$ is the addition map ${\pi(x,y) = x+y}$ , and ${X = (X_1, X_2)}$ , ${Y = (Y_1, Y_2)}$ are pairs of independent random variables in ${{\bf F}_2^n}$ , we obtain the following corollary:

Corollary 6 Let ${X_1,X_2,Y_1,Y_2}$ be independent ${{\bf F}_2^n}$ -valued random variables. Then we have the identity
$\displaystyle d[X_1;Y_1] + d[X_2;Y_2] = d[X_1+X_2;Y_1+Y_2]$

$\displaystyle + d[X_1|X_1+X_2;Y_1|Y_1+Y_2]$

$\displaystyle + I[(X_1+Y_1, X_2+Y_2) : (X_1+X_2,Y_1+Y_2) | X_1+X_2+Y_1+Y_2 ].$

This is a useful and flexible identity, especially when combined with (2). For instance, we can discard the conditional mutual information term as being non-negative, to obtain the inequality

$\displaystyle d[X_1;Y_1] + d[X_2;Y_2] \geq d[X_1+X_2;Y_1+Y_2]$

$\displaystyle + d[X_1|X_1+X_2;Y_1|Y_1+Y_2].$

If we let ${X_1, Y_1, X_2, Y_2}$ be independent copies of ${X, Y, Y, X}$ respectively (note the swap in the last two variables!) we obtain

$\displaystyle 2 d[X;Y] \geq d[X+Y;X+Y] + d[X_1|X_1+X_2;Y_1|Y_1+Y_2].$

From entropic Ruzsa calculus, one can check that ${X+Y}$ , ${X_1|X_1+X_2}$ , and ${Y_1|Y_1+Y_2}$ are all relevant random variables, so from (2) we now obtain both upper and lower bounds for ${d[X+Y;X+Y]}$ :

$\displaystyle d[X+Y; X+Y] = (1 + O(\eta)) d[X;Y].$

A pleasant upshot of this is that we now get to work in the symmetric case ${X=Y}$ without loss of generality. Indeed, if we set ${X^* := X+Y}$ , we now have from (2) that

$\displaystyle d[X'|Z; Y'|W] \geq (1-O(\eta)) d[X^*;X^*] \ \ \ \ \ (3)$

whenever ${X'|Z, Y'|W}$ are relevant, which by entropic Ruzsa calculus is equivalent to asking that

$\displaystyle d[X'|Z; X^*], d[Y'|W; X^*] = O(d[X^*;X^*]).$

Now we use the fibring identity again, relabeling ${Y_1,Y_2}$ as ${X_3,X_4}$ and requiring ${X_1,X_2,X_3,X_4}$ to be independent copies of ${X^*}$ . We conclude that

$\displaystyle 2d[X^*; X^*] = d[X_1+X_2;X_3+Y_4] + d[X_1|X_1+X_2;X_3|X_1+X_4]$

$\displaystyle + I[(X_1+X_3, X_2+X_4) : (X_1+X_2,X_3+X_4) | X_1+X_2+X_3+X_4 ].$

As before, the random variables ${X_1+X_2}$ , ${X_3+X_4}$ , ${X_1|X_1+X_2}$ , ${X_3|X_3+X_4}$ are all relevant, so from (3) we have

$\displaystyle d[X_1+X_2;X_3+X_4], d[X_1|X_1+X_2;X_3|X_1+X_4]$

$\displaystyle \geq (1-O(\eta)) d[X^*;X^*].$

We could now also match these lower bounds with upper bounds, but the more important takeaway from this analysis is a really good bound on the conditional mutual information:

$\displaystyle I[(X_1+X_3, X_2+X_4) : (X_1+X_2,X_3+X_4) | X_1+X_2+X_3+X_4 ]$

$\displaystyle = O(\eta) d[X^*;X^*].$

By the data processing inequality, we can discard some of the randomness here, and conclude

$\displaystyle I[X_1+X_3 : X_1+X_2 | X_1+X_2+X_3+X_4 ] = O(\eta) d[X^*;X^*].$

Let us introduce the random variables

$\displaystyle S := X_1+X_2+X_3+X_4; U := X_1+X_2; V = X_1 + X_3$

then we have

$\displaystyle I[U : V | S] = O(\eta) d[X^*;X^*].$

Intuitively, this means that ${U}$ and ${V}$ are very nearly independent given ${S}$ . For sake of argument, let us assume that they are actually independent; one can achieve something resembling this by invoking the entropic Balog-Szemerédi-Gowers theorem, established in the blueprint, after conceding some losses of ${O(\eta) d[X^*,X^*]}$ in the entropy, but we skip over the details for this blog post. The key point now is that because we are in characteristic ${2}$ , ${U+V}$ has the same form as ${U}$ or ${V}$ :

$\displaystyle U + V = X_2 + X_3.$

In particular, by permutation symmetry, we have

$\displaystyle {\mathbf H}[U+V|S] ={\mathbf H}[U|S] ={\mathbf H}[V|S],$

and so by the definition of conditional Ruzsa distance we have a massive distance decrement

$\displaystyle {\bf E}_s d[U|S=s; V|S=s] = 0,$

(where ${s}$ is drawn from the distribution of ${S}$ ), contradicting (1) as desired. (In reality, we end up decreasing the distance not all the way to zero, but instead to ${O(\eta d[X^*,X^*])}$ due to losses in the Balog-Szemerédi-Gowers theorem, but this is still enough to reach a contradiction. The quantity ${{\bf E}_s d[U|S=s; V|S=s]}$ is very similar to ${d[U|S; V|S]}$ , but is slightly different; the latter quantity is ${{\bf E}_{s,s'}d[U|S=s; V|S=s']}$ .)

Remark 7 A similar argument works in the ${m}$ -torsion case for general ${m}$ . Instead of decrementing the entropic Ruzsa distance, one instead decrements a “multidistance”
$\displaystyle {\mathbf H}[X_1 + \dots + X_m] - \frac{1}{m} ({\mathbf H}[X_1] + \dots + {\mathbf H}[X_m])$
for independent ${X_1,\dots,X_m}$ . By an iterated version of the fibring identity, one can first reduce again to the symmetric case where the random variables are all copies of the same variable ${X^*}$ . If one then takes ${X_{i,j}}$ , ${i,j=1,\dots,m}$ to be an array of ${m^2}$ copies of ${X^*}$ , one can get to the point where the row sums ${\sum_i X_{i,j}}$ and the column sums ${\sum_j X_{i,j}}$ have small conditional mutual information with respect to the double sum ${S := \sum_i \sum_j X_{i,j}}$ . If we then set ${U := \sum_i \sum_j j X_{i,j}}$ and ${V := \sum_i \sum_j i X_{i,j}}$ , the data processing inequality again shows that ${U}$ and ${V}$ are nearly independent given ${S}$ . The ${m}$ -torsion now crucially intervenes as before to ensure that ${U+V = \sum_i \sum_j (i+j) X_{i,j}}$ has the same form as ${U}$ or ${V}$ , leading to a contradiction as before. See this previous blog post for more discussion.

Marton’s conjecture in abelian groups with bounded torsion

4 April, 2024 in math.CO, paper | Tags: additive combinatorics, Ben Green, Freddie Manners, Polynomial Freiman-Ruzsa conjecture, Shannon entropy, Timothy Gowers | by Terence Tao | 14 comments

Tim Gowers, Ben Green, Freddie Manners, and I have just uploaded to the arXiv our paper “Marton’s conjecture in abelian groups with bounded torsion“. This paper fully resolves a conjecture of Katalin Marton (the bounded torsion case of the Polynomial Freiman–Ruzsa conjecture (first proposed by Katalin Marton):

Theorem 1 (Marton’s conjecture) Let ${G = (G,+)}$ be an abelian ${m}$ -torsion group (thus, ${mx=0}$ for all ${x \in G}$ ), and let ${A \subset G}$ be such that ${|A+A| \leq K|A|}$ . Then ${A}$ can be covered by at most ${(2K)^{O(m^3)}}$ translates of a subgroup ${H}$ of ${G}$ of cardinality at most ${|A|}$ . Moreover, ${H}$ is contained in ${\ell A - \ell A}$ for some ${\ell \ll (2 + m \log K)^{O(m^3 \log m)}}$ .

We had previously established the ${m=2}$ case of this result, with the number of translates bounded by ${(2K)^{12}}$ (which was subsequently improved to ${(2K)^{11}}$ by Jyun-Jie Liao), but without the additional containment ${H \subset \ell A - \ell A}$ . It remains a challenge to replace ${\ell}$ by a bounded constant (such as ${2}$ ); this is essentially the “polynomial Bogolyubov conjecture”, which is still open. The ${m=2}$ result has been formalized in the proof assistant language Lean, as discussed in this previous blog post. As a consequence of this result, many of the applications of the previous theorem may now be extended from characteristic ${2}$ to higher characteristic.

Our proof techniques are a modification of those in our previous paper, and in particular continue to be based on the theory of Shannon entropy. For inductive purposes, it turns out to be convenient to work with the following version of the conjecture (which, up to ${m}$ -dependent constants, is actually equivalent to the above theorem):

Theorem 2 (Marton’s conjecture, entropy form) Let ${G}$ be an abelian ${m}$ -torsion group, and let ${X_1,\dots,X_m}$ be independent finitely supported random variables on ${G}$ , such that
$\displaystyle {\bf H}[X_1+\dots+X_m] - \frac{1}{m} \sum_{i=1}^m {\bf H}[X_i] \leq \log K,$
where ${{\bf H}}$ denotes Shannon entropy. Then there is a uniform random variable ${U_H}$ on a subgroup ${H}$ of ${G}$ such that
$\displaystyle \frac{1}{m} \sum_{i=1}^m d[X_i; U_H] \ll m^3 \log K,$
where ${d}$ denotes the entropic Ruzsa distance (see previous blog post for a definition); furthermore, if all the ${X_i}$ take values in some symmetric set ${S}$ , then ${H}$ lies in ${\ell S}$ for some ${\ell \ll (2 + \log K)^{O(m^3 \log m)}}$ .

As a first approximation, one should think of all the ${X_i}$ as identically distributed, and having the uniform distribution on ${A}$ , as this is the case that is actually relevant for implying Theorem 1; however, the recursive nature of the proof of Theorem 2 requires one to manipulate the ${X_i}$ separately. It also is technically convenient to work with ${m}$ independent variables, rather than just a pair of variables as we did in the ${m=2}$ case; this is perhaps the biggest additional technical complication needed to handle higher characteristics.

The strategy, as with the previous paper, is to attempt an entropy decrement argument: to try to locate modifications ${X'_1,\dots,X'_m}$ of ${X_1,\dots,X_m}$ that are reasonably close (in Ruzsa distance) to the original random variables, while decrementing the “multidistance”

$\displaystyle {\bf H}[X_1+\dots+X_m] - \frac{1}{m} \sum_{i=1}^m {\bf H}[X_i]$

which turns out to be a convenient metric for progress (for instance, this quantity is non-negative, and vanishes if and only if the ${X_i}$ are all translates of a uniform random variable ${U_H}$ on a subgroup ${H}$ ). In the previous paper we modified the corresponding functional to minimize by some additional terms in order to improve the exponent ${12}$ , but as we are not attempting to completely optimize the constants, we did not do so in the current paper (and as such, our arguments here give a slightly different way of establishing the ${m=2}$ case, albeit with somewhat worse exponents).

As before, we search for such improved random variables ${X'_1,\dots,X'_m}$ by introducing more independent random variables – we end up taking an array of ${m^2}$ random variables ${Y_{i,j}}$ for ${i,j=1,\dots,m}$ , with each ${Y_{i,j}}$ a copy of ${X_i}$ , and forming various sums of these variables and conditioning them against other sums. Thanks to the magic of Shannon entropy inequalities, it turns out that it is guaranteed that at least one of these modifications will decrease the multidistance, except in an “endgame” situation in which certain random variables are nearly (conditionally) independent of each other, in the sense that certain conditional mutual informations are small. In particular, in the endgame scenario, the row sums ${\sum_j Y_{i,j}}$ of our array will end up being close to independent of the column sums ${\sum_i Y_{i,j}}$ , subject to conditioning on the total sum ${\sum_{i,j} Y_{i,j}}$ . Not coincidentally, this type of conditional independence phenomenon also shows up when considering row and column sums of iid independent gaussian random variables, as a specific feature of the gaussian distribution. It is related to the more familiar observation that if ${X,Y}$ are two independent copies of a Gaussian random variable, then ${X+Y}$ and ${X-Y}$ are also independent of each other.

Up until now, the argument does not use the ${m}$ -torsion hypothesis, nor the fact that we work with an ${m \times m}$ array of random variables as opposed to some other shape of array. But now the torsion enters in a key role, via the obvious identity

$\displaystyle \sum_{i,j} i Y_{i,j} + \sum_{i,j} j Y_{i,j} + \sum_{i,j} (-i-j) Y_{i,j} = 0.$

In the endgame, the any pair of these three random variables are close to independent (after conditioning on the total sum ${\sum_{i,j} Y_{i,j}}$ ). Applying some “entropic Ruzsa calculus” (and in particular an entropic version of the Balog–Szeméredi–Gowers inequality), one can then arrive at a new random variable ${U}$ of small entropic doubling that is reasonably close to all of the ${X_i}$ in Ruzsa distance, which provides the final way to reduce the multidistance.

Besides the polynomial Bogoluybov conjecture mentioned above (which we do not know how to address by entropy methods), the other natural question is to try to develop a characteristic zero version of this theory in order to establish the polynomial Freiman–Ruzsa conjecture over torsion-free groups, which in our language asserts (roughly speaking) that random variables of small entropic doubling are close (in Ruzsa distance) to a discrete Gaussian random variable, with good bounds. The above machinery is consistent with this conjecture, in that it produces lots of independent variables related to the original variable, various linear combinations of which obey the same sort of entropy estimates that gaussian random variables would exhibit, but what we are missing is a way to get back from these entropy estimates to an assertion that the random variables really are close to Gaussian in some sense. In continuous settings, Gaussians are known to extremize the entropy for a given variance, and of course we have the central limit theorem that shows that averages of random variables typically converge to a Gaussian, but it is not clear how to adapt these phenomena to the discrete Gaussian setting (without the circular reasoning of assuming the polynoimal Freiman–Ruzsa conjecture to begin with).

On a conjecture of Marton

13 November, 2023 in math.CO, paper | Tags: additive combinatorics, Ben Green, Freddie Manners, Freiman's theorem, Polynomial Freiman-Ruzsa conjecture, Shannon entropy | by Terence Tao | 35 comments

Tim Gowers, Ben Green, Freddie Manners, and I have just uploaded to the arXiv our paper “On a conjecture of Marton“. This paper establishes a version of the notorious Polynomial Freiman–Ruzsa conjecture (first proposed by Katalin Marton):

Theorem 1 (Polynomial Freiman–Ruzsa conjecture) Let ${A \subset {\bf F}_2^n}$ be such that ${|A+A| \leq K|A|}$ . Then ${A}$ can be covered by at most ${2K^{12}}$ translates of a subspace ${H}$ of ${{\bf F}_2^n}$ of cardinality at most ${A}$ .

The previous best known result towards this conjecture was by Konyagin (as communicated in this paper of Sanders), who obtained a similar result but with ${2K^{12}}$ replaced by ${\exp(O_\varepsilon(\log^{3+\varepsilon} K))}$ for any ${\varepsilon>0}$ (assuming that say ${K \geq 3/2}$ to avoid some degeneracies as ${K}$ approaches ${1}$ , which is not the difficult case of the conjecture). The conjecture (with ${12}$ replaced by an unspecified constant ${C}$ ) has a number of equivalent forms; see this survey of Green, and these papers of Lovett and of Green and myself for some examples; in particular, as discussed in the latter two references, the constants in the inverse ${U^3({\bf F}_2^n)}$ theorem are now polynomial in nature (although we did not try to optimize the constant).

The exponent ${12}$ here was the product of a large number of optimizations to the argument (our original exponent here was closer to ${1000}$ ), but can be improved even further with additional effort (our current argument, for instance, allows one to replace it with ${7+\sqrt{17} = 11.123\dots}$ , but we decided to state our result using integer exponents instead).

In this paper we will focus exclusively on the characteristic ${2}$ case (so we will be cavalier in identifying addition and subtraction), but in a followup paper we will establish similar results in other finite characteristics.

Much of the prior progress on this sort of result has proceeded via Fourier analysis. Perhaps surprisingly, our approach uses no Fourier analysis whatsoever, being conducted instead entirely in “physical space”. Broadly speaking, it follows a natural strategy, which is to induct on the doubling constant ${|A+A|/|A|}$ . Indeed, suppose for instance that one could show that every set ${A}$ of doubling constant ${K}$ was “commensurate” in some sense to a set ${A'}$ of doubling constant at most ${K^{0.99}}$ . One measure of commensurability, for instance, might be the Ruzsa distance ${\log \frac{|A+A'|}{|A|^{1/2} |A'|^{1/2}}}$ , which one might hope to control by ${O(\log K)}$ . Then one could iterate this procedure until doubling constant dropped below say ${3/2}$ , at which point the conjecture is known to hold (there is an elementary argument that if ${A}$ has doubling constant less than ${3/2}$ , then ${A+A}$ is in fact a subspace of ${{\bf F}_2^n}$ ). One can then use several applications of the Ruzsa triangle inequality

$\displaystyle \log \frac{|A+C|}{|A|^{1/2} |C|^{1/2}} \leq \log \frac{|A+B|}{|A|^{1/2} |B|^{1/2}} + \log \frac{|B+C|}{|B|^{1/2} |C|^{1/2}}$

to conclude (the fact that we reduce ${K}$ to ${K^{0.99}}$ means that the various Ruzsa distances that need to be summed are controlled by a convergent geometric series).

There are a number of possible ways to try to “improve” a set ${A}$ of not too large doubling by replacing it with a commensurate set of better doubling. We note two particular potential improvements:

(i) Replacing ${A}$ with ${A+A}$ . For instance, if ${A}$ was a random subset (of density ${1/K}$ ) of a large subspace ${H}$ of ${{\bf F}_2^n}$ , then replacing ${A}$ with ${A+A}$ usually drops the doubling constant from ${K}$ down to nearly ${1}$ (under reasonable choices of parameters).
(ii) Replacing ${A}$ with ${A \cap (A+h)}$ for a “typical” ${h \in A+A}$ . For instance, if ${A}$ was the union of ${K}$ random cosets of a subspace ${H}$ of large codimension, then replacing ${A}$ with ${A \cap (A+h)}$ again usually drops the doubling constant from ${K}$ down to nearly ${1}$ .

Unfortunately, there are sets ${A}$ where neither of the above two operations (i), (ii) significantly improves the doubling constant. For instance, if ${A}$ is a random density ${1/\sqrt{K}}$ subset of ${\sqrt{K}}$ random translates of a medium-sized subspace ${H}$ , one can check that the doubling constant stays close to ${K}$ if one applies either operation (i) or operation (ii). But in this case these operations don’t actually worsen the doubling constant much either, and by applying some combination of (i) and (ii) (either intersecting ${A+A}$ with a translate, or taking a sumset of ${A \cap (A+h)}$ with itself) one can start lowering the doubling constant again.

This begins to suggest a potential strategy: show that at least one of the operations (i) or (ii) will improve the doubling constant, or at least not worsen it too much; and in the latter case, perform some more complicated operation to locate the desired doubling constant improvement.

A sign that this strategy might have a chance of working is provided by the following heuristic argument. If ${A}$ has doubling constant ${K}$ , then the Cartesian product ${A \times A}$ has doubling constant ${K^2}$ . On the other hand, by using the projection map ${\pi: {\bf F}_2^n \times {\bf F}_2^n \rightarrow {\bf F}_2^n}$ defined by ${\pi(x,y) := x+y}$ , we see that ${A \times A}$ projects to ${\pi(A \times A) = A+A}$ , with fibres ${\pi^{-1}(\{h\})}$ being essentially a copy of ${A \cap (A+h)}$ . So, morally, ${A \times A}$ also behaves like a “skew product” of ${A+A}$ and the fibres ${A \cap (A+h)}$ , which suggests (non-rigorously) that the doubling constant ${K^2}$ of ${A \times A}$ is also something like the doubling constant of ${A + A}$ , times the doubling constant of a typical fibre ${A \cap (A+h)}$ . This would imply that at least one of ${A +A}$ and ${A \cap (A+h)}$ would have doubling constant at most ${K}$ , and thus that at least one of operations (i), (ii) would not worsen the doubling constant.

Unfortunately, this argument does not seem to be easily made rigorous using the traditional doubling constant; even the significantly weaker statement that ${A+A}$ has doubling constant at most ${K^2}$ is false (see comments for more discussion). However, it turns out (as discussed in this recent paper of myself with Green and Manners) that things are much better. Here, the analogue of a subset ${A}$ in ${{\bf F}_2^n}$ is a random variable ${X}$ taking values in ${{\bf F}_2^n}$ , and the analogue of the (logarithmic) doubling constant ${\log \frac{|A+A|}{|A|}}$ is the entropic doubling constant ${d(X;X) := {\bf H}(X_1+X_2)-{\bf H}(X)}$ , where ${X_1,X_2}$ are independent copies of ${X}$ . If ${X}$ is a random variable in some additive group ${G}$ and ${\pi: G \rightarrow H}$ is a homomorphism, one then has what we call the fibring inequality

$\displaystyle d(X;X) \geq d(\pi(X);\pi(X)) + d(X|\pi(X); X|\pi(X)),$

where the conditional doubling constant ${d(X|\pi(X); X|\pi(X))}$ is defined as

$\displaystyle d(X|\pi(X); X|\pi(X)) = {\bf H}(X_1 + X_2 | \pi(X_1), \pi(X_2)) - {\bf H}( X | \pi(X) ).$

Indeed, from the chain rule for Shannon entropy one has

$\displaystyle {\bf H}(X) = {\bf H}(\pi(X)) + {\bf H}(X|\pi(X))$

and

$\displaystyle {\bf H}(X_1+X_2) = {\bf H}(\pi(X_1) + \pi(X_2)) + {\bf H}(X_1 + X_2|\pi(X_1) + \pi(X_2))$

while from the non-negativity of conditional mutual information one has

$\displaystyle {\bf H}(X_1 + X_2|\pi(X_1) + \pi(X_2)) \geq {\bf H}(X_1 + X_2|\pi(X_1), \pi(X_2))$

and it is an easy matter to combine all these identities and inequalities to obtain the claim.

Applying this inequality with ${X}$ replaced by two independent copies ${(X_1,X_2)}$ of itself, and using the addition map ${(x,y) \mapsto x+y}$ for ${\pi}$ , we obtain in particular that

$\displaystyle 2 d(X;X) \geq d(X_1+X_2; X_1+X_2) + d(X_1,X_2|X_1+X_2; X_1,X_2|X_1+X_2)$

or (since ${X_2}$ is determined by ${X_1}$ once one fixes ${X_1+X_2}$ )

$\displaystyle 2 d(X;X) \geq d(X_1+X_2; X_1+X_2) + d(X_1|X_1+X_2; X_1|X_1+X_2).$

So if ${d(X;X) = \log K}$ , then at least one of ${d(X_1+X_2; X_1+X_2)}$ or ${d(X_1|X_1+X_2; X_1|X_1+X_2)}$ will be less than or equal to ${\log K}$ . This is the entropy analogue of at least one of (i) or (ii) improving, or at least not degrading the doubling constant, although there are some minor technicalities involving how one deals with the conditioning to ${X_1+X_2}$ in the second term ${d(X_1|X_1+X_2; X_1|X_1+X_2)}$ that we will gloss over here (one can pigeonhole the instances of ${X_1}$ to different events ${X_1+X_2=x}$ , ${X_1+X_2=x'}$ , and “depolarise” the induction hypothesis to deal with distances ${d(X;Y)}$ between pairs of random variables ${X,Y}$ that do not necessarily have the same distribution). Furthermore, we can even calculate the defect in the above inequality: a careful inspection of the above argument eventually reveals that

$\displaystyle 2 d(X;X) = d(X_1+X_2; X_1+X_2) + d(X_1|X_1+X_2; X_1|X_1+X_2)$

$\displaystyle + {\bf I}( X_1 + X_2 : X_1 + X_3 | X_1 + X_2 + X_3 + X_4)$

where we now take four independent copies ${X_1,X_2,X_3,X_4}$ . This leads (modulo some technicalities) to the following interesting conclusion: if neither (i) nor (ii) leads to an improvement in the entropic doubling constant, then ${X_1+X_2}$ and ${X_2+X_3}$ are conditionally independent relative to ${X_1+X_2+X_3+X_4}$ . This situation (or an approximation to this situation) is what we refer to in the paper as the “endgame”.

A version of this endgame conclusion is in fact valid in any characteristic. But in characteristic ${2}$ , we can take advantage of the identity

$\displaystyle (X_1+X_2) + (X_2+X_3) = X_1 + X_3.$

Conditioning on ${X_1+X_2+X_3+X_4}$ , and using symmetry we now conclude that if we are in the endgame exactly (so that the mutual information is zero), then the independent sum of two copies of ${(X_1+X_2|X_1+X_2+X_3+X_4)}$ has exactly the same distribution; in particular, the entropic doubling constant here is zero, which is certainly a reduction in the doubling constant.

To deal with the situation where the conditional mutual information is small but not completely zero, we have to use an entropic version of the Balog-Szemeredi-Gowers lemma, but fortunately this was already worked out in an old paper of mine (although in order to optimise the final constant, we ended up using a slight variant of that lemma).

I am planning to formalize this paper in the Lean4 language. Further discussion of this project will take place on this Zulip stream, and the project itself will be held at this Github repository.

Sumsets and entropy revisited

27 June, 2023 in math.CO, paper | Tags: Ben Green, entropy, Freddie Manners, Polynomial Freiman-Ruzsa conjecture | by Terence Tao | 13 comments

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 ${Z}$ ) Let ${A \subset {\bf Z}^D}$ be a finite non-empty set whose doubling constant ${\sigma[A] := |A+A|/|A|}$ is at most ${K}$ . Then there is a subset ${A'}$ of ${A}$ of density ${\gg K^{-O(1)}}$ that has affine dimension ${O(\log K)}$ (i.e., it is contained in an affine space of dimension ${O(\log K)}$ ).

Conjecture 2 (PFR over ${{\bf F}_2}$ ) Let ${A \subset {\bf F}_2^D}$ be a non-empty set whose doubling constant ${\sigma[A]}$ is at most ${K}$ . Then ${A}$ can be covered by ${O(K^{O(1)})}$ cosets of a subspace of cardinality at most ${|A|}$ .

Our main results are then as follows.

Theorem 3 If ${A \subset {\bf Z}^D}$ with ${\sigma[A] \leq K}$ , then

(i) There is a subset ${A'}$ of ${A}$ of density ${\gg K^{-O(1)}}$ of “skew-dimension” (or “query complexity”) ${O(\log K)}$ .
(ii) There is a subset ${A'}$ of ${A}$ of density ${\gg \exp( -O(\log^{5/3+o(1)} K) )}$ of affine dimension ${O(\log K)}$ (where ${o(1)}$ goes to zero as ${K \rightarrow \infty}$ ).
(iii) If Conjecture 2 holds, then there is a subset ${A'}$ of ${A}$ of density ${\gg K^{-O(1)}}$ of affine dimension ${O(\log K)}$ . 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 ${0}$ , and a set ${A \subset {\bf Z}^{D_1} \times {\bf Z}^{D_2}}$ whose projection to ${{\bf Z}^{D_1}}$ has skew-dimension at most ${d_1}$ , and whose fibers in ${\{x\} \times {\bf Z}^{D_2}}$ have skew-dimension at most ${d_2}$ for any ${x}$ , will have skew-dimension at most ${d_1+d_2}$ . (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 ${5/3+o(1)}$ replaced by ${2}$ 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 ${A}$ with random variables ${X}$ , 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 ${\sigma[A] := |A+A|/|A|}$ of a finite non-empty subset ${A}$ of an abelian group ${G}$ , is the entropy doubling constant

$\displaystyle \sigma_{\mathrm{ent}}[X] := {\exp( \bf H}(X_1+X_2) - {\bf H}(X) )$

of a finitely-valued random variable ${X}$ in ${G}$ , where ${X_1,X_2}$ are independent copies of ${X}$ and ${{\bf H}}$ denotes Shannon entropy. There is also an analogue of the Ruzsa distance

$\displaystyle d(A,B) := \log \frac{|A-B|}{|A|^{1/2} |B|^{1/2}}$

between two finite non-empty subsets ${A,B}$ of ${G}$ , namely the entropic Ruzsa distance

$\displaystyle d_{\mathrm{ent}}(X,Y) := {\bf H}(X'+Y') - \frac{1}{2} {\bf H}(X) - \frac{1}{2} {\bf H}(Y)$

where ${X',Y'}$ are independent copies of ${X,Y}$ 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

$\displaystyle d_{\mathrm{ent}}(\phi(X),\phi(Y)) \leq d_{\mathrm{ent}}(X,Y)$

whenever ${\phi: G \rightarrow H}$ 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 ${X,Y}$ (in which one conditions ${\phi(X)}$ and ${\phi(Y)}$ to be fixed). On the other hand, there are direct connections between the combinatorial and entropic sumset quantities. For instance, if ${U_A}$ is a random variable drawn uniformly from ${A}$ , then

$\displaystyle \sigma_{\mathrm{ent}}[U_A] \leq \sigma[A].$

Thus if ${A}$ has small doubling, then ${U_A}$ has small entropic doubling. In the converse direction, if ${X}$ has small entropic doubling, then ${X}$ is close (in entropic Ruzsa distance) to a uniform random variable ${U_S}$ drawn from a set ${S}$ 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 ${d_{\mathrm{ent}}(X,Y)}$ is sufficiently small, then there exists a finite subgroup ${H}$ of ${G}$ such that

$\displaystyle d_{\mathrm{ent}}(X,U_H), d_{\mathrm{ent}}(Y,U_H) \leq 12 d_{\mathrm{ent}}(X,Y). \ \ \ \ \ (1)$

This result uses the results just mentioned to relate ${X,Y}$ to a set ${S}$ of small doubling, which can then be related to a subgroup ${H}$ 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 ${A,B}$ of ${{\bf Z}^D}$ , one can find subsets ${A' \subset A}$ , ${B' \subset B}$ with

$\displaystyle |A'| |B'| \geq e^{-C d_{\mathrm{ent}}(U_A, U_B)} |A| |B|$

such that ${A', B'}$ have skew-dimension at most ${C d_{\mathrm{ent}}(U_A, U_B)}$ , for some absolute constant ${C}$ . This can be shown by an induction on ${|A||B|}$ (say). One applies a non-trivial coordinate projection ${\pi: {\bf Z}^D \rightarrow {\bf Z}}$ to ${A,B}$ . If ${\pi(U_A)}$ and ${\pi(U_B)}$ are very close in entropic Ruzsa distance, then the 99% inverse theorem shows that these random variables must each concentrate at a point (because ${{\bf Z}}$ has no non-trivial finite subgroups), and can pass to a fiber of these points and use the induction hypothesis. If instead ${\pi(U_A)}$ and ${\pi(U_B)}$ are far apart, then by the behavior of entropy under projections one can show that the fibers of ${A}$ and ${B}$ under ${\pi}$ are closer on average in entropic Ruzsa distance of ${A}$ and ${B}$ 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 ${{\bf Z}^D}$ must be irregularly distributed modulo ${2}$ . A clean formulation of this in entropic language is the inequality

$\displaystyle d_{\mathrm{ent}}(X, 2Y) \leq 5 d_{\mathrm{ent}}(X,Y)$

whenever ${X,Y}$ take values in a torsion-free abelian group such as ${{\bf Z}^D}$ ; 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

$\displaystyle {\bf H}( X \hbox{ mod } 2 ), {\bf H}( Y \hbox{ mod } 2 ) \leq 10 d_{\mathrm{ent}}(X,Y).$

This is the key link between the ${{\bf Z}^D}$ and ${{\bf F}_2^D}$ worlds that is used to prove (ii), (iii): while (iii) relies on the still unproven PFR conjecture over ${{\bf F}_2}$ , (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 ${5/3+o(1)}$ by ${2}$ 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 ${X}$ is an ${{\bf F}_2^D}$ -valued random variable then there exists a subspace ${H}$ of ${{\bf F}_2^D}$ such that

$\displaystyle d_{\mathrm{ent}}(X, U_H) \ll \sigma_{\mathrm{ent}}[X].$

Right now the best result in this direction is

$\displaystyle d_{\mathrm{ent}}(X, U_H) \ll_\varepsilon \sigma_{\mathrm{ent}}[X] + \sigma_{\mathrm{ent}}^{3+\varepsilon}[X]$

for any ${\varepsilon > 0}$ , by using Konyagin’s partial result towards the PFR.

	Anonymous on A digestion of the Jacobian co…
	Anonymous on A digestion of the Jacobian co…
	Anonymous on Career advice
	Vignon Oussa on A partial digestion of the HRT…
	Vignon Oussa on A partial digestion of the HRT…
	jt.vanvelthoven on A partial digestion of the HRT…
	David Speyer on A digestion of the Jacobian co…
	Terence Tao on A partial digestion of the HRT…
	Terence Tao on 285G, Lecture 0: Riemannian ma…
	jmdpark on A partial digestion of the HRT…
	Anonymous on 285G, Lecture 0: Riemannian ma…
	Anonymous on 275A, Notes 2: Product measure…
	Anonymous on Products of consecutive intege…
	Lech Mazur on Sendov’s conjecture for…
	Anonymous on A digestion of the Jacobian co…

Tag Archive

An abridged proof of Marton’s conjecture

Marton’s conjecture in abelian groups with bounded torsion

On a conjecture of Marton

Sumsets and entropy revisited

Recent Comments

Top Posts

Archives

Categories

The Polymath Blog

For commenters