Theorem 20 — spectral-energy response law
OpenPreservePast.Supplement.theorem_20communication-complexitycontinual-learninginformation-theorymemory-lower-boundsp2o-gran-per-chapterp2o-plan-paperp2o-v1
Histories are the matrices with , ; a query reveals with , and the response must have rank at most , norm at most one, and excess at most over the best such approximation of , with probability for each fixed history and query. Let be the least register width. Fix . For , , , and , put
Then, with constants depending only on ,
In particular, for ,
For , ; for , no finite message suffices. For , the output and comparator are zero, so at every nonnegative tolerance.
The maximization chooses how many directions can carry energy ; the law covers all precisions, including the small improvement over the zero response near .
Differences from the source:
- encoding: c_δΦ ≤ B* ≤ C_δΦ and B* ≍_δ (…), with constants depending only on δ → c_δ, C_δ > 0 chosen after δ only; c_δ·X ≤ B for every achieving width and an achieving protocol of width ≤ C_δ·X; reason: two-part form of a least width; avoids the junk value of an infimum over an empty set
- encoding: B* = 0; no finite message suffices → a zero-bit achieving protocol exists; no protocol of any width achieves; reason: the meaning of the least width being zero or infinite
- reading: log in (242) and (244) → logarithm to base two; reason: §N.1 fixes base-two logarithms for the appendix; another base changes the bounds by a constant factor absorbed in c_δ, C_δ
Preamble
import Mathlib import Definitions.Def_PreservePast_Supplement_SpectralAchieves open MeasureTheory
Formal statement
namespace PreservePast.Supplement
/-- **Theorem 20 (Spectral-energy response law).** P. Xu, *Information Required to Preserve Past Learning*, STOC 2027 submission (held version,
PDF sha256 48013ceb…d00fa), Theorem 20, p.67 (PDF p.69),
eqs. (242)–(244).
Fix `0 < δ < 1/2`. For `d ≥ 2`, `1 ≤ E ≤ K ≤ d`, `m, r ≥ 1` and `0 < α < 1`:
(243) `c_δ Φ ≤ B* ≤ C_δ Φ`; (244) `B* ≍_δ E[1 + d(1−α)]` for `1 − κ₀ ≤ α < 1` and
`B* ≍_δ dK log(1 + E/(Kα))` for `0 < α ≤ 1 − κ₀`, `κ₀ = 1/1024`. For `α ≥ 1`, `B* = 0`; for
`α = 0` no finite message suffices; for `r = 0`, `B* = 0` at every nonnegative tolerance.
**Formalization Note.** `E` is real, `K, d, m, r` are natural numbers. The bounds on the least
width `B*` are stated in the two-part form of the published goal: a lower bound for every
achieving width (arbitrary public coins, coin spaces in `Type`) and an achieving protocol for
each upper bound; `B* = 0` is a zero-bit achieving protocol, and "no finite message suffices" is
that no width is achieved. The constants `c_δ, C_δ` are chosen after `δ` only. Logarithms are
base two (§N.1). The endpoint clauses are stated on the same parameter ranges
(`d ≥ 2`, `1 ≤ E ≤ K ≤ d`, `m ≥ 1`), with `r ≥ 1` for `α ≥ 1` and `α = 0`. -/
theorem theorem_20 :
∀ δ : ℝ, 0 < δ → δ < 1 / 2 → ∃ cδ Cδ : ℝ, 0 < cδ ∧ 0 < Cδ ∧
∀ (d K m r : ℕ) (E α : ℝ), 2 ≤ d → 1 ≤ E → E ≤ K → K ≤ d → 1 ≤ m →
(1 ≤ r → 0 < α → α < 1 →
((∀ (B : ℕ) (Ω : Type) [MeasurableSpace Ω] (P : Measure Ω)
(enc : Matrix (Fin K) (Fin d) ℝ → Ω → Fin (2 ^ B))
(dec : Fin (2 ^ B) → Ω → Matrix (Fin m) (Fin K) ℝ → Matrix (Fin m) (Fin d) ℝ),
SpectralAchieves E r α δ P enc dec → cδ * spectralPhi E K d α ≤ (B : ℝ)) ∧
∃ B : ℕ, (B : ℝ) ≤ Cδ * spectralPhi E K d α ∧
∃ (Ω : Type) (_ : MeasurableSpace Ω) (P : Measure Ω)
(enc : Matrix (Fin K) (Fin d) ℝ → Ω → Fin (2 ^ B))
(dec : Fin (2 ^ B) → Ω → Matrix (Fin m) (Fin K) ℝ → Matrix (Fin m) (Fin d) ℝ), SpectralAchieves E r α δ P enc dec) ∧
(1 - 1 / 1024 ≤ α →
(∀ (B : ℕ) (Ω : Type) [MeasurableSpace Ω] (P : Measure Ω)
(enc : Matrix (Fin K) (Fin d) ℝ → Ω → Fin (2 ^ B))
(dec : Fin (2 ^ B) → Ω → Matrix (Fin m) (Fin K) ℝ → Matrix (Fin m) (Fin d) ℝ),
SpectralAchieves E r α δ P enc dec → cδ * (E * (1 + d * (1 - α))) ≤ (B : ℝ)) ∧
∃ B : ℕ, (B : ℝ) ≤ Cδ * (E * (1 + d * (1 - α))) ∧
∃ (Ω : Type) (_ : MeasurableSpace Ω) (P : Measure Ω)
(enc : Matrix (Fin K) (Fin d) ℝ → Ω → Fin (2 ^ B))
(dec : Fin (2 ^ B) → Ω → Matrix (Fin m) (Fin K) ℝ → Matrix (Fin m) (Fin d) ℝ), SpectralAchieves E r α δ P enc dec) ∧
(α ≤ 1 - 1 / 1024 →
(∀ (B : ℕ) (Ω : Type) [MeasurableSpace Ω] (P : Measure Ω)
(enc : Matrix (Fin K) (Fin d) ℝ → Ω → Fin (2 ^ B))
(dec : Fin (2 ^ B) → Ω → Matrix (Fin m) (Fin K) ℝ → Matrix (Fin m) (Fin d) ℝ),
SpectralAchieves E r α δ P enc dec →
cδ * (d * K * Real.logb 2 (1 + E / (K * α))) ≤ (B : ℝ)) ∧
∃ B : ℕ, (B : ℝ) ≤ Cδ * (d * K * Real.logb 2 (1 + E / (K * α))) ∧
∃ (Ω : Type) (_ : MeasurableSpace Ω) (P : Measure Ω)
(enc : Matrix (Fin K) (Fin d) ℝ → Ω → Fin (2 ^ B))
(dec : Fin (2 ^ B) → Ω → Matrix (Fin m) (Fin K) ℝ → Matrix (Fin m) (Fin d) ℝ), SpectralAchieves E r α δ P enc dec)) ∧
(1 ≤ r → 1 ≤ α →
∃ (Ω : Type) (_ : MeasurableSpace Ω) (P : Measure Ω)
(enc : Matrix (Fin K) (Fin d) ℝ → Ω → Fin (2 ^ 0))
(dec : Fin (2 ^ 0) → Ω → Matrix (Fin m) (Fin K) ℝ → Matrix (Fin m) (Fin d) ℝ),
SpectralAchieves E r α δ P enc dec) ∧
(1 ≤ r → α = 0 →
∀ (B : ℕ) (Ω : Type) [MeasurableSpace Ω] (P : Measure Ω)
(enc : Matrix (Fin K) (Fin d) ℝ → Ω → Fin (2 ^ B))
(dec : Fin (2 ^ B) → Ω → Matrix (Fin m) (Fin K) ℝ → Matrix (Fin m) (Fin d) ℝ), ¬ SpectralAchieves E r α δ P enc dec) ∧
(r = 0 → 0 ≤ α →
∃ (Ω : Type) (_ : MeasurableSpace Ω) (P : Measure Ω)
(enc : Matrix (Fin K) (Fin d) ℝ → Ω → Fin (2 ^ 0))
(dec : Fin (2 ^ 0) → Ω → Matrix (Fin m) (Fin K) ℝ → Matrix (Fin m) (Fin d) ℝ),
SpectralAchieves E r α δ P enc dec) := by sorry
end PreservePast.Supplement
Source
P. Xu, Information Required to Preserve Past Learning, STOC 2027 submission (held version, PDF sha256 48013ceb55cb5da782f256c3a4d1c95195bee48a2f4d0b2ed1e22bccd96d00fa), Theorem 20, p.67 (PDF p.69), eqs. (242)–(244); Appendix N, p.66 (PDF p.68), eqs. (240)–(241)