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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

The exact collision cost of low-weight uniformity for polynomial maps over GF(2)

Ayomide Shittu Daniel Shittu
Zenodo (CERN European Organization for Nuclear Research)
Coding theory and cryptography
article

The exact collision cost of low-weight uniformity for polynomial maps over GF(2)

Ayomide Shittu Daniel Shittu
article en

Abstract

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

Zenodo (CERN European Organization for Nuclear Research)
Coding theory and cryptography
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
The exact collision cost of low-weight uniformity for polynomial maps over GF(2) — Ayomide Shittu Daniel Shittu · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS