Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Algebra / FieldBasis

Definition
QPBT_QPBT_Algebra_FieldBasis

by Dengnifer · Oct 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

qpbt

This bundle defines the admissible finite-field model and the basis data used by the QPBT formalization. It records dual and self-dual normal bases, normality, the squaring automorphism, the selected fixed model, and the binary representation of field elements.

Principal definitions:

  • MIPStarRE.QPBT.IsAdmissibleSize: the predicate that the field size has the required power-of-two form.
  • MIPStarRE.QPBT.IsDualBasisPair: the dual-basis relation.
  • MIPStarRE.QPBT.Basis.IsSelfDual: self-duality of a basis.
  • MIPStarRE.QPBT.Basis.IsNormal: normality of a basis.
  • MIPStarRE.QPBT.squareMulEquiv: the squaring automorphism on the finite group.
  • MIPStarRE.QPBT.FixedFieldModel: the carrier and coding data for a fixed field model.
  • MIPStarRE.QPBT.fixedFieldModel: the selected global field model for an admissible size.
  • MIPStarRE.QPBT.binaryRepresentation: the binary coordinate representation from the chosen basis.

Formalization Credit. This Lean declaration is part of the Quantum Pauli basis test formalization by Ruixuan Deng. The source code was generated by AI agents; Ruixuan Deng is the responsible maintainer.

Mathematical Source. The mathematical source is Ji, Natarajan, Vidick, Wright, and Yuen, MIP*=RE, arXiv:2001.04383v3.

Definition code
-- Generated from QPBT/Algebra/FieldBasis.lean by skeleton subtraction.
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_AxisParallelLine
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_DiagonalLine
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_LinePolynomials
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_LowDegreePolynomial
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_OpFamily
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_ParametersBase
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_ParametersFiniteAnswers
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_QuantumState
import Definitions.Def_LIDT_MIPStarRE_LDT_CommutativityPoints_Defs
import Definitions.Def_LIDT_MIPStarRE_LDT_ExpansionHypercubeGraph_Defs_Core
import Definitions.Def_LIDT_MIPStarRE_LDT_GlobalVariance_Defs_Core
import Definitions.Def_LIDT_MIPStarRE_LDT_MakingMeasurementsProjective_Defs
import Definitions.Def_LIDT_MIPStarRE_LDT_Pasting_Defs_Families
import Definitions.Def_LIDT_MIPStarRE_LDT_Pasting_Defs_Interpolation
import Definitions.Def_LIDT_MIPStarRE_LDT_Tactic_AvgCongr
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_StrategyCore

namespace MIPStarRE.QPBT
end MIPStarRE.QPBT
namespace MIPStarRE.QPBT.Basis
end MIPStarRE.QPBT.Basis

/-!
# Finite-field bases and the fixed binary representation

The Pauli basis test uses fields of size `2^k` for odd `k`, together with a
chosen self-dual normal basis over `ZMod 2`.  This file constructs such bases
and records the resulting fixed field model for later proofs.

## References

The declarations correspond to blueprint `def:admissible-size`,
`def:dual-self-dual-normal-basis`, `def:subfields-kappa`, `def:subfield-trace`,
and `def:binary-representation`.
Their paper origin is `references/qpbt-paper/04_preliminaries.tex:433-502,653-728`.
-/

@[expose] public section

open scoped BigOperators

namespace MIPStarRE.QPBT

/-- `IsAdmissibleSize q` is the predicate `q = 2^k` for an odd exponent.
This is blueprint `def:admissible-size`, with paper origin
`references/qpbt-paper/04_preliminaries.tex:662-667`.
-/
def IsAdmissibleSize (q : ℕ) : Prop := ∃ k : ℕ, Odd k ∧ q = 2 ^ k





