op_153_square_diff_free_five_card_le_two
Every subset $A \subseteq \{1, 2, 3, 4, 5\}$ 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_five_card_le_two
(A : Finset ℕ) (hA : A ⊆ Finset.Icc 1 5)
(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- Built on 1
- op_153_square_diff_free_four_card_le_twoEvery subset $A \subseteq \{1, 2, 3, 4\}$ 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 of natural numbers $A \subseteq \{1, 2, 3, 4, 5\}$, if no two distinct elements $a, b \in A$ satisfy $(a : \mathbb{Z}) - b = n^2$ for some positive integer $n \in \mathbb{N}$ (expressed via evaluating the polynomial $X^2 \in \mathbb{Z}[X]$ at $n$), 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 proof proceeds by case analysis on whether 5 ∈ A. If 5 ∉ A, then A ⊆ {1, 2, 3, 4}, reducing the claim directly to the four-element case established in op_153_square_diff_free_four_card_le_two. If 5 ∈ A, the proof splits on whether 2 ∈ A. In each subcase, the square-difference-free hypothesis excludes enough elements (1 and 4 because 5 - 1 = 2² and 5 - 4 = 1², plus 3 when 2 ∈ A because 3 - 2 = 1²) to force A ⊆ {2, 5} or A ⊆ {3, 5}, both of which have cardinality at most 2.
We begin a case analysis on whether 5 ∈ A, and within that branch, whether 2 ∈ A, focusing first on the subcase where 5 ∈ A and 2 ∈ A.
We split the proof into cases based on whether 5 ∈ A. In the branch where 5 ∈ A, we further split on whether 2 ∈ A.
by_cases h5 : 5 ∈ A · by_cases h2 : 2 ∈ A
Under the assumptions 5 ∈ A and 2 ∈ A, we have A ⊆ {2, 5}.
If 1 ∈ A, then 5 - 1 = 4 = 2², contradicting the square-difference-free hypothesis. If 3 ∈ A, then 3 - 2 = 1 = 1², also contradicting the hypothesis. If 4 ∈ A, then 5 - 4 = 1 = 1², another contradiction. Since every element x ∈ A belongs to the interval [1, 5] and cannot be 1, 3, or 4, testing each integer in {1, 2, 3, 4, 5} shows that x must be 2 or 5.
uses
Finset.mem_Icc· have hsub : A ⊆ ({2, 5} : Finset ℕ) := by have h1not : 1 ∉ A := by intro h1 exact hdiff 5 h5 1 h1 (by norm_num) ⟨2, by norm_num, by norm_num⟩ have h3not : 3 ∉ A := by intro h3 exact hdiff 3 h3 2 h2 (by norm_num) ⟨1, by norm_num, by norm_num⟩ have h4not : 4 ∉ A := by intro h4 exact hdiff 5 h5 4 h4 (by norm_num) ⟨1, by norm_num, by simp⟩ intro x hx have hx15 : x ∈ Finset.Icc 1 5 := hA hx rw [Finset.mem_Icc] at hx15 have hxlow : 1 ≤ x := hx15.1 have hxup : x ≤ 5 := hx15.2 interval_cases x <;> simp_all
When 5 ∈ A and 2 ∈ A, the cardinality of A is at most 2.
Since A ⊆ {2, 5}, the monotonicity of cardinality on finite sets and transitivity of inequality give |A| ≤ |{2, 5}| ≤ 2.
uses
le_trans,Finset.card_le_cardexact le_trans (Finset.card_le_card hsub) (by simp)
Under the assumptions 5 ∈ A and 2 ∉ A, we have A ⊆ {3, 5}.
In this subcase, 1 ∉ A because 5 - 1 = 2², and 4 ∉ A because 5 - 4 = 1², both violating the square-difference-free hypothesis. Since 1, 2, 4 ∉ A and A ⊆ {1, 2, 3, 4, 5}, checking each candidate in {1, 2, 3, 4, 5} leaves only 3 and 5, so A ⊆ {3, 5}.
uses
Finset.mem_Icc· have hsub : A ⊆ ({3, 5} : Finset ℕ) := by have h1not : 1 ∉ A := by intro h1 exact hdiff 5 h5 1 h1 (by norm_num) ⟨2, by norm_num, by norm_num⟩ have h4not : 4 ∉ A := by intro h4 exact hdiff 5 h5 4 h4 (by norm_num) ⟨1, by norm_num, by simp⟩ intro x hx have hx15 : x ∈ Finset.Icc 1 5 := hA hx rw [Finset.mem_Icc] at hx15 have hxlow : 1 ≤ x := hx15.1 have hxup : x ≤ 5 := hx15.2 interval_cases x <;> simp_all
When 5 ∈ A and 2 ∉ A, the cardinality of A is at most 2.
Since A ⊆ {3, 5}, monotonicity of finite set cardinality and transitivity of inequality give |A| ≤ |{3, 5}| ≤ 2.
uses
le_trans,Finset.card_le_cardexact le_trans (Finset.card_le_card hsub) (by simp)
Under the assumption 5 ∉ A, we have A ⊆ {1, 2, 3, 4}.
Any x ∈ A satisfies 1 ≤ x ≤ 5 by hypothesis. Since 5 ∉ A, we have x ≠ 5, which implies 1 ≤ x ≤ 4 by linear integer arithmetic.
uses
Finset.mem_Icc· have hA4 : A ⊆ Finset.Icc 1 4 := by intro x hx have hx15 : x ∈ Finset.Icc 1 5 := hA hx rw [Finset.mem_Icc] at hx15 ⊢ have hx5 : x ≠ 5 := by intro h apply h5 simpa [h] using hx omega
When 5 ∉ A, the cardinality of A is at most 2, completing the proof.
With A ⊆ {1, 2, 3, 4}, the claim follows directly from the previously proved theorem op_153_square_diff_free_four_card_le_two for subsets of {1, 2, 3, 4}.
uses
op_153_square_diff_free_four_card_le_twoexact op_153_square_diff_free_four_card_le_two A hA4 hdiff
Finset.mem_Icc- An element x belongs to the closed interval [a, b] if and only if a ≤ x and x ≤ b.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Finset.card_le_card- If a finite set s is a subset of t, then the cardinality of s is at most the cardinality of t.
op_153_square_diff_free_four_card_le_two- Every square-difference-free subset of {1, 2, 3, 4} has cardinality at most 2.
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, 5} has cardinality at most 2. -/theorem op_153_square_diff_free_five_card_le_two (A : Finset ℕ) (hA : A ⊆ Finset.Icc 1 5) (hdiff : ∀ a ∈ A, ∀ b ∈ A, a ≠ b → ¬ ∃ n : ℕ, 0 < n ∧ (a : ℤ) - b = (Polynomial.X ^ 2 : Polynomial ℤ).eval (n : ℤ)) : A.card ≤ 2 := by by_cases h5 : 5 ∈ A · by_cases h2 : 2 ∈ A · have hsub : A ⊆ ({2, 5} : Finset ℕ) := by have h1not : 1 ∉ A := by intro h1 exact hdiff 5 h5 1 h1 (by norm_num) ⟨2, by norm_num, by norm_num⟩ have h3not : 3 ∉ A := by intro h3 exact hdiff 3 h3 2 h2 (by norm_num) ⟨1, by norm_num, by norm_num⟩ have h4not : 4 ∉ A := by intro h4 exact hdiff 5 h5 4 h4 (by norm_num) ⟨1, by norm_num, by simp⟩ intro x hx have hx15 : x ∈ Finset.Icc 1 5 := hA hx rw [Finset.mem_Icc] at hx15 have hxlow : 1 ≤ x := hx15.1 have hxup : x ≤ 5 := hx15.2 interval_cases x <;> simp_all exact le_trans (Finset.card_le_card hsub) (by simp) · have hsub : A ⊆ ({3, 5} : Finset ℕ) := by have h1not : 1 ∉ A := by intro h1 exact hdiff 5 h5 1 h1 (by norm_num) ⟨2, by norm_num, by norm_num⟩ have h4not : 4 ∉ A := by intro h4 exact hdiff 5 h5 4 h4 (by norm_num) ⟨1, by norm_num, by simp⟩ intro x hx have hx15 : x ∈ Finset.Icc 1 5 := hA hx rw [Finset.mem_Icc] at hx15 have hxlow : 1 ≤ x := hx15.1 have hxup : x ≤ 5 := hx15.2 interval_cases x <;> simp_all exact le_trans (Finset.card_le_card hsub) (by simp) · have hA4 : A ⊆ Finset.Icc 1 4 := by intro x hx have hx15 : x ∈ Finset.Icc 1 5 := hA hx rw [Finset.mem_Icc] at hx15 ⊢ have hx5 : x ≠ 5 := by intro h apply h5 simpa [h] using hx omega exact op_153_square_diff_free_four_card_le_two A hA4 hdiff