AFTD Auto-Formalizing Theoretical Domains

Loomis.loomis_theorem

theoremverifiedformalizationimported Lean

Loomis Theorem [MFoGT, Theorem 2.5.1]. For any pair of matrices A B : I → J → ℝ with B entrywise positive, there exist mixed strategies x : Δ(I), y : Δ(J) and a value v : ℝ such that for every column j ∈ J and every row i ∈ I, $$ v \cdot (xB)_j \le (xA)_j, \qquad (Ay)_i \le v \cdot (By)_i. $$ The common value v = lamB0 A B = muB0 A B.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Loomis in
open Finset BigOperators in
set_option linter.unusedSectionVars false in
variable {I J : Type*} [Fintype I] [Fintype J] [Nonempty I] [Nonempty J] in
theorem Loomis.loomis_theorem (A B : I → J → ℝ) (hB : IsPositive B) :
    ∃ (x : stdSimplex ℝ I) (y : stdSimplex ℝ J) (v : ℝ),
      (∀ j, v * xB B x j ≤ xA A x j) ∧
      (∀ i, Ay A y i ≤ v * By B y i)
Formalizes
EconCSLib, `Loomis.loomis_theorem`
Lean proof
By xbei (from the file's git history), from github.com/gametheoryinlean/EconCSLib at 1a88f809b538 (Copyright (c) 2026 EconCSLib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.30.0.
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 11
  • Loomis.loomis_value_eqLoomis scalar equality: every finite positive-B matrix pair over ℝ has equal maxmin and minmax Loomis ratios.
  • Loomis.IsPositiveA matrix B : I → J → ℝ is entrywise positive if every entry is > 0. This is the hypothesis driving the general Loomis theorem, and…
  • Loomis.xBRow-vector product (xB)_j = ∑ᵢ xᵢ Bᵢⱼ.
  • Loomis.xARow-vector product (xA)_j = ∑ᵢ xᵢ Aᵢⱼ.
  • Loomis.AyColumn-vector product (Ay)_i = ∑ⱼ Aᵢⱼ yⱼ.
  • Loomis.ByColumn-vector product (By)_i = ∑ⱼ Bᵢⱼ yⱼ.
  • Loomis.lamB0Maxmin Loomis scalar λ₀ = sup_x λ_aux(x).
  • Loomis.exists_xx_lamB0Attainment of lamB0: there exists a mixed strategy xx with (xA xx)_j ≥ lamB0 · (xB xx)_j for every column.
  • Loomis.muB0Minmax Loomis scalar μ₀ = inf_y μ_aux(y).
  • Loomis.exists_yy_muB0Attainment of muB0: there exists a mixed strategy yy with (Ay yy)_i ≤ muB0 · (By yy)_i for every row.
  • wsum_pure_applyWeighted sum at a point mass evaluates the chosen coordinate.
Used by 1

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen Loomis inopen Finset BigOperators inset_option linter.unusedSectionVars false invariable {I J : Type*} [Fintype I] [Fintype J] [Nonempty I] [Nonempty J] in/-- **Loomis Theorem** [MFoGT, Theorem 2.5.1]. For any pair of matrices `A B : I → J → ℝ` with `B` entrywise positive, there exist mixed strategies `x : Δ(I)`, `y : Δ(J)` and a value `v : ℝ` such that for every column `j ∈ J` and every row `i ∈ I`, $$ v \cdot (xB)_j \le (xA)_j, \qquad (Ay)_i \le v \cdot (By)_i. $$ The common value `v = lamB0 A B = muB0 A B`. -/theorem Loomis.loomis_theorem (A B : I → J → ℝ) (hB : IsPositive B) :    ∃ (x : stdSimplex ℝ I) (y : stdSimplex ℝ J) (v : ℝ),      (∀ j, v * xB B x j ≤ xA A x j) ∧      (∀ i, Ay A y i ≤ v * By B y i) := by  obtain ⟨x, Hx⟩ := exists_xx_lamB0 A B hB  obtain ⟨y, Hy⟩ := exists_yy_muB0 A B hB  refine ⟨x, y, lamB0 A B, Hx, fun i => ?_⟩  rw [loomis_value_eq A B hB]  exact Hy i
See it in the graphDiscuss this resultChallenge it