# Lemmas for the interaction between polynomials and ∑ and ∏. #

Recall that ∑ and ∏ are notation for Finset.sum and Finset.prod respectively.

## Main results #

• Polynomial.natDegree_prod_of_monic : the degree of a product of monic polynomials is the product of degrees. We prove this only for [CommSemiring R], but it ought to be true for [Semiring R] and List.prod.
• Polynomial.natDegree_prod : for polynomials over an integral domain, the degree of the product is the sum of degrees.
• Polynomial.leadingCoeff_prod : for polynomials over an integral domain, the leading coefficient is the product of leading coefficients.
• Polynomial.prod_X_sub_C_coeff_card_pred carries most of the content for computing the second coefficient of the characteristic polynomial.
theorem Polynomial.natDegree_list_sum_le {S : Type u_1} [] (l : List ()) :
l.sum.natDegree List.foldr max 0 (List.map Polynomial.natDegree l)
theorem Polynomial.natDegree_multiset_sum_le {S : Type u_1} [] (l : ) :
l.sum.natDegree Multiset.foldr max 0 (Multiset.map Polynomial.natDegree l)
theorem Polynomial.natDegree_sum_le {ι : Type w} (s : ) {S : Type u_1} [] (f : ι) :
(s.sum fun (i : ι) => f i).natDegree Finset.fold max 0 (Polynomial.natDegree f) s
theorem Polynomial.natDegree_sum_le_of_forall_le {ι : Type w} (s : ) {S : Type u_1} [] {n : } (f : ι) (h : is, (f i).natDegree n) :
(s.sum fun (i : ι) => f i).natDegree n
theorem Polynomial.degree_list_sum_le {S : Type u_1} [] (l : List ()) :
l.sum.degree (List.map Polynomial.natDegree l).maximum
theorem Polynomial.natDegree_list_prod_le {S : Type u_1} [] (l : List ()) :
l.prod.natDegree (List.map Polynomial.natDegree l).sum
theorem Polynomial.degree_list_prod_le {S : Type u_1} [] (l : List ()) :
l.prod.degree (List.map Polynomial.degree l).sum
theorem Polynomial.coeff_list_prod_of_natDegree_le {S : Type u_1} [] (l : List ()) (n : ) (hl : pl, p.natDegree n) :
l.prod.coeff (l.length * n) = (List.map (fun (p : ) => p.coeff n) l).prod
theorem Polynomial.natDegree_multiset_prod_le {R : Type u} [] (t : ) :
t.prod.natDegree (Multiset.map Polynomial.natDegree t).sum
theorem Polynomial.natDegree_prod_le {R : Type u} {ι : Type w} (s : ) [] (f : ι) :
(s.prod fun (i : ι) => f i).natDegree s.sum fun (i : ι) => (f i).natDegree
theorem Polynomial.degree_multiset_prod_le {R : Type u} [] (t : ) :
t.prod.degree (Multiset.map Polynomial.degree t).sum

The degree of a product of polynomials is at most the sum of the degrees, where the degree of the zero polynomial is ⊥.

theorem Polynomial.degree_prod_le {R : Type u} {ι : Type w} (s : ) [] (f : ι) :
(s.prod fun (i : ι) => f i).degree s.sum fun (i : ι) => (f i).degree
theorem Polynomial.leadingCoeff_multiset_prod' {R : Type u} [] (t : ) (h : (Multiset.map Polynomial.leadingCoeff t).prod 0) :

The leading coefficient of a product of polynomials is equal to the product of the leading coefficients, provided that this product is nonzero.

