Theorem 4.2 — Robust Schur-power dimension of the public code
OpenExpandingCodes.PolynomialStretch.Supplement.robust_schur_dimensionFix positive integers and a real with and . Let be any probability sequence with , interpreted as eventual strict probabilities and . Let and be the full constant-weight-slice space and its actual dimension defined above.
Set . There is a threshold depending on the fixed parameters and density sequence such that, for every larger , with probability at least
over , every simple -uniform hypergraph on the same vertices with
satisfies . The event is simultaneous over all and permits arbitrary edge additions. The deletion comparison is strict and real-valued.
This companion theorem supplies a common full-product-dimension benchmark for random and planted public matrices, including the stated punctures. It is not a lemma used to prove the mission's code-construction goal.
Formalization Note The displayed failure exponent instantiates the source's : the union bound on printed p. 23 / PDF p. 24 gives , which is eventually at most under the strict gap. No density sequence is fixed to a special example.
Differences from the source:
- encoding: failure exp(-N^{Omega(1)}) for every density p=N^{-beta+o(1)} → failure exp(-N^{(k-beta-r)/2}) with a sequence-dependent eventual threshold; reason: the proof on printed p. 23 bounds failure by 2^{s_r} exp(-p binom(N,k)/(8s_r)); the strict gap makes this exponent permissible
- encoding: edge-indexed binary codes and arbitrary additions followed by fewer than p binom(N,k)/(2s_r) deletions → lexicographically ordered finite coordinates and the strict real bound on E(G) minus E(G prime); reason: identifies precisely the same simultaneous event and imports only the ordinary Schur power
import Definitions.Def_ExpandingCodes_PolynomialStretch_Supplement_Algebra set_option autoImplicit false
namespace ExpandingCodes.PolynomialStretch.Supplement
/-- Theorem 4.2. The proof's union bound supplies the fixed failure exponent
(k-β-r)/2; the threshold may depend on the entire density sequence p. -/
theorem robust_schur_dimension (k r : ℕ) (β : ℝ)
(hk : 0 < k) (hr : 0 < r) (hβ : 0 < β) (hβk : β < k)
(hgap : 2 * (r : ℝ) < (k : ℝ) - β)
(p : ℕ → unitInterval) (hp : DensityExponent p β) :
∃ N₀ : ℕ, 2 ≤ N₀ ∧ ∀ N : ℕ, N₀ ≤ N →
1 - Real.exp (-(N : ℝ) ^ (((k : ℝ) - β - r) / 2)) ≤
finiteProb (nullLaw N k (p N)) (fun G => RobustDimension G (p N) r) := by sorry
end ExpandingCodes.PolynomialStretch.Supplement