Additive combinatorics

Last updated: Mar 16, 2012

Additive Combinatorics

Terence Tao, Van Vu

Cambridge University Press

Hardback, 530 pages (ISBN-13: 9780521853866; ISBN-10: 0521853869)

Paperback, 512 pages (ISBN-13: 9780521136563)

This book covers the basic tools in additive combinatorics: sum set estimates, inverse theorems, graph theory techniques, crossing numbers, algebraic methods, Szemerédi’s theorem. A revised edition is forthcoming.

Sample chapters (contents, probabilistic method, sum set estimates, additive geometry)

— Deleted scenes —

— Precursor material —

— Errata —

p. xi: Reference [116] should be [113].
p. xiv: “Chevalley-Waring” should be “Chevalley-Warning”.
p. 1, last display: $E(|X|^2)-E(|X|)^2$ should be $E(X^2)-E(X)^2$ .
p. 3, after Lemma 1.2: “with probability n” should be “with probability 1″.
p. 4, after Question 1.4, “Kleiman” should be “Kleitman”.
p. 5: In Q. 1.1.3, $(-1)^k$ should be $(-1)^{|A|+1}$ (two occurrences). In Q. 1.1.5, $A \cap (B+x)$ and $A \cap (B+y)$ should be $A \cup (B+x)$ and $A \cup (B+y)$ respectively.
p. 6: Exercise 1.1.8 is missing. This exercise reads: “Let $A$ be an additive set. Show that there exists a subset $X \subset 2A-A$ of cardinality $|X|= O( \frac{|2A-A|}{|A|} (1 + \log |A| ) )$ such that $2A \subset A+X$ . (Hint: translate $A$ randomly by independent elements of $2A-A$ , and use the first moment method.)”
p. 8: In the fourth display, $\ln$ should be $\log$ . $|B|-10 \leq \nu(x) \leq |B|$ should be $|B| \leq \nu(x) \leq |B|+10$ .
p. 9: In Exercise 1.2.4, the inequality should be reversed.
p. 11: In the paragraph after (1.17), $\ln$ should be $\log$ .
p. 14: In the 9th line from below, $\ln$ should be $\log$ (two places); similarly before (1.23) on P. 15. In the final display, $\kappa/2$ should be $\kappa/16$ .
p. 15: In the first display, the first $\leq$ sign should be $\geq$ .
p. 17: In the first line, Corollary 1.8 should be Corollary 1.9. In Exercise 1.3.1, n needs to be even and $\lambda$ needs to be odd. In Exercise 1.3.4, the first expectation should be a probability. In Exercises 1.3.5 and 1.3.6, $\lambda$ needs to be positive.
p.18: In Exercise 1.3.8, the expectation should be $2^{n-1} - 1/2$ and the variance should be $2^{n-2} - 1/4$ . In Exercise 1.3.11, $E( |X|^p )^{1/p}$ should be $E( | X-E(X) |^p )^{1/p}$ .
p. 21: In Definition 1.21,”we say that $X$ is a $(1-\epsilon)$ -complementary base of $A$ ” should be”we say that $X$ is a $(1-\epsilon)$ -complementary base of order $k$ of $A$ “.
p. 22, before second display: Lemma 1.53 should be Theorem 1.53.
p. 23: Near top: “the event that $x_j$ is good” should be “the event that $j$ is good”. In the last line of the proof of Lemma 1.24, $\ln$ should be $\log$ .
p. 24: In the last display, the third $\overline{A_i}$ should be $\overline{A_j}$ .
p. 25: In the first display, $\geq$ should be $\leq$ .
p. 36: In the first line of the proof of Theorem 1.39, add “Without loss of generality we may assume $\epsilon <1/h$ . In the third display on the last line, $O_h(n^{-he})$ should be $O_h(m^{-he})$ .
p. 37: In the first display, $F_h(g,N)$ should be |A|.
p. 38: In the RHS of the display in Corollary 1.42 RHS of the formula, $D_{k,n}$ should be $(D_{k,n}-1)^k$ .
p. 40: In the RHS of the last display $D_n$ should be $(D_n-1)^k$ .
p. 41: In the first display, $D_n + 1$ should be $(D_n + 1)^k$ .
p. 44: One line before the third display, $m=[n^{1/k}]$ should be $m=[n^{1/r}]$ .
p. 47: In the penultimate equation in the proof of Proposition 1.51, the summation $\sum_{p\leq t}$ should be $\sum_{p \leq \min(n,t)}$ , and one should observe that the integrand vanishes for $t <2$ . In the last equation, $\int_1^\infty (\log t + O(1)) \ldots$ should be $\int_2^\infty (\log \min(n,t) + O(1)) \ldots$ . The last sentence of the proof should then say “Direct computation then shows that $\int_2^\infty \log \min(n,t) \frac{dt}{t \log^2 t} = \log \log n + O(1)$ and $\int_2^\infty \frac{dt}{t \log^2 t} = O(1)$ , and the claim follows”.
p. 57: In the bounds for $\delta[A]$ , $\frac{|A|-1}{2} + \frac{1}{|A|}$ should be $|A|-1 + \frac{1}{|A|}$ (two occurrences). Similarly, $\frac{N-1}{2}$ should be $N-1$ (two occurrences).
p. 58: In Exercise 2.2.5, $\sqrt{\sigma(A) |A|/2}$ should be $\sqrt{\sigma(A) |A|}$ .
p. 68: In Exercise 2.3.14, $A-A$ should be $A+A$ , and $x+A$ should be $x-A$ . Replace “though the set $F$ may be symmetric around a non-zero origin $x/2$ ” with “where by symmetry here we mean that $F=x-F$ ”. (The point is that $x/2$ might not actually exist and be unique for some groups.)
p. 69: In Exercise 2.3.20, a square root is missing from the left-hand side.
p. 76: In Exercise 2.4.4, Corollary 2.19 should be Corollary 2.20.
p. 77: In Exercise 2.4.7, $\frac{1}{(KK')^3}$ should be $(KK')^3$ .
p. 78: In, Exercise 2.4.11, Proposition 2.4.11 should be Proposition 2.27.
p. 79: In (2.20), $K^4$ should be $K^5$ .
p. 80: In the first paragraph, $K^4$ should be $K^5$ . In the second display of the proof of Lemma 2.30, the \frac{}{} should be a / (and in particular should not enclose the left-hand side of the inequality). Near top: “the iterated sum and difference sets of $A''$ and $B''$ ” should be the iterated sum and difference sets of $A'$ and $B'$ “.
p. 82: In Exercise 2.5.3, add $|B''| \geq 2|B|/K$ after $|A''| \geq 2|A|/K$ . In Exercise 2.5.4, “is can be used” should be “can be used”.
p. 85: In, Lemma 2.23, “there exists a set $G \subset |S|^2$ ” should be “there exists a set $G \subset S^2$ “.
p. 86: In the first display of the proof of Lemma 2.34, $\tilde G$ should be G.
p. 87: In the fourth display, the $G'$ on the LHS and RHS should be $G_m$ . In the last sentence in the statement of Theorem 2.35, $L^{\epsilon}$ should be $L^{-\epsilon}$ .
p. 95: Lemma 2.41, while correct, does not imply Corollary 2.42 as stated (since $d(A,A)$ does not control $|A^{-1} \cdot A|$ ). Thanks to Mei-Chu Chang for pointing out the problem. Replace “As $d(A,A) \leq 2d(A,B)$ , this implies” by “A similar argument (see [Proposition 4.5, 362]) gives”. Rename Corollary 2.42 as Proposition 2.42, replace “ $B$ ” by “ $A$ ” in the first sentence, replace “ $|S| \geq \Omega(K^{-O(1)} |A|)$ ” by “ $|S| \geq |A|/2K$ ” in the second sentence, and replace “ $O(K)^{O(1+n)}$ ” by “ $2^n K^{2n+1}$ ” in the display.
p. 96: “verstion” should be “version”.
p. 97: In Theorem 2.48 (ii), $G \subset A \cdot B$ should be $G \subset A \times B$ .
p. 107: before Corollary 2.62, “Corollary 2.60″ should be “Theorem 2.60″.
p. 112, bottom: “in Section 4.4″ should be “to Section 4.4″.
p. 114, line 3: the last $Z$ should be an $X$ .
p. 115, fourth line of Lemma 3.4: ${\Bbb R}^d$ should be ${\Bbb R}^k$ .
p. 116, proof of Corollary 3.6: “induce” should be “induct”. In the last two sentences of this proof, $w$ should be $v$ (three occurrences).
p. 117, proof of Theorem 3.7: “induce” should be “induct”.
p. 118: Exercise 3.1.1 $\phi (Z')$ should be $\phi (Z)$
p. 120: In the second display, $(m,m,\ldots, m)$ should be $(m-1, m-1, \ldots, m-1)$ .
p. 121, after the proof of Lemma 3.11, “an progression” should be “a progression”.
p. 122, after first display: “for all real $a,b \geq 0$ ” should be “for all non-negative reals $a,b \geq 0$ “. In the next sentence, “for any integer $A$ ” should be “for any positive integer $n$ “, and “ $|n| \cdot A$ ” should be “ $n \cdot A$ “.
p. 123, proof of Theorem 3.13: $|\det(L)|$ should be $|\det(L)| \hbox{mes}(B_d)$ . On the same line, “whch” should be “which”.
p. 124: $\hbox{arctan}(r^2-1)$ should be $\hbox{arctan}(\sqrt{r^2-1})$ (two occurrences). In the first display and two lines further down, $\sqrt{d}$ should be $d$ . In the second-to-last display, $L_{\varepsilon,\delta} \ldots \varepsilon e_1$ should be $\{ L_{\varepsilon,\delta} \ldots \varepsilon e_1: (x_1,\ldots,x_d) \in B_d \}$ . In the last paragraph, $n \cdot B_d$ should be $d \cdot B_d$ .
p. 128: In the proof of Proposition 3.19, $\sup_x f(x) = \sup_y f(y) = 1$ should be $\int_{\Bbb R} f = \int_{\Bbb R} g = 1$ .
p. 129: In the proof of Proposition 3.20, “induce” should be “induct”. Remove the “that” before “(using Fatou’s lemma)”. In the next display, $f_d(y_d)$ should be $f_d(x_d)$ .
p. 130: In Exercise 3.4.5, “amd” should be “and”. In Exercise 3.4.6, all occurrences of $n$ should be $d$ .
p. 131: Delete the sentence beginning with “The lower bound is trivial…” from the proof of Lemma 3.21.
p. 133: On the second display, $(x-V) \cap (\Gamma+P-P)$ should be $(x-V) \cap (\Gamma+P)$ . Just before the third display, $R^d + O_{V,P,d}(R^{d-1})$ should be $(R^d + O_{V,P,d}(R^{d-1})) \hbox{mes}(B)$ . In Corollary 3.25, $N \theta_1 \dots \theta_d \leq 1$ should be $N \theta_1 \dots \theta_d \geq 1$ . In the next display, delete $+ {\Bbb Z}^d$ .
p. 134: In Lemma 3.27, Blichtfeld should be Blichfeldt.
p. 139: In the last display, |B| should be $|B \cap \Gamma|$ .
p. 140: In the proof of Theorem 3.34, $\Gamma \cap V_{i-1} +W$ should be $\Gamma \cap V_i$ .
p. 141-142: Throughout the statement and proof of Lemma 3.36, $r^{2r}$ should be replaced with $O(r)^{3r/2}$ , and $d^{2d}$ replaced with $O(d)^{3d/2}$ . In the last two equations in the display, replace $\hbox{mes}({\Bbb R}^d/\Gamma)$ and $2d \cdot d!$ both by $O(d)^{3d/2}$ .
p. 144: In the last pragraph of the proof of Theorem 3.38, the superfluous ) should be deleted.
p. 145: In Theorem 3.40, replace “If $d \geq 2$ and $P$ is not proper” with “If $d \geq 2$ , $P$ is not proper, and $Z$ is torsion-free”. In the proof, “We induce on $d$ ” should be “We induct on $d$ ”. On the last line, “unless $Z$ is torsion-free” should be deleted.
p. 147: In the second paragraph, “ $M_1, \ldots, M_{d-1}$ ” should be “ $M := (M_1,\ldots , M_{d-1})$ “.
p. 155: In Q 4.1.7, ${\Bbb E}_{\xi \in H^\perp}$ should be $\sum_{\xi \in H^\perp}$ . In Q 4.1.10, the range of $\tilde \bullet$ should be ${\Bbb R}/{\Bbb Z}$ rather than C.
p. 157: In (4.14), $E(1_A,1_B)$ should be $E_Z (1_A*1_B)^2$ .
p. 158: In the proof of Lemma 4.10, $\xi/a$ should be $\xi a$ . Between the second-to-last and third-to-last lines of the long display in that proof, insert the lines “ $= {\Bbb P}_F(A)^3 - |F|^{-1/2} \|f\|_{L^2(F)}^2$ ” and “ $\geq {\Bbb P}_F(A)^3 - |F|^{-1/2} [ {\Bbb E}_{a \in A} \| 1_{a \cdot A} \|_{L^2(F)} ]^2$ ”.
p. 159: In Exercise 4.2.2, “let $p'$ the dual exponent” should be “let $p'$ be the dual exponent”.
p. 162: In the proof of Lemma 4.14, $F \backslash 0$ should be $F \backslash \{0\}$ . In the third line of Corollary 4.15, $a_1, \ldots, a_k$ should belong to $A$ rather than $F$ , and $2^{1-k}$ should be $2^{-k}(1 + |F|^{-1})$ . (Remark: the order estimate only gives the qualitative result $kA=F$ for $|F|$ sufficiently large, but the small values of $|F|$ can be done by hand.) In the last word of the last sentence, $F$ should be $A$ .
p. 164, in Q. 4.3.10, “ $A\cdot 2A = A$ ” should be “ $A \cdot 2A=2A$ “.
p. 165, bottom paragraph: “combinatorialinformation” should be “combinatorial information”.
p. 170, proof of Lemma 4.25: $\log_2 5$ should be 2, and the condition $|a| \leq 0.1$ should be $|a-a'| \leq 0.1$ .
p. 171, in Q 4.4.6, $\sqrt{2}$ should be $1/4$ .
p. 173: In the proof of Proposition 4.29, (4.31) should be (4.30). In the second and last displays, $e(x,\xi)$ should be $e(\xi \cdot x)$ .
p. 174: In the third display, $\|c_\xi\|_H^4$ should be $|c_\xi|^4$ .
p. 175: In the four summations involving $r_{h_1,h_2}$ , $\xi$ should range over Z rather than S. After the second display, $e(x,\xi)$ and $e(x,-\xi)$ should be $e(\xi \cdot x)$ and $e(-\xi \cdot x)$ respectively, and similarly on the third display.
p. 176: In the last display, $e(x,\xi)$ should be $e(\xi \cdot x)$ .
p. 177: In the first display, $e(x,\xi)$ should be $e(\xi \cdot x)$ . In the third display, $e^{\sigma^2/\lambda}$ should be $e^{\sigma^2/2}$ . In the penultimate display, $(1-\varepsilon^2)$ should be $(1-\varepsilon)^2$ . “If take” should be “Taking”. In the last display, $\leq$ should be =.
p. 179: In Exercise 4.5.4, $e(x,\xi)$ should be $e(\xi \cdot x)$ .
p. 181: In the proof of Lemma 4.35, “incrementing k+1″ should be “incrementing k”.
p. 182, middle: “ $S' \in S_\theta$ ” should be “ $S' \subset S_\theta$ “. After the fourth display, $e(x,\xi)$ should be $e(\xi \cdot x)$ . In the last display, the upper limit of the integral should be infinite.
p. 183: In the last four displayed equations, all $\geq$ signs should be $\leq$ . In (4.38), $(A)$ is missing from the RHS. In the sixth display, $e(x,\xi+\xi')$ should be $e( (\xi+\xi') \cdot x))$ .
p. 184: In the fourth and fifth displays, ${\bf P}_Z(A)$ should appear on the right-hand side. (Also, to avoid ambiguity, one may wish to rewrite $\alpha^2/2|S|^2$ in the fifth display as $\frac{1}{2} \alpha^2 |S|^2$ .)
p. 185: In the proof of Proposition 4.39, $e(x,\xi)$ should be $e(x\cdot \xi)$ .
p. 186: In Proposition 4.40, $\sqrt{8 \varepsilon K}$ can be improved to $\sqrt{\varepsilon K/2}$ (though the existing bound is certainly correct). In the line before the last display, $|A| e(\xi \cdot(x-y))$ should be $|A|( e(\xi \cdot (x-y)) - 1 )$ .
p. 187: In Theorem 4.41, ${\Bbb Z}_p \backslash 0$ should be ${\Bbb Z}_p \backslash \{0\}$ .
p. 190: In the first display, 1/2 should be 1/6.
p. 191: The second equality in the third line should be an inequality $\leq$ .
p. 193: In the third line of the first display, $\sum_{h \in H} \|T^h f\|_{L^p(Z)}^{1/p}$ should be $(\sum_{h \in H} \|T^h f\|_{L^p(Z)}^p){1/p}$ . In the second and final displays (and in the first display of p194 and the second, third, and fourth displays in p195), $j \in J$ should be $j \leq J$ (seven occurrences).
p. 194: In the first display, $e(x+jr,\xi)$ should be $e(\xi \cdot (x+jr))$ . After the second display, ${\Bbb E}_Z f$ should equal latex \delta^2$ rather than $\delta$ .
p. 195, first line: $S_{err}$ should be $\Gamma_{err}$ . In the first display, $10 \log \frac{1}{\delta}$ should be M.
p. 196: After the proof of Theorem 4.47, “, non-empty set E” should be “. One then considers a non-empty set E”. A few lines afterwards, “replace” should be “replaces”. In Exercise 4.7.1, $A_1+A_1$ should be $A_1+A_2$ .
p. 200: “induce” should be “induct” (four occurrences). In the fourth line of the proof, $|A_{(e)}|+|B_{(e)}|$ should be $|A_{(e)}+B_{(e)}|$ .
p. 203: the subscript ${0}$ should be $(0)$ (three occurrences).
p. 208: In the sixth line of the last display, $2k$ should be replaced by $(|H|-2)$ (here we use the bound $|\phi_h(A)| \geq 2$ ), and similarly for the seventh through ninth lines (and the tenth line should be deleted).
p. 209: In Exercise 5.1.2, Lemma 5.1 should be Lemma 5.2. In Exercise 5.1.6, “Schirelmann” should be “Schnirelmann”.
p. 210: In Exercise 5.1.9, $A_1+\ldots + A_N$ should equal ${\Bbb Z}_p$ rather than p.
p. 211: In the proof of Lemma 5.13, “induce” should be “induct” (two occurrences). “Frieman” should be “Freiman”.
p. 212: In the proof of Lemma 5.14, $(A \cup B) \backslash 0$ should be $(A \cup B) \backslash \{0\}$ .
p. 213: In the proof of Proposition 5.15, $A \backslash a_0$ should be $A \backslash \{a_0\}$ , $B \backslash b_0$ should be $B \backslash \{b_0\}$ , and $0 \cup A'$ should be $\{0\} \cup A'$ .
p. 214: In the proof of Corollary 5.16, “induce” should be “induct”.
p. 215, middle, “closed unit interval” should be “closed unit ball”. In the proof of Lemma 5.18, “induce” should be “induct”.
p. 216, middle: “some origin $a=x/2$ ” should be “we see that $A \cap H_+$ contains a set $F$ symmetric around some origin $a=x/2$ “.
p. 217: In the first paragraph, P’ should be symmetric around a rather than around a’. In the proof of Theorem 5.20, “induce” should be “induct”.
p. 218, fourth line: $\varepsilon/K|A|$ should be $\frac{\varepsilon}{K} |A|$ . Similarly on the sixth line. Also, on that line, $|A''| \leq \varepsilon/K|A|$ should be $|A''| \geq \frac{\varepsilon}{K}|A|$ .
p. 219: Before the third display, (5.14) should be (5.13).
p. 221: In the first example, $\phi(Z)$ should be $\phi(A)$ . In the fourth line of the fifth example, $(P, {\bf Z})$ should be $(P,Z)$ .
p. 225: In the first line, $j(\lambda)<8$ should be $j(\lambda)<n$ . A period is missing before “Fortunately” in the sentence after the first display.
p. 226: In Exercise 5.3.7, the range of $\phi$ should be $A' \uplus B'$ rather than $A' \uplus B$ .
p. 229: In the proof of Theorem 5.30, Corollary 2.23 should be Lemma 5.26. In the last line of this proof, P should be Frieman isomorphic to Q, rather than to P. In Lemma 5.31, $2K(1+\log_2(KK'))$ should be $4K(1+\log_2(KK'))$ .
p. 230: In the first display, $K' K^{n+1}$ should be $K' K^{n+1} |B|$ . In the second display, $A_{N_1}$ should be $A_{N-1}$ .
p. 231: In the fifth line, $w'_d$ should be $w_{d'}$ . In Theorem 5.33, the hypothesis $|A| \geq 100 K^2$ should be included, and the first paragraph of the proof of Theorem 5.33 should be deleted. Throughout this proof, $\exp(O(K^{O(1)})))$ should be $\exp(O(K^{O(1)}))$ .
p. 236: In Proposition 5.41, “Frieman” should be “Freiman”. In Corollary 5.42, K should be d.
p. 237: In Exercise 5.5.1, Hom should be $\hbox{Hom}_k$ .
p. 240: In Theorem 5.44, “Then there a” should be “Then there is a”
p. 241: The end of proof box on the fourth line should be moved to the end of the first paragraph in page 244.
p. 243: In the last line, $B$ should be $B \cap {\Bbb Z}^d$ .
p. 247: In Exercise 6.1.2, “symmetruc” should be “symmetric”, and one should assume $0 \not \in A$ .
p. 248: In Exercise 6.1.4, the denominator $|V_1| |V_2|$ should be $|V_1|^2 |V_2|^2$ .
p. 249: In the second line from the bottom, Ruzsa[297] should be Ruzsa[303].
p. 250: In the first display, $r^2$ should be r (and in the previous line, $D_r$ should have radius $\sqrt{r}$ rather than r).
p. 253: In Remark 6.8, “We say that S” should be “We say that S is”.
p. 255: In the proof of Theorem 6.9, “induce” should be “induct”, “vacuoust” should be “vacuous”, and “(with $R(1,m)=1$ )” should be deleted. “ $G_{red} = G_{red}$ ” should be “ $G_{red} = G'_{red}$ “. Shortly afterwards, “latter” should be “former”.
p. 256: In the proof of Corollary 6.12, “induce” should be “induct”, and “ $G$ contains a” should be “ $G$ contains an” (two occurrences). “complete the induction and than the proof” should be “closes the induction and completes the proof”.
p. 257: In the first line, “ $E_r$ monochromatic” should be “ $E_r$ -monochromatic”. In Theorem 6.15, $d(|A|,m)$ should be $d(n,m)$ . In Proposition 6.16, ${\Bbb Z}^d$ should be ${\Bbb Z}^{\tilde d}$ , “exists distinct classes” should be “exist distinct classes”, and “ $v_1,\ldots,v_s$ ” should be “non-zero $v_1,\ldots,v_s$ “. In the proof of Proposition 6.16, “induce” should be “induct”, and “inducing” should be “inducting”.
p. 258: In the last paragraph of the proof of Proposition 6.16, $v \in [0,1]^{d_2}$ should be $v_* \in [0,1]^{d_2}$ .
p. 259, first paragraph: “the bound…which follow…are” should be “the bound…which follows…is”. “being of growing” should be “growing”.
p. 260, in Exercise 6.3.3, $\{x+y,xy\}$ should be $\{x,y,x+y,xy\}$ .
p. 263: In the statement of Corollary 6.20, the $K^4$ in the denominator in the last line should be $K^5$ . In the second paragraph of the proof. the denominator $8K^2$ should be $128 K^2$ .
p. 264: In the second paragraph, the denominator $8K^2$ should be $128 K^2$ . In the penultimate display, $A \stackrel{G}{+} B$ should be $(A \stackrel{G}{+} B)^3$ . In the proof of Corollary 6.20, $16 \sqrt{2} K$ should be $16 \sqrt{2} K^2$ (two occurrences), and $K^4$ should be $K^5$ (one occurrence). In the proof of Theorem 2.29, $K^4$ should be $K^5$ (four occurrences).
p. 265: In Theorem 6.21, the first “then” should be an “and”. In the third display, $(a',b') \in A \times B$ should be $(a,b) \in A \times B$ .
p. 268: In the first line, “smallest” should be “largest”. In the line before Example 6.26, the right parenthesis should be deleted. In the fifth paragraph, $\|H \circ G\| \leq \|G\| \|H \|$ should be $\|H \circ G\| \geq \|G\| \|H\|$ .
p. 271: In the last paragraph of 6.5.2, $G_1 \circ \ldots \circ G_k$ should be $G_k \circ \ldots \circ G_1$ (two occurrences).
p. 272, first display: $\frac{|X|}{|C_k|}$ should be $\frac{|C_k|}{|X|}$ .
p. 276: In the first bullet point, “can occur” should be “is”. In the second sentence after these bullet points, “has” should be “have”.
p. 278: In the proof of Corollary 7.4, $v_i > 1$ should be $v_i \geq 1$ . In the proof of Lemma 7.6, “induce” should be “induct”.
p. 279: In the third paragraph, Theorem 6.31 should be Theorem 6.32.
p. 280: In Exercise 7.1.4, Proposition 7.9 should be Lemma 7.9.
p. 286: In the first display, there should be no m on the LHS.
p. 289: In the third line, ${\Bbb P}(X^{(\mu/d)}_{w_1^k w_2^k \ldots w_d^k})$ should be ${\Bbb P}(X^{(\mu/d)}_{w_1^k w_2^k \ldots w_d^k} = 0)$ .
p. 290: In the display before (7.4), $e^{-\pi |X|^2/2}$ should be $e^{-\pi|X|^2/C}$ .
p. 292: In Exercise 7.3.2, ${\Bbb P}$ should be ${\Bbb E}$ .
p. 294: In statement of Proposition 7.21, add “Furthermore, each of the $w_i$ lies in the set $\{v_1,\ldots, v_n\}$ “.
p. 295: After the third display, the $\eta$ s should be $\epsilon$ s.
p. 298: In the last paragraph, ${\Bbb P}(E_k)$ should be ${\Bbb P}(E_k \backslash E_{k-1})$ .
p. 300: In the fourth line of the proof of Corollary 7.28, $X_{i-1}$ should be $X_i$ (two occurrences).
p. 308: In the third paragraph, Andrew’s should be Andrews’.
p. 309: In the second paragraph, the accent on Szemerédi is misplaced. The proof of Theorem 8.1 (as well as the explicit choice of constants) is due to Chazelle, Sharir, and Welzl (see M. Aigner and G. Ziegler, Proofs from the Book, Springer-Verlag,
Heidelberg, (2004), viii+239 pp.)
p. 310: In the second display, $p^{-2}$ should be $p^{-3}$ .
p. 312: In the dual formulation of Corollary 8.5, there is a “:” missing in the set notation.
p. 314: In Ex 8.2.6, “exactly two points” should be “at least two points”. (It is however an interesting question as to whether the exercise is correct as stated.) In Exercise 8.2.10, a-a should be a-a’.
p. 316: In Theorem 8.15, $\Theta$ should be $\Omega$ (two occurrences).
p. 318: On the sixth line, a right parenthesis is missing in $\Omega ( \frac{|A|^6}{|A \cdot A|} )$ .
p. 322: In (8.6) $|P|^{3-\frac{1}{d}}r^{-d}$ should be $O_d(|P|^{3-\frac{1}{d}}r^{-d})$ .
p. 324: In Exercise 8.4.3, $|L \cap P|$ should be $|l \cap P|$ .
p. 325: Exercise 8.4.7 is heuristically correct, but the rigorous implementation of this exercise is somewhat subtle; see this post for details.
p. 330: In the proof of Theorem 9.2, “induce” should be “induct”.
p. 331: After the end of the proof, “Combinatorial Nullstelensatz” should be “combinatorial Nullstellensatz”.
p. 332: In Exercise 9.1.2, the $d_j$ in $\cup_{j=1}^{d_j}$ should be $d_i$ . In Exercise 9.1.3, the Hilbert nullstellensatz of course only applies when F is algebraically closed. In Exercise 9.1.4, $P(x_1,\ldots,x_n)=0$ should be $P(x_1,\ldots,x_n) \neq 0$ .
p. 333: In Lemma 9.3, $F_p$ should be $F$ .
p. 338: In the proof of Theorem 9.11, “induce” should be “induct”.
p. 341: In Question 9.2.6, $V$ should be $\Delta_n$ .
p. 342: In Theorem 9.17, $|R_i|$ should be $|R_i|+1$ , and $r_i$ should be $|R_i|$ . In the last sentence of the proof of Theorem 9.16, “ $s \in S_i$ ” should be “ $s \in B$ “.
p. 343: In the first display, the right-hand side should just be $\prod_{i, j \in [1,k]: i \neq j} \prod_{r \in R_i} (a_i+t_i-a_j-t_j-r)$ . In the next paragraph, $x_i$ should be $t_i$ , and in the paragraph after that, $r_i$ should be $|R_i|$ . In the first line of the last display, $(a_{\tau(i)}t_{\tau(i)}^{i-1}$ should be $(a_{\tau(i)}t_{\tau(i)})^{i-1}$ . In Lemma 9.18, the second sentence should start “Then” rather than “The”. In the 5th line (the line before 2nd display) $\prod_{1 \leq i \neq j \leq k} \prod_{r \in R_i}$ should be $\prod_{1 \leq i \leq k}$ .
p. 344: In proof of Corollary 9.19, “the multiplicatively invertible” should be “the set of multiplicatively invertible”. After the end of the proof of Lemma 9.18, “additive group” should be “an additive group”. In Theorem 9.20, “be power of $p$ ” should be “be a power of $p$ “.
p. 345: In Exercise 9.3.3, “Let $P_{\pi}$ ” should be “Set $P_{\pi}$ “, and $P(\pi)$ should be $P_\pi$ .
p. 348: In the proof of Theorem 9.24, $\hbox{deg}(F)$ should be $\hbox{deg}(P_i)$ .
p. 350: In Lemma 9.27, $s(|Z|)$ should be $s(Z)$ .
p. 352-353: In the proof of Lemma 9.31: all occurrences of $g_1$ should be $a_1$ , etc. Also, $g_{m+1},\ldots,g_m$ should be $a_{m+1},\ldots,a_n$ . In Theorem 9.32, [266] should be [267]. In Exercise 9.5.3, $2n-1$ should be $2n^2 -1$ .
p. 354: Right before Theorem 9.36, “made a significant progress” should be “made significant progress”. In the third line of Exercise 9.5.4, $h$ should be $k$ . In the RHS of (9.14), $s(n,d)$ should be $s(m,d)$ . Right after Theorem 9.36, $\frac{41}{11}$ should be $\frac{41}{10}$ .
p. 355: In Remark 9.38, “combining” should be “combined”. In the first display, $(1 - \sigma a_it_i)^{p-1} ((1 - \sigma b_i t_i)^{p-1} -1)$ should be $(1- (\sigma a_i t_i)^{p-1} )(1- (\sigma b_i t_i)^{p-1} )$ . In the last sentence of the proof of Theorem 9.36, $x_1 \cdots x_m$ should be $t_1 \cdots t_m$ .
p. 356: In Exercise 9.6.3, $\frac{41}{11}n$ should be $\frac{41}{10}n$ , and “induce” should be “induct”.
p. 358: In the 3rd display $s^{|G|} - 4$ should be $s^{|G|} - r$ .
p. 362, bottom line: “as follows” should be “are as follows”.
p. 363, middle: delete “and using Exercise 9.4.1″. Somewhat further down, $f, g \in {\Bbb Z}[z]$ should just be ${\Bbb Z}[z]$ .
p. 364, in the proof of Lemma 9.48, “least common multiple” should be “greatest common divisor”.
p. 365: In Theorem 9.5.2, add the condition “ $f$ is nonzero”.
p. 366: In the last line of the proof of Theorem 9.53, max should be min. In the first paragraph of the proof of Corollary 9.54, “keeping $\underline{x}$ fixed” should be “keeping $\underline{\xi}$ fixed”.
p. 367: In Exercise 9.8.3 $\phi_p(t-1)$ should be $\phi_p(t+1)$ (two occurrences).
p. 368: In Exercise 9.8.8, delete “, and let $n_1,\ldots,n_k$ be distinct integers in $[0,p)$ “. In the second display of Exercise 9.8.11, the sup should be an inf.
p. 370: In Examples 10.3, $k > n$ should be $k > p$ . In Theorem 10.5, the phrase “… with $|Z|$ coprime to $(k-1)!$ ” should be added at the end of the first sentence.
p. 371: In Exercise 10.0.4, Exercise 6.3.7 should be Theorem 6.17. In the third line of Exercise 10.0.5, “color class” should be “color classes”.
p. 375: In the second and third displays, $\Lambda$ should be $\Lambda_3$ . In the line afterwards, (4.3) should be (4.2).
p. 376: In the second line before the exercises, one of the “that”s should be removed.
p. 377: In Exercise 10.1.6, “aproper” should be “a proper”.
p. 378: Corollary 10.10 should be Proposition 10.10, and similarly in page 380.
p. 379: In the third display of the proof of Lemma 10.15, $e( \xi \cdot x + \theta )$ should be $e( \xi \cdot (x+x_0) + \theta )$ . In the third line of the proof of Theorem 10.12 (which should be Proposition 10.12), $3/n$ should be $3|Z|/n$ . In the second line of the proof of Theorem 10.12, “induce” should be “induct”.
p. 380: In the proof of Proposition 10.17, “induce” should be “induct”. In the line after the top display, it should say “ $n > 3$ ” rather than “ $n \geq 3$ “.
p. 381: In the second line, $4$ should be $8$ . (In the next two displays, the 4 is correct.) In the third line, add “and $x_0$ in $Z$ ” just before “, such that”. In the third and fourth displays, ${\Bbb E}_Z(g)$ should be ${\Bbb E}_{Z'}(g)$ .
p. 382: in the paragraph after statement of Theorem 10.20: replace” $\delta$ and $M$ ” with just “ $M$ “.
p. 383: in the third display, the first = sign should be $\leq$ , while $\sup_{\xi \in V^\perp \ 0} |\hat \nu(\xi)|$ should be $\sup_{\xi \in V^\perp} |\hat \nu(\xi) - {\Bbb I}(\xi = 0)$ |.
p. 384: in Lemma 10.22, $\eta$ needs to be between 0 and 1.
p. 385: in third display, $\xi-\xi'$ should be $\xi'-\xi$ , and similarly on the next two lines. In the next display, the sum $\eta + {\Bbb I}(\xi-\xi'=0)$ should be enclosed in parentheses.
p. 386: Exercise 10.2.1 is redundant (being essentially the union of 10.0.8 and 10.0.11) and should be deleted.
p. 387: In the first line, Theorem 10.12 should be Proposition 10.12; in the fourth line, Corollary 10.10 should be Proposition 10.10.
p. 388, fifth line of proof of Lemma 10.25: insert “, since” after “On the other hand”. In the third-to-last line, “the sum” should be “the summand”.
p. 389: in top line, “ $f$ is bounded” should be “ $f$ is bounded by 1″. In third line, $P$ should be $P'$ . In Exercise 10.3.1, add the hint “(You may want to first establish the weaker but easier bound $r_3(P) = o(|P|)$ .)”
p. 390: In Proposition 10.28, one should have $|S| = O( \delta^{-5} )$ rather than $|S| = O( \delta^{-3} )$ .
p. 391: The conclusion of Lemma 10.29 should be ${\Bbb E}_{n \in P'} f(n) = \Omega(\sigma)$ rather than $|{\Bbb E}_{n \in P'} f(n)| =\Omega(\sigma)$ (one wants a density increment, not a density decrement). To get this, one has to add “also, observe that the expression inside the norm has mean zero” just before the final display, replace the $L^\infty$ norm on the final display with a supremum (with no absolute values), and remove the absolute values on the first display of the next page.
p. 394: In the second, third, and fourth display, the indicator functions should be applied to x instead of r. Also, in the fourth equation, $\leq$ should be $\geq$ .
p. 398: About half-way down on the page, “to be introduce” should be “to be introduced”.
p. 402: in the last two displays, $\in a+bi+\alpha \in B$ should be $\in a+bi+\alpha+B)$ .
p. 407: In Remark 10.44, “Gowers shown” should be “Gowers has shown”.
p. 418: In “choices of $f_0,\ldots,f_{k-1})$ “, the parenthesis should be deleted.
p. 439: In the second line, $\xi \in W$ should be $x \in W$ . In the fourth line, $Mx \cdot x$ should be $Mx \cdot x = 0$ . In the proof of Proposition 11.12, “induce” should be “induct”.
p. 454: In the line before Theorem 11.27, the brackets \{ \} around $v_{k+1}$ are missing.
p. 462: In the last line, “in” should be $\in$ .
p. 465: “and some k-pseudorandom measure $\nu$ , then” should be “for some k-pseudorandom measure $\nu$ . Then”.
p. 474: In the proof of Lemma 12.6, “induce” should be “induct”. In Theorem 12.5, “constants” should be “constant”.
p. 500: In [288], “arithemtic” should be “arithmetic”.
p. 503: Reference [352] should be redirected to [380].
p. 505: $o_n \to \infty$ should be $o_{n \to \infty}$ , and O(f(n)) needs to be in math mode.
p. 506: “Chevalley-Waring” should be “Chevalley-Warning”, and Blichtfeld should be Blichfeldt.

– Errata to the revised edition –

p. 16. In the final display, $8 \log n$ should be $32 \log n$ . On the next line, “Corollary 1.10 (or Corollary 1.8)” should read “Corollary 1.9″.
p.17. In Exercise 1.3.4, $e^{\lambda \sigma/2\sqrt{2}}$ should be $e^{-\lambda \sigma/2\sqrt{2}}$ .
p.18. In Exercise 1.3.10, add “with $k, m$ not both equal to $1$ ” before the first comma.
p. 23: In (1.30), third summation, $v \in V$ should be $i\ in V$ .
p. 30. In the third display, $p \geq n-2n^{2/3}$ should be $p \geq n-n^{0.9}$ (say), and the third equality should be a $\geq$ sign.
p. 35, first line: a right parenthesis ) missing before ${\bf E}(Y)$ .
p. 36-37: The proof of Theorem 1.39 requires a number of significant changes. After the first paragraph, add “We will show first that with probability 1, that any natural number $n$ has at most a bounded number of representations as the sum of $k$ elements of $A$ between $n^\varepsilon$ and $n$ ; the treatment of the remaining sums in which at least one term is less than $n^\varepsilon$ is left as an exercise.” Then, in the definition of $Y_m$ and also in the computation of ${\bf E}(Y_m)$ , insert the lower bound $n^\varepsilon \leq n_1$ in the sum. On the first line of page 37, and in Exercise 1.7.2, replace $n^{-1/h}$ with $n^{-\delta}$ for some $\delta > 0$ . Extend Exercise 1.7.2 by adding “Then complete the proof of Theorem 1.39 by using similar arguments to treat the contribution of sums in which some of the summands have size less than $n^\varepsilon$ for some sufficiently small $\varepsilon$ , by using an induction hypothesis to bound the number of representations by sums of fewer than $k$ elements of size less than $n^\varepsilon$ .”
p. 42: Exercise 1.8.1 contains a number of inaccuracies (namely, “ $A \in {\bf Z}^+$ ” should be “ $A \subset {\bf Z}^+$ , and “no two elements” should be “no two distinct elements” (and so $2B$ should really be $2^* B$ here)), and is in any case a consequence of Theorem 6.2, and so should probably be deleted (it is rather difficult to establish this exercise with the tools developed up to that point).
p. 45: After equation (1.45), the assertion $p_k = k \log k + O_\epsilon(k^{1/2+\epsilon})$ should instead be $p_k = Li^{-1}(k) + O_\epsilon(k^{1/2+\epsilon})$ , where $Li(x) := p.v.\int_0^x \frac{dt}{\log t}$ is the logarithmic integral.
p.54: After the proof of Lemma 2.1, “Corollary 5.13″ should be “Lemma 5.13″.
p. 58: In Exercise 2.2.6, $2\sqrt{\sigma(A) |A|}$ should be $\sqrt{2\sigma(A) |A|}$ . (This error is not present in the first edition.)
p.62: In (2.7), after Definition 2.8, $\hbox{min}(|A| |B| )$ should be $\hbox{min}(|A|, |B| )$ .
p. 63: In the sixth line of the first display, $a-b'=a'-b$ should be $a-b'=y$ .
p. 83: In Exercise 2.5.5, the small K case is somewhat more difficult than the hint suggests, since if $K = 1 + \varepsilon$ for some small $\varepsilon$ then a direct application of Exercise 2.5.4 will give losses of $1 + O(\varepsilon^{1/2})$ rather than $1 + O(\varepsilon)$ . One way to proceed is to first use the lossy argument, apply Exercise 2.4.4 to locate a relevant finite group, and then use ad hoc arguments to refine the error. In Exercises 2.5.6 and 2.5.7, the reference [80] should instead be to “G. Elekes, I. Ruzsa, The structure of sets with few sums along a graph”, J. Combin. Theory Ser. A 113 (2006), no. 7, 1476–1500. Finally, in Exercise 2.5.7, the graph G should be assumed to be symmetric.
p. 116: In the proof of Corollary 3.6, $\{ n \in {\bf Z}^n: n \cdot (v_1,\ldots,v_n) = 0 \}$ should be $\{ m \in {\bf Z}^n: m \cdot (v_1,\ldots,v_n) = 0 \}$ , and “for some $w \in {\bf Z}^d$ ” should be “for some $w \in {\bf Z}^n$ .
p. 118: In the proof of Corollary 3.9, some explanation should be added as to why the torsion group is finite. This follows first from the observation that any subgroup of a finitely generated abelian group is also finitely generated (this follows from viewing the group as the image of a lattice and using Lemma 3.4), and that finitely generated abelian torsion groups are finite (because there are only finitely many distinct ways to combine the generators together).
p. 121: After Lemma 3.11, “exponentially in |A|” should be “exponentially in K”.
p. ???: In the proof of 3.19, the normalisation $\int_{\bf R} f = \int_{\bf R} g = 1$ should not be used; instead, one should normalise $\sup f = \sup g = 1$ (and the comment that it suffices to show $\int_{\bf R} h \geq 1$ should be deleted). The second display should then be restricted to the range $0 < \lambda < 1$ (note that Lemma 3.18 requires all sets involved to be non-empty), and one should also mention the weighted arithmetic mean-geometric mean inequality at the end of the proof.
p. 142: In the proof of Lemma 3.36, $L$ and $L_j$ should be $N$ and $N_j$ respectively (for consistency).
p. 131: In the second paragraph of the proof of Lemma 3.21, “translates of $\Gamma$ ” should be “translates of $\Gamma'$ “.
p. 133: The Kronecker approximation theorem should more accurately be called a simultaneous Dirichlet approximation theorem.
p. 134: In the first line, “with” should be “within”.
p. 135: In the definition of $\lambda_j$ , $k$ should be $j$ .
p. 154: In display (4.9) there is a full stop missing.
p. 155: In Exercise 4.1.7, ${\bf E}_{\xi \in H^\perp} \hat f(\xi)$ should be $\sum_{\xi \in H^\perp} \hat f(\xi)$ . In Exercise 4.1.8, $f((\phi^\dagger)^{-1}(x))$ should be $\hat f((\phi^\dagger)^{-1}(x))$ .
p. 158: In the proof of Lemma 4.10, in the final display, the last equals sign should be a $\geq$ sign. An additional sentence of explanation should be added: “The penultimate inequality follows from Plancherel’s theorem, followed by Minkowski’s inequality to estimate the $L^2$ norm of f.”
p. 163: In Exercise 4.3.4, “is contained in a coset” should read “is a coset”. In Exercise 4.3.14, Polya should be Pólya (and similarly for the corresponding entry in the index). In Exercise 4.3.2, $T^h A$ should be $h+A$ .
p. 168-169: Before Proposition 4.23, “dispense with” should be “almost dispense with”. In Proposition 4.23, the proper progression $P$ should be the proper coset progression $P+H$ , where $H$ is a subgroup of ${\bf Z}_N$ (i.e. the multiples of $M$ for some factor $M$ of $N$ ). The last sentence of the proposition is redundant and can be deleted. In the proof, one first handles the case when $\alpha$ has order $N$ in ${\bf Z}^d$ , in which case the first display of p.169 is an equality, and one obtains a progression of rank $d$ . In the general case, when $\alpha$ has order $M$ for some $M$ dividing $N$ , one then passes from ${\bf Z}_N$ to ${\bf Z}_M$ by quotienting out the group $H$ generated by $M$ , and then applies the previous case.
p. 170: In the proof of Lemma 4.25, “find thus find” should be “thus find”.
p. 171: In Exercise 4.4.7, “lower” should be “increase”.
p. 174: In Remark 4.31, the sentence “The converse statement is true up to logarithmic factors; see exercises.” should be deleted.
p. 176-177: The denominator $4+\varepsilon$ in (4.34) can be improved to $2+\varepsilon$ , by setting $\sigma$ equal to $\lambda$ instead of $\lambda/2$ in page 177 (changing the fourth and fifth displays appropriately).
p. 180: Exercise 4.5.11 does not work as stated and should be deleted.
p. 181: In Lemma 4.35, add “ $k \geq 0$ is an integer, ” after “where”. In the proof, “incrementing $k+1$ ” should be “incrementing $k$ to $k+1$ “.
p. 183: In the statement of Lemma 4.37, the second “an” should be “a”.
p. 187: In the statement of Theorem 4.41, the upper bound for $\|H\|_u$ should be $p^{-\varepsilon} {\bf P}_F(H)$ rather than just $p^{-\varepsilon}$ .
p. 188: At the end of the proof of Theorem 4.41, add the following parenthetical remark: “The upper bound on $|A|$ required for Corollary 2.62 is supplied by (4.37) and the lower bound on $|H|$ .” In Exercise 4.6.2: $\hbox{Sym}_0$ should be $\hbox{Sym}_1$ (two occurrences).
p. 189: In the discussion after Theorem 4.42, the bound $E(A,A) \geq |A|^2$ should be $latex E(A,A) >= P(A) |A|^3$.
p. 191: In the third equation of the display, the $L^2(Z)$ norms should be $\ell^2(Z)$ (and the final term $\widehat{1_{A_3}}(\xi)$ should just be $\widehat{1_{A_3}}$ .
p. 193: Lemma 4.46 has a redundant “such that”.
p. 194: In Theorem 4.47, the $\frac{(\log \log N)^3}{\log N}$ should be $\frac{(\log \log N)^{3/2}}{\log^{1/2} N}$ , and $(\delta \log N)^{1/3}$ should be $(\delta^2 \log N)^{1/3}$ .
p.196: A right parenthesis is missing after the reference to Green [149]. In the penultimate line in the proof of Theorem 4.47, as well as in the sentence immediately after this proof, and in the second sentence on page 197, $(\delta \log N)^{1/3}$ should be $(\delta^2 \log N)^{1/3}$ .
p. 199: In the second sentence in the paragraph before the statement of Lemma 5.3, “Lemma” should be uncapitalised.
p. 211: In the statement of Lemma 5.13, “let suppose” should be just “suppose”.
p. 226: In Exercise 5.3.4, the hypothesis “ $0 \in A$ ” is missing.
p. 254: In exercise 6.2.8, the adjective “triangle-free” should be deleted.
p. 271: In Section 6.5.2, $G_1 \circ \ldots \circ G_k$ should be $G_k \circ \ldots \circ G_1$ (two occurrences).
p. 279: In Proposition 7.7, $\lfloor (|X|+i)/2\rfloor$ should be $\lfloor |X|/2\rfloor + i$ .
p. 286: In the second paragraph, the condition $\alpha \geq {\bf E}_{Z_p}(G)$ should be replaced by $\alpha > \min G$ , and the phrase “by Markov’s inequality” should be dropped. Similarly, in the third and fifth displays, the first occurrence of ${\bf E}_{Z_p}(G)$ in each should be $\min G$ .
p. 291: In the definition of $w(\xi)$ after the first display, a $d\xi_1$ is needed at the end of the integral. In the first paragraph, add “but still bounded” after “sufficiently large”.
p. 292: In Exercise 7.3.4, the comma should be an apostrophe.
p. 299: In the first display, $3 \log_ 2 n$ should be $3n/\log_2 n$ .
p. 315: In the proof of Theorem 8.14, $c \in P$ should be $c \in A$ .
p. 316: In the third to last line, $|A|^{18/3}$ should be $|A|^{8/3}$ .
p. 331: In the third and fifth displays, the summation should run up to $|S_n|-1$ rather than $|S_n|$ . In the proof of Theorem 9.2, $t_{n-1}^{d_n-1}$ should be $t_{n-1}^{d_{n-1}}$ .
p. 333: In the proof of Lemma 9.3, “P vanishes on contains” should be “P vanishes on a set which contains”.
p. 346: “Cauchy’s theorem” should be “Lagrange’s theorem”.
p. 370: In the last paragraph, the reference “Meshulam [248]” should instead be “Brown and Buhler [BB] (see also Frankl, Graham, and Rodl [FGR]“, where [BB] is “T. C. Brown and J. C. Buhler, Lines imply spaces in density Ramsey theory, J. Combin. Theory Ser. A 36 (1984), 214-220.”, and [FGR] is “P. Frankl, R. Graham, and V. Rodl, On subsets of abelian groups with no 3-term arithmetic progresion, J. Combin. Theory Ser. A 45 (1987), 157-161.”
p. 388: In Lemma 10.25, there should be no absolute value signs around ${\bf E}_{n \in P'} f(n)$ . In the last display, $\delta N/4$ should be $\delta/8$ , and in the first display on page 389, $\sigma |P_0|/4$ should be $\sigma |P_0|/8$ .
p. 388, 390-391: The Kronecker approximation theorem should more accurately be called a simultaneous Dirichlet approximation theorem.
p. 391: In Lemma 10.29, $[1,n]$ should be $[1,N]$ , there should be an additional hypothesis of ${\bf E}_{n \in [1,N]} |f(n)| \leq \delta$ . The bound $\Omega(\sigma N^{1/(|S|+1)})$ should be $\Omega(N^{1/(|S|+1)})$ , and the bound $\Omega(\sigma)$ should be $\Omega(\sigma/\delta)$ . In the third display of the proof, the right-hand side of 1 should be $\delta$ , and in the fifth display, the right-hand side should be $\Omega(\sigma/\delta)$ .
p. 397: In Exercise 10.4.2, Lemma 10.15 should be Lemma 10.29.
p. 412: In the second case of Corollary 10.50 the word ’and’ should be inserted.
p. 414: In the first paragraph, “motivation” should be “motivations”.
p. 465: In the definition of $P_{W,b,N}$ , $Wp+b$ should be $Wq+b$ ; also, on the last line, “to order to” should be “in order to”.
p. 477: In the top line, “an positive” should be “a positive”.
p. 492: [98] and [100] refer to the same article; [98] should be deleted and redirected to [100].

Thanks to Eric Aas, Andrea, Louigi Addario-Berry, Khodakhast Bibak, Thomas Bloom, Lin Bo, Richard Brent, Tom Brown, Andres Caicedo, Rafael Tesoro Carretero, Kestutis Cesnavicius, Mei-Chu Chang, Sheng-Fu Chiu, David Colvert, Paul Delhanty, Moubariz Garaev, Paul Hagelstein, Le Thai Hoang, Tom Koornwinder, Jarek Kuben, Choongbum Lee, Mark Lewko, Victor Lie, Isabel Lugo, Heiko Mattern, Vicky Neale, Gyan Prakash, Sean, Tomer Shalev, Olof Sisask, Justin W. Smith, Srivastan, Thomas, Sam van Gool, and Mate Weirdl for corrections.

154 comments

Comments feed for this article

28 January, 2008 at 6:58 am

Hoang

On p.263 :”Let us call a pair (a,a’) bad if they are not connected by at least $\frac{L^2 \|B\|}{8K^2}$ paths of length 2″, shouldn’t that number be $\frac{L^2 \|B\|}{128K^3}$ ?. The same $\frac{L^2 \|B\|}{8K^2}$ also appears and need to be replaced on p.264

28 January, 2008 at 10:37 am

Terence Tao

Thanks for the correction!

31 January, 2008 at 3:16 pm

Anonymous

Would you mind elaborating a bit on (Open) Question 1.4 in section 1.1 of the text. I’m assuming you are using n here to indicate |A| in the previous theorem. As I read it this result can’t be true as (n/3)+10 can exceed the size of the set for small sets. That aside I’m curious about the constant 10. Bourgan’s paper appears to show that there exists B (in the language of Theorem 1.3) such that |B|>= |A|/3 +2. Has there been further improvement to the constant increasing it to 9? Are counterexamples know for 11? Thanks for the clarification and great blog!!

31 January, 2008 at 4:16 pm

Hao

Dear Anonymous,

I think you can consider n sufficiently large so that small sets are not important here. Bourgain’s result should be |A|/3+2/3, slightly better than |A|/3+1/3 by the probabilistic method.

1 April, 2008 at 2:25 am

Anonymous

Dear Professor Tao,

Sorry for bothering you.
I have some questions on the proof of Lemma 4.25, on p. 170.

a. In line 3, when invoking Lemma 4.20, where does the number 5 in the log come from? Why isn’t that a 4?

b. In line 5, where it says that this should hold for all $|a| \leq 0.1$ : I cannot really make sense of it. Did you mean $|a-a'| \leq 0.1$ ?

c. To be honest to the point of embarrassment: I cannot easily see why the Bohr set is then regular. For the quotients of the densities of the two Bohr sets, I always get a useless estimate: $(1 + \kappa)^{20d}$ instead of $1+100d \kappa$ …..

1 April, 2008 at 2:49 pm

Terence Tao

Dear Anonymous,

You are correct, one can replace $\log_2 5$ with $\log_2 4$ (i.e. with 2) in that bound, and that the condition $|a| \leq 0.1$ should be $|a-a'| \leq 0.1$ .

For your last question, one has that $(1+\kappa)^{20d} \leq 1+100d\kappa$ whenever $\kappa \leq 1/100d$ . This follows from the inequalities $1+x \leq \exp(x) \leq 1 + 5x$ whenever $0 \leq x \leq 1/5$ , which follow from the fundamental theorem of calculus (since $\exp'(x) = \exp(x)$ is bounded between 1 and 5 in the interval ${}[0,1/5]$ ).

2 April, 2008 at 12:34 am

Vicky Neale

On page 107 (in the proof of Proposition 2.61) there seems to be a reference to Exercise 1.1.8. I haven’t found Exercise 1.1.8; is there a typo?

Thanks!

2 April, 2008 at 9:59 am

Terence Tao

Hmm, that’s strange, that exercise managed to get deleted from the print version. It’s now in the errata above.

14 April, 2008 at 10:39 pm

Anonymous

Dear Prof Tao

I have some questions about the proof of Proposition 10.32.

* On p. 394, 2nd, 3rd & 4th displayed equation, I think some of the $r$ s should be replaced by $x$ s?

* 4th displayed equation on that page: should that be $\ge$ instead of $\le$ ?

Thanks!

17 April, 2008 at 10:00 am

Terence Tao

Dear anonymous: Thanks for the correction!

13 June, 2008 at 7:42 am

Isabel Lugo

Exercise 6.1.4 (“Cauchy-Schwarz for bipartite graphs”) appears to be in error.

You ask for proofs:
(a) that a bipartite graph $G(V_1, V_2, E)$ contains at least $|E|^2/|V_2|$ paths of length two with both endpoints in $|V_1|$ , including degenerate paths;
(b) that it contains at least $|E|^4/(|V_1| |V_2|)$ cycles of length 4.

A Cauchy-Schwarz type argument gives the answer for the first part. Another C-S argument, when I attempted it, gave me a bound of $|E|^4/(|V_1| |V_2|)^2$ for the second part. And this appears to be sharp; for example consider the complete bipartite graph $K_{n,n}$ . This graph has $n^2$ edges and a number of 4-cycles which grows like $Cn^4$ for some positive constant C — the exact count depending on how degeneracies are counted and whether things like (1, 2, 3, 4) and (3, 4, 1, 2) are counted as different cycles. The bound given in the problem is $n^6$ .

13 June, 2008 at 7:46 am

Isabel Lugo

Also, although this is irrelevant to this post — my previous comment shows up with the time stamp “13 June, 2008 at 7:42 am”. I made it at 11:42 am US Eastern time (my local time); I assume since you’re in Los Angeles your blog uses US Pacific time (your local time), hence it should show 8:42 am. I suspect for some reason WordPress is not adjusting for daylight savings time.

13 June, 2008 at 2:43 pm

Isabel Lugo

Another potential erratum: the second displayed equation on p. 310 (lower bound for the crossing number) is given as

$cross(G) \ge p^{-3} |E| - 3 p^{-2} |V|$

but this should be

$cross(G) \ge p^{-2} |E| - 3 p^{-3} |V|$ .

14 June, 2008 at 10:53 am

Terence Tao

Dear Isabel: Thanks for the corrections! WordPress.com does not seem to have an easy way to automatically adjust for daylight savings; I could move the blog time zone back and forth an hour every six months, but this seems to be more trouble than it is worth…

7 October, 2008 at 12:00 pm

Finite subsets of groups with no finite models « What’s new

[...] larger than A itself if A has some additive structure; see this paper of Ruzsa (or Lemma 5.26 of my book with Van Vu) for a precise statement. This projection trick has a number of important uses in additive [...]

12 October, 2008 at 2:00 pm

Paul Hagelstein

In Appendix 1.10 p. 47, the last two equations for the sums over primes less than or equal to n feature an “n” on the LHS but not the RHS. Offhand the only correction I see involves an “integration by parts” argument frequently associated to Abel’s summation technique, but I have the impression that you have a more efficient argument in mind!

12 October, 2008 at 2:49 pm

Terence Tao

Dear Paul: Thanks for pointing out the issue! I have adjusted the erratum for that page to provide what I think fixes the problem.

6 December, 2008 at 10:43 am

Sean

Here are some possible typos:
– p. 1: I think the last equation should end “E(X^2) – E(X)^2″ (no absolute values).
- p. 8: $|B| - 10 \leq \nu(x) \leq |B|$ should read $|B| \leq \nu(x) \leq |B| + 10$ .
- p. 58, Exercise 2.2.5: There are examples of additive sets A with non-empty subsets B which have doubling constant larger than \sqrt{ \sigma[A]|A|/2 }. Take A = B with |A| \leq 2, or (less trivially), A = {0,1,2,3} and B= {0,1,3}. However, it is easy to show that the doubling constant of B is at most \sqrt{ \sigma[A]|A| }. Is this the correct bound for the exercise, or is the bound meant asymptotically? I’m guessing that changing the bound in Ex 2.2.5 also affects the bound in Ex 2.2.6.

Thanks!

9 December, 2008 at 6:48 am

Terence Tao

Dear Sean, thanks for the corrections!

4 October, 2012 at 6:32 am

ablmff

Hi, for 2.2.6, isn’t it easy to prove the bound \sqrt{ 2 \sigma[A] |A| } ? We are confused why 2 should be outside the square root.

[Yes, you're right; this was actually correct in the first edition, but was mistakenly revised in the second edition. I'll add a new erratum to reflect this. -T]

4 February, 2009 at 4:01 am

Vicky Neale

I’m a bit anxious about the spelling of Blichtfeld/Blichfeldt as it appears on page 134 (Lemma 3.27) and in the index. For example, the splendid Mactutor history of maths site has a biography of Blichfeldt (http://www-history.mcs.st-and.ac.uk/Biographies/Blichfeldt.html). I’m certainly not an expert, though!

5 February, 2009 at 9:12 am

Terence Tao

Oops, you’re right, thanks!

3 March, 2009 at 6:55 pm

John

Could it be the case that the second exponent in exercise 2.3.13., p.68, is wrong? $|A+A|\leq |A-A|^{3/2}$ seems hard to prove at this point of the text (whereas $|A+A|\leq |A-A|^{2}$ would follow along the same lines of the first inequality). Thanks!

4 March, 2009 at 8:56 am

Terence Tao

Dear John,

I think it works in both directions (for the second inequality, you have to substitute -A for B).

7 March, 2009 at 7:47 pm

Anonymous

Dear Professor Tao,
In page 122, after the first math display, should one read “In particular we have $nA=n\cdot A$ “?

8 March, 2009 at 9:55 am

Terence Tao

Dear anonymous:

Thanks for the correction!

25 April, 2009 at 6:13 am

Anonymous

Dear Prof Tao,

This comment is somewhat tangential, but concerns the proof of the Squeezing Lemma (page 137):

How does one go about showing the existence of a continuous right inverse of $\pi$ ? I can’t seem to find a rigorous definition of centre of mass.

Thanks

27 April, 2009 at 10:28 am

Terence Tao

Dear anonymous,

The centre of mass of a bounded non-empty open set A of in ${\Bbb R}^n$ is defined as the vector $\frac{1}{mes(A)} \int_A \vec x\ dx$ . The dominated convergence theorem can be used to establish continuity of the centre of mass with respect to the type of perturbations in A one would encounter in the squeezing lemma.

28 May, 2009 at 2:18 am

Olof Sisask

Exercise 10.2.1 appears to duplicate exercises 10.0.8 and 10.0.11, and this may not be intentional. (I would say that 10.2.1 is the outlier, rather than 10.0.8 and 10.0.11.)

Thanks.

28 May, 2009 at 9:15 am

Terence Tao

Hmm, how strange. It’s not exactly an erratum, but I’ll make a note of it nevertheless.

29 May, 2009 at 9:30 am

Olof Sisask

A small typo: four lines into the proof of Cauchy-Davenport on p. 200, the |A_e| + |B_e| on the left-hand side of the inequality should be |A_e + B_e|. [Updated, thanks - T.]

25 June, 2009 at 5:13 pm

Sumset and inverse sumset theorems for Shannon entropy « What’s new

[...] Probability, and Computing. This paper evolved from a “deleted scene” in my book with Van Vu entitled “Entropy sumset estimates“. In those notes, we developed analogues of the [...]

8 July, 2009 at 8:50 pm

Mark Lewko

On page 465, should q and p be the same parameter in the definition of P_{W,b,N}? Also on page 465, I think there might be a typo in the phrase “again needed to order to neglect the r = 0 diagonal term”. [Corrected, thanks - T.]

17 July, 2009 at 10:00 am

Hales-Jewett 定理的归纳证明 « Liu Xiaochuan’s Weblog

[...] der Waerden’s theorem都是它的特例。下面的证明是在Terence Tao和Van Vu的书 Additive Combinatorics [...]

23 July, 2009 at 2:10 am

Vicky

A very tiny point: I think that in Exercise 4.3.14 (page 165), Polya has lost his accent. This seems to be the case in the corresponding index entry too.

Thanks.

[Corrected, thanks - T.]

5 August, 2009 at 8:55 am

Andrea

Dear Prof. Tao,

on page 331, in the third display one sum extremum shouldn’t be $\left|S_{n}\right| - 1$ instead of $\left|S_{n}\right|$ ? The same in the fifth display. [Corrected, thanks -T.]

20 August, 2009 at 1:16 pm

Mark Lewko

Here are a few possible typos I have collected. In the proof of Lemma 4.25 on page 170, the phrase “find thus find” reads like a typo. On page 292, should the comma in exercise 7.3.4 be an apostrophe? Related to this, did the title of reference [367] change? It doesn’t seem to appear on your website (at least under this name). Lastly, I think the page numbers for reference [41] are off (or its a rather lengthy paper!).

20 August, 2009 at 7:53 pm

Terence Tao

Thanks for the corrections! The paper [367] is still on the backburner, but we’ll get to it at some point…

26 October, 2009 at 5:59 pm

Mark Lewko

Could you give me a(n additional) hint on exercise 4.5.11, specifically on how to “reverse the proof of Lemma 4.30″? It appears that you need to be able to show that $r_{h_{1},h_{2}}(n)$ can’t be large very often, however it isn’t clear to me how to deduce this from the hypothesis.

Also, assuming that you can prove the estimate for characteristic functions (which is what my question refers to), I think you should be able remove the logarithm that arises from the dyadic pigeonhole argument with the tensor product trick.

26 October, 2009 at 7:51 pm

Terence Tao

Ack, yes, you’re right. The problem still works if the hypothesis $|hS'| \geq |S'|^h/A^{2h}$ is strengthened to $\sum_{\xi \in hS'} r_{h;S'}(\xi)^2 \leq A^{2h} |S'|^h$ , where $r_{h,S'}$ is the analogue of $r_h$ for $S'$ , but this is not nearly as interesting. I don’t see an easy way to salvage the original spirit of the exercise and so it will unfortunately have to be deleted.

31 October, 2009 at 5:57 pm

Mark Lewko

The statement of Lemma 4.46 on page 193 contains an unneeded “such that”. [Corrected, thanks - T.]

12 November, 2009 at 10:26 am

An elementary non-commutative Freiman theorem « What’s new

[...] established. However, I wanted to record here an elementary argument (based on Exercise 2.6.5 of my book with Van Vu, which in turn is based on this paper of Izabella Laba) that handles the case when is very close [...]

16 December, 2009 at 9:02 am

Olof

Small typo: p. 474: In Theorem 12.5, “constants” should be “constant”.

Thanks.

[Corrected, thanks - T.]

9 January, 2010 at 10:11 am

Thomas

On page 333, in the proof of Lemma 9.3, the second to last sentence reads “…P vanishes on contains…” where it should presumably read “…P vanishes on a set which contains…”

[Thanks for the correction - T.]

12 January, 2010 at 1:53 pm

Justin W Smith

pg 315. Proof of Theorem 8.14. Small typo.

Should say “…namely the points $(b + c, ac)$ with $c \in A$.”

[Corrected, thanks - T.]

23 February, 2010 at 11:38 pm

Ryosuke

Dear Prof. Tao,

On page 145, is theorem 3.40 true for any addivitve group? I found there is a additional condition “near torsion-free” in reference [365] in remark 3.41 and I don’t know if this condition can be removed or not. (In [365], you say it can be replaced by bound |P|.) Thanks.

24 February, 2010 at 12:07 am

Terence Tao

The torsion-free hypothesis is only needed to ensure that the proper progression Q is symmetric; otherwise, the arguments still work with torsion (though they become a little bit lengthier).

In Corollary 1.18 of our subsequent paper in

http://arxiv.org/abs/math.CO/0701005

Van and I obtained a sharper result (using some ideas communicated to us by Ben Green). The symmetry problem can be avoided by redefining the concept of a generalised arithmetic progression in a manner that allows one to define non-integer dilates P_t of a progression P.

12 March, 2010 at 10:20 pm

Ryosuke

Dear Prof. Tao,

I don’t know how to apply Chernoff’s inequality on Lemma 4.16.. In fact, I don’t know how to define random variables like Chernoff’s inequality on p 11. Could you give me a hint? thanks.

14 March, 2010 at 12:10 am

Terence Tao

One can write the indicator function $1_B$ as $\sum_{a \in A} X_a \delta_a$ , where $\delta_a$ is the Kronecker delta at $a$ , and the $X_a$ are iid Bernoulli random variables.

15 March, 2010 at 9:26 pm

Ryosuke

Dear Prof. Tao,

On p 168, Lemma 4.22, since inequality (4.28) is proved by discrete John’s lemma, I think its power of d’ should be -3d’/2. Isn’t it?

19 March, 2010 at 2:51 pm

Terence Tao

The argument uses the leftmost inclusions of the discrete John theorem, rather than the rightmost inclusions.

20 April, 2010 at 12:41 am

Ryosuke

Dear Prof. Tao,

On p 169, you use 2nd Minkowski theorm to prove lemma 4.23, but it seems that to get lower bound of |P| we need upper bound of mes(R^d/Gamma) in stead lower bound (1/N in p169).

20 April, 2010 at 9:40 am

Terence Tao

Oops, good point! One has to fix the proposition by replacing P by P+H, where H is a subgroup of $Z_N$ (i.e. a cyclic group generated by some factor $M$ of $N$ ). The point being that the if the order $M$ of $\alpha \hbox{ mod } Z^d$ is a factor of $N$ , rather than being equal to $N$ , then one has to quotient out by the subgroup $H$ first before the top display of p.169 becomes an equality. I’ve added an erratum to this page to reflect the changes.

26 April, 2010 at 1:35 am

Ryosuke

Dear Prof. Tao,

On p 176, I find that right hand side of (4.34) in lemma 4.33 can be written as exp(- (lambda^2)/(2+epsilon)). Since we can simply multiply “i” to get exp(- (lambda^2)/4) in proof.

I want to consult an other question: In proposition 4.29. Is there any inductive formula of alpha(h, |S|)?

Thanks!

26 April, 2010 at 10:50 am

Terence Tao

Dear Ryosuke,

I don’t see how to use multiplication by i to improve the exponent to $\lambda^2/2$ ; using the inequality $|z| \leq \sqrt{2} \max( |\hbox{Re}(z)|, |\hbox{Re}(iz)| )$ only gives $\lambda^2/8$ .

In principle $\alpha(h,|S|)$ can be written down explicitly, but I doubt that there is a formula for it that does not involve at least one summation sign. In the asymptotic limit $|S| \to \infty$ it becomes $(h!)^{1/2h}$ .

28 April, 2010 at 5:25 pm

Ryosuke

Dear Prof. Tao,

In your Errata, p177 and taking lambda=sigma, I get the fourth display should be e^(-lambda^2)/2 rather than e^(-lambda^2)/4. So I get 4 rather than 8.

28 April, 2010 at 7:48 pm

Terence Tao

Ah, fair enough; I’ve added the improvement as an erratum.

4 May, 2010 at 4:29 am

Gyan

Dear Professor Tao,
The proof of Theorem 4.41 as per the edition ISBN-13 978-0-521-85386-6
is a bit unclear to me.
The lower bound obtained for $E(x^{-1}A, H)$ with $A= {\rm Spec}_{\alpha_j}$ is fine. Then on page 188 third line, the Reader is
asked to use Corollary 2.62 to obtain a contradiction. However to use
Corollary 2.62 directly, we will need to have some upper bound for the
cardinality of A. For instance $|A| < p^{1-\delta}$ will suffice.
I do not know how to obtain such a bound.

The case when $|A| > p^{1-\delta}$ can be however easily handled
by appealing to Exercise 4.6.3 to obtain a lower bound for $E(H,H)$ and then applying Corollary 2.62 to obtain a contradiction.

4 May, 2010 at 8:39 am

Terence Tao

I believe (4.37) establishes such an upper bound on |A| using the lower bound hypothesis on |H|. I’ll add a note in the errata to clarify this.

4 May, 2010 at 10:33 pm

Gyan

Using the assumed lower bound $p^{\delta}$ for $|H|$ and (4.37), we will get that |A| is not more than $(\alpha_j)^{-2}p^{1-\delta}$ . Therefore we obtain that |A| is at most $p^{\epsilon C(J)}p^{1-\delta}.$ Since the present statement of Corollary 2.62 gives result only for those A with |A| at most $p^{1-\delta}$ , it is not clear how to use it
directly.

However I believe that the statement of Corollary 2.62 is true even for those A with |A| at most $p^{1-\frac{\delta}{2}}$ . This follows from the same proof as given in the book. Once one observes this, the problem mentioned above disappears.

5 May, 2010 at 2:45 am

Gyan

Dear Prof. Tao,

Sorry, I missed the trivial fact that $|H| > p^{\delta}$ implies that $|H| > p^{\delta/2}$ . Therefore Corollary 2.62 is trivially applicable for the sets A with $|A| < p^{1-\frac{\delta}{2}}.$ This clears all my earlier confusions.

A small typo in the statement of Theorem 4.41.
Shouldn’t “…. $||H||_u < p^{-\epsilon}$ ….” be replaced by $||H||_u < p^{-\epsilon}\frac{|H|}{p}$ ?

[Corrected, thanks. - T.]

6 May, 2010 at 5:53 am

Ryosuke

Yes, I also faced this problem, and I find the same way as you did. So happy it is right.

6 May, 2010 at 5:59 am

Thomas Bloom

A couple of minor errors.
On page 346, “Cauchy’s theorem” should be “Lagrange’s theorem” and on page 414, “motivation” should be “motivations” (first paragraph).

[Added, thanks - T.]

18 May, 2010 at 4:41 pm

Weiyu Xu

a few comments and questins on proving Lemma 7.17 (Esseen Concentration Inequality).

Comments:
1. On Page 291, in the definition of w(\xi), I believe we are missing a “d\xi_{1}”
2. Right before the definition of w(\xi), , should the equality be replaced with an inequality?

one question: In Equation (7.4) on page 290, is \Omega(1) dependent on C?

18 May, 2010 at 9:52 pm

Terence Tao

Thanks for the corrections! For 2, both equality and inequality would be appropriate here (due to the nature of the Omega(1) notation). The constants here do depend on C, but C will be taken to be bounded (this should have been mentioned at the top of page 291).

20 May, 2010 at 9:45 pm

254B, Notes 5: The inverse conjecture for the Gowers norm I. The finite field case « What’s new

[...] lemma and Freiman’s theorem for vector spaces; see Section 11.3 of my book with Van for further discussion. The proof is elementary but a little lengthy and would take us too far [...]

1 June, 2010 at 5:37 pm

Ryosuke

Dear Prof. Tao,

On p 279, proposition 7.7, I think [(|X|+i)/2] should be replaced by [|X|/2]+i, then it will be the same result in lemma of [206].

I am not sure if you want to state proposition as I thought.

1 June, 2010 at 8:42 pm

Terence Tao

I believe the two sums are the same (both are equal to the sum of the k largest binomial coefficients).

1 June, 2010 at 9:17 pm

Ryosuke

Yse, I know that
{sum C(|X|,[(|X|+i)/2] ) from i=1 to k} = {sum C(|X|, [|X|/2]+i) from i = integers between -k/2 to (k-1)/2}

but in your book, the express is {sum C(|X|, [(|X|+i)/2) from i = integers between -k/2 to (k-1)/2}.

1 June, 2010 at 10:57 pm

Terence Tao

Ah, I see what you are saying now. Thanks for the correction!

7 June, 2010 at 7:24 am

Thomas Bloom

In Exercise 6.2.8, G shouldn’t be ‘triangle-free’, as later in the same sentence it has ‘T triangles’.

Also, in Exercise 1.1.7, do you need the 10 in loglog(10+Z)? I did the exercise without needing it, and isn’t loglog(10+Z)=O(loglogZ) (and vice versa) anyway?

Thanks.

7 June, 2010 at 9:28 am

Terence Tao

Thanks for the correction! The 10 is there purely to prevent the double logarithm from becoming negative.

8 June, 2010 at 5:46 pm

Ryosuke

Dear Prof. Tao,

Can you give me some hint to drive lest display of proof of lemma 7.14 ?
Because everytime I use pointwise bound F < G^theta(u'/u), I get RHS of lest inequality = E(G)^c instead power theta(u'/u).

thank you.

8 June, 2010 at 7:49 pm

Terence Tao

Ah, the cutoff in $\alpha$ here was not optimised correctly. The first case $\alpha \geq {\bf E}_{Z_p}(G)$ should instead be enlarged to $\alpha > \min G$ (which does not affect the contribution of this case), so that the second case can be shrunk down to $\alpha < \min G$ (at which point the stated argument works). I've added an erratum accordingly.

8 June, 2010 at 8:57 pm

Ryosuke

Yes, you’re right! thank you.

20 June, 2010 at 6:10 am

Anonymous

Dear Prof. Tao,

Can you explain first display of last paragraph on p 295? I cannot figure out how to apply volume-packing argument on it.( I cannot find additive structure of these sets. )

thank you.

21 June, 2010 at 5:29 pm

Terence Tao

This particular display is just a consequence of the monotonicity properties of $P( X_{1^{k^2}}^{(1/4d)}=m)$ stated at the beginning of the paragraph. (It is a component of the volume packing argument, rather than a consequence of it.)

22 June, 2010 at 12:06 am

Ryosuke

But it seems strange. RHS is a average of $P(X_{1^{k^2}}^{(1/4d)}=m)$ (And I think there miss a ‘ for $m$ ) with center at $m$ . If $m=0$ RHS should be small than LHS, I still cannot understand how to use monotonicity to get this.

22 June, 2010 at 8:59 am

Terence Tao

When m=0 one can use the fact that this expression is comparable to 1/k for $|m| \leq k$ , as mentioned in the preceding paragraph.

22 June, 2010 at 5:50 pm

Ryosuke

So let $f(m)=P(X_{1^{k^2}}^{(1/4d)}=m)$ , I know we have: 1. $f(m)$ decreasing for $m \geq 0$ . 2. $f(m)$ is even. 3. $f(m) = O(1/k)$ for all $m$ and $f(m)=\Omega (1/k)$ for all $|m| \leq k$ . So you mean we can use 1~3 to prove:
$f(m)= O_d(\frac{1}{k} \sum_{n \in (m-k/2, m+k/2)}f(n))$ ?

22 June, 2010 at 6:33 pm

Terence Tao

Yes, this is correct (together with the fact that f is nonnegative). For m = O(k) one uses 3; for |m| >> k one uses 1 and 2.

23 June, 2010 at 12:19 am

Ryosuke

Oh, I get it! thanks!

20 June, 2010 at 10:33 pm

Ryosuke

Dear Prof. Tao,

On p 299, I cannot derive conclusion form first display. Can you explain how to computate it? Thanks.

21 June, 2010 at 5:35 pm

Terence Tao

The dominant contribution is when $n-k$ is close to $3 n/\log_2 n$ . In that regime, the final factor in the first display is already much smaller than $2^{-n}$ (it’s basically $2^{-3n/2+o(n)}$ . The first two factors are $2^{o(n)}$ , so together they smaller than the desired bound (with a bit of room to spare).

21 June, 2010 at 5:02 pm

Tom

For exercise 1 in chapter 1…what am I missing: Want to show that $E(X) = \int_{0}^{\infty} P(X > \lambda) \ d \lambda$ . So $E(X) = \int_{0}^{infty} \lambda p(\lambda)$ . Or:

$E(X) = \lambda P(X \leq \lambda)- P(X \leq \lambda)$

$= \lambda P(X \leq \lambda)- E(X) = \int_{0}^{\infty} P(X \leq \lambda) \ d \lambda$

$= \lambda P(X \leq \lambda)- E(X) = \int_{0}^{\infty} 1-P(X > \lambda) \ d \lambda$

$= \lambda P(X \leq \lambda)- E(X) = \lambda- \int_{0}^{\infty} P(X > \lambda) \ d \lambda$

Thus: $\int_{0}^{\infty} P(X > \lambda) \ d \lambda = E(X)-\lambda [\underbrace{P(X \leq \lambda)-1}_{0}]$ .

Is that correct? Can we use Markov’s Inequality?

21 June, 2010 at 5:39 pm

Terence Tao

I’m sorry, your equations are not making sense. (For instance, you are using $\lambda$ both as a free variable and as a dummy variable of integration.) Also, you seem to be trying to derive consequences of the desired identity, rather than trying to prove it. I would recommend trying to explicitly compute a concrete example, e.g. let X be a random variable that equals 5 with probability 0.3 and 0 with probability 0.7, as this may help clear up some confusion.

21 June, 2010 at 6:11 pm

Tom

Dear Terry,

I was trying to do the following: $E(X) = \int_{0}^{\infty} \lambda p(\lambda) \ d \lambda \Rightarrow E(X) = \int_{0}^{\infty} P(X > \lambda) \ d \lambda$ (assuming $X$ is non-negative).

23 June, 2010 at 8:45 am

Terence Tao

Try expressing $P(X > \lambda)$ in terms of the probability density function $p(\lambda)$ . (Strictly speaking, this only works for continuous probability distributions, unless one uses measure theory.)

24 June, 2010 at 9:06 pm

Tom

$\int_{0}^{\infty} P(X > \lambda) \ d \lambda = \int_{0}^{\infty} \int_{\lambda}^{\infty} p(x) \ dx \ d \lambda$ .

Is this correct?

25 June, 2010 at 5:27 am

Now try Fubini !!!

25 June, 2010 at 6:44 pm

The uncertainty principle « What’s new

[...] under addition a “reasonable fraction of the time”; for a precise definition, see my book with Van Vu). However, there are dyadic models of Euclidean domains, such as the field of formal Laurent [...]

29 June, 2010 at 3:17 am

Thomas Bloom

Some more typos:
p. 131, the second \Gamma in the second paragraph of the proof should be \Gamma’

p. 134, first line, ‘with’ should be ‘within’

p. 135, in the definition of \lambda_j, k should be j.

p. 196, the second line after the proof finishes is missing a closing bracket after \delta

p. 388, last line, \sigma N/4 should be \sigma/4

p. 391, in the statement of Lemma 10.29, [1,n] should be [1,N]

p. 397, in Exercise 10.4.2, Lemma 10.15 should be Lemma 10.29

[Corrected, thanks - T.]

30 June, 2010 at 1:50 pm

Yiannis

hi,

i have a simple question — is there a corresponding development of sumset and inverse sumset theorems (or at least partial results) for continuous subsets of the real line or, more generally, for infinite subsets of arbitrary (abelian, locally compact) additive groups, with respect to Haar measure instead of set cardinality? it seems that some of the basic sumset bounds generalize very easily (at least to the case of the real line) but some other results don’t. (in fact, even some of the simplest bounds fail in this case.)

i understand this has probably been discussed at length somewhere, so i apologize in advance for my ignorance!

thanks!

yiannis

1 July, 2010 at 8:41 am

Terence Tao

Dear Yiannis,

I discuss this in my paper http://front.math.ucdavis.edu/math.CO/0601431 , particularly the last section.

1 July, 2010 at 10:00 am

Yiannis

hi — got it, thanks!
yiannis

9 November, 2010 at 7:27 pm

Fernando

Dear Prof Tao,

In the proof of Theorem 1.39 about B_h[g] set, it says in the end that one can establish E(partial derivative of Y_m)=O(m^{-1/h}). But let’s say h=2, and so

Y_m=t_1*t_{m-1}+t_2*t_{m-2}+…

So the partial derivative of Y_m with respect to t_{m-1} is just t_1, but E(t_1) is a constant, and is not bounded by m^{-1/h} for large m. Is there something wrong with this argument or did I misunderstand the statement?

Thanks,
Fernando

17 November, 2010 at 10:33 am

Terence Tao

Yes, this is a moderately serious issue. It can be fixed by a “splitting” argument, in which one first only considers representations in which all terms have size at least $n^\varepsilon$ (say). The remaining terms can be handled by an induction hypothesis, noting from the Borel-Cantelli lemma that we can assume that there is a uniform bound on the number of elements of A in any interval of the form $[n, n+n^\varepsilon]$ if $\varepsilon$ is small enough. I’ll add some details of the fix as an erratum.

10 November, 2010 at 3:42 am

Olof Sisask

Hiya, some small typos:

p. 388: There should not be absolute value signs in the conclusion (density increment vs density decrement), and the bound should probably be delta/8 rather than delta/4 from the proof given: in getting the last displayed inequality on the page one presumably divides by 2N for the pigeonholing and then by 2 for the Re(1+e(…)) term. This change propagates to changing the 4 to an 8 in the first display on p. 389.

[Corrected, thanks - T.]
Thanks.

18 November, 2010 at 4:26 am

Olof Sisask

Hiya, I think there might be an issue with the bounds in Theorem 4.47 on p. 194: perhaps the length of the arithmetic progression ought to be $\exp(c (\delta^2 \log N)^{1/3})$ (with a $\delta^2$ rather than $\delta$ ) and the lower bound on $\delta$ ought perhaps to be the square root of what it currently is. It seems that this is needed in getting the bound in the first display on p. 196, given that |S| is of the order $(log J)^2/\delta^2$ . If correct, this change needs to propagate to the third and penultimate lines of the proof of Theorem 4.47, the discussion afterwards, and to the second line of p. 197.

[Added, thanks. I checked the original reference of Bourgain, and of course he writes the exponents correctly; I can't remember how the error slipped in initially. - T.]
Thanks.

1 December, 2010 at 2:11 am

I think there’s still some problem with Exercise 1.3.1. Take for instance $\lambda=n-1$ for some even $n$. Since $n$ is even, the only way the sum can be $>=\lambda$ is if the sum equals $n$.

1 December, 2010 at 10:42 am

Terence Tao

I think it’s fine in this case; both sides are equal to $2^{1-n}$ . (The left-hand event occurs if and only the first $n-1$ signs $\varepsilon_1,\ldots,\varepsilon_{n-1}$ are equal to $+1$ .)

7 December, 2010 at 10:15 am

Heiko

Hello,
i was wondering if the case k=1=m should be ruled out, because we could choose B=N and that would be a perfectly regular basis of order 1 (although a rather boring one).

Corrected, thanks – T.]

7 December, 2010 at 10:18 am

Heiko

In Exercise 1.3.10, i meant. Sorry

6 January, 2011 at 10:53 am

Máté Wierdl

Terry, on page 17, Exercise 1.3.4, in the estimate the negative sign is missing from the second exponential in front of lambda.

[Corrected, thanks - T.]

1 February, 2011 at 11:53 am

Anonymous

Equation (2.7): I believe min(|A||B|) should read min(|A|,|B|) (this is in the softcover edition… I couldn’t find an errata page for that edition) [Corrected, thanks - T.]

7 February, 2011 at 9:35 am

Polymath6: thoughts on empirically testing the finite-field heuristic for very low ‘n’ « Paul Delhanty

[...] context is relatively undemanding. For example, consider the concept of a Bohr set. (See also Tao & Vu’s Additive Combinatorics – 4.4 Bohr Sets.) In the context of the cap-set problem, Bohr sets are just subspaces, so [...]

13 February, 2011 at 8:10 am

Erik Aas

On p.271, not only should G_1 o … o G_k be changed to G_k o … o G_1, but also

||G_1 o … o G_k|| _ {1/k} to ||G_k o … o G_1|| ^{1/k},

I think.

[Corrected, thanks -T.]

13 February, 2011 at 8:24 am

Thomas Bloom

p. 391: in the statement of Lemma 10.29, the $\Omega(\sigma N^{1/(\lvert S\rvert+1})$ should be $\Omega(N^{1/\lvert S\rvert+1})$, and the final bound of $\Omega(\sigma)$ should be $\Omega(\sigma\delta^{-1})$, where $\delta=\mathbb{E}f$, otherwise one can’t get the Heath-Brown/Szemeredi bound. Also in the proof, the L^1 norm of f should be bounded by $2\delta$ rather than $1$ to enable this improved statement.

[Corrected, thanks -T.]

Also, on pages 390, 391, 388, 133, should the references to the Kronecker approximation theorem be instead to a multidimensional Dirichlet approximation theorem, this being the name usually used for this kind of result? (Kronecker applying to linearly independent sets).

[Hmm, tough call. There does not appear to be prior literature referring to a multidimensional Dirichlet approximation theorem. You are right that the Kronecker approximation theorem, as stated in the literature, is slightly different (although it does imply the qualitative version, at least, of the result used here). On balance, though, I guess the former term is more appropriate. - T.]

17 June, 2011 at 11:13 pm

Christian Elsholtz

>>There does not appear to be prior literature referring to a multidimensional Dirichlet approximation theorem. <<

"Simultaneous approximation" (rather than multidimensional approximation) is a standard term, so that I suggest "simultaneous Dirichlet approximation".

[Adjusted, thanks - T.]

9 June, 2011 at 11:38 pm

Smooth geometry vs (nonsmooth calculus and combinatorics) | chorasimilarity

[...] Additive combinatorics, see this book by Terence Tao, Van Vu. [...]

15 June, 2011 at 5:44 am

DavidJCovert@gmail.com

One small typo: at the bottom of page 316 (in the first edition), $C|A+A|^{8/3}/|A|^{18/3}$ should be $C|A+A|^{8/3}/|A|^{8/3}$.

[Added, thanks - T.]

19 July, 2011 at 1:00 am

tomer

at p.162, the last line should be <= |F| (rather than = |F|)

[Sorry, I was unable to locate this issue in either the paperback or hardback versions. - T.]

26 July, 2011 at 4:39 am

Anonymous

at Lemma 4.14 (Gauss sum estimate), the last line of the proof
it should be <= |F| (rather than = |F|)

26 July, 2011 at 4:47 am

Anonymous

sorry for the trouble – my mistake

28 July, 2011 at 11:19 pm

tomer shalev

Page 191, the third line in the computation segment (of |f(x) – f(0)|), the L-2 norms due to cauchy-schwarz should be l-2 norm (with small L) ?

[Corrected, thanks - T.]

30 July, 2011 at 7:03 am

tomer shalev

another error: page 63, the sixth line in the computation ( of E(A,B) ),
a’ – b should be omitted and instead should be y variable.

[Corrected, thanks - T.]

8 August, 2011 at 11:36 am

David Covert

Very minor typo in revised addition (Additive_sample.pdf), page 87, Lemma 2.13: One instance of $X_{+}$ should be $X_{-}$.

[Thanks! Actually this was already corrected in the published version - T.]

25 August, 2011 at 9:15 am

The Collatz conjecture, Littlewood-Offord theory, and powers of 2 and 3 « What’s new

[...] by a standard Fourier-analytic computation involving Riesz products (see Chapter 7 of my book with Van Vu, or this recent preprint of Maples). Using this Fourier representation, the fact that this [...]

27 August, 2011 at 11:35 am

254A, Notes 0 – Hilbert’s fifth problem and related topics « What’s new

[...] of additive or multiplicative structure are “essentially” equivalent; see Chapter 2 of my book with Van Vu (or this paper of mine in the non-commutative case) for more [...]

12 November, 2011 at 7:18 am

Tomer Shalev

page 16, theorem 1.16. last line of the page regarding the inequality of the expectation of the representing function.. should 8(logn) be 32(logn)?
otherwise I can’t get the O(1/n^2) that should follow from corollary 1.9.

another point: it is said in the theorem that corollary 1.10 is applicable as well, but then you have the set P of primes which is infinte and a finite random set B then one can’t use corollary 1.10 due to the infiniteness of P.
I will be happy to figure out where i did not follow or understand.

page 181, lemma 4.35 (cube covering lemma): it should be noted in the theorem that the union of D_1,…., D_k may be empty as well.
the reading of the theorem made me believe at first that these sets exist with the fixed (d + 1) cardinality, which is of course not the case when one reads the proof.

[These errata have been added, thanks - T.]

1 December, 2011 at 11:35 pm

Tomer Shalev

page 81, Lemma 2.30 . I believe that the definition of S should be
with a power of 2 in the left hand side
i.e S:= {x\in A+B… |A \cap (x- B)|^2 >= …}
otherwise I can’t follow the deduction of the inequality computation in the third line. If so true, then all of the proof should be adjusted and rewritten from there on, possibly changing the theorem slightly.

4 December, 2011 at 5:06 pm

Terence Tao

Actually, I think the definition of S is correct as it stands. The point is that one should only estimate one of the two factors of $|A\cap(x-B)|$ , thus

$\sum_{x \not \in S} |A \cap (x-B)|^2 \leq (|A|^{1/2} |B|^{1/2}/2K) \sum_x |A \cap (x-B)| \leq |A|^{3/2} |B|^{3/2}/2K$ .

4 December, 2011 at 10:19 pm

Tomer Shalev

ofcourse, thanks for making this point clearer

6 December, 2011 at 4:26 am

Win-Vector Blog » What to do when you run out of memory

[...] Historically computer scientists have concentrated on streaming or online algorithms (that is algorithms that work with the data in the order it is available and use limited memory). For many problems we have found this an insufficient model and it is much better to assume you can re-order and replicate data (such as scattering data to many processors and re-collecting it to sort). The scatter/gather paradigm is ubiquitous and is the underpinning of large scale sorting, databases and Map Reduce. So in one sense databases and Map Reduce different APIs on top of very related technologies (journaling, splitting and merging). Replicating data (or even delaying duplicate elimination) that is already “too large to handle” may seem counterintuitive; but it is exploiting the primary property of secondary storage: that secondary storage tends to be much larger than primary storage (typically by 2 orders of magnitude, compare a 2 terabyte drive to an 8 gigabyte memory stick).In our web age, the typical big data problems are inverting indices (for fast search lookup) and computing term frequencies (for TF/IDF scoring or for things like Naive Bayes classifiers). Since these are over-worked examples we will use a mathematical problem from “Additive Combinatorics”, Terence Tao, Van Vu, (ISBN-13: 9780521853866; ISBN-10: 0521853… [...]

22 December, 2011 at 9:21 am

Xi Wu

Hi,

For Q 4.1.7, I think \E_{H^{\perp}} is correct, you need this to give a factor |H^{\perp}| and then apply (4.6), i.e. |Z| = |H||H^{\perp}|.

For Q 4.1.8. in the last line of the furthermore part, I think ” f((\phi^{\dag})^{-1}(x)) ” should be ” \hat(f)((\phi^{\dag})^{-1}(x)) ”

[Added, thanks - T.]

12 March, 2012 at 11:33 pm

Tomer Shalev

Hi Prof. Tao.

can you please elaborate more on the solution
of exercise 2.4.10 in page 78. the hint in the exercise unfortunately
didn’t make any sense to me

12 March, 2012 at 11:35 pm

Tomer Shalev

it’s just that approximate groups work well for doubled sets.

13 March, 2012 at 11:50 am

Terence Tao

Dear Tomer,

After placing A in a translate x+H of an approximate group, and B in a translate y+K of another approximate group, it is easy to see that H+K is also an approximate group. The main difficulty is to show that A+B is a large subset of x+H+y+K, which is where the hint comes in.

13 March, 2012 at 11:18 pm

Tomer Shalev

Hi Prof Tao.

this was my strategy before I wrote here. but I am
still missing something.
This is what it looks like:

essentialy H = A-A, K = B-B . H + K = A – A + B -B
A+B is not a large subset of H+K at first impression, unless H+K has
a small doubling.
i can get the following:
|A+B| >= |H+K| / ( (K_1)^5 * (K_2)^5 * |A-A()B-B| )

My problem is ofcourse showing that |A-A()B-B| is comparable to
the doubling constant of A and B.

BTW, all of my playing around with the representing function, Approximate groups and the doubling constant makes me believe that the
doubling constant is not the most natural measure. No one ever justified
the doubling constant in terms of covering A-A with O(K) translates of A,
where K is the doubling constant. it actually happens when A is a sidon set or arithmatic progression of dimension 1. while this seems nowhere justifiable, strange properties seem to happen like sub multiplicitivity under sum set operation.
It is easy to see that another measuring can strengthen the doubling measure. for example: suppose the doubling constant was the cardinality
of the maximal sub collection of {-A + a : a \in A} obeying the property
{-A + a()-A + b} = {0}, in special cases like sidon and arithmatic progression these measure is equivilent to the doublng constant.

14 March, 2012 at 7:45 am

Terence Tao

Here is a sketch of proof. To simplify the notation let us suppress the dependence on K_1, K_2. We place A in a coset x+H of an approximate group, and B in a coset y+K of another approximate group, with $|A| \gg |H|$ and $|B| \gg |K|$ . Since H and K are approximate groups, H+K is also. (indeed, if 2H can be covered by a bounded number of translates of H, and 2K can be covered by a bounded number of translates of K, then 2(H+K)=2H+2K can be covered by a bounded number of translates of H+K). So

$|(A+B)+(A+B)| \leq |(H+K)+(H+K)| \ll |H+K|.$

To finish the job we need to show that

$|A+B| \gg |H+K|.$

From the inequality in the hint one has

$|A+B| \geq |A| |B| / |(A-A) \cap (B-B)|$

$\gg |H| |K| / |(H-H) \cap (K-K)|$ .

On the other hand, from the Ruzsa triangle inequality one has

$|H+K| \leq |H+((H-H) \cap (K-K))| \times$
$\times |((H-H) \cap (K-K))+K| / |(H-H) \cap (K-K)|$

$\ll |H| |K| / |(H-H) \cap (K-K)|$

and the claim follows.

I agree with you that the doubling constant is not the most tractable quantity to measure additive structure; its presence in the subject is primarily for historical reasons. Fortunately, the basic additive combinatorics theory allows one to efficiently convert control of doubling constants to more useful control, such as control of the approximate group parameter.

14 March, 2012 at 9:48 am

Tomer Shalev

Thanks prof. Tao
I believe that the last computation should be:
since $H + H \subseteq H + X_1$ and
$K + K \subseteq K+ X_2$ where
$|X_1|, |X_2| \ll 1$

then by Ruzsa:
$|H+K| \leq |H+(H + X_1\cap K+ X_2)| |(H + X_1\cap K+ X_2)+K| /$ $|H + X_1\cap K+ X_2|$
$\leq |H + H + X_1| |K + K + X_2| / |(H-H) \cap (K-K)|$
$\leq |H + X_1 + X_1| |K + X_2 +X_2| / |(H-H) \cap (K-K)|$
$\leq |H| |X_1|^2 |K| |X_2|^2 / |(H-H) \cap (K-K)|$
$\ll |H| |K| / |(H-H) \cap (K-K)|$

My problem was justifying :
$1 / |H \cap K| \ll 1 / |(H-H) \cap (K-K)$

14 March, 2012 at 9:52 am

Tomer Shalev

latex cut the first line after “ruzsa”. if you hit the reply button you will see the rest. I now see that you corrected the first sketch with which I had problems at the end.
thank you

14 March, 2012 at 2:56 am

Vorlesung Kombinatorische Zahlentheorie » notebook

[...] – Terence Tao and Van Vu, Additive Combinatorics, Cambridge 2006. University Press; see also http://terrytao.wordpress.com/books/additive-combinatorics/ – Alfred Geroldinger and Imre Ruzsa, Combinatorial number theory and additive group theory, [...]

22 May, 2012 at 3:08 am

Anonymous

Hi Prof. Tao,

Reporting a typo in the old edition of the book, in p. 116 in the proof of Corollary 3.6. (1) In line no. 9 of the proof, $w \in \mathbf Z^d$ should be $\mathbf Z^n$. (2) The symbol “n” in two different ways, leading to some curious phrases like $n \in \mathbf Z^n$; e.g., see line no. 3 of the proof. In case it helps, I checked the previous pages, and found that you had avoided using “n” for the dimension prior to this paragraph.

Also, I would like a clarification reg. the proof of Corollary 3.9. In the very first line, you define the torsion subgroup of G, and invoke Corollary 3.8 for this subgroup to conclude that it is a direct sum of finite cyclic groups. But then, should one not first prove that the torsion subgroup is finite? This would of course follow if one shows that (a) any subgroup of a f.g. abelian group is f.g., and (b) if a f.g. abelian group is also a torsion group, then it is finite. I browsed through the earlier theorems to see whether either of these statements have been proved/mentioned, but I did not find anything relevant. Am I missing something here? Thank you.

26 May, 2012 at 4:15 pm

Terence Tao

Thanks for the corrections!

Regarding the facts that (a) any subgroup of a f.g. abelian group is f.g., and (b) any f.g. torsion abelian group is finite, claim (a) follows for lattices from Lemma 3.4, and then for arbitrary f.g. groups by viewing such groups as homomorphic images of lattices. For (b), observe that each generator of a f.g. torsion group has finite order, and so there are only finitely any distinct additive combinations of such generators.

27 May, 2012 at 9:29 pm

Srivatsan

Hi, I was the one who posted the previous post. Thank you for your clarification.

I fished out a couple more typos, again in the old edition. (1.) p. 121: In the paragraph following Lemma 3.11, the notation $|A|$ in “exponentially in $|A|$ ” is not defined. It should probably be $K$ . (2.) p. 141: The proof of Lemma 3.36 (Discrete John’s theorem) uses $L$ for the dimension of the progression, which the statement of the theorem denotes by $N$ . This is of course not really a bug, but there does not seem to be any need for the switch either.

Note: The blog post says that it was last updated on May 26, but the errata is not updated. Is this some issue with wordpress?

[Corrections added, thanks - T.]

21 August, 2012 at 11:24 am

self study

revised edition, page 18, exercise 1.3.6: in equation 1.24, can:

$\leq e^{-\lambda^2/4}$ actually be tightened to $\leq e^{-\lambda^2/2}$ via a straight forward application of http://en.wikipedia.org/wiki/Azuma_inequality with $c_i = 2$ ??

27 August, 2012 at 2:25 pm

self study

Page 23, Equation 1.30

Is the “v” in $$\prod_{v \in V} )1-P(A_i))$$ supposed to be an “i”, i.e. $$\prod_{i in V}) (1- P(A_i))$$ ?

Thanks!

[Yes, this has been added to the errata now, thanks - T.]

10 September, 2012 at 3:20 pm

Page 42, Exercise 1.8.1:

Should $$A \in Z^+$$ be $$A \subseteq Z^+$$ ?

10 September, 2012 at 9:37 pm

Terence Tao

Thanks for the correction! Actually, there is a more serious issue with Ex 1.8.1, which is that the two elements of B should be distinct (i.e. 2B should be $2^* B$ ).

10 September, 2012 at 3:21 pm

(If the above is true, can you also provide a hint for this problem? :-) )

10 September, 2012 at 3:34 pm

Err, sorry about spamming your blog, no hint required. Just solved 1.8.1

11 September, 2012 at 12:04 pm

So it turns out my proof from yesterday doesn’t quite work.

(1)

The first thing I tried is P(x \in B) = \frac{\log n}{n}, but this breaks down when we have:

A = (N + [1, ..., k]) \cup (2N + [1, ..., k]) \cup (3N + [1, .., 2k]).

(2)

From that, the intuition is “okay, so maybe I need to somehow bias things toward the larger elements.” Divide the numbers into segments of [1,2), [2, 4), [4,8), ... . Then look at the largest non empty segment. If there are $\log n$ elements, we're done (since the sum of two elements within a segment can't be in the segment.)

So, if the # of the lements in the segments are s_0, s_1, ..., s_m [where s_0 is the largest non-empty segment], we end up getting some equation of the form:

force \sum_i s_{i-1}/s_i * (k_i/s_i)^2 < 1

when \sum_i k_i = \log n

Unfortunately, the case where all the s_i = 1 breaks the above (since the first sum ends up being \log n rather than 1).

I was wondering if you could provide some intuition on how to pick b.

Thanks!

11 September, 2012 at 7:20 pm

Terence Tao

Hmm, now that I look more closely, it seems that this exercise is misplaced; it is basically a duplicate of Theorem 6.2. I am not sure why it ended up in Section 1.8; it is not particularly easy to prove using the methods from that section…

11 September, 2012 at 11:31 pm

I was going to stop reading the book after chapter4, but now it looks like I’ll have to get through section 6.2 at the least. :-)

9 October, 2012 at 7:35 am

ablmff

In 2.3.23, we are asked to give an example with certain properties, but do we need to give an example which works for all possible N, or can we choose a particular N?

9 October, 2012 at 6:53 pm

Terence Tao

One should be able to construct an example for all sufficiently large N (of course, the claim is trivial for very small N, e.g. N=1).

14 October, 2012 at 12:58 pm

ablmff

I think there might be a bit ambiguity in exercise 2.5.7. It says:

G \subset A \times A is such that every element of A is connected via G to at least K^{-1}|A| elements of |A|.

Here, does the A in “every element of A” refer to the first A in “A \times A”, or to both of them?

[To both; I'll add an erratum to clarify this. -T]

5 November, 2012 at 6:06 am

ablmff

I think in Ex 4.3.2, \|T^h A\| should be \|h A\|.

5 November, 2012 at 6:07 am

ablmff

Sorry, should be \|h + A\|

[Erratum added, thanks - T.]

14 November, 2012 at 4:45 pm

Yogesh Anbalagan

p. 315 In the proof of theorem 8.14 … the points (b+c, ac) with C ___ … C should be element of A ? Is that a typo?

[Yes; see the errata list for the revised edition. -T.]

18 December, 2012 at 2:59 am

Rafael Tesoro Carretero

I found the erratas list very useful, thanks for this!

It seems to me another minor one may be the following. In the middle of page 264 there should be E instead of G, and the first pair should be (a,b) instead of (a’,b’):

|\{ (a,b) \in A \times B : (a,b’),(a’,b’),(a’,b) \in E \}| \ge \frac{|A||B|}{2^{12}K^5}.

[Corrected, thanks - T.]

1 February, 2013 at 10:19 am

Small doubling in groups « What’s new

[...] much detail the proof techniques used in these results (although the abelian case is discussed in this book of mine with Vu, and the nonabelian case discussed in this more recent book of mine), but instead focuses on the [...]

16 March, 2013 at 5:28 pm

Jarek Kuben

In the proof of Theorem 9.2, page 331, 15th line, should be t_{n-1}^{d_{n-1}} instead of t_{n-1}^{d_{n}-1}.

[Added, thanks - T.]

	Luqing Ye on Analysis II
	Kailyn on About
	BWW on Analysis II
	Terence Tao on Multiple recurrence and conver…
	Joel Moreira on Multiple recurrence and conver…
	mathtuition88 on Does one have to be a genius t…
	The Beauty of Bounde… on Simons Lecture I: Structure an…
	The Beauty of Bounde… on Marker lecture III: “Sma…
	Luqing Ye on 245A, Notes 2: The Lebesgue…
	Anonymous on Notes on the classification of…
	Luqing Ye on 245A, Notes 2: The Lebesgue…
	Luqing Ye on 245A, Notes 2: The Lebesgue…
	Luqing Ye on 245A, Notes 2: The Lebesgue…
	Luqing Ye on 245A, Notes 2: The Lebesgue…
	Luqing Ye on 245A, Notes 2: The Lebesgue…

Additive combinatorics

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

Google+ feed

Tags

The Polymath Blog

Mathematics in Australia

154 comments

Leave a Reply Cancel reply

For commenters

Follow “What's new”

Additive combinatorics

Share this:

Like this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

Google+ feed

Tags

The Polymath Blog

Mathematics in Australia

154 comments

Leave a Reply Cancel reply

For commenters

Follow “What's new”