AFTD Auto-Formalizing Theoretical Domains

is_intersective_comp_X_add_C

theoremverified

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

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.

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

    lines 4–6

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

    lines 7–10

    uses Polynomial.eval_comp, Polynomial.eval_add, Polynomial.eval_X, Polynomial.eval_C, sub_add_cancel

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

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