/-- A dual pair of bases for blueprint
`def:dual-self-dual-normal-basis`, paper `04_preliminaries.tex:494-496`. -/
def IsDualBasisPair {F K ι : Type*} [CommRing F] [CommRing K] [DecidableEq ι]
    [Algebra F K] (b b' : Module.Basis ι F K) : Prop :=
  ∀ i j, Algebra.trace F K (b i * b' j) = if i = j then 1 else 0

namespace Basis

/-- Self-duality in blueprint
`def:dual-self-dual-normal-basis`, paper `04_preliminaries.tex:494-497`. -/
def IsSelfDual {F K ι : Type*} [CommRing F] [CommRing K] [DecidableEq ι]
    [Algebra F K] (b : Module.Basis ι F K) : Prop :=
  _root_.MIPStarRE.QPBT.IsDualBasisPair b b

/-- Normality in blueprint
`def:dual-self-dual-normal-basis`, paper `04_preliminaries.tex:498-502`. The
Frobenius exponent uses the cardinality of the base field. -/
def IsNormal {F K : Type*} [CommSemiring F] [Fintype F] [Field K] [Algebra F K]
    {k : ℕ} (b : Module.Basis (Fin k) F K) : Prop :=
  ∃ α : K, ∀ j, b j = α ^ (Fintype.card F ^ j.1)

end Basis

/- The characteristic-two self-dual normal-basis construction is carried out
in the group algebra of the finite Galois group.  The transition from a normal
basis to its trace dual is a symmetric unit; odd cardinality makes its square
root unique and symmetric. -/

section GroupAlgebra

variable {G : Type*} [CommGroup G]

/-- The squaring automorphism of a commutative group whose `Nat.card` is odd. -/
noncomputable def squareMulEquiv (hodd : Odd (Nat.card G)) : G ≃* G :=
  MulEquiv.ofBijective (powMonoidHom 2) hodd.coprime_two_right.pow_left_bijective

theorem monoid_algebra_sq_eq_dom_congr (hodd : Odd (Nat.card G))
    (x : MonoidAlgebra (ZMod 2) G) :
    x ^ 2 = MonoidAlgebra.domCongr (ZMod 2) (ZMod 2) (_root_.MIPStarRE.QPBT.squareMulEquiv hodd) x := by
  letI : CharP (MonoidAlgebra (ZMod 2) G) 2 :=
    charP_of_injective_algebraMap' (ZMod 2) 2
  induction x using MonoidAlgebra.induction_linear with
  | zero => simp
  | add x y hx hy =>
      rw [add_pow_char, hx, hy, map_add]
  | single g r =>
      simp [MonoidAlgebra.single_pow, _root_.MIPStarRE.QPBT.squareMulEquiv, ZMod.pow_card]
      rfl

theorem monoid_algebra_sq_bijective (hodd : Odd (Nat.card G)) :
    Function.Bijective (fun x : MonoidAlgebra (ZMod 2) G => x ^ 2) := by
  have heq : (fun x : MonoidAlgebra (ZMod 2) G => x ^ 2) =
      MonoidAlgebra.domCongr (ZMod 2) (ZMod 2) (_root_.MIPStarRE.QPBT.squareMulEquiv hodd) := by
    funext x
    exact _root_.MIPStarRE.QPBT.monoid_algebra_sq_eq_dom_congr hodd x
  rw [heq]
  exact (MonoidAlgebra.domCongr (ZMod 2) (ZMod 2) (_root_.MIPStarRE.QPBT.squareMulEquiv hodd)).bijective

end GroupAlgebra

section NormalTraceDual

variable {K : Type*} [Field K] [Fintype K] [Algebra (ZMod 2) K]

local notation "G" => Gal(K/(ZMod 2))

-- Named, not anonymous: both instances are in the comparator statement
-- closure, and an anonymous instance is given a generated name that encodes
-- the defining module, which the Mathlib-only challenge file cannot
-- reproduce.  See `docs/comparator.md`, "Environment alignment for QPBT".
noncomputable local instance instCommGroupGaloisZMod2 : CommGroup G :=
  IsCyclic.commGroup
noncomputable local instance instDecidableEqGaloisZMod2 : DecidableEq G :=
  Classical.decEq G

theorem normal_basis_trace_dual_apply (σ : G) :
    (IsGalois.normalBasis (ZMod 2) K).traceDual σ =
      σ ((IsGalois.normalBasis (ZMod 2) K).traceDual 1) := by
  classical
  let b := IsGalois.normalBasis (ZMod 2) K
  have hdual : (b.traceDual : G → K) = fun τ => τ (b.traceDual 1) := by
    rw [b.traceDual_eq_iff]
    intro τ υ
    simp only [Algebra.traceForm_apply]
    calc
      Algebra.trace (ZMod 2) K (τ (b.traceDual 1) * b υ) =
          Algebra.trace (ZMod 2) K
            (τ⁻¹ (τ (b.traceDual 1) * b υ)) := by
              symm
              exact Algebra.trace_eq_of_algEquiv τ⁻¹ _
      _ = Algebra.trace (ZMod 2) K (b.traceDual 1 * b (τ⁻¹ * υ)) := by
        congr 2
        rw [map_mul]
        have hτ : τ⁻¹ (τ (b.traceDual 1)) = b.traceDual 1 := by
          change τ.symm (τ (b.traceDual 1)) = b.traceDual 1
          exact τ.symm_apply_apply _
        have hυ : τ⁻¹ (b υ) = b (τ⁻¹ * υ) := by
          calc
            τ⁻¹ (b υ) = τ⁻¹ (υ (b 1)) := by
              rw [IsGalois.normalBasis_apply]
            _ = (τ⁻¹ * υ) (b 1) := rfl
            _ = b (τ⁻¹ * υ) := (IsGalois.normalBasis_apply _).symm
        rw [hτ, hυ]
      _ = if τ⁻¹ * υ = 1 then 1 else 0 := b.trace_traceDual_mul 1 (τ⁻¹ * υ)
      _ = if υ = τ then 1 else 0 := by simp only [inv_mul_eq_one, eq_comm]
  exact congr_fun hdual σ

theorem normal_basis_repr_symm_mul_single
    (a : MonoidAlgebra (ZMod 2) G) (σ : G) (r : ZMod 2) :
    ((MonoidAlgebra.coeffLinearEquiv (ZMod 2)).trans
        (IsGalois.normalBasis (ZMod 2) K).repr.symm)
        (a * MonoidAlgebra.single σ r) =
      r • σ (((MonoidAlgebra.coeffLinearEquiv (ZMod 2)).trans
        (IsGalois.normalBasis (ZMod 2) K).repr.symm) a) := by
  classical
  let b := IsGalois.normalBasis (ZMod 2) K
  let φ := (MonoidAlgebra.coeffLinearEquiv (ZMod 2)).trans b.repr.symm
  change φ (a * MonoidAlgebra.single σ r) = r • σ (φ a)
  induction a using MonoidAlgebra.induction_linear with
  | zero => simp
  | add x y hx hy => simp only [add_mul, map_add, hx, hy, smul_add]
  | single τ s =>
      simp only [MonoidAlgebra.single_mul_single, φ, LinearEquiv.trans_apply,
        MonoidAlgebra.coeffLinearEquiv_apply, MonoidAlgebra.coeff_single,
        b.repr_symm_single, map_smul, smul_smul]
      rw [mul_comm s r]
      apply congrArg (fun x : K => (r * s) • x)
      rw [mul_comm τ σ]
      calc
        b (σ * τ) = (σ * τ) (b 1) := IsGalois.normalBasis_apply _
        _ = σ (τ (b 1)) := rfl
        _ = σ (b τ) := congrArg σ (IsGalois.normalBasis_apply τ).symm

theorem normal_basis_transition (a : MonoidAlgebra (ZMod 2) G) :
    let b := IsGalois.normalBasis (ZMod 2) K
    let φ := (MonoidAlgebra.coeffLinearEquiv (ZMod 2)).trans b.repr.symm
    let ψ := (MonoidAlgebra.coeffLinearEquiv (ZMod 2)).trans b.traceDual.repr.symm
    let v := φ.symm (b.traceDual 1)
    φ (v * a) = ψ a := by
  classical
  dsimp only
  let b := IsGalois.normalBasis (ZMod 2) K
  let φ := (MonoidAlgebra.coeffLinearEquiv (ZMod 2)).trans b.repr.symm
  let ψ := (MonoidAlgebra.coeffLinearEquiv (ZMod 2)).trans b.traceDual.repr.symm
  let v := φ.symm (b.traceDual 1)
  change φ (v * a) = ψ a
  induction a using MonoidAlgebra.induction_linear with
  | zero => simp
  | add x y hx hy => simp only [mul_add, map_add, hx, hy]
  | single σ r =>
      rw [_root_.MIPStarRE.QPBT.normal_basis_repr_symm_mul_single]
      rw [show φ v = b.traceDual 1 from φ.apply_symm_apply _]
      simp only [ψ, LinearEquiv.trans_apply, MonoidAlgebra.coeffLinearEquiv_apply,
        MonoidAlgebra.coeff_single, b.traceDual.repr_symm_single]
      exact congrArg (fun x : K => r • x) (_root_.MIPStarRE.QPBT.normal_basis_trace_dual_apply σ).symm

theorem normal_basis_transition_is_unit :
    let b := IsGalois.normalBasis (ZMod 2) K
    let φ := (MonoidAlgebra.coeffLinearEquiv (ZMod 2)).trans b.repr.symm
    IsUnit (φ.symm (b.traceDual 1)) := by
  classical
  dsimp only
  let b := IsGalois.normalBasis (ZMod 2) K
  let φ := (MonoidAlgebra.coeffLinearEquiv (ZMod 2)).trans b.repr.symm
  let ψ := (MonoidAlgebra.coeffLinearEquiv (ZMod 2)).trans b.traceDual.repr.symm
  let v := φ.symm (b.traceDual 1)
  change IsUnit v
  rw [IsUnit.isUnit_iff_mulLeft_bijective]
  have heq : (fun a => v * a) = fun a => φ.symm (ψ a) := by
    funext a
    apply φ.injective
    rw [φ.apply_symm_apply]
    exact _root_.MIPStarRE.QPBT.normal_basis_transition a
  rw [heq]
  exact φ.symm.bijective.comp ψ.bijective

theorem normal_basis_repr_apply_eq_trace (x : K) (σ : G) :
    let b := IsGalois.normalBasis (ZMod 2) K
    (b.repr x) σ = Algebra.trace (ZMod 2) K (x * b.traceDual σ) := by
  classical
  dsimp only
  let b := IsGalois.normalBasis (ZMod 2) K
  simpa only [Algebra.traceForm_apply, b.traceDual_traceDual] using
    b.traceDual.traceDual_repr_apply x σ

theorem normal_basis_transition_inv :
    let b := IsGalois.normalBasis (ZMod 2) K
    let φ := (MonoidAlgebra.coeffLinearEquiv (ZMod 2)).trans b.repr.symm
    let v := φ.symm (b.traceDual 1)
    MonoidAlgebra.domCongr (ZMod 2) (ZMod 2) (MulEquiv.inv G) v = v := by
  classical
  dsimp only
  let b := IsGalois.normalBasis (ZMod 2) K
  let φ := (MonoidAlgebra.coeffLinearEquiv (ZMod 2)).trans b.repr.symm
  let v := φ.symm (b.traceDual 1)
  let invAlg := MonoidAlgebra.domCongr (ZMod 2) (ZMod 2) (MulEquiv.inv G)
  change invAlg v = v
  ext σ
  have hv (τ : G) : v.coeff τ =
      Algebra.trace (ZMod 2) K (b.traceDual 1 * b.traceDual τ) := by
    change (b.repr (b.traceDual 1)) τ = _
    exact _root_.MIPStarRE.QPBT.normal_basis_repr_apply_eq_trace (b.traceDual 1) τ
  rw [MonoidAlgebra.coeff_domCongr, hv, hv]
  change Algebra.trace (ZMod 2) K (b.traceDual 1 * b.traceDual σ⁻¹) =
    Algebra.trace (ZMod 2) K (b.traceDual 1 * b.traceDual σ)
  calc
    Algebra.trace (ZMod 2) K (b.traceDual 1 * b.traceDual σ⁻¹) =
        Algebra.trace (ZMod 2) K
          (σ (b.traceDual 1 * b.traceDual σ⁻¹)) := by
            symm
            exact Algebra.trace_eq_of_algEquiv σ _
    _ = Algebra.trace (ZMod 2) K (b.traceDual σ * b.traceDual 1) := by
      congr 2
      rw [map_mul, ← _root_.MIPStarRE.QPBT.normal_basis_trace_dual_apply σ,
        _root_.MIPStarRE.QPBT.normal_basis_trace_dual_apply σ⁻¹]
      have hσ : σ (σ⁻¹ (b.traceDual 1)) = b.traceDual 1 := by
        change σ (σ.symm (b.traceDual 1)) = b.traceDual 1
        exact σ.apply_symm_apply _
      rw [hσ]
    _ = Algebra.trace (ZMod 2) K (b.traceDual 1 * b.traceDual σ) := by
      rw [mul_comm]

theorem trace_group_algebra_pairing
    (a d : MonoidAlgebra (ZMod 2) G) :
    let b := IsGalois.normalBasis (ZMod 2) K
    let φ := (MonoidAlgebra.coeffLinearEquiv (ZMod 2)).trans b.repr.symm
    let ψ := (MonoidAlgebra.coeffLinearEquiv (ZMod 2)).trans b.traceDual.repr.symm
    let invAlg := MonoidAlgebra.domCongr (ZMod 2) (ZMod 2) (MulEquiv.inv G)
    Algebra.trace (ZMod 2) K (φ a * ψ d) = (invAlg a * d).coeff 1 := by
  classical
  dsimp only
  let b := IsGalois.normalBasis (ZMod 2) K
  let φ := (MonoidAlgebra.coeffLinearEquiv (ZMod 2)).trans b.repr.symm
  let ψ := (MonoidAlgebra.coeffLinearEquiv (ZMod 2)).trans b.traceDual.repr.symm
  let invAlg := MonoidAlgebra.domCongr (ZMod 2) (ZMod 2) (MulEquiv.inv G)
  change Algebra.trace (ZMod 2) K (φ a * ψ d) = (invAlg a * d).coeff 1
  induction a using MonoidAlgebra.induction_linear with
  | zero => simp
  | add x y hx hy =>
      simp only [map_add, add_mul, hx, hy, MonoidAlgebra.coeff_add, Finsupp.add_apply]
  | single σ r =>
      induction d using MonoidAlgebra.induction_linear with
      | zero => simp
      | add x y hx hy =>
          simp only [map_add, mul_add, hx, hy, MonoidAlgebra.coeff_add,
            Finsupp.add_apply]
      | single τ s =>
          simp only [φ, ψ, invAlg, LinearEquiv.trans_apply,
            MonoidAlgebra.coeffLinearEquiv_apply, MonoidAlgebra.coeff_single,
            b.repr_symm_single, b.traceDual.repr_symm_single, smul_mul_smul,
            map_smul, b.trace_mul_traceDual, MonoidAlgebra.domCongr_single,
            MonoidAlgebra.single_mul_single, MonoidAlgebra.coeff_single]
          by_cases h : σ = τ
          · subst τ
            simp [mul_comm]
          · have hne : σ⁻¹ * τ ≠ 1 := by simpa [inv_mul_eq_one]
            simp [h, hne]

/-- A finite binary extension whose Galois group has odd cardinality admits a
self-dual normal basis indexed by that group. Starting from Mathlib's normal
basis, the construction multiplies by the inversion-invariant square root of
the transition element to the trace-dual basis in the group algebra. This is
the construction underlying `exists_selfDualNormalBasis`, paper
`04_preliminaries.tex:702-725`. -/
theorem exists_self_dual_normal_basis_gal (hodd : Odd (Nat.card G)) :
    ∃ c : Module.Basis G (ZMod 2) K,
      (∀ σ τ, Algebra.trace (ZMod 2) K (c σ * c τ) =
        if σ = τ then 1 else 0) ∧
      ∃ α : K, ∀ σ, c σ = σ α := by
  classical
  let A := MonoidAlgebra (ZMod 2) G
  let b := IsGalois.normalBasis (ZMod 2) K
  let φ : A ≃ₗ[ZMod 2] K :=
    (MonoidAlgebra.coeffLinearEquiv (ZMod 2)).trans b.repr.symm
  let ψ : A ≃ₗ[ZMod 2] K :=
    (MonoidAlgebra.coeffLinearEquiv (ZMod 2)).trans b.traceDual.repr.symm
  let v : A := φ.symm (b.traceDual 1)
  let invAlg : A ≃ₐ[ZMod 2] A :=
    MonoidAlgebra.domCongr (ZMod 2) (ZMod 2) (MulEquiv.inv G)
  obtain ⟨u, hu⟩ := (_root_.MIPStarRE.QPBT.monoid_algebra_sq_bijective hodd).surjective v
  change u ^ 2 = v at hu
  have hv_unit : IsUnit v := _root_.MIPStarRE.QPBT.normal_basis_transition_is_unit
  have hu_unit : IsUnit u := by
    rw [← isUnit_pow_iff (by omega : 2 ≠ 0), hu]
    exact hv_unit
  let U : Aˣ := hu_unit.unit
  have hU : (U : A) = u := hu_unit.unit_spec
  have hu_inv : invAlg u = u := by
    apply (_root_.MIPStarRE.QPBT.monoid_algebra_sq_bijective hodd).injective
    calc
      invAlg u ^ 2 = invAlg (u ^ 2) := (map_pow invAlg u 2).symm
      _ = invAlg v := congrArg invAlg hu
      _ = v := _root_.MIPStarRE.QPBT.normal_basis_transition_inv
      _ = u ^ 2 := hu.symm
  let mulU : A ≃ₗ[ZMod 2] A := Units.mulLeftLinearEquiv (ZMod 2) A U
  let c : Module.Basis G (ZMod 2) K :=
    (MonoidAlgebra.basis G (ZMod 2)).map (mulU.trans φ)
  have hc (σ : G) :
      c σ = φ ((U : A) * MonoidAlgebra.single σ (1 : ZMod 2)) := by
    simp only [c, Module.Basis.map_apply, LinearEquiv.trans_apply,
      MonoidAlgebra.basis_apply]
    exact congrArg φ (Units.mulLeftLinearEquiv_apply (ZMod 2) U _)
  have htransition (a : A) : φ (v * a) = ψ a := _root_.MIPStarRE.QPBT.normal_basis_transition a
  have hc_dual (τ : G) :
      c τ = ψ ((U⁻¹ : Aˣ) * MonoidAlgebra.single τ (1 : ZMod 2)) := by
    rw [hc, ← htransition]
    apply congrArg φ
    rw [← hu, ← hU]
    symm
    calc
      (U : A) ^ 2 * ((U⁻¹ : Aˣ) * MonoidAlgebra.single τ (1 : ZMod 2)) =
          (U : A) * (((U : A) * (U⁻¹ : Aˣ)) *
            MonoidAlgebra.single τ (1 : ZMod 2)) := by
              simp only [pow_two, mul_assoc]
      _ = (U : A) * MonoidAlgebra.single τ (1 : ZMod 2) := by simp
  refine ⟨c, ?_, φ (U : A), ?_⟩
  · intro σ τ
    rw [hc σ, hc_dual τ, _root_.MIPStarRE.QPBT.trace_group_algebra_pairing]
    have hInvU : invAlg (U : A) = (U : A) := by simpa [hU] using hu_inv
    rw [map_mul, hInvU, MonoidAlgebra.domCongr_single]
    simp only [MulEquiv.inv_apply]
    by_cases h : σ = τ
    · subst τ
      simp [mul_assoc, mul_comm, mul_left_comm]
    · have hne : σ⁻¹ * τ ≠ 1 := by simpa [inv_mul_eq_one]
      have hne' : τ * σ⁻¹ ≠ 1 := by simpa [mul_comm] using hne
      simp [mul_assoc, mul_comm, mul_left_comm, h, hne']
  · intro σ
    rw [hc, _root_.MIPStarRE.QPBT.normal_basis_repr_symm_mul_single]
    simp only [one_smul]
    rfl

end NormalTraceDual

/-- Existence over the binary extension of cardinality `2^k` for odd `k`;
blueprint `def:dual-self-dual-normal-basis`,
paper `04_preliminaries.tex:702-725`. -/
theorem exists_selfDualNormalBasis {K : Type*} [Field K] [Fintype K]
    [Algebra (ZMod 2) K] (k : ℕ) (hk : Odd k)
    (hcard : Fintype.card K = 2 ^ k) :
    ∃ b : Module.Basis (Fin k) (ZMod 2) K,
      _root_.MIPStarRE.QPBT.Basis.IsSelfDual b ∧ _root_.MIPStarRE.QPBT.Basis.IsNormal b := by
  classical
  let G := Gal(K/(ZMod 2))
  letI : CommGroup G := IsCyclic.commGroup
  have hfinrank : Module.finrank (ZMod 2) K = k := by
    apply Nat.pow_right_injective (by omega : 1 < 2)
    change 2 ^ Module.finrank (ZMod 2) K = 2 ^ k
    calc
      2 ^ Module.finrank (ZMod 2) K =
          Fintype.card (ZMod 2) ^ Module.finrank (ZMod 2) K := by norm_num
      _ = Fintype.card K := Module.card_eq_pow_finrank.symm
      _ = 2 ^ k := hcard
  have hcardG : Nat.card G = k :=
    (IsGalois.card_aut_eq_finrank (ZMod 2) K).trans hfinrank
  have hoddG : Odd (Nat.card G) := hcardG ▸ hk
  obtain ⟨cG, hcG_selfDual, α, hcG_normal⟩ :=
    _root_.MIPStarRE.QPBT.exists_self_dual_normal_basis_gal (K := K) hoddG
  let frob := FiniteField.frobeniusAlgEquivOfAlgebraic (ZMod 2) K
  let e₀ : Fin (Module.finrank (ZMod 2) K) ≃ G := Equiv.ofBijective
    (fun i => frob ^ i.1)
    (FiniteField.bijective_frobeniusAlgEquivOfAlgebraic_pow (ZMod 2) K)
  let e : Fin k ≃ G := (finCongr hfinrank.symm).trans e₀
  let c : Module.Basis (Fin k) (ZMod 2) K := cG.reindex e.symm
  refine ⟨c, ?_, α, ?_⟩
  · intro i j
    rw [Module.Basis.reindex_apply, Module.Basis.reindex_apply]
    simpa [e] using hcG_selfDual (e i) (e j)
  · intro i
    rw [Module.Basis.reindex_apply, hcG_normal]
    change (frob ^ i.1) α = α ^ (Fintype.card (ZMod 2) ^ i.1)
    rw [AlgEquiv.coe_pow,
      FiniteField.coe_frobeniusAlgEquivOfAlgebraic_iterate]

theorem zmod2_fin_equiv_symm_val (x : ZMod 2) :
    ((ZMod.finEquiv 2).symm x).val = if x = 1 then 1 else 0 := by
  fin_cases x <;> rfl

/--
A fixed finite-field model records the carrier and the chosen coding of its
elements by `Fin q`.  The algebra structure and stored basis data make explicit
the paper's once-and-for-all self-dual normal-basis convention; they are
deliberately part of the model rather than quantified afresh by the soundness
theorem.  This is the Lean carrier for blueprint
`def:binary-representation`, paper origin
`references/qpbt-paper/04_preliminaries.tex:653-728`.
-/
/- The finite-field carrier is specialized to `Type 0`, as are the finite
models used by the surrounding Euclidean-space API. -/
structure FixedFieldModel (q : ℕ) extends _root_.LIDT.MIPStarRE.LDT.FieldModel.{0} q where
  /-- Scalar restriction from `ZMod 2` to the chosen field. -/
  algebra : Algebra (ZMod 2) K
  /-- Dimension of the chosen basis over the prime subfield. -/
  basisDim : ℕ
  /-- The chosen basis dimension is odd, as required for a self-dual normal basis
  over the binary field. -/
  basisDimOdd : Odd basisDim
  /-- The admissible field-size relation for the chosen basis dimension. -/
  basisCard : q = 2 ^ basisDim
  /-- The chosen basis of `K` over `ZMod 2`. -/
  basis : Module.Basis (Fin basisDim) (ZMod 2) K
  /--
  The inherited coding of `K` is the natural binary encoding of the stored
  basis coordinates.  This field records the source's `downsize` convention
  rather than allowing an unrelated permutation of `Fin q`.  It is the
  coordinate clause of blueprint
  `def:binary-representation`, with paper origin
  `references/qpbt-paper/04_preliminaries.tex:669-680`.
  -/
  representation_natural :
    ∀ v : Fin basisDim → ZMod 2,
      (toFieldModel.equiv (basis.equivFun.symm v)).val =
        ∑ i : Fin basisDim, if v i = 1 then 2 ^ i.1 else 0
  /-- Self-duality of the chosen basis with respect to the field trace. -/
  selfDual : ∀ i j, Algebra.trace (ZMod 2) K (basis i * basis j) =
    if i = j then 1 else 0
  /-- Normality of the chosen basis, recorded by a Frobenius generator. -/
  normal : ∃ α : K, ∀ i, basis i = α ^ (2 ^ i.1)

/-!
The paper fixes the field representation and self-dual normal basis once for
each admissible field size.  We expose that choice through a single global
selector rather than carrying a potentially different model in every game
parameter record.  Existence is a named stage-4.3 proof obligation; the
selector itself is the resulting noncomputable choice.
-/

/-- An admissible binary field size admits the fixed self-dual normal model used
by the Pauli basis test.  This is the existence assertion implicit in
`def:dual-self-dual-normal-basis` and blueprint
`def:binary-representation`, paper origin
`references/qpbt-paper/04_preliminaries.tex:653-680,702-725`.

This theorem constructs the finite field and its little-endian coordinate
coding.  It records only mathematical existence; it does not formalize the
algorithmic complexity assertion in `lem:efficient_basis`.
-/
theorem exists_fixed_field_model (q : ℕ) (hq : _root_.MIPStarRE.QPBT.IsAdmissibleSize q) :
    Nonempty (_root_.MIPStarRE.QPBT.FixedFieldModel q) := by
  classical
  obtain ⟨k, hk, hq⟩ := hq
  subst q
  have hk0 : k ≠ 0 := by
    obtain ⟨m, hm⟩ := hk
    omega
  letI : Fact (Nat.Prime 2) := ⟨Nat.prime_two⟩
  let K := GaloisField 2 k
  letI : Fintype K := Fintype.ofFinite K
  have hcardK : Fintype.card K = 2 ^ k := by
    rw [Fintype.card_eq_nat_card, GaloisField.card 2 k hk0]
  obtain ⟨b, hb_selfDual, hb_normal⟩ :=
    _root_.MIPStarRE.QPBT.exists_selfDualNormalBasis (K := K) k hk hcardK
  let bitEquiv : (Fin k → ZMod 2) ≃ (Fin k → Fin 2) :=
    Equiv.piCongrRight fun _ => (ZMod.finEquiv 2).symm
  let fieldEquiv : K ≃ Fin (2 ^ k) :=
    b.equivFun.toEquiv |>.trans bitEquiv |>.trans finFunctionFinEquiv
  refine ⟨{
    toFieldModel := {
      K := K
      instField := inferInstance
      instFintype := inferInstance
      instDecidableEq := inferInstance
      equiv := fieldEquiv
    }
    algebra := (inferInstance : Algebra (ZMod 2) K)
    basisDim := k
    basisDimOdd := hk
    basisCard := rfl
    basis := b
    representation_natural := ?_
    selfDual := hb_selfDual
    normal := ?_
  }⟩
  · intro v
    change (fieldEquiv (b.equivFun.symm v)).val = _
    simp only [fieldEquiv, Equiv.trans_apply, LinearEquiv.coe_toEquiv,
      LinearEquiv.apply_symm_apply, bitEquiv]
    rw [finFunctionFinEquiv_apply]
    apply Finset.sum_congr rfl
    intro i _
    change ((ZMod.finEquiv 2).symm (v i)).val * 2 ^ i.1 = _
    rw [_root_.MIPStarRE.QPBT.zmod2_fin_equiv_symm_val]
    split_ifs <;> simp
  · obtain ⟨α, hα⟩ := hb_normal
    refine ⟨α, fun i => ?_⟩
    simpa using hα i

/-- The once-and-for-all field model selected for an admissible size.  Every
QPBT parameter record uses this same choice, matching the paper's fixed
self-dual normal-basis identification rather than quantifying over arbitrary
representations.  Blueprint `def:binary-representation`; paper origin
`references/qpbt-paper/04_preliminaries.tex:653-680`.
-/
noncomputable def fixedFieldModel (q : ℕ) (hq : _root_.MIPStarRE.QPBT.IsAdmissibleSize q) :
    _root_.MIPStarRE.QPBT.FixedFieldModel q :=
  Classical.choice (_root_.MIPStarRE.QPBT.exists_fixed_field_model q hq)

instance instFieldK {q : ℕ} (F : _root_.MIPStarRE.QPBT.FixedFieldModel q) : Field F.K := F.toFieldModel.instField
instance instFintypeK {q : ℕ} (F : _root_.MIPStarRE.QPBT.FixedFieldModel q) : Fintype F.K := F.toFieldModel.instFintype
instance instDecidableEqK {q : ℕ} (F : _root_.MIPStarRE.QPBT.FixedFieldModel q) : DecidableEq F.K :=
  F.toFieldModel.instDecidableEq
instance instAlgebraZModOfNatNatK {q : ℕ} (F : _root_.MIPStarRE.QPBT.FixedFieldModel q) : Algebra (ZMod 2) F.K :=
  F.algebra

/-- The fixed binary representation obtained from the chosen basis coordinates. -/
noncomputable def binaryRepresentation {q : ℕ} (F : _root_.MIPStarRE.QPBT.FixedFieldModel q) : F.K ≃ Fin q :=
  F.toFieldModel.equiv

/--
The coordinate map associated with a finite basis.  This is the `κ` of
blueprint `def:subfields-kappa`,
whose paper origin is `references/qpbt-paper/04_preliminaries.tex:433-502`.
-/
noncomputable abbrev kappa {F K ι : Type*} [CommSemiring F] [Semiring K]
    [Algebra F K] [Finite ι]
    (b : Module.Basis ι F K) : K ≃ₗ[F] (ι → F) :=
  b.equivFun



/--
The finite-field trace used by the Pauli phases.  This is a thin wrapper around
Mathlib's basis-independent `Algebra.trace`, matching Equation `eq:def-trace`
in blueprint `def:subfield-trace`
(`references/qpbt-paper/04_preliminaries.tex:481-502`).
-/
noncomputable abbrev binTrace (K : Type*) [CommRing K] [Algebra (ZMod 2) K] :
    K →ₗ[ZMod 2] ZMod 2 :=
  Algebra.trace (ZMod 2) K

/-- The trace selected by a fixed model; this is the map denoted `tr` in the
paper's blueprint `def:binary-representation`,
paper origin `references/qpbt-paper/04_preliminaries.tex:653-680`. -/
noncomputable def fixedBinTrace {q : ℕ} (F : _root_.MIPStarRE.QPBT.FixedFieldModel q) : F.K → ZMod 2 :=
  _root_.MIPStarRE.QPBT.binTrace F.K



end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Algebra/FieldBasis.lean#L26-L607

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