# mathlibdocumentation

data.mv_polynomial.variables

# Degrees and variables of polynomials

This file establishes many results about the degree and variable sets of a multivariate polynomial.

The variable set of a polynomial $P \in R[X]$ is a finset containing each $x \in X$ that appears in a monomial in $P$.

The degree set of a polynomial $P \in R[X]$ is a multiset containing, for each $x$ in the variable set, $n$ copies of $x$, where $n$ is the maximum number of copies of $x$ appearing in a monomial of $P$.

## Main declarations

• mv_polynomial.degrees p : the multiset of variables representing the union of the multisets corresponding to each non-zero monomial in p. For example if 7 ≠ 0 in R and p = x²y+7y³ then degrees p = {x, x, y, y, y}

• mv_polynomial.vars p : the finset of variables occurring in p. For example if p = x⁴y+yz then vars p = {x, y, z}

• mv_polynomial.degree_of n p : ℕ -- the total degree of p with respect to the variable n. For example if p = x⁴y+yz then degree_of y p = 1.

• mv_polynomial.total_degree p : ℕ -- the max of the sizes of the multisets s whose monomials X^s occur in p. For example if p = x⁴y+yz then total_degree p = 5.

## Notation

As in other polynomial files, we typically use the notation:

• σ τ : Type* (indexing the variables)

• R : Type* [comm_semiring R] (the coefficients)

• s : σ →₀ ℕ, a function from σ to ℕ which is zero away from a finite set. This will give rise to a monomial in mv_polynomial σ R which mathematicians might call X^s

• r : R

• i : σ, with corresponding monomial X i, often denoted X_i by mathematicians

• p : mv_polynomial σ R

### degrees

def mv_polynomial.degrees {R : Type u} {σ : Type u_1}  :

The maximal degrees of each variable in a multi-variable polynomial, expressed as a multiset.

(For example, degrees (x^2 * y + y^3) would be {x, x, y, y, y}.)

Equations
theorem mv_polynomial.degrees_monomial {R : Type u} {σ : Type u_1} (s : σ →₀ ) (a : R) :

theorem mv_polynomial.degrees_monomial_eq {R : Type u} {σ : Type u_1} (s : σ →₀ ) (a : R) :
a 0

theorem mv_polynomial.degrees_C {R : Type u} {σ : Type u_1} (a : R) :
= 0

theorem mv_polynomial.degrees_X {R : Type u} {σ : Type u_1} (n : σ) :
{n}

theorem mv_polynomial.degrees_zero {R : Type u} {σ : Type u_1}  :

theorem mv_polynomial.degrees_one {R : Type u} {σ : Type u_1}  :

theorem mv_polynomial.degrees_add {R : Type u} {σ : Type u_1} (p q : R) :

theorem mv_polynomial.degrees_sum {R : Type u} {σ : Type u_1} {ι : Type u_2} (s : finset ι) (f : ι → ) :
(∑ (i : ι) in s, f i).degrees s.sup (λ (i : ι), (f i).degrees)

theorem mv_polynomial.degrees_mul {R : Type u} {σ : Type u_1} (p q : R) :

theorem mv_polynomial.degrees_prod {R : Type u} {σ : Type u_1} {ι : Type u_2} (s : finset ι) (f : ι → ) :
(∏ (i : ι) in s, f i).degrees ∑ (i : ι) in s, (f i).degrees

theorem mv_polynomial.degrees_pow {R : Type u} {σ : Type u_1} (p : R) (n : ) :

theorem mv_polynomial.mem_degrees {R : Type u} {σ : Type u_1} {p : R} {i : σ} :
i p.degrees ∃ (d : σ →₀ ), 0 i d.support

theorem mv_polynomial.le_degrees_add {R : Type u} {σ : Type u_1} {p q : R} :
p.degrees (p + q).degrees

theorem mv_polynomial.degrees_add_of_disjoint {R : Type u} {σ : Type u_1} {p q : R} :
(p + q).degrees = p.degrees q.degrees

theorem mv_polynomial.degrees_map {R : Type u} {S : Type v} {σ : Type u_1} (p : R) (f : R →+* S) :

