ENTROPY METHODS

TERENCE TAO, VAN VU

1. Introduction

In this expository article we introduce the notion of an entropy H(X) of a discrete variable X taking a finite number of values; informally, this captures the amount of information one learns when one evaluates the value of X. Our emphasis here shall be a little different than that for the probabilistic method, in which the focus is on complex-valued or real-valued random variables, and on their expectation and variance; here, the range of the random variable will play almost no role, and expectation and variance will not appear at all in this discussion. On the other hand, the concepts of determinism and independence will still play major roles in this discussion.

Definition 1.1. Let X be a discrete random variable. We define the entropy H(X) of X to be the quantity^{1}

H(X) := −∑_{k}P(X = k)logP(X = k)

with the convention that 0log0 = 0; note that only finitely many terms in the series will be non-zero since X is discrete. If Y is another discree random variable, and (X,Y) is the joint random variable, we abbreviate H((X,Y)) as H(X,Y); similarly we define H(X,Y,Z), etc.

Remark 1.2. Clearly H(X) depends only on the probability distribution of X, thus H(X) = H(X′) whenever [X] = [X′]. For similar reasons, H(X) depends only on the σ-algebra B_{X} generated by X, thus H(X) = H(Y) whenever B_{X} = B_{Y}. Indeed, we can define an entropy of a probability distribution or of a σ-algebra, for instance H(B) := −∑_{A} P(A)logP(A) where A ranges over all atoms of B; thus H(X) = H(B_{X}) for any discrete random variable X.

A basic estimate is

Lemma 1.3 (Jensen’s inequality). Let X be a discrete random variable taking values in a finite set K. Then we have

(1)  0 ≤ H(X) ≤ log|K|.

We have H(X) = log|K| if and only if X has the uniform distribution on K, and H(X) = 0 if and only if X is deterministic. In particular, a random variable must take at least exp(H(X)) values.

1In some texts the entropy is defined using the logarithm base two intead of the natural logarithm. This does not make a substantial difference to any of the entropy inequalities we will derive here, though.

We leave the proof of this lemma as an exercise (Exercise 2). The quantity H(X) is related to the asymptotic probability distribution of a large number of trials X_{1},...,X_{M} of the same random variable X:

Lemma 1.4 (Concentration of measure). Let X be a random variable taking values in a finite set K. Let M be a large integer, and let X_{1},...,X_{M} be independent trials of X. Then there exists a set K_{X,M} ⊂ K^{M} of cardinality

(2)  |K_{X,M}| = e^{(H(X)+o(1))M}

such that

(3)  P((X_{1},...,X_{M}) ∈ K_{X,M}) = 1−o(1)

and

(4)  P((X_{1},...,X_{M}) = k⃗) = e^{(−H(X)+o(1))M}

for all k⃗ ∈ K_{X,M}. Here we use o(1) to denote any expression which goes to zero as M → ∞ for fixed X.

One can obtain much better control on the o(1) errors, of course, but we will not need to do so here. The above lemma asserts, roughly speaking, one should think of the joint variable (X_{1},...,X_{M}) as approximately having a uniform distribution on Ω := e^{MH(X)} elements; this can be viewed as a “thermodynamic” definition H(X) = \frac{1}{M} logΩ of the entropy. The approximate uniformity of distribution here means that we do not have to invoke tools such as the pigeonhole principle or the Cauchy-Schwarz inequality in the analysis of entropy; these tools come in some sense “for free”, being subsumed in the Shannon entropy inequalities which we shall describe below.

Proof. Let ω(M) be any function of M which goes to ∞ as M → ∞. For each k ∈ K, let Y_{k} := ∑_{m=1}^{M} I(X_{m} = k), i.e. Y_{k} counts the number of trials of X which take the value of k. From Hoeffding’s inequality we see that

P(|Y_{k} −MP(X = k)| ≥ ω(M)M^{1/2}) = o(1)

for all k ∈ K. Since the cardinality |K| of K does not depend on M, we thus have

P(|Y_{k} −MP(X = k)| ≤ ω(M)M^{1/2} for all k ∈ K) = o(1).

Thus if we define

K_{X,M} := {(k_{1},...,k_{M}) ∈ K^{M} : | ∑_{m=1}^{M}I(k_{m} = k)−MP(X = k)| ≤ ω(M)M^{1/2} for all k ∈ K}

then we have (3). It thus remains to prove (4), since (2) will then follow since the total probability must equal 1. But by independence we have for any k⃗ = (k_{1},...,k_{M}) ∈ K_{X,M}

logP((X_{1},...,X_{M}) = k⃗) = ∑_{m=1}^{M}logP(X_{m} = k_{m})

= ∑_{k∈K}( ∑_{m=1}^{M}I(k_{m} = k))logP(X = k)

