Public Schur powers and real low-degree advantage
DefinitionExpandingCodes_PolynomialStretch_Supplement_AlgebraFor a simple -uniform hypergraph on , let be the binary column span of its incidence matrix, with coordinates the lexicographic list of present edges. The published Schur power is used over : it spans all -fold coordinatewise products of codewords, with repeated factors allowed. On all potential edges define
The constant monomial is excluded from the generating family. The robust-dimension event requires simultaneously for every satisfying the strict real comparison
This permits arbitrary additions before the deletions. A density sequence has exponent when it is eventually strictly between zero and one and .
For a fixed planted hypergraph , is the independent Bernoulli- background and adjoins an independent uniformly injected copy of . A test is a real multivariate polynomial in all potential-edge indicators, with total degree at most and positive variance under . Its normalized advantage is
The degree- advantage is the supremum over these values. Theorem 5.1 explicitly asserts that this set is nonempty, bounded above, and has a maximizer, as required by the source's word “maximum.” All expectations are finite sums, so nonintegrability cannot default an expectation to zero. Coefficients can depend arbitrarily on .
Formalization Note The total definitions return the usual Lean division and real-supremum defaults on invalid inputs; no result invokes them there. Theorem 4.2 is eventual and reaches . Theorem 5.1 has strict positive probability, positive variance in the admissible set, and a strictly positive real base .
import Mathlib
import Definitions.Def_ExpandingCodes_PolynomialStretch_Supplement_Hypergraphs
import Definitions.Def_QuantumGroupCodes836_Addressability_Linear
set_option autoImplicit false
open scoped BigOperators Classical
namespace ExpandingCodes.PolynomialStretch.Supplement
noncomputable section
/-- Column span, in the lexicographic order of present edges. -/
def publicCode {N k : ℕ} (G : Hypergraph N k) : Submodule Bit (Word (edgeCount G)) :=
Submodule.span Bit (Set.range fun v : Fin N => fun i => incidence G i v)
/-- No constant monomial: only 1≤|I|≤r. -/
def monomialSpace (N k r : ℕ) : Submodule Bit (Edge N k → Bit) :=
Submodule.span Bit {f | ∃ I : Finset (Fin N), 1 ≤ I.card ∧ I.card ≤ r ∧
f = fun e => ∏ i ∈ I, if i ∈ e.val then (1 : Bit) else 0}
def sliceDimension (N k r : ℕ) : ℕ := Module.finrank Bit (monomialSpace N k r)
def schurDimension {N k : ℕ} (G : Hypergraph N k) (r : ℕ) : ℕ :=
Module.finrank Bit (QuantumGroupCodes836.Addressability.schurPower (publicCode G) r)
def RobustDimension {N k : ℕ} (G : Hypergraph N k) (p : unitInterval) (r : ℕ) : Prop :=
∀ G' : Hypergraph N k,
((edgesFinset G \ edgesFinset G').card : ℝ) <
(p : ℝ) * Nat.choose N k / (2 * sliceDimension N k r) →
schurDimension G' r = sliceDimension N k r
/-- Arbitrary probability sequences with the source's little-o exponent. -/
def DensityExponent (p : ℕ → unitInterval) (β : ℝ) : Prop :=
(∀ᶠ N in Filter.atTop, 0 < (p N : ℝ) ∧ (p N : ℝ) < 1) ∧
Filter.Tendsto (fun N : ℕ => Real.log (p N : ℝ) / Real.log (N : ℝ))
Filter.atTop (nhds (-β))
abbrev TestPolynomial (N k : ℕ) := MvPolynomial (Edge N k) ℝ
def evaluate {N k : ℕ} (f : TestPolynomial N k) (G : Hypergraph N k) : ℝ :=
MvPolynomial.eval (fun e => if G e then 1 else 0) f
def nullMean {N k : ℕ} (p : unitInterval) (f : TestPolynomial N k) : ℝ :=
finiteMean (nullLaw N k p) (evaluate f)
def nullVariance {N k : ℕ} (p : unitInterval) (f : TestPolynomial N k) : ℝ :=
finiteMean (nullLaw N k p) fun G => (evaluate f G - nullMean p f) ^ 2
def normalizedAdvantage {n N k : ℕ} (H : Hypergraph n k) (p : unitInterval)
(f : TestPolynomial N k) : ℝ :=
|plantedMean H p (evaluate f) - nullMean p f| / Real.sqrt (nullVariance p f)
/-- The admissible set includes arbitrary H-dependent REAL coefficients. -/
def advantageValues {n N k : ℕ} (H : Hypergraph n k) (p : unitInterval) (D : ℕ) : Set ℝ :=
{a | ∃ f : TestPolynomial N k, f.totalDegree ≤ D ∧ 0 < nullVariance p f ∧
a = normalizedAdvantage H p f}
def degreeAdvantage {n N k : ℕ} (H : Hypergraph n k) (p : unitInterval) (D : ℕ) : ℝ :=
sSup (advantageValues (N := N) H p D)
end
end ExpandingCodes.PolynomialStretch.Supplement