(2.18), proof of (2.16), p. 529 — linearly independent b_j of degree ≤ m all divisible by h₁: #J ≤ m + 1 − deg h₁
ProvedLLLFactor.Factors.card_le_2_18linear-independencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial-factorization
Let and let have degree at most and linearly independent coefficient vectors in . Let and let be a nonzero polynomial dividing for every . Then
Each with lies in , a space of rank ; this counting bound is half of the squeeze that determines in Proposition (2.16).
Formalization Note On the page ; the statement is given for any nonzero common divisor , which contains the page's case. The right-hand side is a natural-number difference; when it is and the statement says , which is correct because no nonzero polynomial of degree is divisible by . Indices are 0-based.
Preamble
import Mathlib import Definitions.Def_LLLFactor_Factors_Setting open Polynomial
Formal statement
namespace LLLFactor.Factors
theorem card_le_2_18 (m : ℕ) (b : Fin (m + 1) → ℤ[X])
(hli : LinearIndependent ℝ (coeffVec m ∘ b)) (hdeg : ∀ j, (b j).natDegree ≤ m)
(J : Finset (Fin (m + 1))) (h₁ : ℤ[X]) (hh₁ : h₁ ≠ 0) (hdvd : ∀ j ∈ J, h₁ ∣ b j) :
J.card ≤ m + 1 - h₁.natDegree := by sorry
end LLLFactor.Factors
Source
Lenstra, Lenstra, Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), p. 529, (2.18) in the proof of (2.16) Proposition
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.