Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Inverse trace in arbitrary binary coordinates

Definition
ParityBarrier563_Trilinear_Supplement_InverseTrace

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

boolean-circuitscomplexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let K be a field with an algebra structure over F2\mathbb F_2F2​ and an ordered basis e0,…,en−1e_0,\ldots,e_{n-1}e0​,…,en−1​. Encode x∈{0,1}nx\in\{0,1\}^nx∈{0,1}n by ιe(x)=∑ixiei\iota_e(x)=\sum_i x_ie_iιe​(x)=∑i​xi​ei​. Define

Tr⁡n(z)=∑j=0n−1z2j,Ie(x)=1{Tr⁡n(ιe(x)−1)=1},χ(z)=(−1)Tr⁡n(z).\operatorname{Tr}_n(z)=\sum_{j=0}^{n-1}z^{2^j},\quad I_e(x)=1_{\{\operatorname{Tr}_n(\iota_e(x)^{-1})=1\}},\quad\chi(z)=(-1)^{\operatorname{Tr}_n(z)}.Trn​(z)=j=0∑n−1​z2j,Ie​(x)=1{Trn​(ιe​(x)−1)=1}​,χ(z)=(−1)Trn​(z).

For n≥1n\ge1n≥1, the basis identifies K with F2n\mathbb F_{2^n}F2n​ and the trace lies in its prime subfield. Inverse at zero is zero. The sign is the published 2Ie−12I_e-12Ie​−1. Coordinate shifts use XOR; zeroFill embeds a live-coordinate assignment with zero on fixed coordinates. These definitions cover every basis without a preferred polynomial basis.

Definition code
import Mathlib
import Definitions.Def_ParityBarrier563_Trilinear_Supplement_FiniteAverages

set_option autoImplicit false
open scoped Classical

namespace ParityBarrier563.Trilinear.Supplement

/-- Coordinate encoding in an arbitrary F₂-basis. A basis with n vectors supplies exactly
all elements of the characteristic-two field, hence the field has 2^n elements. -/
noncomputable def fieldPoint {n : ℕ} {K : Type} [Field K] [Algebra (ZMod 2) K]
    (e : Module.Basis (Fin n) (ZMod 2) K) (x : Fin n → Bool) : K :=
  ∑ i, (if x i then e i else 0)

/-- Absolute trace, calculated in K. Its values lie in the embedded F₂. -/
def absoluteTrace (n : ℕ) {K : Type} [Field K] (z : K) : K :=
  ∑ j : Fin n, z ^ (2 ^ j.val)

/-- Inverse trace, accepting exactly when its F₂ value is one; field inverse at 0 is 0. -/
noncomputable def inverseTrace {n : ℕ} {K : Type} [Field K] [Algebra (ZMod 2) K]
    (e : Module.Basis (Fin n) (ZMod 2) K) : BoolFn (Fin n) :=
  fun x => decide (absoluteTrace n (fieldPoint e x)⁻¹ = 1)

/-- Canonical additive character (-1)^Tr, with Tr computed in K. -/
noncomputable def character (n : ℕ) {K : Type} [Field K] (z : K) : ℝ :=
  if absoluteTrace n z = 1 then -1 else 1

/-- Fill live coordinates and put zero on fixed coordinates, for a shift uniform in live(τ). -/
def zeroFill {V : Type} (τ : Restriction V) (w : Live τ → Bool) : V → Bool :=
  fun v => match h : τ v with
    | none => w ⟨v,h⟩
    | some _ => false

/-- Coordinate XOR equals addition in every F₂-basis. -/
def shift {V : Type} (w : V → Bool) (J : RealFn V) : RealFn V :=
  fun x => J (fun i => Bool.xor (x i) (w i))

end ParityBarrier563.Trilinear.Supplement
Source
Nikolai Chukhin, Xin Li, Ivan Mihajlin, Yan Zhong, Breaking the Parity Barrier for Constant-Depth Circuits, STOC 2027 submission #563 (October 2026), §1.2, printed p.3 / PDF 5; §2, printed p.11 / PDF 13; §5.3, printed p.22 / PDF 24

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