is_intersective_mul_left
For any polynomials g, h ∈ ℤ[X], if h is intersective then g * h is intersective.
Statement
theorem is_intersective_mul_left (g h : Polynomial ℤ) (hh : is_intersective h) :
is_intersective (g * h)- 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
- is_intersective_mul_rightIf $g \in \mathbb{Z}[X]$ is intersective, then $g \cdot h$ is intersective for any $h \in \mathbb{Z}[X]$.
The proof, explained
An integer polynomial is intersective if it has a root modulo every positive integer. To show that the product $g \cdot h$ is intersective when $h$ is intersective, we fix any modulus $m > 0$ and choose an integer root $n$ of $h$ modulo $m$. Since the evaluation of $g \cdot h$ at $n$ is $g(n) \cdot h(n)$, and $m$ divides $h(n)$, it follows that $m$ also divides $(g \cdot h)(n)$.
Given any modulus $m > 0$, an integer root $n$ of $h$ modulo $m$ is selected as the witness for $g \cdot h$.
By definition, a polynomial is intersective if it has a root modulo every positive integer. Given $m > 0$, the intersectivity of $h$ provides an integer $n$ satisfying $h(n) \equiv 0 \pmod m$. We choose this same $n$ to serve as the root for $g \cdot h$.
intro m hm obtain ⟨n, hn⟩ := hh m hm use n
$(g \cdot h)(n) \equiv 0 \pmod m$, which completes the proof that $g \cdot h$ is intersective.
Evaluating the product polynomial at $n$ gives $g(n) \cdot h(n)$ by `Polynomial.eval_mul`. Congruence to $0$ modulo $m$ is equivalent to divisibility by $m$ (`Int.modEq_zero_iff_dvd`), so the hypothesis $h(n) \equiv 0 \pmod m$ means $m \mid h(n)$. Since $m$ divides $h(n)$, it also divides $g(n) \cdot h(n)$ by `dvd_mul_of_dvd_right`.
uses
Polynomial.eval_mul,Int.modEq_zero_iff_dvd,dvd_mul_of_dvd_rightrw [Polynomial.eval_mul] rw [Int.modEq_zero_iff_dvd] at hn ⊢ exact dvd_mul_of_dvd_right hn _
Polynomial.eval_mul- The evaluation of a product of polynomials at a point is the product of their individual evaluations: $(p \cdot q)(x) = p(x) \cdot q(x)$.
Int.modEq_zero_iff_dvd- An integer is congruent to $0$ modulo $n$ if and only if $n$ divides it: $a \equiv 0 \pmod n \iff n \mid a$.
dvd_mul_of_dvd_right- If $a$ divides $b$, then $a$ divides $c \cdot b$ for any $c$.
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.
/-- A multiple of an intersective polynomial is intersective. -/theorem is_intersective_mul_left (g h : Polynomial ℤ) (hh : is_intersective h) : is_intersective (g * h) := by intro m hm obtain ⟨n, hn⟩ := hh m hm use n rw [Polynomial.eval_mul] rw [Int.modEq_zero_iff_dvd] at hn ⊢ exact dvd_mul_of_dvd_right hn _