Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao

Subscribe to feed

Metric entropy analogues of sum set theory

19 March, 2014 inexpository,math.CO,math.MG | Tags:additive combinatorics,metric entropy,sum set estimates | byTerence Tao

A core foundation of the subject now known asarithmetic combinatorics (and particularly the subfield ofadditive combinatorics) are the elementary sum set estimates (sometimes known as “Ruzsa calculus”) that relate the cardinality of various sum sets

$\displaystyle A+B := \{ a+b: a \in A, b \in B \}$

and difference sets

$\displaystyle A-B := \{ a-b: a \in A, b \in B \},$

as well as iterated sumsets such as {3A=A+A+A} , {2A-2A=A+A-A-A} , and so forth. Here, {A, B} are finite non-empty subsets of some additive group {G = (G,+)} (classically one took ${G={\bf Z}}$ or ${G={\bf R}}$ , but nowadays one usually considers more general additive groups). Some basic estimates in this vein are the following:

Lemma 1 (Ruzsa covering lemma) Let be finite non-empty subsets of. Then may be covered by at most ${\frac{|A+B|}{|B|}}$ translates of.

Proof: Consider a maximal set of disjoint translates {a+B} of {B} by elements ${a \in A}$ . These translates have cardinality {|B|} , are disjoint, and lie in {A+B} , so there are at most ${\frac{|A+B|}{|B|}}$ of them. By maximality, for any ${a' \in A}$ , {a'+B} must intersect at least one of the selected {a+B} , thus ${a' \in a+B-B}$ , and the claim follows. $\Box$

Lemma 2 (Ruzsa triangle inequality) Let be finite non-empty subsets of. Then ${|A-C| \leq \frac{|A-B| |B-C|}{|B|}}$ .

Proof: Consider the addition map ${+: (x,y) \mapsto x+y}$ from ${(A-B) \times (B-C)}$ to {G} . Every element {a-c} of {A - C} has a preimage ${\{ (x,y) \in (A-B) \times (B-C)\}}$ of this map of cardinality at least {|B|} , thanks to the obvious identity {a-c = (a-b) + (b-c)} for each ${b \in B}$ . Since ${(A-B) \times (B-C)}$ has cardinality {|A-B| |B-C|} , the claim follows. $\Box$

Such estimates (which are covered, incidentally, in Section 2 ofmy book with Van Vu) are particularly useful for controlling finite sets {A} of small doubling, in the sense that ${|A+A| \leq K|A|}$ for some bounded {K} . (There are deeper theorems, most notablyFreiman’s theorem, which give more control than what elementary Ruzsa calculus does, however the known bounds in the latter theorem are worse than polynomial in {K} (although it isconjectured otherwise), whereas the elementary estimates are almost all polynomial in {K} .)

However, there are some settings in which the standard sum set estimates are not quite applicable. One such setting is the continuous setting, where one is dealing with bounded open sets in an additive Lie group (e.g. ${{\bf R}^n}$ or a torus ${({\bf R}/{\bf Z})^n}$ ) rather than a finite setting. Here, one can largely replicate the discrete sum set estimates by working with a Haar measure in place of cardinality; this is the approach taken for instance inthis paper of mine. However, there is another setting, which one might dub the “discretised” setting (as opposed to the “discrete” setting or “continuous” setting), in which the sets {A} remain finite (or at least discretisable to be finite), but for which there is a certain amount of “roundoff error” coming from the discretisation. As a typical example (working now in a non-commutative multiplicative setting rather than an additive one), consider the orthogonal group ${O_n({\bf R})}$ of orthogonal ${n \times n}$ matrices, and let {A} be the matrices obtained by starting with all of the orthogonal matrice in ${O_n({\bf R})}$ and rounding each coefficient of each matrix in this set to the nearest multiple of ${\epsilon}$ , for some small ${\epsilon>0}$ . This forms a finite set (whose cardinality grows as ${\epsilon\rightarrow 0}$ like a certain negative power of ${\epsilon}$ ). In the limit ${\epsilon \rightarrow 0}$ , the set {A} is not a set of small doubling in the discrete sense. However, ${A \cdot A}$ is still close to {A} in a metric sense, being contained in the ${O_n(\epsilon)}$ -neighbourhood of {A} . Another key example comes from graphs ${\Gamma := \{ (x, f(x)): x \in G \}}$ of maps ${f: A \rightarrow H}$ from a subset {A} of one additive group {G = (G,+)} to another {H = (H,+)} . If {f} is “approximately additive” in the sense that for all ${x,y \in G}$ , {f(x+y)} is close to {f(x)+f(y)} in some metric, then ${\Gamma}$ might not have small doubling in the discrete sense (because {f(x+y)-f(x)-f(y)} could take a large number of values), but could be considered a set of small doubling in a discretised sense.

One would like to have a sum set (or product set) theory that can handle these cases, particularly in “high-dimensional” settings in which the standard methods of passing back and forth between continuous, discrete, or discretised settings behave poorly from a quantitative point of view due to the exponentially large doubling constant of balls. One way to do this is to impose a translation invariant metric {d} on the underlying group {G = (G,+)} (reverting back to additive notation), and replace the notion of cardinality by that of metric entropy. There are a number of almost equivalent ways to define this concept:

Definition 3 Let be a metric space, let be a subset of, and let be a radius.
Thepacking number ${N^{pack}_r(E)}$ is the largest number of points ${x_1,\dots,x_n}$ one can pack inside such that the balls ${B(x_1,r),\dots,B(x_n,r)}$ are disjoint.
Theinternal covering number ${N^{int}_r(E)}$ is the fewest number of points ${x_1,\dots,x_n \in E}$ such that the balls ${B(x_1,r),\dots,B(x_n,r)}$ cover.
Theexternal covering number ${N^{ext}_r(E)}$ is the fewest number of points ${x_1,\dots,x_n \in X}$ such that the balls ${B(x_1,r),\dots,B(x_n,r)}$ cover.
Themetric entropy ${N^{ent}_r(E)}$ is the largest number of points ${x_1,\dots,x_n}$ one can find in that are-separated, thus ${d(x_i,x_j) \geq r}$ for all ${i \neq j}$ .

It is an easy exercise to verify the inequalities

$\displaystyle N^{ent}_{2r}(E) \leq N^{pack}_r(E) \leq N^{ext}_r(E) \leq N^{int}_r(E) \leq N^{ent}_r(E)$

for any {r>0} , and that ${N^*_r(E)}$ is non-increasing in {r} and non-decreasing in {E} for the three choices {* = pack,ext,ent} (but monotonicity in {E} can fail for {*=int} !). It turns out that the external covering number ${N^{ent}_r(E)}$ is slightly more convenient than the other notions of metric entropy, so we will abbreviate ${N_r(E) = N^{ent}_r(E)}$ . The cardinality {|E|} can be viewed as the limit of the entropies ${N^*_r(E)}$ as ${r \rightarrow 0}$ .

If we have the bounded doubling property that {B(0,2r)} is covered by {O(1)} translates of {B(0,r)} for each {r>0} , and one has a Haar measure {m} on {G} which assigns a positive finite mass to each ball, then any of the above entropies ${N^*_r(E)}$ is comparable to {m( E + B(0,r) ) / m(B(0,r))} , as can be seen by simple volume packing arguments. Thus in the bounded doubling setting one can usually use the measure-theoretic sum set theory to derive entropy-theoretic sumset bounds (see e.g.this paper of mine for an example of this). However, it turns out that even in the absence of bounded doubling, one still has an entropy analogue of most of the elementary sum set theory, except that one has to accept some degradation in the radius parameter {r} by some absolute constant. Such losses can be acceptable in applications in which the underlying sets {A} are largely “transverse” to the balls {B(0,r)} , so that the ${N_r}$ -entropy of {A} is largely independent of {A} ; this is a situation which arises in particular in the case of graphs ${\Gamma = \{ (x,f(x)): x \in G \}}$ discussed above, if one works with “vertical” metrics whose balls extend primarily in the vertical direction. (I hope to present a specific application of this type here in the near future.)

Henceforth we work in an additive group {G} equipped with a translation-invariant metric {d} . (One can also generalise things slightly by allowing the metric to attain the values {0} or ${+\infty}$ , without changing much of the analysis below.) By the Heine-Borel theorem, any precompact set {E} will have finite entropy ${N_r(E)}$ for any {r>0} . We now have analogues of the two basic Ruzsa lemmas above:

Lemma 4 (Ruzsa covering lemma) Let be precompact non-empty subsets of, and let. Then may be covered by at most ${\frac{N_r(A+B)}{N_r(B)}}$ translates of.

Proof: Let ${a_1,\dots,a_n \in A}$ be a maximal set of points such that the sets ${a_i + B + B(0,r)}$ are all disjoint. Then the sets ${a_i+B}$ are disjoint in {A+B} and have entropy ${N_r(a_i+B)=N_r(B)}$ , and furthermore any ball of radius {r} can intersect at most one of the ${a_i+B}$ . We conclude that ${N_r(A+B) \geq n N_r(B)}$ , so ${n \leq \frac{N_r(A+B)}{N_r(B)}}$ . If ${a \in A}$ , then {a+B+B(0,r)} must intersect one of the ${a_i + B + B(0,r)}$ , so ${a \in a_i + B-B + B(0,2r)}$ , and the claim follows. $\Box$

Lemma 5 (Ruzsa triangle inequality) Let be precompact non-empty subsets of, and let. Then ${N_{4r}(A-C) \leq \frac{N_r(A-B) N_r(B-C)}{N_r(B)}}$ .

Proof: Consider the addition map ${+: (x,y) \mapsto x+y}$ from ${(A-B) \times (B-C)}$ to {G} . The domain ${(A-B) \times (B-C)}$ may be covered by ${N_r(A-B) N_r(B-C)}$ product balls ${B(x,r) \times B(y,r)}$ . Every element {a-c} of {A - C} has a preimage ${\{ (x,y) \in (A-B) \times (B-C)\}}$ of this map which projects to a translate of {B} , and thus must meet at least ${N_r(B)}$ of these product balls. However, if two elements of {A-C} are separated by a distance of at least {4r} , then no product ball can intersect both preimages. We thus see that ${N_{4r}^{ent}(A-C) \leq \frac{N_r(A-B) N_r(B-C)}{N_r(A-C)}}$ , and the claim follows. $\Box$

Below the fold we will record some further metric entropy analogues of sum set estimates (basically redoing much of Chapter 2 ofmy book with Van Vu). Unfortunately there does not seem to be a direct way to abstractly deduce metric entropy results from their sum set analogues (basically due to the failure of a certain strong version of Freiman’s theorem, as discussed inthis previous post); nevertheless, the proofs of the discrete arguments are elementary enough that they can be modified with a small amount of effort to handle the entropy case. (In fact, there should be a very general model-theoretic framework in which both the discrete and entropy arguments can be processed in a unified manner; seethis paper of Hrushovski for one such framework.)

It is also likely that many of the arguments here extend to the non-commutative setting, but for simplicity we will not pursue such generalisations here.

— 1. Approximate groups —

In discrete sum set theory, a key concept is that of a-approximate group – a finite symmetric subset {A} of {G} containing the origin such that {A+A} is covered by at most {K} translates of {A} . The analogous concept here will be that of a-approximate group: a precompact symmetric subset {A} of {G} containing the origin such that {A+A} is covered by at most {K} copies of {A+B(0,r)} . Such sets obey good iterated doubling properties; for instance, {mA} is covered by at most ${K^{m-1}}$ copies of {A+B(0,(m-1)r)} for any ${m \geq 1}$ . They can be generated from sets of small tripling:

Lemma 6 Let be a precompact non-empty subset of, and let. If ${N_r(3A) \leq K N_{16r}(A)}$ or ${N_r(2A-A) \leq K N_{16 r}(A)}$ , then is a ${(K^4,32r)}$ -approximate group.

Proof: From Lemma5 we have

$\displaystyle N_{4r}(2A-2A) \leq \frac{N_r(2A \pm A) N_r(\mp A-2A)}{N_r(A)} \leq K^2 N_{16r}(A)$

(for an appropriate choice of sign) and

$\displaystyle N_{16r}(3A-2A) \leq \frac{N_{4r}((A-2A)+A) N_{4r}(-A-(-2A))}{N_{4r}(A)} \leq K^4 N_{16r}(A)$

and thus by Lemma4, {2A-2A} may be covered by at most ${K^4}$ copies of {A-A + B(0,32r)} , giving the claim. $\Box$

— 2. From small doubling to small tripling or quadrupling —

As we saw above, Lemma5 and Lemma4 are already very powerful once one has some sort of control on triple or higher sums such as {3A} , {2A-A} , or {2A-2A} . But if only controls a double sum such as {A-A} or {A+A} , it is a bit trickier to proceed. Here is one estimate (somewhat analogous to Proposition 2.18 frommy book with Van Vu, but with slightly worse numerology):

Lemma 7 Let be a precompact non-empty subset of, and let. If ${N_r(A-A) \leq K N_{4r}(A)}$ , then ${N_{24r}(2A-2A) \leq 32 K^5 N_{4r}(A)}$ .

One can combine this lemma with Lemma5 to obtain similar conclusions starting with a hypothesis on {A+A} rather than {A-A} ; we leave this to the interested reader. Of course, the conclusion can also be combined with Lemma6; we again leave this as an exercise.

Proof: Write ${N := N_{4r}(A)}$ . Then ${N^{ent}_{4r}(A) \geq N}$ , so we may find a {4r} -separated subset ${\Sigma}$ of {A} with ${|\Sigma| = N}$ . By hypothesis, we may cover {A-A} by balls ${B(x_1,r),\dots,B(x_m,r)}$ with ${m \leq K N}$ . Call a centre ${x_i}$ popular if ${B(x_i,r)}$ contains at least {N/2K} differences {a-b} with ${a,b \in \Sigma}$ (counting multiplicity), and let {S} denote the set of popular centres. Then at most ${KN \times (N/2K)}$ of the ${N^2}$ pairs ${(a,b) \in \Sigma^2}$ have {a-b} lying in an unpopular ball ${B(x_i,r)}$ , thus we have ${a-b \in S + B(0,r)}$ for at least ${N^2/2}$ pairs {(a,b)} in ${\Sigma^2}$ . Thus, by the pigeonhole principle, there exists ${b \in \Sigma}$ such that at least {N/2} elements of ${\Sigma-b}$ lie in {S + B(0,r)} . Thus

$\displaystyle N^{ent}_{4r}( S + B(0,r) ) \geq N/2$

and thus

$\displaystyle N_{2r}( S + B(0,r) ) \geq N/2$

and thus

$\displaystyle N_{r}( S ) \geq N/2. \ \ \ \ \ (1)$

Next, for any ${x \in -A + S + A}$ , we consider the set ${U_x}$ of pairs ${(x_i,x_j)}$ such that ${-x_i + x_j \in x + B(0,3r)}$ . We may write

$\displaystyle x = -a + s + b$

for some ${a,b \in A}$ and ${s \in S}$ . By definition of {S} , we can find distinct pairs ${(a_k,b_k) \in \Sigma}$ for ${1 \leq k \leq k_*}$ with ${k_* \geq N/2K}$ such that ${a_k-b_k \in B(s,r)}$ for all {k} . As ${\Sigma}$ is {4r} -separated and {B(s,r)} has diameter at most {2r} , the ${a_k}$ must be distinct in {k} , and similarly for the ${b_k}$ . We then have

$\displaystyle x \in (a_k - a) + (b-b_k) + B(0,r)$

for ${k=1,\dots,k_*}$ . Each ${a - a_k}$ lies in {A-A} and is thus lies in ${B(x_i,r)}$ for some {i} , and similarly ${b-b_k \in B(x_j,r)}$ for some {j} . Then

$\displaystyle -x_i + x_j \in (a_k-a) + (b-b_k) + B(0,2r) \subset x + B(0,3r)$

and so ${(x_i,x_j) \in U_x}$ . Also, since ${a_k - a \in B(x_i,r)}$ and the ${a_k}$ are {4r} -separated, we see that the ${x_i}$ are distinct as {k} varies. We conclude that ${|U_x| \geq k_* \geq N/2K}$ . On the other hand, the total number of pairs ${(x_i,x_j)}$ is ${m^2 \leq (KN)^2}$ , and any two {6r} -separated points {x,y} in {-A+S+A} generate disjoint sets ${U_x, U_y}$ . We conclude that there can be at most ${(KN)^2 / (N/2K) = 4K^3 N}$ {6r} -separated points in, thus

$\displaystyle N^{ent}_{6r}( -A + S + A ) \leq 4 K^3 N$

and thus

$\displaystyle N_{6r}(S + A-A) \leq 4 K^2 N.$

By Lemma5 and(1), we conclude that

$\displaystyle N_{24r}( 2A-2A) \leq \frac{(4K^2 N)^2}{N_{6r}(S)} \leq 32 K^5 N$

and the claim follows. $\Box$

— 3. The Balog-Szemeredi-Gowers lemma —

One of the most difficult, but powerful, components of the elementary sum set theory is the tool now known as theBalog-Szemerédi-Gowers lemma, which converts control on partial sumsets (or equivalently, lower bounds on “additive energy”) to control on total sumsets, after suitable refinements of the sets. Here is one metric entropy version of this lemma.

Lemma 8 (Balog-Szemerédi-Gowers) Let and ${K \geq 1}$ , and let be precompact subsets of. Suppose that
$\displaystyle N_{r}(A), N_{r}(B) \leq N$
and
$\displaystyle N_{22r}( \{ (a,b,a',b') \in A \times B \times A \times B: d(a+b, a'+b') < r \} )$
$\displaystyle \geq N^3/K,$
where we endow ${G \times G \times G \times G}$ with the sup norm metric. Then there exist subsets, of respectively with
$\displaystyle N_r(A'), N_r(B') \gg K^{-O(1)} N$
and
$\displaystyle N_{54r}( A' + B' ) \ll K^{O(1)} N.$

Again, this lemma may be usefully combined with the previous sum set estimates, much as was done in my book with Van Vu; I leave the details to the interested reader.

Proof: Let ${\Sigma_A}$ , ${\Sigma_B}$ be maximal {2r} -separated subsets of {A, B} respectively, thus ${|\Sigma_A| \leq N^{ent}_{2r}(A) \leq N_r(A) \leq N}$ , and similarly ${|\Sigma_B| \leq N}$ .

By hypothesis, we can find at least ${N^3/K}$ quadruples {(a,b,a',b')} which are {22r} -separated in ${A \times B \times A \times B}$ , such that

$\displaystyle d(a+b,a'+b') < r$

for all such quadruples. By construction of ${\Sigma_A, \Sigma_B}$ , each such quadruple can be associated to a nearby quadruple ${(\alpha,\beta,\alpha',\beta') \in \Sigma_A \times \Sigma_B \times \Sigma_A \times \Sigma_B}$ with

$\displaystyle d(\alpha,a), d(\beta,b), d(\alpha',a'), d(\beta',b') < 2r$

and thus by the triangle inequality

$\displaystyle d(\alpha+\beta,\alpha'+\beta') < 9r. \ \ \ \ \ (2)$

Also by the triangle inequality we see that each ${(\alpha,\beta,\alpha',\beta')}$ can be associated to at most one of the quadruples {(a,b,a',b')} , and as the are {22r} -separated, the ${\alpha,\beta,\alpha',\beta')}$ are {18r} -separated. We conclude that there is a set of at least ${N^3/K}$ quadruples ${(\alpha,\beta,\alpha',\beta')}$ in ${\Sigma_A \times \Sigma_B \times \Sigma_A \times \Sigma_B}$ obeying(2) that are {18r} -separated.

