op_153_square_diff_free_four_card_le_two
Every subset $A \subseteq \{1, 2, 3, 4\}$ whose distinct elements have difference not equal to $n^2$ for any positive integer $n$ has cardinality at most 2.
Statement
theorem op_153_square_diff_free_four_card_le_two
(A : Finset ℕ) (hA : A ⊆ Finset.Icc 1 4)
(hdiff : ∀ a ∈ A, ∀ b ∈ A, a ≠ b → ¬ ∃ n : ℕ, 0 < n ∧ (a : ℤ) - b = (Polynomial.X ^ 2 : Polynomial ℤ).eval (n : ℤ)) :
A.card ≤ 2- Source
- arXiv:2610.07765 Corollary 1.2 -- A new bound for the Furstenberg--Sárközy theorem using the van der Corput property
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- op_153_square_diff_free_five_card_le_twoEvery subset $A \subseteq \{1, 2, 3, 4, 5\}$ whose distinct elements have difference not equal to $n^2$ for any positive integer $n$ has…
Read back from the Lean
For any finite set $A$ of natural numbers, if $A \subseteq \{1, 2, 3, 4\}$ (i.e., Finset.Icc 1 4) and for every pair of distinct elements $a, b \in A$, there is no natural number $n > 0$ such that $(a : \mathbb{Z}) - (b : \mathbb{Z})$ equals the polynomial $X^2 \in \mathbb{Z}[X]$ evaluated at $n$ (as an integer), then the cardinality of $A$ is at most 2.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem is proved by constructing an injection from A into the two-element set {1, 2}. Because distinct elements of A cannot differ by a square, A cannot contain consecutive integers since their difference is 1 = 1². The map f(x) = ⌊(x + 1) / 2⌋ collapses {1, 2} to 1 and {3, 4} to 2; since A contains at most one element from each of these two pairs, f is injective on A, which implies |A| ≤ |{1, 2}| = 2.
Define a pairing map f(x) = ⌊(x + 1) / 2⌋.
We define f : ℕ → ℕ by f(x) = (x + 1) / 2 using integer division, which sends {1, 2} to 1 and {3, 4} to 2.
let f : ℕ → ℕ := fun x => (x + 1) / 2
No two consecutive integers can both belong to A.
Suppose for contradiction that both a and a + 1 belong to A. Since a + 1 ≠ a, their difference is (a + 1) - a = 1 = 1². Setting n = 1 > 0 provides a positive integer whose square equals the difference, contradicting the hypothesis hdiff that no two distinct elements of A have difference equal to a positive square.
have hno : ∀ a ∈ A, a + 1 ∈ A → False := by intro a ha ha1 have h := hdiff (a + 1) ha1 a ha (by omega) apply h refine ⟨1, by norm_num, ?_⟩ simp
The map f sends every element of A into {1, 2}.
From A ⊆ {1, 2, 3, 4}, every a ∈ A satisfies 1 ≤ a ≤ 4. Evaluating f on each of the four possible values gives f(1) = 1, f(2) = 1, f(3) = 2, and f(4) = 2, so f(a) ∈ {1, 2} in all cases.
uses
Finset.coe_insert,Finset.coe_singleton,Set.mem_insert_iff,Set.mem_singleton_iff,Finset.mem_Icchave hmap : Set.MapsTo f ↑A ↑({1, 2} : Finset ℕ) := by intro a ha simp only [Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff, Set.mem_singleton_iff] have ha' := hA ha simp only [Finset.mem_Icc] at ha' have ha1 : 1 ≤ a := ha'.1 have ha4 : a ≤ 4 := ha'.2 interval_cases a <;> norm_num [f]
The map f is injective on A.
Assume for contradiction that distinct elements a, b ∈ A satisfy f(a) = f(b). Since 1 ≤ a, b ≤ 4, there are 16 possibilities for the pair (a, b). For pairs with a = b, this contradicts a ≠ b. For pairs with f(a) ≠ f(b) (one in {1, 2} and the other in {3, 4}), this contradicts f(a) = f(b). The remaining pairs are {1, 2} and {3, 4}, both of which consist of consecutive integers and are ruled out because no two consecutive integers can both belong to A.
uses
Finset.mem_Icchave hinj : Set.InjOn f ↑A := by intro a ha b hb hfab by_contra hne have ha' := hA ha have hb' := hA hb simp only [Finset.mem_Icc] at ha' hb' have ha1 : 1 ≤ a := ha'.1 have ha4 : a ≤ 4 := ha'.2 have hb1 : 1 ≤ b := hb'.1 have hb4 : b ≤ 4 := hb'.2 interval_cases a <;> interval_cases b <;> simp_all [f]
The cardinality of A is at most 2.
Since f maps A into {1, 2} and is injective on A, the cardinality of A is at most the cardinality of {1, 2}, which is 2.
uses
Finset.card_le_card_of_injOnexact Finset.card_le_card_of_injOn f hmap hinj
Finset.coe_insert- Coercing the insertion of an element into a finite set to a set is equal to inserting the element into the coerced set.
Finset.coe_singleton- Coercing a singleton finite set to a set yields the singleton set.
Set.mem_insert_iff- An element belongs to insert a s if and only if it equals a or belongs to s.
Set.mem_singleton_iff- An element belongs to the singleton set {b} if and only if it equals b.
Finset.mem_Icc- An element belongs to the closed interval [a, b] if and only if a ≤ x and x ≤ b.
Finset.card_le_card_of_injOn- If a function maps a finite set s into a finite set t and is injective on s, then |s| ≤ |t|.
- Injectivity of the pairing map f on A is established by finite case exhaustion over all 16 pairs (a, b) in {1, 2, 3, 4}² using `interval_cases` and `simp_all`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Every square-difference-free subset of {1, 2, 3, 4} has cardinality at most 2. -/theorem op_153_square_diff_free_four_card_le_two (A : Finset ℕ) (hA : A ⊆ Finset.Icc 1 4) (hdiff : ∀ a ∈ A, ∀ b ∈ A, a ≠ b → ¬ ∃ n : ℕ, 0 < n ∧ (a : ℤ) - b = (Polynomial.X ^ 2 : Polynomial ℤ).eval (n : ℤ)) : A.card ≤ 2 := by let f : ℕ → ℕ := fun x => (x + 1) / 2 have hno : ∀ a ∈ A, a + 1 ∈ A → False := by intro a ha ha1 have h := hdiff (a + 1) ha1 a ha (by omega) apply h refine ⟨1, by norm_num, ?_⟩ simp have hmap : Set.MapsTo f ↑A ↑({1, 2} : Finset ℕ) := by intro a ha simp only [Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff, Set.mem_singleton_iff] have ha' := hA ha simp only [Finset.mem_Icc] at ha' have ha1 : 1 ≤ a := ha'.1 have ha4 : a ≤ 4 := ha'.2 interval_cases a <;> norm_num [f] have hinj : Set.InjOn f ↑A := by intro a ha b hb hfab by_contra hne have ha' := hA ha have hb' := hA hb simp only [Finset.mem_Icc] at ha' hb' have ha1 : 1 ≤ a := ha'.1 have ha4 : a ≤ 4 := ha'.2 have hb1 : 1 ≤ b := hb'.1 have hb4 : b ≤ 4 := hb'.2 interval_cases a <;> interval_cases b <;> simp_all [f] exact Finset.card_le_card_of_injOn f hmap hinj