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