Exact parameter regimes and conditional hardness predicates
DefinitionExpandingCodes_PolynomialStretch_Supplement_ConjecturesThe conjectures are propositions used as hypotheses, never axioms. For rational , the ambient size and implementable density are
The general probability-clamping helper only totalizes inputs outside ; 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, are rational, , , , , and is the published row-count function. The constraints are
The real exponent need not be rational. Unmarked planting asserts an eventual advantage bound for every size- circuit, uniformly over every expanding with exactly edges; the threshold precedes and the circuit. Random noisy XOR compares and , with uniform and independent Bernoulli- errors. All graph outcomes, including exceptional nonexpanders, are averaged.
For the marked regime, are rational and . Put , , and let be the least integer at least with . Set , , , and . The constraints are
Marked planting is a separate predicate with marked background and inputs, and expansion on underlying vertices. Random Goldreich compares to . Its maximal size- circuit advantage tends to zero: for each positive tolerance, one eventual threshold works for all allowed circuits. This is the full condition.
These definitions fix the domains, quantifier order and laws of the assumptions in Theorems 3.4 and 3.6. The arithmetic formula for rounds up to the required congruence class; natural subtraction occurs only in a sequence interpreted eventually as grows.
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