Theorem 8.1 — induction step in expectation
OpenRandOrderCSP.Supplement.theorem_8_1Fix integers and a -uniform hypergraph with vertex set of size . For let be its -fold blowup, with vertex set of size , and let be its Poisson sparsification (every edge of is copied an independent number of times). Write for the event that the incidence graph of is a forest, for the partition of into the vertex sets of the connected components of , and for the sets meeting no block of in exactly one element. For , is its set of nonzero coordinates and . Fourier coefficients are , and is the density of a distribution on . The family consists of all with and . A distribution is -bounded when for all , where is the Fourier envelope (5.3).
Theorem. There is such that for every there are and with the following property. For all integers , every , and every -bounded distribution on , if , then
The constant depends only on , and ; and depend also on , but not on , , , or .
This is the averaged form of the inductive step of the lower-bound argument: a Fourier-bounded prior, correlated against any bounded test function supported on singleton-free frequencies of an acyclic sparsified blowup, stays within the envelope at a worse but fixed constant. The paper deduces Theorem 5.10 (the high-probability inductive step) from it.
Formalization Note The random hypergraph is sparsify (blowup G n) c for a Poisson count vector c, and the expectation is a Lebesgue integral over c in ; the integrand is off . The supremum is taken in over the subtype of nonnegative sums, so it is the paper's real supremum (the set is nonempty, containing , and bounded). The summation variable is named W in Lean because V is the vertex type of . "-bounded distribution" is IsDistr D ∧ IsEnvBounded ζ s D; the published IsEnvBounded includes the condition under which the paper defines the envelope.
Differences from the source:
- encoding: finite vertex and edge sets, the copy set , and a distribution on →
Fintypecarrier/index types,Fin n, and a real mass function satisfyingIsDistr; reason: these are Lean representations of exactly the finite objects on the page, and theNeZero qinstance needed by Fourier coefficients is derived from rather than assumed. - encoding: (ζ, s)-bounded, with the envelope defined only for s ≤ (e²q⁴/ζ²)N → IsEnvBounded ζ s D includes that inequality as a conjunct; reason: the paper writes U_{ζ,s,N} only on that domain, so a (ζ, s)-bounded distribution satisfies it; σ is chosen after ζ, so no instance the page covers is excluded.
- encoding: E_H[[[Acy(H)]] sup_g …] over H ∼ Poi(G^n_∗, αn^{−(k−1)}) → ∫⁻ over the Poisson count vector of (if Acy then ⨆ over the subtype ℱ_U(s) else 0) in ℝ≥0∞; reason: H is a function of the count vector, and the inner sums are nonnegative and bounded, so the ℝ≥0∞ supremum and integral equal the paper's real ones.
import Mathlib import Definitions.Def_RandOrderCSP_optLP import Definitions.Def_RandOrderCSP_compPartition import Definitions.Def_RandOrderCSP_blockVol import Definitions.Def_RandOrderCSP_blowup import Definitions.Def_RandOrderCSP_poiLaw import Definitions.Def_RandOrderCSP_fourierCoeff import Definitions.Def_RandOrderCSP_envelope set_option autoImplicit false open MeasureTheory
namespace RandOrderCSP.Supplement
open scoped Classical in
/-- **Theorem 8.1 (induction step in expectation).** Singer, Tulsiani, Velusamy, *A dichotomy theorem for
approximating CSPs in random-order streams*, STOC 2027 submission (manuscript sha256 3aca9d2f…),
Theorem 8.1, p.35 (PDF p.39), display (8.2).
For fixed `q, k ≥ 2` and a `k`-uniform hypergraph `G∗` there is `α₀ > 0` such that for every `ζ ≥ 1`
there are `σ > 0` and `ζ′ ≥ 1` with: for all integers `n, s, r ≥ 1`, every `α ∈ (0, α₀)` and every
`(ζ, s)`-bounded distribution `D` on `ℤ_q^U` (`U = 𝒱_{G∗^n}`), if `1 ≤ r ≤ s ≤ σn` then, for
`H ∼ Poi(G∗^n, αn^{-(k-1)})`,
`E[ [[Acy(H)]] sup_{g ∈ ℱ_U(s)} ∑_{V, Z ∈ ℤ_q^U, supp(Z) ∈ SF_{𝒫_H}, wt(Z − V) = r} |μ̂_D(V)| |ĝ(Z)| ]
≤ U_{ζ′,s,N}(r)` with `N = |U| = n · v_{G∗}`.
**Formalization Note.** `H` is `sparsify (blowup G n) c` for a count vector `c ∼ poiLaw` at rate
`poiRate α n k`, and the expectation is the Lebesgue integral over `c` in `ℝ≥0∞`; the integrand is `0`
off `Acy(H)`. The supremum over `ℱ_U(s)` is an `ℝ≥0∞` supremum of the (nonnegative) inner sums, so it
equals the paper's real supremum (that set is nonempty, `g = 0`, and bounded). `μ_D` is
`density D = q^N · D` cast to `ℂ`. "`(ζ, s)`-bounded distribution" is `IsDistr D ∧ IsEnvBounded ζ s D`;
`IsEnvBounded` carries the conjunct `s ≤ (e²q⁴/ζ²)N` of the envelope's printed domain. The
`NeZero q` instance used by the Fourier definitions is derived from `hq`; it is not an additional
hypothesis. `α` ranges over the open interval `(0, α₀)`, as printed. -/
theorem theorem_8_1 {k q : ℕ} (hk : 2 ≤ k) (hq : 2 ≤ q) {V E : Type} [Fintype V]
[DecidableEq V] [Fintype E] (G : Hypergraph k V E) :
letI : NeZero q := ⟨by omega⟩
∃ α₀ : ℝ, 0 < α₀ ∧
∀ ζ : ℝ, 1 ≤ ζ →
∃ σ ζ' : ℝ, 0 < σ ∧ 1 ≤ ζ' ∧
∀ n s r : ℕ, 1 ≤ n → 1 ≤ s → 1 ≤ r → ∀ α : ℝ, 0 < α → α < α₀ →
∀ D : (V × Fin n → ZMod q) → ℝ, IsDistr D → IsEnvBounded ζ s D →
r ≤ s → (s : ℝ) ≤ σ * n →
∫⁻ c, (if (sparsify (blowup G n) c).Acy then
⨆ g : {g : (V × Fin n → ZMod q) → ℂ // InFamilyF (s : ℝ) g},
ENNReal.ofReal
(∑ W : V × Fin n → ZMod q,
∑ Z ∈ Finset.univ.filter (fun Z : V × Fin n → ZMod q =>
IsSF (sparsify (blowup G n) c).compPartition (vsupp Z) ∧
wt (Z - W) = r),
‖fourierCoeff (fun X => ((density D X : ℝ) : ℂ)) W‖ *
‖fourierCoeff g.1 Z‖)
else 0)
∂(poiLaw (E × (Fin k → Fin n)) (poiRate α n k)) ≤
ENNReal.ofReal (envelope q ζ' s (Fintype.card (V × Fin n)) r) := by sorry
end RandOrderCSP.Supplement