Modular predicates MOD, MOD12, signed weight profile, Fourier coefficients, binomial transform and
DefinitionGoldreichAffine_Exponential_Supplement_ModularFor integers and a residue set , the modular predicate on inputs is
where is the Hamming weight. with .
The signed weight profile is if and otherwise, for . Its Fourier coefficients are
For a binary sequence over , its binomial transform is
For the paper uses , which is exactly when (the predicate's value at weight ); the resulting is the common coefficient of all degree- monomials in the algebraic normal form of a residual whose fixed inputs have weight .
Finally, for ,
These objects state Lemma 5, Theorems 3 and 6, and Lemmas 7–8.
Formalization Note The output bit is false and is true; the paper's polarity ( on ) is kept. Residue sets are finite sets of naturals; the standing condition is a hypothesis of each theorem. is ZMod 2, and is a real power.
import Definitions.Def_GoldreichAffine_Exponential_BooleanCore
open scoped BigOperators
open MatousekLP.Codes (Word weight)
set_option autoImplicit false
namespace GoldreichAffine.Exponential.Supplement
/-- MOD^{t,S0}_d (printed p.3 / PDF p.4): value 0 (false) iff ‖x‖ mod t ∈ S0, else 1 (true). -/
def modPredicate (t : ℕ) (S0 : Finset ℕ) (d : ℕ) : Predicate d :=
fun x => !decide (weight x % t ∈ S0)
/-- The residue set S0 = {0,1,3,4,6,9} of MOD12 (printed p.10 / PDF p.11). -/
def mod12Residues : Finset ℕ := {0, 1, 3, 4, 6, 9}
/-- MOD12_b = MOD^{12,S0}_b with S0 = {0,1,3,4,6,9}. -/
def mod12 (b : ℕ) : Predicate b := modPredicate 12 mod12Residues b
/-- Signed weight profile g_{t,S0}(w) = 1 if w mod t ∈ S0, -1 otherwise (printed p.25 / PDF p.26). -/
def signedProfile (t : ℕ) (S0 : Finset ℕ) (w : ℕ) : ℤ :=
if w % t ∈ S0 then 1 else -1
/-- Fourier coefficient ĝ_ν = (1/t) Σ_{w=0}^{t-1} g(w) ω^{-νw}, ω = exp(2πi/t). -/
noncomputable def fourierCoeff (t : ℕ) (S0 : Finset ℕ) (ν : ℕ) : ℂ :=
(1 / (t : ℂ)) * ∑ w ∈ Finset.range t,
(signedProfile t S0 w : ℂ) * Complex.exp (-(2 * Real.pi * Complex.I * (ν : ℂ) * (w : ℂ) / (t : ℂ)))
/-- Binomial transform of a binary sequence a over F₂:
λ^a_j(w) = Σ_{h=0}^{j} C(j,h) a(w+h) (printed p.30 / PDF p.31). -/
def binomialTransform (a : ℕ → ZMod 2) (j w : ℕ) : ZMod 2 :=
∑ h ∈ Finset.range (j + 1), (j.choose h : ZMod 2) * a (w + h)
/-- The binary sequence (1 - g_{t,S0}(h))/2: 1 iff h mod t ∉ S0, i.e. the MOD value at weight h.
So binomialTransform (modSequence t S0) j w is the paper's λ_j(w). -/
def modSequence (t : ℕ) (S0 : Finset ℕ) (h : ℕ) : ZMod 2 :=
if h % t ∈ S0 then 0 else 1
/-- The sequence of MOD12: its binomial transform gives λ_j(w) for MOD12_b. -/
def mod12Sequence : ℕ → ZMod 2 := modSequence 12 mod12Residues
/-- B12(b') of Theorem 6 (printed pp.10–11 / PDF pp.11–12), exactly as printed;
2^{-b'/2} is a real power. -/
noncomputable def B12 (b' : ℕ) : ℝ :=
Real.sqrt 2 / 6 * (Real.cos (Real.pi / 12) ^ b' + Real.sin (Real.pi / 12) ^ b'
+ (2 : ℝ) ^ (-(b' : ℝ) / 2))
+ 1 / Real.sqrt 3 * (Real.sqrt 3 / 2) ^ b'
end GoldreichAffine.Exponential.Supplement