Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A note on Linnik’s theorem on quadratic non-residues

  • Published:
Archiv der Mathematik Aims and scope Submit manuscript

Abstract

We present a short and purely combinatorial proof of Linnik’s theorem: for any \(\varepsilon >0\) there exists a constant \(C_\varepsilon \) such that for any N, there are at most \(C_\varepsilon \) primes \(p\le N\) such that the least positive quadratic non-residue modulo p exceeds \(N^\varepsilon \).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Balister, P., Bollobás, B., Lee, J.D., Morris, R., Riordan, O.: A note on Linnik’s theorem on quadratic non-residues, arXiv:1712.07179

  2. Bombieri, E.: On the large sieve. Mathematika 12, 201–225 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  3. Cojocaru, A.C., Murty, M.R.: An Introduction to Sieve Methods and Their Applications, London Mathematical Society Student Texts, vol. 66. Cambridge University Press, Cambridge (2006)

    Google Scholar 

  4. Dickman, K.: On the frequency of numbers containing prime factors of a certain relative magnitude. Ark. Mat. Astron. Fys. 22, 1–14 (1930)

    MATH  Google Scholar 

  5. Friedlander, J.B., Iwaniec, H.: Opera de cribro, American Mathematical Society Colloquium Publications, vol. 57. American Mathematical Society, Providence, RI (2010)

    MATH  Google Scholar 

  6. Goldfeld, D.: The elementary proof of the prime number theorem: an historical perspective. In: Chudnovsky, D., Chudnovsky, G., Nathanson, M. (eds.) Number Theory, pp. 179–192. Springer, New York (2004)

    Chapter  Google Scholar 

  7. Linnik, U.V.: The large sieve. C. R. (Doklady) Acad. Sci. URSS (N.S.) 30, 292–294 (1941)

    MathSciNet  MATH  Google Scholar 

  8. Linnik, U.V.: A remark on the least quadratic non-residue. C. R. (Doklady) Acad. Sci. URSS (N.S.) 36, 119–120 (1942)

    MathSciNet  MATH  Google Scholar 

  9. Mertens, F.: Ein Beitrag zur analytischen Zahlentheorie. J. Reine Angew. Math. 78, 46–62 (1874)

    MathSciNet  MATH  Google Scholar 

  10. Rényi, A.: On the representation of an even number as the sum of a single prime and a single almost-prime number. Dokl. Akad. Nauk SSSR (N.S.) 56, 455–458 (1947)

    MathSciNet  MATH  Google Scholar 

  11. Rényi, A.: Un nouveau théorème concernant les fonctions indépendantes et ses applications à la théorie des nombres. J. Math. Pures Appl. 28, 137–149 (1949)

    MathSciNet  MATH  Google Scholar 

  12. Rényi, A.: On the large sieve of Ju.V. Linnik. Compos. Math. 8, 68–75 (1951)

    MathSciNet  Google Scholar 

  13. Rényi, A.: New version of the probabilistic generalization of the large sieve. Acta Math. Acad. Sci. Hung. 10, 217–226 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  14. Roth, K.F.: On the large sieves of Linnik and Rényi. Mathematika 12, 1–9 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  15. Tenenbaum, G.: Introduction to Analytic and Probabilistic Number Theory (3rd edn), Graduate Studies in Mathematics, vol. 163. American Mathematical Society, Providence (2015)

    Book  Google Scholar 

Download references

Acknowledgements

The work of the first two authors was partially supported by NSF Grant DMS 1600742, and work of the second author was also partially supported by MULTIPLEX Grant 317532. The work of the fourth author was partially supported by CNPq (Proc. 303275/2013-8) and FAPERJ (Proc. 201.598/2014). The research in this paper was carried out while the third, fourth and fifth authors were visiting the University of Memphis.

Author information

Authors and Affiliations

  1. Department of Mathematical Sciences, University of Memphis, Memphis, TN, 38152, USA

    Paul Balister & Béla Bollobás

  2. Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge, CB3 0WB, UK

    Béla Bollobás

  3. London Institute for Mathematical Sciences, 35a South St., Mayfair, London, W1K 2XF, UK

    Béla Bollobás

  4. Microsoft Research, Redmond, USA

    Jonathan D. Lee

  5. IMPA, Estrada Dona Castorina 110 Jardim Botânico, Rio de Janeiro, RJ, Brazil

    Robert Morris

  6. Mathematical Institute, University of Oxford, Radcliffe Observatory Quarter, Woodstock Road, Oxford, OX2 6GG, UK

    Oliver Riordan

Authors
  1. Paul Balister
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Béla Bollobás
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jonathan D. Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Robert Morris
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Oliver Riordan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Robert Morris.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Balister, P., Bollobás, B., Lee, J.D. et al. A note on Linnik’s theorem on quadratic non-residues. Arch. Math. 112, 371–375 (2019). https://doi.org/10.1007/s00013-018-1281-y

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00013-018-1281-y

Mathematics Subject Classification

Keywords

Search

Navigation