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$ $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 the 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?

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?

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$ $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 the 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?

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$ $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 the 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?