×

Optimal bounds for Büchi’s problem in modular arithmetic. (English) Zbl 1369.11015

Summary: We study the second order analogue of the problem of finding optimal lower and upper bounds for the length of sequences of squares in arithmetic progression modulo a prime, and some connections with the computational problem of finding a quadratic nonresidue modulo a prime. More precisely, we work modulo an integer and our objects of study are those sequences of squares whose the second difference is an invertible constant. The main results of our work is a number of exact formulae that allow to reduce the problem to prime moduli. We also observe several phenomena which are supported by extensive numerical computations.

MSC:

11B50 Sequences (mod \(m\))
11T99 Finite fields and commutative rings (number-theoretic aspects)
11Y55 Calculation of integer sequences

Software:

Xcas; OEIS; PARI/GP; Python
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] The on-line encyclopedia of integer sequences (OEIS), http://oeis.org; The on-line encyclopedia of integer sequences (OEIS), http://oeis.org
[2] PARI/GP, version http://pari.math.u-bordeaux.fr/; PARI/GP, version http://pari.math.u-bordeaux.fr/
[3] Python, version http://www.python.org; Python, version http://www.python.org
[4] Xcas 1.1.0 (c) 2000-14, Bernard Parisse, Renee De Graeve, http://www-fourier.ujf-grenoble.fr/ parisse/giac.html; Xcas 1.1.0 (c) 2000-14, Bernard Parisse, Renee De Graeve, http://www-fourier.ujf-grenoble.fr/ parisse/giac.html
[5] Ankeny, N. C., The least quadratic non residue, Ann. of Math. (2), 55, 65-72 (1952) · Zbl 0046.04006
[6] Bach, E., Explicit bounds for primality testing and related problems, Math. Comp., 55, 191, 355-380 (1990) · Zbl 0701.11075
[7] Burgess, D. A., The distribution of quadratic residues and non-residues, Mathematika, 4, 106-112 (1957) · Zbl 0081.27101
[8] Cohen, H., A Course in Computational Algebraic Number Theory, Springer GTM, vol. 138 (2000)
[9] Graham, S. W.; Ringrose, C. J., Lower bounds for least quadratic nonresidues, (Analytic Number Theory. Analytic Number Theory, Allerton Park, IL, 1989. Analytic Number Theory. Analytic Number Theory, Allerton Park, IL, 1989, Progr. Math., vol. 85 (1990), Birkhäuser Boston: Birkhäuser Boston Boston, MA), 269-309
[10] D. Hensley, Sequences of squares with second difference of two and a problem of logic, unpublished (1980-1983).; D. Hensley, Sequences of squares with second difference of two and a problem of logic, unpublished (1980-1983).
[11] D. Hensley, Sequences of squares with second difference of two and a conjecture of Büchi, unpublished (1980-1983).; D. Hensley, Sequences of squares with second difference of two and a conjecture of Büchi, unpublished (1980-1983).
[12] Iwaniec, H.; Kowalski, E., Analytic Number Theory, AMS Colloquium Publications, vol. 53 (2004) · Zbl 1059.11001
[13] Lipshitz, L., Quadratic forms, the five square problem, and Diophantine equations, (MacLane, S.; Siefkes, Dirk, The Collected Works of J. Richard Büchi (1990), Springer), 677-680
[14] Montgomery, H. L., Topics in Multiplicative Number Theory, Lecture Notes in Mathematics, vol. 227 (1971) · Zbl 0216.03501
[15] Pasten, H., Büchi’s problem in any power for finite fields, Acta Arith., 149, 1, 57-63 (2011) · Zbl 1288.11115
[16] Pasten, H., Powerful values of polynomials and a conjecture of Vojta, J. Number Theory, 133, 9, 2964-2998 (2013) · Zbl 1364.11090
[17] Pasten, H.; Pheidas, T.; Vidaux, X., A survey on Büchi’s problem: new presentations and open problems, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI). Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), J. Math. Sci. (N. Y.), 171, 6, 765-781 (2010), translation in · Zbl 1282.11015
[18] Stepanov, S. A., Lower bounds for incomplete sums of the characters of polynomials, Tr. Mat. Inst. Steklova, 143, 175-177 (1977), (in Russian)
[19] Stepanov, S. A., Arithmetic of Algebraic Curves, Monographs in Contemporary Mathematics, 368 (1995), Nauka: Nauka Moscow, Translated from Russian to English in: · Zbl 0753.14021
[20] Weil, A., On some exponential sums, Proc. Natl. Acad. Sci. USA, 34, 204-207 (1948) · Zbl 0032.26102
[21] Woods, A., Musing on Büchi’s quadratic forms problem and the logic of finite fields
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.