Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite unmarked and marked hypergraph experiments

Definition
ExpandingCodes_PolynomialStretch_Supplement_Hypergraphs

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricscryptographyinformation-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

A simple kkk-uniform hypergraph on [N][N][N] is its indicator vector on the set ([N]k)\binom{[N]}k(k[N]​) of unordered kkk-element subsets. The published uniform-hypergraph object and its product Bernoulli law are reused. Edges are listed lexicographically by increasing endpoint lists. The incidence matrix has one row per present edge in that order. Its column count retains all NNN vertices, including isolated vertices.

For a fixed hypergraph HHH on [n][n][n], let G0G_0G0​ have independent Bernoulli-ppp edge indicators and independently choose a uniform injection π:[n]↪[N]\pi:[n]\hookrightarrow[N]π:[n]↪[N]. The planted experiment is

G=G0∪π(H).G=G_0\cup\pi(H).G=G0​∪π(H).

An edge already present is included once. Expectations are finite sums of singleton probabilities; uniform averages divide by the cardinality of the finite sample space. The empty injection family is assigned average zero only outside the domain N≥nN\ge nN≥n used in the results.

A marked edge is a pair (e,L)(e,L)(e,L) with ∣e∣=2ℓ|e|=2\ell∣e∣=2ℓ, L⊆eL\subseteq eL⊆e and ∣L∣=ℓ|L|=\ell∣L∣=ℓ. Marked background indicators are mutually independent, including different marks on the same support. The marked planting experiment transports both sets. Marked incidence rows ignore the mark when counting vertices, but retain one row for each marked edge. The XOR-MAJ bit is the parity on LLL added modulo two to the strict majority on e∖Le\setminus Le∖L.

For an edge family FFF, its spanned vertices are ⋃F\bigcup F⋃F. The expansion predicate for the non-asymptotic result is

∣⋃F∣≥γk∣F∣(F⊆E(H), ∣F∣≤D).\left|\bigcup F\right|\ge\gamma k|F|\quad(F\subseteq E(H),\ |F|\le D).​⋃F​≥γk∣F∣(F⊆E(H), ∣F∣≤D).

These objects supply the actual random experiments and expansion hypotheses in the supplement.

Definition code
import Mathlib
import Definitions.Def_RandomIsetThreshold_Degree_Hypergraph
import Definitions.Def_ExpandingCodes_PolynomialStretch_BinaryModel
set_option autoImplicit false
open scoped BigOperators Classical

namespace ExpandingCodes.PolynomialStretch.Supplement

noncomputable section
abbrev Edge := RandomIsetThreshold.Degree.Edge
abbrev Hypergraph := RandomIsetThreshold.Degree.Cube

/-- The finite expectation, avoiding any integrability convention. -/
def finiteMean {α : Type} [Fintype α] [MeasurableSpace α] (μ : MeasureTheory.Measure α) (f : α → ℝ) : ℝ :=
  ∑ x, μ.real {x} * f x

def uniformMean {α : Type} [Fintype α] (f : α → ℝ) : ℝ :=
  (∑ x, f x) / Fintype.card α

def finiteProb {α : Type} [Fintype α] [MeasurableSpace α] (μ : MeasureTheory.Measure α) (E : α → Prop) : ℝ :=
  finiteMean μ (fun x => if E x then 1 else 0)

abbrev nullLaw (N k : ℕ) (p : unitInterval) :=
  RandomIsetThreshold.Degree.graphLaw N k p

/-- Lexicographic order on increasing lists of endpoints. -/
def edgeOrder {N k : ℕ} (e f : Edge N k) : Bool :=
  decide (List.Lex (· < ·) (e.val.sort (· ≤ ·)) (f.val.sort (· ≤ ·)) ∨ e = f)

def allEdges (N k : ℕ) : List (Edge N k) :=
  (Finset.univ : Finset (Edge N k)).toList.mergeSort edgeOrder

def presentEdges {N k : ℕ} (G : Hypergraph N k) : List (Edge N k) :=
  (allEdges N k).filter G

def edgeCount {N k : ℕ} (G : Hypergraph N k) : ℕ := (presentEdges G).length

def incidence {N k : ℕ} (G : Hypergraph N k) : Generator (edgeCount G) N :=
  fun i v => if v ∈ ((presentEdges G).get i).val then 1 else 0

def edgeBits {N k : ℕ} (G : Hypergraph N k) : List Bool := (allEdges N k).map G

def edgeImage {n N k : ℕ} (π : Fin n ↪ Fin N) (e : Edge n k) : Edge N k :=
  ⟨e.val.map π, by simp [e.property]⟩

def plant {n N k : ℕ} (H : Hypergraph n k) (G : Hypergraph N k)
    (π : Fin n ↪ Fin N) : Hypergraph N k :=
  fun e => G e || decide (∃ f : Edge n k, H f = true ∧ edgeImage π f = e)

