Theorem 5.1 — Exact low-degree advantage bound for arbitrary planted hypergraphs
OpenExpandingCodes.PolynomialStretch.Supplement.low_degree_boundLet be any fixed simple -uniform hypergraph on with edges. Fix an integer , , and . Assume every of size at most spans at least vertices, and . The null law is ; the planted law adjoins an independently uniformly injected copy of all vertices of .
The maximal normalized difference of means over real polynomials of total degree at most with obeys
The maximum is attained: its defining set is nonempty and bounded, and an admissible maximizing polynomial exists. Coefficients may depend arbitrarily on . The power in the denominator is a real power. Empty , isolated vertices and remain allowed.
This unconditional companion theorem gives the non-asymptotic low-degree estimate for arbitrary planted hypergraphs; it does not assert hardness against general algorithms and is not used to prove the code-construction goal.
Differences from the source:
- encoding: the maximum normalized mean difference over real degree-D polynomials with positive null variance → a real supremum together with explicit nonemptiness, boundedness, and attainment in the conclusion; reason: prevents default supremum values from weakening the source maximum
- encoding: simple hypergraphs on [n], probabilities 0<p<1, and the exact bound (9) → finite edge-indicator coordinates, unit-interval probabilities with strict endpoint exclusions, finite expectations and Real.rpow; reason: retains all finite instances, all n vertices and the exact constants without integral or natural-subtraction defaults
import Definitions.Def_ExpandingCodes_PolynomialStretch_Supplement_Algebra set_option autoImplicit false
namespace ExpandingCodes.PolynomialStretch.Supplement
/-- Theorem 5.1. The maximum's nonemptiness, boundedness and attainment are explicit,
so the supremum cannot exploit a default value on an empty or unbounded set. -/
theorem low_degree_bound (n N k D : ℕ) (H : Hypergraph n k)
(hD : 1 ≤ D) (p : unitInterval) (hp : 0 < (p : ℝ)) (hp1 : (p : ℝ) < 1)
(hN : n ≤ N) (γ : ℝ) (hγ : 0 < γ) (hγ1 : γ ≤ 1)
(hexpand : PatternExpansion H D γ) (hcut : k * D < N - 1) :
(advantageValues (N := N) H p D).Nonempty ∧
BddAbove (advantageValues (N := N) H p D) ∧
(∃ f : TestPolynomial N k, f.totalDegree ≤ D ∧ 0 < nullVariance p f ∧
normalizedAdvantage H p f = degreeAdvantage (N := N) H p D) ∧
degreeAdvantage (N := N) H p D ≤
Real.sqrt (Real.exp ((Nat.factorial k : ℝ) * (edgeCount H : ℝ) ^ 2 * (1 - (p : ℝ)) /
((p : ℝ) * Real.rpow ((N : ℝ) - (k * D : ℕ)) (γ * k))) - 1) := by sorry
end ExpandingCodes.PolynomialStretch.Supplement