where X 1 , X 2 are independent copies of X. Here, H(X) denotes the Shannon entropy of X, the definition and basic properties of which we review in Appendix A.

If A ⊆ G is a finite non-empty set, by abuse of notation we write 𝜎 ent [A] = 𝜎 ent [U A ], where U A is a uniform random variable drawn from A. For instance, if H is a finite subgroup of G, one can check that 𝜎 ent [H] = 1.

The entropic doubling constant is related to other standard measures of additive structure via the inequalities

Here, 𝜎[A] ∶= |A+A| |A| is the doubling constant of A and

is the additive energy of A.

The second inequality in (1.1) was noted in [20, eq. 10], and we recall the proof in Appendix B. The first inequality seems not to have appeared explicitly in the literature, but it follows easily either by a direct argument using the weighted AM-GM inequality, or by quoting the monotonicity of Rényi entropy. For completeness, we give this argument in Appendix B. Both inequalities can be far from tight: we give an example in Appendix B.

1.1.1 Entropic Ruzsa distance

If X, Y are G-valued random variables (not necessarily independent, or even defined on the same sample space), then we define the entropic Ruzsa distance 𝑑 ent (X, Y) between these variables by the formula

where X ′ , Y ′ are independent copies of X, Y respectively. This concept, introduced by Ruzsa [16] and studied in more detail by the third author [20], generalizes entropic doubling, since 𝜎 ent [X] = e 𝑑 ent (X,-X) . It is easy to see that 𝑑 ent (X, Y) = 𝑑 ent (Y, X) ≥ 0, and also that 𝑑 ent (U H , U H ) = 0 for any finite subgroup H of G. Note that 𝑑 ent (X, Y) depends only on the distributions p X (x) ∶= P(X = x); p Y (y) ∶= P(Y = y) of X, Y. We have (see the final paragraph of [16], [20, theorem 1.10], or Lemma 1.1 below) the entropic Ruzsa triangle inequality 𝑑 ent (X, Z) ≤ 𝑑 ent (X, Y) + 𝑑 ent (Y, Z) (1.3) for any three G-valued random variables X, Y, Z.

Remark. It is somewhat traditional to use the letter K for the combinatorial doubling constant 𝜎 [A]. We will generally use the letter k for distances 𝑑 ent (X, Y). Where these arise from sets (for instance if X = Y = U A ) one should informally think of k being on the order of log K. It should be carefully noted that k may take values in [0, ∞) and is not constrained to be an integer.

It will be technically convenient to introduce a small modification of the entropic Ruzsa distance. Define the maximal entropic Ruzsa distance 𝑑 * ent (X, Y) to be the quantity

where X ′ , Y ′ range over all pairs of random variables with marginal distributions p X , p Y respectively (i.e., all couplings of X and Y). In particular, X ′ , Y ′ are not required to be independent. We have the following observations. Lemma 1.1. Let X, Y, Z be G-valued random variables. Then:

ent (X, Y) ≤ 3𝑑 ent (X, Y). For the proof, see Section 2.

We turn now to our first main result, which gives a closer connection than (1.1) between small entropy doubling (or more generally small Ruzsa distance) and small doubling. Here, for a real parameter p ∈ (0, 1), we write h(p) ∶= p log 1 p + (1p) log 1 1-p for the entropy of the Bernouilli random variable with probability p. Proposition 1.2. Let C ≥ 4 be a real parameter. For any G-valued random variables X, Y there is a non-empty finite subset S of G such that, if U S is a uniform random variable on S, then

) (1.5)

) .

(1.6)

We isolate two special cases of this proposition for future use:

(i) If we take C = 4 in the above proposition, then (using, in addition, Lemma 1.1 (ii)) we obtain the bounds 𝑑 ent (U S , Y) ≤ 6𝑑 ent (X, Y) + log 2 and |S -S| ≤ 4e 12𝑑 ent (X,Y) |S|. (ii) If 𝑑 ent (X, Y) = 𝜀 for some 0 < 𝜀 ≤ 1 16 , then on taking C ∶= 𝜀 -1∕2 we obtain the bounds 𝑑 ent (U S , Y) ≪ 𝜀 1∕2 log 1 𝜀 and |S -S| ≤

We also remark that a qualitative version of this proposition (with unspecified dependence on 𝑑 ent (X, Y) on the right-hand side) was previously established in [20, proposition 5.2].

In the regime where 𝑑 ent (X, Y) is small, we can in fact obtain the following more precise result.

There is absolute constant 𝜀 0 > 0 such that the following is true. Let X, Y be G-valued random variables, and suppose that 𝑑 ent (X, Y) ≤ 𝜀 0 . Then there is some

Remark. The constant 𝜀 0 could be specified explicitly if desired, but we have not carried out such a calculation. The constant 12 can be improved, but we will not attempt to optimise it here.

1.1.3 Behaviour under homomorphisms Given the close relation between notions of entropy doubling and Ruzsa distance and the usual combinatorial notions, one would be forgiven for wondering what the point of introducing the former is.

The answer is that the entropy notions are more flexible and behave better in various ways. Most obviously, they are defined for arbitrary random variables X, with no requirement that X be uniform on a set. Related to this is the fact that the entropy notions behave well under homomorphisms in a way that the combinatorial notions do not.

The following is our main result in this direction. Here (and below) we use (X|E) to denote a random variable X conditioned to a positive probability event E. We adopt the convention that expressions such as

In particular, we have

and thus

