mathlib documentation

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 #

source
theorem polynomial.nat_degree_list_sum_le {S : Type u_1} [semiring S] (l : list S[X]) :
l.sum.nat_degree ≤ list.foldr max 0 (list.map polynomial.nat_degree l)
source
theorem polynomial.nat_degree_multiset_sum_le {S : Type u_1} [semiring S] (l : multiset S[X]) :
l.sum.nat_degree ≤ multiset.foldr max max_left_comm 0 (multiset.map polynomial.nat_degree l)
source
theorem polynomial.nat_degree_sum_le {ι : Type w} (s : finset ι) {S : Type u_1} [semiring S] (f : ι → S[X]) :
(∑ (i : ι) in s, f i).nat_degree ≤ finset.fold max 0 (polynomial.nat_degree ∘ f) s
source
theorem polynomial.degree_list_sum_le {S : Type u_1} [semiring S] (l : list S[X]) :
l.sum.degree ≤ (list.map polynomial.nat_degree l).maximum
source
theorem polynomial.nat_degree_list_prod_le {S : Type u_1} [semiring S] (l : list S[X]) :
l.prod.nat_degree ≤ (list.map polynomial.nat_degree l).sum
source
theorem polynomial.degree_list_prod_le {S : Type u_1} [semiring S] (l : list S[X]) :
l.prod.degree ≤ (list.map polynomial.degree l).sum
source
theorem polynomial.coeff_list_prod_of_nat_degree_le {S : Type u_1} [semiring S] (l : list S[X]) (n : ℕ) (hl : ∀ (p : S[X]), p ∈ l → p.nat_degree ≤ n) :
l.prod.coeff ((l.length) * n) = (list.map (λ (p : S[X]), p.coeff n) l).prod
source
theorem polynomial.nat_degree_multiset_prod_le {R : Type u} [comm_semiring R] (t : multiset R[X]) :
t.prod.nat_degree ≤ (multiset.map polynomial.nat_degree t).sum
source
theorem polynomial.nat_degree_prod_le {R : Type u} {ι : Type w} (s : finset ι) [comm_semiring R] (f : ι → R[X]) :
(∏ (i : ι) in s, f i).nat_degree ≤ ∑ (i : ι) in s, (f i).nat_degree
source
theorem polynomial.degree_multiset_prod_le {R : Type u} [comm_semiring R] (t : multiset R[X]) :
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 ⊥.

source
theorem polynomial.degree_prod_le {R : Type u} {ι : Type w} (s : finset ι) [comm_semiring R] (f : ι → R[X]) :
(∏ (i : ι) in s, f i).degree ≤ ∑ (i : ι) in s, (f i).degree
source
theorem polynomial.leading_coeff_multiset_prod' {R : Type u} [comm_semiring R] (t : multiset R[X]) (h : (multiset.map polynomial.leading_coeff t).prod ≠ 0) :
t.prod.leading_coeff = (multiset.map polynomial.leading_coeff t).prod

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.

