Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Field setups: a sample field S\mathbb{S}S and an extension K=S(γ)K=\mathbb{S}(\gamma)K=S(γ) of degree δ\deltaδ (Lemma A.3, Construction A.4)

Definition
LatticePrepro_Tables_FieldSetup

by WizardOfMenlo · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

coding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing

For a prime ppp and natural numbers d,δd,\deltad,δ, a field setup (FieldSetup p d δ) consists of

  1. a finite field S\mathbb{S}S, the sample field, which is an Fp\mathbb{F}_pFp​-algebra and has exactly pdp^dpd elements;
  2. a field KKK, the moment field, which is an algebra over Fp\mathbb{F}_pFp​ and over S\mathbb{S}S, compatibly (the scalar actions form a tower Fp→S→K\mathbb{F}_p\to\mathbb{S}\to KFp​→S→K);
  3. an element γ∈K\gamma\in Kγ∈K such that
    • every x∈Kx\in Kx∈K equals f(γ)f(\gamma)f(γ) for some f∈S[X]f\in\mathbb{S}[X]f∈S[X] with deg⁡f<δ\deg f<\deltadegf<δ, and
    • 1,γ,…,γδ−11,\gamma,\dots,\gamma^{\delta-1}1,γ,…,γδ−1 are linearly independent over S\mathbb{S}S.

Thus K=S(γ)K=\mathbb{S}(\gamma)K=S(γ) is an extension of S\mathbb{S}S of degree δ\deltaδ, with power basis 1,γ,…,γδ−11,\gamma,\dots,\gamma^{\delta-1}1,γ,…,γδ−1.

These are the fields of step 1 of Construction A.4, whose existence (and, in the paper, explicit construction) is Lemma A.3. All the explicit evaluation tables of Appendix A are defined relative to a field setup: coordinates are indexed by S\mathbb{S}S, and moments are evaluations at γ\gammaγ.

Formalization Note: The structure bundles the two types with their algebraic instances (Field, Fintype, DecidableEq, Algebra, IsScalarTower). Finiteness of KKK is not a separate field; it follows from the first property of γ\gammaγ. Unlike the paper, S\mathbb{S}S is not presented as Fp[X]/(f)\mathbb{F}_p[X]/(f)Fp​[X]/(f) with a fixed basis, and δ\deltaδ is not required to be a power of ppp. The degree condition is stated with natDegree. The paper writes K,e,c,ζ,E\mathbb{K},e,c,\zeta,\mathbb{E}K,e,c,ζ,E for S,d,δ,γ,K\mathbb{S},d,\delta,\gamma,KS,d,δ,γ,K.

Definition code
import Mathlib

/-!
# Field setups for the explicit construction (Lemma A.3, existence part)

The explicit evaluation tables use a *sample field* `𝕊` of size `q = p^d` and an extension
`K = 𝕊(γ)` of degree `δ`, so that every element of `K` is a polynomial of degree `< δ` in `γ`
with coefficients in `𝕊`, and `1, γ, …, γ^{δ-1}` are `𝕊`-linearly independent.

We only need the *existence* of such fields (the paper's Lemma A.3 additionally constructs
them in polynomial time, which we do not formalize).
-/

namespace LatticePrepro

/-- A sample field `𝕊` of size `p^d` and an extension `K = 𝕊(γ)` of degree `δ`. -/
structure FieldSetup (p : ℕ) [Fact p.Prime] (d δ : ℕ) where
  /-- The sample field. -/
  𝕊 : Type
  [field𝕊 : Field 𝕊]
  [fintype𝕊 : Fintype 𝕊]
  [decEq𝕊 : DecidableEq 𝕊]
  [alg𝕊 : Algebra (ZMod p) 𝕊]
  card_𝕊 : Fintype.card 𝕊 = p ^ d
  /-- The moment field. -/
  K : Type
  [fieldK : Field K]
  [algK : Algebra (ZMod p) K]
  [alg𝕊K : Algebra 𝕊 K]
  [tower : IsScalarTower (ZMod p) 𝕊 K]
  /-- The generator `γ`. -/
  γ : K
  /-- Every element of `K` is a polynomial of degree `< δ` in `γ`. -/
  exists_aeval : ∀ x : K, ∃ f : Polynomial 𝕊, f.natDegree < δ ∧ Polynomial.aeval γ f = x
  /-- The powers `1, γ, …, γ^{δ-1}` are `𝕊`-linearly independent. -/
  linearIndependent_pow : LinearIndependent 𝕊 (fun i : Fin δ => γ ^ (i : ℕ))

namespace FieldSetup

variable {p : ℕ} [Fact p.Prime] {d δ : ℕ}

attribute [instance] field𝕊 fintype𝕊 decEq𝕊 alg𝕊 fieldK algK alg𝕊K tower

variable (FS : FieldSetup p d δ)

end FieldSetup

end LatticePrepro
Source
G. Fenzi, G. Weissenberg, Nearly Optimal Hardness for CVP and NCP with Preprocessing (STOC 2027 submission #847; IACR ePrint 2026/2634, https://eprint.iacr.org/2026/2634), Lemma A.3 (\label{lem:explicit-fields}) and Construction A.4, step 1 (\label{step:moment-fields}); Lean: LatticePrepro/Tables/FieldSetup.lean, LatticePrepro.FieldSetup

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