Submitted on 04 Mar 2015
Integer Addition and Hamming Weight
John Y. Kim
We study the effect of addition on the Hamming weight of a positive integer.
Consider the first $2^n$ positive integers, and fix an $\alpha$ among them. We
show that if the binary representation of $\alpha$ consists of $\Theta(n)$
blocks of zeros and ones, then addition by $\alpha$ causes a constant fraction
of low Hamming weight integers to become high Hamming weight integers. This
result has applications in complexity theory to the hardness of computing
powering maps using bounded-depth arithmetic circuits over $\mathbb{F}_2$. Our
result implies that powering by $\alpha$ composed of many blocks require
exponential-size, bounded-depth arithmetic circuits over $\mathbb{F}_2$.
http://arxiv.org/abs/1503.01170v2