Quadratic Residues and Non-Residues in Arithmetic Progression

详细信息    查看全文

• 刊名：Lecture Notes in Mathematics
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：2171
• 期：1
• 页码：227-271
• 全文大小：734 KB
• 参考文献：1.B. Berndt, Classical theorems on quadratic residues. Enseignement Math. 22, 261–304 (1976)MathSciNet MATH
  2.H. Cohen, Number Theory, vol. I (Springer, New York, 2000)MATH
  3.J.B. Conway, Functions of One Complex Variable, vol. 1 (Springer, New York, 1978)CrossRef
  4.K.L. Chung, A Course in Probability Theory (Academic Press, New York, 1974)MATH
  5.H. Davenport, On character sums in finite fields. Acta Math. 71, 99–121 (1939)MathSciNet CrossRef MATH
  6.H. Davenport, Multiplicative Number Theory (Springer, New York, 2000)MATH
  7.H. Davenport, P. Erdös, The distribution of quadratic and higher residues. Publ. Math. Debrecen 2, 252–265 (1952)MathSciNet MATH
  8.R. Dedekind, Sur la Th \(\acute{\text{e}}\) orie des Nombres Entiers Alg \(\acute{\text{e}}\) briques (1877); English translation by J. Stillwell (Cambridge University Press, Cambridge, 1996)
  9.P.G.L. Dirichlet, Sur la convergence des series trigonom\(\acute{\text{e}}\) trique qui servent \(\grave{\text{a}}\) repr\(\acute{\text{e}}\) senter une fonction arbitraire entre des limites donn\(\acute{\text{e}}\) e. J. Reine Angew. Math. 4, 157–169 (1829)
  10.P.G.L. Dirichlet, Beweis eines Satzes da\(\ss \) jede unbegrenzte arithmetische Progression, deren erstes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Faktor sind, unendlich viele Primzahlen enh\(\ddot{\text{a}}\) lt. Abh. K. Preuss. Akad. Wiss. 45–81 (1837)
  11.P.G.L. Dirichlet, Recherches sur diverses applications de l’analyse infinit\(\acute{\text{e}}\) simal \(\grave{\text{a}}\) la th\(\acute{\text{e}}\) orie des nombres. J. Reine Angew. Math. 19, 324–369 (1839); 21 (1–12), 134–155 (1840)
  12.P.G.L. Dirichlet, Vorlesungen über Zahlentheorie (1863); English translation by J. Stillwell (American Mathematical Society, Providence, 1991)
  13.J. Dugundji, Topology (Allyn and Bacon, Boston, 1966)MATH
  14.P. Erdös, On a new method in elementary number theory which leads to an elementary proof of the prime number theorem. Proc. Nat. Acad. Sci. U.S.A. 35, 374–384 (1949)MathSciNet CrossRef MATH
  15.L. Euler, Theoremata circa divisores numerorum in hac forma pa 2 ± qb 2 contentorum. Comm. Acad. Sci. Petersburg 14, 151–181 (1744/1746)
  16.L. Euler, Theoremata circa residua ex divisione postestatum relicta. Novi Commet. Acad. Sci. Petropolitanea 7, 49–82 (1761)
  17.L. Euler, Observationes circa divisionem quadratorum per numeros primes. Opera Omnia I-3, 477–512 (1783)
  18.M. Filaseta, D. Richman, Sets which contain a quadratic residue modulo p for almost all p. Math. J. Okayama Univ. 39, 1–8 (1989)
  19.C.F. Gauss, Disquisitiones Arithmeticae (1801); English translation by A. A. Clarke (Springer, New York, 1986)
  20.C.F. Gauss, Theorematis arithmetici demonstratio nova. Göttingen Comment. Soc. Regiae Sci. XVI, 8 pp. (1808)
  21.C.F. Gauss, Summatio serierum quarundam singularium. Göttingen Comment. Soc. Regiae Sci. 36 pp. (1811)
  22.C.F. Gauss, Theorematis fundamentalis in doctrina de residuis quadraticis demonstrationes et amplicationes novae, 1818, Werke, vol. II (Georg Olms Verlag, Hildescheim, 1973), pp. 47–64
  23.C.F. Gauss, Theorematis fundamentallis in doctrina residuis demonstrationes et amplicationes novae. Göttingen Comment. Soc. Regiae Sci. 4, 17 pp. (1818)
  24.C.F. Gauss, Theoria residuorum biquadraticorum: comentatio prima. Göttingen Comment. Soc. Regiae Sci. 6, 28 pp. (1828)
  25.C.F. Gauss, Theoria residuorum biquadraticorum: comentatio secunda. Göttingen Comment. Soc. Regiae Sci. 7, 56 pp. (1832)
  26.D. Gröger, Gauß’ Reziprozitätgesetze der Zahlentheorie: Eine Gesamtdarstellung der Hinterlassenschaft in Zeitgemäßer Form (Erwin-Rauner Verlag, Augsburg, 2013)
  27.E. Hecke, Vorlesungen über die Theorie der Algebraischen Zahlen (1923); English translation by G. Brauer and J. Goldman (Springer, New York, 1981)MATH
  28.D. Hilbert, Die Theorie der Algebraischen Zahlkörper (1897); English translation by I. Adamson (Springer, Berlin, 1998)
  29.T. Hungerford, Algebra (Springer, New York, 1974)MATH
  30.K. Ireland, M. Rosen, A Classical Introduction to Modern Number Theory (Springer, New York, 1990)CrossRef MATH
  31.P. Kurlberg, The distribution of spacings between quadratic residues II. Isr. J. Math. 120, 205–224 (2000)MathSciNet CrossRef MATH
  32.P. Kurlberg, Z. Rudnick, The distribution of spacings between quadratic residues. Duke Math. J. 100, 211–242 (1999)MathSciNet CrossRef MATH
  33.J.L. Lagrange, Probl\(\grave{\text{e}}\) mes ind\(\acute{\text{e}}\) termin\(\acute{\text{e}}\) s du second degr\(\acute{\text{e}}\) . Mém. Acad. R. Berlin 23, 377–535 (1769)
  34.J.L. Lagrange, Reserches d’Arithm\(\acute{\text{e}}\) tique, 2nde partie. Nouv. Mém. Acad. Berlin 349–352 (1775)
  35.E. Landau, Elementary Number Theory. English translation by J. Goodman (Chelsea, New York, 1958)MATH
  36.A. Legendre, Reserches d’analyse indéterminée. Histoiré de l’Académie Royale des Sciences de Paris (1785), pp. 465–559, Paris 1788
  37.A. Legendre, Essai sur la Th \(\acute{\text{e}}\) orie des Nombres (Paris, 1798)
  38.F. Lemmermeyer, Reciprocity Laws (Springer, New York/Berlin/Heidelberg, 2000)CrossRef MATH
  39.W.J. LeVeque, Topics in Number Theory, vol. II (Addison-Wesley, Reading, 1956)MATH
  40.D. Marcus, Number Fields (Springer, New York, 1977)CrossRef MATH
  41.H. Montgomery, R. Vaughan, Multiplicative Number Theory I: Classical Theory (Cambridge University Press, Cambridge, 2007)MATH
  42.R. Nevenlinna, V. Paatero, Introduction to Complex Analysis (Addison-Wesley, Reading, 1969)
  43.O. Ore, Les Corps Alg \(\acute{\text{e}}\) briques et la Th \(\acute{\text{e}}\) orie des Id \(\acute{\text{e}}\) aux (Gauthier-Villars, Paris, 1934)
  44.G. Perel’muter, On certain character sums. Usp. Mat. Nauk. 18, 145–149 (1963)MathSciNet MATH
  45.C. de la Vall\(\acute{\text{e}}\) e Poussin, Recherches analytiques sur la th\(\acute{\text{e}}\) orie des nombres premiers. Ann. Soc. Sci. Bruxelles 20, 281–362 (1896)
  46.H. Rademacher, Lectures on Elementary Number Theory (Krieger, New York, 1977)MATH
  47.G.F.B. Riemann, \(\ddot{\text{U}}\) ber die Anzahl der Primzahlen unter einer gegebenen Gr\(\ddot{\text{o}}\ss \) e. Monatsberischte der Berlin Akademie (1859), pp. 671–680
  48.K. Rosen, Elementary Number Theory and Its Applications (Pearson, Boston, 2005)
  49.J. Rosenberg, Algebraic K-Theory and Its Application (Springer, New York, 1996)
  50.W. Schmidt, Equations over Finite Fields: an Elementary Approach (Springer, Berlin, 1976)CrossRef MATH
  51.A. Selberg, An elementary proof of Dirichlet’s theorem on primes in arithmetic progressions, Ann. Math. 50, 297–304 (1949)MathSciNet CrossRef MATH
  52.A. Selberg, An elementary proof of the prime number theorem. Ann. Math. 50, 305–313 (1949)MathSciNet CrossRef MATH
  53.A. Shamir, Identity-based cryptosystems and signature schemes, in Advances in Cryptology, ed. by G.R. Blakely, D. Chaum (Springer, Berlin, 1985), pp. 47–53CrossRef
  54.J. Shohat, J.D. Tamarkin, The Problem of Moments (American Mathematical Society, New York, 1943)CrossRef MATH
  55.R. Taylor, A. Wiles, Ring-theoretic properties of certain Hecke algebras. Ann. Math. 141, 553–572 (1995)MathSciNet CrossRef MATH
  56.J. Urbanowicz, K.S. Williams, Congruences for L-Functions (Kluwer, Dordrecht, 2000)CrossRef MATH
  57.A. Weil, Sur les Courbes Algébriques et les Variétes qui s’en Déduisent (Hermann et Cie, Paris, 1948)MATH
  58.A. Weil, Basic Number Theory (Springer, New York, 1973)CrossRef MATH
  59.L. Weisner, Introduction to the Theory of Equations (MacMillan, New York, 1938)MATH
  60.A. Wiles, Modular elliptic curves and Fermat’s last theorem. Ann. Math. 141, 443–551 (1995)MathSciNet CrossRef MATH
  61.S. Wright, Quadratic non-residues and the combinatorics of sign multiplication. Ars Combin. 112, 257–278 (2013)MathSciNet MATH
  62.S. Wright, Quadratic residues and non-residues in arithmetic progression. J. Number Theory 133, 2398–2430 (2013)MathSciNet CrossRef MATH
  63.S. Wright, On the density of primes with a set of quadratic residues or non-residues in given arithmetic progression, J. Combin. Number Theory 6, 85–111 (2015)MathSciNet MATH
  64.B.F. Wyman, What is a reciprocity law? Am. Math. Monthly 79, 571–586 (1972)MathSciNet CrossRef MATH
  65.A. Zygmund, Trigonometric Series (Cambridge University Press, Cambridge, 1968)MATH
  
