Spreading-out integers via multiplication

Question

Let $a_1,...,a_n\in [0,m]$ be a set of $n$ positive integers, where $n<<m$, $m=poly(n)$. One can assume $m$ is prime. Is there an efficient, possibly randomized, way to find an integer $N=poly(n)$, such that $(a_i \cdot N) (mod \ m)$ is approximately uniform on $[0,m]$. The value of $N$ may also depend on the approximation parameter.

Answer 1

Choosing $N$ at random and checking should work. Put $e(t)=e^{2\pi i t/m}$. Then we have \begin{eqnarray*} \sum_{N=1}^m\sum_{k=1}^K\left|\sum_{i=1}^ne(k N a_i)\right|^2 & = & \sum_{N=1}^m\sum_{k=1}^K\sum_1\leq i,j\leq n e(kN(a_i-a_j))\\ & = & m\sum_{k\leq K} \#\{(i,j)|a_i\equiv a_j\pmod{\frac{m}{(m, k)}}\}. \end{eqnarray*} Since the $a_i$ are all different and in $[0, m]$, for fixed $a_i$ the number of $a_j$ satisfying the last congruence is $(m,k)$ at most, and the last sum is bounded above by $mn\sum_{k\leq K}(k,m)\leq mnK^2$.

Denote by $D_N$ the discrepancy of $a_iN\bmod m$. Then we have $$ D_N\ll \frac{n}{K}+\sum_{k\leq K}\frac{1}{k}\left|\sum_{i=1}^n e(kNa_i)\right|, $$ thus $$ \frac{1}{m}\sum_{N=1}^m D_N \ll \frac{n}{K} + \sqrt{nK}\log K. $$ Hence for most $N$ we have $D_N\ll n^{2/3}\log n$, which is reasonable good equidistribution.

Checking whether for a random $N$ we have that $D_N<n$ is small requires between $n^{1+\epsilon}$ and $n^{3/2}$ steps, depending on how small $D_N$ has to be.