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):

  1. Terry Tao, “Long arithmetic progressions in the primes”- slides, aimed at undergraduate audience
  2. Terry Tao, “Long arithmetic progressions in the primes”- slightly more detailed version of previous
  3. Terry Tao, “Multiscale analysis of the primes” - slides
  4. Bryna Kra, “The Green-Tao theorem on arithmetic progressions in the primes: an ergodic point of view
  5. 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.
  6. Terry Tao, “The dichotomy between structure and randomness, arithmetic progressions, and the primes” (ICM lecture)
  7. Terry Tao, “Obstructions to uniformity, and arithmetic patterns in the primes
  8. Ben Green, “Long arithmetic progressions of primes
  9. 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 37thannual 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

Annals of Math. Volume 175 (2012), Issue 2, 465-540.

arXiv:0709.3562

discussion

van der Corput lemma

The M\"obius function is asymptotically orthogonal to nilsequences

Ben Green

To appearAnnals 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

 J. Aust. Math. Soc.

91 (2011), 405-413

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 appearRandom 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

Annals of  Math. 175 (2012), 1283-1327.

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

Annals of Probability 40 (2012), 1283--1315.

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

Combinatorica, 2012

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

To appear, 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

Mathematics of Computation 81 (2012), 1233-1246

arXiv:1009.3956

discussion

Large values of the Gowers-Host-Kra seminorms

Tanja Eisner

To appearJ. d’Analyse Mathematique

arXiv:1012.3509

discussion

Outliers in the spectrum of iid matrices with bounded rank permutations

To appearProbability 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

Electronic Journal of Probability 16 (2011), 2104-2121

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

To appear, Disc. Comp. Geom.

arXiv:1103.2926

discussion

Noncommutative sets of small doubling

To appear, European Journal of Combinatorics

arXiv:1106:2267

discussion

Counting the number of solutions to the Erdös-Straus equation on unit fractions

Christian Elsholtz

To appear,  J. Aust. Math. Soc.

arXiv:1107:1010

discussion

update

The structure of approximate groups

Emmanuel Breuillard

Ben Green

To appearPub. IHES

arXiv:1110.5008

discussion

A central limit theorem for the determinant of a Wigner matrix

Van Vu

Adv. Math. 231 (2012), 74-101

arXiv:1111.6300

discussion

Random matrices: The Four Moment Theorem for Wigner matrices

Van Vu

Submitted, MSRI Book series

arXiv:1112.1976

discussion

A nilpotent Freiman dimension lemma

Emmanuel Breuillard

Ben Green

To appearEuropean Journal of Combinatorics 

arXiv:1112.4174

discussion

Random matrices: Sharp concentration of eigenvalues

Van Vu

Submitted, Electronic Journal of Probability

arXiv:1201.4789

discussion

Every odd number greater than 1 is the sum of at most five primes

To appearMathematics of Computation 

arXiv:1201.6656

discussion

Random matrices:  The Universality phenomenon for Wigner ensembles

Van Vu

Submitted, AMS Book series

arXiv:1202.0068

discussion

The asymptotic distribution of a single eigenvalue gap of a Wigner matrix

To appear, Probability Theory and Related Fields

arXiv:1203.1605

discussion

E pluribus unum: from complexity, universality

Daedalus 141 (3) (Summer 2012)

Web version

New bounds for Szemeredi's theorem, Ia: Progressions of length 4 in finite field geometries revisited

Ben Green

Submitted, Proc. Lond. Math. Soc.

arXiv:1205.1330

discussion

Random matrices: Universality of local spectral statistics of non-Hermitian matrices

Submitted, Duke Math. J.

arXiv:1206:1893

discussion

On sets defining few ordinary lines

Ben Green

Submitted, Disc. Comp. Geom.

arXiv:1208.4714

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

  1. Best bounds for cap sets
  2. Noncommutative Freiman theorem
  3. Triangle and diamond densities in  large dense graphs
  4. Effective Skolem-Mahler-Lech theorem
  5. The parity problem in sieve theory

Miscellaneous

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

Back to my preprints page.