op_153_intersective_quadratic_normalize_positive
If the eventual subexponential difference bound holds for every degree-2 intersective integer polynomial that is strictly positive on all positive integers, then it holds for every degree-2 intersective integer polynomial (no positivity hypothesis): flip the sign so that the leading coefficient is positive, then shift the argument by a constant so that the polynomial is positive on all positive integers. Both operations preserve degree-2-ness and intersective-ness, and the shifted polynomial's positive values are a subset (up to sign) of h's values on positive integers, so a set avoiding differences equal to h(n) also avoids differences equal to the shifted polynomial's values.
Statement
theorem op_153_intersective_quadratic_normalize_positive
(H : ∀ (g : Polynomial ℤ), g.degree = 2 → is_intersective g →
(∀ n : ℕ, 0 < n → 0 < g.eval (n : ℤ)) →
∃ c > 0, ∃ C > 0, ∃ N₀ : ℕ, ∀ N : ℕ, N₀ ≤ N →
∀ A ⊆ Finset.Icc 1 N,
(∀ a ∈ A, ∀ b ∈ A, a ≠ b → ¬ ∃ n : ℕ, 0 < n ∧ (a : ℤ) - b = g.eval (n : ℤ)) →
(A.card : ℝ) ≤ C * (N : ℝ) * Real.exp (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ))))) :
∀ (h : Polynomial ℤ), h.degree = 2 → is_intersective h →
∃ c > 0, ∃ C > 0, ∃ N₀ : ℕ, ∀ N : ℕ, N₀ ≤ N →
∀ A ⊆ Finset.Icc 1 N,
(∀ a ∈ A, ∀ b ∈ A, a ≠ b → ¬ ∃ n : ℕ, 0 < n ∧ (a : ℤ) - b = h.eval (n : ℤ)) →
(A.card : ℝ) ≤ C * (N : ℝ) * Real.exp (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ))))- Source
- step towards op_153_subexp_bound_intersective_quadratic
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- is_intersective_comp_X_add_CIf $h \in \mathbb{Z}[X]$ is intersective, then the translated polynomial $h(X + c)$ is also intersective for any integer $c$.
- is_intersectiveAn integer polynomial $h \in \mathbb{Z}[X]$ is intersective if for every positive integer $m$, there exists an integer $n$ such that…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
The proof, explained
The proof reduces the subexponential difference bound for an arbitrary degree-2 intersective polynomial h to the positive case in two steps. First, an auxiliary lemma establishes that any integer quadratic with leading coefficient a ≥ 1 is strictly positive for all integers x ≥ 2|b| + 2|c| + 2. Next, by flipping the sign of h if necessary, we obtain a polynomial s with leading coefficient at least 1, and shifting the argument by C₁ = 2|s₁| + 2|s₀| + 2 produces g(X) = s(X + C₁), which preserves degree 2 and intersectivity while being strictly positive on all positive integers. Applying the assumption to g, the bound transfers to h because every positive value of g is of the form ±h(m) for some positive integer m, so avoiding differences in h(ℕ⁺) implies avoiding differences in g(ℕ⁺).
An integer quadratic a x² + b x + c with a ≥ 1 is strictly positive whenever x ≥ 2|b| + 2|c| + 2.
Using neg_abs_le and abs_nonneg, we record b ≥ -|b| and c ≥ -|c| with |b|, |c| ≥ 0. From 2|b| + 2|c| + 2 ≤ x, linear arithmetic (linarith) gives x ≥ 2 and x ≥ 0. Non-linear arithmetic (nlinarith) then derives 2x ≤ x², 2|b|x ≤ x², and 4|c| ≤ 2|c|x. Combining these bounds ensures that the dominant positive term a x² exceeds |b|x + |c|, so a x² + b x + c > 0 by non-linear arithmetic (nlinarith).
uses
neg_abs_le,abs_nonneghave hb1 : -|b| ≤ b := neg_abs_le b have hc1 : -|c| ≤ c := neg_abs_le c have hb0 : 0 ≤ |b| := abs_nonneg b have hc0 : 0 ≤ |c| := abs_nonneg c have hx2 : 2 ≤ x := by linarith have hx0 : 0 ≤ x := by linarith have hxx : x * 2 ≤ x * x := by nlinarith have hxb : 2 * |b| * x ≤ x * x := by have : 2 * |b| ≤ x := by linarith nlinarith have hxc : 4 * |c| ≤ 2 * |c| * x := by nlinarith nlinarith
Introduce the polynomial h of degree 2 and intersective, and define s by flipping h's sign if its leading coefficient is negative.
We introduce the degree-2 intersective polynomial h together with the assumptions hdeg and hint. We define s to be h if h's leading coefficient h.coeff 2 is positive, and -h otherwise, guaranteeing that s has a positive leading coefficient.
intro h hdeg hint set s := if 0 < h.coeff 2 then h else -h
For every integer x, s(x) = h(x) or s(x) = -h(x).
Unfolding s and case-splitting on whether 0 < h.coeff 2 gives either s = h (so s(x) = h(x)) or s = -h (so s(x) = -h(x) using Polynomial.eval_neg).
uses
Polynomial.eval_neghave hs_eval (x : ℤ) : s.eval x = h.eval x ∨ s.eval x = -h.eval x := by dsimp [s]; split_ifs · left; rfl · right; simp [Polynomial.eval_neg]
s has degree 2.
Case-splitting on the sign of h.coeff 2, the degree of s is hdeg (which is 2) if s = h, and Polynomial.degree_neg shows (-h).degree = h.degree = 2 if s = -h.
uses
Polynomial.degree_neghave hs_deg : s.degree = 2 := by dsimp [s]; split_ifs · exact hdeg · rw [Polynomial.degree_neg, hdeg]
s is intersective.
If s = h, intersectivity is given by hint. If s = -h, then for any modulus m > 0, hint gives an integer n with h(n) ≡ 0 [ZMOD m]; negating this congruence and simplifying with Polynomial.eval_neg shows (-h)(n) ≡ 0 [ZMOD m].
uses
Polynomial.eval_neghave hs_int : is_intersective s := by dsimp [s]; split_ifs · exact hint · intro m hm obtain ⟨n, hn⟩ := hint m hm refine ⟨n, ?_⟩ have := hn.neg simpa [Polynomial.eval_neg] using this
The leading coefficient of s is at least 1.
Since deg(h) = 2, h is nonzero (otherwise its degree would be ⊥ by Polynomial.degree_zero), so its leading coefficient is nonzero by Polynomial.leadingCoeff_ne_zero.mpr. By Polynomial.coeff_natDegree and Polynomial.natDegree_eq_of_degree_eq_some, this leading coefficient equals h.coeff 2. When h.coeff 2 > 0, s.coeff 2 = h.coeff 2 ≥ 1. When ¬(0 < h.coeff 2), lt_of_le_of_ne and not_lt.mp give h.coeff 2 < 0, so s.coeff 2 = -h.coeff 2 ≥ 1 by Polynomial.coeff_neg and linear integer arithmetic.
uses
Polynomial.natDegree_eq_of_degree_eq_some,Polynomial.degree_zero,Polynomial.leadingCoeff_ne_zero.mpr,Polynomial.coeff_natDegree,Polynomial.coeff_neg,lt_of_le_of_ne,not_lt.mphave hs_lead : 1 ≤ s.coeff 2 := by have hd : s.natDegree = 2 := Polynomial.natDegree_eq_of_degree_eq_some hs_deg have hne : h ≠ 0 := by rintro rfl rw [Polynomial.degree_zero] at hdeg revert hdeg decide have hlc := Polynomial.leadingCoeff_ne_zero.mpr hne have h2 : h.coeff 2 = h.leadingCoeff := by have hd_h : h.natDegree = 2 := Polynomial.natDegree_eq_of_degree_eq_some hdeg rw [← hd_h, Polynomial.coeff_natDegree] have h_ne_zero : h.coeff 2 ≠ 0 := by rw [h2]; exact hlc dsimp [s] split_ifs with hpos · exact hpos · rw [Polynomial.coeff_neg] have : h.coeff 2 < 0 := lt_of_le_of_ne (not_lt.mp hpos) h_ne_zero linarith
Define the shift constant C₁ = 2|s₁| + 2|s₀| + 2.
We define C₁ as a natural number and check that its integer cast equals 2|s.coeff 1| + 2|s.coeff 0| + 2.
set C₁ : ℕ := 2 * (s.coeff 1).natAbs + 2 * (s.coeff 0).natAbs + 2 have hC₁ : (C₁ : ℤ) = 2 * |s.coeff 1| + 2 * |s.coeff 0| + 2 := by dsimp [C₁] push_cast rfl
Define g(X) = s(X + C₁) and show it has degree 2.
We set g = s ∘ (X + C₁). By Polynomial.degree_comp, deg(s ∘ (X + C₁)) = deg(s) * deg(X + C₁). Since deg(X + C₁) = 1 by Polynomial.degree_X_add_C and deg(s) = 2, the product is 2.
uses
Polynomial.degree_comp,Polynomial.degree_X_add_Cset g := s.comp (Polynomial.X + Polynomial.C (C₁ : ℤ)) have hdeg_g : g.degree = 2 := by dsimp [g] rw [Polynomial.degree_comp] · rw [Polynomial.degree_X_add_C, hs_deg] rfl · rw [Polynomial.degree_X_add_C] decide
g is intersective.
Shifting an intersective polynomial by an integer constant preserves intersectivity, as established by is_intersective_comp_X_add_C.
uses
is_intersective_comp_X_add_Chave hint_g : is_intersective g := by dsimp [g] exact is_intersective_comp_X_add_C s hs_int (C₁ : ℤ)
For every positive integer n, g(n) > 0.
For n > 0, we rewrite g(n) as s.coeff 2 * (n + C₁)² + s.coeff 1 * (n + C₁) + s.coeff 0 by expanding the composition and the polynomial evaluation with Polynomial.eval_comp, Polynomial.eval_add, Polynomial.eval_X, Polynomial.eval_C, Polynomial.eval_eq_sum_range, Finset.sum_range_succ, Finset.sum_range_zero, zero_add, pow_zero, mul_one, and pow_one. We then apply the quadratic positivity lemma op_153_intersective_quadratic_normalize_positive_quad_pos with leading coefficient s.coeff 2 ≥ 1 and argument x = n + C₁: since n ≥ 1 (by omega), x ≥ C₁ + 1 > 2|s.coeff 1| + 2|s.coeff 0| + 2, ensuring g(n) > 0.
uses
Polynomial.natDegree_eq_of_degree_eq_some,Polynomial.eval_comp,Polynomial.eval_add,Polynomial.eval_X,Polynomial.eval_C,Polynomial.eval_eq_sum_range,Finset.sum_range_succ,Finset.sum_range_zero,zero_add,pow_zero,mul_one,pow_one,op_153_intersective_quadratic_normalize_positive_quad_poshave hpos_g : ∀ n : ℕ, 0 < n → 0 < g.eval (n : ℤ) := by intro n hn have hd : s.natDegree = 2 := Polynomial.natDegree_eq_of_degree_eq_some hs_deg have heval : g.eval (n : ℤ) = s.coeff 2 * ((n : ℤ) + (C₁ : ℤ))^2 + s.coeff 1 * ((n : ℤ) + (C₁ : ℤ)) + s.coeff 0 := by dsimp [g] rw [Polynomial.eval_comp, Polynomial.eval_add, Polynomial.eval_X, Polynomial.eval_C, Polynomial.eval_eq_sum_range, hd] simp only [Finset.sum_range_succ, Finset.sum_range_zero, zero_add, pow_zero, mul_one, pow_one] ring rw [heval] apply op_153_intersective_quadratic_normalize_positive_quad_pos (s.coeff 2) (s.coeff 1) (s.coeff 0) ((n : ℤ) + (C₁ : ℤ)) hs_lead rw [hC₁] have : 1 ≤ (n : ℤ) := by omega linarith
Apply hypothesis H to g to obtain the constants c, C, and N₀.
Hypothesis H applies to g because it has degree 2, is intersective, and is strictly positive on positive integers. This yields constants c > 0, C > 0, and N₀. To show they also work for h, it suffices to prove that any set A avoiding positive difference values of h also avoids positive difference values of g.
obtain ⟨c, hc, C, hC, N₀, hN₀⟩ := H g hdeg_g hint_g hpos_g refine ⟨c, hc, C, hC, N₀, fun N hN A hA h_avoid => ?_⟩ apply hN₀ N hN A hA
Any set avoiding differences in h(ℕ⁺) also avoids differences in g(ℕ⁺), completing the proof.
Suppose distinct a, b ∈ A satisfy a - b = g(n) for some n > 0. Since g(n) = s(n + C₁) and n + C₁ > 0 (by omega), s(n + C₁) is either h(n + C₁) or -h(n + C₁). In the first case, a - b = h(n + C₁) contradicts the avoidance condition for h. In the second case, b - a = h(n + C₁), and since a ≠ b implies b ≠ a by Ne.symm, this also contradicts avoidance. Hence A avoids positive values of g, so |A| satisfies the desired subexponential bound.
uses
Polynomial.eval_comp,Ne.symmintro a ha b hb hab ⟨n, hn, heq⟩ have heval : g.eval (n : ℤ) = s.eval ((n + C₁ : ℕ) : ℤ) := by dsimp [g] simp [Polynomial.eval_comp] rw [heval] at heq have hm_pos : 0 < n + C₁ := by omega have hs_ev := hs_eval ((n + C₁ : ℕ) : ℤ) rcases hs_ev with h1 | h2 · rw [h1] at heq exact h_avoid a ha b hb hab ⟨n + C₁, hm_pos, heq⟩ · rw [h2] at heq have h_symm : (b : ℤ) - a = h.eval ((n + C₁ : ℕ) : ℤ) := by calc (b : ℤ) - a = -((a : ℤ) - b) := by ring _ = -(-h.eval ((n + C₁ : ℕ) : ℤ)) := by rw [heq] _ = h.eval ((n + C₁ : ℕ) : ℤ) := by ring exact h_avoid b hb a ha (Ne.symm hab) ⟨n + C₁, hm_pos, h_symm⟩
neg_abs_le- For any element a in an ordered additive group, -|a| ≤ a.
abs_nonneg- For any element a in a lattice ordered additive group, 0 ≤ |a|.
Polynomial.eval_neg- For any ring R, evaluating the negation of a polynomial p at x equals the negation of p(x): (-p)(x) = -p(x).
Polynomial.degree_neg- For any ring R, the degree of -p equals the degree of p.
Polynomial.natDegree_eq_of_degree_eq_some- If the degree of p equals n (as an element of WithBot ℕ), then its degree as a natural number (natDegree) is n.
Polynomial.degree_zero- The degree of the zero polynomial is ⊥ (negative infinity).
Polynomial.leadingCoeff_ne_zero.mpr- If a polynomial is nonzero, its leading coefficient is nonzero.
Polynomial.coeff_natDegree- The coefficient of a polynomial at its degree (natDegree) is its leading coefficient.
Polynomial.coeff_neg- The n-th coefficient of -p is the negation of the n-th coefficient of p.
lt_of_le_of_ne- In a partial order, if a ≤ b and a ≠ b, then a < b.
not_lt.mp- If ¬(a < b) in a linear order, then b ≤ a.
Polynomial.degree_comp- For polynomials over a domain, if deg(q) > 0, then deg(p ∘ q) = deg(p) * deg(q).
Polynomial.degree_X_add_C- The polynomial X + C a has degree 1.
is_intersective_comp_X_add_C- If h is an intersective integer polynomial, then h(X + c) is also intersective for any integer c.
Polynomial.eval_comp- Evaluating a composition of polynomials p ∘ q at x equals p(q(x)).
Polynomial.eval_add- Evaluating a sum of polynomials p + q at x equals p(x) + q(x).
Polynomial.eval_X- Evaluating the variable X at x yields x.
Polynomial.eval_C- Evaluating a constant polynomial C a at x yields a.
Polynomial.eval_eq_sum_range- Evaluating a polynomial p at x equals the sum of coeff(i) * x^i for i from 0 to natDegree(p).
Finset.sum_range_succ- Splits the sum over range (n + 1) into the sum over range n plus the term at n.
Finset.sum_range_zero- The sum over range 0 is 0.
zero_add- 0 + a = a.
pow_zero- a^0 = 1.
mul_one- a * 1 = a.
pow_one- a^1 = a.
op_153_intersective_quadratic_normalize_positive_quad_pos- A quadratic a x^2 + b x + c with a ≥ 1 is strictly positive for all integers x ≥ 2|b| + 2|c| + 2.
Ne.symm- Symmetry of inequality: if a ≠ b then b ≠ a.
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.
lemma op_153_intersective_quadratic_normalize_positive_quad_pos (a b c x : ℤ) (ha : 1 ≤ a) (hx : 2 * |b| + 2 * |c| + 2 ≤ x) : 0 < a * x^2 + b * x + c := by have hb1 : -|b| ≤ b := neg_abs_le b have hc1 : -|c| ≤ c := neg_abs_le c have hb0 : 0 ≤ |b| := abs_nonneg b have hc0 : 0 ≤ |c| := abs_nonneg c have hx2 : 2 ≤ x := by linarith have hx0 : 0 ≤ x := by linarith have hxx : x * 2 ≤ x * x := by nlinarith have hxb : 2 * |b| * x ≤ x * x := by have : 2 * |b| ≤ x := by linarith nlinarith have hxc : 4 * |c| ≤ 2 * |c| * x := by nlinarith nlinarith/-- Sign and translation normalisation: the eventual subexponential bound for quadratics that are positive on the positive integers implies it for all degree-2 intersective quadratics. -/theorem op_153_intersective_quadratic_normalize_positive (H : ∀ (g : Polynomial ℤ), g.degree = 2 → is_intersective g → (∀ n : ℕ, 0 < n → 0 < g.eval (n : ℤ)) → ∃ c > 0, ∃ C > 0, ∃ N₀ : ℕ, ∀ N : ℕ, N₀ ≤ N → ∀ A ⊆ Finset.Icc 1 N, (∀ a ∈ A, ∀ b ∈ A, a ≠ b → ¬ ∃ n : ℕ, 0 < n ∧ (a : ℤ) - b = g.eval (n : ℤ)) → (A.card : ℝ) ≤ C * (N : ℝ) * Real.exp (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ))))) : ∀ (h : Polynomial ℤ), h.degree = 2 → is_intersective h → ∃ c > 0, ∃ C > 0, ∃ N₀ : ℕ, ∀ N : ℕ, N₀ ≤ N → ∀ A ⊆ Finset.Icc 1 N, (∀ a ∈ A, ∀ b ∈ A, a ≠ b → ¬ ∃ n : ℕ, 0 < n ∧ (a : ℤ) - b = h.eval (n : ℤ)) → (A.card : ℝ) ≤ C * (N : ℝ) * Real.exp (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)))) := by intro h hdeg hint set s := if 0 < h.coeff 2 then h else -h have hs_eval (x : ℤ) : s.eval x = h.eval x ∨ s.eval x = -h.eval x := by dsimp [s]; split_ifs · left; rfl · right; simp [Polynomial.eval_neg] have hs_deg : s.degree = 2 := by dsimp [s]; split_ifs · exact hdeg · rw [Polynomial.degree_neg, hdeg] have hs_int : is_intersective s := by dsimp [s]; split_ifs · exact hint · intro m hm obtain ⟨n, hn⟩ := hint m hm refine ⟨n, ?_⟩ have := hn.neg simpa [Polynomial.eval_neg] using this have hs_lead : 1 ≤ s.coeff 2 := by have hd : s.natDegree = 2 := Polynomial.natDegree_eq_of_degree_eq_some hs_deg have hne : h ≠ 0 := by rintro rfl rw [Polynomial.degree_zero] at hdeg revert hdeg decide have hlc := Polynomial.leadingCoeff_ne_zero.mpr hne have h2 : h.coeff 2 = h.leadingCoeff := by have hd_h : h.natDegree = 2 := Polynomial.natDegree_eq_of_degree_eq_some hdeg rw [← hd_h, Polynomial.coeff_natDegree] have h_ne_zero : h.coeff 2 ≠ 0 := by rw [h2]; exact hlc dsimp [s] split_ifs with hpos · exact hpos · rw [Polynomial.coeff_neg] have : h.coeff 2 < 0 := lt_of_le_of_ne (not_lt.mp hpos) h_ne_zero linarith set C₁ : ℕ := 2 * (s.coeff 1).natAbs + 2 * (s.coeff 0).natAbs + 2 have hC₁ : (C₁ : ℤ) = 2 * |s.coeff 1| + 2 * |s.coeff 0| + 2 := by dsimp [C₁] push_cast rfl set g := s.comp (Polynomial.X + Polynomial.C (C₁ : ℤ)) have hdeg_g : g.degree = 2 := by dsimp [g] rw [Polynomial.degree_comp] · rw [Polynomial.degree_X_add_C, hs_deg] rfl · rw [Polynomial.degree_X_add_C] decide have hint_g : is_intersective g := by dsimp [g] exact is_intersective_comp_X_add_C s hs_int (C₁ : ℤ) have hpos_g : ∀ n : ℕ, 0 < n → 0 < g.eval (n : ℤ) := by intro n hn have hd : s.natDegree = 2 := Polynomial.natDegree_eq_of_degree_eq_some hs_deg have heval : g.eval (n : ℤ) = s.coeff 2 * ((n : ℤ) + (C₁ : ℤ))^2 + s.coeff 1 * ((n : ℤ) + (C₁ : ℤ)) + s.coeff 0 := by dsimp [g] rw [Polynomial.eval_comp, Polynomial.eval_add, Polynomial.eval_X, Polynomial.eval_C, Polynomial.eval_eq_sum_range, hd] simp only [Finset.sum_range_succ, Finset.sum_range_zero, zero_add, pow_zero, mul_one, pow_one] ring rw [heval] apply op_153_intersective_quadratic_normalize_positive_quad_pos (s.coeff 2) (s.coeff 1) (s.coeff 0) ((n : ℤ) + (C₁ : ℤ)) hs_lead rw [hC₁] have : 1 ≤ (n : ℤ) := by omega linarith obtain ⟨c, hc, C, hC, N₀, hN₀⟩ := H g hdeg_g hint_g hpos_g refine ⟨c, hc, C, hC, N₀, fun N hN A hA h_avoid => ?_⟩ apply hN₀ N hN A hA intro a ha b hb hab ⟨n, hn, heq⟩ have heval : g.eval (n : ℤ) = s.eval ((n + C₁ : ℕ) : ℤ) := by dsimp [g] simp [Polynomial.eval_comp] rw [heval] at heq have hm_pos : 0 < n + C₁ := by omega have hs_ev := hs_eval ((n + C₁ : ℕ) : ℤ) rcases hs_ev with h1 | h2 · rw [h1] at heq exact h_avoid a ha b hb hab ⟨n + C₁, hm_pos, heq⟩ · rw [h2] at heq have h_symm : (b : ℤ) - a = h.eval ((n + C₁ : ℕ) : ℤ) := by calc (b : ℤ) - a = -((a : ℤ) - b) := by ring _ = -(-h.eval ((n + C₁ : ℕ) : ℤ)) := by rw [heq] _ = h.eval ((n + C₁ : ℕ) : ℤ) := by ring exact h_avoid b hb a ha (Ne.symm hab) ⟨n + C₁, hm_pos, h_symm⟩