theorem mv_polynomial.degrees_rename {R : Type u} {σ : Type u_1} {τ : Type u_2} (f : σ → τ) (φ : R) :
φ).degrees

theorem mv_polynomial.degrees_map_of_injective {R : Type u} {S : Type v} {σ : Type u_1} (p : R) {f : R →+* S} :
( p).degrees = p.degrees

### vars

def mv_polynomial.vars {R : Type u} {σ : Type u_1}  :

vars p is the set of variables appearing in the polynomial p

Equations
@[simp]
theorem mv_polynomial.vars_0 {R : Type u} {σ : Type u_1}  :

@[simp]
theorem mv_polynomial.vars_monomial {R : Type u} {σ : Type u_1} {r : R} {s : σ →₀ }  :
r 0.vars = s.support

@[simp]
theorem mv_polynomial.vars_C {R : Type u} {σ : Type u_1} {r : R}  :

@[simp]
theorem mv_polynomial.vars_X {R : Type u} {σ : Type u_1} {n : σ} [nontrivial R] :
.vars = {n}

theorem mv_polynomial.mem_vars {R : Type u} {σ : Type u_1} {p : R} (i : σ) :
i p.vars ∃ (d : σ →₀ ) (H : d p.support), i d.support

theorem mv_polynomial.mem_support_not_mem_vars_zero {R : Type u} {σ : Type u_1} {f : R} {x : σ →₀ } (H : x f.support) {v : σ} :
v f.varsx v = 0

theorem mv_polynomial.vars_add_subset {R : Type u} {σ : Type u_1} (p q : R) :
(p + q).vars p.vars q.vars

theorem mv_polynomial.vars_add_of_disjoint {R : Type u} {σ : Type u_1} {p q : R} :
q.vars(p + q).vars = p.vars q.vars

theorem mv_polynomial.vars_mul {R : Type u} {σ : Type u_1} (φ ψ : R) :
* ψ).vars φ.vars ψ.vars

@[simp]
theorem mv_polynomial.vars_one {R : Type u} {σ : Type u_1}  :

theorem mv_polynomial.vars_pow {R : Type u} {σ : Type u_1} (φ : R) (n : ) :
^ n).vars φ.vars

theorem mv_polynomial.vars_prod {R : Type u} {σ : Type u_1} {ι : Type u_2} {s : finset ι} (f : ι → ) :
(∏ (i : ι) in s, f i).vars s.bind (λ (i : ι), (f i).vars)

The variables of the product of a family of polynomials are a subset of the union of the sets of variables of each polynomial.

theorem mv_polynomial.vars_C_mul {σ : Type u_1} {A : Type u_3} (a : A) (ha : a 0) (φ : A) :

theorem mv_polynomial.vars_sum_subset {R : Type u} {σ : Type u_1} {ι : Type u_3} (t : finset ι) (φ : ι → ) :
(∑ (i : ι) in t, φ i).vars t.bind (λ (i : ι), (φ i).vars)

theorem mv_polynomial.vars_sum_of_disjoint {R : Type u} {σ : Type u_1} {ι : Type u_3} (t : finset ι) (φ : ι → ) :
pairwise (disjoint on λ (i : ι), (φ i).vars)(∑ (i : ι) in t, φ i).vars = t.bind (λ (i : ι), (φ i).vars)

theorem mv_polynomial.vars_map {R : Type u} {S : Type v} {σ : Type u_1} (p : R) (f : R →+* S) :

theorem mv_polynomial.vars_map_of_injective {R : Type u} {S : Type v} {σ : Type u_1} (p : R) {f : R →+* S} :
( p).vars = p.vars

theorem mv_polynomial.vars_monomial_single {R : Type u} {σ : Type u_1} (i : σ) {e : } {r : R} :
e 0r 0 r).vars = {i}

theorem mv_polynomial.vars_eq_support_bind_support {R : Type u} {σ : Type u_1} (p : R) :

### degree_of

def mv_polynomial.degree_of {R : Type u} {σ : Type u_1}  :
σ →

degree_of n p gives the highest power of X_n that appears in p

Equations

### total_degree