/-- Independent background and a uniform injection of ALL n vertices, including isolated ones.
The empty injection family has uniformMean=0 outside N≥n; no theorem uses that case. -/
def plantedMean {n N k : ℕ} (H : Hypergraph n k) (p : unitInterval)
    (f : Hypergraph N k → ℝ) : ℝ :=
  finiteMean (nullLaw N k p) fun G =>
    uniformMean fun π : Fin n ↪ Fin N => f (plant H G π)

def edgesFinset {N k : ℕ} (G : Hypergraph N k) : Finset (Edge N k) :=
  Finset.univ.filter fun e => G e = true

def spannedVertices {N k : ℕ} (F : Finset (Edge N k)) : Finset (Fin N) :=
  F.biUnion fun e => e.val

/-- Exact finite expansion condition used in Theorem 5.1. -/
def PatternExpansion {n k : ℕ} (H : Hypergraph n k) (D : ℕ) (γ : ℝ) : Prop :=
  ∀ F ⊆ edgesFinset H, F.card ≤ D →
    γ * k * F.card ≤ ((spannedVertices F).card : ℝ)

/-- Marked edges form their own independent-coordinate background, not a consequence of
unmarked planting. A mark is an unordered parity half. -/
abbrev MarkedEdge (N ℓ : ℕ) :=
  {z : Edge N (2 * ℓ) × Finset (Fin N) // z.2 ⊆ z.1.val ∧ z.2.card = ℓ}
abbrev MarkedGraph (N ℓ : ℕ) := MarkedEdge N ℓ → Bool

def markedOrder {N ℓ : ℕ} (e f : MarkedEdge N ℓ) : Bool :=
  edgeOrder e.val.1 f.val.1 && decide (e.val.1 ≠ f.val.1) ||
    decide (e.val.1 = f.val.1 ∧
      (List.Lex (· < ·) (e.val.2.sort (· ≤ ·)) (f.val.2.sort (· ≤ ·)) ∨ e = f))

def allMarkedEdges (N ℓ : ℕ) : List (MarkedEdge N ℓ) :=
  (Finset.univ : Finset (MarkedEdge N ℓ)).toList.mergeSort markedOrder

def markedList {N ℓ : ℕ} (G : MarkedGraph N ℓ) : List (MarkedEdge N ℓ) :=
  (allMarkedEdges N ℓ).filter G

def markedBits {N ℓ : ℕ} (G : MarkedGraph N ℓ) : List Bool := (allMarkedEdges N ℓ).map G

def markedIncidence {N ℓ : ℕ} (G : MarkedGraph N ℓ) :
    Generator (markedList G).length N :=
  fun i v => if v ∈ ((markedList G).get i).val.1.val then 1 else 0

def markedNullLaw (N ℓ : ℕ) (p : unitInterval) : MeasureTheory.Measure (MarkedGraph N ℓ) :=
  MeasureTheory.Measure.pi fun _ => ProbabilityTheory.bernoulliMeasure true false p

def markedImage {n N ℓ : ℕ} (π : Fin n ↪ Fin N) (e : MarkedEdge n ℓ) : MarkedEdge N ℓ :=
  ⟨(edgeImage π e.val.1, e.val.2.map π), by
    constructor
    · exact Finset.map_subset_map.mpr e.property.1
    · simpa using e.property.2⟩

def markedPlant {n N ℓ : ℕ} (H : MarkedGraph n ℓ) (G : MarkedGraph N ℓ)
    (π : Fin n ↪ Fin N) : MarkedGraph N ℓ :=
  fun e => G e || decide (∃ f : MarkedEdge n ℓ, H f = true ∧ markedImage π f = e)

def markedPlantedMean {n N ℓ : ℕ} (H : MarkedGraph n ℓ) (p : unitInterval)
    (f : MarkedGraph N ℓ → ℝ) : ℝ :=
  finiteMean (markedNullLaw N ℓ p) fun G =>
    uniformMean fun π : Fin n ↪ Fin N => f (markedPlant H G π)

/-- XOR of the parity half with strict majority of the other half (ℓ is odd in §3.4). -/
def xorMaj {N ℓ : ℕ} (e : MarkedEdge N ℓ) (x : Fin N → Bool) : Bool :=
  xor (decide ((∑ v ∈ e.val.2, if x v then 1 else 0 : ℕ) % 2 = 1))
    (decide (ℓ < 2 * ((e.val.1.val \ e.val.2).filter fun v => x v).card))

end
end ExpandingCodes.PolynomialStretch.Supplement
Source
Isaac M Hair, Amit Sahai, Expanding Codes with Polynomial Stretch, STOC 2027 submission #824 (October 2026), printed pp. 15–16 / PDF pp. 16–17, §3.1; printed pp. 19–20 / PDF pp. 20–21, §3.4; printed p. 24 / PDF p. 25, §5

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me