Lemma A.3 (existence part) — field setups exist
ProvedLatticePrepro.FieldSetup.exists_fieldSetupLet be a prime and let be integers with and . Then there exists a field setup with parameters : a finite field with , a field that is an algebra over and over (compatibly), and an element such that
and are linearly independent over . In other words, is an extension of of degree with power basis .
This provides the fields of step 1 of Construction A.4. In Theorem A.8 it is applied with the least power of that is at least , and the least power of that is at least .
Formalization Note: The conclusion is Nonempty (FieldSetup p d δ). Only existence is formalized: the paper's Lemma A.3 also constructs an irreducible with and builds as an Artin–Schreier tower (for a power of ) in polynomial time, which is not part of this statement. Here may be any positive integer.
import Mathlib
import Definitions.Def_LatticePrepro_Tables_FieldSetup
open LatticePrepro
open LatticePrepro.FieldSetup
variable {p : ℕ} [Fact p.Prime] {d δ : ℕ}theorem LatticePrepro.FieldSetup.exists_fieldSetup (p : ℕ) [Fact p.Prime] (d δ : ℕ) (hd : 1 ≤ d) (hδ : 1 ≤ δ) :
Nonempty (FieldSetup p d δ) := by sorry