AFTD Auto-Formalizing Theoretical Domains

op_153_card_le_of_poly_diff_free

theoremverified

Let $h \in \mathbb{Z}[X]$ be an integer polynomial such that $h(1) = k > 0$. Every subset $A \subseteq \{1, \dots, 2k\}$ whose distinct elements have difference not equal to $h(n)$ for any positive integer $n$ satisfies $|A| \le k$.

Statement

theorem op_153_card_le_of_poly_diff_free (h : Polynomial ℤ) (k : ℕ) (hk : 0 < k)
    (heval : h.eval (1 : ℤ) = (k : ℤ)) (A : Finset ℕ)
    (hA : A ⊆ Finset.Icc 1 (2 * k))
    (hdiff : ∀ a ∈ A, ∀ b ∈ A, a ≠ b → ¬ ∃ n : ℕ, 0 < n ∧ (a : ℤ) - b = h.eval (n : ℤ)) :
    A.card ≤ k
Source
arXiv:2610.07765 Sec. 1, line 244 -- 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_card_le_of_avoiding_diffFor every positive integer $k$, every subset $A \subseteq \{1, \dots, 2k\}$ such that no two distinct elements of $A$ have difference…

Read back from the Lean

Let $h \in \mathbb{Z}[X]$ be a polynomial with integer coefficients, and let $k$ be a positive integer ($k > 0$) such that $h(1) = k$. Let $A$ be a finite set of natural numbers contained in the interval $\{1, \dots, 2k\}$. If for all distinct $a, b \in A$, there does not exist any positive integer $n \ge 1$ such that $a - b = h(n)$, then the cardinality of $A$ is at most $k$.

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 claim is reduced to the lemma op_153_card_le_of_avoiding_diff, which states that any subset of {1, ..., 2k} avoiding the single difference k has size at most k. To show that A avoids difference k, we observe that if two distinct elements satisfied a - b = k, then a - b = h(1) with 1 > 0, which directly contradicts the assumption that A is h-difference-free.

  1. It suffices to show that no two distinct elements of A have difference k.

    By op_153_card_le_of_avoiding_diff, any subset of {1, ..., 2k} that avoids the fixed difference k has cardinality at most k. Applying this reduces the goal to verifying that A avoids the difference k.

    line 7

    uses op_153_card_le_of_avoiding_diff

      apply op_153_card_le_of_avoiding_diff k hk A hA
  2. No two distinct elements of A have difference k.

    Suppose, for contradiction, that there exist distinct elements a, b ∈ A with a - b = k. By the polynomial-difference-free hypothesis (hdiff), no difference of distinct elements can equal h(n) for any positive integer n. Choosing n = 1, which is strictly positive by Nat.one_pos, we evaluate h(1) = k = a - b (rewriting via Nat.cast_one, heval, and hsub), which contradicts hdiff.

    lines 8–12

    uses Nat.one_pos, Nat.cast_one

      intro a ha b hb hab hsub
      have hcontra := hdiff a ha b hb hab
      apply hcontra
      refine ⟨1, Nat.one_pos, ?_⟩
      rw [Nat.cast_one, heval, hsub]
op_153_card_le_of_avoiding_diff
A subset of {1, ..., 2k} containing no two distinct elements with difference k has cardinality at most k.
Nat.one_pos
The natural number 1 is strictly positive (0 < 1).
Nat.cast_one
The coercion of the natural number 1 into an additive monoid with one is 1.

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

/-- For any polynomial h with h(1) = k > 0, any h-difference-free subset of {1, ..., 2k} has size at most k. -/theorem op_153_card_le_of_poly_diff_free (h : Polynomial ℤ) (k : ℕ) (hk : 0 < k)    (heval : h.eval (1 : ℤ) = (k : ℤ)) (A : Finset ℕ)    (hA : A ⊆ Finset.Icc 1 (2 * k))    (hdiff : ∀ a ∈ A, ∀ b ∈ A, a ≠ b → ¬ ∃ n : ℕ, 0 < n ∧ (a : ℤ) - b = h.eval (n : ℤ)) :    A.card ≤ k := by  apply op_153_card_le_of_avoiding_diff k hk A hA  intro a ha b hb hab hsub  have hcontra := hdiff a ha b hb hab  apply hcontra  refine ⟨1, Nat.one_pos, ?_⟩  rw [Nat.cast_one, heval, hsub]
See it in the graphDiscuss this resultChallenge it