Definition 2.3 — substituting for undoes
ProvedKedlayaUmans.Reduction.inverse_kroneckerkronecker-substitutionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polynomials
Let be a commutative ring, , , and let have individual degrees at most (every variable occurs with exponent at most ). If , then
that is, substituting for in recovers .
This is the sense in which is the inverse of the Kronecker substitution, and it is the first half of the correctness argument for the reduction of Theorem 3.1.
Formalization Note The substitution is MvPolynomial.aeval at . The degree hypothesis is ∀ i, f.degreeOf i ≤ h ^ ℓ - 1; since , and the natural-number subtraction is exact.
Preamble
import Mathlib import Definitions.Def_KedlayaUmans_Reduction_Psi
Formal statement
namespace KedlayaUmans.Reduction
open MvPolynomial
theorem inverse_kronecker {R : Type*} [CommRing R] {m : ℕ} (h ℓ : ℕ) (hh : 2 ≤ h)
(f : MvPolynomial (Fin m) R) (hf : ∀ i, f.degreeOf i ≤ h ^ ℓ - 1) :
aeval (fun ij : Fin m × Fin ℓ => (X ij.1 : MvPolynomial (Fin m) R) ^ (h ^ (ij.2 : ℕ)))
(psi h ℓ f) = f := by sorry
end KedlayaUmans.Reduction
Source
Kedlaya, Umans, Fast polynomial factorization and modular composition, Dagstuhl Seminar Proceedings 08381 (version of Aug. 31, 2008), p. 8, remark after Definition 2.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.