Finite-interval Szemerédi input for Varnavides counting
ProvedGreenTao.finite_interval_szemerediadditive-combinatoricsarithmetic-progressionsgreen-tao
Fix an integer and a real number . There is an integer such that every set with contains an arithmetic progression of length and positive common difference:
This finite-interval existence statement is the qualitative input used by the affine-window proof of Varnavides counting. The length depends only on and . It is an interval form of Szemerédi’s theorem, expressed with zero-based indices for pulling sets back along affine maps.
Preamble
import Mathlib
Formal statement
theorem GreenTao.finite_interval_szemeredi (k : ℕ) (hk : 3 ≤ k) (δ : ℝ) (hδ : 0 < δ) :
∃ L : ℕ, k ≤ L ∧
∀ S : Finset ℕ, S ⊆ Finset.range L → δ * (L : ℝ) ≤ (S.card : ℝ) →
∃ a d : ℕ, 0 < d ∧ a + (k - 1) * d < L ∧
∀ j < k, a + j * d ∈ S := by sorrySource
E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975). Finite-interval form of the qualitative theorem; compare Green–Tao, https://arxiv.org/html/math/0404188v6, §2 Proposition 2.1 and the Varnavides discussion after Proposition 2.3. The proof imports the existing platform theorem Erdos142.erdos_139_szemeredi (7653083f-b258-4a2c-a86d-f689b72bf0ff) rather than reproving it.