# Solutions to $\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$ with $|x_i| < \ell$

Are there any clear conditions on $$p,\ell$$ and $$m$$ under which the equation $$\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$$ has at most one solution with $$|x_i|<\ell$$ with high probability over a random choice of $$\gamma$$ and the $$\xi_i$$?

This is closely related to the SIS problem, but instead of having several equations this only involves one. Also, the question is not about the hardness of finding such solutions, but about the conditions on which at most one solution exists.

As an example, if $$\ell = 2$$, then the problems looks much like the Knapsack problem, and is likely to have one solution at most. However, as $$\ell$$ grows larger, the chances there are more than one solution also grow.

• Is $p$ supposed to be prime? And when you say a solution you mean a non-zero vector $( x_1, ..., x_m)$, right? Dec 17 '18 at 8:03
• Not necessarily non-zero, since $\gamma$ is chosen at random. And yes, $p$ is supposed to be a prime :) Dec 20 '18 at 23:00

Are there any clear conditions on $$p,\ell$$ and $$m$$ under which the equation $$\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$$ has at most one solution with $$|x_i|<\ell$$, where $$\gamma$$ and the $$\xi_i$$ are uniformly random?
For any $$\ell \ge 2$$, there will be values of $$\gamma$$ and $$\xi_i$$ for which there are multiple solutions; one such set of values would be $$\gamma = 0$$ and $$\xi_1 = 0$$. Hence, any condition that forbids multiple solutions would necessarily have $$\ell < 2$$ (which isn't very interesting)
Perhaps you mean to ask "yields more than one solution with probability $$< \epsilon$$"; that is a rather harder question, but might give you a more useful answer.