digit_exchange_walsh
Given a natural number m, an element c in GaloisField 2 m, input masks u, v in GaloisField 2 m, and output masks s, t in GaloisField 2 m, the binary Walsh transform digit_exchange_walsh m c u v s t is the sum over a, b in GaloisField 2 m of (-1)^(Tr(u * a + v * b + s * L + t * D(L) * a)), where D(x) = x^2 + x + c, L = D(a) * b, and Tr is the absolute trace to ZMod 2.
Statement
noncomputable def digit_exchange_walsh (m : ℕ) (c : GaloisField 2 m) (u v s t : GaloisField 2 m) : ℤ
- Related work
- arXiv:2611.02572
- Verified
- 13 Nov 2026
- Axioms
- none listed
- Used by 1
- digit_exchange_walsh_probGiven a natural number m, c in GaloisField 2 m, and j in Nat, digit_exchange_walsh_prob m c j is the probability that the absolute value…
Read back from the Lean
A definition digit_exchange_walsh which, given a natural number m : ℕ and elements c, u, v, s, t : GaloisField 2 m, computes the integer-valued sum over all pairs (a, b) ∈ GaloisField 2 m × GaloisField 2 m of:
- 1 if Algebra.trace (ZMod 2) (GaloisField 2 m) (u * a + v * b + s * L + t * D(L) * a) = 0
- -1 if the trace is non-zero (i.e. equal to 1 in ZMod 2),
where D(x) = x^2 + x + c and L = D(a) * b.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Binary Walsh transform W(u,v;s,t) of the digit-exchange permutation over GF(2^m). -/ noncomputable def digit_exchange_walsh (m : ℕ) (c : GaloisField 2 m) (u v s t : GaloisField 2 m) : ℤ := by classical let D (x : GaloisField 2 m) : GaloisField 2 m := x ^ 2 + x + c let F := GaloisField 2 m haveI : Fintype F := Fintype.ofFinite F exact ∑ a : F, ∑ b : F, let L := D a * b let val := u * a + v * b + s * L + t * D L * a if Algebra.trace (ZMod 2) F val = 0 then (1 : ℤ) else (-1 : ℤ)