op_153_card_le_of_poly_diff_free
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.
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.
uses
op_153_card_le_of_avoiding_diffapply op_153_card_le_of_avoiding_diff k hk A hANo 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.
uses
Nat.one_pos,Nat.cast_oneintro 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
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.
/-- 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]