Preprints in additive combinatorics and number theory

---

Math 254A home page - Arithmetic combinatorics (2003)

If you are interested in long arithmetic progressions in the primes, but don’t want to plunge directly into all the details, I can suggest the following surveys (in roughly increasing order of technical level of treatment):

• Terry Tao, “Long arithmetic progressions in the primes”- slides, aimed at undergraduate audience
• Terry Tao, “Long arithmetic progressions in the primes”- slightly more detailed version of previous
• Terry Tao, “Multiscale analysis of the primes” - slides
• Bryna Kra, “The Green-Tao theorem on arithmetic progressions in the primes: an ergodic point of view”
• Bernard Host, “Progressions arithmétiques dans les nombres premiers, d'après B. Green et T. Tao”. Seminaire Bourbaki,Mars 2005, 57eme annee, 2004-2005, no. 944.
• Terry Tao, “The dichotomy between structure and randomness, arithmetic progressions, and the primes” (ICM lecture)
• Terry Tao, “Obstructions to uniformity, and arithmetic patterns in the primes”
• Ben Green, “Long arithmetic progressions of primes”
• Terry Tao, “Arithmetic progressions and the primes - El Escorial lectures” (A harmonic analysis perspective)

Papers, and projects close to completion

Title	With	Status	Download
A sum-product estimate for finite fields, and applications	Jean Bourgain Nets Katz	GAFA 14 (2004), 27-57	math.CO/0301343
The primes contain arbitrarily long arithmetic progressions	Ben Green	Annals of Math. 167 (2008), 481-547	math.NT/0404188 quantitative bound slides more slides even more slides
New bounds for Szemeredi's Theorem, I: Progressions of length 4 in finite field geometries	Ben Green	To appear, Proc. Lond. Math. Soc.	math.NT/0509560
Restriction theory of the Selberg Sieve, with applications	Ben Green	Journal de Théorie des Nombres de Bordeaux 18 (2006), 137—172	math.NT/0405581
A quantitative ergodic theory proof of Szemer\'edi's theorem		Electron. J. Combin. 13 (2006). 1 No. 99, 1-49.	math.CO/0405251 short version
On random $\pm 1$ matrices: Singularity and Determinant	Van Vu	Random Structures and Algorithms 28 (2006),  1—23. [An extended abstracted is also in: STOC’05: Proceedings of the 37^th annual ACM symposium on the theory of computing, 431—440, New York 2005.]	math.CO/0411095
Arithmetic progressions and the primes		Collectanea Mathematica (2006), Vol. Extra., 37-88. [Proceedings, 7th International Conference on Harmonic Analysis and Partial Differential Equations]	math.NT/0411246
On the singularity probability of random Bernoulli matrices	Van Vu	J. Amer. Math. Soc. 20 (2007), 603-628	math.CO/0501313
The Gaussian primes contain arbitrarily shaped constellations		J. d’Analyse Mathematique 99 (2006), 109-176	math.CO/0501314
An inverse theorem for the Gowers $U^3(G)$ norm	Ben Green	Proc. Edin. Math. Soc. 51 (2008), 73-153	math.NT/0503014
A variant of the hypergraph removal lemma		J. Combin. Thy. A 113 (2006), 1257--1280	math.CO/0503572
Szemer\’edi’s regularity lemma revisited		Contrib. Discrete Math. 1 (2006), 8-28	math.CO/0504472 Short story version
Random symmetric matrices are almost surely non-singular	Kevin Costello Van Vu	Duke Math. J. 135 (2006), 395-413	math.PR/0505156
Obstructions to uniformity, and arithmetic patterns in the primes		Quarterly J. Pure Appl. Math. 2 (2006), 199-217 [Special issue in honour of John H. Coates, Vol. 1 of 2]	math.NT/0505402
Compressions, convex geometry, and the Freiman-Bilu theorem	Ben Green	Quarterly J. Math. 57 (2006), 495-504	math.NT/0511069
Inverse Littlewood-Offord theorems and the condition number of random discrete matrices	Van Vu	Annals of Math. 169 (2009), 595-632	math.PR/0511215
New bounds for Szemeredi's Theorem, II: A new bound for r_4(N)	Ben Green	Analytic number theory: essays in honour of Klaus Roth, W. W. L. Chen, W. T. Gowers, H. Halberstam, W. M. Schmidt, R. C. Vaughan, eds, Cambridge University Press, 2009. 180-204.	math.NT/0610604
New bounds for Szemeredi's Theorem, III: A polylog bound for r_4(N)	Ben Green	In preparation
Quadratic uniformity of the M\"obius function	Ben Green	Annales de l’Institut Fourier 58 (2009), 1863—1935.	math.NT/0606087
Linear equations in primes	Ben Green	To appear, Annals of Math.	math.NT/0606088
The dichotomy between structure and randomness, arithmetic progressions, and the primes		2006 ICM proceedings, Vol. I., 581--608	math.NT/0512114 slides
Product set estimates in noncommutative groups		To appear, Combinatorica	math.CO/0601431
A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal lemma		J. d’Analyse Mathematique 103 (2007), 1--45.	math.CO/0602037 slides
The ergodic and combinatorial approaches to Szemer\'edi's theorem		Centre de Recerches Math\'ematiques, CRM Proceedings and Lecture Notes Vol. 43 (2007), 145--193	math.CO/0604456
The primes contain arbitrarily long polynomial progressions	Tamar Ziegler	Acta Math. 201 (2008), 213—305.	math.NT/0610050
John-type theorems for generalized arithmetic progressions and iterated sumsets	Van Vu	Adv. in Math. 219 (2008), 428—449.	math.CO/0701005
A note on the Freiman and Balog-Szemeredi-Gowers theorems in finite fields	Ben Green	To appear, J. Aust. Math. Soc.	math.CO/0701585
On the condition number of a randomly perturbed matrix	Van Vu	Proceedings of the thirty-ninth annual ACM symposium on Theory of computing  (STOC) 2007, 248-255	math.PR/0703307 discussion slides
Freiman's theorem in finite fields via extremal set theory	Ben Green	To appear, Combinatorics, Probability, and Computing	math.CO/0703668 discussion
Szemerédi's theorem	Ben Green	Scholarpedia, p. 15573	Scholarpedia article discussion
Norm convergence of multiple ergodic averages for commuting transformations		Ergodic Theory and Dynamical Systems 28 (2008), 657-688	arXiv:0707.1117 discussion
Structure and randomness in combinatorics		Proceedings of the 48th annual symposium on Foundations of Computer Science (FOCS) 2007, 3-18	arXiv:0707.4269 discussion slides discussion of slides
Random Matrices: The circular Law	Van Vu	Communications in Contemporary Mathematics, 10 (2008), 261--307	arXiv:0708.2895 discussion
The quantitative behaviour of polynomial orbits on nilmanifolds	Ben Green	Submitted, Annals of Math.	arXiv:0709.3562 discussion van der Corput lemma
The M\"obius function is asymptotically orthogonal to nilsequences	Ben Green	Submitted, Annals of Math.	arXiv:0807.1736 discussion
The distribution of polynomials over finite fields, with applications to the Gowers norms	Ben Green	Submitted, Contributions to Discrete Mathematics	announcement arXiv:0711.3191 discussion
On the testability and repair of hereditary hypergraph properties	Tim Austin	To appear, Random Structures and Algorithms	talk arXiv:0801.2179 discussion
A remark on primality testing and decimal expansions		To appear, J. Aust. Math. Soc.	arXiv:0802.3361 discussion
On the permanent of random Bernoulli matrices	Van Vu	Adv. Math. 220 (2009), 657—669.	arXiv:0804.2632 discussion early version
Smooth analysis of the condition number and the least singular value	Van Vu	Submitted, Mathematics of Computation	arXiv:0805.3167 discussion
The sum-product phenomenon in arbitrary rings		To appear, Contributions to Discrete Mathematics	arXiv:0806.2497 discussion
Random matrices: Universality of ESDs and the circular law	Van Vu	Submitted, Annals of Probability	arXiv:0808.4898 discussion
From the Littlewood-Offord problem to the circular law: universality of the spectral distribution of random matrices	Van Vu	To appear, Bull. Amer. Math. Soc.	arXiv:0810.2994 discussion
The inverse conjecture for the Gowers norm over finite fields via the correspondence principle	Tamar Ziegler	Submitted, Analysis & PDE	arXiv:0810.5527 discussion
An inverse theorem for the uniformity seminorms associated with the action of $F^\omega$	Vitaly Bergelson Tamar Ziegler	To appear, GAFA	arXiv:0901.2602 discussion
A sharp inverse Littlewood-Offord theorem	Van Vu	Submitted, Random Structures and Algorithms	arXiv:0902.2357 discussion
Random matrices: the distribution of smallest singular values	Van Vu	To appear, GAFA	arXiv:0903.0614 discussion
Random matrices: universality of local eigenvalue statistics	Van Vu	Submitted, Acta Math.	arXiv:0906.0510 discussion

