Energy estimation reveals structure in binary hamming slices
Energy Estimation of the Hamming Slice and its Applications
Information Theory
Summary
This paper studies sets of numbers defined by how many 1s appear in their binary form, called their Hamming weight. The authors find a precise formula for how often sums of these numbers overlap, known as additive energy. They also introduce a new method using a cyclic automaton to understand the patterns of how digit-carrying works in modular addition. These results help describe how sums involving these numbers distribute and when such sums cover many possible values evenly.
What this means in practice
- •For cryptography engineers: Improve the analysis of modular arithmetic structures found in cryptographic algorithms involving binary residue sets with fixed Hamming weight.
- •For error correcting code designers: Use the energy estimates to better understand the distribution of binary vectors with fixed Hamming weight, aiding in code design and analysis.
A theory result. No direct application yet.
Authors
Aniruddha Biswas, Jihun Hwang, Hemanta K. Maji, Ilya D. Shkredov, Xiuyu Ye
Abstract
Let $R=\mathbb{Z}/(2^n-1)\mathbb{Z}$, where $n\geq 3$, and let $S_w\subseteq R$ be the residues whose canonical $n$-digit binary expansion has Hamming weight $w$. We obtain, in particular, an asymptotic formula for the additive energy of $S_w$ \[ E(S_w)=\frac{\left|S_w\right|^4}{|R|}+ \mathcal{O}\left(|R|^3 n^{-3} \right), \] which holds uniformly in $w$. The error term is optimal in order, with a matching lower bound for $w=\lfloor n/2+\sqrt{n} \rfloor$. It follows that triple sums of arbitrary unit dilates have asymptotically uniform representation counts when $\prod_{j=1}^{3} \left|S_{w_j} \right| /\left(|R| n^{-3/5}\right)^3\to\infty$, and that double sums have asymptotically full support when $\left|S_{w_1}\right| \left|S_{w_2} \right|/\left(|R| n^{-3/4}\right)^2\to\infty$. In the proof, modular collisions are represented using a cyclic binary carry automaton; this appears to be a novel approach in this area of problems.