= ∑_{k∈K}(MP(X = k)+O(ω(M)M^{1/2})logP(X = k)

= −MH(X)+O(ω(M)M^{1/2}),

and (4) follows by choosing ω to be suitably slowly growing in M. □

For any discrete random variable X : Ω → K, and any event A ⊂ Ω of positive probability, we can define the conditional entropy H(X|A) as the entropy of the random variable (X|A), thus

H(X|A) = − ∑_{k∈K} P(X = k|A)logP(X = k|A).

If Y : Ω → L is another discrete random variable, we define the conditional entropy H(X|Y) as

(5)  H(X|Y) := ∑_{l∈L}H(X|Y = l)P (Y = l).

Informally, this is the expected amount of information one learns from X assuming that one already knows the value of Y. Observe that this quantity is automatically non-negative.

We now record some fundamental inequalities concerning entropy.

Theorem 1.5 (Shannon entropy inequalities). Let X,Y,Z,W be discrete random variables on a probability space Ω.

• (Bayes identity) We have

(6)  H(X,Y) = H(X|Y)+H(Y) = H(Y |X)+H(X)

and more generally

(7)  H(X,Y |Z) = H(X|Y,Z)+H(Y |Z) = H(Y |X,Z)+H(X|Z).

• (Independence) If X and Y are independent, then

(8)  H(X,Y) = H(X)+H(Y); H(X|Y) = H(X); H(Y |X) = H(Y).

More generally, if X and Y are independent conditioning on Z, then (9) H(X,Y |Z) = H(X|Z)+H(Y |Z); H(X|Y,Z) = H(X|Z); H(Y |X,Z) = H(Y,Z).

• (Monotonicity) If Y is determined by X, then

(10)  H(Y) ≤ H(Y)+H(X|Y) = H(X) and H(Y |X) = 0.

In particular, if X and Y determine each other, then H(X) = H(Y). More generally, if Y is determined by X,Z, then

(11)  H(Y |Z) ≤ H(Y |Z)+H(X|Y,Z) = H(X|Z) and H(Y |X,Z) = 0.

Thus if X and Y determine each other given Z, then H(X|Z) = H(Y |Z). Similarly, if Z is determined by W, then

(12)  H(X|W) ≤ H(X|Z) ≤ H(X).

• (Sub-additivity) If X and Y determine W, then

(13)  H(W) ≤ H(X,Y) ≤ H(X)+H(Y).

More generally, if X,Y,Z determine W, then

(14)  H(W |Z) ≤ H(X,Y |Z) ≤ H(X|Z)+H(Y |Z).

• (Submodularity) If X determines Z, that Y determines Z, and (X,Y) determines W, then

(15)  H(Z)+H(W) ≤ H(X)+H(Y).

We remark that all of these inequalities correspond well to one’s intuitive notion of information. The deepest and most powerful inequality here is the submodularity inequality, which shall use often.

Proof. Let K, L be the range of X,Y respectively. Expanding out H(X,Y), we obtain

H(X,Y) = ∑_{k∈K} ∑_{l∈L}P(X = k,Y = l)logP(X = k,Y = l)

= ∑_{l∈L}P (Y = l)(∑_{k∈K} P(X = k|Y = l)(logP(X = k|Y = l)+logP(Y = l))

= ∑_{l∈L}P (Y = l)H(X|Y = l)+∑_{l∈L}P (Y = l)logP(Y = l)

= H(X|Y)+H(Y);

from this and symmetry we obtain (6). The generalization (7) then follows immediately by substituting in the formula H(X|Y) = H(X,Y)−H(Y) to eliminate all the conditional expectations.

If X and Y are independent, then (X|Y = l) has the same distribution as X for all l in the range of Y, and hence H(X|Y = l) = H(X). Taking expectations over l we obtain H(X|Y) = H(X), and (8) then follows from (6) and symmetry. If instead X and Y are independent conditioning on Z, then (X|Z = m) is independent of (Y |Z = m), hence H(X,Y |Z = m) = H(X|Z = m)+H(Y |Z = m) for all m in the range of Z. Taking expectations over m we obtain (9).

If Y is determined by X, then X and (X,Y) generate the same σ-algebra, and hence H(X) = H(X,Y), and (10) follows from (6) and the positivity of conditional entropy. The claim (11) then follows by conditioning on Z = m and then taking expectations over m, as before.

Now let X and Z be arbitrary, and let K and M be the ranges of X and Z. Let f denote the function f(x) := −xlogx, thus

H(X|Z) = ∑_{m∈M} P(Z = m) ∑_{k∈K} f(P(X = k|Z = m)).

But since f is concave on 0 ≤ x ≤ 1, we have

∑_{m∈M} P(Z = m)f(P(X = k|Z = m)) ≤ f( ∑_{m∈M} P(Z = m)P(X = k|Z = m)) = f(P(X = k)),

and summing over all k we obtain H(X|Z) ≤ H(X). The remaining claim in (12) can be proven by conditioning on Z = m and taking expectations on m as before.

The first inequality in (13) follows from (10); the second inequality follows from (6) and (12). One can then deduce (14) from (13) by conditioning on Z = m and taking expectations as before.

Finally, (15) follows directly from (14) and (10). □

From these Shannon inequalities we can compute the entropy of multiple (conditionally) independent trials:

Corollary 1.6. Let X_{1},...,X_{N} be random variables, and let X′_{1},...,X′_{N} be independent trials of X_{1},...,X_{N}, then

H(X′_{1},...,X′_{N}) = H(X_{1})+...+H(X_{N}).

More generally, if X_{1},...,X_{N},Y_{1},...,Y_{N} are random variables, with [Y_{1}] = ... = [Y_{N}], and X′_{1},...,X′_{N},Y are conditionally independent trials of X_{1},...,X_{N} conditioning on Y_{1} = ... = Y_{N} = Y, then

H(X′_{1},...,X′_{N}|Y) = H(X_{1}|Y_{1})+...+H(X_{N}|Y_{N})

or equivalently

H(X′_{1},...,X′_{N}) = H(X_{1},Y_{1})+...+H(X_{N},Y_{N})−(N −1)H(Y).

In particular, if each of the Y_{n} are determined by X_{n}, then

H(X′_{1},...,X′_{N}) = H(X_{1})+...+H(X_{N})−(N −1)H(Y).

(1) If B is a σ-algebra, show that H(B) = E(X), where X be the random variable X(x) := −logP(B(x)).

(2) Prove Lemma 1.3. (Hint: use the fact that the function −xlogx is concave when 0 ≤ x ≤ 1.)

(3) If B is a σ-algebra, show that B contains at least exp(H(B)) atoms.

(4) Let X,Y be discrete random variables on a probability space Ω. Show that H(X,Y) = H(X) + H(Y) (or equivalently, that H(X|Y) = H(X) or H(Y |X) = H(Y)) if and only if X and Y are independent. Show that H(X,Y) = H(X) if and only if Y is determined by X. This should be compared with the inequalites max(H(X),H(Y)) ≤ H(X,Y) ≤ H(X)+H(Y) which are true for general pairs of random variables X,Y, and emphasizes the extent to which determinism and independence are opposite extremes.

(5) Use the concentration of measure lemma to give an alternate proof of (13).

(6) Let B_{1} and B_{2} be two σ-algebras on a finite probability space Ω. Use the submodularity inequality (15) to deduce that

H(B_{1} ∨B_{2})+H(B_{1} ∧B_{2}) ≤ H(B_{1})+H(B_{2});

this may help explain the term “submodularity”. In particular we have H(B_{1} ∨B_{2}) ≤ H(B_{1})+H(B_{2}).

(7) (Uniqueness of entropy) Suppose for every finite set K and any discrete random variable X taking values in K, we assigned a non-negative real number H̃(X) which depended only on the probability distribution of X (so we have H̃(X) = H̃(X′) whenever [X] = [X′]), such that H̃ obeyed the identities (6) and (10), where H̃(X|Y) is defined as in (5). Suppose also that for any fixed K, the dependence of H̃(X) on the probabilities P(X = k) is (jointly) continuous. Show that there exists a non-negative constant c ≥ 0

Additive sets A,B  Discrete random variable X,Y
(Log-)cardinality log|A|  Entropy H(X)
Complete sum set A±B  X ±Y with X,Y independent
Partial sum set A±_{G} B  X ±Y with X,Y correlated
Cartesian product A×B  Joint variable (X,Y)
Tensor power A^{⊕N}  N independent trials X_{1},...,X_{N}
Subset A′ of A  Conditioning (X|B) of X
Ruzsa distance d(A,B)  Ruzsa distance d(X,Y)
Functional relationship f : A → B Y is determined by X
(Log-)multiplicity of f : A → B  Conditional entropy H(X|Y)
Additive energy log \frac{|A|^{2}|B|^{2}}{E(A,B)}  Renyi 2-entropy H_{2}(X +Y)

Figure 1. A partial dictionary between sums of additive sets, and discrete random variables.

such that H̃(X) = cH(X) for all random variables X. (Hint: Normalize H̃(X) = H(X) when X is the uniform distribution on {0,1}. Then show that H̃(X) = H(X) whenever X is the uniform distribution on A and |A| is a power of 2. Then, show that H̃(X) = H(X) whenever all the probabilities P(X = x) are either zero or a negative power of 2. Then conclude using the continuity.)

2. Entropy sum set estimates

Let us now work in a fixed additive group G. There is a strong analogy between additive sets A in G and discrete random variables X in G; see Figure 2. For instance, to every additive set A one can associate the uniform distribution X_{A} on A, and H(X_{A}) = log|A|. In the converse direction we have Lemma 1.4, which shows that any random variable X, when sampled a large number M of times, becomes approximately uniform on some large additive set K_{X,M} ⊂ G^{M} of cardinality roughly exp(MH(X)). Note however that since one has to discard an error of o(1) to achieve this, the analogy between the two theories, while mostly accurate, is not completely perfect. However, there are certain areas of additive combinatorics where there is a rigorous equivalence between the sumset-theoretic and entropy-theoretic formulations of a problem; see Section 3.

For finite sets we have |A±B| ≤ |A||B|. The entropy analogue of this is

Lemma 2.1. Let X,Y be discrete random variables in an additive group G, and let ± be a sign. Then

H(X ±Y) ≤ H(X)+H(Y).

If furthermore X and Y are independent, then

max(H(X),H(Y)) ≤ H(X ±Y).

Proof. The first inequality follows immediately from sub-additivity (13). For the second bound, we observe

H(X ±Y) ≥ H(X ±Y |Y) = H(X|Y) = H(X)

where the first inequality is monotonicity (12), the second follows since X ±Y and X determine each other conditioning on Y, and the third is independence (8). From this and symmetry we obtain the claim. □

We can now give the analogue of Ruzsa distance for discrete random variables.

Definition 2.2 (Ruzsa distance). Let X,Y be discrete random variables taking values in an additive group G. We define the Ruzsa distance d(X,Y) between X,Y to be

d(X,Y) := H(X_{1} −Y_{1})− \frac{1}{2}H(X_{1})− \frac{1}{2}H(Y_{1})

where X_{1} and Y_{1} are independent trials of X and Y respectively.

It is clear from the definition that d(X,Y) depends only on the individual distributions of X and Y, and not on the joint distribution, since we have enforced independence of the trials. This is the natural analogue of Ruzsa distance, but for random variables rather than sets. One piece of evidence in this direction is in Exercise 1; another is in the following analogue of the Ruzsa triangle inequality.

Lemma 2.3 (Ruzsa triangle inequality, entropy version). The Ruzsa distance d(X,Y) is non-negative, symmetric, and obeys the triangle inequality

d(X,Z) ≤ d(X,Y)+d(Y,Z)

for all discrete random variables X,Y,Z taking values in an additive group G.

Proof. The symmetry is clear, while the non-negativity follows from Lemma 2.1. It remains to prove the triangle inequality, which is equivalent to showing that

H(X_{1} −Z_{1})+H(Y_{1}) ≤ H(X_{1} −Y_{1})+H(Y_{1} −Z_{1})

where X_{1},Y_{1},Z_{1} are independent trials of X, Y, Z respectively. But if we define the joint random variables

X := (X_{1},Z_{1})
Y := (X_{1} −Y_{1},Y_{1} −Z_{1})
Z := X_{1} −Z_{1}
W := (X_{1},Y_{1},Z_{1})

we see that X determines Z, that Y determines Z, and (X,Y) determines W. Applying the submodularity inequality (15) we then have

H(Z)+H(W) ≤ H(X)+H(Y).

But by independence (8) and sub-additivity (13) we have

H(X) = H(X_{1})+H(Z_{1}); H(Y) ≤ H(X_{1}−Y_{1})+H(Y_{1}−Z_{1}); H(W) = H(X_{1})+H(Y_{1})+H(Z_{1})

and the claim follows. □

We can establish a number of other entropy inequalities in a similar spirit, using elementary arithmetic identities and entropy inequalities such as the submodularity inequality to obtain estimates similar to standard sum set estimates. While the proofs here may seem quite different from the proofs of the sumset estimates, they are at heart the same proof, because they both ultimately rely on the same elementary arithmetic identities. For instance, we have the following analogue of the set inequality |A+B| ≤ |A−B|^{3}/|A||B|.

Proposition 2.4. Let X,Y be discrete random variables in an ambient group G. Then we have

d(X,−Y) ≤ 3d(X,Y)

or in other words, if X_{1},Y_{1} are independent trials of X,Y, then

H(X_{1} +Y_{1}) ≤ 3H(X_{1} −Y_{1})−H(X_{1})−H(Y_{1}).

Proof. Without loss of generality we may assume X,Y are independent (since the claim only depends on the individual distributions of X,Y and not on the joint distribution). It thus suffices to show that H(X_{1} + Y_{1}) ≤ 3H(X − Y) − H(X) − H(Y).

Let (X_{2},Y_{2}) and (X_{3},Y_{3}) be conditionally independent trials of (X,Y) conditioning on X −Y, thus X_{2} −Y_{2} = X_{3} −Y_{3}, and hence

X_{1} +Y_{1} = (X_{1} −Y_{3})−(X_{2} −Y_{1})+X_{3} +Y_{2}.

Thus if we define the joint random variables

X := (X_{1} −Y_{3},X_{2} −Y_{1},X_{3},Y_{2})
Y := (X_{1},Y_{1})
Z := X_{1} +Y_{1}
W := (X_{1},X_{2},X_{3},Y_{1},Y_{2},Y_{3})

we see that X determines Z, that Y determines Z, and (X,Y) determines W. Applying the submodularity inequality (15) we then have

H(Z)+H(W) ≤ H(X)+H(Y).

But by independence (8) and Corollary 1.6 we have

H(Y) = H(X)+H(Y); H(W) = 3H(X)+3H(Y)−H(X −Y)

while from subadditivity (13), and the observation that (X_{1},Y_{3}) and (X_{2},Y_{1}) have the same distribution as (X,Y), we have

H(X) ≤ 2H(X −Y)+H(X)+H(Y).

Combining these inequalities, the claim follows. □

Another result in additive combinatorics says that if A and B are subsets of an additive group then there exists a large sumset S of A + B such that |nS| ≤ O_{n}(|A+B|^{2n+1}/|A|^{n}|B|^{n}) for all n. We have an entropy version of this fact:

Proposition 2.5. Let X,Y be independent discrete random variables taking values in an additive group G, let S := X + Y, and let S_{0},...,S_{n} be n + 1 independent trials of S. Then for any integer n ≥ 0 we have

H(S_{0} +...+S_{n}) ≤ (2n+1)H(X +Y)−nH(X)−nH(Y).

Proof. Without loss of generality we may assume S_{i} = X_{i} +Y_{i} for 0 ≤ i ≤ n, where (X_{i},Y_{i}) are independent trials of (X,Y). Then

S_{0} +...+S_{n} = (Y_{0} +X_{1})+...+(Y_{n−1} +X_{n})+(Y_{n} +X_{0}).

Observe that the random variables Y_{0} +X_{1},...,Y_{n−1+X_{n}},Y_{n} +X_{0},X_{0},Y_{0},S_{1},...,S_{n} will determine all of the X_{i}, Y_{i}. Thus if we set

X := (Y_{0} +X_{1},...,Y_{n−1} +X_{n},Y_{n} +X_{0})
Y := (X_{0},Y_{0},S_{1},...,S_{n})
Z := S_{0} +...+S_{n}
W := (X_{0},...,X_{n},Y_{0},...,Y_{n})

we see that X determines Z, that Y determines Z, and (X,Y) determines W. Applying the submodularity inequality (15) we then have

H(Z)+H(W) ≤ H(X)+H(Y).

However, by subadditivity (13) we have H(X) ≤ (n + 1)H(X + Y) and H(Y) ≤ H(X)+H(Y)+nH(X +Y), while from independence (8) we have H(W) = (n+ 1)H(X)+(n+1)H(Y). The claim follows. □

From this and the Ruzsa triangle inequality, one can obtain the inequality (16) H(X_{1}+...+X_{n}−X′_{1}−...−X′_{n′} +Y_{1}+...+Y_{m}−Y′_{1}−...−Y′_{m′}) ≤ H(X)+C(n+n′+m+m′)d(X,X)

whenever n,n′,m,m′ and the random variables in the left-hand side are independent trials of X and Y; see Exercise 4. Another consequence is that

(17)  d(X_{1} −X_{2},X_{1} −X_{2}) <= 2d(X,X)

whenever X_{1},X_{2} are independent trials of X.

The additive energy has an information theoretic counterpart relating to the Renyi 2-entropy; see Exercise 12 or [4].

There are analogues of the Balog-Szemerédi-Gowers theorem for random variables. The main point of the Balog-Szemerédi-Gowers theorem was to pass from cardinality control on a partial sum set to cardinality control on a complete sum set; here, the idea will be to pass from entropy control of a sum of correlated random variables to entropy control of a sum of (conditionally) independent random variables. We first give an entropy version of a weak Balog-Szemerédi theorem.

Lemma 2.6 (Weak Balog-Szemerédi-Gowers theorem, entropy version). Let (X,Y) be a pair of discrete random variables, not necessarily independent, taking values in G×G. Let (X_{1},Y), (X_{2},Y) be conditionally independent trials of (X,Y) conditioning on Y. Then

H(X_{1} −X_{2}|Y) ≤ 2H(X +Y)+2H(X)+H(Y)−2H(X,Y).

In particular, if we have H(X,Y) ≥ H(X) + H(Y) − logK and H(X + Y) ≤ \frac{1}{2}H(X)+ \frac{1}{2}H(Y)+logK′ then

H(X_{1}|Y) = H(X_{2}|Y) ≥ H(X)−logK

(thanks to (6)) and

H(X_{1} −X_{2}|Y) ≤ H(X)+2logK +2logK′.

Proof. We view (X_{1},X_{2},Y) as a single random variable taking values in G, and create two conditionally independent trials (X_{1},X_{2},Y) and (X_{1},X_{2},Y′) of this variable conditioning on (X_{1},X_{2}), thus by Corollary 1.6

H(X_{1},X_{2},Y,Y′) = 2H(X_{1},X_{2},Y)−H(X_{1},X_{2})
≥ 2(2H(X,Y)−H(Y))−(H(X_{1})+H(X_{2}))
= 4H(X,Y)−2H(Y)−2H(X).

Now we use submodularity again, introducing

X := (X_{1} +Y′,X_{2} +Y′,Y)
Y := (X_{1},X_{2},Y)
Z := (X_{1} −X_{2},Y)
W := (X_{1},X_{2},Y,Y′).

Observe that X determines Z, that Y determines Z, and (X,Y) determines W, and thus

H(Z)+H(W) ≤ H(X)+H(Y).

We have already computed that H(W) ≥ 4H(X,Y)−2H(Y)−2H(X); also from Corollary 1.6 we have

H(Y) = 2H(X,Y)−H(Y)

and by Bayes’ formula (6)

H(Z) = H(X_{1} −X_{2}|Y)+H(Y).

Finally, by subadditivity (13) we have

H(X) ≤ 2H(X +Y)+H(Y)

since (X_{1},Y′) and (X_{2},Y′) both have the same distribution as (X,Y). Combining all these inequalities, the claim follows. □

Now we give the counterpart to the full Balog-Szemerédi-Gowers theorem.

Theorem 2.7 (Balog-Szemerédi-Gowers theorem, entropy version). Let (X,Y) be a pair of discrete random variables, not necessarily independent, taking values in G× G. Let (X_{1},Y), (X_{2},Y) be conditionally independent trials of (X,Y) conditioning on Y, and then let (X′_{1},X′_{2},Y_{1}) and (X′_{1},Y_{2}) be conditionally independent trials of (X_{1},X_{2},Y) and (X,Y) conditioning on X_{1} = X. Then

H(X′_{2}|X′_{1},Y_{1}) = H(X|Y); H(Y_{2}|X′_{1},Y_{1}) = H(Y |X)

and

H(X′_{2} +Y_{2}|X′_{1},Y_{1}) ≤ 3H(X +Y)+3H(X)+3H(Y)−4H(X,Y).

Furthermore, X′_{2} and Y_{2} are conditionally independent, conditioning on X′_{1},Y_{1}. In particular, if H(X,Y) ≥ H(X)+H(Y)−logK and H(X +Y) ≤ \frac{1}{2}H(X)+ \frac{1}{2}H(Y)+ logK′ then

H(X′_{2}|X′_{1},Y_{1}) ≥ H(X)−logK; H(Y_{2}|X′_{1},Y_{1}) ≥ H(Y)−logK; H(X′_{2}+Y_{2}|X′_{1},Y_{1}) ≤ \frac{1}{2}H(X)+ \frac{1}{2}H(Y)+3logK′+4logK.

Proof. By construction, if one conditions on X′_{1} then Y_{2} and (X′_{2},Y_{1}) are conditionally independent, which implies that X′_{2} and Y_{2} are conditionally independent conditioning on X′_{1},Y_{1}. Also, since (X′_{1},X′_{2},Y_{1}) has the same distribution as (X_{1},X_{2},Y), we have

H(X′_{2}|X′_{1},Y′_{1}) = H(X_{2}|X_{1},Y) = H(X_{2}|Y) = H(X|Y)

since X_{1} is independent of (X_{2},Y). Similarly, since Y_{2} and Y_{1} are independent conditioning on X′_{1}, we have (by (9))

H(Y_{2}|X′_{1},Y_{1}) = H(Y_{2}|X′_{1}) = H(Y |X).

It remains to establish the bound on H(X′_{2} +Y_{2}|X′_{1},Y_{1}). By Lemma 2.6 we already have

H(X′_{1} −X′_{2}|Y_{1}) ≤ 2H(X +Y)+2H(X)+H(Y)−2H(X,Y).

We then apply the submodularity inequality with

X := (X′_{2},Y_{2},Y_{1})
Y := (X′_{1} −X′_{2},X′_{1} +Y_{2},Y_{1})
Z := (X′_{2} +Y_{2},Y_{1})
W := (X′_{1},X′_{2},Y_{1},Y_{2});

it is clear that X determines Z, that Y determines Z, and (X,Y) determine W, so by (15) we have

H(Z)+H(W) ≤ H(X)+H(Y).

From sub-additivity we have H(X) ≤ H(X′_{2},Y_{1})+H(Y_{2}) = H(X,Y)+H(Y) and

H(Y) ≤ H(X′_{1} −X′_{2}|Y_{1})+H(Y_{1})+H(X′_{1} +Y_{2})
≤ (2H(X +Y)+2H(X)+H(Y)−2H(X,Y))+H(Y)+H(X +Y)

while from two applications of Corollary 1.6 we have

H(W) = H(X′_{1},X′_{2},Y_{1})+H(X′_{1},Y_{2})−H(X′_{1})
= (2H(X,Y)−H(Y))+H(X,Y)−H(X)

and from (6) we have H(Z) = H(X′_{2} +Y_{2}|Y_{1})+H(Y). Combining these inequalities gives the result. □

As the above examples show, there is certainly a strong analogy between sum set estimates, and entropy inequalities for sums of random variables. However the latter theory has not been developed nearly as thoroughly as the former; for instance we do not have a “Freiman theorem” which classifies the random variables X for which d(X,X) or d(X,−X) is small. Nor do we have an analogue of the Plünnecke inequalities for random variables.

(1) Let A,B be additive sets with ambient group G, and let X_{A} and X_{B} be uniform distributions on A and B respectively. Show that d(X_{A},X_{B}) ≤ d(A,B). (Hint: use (1)).

(2) Let X,Y be discrete random variables taking values in a group G. Show that |H(X)−H(Y)| ≤ \frac{1}{2}d(X,Y).

(3) Let X,Y be independent random variables, and let (X_{1},Y_{1}) and (X_{2},Y_{2}) be conditionally independent trials of (X,Y) conditioning on X +Y, thus we have Y_{2} = X_{1} −X_{2} +Y_{1}. Show that H(X_{1},X_{2},Y_{1}|Y_{2}) = 2H(X)+H(Y)− H(X +Y). (This result is analogous to Ruzsa’s covering lemma.)

(4) Deduce (16) and (17) from Proposition 2.5. What constant C can you get for (16)?

(5) Let X,Y be independent discrete random variables taking values in an additive group G, let Y_{1},Y_{2},Y_{3},Y_{4} be independent trials of Y, and let X_{5},X_{6} be independent trials of X. Show that

H(Y_{1} −Y_{2} −Y_{3} +Y_{4}) ≤ 4H(X +Y)+H(X_{5} −X_{6})−4H(X),

which is the counterpart of the set inequality |2A − 2A| ≤ \frac{|A+B|^{4}|B−B|}{|B|^{4}}. Hint: let (X_{3},Y_{3}) and (X_{5},Y_{5}) be conditionally independent trials of (X,Y) conditioning on X + Y, let (X_{4},Y_{4}) and (X_{6},Y_{6}) be another pair of conditionally independent trials of (X,Y) conditioning on X + Y which are independent of the preceding random variables, and let Y_{1},Y_{2} be two independent trials of Y which are independent of all preceding variables. Exploit the submodularity inequality applied to the random variables

X := (X_{3} +Y_{1},X_{5} −Y_{6},X_{4} +Y_{2},Y_{5},Y_{6})
Y := (Y_{1},Y_{2},Y_{3},Y_{4})
Z := Y_{1} −Y_{2} +Y_{3} +Y_{4}
W := (X_{3},X_{4},X_{5},X_{6},Y_{1},Y_{2},Y_{3},Y_{4},Y_{5},Y_{6}).

taking advantage of the identity

Y_{1} −Y_{2} −Y_{3} +Y_{4} = (X_{3} +Y_{1})−(X_{5} −X_{6})−(X_{4} +Y_{2})−Y_{5} +Y_{6}.

(6) Suppose that X,Y are discrete random variables in an ambient group G such that d(X,Y) = 0. Show that there exists a finite subgroup H in G, and elements x,y ∈ G, such that X is the uniform distribution on x + H and Y is the uniform distribution on y + H. (Hint: Use Exercise 4 from Section 1).

(7) Develop entropy analogues of non-commutative sumset theory.

(8) [Imre Ruzsa, private communication] Let X,Y be independent discrete random variables taking values in an additive group G, and suppose that H(X +Y) > H(X −Y). Let 0 < α < H(X), 0 < β < H(Y) be real numbers chosen so that H(X −Y) < α+β < H(X +Y) (this is always possible, thanks to Lemma 2.1). Let n be a large number, and let (X_{1},...,X_{n}),(Y_{1},...,Y_{n}) ∈ G^{n} be independent trials of X and Y respectively. let A,B ⊆ G^{n} be chosen by letting A be the values of ⌊e^{αn}⌋ independent trials of (X_{1},...,X_{n}), and letting B be the values of ⌊e^{βn}⌋ independent trials of (Y_{1},...,Y_{n}) (independent of the trials used to select A). Show that with probability 1 − o(1), one has |A| = e^{(α−o(1))n}, |B| = e^{(β−o(1))n}, |A + B| = e^{(α+β−o(1))n}, but |A − B| ≤ e^{(α+β−ε+o(1))n} for some ε > 0 depending only in α, β, X, Y. Thus |A + B| is close to |A||B| but |A − B| is significantly smaller than A,B. (Hint: the elements a ∈ A, b ∈ B for which a does not have the statistics of X, b does not have the statistics of Y, a + b does not have the statistics of X + Y, or a − b does not have the statistics of X − Y all give negligible contributions thanks to Lemma 1.4. To get the lower bound on |A + B|, estimate the multiplicity of A + B at points which have the statistics of X +Y).

(9) [Imre Ruzsa, private communication] By modifying the arguments in Exercise 8, give an example of an arbitrarily large additive set A such that |A + A| = |A|^{2−o(1)} but |A − A| ≤ |A|^{2−ε+o(1)} for some absolute constant ε > 0, or such that |A−A| = |A|^{2−o(1)} but |A+A| ≤ |A|^{2−ε+o(1)} for some absolute constant ε > 0.

(10) If X is a discrete random variable, we define the Renyi 2-entropy H_{2}(X) to be the quantity H_{2}(X) := −log_{2} ∑_{k} P(X = k)^{2}. Show that H(X) ≤ H_{2}(X), with equality if and only if X has a uniform distribution. The Renyi 2-entropy is also known as the extension entropy, and the quantity ∑_{k} P(X = k)^{2} is also known as the collision probability.

(11) [4] Let X, Y be independent variables taking values in an additive group. Show that H_{2}(X −Y) = H_{2}(X +Y) ≤ \frac{1}{2}H_{2}(X −X)+ \frac{1}{2}H_{2}(Y −Y).

(12) Let A and B be additive sets in an ambient group G, and let X,Y be random variables selected uniformly and independently from A and B respectively. Show that H_{2}(X +Y) = H_{2}(X −Y) = log \frac{|A|^{2}|B|^{2}}{E(A,B)} .

3. Entropy inequalities of Kakeya and Erdös distance type

One striking development in recent years is the discovery that entropy sum set inequalities for non-independent pairs of variables X,Y can be of great utility in some classical problems in incidence geometry, in particular the Kakeya problem and the Erdös distance problem. We phrase these two problems as follows.

Conjecture 3.1 (Geometric Kakeya conjecture for finite fields). Let F be a finite field and let d ≥ 1, thus F^{d} is a vector space over the field F. Let E ⊆ F^{d} be a set such that given any v ∈ F^{d} there exists an x ∈ F^{d} such that the line {x+tv : t ∈ F } is completely contained in F. Then we have |E| ≥ c_{ε,d}|F |^{d−ε} for every ε > 0, where c_{ε,d} > 0 is a quantity that does not depend on F or E, provided that the characteristic of F is sufficiently large depending on ε. (It may even be possible to take ε = 0; no counterexample to this claim is known).

Conjecture 3.2 (Geometric Erdös distance conjecture). Let P be a set of n points in the plane R^{2}, and let Δ(P) := {|x−y| : x,y ∈ P } be the set of distances. Then |Δ(P)| ≥ c_{ε}n^{2−ε} for every ε > 0, where c_{ε} > 0 is a quantity that does not depend on n or P.

These conjectures remain open, but in both cases some partial bounds are known. For instance, using geometric methods one can obtain the lower bounds of |E| ≥ c_{d}|F |^{(d+2)/2} for the Kakeya conjecture and of |Δ(P)| ≥ cn^{4/5} for the Erdös distance problem. But the only known improvement to these bounds have come from employing methods from additive combinatorics (with the exception of the finite field Kakeya problem in four dimensions, in which algebraic geometry has been used to obtain a slight additional improvement). In particular, the following two conjectures have been identified:

Conjecture 3.3 (Entropy Kakeya conjecture). Given any ε > 0 there exist numbers r_{1},...,r_{k} ∈ (Q\{−1})∪{∞} such that one has the entropy inequality

(18)  H(X −Y) ≤ (1+ε) max_{1≤i≤k}H(X +r_{i}Y)

for all discrete random variables X,Y (not necessarily independent) in an finite vector space F^{d−1}, provided that the characteristic of F is sufficiently large depending on ε (in particular, so that multiplication by r_{i} will make sense). Here we adopt the convention that H(X +∞Y) = H(Y).

Conjecture 3.4 (Entropy Erdös distance conjecture). Given any ε > 0 there exists a d ≥ 3 such that one has the entropy inequality

H(X_{1},...,X_{d}) ≤ (2+ε) max_{1≤i<j≤d}H(X_{i} +X_{j})

whenever X_{1},...,X_{d} are discrete random variables (not necessarily independent) in the real line R, with the property that X_{1},...,X_{d} is determined by any of the X_{i} (thus H(X_{1},...,X_{d}|X_{i}) = 0 for all 1 ≤ i ≤ d).

A version of the Entropy Kakeya conjecture is implicit in [6] and [15], but the entropy formulation given above is due to Ruzsa (private communication). A version of the Entropy Erdös conjecture is implicit in [25], but the entropy formulation given above is due to [13]. For a more systematic study of these conjectures (and in particular a surprising connection to the theory of finite groups) see [14].

The connection between the entropy and geometric versions of these conjectures is the following. It was implicitly noted in [6] that if the entropy Kakeya conjecture is true for some ε > 0, then the geometric Kakeya conjecture is true with ε replaced by \frac{ε}{ε+1}(d−1); in particular the full entropy Kakeya conjecture would imply the full geometric Kakeya conjecture. In [29] (and implicitly in [25]) it was shown that if the entropy Erdös distance conjecture were true for some ε > 0, then the geometric Erdös distance conjecture would be true with ε replaced by any quantity greater than 1− \frac{4}{5−1/(2−ε)}. In particular, the full entropy Erdös distance conjecture would imply the geometric Erdös distance conjecture for all ε > 1/9 = 0.111... (currently this is only known for ε > 3/22, see [13]). We sketch the connection between the two Kakeya conjectures Exercises 1, 2, and the connection between the two Erdös conjectures in ???.

For now, we give some partial results on these two entropy conjectures, beginning with the entropy Kakeya conjecture. We will always assume that the characteristic of the field F is large enough that one can make sense of multiplication by the rational numbers involved. Observe that for any distinct r,r′ ∈ Q\{−1} ∪ {∞}, that X −Y is completely determined by X +rY and X +r′Y, and hence we have

H(X −Y) ≤ H(X +rY)+H(X +r′Y).

This establishes the entropy Kakeya conjecture for ε ≥ 1. Now we lower the value of ε.

Proposition 3.5. [15] Let X,Y be two discrete random variables (not necessarily independent) taking values in an additive group where every non-zero element has order at least 3. Then

3H(X,Y)+H(X −Y) ≤ 2H(X)+2H(Y)+2H(X +Y)+H(X +2Y).

Since H(X −Y) ≤ H(X,Y), this establishes the entropy Kakeya conjecture for ε ≥ 1−1/4.

Proof. Let (X,Y), (X,Y′) be two conditionally independent trials of (X,Y) conditioning on X. We then apply the submodularity inequality to the random variables

X := (Y,X +2Y)
Y := (X +Y,X +Y′)
Z := Y −(X +2Y′) = (X +Y)−2(X +Y′)
W := (X,Y,Y′)

to conclude

H(Y −X −2Y′)+H(X,Y,Y′) ≤ H(Y)+H(X +2Y)+2H(X +Y).

But by Corollary 1.6 we have H(X,Y,Y′) = 2H(X,Y)−H(X). Also, since X −Y is clearly determined by Y −X −2Y′ and Y′ we have H(X −Y) ≤ H(Y −X −2Y′)+ H(Y). Inserting these bounds in the above inequality, the claim follows. □

In a similar vein, we have the following estimate which only establishes the entropy Kakeya conjecture for ε ≥ 1 − 1/6 = 0.833... but does not require the random variable X +2Y. This is actually fairly sharp; see Exercise 5. The estimate also has some application to partial sum and difference sets, see Exercise 4.

Proposition 3.6. [15] Let X,Y be two discrete random variables (not necessarily independent) taking values in an additive group G. Then

5H(X,Y)+H(X −Y) ≤ 4H(X)+4H(Y)+3H(X +Y).

Proof. As before we let (X,Y) and (X,Y′) be two conditionally independent trials of (X,Y) conditioning on X. Applying the submodularity inequality to the random variables

X := (X +Y,X +Y′)
Y := (Y,Y′)
Z := Y −Y′
W := (X,Y,Y′)

we conclude that

(19)  H(Y −Y′)+H(X,Y,Y′) ≤ 2H(Y)+2H(X +Y).

Next, we let (X,Y,Y′) and (X′′,Y′′,Y′) be two conditionally independent trials of (X,Y,Y′) conditioning on Y′ and on X +Y = X′′ +Y′′. Then by Corollary 1.6

H(X,Y,Y′,X′′,Y′′) = 2H(X,Y,Y′)−H(Y)−H(X +Y).

On the other hand, we split (using (12))

H(X,Y,Y′,X′′,Y′′) = H(X′′,Y′,X′′−Y′,X,Y′′,Y −Y′) ≤ H(X′′,Y′|X′′−Y′)+H(X′′−Y′,X,Y′′,Y −Y′).

But from the identity

X′′ −Y′ = X −Y′′ +(Y −Y′)

we see that X′′ −Y′ is determined by X, Y′′, and Y −Y′, and thus

H(X′′ −Y′,X,Y′′,Y −Y′) = H(X,Y′′,Y −Y′) ≤ H(X)+H(Y)+H(Y −Y′).

Combining these inequalities we obtain

2H(X,Y,Y′)−H(Y)−H(X +Y) ≤ H(X,Y |X −Y)+H(X)+H(Y)+H(Y −Y′).

Inserting this into (19) we obtain

3H(X,Y,Y′) ≤ H(X)+4H(Y)+3H(X +Y)+H(X,Y |X −Y).

From Corollary 1.6 we have H(X,Y,Y′) = 2H(X,Y) − H(X), while H(X,Y |X − Y) = H(X,Y)−H(X −Y). The claim follows. □

For some further progress on the entropy Kakeya conjecture, see [16]; the best known result is that this conjecture is true for all ε > 0.67513....

Now we consider the entropy Erdös conjecture. Observe that if X_{1},X_{2},X_{3} are real valued, then (X_{1},X_{2},X_{3}) are determined by X_{1} +X_{2}, X_{2} +X_{3}, and X_{3} +X_{1}, thus

H(X_{1},X_{2},X_{3}) ≤ H(X_{1} +X_{2})+H(X_{2} +X_{3})+H(X_{3} +X_{1}).

This establishes the entropy Erdös conjecture when ε = 1 (this was first observed implicitly in [25]). By increasing d = 3 to d = 5 one can improve ε to 3/4:

Proposition 3.7. [29] Let X_{1},X_{2},X_{3},X_{4},X_{5} be random variables taking values in an additive group where all non-zero elements have order at least three, and such that (X_{1},X_{2},X_{3},X_{4},X_{5}) is determined by X_{i} for each 1 ≤ i ≤ 5. Then

H(X_{1},X_{2},X_{3},X_{4},X_{5}) ≤ (3− \frac{1}{4}) max_{1≤i<j≤5}H(X_{i} +X_{j}).

Proof. Let us normalize max_{1≤i<j≤5} H(X_{i} +X_{j}) = logN. By (14) we have

H(X_{1} +X_{3},X_{1} +X_{4},X_{1} +X_{5}|X_{1} −X_{2}) ≤ ∑_{j=3,4,5}H(X_{1} +X_{j}|X_{1} −X_{2}).

Observe that X_{1} +X_{4},X_{1} +X_{5} determine X_{4} −X_{5}, hence (20)

H(X_{1} +X_{3},X_{1} +X_{4},X_{1} +X_{5},X_{4} −X_{5}|X_{1} −X_{2}) ≤ ∑_{j=3,4,5}H(X_{1} +X_{j}|X_{1} −X_{2}).

By (12) we have

H(X_{1}+X_{3},X_{1}+X_{4},X_{1}+X_{5},X_{3}+X_{4},X_{4}−X_{5}|X_{1}−X_{2}) ≤ H(X_{1}+X_{3},X_{1}+X_{4},X_{1}+X_{5},X_{4}−X_{5}|X_{1}−X_{2})+H(X_{3}+X_{4}|X_{4}−X_{5})

But observe that from X_{1}+X_{3},X_{1}+X_{4},X_{3}+X_{4} one can already determine X_{1},X_{3},X_{4}, which then determine all the X’s by hypothesis. Thus

H(X_{1},X_{2},X_{3},X_{4},X_{5}|X_{1}−X_{2}) ≤ H(X_{1}+X_{3},X_{1}+X_{4},X_{1}+X_{5},X_{4}−X_{5}|X_{1}−X_{2})+H(X_{3}+X_{4}|X_{4}−X_{5}).

Combining this with (20) we obtain

H(X_{1},X_{2},X_{3},X_{4},X_{5}) ≤ ∑_{j=3,4,5}H(X_{1}+X_{j}|X_{1}−X_{2})+H(X_{1}−X_{2})+H(X_{3}+X_{4}|X_{4}−X_{5}).

Now we observe that

H(X_{3}+X_{4}|X_{4}−X_{5}) = H(X_{3}+X_{4},X_{3}+X_{5}|X_{4}−X_{5}) ≤ H(X_{3}+X_{4})+H(X_{3}+X_{5})−H(X_{4}−X_{5}) ≤ 2logN −H(X_{4}−X_{5})

and similarly for H(X_{1} +X_{j}|X_{1} −X_{2}), thus

H(X_{1},X_{2},X_{3},X_{4},X_{5}) ≤ 8logN −2H(X_{1} −X_{2})−H(X_{4} −X_{5}).

On the other hand, we have

H(X_{1},X_{2},X_{3},X_{4},X_{5}) = H(X_{1}) ≤ H(X_{1}+X_{2})+H(X_{1}−X_{2}) ≤ logN +H(X_{1}−X_{2})

and similarly for H(X_{4} −X_{5}). Thus we have

H(X_{1},X_{2},X_{3},X_{4},X_{5}) ≤ 11logN −3H(X_{1},X_{2},X_{3},X_{4},X_{5})

and the claim follows. □

The constant 3 − \frac{1}{4} in the above proposition was improved further to 3 − \frac{2}{7} in [13] by using the technique of conditionally independent trials as in Proposition 3.6 and Proposition 3.5. Combining these arguments with an additional iteration argument, the arithmetic Erdös conjecture was established in [13] for all ε > \frac{4−e}{10−3e} = 0.69464....

(1) (Ruzsa, private communication) Suppose that ε,r_{1},...,r_{k},F,d−1 are such that the entropy inequality (18) holds. Let A,B ⊂ F^{d−1} be additive sets. Establish the inequality

(21)  |A−_{G} B| ≤ ( max_{1≤i≤k}|A+_{G} r_{i} ·B|)^{1+ε}

where by slight abuse of notation we have A+_{G} r·B := {a+rb : (a,b) ∈ G} and one adopts the convention that |A+_{G} ∞·B| = |{b : (a,b) ∈ G}|. (Hint: first refine G so that the map (a,b) ↦ a − b is injective on G, and then consider the uniform distribution on G). Conversely, if the inequality (21) holds for all A,G,B and all dimensions d, establish the entropy inequality (18) for the same values of ε,r_{1},...,r_{k},F. (Hint: use Lemma 1.4 to convert the random variables into approximately uniform distributions, and eliminate the o(1) losses using a tensor power trick).

(2) Suppose that ε,r_{1},...,r_{k},F,d are such that the entropy inequality (18) holds. Let E ⊆ F^{d} be as in the geometric Kakeya conjecture, and for each t ∈ F let E_{t} := {x ∈ F^{d−1} : (x,t) ∈ E} be the “slice” of E at height t. Let t_{i} ∈ F be such that r_{i} = t_{i}/(1−t_{i}). Using Exercise 1, establish the inequality

|F |^{d−1} ≤ ( max_{1≤i≤k}|E_{t_{i}+s}|)^{1+ε}

for any s ∈ F. Conclude in particular that

|E| ≥ |F |^{d− \frac{ε}{ε+1} (d−1)}.

(3) [29] Let ε > 0 and d ≥ 3 be such that the entropy Erdös distance conjecture holds. Let G be a subset of R^{d} such that the co-ordinate maps (x_{1},...,x_{d}) ↦ x_{i} are injective on G for each 1 ≤ i ≤ d, and such that

|{x_{i} +x_{j} : (x_{1},...,x_{d}) ∈ G}| ≤ N

for all 1 ≤ i < j ≤ d and some N ≥ 1. Conclude that |G| ≤ N^{2+ε}.

(4) Using Proposition 3.6, establish the inequality

|A−_{G} B| ≤ \frac{|A|^{4}|B|^{4}|A+_{G} B|^{3}}{|G|^{5}}

for any additive sets A,B in an ambient group Z, and any non-empty G ⊆ A×B. If all non-zero elements in Z have order at least three, establish the inequality

|A−_{G} B| ≤ \frac{|A|^{2}|B|^{2}|A+_{G} B|^{2}|A+_{G} 2·B|}{|G|^{3}}.

For a proof of these inequalities which does not require entropy, see [15].

(5) (Ruzsa, private communication). Let F be a finite field, let (X,Y) ∈ F ×F be the uniform distribution on {(0,0),(0,1),(1,0)}. Show that

H(X −Y) = (1+ε)max(H(X),H(Y),H(X +Y))

where ε := \frac{log 27}{log 27/4} −1 = 0.726....

(6) Assume the Erdös distance conjecture (Conjecture 3.2). Conclude that for any additive set A of real numbers, one has |f(A−A)+f(A−A)| ≥ c_{ε}|A|^{2−ε} for all ε > 0, where f : R → R is the squaring function f(x) := x^{2}. This statement, which is thus weaker than the Erdös distance conjecture, remains open.

References

[1] M. Ajtai, V. Chvátal, M. Newborn, and E. Szemerdi, Crossing-free subgraphs, Annals of Discrete Mathematics 12 (1982), 9–12.

[2] B. Aronov, J. Pach, M. Sharir, G. Tardos, Distinct distances in three and higher dimensions, Combin. Probab. Comput. 13 (2004), no. 3, 283–293.

[3] A. Balog, E. Szemerédi, A statistical theorem of set addition, Combinatorica, 14 (1994), 263–268.

[4] B. Barak, R. Impagliazzo, A. Wigderson, Extracting randomness using few independent sources, preprint.

[5] J. Beck, On the lattice property of the plane and some problems of Dirac, Motzkin, and Erdos in combinatorial geometry, Combinatorica 3 (1983), 281–297.

[6] J. Bourgain, On the dimension of Kakeya sets and related maximal inequalities, GAFA 9 (1999), 256–282.

[7] F. Chung, The number of distinct distances determined by n points in the plane, J. Combin. Theory Ser. A 36 (1984), 342–354.

[8] F. Chung, E. Szemerédi, W. Trotter, The number of different distances determined by a set of n points in the Euclidean plane, Discrete Computational Geom. 7 (1992), 1–11.

[9] K. Clarkson, H. Edelsbrunner, L. Gubias, M. Sharir, E. Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete Comput. Geom. 5 (1990), 99–160.

[10] P. Erdős, On sets of distances of n points, Amer. Math. Monthly 53 (1946), 248–250.

[11] J. Garibaldi, Erdős distance problem for convex metrics, UCLA Ph.D. Thesis.

[12] A. Iosevich, Curvature, combinatorics, and the Fourier transform, Not. Amer. Math. Soc. 48 (2001), 577–583.

[13] N. Katz, G. Tardos, A new entropy inequality for the Erdős distance problem, Towards a theory of geometric graphs, (ed. J. Pach), Contemporary Mathematics 342 (2004), 119–126.

[14] N. Katz, On arithmetic combinatorics and finite groups, preprint.

[15] N. Katz, T. Tao, Bounds on arithmetic progressions, and applications to the Kakeya conjecture, Math. Res. Letters 6 (1999), 625–630.

[16] N. Katz, T. Tao, New bounds for Kakeya problems, Journal d’Analyse de Jerusalem, 87 (2002), 231–263.

[17] N. Katz, T. Tao, Some connections between the Falconer and Furstenburg conjectures, New York J. Math. 7 (2001), 148–187.

[18] G. Mockenhaupt, T. Tao, Kakeya and restriction phenomena for finite fields, Duke Math. J. 121 (2004), 35-74

[19] L. Moser, On the different distances determined by n points, Amer. Math. Monthly 59 (1952), 85–91.

[20] J. Pach, Crossing numbers, Discrete and computational geometry (Tokyo, 1998), 267–273, Lecture Notes in Comput. Sci., 1763, Springer, Berlin, 2000.

[21] J. Pach, G. Tardos, Isosceles triangles determined by a planar point set, Graphs and Combinatorics 18 (2002), 769–779.

[22] J. Pach and G. Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997), 427–439.

[23] J. Solymosi, V. Vu, Distinct distances in high dimensional homogeneous sets, preprint.

[24] J. Solymosi, V. Vu, Near optimal bound for the distinct distances problem in high dimensions, preprint.

[25] J. Solymosi, C. D. Tóth, Distinct distances in the plane, Discrete Comput. Geom. 25 (4) (2001), 629–634.

[26] J. Solymosi, G. Tardos, C.D. Tóth, The k most frequent distances in the plane, preprint.

[27] L. Székely, Crossing numbers and hard Erdős problems in discrete geometry, Combin. Probab. Comput. 6 (1997), 353–358.

[28] E. Szemerédi, W. T. Trotter Jr., Extremal problems in discrete geometry, Combinatorica 3 (1983), 381–392.

[29] G. Tardos, On distinct sums and distinct distances, preprint.

[30] T. Tao, Finite field analogues of the Erdős, Falconer, and Furstenburg problems, unpublished.

[31] C. Toth, The Szemeredi-Trotter theorem in the complex plane, to appear.