Short stories

Gowers' proof of Szemeredi's theorem for progressions of length 4	An ergodic transference theorem
A quantitative ergodic theory proof of Szemeredi’s theorem (abridged)	A quantitative bound for prime progressions of length k
Fourier analytic proofs of the prime number theorem	Szemeredi’s proof of Szemeredi’s theorem
Non-commutative sum set estimates	A remark on Goldston-Yildirim correlation estimates
Arithmetic Ramsey Theory	Menger’s theorem
The Roth-Bourgain theorem	Santalo’s inequality
Quadratic reciprocity via theta functions	Entropy sumset estimates
The parity problem in sieve theory	The crossing number inequality
Ratner's theorems	Dvir's proof of the finite field Kakeya conjecture
The van der Corput trick, and equidistribution on nilmanifolds	Tate's proof of the functional equation
Some notes on non-classical polynomials in finite characteristic	A counterexample to a strong polynomial Freiman-Ruzsa conjecture
Finite subsets of groups with no finite models	The Lucas-Lehmer test for Mersenne primes
The divisor bound	The correspondence principle and finitary ergodic theory
Szemeredi’s regularity lemma via random partitions	Szemeredi’s regularity lemma via the correspondence principle

Open questions

• Best bounds for cap sets
• Noncommutative Freiman theorem
• Triangle and diamond densities in  large dense graphs
• Effective Skolem-Mahler-Lech theorem
• The parity problem in sieve theory

Miscellaneous

• My book with Van Vu, titled “Additive combinatorics”, is currently in print; see this page for more details.
• Structure and randomness in the prime numbers (UCLA Science Faculty Research Colloquium, Jan 17 2007)

Back to my preprints page.