AFTD Auto-Formalizing Theoretical Domains

digit_exchange_walsh_prob

deforiginal

Given 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 of digit_exchange_walsh m c u v s t equals j * 2^m, when the input mask (u,v) is chosen uniformly from (GaloisField 2 m)^2 and the output mask (s,t) is chosen uniformly from (GaloisField 2 m)^2 minus {(0,0)}.

Statement

noncomputable def digit_exchange_walsh_prob (m : ℕ) (c : GaloisField 2 m) (j : ℕ) : ℝ
Related work
arXiv:2611.02572
Verified
13 Nov 2026
Axioms
none listed
Built on 1
  • digit_exchange_walshGiven 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,…

Read back from the Lean

digit_exchange_walsh_prob m c j is defined as a real number representing the proportion (probability) of mask pairs ((u, v), (s, t)) in (GaloisField 2 m × GaloisField 2 m) × ((GaloisField 2 m × GaloisField 2 m) \ {(0, 0)}) for which the absolute value of digit_exchange_walsh m c u v s t equals j * 2^m.

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

/-- Probability that |W(u,v;s,t)| = j * 2^m for random input masks and nonzero output masks. -/
noncomputable def digit_exchange_walsh_prob (m : ℕ) (c : GaloisField 2 m) (j : ℕ) : ℝ := by
  classical
  let F := GaloisField 2 m
  haveI : Fintype F := Fintype.ofFinite F
  let inputMasks : Finset (F × F) := Finset.univ
  let outputMasks : Finset (F × F) := Finset.univ.filter (· ≠ (0, 0))
  let totalMasks : Finset ((F × F) × (F × F)) := inputMasks ×ˢ outputMasks
  let favorable := totalMasks.filter (fun ⟨⟨u, v⟩, ⟨s, t⟩⟩ =>
    |digit_exchange_walsh m c u v s t| = (j : ℤ) * (2 : ℤ) ^ m)
  exact (favorable.card : ℝ) / (totalMasks.card : ℝ)
See it in the graphDiscuss this resultChallenge it