AFTD Auto-Formalizing Theoretical Domains

is_intersective_mul_left

theoremverified

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)$.

  1. 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$.

    lines 4–6

      intro m hm
      obtain ⟨n, hn⟩ := hh m hm
      use n
  2. $(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`.

    lines 7–9

    uses Polynomial.eval_mul, Int.modEq_zero_iff_dvd, dvd_mul_of_dvd_right

      rw [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

/-- 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 _
See it in the graphDiscuss this resultChallenge it