Distribution of $n$-th roots modulo a smooth number

Question

Let $n \ge 2$. Let $p_1,\dots,p_m$ be distinct primes $\equiv 1 \pmod{n}$. Let $N=p_1 p_2 \cdots p_m$. If $\gcd(a,N)=1$ and the equation $x^n \equiv a \pmod{N}$ has a solution then it has $n^m$ solutions. This question concerns how these $n$-th roots are distributed as $a$ varies, particularly with $n$ fixed and $m$ large.

Question. Do there exist $\alpha$ and $\beta$ with $0 \le \alpha \le \beta <1$ and $\beta-\alpha$ small, such that for every $a$ coprime to $N$ that is an $n$-th power modulo $N$, there is $b$ satisfying $\alpha N \le b \le \beta N$ and $b^n \equiv a \pmod{N}$? Can we take $\beta-\alpha=O(n^{-m})$?

Answer 1

This is a partial answer. The idea is from my recent preprint http://arxiv.org/abs/1509.03768

Additionally assuming that $p_1, \cdots, p_m$ are least among the congruence $1$ mod $n$,

By repeated application of Linnik's theorem, there is an absolute constant $L$ such that $N< n^{L^m}$.

We use the following result on exponential sums over $\mathbb{Z}_N^{*}$ by J. Bourgain:

Let $N\geq 1$. For any $\epsilon>0$, there exist a constant $\delta_0=\delta_0(\epsilon)>0$ such that for any subgroup $H$ of $\mathbb{Z}_N^{*}$ with $|H|>N^{\epsilon}$, $$ \max_{(m,N)=1}\left|\sum_{a\in H}e^{2\pi i m\frac {a}N}\right|<N^{-\delta_0}|H|.$$

Note that we can use the above for any cosets of $H$.

The set of solutions of the congruence $x^n \equiv a$ mod $N$ forms a coset of the subgroup $H$ of $\mathbb{Z}_N^{*}$ where $$ H=\{y\in\mathbb{Z}_N^{*} | y^n \equiv 1 \textrm{ mod }N\}.$$

Taking $\epsilon = \frac{m}{L^m}$, we have $N^{\epsilon}<|H|$.

Then by Bourgain's exponential sum result applied on the coset, and Erdős-Turán inequality, there exists $\delta(m)>0$ such that $$ \left||\{ 0<x<N : x^n\equiv a (\textrm{ mod }N), \frac xN \in (\alpha,\beta) \textrm{ mod $1$} \}| - (\beta-\alpha)n^m\right|\leq n^m N^{-\delta(m)}$$ Thus, $$ |\{ 0<x<N : x^n\equiv a (\textrm{ mod }N), \frac xN \in (\alpha,\beta) \textrm{ mod $1$} \}| = (\beta-\alpha)n^m +O(n^m N^{-\delta(m)}).$$ Therefore, if $N^{-\delta(m)}=o(\beta-\alpha)$, then we are guaranteed the existence of solution to $x^n\equiv a$ mod $N$ in the interval $(\alpha N, \beta N)$.

Here's the reference:

J. Bourgain, Exponential sum estimates over subgroups of $\mathbb{Z}_q^{*}$, $q$ arbitrary , Journal d'Analyse Mathematique, December 2005, Volume 97, Issue 1, pp 317-355.

Answer 2

Partial answer.

For $n=2$ finding the smallest solution is NP-complete via reduction from SAT.

NP-Complete Decision Problems for Binary Quadratics p. 3

The problem of solving $ x^2 \equiv a \pmod{N}$ with natural solution satisfying $ 0 \le x \le \gamma$ is NP-complete.

Since this is NP-complete and $a$ depends on the SAT instance I don't expect very sharp bounds, might be wrong on this.