Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Exact parameter regimes and conditional hardness predicates

Definition
ExpandingCodes_PolynomialStretch_Supplement_Conjectures

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

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

The conjectures are propositions used as hypotheses, never axioms. For rational C,βC,\betaC,β, the ambient size and implementable density are

N=⌈nC⌉,p=2−⌈βlog⁡2N⌉.N=\lceil n^C\rceil,\qquad p=2^{-\lceil\beta\log_2N\rceil}.N=⌈nC⌉,p=2−⌈βlog2​N⌉.

The general probability-clamping helper only totalizes inputs outside [0,1][0,1][0,1]; it leaves these dyadic probabilities unchanged. Hypergraphs are encoded by their full lexicographic indicator vectors. In a labelled experiment the indicator vector is followed by one label slot per potential edge, with absent-edge slots zero. The fixed parameters and input lengths are public nonuniform metadata. These are explicit finite enumeration, sorting, filtering and padding operations; no encoding advice is chosen.

For the noisy-XOR regime, ε,C,β\varepsilon,C,\betaε,C,β are rational, 0<ε<1/20<\varepsilon<1/20<ε<1/2, d=2⌈512ε−2⌉d=2\lceil512\varepsilon^{-2}\rceild=2⌈512ε−2⌉, k=⌈4d2ε−2⌉k=\lceil4d^2\varepsilon^{-2}\rceilk=⌈4d2ε−2⌉, a=2d2a=2d^2a=2d2, and m(n)m(n)m(n) is the published row-count function. The constraints are

C>max⁡{1,2a/((1/2−ε)k)},k/2<β<(1−ε)k−2a/C,C>\max\{1,2a/((1/2-\varepsilon)k)\},\quad k/2<\beta<(1-\varepsilon)k-2a/C,C>max{1,2a/((1/2−ε)k)},k/2<β<(1−ε)k−2a/C, 0<δ<min⁡{1−ε,C(2β−k)/(k−2)}.0<\delta<\min\{1-\varepsilon,C(2\beta-k)/(k-2)\}.0<δ<min{1−ε,C(2β−k)/(k−2)}.

The real exponent δ\deltaδ need not be rational. Unmarked planting asserts an eventual advantage bound 1/41/41/4 for every size-exp⁡(nδ)\exp(n^\delta)exp(nδ) circuit, uniformly over every expanding HHH with exactly m(n)m(n)m(n) edges; the threshold precedes HHH and the circuit. Random noisy XOR compares (G,AGx+e)(G,A_Gx+e)(G,AG​x+e) and (G,U∣G∣)(G,U_{|G|})(G,U∣G∣​), with uniform xxx and independent Bernoulli-(1/2−ε)(1/2-\varepsilon)(1/2−ε) errors. All graph outcomes, including exceptional nonexpanders, are averaged.

