AFTD Auto-Formalizing Theoretical Domains

op_153_square_diff_free_five_card_le_two

theoremverified

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

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.

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

    lines 6–7

      by_cases h5 : 5 ∈ A
      · by_cases h2 : 2 ∈ A
  2. 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.

    lines 8–23

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

    line 24

    uses le_trans, Finset.card_le_card

          exact le_trans (Finset.card_le_card hsub) (by simp)
  4. 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}.

    lines 25–37

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

    line 38

    uses le_trans, Finset.card_le_card

          exact le_trans (Finset.card_le_card hsub) (by simp)
  6. 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.

    lines 39–47

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

    line 48

    uses op_153_square_diff_free_four_card_le_two

        exact 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

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