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.

  • $\begingroup$ Should there be some additional hypothesis to prevent, for example, the situation where all the $a_i$ are equal? $\endgroup$ – Andreas Blass Jul 18 '13 at 14:52
  • $\begingroup$ Yes, let's assume they are all different. $\endgroup$ – Lior Eldar Jul 18 '13 at 15:04
  • $\begingroup$ "All different" won't work because there are $n$ of the integers $a_i$'s, all in $[0,m]$ with $m < n$ $\endgroup$ – Andreas Blass Jul 18 '13 at 15:08
  • $\begingroup$ Of corse! - fixed the mistake above. $\endgroup$ – Lior Eldar Jul 18 '13 at 15:49

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.