Documentation

Mathlib.Algebra.MonoidAlgebra.Degree

Lemmas about the sup and inf of the support of AddMonoidAlgebra #

TODO #

The current plan is to state and prove lemmas about Finset.sup (Finsupp.support f) D with a "generic" degree/weight function D from the grading Type A to a somewhat ordered Type B.

Next, the general lemmas get specialized for some yet-to-be-defined degrees.

sup-degree and inf-degree of an AddMonoidAlgebra #

Let R be a semiring and let A be a SemilatticeSup. For an element f : R[A], this file defines

If the grading type A is a linearly ordered additive monoid, then these two notions of degree coincide with the standard one:

The main results are

Implementation notes #

The current plan is to state and prove lemmas about Finset.sup (Finsupp.support f) D with a "generic" degree/weight function D from the grading Type A to a somewhat ordered Type B. Next, the general lemmas get specialized twice:

These final lemmas are the ones that likely get used the most. The generic lemmas about Finset.support.sup may not be used directly much outside of this file. To see this in action, you can look at the triple (sup_support_mul_le, maxDegree_mul_le, le_minDegree_mul).

In this section, we use degb and degt to denote "degree functions" on A with values in a type with bot or top respectively.

theorem AddMonoidAlgebra.sup_support_add_le {R : Type u_1} {A : Type u_2} {B : Type u_4} [SemilatticeSup B] [OrderBot B] [Semiring R] (degb : AB) (f : AddMonoidAlgebra R A) (g : AddMonoidAlgebra R A) :
Finset.sup (f + g).support degb Finset.sup f.support degb Finset.sup g.support degb
theorem AddMonoidAlgebra.le_inf_support_add {R : Type u_1} {A : Type u_2} {T : Type u_3} [SemilatticeInf T] [OrderTop T] [Semiring R] (degt : AT) (f : AddMonoidAlgebra R A) (g : AddMonoidAlgebra R A) :
Finset.inf f.support degt Finset.inf g.support degt Finset.inf (f + g).support degt
theorem AddMonoidAlgebra.sup_support_mul_le {R : Type u_1} {A : Type u_2} {B : Type u_4} [SemilatticeSup B] [OrderBot B] [Semiring R] [Add A] [Add B] [CovariantClass B B (fun (x x_1 : B) => x + x_1) fun (x x_1 : B) => x x_1] [CovariantClass B B (Function.swap fun (x x_1 : B) => x + x_1) fun (x x_1 : B) => x x_1] {degb : AB} (degbm : ∀ {a b : A}, degb (a + b) degb a + degb b) (f : AddMonoidAlgebra R A) (g : AddMonoidAlgebra R A) :
Finset.sup (f * g).support degb Finset.sup f.support degb + Finset.sup g.support degb
theorem AddMonoidAlgebra.le_inf_support_mul {R : Type u_1} {A : Type u_2} {T : Type u_3} [SemilatticeInf T] [OrderTop T] [Semiring R] [Add A] [Add T] [CovariantClass T T (fun (x x_1 : T) => x + x_1) fun (x x_1 : T) => x x_1] [CovariantClass T T (Function.swap fun (x x_1 : T) => x + x_1) fun (x x_1 : T) => x x_1] {degt : AT} (degtm : ∀ {a b : A}, degt a + degt b degt (a + b)) (f : AddMonoidAlgebra R A) (g : AddMonoidAlgebra R A) :
Finset.inf f.support degt + Finset.inf g.support degt Finset.inf (f * g).support degt
theorem AddMonoidAlgebra.sup_support_list_prod_le {R : Type u_1} {A : Type u_2} {B : Type u_4} [SemilatticeSup B] [OrderBot B] [Semiring R] [AddMonoid A] [AddMonoid B] [CovariantClass B B (fun (x x_1 : B) => x + x_1) fun (x x_1 : B) => x x_1] [CovariantClass B B (Function.swap fun (x x_1 : B) => x + x_1) fun (x x_1 : B) => x x_1] {degb : AB} (degb0 : degb 0 0) (degbm : ∀ (a b : A), degb (a + b) degb a + degb b) (l : List (AddMonoidAlgebra R A)) :
Finset.sup (List.prod l).support degb List.sum (List.map (fun (f : AddMonoidAlgebra R A) => Finset.sup f.support degb) l)
theorem AddMonoidAlgebra.le_inf_support_list_prod {R : Type u_1} {A : Type u_2} {T : Type u_3} [SemilatticeInf T] [OrderTop T] [Semiring R] [AddMonoid A] [AddMonoid T] [CovariantClass T T (fun (x x_1 : T) => x + x_1) fun (x x_1 : T) => x x_1] [CovariantClass T T (Function.swap fun (x x_1 : T) => x + x_1) fun (x x_1 : T) => x x_1] {degt : AT} (degt0 : 0 degt 0) (degtm : ∀ (a b : A), degt a + degt b degt (a + b)) (l : List (AddMonoidAlgebra R A)) :
List.sum (List.map (fun (f : AddMonoidAlgebra R A) => Finset.inf f.support degt) l) Finset.inf (List.prod l).support degt
theorem AddMonoidAlgebra.sup_support_pow_le {R : Type u_1} {A : Type u_2} {B : Type u_4} [SemilatticeSup B] [OrderBot B] [Semiring R] [AddMonoid A] [AddMonoid B] [CovariantClass B B (fun (x x_1 : B) => x + x_1) fun (x x_1 : B) => x x_1] [CovariantClass B B (Function.swap fun (x x_1 : B) => x + x_1) fun (x x_1 : B) => x x_1] {degb : AB} (degb0 : degb 0 0) (degbm : ∀ (a b : A), degb (a + b) degb a + degb b) (n : ) (f : AddMonoidAlgebra R A) :
Finset.sup (f ^ n).support degb n Finset.sup f.support degb
theorem AddMonoidAlgebra.le_inf_support_pow {R : Type u_1} {A : Type u_2} {T : Type u_3} [SemilatticeInf T] [OrderTop T] [Semiring R] [AddMonoid A] [AddMonoid T] [CovariantClass T T (fun (x x_1 : T) => x + x_1) fun (x x_1 : T) => x x_1] [CovariantClass T T (Function.swap fun (x x_1 : T) => x + x_1) fun (x x_1 : T) => x x_1] {degt : AT} (degt0 : 0 degt 0) (degtm : ∀ (a b : A), degt a + degt b degt (a + b)) (n : ) (f : AddMonoidAlgebra R A) :
n Finset.inf f.support degt Finset.inf (f ^ n).support degt
theorem AddMonoidAlgebra.sup_support_multiset_prod_le {R : Type u_1} {A : Type u_2} {B : Type u_4} [SemilatticeSup B] [OrderBot B] [CommSemiring R] [AddCommMonoid A] [AddCommMonoid B] [CovariantClass B B (fun (x x_1 : B) => x + x_1) fun (x x_1 : B) => x x_1] [CovariantClass B B (Function.swap fun (x x_1 : B) => x + x_1) fun (x x_1 : B) => x x_1] {degb : AB} (degb0 : degb 0 0) (degbm : ∀ (a b : A), degb (a + b) degb a + degb b) (m : Multiset (AddMonoidAlgebra R A)) :
Finset.sup (Multiset.prod m).support degb Multiset.sum (Multiset.map (fun (f : AddMonoidAlgebra R A) => Finset.sup f.support degb) m)
theorem AddMonoidAlgebra.le_inf_support_multiset_prod {R : Type u_1} {A : Type u_2} {T : Type u_3} [SemilatticeInf T] [OrderTop T] [CommSemiring R] [AddCommMonoid A] [AddCommMonoid T] [CovariantClass T T (fun (x x_1 : T) => x + x_1) fun (x x_1 : T) => x x_1] [CovariantClass T T (Function.swap fun (x x_1 : T) => x + x_1) fun (x x_1 : T) => x x_1] {degt : AT} (degt0 : 0 degt 0) (degtm : ∀ (a b : A), degt a + degt b degt (a + b)) (m : Multiset (AddMonoidAlgebra R A)) :
Multiset.sum (Multiset.map (fun (f : AddMonoidAlgebra R A) => Finset.inf f.support degt) m) Finset.inf (Multiset.prod m).support degt
theorem AddMonoidAlgebra.sup_support_finset_prod_le {R : Type u_1} {A : Type u_2} {B : Type u_4} {ι : Type u_5} [SemilatticeSup B] [OrderBot B] [CommSemiring R] [AddCommMonoid A] [AddCommMonoid B] [CovariantClass B B (fun (x x_1 : B) => x + x_1) fun (x x_1 : B) => x x_1] [CovariantClass B B (Function.swap fun (x x_1 : B) => x + x_1) fun (x x_1 : B) => x x_1] {degb : AB} (degb0 : degb 0 0) (degbm : ∀ (a b : A), degb (a + b) degb a + degb b) (s : Finset ι) (f : ιAddMonoidAlgebra R A) :
Finset.sup (Finset.prod s fun (i : ι) => f i).support degb Finset.sum s fun (i : ι) => Finset.sup (f i).support degb
theorem AddMonoidAlgebra.le_inf_support_finset_prod {R : Type u_1} {A : Type u_2} {T : Type u_3} {ι : Type u_5} [SemilatticeInf T] [OrderTop T] [CommSemiring R] [AddCommMonoid A] [AddCommMonoid T] [CovariantClass T T (fun (x x_1 : T) => x + x_1) fun (x x_1 : T) => x x_1] [CovariantClass T T (Function.swap fun (x x_1 : T) => x + x_1) fun (x x_1 : T) => x x_1] {degt : AT} (degt0 : 0 degt 0) (degtm : ∀ (a b : A), degt a + degt b degt (a + b)) (s : Finset ι) (f : ιAddMonoidAlgebra R A) :
(Finset.sum s fun (i : ι) => Finset.inf (f i).support degt) Finset.inf (Finset.prod s fun (i : ι) => f i).support degt

