The exact collision cost of low-weight uniformity for polynomial maps over GF(2)
Let Q: F₂ⁿ → F₂ᵐ have coordinates of algebraic degree at most k, and suppose its output on a uniform input is d-wise uniform but not uniform. This note finds the exact smallest number of ordered collisions such a map can have. For square maps (m = n), the minimum excess over a bijection is 2^max(⌈n/k⌉, d+1). Two classical bounds give this value, and an explicit ring of gates attains it for every k ≥ 1 and 0 ≤ d < n. New in this version: compressing maps (1 ≤ m ≤ n). Here the minimum of C(Q) − 2^(2n−m) is 2^max(2⌈n/k⌉ − m, ⌈n/k⌉, d+1). While m ≥ ⌈n/k⌉, the answer matches the square case and is attained by dropping control wires from the ring. When m falls below ⌈n/k⌉ the minimum jumps to 2^(2⌈n/k⌉ − m). The jump comes from a Parseval bound, and it is attained by folding the surplus ring wires into one output, which leaves a single nonzero Walsh coefficient. All results are proved in Lean 4 using only Lean's standard axioms. They are also checked by exhaustive enumeration of small cases. The case of maps with more outputs than inputs remains open. This is an informal note, released to put the result out there. A more careful write-up may follow. Comments and pointers to prior work are welcome. Code: https://github.com/LizzoLizard/quiet-collisions-math
Authors
- Ayomide Shittu Daniel Shittu
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-21
- DOI
- https://doi.org/10.5281/zenodo.24427416
- Primary Topic
- Coding theory and cryptography
- Type
- article
- Field-Weighted Citation Impact
- 0.00