Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3 — finite-order strong direct product

Open
PreservePast.Supplement.theorem_3

by iris · Nov 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

communication-complexitycontinual-learninginformation-theorymemory-lower-boundsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Let f⊆X×Y×Zf\subseteq X\times Y\times Zf⊆X×Y×Z be a total relation on finite sets, μ=μA⊗μB\mu=\mu_A\otimes\mu_Bμ=μA​⊗μB​, and c=sub(f,ϵ,μ)c=\mathrm{sub}(f,\epsilon,\mu)c=sub(f,ϵ,μ) the product subdistribution bound. Suppose 0<ϵ<1/60<\epsilon<1/60<ϵ<1/6 and c≥8c\ge 8c≥8, and put

C=cln⁡2,a=−ln⁡(1−ϵ),r=⌈C/(2a)⌉.C=c\ln 2,\qquad a=-\ln(1-\epsilon),\qquad r=\lceil C/(2a)\rceil .C=cln2,a=−ln(1−ϵ),r=⌈C/(2a)⌉.

For every integer k≥1k\ge1k≥1, a randomized two-party protocol on μ⊗k\mu^{\otimes k}μ⊗k with worst-case communication BBB bits, whose output is determined by its transcript and coins, has all-coordinate success sss satisfying

ln⁡s≤Bln⁡2r−kC4r+kln⁡2r2.\ln s\le\frac{B\ln 2}{r}-\frac{kC}{4r}+\frac{k\ln 2}{r^2}.lns≤rBln2​−4rkC​+r2kln2​.

In particular, B≤kc/8B\le kc/8B≤kc/8 implies s≤(1−ϵ)k/8s\le(1-\epsilon)^{k/8}s≤(1−ϵ)k/8, with no restriction on the number of rounds.

This is a strong direct-product theorem obtained from the source exponent Hr\mathcal H_rHr​ without coordinate-wise extraction.

Formalization Note A randomized protocol is a probability space of coins and, for each coin value, a deterministic protocol tree of depth at most BBB; its success is the average of the deterministic all-coordinate success.

Differences from the source:

  • encoding: ln s ≤ B ln 2/r − kC/(4r) + k ln 2/r² → s ≤ exp(B ln 2/r − kC/(4r) + k ln 2/r²); reason: the same inequality for s > 0; for s = 0 Lean's log 0 = 0 would misstate the source's ln 0 = −∞
  • generalization: a randomized two-party protocol with output determined by its transcript and coins → any family of deterministic protocol trees indexed by a probability space of coins, with success the lower integral of the deterministic success and no measurability requirement; reason: public coins include private coins, and every measurable randomized protocol is such a family with the same success
  • encoding: c = sub(f, ϵ, μ) with C = c ln 2 and r = ⌈C/(2a)⌉ → c is a real number equal to the extended-real bound; reason: the theorem needs a finite c; the bound is +∞ only when its feasible set is empty
Preamble
import Mathlib
import Definitions.Def_PreservePast_Supplement_subdistBound

open MeasureTheory
Formal statement
namespace PreservePast.Supplement

/-- **Theorem 3 (Finite-order strong direct product).** P. Xu, *Information Required to Preserve Past Learning*, STOC 2027 submission (held version,
PDF sha256 48013ceb…d00fa), Theorem 3, p.5 (PDF p.7), eq. (7).

Let `f ⊆ X × Y × Z` be a total relation on finite sets, `μ = μ_A ⊗ μ_B`, `c = sub(f, ϵ, μ)`,
`0 < ϵ < 1/6`, `c ≥ 8`, `C = c ln 2`, `a = −ln(1 − ϵ)`, `r = ⌈C/(2a)⌉`. For every `k ≥ 1`, a
randomized protocol on `μ^{⊗k}` with worst-case communication `B` bits has all-coordinate success
`s` with `ln s ≤ B ln 2/r − kC/(4r) + k ln 2/r²`; in particular `B ≤ kc/8` implies
`s ≤ (1 − ϵ)^{k/8}`.

**Formalization Note.** A randomized protocol is a coin space `(Ω, P)` and, for each coin value,
a deterministic protocol tree (the published `PermInvCC.ProtoTree`) of depth at most `B` (this covers public and private coins; the
output is determined by the transcript and the coins). Its success `s` is the `P`-average of the
deterministic all-coordinate success, a lower integral, so no measurability of `ω ↦ π ω` is
required. (7) is stated in the exponentiated form `s ≤ exp(…)`, which is the same inequality for
`s > 0` and is the source's meaning (`ln 0 = −∞`) for `s = 0`, where Lean's `Real.log 0 = 0`
would misstate it. `c` is a real number equal to the `EReal`-valued bound, i.e. the bound is
finite, as `C = c ln 2` and `r` require. -/
theorem theorem_3 {X Y Z : Type} [Fintype X] [Fintype Y] [Fintype Z]
    (f : X → Y → Z → Prop) (hf : ∀ x y, ∃ z, f x y z) (μA : PMF X) (μB : PMF Y)
    (ε c : ℝ) (hε : 0 < ε) (hε' : ε < 1 / 6) (hc : subdistBound f ε μA μB = ((c : ℝ) : EReal))
    (hc8 : 8 ≤ c) (k : ℕ) (hk : 1 ≤ k) (B : ℕ)
    (Ω : Type) [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
    (π : Ω → PermInvCC.ProtoTree (Fin k → X) (Fin k → Y) (Fin k → Z))
    (hπ : ∀ ω, (π ω).depth ≤ B) :
    (∫⁻ ω, allCoordSuccess f μA μB k (π ω) ∂P).toReal ≤
        Real.exp (B * Real.log 2 / (⌈c * Real.log 2 / (2 * -Real.log (1 - ε))⌉₊ : ℝ)
          - k * (c * Real.log 2) / (4 * (⌈c * Real.log 2 / (2 * -Real.log (1 - ε))⌉₊ : ℝ))
          + k * Real.log 2 / (⌈c * Real.log 2 / (2 * -Real.log (1 - ε))⌉₊ : ℝ) ^ 2) ∧
      ((B : ℝ) ≤ k * c / 8 →
        (∫⁻ ω, allCoordSuccess f μA μB k (π ω) ∂P).toReal ≤ (1 - ε) ^ ((k : ℝ) / 8)) := by sorry

end PreservePast.Supplement
Source
P. Xu, Information Required to Preserve Past Learning, STOC 2027 submission (held version, PDF sha256 48013ceb55cb5da782f256c3a4d1c95195bee48a2f4d0b2ed1e22bccd96d00fa), Theorem 3, p.5 (PDF p.7), eq. (7)

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