for any G-valued random variable X.

Remark. The main inequality here is a precise version of the intuition that the doubling constant of a subset of G in the presence of a homomorphism 𝜋 ∶ G → H should somehow be at least the doubling constant of the 'base' times some combination of the doubling constants of the 'fibres'. To make sense of this rigorously we need to pass from sets to general random variables, and replace combinatorial doubling by entropy doubling. An example of the failure of a similar result in the purely combinatorial setting (in fact of the analogue of (1.7)) is outlined in [22, exercise 2.2.10].

Remark. Many previous works have noted the advantageous properties of entropy in somewhat related settings. To give a few examples, in rough chronological order there is the work of Avez [1] and of Kaȋmanovich and Vershik [11] on random walks on discrete groups, the work of Hochman [10] on fractals, and the work of Breuillard-Varjú [3] on Bernouilli convolutions.

We turn now to applications of the results of the previous subsection to inverse theorems for sets with small doubling.

The first application is a new proof of a result of Pálvölgyi and Zhelezov [15], which they used to give a new and much shorter proof of a celebrated result of Bourgain and Chang [2]. For the purposes of this result, an affine coordinate space is a subset of Z D (for some D) obtained by fixing the values of some possibly empty set of coordinates. For instance, {(2, -1, x 3 ) ∶ x 3 ∈ Z} ⊆ Z 3 is an affine coordinate space. If A is a finite subset of some affine coordinate space V, itsfoot_1 skew-dimension dim * (A) is defined inductively, as follows:

1. dim * (A) = 0 if and only if A is a singleton (or empty).

Theorem 1.5 (Pálvölgyi-Zhelezov). Suppose A is a finite subset of some affine coordinate space with

This result is essentially contained in a paper [15] of Pálvölgyi and Zhelezov: whilst it is not actually stated in that paper, it is mentioned in a talk by Zhelezov [23, min 27:30], and can be established using the methods of [15]. Lecture notes of the first author may be consulted for a detailed account with some simplifications [8], as well as details of the deduction of the result of Bourgain and Chang.

In fact we will establish the following slightly stronger result.

There is an absolute constant C with the following property. Suppose that A, B ⊆ Z D . Then there are A ′ ⊆ A and

Setting B = -A and using (1.1), we recover Theorem 1.5. The "bilinear" form of Theorem 1.6 will be convenient for induction purposes.

1.2.2 Dimension and PFR over Z Whilst the notion of skew-dimension is useful in the context of the work of Bourgain and Chang, the actual (affine) dimension dim A, defined as the dimension of the span of A -A over the reals, is a more intrinsically natural quantity. Note that dim * A ≤ dim A for any A. It is conjectured that Theorem 1.5 remains true with dim * A ′ replaced by dim A ′ -this is sometimes (see, for instance, [4], [15, conjecture 1]) called the weak Polynomial Freiman-Ruzsa conjecture (PFR) over Z. (The term 'weak' comes from the fact that only the dimension is controlled, and no attempt is made to put A economically inside a box or homomorphic image of the lattice points in a convex set.

Such stronger statements are also speculated to be true, but care must be taken in their formulation, as discussed in [13].)

Prior to this paper, the best known bound in the direction of this conjecture was a result of the second author [14].

The proof of this result in [14] was a little exotic, making use of projections modulo 2 and a kind of "U 3 -energy". We provide a new, shorter, proof of this result, retaining the first feature but using entropic notions in place of the exotic energy.

We will eventually go further in this paper by using results on sets with additive structure in F D 2 to improve the bounds, but before doing that we make a detour into the world of structure theorems for sets of small doubling in F D 2 .

1.2.3 Small doubling in F D 2 and PFR over F 2 In the following discussion, F D 2 denotes the vector space of dimension D over F 2 ; the value of D is typically somewhat unimportant. Essentially everything we have to say would work equally well over other finite fields F, but this introduces some further technicalities and implied constants would need to depend on F, and we do not discuss this aspect here. Denote by C PFR any constant for which the following statement is true: if A ⊆ F D 2 , and if the doubling constant 𝜎[A] is at most K, then A is covered by exp(O(log C PFR (2K))) cosets of some subspace H ≤ F D 2 of size at most |A|. The implied constant in the O() notation is allowed to depend on C PFR . A celebrated result of Sanders [18, corollary A.2] (together with standard covering lemmas) is that one may take C PFR = 4. By an improved version of the argument due to Konyagin (see [19, theorem 1.4]), one can in fact take any C PFR > 3. Strictly speaking, the statement in [19] applies to more general abelian groups than F D 2 , but replaces the subspace H by a convex coset progression. However, an inspection of the arguments in the characteristic 2 case shows that the convex coset progression in this case can be taken to be a subspace (basically because the convex coset progressions are constructed via Bohr sets, which are automatically subspaces in the characteristic 2 setting). Alternatively, one can invoke the discrete John theorem (see [21, theorem 1.6]) to control the convex coset progression by a generalized arithmetic progression (up to acceptable losses, and increasing C PFR by an epsilon), and then observe that in F D 2 , all generalized arithmetic progressions are in fact subspaces. We leave the details of these arguments to the interested reader.

We have the following notorious conjecture, known as the Polynomial Freiman-Ruzsa conjecture over F 2 . Conjecture 1.9. We may take C PFR = 1.