Call a pair ${(\alpha,\beta) \in \Sigma_A \times \Sigma_B}$ popular if there are at least {N/4K} of the above quadruples ${(\alpha,\beta,\alpha',\beta')}$ in ${\Sigma_A \times \Sigma_B \times \Sigma_A \times \Sigma_B}$ obeying(2) with the indicated first two coefficients. The unpopular pairs ${(\alpha,\beta)}$ absorb at most ${N^3/2K}$ of the ${N^3/K}$ quadruples, so at least ${N^3/2K}$ of the quadruples are associated to popular pairs ${(\alpha,\beta)}$ . On the other hand, as the quadruples are {18r} -separated, we see from(2) and the triangle inequality that for each ${\alpha,\beta,\alpha'}$ there is at most one ${\beta'}$ giving rise to a quadruple ${(\alpha,\beta,\alpha',\beta')}$ . Thus each ${(\alpha,\beta)}$ can be associated to at most {N} quadruples, and we conclude that the set ${E \subset \Sigma_A \times \Sigma_B}$ of popular pairs ${(\alpha,\beta)}$ has size at least ${N^2/2K}$ . In particular this shows that ${|\Sigma_A|, |\Sigma_B| \gg N/K}$ .

We now apply the graph-theoretic Balog-Szemerédi-Gowers lemma (see Corollary 6.19 ofmy book with Van Vu) to conclude that there exists a subset {A'} of ${\Sigma_A}$ and {B'} of ${\Sigma_B}$ with

