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

• AddMonoidAlgebra.supDegree: the sup-degree taking values in WithBot A,
• AddMonoidAlgebra.infDegree: the inf-degree taking values in WithTop A.

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

• the sup-degree is the maximum of the exponents of the monomials that appear with non-zero coefficient in f, or ⊥, if f = 0;
• the inf-degree is the minimum of the exponents of the monomials that appear with non-zero coefficient in f, or ⊤, if f = 0.

The main results are

• AddMonoidAlgebra.supDegree_mul_le: the sup-degree of a product is at most the sum of the sup-degrees,
• AddMonoidAlgebra.le_infDegree_mul: the inf-degree of a product is at least the sum of the inf-degrees,
• AddMonoidAlgebra.supDegree_add_le: the sup-degree of a sum is at most the sup of the sup-degrees,
• AddMonoidAlgebra.le_infDegree_add: the inf-degree of a sum is at least the inf of the inf-degrees.

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:

• once for supDegree (essentially a simple application) and
• once for infDegree (a simple application, via OrderDual).

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_3} {B : Type u_5} [SemilatticeSup B] [OrderBot B] [Semiring R] (degb : A → 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_add {R : Type u_1} {A : Type u_3} {T : Type u_4} [SemilatticeInf T] [OrderTop T] [Semiring R] (degt : A → T) (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_3} {B : Type u_5} [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 : A → B} (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_3} {T : Type u_4} [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 : A → T} (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_3} {B : Type u_5} [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 : A → B} (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_3} {T : Type u_4} [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 : A → T} (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_3} {B : Type u_5} [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 : A → B} (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_3} {T : Type u_4} [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 : A → T} (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_3} {B : 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 : A → B} (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_3} {T : Type u_4} [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 : A → T} (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_3} {B : Type u_5} {ι : Type u_6} [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 : A → B} (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_3} {T : Type u_4} {ι : Type u_6} [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 : A → T} (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_3} {B : Type u_5} [Semiring R] [SemilatticeSup B] [OrderBot B] (D : A → B) (f : AddMonoidAlgebra R A) : B

Let R be a semiring, let A be an AddZeroClass, 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

• AddMonoidAlgebra.supDegree D f = Finset.sup f.support D

theorem AddMonoidAlgebra.supDegree_add_le {R : Type u_1} {A : Type u_3} {B : Type u_5} [Semiring R] [AddZeroClass A] [SemilatticeSup B] [OrderBot B] {D : A → B} {f : AddMonoidAlgebra R A} {g : AddMonoidAlgebra R A} : AddMonoidAlgebra.supDegree D (f + g) ≤ AddMonoidAlgebra.supDegree D f ⊔ AddMonoidAlgebra.supDegree D g

@[simp]

theorem AddMonoidAlgebra.supDegree_neg {R' : Type u_2} {A : Type u_3} {B : Type u_5} [Ring R'] [AddZeroClass A] [SemilatticeSup B] [OrderBot B] {D : A → B} {f : AddMonoidAlgebra R' A} : AddMonoidAlgebra.supDegree D (-f) = AddMonoidAlgebra.supDegree D f

theorem AddMonoidAlgebra.supDegree_sub_le {R' : Type u_2} {A : Type u_3} {B : Type u_5} [Ring R'] [AddZeroClass A] [SemilatticeSup B] [OrderBot B] {D : A → B} {f : AddMonoidAlgebra R' A} {g : AddMonoidAlgebra R' A} : AddMonoidAlgebra.supDegree D (f - g) ≤ AddMonoidAlgebra.supDegree D f ⊔ AddMonoidAlgebra.supDegree D g

theorem AddMonoidAlgebra.supDegree_sum_le {R : Type u_1} {A : Type u_3} {B : Type u_5} [Semiring R] [SemilatticeSup B] [OrderBot B] {D : A → B} {ι : Type u_7} {s : Finset ι} {f : ι → AddMonoidAlgebra R A} : AddMonoidAlgebra.supDegree D (Finset.sum s fun (i : ι) => f i) ≤ Finset.sup s fun (i : ι) => AddMonoidAlgebra.supDegree D (f i)

theorem AddMonoidAlgebra.supDegree_single_ne_zero {R : Type u_1} {A : Type u_3} {B : Type u_5} [Semiring R] [SemilatticeSup B] [OrderBot B] {D : A → B} (a : A) {r : R} (hr : r ≠ 0) : AddMonoidAlgebra.supDegree D (AddMonoidAlgebra.single a r) = D a

theorem AddMonoidAlgebra.supDegree_single {R : Type u_1} {A : Type u_3} {B : Type u_5} [Semiring R] [AddZeroClass A] [SemilatticeSup B] [OrderBot B] {D : A → B} (a : A) (r : R) : AddMonoidAlgebra.supDegree D (AddMonoidAlgebra.single a r) = if r = 0 then ⊥ else D a

@[simp]

theorem AddMonoidAlgebra.supDegree_zero {R : Type u_1} {A : Type u_3} {B : Type u_5} [Semiring R] [AddZeroClass A] [SemilatticeSup B] [OrderBot B] {D : A → B} : AddMonoidAlgebra.supDegree D 0 = ⊥

theorem AddMonoidAlgebra.ne_zero_of_supDegree_ne_bot {R : Type u_1} {A : Type u_3} {B : Type u_5} [Semiring R] [AddZeroClass A] [SemilatticeSup B] [OrderBot B] {D : A → B} {p : AddMonoidAlgebra R A} : AddMonoidAlgebra.supDegree D p ≠ ⊥ → p ≠ 0

theorem AddMonoidAlgebra.ne_zero_of_not_supDegree_le {R : Type u_1} {A : Type u_3} {B : Type u_5} [Semiring R] [AddZeroClass A] [SemilatticeSup B] [OrderBot B] {D : A → B} {p : AddMonoidAlgebra R A} {b : B} (h : ¬AddMonoidAlgebra.supDegree D p ≤ b) : p ≠ 0

theorem AddMonoidAlgebra.apply_eq_zero_of_not_le_supDegree {R : Type u_1} {A : Type u_3} {B : Type u_5} [Semiring R] [SemilatticeSup B] [OrderBot B] {D : A → B} {p : AddMonoidAlgebra R A} {a : A} (hlt : ¬D a ≤ AddMonoidAlgebra.supDegree D p) : p a = 0

theorem AddMonoidAlgebra.supDegree_mul_le {R : Type u_1} {A : Type u_3} {B : Type u_5} [Semiring R] [AddZeroClass A] [SemilatticeSup B] [Add B] [OrderBot B] {D : A → B} {p : AddMonoidAlgebra R A} {q : AddMonoidAlgebra R A} (hadd : ∀ (a1 a2 : A), D (a1 + a2) = D a1 + D a2) [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] : AddMonoidAlgebra.supDegree D (p * q) ≤ AddMonoidAlgebra.supDegree D p + AddMonoidAlgebra.supDegree D q

theorem AddMonoidAlgebra.supDegree_prod_le {R : Type u_7} {A : Type u_8} {B : Type u_9} [CommSemiring R] [AddCommMonoid A] [AddCommMonoid B] [SemilatticeSup 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} (hzero : D 0 = 0) (hadd : ∀ (a1 a2 : A), D (a1 + a2) = D a1 + D a2) {ι : Type u_10} {s : Finset ι} {f : ι → AddMonoidAlgebra R A} : AddMonoidAlgebra.supDegree D (Finset.prod s fun (i : ι) => f i) ≤ Finset.sum s fun (i : ι) => AddMonoidAlgebra.supDegree D (f i)

theorem AddMonoidAlgebra.apply_add_of_supDegree_le {R : Type u_1} {A : Type u_3} {B : Type u_5} [Semiring R] [AddZeroClass A] [SemilatticeSup B] [Add B] [OrderBot B] {D : A → B} {p : AddMonoidAlgebra R A} {q : AddMonoidAlgebra R A} (hadd : ∀ (a1 a2 : A), D (a1 + a2) = D a1 + D a2) [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] (hD : Function.Injective D) {ap : A} {aq : A} (hp : AddMonoidAlgebra.supDegree D p ≤ D ap) (hq : AddMonoidAlgebra.supDegree D q ≤ D aq) : (p * q) (ap + aq) = p ap * q aq

theorem AddMonoidAlgebra.supDegree_withBot_some_comp {R : Type u_1} {A : Type u_3} {B : Type u_5} [Semiring R] [SemilatticeSup B] [OrderBot B] {D : A → B} {s : AddMonoidAlgebra R A} (hs : s.support.Nonempty) : AddMonoidAlgebra.supDegree (WithBot.some ∘ D) s = ↑(AddMonoidAlgebra.supDegree D s)

@[reducible]

def AddMonoidAlgebra.infDegree {R : Type u_1} {A : Type u_3} {T : Type u_4} [Semiring R] [SemilatticeInf T] [OrderTop T] (D : A → T) (f : AddMonoidAlgebra R A) : T

Let R be a semiring, let A be an AddZeroClass, 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

• AddMonoidAlgebra.infDegree D f = Finset.inf f.support D

theorem AddMonoidAlgebra.le_infDegree_add {R : Type u_1} {A : Type u_3} {T : Type u_4} [Semiring R] [AddZeroClass A] [SemilatticeInf T] [OrderTop T] (D : A → T) (f : AddMonoidAlgebra R A) (g : AddMonoidAlgebra R A) : AddMonoidAlgebra.infDegree D f ⊓ AddMonoidAlgebra.infDegree D g ≤ AddMonoidAlgebra.infDegree D (f + g)

theorem AddMonoidAlgebra.le_infDegree_mul {R : Type u_1} {A : Type u_3} {T : Type u_4} [Semiring R] [AddZeroClass A] [SemilatticeInf T] [Add 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 : AddHom A T) (f : AddMonoidAlgebra R A) (g : AddMonoidAlgebra R A) : AddMonoidAlgebra.infDegree (⇑D) f + AddMonoidAlgebra.infDegree (⇑D) g ≤ AddMonoidAlgebra.infDegree (⇑D) (f * g)

theorem AddMonoidAlgebra.infDegree_withTop_some_comp {R : Type u_1} {A : Type u_3} {T : Type u_4} [Semiring R] [SemilatticeInf T] [OrderTop T] {D : A → T} {s : AddMonoidAlgebra R A} (hs : s.support.Nonempty) : AddMonoidAlgebra.infDegree (WithTop.some ∘ D) s = ↑(AddMonoidAlgebra.infDegree D s)