There are a large number of equivalent formulations of Conjecture 1.9; see [7,9,12,17]. We add a further equivalent form of Conjecture 1.9, formulated in terms of entropy. It says that, in the case G = F D 2 , Proposition 1.3 is valid with no smallness restriction on the entropic distance 𝑑 ent (X, Y). Proposition 1.10. Conjecture 1.9 is equivalent to the claim that, for any

Small doubling and dimension, again

We now return to the main topic, and offer the following improvement of Theorem 1.8.

We remark that the constant C is allowed to depend on C PFR (and so by implication on the implied constant in the definition of C PFR ). As it turns out, the implied constant in the ≪ is independent of C PFR , and in particular can be taken to be 40∕ log 2.

Thus, using the Konyagin/Sanders result we can obtain

which is the strongest unconditional result currently known. Perhaps more interestingly, we obtain the following conditional implication between the two forms of the Polynomial Freiman-Ruzsa conjecture discussed above.

Corollary 1.12. Conjecture 1.9 implies Conjecture 1.7.

We begin by developing the theory of entropy doubling and (entropy) Ruzsa distance, as discussed above. In Section 2 we establish Lemma 1.1. In Section 3, we look at the link between random variables and sets and establish Proposition 1.2. In Section 4 we look at homomorphisms and give the (short) proof of Proposition 1.4. Then, in Section 5, we combine these results to prove Proposition 1.3, which relates random variables with small entropy doubling to subgroups. This section is a little lengthy but, as we indicate at the appropriate points, not all of the analysis is needed in subsequent sections.

After this, we turn to the applications to small doubling in Z D . We begin, in Section 6, by proving Theorem 1.6 (and thus reproving Theorem 1.5). Then, we give a new proof of the result of the second author, Theorem 1.8.

Next, we take a brief detour into structural results over F 2 , establishing the equivalence of the Polynomial Freiman-Ruzsa conjecture in this setting with its entropic formulation (Proposition 1.10).

Finally, we return to small doubling in Z D , establishing Theorem 1.11 (and hence Corollary 1.12) in Section 9.

Finally, we remark that although we have written the paper in the context of an abelian group G, many of the arguments (e.g., the proof of Theorem 1.3) do not require this assumption.

In this section we prove Lemma 1.1.

Proof of Lemma 1.1. We begin with part (i). It suffices to show that

This is equivalent to establishing

whenever Y is independent of (X, Z) (but X and Z are not required to be independent of each other). We apply the submodularity inequality (A5) with A = X -Y, B = Z, C = X -Z. With these choices we have

In the second display we used (A3). Applying (A5) gives part (i) of Lemma 1.1.

For part (ii), the first inequality 𝑑 ent (X, Y) ≤ 𝑑 * ent (X, Y) is trivial. For the second inequality, we apply (i) and (1.3) to conclude that

giving the claim. ▪

The objective of this section is to prove Proposition 1.2. Let C, X, Y be as in that proposition. We may assume without loss of generality that X, Y are independent. For brevity we adopt the notation k ∶= 𝑑 ent (X, Y). We need to locate a set S satisfying (1.5) and (1.6). The key lemma is the following.

and such that

whenever Z is an S-valued random variable.

Proof. As X, Y are independent and k = 𝑑 ent (X, Y), we have

and hence by (A14) it follows that

Applying the equality case of (A18), we conclude that

Inspired by this, we define S by the formula

Denote by A the random variable A ∶= 1 X∈S , and write p ∶= P(A = 1) = P(X ∈ S). By Markov's inequality and (3.4), it follows that

Now we make some observations. First,

Second, since Y is independent of X and A, it follows using (A13) that

.8) Combining (3.7), (3.8) with (3.3) we conclude after a short computation that k ≥ p 2 H(Y) -p 2 H(X|A = 1) -1 2 h(p). (3.9) By (A1), we have H(X|A = 1) ≤ log |S|. Substituting into (3.9) and rearranging yields log |S| ≥ H(Y) -h(p) p -2k p . Using (3.6) (and the monotone decreasing nature of h(p) for p ≥ 1∕2), we obtain (3.1). Now we prove (3.2). From (A18) (replacing X by X -Y there) we have

Note here that the Kullback-Leibler divergence is well-defined and finite. Indeed, Z takes values z ∈ S, and hence by the definition of S we have p X (z) > 0 for such z. Proof of Proposition 1.2. We begin by establishing (1.5). Let S be as in Lemma 3.1.

Taking Z = U S in (3.2), we have

The required bound (1.5) then follows from (3.1). Now we prove (1.6). Let Z, Z ′ be any pair of S-valued random variables. From Lemma 1.1 (ii) and (3.2) we have

or equivalently

Now we observe that it is possible to choose Z, Z ′ supported on S so that Z -Z ′ has the uniform distribution on S -S. To do this, simply take (Z, Z ′ ) to have distribution function

Using (3.10) and (3.1), (1.6) follows. ▪ Remark. The last part of this argument has considerable similarity with [16, sect. 5].

In this section we establish Proposition 1.4. Let notation be as in the statement of that proposition.

Proof of Proposition 1.4. We have

and similarly

Subtracting half of (4.2) and half of (4.3) from (4.1) gives

Now X i determines Y i , and so

Moreover, by (A7),

. Combining (4.4), (4.5), (4.6) gives the result.

In fact one sees that the difference between the LHS and the RHS in the proposition is

. ▪

In this section we prove Proposition 1.3, which states that random variables X, Y for which 𝑑 ent (X, Y) is small are close to uniform on a subgroup. We first handle the case X = Y (in which case we will establish Proposition 1.3 with the improved constant of 6). Assume henceforth that X is a G-valued random variable with 𝑑 ent (X, X) = 𝜀 ≤ 𝜀 0 .