source
theorem polynomial.leading_coeff_prod' {R : Type u} {ι : Type w} (s : finset ι) [comm_semiring R] (f : ι → R[X]) (h : ∏ (i : ι) in s, (f i).leading_coeff ≠ 0) :
(∏ (i : ι) in s, f i).leading_coeff = ∏ (i : ι) in s, (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.

source
theorem polynomial.nat_degree_multiset_prod' {R : Type u} [comm_semiring R] (t : multiset R[X]) (h : (multiset.map (λ (f : R[X]), f.leading_coeff) t).prod ≠ 0) :
t.prod.nat_degree = (multiset.map (λ (f : R[X]), f.nat_degree) 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.nat_degree_multiset_prod (without the ') for a version for integral domains, where this condition is automatically satisfied.

source
theorem polynomial.nat_degree_prod' {R : Type u} {ι : Type w} (s : finset ι) [comm_semiring R] (f : ι → R[X]) (h : ∏ (i : ι) in s, (f i).leading_coeff ≠ 0) :
(∏ (i : ι) in s, f i).nat_degree = ∑ (i : ι) in s, (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.

source
theorem polynomial.nat_degree_multiset_prod_of_monic {R : Type u} [comm_semiring R] (t : multiset R[X]) (h : ∀ (f : R[X]), f ∈ t → f.monic) :
t.prod.nat_degree = (multiset.map polynomial.nat_degree t).sum
source
theorem polynomial.nat_degree_prod_of_monic {R : Type u} {ι : Type w} (s : finset ι) [comm_semiring R] (f : ι → R[X]) (h : ∀ (i : ι), i ∈ s → (f i).monic) :
(∏ (i : ι) in s, f i).nat_degree = ∑ (i : ι) in s, (f i).nat_degree
source
theorem polynomial.coeff_multiset_prod_of_nat_degree_le {R : Type u} [comm_semiring R] (t : multiset R[X]) (n : ℕ) (hl : ∀ (p : R[X]), p ∈ t → p.nat_degree ≤ n) :
t.prod.coeff ((⇑multiset.card t) * n) = (multiset.map (λ (p : R[X]), p.coeff n) t).prod
source
theorem polynomial.coeff_prod_of_nat_degree_le {R : Type u} {ι : Type w} (s : finset ι) [comm_semiring R] (f : ι → R[X]) (n : ℕ) (h : ∀ (p : ι), p ∈ s → (f p).nat_degree ≤ n) :
(∏ (i : ι) in s, f i).coeff ((s.card) * n) = ∏ (i : ι) in s, (f i).coeff n
source
theorem polynomial.coeff_zero_multiset_prod {R : Type u} [comm_semiring R] (t : multiset R[X]) :
t.prod.coeff 0 = (multiset.map (λ (f : R[X]), f.coeff 0) t).prod
source
theorem polynomial.coeff_zero_prod {R : Type u} {ι : Type w} (s : finset ι) [comm_semiring R] (f : ι → R[X]) :
(∏ (i : ι) in s, f i).coeff 0 = ∏ (i : ι) in s, (f i).coeff 0
source
theorem polynomial.multiset_prod_X_sub_C_next_coeff {R : Type u} [comm_ring R] (t : multiset R) :
(multiset.map (λ (x : R), polynomial.X - ⇑polynomial.C x) t).prod.next_coeff = -t.sum
source
theorem polynomial.prod_X_sub_C_next_coeff {R : Type u} {ι : Type w} [comm_ring R] {s : finset ι} (f : ι → R) :
(∏ (i : ι) in s, (polynomial.X - ⇑polynomial.C (f i))).next_coeff = -∑ (i : ι) in s, f i
source
theorem polynomial.multiset_prod_X_sub_C_coeff_card_pred {R : Type u} [comm_ring R] (t : multiset R) (ht : 0 < ⇑multiset.card t) :
(multiset.map (λ (x : R), polynomial.X - ⇑polynomial.C x) t).prod.coeff (⇑multiset.card t - 1) = -t.sum
source
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) :
(∏ (i : ι) in s, (polynomial.X - ⇑polynomial.C (f i))).coeff (s.card - 1) = -∑ (i : ι) in s, f i
source
theorem polynomial.nat_degree_prod {R : Type u} {ι : Type w} (s : finset ι) [comm_ring R] [no_zero_divisors R] (f : ι → R[X]) (h : ∀ (i : ι), i ∈ s → f i ≠ 0) :
(∏ (i : ι) in s, f i).nat_degree = ∑ (i : ι) in s, (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.

source
theorem polynomial.nat_degree_multiset_prod {R : Type u} [comm_ring R] [no_zero_divisors R] (s : multiset R[X]) (h : 0 ∉ s) :
s.prod.nat_degree = (multiset.map polynomial.nat_degree s).sum
source
theorem polynomial.degree_multiset_prod {R : Type u} [comm_ring R] [no_zero_divisors R] (t : multiset R[X]) [nontrivial R] :
t.prod.degree = (multiset.map (λ (f : R[X]), 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 ⊥.

source
theorem polynomial.degree_prod {R : Type u} {ι : Type w} (s : finset ι) [comm_ring R] [no_zero_divisors R] (f : ι → R[X]) [nontrivial R] :
(∏ (i : ι) in s, f i).degree = ∑ (i : ι) in s, (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 ⊥.

source
theorem polynomial.leading_coeff_multiset_prod {R : Type u} [comm_ring R] [no_zero_divisors R] (t : multiset R[X]) :
t.prod.leading_coeff = (multiset.map (λ (f : R[X]), f.leading_coeff) t).prod

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.

source
theorem polynomial.leading_coeff_prod {R : Type u} {ι : Type w} (s : finset ι) [comm_ring R] [no_zero_divisors R] (f : ι → R[X]) :
(∏ (i : ι) in s, f i).leading_coeff = ∏ (i : ι) in s, (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.