$\displaystyle |A'|, |B'| \gg N/K^{O(1)}$

such that for every ${a \in A'}$ and ${b \in B'}$ there exist ${\gg N^2/K^{O(1)}}$ pairs ${(a',b') \in A \times B}$ such that {(a,b'), (a',b'), (a',b)} lie in {E} . Since ${\Sigma_A, \Sigma_B}$ was already {2r} -separated, we conclude that

$\displaystyle N_r(A'), N_r(B') \gg N/K^{O(1)}.$

Now fix ${a \in A'}$ and ${b \in B'}$ , and let {(a',b')} be one of the above ${\gg N^2/K^{O(1)}}$ pairs. As {(a,b')} is popular, we can thus find ${\gg N/K}$ pairs ${(\alpha_1,\beta_1) \in \Sigma_A \times \Sigma_B}$ such that

$\displaystyle \alpha_1 - \beta_1 \in a - b' + B(0,9r); \ \ \ \ \ (3)$

furthermore, the ${(a,b',\alpha_1,\beta_1)}$ lie in an {18r} -separated set. Similarly, we can find ${\gg N/K}$ pairs ${(\alpha_2,\beta_2) \in \Sigma_A \times \Sigma_B}$ and ${\gg N/K}$ pairs ${(\alpha_3,\beta_3) \in \Sigma_A \times \Sigma_B}$ such that

$\displaystyle \alpha_2 - \beta_2 \in a' - b' + B(0,9r) \ \ \ \ \ (4)$

and

$\displaystyle \alpha_3 - \beta_3 \in a' - b + B(0,9r) \ \ \ \ \ (5)$

with the ${(a',b',\alpha_2,\beta_2)}$ and ${(a',b,\alpha_3,\beta_3)}$ also lying in an {18r} -separated set. In particular, we see that given {a, b} , ${\alpha_1,\beta_1}$ uniquely determine {b'} , and ${\alpha_3,\beta_3}$ uniquely determine {a'} , so a single sextuple ${(\alpha_1,\beta_1,\alpha_2,\beta_2,\alpha_3,\beta_3)}$ can arise from at most one pair {(a',b')} ; in particular, we see that ${\gg (N^2/K^{O(1)}) \times (N/K)^3 = N^5 / K^{O(1)}}$ sextuples are associated to each pair {(a,b)} . Taking alternating combinations of(3),(4),(5) we see that

$\displaystyle \alpha_1 - \beta_1 - \alpha_2 + \beta_2 - \alpha_3 + \beta_3 \in a - b + B(0,27r).$

In particular, if {(a,b)} and ${(\tilde a, \tilde b)}$ are two pairs in ${A' \times B'}$ with ${a-b, \tilde a - \tilde b}$ at least {54r} apart, then a single sextuple ${(\alpha_1,\beta_1,\alpha_2,\beta_2,\alpha_3,\beta_3)}$ can be associated to at most one of these pairs. Since the number of sextuples is at most ${N^6}$ , we conclude that there are at most ${K^{O(1)} N}$ pairs {(a,b)} with {54r} -separated differences {a-b} , thus ${N_{54r}(A'-B') \ll K^{O(1)} N}$ as required. $\Box$

The Polymath Blog

20 comments

Comments feed for this article

19 March, 2014 at 6:44 pm

Anonymous

Is there a typo in the definition of difference sets?

[Corrected, thanks – T.]

19 March, 2014 at 10:18 pm

domotorp

In proof of Lemma 1, {|A|} should be {|B|}.

[Corrected, thanks – T.]

19 March, 2014 at 11:50 pm

domotorp

Another typo above Def 3: odubling

[Corrected, thanks – T.]

20 March, 2014 at 12:26 am

domotorp

And at the end of Def 3 there is an extra {itemize}

[Corrected, thanks – T.]

20 March, 2014 at 12:30 am

domotorp

Closing parenthesis missing from para above lemma 4.

[Corrected, thanks – T.]

19 March, 2014 at 11:56 pm

domotorp

The internal covering number, {N^{int}_r(E)}, might decrease in E – consider r=3 and E={0,2,4} and E’={0,4}.

[Corrected, thanks – T.]

20 March, 2014 at 4:55 am

kyle

I think there are some typos in the proof of lemma 1. For example, I think the maximal set that is chosen should be a subset of A, not a subset of B as stated. I also agree with the earlier comment by domotorp that the cardinality of each of these translates is |B|, not |A|.

20 March, 2014 at 4:56 am

kyle

Sorry, didn’t mean to post a reply under this comment.

20 March, 2014 at 4:54 am

chorasimilarity

Kind of being in this frame of “discretized”, but not discrete, nor continuous, inarXiv:1304.3358 there is a very simple note about a “geometric Ruzsa triangle intequality”, which does not even use group operations, maybe is of some interest here.

20 March, 2014 at 1:06 pm

Pascal

Is there a version of the basic results of additive combinatorics for multisets rather than sets, or even better for multisets where negative cardinalities are allowed?

If this looks like a baroque idea, note that there is a quite natural interpretation: if c_a denotes the mulitplicity of element a, we can represent a multiset by the polynomial sum_a c_a X^a. Taking a sum set A+B then amounts to multiplying the 2 corresponding polynomials.

20 March, 2014 at 3:46 pm

Terence Tao

There is a closely analogous theory to discrete sumset theory for random variables, with Shannon entropy taking the place of cardinality: seehttp://www.ams.org/mathscinet-getitem?mr=2647496 . For signed functions, the appropriate tool is Fourier analysis and convolution, for which there are certainly a lot of estimates available (though once one gives up positivity, many of the more combinatorial estimates in the sumset theory no longer have good analogues).

27 March, 2014 at 2:35 am

Geoff Sang

Hi Terence,
I am a year 9 student from Western Australia, and I find your blog very fascinating. The school maths I do are easy however I know that there are many more students better than I am.

I have never done complicated maths before like the Australian Maths Olympiad (unlike you when you were my age), but now I am starting to learn the fundamentals. Proof has always been an obstacle when I do competitions (e.g. The Western Australian Junior Mathematical Olympiad). How could I practice proof and also understand a question better when doing competitions?

Thank you,
Geoff Sang

21 March, 2014 at 5:05 pm

arch1

In the proof of Lemma 1 should “lie in |A + B|” be “lie in A + B”?

[Corrected, thanks – T.]

25 March, 2014 at 5:59 am

arch1

In the orthogonal nxn matrix example: “…let A be the matrices obtained by starting with an orthogonal matrix in On(R) and rounding each coefficient to the nearest multiple of epsilon…. This is a finite set (whose cardinality grows as [epsilon goes to 0] like a certain negative power of epsilon).”

The above recipe seems to me to produce exactly one matrix, regardless of epsilon’s value, so I must be missing something real basic. Can someone help?

[Reworded for clarity – T.]

28 March, 2014 at 8:09 am

MrCactu5 (@MonsieurCactus)

It looks like you are describing some sort of generalized Hamming Code? For noisy channel coding the “buzzwords” should be a certain Hammin distance apart.

At this point I am taking a step back and reading through your book with Van Vu.

29 May, 2014 at 9:15 am

Anonymous

Prof. Tao,

In general, we can not replace B-B by in Ruzsa’s covering lemma without some sort of loss. That is showed in an exercise in the book of you and Prof. Vu. If A, B are finite subsets of integers, is it true that we can cover by at most |A+B|/|B| ( |A-B|/|B| ) translates of? I did some simulations, and no counterexample was found.

Best,
Jiange

29 May, 2014 at 11:57 am

Terence Tao

Unfortunately not; one can take a counterexample A,B in a finite group such as ${\bf Z}/N{\bf Z}$ (e.g. the one in Exercise 2.4.1 of my book with Van), and “transfer” it to the integers by considering a set such as $A' := \{ 1 \leq n \leq M: n \hbox{ mod } N \in A \}$ and $B' := \{ 1 \leq n \leq M: n \hbox{ mod } N \in B \}$ , where is much larger than. This modifies the covering number by a factor of 2 or so, but the failure in ${\bf Z}/N{\bf Z}$ of the naive Ruzsa covering lemma is by an arbitrarily large constant, so it can also create an arbitrarily large failure of that covering lemma in the integers.

2 May, 2018 at 8:25 am

Anonymous

Typo:
In the paragraph following Definition 3,
“…the external covering number $N^{ent}_r (E)$ is slightly more convenient than the other notions of metric entropy, so we will abbreviate $N_r(E) = N^{ent}_r (E)$ ”
should be
“…the external covering number $N^{ext}_r (E)$ is slightly more convenient than the other notions of metric entropy, so we will abbreviate $N_r(E) = N^{ext}_r (E)$ ” (The difference is in the superscript.)
I think.

26 April, 2019 at 11:48 am

aetjmaison

In your definitions of entropies, are the balls open? If they are closed, should the inequality be strict in the definition of r-separation? Thank you.

26 April, 2019 at 4:29 pm

Terence Tao

It doesn’t make too much difference to the arguments, but in my post the balls are open, and I believe all the statements in the post are valid with non-strict inequality in the definition of separation.

For commenters

To enter in LaTeX in comments, use $latex<Your LaTeX code>$ (without the < and > signs, of course; in fact, these signs should be avoided as they can cause formatting errors). Also, backslashes \ need to be doubled as \\. See theabout page for details and for other commenting policy.

« Conserved quantities for the surface quasi-geostrophic equation

The Monge-Cayley-Salmon theorem via classical differential geometry»

Blog at WordPress.com.Ben Eastaugh and Chris Sternal-Johnson.

Subscribe to feed.

	Sam on245B, notes 0: A quick review…
	Terence Tao onCall for industry sponsors for…
	Terence Tao onSum-difference exponents for b…
	Terence Tao onCall for industry sponsors for…
	Anonymous onCall for industry sponsors for…
	Mark Lewko onSum-difference exponents for b…
	Anonymous onCall for industry sponsors for…
	Terence Tao onSum-difference exponents for b…
	Terence Tao onSum-difference exponents for b…
	Terence Tao on245A: Problem solving str…
	Terence Tao onCall for industry sponsors for…
	Anonymous on245A: Problem solving str…
	Anastasiia Kovtun onThe Poisson-Dirichlet process,…
	Anonymous onClimbing the cosmic distance l…
	Saksham onCall for industry sponsors for…

Movatterモバイル変換

Metric entropy analogues of sum set theory

Share this:

Recent Comments

Top Posts

Archives

Categories

The Polymath Blog

20 comments

Leave a commentCancel reply

For commenters