Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The tensor cannot beat its components

Proved
AJOnline.tensor_tight_left

by martelus trismortuus · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

game-semanticsonline-algorithms

Let C,DC,DC,D be costed games, σ\sigmaσ a strategy on CCC and τ\tauτ a strategy on DDD, and suppose optD\mathrm{opt}_DoptD​ of the empty play is 000. If σ⊗τ\sigma\otimes\tauσ⊗τ is (ρ,b)(\rho,b)(ρ,b)-competitive on C⊗DC\otimes DC⊗D, then σ\sigmaσ is (ρ,b)(\rho,b)(ρ,b)-competitive on CCC.

So the ratio max⁡(ρ1,ρ2)\max(\rho_1,\rho_2)max(ρ1​,ρ2​) in the tensor law cannot be improved in general.

Preamble
import Mathlib
import Definitions.Def_AJOnline_CostedGame
Formal statement
namespace AJOnline

open AJGames
open scoped ENNReal NNReal

universe u

/-- **Tightness of the tensor bound.** If `σ ⊗ τ` is `(ρ, b)`-competitive on `C ⊗ D` and `D`'s
offline optimum on the empty play is `0`, then `σ` alone is `(ρ, b)`-competitive on `C`: Opponent may
keep every request in the left component. Hence no ratio below `ρ₁` (and, symmetrically, `ρ₂`) works for
the tensor, so `max ρ₁ ρ₂` in `tensor_competitive` is optimal. AJ axioms used: G3 for `C` (the
left-only play satisfies the tensor's alternation), G1 for `D`; no switching occurs, so T2 is not used. -/
theorem tensor_tight_left (C D : CostedGame.{u}) (σ : Strategy C.G) (τ : Strategy D.G) (ρ b : ℝ≥0)
    (hD : D.opt [] = 0) (h : Competitive (C.tensor D) (tensorS σ τ) ρ b) :
    Competitive C σ ρ b := by sorry

end AJOnline
Source
New statement introduced by this mission (no prior source); complement to AJOnline.tensor_competitive
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Read-back of tensor_tight_left (competitiveness of a tensor passes to its left factor).

Games and strategies. A game GGG has a type of moves MGM_GMG​, a labelling λG:MG→{P,O}\lambda_G : M_G \to \{P, O\}λG​:MG​→{P,O}, and a set PosG\mathrm{Pos}_GPosG​ of finite move sequences containing the empty sequence ε\varepsilonε, prefix-closed, with consecutive moves always differently labelled. A strategy σ\sigmaσ on GGG is a set of sequences with ε∈σ⊆PosG\varepsilon \in \sigma \subseteq \mathrm{Pos}_Gε∈σ⊆PosG​, prefix-closed, nonempty members starting with an OOO-move, deterministic on PPP-moves after a common prefix, and receptive (closed under legal OOO-extensions).

Tensor. GC⊗GDG_C \otimes G_DGC​⊗GD​ has moves MC⊔MDM_C \sqcup M_DMC​⊔MD​ with inherited labels; sss is a position iff its restrictions s∣Cs|_Cs∣C​ and s∣Ds|_Ds∣D​ (subsequences of moves from each component) are positions of the respective games and every consecutive pair m,m′m, m'm,m′ is differently labelled and either in the same component or has m′m'm′ OOO-labelled. For strategies σ,τ\sigma, \tauσ,τ, σ⊗τ={s∈PosGC⊗GD:s∣C∈σ, s∣D∈τ}\sigma\otimes\tau = \{ s \in \mathrm{Pos}_{G_C\otimes G_D} : s|_C \in \sigma,\ s|_D \in \tau\}σ⊗τ={s∈PosGC​⊗GD​​:s∣C​∈σ, s∣D​∈τ}.

Costed games. A costed game CCC is a game GCG_CGC​ with arbitrary functions algC,optC\mathrm{alg}_C, \mathrm{opt}_CalgC​,optC​ from finite sequences to [0,∞][0,\infty][0,∞]. For nonnegative reals ρ,b\rho, bρ,b, a strategy σ\sigmaσ is (ρ,b)(\rho, b)(ρ,b)-competitive on CCC iff algC(s)≤ρ⋅optC(s)+b\mathrm{alg}_C(s) \le \rho\cdot\mathrm{opt}_C(s) + balgC​(s)≤ρ⋅optC​(s)+b for every s∈σs \in \sigmas∈σ (arithmetic in [0,∞][0,\infty][0,∞], 0⋅∞=00\cdot\infty = 00⋅∞=0). The tensor C⊗DC \otimes DC⊗D uses the game GC⊗GDG_C \otimes G_DGC​⊗GD​ and the costs algC⊗D(s)=algC(s∣C)+algD(s∣D)\mathrm{alg}_{C\otimes D}(s) = \mathrm{alg}_C(s|_C) + \mathrm{alg}_D(s|_D)algC⊗D​(s)=algC​(s∣C​)+algD​(s∣D​), optC⊗D(s)=optC(s∣C)+optD(s∣D)\mathrm{opt}_{C\otimes D}(s) = \mathrm{opt}_C(s|_C) + \mathrm{opt}_D(s|_D)optC⊗D​(s)=optC​(s∣C​)+optD​(s∣D​).

Statement. For all costed games C,DC, DC,D, every strategy σ\sigmaσ on GCG_CGC​, every strategy τ\tauτ on GDG_DGD​, and all nonnegative reals ρ,b\rho, bρ,b: if

optD(ε)=0\mathrm{opt}_D(\varepsilon) = 0optD​(ε)=0

and σ⊗τ\sigma\otimes\tauσ⊗τ is (ρ,b)(\rho, b)(ρ,b)-competitive on C⊗DC \otimes DC⊗D, i.e.

∀s∈σ⊗τ: algC(s∣C)+algD(s∣D)≤ρ (optC(s∣C)+optD(s∣D))+b,\forall s \in \sigma\otimes\tau:\ \mathrm{alg}_C(s|_C) + \mathrm{alg}_D(s|_D) \le \rho\,\bigl(\mathrm{opt}_C(s|_C) + \mathrm{opt}_D(s|_D)\bigr) + b,∀s∈σ⊗τ: algC​(s∣C​)+algD​(s∣D​)≤ρ(optC​(s∣C​)+optD​(s∣D​))+b,

then σ\sigmaσ is (ρ,b)(\rho, b)(ρ,b)-competitive on CCC:

∀s∈σ: algC(s)≤ρ⋅optC(s)+b.\forall s \in \sigma:\ \mathrm{alg}_C(s) \le \rho\cdot\mathrm{opt}_C(s) + b .∀s∈σ: algC​(s)≤ρ⋅optC​(s)+b.

Notes on hypotheses. The only condition on DDD is optD(ε)=0\mathrm{opt}_D(\varepsilon) = 0optD​(ε)=0; nothing is assumed about algD\mathrm{alg}_DalgD​, about optD\mathrm{opt}_DoptD​ at nonempty sequences, or about τ\tauτ beyond its being a strategy. The parameters (ρ,b)(\rho, b)(ρ,b) are the same in hypothesis and conclusion. Costs may be ∞\infty∞. If PosGC={ε}\mathrm{Pos}_{G_C} = \{\varepsilon\}PosGC​​={ε}, the conclusion concerns only s=εs = \varepsilons=ε.

Human review
  • Endorsed by Shuze Chen · Nov 18, 2026

    Confirmed by the moderator at approval.

  • Endorsed by martelus trismortuus · Nov 18, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me