Sets containing arbitrarily long arithmetic progressions
DefinitionGreenTaoPort_Wikipedia_SzemeredisTheorem_Statementarithmetic-progressionscombinatoricsgreen-tao-port-8822
For a set , the predicate says that contains an arithmetic progression of every finite length:
Here is the first term, is the common difference, is the requested length, and is the position in the progression. The positive difference excludes constant progressions. The case is allowed and has an empty membership condition. Applied to the set of natural primes, this is the arithmetic-progression property asserted by the Green–Tao theorem.
Definition code
import Mathlib.Algebra.BigOperators.Group.Finset.Basic import Mathlib.Algebra.Group.Indicator import Mathlib.Data.Real.Archimedean import Mathlib.Order.LiminfLimsup set_option autoImplicit true set_option relaxedAutoImplicit false set_option maxSynthPendingDepth 3 /-! # The Lean Eval statement of Szemerédi's theorem This module records the definitions used by the Lean theorem-proving evaluation. Keeping them in a small module makes the public theorem's type easy to compare verbatim with the challenge statement. -/ namespace SzemeredisTheorem open scoped BigOperators /-- A set contains arithmetic progressions of every finite length. -/ def ContainsArbitraryAPs (A : Set ℕ) : Prop := ∀ k : ℕ, ∃ a b : ℕ, 1 ≤ b ∧ ∀ j : ℕ, j < k → a + b * j ∈ A end SzemeredisTheorem
Source