Documentation

MIPRE.Background.Repetition.CommutingRepetition.MainTheorem.Constants

theorem CommutingRepetition.constant_choice {C c ε : } (hC : 1 C) (hc0 : 0 < c) (hc : c min (1 / 8) (min (1 / (8192 * C ^ 6)) (1 / 19200))) (hε0 : 0 < ε) (hε1 : ε 1) (hℓ : 0 ) :
c * ε ^ 7 / (ε + ) c * ε ^ 6 c * ε ^ 7 / (ε + ) ε / 8 0 < ε / (4 * C) ε / (4 * C) 1

Constant choice (node 1.5.1; 07_main_theorem.tex, eqs universal-c-choice, gamma-xi-choice, gamma-greedy-condition): for C ≥ 1, c ≤ min{1/8, 1/(8192 C⁶), 1/19200}, 0 < ε ≤ 1, ℓ ≥ 0, the choices γ = c ε⁷/(ε + ℓ) and ξ = ε/(4C) satisfy the downstream hypotheses: γ ≤ c ε⁶ ≤ ε/8 and 0 < ξ ≤ 1.

theorem CommutingRepetition.counterexample_extraction {X Y A B : Type} [Fintype X] [Fintype Y] [Fintype A] [Fintype B] [Nonempty X] [Nonempty Y] [Nonempty A] [Nonempty B] (G : Game X Y A B) (n : ) {γ : } (hsup : Real.exp (-(γ * n)) < (G.repeat n).omegaCO) :
∃ (Trep : TracialStrategy (Fin nX) (Fin nY) (Fin nA) (Fin nB)), Real.exp (-(γ * n)) < (G.repeat n).win Trep.correlation

Counterexample extraction (node 1.5.2; 07_main_theorem.tex, eq alleged-repeated-counterexample and following): if the repeated value exceeds e^{−γn}, the strict tracial reduction at H = G^{⊗n}, λ = e^{−γn} yields an exact tracially embeddable repeated strategy with success still above e^{−γn}. No attainment is used.

theorem CommutingRepetition.eta_delta_bounds {c ε η Δ : } (hc0 : 0 < c) (hc : c 1 / 8) (hε0 : 0 < ε) (hε1 : ε 1) (hℓ : 0 ) ( : η 8 * (c * ε ^ 7 / (ε + )) * ((ε + ) / ε)) ( : Δ 16 * η) :
η 8 * c * ε ^ 6 8 * c * ε ^ 6 1 Δ 128 * c * ε ^ 6

Pre-rounding parameter arithmetic (node 1.5.3; 07_main_theorem.tex, eq main-q-eta-delta): with γ = c ε⁷/(ε + ℓ) and c ≤ 1/8, the pre-rounding outputs satisfy η ≤ 8cε⁶ ≤ 1 and Δ ≤ 128cε⁶.

theorem CommutingRepetition.contradiction_arithmetic {C c ε η Δ w : } (hC : 1 C) (hc0 : 0 < c) (hc : c min (1 / 8) (min (1 / (8192 * C ^ 6)) (1 / 19200))) (hε0 : 0 < ε) (hε1 : ε 1) (hη0 : 0 η) ( : η 8 * c * ε ^ 6) (hΔ0 : 0 Δ) ( : Δ 128 * c * ε ^ 6) (hw : 1 - ε / 4 - C / 2 * (Δ ^ (1 / 6) + ε / (4 * C)) - 5 * (3 * η / 2) w) :
1 - 3 * ε / 4 w

Arithmetic contradiction (node 1.5.4; 07_main_theorem.tex, eqs explicit-one-shot-lower-bound, strict-one-shot-contradiction): inserting η ≤ 8cε⁶, Δ ≤ 128cε⁶, ξ = ε/(4C) into the one-shot payoff bound w ≥ 1 − ε/4 − (C/2)(Δ^{1/6} + ξ) − 5√(3η/2) forces w ≥ 1 − 3ε/4: the three displayed losses are at most ε/4, ε/8, ε/8 by the constraints (128c)^{1/6} ≤ 1/(2C), (C/2)ξ = ε/8, 5√(12c) ≤ 1/8.

theorem CommutingRepetition.predicate_case :
∃ (c : ), 0 < c ∀ (X Y A B : Type) [inst : Fintype X] [inst_1 : Fintype Y] [inst_2 : Fintype A] [inst_3 : Fintype B] [Nonempty X] [Nonempty Y] [Nonempty A] [Nonempty B] (G : Game X Y A B), G.IsPredicate∀ (n : ), 1 n(G.repeat n).omegaCO Real.exp (-(c * ((1 - G.omegaCO) ^ 7 / (1 - G.omegaCO + Real.log ((Fintype.card A) * (Fintype.card B))))) * n)

The predicate case (node 1.5; 07_main_theorem.tex sec 7.3): the uniform repetition bound for games whose payoff is a predicate. If ω^co(G^{⊗n}) > e^{−γn} then nodes 1.1, 1.2, 1.3, 1.4 produce a legal one-shot strategy with win_G ≥ 1 − 3ε/4 > 1 − ε = ω^co(G), contradicting the definition of the supremum (attainment of neither value is needed).