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	Proc. Lond. Math. Soc. 98 (2009), 365-392	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^thannual 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
Szemeredi'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	Annals of Math. 171 (2010), 1753-1850	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		Combinatorica 28 (2008), 547-594	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	J. Aust. Math. Soc. 86 (2009), 61-74.	math.CO/0701585
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	Combin. Probab. Comput. 18 (2009), no. 3, 335--355	math.CO/0703668 discussion
Szemeredi'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	To appear, Annals of Math.	arXiv:0709.3562 discussion van der Corput lemma
The M\"obius function is asymptotically orthogonal to nilsequences	Ben Green	To appear, Annals of Math.	arXiv:0807.1736 discussion
The distribution of polynomials over finite fields, with applications to the Gowers norms	Ben Green	Contrib. Discrete Math. 4 (2009), no. 2, 1--36.	announcement arXiv:0711.3191 discussion
On the testability and repair of hereditary hypergraph properties	Tim Austin	Random Structures and Algorithms 36 (2010), 373-463	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	Mathematics of Computation, 79 (2010), 2333-2352	arXiv:0805.3167 discussion
The sum-product phenomenon in arbitrary rings		Contrib. Discrete Math. 4 (2009), no. 2, 59--82.	arXiv:0806.2497 discussion
Random matrices: Universality of ESDs and the circular law	Van Vu Manjunath Krishnapur(appendix)	Annals of Probability 38 (2010), no. 5, 2023--2065.	arXiv:0808.4898 discussion
From the Littlewood-Offord problem to the circular law: universality of the spectral distribution of random matrices	Van Vu	Bull. Amer. Math. Soc. 46 (2009), 377-396	arXiv:0810.2994 discussion
The inverse conjecture for the Gowers norm over finite fields via the correspondence principle	Tamar Ziegler	Analysis & PDE 3 (2010), 1-20	arXiv:0810.5527 discussion
An inverse theorem for the uniformity seminorms associated with the action of $F^\omega$	Vitaly Bergelson Tamar Ziegler	Geom. Funct. Anal. 19 (2010), no. 6, 1539--1596.	arXiv:0901.2602 discussion
A sharp inverse Littlewood-Offord theorem	Van Vu	To appear, Random Structures and Algorithms	arXiv:0902.2357 discussion
Random matrices: the distribution of smallest singular values	Van Vu	GAFA, 20 (2010), 260-297	arXiv:0903.0614 discussion
Random matrices: universality of local eigenvalue statistics	Van Vu	Acta Math 206 (2011), 127-204	arXiv:0906.0510 discussion
An equivalence between inverse sumset theorems and inverse conjectures for the U^3 norm	Ben Green	Math. Proc. Camb. Phil. Soc. 149 (2010), 1-19	arXiv:0906.3100 discussion
Freiman.s theorem for solvable groups		Contributions to Discrete Mathematics 5 (2010), no. 2, 137.184,	arXiv:0906.3535 discussion
Sumset and inverse sumset theorems for Shannon entropy		Combinatorics, Probability, and Computing 19 (2010), 603-639	arXiv:0906.4387 discussion
Bulk universality for Wigner hermitian matrices with subexponential decay	Laszlo Erdos Jose Ramírez Benjamin Schlein Van Vu Horng-Tzer Yau	Math. Res. Lett. 17 (2010), 793-794	arXiv:0906.4400 discussion
Random matrices: universality of local eigenvalue statistics up to the edge	Van Vu	Communications in Mathematical Physics, 298 (2010), 549-572	arXiv:0908.1982 discussion
A remark on partial sums involving the Mobius function		Bull. Aust. Math. Soc. 81 (2010), 343-349	arXiv:0908:4323 discussion
A new proof of the density Hales-Jewett theorem	D.H.J. Polymath	An Irregular Mind: Szemeredi is 70, Bolyai Society Mathematical Studies, 689-754	arXiv:0910.3926 discussion
A finitary version of Gromov's polynomial growth theorem	Yehuda Shalom	GAFA 20 (2010), no. 6, 1502.1547.	arXiv:0910.4148 discussion
An inverse theorem for the Gowers U^4 norm	Ben Green Tamar Ziegler	Glasgow Mathematical Journal 53 (2011), no. 1, 1.50	arXiv:0911.5681 discussion
Random covariance matrices: Universality of local statistics of eigenvalues	Van Vu	Submitted, Annals of Probability	arXiv:0912.0966 discussion
Nonconventional ergodic averages and multiple recurrence for von Neumann dynamical systems	Tim Austin Tanja Eisner	Pacific Journal of Mathematics 250-1 (2011), 1--60. DOI 10.2140/pjm.2011.250.1	arXiv:0912.5093 discussion
Linear approximate groups	Emmanuel Breuillard Ben Green	Electronic research announcements 17 (2010), 57-67	arXiv:1001.4570 discussion
An arithmetic regularity lemma, an associated counting lemma, and applications	Ben Green	An Irregular Mind: Szemeredi is 70, Bolyai Society Mathematical Studies, 261-334	arXiv:1002.2028 discussion
Yet another proof of Szemeredi's theorem	Ben Green	An Irregular Mind: Szemeredi is 70, Bolyai Society Mathematical Studies, 335-342	arXiv:1002.2254 discussion
The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and F\"uredi	Van Vu	To appear, Combinatorica	arXiv:1002.5028 discussion
Suzuki groups as expanders	Emmanuel Breuillard Ben Green	Groups, Geometry, and Dynamics 5 (2011), no. 2, 281.-299.	arXiv:1005.0782 discussion
Approximate subgroups of linear groups	Emmanuel Breuillard Ben Green	To appear, GAFA	arXiv:1005.1881 discussion
Strongly dense free subgroups of semisimple algebraic groups	Emmanuel Breuillard Ben Green Bob Guralnick	To appear, Israel J. Math.	arXiv:1010.4259 discussion
Expansion in simple groups of Lie type	Emmanuel Breuillard Ben Green Bob Guralnick	In preparation
An inverse theorem for the Gowers U^{s+1}[N] norm	Ben Green Tamar Ziegler	Submitted, Annals of Math. (Announcement: Submitted, Electronic Research Announcements)	announcement announcement discussion arXiv:1009.3998 discussion
Random matrices: Localization of the eigenvalues and the necessity of four moments	Van Vu	Acta Mathematica Vietnamica 36 (2011), 431--449	arXiv:1005.2901 discussion
Deterministic methods to find primes	Ernie Croot Harald Helfgott	To appear, Mathematics of Computation	arXiv:1009.3956 discussion
Large values of the Gowers-Host-Kra seminorms	Tanja Eisner	To appear, J. d.Analyse Mathematique	arXiv:1012.3509 discussion
Outliers in the spectrum of iid matrices with bounded rank permutations		To appear, Probability theory and related fields	arXiv:1012.4818 discussion
The inverse conjecture for the Gowers norm over finite fields in low characteristic	Tamar Ziegler	To appear, Annals of Combinatorics	arXiv:1101.1469 discussion
A note on approximate subgroups of GL_n(C) and uniformly nonamenable groups	Emmanuel Breuillard Ben Green	Submitted,	arXiv:1101.2552 discussion
The Wigner-Dyson-Mehta bulk universality conjecture for Wigner matrices	Van Vu	To appear, Electronic Journal of Probability	arXiv:1101.5707 discussion
Random matrices: Universal properties of Eigenvectors	Van Vu	To appear, Random matrices: Theory and Applications	arXiv:1103.2801 discussion
An incidence theorem in higher dimensions	Jozsef Solymosi	Submitted, Disc. Comp. Geom.	arXiv:1103.2926 discussion
Noncommutative sets of small doubling		Submitted, European Journal of Combinatorics	arXiv:1106:2267 discussion
Counting the number of solutions to the Erdös-Straus equation on unit fractions	Christian Elsholtz	Submitted, J. Aust. Math. Soc.	arXiv:1107:1010 discussion update
The structure of approximate groups	Emmanuel Breuillard Ben Green	Submitted, Pub. IHES	arXiv: 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

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.