Shorthands for special cases #

Note that these definitions are reducible, in order to make it easier to apply the more generic lemmas above.

@[reducible]
def AddMonoidAlgebra.supDegree {R : Type u_1} {A : Type u_2} {B : Type u_4} [Semiring R] [SemilatticeSup B] [OrderBot B] (D : AB) (f : AddMonoidAlgebra R A) :
B

Let R be a semiring, let A, B be two AddZeroClasses, let B be an OrderBot, and let D : A → B be a "degree" function. For an element f : R[A], the element supDegree f : B is the supremum of all the elements in the support of f, or if f is zero. Often, the Type B is WithBot A, If, further, A has a linear order, then this notion coincides with the usual one, using the maximum of the exponents.

Equations
Instances For
    theorem AddMonoidAlgebra.supDegree_mul_le {R : Type u_1} {A : Type u_2} {B : Type u_4} [Semiring R] [AddZeroClass A] [SemilatticeSup B] [AddZeroClass B] [OrderBot B] [CovariantClass B B (fun (x x_1 : B) => x + x_1) fun (x x_1 : B) => x x_1] [CovariantClass B B (Function.swap fun (x x_1 : B) => x + x_1) fun (x x_1 : B) => x x_1] (D : A →+ B) (f : AddMonoidAlgebra R A) (g : AddMonoidAlgebra R A) :
    @[reducible]
    def AddMonoidAlgebra.infDegree {R : Type u_1} {A : Type u_2} {T : Type u_3} [Semiring R] [SemilatticeInf T] [OrderTop T] (D : AT) (f : AddMonoidAlgebra R A) :
    T

    Let R be a semiring, let A, B be two AddZeroClasses, let T be an OrderTop, and let D : A → T be a "degree" function. For an element f : R[A], the element infDegree f : T is the infimum of all the elements in the support of f, or if f is zero. Often, the Type T is WithTop A, If, further, A has a linear order, then this notion coincides with the usual one, using the minimum of the exponents.

    Equations
    Instances For
      theorem AddMonoidAlgebra.le_infDegree_mul {R : Type u_1} {A : Type u_2} {T : Type u_3} [Semiring R] [AddZeroClass A] [SemilatticeInf T] [AddZeroClass T] [OrderTop T] [CovariantClass T T (fun (x x_1 : T) => x + x_1) fun (x x_1 : T) => x x_1] [CovariantClass T T (Function.swap fun (x x_1 : T) => x + x_1) fun (x x_1 : T) => x x_1] (D : A →+ T) (f : AddMonoidAlgebra R A) (g : AddMonoidAlgebra R A) :