Monic reduction with linear degree and exponential coefficient bounds
ProvedTranscendenceTheory.bivariate_monic_reduction_boundFor an integer polynomial, let denote the sum of the absolute values of all its integer coefficients. Let
be monic in . Let be a nonnegative integer such that every coefficient of as a polynomial in has -degree at most . For every integer bivariate polynomial , of total degree , there exists satisfying
The same works for every commutative ring , every ring homomorphism , and every satisfying :
The representative is chosen before the evaluation ring, homomorphism, and root. The zero polynomial and constant inputs are included, with natural degree zero for the zero polynomial. No field, irreducibility, or transcendence hypothesis is required. This supplies uniform degree and coefficient estimates when expressions are reduced to a fixed power basis of an integral algebraic generator.
import Mathlib.Algebra.Polynomial.Div import Mathlib.Algebra.Polynomial.BigOperators import Mathlib.Tactic.Ring import Mathlib.Algebra.MvPolynomial.Degrees import Mathlib.Data.Fin.VecNotation open Polynomial open scoped Polynomial
theorem TranscendenceTheory.bivariate_monic_reduction_bound (g : ℤ[X][X]) (hg : g.Monic)
(hg_degree : 0 < g.natDegree) (B : ℕ)
(hB : ∀ i, (g.coeff i).natDegree ≤ B) (p : MvPolynomial (Fin 2) ℤ) :
∃ r : ℤ[X][X],
r.natDegree < g.natDegree ∧
(∀ i, (r.coeff i).natDegree ≤ (B + 1) * p.totalDegree) ∧
(∑ i ∈ r.support, ∑ j ∈ (r.coeff i).support, ((r.coeff i).coeff j).natAbs) ≤
(∑ m ∈ p.support, (p.coeff m).natAbs) *
(1 + ∑ i ∈ g.support, ∑ j ∈ (g.coeff i).support,
((g.coeff i).coeff j).natAbs) ^ (p.totalDegree + 1) ∧
∀ (A : Type) [CommRing A] (φ : ℤ[X] →+* A) (y : A),
g.eval₂ φ y = 0 →
r.eval₂ φ y = MvPolynomial.eval₂ (Int.castRingHom A) ![φ X, y] p := by sorry