×

A generalization of the Goresky-Klapper conjecture. I. (English) Zbl 1435.11007

Summary: For a fixed integer \(n\geq 2\), we show that a permutation of the least residues mod \(p\) of the form \(f(x)=Ax^k \bmod p\) cannot map a residue class mod \(n\) to just one residue class \(\mod n\) once \(p\) is sufficiently large, other than the maps \(f(x)=\pm x \bmod p\) when \(n\) is even and \(f(x)=\pm x\) or \(\pm x^{(p+1)/2} \bmod p\) when \(n\) is odd.

MSC:

11A07 Congruences; primitive roots; residue systems
11B50 Sequences (mod \(m\))
11L07 Estimates on exponential sums
11L03 Trigonometric and exponential sums (general theory)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] E. Alkan, F. Stan, and A. Zaharescu, Lehmer \(k\)-tuples, Proc. Amer. Math. Soc., 134 (2006), pp. 2807–2818. · Zbl 1173.11045
[2] E. Bach and J. Sorenson, Explicit bounds for primes in residue classes, Math. Comp., 65 (1996), pp. 1717–1735. · Zbl 0853.11077
[3] J. Bourgain, T. Cochrane, J. Paulhus, and C. Pinner, Decimations of \(l\)-sequences and permutations of even residues mod \(p\), SIAM J. Discrete Math., 23 (2009), pp. 842–857. · Zbl 1213.11006
[4] J. Bourgain, T. Cochrane, J. Paulhus, and C. Pinner, On the parity of \(k\)th powers mod \(p\) a generalization of a problem of Lehmer, Acta Arith., 147 (2011), pp. 173–203. · Zbl 1239.11106
[5] D. A. Burgess, A note on the distribution of residues and non-residues, J. Lond. Math. Soc., 38 (1963), pp. 253–256. · Zbl 0118.04703
[6] T. Cochrane and S. Konyagin, Proof of the Goresky Klapper conjecture on decimations of \(L\)-sequences, SIAM J. Discrete Math., 25 (2011), pp. 1812–1831. · Zbl 1238.11003
[7] T. Cochrane, M. Mossinghoff, C. Pinner, and C. Richardson, A Generalization of the Goresky-Klapper Conjecture, Part II, Experiment. Math., to appear.
[8] T. Cochrane and C. Pinner, Explicit bounds on monomial and binomial exponential sums, Q. J. Math., 66 (2017), pp. 203–219. · Zbl 1404.11004
[9] T. Cochrane, On a trigonometric inequality of Vinogradov, J. Number Theory, 26 (1987), pp. 9–16. · Zbl 0629.10030
[10] A. O. Gelfond and Yu. V. Linnik, Elementary Methods in Analytic Number Theory, Rand McNally, Chicago, 1965.
[11] M. Goresky and A. Klapper, Arithmetic cross-correlations of FCSR sequences, IEEE Trans. Inform. Theory, 43 (1997), pp. 1342–1346. · Zbl 0878.94047
[12] S. W. Graham and C. J. Ringrose, Lower bounds for least quadratic nonresidues, Anal. Number Theory Progr. Math. 85, Birkhäuser, Boston, 1990, pp. 269–309.
[13] R. K. Guy, Unsolved Problems in Number Theory, 3rd ed., Probl. Books Math., Springer-Verlag, New York, 2004. · Zbl 1058.11001
[14] D. R. Heath-Brown, Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression, Proc. Lond. Math. Soc. (3), 64 (1992), pp. 265–338. · Zbl 0739.11033
[15] P. Hummel, On consecutive quadratic non-residues: A conjecture of Issai Schur, J. Number Theory, 103 (2003), pp. 257–266. · Zbl 1049.11006
[16] Y. Lamzouri, X. Li, and K. Soundararajan, Conditional bounds for the least quadratic non-residue and related problems, Math. Comp., 84 (2015), pp. 2391–2412. · Zbl 1326.11058
[17] Y. Lu and Y. Yi, On the generalization of the D. H. Lehmer problem, Acta Math. Sin. (Engl. Ser.), 25 (2009), pp. 1269–1274. · Zbl 1170.11022
[18] Y. Lu and Y. Yi, On the generalization of the D. H. Lehmer problem II, Acta Arith., 142 (2010), pp. 179–186. · Zbl 1194.11096
[19] H. L. Montgomery, Topics in Multiplicative Number Theory, Lecture Notes in Math. 227, Springer-Verlag, New York, 1971. · Zbl 0216.03501
[20] I. Shparlinski, On a generalisation of a Lehmer problem, Math. Z., 263 (2009), pp. 619–631. · Zbl 1269.11068
[21] I. Shparlinski, On a generalised Lehmer problem for arbitrary powers, East-West J. Math., 2008, pp. 197–204. · Zbl 1182.11005
[22] A. Weil, On some exponential sums, Proc. Natl. Acad. Sci. USA, 34 (1948), pp. 204–207. · Zbl 0032.26102
[23] P. Xi and Y. Yi, Generalized D. H. Lehmer problem over short intervals, Glasg. Math. J., 53 (2011), pp. 293–299. · Zbl 1273.11008
[24] T. Xylouris, On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions, Acta Arith., 150 (2011), pp. 65–91. · Zbl 1248.11067
[25] Y. Yi and W. Zhang, On the generalization of a problem of D. H. Lehmer, Kyushu J. Math., 56 (2002), pp. 235–241. · Zbl 1136.11323
[26] W. Zhang, On a problem of D. H. Lehmer and its generalization, Compos. Math., 86 (1993), pp. 307–316. · Zbl 0783.11002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.