# mathlibdocumentation

algebra.polynomial.big_operators

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

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

## Main results #

• polynomial.nat_degree_prod_of_monic : the degree of a product of monic polynomials is the product of degrees. We prove this only for [comm_semiring R], but it ought to be true for [semiring R] and list.prod.
• polynomial.nat_degree_prod : for polynomials over an integral domain, the degree of the product is the sum of degrees.
• polynomial.leading_coeff_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.nat_degree_list_sum_le {S : Type u_1} [semiring S] (l : list (polynomial S)) :
theorem polynomial.nat_degree_multiset_sum_le {S : Type u_1} [semiring S] (l : multiset (polynomial S)) :
theorem polynomial.nat_degree_sum_le {ι : Type w} (s : finset ι) {S : Type u_1} [semiring S] (f : ι → ) :
(s.sum (λ (i : ι), f i)).nat_degree
theorem polynomial.degree_list_sum_le {S : Type u_1} [semiring S] (l : list (polynomial S)) :
theorem polynomial.nat_degree_list_prod_le {S : Type u_1} [semiring S] (l : list (polynomial S)) :
theorem polynomial.degree_list_prod_le {S : Type u_1} [semiring S] (l : list (polynomial S)) :
theorem polynomial.coeff_list_prod_of_nat_degree_le {S : Type u_1} [semiring S] (l : list (polynomial S)) (n : ) (hl : ∀ (p : , p lp.nat_degree n) :
l.prod.coeff (l.length * n) = (list.map (λ (p : , p.coeff n) l).prod
theorem polynomial.nat_degree_prod_le {R : Type u} {ι : Type w} (s : finset ι) (f : ι → ) :
(s.prod (λ (i : ι), f i)).nat_degree s.sum (λ (i : ι), (f i).nat_degree)
theorem polynomial.degree_multiset_prod_le {R : Type u} (t : multiset (polynomial R)) :

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 : finset ι) (f : ι → ) :
(s.prod (λ (i : ι), f i)).degree s.sum (λ (i : ι), (f i).degree)
theorem polynomial.leading_coeff_multiset_prod' {R : Type u} (t : multiset (polynomial R)) (h : 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.leading_coeff_multiset_prod (without the ') for a version for integral domains, where this condition is automatically satisfied.

theorem polynomial.leading_coeff_prod' {R : Type u} {ι : Type w} (s : finset ι) (f : ι → ) (h : s.prod (λ (i : ι), (f i).leading_coeff) 0) :
(s.prod (λ (i : ι), f i)).leading_coeff = s.prod (λ (i : ι), (f i).leading_coeff)

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.leading_coeff_prod (without the ') for a version for integral domains, where this condition is automatically satisfied.

theorem polynomial.nat_degree_multiset_prod' {R : Type u} (t : multiset (polynomial R)) (h : (multiset.map (λ (f : , f.leading_coeff) t).prod 0) :

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.nat_degree_multiset_prod (without the ') for a version for integral domains, where this condition is automatically satisfied.

theorem polynomial.nat_degree_prod' {R : Type u} {ι : Type w} (s : finset ι) (f : ι → ) (h : s.prod (λ (i : ι), (f i).leading_coeff) 0) :
(s.prod (λ (i : ι), f i)).nat_degree = s.sum (λ (i : ι), (f i).nat_degree)

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.nat_degree_prod (without the ') for a version for integral domains, where this condition is automatically satisfied.

theorem polynomial.nat_degree_multiset_prod_of_monic {R : Type u} (t : multiset (polynomial R)) (h : ∀ (f : , f t → f.monic) :
theorem polynomial.nat_degree_prod_of_monic {R : Type u} {ι : Type w} (s : finset ι) (f : ι → ) (h : ∀ (i : ι), i s(f i).monic) :
(s.prod (λ (i : ι), f i)).nat_degree = s.sum (λ (i : ι), (f i).nat_degree)
theorem polynomial.coeff_multiset_prod_of_nat_degree_le {R : Type u} (t : multiset (polynomial R)) (n : ) (hl : ∀ (p : , p tp.nat_degree n) :
t.prod.coeff * n) = (multiset.map (λ (p : , p.coeff n) t).prod
theorem polynomial.coeff_prod_of_nat_degree_le {R : Type u} {ι : Type w} (s : finset ι) (f : ι → ) (n : ) (h : ∀ (p : ι), p s(f p).nat_degree n) :
(s.prod (λ (i : ι), f i)).coeff (s.card * n) = s.prod (λ (i : ι), (f i).coeff n)
theorem polynomial.coeff_zero_multiset_prod {R : Type u} (t : multiset (polynomial R)) :
t.prod.coeff 0 = (multiset.map (λ (f : , f.coeff 0) t).prod
theorem polynomial.coeff_zero_prod {R : Type u} {ι : Type w} (s : finset ι) (f : ι → ) :
(s.prod (λ (i : ι), f i)).coeff 0 = s.prod (λ (i : ι), (f i).coeff 0)
theorem polynomial.multiset_prod_X_sub_C_next_coeff {R : Type u} [comm_ring R] (t : multiset R) :
(multiset.map (λ (x : R), t).prod.next_coeff = -t.sum
theorem polynomial.prod_X_sub_C_next_coeff {R : Type u} {ι : Type w} [comm_ring R] {s : finset ι} (f : ι → R) :
(s.prod (λ (i : ι), polynomial.X - polynomial.C (f i))).next_coeff = -s.sum (λ (i : ι), f i)
theorem polynomial.multiset_prod_X_sub_C_coeff_card_pred {R : Type u} [comm_ring R] (t : multiset R) (ht : 0 < ) :
(multiset.map (λ (x : R), t).prod.coeff - 1) = -t.sum
theorem polynomial.prod_X_sub_C_coeff_card_pred {R : Type u} {ι : Type w} [comm_ring R] (s : finset ι) (f : ι → R) (hs : 0 < s.card) :
(s.prod (λ (i : ι), polynomial.X - polynomial.C (f i))).coeff (s.card - 1) = -s.sum (λ (i : ι), f i)
theorem polynomial.degree_list_prod {R : Type u} [semiring R] [nontrivial R] (l : list (polynomial R)) :

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.nat_degree_prod {R : Type u} {ι : Type w} (s : finset ι) (f : ι → ) (h : ∀ (i : ι), i sf i 0) :
(s.prod (λ (i : ι), f i)).nat_degree = s.sum (λ (i : ι), (f i).nat_degree)

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

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

theorem polynomial.nat_degree_multiset_prod {R : Type u} (t : multiset (polynomial R)) (h : 0 t) :
theorem polynomial.degree_multiset_prod {R : Type u} (t : multiset (polynomial R)) [nontrivial R] :
t.prod.degree = (multiset.map (λ (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 : finset ι) (f : ι → ) [nontrivial R] :
(s.prod (λ (i : ι), f i)).degree = s.sum (λ (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 ⊥.

The leading coefficient of a product of polynomials is equal to the product of the leading coefficients.

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

theorem polynomial.leading_coeff_prod {R : Type u} {ι : Type w} (s : finset ι) (f : ι → ) :
(s.prod (λ (i : ι), f i)).leading_coeff = s.prod (λ (i : ι), (f i).leading_coeff)

The leading coefficient of a product of polynomials is equal to the product of the leading coefficients.

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