AFTD Auto-Formalizing Theoretical Domains

is_intersective_exists_even

theoremverified

Every intersective polynomial $h \in \mathbb{Z}[X]$ takes an even value at some positive natural number $n > 0$.

Statement

theorem is_intersective_exists_even (h : Polynomial ℤ) (hh : is_intersective h) :
    ∃ n : ℕ, 0 < n ∧ Even (h.eval (n : ℤ))
Source
step towards op_153_subexp_bound_intersective_quadratic
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • is_intersectiveAn integer polynomial $h \in \mathbb{Z}[X]$ is intersective if for every positive integer $m$, there exists an integer $n$ such that…
  • is_intersective_exists_posIf h ∈ ℤ[X] is intersective and m is a positive integer, there exists a positive integer n > 0 such that h(n) ≡ 0 (mod m).

The proof, explained

The proof specializes the property of intersective polynomials (`is_intersective_exists_pos`) to the modulus m = 2. This produces a positive integer n > 0 such that h(n) ≡ 0 (mod 2). The modular congruence means that h(n) is divisible by 2, which by `Int.even_iff.mpr` implies that h(n) is even.

  1. There exists a positive integer n > 0 such that h(n) ≡ 0 (mod 2).

    Apply `is_intersective_exists_pos` to the polynomial h with modulus m = 2, using `norm_num` to verify 0 < 2. This gives a positive integer n > 0 satisfying h(n) ≡ 0 (mod 2).

    line 4

    uses is_intersective_exists_pos

      obtain ⟨n, hnpos, hnmod⟩ := is_intersective_exists_pos h hh 2 (by norm_num)
  2. There exists a positive integer n > 0 such that h(n) is even.

    The integer n from the previous step serves as the witness: n > 0 holds by construction, and since h(n) ≡ 0 (mod 2), `Int.even_iff.mpr` proves that h(n) is even.

    line 5

    uses Int.even_iff.mpr

      exact ⟨n, hnpos, Int.even_iff.mpr hnmod⟩
is_intersective_exists_pos
For any intersective polynomial h and any modulus m > 0, there exists a positive integer n > 0 such that h(n) ≡ 0 (mod m).
Int.even_iff.mpr
An integer k is even if k % 2 = 0.

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

/-- Every intersective polynomial h ∈ ℤ[X] takes an even value at some positive integer n > 0. -/theorem is_intersective_exists_even (h : Polynomial ℤ) (hh : is_intersective h) :    ∃ n : ℕ, 0 < n ∧ Even (h.eval (n : ℤ)) := by  obtain ⟨n, hnpos, hnmod⟩ := is_intersective_exists_pos h hh 2 (by norm_num)  exact ⟨n, hnpos, Int.even_iff.mpr hnmod⟩
See it in the graphDiscuss this resultChallenge it