We first observe that a weak version of Proposition 1.3 (which in fact suffices for many applications) follows quickly from Proposition 1.2. As observed in item (ii) after Proposition 1.2, we see that there is S such that

and

where the last inequality holds if 𝜀 0 is small enough. A well-known classical observation of Freiman [5] now implies that H ∶= S -S is a group. We recall the short proof here. For any x, y ∈ S, x -S and y -S both lie in S -S and so

For each such pair, we have xy = uv. Now let x ′ , y ′ ∈ S be any other elements. Similarly, there are

|S| values of u ′ , and all these values lie in S; therefore we must have v = u ′ for some pair of these elements. It then follows that

Since x, y, x ′ , y ′ were arbitrary, it follows that S -S is closed under addition. Since it contains 0 and is closed under taking inverses, it must be a group.

From (A16) (noting that S is contained in a single coset of H) and (5.2) we have

Therefore from (5.1) and (1.3) we have

This is weaker than Proposition 1.3 only in the non-linear dependency on 𝜀, which in many applications is not important. We will deduce the stronger statement of Proposition 1.3 by bootstrapping this bound. To do this, we require two lemmas which are essentially special cases of Proposition 1.3 itself. First, we consider the case in which X is highly concentrated near one point.

There is 𝛿 0 > 0 such that the following is true. Suppose that X is a G-valued random variable and x 0 ∈ G is a value such that P(X = x 0 ) ≥ 1 -𝛿 0 . Then H(X) ≤ 2𝑑 ent (X, X).

Proof. By replacing X by Xx 0 if necessary, we may assume without loss of generality that x 0 = 0. Let X 1 , X 2 be independent copies of X. Then our task is equivalent to showing that

(5.4)

Write p ∶= P(X ≠ 0) (thus p ≤ 𝛿 0 ), and let A denote the indicator function of the event that X 1 , X 2 ≠ 0; then P(A = 0) = 1p 2 and P(A = 1) = p 2 . As a consequence, we have

where we used (A13) in the last line. Now note that for any z, if A = 0 and X 1 -X 2 = z then (X 1 , X 2 ) can take only two values (z, 0) and (0, -z) if z ≠ 0, and only one value (0, 0) if z = 0. Hence

Combining with (5.5), we obtain

We also observe that

(5.7)

We further note that, writing I for the indicator of X ≠ 0,

.8) 10982418, 0, Downloaded from https://onlinelibrary.wiley.com/doi/10.1002/rsa.21252 by Princeton University, Wiley Online Library on [23/08/2024]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License

Taking (5.7) minus p times (5.8) gives

Combining this with (5.6), we obtain

(5.9)

Recall that our aim is to demonstrate (5.4). To get this from (5.9), we first note that expansion to leading order gives

provided 𝛿 0 is small enough: the LHS here is ∼ 2p log 2, whilst the right hand side is ∼ 1 2 p log 1 p . (A more careful analysis shows that 𝛿 0 = 1 20 is sufficient.) We also have

(5.11)

The desired bound (5.4) then follows immediately from (5.9), (5.10) and (5.11). ▪

Remark. The constant 2 in the statement of Lemma 5.1 can be replaced by anything larger than 1, at the expense of making 𝛿 0 smaller. This may be shown with very minor modifications of the above argument.

We next consider the case of a random variable supported on H.

To prove this we will use the following lemma concerning couplings of almost uniform random variables, which is plausibly of independent interest. Here, for a probability distribution p on a group

for the 𝓁 1 -distance of p from the uniform distribution (or, equivalently, twice the total variation distance of p from the uniform distribution).

(5.12)

Then there exists a pair of random variables (X, Y) on H (not necessarily independent) having the marginal distributions p X = p 1 , p Y = p 2 and p X-Y = p 3 .

Proof. We wish to show that the triple of distributions

Here (as usual) 𝛿 t (u) = 1 if u = t, and 𝛿 t (u) = 0 otherwise. By the (finite-dimensional) Hahn-Banach theorem, this is equivalent to showing that there is no hyperplane separating (p 1 , p 2 , p 3 ) from Σ, or in other words whenever

for all x, y ∈ H, one also has

Henceforth, assume (5.13). Note that (5.13) and (5.14) are both unaffected if we shift f 1 , f 2 , f 3 by constants c 1 , c 2 , c 3 summing to zero. Thus we may normalize so that

If this quantity is non-negative then (5.14) is immediate, so we may assume that it is negative. By rescaling we may thus normalize so that

(5.15)

In particular, there exists x 0 ∈ H such that f 1 (x 0 ) = -1. From (5.13) and (5.15), we conclude that for every y ∈ H one has

This implies that f 2 (y)p 2 (y) + f 3 (x 0y)p 3 (x 0y) ≥ (f 2 (y) + f 3 (x 0y)) min(p 2 (y), p 3 (x 0y))

Summing over y, we conclude that

Cyclically permuting the roles of f 1 , f 2 , f 3 and p 1 , p 2 , p 3 and averaging, the desired bound (5.14) then follows from (5.12). ▪

Proof of Lemma 5.2. By (A10) and Pinsker's inequality (A12) it follows that

(5.16) Applying Lemma 5.3 (with p 1 = p 2 = p X and p 3 = 1 |H| ), it follows that there exists a pair of random variables (X 1 , X 2 ) such that X 1 , X 2 each have the same marginal distribution as X, and X 1 -X 2 is uniform on H.

