A uniform set with fewer than expected arithmetic progressions of length 4 (Q2220982): Difference between revisions

Proofs of \textit{E. Szemerédi} [Acta Arith. 27, 199--245 (1975; Zbl 0303.10056)] include a -- possibly deeply buried -- notion of randomness for a set of integers that implies the set contains as many arithmetic progressions of a given length as a truly random set would. For progressions of length \(3\) this may be expressed using Fourier analysis of the characteristic function of a subset of \(\{1,\ldots,N\}\) identified with the group \(\mathbb{Z}/N\mathbb{Z}\) in order to provide a group structure, specifically in terms of the Fourier coefficients being small away from zero. The author generalized earlier work of \textit{K. F. Roth} [J. Lond. Math. Soc. 28, 104--109 (1953; Zbl 0050.04002)] to give a new approach to Szemerédi's theorem in \textit{W. T. Gowers} [Geom. Funct. Anal. 11, No. 3, 465--588 (2001); Erratum 11, No. 4, 869 (2001; Zbl 1028.11005)] where a conjecture was made concerning the quantitative relationship between bounds on the Fourier coefficient and the number of arithmetic progressions of length \(3\) and \(4\) in the set. Specifically, a subset \(A\) of \(\{1,\ldots,N\}\) identified with \(\mathbb{Z}/N\mathbb{Z}\) is said to be \(c\)-uniform if \(\vert\widehat{A}(r)\vert\le c\) for all non-zero \(r\), and the conjecture formulated in the above paper was that a set \(A\) of density \(\delta>0\) that is \(c\)-uniform contains at least \((\delta^4-c')N^2\) many quadrangles of the set \((x,d+d,x+2d,x+3d)\), where \(c'\to0\) as \(c\to 0\). Motivation for this conjecture, and the context in which to view it, are discussed. The conjecture is then disproved in this paper, via the construction of a set \(A\) with density \(\frac12+o(1)\) which has the property that its Fourier coefficients are very small away from zero, but if \(x\) and \(d\) are chosen uniformly at random, then the probability that all the elements \(x\), \(x+d\), \(x+2d\), \(x+3d\) all lie in \(A\) is at most \(\frac{1}{16}-c\) for some absolute positive constant \(c\). Related open problems for arithmetic progressions of length \(4\) are formulated.