Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

On a problem of D. H. Lehmer


Authors: Stéphane R. Louboutin, Joël Rivat and András Sárközy
Journal: Proc. Amer. Math. Soc. 135 (2007), 969-975
MSC (2000): Primary 11K45; Secondary 11L05, 11L40
DOI: https://doi.org/10.1090/S0002-9939-06-08558-3
Published electronically: September 26, 2006
MathSciNet review: 2262896
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ p$ be an odd prime number. For $ n\in\{1,\ldots,p-1\}$ we denote the inverse of $ n$ modulo $ p$ by $ n^{*}$ with $ n^{*}\in\{1,\ldots,p-1\}$. Given $ \varepsilon>0$, we prove that in any range $ n\in\{N+1,\ldots,N+L\}\subseteq\{1,\ldots,p-1\}$ of length $ L\geq p^{1/2+\varepsilon}$ the probability that $ n^{*}$ has the same parity as $ n$ tends to $ 1/2$ as $ p\rightarrow +\infty$. This result was previously known only to hold true in the full range $ n\in\{1,\ldots,p-1\}$ of length $ L=p-1$. We will also obtain quantitative results on the pseudorandomness of the sequence $ (-1)^{n+n^{*}}$ for which we estimate the well-distribution $ W$ and correlation measures $ C_k$ as defined by Mauduit and Sárközy (1997).


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

  • 1. N. Alon, Y. Kohayakawa, C. Mauduit, C.-G. Moreira, and V. Rödl, Measures of pseudorandomness for finite sequences: minimum and typical values, submitted to Combinatorics, Probability and Computation (to appear).
  • 2. Julien Cassaigne, Christian Mauduit, and András Sárközy, On finite pseudorandom binary sequences VII: The measures of pseudorandomness, Acta Arithmetica 103 (2002), no. 2, 97-118. MR 1904866 (2004c:11139)
  • 3. Jürgen Eichenauer-Herrmann and Harald Niederreiter, Bounds for exponential sums and their applications to pseudorandom numbers, Acta Arithmetica 67 (1994), no. 3, 269-281. MR 1292739 (95g:11079)
  • 4. Etienne Fouvry, Philippe Michel, Joël Rivat, and András Sárközy, On the pseudorandomness of the signs of Kloosterman sums, Journal of the Australian Mathematical Society 77 (2004), 425-436. MR 2099811 (2005h:11165)
  • 5. Richard K. Guy, Unsolved problems in number theory, Unsolved Problems in Intuitive Mathematics, vol. 1, Springer-Verlag, New York, 1981, Problem Books in Mathematics. MR 0656313 (83k:10002)
  • 6. Christian Mauduit and András Sárközy, On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol, Acta Arithmetica 82 (1997), 365-377. MR 1483689 (99g:11095)
  • 7. Christian Mauduit and András Sárközy, Construction of pseudorandom binary sequences by using the multiplicative inverse, Acta Mathematica Hungarica 108 (2005), 239-252. MR 2162562 (2006c:11092)
  • 8. C. J. Moreno and O. Moreno, Exponential sums and Goppa codes: I, Proceedings of the American Mathematical Society 111 (1991), 523-531. MR 1028291 (91f:11087)
  • 9. Joël Rivat and András Sárközy, Modular constructions of pseudorandom binary sequences with composite moduli, Periodica Mathematica Hungarica 51 (2005), 75-107. MR 2194941
  • 10. A. Weil, Sur les courbes algébriques et les variétés qui s'en déduisent, Act. Sci. Ind., vol. 1041, Hermann, Paris, 1948. MR 0027151 (10:262c)
  • 11. Zhang Wenpeng, On a problem of D. H. Lehmer and its generalization, Compositio Math. 86 (1993), no. 3, 307-316. MR 1219630 (94f:11104)
  • 12. Wen Peng Zhang, A problem of D. H. Lehmer and its generalization. II, Compositio Math. 91 (1994), no. 1, 47-56. MR 1273925 (95f:11079)
  • 13. Yi Yuan and Wen-peng Zhang, On generalization of Lehmer D H problem, Gongcheng Shuxue Xuebao 20 (2003), no. 1, 60-64. MR 1975320 (2004b:11123)
  • 14. Wenpeng Zhang, A problem of D. H. Lehmer and its mean square value formula, Japan. J. Math. (N.S.) 29 (2003), no. 1, 109-116. MR 1986866 (2004d:11097)
  • 15. Wenpeng Zhang, A problem of D. H. Lehmer and Kloosterman's sums, Monatshefte für Mathematik 139 (2003), 247-257. MR 1994384 (2004e:11088)
  • 16. Wenpeng Zhang, Xu Zongben, and Yi Yuan, A problem of D. H. Lehmer and its mean square value formula, J. Number Theory 103 (2003), no. 2, 197-213. MR 2020268 (2004m:11128)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 11K45, 11L05, 11L40

Retrieve articles in all journals with MSC (2000): 11K45, 11L05, 11L40


Additional Information

Stéphane R. Louboutin
Affiliation: Institut de Mathématiques de Luminy, UMR 6206, 163, avenue de Luminy, Case 907, 13288 Marseille Cedex 9, France
Email: loubouti@iml.univ-mrs.fr

Joël Rivat
Affiliation: Institut de Mathématiques de Luminy, UMR 6206, 163, avenue de Luminy, Case 907, 13288 Marseille Cedex 9, France
Email: rivat@iml.univ-mrs.fr

András Sárközy
Affiliation: Department of Algebra and Number Theory, Eötvös Loránd University, H-1117 Budapest, Pázmány Péter sétány 1/c, Hungary
Email: sarkozy@cs.elte.hu

DOI: https://doi.org/10.1090/S0002-9939-06-08558-3
Keywords: Pseudo-random, binary sequence, correlation
Received by editor(s): August 8, 2005
Received by editor(s) in revised form: November 8, 2005
Published electronically: September 26, 2006
Additional Notes: The research of the third author was partially supported by the Hungarian National Foundation for Scientific Research, Grants No T043623 and T049693. This paper was written when the third author was visiting the Institut de Mathématiques de Luminy.
Communicated by: Wen-Ching Winnie Li
Article copyright: © Copyright 2006 American Mathematical Society

American Mathematical Society