which immediately implies the result. ▪

Proof of Proposition 1.3. We first establish the case X = Y (with the constant 12 replaced by 6). Suppose, as we have throughout the section, that 𝑑 ent (X, X) = 𝜀 ≤ 𝜀 0 . Let 𝜋 ∶ G → G∕H be the quotient projection. Recall from (A16) that

.17) From (5.3) we have the weak bound 𝑑 ent (X, U H ) ≪ 𝜀 1∕2 log 1 𝜀 . Thus H(𝜋(X)) ≪ 𝜀 1∕2 log 1 𝜀 (5.18) and H(X) ≥ log |H| -O ( 𝜀 1∕2 log 1 𝜀 ) . (5.19) Now by Proposition 1.4 (replacing H there by G∕H, and recalling that 𝑑 ent (X, X) = 𝜀) we obtain 𝑑 ent (𝜋(X), 𝜋(X)) ≤ 𝜀 (5.20) and ∑ y 1 ,y 2 ∈G∕H p 𝜋(X) (y 1 )p 𝜋(X) (y 2 )𝑑 ent (X y 1 , X y 2 ) ≤ 𝜀, (5.21)

where X y denotes X conditioned to the event 𝜋(X) = y. By (5.18) and (A2), we see that there is some y 0 ∈ G∕H such that P(𝜋(X)

. By translating X if necessary, we may assume without loss of generality that y 0 = 0, that is to say

where 𝛿 0 is the constant from Lemma 5.1, and we assume that 𝜀 0 from the statement of Proposition 1.3 is sufficiently small. Applying Lemma 5.1 to 𝜋(X) using (5.20), (5.22), we conclude that H(𝜋(X)) ≤ 2𝜀.

(5.23)

Meanwhile, discarding all terms in the sum over y 1 in (5.21) except the term y 1 = 0, and using (5.22), it follows that

Using H(X) = H(X|𝜋(X)) + H(𝜋(X)) and (5.23), we conclude that

(5.24)

In particular, from (5.19) we deduce

) .

(5.25)

Now by discarding all terms in (5.21) except the one with y 1 = y 2 = 0, and using (5.22), we have

It follows from Lemma 5.2 that H(X 0 ) ≥ log |H| -2.42𝜀, and hence by (5.24) we obtain H(X) ≥ log |H| -6.62𝜀.

Combining this with (5.17) and (5.23) gives 𝑑 ent (X, U H ) ≤ 5.31𝜀 ≤ 6𝜀, which is the statement of Proposition 1.3 (with a better constant) in the symmetric case X = Y.

Finally, we deduce the general case in which X and Y may be different. Suppose now that 𝑑 ent (X, Y) = 𝜀 ≤ 𝜀 ′ 0 , where 𝜀 ′ 0 ∶= 𝜀 0 ∕2 with 𝜀 0 the constant above. By the triangle inequality, 𝑑 ent (X, X) ≤ 2𝜀 ≤ 𝜀 0 , and so by the symmetric case of Proposition 1.3 established above we have 𝑑 ent (X, U H ) ≤ 12𝜀 for some subgroup H ≤ G. Similarly, we have 𝑑 ent (Y, U H ′ ) ≤ 12𝜀 for some subgroup H ′ ≤ G.

It remains to argue that H = H ′ . For this, we observe that by the triangle inequality we have

.26) If H ≠ H ′ , then H+H ′ is a subgroup of G properly containing H, H ′ and therefore of size at least 2 max(|H|, |H ′ |). Since U H -U H ′ is uniform on H + H ′ , we have 𝑑(U H , U H ′ ) ≥ log 2, which contradicts (5.26) if 𝜀 0 is small enough. Therefore we do indeed have H = H ′ , and this concludes the proof. ▪

In this section we give the proof of Theorem 1.6 (and thus Theorem 1.5).

Proof of Theorem 1.6. Let 𝜀 > 0 be a small constant to be specified later, and set C ∶= 2∕𝜀. We will prove Theorem 1.6 with this particular value of C.

We proceed by on |A||B| and on D. Denote by 𝜋 ∶ Z D → Z projection onto the first coordinate. We may assume that at least one of the sets 𝜋(A), 𝜋(B) is not a singleton (otherwise D may be reduced to D -1).

Let X 1 , X 2 be uniform random variables on A, B respectively, and let Y i = 𝜋(X i ). Applying Proposition 1.4 and rearranging, we obtain

where

and

We now divide into two cases, according to whether

Let 𝜀 0 be the constant from Proposition 1.3, and assume that 𝜀 ≤ min

. By Proposition 1.3 and the fact that H = {0} is the only finite subgroup of Z, we have

by the choice of C, 𝜀. Inserting this into (6.1) and rearranging, we obtain

In particular, there exist i, j such that

Invoking the induction hypothesis (with A, B replaced by A ∩ 𝜋 -1 ({i}) and B ∩ 𝜋 -1 ({j}) respectively), we see that there are sets

This closes the induction in Case 1.

In this case we see from (6.1) that

The contribution from those (i, j) with log

By the induction hypothesis, for each pair (i, j) ∈ S there are sets

and all with skew-dimension at most

