We have two vectors $A=\{a_{1},...,a_{z}\},X=\{x_{1},...,x_{z}\}\in\mathbb{N}^{z}$ and $n\in\mathbb{N}$ with $A\cdot X=n$ as their normal Euclidean inner product.
The values of $A$ and $n$ are known and the goal is to find a lower bound for $\max_{i=1}^{z}(v(x_{i}))$ were $v(n)$ is the binary digit sum of $n$.
If we have a sub-multiplicative and sub-additive function $f$ so $f(a+b)\le f(a)+f(b)$ and $f(a\cdot b)\le f(a)\cdot f(b)$ we can rearrange the norm to give this:
$$\max_{i=1}^{z}f(x_{i})\geq\left\lceil \frac{f(n)}{\sum_{i=1}^{z}f(a_{i})}\right\rceil$$
It's possible to pick $f(n)=v(n)$ since it's well known that digit sums have this property. More generally we can have with odd integer $m$:
$f(n)=v(m\cdot n\bmod 2^k)$ with integer $k$ and $x\bmod b$ being the least positive integer in the residue class modulo $b$
$f(n)=v(m\cdot n\bmod 2^k-2^j)$, integer $j,k$ with $k>j$
$f(n)=v_{NAF}(n)$ where $v_{NAF}(n)$ is the number of non-zero digits in the nonadjacent form of the integer $n$ (digits +1,0,-1 in binary).
Each of these selections for $f(n)$ work for different problems. In practice they work very well. I have a couple of questions.
Are there other functions ($f$) I could use to get bounds on the hamming weight of $x_i$?
I can't help thinking I am missing some kind of generalization of these techniques that would be better. Am I nibbling at the edges of something better?
