Varnavides affine-window counting from finite Szemerédi
ProvedGreenTao.affine_window_varnavidesadditive-combinatoricsarithmetic-progressionsgreen-tao
Let satisfy , and let . Assume every of cardinality at least contains a -term arithmetic progression with positive common difference. For every prime and every with ,
The count includes zero common differences and counts ordered pairs . This is the affine-window counting step in the Varnavides argument, separating the combinatorial averaging from the finite-interval Szemerédi input.
Preamble
import Definitions.Def_GreenTao_Pseudorandom import Mathlib open scoped BigOperators Topology open Filter GreenTao
Formal statement
theorem GreenTao.affine_window_varnavides (k L : ℕ) (hk : 3 ≤ k) (hkL : k ≤ L)
(δ : ℝ) (hδ : 0 < δ)
(hinterval : ∀ S : Finset ℕ, S ⊆ Finset.range L →
δ / 2 * (L : ℝ) ≤ (S.card : ℝ) →
∃ a d : ℕ, 0 < d ∧ a + (k - 1) * d < L ∧ ∀ j < k, a + j * d ∈ S)
(m : ℕ+) (hm : Nat.Prime (m : ℕ)) (hLm : L ≤ (m : ℕ))
(A : Finset (ZMod (m : ℕ))) (hA : δ * (m : ℝ) ≤ (A.card : ℝ)) :
δ / (2 * (L : ℝ) ^ 2) ≤
GreenTao.apAvg k (fun x => if x ∈ A then 1 else 0) := by sorrySource
P. Varnavides, On certain sets of positive density, J. London Math. Soc. 34 (1959), 358–360. General k-term affine-window counting argument discussed in Green–Tao, https://arxiv.org/html/math/0404188v6, §2 after Proposition 2.3. This auxiliary conditional formulation makes the finite-interval input and the resulting constant δ/(2L²) explicit; it is not a verbatim numbered theorem of the source.