Fixed points of Frobenius lie in the prime field
ProvedLatticePrepro.exists_zmod_of_pow_eqcoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
Let be a prime and let be a field that is an algebra over the prime field , with structure map (so has characteristic ). If an element is fixed by the Frobenius map, then it comes from the prime field:
In the moment reconstruction theorem (Theorem A.7), the coefficients of the reconstructed coefficient function are shown to be fixed by Frobenius; this lemma then places them in , so that the reconstructed function takes values in the prime field, as coefficient functions must (Definition 4.1).
Formalization Note: is ZMod p with Fact p.Prime, and is algebraMap (ZMod p) Ω. The field is arbitrary; it need not be finite (in the application it is an algebraic closure).
Preamble
import Mathlib
open Polynomial
variable {Ω : Type*} [Field Ω]Formal statement
theorem LatticePrepro.exists_zmod_of_pow_eq {p : ℕ} [hp : Fact p.Prime] [Algebra (ZMod p) Ω] {c : Ω}
(hc : c ^ p = c) : ∃ a : ZMod p, algebraMap (ZMod p) Ω a = c := by sorrySource
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), auxiliary lemma used in the proof of Theorem A.7 (\label{thm:moment-hankel-reconstruction}); Lean: LatticePrepro/Basic/FiniteField.lean, LatticePrepro.exists_zmod_of_pow_eq