def mv_polynomial.total_degree {R : Type u} {σ : Type u_1}  :

total_degree p gives the maximum |s| over the monomials X^s in p

Equations
theorem mv_polynomial.total_degree_eq {R : Type u} {σ : Type u_1} (p : R) :

theorem mv_polynomial.total_degree_le_degrees_card {R : Type u} {σ : Type u_1} (p : R) :

@[simp]
theorem mv_polynomial.total_degree_C {R : Type u} {σ : Type u_1} (a : R) :

@[simp]
theorem mv_polynomial.total_degree_zero {R : Type u} {σ : Type u_1}  :

@[simp]
theorem mv_polynomial.total_degree_one {R : Type u} {σ : Type u_1}  :

@[simp]
theorem mv_polynomial.total_degree_X {σ : Type u_1} {R : Type u_2} [nontrivial R] (s : σ) :

theorem mv_polynomial.total_degree_add {R : Type u} {σ : Type u_1} (a b : R) :

theorem mv_polynomial.total_degree_mul {R : Type u} {σ : Type u_1} (a b : R) :

theorem mv_polynomial.total_degree_pow {R : Type u} {σ : Type u_1} (a : R) (n : ) :

theorem mv_polynomial.total_degree_list_prod {R : Type u} {σ : Type u_1} (s : list R)) :

theorem mv_polynomial.total_degree_multiset_prod {R : Type u} {σ : Type u_1} (s : multiset R)) :

theorem mv_polynomial.total_degree_finset_prod {R : Type u} {σ : Type u_1} {ι : Type u_2} (s : finset ι) (f : ι → ) :
(s.prod f).total_degree ∑ (i : ι) in s, (f i).total_degree

theorem mv_polynomial.exists_degree_lt {R : Type u} {σ : Type u_1} [fintype σ] (f : R) (n : ) (h : f.total_degree < ) {d : σ →₀ } :
d f.support(∃ (i : σ), d i < n)

theorem mv_polynomial.coeff_eq_zero_of_total_degree_lt {R : Type u} {σ : Type u_1} {f : R} {d : σ →₀ } :
f.total_degree < ∑ (i : σ) in d.support, d i = 0

theorem mv_polynomial.total_degree_rename_le {R : Type u} {σ : Type u_1} {τ : Type u_2} (f : σ → τ) (p : R) :

### vars and eval

theorem mv_polynomial.eval₂_hom_eq_constant_coeff_of_vars {R : Type u} {S : Type v} {σ : Type u_1} (f : R →+* S) {g : σ → S} {p : R} :
(∀ (i : σ), i p.varsg i = 0) p =

theorem mv_polynomial.aeval_eq_constant_coeff_of_vars {R : Type u} {S : Type v} {σ : Type u_1} [ S] {g : σ → S} {p : R} :
(∀ (i : σ), i p.varsg i = 0) p =

theorem mv_polynomial.eval₂_hom_congr' {R : Type u} {S : Type v} {σ : Type u_1} {f₁ f₂ : R →+* S} {g₁ g₂ : σ → S} {p₁ p₂ : R} :
f₁ = f₂(∀ (i : σ), i p₁.varsi p₂.varsg₁ i = g₂ i)p₁ = p₂ g₁) p₁ = g₂) p₂

theorem mv_polynomial.vars_bind₁ {R : Type u} {σ : Type u_1} {τ : Type u_2} (f : σ → ) (φ : R) :
( φ).vars φ.vars.bind (λ (i : σ), (f i).vars)

theorem mv_polynomial.mem_vars_bind₁ {R : Type u} {σ : Type u_1} {τ : Type u_2} (f : σ → ) (φ : R) {j : τ} :
j ( φ).vars(∃ (i : σ), i φ.vars j (f i).vars)

theorem mv_polynomial.vars_rename {R : Type u} {σ : Type u_1} {τ : Type u_2} (f : σ → τ) (φ : R) :
φ).vars φ.vars

theorem mv_polynomial.mem_vars_rename {R : Type u} {σ : Type u_1} {τ : Type u_2} (f : σ → τ) (φ : R) {j : τ} :
j φ).vars(∃ (i : σ), i φ.vars f i = j)