(Here we used the fact that C = 2∕𝜀.) For each i ∈ Z, set A ′ i to be the largest of the sets A ′ i,j , (i, j) ∈ S (or A ′ i = ∅ if (i, j) ∉ S for every j), and similarly for each j ∈ Z set B ′ j to be the largest of the sets B ′ i,j , (i, j) ∈ S, breaking ties arbitrarily. Finally, set A ′ ∶= ⋃ i∈Z A ′ i and B ′ ∶=

By the definition of skew-dimension and the bound (6.6), we have dim

From the elementary inequality t ≥ log t for t ≥ 1 applied to t = (K∕K i,j ) C (noting by (6.4) that we do indeed have t ≥ 1), we have

for any (i, j) ∈ S. From this and (6.5), ( 6.3) we have

10982418, 0, Downloaded from https://onlinelibrary.wiley.com/doi/10.1002/rsa.21252 by Princeton University, Wiley Online Library on [23/08/2024]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License

This completes the induction, and the theorem is proved. ▪

We turn now to the question of the dimension (as opposed to the weaker skew-dimension) of subsets of Z D with small doubling. Our aim in this section is to give an entropic proof of Theorem 1.8. In so doing, we will also lay the groundwork for the proof of Theorem 1.11, our improvement upon this result.

As in [14, slogan 2.5], a key idea is that a set A ⊆ Z D with small doubling must look rather singular under the projection map 𝜙 ∶ Z D → F D 2 . In Lemma 7.2 below, we give an entropic formulation of this principle. We isolate the following lemma from the proof. Lemma 7.1. Let G be torsion-free, and let X, Y be G-valued random variables. Then 𝑑 ent (X, 2Y) ≤ 5𝑑 (X, Y).

Proof. We assume X, Y are independent. Thenfoot_2

by definition of 𝑑 * ent . By Lemma 1.1,

Letting Y 1 , Y 2 be independent copies of Y (which are also independent of X) we have

and

so applying the submodularity inequality (A5) gives

Combining this with (7.3) gives

which, together with (7.1) and (7.2), yields

and so

where we used (A14) in the last step. ▪

However, 𝜙(2Y) is identically zero and so

Combining this with (7.4) gives the stated bound for H(𝜙(X)). The bound for H(𝜙(Y)) follows in the same way. ▪ Remark. It is perhaps worth remarking on the meaning and proof of this statement. Supposing that A ⊂ Z D is a set with small (combinatorial) doubling K, it follows that the dilate 2 ⋅ A, which is contained in A + A, is commensurate (up to polynomial factors in K) with A. Projecting mod 2, one therefore expects the projection 𝜋(A) to be commensurate with the projection 𝜋(2 ⋅ A) = {0}. A version of this argument appears in [14, appendix B]. In the entropy setting, Lemma 7.1 acts as a replacement for the trivial observation that 2 ⋅ A is contained in A + A.

Now we are ready for the proof of Theorem 1.8 itself. To make the argument work, we will in fact need to establish the following bipartite variant of the result.

There is an absolute constant C 1 such that, setting f (t) ∶= C 1 t(1 + t), the following is true. Let D ∈ N, and suppose that A, B ⊆ Z D are finite non-empty sets. Then there exist nonempty

)

It is clear from (1.1) that this indeed implies Theorem 1.8. We first prove a simple lemma which will be used several times in what follows.

Lemma 7.4. Let 𝜙 ∶ G → H be a homomorphism, and A, B ⊆ G finite subsets. For x, y ∈ H write A x = A ∩ 𝜙 -1 (x) and B y = B ∩ 𝜙 -1 (y) for the fibres of A and B, and write

Then there exist x, y ∈ H such that A x , B y are non-empty and with

Proof. First observe that the random variables (U A |𝜙(U A ) = x) and (U B |𝜙(U B ) = y) are equal in distribution to U A x , U B y respectively, that is to say the uniform distributions on the fibres. It follows from Proposition 1.4 that

By definition,

It follows by the pigeonhole principle that there is at least one choice of x, y such that 𝛼 x , 𝛽 y > 0 and

Rearranging gives (7.6). ▪

We now turn to the proof of Theorem 7.3.

Proof of Theorem 7.3. Let us begin by noting the simple inequality

Let us turn now to the main proof. We will proceed by induction on |A| + |B|. We may also assume that A, B do not sit inside cosets of a proper subgroup of Z D , else we may replace Z D by that subgroup. We also suppose D ≥ 1, as the result is trivial otherwise.

Let 𝜙 ∶ Z D → F D 2 be the natural homomorphism. Then, by the preceding remark and the fact that ker 𝜙 is a proper subgroup of Z D , we may assume that at least one of 𝜙(A), 𝜙(B) is not a singleton. For x, y ∈ F D 2 , denote by A x ∶= A ∩ 𝜙 -1 (x) and B y ∶= B ∩ 𝜙 -1 (y) the fibres of A, B. Note that

for all x, y. Write k ∶= 𝑑 ent (U A , U B ) and 𝜀 ∶= 𝑑 ent (𝜙(U A ), 𝜙(U B )). Let 𝛿 > 0 be a small positive constant to be determined later, and set C 1 ∶= max(20∕𝛿, 100). We will divide into two cases, according to whether or not 𝜀 ≤ 𝛿.

Case 1: 𝜀 > 𝛿. By Lemma 7.2 with X = U A , Y = U B , we have H(𝜙(U A )) + H(𝜙(U B )) ≤ 20k. (7.10) By Lemma 7.4 applied to G = Z D and H = F D 2 , we may find x, y ∈ F D 2 such that (7.6) holds. Fix such x, y, and for brevity set k ′ ∶= 𝑑 ent (U A x , U B y ). Then (7.6) implies that k ′ ≤ k and log |A| |A x | + log |B| |B y | ≤ 20k 𝜀 (kk ′ ). (7.11)

