AFTD Auto-Formalizing Theoretical Domains

op_153_square_diff_free_four_card_le_two

theoremverified

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

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.

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

    line 6

      let f : ℕ → ℕ := fun x => (x + 1) / 2
  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.

    lines 7–12

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

    lines 13–20

    uses Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff, Set.mem_singleton_iff, Finset.mem_Icc

      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]
  4. 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.

    lines 21–31

    uses Finset.mem_Icc

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

    line 32

    uses Finset.card_le_card_of_injOn

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

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