AFTD Auto-Formalizing Theoretical Domains

op_153_square_diff_free_three_card_le_two

theoremverified

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.

  1. 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}.

    lines 6–11

    uses Finset.mem_Icc

      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
  2. 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}.

    lines 12–17

    uses Finset.eq_of_subset_of_card_le

      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
  3. 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.

    lines 18–21

      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.

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

/-- 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⟩
See it in the graphDiscuss this resultChallenge it