Noting (7.9), we may apply the induction hypothesis to conclude that there are

This and (7.11) immediately imply log |A| |A ′ | + log |B| |B ′ | ≤ f (k ′ ) + 20k 𝜀 (kk ′ ). By (7.8), this is at most f (k), since C 1 ≥ 20∕𝛿 ≥ 20∕𝜀. This closes the induction in Case 1. Case 2: 𝜀 ≤ 𝛿. Recall here that 𝜀 = 𝑑 ent (𝜙(U A ), 𝜙(U B )), and note that 𝜀 ≤ k by Proposition 1.4. Let 𝜀 0 be the constant from Proposition 1.3 and suppose 𝛿 ≤ 𝜀 0 . By Proposition 1.3 there is some H ≤ F D 2 such that 𝑑 ent (𝜙(U A ), U H ), 𝑑 ent (𝜙(U B ), U H ) ≤ 12𝜀. It is possible that H = F D 2 . In this case, we have by (A14) and Lemma 7.2 that log(2 D ) = H(U H ) ≤ H(𝜙(U A )) + 2𝑑 ent (𝜙(U A ), U H ) ≤ 10k + 24𝜀 ≤ 34k, and so D ≤ 100k. This gives Theorem 7.3 simply by taking A = A ′ , B = B ′ , since C 1 ≥ 100. Alternatively, suppose that H is a proper subgroup of F D 2 . Denote by φ the composition of 𝜙 with projection to F D 2 ∕H. By (A17) we have

By (A2) there is some x 0 such that P( φ(U A ) = x 0 ) ≥ e -32𝜀 ≥ e -32𝛿 . Choosing 𝛿 sufficiently small, this is ≥ 1 -𝛿 0 where 𝛿 0 is the constant in Lemma 5.1, and so by Lemma 5.1

where the second inequality is by (1.3). The same bound holds for H( φ(U B )).

Hence by Lemma 7.4 applied to φ, A and B (noting that we cannot have H( φ(U A )) = H( φ(U B )) = 0, as then A, B would be contained in cosets of a proper subgroup) we deduce that there exist

where

We now finish the proof as before. Set k ′ = 𝑑 ent (U A x , U A y ), which is ≤ k by (7.12). Since A, B are not contained in cosets of a proper subgroup of Z D , we have

and so by induction we may find

By (7.8) (and since C 1 ≥ 8) this is at most f (k). This closes the induction in Case 2 and the proof of Theorem 7.3 is complete. ▪ Remark. For this argument, the full strength of Proposition 1.3 was not needed, and the weaker bound (5.3) would have sufficed.

In this section we establish Proposition 1.10. Recall that the content of this proposition is that the following two statements are equivalent: (1) ) cosets of some subspace

Proof of Proposition 1.10. We first derive the entropic statement, that is to say Statement 2 above, from the combinatorial one (Statement 1). Write k ∶= 𝑑 ent (X, Y) and set K ∶= e k . We may assume that k ≥ 𝜀 0 , where 𝜀 0 is the constant in Proposition 1.

3, since the claim follows immediately from that proposition otherwise. Applying Proposition 1.2 with C = 4, we obtain a set S ⊆ F D 2 with 𝑑 ent (X, U S ) ≪ k (8.1) and (recalling that |S+S| |S| ≤ ( |S-S| |S| ) 3 ; see for example, [22, corollary 2.12]) |S + S| ≪ K O(1) |S|. (8.2) By Statement 1 there is a subgroup H ≤ F D 2 , |H| ≤ |S|, such that S is covered by O(K O (1) ) cosets of H. Note, in particular, that S + H is contained in the union of the aforementioned cosets, and so |S + H| ≪ K O (1) min(|S|, |H|). Now for any sets A, B we have

) .

(This is the bipartite version of (

1.1).) Applying this with A = S and B = H (and noting H = -H) gives 𝑑 ent (U S , U H ) ≪ k, and so by the triangle inequality and (8.1) we have 𝑑 ent (X, U H ) ≪ k, which is the conclusion in Statement 2. We now to the reverse implication, deriving the combinatorial Statement 1 from the entropic Statement 2. Suppose that A ⊆ F D 2 is a set and write K ∶= 𝜎[A] and k∶= log K. Then, by (1.1), we have 𝑑 ent (A, -A) = log 𝜎 ent [A] ≤ k. Assuming Statement 2, there is some finite subgroup H ≤ F D 2 with 𝑑 ent (U A , U H ) ≪ k. By (A14) and the fact that H(U A ) = log |A|, H(U H ) = log |H|, we have

Writing p(x) for the density function of U A -U H , thus p(x) = |A∩(H+x)| |A||H| , it follows from (A2) that there is some x 0 such that

Recall the Ruzsa covering lemma (see e.g., [22, lemma 2.14]), which states that if |U + V| ≤ K|U| then V is covered by K translates of U -U. Applying this with U = A ∩ (H + x 0 ) and V = A, and using the fact that U + V ⊆ A + A and U -U ⊆ H, it follows that A is covered by O(K O (1) ) translates of H.

