Inverse trace in arbitrary binary coordinates
DefinitionParityBarrier563_Trilinear_Supplement_InverseTraceboolean-circuitscomplexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let K be a field with an algebra structure over and an ordered basis . Encode by . Define
For , the basis identifies K with and the trace lies in its prime subfield. Inverse at zero is zero. The sign is the published . 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