is_intersective_comp_X_add_C
If $h \in \mathbb{Z}[X]$ is intersective, then the translated polynomial $h(X + c)$ is also intersective for any integer $c$.
Statement
theorem is_intersective_comp_X_add_C (h : Polynomial ℤ) (hh : is_intersective h) (c : ℤ) :
is_intersective (h.comp (Polynomial.X + Polynomial.C c))- Source
- step towards op_153_subexp_bound_intersective_quadratic
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_intersectiveAn integer polynomial $h \in \mathbb{Z}[X]$ is intersective if for every positive integer $m$, there exists an integer $n$ such that…
- Used by 1
- op_153_intersective_quadratic_normalize_positiveIf the eventual subexponential difference bound holds for every degree-2 intersective integer polynomial that is strictly positive on all…
The proof, explained
A polynomial h ∈ ℤ[X] is intersective if it has a root modulo every positive integer m. To show that the translated polynomial h(X + c) is also intersective, we fix any modulus m > 0 and choose an integer n such that h(n) ≡ 0 (mod m), which exists by the intersectivity of h. Evaluating h(X + c) at the shifted point n - c simplifies algebraically to h(n) ≡ 0 (mod m), confirming that n - c is a valid root modulo m.
For any modulus m > 0, it suffices to show that h(X + c) evaluated at n - c is congruent to 0 modulo m, where n is a root of h modulo m.
By definition, an intersective polynomial must have a root modulo every integer m > 0. Given such an m, the hypothesis that h is intersective (hh) provides an integer n such that h(n) ≡ 0 [ZMOD m]. We pick n - c as the candidate root for the shifted polynomial h(X + c).
intro m hm obtain ⟨n, hn⟩ := hh m hm use n - c
Evaluating h(X + c) at n - c yields h(n), which is congruent to 0 modulo m.
By the evaluation law for polynomial composition (Polynomial.eval_comp), evaluating h(X + c) at n - c is equivalent to evaluating h at the value of X + c at n - c. Evaluating the sum, the indeterminate, and the constant (Polynomial.eval_add, Polynomial.eval_X, Polynomial.eval_C) computes this argument as (n - c) + c, which simplifies to n by additive cancellation (sub_add_cancel). This reduces the goal to h(n) ≡ 0 [ZMOD m], which holds directly by the definition of n (hn).
uses
Polynomial.eval_comp,Polynomial.eval_add,Polynomial.eval_X,Polynomial.eval_C,sub_add_cancelrw [Polynomial.eval_comp] simp only [Polynomial.eval_add, Polynomial.eval_X, Polynomial.eval_C] rw [sub_add_cancel] exact hn
Polynomial.eval_comp- Evaluating a composed polynomial p(q(X)) at x is equal to evaluating p at q(x).
Polynomial.eval_add- The evaluation of a sum of polynomials p + q at x is p(x) + q(x).
Polynomial.eval_X- Evaluating the indeterminate polynomial X at x yields x.
Polynomial.eval_C- Evaluating a constant polynomial C(a) at x yields a.
sub_add_cancel- For any elements a and b in an additive group, (a - b) + 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.
/-- If h ∈ ℤ[X] is intersective, then the shifted polynomial h(X + c) is also intersective for any integer c. -/theorem is_intersective_comp_X_add_C (h : Polynomial ℤ) (hh : is_intersective h) (c : ℤ) : is_intersective (h.comp (Polynomial.X + Polynomial.C c)) := by intro m hm obtain ⟨n, hn⟩ := hh m hm use n - c rw [Polynomial.eval_comp] simp only [Polynomial.eval_add, Polynomial.eval_X, Polynomial.eval_C] rw [sub_add_cancel] exact hn