Additive combinatorics

Last updated: Feb 24, 2024

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.

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 $16$ (not $\kappa/16$ as stated previously).
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$ . In the next paragraph, the inclusion $\supseteq$ should be $\subseteq$ , and the constraint $1 > \lambda > 0$ may be relaxed to $1 > \lambda \geq 0$ .
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.
Page 132: In the statement of Lemma 3.24, one needs to add the hypothesis that all the sums in $\Gamma+P$ are distinct.
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). [Update: this is slightly inaccurate, see revised erratum below.]
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. In Exercise 7.1.1, Lemma 7.3 should be Lemma 7.2.
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|} )$ . In Exercise 8.3.4, $|A|^{1/2} |B|^{1/2} |C|^{3/2}$ should be $|A|^{1/2} |B|^{3/2} |C|^{1/2}$ . In Exercise 8.3.5, $\Theta(|A|^{5/2})$ should be $\Omega(|A|^{5/2})$ .
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.6. In Exercises 1.1.6, 1.1.7, $[0,1]^d$ should be $\{0,1\}^d$ .
p. 7: in the display after (1.10), add an additional right parenthesis before the equality sign.
p. 12. In Example 1.12, “Legendre’s theorem” should be “Lagrange’s theorem”.
p. 15. In the final display, $\kappa/2$ (or $\kappa/16$ ) should be $16$ (this supersedes the previous erratum for this line).
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}}$ . Also add “The variance of a complex variable $X$ is defined to be ${\bf E}(|X|^2) - |{\bf E} X|^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. 26: In the penultimate paragraph, $x \in S'$ should be $x+S'$ .
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. 48: in the first bound of Exercise 1.10.3, the error term of $O(n^{1/2})$ should be $O(\log n)$ .
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.)
Page 61. In the penultimate bullet point of Proposition 2.7, add the requirement $n+m \geq 1$ . After Proposition 2.7, “ $0$ , $0$ , or $1$ respectively” should be “ $0$ , $1$ , or $1$ respectively”.
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. 66: In Exercise 2.3.2, $\frac{1}{2} \log 2$ should be $\log 2$ . In Exercise 2.3.7, replace the first bound with $\sigma[A \cup B] \leq O( \exp^{4d(A,B)})$ and the second bound with $d(A,B) \leq O( \log \sigma[A \cup B] + \log \frac{|A \cup B|}{|A|} + \log \frac{|A \cup B|}{|B|}$ .
p. 70: In the statement of Ruzsa’s covering lemma, insert “at most” after “In particular, $B$ can be covered by”.
p. 71: In the proof of the Green-Ruzsa covering lemma, “the size of $|X+A|$ ” should be “the size $|X+A|$ of $X+A$ “.
p. 73: In Corollary 2.22, replace “covered by $\delta[A]^5$ ” with “covered by at most $\delta^5$ “. Similarly in the proof of the corollary.
p. 74: In Corollary 2.23, add the hypothesis $n_1+n_2, n_3+n_4 > 0$ , and replace the exponent $10$ by $20$ .
p. 76: In Exercise 2.4.5, $\binom{K+n-1}{n}$ can be improved to $\binom{K+n-2}{n-1}$ . In the final inequality in Exercise 2.4.8, the quantities $d(G_1,G_2)$ and $d(G_1+G_3,G_2+G_3)$ should be swapped.
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. 88: In the definition of $\tilde O, \tilde \Omega$ , $\log L$ should be $(1+\log L)$ .
p. ???: Exercise 2.6.6 is false as stated; the conclusion needs to be weakened, in that the indicated translates of $H$ only cover $1-\varepsilon$ of $A$ rather than all of $A$ . Furthermore, the proof requires Exercise 6.5.1. Hence this exercise should be moved to Section 6.5, with a hint to use Exercise 6.5.1 and the Ruzsa covering lemma (Theorem 2.35 is not directly required, though the strategy of proof can still be useful).
p. 100: In Corollary 2.52, A should be assumed to be a finite subset, rather than a finite subfield.
p. 104: the last paragraph here (from “Now let $x$ …” onwards) can be deleted, and replaced by the much shorter “Since $G= Q[A']$ and $A'$ contains both 0 and 1, we have $A' \subset G$ “.
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. 128: 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. 131: In the second paragraph of the proof of Lemma 3.21, “translates of $\Gamma$ ” should be “translates of $\Gamma'$ “.
p. 132: In Lemma 3.23, the hypothesis that the cosets $p+\Gamma$ for $p \in P$ are disjoint should be added.
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. 136, in the first line, “directional basis for A” should be “directional basis for B”.
p. 142: In the proof of Lemma 3.36, $L$ and $L_j$ should be $N$ and $N_j$ respectively (for consistency).
p. 143?: Exercise 3.5.3 is false. In its place, one can put the following example (from this reference): Let $A$ be the convex hull of the four points $(N,0,0), (-N,0,0), (0,N,1), (0,-N,1)$ for a natural number $N$ . Show that $(A \cap {\bf Z}^3)$ has cardinality $4N+2$ , but $2(A \cap {\bf Z}^3)$ has cardinality at least $(N+1)^2$ . Thus one cannot remove the symmetry hypotheses from Lemma 3.21.
p. 154: In display (4.9) there is a full stop missing.
p. 155: In Exercise 4.1.5, “pairwise independent” should be “pairwise uncorrelated”. 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))$ . In Exercise 4.1.4, “for all $c$ ” should be “for all $x$ “.
p. 156: In the second display (defining $\|f\|_{L^\infty(Z)}$ ), $=$ should be $:=$ .
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. 162: In the last line, “sum of two elements” should be “sum of two squares”.
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$ . In the discussion of Lemma 4.16,the term $\tau Z$ in the approximation for $\|B\|_u$ after the display should be deleted. In the statement of Lemma 4.16, $e^{-\lambda \sigma/2\sqrt{2}}$ should be $e^{-\lambda \sigma |Z|/2\sqrt{2}}$ .
p. 165: In Exercise 4.3.15, the transformation $M$ needs to be assumed to be symmetric.
p. 166: In Lemma 4.20, the additional hypothesis $\rho \leq 1$ should be added.
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. 179: In Exercise 4.5.8, $|Z|^{1/h}$ should be $O(h |Z|^{1/h})$ . In Exercise 4.5.7, $\min$ should be $\max$ .
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$ “. “all dissociated subsets of $S$ ” should be “all dissociated subsets of $R$ “.
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. 201: In the second-t0-last displayed equation, $A_{(0)} + H \backslash A_{(0)}$ should be $(A_{(0)} + H) \backslash A_{(0)}$ .
p. 208: The sixth line of the long display should be $|A| + 3 |\phi_h(A)| |H| - (|H|-2) |\phi_h(A)| - |\phi_h(A)| - 2|H| + 2(|H|-2) - 2k + 1$ (here we use $|\phi_h(A)| \geq 2$ ). The seventh line should be $|A| + 2 |\phi_h(A)| |H| + |\phi_h(A)| - 2k - 3$ . The eighth line should be $|A| + 2 (|A|+k-1) + |\phi_h(A)| - 2k - 3$ . The final line remains as $3|A|-3$ (here we again use $|\phi_h(A)| \geq 2$ ).
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. In exercise 5.3.2, $\{0,1,n\}$ should be $\{0,1,n+2\}$ .
p. 236: In the proof of Proposition 5.41, all occurrences of ${\bf R}$ should be ${\bf Z}$ .
p. 239: The example in Exercise 5.5.17 is incorrect; the set $A$ should be $\{ 2e_i, e_i + e_{i+1}: i=1,\dots,5\}$ in ${\bf Z}^5$ , where $e_1,\dots,e_5$ is the standard basis and one adopts the convention $e_6 =1$ ; “quadrilateral” should be “pentagon” and ${\bf Z}^4$ and ${\bf Z}^2$ should be replaced by ${\bf Z}^5$ throughout.
p. 241: In the last line of the first display in the proof of Lemma 5.45, $(|X|+2n-2)|X|$ should be $(|X|+2n-2)^{|X|}$ .
p. 242: Before (5.19), a right parenthesis should be inserted after $\mathrm{Tor}(Z)$.
p. 248: In the proof of Theorem 6.1, “probablistic” should be “probabilistic”.
p. 249: In the second paragraph of the proof of Theorem 6.2, all occurrences of $n-i$ should be $i-1$ .
p. 254: In exercise 6.2.8, the adjective “triangle-free” should be deleted. In Exercise 6.2.3, the final period should be inside the parenthesis.
p. 260: In Exercise 6.3.5, $B+B$ should be replaced with $B \hat + B$ , with the note “where $B \hat + B := \{ b_1+b_2: b_1,b_2 \in B, b_1 \neq b_2\}$ is the restricted sumset of $B$ with itself” added.
p. 263: In the final display, the right parenthesis after $(a,b) \in E$ should be deleted. Similarly for the first display on page 264.
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. 272: The definition of $C_i^\pm$ needs to be moved from page 273 to just before Lemma 6.34.
p. 273: In Exercise 6.4.2, “Claim 6.31 and Claim 6.4” should be “equations (6.3) and (6.4)”.
p. 279: In Proposition 7.7, $\lfloor (|X|+i)/2\rfloor$ should be $\lfloor |X|/2\rfloor + i$ .
p. 281: In the last paragraph, “ $Z$ is odd” should be “ $|Z|$ is odd”.
p. 285: Corollary 5.25 should be Lemma 5.25.
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. 293: $v_1,\dots,v_n$ should be elements of $P$ rather than $V$ . In Example 7.19, “which have volume” should be “which has volume”.
p. 294: After the first proof of (7.20), “lower dimension its” should be “lower its dimension”.
p. 299: In the first display, $3 \log_ 2 n$ should be $3n/\log_2 n$ .
p. ???: In Section 7.7 and in reference [101], the accent in Esseen should be dropped.
p. 313: In Theorem 8.10, “at most $\beta$ lines” should be “at most $\beta$ curves”.
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. 358: In the second display of the proof of Lemma 9.43, $s^{|G|}-4$ should be $s^{|G|}-r$ .
p. 363: in the last paragraph “the finite field $F_p$ ” should be “the ring $F_p[z]$ of formal polynomials with coefficients in the finite field $F_p$ “.
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. 371: In Exercise 10.0.3, add “The upper density of a subset $A$ of the integers is defined as $\lim\sup_{N \to \infty} \frac{|A \cap \{-N,\dots,N\}|}{2N+1}$ .”.
p. 372: In Exercise 10.0.8, add the hypothesis that no non-zero element of the groups containing $A$ or $B$ has order less than $k$ .
p. 386: In the first display, $\alpha = o( |Z|^{-1/10})$ should be $\alpha \geq |Z|^{-1/10}$ .
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. 394: in the second display, $1_{\mathrm{Bohr}(S,\rho-\rho_1)}(r)$ should be $1_{\mathrm{Bohr}(S,\rho-\rho_1)}(x)$ .
p. 396: In each of the two displays after “From (10.16), we have”, there is an extra right parenthesis on the right-hand side that should be deleted.
p. 397: In Exercise 10.4.2, Lemma 10.15 should be Lemma 10.29.
p. 402: In (10.21), $\in a+bi+\alpha \in B$ should be $- a-bi-\alpha \in B)$ , and similarly in the folowing display.
Page ???: In the statement of Theorem 10.31, the bound for $\Lambda(f,f,f)$ should be $\Omega({\bf E}_Z(f)^{O({\bf E}_Z(f)^{-2})})$ rather than $\Omega({\bf E}_Z(f)^{-O({\bf E}_Z(f)^{2})})$ .
p. 405: In Exercise 10.5.1, $K^2$ should be $O_{K,\sigma}(1)$ .
p. 412: In the second case of Corollary 10.50 the word ‘and’ should be inserted.
p. 413: In Exercise 10.7.2, $O(k)$ should be $O(k+r)$ . In the second display, $O( \frac{N}{d} )$ should similarly be $O( \frac{N}{d} + v_i )$ (which is permissible since $\sum_{i=1}^d v_i = O(N)$ ).
p. 414: In the first paragraph, “motivation” should be “motivations”.
p. 430: In the last line, a right parenthesis is missing after $\exp(O(\eta^{-O(1)})$.
p. 435: In the penultimate display, $V_2$ should be $V_1$ .
p. 436: In the equation before (11.21), ${\bf b}(y)$ should be ${\bf b}(x+y+h)$ , and the right brace should be deleted.
p. 437: In the definition of $W$ , $h \in W_1$ should be $x \in W_1$ .
p. 439. In proposition 11.12, In the last line, a right parenthesis is missing after $\exp(O(\eta_k^{-O_k(1)})$.
P. 449: In the sixth line from the bottom, “positive upper progressions” should be “positive upper density”. In the first display in the proof of Theorem 11.23, $((c_j))_{j=1}^\infty$ should be $((c_j)_{j=1}^\infty)$ .
p. 450: In the last line of the proof, “non-zero $B$ ” should be “non-zero $n$ “.
p. 452: In Theorem 11.25, ${\bf Z}^d$ should be ${\bf Z}$ .
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, Ryan Alweiss, Andrea, Louigi Addario-Berry, Khodakhast Bibak, Thomas Bloom, Lin Bo, Richard Brent, Walter Bridges, Adam Brown, Tom Brown, Andres Caicedo, Rafael Tesoro Carretero, Kestutis Cesnavicius, Mei-Chu Chang, Sheng-Fu Chiu, David Colvert, Paul Delhanty, RFZ, Mikhail Gabdullin, Moubariz Garaev, Stephen Ge, Marcel Goh, Paul Hagelstein, Le Thai Hoang, Zach Hunter, Ce Jin, Tom Koornwinder, Jarek Kuben, Nitish Kumar, Pham Lam, Choongbum Lee, Mark Lewko, Victor Lie, Chao-Ming Lin, Yang Liu, Isabel Lugo, Freddie Manners, Heiko Mattern, Vicky Neale, Danny Nguyen, Lam Pham, Gyan Prakash, Firdavs Rakhmonov, Aditya Guha Roy, Juanjo Rué, Sean, Mark Sellke, Tomer Shalev, Olof Sisask, Justin W. Smith, Sai Teja Somu, Srivastan, Thomas, Matthew Tointon, Sam van Gool, Marco Vitturi, and Mate Weirdl for corrections.

270 comments

Comments feed for this article

19 January, 2021 at 1:04 am

adityaguharoy

On page 62 line 1, equation number 2.7 the right hand side should be $|A| |B| \min ( |A| , |B| ).$ The comma inside the minimum is missing.

19 January, 2021 at 1:15 am

N is a number

Can you please give an idea motivating the name “additive energy” in page 61 ?

[See https://mathoverflow.net/questions/223954/where-did-the-term-additive-energy-originate -T.]

21 January, 2021 at 9:41 am

Aditya Guha Roy

Related to an already mentioned errata on page 162, there is a typo in the last line. On the last two lines of that page, I think it should say that 0 can only be represented as a sum of two squares in only one way. The squares is mentioned as elements in the book.

[Correction added, thanks – T.]

22 January, 2021 at 6:27 am

Aditya Guha Roy

Just some nitpicking : in the statement of lemma 4.20 (size bounds) on page 166, one should have $\rho \le 1$ in order to ensure that $\rho ^{|S|} \le 1$ .

[This correction has already been noted – T.]

25 January, 2021 at 9:07 pm

adityaguharoy

On page 61 in the 5th point of the statement of Proposition 2.7 (vanishing of the Ruzsa distance), I think we should have $|nA - mA| = |A|$ for all non-negative integers $n,m$ with $(n,m) \ne (0,0)$ because if both $n,m$ are equal to zero, then $nA = \{ 0 \} = mA$ whence $nA - mA = \{ 0 \}$ .
The condition $(n,m) \ne (0,0)$ is missing in the text.

[Erratum added, thanks – T.]

25 January, 2021 at 9:13 pm

adityaguharoy

The result for $(n,m) \ne (0,0)$ follows from $\sigma [A] = 1$ by an application of the exact sum set theorem (Proposition 2.2 in the book).

27 January, 2021 at 4:24 am

adityaguharoy

On line 8 of page 63 the sum should be $\sum_{y \in A-B} | \{ ( a,a' , b , b' ) \in A \times A \times B \times B : a-b = y = a' - b ' \} |$ .

[A version of this correction is already implemented – T.]

1 February, 2021 at 9:24 pm

Aditya Guha Roy

In Corollary 2.23 shouldn’t we need the condition that $n_1 + n_2 + n_3 + n_4 \ne 0$ because if each $n_i = 0$ then the LHS of the display on the last line of page 73 will be $= 1$ (since those sets contain the identity element $0$ ) while the RHS will be $= 0$ .

Another thing:
On the display on the last line of page 73 shouldn’t the right hand side be $5(n_1+n_2+n_3+n_4-1) d(A,A)$ because when we apply equation 2.17 with the mentioned trivial estimates we would get $\frac{|n_1 A - n_2 A - n_3 A +n_4 A|}{|n_1 A - n_2 A|^{1/2} |n_3 A - n_4 A|^{1/2}} \le \frac{ \delta [A] ^{5(n_1+n_2+n_3+n_4 - 1} |A| }{ | A |^{1/2} |A|^{1/2} }$ where the numerator comes from equation 2.17 and the denominator comes from the trivial estimate $|k A| \ge |A|$ for any integer non-zero integer $k.$

But somehow I see that if the latter is also true then we need the former condition to be strengthened to $n_1 + n_2 + n_3 + n_4 \ge 2,$ because having $n_1 + n_2 + n_3 + n_4 = 1$ will give the same problem.

[Erratum added. The small optimisation of the $-1$ factor has been omitted from this preliminary estimate to reduce clutter. -T]

16 March, 2021 at 11:36 am

Zach Hunter

On the erratum for page 15, I am confused why you say $\kappa/2$ should be replaced by $\kappa/16$ instead of 16. I have not worked out the constants for $\Theta(C^2 \log(n) )$ , so maybe $\kappa/16$ also works, but I would think that 16 is the simpler constant…

[Corrected, thanks – T.]

8 April, 2021 at 11:01 pm

Marcel Goh

Hi Prof. Tao, I am wondering if the measure ${\bf P}$ constructed at the top of page 450 is measure-preserving. It needs to be to apply Theorem 11.23, but it is not immediately obvious to me why it is. I can sort of see how one might argue that shifting the index by 1 inside the formula wouldn’t change the $\limsup$ or $\liminf$ of the sequence of averages that we apply $\lambda$ to. But since $\lambda$ is only guaranteed to be sandwiched between the two limits, if the inner sequence is not convergent, are we always sure that $\lambda$ applied to the sequence is shift-invariant? Would you be able to spell this out a bit more? Thanks in advance!

18 April, 2021 at 9:39 pm

Terence Tao

For any set $B$ of integers, ${\bf P}_{[-N_j, N_j]}(B)$ and ${\bf P}_{[-N_j, N_j]}(B+1)$ differ by $O(1/N_j)$ , and hence their generalised limits $\lambda$ will agree.

25 May, 2021 at 5:03 am

Zach Hunter

On page 51, when describing Goldbach’s conjecture, you write $2\textbf{P}$ rather than $2P$.

25 May, 2021 at 5:59 am

Aditya Guha Roy

I think $\mathbf{P}$ is used to denote the set of all prime numbers, thus the notation.

25 May, 2021 at 6:14 am

Aditya Guha Roy

Please ignore my comment above, because on page 12 (line number 6 from below), it is mentioned that the set of primes will be denoted by $P,$ and in a previous section it is stated that $\mathbf{P}$ shall be used to denote the probability of an event.
Apologies for any inconvenience caused due to my comment above.

25 May, 2021 at 6:05 am

N is a number

Prof. Tao, in exercise 1.1.4 on page 5 of the book you mention the term “popularity principle” for the mentioned inequality $\mathbf{E}[X \textbf{1}(X > \frac{1}{2}\mathbf{E}(X)] \geq \frac{1}{2}\mathbf{E}(X)$ . Can you suggest a reason why this nomenclature is assigned to the inequality?

[The term arose from Gowers’ use of “popular differences” in his proof of Szemeredi’s theorem, see e.g., p. 504 of https://www.cs.umd.edu/~gasarch/TOPICS/vdw/sz-thm-gowers-proof.pdf -T]

1 June, 2021 at 10:24 am

Zach Hunter

On page 26, you write $x’ \in S$ rather than $x’ + S$.

[Erratum added, thanks – T.]

23 July, 2021 at 5:38 am

Zach Hunter

On page 88, when defining $\tilde{O}$ and $\tilde{\Omega}$ , I think that $\log(L)$ should be $\max\{1,\log(L)\}$ . Otherwise, the claim that $\alpha_j = \tilde{\Omega(1)}$ would be false, as the LHS does not depend on $L$ , however the RHS says it should get arbitrarily large as $L$ approaches 1.

[Erratum added, thanks – T.]

13 September, 2021 at 9:17 pm

s1mple

In the proof of Proposition 10.24, why was it necessary to choose $p$ large enough ($2N < p N?

[If $p$ is too small, then there can be arithmetic progressions in $[1,N] \hbox{ mod } p$ that do not arise from arithmetic progressions in $[1,N]$ (viewed as a susbet of the integers), due to wraparound effects. -T]

13 September, 2021 at 9:33 pm

s1mple

In lemma 10.29, how does the last equation on page 391, follow from holder’s inequality, can you please explain? I am getting $\Omega(\sigma^{1/2}).
Even if we consider the display after ” In particular, from (4.2),(4.9)…” then if we take the maximum out on the LHS and then try to see, then also the last display comes out to be $\Omega(\sigma^{1/2}).

[Here we are using $\|F\|_{L^2}^2 \leq \|F\|_{L^1} \|F\|_{L^\infty}$ . -T]

14 September, 2021 at 1:43 am

s1mple

Dear Tao,
Page 394, on the RHS (inequality) of display 2, it should be $\delta^2 \mathbb{E}_{x \in Z} f(X)1_{Bohr(s,\rho-\rho_1)}(x)$ instead of $Bohr(s,\rho-\rho_1)(r)$

[Corrected, thanks -T]

21 September, 2021 at 7:28 am

Aditya Guha Roy

I wanted to mention a nice expository application of the techniques in the first section of the chapter on Fourier analysis, which I learned from my friend Drago Grozev, in solving a problem from the IMO Shortlist of 1999 (the problem was the 6th combinatorics problem, better known as C6).

I am sharing the details below, because I feel that there exist some more people who will like it, just like how I did.

Let $x, y$ be two odd integers with $|x| \ne |y|$ . We color the integers using 4 colors. Show that there exists two integers $a,b$ of the same color which satisfy $a-b \in \{x,y, x+y , x-y \}$ .

The Fourier analytic solution to this problem proceeds as follows:
First of all notice that one can assume without losing generality that $x,y$ are positive.
Now let us fix one of the 4 colors, say it is green and we define a function $g : \mathbf{Z} \to \{0,1\}$ where $g(k) = 1$ if and only if $k$ is colored green.
Now for sake of contradiction, assume that the to-be-proved claim is false.
Then for each positive integer $m$ one has
$g(m) + g(m-x) + g(m-y) + g(m-x-y) = 1$ .
Next, notice that the function $g$ must be periodic. Let $l$ be a period of $g$ , and let $\hat{g}$ be the Fourier transform of $g$ .
Now, from the properties of $g$ deduced above it follows that $||g||_{L_2}^2 = 1/4$ and also $\hat{g}(0) = 1/4$

Now, using the conditions on $x,y$ and applying the inverse Fourier transform yields
$g(xy) = \hat{g}(0) - \sum_{m \in A} \hat{g}(m)$
and $g(2xy) = \hat{g}(0) + \sum_{m \in A} \hat{g}(m)$
where $A = \text{supp} (\hat{g} ) \setminus \{ 0 \}$
thus leading to $g(xy) + g(2xy) = 1/2$ which is not possible, since $g$ is integer-valued, a contradiction is obtained as desired. $\square$

21 September, 2021 at 8:15 am

N is a number

Prof. Tao,
on page 157 in equation 4.14 you have written $E ( 1_{A} , 1_{B})$ ; however the additive energy was defined for sets, and here we have their characteristic functions.
Apologies in advance if I missed taking a note of this notation defined somewhere earlier in the text.

[See the existing erratum for this equation – T.]

22 September, 2021 at 10:58 pm

N is a number

A small not-so-serious typo: on page 156 and in the 7th line after the section heading “L^p theory” I think you would like to put a colon (:) before the equality sign when you define $||f||_{L^{\infty}(Z)}$ since this expression defines the quantity on the left.

[Erratum added, thanks – T.]

13 November, 2021 at 5:47 pm

RFZ

Dear Prof. Tao,
on page 61 (Proposition 2.7) the fifth condition should be $|nA-mA|=|A|$ for all pairs of non-negative integers $n,m$ with $n+m\geq 1$. Because if $(n,m)=(0,0)$, then $|0A-0A|=|A|$ but $0A$ is defined to be $\{0\}$.

[This errata was already added – T.]

14 November, 2021 at 9:03 am

RFZ

Dear Prof. Tao,
on page 61 after proposition 2.7 the sentence “Later on in this chapter we shall generalize this proposition to the case when the Russia distance, difference constant, or doubling constant are little larger than 0,0, or 1, respectively…” to “Later on in this chapter we shall generalize this proposition to the case when the Russia distance, difference constant, or doubling constant are little larger than 0,1, or 1, respectively…”.

[Correction added, thanks – T.]

24 November, 2021 at 11:49 am

RFZ

Dear Prof. Tao,

I was wondering is the inequality in problem 2.2.6 on page 58 correct? I guess it should be ” at most $2\sqrt{\sigma[A]|A|}-1$ “. Since $S$ is a Sidon set, then $\sigma[S]=\dfrac{|S|+1}{2}$ . Also $S\subset A$ then by problem 2.2.5 we have $\sigma[S]\leq \sqrt{|A+A|}$ . Combining them we obtain the following: $S\leq 2\sqrt{\sigma[A]|A|}-1,$ where $S$ is a Sidon set in $A$ . Please correct me if I’m wrong. Thanks a lot!

24 November, 2021 at 12:48 pm

RFZ

Sorry I was wrong. I’ve figured out how to solve. Easy to see that $|S|^2=\sum_{t\in S+S}\#\{(x,y)\in S^2: x+y=t\}$ but since $S$ is a Sidon set in $A$ , then $\#\{(x,y)\in S^2: x+y=t\}=2$ . Hence $|S|^2=2|S+S|\leq 2|A+A|$ and taking square root we obtain the desired inequality.

24 January, 2022 at 11:47 am

achraf mhamdi

I am reading this which is good but the book lacks many things. There is no complete solutions to most of the exercises and many notations introfducted in the book don’t have explanations. This is a big problem for the book. Like the function theta and omega which are not introduced in the book and just write some pages intruducting which function’s name you are talking about.

27 January, 2022 at 12:15 pm

achraf

Can you provide us with a full solution manual to the exercises, please?

14 February, 2022 at 3:11 pm

RFZ

Dear Prof. Tao!
I have some remarks:
1) Please take a look at page 70 (Ruzsa’s covering lemma). The last line of statement of lemma says “In particular, $B$ can be covered by $\min \{\frac{|A+B|}{|A|}, \frac{|A-B|}{|A|}\}$ translates of $A-A$ “. I think you forgot a sign $\leq$ before $\min$ . I mean the corrected version should be the following: “In particular, $B$ can be covered by $\leq \min \{\frac{|A+B|}{|A|}, \frac{|A-B|}{|A|}\}$ translates of $A-A$ “.

2) Please take a look at page 71 (Green-Ruzsa covering). The second paragraph of the proof starts as “Every time we add an element to $X$ , the size of $|X+A|$ …”. Corrected version should be the “the size of $X+A$ “.

[Corrections added, thanks – T.]

15 February, 2022 at 6:11 pm

RFZ

Dear Prof. Tao!
On page 73 the statement of Corollary 2.22 should be corrected in the following way: $2A-A$ can be covered by $\leq \delta[A]^5$ translates of $A-A$ . The sign $\leq$ must e inserted before $\delta[A]^5$

[Correction added, thanks – T.]

16 February, 2022 at 8:38 am

RFZ

Dear Prof. Tao,
I guess you also need to add some corrections to the paragraph which follows immediately after Corollary 2.22. We need to insert the sign $\leq$ each time before $\delta[A]$ . More precisely, it should be as follows: “This then shows that $3A-A$ is covered by $\leq \delta[A]^5$ translates of $2A-A$ , and hence by $\leq \delta[A]^{10}$ ” translates of $A-A$ . Continuing in this fashion, an easy induction then shows $mA-nA$ can be covered by $\leq \delta[A]^{5(m+n-2)}$ translates of $A-A$ .

16 February, 2022 at 1:33 pm

RFZ

Dear Prof. Tao,

On page 73, please take a look at Corollary 2.23. In one of the previous comments Aditya Guha Roy pointed out that this inequality is false when all $n_i=0$ and this “correction” has been added. But I think that this inequality is true even all $n_i=0$ . Indeed, $0A$ is defined to be $\{0\}$ . Hence, the LHS of the inequality becomes $d(n_1A-n_2A,n_3A-n_4A)=d(0A-0A,0A-0A)=$ $d(\{0\}-\{0\},\{0\}-\{0\})=d(\{0\},\{0\})=\log \dfrac{|\{0\}|}{|\{0\}|}=\log 1=0$ and the RHS of the inequality is also $0$ .

16 February, 2022 at 1:35 pm

RFZ

P.S. I forgot to add that please correct me if I’m wrong. Maybe I am missing some details.

[The problem lies more with the case where say $(n_1,n_2)=(0,0)$ but $(n_3,n_4) \neq (0,0)$ . -T]

18 February, 2022 at 8:06 am

RFZ

Dear Prof. Tao, sorry but even if you take $n_1=n_2=0$ and $n_3=1$ and $n_4=0$ the inequality becomes $d(0A-0A, A-0A)\leq 5(0+0+1+0)d(A,A) \Leftrightarrow$ $d(\{0\},A)\leq 5d(A,A) \Leftrightarrow$ $0\leq 5d(A,A)$ which is true. I don’t see any issue here. Please correct me if I’m wrong!

[ $d(\{0\},A) \neq 0$ . -T]

20 February, 2022 at 12:39 pm

RFZ

Dear Prof. Tao,
As I wrote above the inequality $d(n_1A-n_2A, n_3A-n_4A)\leq 5(n_1+n_2+n_3+n_4)d(A,A)$ holds for all $n_i\geq 0$ . You said that if one takes $n_1=n_2=0$ and $n_3=1, n_4=0$ we have issues but I think it is still true. I showed it in the above comment (please take a look). Please let me know does it make sense now? Thanks a lot!

16 February, 2022 at 1:57 pm

RFZ

Dear Prof. Tao,
Please take a look at the first inequality on the page 74: $\sigma[n_1A-n_2A]\leq \sigma[A]^{10(n_1+n_2)}$ . I think that the exponent here should be 20, not 10. Corollary 2.23 says that $d(n_1A-n_2A,n_3A-n_4A)\leq 5(n_1+n_2+n_3+n_4)d(A,A) \Leftrightarrow$ $\frac{|n_1A-n_2A-n_3A+n_4A|}{\sqrt{|n_1A-n_2A||n_3A-n_4A|}}\leq (\frac{|A-A|}{|A|})^{5(n_1+n_2+n_3+n_4)}$ . Taking $n_4=n_1$ and $n_3=n_2$ , we obtain: $\frac{|n_1A-n_2A-n_2A+n_1A|}{|n_1A-n_2A|}\leq \delta[A]^{10(n_1+n_2)} \Leftrightarrow$ $\sigma[n_1A-n_2A]\leq \delta[A]^{10(n_1+n_2)}$ . Using inequality (2.11) on the page 64 which is $\delta[A]^{1/2}\leq \sigma[A]$ we obtain: $\sigma[n_1A-n_2A]\leq \sigma[A]^{20(n_1+n_2)}$ . Please correct me if I’m wrong!

[It’s more efficient to take $n_4 = n_2$ and $n_3 = n_1$ , then one can avoid using (2.11). -T]

18 February, 2022 at 7:53 am

RFZ

Dear Prof. Tao, Sorry but if you take $n_4=n_2$ and $n_3=n_1$ , we obtain the following: $\frac{|(n_1A-n_2A)-(n_1A-n_2A)|}{|n_1A-n_2A|}\leq (\frac{|A-A|}{|A|})^{10(n_1+n_2)}$ and we can write as $\delta[n_1A-n_2A]\leq \delta[A]^{10(n_1+n_2)}$ , but we need to obtain this kind of estimate for $\sigma[A]$ which is a doubling constant. Or maybe in the book it should $\sigma[n_1A-n_2A]\leq \sigma[A]^{10(n_1+n_2)}$ rather than $\delta[n_1A-n_2A]\leq \delta[A]^{10(n_1+n_2)}$ . Am I missing something?

18 February, 2022 at 7:55 am

RFZ

Sorry I meant the following: Maybe it should be $\delta[n_1A-n_2A]\leq \delta[A]^{10(n_1+n_2)}$ rather than $\sigma[n_1A-n_2A]\leq \sigma[A]^{10(n_1+n_2)}$

[Ah, I see the issue now, thanks. The simplest thing to do is to replace 10 by 20 as originally suggested – T.]

20 February, 2022 at 7:33 am

RFZ

Dear Prof. Tao, I was wondering is something wrong with my above two comments? For some reason you did not reply. Thanks a lot!

17 February, 2022 at 5:29 am

N is a number

Prof. Tao, some of the links on this page are not working for example the link to Arithmetic Ramsey theory, Math 262 notes are not working. Could you please check them?

[I think Van Vu has not maintained that web page since he moved to Yale. -T]

23 February, 2022 at 6:58 am

RFZ

Dear Prof. Tao, In exercise 2.4.5 on page 76 there is a small mistake. The bound $|nG|\leq \min(K^n, n^{K-1})|G|$ for all $n\geq 1$ does not follow immediately from $|nG|\leq \binom{K+n-1}{n}|G|$ because $\binom{K+n-1}{n} > n$ for $K=2$ .

However, the above estimate could be improved slighty as follows: one can show that
$|nG|\leq \binom{K+n-2}{n-1}|G|$ and this one immediately implies that $|nG|\leq \min(K^n,n^{K-1})|G|.$

Proof: Let’s prove that $|nG|\leq \binom{K+n-2}{n-1}|G|$ . Since $G$ is a $K$ -approximate group, then $2G\subseteq G+X_0$ with $|X_0|\leq K$ . By induction one can show that $nG\subseteq G+(n-1)X_0$ and hence $|nG|\leq |G||(n-1)X_0|$ and we can estimate $|(n-1)X_0|$ by inequality (2.3) on page 54. Therefore $|nG|\leq |G|\binom{|X_0|+n-2}{n-1}=|G|\frac{|X_0|\cdots(|X_0|+n-2)}{(n-1)!}\leq |G|\frac{K\cdots (K+n-2)}{(n-1)!}=|G|\binom{K+n-2}{n-1}$ and it immediately implies that $|nG|\leq \min(K^n,n^{K-1})|G|.$

[Correction added, thanks -T.]

24 February, 2022 at 11:11 am

Aditya Guha Roy

I think we can still deduce the latter claim from the former part of the exercise, by looking at the case of $K = 2$ separately.

24 February, 2022 at 3:59 pm

RFZ

That could be true but I did not check it at all. Anyway the bound $|nG|\leq \binom{K+n-2}{n-1}|G|$ is better than $|nG|\leq \binom{K+n-1}{n}|G|.$ Moreover, it immediately implies that $|nG|\leq \min(K^n,n^{K-1})|G|$

25 February, 2022 at 8:00 am

Aditya Guha Roy

Fair enough.

27 February, 2022 at 10:23 am

RFZ

Dear Prof. Tao,

In exercise 2.4.7 on page 77 the upper bound $|2G\cap 2H|\leq (KK')^3\dfrac{|G||H|}{|G+H|}$ can be improved to the following one: $|2G\cap 2H|\leq (KK')^2\dfrac{|G||H|}{|G+H|}.$

Proof: By Ruzsa triangle inequality we have: $|G+H||2G\cap 2H|\leq |G+(2G\cap 2H)||H+(2G\cap 2H)|;$

1) Note that $G+(2G\cap 2H)\subseteq (3G)\cap (G+2H)\subseteq 3G\subseteq G+2X_0$ the last inequality follows from the fact that $G$ is a $K$ -approximate group, i.e. $2G\subseteq G+X_0$ for some additive set $X_0$ such that $|X_0|\leq K$ .

2) In the same way one can show that $H+(2G\cap 2H)\subseteq (3H)\cap (2G+H)\subseteq 3H\subseteq H+2X_1$ because $H$ is a $K'$ -approximate group, i.e. $2H\subseteq H+X_1$ for some additive set $X_1$ such that $|X_1|\leq K'$ .

We see that $1)\Rightarrow$ $|G+(2G\cap 2H)|\leq |G+2X_0|\leq |G||X_0|^2\leq K^2|G|$ and $2)\Rightarrow|H+(2G\cap 2H)|\leq |H+2X_1|\leq |H||X_1|^2\leq (K')^2|H|.$

Combining these inequalities we obtain that $|G+H||2G\cap 2H|\leq (KK')^2|G||H|$ .

27 February, 2022 at 12:43 pm

RFZ

P.S. in this problem the final inequality which is $d(G,2G\cap 2H)+d(2G\cap 2H, H)\leq d(G,H)+3\log KK'$ can be slightly improved as follows: $d(G,2G\cap 2H)+d(2G\cap 2H, H)\leq d(G,H)+2\log KK'$ .

Proof: The last inequality can be be written as $|(2G\cap 2H)+G||(2G\cap 2H)+H|\leq (KK')^2|G+H||2G\cap 2H|$ and we need to prove it. Since $G$ is a $K$ -approximate group and $H$ is a $K'$ -approximate groups, then $2G\subseteq G+X_0$ and $2H\subseteq H+X_1$ for some additive sets $X_0, X_1$ such that $|X_0|\leq K,|X_1|\leq K'.$

It is easy to see that $(2G\cap 2H)+G\subseteq 3G\subseteq G+2X_0$ and $(2G\cap 2H)+H\subseteq3H\subseteq H+2X_1$ . Hence $|(2G\cap 2H)+G||(2G\cap 2H)+H|\leq |G||H||X_0|^2|X_1|^2\leq (KK')^2|G||H|.$ But $|G||H|\leq |2G\cap 2H||G+H|$ (see the first inequality of this problem) and hence $(KK')^2|G||H|\leq (KK')^2|2G\cap 2H||G+H|.$

7 March, 2022 at 4:20 pm

RFZ

Dear Prof. Tao,
What about the above 2 corrections which I’ve mentioned?

28 February, 2022 at 8:46 am

Aditya Guha Roy

On page xvii I think there is some error on line 18-19 where you say that $N$ is called dimension of $P$ and also $d$ the dimension (or rank) of $P$ (this is in context of the definition of generalized arithmetic progressions).

[ $N$ are the dimensions of the progression, which is a distinct concept from the dimension of the progression, though the latter is often referred to as the rank to avoid confusion. -T]

7 March, 2022 at 12:33 pm

RFZ

Dear Prof. Tao,
1) In problem 2.4.8 on page 77-78 the last inequality which is $d(G_1,G_2)\leq d(G_1+G_3,G_2+G_3)+2\log K_1K_2K_3$ is wrong. One can take $G_1$ to be interval on $x$ -axis of $\mathbb{Z}^2$ , $G_2$ to be an interval on $y$ -axis of $\mathbb{Z}^2$ and $G_3$ to be large rectangular box. However, the following inequality is true: $d(G_1+G_3,G_2+G_3)\leq d(G_1,G_2)+2\log K_1K_2K_3$ .

2) In problem 2.4.6 one should add $K^2$ before $\min$ , i.e. I mean it should be $|nA|\leq K^2\cdot \min(K^{Cn}, n^{K^C-1})|A|$ .

4) I see that the correction ( $n_1+n_2>0, n_3+n_4>0$ ) has been added to Corollary 2.23 on page 73-74. Even in this case if you take $n_1=1, n_2=0$ and $n_3=0, n_4=2$ you will obtian the following inequality $d(A,-2A)\leq 15 d(A,A) \Leftrightarrow$ $\dfrac{|3A|}{\sqrt{|A||2A|}}\leq \left( \dfrac{|A-A|}{|A|}\right)^{15}$ . However, the last inequality may not be true. So therefore for safety I suggest to take all $n_1,n_2,n_3,n_4\geq 1$ .

[(1) corrected, thanks. The $K^2$ factor in (2) can be deleted by increasing $C$ suitably, and using Exercise 2.4.4 to handle the case of $K$ close to 1. As for (4), I believe this estimate continues to hold in the cases indicated (for instance from the $(m,n)=(3,1)$ case of (2.17) one has $|3A| \leq |3A-A| \leq \delta[A]^{15} |A|$ , which implies the estimate you stated) – T.]

12 October, 2022 at 8:16 pm

marcel goh

Dear Prof. Tao,

In the proof of irreducibility of cyclotomic polynomials (Lemma 9.48), when we constructed $h(z)$ , we assert that it is a nontrivial monic polynomial in ${\bf Z}[z]$ , and later, we derive a contradiction because we show that, in ${\bf F}_p$ , $h(z)$ divides both $z^n-1$ and $nz^{n-1}$ , when in fact these polynomials have g.c.d. $1$ . However, I’m not sure how we are certain that $h(z)$ is not equal to $1$ modulo $p$ (the way that, say, $z^4 - z^2 +1$ equals $1$ modulo $3$ ). Thanks!

21 October, 2022 at 10:54 am

Terence Tao

Sorry for the confusion. We are actually working in the formal polynomial ring $F_p[z]$ rather than the space of polynomial functions from $F_p$ to $F_p$ . This is still a unique factorization domain, and in this case for instance $z^4 - z^2 + 1$ and $1$ are distinct polynomials in the ring $F_3[z]$ despite having the same evaluations at every point of $F_3$ .

16 March, 2023 at 9:39 am

Zach Hunter

Throughout Chapter 7.7, you write “Ess\’een” several times and also do this in item [101] of the bibliography… However, it seems to me that there should be no accent! This is how the name is written on Wikipedia and the very paper you cite.

[Erratum added – T.]

31 January, 2024 at 12:24 am

Anonymous

In exercise 4.3.15, should there be an additional restriction that $M$ is self-adjoint? Without that I am only getting the result for $\text{dim}(Z) \geq 5$ instead of 3. The paper mentioned in the references seems to show this only when $M$ is self-adjoint (lemma 7.3 in https://arxiv.org/pdf/math/0503014.pdf )

[Erratum added – T.]

	Anonymous on Two announcements: AI for Math…
	Anonymous on 254A, Supplement 4: Probabilis…
	Terence Tao on Analysis II
	Anonymous on Analysis II
	El problema de Erdős… on Two announcements: AI for Math…
	Anonymous on An airport-inspired puzzle
	oliverknill on Two announcements: AI for Math…
	Anonymous on An airport-inspired puzzle
	Prashant Patil on Two announcements: AI for Math…
	Anonymous on Two announcements: AI for Math…
	Anonymous on Two announcements: AI for Math…
	Anonymous on 275A, Notes 3: The weak and st…
	Anonymous on 275A, Notes 3: The weak and st…
	Anonymous on Two announcements: AI for Math…
	Anonymous on Two announcements: AI for Math…

Additive combinatorics

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

270 comments

Leave a reply to Anonymous Cancel reply

For commenters

Additive combinatorics

Share this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

270 comments

Leave a reply to Anonymous Cancel reply

For commenters