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

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.

Errata: Acta Math. 210, (2013), Page 403-404

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

erratum

The M\"obius function is asymptotically orthogonal to nilsequences

Ben Green

Annals of Math., 175 (2012), 541--566 

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

Random Structures and Algorithms

37 (2010), 525-539

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, 32 (2012), 363-372

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

 GAFA  21 (2011), 774-819

arXiv:1005.1881

discussion

Strongly dense free subgroups of semisimple algebraic groups

Emmanuel Breuillard

Ben Green

Bob Guralnick

Israel J. Math. 192 (2012), 347-379

arXiv:1010.4259

discussion

Expansion in simple groups of Lie type

Emmanuel Breuillard

Ben Green

Bob Guralnick

J. Europ. Math. Soc. 17 (2015), 1367-1434

arXiv:1309.1975

discussion

An inverse theorem for the Gowers U^{s+1}[N] norm

Ben Green

Tamar Ziegler

Annals of Math. 176 (2012), no. 2, 1231–1372.

(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

J. d’Analyse Mathematique 117 (2012), 133-186

arXiv:1012.3509

discussion

Outliers in the spectrum of iid matrices with bounded rank permutations

Probability theory and related fields

155 (2013), 231-263

arXiv:1012.4818

discussion

The inverse conjecture for the Gowers norm over finite fields in low characteristic

Tamar Ziegler

Annals of Combinatorics 16 (2012), 121-188

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

Random matrices: Theory and Applications 1 (2012), 1150001

arXiv:1103.2801

discussion

An incidence theorem in higher dimensions

Jozsef Solymosi

 Disc. Comp. Geom. 48 (2012), 255-280

arXiv:1103.2926

discussion

Noncommutative sets of small doubling

European Journal of Combinatorics 34 (2013), 1459-1465

arXiv:1106:2267

discussion

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

Christian Elsholtz

 J. Aust. Math. Soc. 94 (2013), 50-105

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

 European Journal of Combinatorics 34 (2013), 1287-1292

arXiv:1112.4174

discussion

Random matrices: Sharp concentration of eigenvalues

Van Vu

 Random matrices: Theory and Applications 2 (2013), 1350007

arXiv:1201.4789

discussion

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

Mathematics of Computation 83 (2014), 997-1038

arXiv:1201.6656

discussion

Random matrices:  The Universality phenomenon for Wigner ensembles

Van Vu

In: Modern Aspects of Random Matrix Theory, Proceedings of Symposia in Applied Mathematics 72 (2013), V. Vu Editor, 121--172.

arXiv:1202.0068

discussion

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

Probability Theory and Related Fields 157 (2013), 81-106

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

Van Vu

Annals of Prob. 43 (2015), 782-874

arXiv:1206:1893

discussion

On sets defining few ordinary lines

Ben Green

Disc. Comp. Geom. 50 (2013), 409-468

arXiv:1208.4714

discussion

Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets

To appear,  Disc. Comp. Geom. 

arXiv:1211.2894

discussion

Multiple recurrence in quasirandom groups

Vitaly Bergelson

Geom. Func. Anal. 24 (2014), 1-48

arXiv:1211.6372

discussion

Mixing for progressions in nonabelian groups

Forum of Mathematics, Sigma 1 (2013), e2

arXiv:1212.2586

discussion

Multiple recurrence and convergence results associated to $\F_{p}^{\omega}$-actions

Vitaly Bergelson

Tamar Ziegler

To appear, J. d’Analyse Mathematique

arXiv:1305.4717

discussion

A multi-dimensional Szemer\'edi theorem for the primes via a correspondence principle

Tamar Ziegler

Israel J. Math., Feb 2015

arXiv:1306.2886

discussion

Local universality of zeroes of random polynomials

Van Vu

International Mathematics Research Notices 2014;

doi: 10.1093/imrn/rnu084

arXiv:1307.4357

discussion

Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory

EMS surveys in the mathematical sciences 1 (2014), 1--46

arXiv:1310.6482

discussion

New equidistribution results of Zhang type

D.H.J. Polymath

Algebra & Number Theory 8-9 (2014), 2067--2199

arXiv:1402.0811

discussion

Variants of the Selberg sieve, and bounded intervals containing many primes

D.H.J. Polymath

Research in the Mathematical Sciences 1:12 (2014)

arXiv:1407.4897

discussion

Large gaps between consecutive prime numbers

Kevin Ford

Ben Green

Sergei Konyagin

Submitted, Annals Math.

arXiv:1408.4505

discussion

Narrow progressions in the primes

Tamar Ziegler

To appear, “Analytic Number Theory” in honor of Helmut Maier’s 60th birthday

arXiv:1409.1327

discussion

The “bounded gaps between primes” Polymath project - a retrospective

D.H.J. Polymath

Newsletter of the European Mathematical Society, Dec 2014. Issue 94, 13--23

arXiv:1409.8361

discussion

The Elliott-Halberstam conjecture implies the Vinogradov least quadratic nonresidue conjecture

Algebra & Number Theory 9-4 (2015), 1005--1034. DOI 10.2140/ant.2015.9.1005

arXiv:1410.7073

discussion

Random matrices have simple spectrum

Van Vu

To appear, Combinatorica

arXiv:1412.1438

discussion

Long gaps in the primes

Kevin Ford

Ben Green

Sergei Konyagin

James Maynard

Submitted

arXiv:1412.5029

discussion

An averaged form of Chowla’s conjecture

Kaisa Matomaki

Maksym Radziwill

Submitted, Algebra & Number Theory

arXiv:1503.05121

discussion

Random matrices: tail bounds for gaps between eigenvalues

Hoi Nguyen

Van Vu

Submitted

arXiv:1504.00396

discussion

Inverse theorems for sets and measures of polynomial growth

Submitted, Quart. J. Math.

arXiv:1507:01276

discussion

Sign patterns for the Liouville and Mobius functions

Kaisa Matomaki

Maksym Radziwill

Submitted, Forum of Mathematics, Sigma

arXiv:1509.01545

discussion

The logarithmically averaged Chowla and Elliott conjectures for two-point correlations

Submitted, Forum of Mathematics, Pi

arXiv:

discussion

The Erdos discrepancy problem

Submitted, Discrete Analysis

arXiv:1509.05363

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

Back to my preprints page.