See Polynomial.leadingCoeff_multiset_prod (without the ') for a version for integral domains, where this condition is automatically satisfied.

theorem Polynomial.leadingCoeff_prod' {R : Type u} {ι : Type w} (s : ) [] (f : ι) (h : (s.prod fun (i : ι) => (f i).leadingCoeff) 0) :
(s.prod fun (i : ι) => f i).leadingCoeff = s.prod fun (i : ι) => (f i).leadingCoeff

The leading coefficient of a product of polynomials is equal to the product of the leading coefficients, provided that this product is nonzero.

See Polynomial.leadingCoeff_prod (without the ') for a version for integral domains, where this condition is automatically satisfied.

theorem Polynomial.natDegree_multiset_prod' {R : Type u} [] (t : ) (h : (Multiset.map (fun (f : ) => f.leadingCoeff) t).prod 0) :
t.prod.natDegree = (Multiset.map (fun (f : ) => f.natDegree) t).sum

The degree of a product of polynomials is equal to the sum of the degrees, provided that the product of leading coefficients is nonzero.

See Polynomial.natDegree_multiset_prod (without the ') for a version for integral domains, where this condition is automatically satisfied.

theorem Polynomial.natDegree_prod' {R : Type u} {ι : Type w} (s : ) [] (f : ι) (h : (s.prod fun (i : ι) => (f i).leadingCoeff) 0) :
(s.prod fun (i : ι) => f i).natDegree = s.sum fun (i : ι) => (f i).natDegree

The degree of a product of polynomials is equal to the sum of the degrees, provided that the product of leading coefficients is nonzero.

See Polynomial.natDegree_prod (without the ') for a version for integral domains, where this condition is automatically satisfied.

theorem Polynomial.natDegree_multiset_prod_of_monic {R : Type u} [] (t : ) (h : ft, f.Monic) :
t.prod.natDegree = (Multiset.map Polynomial.natDegree t).sum
theorem Polynomial.natDegree_prod_of_monic {R : Type u} {ι : Type w} (s : ) [] (f : ι) (h : is, (f i).Monic) :
(s.prod fun (i : ι) => f i).natDegree = s.sum fun (i : ι) => (f i).natDegree
theorem Polynomial.coeff_multiset_prod_of_natDegree_le {R : Type u} [] (t : ) (n : ) (hl : pt, p.natDegree n) :
t.prod.coeff (Multiset.card t * n) = (Multiset.map (fun (p : ) => p.coeff n) t).prod
theorem Polynomial.coeff_prod_of_natDegree_le {R : Type u} {ι : Type w} (s : ) [] (f : ι) (n : ) (h : ps, (f p).natDegree n) :
(s.prod fun (i : ι) => f i).coeff (s.card * n) = s.prod fun (i : ι) => (f i).coeff n
theorem Polynomial.coeff_zero_multiset_prod {R : Type u} [] (t : ) :
t.prod.coeff 0 = (Multiset.map (fun (f : ) => f.coeff 0) t).prod
theorem Polynomial.coeff_zero_prod {R : Type u} {ι : Type w} (s : ) [] (f : ι) :
(s.prod fun (i : ι) => f i).coeff 0 = s.prod fun (i : ι) => (f i).coeff 0
theorem Polynomial.multiset_prod_X_sub_C_nextCoeff {R : Type u} [] (t : ) :
(Multiset.map (fun (x : R) => Polynomial.X - Polynomial.C x) t).prod.nextCoeff = -t.sum
theorem Polynomial.prod_X_sub_C_nextCoeff {R : Type u} {ι : Type w} [] {s : } (f : ιR) :
(s.prod fun (i : ι) => Polynomial.X - Polynomial.C (f i)).nextCoeff = -s.sum fun (i : ι) => f i
theorem Polynomial.multiset_prod_X_sub_C_coeff_card_pred {R : Type u} [] (t : ) (ht : 0 < Multiset.card t) :
(Multiset.map (fun (x : R) => Polynomial.X - Polynomial.C x) t).prod.coeff (Multiset.card t - 1) = -t.sum
theorem Polynomial.prod_X_sub_C_coeff_card_pred {R : Type u} {ι : Type w} [] (s : ) (f : ιR) (hs : 0 < s.card) :
(s.prod fun (i : ι) => Polynomial.X - Polynomial.C (f i)).coeff (s.card - 1) = -s.sum fun (i : ι) => f i
theorem Polynomial.degree_list_prod {R : Type u} [] [] [] (l : List ()) :
l.prod.degree = (List.map Polynomial.degree l).sum

The degree of a product of polynomials is equal to the sum of the degrees, where the degree of the zero polynomial is ⊥. [Nontrivial R] is needed, otherwise for l = [] we have ⊥ in the LHS and 0 in the RHS.

theorem Polynomial.natDegree_prod {R : Type u} {ι : Type w} (s : ) [] [] (f : ι) (h : is, f i 0) :
(s.prod fun (i : ι) => f i).natDegree = s.sum fun (i : ι) => (f i).natDegree

The degree of a product of polynomials is equal to the sum of the degrees.

See Polynomial.natDegree_prod' (with a ') for a version for commutative semirings, where additionally, the product of the leading coefficients must be nonzero.

theorem Polynomial.natDegree_multiset_prod {R : Type u} [] [] (t : ) (h : 0t) :
t.prod.natDegree = (Multiset.map Polynomial.natDegree t).sum
theorem Polynomial.degree_multiset_prod {R : Type u} [] [] (t : ) [] :
t.prod.degree = (Multiset.map (fun (f : ) => f.degree) t).sum

The degree of a product of polynomials is equal to the sum of the degrees, where the degree of the zero polynomial is ⊥.

theorem Polynomial.degree_prod {R : Type u} {ι : Type w} (s : ) [] [] (f : ι) [] :
(s.prod fun (i : ι) => f i).degree = s.sum fun (i : ι) => (f i).degree

The degree of a product of polynomials is equal to the sum of the degrees, where the degree of the zero polynomial is ⊥.

theorem Polynomial.leadingCoeff_multiset_prod {R : Type u} [] [] (t : ) :
See Polynomial.leadingCoeff_multiset_prod' (with a ') for a version for commutative semirings, where additionally, the product of the leading coefficients must be nonzero.
See Polynomial.leadingCoeff_prod' (with a ') for a version for commutative semirings, where additionally, the product of the leading coefficients must be nonzero.