Last updated: Feb 24, 2024
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 —
- Gowers’ proof of Szemeredi’s theorem for progressions of length 4
- Non-commutative sum set estimates
- The Roth-Bourgain theorem
- Math 254A (some highlights of arithmetic combinatorics)
- Math 262 (Topics in Combinatorics)
— Errata —
- p. xi: Reference [116] should be [113].
- p. xiv: “Chevalley-Waring” should be “Chevalley-Warning”.
- p. 1, last display: should be .
- 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, should be (two occurrences). In Q. 1.1.5, and should be and respectively.
- p. 6: Exercise 1.1.8 is missing. This exercise reads: “Let be an additive set. Show that there exists a subset of cardinality such that . (Hint: translate randomly by independent elements of , and use the first moment method.)”
- p. 8: In the fourth display, should be . should be .
- p. 9: In Exercise 1.2.4, the inequality should be reversed.
- p. 11: In the paragraph after (1.17), should be .
- p. 14: In the 9th line from below, should be (two places); similarly before (1.23) on P. 15. In the final display, should be (not as stated previously).
- p. 15: In the first display, the first sign should be .
- 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 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, needs to be positive.
- p.18: In Exercise 1.3.8, the expectation should be and the variance should be . In Exercise 1.3.11, should be .
- p. 21: In Definition 1.21,”we say that is a -complementary base of ” should be”we say that is a -complementary base of order of “.
- p. 22, before second display: Lemma 1.53 should be Theorem 1.53.
- p. 23: Near top: “the event that is good” should be “the event that is good”. In the last line of the proof of Lemma 1.24, should be .
- p. 24: In the last display, the third should be .
- p. 25: In the first display, should be .
- p. 36: In the first line of the proof of Theorem 1.39, add “Without loss of generality we may assume . In the third display on the last line, should be .
- p. 37: In the first display, should be |A|.
- p. 38: In the RHS of the display in Corollary 1.42 RHS of the formula, should be .
- p. 40: In the RHS of the last display should be .
- p. 41: In the first display, should be .
- p. 44: One line before the third display, should be .
- p. 47: In the penultimate equation in the proof of Proposition 1.51, the summation should be , and one should observe that the integrand vanishes for . In the last equation, should be . The last sentence of the proof should then say “Direct computation then shows that and , and the claim follows”.
- p. 57: In the bounds for , should be (two occurrences). Similarly, should be (two occurrences).
- p. 58: In Exercise 2.2.5, should be .
- p. 68: In Exercise 2.3.14, should be , and should be . Replace “though the set may be symmetric around a non-zero origin ” with “where by symmetry here we mean that ”. (The point is that 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, should be .
- p. 78: In, Exercise 2.4.11, Proposition 2.4.11 should be Proposition 2.27.
- p. 79: In (2.20), should be .
- p. 80: In the first paragraph, should be . 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 and ” should be the iterated sum and difference sets of and “.
- p. 82: In Exercise 2.5.3, add after . In Exercise 2.5.4, “is can be used” should be “can be used”.
- p. 85: In, Lemma 2.23, “there exists a set ” should be “there exists a set “.
- p. 86: In the first display of the proof of Lemma 2.34, should be G.
- p. 87: In the fourth display, the on the LHS and RHS should be . In the last sentence in the statement of Theorem 2.35, should be .
- p. 95: Lemma 2.41, while correct, does not imply Corollary 2.42 as stated (since does not control ). Thanks to Mei-Chu Chang for pointing out the problem. Replace “As , this implies” by “A similar argument (see [Proposition 4.5, 362]) gives”. Rename Corollary 2.42 as Proposition 2.42, replace “” by “” in the first sentence, replace “” by “” in the second sentence, and replace “” by “” in the display.
- p. 96: “verstion” should be “version”.
- p. 97: In Theorem 2.48 (ii), should be .
- 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 should be an .
- p. 115, fourth line of Lemma 3.4: should be .
- p. 116, proof of Corollary 3.6: “induce” should be “induct”. In the last two sentences of this proof, should be (three occurrences).
- p. 117, proof of Theorem 3.7: “induce” should be “induct”.
- p. 118: Exercise 3.1.1 should be
- p. 120: In the second display, should be .
- p. 121, after the proof of Lemma 3.11, “an progression” should be “a progression”.
- p. 122, after first display: “for all real ” should be “for all non-negative reals “. In the next sentence, “for any integer ” should be “for any positive integer “, and “” should be ““.
- p. 123, proof of Theorem 3.13: should be . On the same line, “whch” should be “which”.
- p. 124: should be (two occurrences). In the first display and two lines further down, should be . In the second-to-last display, should be . In the last paragraph, should be .
- p. 128: In the proof of Proposition 3.19, should be . In the next paragraph, the inclusion should be , and the constraint may be relaxed to .
- 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, should be .
- p. 130: In Exercise 3.4.5, “amd” should be “and”. In Exercise 3.4.6, all occurrences of should be .
- 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 are distinct.
- p. 133: On the second display, should be . Just before the third display, should be . In Corollary 3.25, should be . In the next display, delete .
- p. 134: In Lemma 3.27, Blichtfeld should be Blichfeldt.
- p. 139: In the last display, |B| should be .
- p. 140: In the proof of Theorem 3.34, should be .
- p. 141-142: Throughout the statement and proof of Lemma 3.36, should be replaced with , and replaced with . In the last two equations in the display, replace and both by .
- 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 and is not proper” with “If , is not proper, and is torsion-free”. In the proof, “We induce on ” should be “We induct on ”. On the last line, “unless is torsion-free” should be deleted.
- p. 147: In the second paragraph, “” should be ““.
- p. 155: In Q 4.1.7, should be . In Q 4.1.10, the range of should be rather than C.
- p. 157: In (4.14), should be .
- p. 158: In the proof of Lemma 4.10, should be . Between the second-to-last and third-to-last lines of the long display in that proof, insert the lines “” and “”.
- p. 159: In Exercise 4.2.2, “let the dual exponent” should be “let be the dual exponent”.
- p. 162: In the proof of Lemma 4.14, should be . In the third line of Corollary 4.15, should belong to rather than , and should be . (Remark: the order estimate only gives the qualitative result for sufficiently large, but the small values of can be done by hand.) In the last word of the last sentence, should be .
- p. 164, in Q. 4.3.10, “” should be ““.
- p. 165, bottom paragraph: “combinatorialinformation” should be “combinatorial information”.
- p. 170, proof of Lemma 4.25: should be 2, and the condition should be .
- p. 171, in Q 4.4.6, should be .
- p. 173: In the proof of Proposition 4.29, (4.31) should be (4.30). In the second and last displays, should be .
- p. 174: In the third display, should be .
- p. 175: In the four summations involving , should range over Z rather than S. After the second display, and should be and respectively, and similarly on the third display.
- p. 176: In the last display, should be .
- p. 177: In the first display, should be . In the third display, should be . In the penultimate display, should be . “If take” should be “Taking”. In the last display, should be =.
- p. 179: In Exercise 4.5.4, should be .
- p. 181: In the proof of Lemma 4.35, “incrementing k+1” should be “incrementing k”.
- p. 182, middle: “” should be ““. After the fourth display, should be . In the last display, the upper limit of the integral should be infinite.
- p. 183: In the last four displayed equations, all signs should be . In (4.38), is missing from the RHS. In the sixth display, should be .
- p. 184: In the fourth and fifth displays, should appear on the right-hand side. (Also, to avoid ambiguity, one may wish to rewrite in the fifth display as .)
- p. 185: In the proof of Proposition 4.39, should be .
- p. 186: In Proposition 4.40, can be improved to (though the existing bound is certainly correct). In the line before the last display, should be .
- p. 187: In Theorem 4.41, should be .
- 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 .
- p. 193: In the third line of the first display, should be . In the second and final displays (and in the first display of p194 and the second, third, and fourth displays in p195), should be (seven occurrences).
- p. 194: In the first display, should be . After the second display, should equal latex \delta^2$ rather than .
- p. 195, first line: should be . In the first display, 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, should be .
- p. 200: “induce” should be “induct” (four occurrences). In the fourth line of the proof, should be .
- p. 203: the subscript should be (three occurrences).
- p. 208: In the sixth line of the last display, should be replaced by (here we use the bound ), 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, should equal 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, should be .
- p. 213: In the proof of Proposition 5.15, should be , should be , and should be .
- 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 ” should be “we see that contains a set symmetric around some origin “.
- 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: should be . Similarly on the sixth line. Also, on that line, should be .
- p. 219: Before the third display, (5.14) should be (5.13).
- p. 221: In the first example, should be . In the fourth line of the fifth example, should be .
- p. 225: In the first line, should be . A period is missing before “Fortunately” in the sentence after the first display.
- p. 226: In Exercise 5.3.7, the range of should be rather than .
- 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, should be .
- p. 230: In the first display, should be . In the second display, should be .
- p. 231: In the fifth line, should be . In Theorem 5.33, the hypothesis should be included, and the first paragraph of the proof of Theorem 5.33 should be deleted. Throughout this proof, should be .
- 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 .
- 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, should be .
- p. 247: In Exercise 6.1.2, “symmetruc” should be “symmetric”, and one should assume .
- p. 248: In Exercise 6.1.4, the denominator should be .
- p. 249: In the second line from the bottom, Ruzsa[297] should be Ruzsa[303].
- p. 250: In the first display, should be r (and in the previous line, should have radius 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 )” should be deleted. “” should be ““. Shortly afterwards, “latter” should be “former”.
- p. 256: In the proof of Corollary 6.12, “induce” should be “induct”, and “ contains a” should be “ 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, “ monochromatic” should be “-monochromatic”. In Theorem 6.15, should be . In Proposition 6.16, should be , “exists distinct classes” should be “exist distinct classes”, and “” should be “non-zero “. 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, should be .
- 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, should be .
- p. 263: In the statement of Corollary 6.20, the in the denominator in the last line should be . In the second paragraph of the proof. the denominator should be .
- p. 264: In the second paragraph, the denominator should be . In the penultimate display, should be . In the proof of Corollary 6.20, should be (two occurrences), and should be (one occurrence). In the proof of Theorem 2.29, should be (four occurrences).
- p. 265: In Theorem 6.21, the first “then” should be an “and”. In the third display, should be .
- 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, should be .
- p. 271: In the last paragraph of 6.5.2, should be (two occurrences).
- p. 272, first display: should be .
- 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, should be . 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, should be .
- p. 290: In the display before (7.4), should be .
- p. 292: In Exercise 7.3.2, should be .
- p. 294: In statement of Proposition 7.21, add “Furthermore, each of the lies in the set “.
- p. 295: After the third display, the s should be s.
- p. 298: In the last paragraph, should be .
- p. 300: In the fourth line of the proof of Corollary 7.28, should be (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, should be .
- 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, should be (two occurrences).
- p. 318: On the sixth line, a right parenthesis is missing in . In Exercise 8.3.4, should be . In Exercise 8.3.5, should be .
- p. 322: In (8.6) should be .
- p. 324: In Exercise 8.4.3, should be .
- 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 in should be . In Exercise 9.1.3, the Hilbert nullstellensatz of course only applies when F is algebraically closed. In Exercise 9.1.4, should be .
- p. 333: In Lemma 9.3, should be .
- p. 338: In the proof of Theorem 9.11, “induce” should be “induct”.
- p. 341: In Question 9.2.6, should be .
- p. 342: In Theorem 9.17, should be , and should be . In the last sentence of the proof of Theorem 9.16, “” should be ““.
- p. 343: In the first display, the right-hand side should just be . In the next paragraph, should be , and in the paragraph after that, should be . In the first line of the last display, should be . In Lemma 9.18, the second sentence should start “Then” rather than “The”. In the 5th line (the line before 2nd display) should be .
- 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 ” should be “be a power of “.
- p. 345: In Exercise 9.3.3, “Let ” should be “Set “, and should be .
- p. 348: In the proof of Theorem 9.24, should be .
- p. 350: In Lemma 9.27, should be .
- p. 352-353: In the proof of Lemma 9.31: all occurrences of should be , etc. Also, should be . In Theorem 9.32, [266] should be [267]. In Exercise 9.5.3, should be .
- 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, should be . In the RHS of (9.14), should be . Right after Theorem 9.36, should be .
- p. 355: In Remark 9.38, “combining” should be “combined”. In the first display, should be . In the last sentence of the proof of Theorem 9.36, should be .
- p. 356: In Exercise 9.6.3, should be , and “induce” should be “induct”.
- p. 358: In the 3rd display should be .
- p. 362, bottom line: “as follows” should be “are as follows”.
- p. 363, middle: delete “and using Exercise 9.4.1”. Somewhat further down, should just be .
- 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 “ 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 fixed” should be “keeping fixed”.
- p. 367: In Exercise 9.8.3 should be (two occurrences).
- p. 368: In Exercise 9.8.8, delete “, and let be distinct integers in “. In the second display of Exercise 9.8.11, the sup should be an inf.
- p. 370: In Examples 10.3, should be . In Theorem 10.5, the phrase “… with coprime to ” 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, should be . 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, should be . In the third line of the proof of Theorem 10.12 (which should be Proposition 10.12), should be . 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 “” rather than ““.
- p. 381: In the second line, should be . (In the next two displays, the 4 is correct.) In the third line, add “and in ” just before “, such that”. In the third and fourth displays, should be .
- p. 382: in the paragraph after statement of Theorem 10.20: replace” and ” with just ““.
- p. 383: in the third display, the first = sign should be , while should be |.
- p. 384: in Lemma 10.22, needs to be between 0 and 1.
- p. 385: in third display, should be , and similarly on the next two lines. In the next display, the sum 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, “ is bounded” should be “ is bounded by 1″. In third line, should be . In Exercise 10.3.1, add the hint “(You may want to first establish the weaker but easier bound .)”
- p. 390: In Proposition 10.28, one should have rather than .
- p. 391: The conclusion of Lemma 10.29 should be rather than (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 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, should be .
- p. 398: About half-way down on the page, “to be introduce” should be “to be introduced”.
- p. 402: in the last two displays, should be .
- p. 407: In Remark 10.44, “Gowers shown” should be “Gowers has shown”.
- p. 418: In “choices of “, the parenthesis should be deleted.
- p. 439: In the second line, should be . In the fourth line, should be . In the proof of Proposition 11.12, “induce” should be “induct”.
- p. 454: In the line before Theorem 11.27, the brackets \{ \} around are missing.
- p. 462: In the last line, “in” should be .
- p. 465: “and some k-pseudorandom measure , then” should be “for some k-pseudorandom measure . 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: should be , 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, should be .
- 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, (or ) should be (this supersedes the previous erratum for this line).
- p. 16. In the final display, should be . On the next line, “Corollary 1.10 (or Corollary 1.8)” should read “Corollary 1.9”.
- p.17. In Exercise 1.3.4, should be . Also add “The variance of a complex variable is defined to be .
- p.18. In Exercise 1.3.10, add “with not both equal to ” before the first comma.
- p. 23: In (1.30), third summation, should be .
- p. 26: In the penultimate paragraph, should be .
- p. 30. In the third display, should be (say), and the third equality should be a sign.
- p. 35, first line: a right parenthesis ) missing before .
- 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 has at most a bounded number of representations as the sum of elements of between and ; the treatment of the remaining sums in which at least one term is less than is left as an exercise.” Then, in the definition of and also in the computation of , insert the lower bound in the sum. On the first line of page 37, and in Exercise 1.7.2, replace with for some . 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 for some sufficiently small , by using an induction hypothesis to bound the number of representations by sums of fewer than elements of size less than .”
- p. 42: Exercise 1.8.1 contains a number of inaccuracies (namely, “” should be “, and “no two elements” should be “no two distinct elements” (and so should really be 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 should instead be , where is the logarithmic integral.
- p. 48: in the first bound of Exercise 1.10.3, the error term of should be .
- p.54: After the proof of Lemma 2.1, “Corollary 5.13” should be “Lemma 5.13”.
- p. 58: In Exercise 2.2.6, should be . (This error is not present in the first edition.)
- Page 61. In the penultimate bullet point of Proposition 2.7, add the requirement . After Proposition 2.7, “, , or respectively” should be “, , or respectively”.
- p.62: In (2.7), after Definition 2.8, should be .
- p. 63: In the sixth line of the first display, should be .
- p. 66: In Exercise 2.3.2, should be . In Exercise 2.3.7, replace the first bound with and the second bound with .
- p. 70: In the statement of Ruzsa’s covering lemma, insert “at most” after “In particular, can be covered by”.
- p. 71: In the proof of the Green-Ruzsa covering lemma, “the size of ” should be “the size of “.
- p. 73: In Corollary 2.22, replace “covered by ” with “covered by at most “. Similarly in the proof of the corollary.
- p. 74: In Corollary 2.23, add the hypothesis , and replace the exponent by .
- p. 76: In Exercise 2.4.5, can be improved to . In the final inequality in Exercise 2.4.8, the quantities and should be swapped.
- p. 83: In Exercise 2.5.5, the small K case is somewhat more difficult than the hint suggests, since if for some small then a direct application of Exercise 2.5.4 will give losses of rather than . 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 , should be .
- p. ???: Exercise 2.6.6 is false as stated; the conclusion needs to be weakened, in that the indicated translates of only cover of rather than all of . 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 …” onwards) can be deleted, and replaced by the much shorter “Since and contains both 0 and 1, we have “.
- p. 116: In the proof of Corollary 3.6, should be , and “for some ” should be “for some .
- 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 should not be used; instead, one should normalise (and the comment that it suffices to show should be deleted). The second display should then be restricted to the range (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 ” should be “translates of “.
- p. 132: In Lemma 3.23, the hypothesis that the cosets for 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 , should be .
- 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, and should be and respectively (for consistency).
- p. 143?: Exercise 3.5.3 is false. In its place, one can put the following example (from this reference): Let be the convex hull of the four points for a natural number . Show that has cardinality , but has cardinality at least . 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, should be . In Exercise 4.1.8, should be . In Exercise 4.1.4, “for all ” should be “for all “.
- p. 156: In the second display (defining ), should be .
- p. 158: In the proof of Lemma 4.10, in the final display, the last equals sign should be a 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 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, should be . In the discussion of Lemma 4.16,the term in the approximation for after the display should be deleted. In the statement of Lemma 4.16, should be .
- p. 165: In Exercise 4.3.15, the transformation needs to be assumed to be symmetric.
- p. 166: In Lemma 4.20, the additional hypothesis should be added.
- p. 168-169: Before Proposition 4.23, “dispense with” should be “almost dispense with”. In Proposition 4.23, the proper progression should be the proper coset progression , where is a subgroup of (i.e. the multiples of for some factor of ). The last sentence of the proposition is redundant and can be deleted. In the proof, one first handles the case when has order in , in which case the first display of p.169 is an equality, and one obtains a progression of rank . In the general case, when has order for some dividing , one then passes from to by quotienting out the group generated by , 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 in (4.34) can be improved to , by setting equal to instead of in page 177 (changing the fourth and fifth displays appropriately).
- p. 179: In Exercise 4.5.8, should be . In Exercise 4.5.7, should be .
- p. 180: Exercise 4.5.11 does not work as stated and should be deleted.
- p. 181: In Lemma 4.35, add “ is an integer, ” after “where”. In the proof, “incrementing ” should be “incrementing to “. “all dissociated subsets of ” should be “all dissociated subsets of “.
- 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 should be rather than just .
- p. 188: At the end of the proof of Theorem 4.41, add the following parenthetical remark: “The upper bound on required for Corollary 2.62 is supplied by (4.37) and the lower bound on .” In Exercise 4.6.2: should be (two occurrences).
- p. 189: In the discussion after Theorem 4.42, the bound should be $latex E(A,A) >= P(A) |A|^3$.
- p. 191: In the third equation of the display, the norms should be (and the final term should just be .
- p. 193: Lemma 4.46 has a redundant “such that”.
- p. 194: In Theorem 4.47, the should be , and should be .
- 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, should be .
- 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, should be .
- p. 208: The sixth line of the long display should be (here we use ). The seventh line should be . The eighth line should be . The final line remains as (here we again use ).
- p. 211: In the statement of Lemma 5.13, “let suppose” should be just “suppose”.
- p. 226: In Exercise 5.3.4, the hypothesis “” is missing. In exercise 5.3.2, should be .
- p. 236: In the proof of Proposition 5.41, all occurrences of should be .
- p. 239: The example in Exercise 5.5.17 is incorrect; the set should be in , where is the standard basis and one adopts the convention ; “quadrilateral” should be “pentagon” and and should be replaced by throughout.
- p. 241: In the last line of the first display in the proof of Lemma 5.45, should be .
- 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 should be .
- 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, should be replaced with , with the note “where is the restricted sumset of with itself” added.
- p. 263: In the final display, the right parenthesis after should be deleted. Similarly for the first display on page 264.
- p. 271: In Section 6.5.2, should be (two occurrences).
- p. 272: The definition of 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, should be .
- p. 281: In the last paragraph, “ is odd” should be “ is odd”.
- p. 285: Corollary 5.25 should be Lemma 5.25.
- p. 286: In the second paragraph, the condition should be replaced by , and the phrase “by Markov’s inequality” should be dropped. Similarly, in the third and fifth displays, the first occurrence of in each should be .
- p. 291: In the definition of after the first display, a 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: should be elements of rather than . 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, should be .
- p. ???: In Section 7.7 and in reference [101], the accent in Esseen should be dropped.
- p. 313: In Theorem 8.10, “at most lines” should be “at most curves”.
- p. 315: In the proof of Theorem 8.14, should be .
- p. 316: In the third to last line, should be .
- p. 331: In the third and fifth displays, the summation should run up to rather than . In the proof of Theorem 9.2, should be .
- 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, should be .
- p. 363: in the last paragraph “the finite field ” should be “the ring of formal polynomials with coefficients in the finite field “.
- 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 of the integers is defined as .”.
- p. 372: In Exercise 10.0.8, add the hypothesis that no non-zero element of the groups containing or has order less than .
- p. 386: In the first display, should be .
- p. 388: In Lemma 10.25, there should be no absolute value signs around . In the last display, should be , and in the first display on page 389, should be .
- p. 388, 390-391: The Kronecker approximation theorem should more accurately be called a simultaneous Dirichlet approximation theorem.
- p. 391: In Lemma 10.29, should be , there should be an additional hypothesis of . The bound should be , and the bound should be . In the third display of the proof, the right-hand side of 1 should be , and in the fifth display, the right-hand side should be .
- p. 394: in the second display, should be .
- 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), should be , and similarly in the folowing display.
- Page ???: In the statement of Theorem 10.31, the bound for should be rather than .
- p. 405: In Exercise 10.5.1, should be .
- p. 412: In the second case of Corollary 10.50 the word ‘and’ should be inserted.
- p. 413: In Exercise 10.7.2, should be . In the second display, should similarly be (which is permissible since ).
- 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, should be .
- p. 436: In the equation before (11.21), should be , and the right brace should be deleted.
- p. 437: In the definition of , should be .
- 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, should be .
- p. 450: In the last line of the proof, “non-zero ” should be “non-zero “.
- p. 452: In Theorem 11.25, should be .
- p. 465: In the definition of , should be ; 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
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.]
7 June, 2013 at 2:49 am
Tomer Shalev
page 163: after “(for instance)” if we set A = Z … ||z||_u should be zero, but instead, what is written is ||B||_u = tao*Z + O(…) , (tao*Z should be canceled I believe).
[Corrected, thanks – T.]
17 July, 2013 at 6:32 am
Rex
On page 4: “Theorem 1.3 was proved by Erdos in 1965 [86]. Several years later, Bourgain [37] used harmonic analysis arguments to improve the bound slightly.”
It seems that a better description might be: “Three decades later, Bourgain used….”
18 July, 2013 at 9:51 am
Rex
Just so you know, the .dvi file on entropy sumset methods has some formulas that run completely off the page (so they are not visible)
19 July, 2013 at 2:10 am
Rex
p. 14: In the last display, the first sign should be . (just as with pg. 15)
19 July, 2013 at 2:12 am
Rex
Oh, nevermind. My mistake
4 November, 2013 at 1:48 pm
Real stable polynomials and the Kadison-Singer problem | What's new
[…] as the second moment method, exponential moment method, and zeroth moment method, see Chapter 1 of my book with Van Vu. For a general discussion of the probabilistic method, see the book by Alon and Spencer of the same […]
4 February, 2014 at 7:01 pm
Szemerédi’s Theorem Part I – Equivalent formulations | I Can't Believe It's Not Random!
[…] Szemerédi used a complicated combinatorial argument. Two years later Furstenberg provided a different proof of this result, using ergodic theory and a correspondence principle which allows one to derive conclusions about sets of integers by studying dynamics on certain measure spaces. It should also be mentioned that a third proof of the Szemerédi’s Theorem was discovered by Gowers in 2001, generalizing Roth’s harmonic analysis proof of the existence of progressions of length in a set of positive density, to progressions of arbitrary length and having the advantage of providing concrete bounds for the finitistic version. More recently a number of different proofs appeared. A good discussion on the different proofs and similarities between them can be found on chapters 10 and 11 of the Tao and Vu’s book. […]
19 March, 2014 at 5:30 pm
Metric entropy analogues of sum set theory | What's new
[…] estimates (which are covered, incidentally, in Section 2 of my book with Van Vu) are particularly useful for controlling finite sets of small doubling, in the sense that for […]
23 March, 2014 at 6:55 am
Anonymous
can any one please explain me the concept of “uniformly chosen random subset of a unit interval of cardinality N”.??
[One can for instance choose a random set where each of the are chosen independently and uniformly from (one can enforce the constraint if one wishes, but it is not necessary as one ends up with the same distribution of a random variable in either case. -T.]
27 April, 2014 at 12:45 pm
George
On page 128 Proposition 3.19, one should have
(as opposed to the containment going the other way). Also, just above this, it may be more clear to write let be arbitary as opposed to let be arbitrary, to emphasize that one may take , but must be avoided to assure that the sets we wish to apply Lemma 3.18 to are nonempty.
[Corrected, thanks – T.]
14 August, 2014 at 9:04 am
Marco Vitturi
Dear Prof. Tao,
in the final lines of the proof of Freiman’s 3k-3 Theorem (page 208) it appears that the inequality is used reversed, and I can’t see how the relative errata above can fix this. Am I wrong?
[Gah, the previous erratum was not applied correctly. I’ve now supplied a revised erratum in the second errata list. -T.]
27 October, 2014 at 7:28 pm
Lam
Example 1.12 p.12, “the squares are known to be a basis of order 4 (Legendre’s Theorem)” shouldn’t it be “Lagrange’s Theorem”? (4-square theorem)
[Correction added, thanks – T.]
12 November, 2014 at 12:41 pm
Lam
Dear Terry,
On page 294, after the very first proof (of 7.20), it says “however one can lower dimension its by increasing”, probably instead of “lower its dimension by increasing”.
[Correction added, thanks – T.]
18 November, 2014 at 2:09 pm
Lam
Dear Terry,
on page 281, last paragraph it says “we can reduce further to the case that $Z$ is odd”, which should probably read “$|Z|$ is odd” or “the order of $Z$ is odd”?
PS: I do not know if it is actually useful to report such minor typos?
[Correction added, thanks -T.]
19 November, 2014 at 1:50 pm
Lam
p. 293: $v_1,\hdots,v_n$ should probably be elements of $P$ instead of $V$ (volume).
p. 285: Corollary 5.25 should be Lemma 5.25.
[Correction added, thanks – T.]
19 November, 2014 at 1:52 pm
Lam
Example 7.19 p. 293: takes values in the generalized arithmetic progression $nP$ which have volume $n^dV$ (“which has”)
[Correction added, thanks – T.]
19 November, 2014 at 2:33 pm
Lam
In the proof of Lemma 4.35 p.181, it says “we are left with a remainder $R$ where all dissociated subsets of $S$ have cardinality $d$ or less”. Should $S$ be replaced with $R$?
[Correction added, thanks – T.]
10 December, 2014 at 5:58 am
Freddie Manners
Dear Prof Tao,
On p241, proof of Lemma 5.45, last line of the first displayed equation: I think
should read
as an estimate on the binomial coefficient.
[Correction added, thanks – T.]
10 December, 2014 at 6:25 am
Freddie Manners
Dear Prof Tao,
On p239, exercise 5.5.17: I don’t think this example works. The problem is that the midpoints of the quadrilateral , , , themselves form a parallelogram, and this rules out any non-standard Freiman homomorphisms to .
Replacing the generic quadrilateral with a generic pentagon in should fix it, I think, giving a universal ambient group of .
(Also, I think there is a typo
on the penultimate line: the first “2” should be a “4”.)
[Correction added, thanks – T.]
25 February, 2015 at 5:19 am
Quora
Are there any fields of mathematics that incorporate both Combinatorics and Number Theory?
Yes. The definition of mathematical fields is very fuzzy, but there are many questions which seem to belong to both “Number Theory” and “Combinatorics”. For example: in how many ways can a positive integer be represented as a sum of four integer sq…
16 June, 2015 at 1:11 pm
tomer shalev
Hello Professor Tao.
I am getting back to my thesis,
and was wondering about the solution of
exercise 2.1.1.
– how is it possible to come up with a uniform probability
function over the an infinite set of real numbers??
– what am I missing?
all the best
Tomer Shalev
[The exercise is referring to Lebesgue measure on the unit interval [0,1], which is a probability measure. -T.]
17 June, 2015 at 6:15 am
Tomer shalev
Can you please lay a sketch?
17 June, 2015 at 6:25 am
Tomer shalev
The probability to choose a number is zero according to the Lebesgue measure. And the number of representation of a number is maximized when the two sets differences only share zero element. Since differences have mostly non zero measure, but still u have non countable collection of pair wise numbers that have the same difference x = a-b.
[Uncountable sets can still have zero measure. For instance, the set has zero two-dimensional Lebesgue measure for any given number . -T.]
3 July, 2015 at 2:38 pm
tomer shalev
Hi Professor Tao. Regarding your comment at page 161, before the proof of lemma 4.13:
– you wrote that that P(A_1)***P(A_n) is the quantity one would
expect if random selection is involved conditioning on x =a_1 + .. + a_n,
restricted to these random sets.
– essentially meaning, that the representation function at a fixed point
is expected to be P(A_1)***P(A_n)*(|Z|^(n-1)) restricted to these sets.
the first part of P(A_1)***P(A_n) is understood, but the last part (|Z|^(n-1))
would describe the representation function at a fixes point where solutions
are unconditioned. I find it hard to believe and follow this claim.
please clarify, it is important for me to understand.
T
4 July, 2015 at 7:56 am
Terence Tao
For any fixed , the number of solutions to with is , because can be arbitrary elements of , and then is forced to be .
19 July, 2015 at 8:18 am
tomer shalev
Hi Prof Tao.
I have a question:
– page 163, exercise 4.3.4 : I understand how to prove it if the group is cyclic.
– does the fact, that the group has bilinear form that indues a isomorpism means, that this is always the case ( because the circle group is cyclic)?
all the best
Tomer
20 July, 2015 at 8:22 pm
A nonstandard analysis proof of Szemeredi’s theorem | What's new
[…] is basically thanks to an averaging argument of Varnavides; see for instance Chapter 11 of my book with Van Vu or this previous blog post for a discussion. We have removed the cases as they are trivial and […]
26 August, 2015 at 2:44 pm
A timeline of the polynomial method up-to combinatorial nullstellensatz | Anurag's Math Blog
[…] Terence Tao and Van Vu, Chapter 9 in Additive Combinatorics. […]
31 August, 2015 at 2:27 pm
Lam
Dear Terry,
I think there is a minor correction to add p.249 in the proof of Theorem 6.2. It says that “there are only elements of larger than ” but with the ordering, I think it should be . Then for all , and the following sum. Of course the result is the same though.
[Correction added, thanks – T.]
22 January, 2016 at 12:28 pm
Incidences Outside of Discrete Geometry – Some Plane Truths
[…] led to a variety of results in additive combinatorics that rely on incidences. Tao and Vu’s additive combinatorics book contains a full chapter that is dedicated to incidences. Konyagin and Shkredov’s recent […]
31 March, 2016 at 9:38 am
18.099 Transcript: Chang’s Theorem | Power Overwhelming
[…] of the 18.099 discrete analysis reading group at MIT, I presented section 4.7 of Tao-Vu’s Additive Combinatorics textbook. Here were the notes I used for the first part of my […]
4 April, 2016 at 9:42 am
18.099 Transcript: Bourgain’s Theorem | Power Overwhelming
[…] of the 18.099 Discrete Analysis reading group at MIT, I presented section 4.7 of Tao-Vu’s Additive Combinatorics textbook. Here were the notes I used for the second half of my […]
12 August, 2016 at 11:30 pm
Tom
This is probably my fault, but I am confused by exercise 1.10.3 of pag 48. It is asked to run carefully the central binomial reasoning to get $\sum_{p<N}log(p) \leq Nlog4+O(\sqrt(N))$. But I get something a lot smaller than square root: if K is even then I take care of primes between K and K/2 with the central binomial getting for them a factor Klog2, if K is odd I take care of the primes between K and K/2+1/2 with the biggest binomial getting a factor Klog2. So starting from N the worst thing that can happen is that I have to be always in the second case so that I get the upper bound Nlog2+(Nlog2/2+log2/2)+(Nlog2/4+log2/4+log2/2)+(..) < Nlog4+O(log N) since the other terms are all less then log2 and the number of them is less then $log_2(N)+1$. Where is the mistake? If there isn't why did you put such a bigger function as sqr(N)? Sorry and thanks in advance
[Ah, you’re right, the error does not need to be so large for the upper bound, only for the lower bound. An erratum has been added – T.]
4 September, 2016 at 7:16 am
Fat Bird
Dear Professor Tao,
Hello. I’m reading your book and find chapter 4 an extremely fascinating introduction to Fourier analytic methods. Yet there are two points on which I wonder if you could kindly elaborate a little.
The first is exercise 4.2.3 (p. 159), about “dyadic decomposition” just below the display. I suppose, following the previous hints, one should split the function into a sum, with each summand ranging within a dilation of a dyadic interval. In this regard, the strategy is unable to cover all scenarios, for example when, arranging values in ascending order, we have the subsequent one is always more than twice (or N times) the preceding. In this case, each dyadic (or N-adic) interval can only contain one value, and the logarithm estimate degrades.
The second has to do with the “Fourier concentration lemma”, in p. 182. In the proof, the sentence before the second display confuses me. To be precise, if one directly uses lemma 4.35, then he merely can find a union of dissociated sets plus a cube, instead of the promised cube alone. If one incorporated the dissociated sets into the cube, then I truly wonder how he could deal with the dimension. In addition, I have taken a glance at [48], but only found the proof of the latter part.
Sincerely I look forward to your reply.
4 September, 2016 at 11:00 am
Terence Tao
To avoid the problem of too many dyadic scales in Exercise 4.2.3, one should first remove from the portion coming from points where is very small, e.g. less than , as the contribution of this case can be treated by crude estimates (e.g. the triangle inequality).
For Lemma 4.36, one applies Lemma 4.35 with d taken to be slightly larger than the upper bound in the second display, then no dissociated sets will occur.
4 September, 2016 at 8:04 pm
Fat Bird
I get it. Thanks for your attention!
13 December, 2016 at 7:25 am
Anonymous
When is the revised addition forthcoming?
20 December, 2016 at 7:12 am
jura05
Dear Professor Tao!
On p.163, in Lemma 4.6:
In max(…) there should be instead of . We should apply Chernoff’s bound not for , but for .
Otherwise the bound is too weak for , .
[Correction added, thanks – T.]
20 December, 2016 at 1:40 pm
jura05
But I think that one should keep — with bound becomes OK.
[Corrected, thanks – T.]
8 April, 2017 at 7:55 pm
chaominglin
Dear Prof. Tao,
Here are a possible typo. On page 318, Ex: 3.3.4, is that |A|^{1/2} |B|^{3/2} |C|^{1/2} rather than |A|^{1/2} |B|^{1/2} |C|^{3/2}.
[Corrected, thanks – T.]
9 April, 2017 at 9:09 pm
chaominglin
Dear Prof. Tao,
Sorry, I made a typo too, that is Ex: 8.3.4, not Ex: 3.3.4.
Here are another possible typo. On page 318, Ex: 8.3.5, is that \Omega(|A|^{5/2}) instead of \Theta(|A|^{5/2}). I’ve checked the reference [79] and found out that the result is not that strong.
[Corrected, thanks – T.]
12 April, 2017 at 5:29 am
Sai Teja Somu
Page 166: I think the condition $\rho\leq 1$ should be added to Lemma 4.20 as (4.25) is false for $\rho >1$.
[Correction added, thanks – T.]
25 May, 2017 at 6:21 am
jura05
Dear Prof. Tao!
On p.179, ex.4.5.7, there should be instead of , because inequality is obvious.
[Correction added, thanks – T.]
7 July, 2018 at 1:45 pm
1% quasimorphisms and group cohomology | What's new
[…] one has a bounded derivative, as one can use the Bogulybov lemma (see e.g, Proposition 4.39 of my book with Van Vu) to find a large Bohr set inside . In applications, the set need not have bounded size, or even […]
24 February, 2019 at 5:13 pm
Walter Bridges
p. 5 and 6, Exc. 1.1.5 and 1.1.6 should be $\{0,1\}^d$, not $[0,1]^d$. (Of course, $\frac{1}{n}v_i$ isn’t necessarily defined for $v_i$ in an arbitrary additive group, but I still found it a bit confusing.
[Correction added, thanks – T.]
21 March, 2019 at 12:24 pm
Anonymous
I think the errata for p.1 is incorrect. I think the fix should have been \(E(|X|^2)-|E(X)|^2\), since that is what equals \(E(|X-E(X)|^2\) and since exercise 1.3.4 references complex-valued variables.
[Errata added for Ex 1.3.4. (The p1 definition is specifically for real random variables.)
10 September, 2019 at 8:06 am
Adam Brown
Exercise 6.3.5 is false as stated but the spirit of the problem remains intact. Let $A$ be Sidon and choose $C$ to be the dilation $C = 2 \cdot A$.
[Erratum added, thanks – T.]
16 December, 2019 at 12:34 am
anonymous
Up to page 233, better just to add the latest, only reason I pause is to keep the mind fresh, like multitasking in a factory. Will resume later.
—————————————————————————————————-
P83 Ex 2.5.6 Hint ends with small type, hence needs a large bracket, but due to small type has ended up with a small type bracket to be more clear than in my previous post.…
P109 ex2.8.1 usual, hint ends with small typo bracket yet started with regular bracket.
P178 ex 4.5.3 Usual bug, the hint starts with a normal parenthesis ends with a small type parenthesis, funny , how it just pops up occasionally. Actually puts a bit of pressure on to make sure they are all eliminated.
P179 Usual, ex 4.5.11 hint is closed with a small type bracket…
P196 near the top of page beneath “the claim follows” in the next sentence a parenthetical expression starting with (and …. Has no closing parenthesis, no idea where to end it although I am confident it occurs within the same sentence.
P206: usual, except for once it happened in a Lemma instead of an exercise the first sentence of the proof of Lemma5.10 a clause starting with using Lemma 5.3… ends with a small type parenthesis instead of a correct regular parenthesis.
—————————————————————————————————–
17 December, 2019 at 7:08 am
anonymous
Additive Combinatorics paperback most recent edition sourced from kindle;finalized errata based on a full peruse (PP1-512); minus self promoting vocab; please however delete the above four posts time permitting/when able to please. Won’t at all mind if the entire experience of ‘editing’ proves useless, if the errata proves useful, then a bonus. Good to have perused Additive Combinatorics.
——————————————–
P7 : equation 1.10 it’s a horrible expression to parenthesize perfectly, the covariance in between the two equals signs, if you just look at it twice you’ll see it needs just one more bracket in the first main bracketed expression E((Xi – E(Xi)) should be E((Xi – E(Xi))) ….
P34: below theorem 1.36 there is a paragraph starts with informally ends with a Y = equation…with high probability, …///well if you check that equation again the bracket either goes after E(Y)) hence closing the full side of that equation which seems pointless, or, around 1 + Ok,… I’m sure you’ll work it out, anyhow it’s missing a parenthesis…
P196: near the top of page beneath “the claim follows” in the next sentenced a parenthetical expression starting with (and …. Has no closing parenthesis, no idea where to end it although confident it occurs within the same sentence.
P242 : above equation 5.19 is says “Restricting this to elements of A”…I think the parenthesis needs closed after Tor(z) , so it looks like …”Tor(z)), we obtain”
P253 Ex 6.2.3 period outside parenthesized sentence.,
P263: not fully sure, could be deliberate but there is this “”(a,b) is a member of E)”” (is a member of is in mathematical notation, I just can’t write it in here, not in LaTex anyway, meaning to describe that curvy E symbol,) , that is stated a few times in consecutive equations, might be worth double checking can’t see where the opening parenthesis is from nor why it needs to be parenthesized, probably not due to interval/set notation/parenthesizing.
P355: Sentence mid page starts with “””Finally, when…””,….well, after ….“and hence”” is a summation with “”aixi)”, seems the parenthesis is closing something but hasn’t been opened, suspecting that based on other examples that it might need to be “(aixi)””…
P396: Near top of page it states an equation below “””from (10.16) we have””,….well in that equation it closes with a parenthesis that doesn’t seem to have an opening parenthesis, and same for the next equation below.
P402: middle page just below “”An application of the first moment method easily shows that””….is an equation with an unclosed parenthesis on the left side of the equation.
P430: near bottom of page is an exp() expression which needs just one more bracket, occurs right before,….. “”,then there exists a proper arithmetic progression P in Z of””….,…..
P439: In the second sentence of Proposition 11.12 the exp() expression after “”If”” has an unclosed opening parenthesis.
—————————————–
[Corrections added, thanks – T.]
16 April, 2020 at 4:44 pm
Anonymous
Hi, I noticed that Theorem 1.36 on page 34 (the Kim-Vu polynomial concentration inequality) is different from the main theorem in Kim and Vu’s paper [203]. Namely, the power of lambda is k in [203] and k-1/2 in Theorem 1.36. Is this a mistake?
16 April, 2020 at 7:30 pm
Terence Tao
One can gain an extra factor of 1/2 by a refinement of the arguments; see the remark at the end of Section 3 of [203].
18 May, 2020 at 11:07 pm
ConstantinK
I believe I can improve Proposition 2.42 to the following:
Proposition: Let be a multiplicative set so that for some . Then there exists a symmetric set so that $|S| \geq |A|/2$ and
for all integers .
Remark: Note that the size of does not depend on here.
Proof: Let consist of elements of so that
The set is symmetric and it holds that
Then it clearly holds that
using that $K \geq 1$. In particular $|S| \geq |A|/2$. The remainder of the proof is similar to previous arguments.
Q.E.D.
Remark: This is makes Proposition 2.43 a little more effective. On the other hand, I wasn't able to prove the analogous statement in the non-discrete setting.
21 June, 2020 at 6:27 am
ClemensB
Dear Prof. Tao,
I am currently trying to recover the proof of thm. 1.39., p. 36-37. While I am aware of the flaws in the proof printed, I fail to see how it can be salvaged using the errata above.
For the expectation of Y, I have found a solutution, which actually avoids using the suggested bound . For the derivatives, however, I do not manage to get the proper decay, even if I assume that for all $i$.
I assume that once I have established that part (with the lower bound on all variables) properly, I apply induction to the number of variables bounded from above by . I have some thoughts on how to do that, but it would probably depend on the rate of decay of my induction basis.
I also have not yet found a place to use your suggestion (comment https://terrytao.wordpress.com/books/additive-combinatorics/#comment-48142) that we can bound uniformly. Instead, I wish I could control .
I was hoping that maybe you could lay out a more detailed sketch on how to deal with this proof or give some idea how to properly approach it as I am at a loss.
Best regards,
Clemens
23 June, 2020 at 8:00 am
Terence Tao
The expected normalised derivative either vanishes, or is dominated by a sum of the form for some and , which can be estimated by a method similar to that used to estimate the expectation without derivatives.
The other suggestion was slightly incorrectly phrased. The idea is to use the fact that for any , the set of numbers that can be represented as the sum of terms in is still so sparse that any interval will only contain a bounded number of elements in this set, which greatly restricts the number of ways one can represent as the sum of terms in plus terms in .
7 July, 2020 at 5:24 am
ClemensB
Although being late with my reply, thank you very much for the help. The first part was quite doable with the hint.
I did not need the second part in all generality, so the bound for was enough (and also managable).
Best regards,
Clemens
30 September, 2020 at 1:42 am
Miquel
In exercise 4.1.5, I don’t see why the random variables are uncorrelated. According to the definition from wikipedia, one would expect , which isn’t true for .
Many thanks,
Miquel
1 October, 2020 at 7:58 am
Terence Tao
Usually the mathematical term “pairwise [X]” excludes the diagonal case, e.g., “ are pairwise uncorrelated” means “ are uncorrelated for “. Otherwise most uses of pairwise (e.g., pairwise independent, pairwise disjoint, pairwise orthogonal) would degenerate completely.
24 November, 2020 at 10:50 am
Marcel K. Goh
Hi Prof. Tao! I believe that on p. 449, on the 6th line from the bottom of the page, “positive upper progressions” should read “positive upper density”.
[Corrected, thanks – T.]
24 November, 2020 at 11:39 am
Marcel K. Goh
Also, at the bottom of p. 449, in the display math, I think that one of the two right parentheses in the middle should come after the limits of the sequence, to match the notation used in the first displayed equation on p. 450.
[Corrected, thanks – T.]
18 December, 2020 at 8:43 pm
Marcel Goh
Hi Prof. Tao, I have found a couple more small typos. On page 248, in the first line of the proof of Theorem 6.1, the word “probabilistic” is misspelled. On page 450, in the last line of the proof, I believe that “non-zero B” should read “non-zero n” and in the statement of Theorem 11.25 on page 452, either the polynomials should be vector-valued or else the should become in the last line.
[Errata added, thanks – T.]
15 January, 2021 at 6:47 am
Aditya Guha Roy
Prof. Tao on line 2 of page 155 (the exercise on linear phase function) I think there is a typo when you say for all , and I think that should be made for all
[Corrected, thanks – T.]
19 January, 2021 at 2:30 am
N is a number
I think after this one can simply show that is a homomorphism, and then the result follows easily.