If |H| ≤ |A|, we are done. If |H| > |A|, pass to a subgroup H ′ ≤ H of size in the range ( 1 2 |A|, |A|]; then A is covered by O(K O(1) ) translates of H ′ , and the proof is complete in this case also. ▪ A minor modification of the first part of the above proof, using the quantity C PFR from the introduction in place of Statement 1, gives the following statement. Proposition 8.1. Let X, Y be F D 2 -valued random variables, and suppose that 𝑑 ent

), for some absolute constant C (which may depend on C PFR ).

We now prove Theorem 1.11 (and hence Corollary 1.12). The proof is along somewhat similar lines to the proof of Theorem 1.8 given in Section 7, but more involved. An important ingredient will be the following lemma. Throughout this section, C will be the constant in Proposition 8.1 (but the precise nature of this constant is not important).

Lemma 9.1. Suppose that X and Y are F D 2 -valued random variables. Then there is a subgroup H ≤ F D 2 such that, denoting by 𝜓 ∶ F D 2 → F D 2 ∕H the natural projection, and setting k ∶= 𝑑 ent (𝜓(X), 𝜓(Y)), we have log |H| ≤ 2(H(X) + H(Y)) (9.1) and H(𝜓(X)) + H(𝜓(Y)) ≤ 8Ck ( 1 + k C PFR -1 ) . (9.2) We isolate the following (sub-) lemma from the proof. Lemma 9.2. Let n ∈ N. Let X, Y be F n 2 -valued random variables. Set k∶= 𝑑 ent (X, Y), suppose that H(X) + H(Y) > 8Ck ( 1 + k C PFR -1 ) . (9.3) Then there is a nontrivial subgroup H ≤ F n 2 such that log |H| ≤ H(X) + H(Y) (9.4) and (writing 𝜓 ∶ F n 2 → F n 2 ∕H as above) H(𝜓(X)) + H(𝜓(Y)) ≤ 1 2 (H(X) + H(Y)) . (9.5) Proof. Set k ∶= 𝑑 ent (X, Y). Applying Proposition 8.1, we obtain a subgroup H such that 𝑑 ent (X, U H ), 𝑑 ent (Y, U H ) ≤ Ck(1 + k C PFR -1 ). By (A17) and (9.3), it follows that

which is (9.5). To prove (9.4), an application of (A14) yields log

and similarly for Y. Therefore using (9.3) we have

which gives the required bound (9.4).

If H were trivial we would have 𝜓(X) = X, 𝜓(Y) = Y and so (9.5) would imply H(X)+ H(Y) = 0, which then contradicts (9.3). ▪ Proof of Lemma 9.1. We iteratively define a sequence

2 ∕H i the ith associated projection operator, and set k i ∶= 𝑑 ent (𝜓 i (X), 𝜓 i (Y)). We stop the iteration at the ith stage if we have

Otherwise, we apply Lemma 9.2 to 𝜓 i (X), 𝜓 i (Y), obtaining a nontrivial subgroup

and

Clearly from iterated application of (9.8) we obtain

Then, from a telescoping application of (9.7) we get log |H i | ≤ 2(H(X) + H(Y)). (9.9)

Since the groups H i form a strictly increasing sequence, the iteration does terminate at some time i. At this time we have both (9.6) and (9.9) and so, setting 𝜓 = 𝜓 i , the proof of Lemma 9.1 is concluded. ▪

Now we turn our attention to Theorem 1.11. It is a consequence of the following bipartite statement, which should be compared to Theorem 7.3. ). Applying Lemma 7.4 once again, and noting (9.13) and (9.15), we find x, y ∈ F D 2 ∕H such that log |A| |A x | + |B| |B y | ≤ 20C(1 + k 1-𝛾 ) ( k -𝑑 ent (U A x , U B y ) ) (9.16) Set k ′ = 𝑑 ent (U A x , U B y ). By induction on A x , B y we may find A ′ ⊆ A x and B ′ ⊆ B y such that dim A ′ , dim B ′ ≤ C 2 k ′ ≤ C 2 k and log |A x | |A ′ | + log |B y | |B ′ | ≤ f (k ′ ). Adding this to (9.16) yields log |A| |A ′ | + log |B| |B ′ | ≤ f (k ′ ) + 20C(1 + k 1-𝛾 )(kk ′ ). (9.17) However,

10982418, 0, Downloaded from https://onlinelibrary.wiley.com/doi/10.1002/rsa.21252 by Princeton University, Wiley Online Library on [23/08/2024]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License

This, provided C 1 ≥ 20C, the right-hand side of (9.17) is at most f (k), and this closes the induction. The proof is complete. ▪

We conclude with a simple example showing that both inequalities (B1) can be far from tight. Suppose that n = 2m is even and A = H ∪ {x 1 , … , x m }, with H a subgroup of size m and x 1 , … , x m highly dissociated with respect to H, for instance with x i + x jx kx l ∈ H only if {i, j} = {k, l}. Then we have |A| 3 ∕E[A] =

1 16 + o(1) as n → ∞. Turning to 𝜎 ent [A], we of course have H(U A ) = log n. The variable U A + U ′ A may be conditioned to subvariables which are, respectively, uniformly distributed on H, on the set ⋃ m i=1 (x i + H), and on the multiset ⋃ m i,j=1 {x i + x j }, with the conditioning probabilities being 1 4 , 1 2 , 1 4 . One therefore computes that H(U A + U ′ A ) = ( 7 4 + o(1)) log n and so 𝜎 ent [A] = n 3∕4+o(1) . Finally, 𝜎[A] = ( 3 4 + o(1))n.