For the marked regime, ε,C,s\varepsilon,C,sε,C,s are rational and 0<ε<1/1000<\varepsilon<1/1000<ε<1/100. Put κ=arity⁡(ε/4)\kappa=\operatorname{arity}(\varepsilon/4)κ=arity(ε/4), d′=dimension⁡(ε/4)d'=\operatorname{dimension}(\varepsilon/4)d′=dimension(ε/4), and let ttt be the least integer at least 2κ2\sqrt\kappa2κ​ with κ+t≡2(mod4)\kappa+t\equiv2\pmod4κ+t≡2(mod4). Set ℓ=(κ+t)/2\ell=(\kappa+t)/2ℓ=(κ+t)/2, a=2(d′)2a=2(d')^2a=2(d′)2, m(n)=rowCount⁡(d′,n−t)m(n)=\operatorname{rowCount}(d',n-t)m(n)=rowCount(d′,n−t), and β=2ℓ−s\beta=2\ell-sβ=2ℓ−s. The constraints are

C>max⁡{2,2a/(ℓ(1/36−2ε))},2εℓ+2a/C<s<ℓ/36,C>\max\{2,2a/(\ell(1/36-2\varepsilon))\},\quad 2\varepsilon\ell+2a/C<s<\ell/36,C>max{2,2a/(ℓ(1/36−2ε))},2εℓ+2a/C<s<ℓ/36, 0<δ<min⁡{1−ε,C/10}.0<\delta<\min\{1-\varepsilon,C/10\}.0<δ<min{1−ε,C/10}.

Marked planting is a separate predicate with marked background and inputs, and expansion on underlying vertices. Random Goldreich compares (G,fG(UN))(G,f_G(U_N))(G,fG​(UN​)) to (G,U∣G∣)(G,U_{|G|})(G,U∣G∣​). Its maximal size-exp⁡(nδ)\exp(n^\delta)exp(nδ) circuit advantage tends to zero: for each positive tolerance, one eventual threshold works for all allowed circuits. This is the full o(1)o(1)o(1) condition.

These definitions fix the domains, quantifier order and laws of the assumptions in Theorems 3.4 and 3.6. The arithmetic formula for ttt rounds up to the required congruence class; natural subtraction n−tn-tn−t occurs only in a sequence interpreted eventually as nnn grows.

Definition code
import Mathlib
import Definitions.Def_ExpandingCodes_PolynomialStretch_Supplement_Encryption
import Definitions.Def_ExpandingCodes_PolynomialStretch_Parameters
set_option autoImplicit false
open scoped BigOperators Classical

namespace ExpandingCodes.PolynomialStretch.Supplement

noncomputable section
/-- Clamping only totalizes invalid probabilities; dyadic densities already lie in [0,1]. -/
def probability (x : ℝ) : unitInterval :=
  ⟨max 0 (min 1 x), by
    constructor
    · exact le_max_left _ _
    · exact max_le (by norm_num) (min_le_left _ _)⟩

def ambientSize (C : ℚ) (n : ℕ) : ℕ := ⌈(n : ℝ) ^ (C : ℝ)⌉₊

def dyadicDensity (β : ℚ) (N : ℕ) : unitInterval :=
  probability ((2 : ℝ) ^ (⌈(β : ℝ) * Real.logb 2 N⌉₊ : ℕ))⁻¹

/-- (1), (6), (7), with k and m computed from the source's construction. -/
def NoisyParameters (ε C β : ℚ) (δ : ℝ) : Prop :=
  let e : ℝ := ε
  let k : ℝ := arity e
  let a : ℝ := 2 * (dimension e : ℝ) ^ 2
  0 < e ∧ e < 1 / 2 ∧
  max 1 (2 * a / ((1 / 2 - e) * k)) < (C : ℝ) ∧
  k / 2 < (β : ℝ) ∧ (β : ℝ) < (1 - e) * k - 2 * a / (C : ℝ) ∧
  0 < δ ∧ δ < min (1 - e) ((C : ℝ) * (2 * (β : ℝ) - k) / (k - 2))

/-- The smallest t≥2√κ with κ+t=2 mod 4, computed without an existence assumption. -/
def sharedInputs (ε : ℝ) : ℕ :=
  let κ := arity (ε / 4)
  let b := ⌈2 * Real.sqrt κ⌉₊
  b + (6 - (κ + b) % 4) % 4

def majorityArity (ε : ℝ) : ℕ := (arity (ε / 4) + sharedInputs ε) / 2

def goldreichRows (ε : ℝ) (n : ℕ) : ℕ :=
  rowCount (dimension (ε / 4)) (n - sharedInputs ε)

/-- Exactly (8), including the narrower ε-domain and rational C,s. -/
def GoldreichParameters (ε C s : ℚ) (δ : ℝ) : Prop :=
  let e : ℝ := ε
  let ℓ : ℝ := majorityArity e
  let a : ℝ := 2 * (dimension (e / 4) : ℝ) ^ 2
  0 < e ∧ e < 1 / 100 ∧
  max 2 (2 * a / (ℓ * (1 / 36 - 2 * e))) < (C : ℝ) ∧
  2 * e * ℓ + 2 * a / (C : ℝ) < (s : ℝ) ∧ (s : ℝ) < ℓ / 36 ∧
  0 < δ ∧ δ < min (1 - e) ((C : ℝ) / 10)

def plantingLength (n N k : ℕ) : ℕ := (allEdges n k).length + (allEdges N k).length

/-- Conjecture 3.1, UNMARKED: the threshold precedes H and the nonuniform circuit. -/
def UnmarkedPlanting (ε : ℝ) (k : ℕ) (m : ℕ → ℕ) (C β : ℚ) (δ : ℝ) : Prop :=
  ∃ n₀ ≥ 2, ∀ n ≥ n₀, ∀ H : Hypergraph n k,
    edgeCount H = m n → Expanding (incidence H) (1 - ε) k ((n : ℝ) ^ (1 - ε)) →
    ∀ T : BitCircuit (plantingLength n (ambientSize C n) k), oneOutput T →
      (T.size : ℝ) ≤ Real.exp ((n : ℝ) ^ δ) →
      let N := ambientSize C n
      let p := dyadicDensity β N
      |plantedMean (N := N) H p (fun G => if accepts T (edgeBits H ++ edgeBits G) then 1 else 0) -
        finiteMean (nullLaw N k p)
          (fun G => if accepts T (edgeBits H ++ edgeBits G) then 1 else 0)| ≤ 1 / 4

def markedPlantingLength (n N ℓ : ℕ) : ℕ :=
  (allMarkedEdges n ℓ).length + (allMarkedEdges N ℓ).length

/-- Conjecture 3.1, MARKED: marks are retained; expansion counts underlying vertices only. -/
def MarkedPlanting (ε : ℝ) (ℓ : ℕ) (m : ℕ → ℕ) (C β : ℚ) (δ : ℝ) : Prop :=
  ∃ n₀ ≥ 2, ∀ n ≥ n₀, ∀ H : MarkedGraph n ℓ,
    (markedList H).length = m n →
    Expanding (markedIncidence H) (1 - ε) (2 * ℓ) ((n : ℝ) ^ (1 - ε)) →
    ∀ T : BitCircuit (markedPlantingLength n (ambientSize C n) ℓ), oneOutput T →
      (T.size : ℝ) ≤ Real.exp ((n : ℝ) ^ δ) →
      let N := ambientSize C n
      let p := dyadicDensity β N
      |markedPlantedMean (N := N) H p (fun G => if accepts T (markedBits H ++ markedBits G) then 1 else 0) -
        finiteMean (markedNullLaw N ℓ p)
          (fun G => if accepts T (markedBits H ++ markedBits G) then 1 else 0)| ≤ 1 / 4

/-- Full potential-edge slots; absent labels are zero. No hidden ordering or advice. -/
def labelBits {N k : ℕ} (G : Hypergraph N k) (y : Edge N k → Bool) : List Bool :=
  (allEdges N k).map fun e => G e && y e

def parity {N k : ℕ} (e : Edge N k) (x : Fin N → Bool) : Bool :=
  decide ((∑ v ∈ e.val, if x v then 1 else 0 : ℕ) % 2 = 1)

/-- Independent Bernoulli bits on all potential slots; only present slots are read. -/
def bernoulliMean {ι : Type} [Fintype ι] (p : ℝ) (f : (ι → Bool) → ℝ) : ℝ :=
  ∑ y : ι → Bool, (∏ i, if y i then p else 1 - p) * f y

def xorAdvantage (ε : ℝ) (N k : ℕ) (p : unitInterval)
    (T : BitCircuit (2 * (allEdges N k).length)) : ℝ :=
  |finiteMean (nullLaw N k p) (fun G =>
      uniformMean fun x : Fin N → Bool => bernoulliMean (1 / 2 - ε)
        (fun e : Edge N k → Bool =>
          if accepts T (edgeBits G ++ labelBits G (fun a => xor (parity a x) (e a))) then 1 else 0)) -
    finiteMean (nullLaw N k p) (fun G =>
      uniformMean fun y : Edge N k → Bool =>
        if accepts T (edgeBits G ++ labelBits G y) then 1 else 0)|

/-- Conjecture 3.2, averaged over the FULL random graph, without conditioning on expansion. -/
def RandomXOR (ε : ℝ) (k : ℕ) (C β : ℚ) (δ : ℝ) : Prop :=
  ∃ n₀ ≥ 2, ∀ n ≥ n₀,
    ∀ T : BitCircuit (2 * (allEdges (ambientSize C n) k).length), oneOutput T →
      (T.size : ℝ) ≤ Real.exp ((n : ℝ) ^ δ) →
      xorAdvantage ε (ambientSize C n) k (dyadicDensity β (ambientSize C n)) T ≤ 1 / 4

def markedLabelBits {N ℓ : ℕ} (G : MarkedGraph N ℓ) (y : MarkedEdge N ℓ → Bool) : List Bool :=
  (allMarkedEdges N ℓ).map fun e => G e && y e

def goldreichAdvantage (N ℓ : ℕ) (p : unitInterval)
    (T : BitCircuit (2 * (allMarkedEdges N ℓ).length)) : ℝ :=
  |finiteMean (markedNullLaw N ℓ p) (fun G =>
      uniformMean fun x : Fin N → Bool =>
        if accepts T (markedBits G ++ markedLabelBits G (fun e => xorMaj e x)) then 1 else 0) -
    finiteMean (markedNullLaw N ℓ p) (fun G =>
      uniformMean fun y : MarkedEdge N ℓ → Bool =>
        if accepts T (markedBits G ++ markedLabelBits G y) then 1 else 0)|

/-- Conjecture 3.5: uniform o(1) over ALL allowed circuits, not merely a 1/4 bound.
The η-threshold formulation is exactly convergence of the maximal advantage to zero. -/
def RandomGoldreich (ℓ : ℕ) (C β : ℚ) (δ : ℝ) : Prop :=
  ∀ η : ℝ, 0 < η → ∃ n₀ ≥ 2, ∀ n ≥ n₀,
    ∀ T : BitCircuit (2 * (allMarkedEdges (ambientSize C n) ℓ).length), oneOutput T →
      (T.size : ℝ) ≤ Real.exp ((n : ℝ) ^ δ) →
      goldreichAdvantage (ambientSize C n) ℓ (dyadicDensity β (ambientSize C n)) T ≤ η

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, (6)–(7), Conjectures 3.1–3.2; printed pp. 13–14 / PDF pp. 14–15, §2.4; printed pp. 19–20 / PDF pp. 20–21, (8), Conjecture 3.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