Bounds for multiplicative cosets over fields of prime order

Abstract:

Let $m$ be a positive integer and suppose that $p$ is an odd prime with $p \equiv 1 \bmod m$. Suppose that $a \in (\mathbb {Z}/p\mathbb {Z})^*$ and consider the polynomial $x^m-a$. If this polynomial has any roots in $(\mathbb {Z}/p\mathbb {Z})^*$, where the coset representatives for $\mathbb {Z}/p\mathbb {Z}$ are taken to be all integers $u$ with $|u|<p/2$, then these roots will form a coset of the multiplicative subgroup $\mu _m$ of $(\mathbb {Z}/p\mathbb {Z})^*$ consisting of the $m$th roots of unity mod $p$. Let $C$ be a coset of $\mu _m$ in $(\mathbb {Z}/p\mathbb {Z})^*$, and define $|C|=\max _{u \in C}{|u|}$. In the paper “Numbers Having $m$ Small $m$th Roots mod $p$” (Mathematics of Computation, Vol. 61, No. 203 (1993),pp. 393-413), Robinson gives upper bounds for $M_1(m,p)=\min _{\tiny C \in (\mathbb {Z}/p\mathbb {Z})^* /\mu _m }{|C|}$ of the form $M_1(m,p)<K_mp^{1-1/\phi (m)}$, where $\phi$ is the Euler phi-function. This paper gives lower bounds that are of the same form, and seeks to sharpen the constants in the upper bounds of Robinson. The upper bounds of Robinson are proven to be optimal when $m$ is a power of $2$ or when $m=6.$