Documentation

Linglib.Core.Algebra.Order.BigOperators.Ring.Finset

Weighted sums and the lexicographic order #

A weighted sum v ↦ ∑ i, w i * v i of vectors with entries at most M is strictly monotone for the lexicographic order exactly when each weight exceeds M times the sum of the weights after it (Pi.strictMonoOn_sum_mul_iff, for M ≥ 1). With the weights (M + 1) ^ (n - 1 - i) the sum is the base-M + 1 numeral whose digits are the vector, the canonical such weighting.

[UPSTREAM] candidate for Mathlib/Algebra/Order/BigOperators/Ring/Finset.lean.

theorem Pi.pos_of_forall_natCast_mul_sum_Ioi_lt {R : Type u_1} [CommRing R] [LinearOrder R] [IsStrictOrderedRing R] {n M : ℕ} {w : Fin n → R} (hw : ∀ (k : Fin n), ↑M * ∑ i > k, w i < w k) (k : Fin n) :
0 < w k
theorem Pi.strictMonoOn_sum_mul {R : Type u_1} [CommRing R] [LinearOrder R] [IsStrictOrderedRing R] {n M : ℕ} {w : Fin n → R} (hw : ∀ (k : Fin n), ↑M * ∑ i > k, w i < w k) :
StrictMonoOn (fun (v : Lex (Fin n → ℕ)) => ∑ i : Fin n, w i * ↑(ofLex v i)) {v : Lex (Fin n → ℕ) | ∀ (i : Fin n), ofLex v i ≤ M}
theorem Pi.strictMonoOn_sum_mul_iff {R : Type u_1} [CommRing R] [LinearOrder R] [IsStrictOrderedRing R] {n M : ℕ} {w : Fin n → R} (hM : 0 < M) :
StrictMonoOn (fun (v : Lex (Fin n → ℕ)) => ∑ i : Fin n, w i * ↑(ofLex v i)) {v : Lex (Fin n → ℕ) | ∀ (i : Fin n), ofLex v i ≤ M} ↔ ∀ (k : Fin n), ↑M * ∑ i > k, w i < w k