Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Bounds for Multiplicative Cosets over Fields of Prime Order

Author: Corey Powell
Journal: Math. Comp. 66 (1997), 807-822
MSC (1991): Primary 11A07, 11A15; Secondary 11N05, 11R18, 11R44
MathSciNet review: 1372008
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 (\Bbb Z /p\Bbb Z )^{\ast } $ and consider the polynomial $x^m-a$. If this polynomial has any roots in $(\Bbb Z /p\Bbb Z )^{\ast } $, where the coset representatives for $\Bbb Z /p\Bbb 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 $(\Bbb Z /p\Bbb Z )^{\ast } $ consisting of the $m$th roots of unity mod $p$. Let $C$ be a coset of $\mu _m$ in $(\Bbb Z /p\Bbb Z )^{\ast } $, 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 (\Bbb Z /p\Bbb Z )^{\ast } /\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.$

References [Enhancements On Off] (What's this?)

  • 1. J.W.S. Cassels and A. Frohlich, Algebraic Number Theory, Academic Press Limited, 1967. MR 35:6500
  • 2. John L. Kelley and T.P. Srinivasan, Measure and Integral, Springer-Verlag, 1988. MR 89e:28001
  • 3. Sergey Konyagin and Igor Shparlinski, On the Distribution of Residues of Finitely Generated Multiplicative Groups and Some of Their Applications, to appear.
  • 4. S. Lang, Algebraic Number Theory, Springer-Verlag, 1994. MR 95f:11085
  • 5. C.G. Lekkerkerker, Geometry of Numbers, Wolters-Noordhoff and North-Holland Publishing Companies, 1969. MR 42:5915
  • 6. R.M. Robinson, Numbers Having $m$ Small $m$th Roots mod $p$, Mathematics of Computation 61 (1993), no. 203, 393-413. MR 93k:11002
  • 7. P. Stevenhagen and H.W. Lenstra, Jr., Chebotarev and his density theorem, Math. Intelligencer 18 (1996), 26-37. CMP 96:14
  • 8. J.E. Vaaler, A Geometric Inequality with Applications to Linear Forms, Pacific Journal of Mathematics 83 (1979), no. 2, 543-553. MR 81d:52007

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11A07, 11A15, 11N05, 11R18, 11R44

Retrieve articles in all journals with MSC (1991): 11A07, 11A15, 11N05, 11R18, 11R44

Additional Information

Corey Powell
Affiliation: Department of Mathematics, University of California at Berkeley, Berkeley, California 94720

Received by editor(s): May 30, 1995
Received by editor(s) in revised form: January 26, 1996
Article copyright: © Copyright 1997 American Mathematical Society

American Mathematical Society