New pseudorandom sequences constructed by quadratic residues and Lehmer numbers
HTML articles powered by AMS MathViewer
- by Huaning Liu PDF
- Proc. Amer. Math. Soc. 135 (2007), 1309-1318 Request permission
Abstract:
Let $p$ be an odd prime. Define \[ e_n = \begin {cases} (-1)^{n+\overline {n}}, & \text {if $n$ is a quadratic residue mod $p$},\\ (-1)^{n+\overline {n}+1}, & \text {if $n$ is a quadratic nonresidue mod $p$}, \end {cases} \] where $\overline {n}$ is the multiplicative inverse of $n$ modulo $p$ such that $1\leq \overline {n}\leq p-1$. This paper shows that the sequence $\{e_n\}$ is a “good" pseudorandom sequence, by using the properties of exponential sums, character sums, Kloosterman sums and mean value theorems of Dirichlet $L$-functions.References
- Tom M. Apostol, Introduction to analytic number theory, Undergraduate Texts in Mathematics, Springer-Verlag, New York-Heidelberg, 1976. MR 0434929
- Julien Cassaigne, Sébastien Ferenczi, Christian Mauduit, Jöel Rivat, and András Sárközy, On finite pseudorandom binary sequences. III. The Liouville function. I, Acta Arith. 87 (1999), no. 4, 367–390. MR 1671629, DOI 10.4064/aa-87-4-367-390
- Julien Cassaigne, Sébastien Ferenczi, Christian Mauduit, Joël Rivat, and András Sárközy, On finite pseudorandom binary sequences. IV. The Liouville function. II, Acta Arith. 95 (2000), no. 4, 343–359. MR 1785199, DOI 10.4064/aa-95-4-343-359
- Julien Cassaigne, Christian Mauduit, and András Sárközy, On finite pseudorandom binary sequences. VII. The measures of pseudorandomness, Acta Arith. 103 (2002), no. 2, 97–118. MR 1904866, DOI 10.4064/aa103-2-1
- Étienne Fouvry, Philippe Michel, Joël Rivat, and András Sárközy, On the pseudorandomness of the signs of Kloosterman sums, J. Aust. Math. Soc. 77 (2004), no. 3, 425–436. MR 2099811, DOI 10.1017/S1446788700014543
- Takeo Funakura, On Kronecker’s limit formula for Dirichlet series with periodic coefficients, Acta Arith. 55 (1990), no. 1, 59–73. MR 1056115, DOI 10.4064/aa-55-1-59-73
- Richard K. Guy, Unsolved problems in number theory, 2nd ed., Problem Books in Mathematics, Springer-Verlag, New York, 1994. Unsolved Problems in Intuitive Mathematics, I. MR 1299330, DOI 10.1007/978-1-4899-3585-4
- S. R. Louboutin, J. Rivat and A. Sárközy, On a problem of D. H. Lehmer, Proceedings of the American Mathematical Society, to appear.
- Christian Mauduit and András Sárközy, On finite pseudorandom binary sequences. I. Measure of pseudorandomness, the Legendre symbol, Acta Arith. 82 (1997), no. 4, 365–377. MR 1483689, DOI 10.4064/aa-82-4-365-377
- Christian Mauduit and András Sárközy, On the measures of pseudorandomness of binary sequences, Discrete Math. 271 (2003), no. 1-3, 195–207. MR 1999543, DOI 10.1016/S0012-365X(03)00044-X
- André Weil, Sur les courbes algébriques et les variétés qui s’en déduisent, Publ. Inst. Math. Univ. Strasbourg, vol. 7, Hermann & Cie, Paris, 1948 (French). MR 0027151
- André Weil, On some exponential sums, Proc. Nat. Acad. Sci. U.S.A. 34 (1948), 204–207. MR 27006, DOI 10.1073/pnas.34.5.204
- Zhang Wenpeng, On a problem of D. H. Lehmer and its generalization, Compositio Math. 86 (1993), no. 3, 307–316. MR 1219630
- Wen Peng Zhang, A problem of D. H. Lehmer and its generalization. II, Compositio Math. 91 (1994), no. 1, 47–56. MR 1273925
- Wen Peng Zhang, On the difference between a D. H. Lehmer number and its inverse modulo $q$, Acta Arith. 68 (1994), no. 3, 255–263. MR 1308126, DOI 10.4064/aa-68-3-255-263
- Zhang Wenpeng, On a problem of D. H. Lehmer and Kloosterman sums, Monatsh. Math. 139 (2003), no. 3, 247–257. MR 1994384, DOI 10.1007/s00605-002-0529-5
- Wen Peng Zhang, On a problem of D. H. Lehmer and general Kloosterman sums, Acta Math. Sin. (Engl. Ser.) 20 (2004), no. 3, 515–524. MR 2084715, DOI 10.1007/s10114-004-0329-z
- 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, DOI 10.1016/S0022-314X(03)00113-6
Additional Information
- Huaning Liu
- Affiliation: Department of Mathematics, Northwest University, Xi’an, Shaanxi, People’s Republic of China
- Email: hnliu@nwu.edu.cn
- Received by editor(s): October 28, 2005
- Received by editor(s) in revised form: December 23, 2005
- Published electronically: November 14, 2006
- Additional Notes: This work was supported by the NSF (10271093, 60472068) of P. R. China.
- Communicated by: Wen-Ching Winnie Li
- © Copyright 2006
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 135 (2007), 1309-1318
- MSC (2000): Primary 11A07, 11K45
- DOI: https://doi.org/10.1090/S0002-9939-06-08630-8
- MathSciNet review: 2276639