Arithmetic progressions and generalized von Neumann bounds

Fix an integer k at least three and a prime p greater than k, and work in G equal to a finite-dimensional vector space over that prime field. The k-term progression average weights the points x, x+d, up through x+(k−1)d by possibly different functions. Assume every function has magnitude at most one. In this setting the absolute average is at most the smallest U to the k−1 norm among the participating functions. The condition p greater than k is a convenient sufficient way to keep all small coefficient differences invertible.

Repeated Cauchy–Schwarz removes bounded factors while introducing new difference variables, eventually producing a cube average of the selected function. Changes of variables use the invertibility of the progression coefficients’ differences, which is why ambient arithmetic belongs in the theorem statement. A version for arbitrary systems of linear forms needs an appropriate complexity analysis, not merely the number of displayed forms. Likewise, replacing bounded functions by unbounded sparse majorants requires additional pseudorandomness assumptions and a relative counting theorem.

Let A have density alpha and write its indicator as alpha plus a balanced function f. Since alpha lies between zero and one, f has magnitude at most one. Expand the product in the progression average. The term taking alpha from every position is alpha to the power k. Each of the other terms contains at least one copy of f, and all its factors remain bounded by one. Generalized von Neumann bounds each such term by the U to the k−1 norm of f, after including any constant factors.

There are two to the power k minus one possible nonconstant terms, giving the convenient error estimate below. Some terms vanish or admit a better alpha-dependent bound, so this estimate is usually not sharp. Its advantage is a transparent sufficient condition for a useful count. It would be incorrect to keep only the term containing f in every position: the mixed terms are part of the exact multilinear expansion and must be bounded or shown to vanish individually.

For d=0 every point of A produces a diagonal pair, contributing alpha divided by the size of G to the normalized average. Because p exceeds k, a nonzero d makes all k points distinct: if two positions agreed, a nonzero scalar smaller than p would annihilate d. Thus a lower bound strictly larger than the diagonal contribution guarantees a genuinely nontrivial progression. Mere positivity does not suffice, since every nonempty set already has diagonal contributions.

A dense set can fail the small-uniformity assumption, so the inequality alone does not prove Szemerédi’s theorem. Rather, it separates a counting regime from a structural regime: either the balanced norm is small enough to count progressions, or it signals higher-order structure that must be analyzed by other tools. The uniformity order depends on the progression length in this sufficient bound. An arbitrary fixed Fourier test does not automatically control all longer patterns, as quadratic phases already demonstrate.