Documentation

Mathlib.Algebra.Polynomial.BigOperators

Lemmas for the interaction between polynomials and and . #

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

Main results #

theorem Polynomial.natDegree_list_sum_le {S : Type u_1} [Semiring S] (l : List (Polynomial S)) :
Polynomial.natDegree (List.sum l) List.foldr max 0 (List.map Polynomial.natDegree l)
theorem Polynomial.natDegree_multiset_sum_le {S : Type u_1} [Semiring S] (l : Multiset (Polynomial S)) :
Polynomial.natDegree (Multiset.sum l) Multiset.foldr max (_ : ∀ (a b c : ), max a (max b c) = max b (max a c)) 0 (Multiset.map Polynomial.natDegree l)
theorem Polynomial.natDegree_sum_le {ι : Type w} (s : Finset ι) {S : Type u_1} [Semiring S] (f : ιPolynomial S) :
Polynomial.natDegree (Finset.sum s fun (i : ι) => f i) Finset.fold max 0 (Polynomial.natDegree f) s
theorem Polynomial.natDegree_prod_le {R : Type u} {ι : Type w} (s : Finset ι) [CommSemiring R] (f : ιPolynomial R) :
Polynomial.natDegree (Finset.prod s fun (i : ι) => f i) Finset.sum s fun (i : ι) => Polynomial.natDegree (f i)

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 ι) [CommSemiring R] (f : ιPolynomial R) :
Polynomial.degree (Finset.prod s fun (i : ι) => f i) Finset.sum s fun (i : ι) => Polynomial.degree (f i)
theorem Polynomial.leadingCoeff_multiset_prod' {R : Type u} [CommSemiring R] (t : Multiset (Polynomial R)) (h : Multiset.prod (Multiset.map Polynomial.leadingCoeff t) 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 : Finset ι) [CommSemiring R] (f : ιPolynomial R) (h : (Finset.prod s fun (i : ι) => Polynomial.leadingCoeff (f i)) 0) :
Polynomial.leadingCoeff (Finset.prod s fun (i : ι) => f i) = Finset.prod s fun (i : ι) => Polynomial.leadingCoeff (f i)

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.

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 : Finset ι) [CommSemiring R] (f : ιPolynomial R) (h : (Finset.prod s fun (i : ι) => Polynomial.leadingCoeff (f i)) 0) :
Polynomial.natDegree (Finset.prod s fun (i : ι) => f i) = Finset.sum s fun (i : ι) => Polynomial.natDegree (f i)

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_prod_of_monic {R : Type u} {ι : Type w} (s : Finset ι) [CommSemiring R] (f : ιPolynomial R) (h : is, Polynomial.Monic (f i)) :
Polynomial.natDegree (Finset.prod s fun (i : ι) => f i) = Finset.sum s fun (i : ι) => Polynomial.natDegree (f i)
theorem Polynomial.coeff_prod_of_natDegree_le {R : Type u} {ι : Type w} (s : Finset ι) [CommSemiring R] (f : ιPolynomial R) (n : ) (h : ps, Polynomial.natDegree (f p) n) :
Polynomial.coeff (Finset.prod s fun (i : ι) => f i) (s.card * n) = Finset.prod s fun (i : ι) => Polynomial.coeff (f i) n
theorem Polynomial.coeff_zero_prod {R : Type u} {ι : Type w} (s : Finset ι) [CommSemiring R] (f : ιPolynomial R) :
Polynomial.coeff (Finset.prod s fun (i : ι) => f i) 0 = Finset.prod s fun (i : ι) => Polynomial.coeff (f i) 0
theorem Polynomial.multiset_prod_X_sub_C_nextCoeff {R : Type u} [CommRing R] (t : Multiset R) :
Polynomial.nextCoeff (Multiset.prod (Multiset.map (fun (x : R) => Polynomial.X - Polynomial.C x) t)) = -Multiset.sum t
theorem Polynomial.prod_X_sub_C_nextCoeff {R : Type u} {ι : Type w} [CommRing R] {s : Finset ι} (f : ιR) :
Polynomial.nextCoeff (Finset.prod s fun (i : ι) => Polynomial.X - Polynomial.C (f i)) = -Finset.sum s fun (i : ι) => f i
theorem Polynomial.multiset_prod_X_sub_C_coeff_card_pred {R : Type u} [CommRing R] (t : Multiset R) (ht : 0 < Multiset.card t) :
Polynomial.coeff (Multiset.prod (Multiset.map (fun (x : R) => Polynomial.X - Polynomial.C x) t)) (Multiset.card t - 1) = -Multiset.sum t
theorem Polynomial.prod_X_sub_C_coeff_card_pred {R : Type u} {ι : Type w} [CommRing R] (s : Finset ι) (f : ιR) (hs : 0 < s.card) :
Polynomial.coeff (Finset.prod s fun (i : ι) => Polynomial.X - Polynomial.C (f i)) (s.card - 1) = -Finset.sum s fun (i : ι) => f i

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 : Finset ι) [CommSemiring R] [NoZeroDivisors R] (f : ιPolynomial R) (h : is, f i 0) :
Polynomial.natDegree (Finset.prod s fun (i : ι) => f i) = Finset.sum s fun (i : ι) => Polynomial.natDegree (f i)

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.

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 ι) [CommSemiring R] [NoZeroDivisors R] (f : ιPolynomial R) [Nontrivial R] :
Polynomial.degree (Finset.prod s fun (i : ι) => f i) = Finset.sum s fun (i : ι) => Polynomial.degree (f i)

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.leadingCoeff_multiset_prod' (with a ') for a version for commutative semirings, where additionally, the product of the leading coefficients must be nonzero.

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

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

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