Estimating energy of binary slices reveals sum patterns in modular arithmetic
Energy Estimation of the Hamming Slice and its Applications
Information Theory
Summary
This paper studies special groups of numbers that are written in binary and share the same number of ones in their representation. The authors find a formula that predicts how often certain sums of these numbers happen within a special modular system. They also show when these sums cover all possible results, meaning the sums spread out evenly. To do this, they use a unique method involving an automatic machine that tracks how binary carries work in a circle, which is a new idea for this kind of problem.
Hamming weightmodular arithmeticadditive energybinary expansionresiduesasymptotic formulasumsetscarry automatoncyclic groupuniform distribution
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.