op_153_square_diff_free_three_card_le_two
Every subset $A \subseteq \{1, 2, 3\}$ 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_three_card_le_two
(A : Finset ℕ) (hA : A ⊆ Finset.Icc 1 3)
(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, Sec. 1
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For any finite set $A$ of natural numbers that is a subset of the interval $\{1, 2, 3\}$, if for every pair of distinct elements $a, b \in A$, there does not exist a strictly positive natural number $n$ such that $(a : \mathbb{Z}) - (b : \mathbb{Z}) = (X^2)(n)$ (the polynomial $X^2 \in \mathbb{Z}[X]$ evaluated 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
We proceed by contradiction. Since A is a subset of {1, 2, 3}, assuming |A| > 2 forces A = {1, 2, 3}. However, {1, 2, 3} contains the distinct elements 2 and 1 whose difference is 2 - 1 = 1², contradicting the hypothesis that no two distinct elements of A have a positive square difference.
A is a subset of {1, 2, 3}
Given that A ⊆ [1, 3], any element a ∈ A satisfies 1 ≤ a ≤ 3 by Finset.mem_Icc. Checking the cases a = 1, 2, 3 shows that a must belong to {1, 2, 3}.
uses
Finset.mem_Icchave hsub : A ⊆ ({1, 2, 3} : Finset ℕ) := by intro a ha have hmem := hA ha simp only [Finset.mem_Icc] at hmem obtain ⟨hlo, hhi⟩ := hmem interval_cases a <;> simp
If |A| > 2, then A = {1, 2, 3}
Assuming for contradiction that |A| ≤ 2 is false, we have |A| ≥ 3. Since the set {1, 2, 3} has cardinality 3, its cardinality is at most |A|. Since A ⊆ {1, 2, 3}, Finset.eq_of_subset_of_card_le implies that A must equal {1, 2, 3}.
uses
Finset.eq_of_subset_of_card_leby_contra h have h3 : 3 ≤ A.card := by omega have hle : ({1, 2, 3} : Finset ℕ).card ≤ A.card := by have hc : ({1, 2, 3} : Finset ℕ).card = 3 := by decide omega have heq : A = ({1, 2, 3} : Finset ℕ) := Finset.eq_of_subset_of_card_le hsub hle
Contradiction: A contains two distinct elements whose difference is a square
Since A = {1, 2, 3}, both 1 and 2 belong to A, and they are distinct. Their difference is 2 - 1 = 1 = 1², which witnesses n = 1 > 0 with 2 - 1 = n², directly contradicting the square-free difference hypothesis hdiff.
have h1 : (1:ℕ) ∈ A := by rw [heq]; simp have h2 : (2:ℕ) ∈ A := by rw [heq]; simp have hne : (2:ℕ) ≠ 1 := by norm_num exact hdiff 2 h2 1 h1 hne ⟨1, by norm_num, by norm_num⟩
Finset.mem_Icc- An element belongs to the closed interval [a, b] if and only if it is between a and b inclusive.
Finset.eq_of_subset_of_card_le- If a finite subset s ⊆ t has cardinality at least that of t, then s = t.
- The condition that differences avoid positive squares is expressed via evaluation of the polynomial X^2 rather than the usual exponentiation n^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.
/-- Any subset of {1, 2, 3} avoiding positive square differences has cardinality at most 2 (OP-153 partial). -/theorem op_153_square_diff_free_three_card_le_two (A : Finset ℕ) (hA : A ⊆ Finset.Icc 1 3) (hdiff : ∀ a ∈ A, ∀ b ∈ A, a ≠ b → ¬ ∃ n : ℕ, 0 < n ∧ (a : ℤ) - b = (Polynomial.X ^ 2 : Polynomial ℤ).eval (n : ℤ)) : A.card ≤ 2 := by have hsub : A ⊆ ({1, 2, 3} : Finset ℕ) := by intro a ha have hmem := hA ha simp only [Finset.mem_Icc] at hmem obtain ⟨hlo, hhi⟩ := hmem interval_cases a <;> simp by_contra h have h3 : 3 ≤ A.card := by omega have hle : ({1, 2, 3} : Finset ℕ).card ≤ A.card := by have hc : ({1, 2, 3} : Finset ℕ).card = 3 := by decide omega have heq : A = ({1, 2, 3} : Finset ℕ) := Finset.eq_of_subset_of_card_le hsub hle have h1 : (1:ℕ) ∈ A := by rw [heq]; simp have h2 : (2:ℕ) ∈ A := by rw [heq]; simp have hne : (2:ℕ) ≠ 1 := by norm_num exact hdiff 2 h2 1 h1 hne ⟨1, by norm_num, by norm_num⟩