• 作者单位：Steve Wright (14)
  
  14. Department of Mathematics and Statistics, Oakland University, Rochester, Michigan, USA
  
• 丛书名：Quadratic Residues and Non-Residues
• ISBN：978-3-319-45955-4
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Probability Theory and Stochastic Processes
  Dynamical Systems and Ergodic Theory
  Mathematical Biology
  Partial Differential Equations
  Functional Analysis
  Abstract Harmonic Analysis
  Group Theory and Generalizations
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1617-9692
• 卷排序：2171

文摘

The distribution problem for residues and non-residues has been intensively studied for 175 years using a rich variety of formulations and techniques. The work done in Chap. 7 gave a window through which we viewed one of these formulations and also saw a very important technique used to study it. Another problem that has been studied almost as long and just as intensely is concerned with the arithmetic structure of residues and non-residues. In this chapter, we will sample one aspect of that very important problem by studying when residues and non-residues form very long sequences in arithmetic progression. The first major advance in that problem came in 1939 when Harold Davenport proved the existence of residues and non-residues which form arbitrarily long sets of consecutive integers. As an introduction to the circle of ideas on which the work of this chapter is based, we briefly discuss Davenport’s results and the technique that he used to obtain them in Sect. 9.1. Davenport’s approach uses another application of the Dirichlet-Hilbert trick, which we used in the proofs of Theorems 4.​12 and 5.​13 presented in Chap. 5, together with an ingenious estimate of the absolute value of certain Legendre-symbol sums with polynomial values in their arguments. Davenport’s technique is quite flexible, and so we will adapt it in order to detect long sets of residues and non-residues in arithmetic progression. In Sect. 9.2, we will formulate our results precisely as a series of four problems which will eventually be solved in Sects. 9.4 and 9.10. This will require the estimation of the sums of values of Legendre symbols with polynomial arguments a la Davenport, which estimates we will derive in Sect. 9.3 by making use of a very important result of Andr Weil concerning the number of rational points on a nonsingular algebraic curve over ℤ∕p ℤ. In addition to these estimates, we will also need to calculate a term which will be shown to determine the asymptotic behavior of the number of sets of residues or non-residues which form long sequences of arithmetic progressions, and this calculation will be performed in Sects. 9.6–9.9. Here we will see how techniques from combinatorial number theory are applied to study residues and non-residues. In Sect. 9.11, an interesting class of examples will be presented, and we will use it to illustrate exactly how the results obtained in Sect. 9.10, together with some results of Sect. 9.11, combine to describe asymptotically how many sets there are of residues or non-residues which form long arithmetic progressions. Finally, the last section of this chapter discusses a result which, in certain interesting situations, calculates the asymptotic density of the set of primes which have residues and non-residues which form long sets of specified arithmetic progressions.