next up previous
Next: About this document ...

A WebPage on Number Theory papers relevant to VDW theorem

by William Gasarch

(For now this is just papers that I want to gather in one place)

Papers about Consecutive $n$th powers

Definition: ${\rm con}_L(k)$ is the least prime such that for all $p\ge {\rm con}_n(k)$ there will be $k$ a run of $k$ consecutive $L$th powers.

End of Definition


We abbreviate the phrase run of $k$ consecutive $L$th powers by RkCL.

The following is in a paper by Lehmer and Lehmer (paper below) however, they seem to treat it as folklore.

Theorem: ${\rm con}_2(2)=7$.

Proof:

Note that there is no R2C2 mod 5. Note that there is a R2C2 mod 7: 1,2 since $3^2\equiv 2 \pmod 7$.

Let $p\ge 11$. All arithmetic is mod $p$. If 2 is a square then there is a pair, namely $(1,2)$. If 5 is a square then there is a pair, namely $(4,5)$. If neither is a square then the product $2\times 5 \pmod p$ is a square and hence

End of Proof

Note that this proof is elementary. More formally we have a bound on where the R2C2 will be: it will always start with a number that is $\le 9$. We call such proofs LL to honor Lehmer and Lehmer. (Using the term elementary is not good since this can mean other things.)

Many of the papers listed below show that this kind of proof is not possible for some of the ${\rm con}_n(k)$ values.

  1. H. Davenport.
    On the distribution of quadratic residues mod p.
    Journal of the London Mathematical Society, 6:49-54, 1932. For $k=4,5$ the number of RkC2 is $p/2^k + O(p^{3/4})$.

  2. H. Davenport.
    On the distribution of $l$th power residues mod p.
    Journal of the London Mathematical Society, 7:117-121, 1932. LthResiduesdavenport The last theorem of this paper is that if $p\ge 100L^{12}$ then there are 3 consecutive $L$th roots mod $p$.

  3. H. Davenport.
    On the distribution of quadratic residues mod p.
    Journal of the London Mathematical Society, 8:46-52, 1933. qresdavenport2

  4. D. Burgess.
    The distribution of the quadratic residues and non-residues.
    Mathematika, pages 106-112, 1957. BURGESS.PDF. this paper shows that the max number of consecutive quadraic residues or non-residues mod $p$ is $O(p^{1/4 +\delta})$.

  5. D. H. Lehmer and E. Lehmer.
    On runs of residues.
    Proceedings of the American Mathematical Society, 13:102-106, 1962. This paper shows that there is no LL proof of a bound on ${\rm con}_2(3)$. LL.PDF.

  6. D. H. Lehmer, E. Lehmer, W. Mills, and J.L.Selfridge.
    Machine proof of a theorem on cubic residues.
    Mathematics of Computation, 16:407-415, 1962. This paper gives an LL proof that ${\rm con}_3(3)=293$. LLMS.PDF.

  7. R. G. Bierstedy and W. H. Mills.
    On the bound for a pair of consecutive quartic residues of a prime.
    Proceedings of the American Mathematical Society, 14:628-632, 1963. This paper gives an LL proof that ${\rm con}_4(2) = 43$. BIEMILLS.PDF.

  8. D. H. Lehmer and E. Lehmer.
    On runs of residues.
    Proceedings of the American Mathematical Society, 13:102-106, 1962. D. H. Lehmer, E. Lehmer, and W. Mills.
    Pairs of consecutive power residues.
    Canadian Journal of Mathematics, 15:172-177, 1963. This paper gives an LL proof that ${\rm con}_5(2) = 281$ and ${\rm con}_6(2) = 499$. LLM.PDF

  9. J. Brillhart, D. H. Lehmer, and E. Lehmer.
    Bounds for pairs of consecutive seventh and higher powers.
    Mathematics of Computation, 18:397-407, 1964. This paper shows that if there is an LL proof for ${\rm con}_7(2)$, ( ${\rm con}_8(2)$, ${\rm con}_9(2)$, ${\rm con}_{10}(2)$) then the numbers involved will be quite large (see the paper itself to make this formal). BLL.PDF.

  10. R. Graham.
    On quadruples of consecutive kth power residues.
    Proceedings of the American Mathematical Society, 15:196-197, 1964. 1964. This paper show that, for all $k$, there is NO LL proof for ${\rm con}_k(4)$. GRAHAM.PDF.

  11. M. Dunton.
    Bounds for pairs of cubic residues.
    Proceedings of the American Mathematical Society, 16:330-332, 1965. DUNTON.PDF. This paper gives an elementary proof that ${\rm con}_3(2)=13$.

  12. J. R. Rabung and J. H. Jordan.
    Consecutive power residues or nonresidues.
    Mathematics of Computation, 24:737-740, 1970.
    http://www.jstor.org/stable/2004850 or http://www.cs.umd.edu/~gasarch/res/. 1970. This paper looks at the problem of finding a sequence of $n$th powers OR non-$n$th powers. BJ.PDF.

  13. J. R. Rabung.
    On applications of van der Waerden's theorem.
    Mathematical Magazine, 48:142-148, 1975. APPVDW.PDF. This paper looks at these kind of problems within the Gaussian Integers.

  14. R. Peralta.
    On the distribution of quadratic residues and nonresidues modulo a prime number.
    Mathematics of Computation, 58:433-440, 1992. 1992. This paper shows that ${\rm con}_2(k) \le O(k2^k)$. It is not stated that way. PER.PDF.

Papers about FLT

  1. G. Libri.
    Memoire sur la theörie des nombres.
    Journal für die reine und angewandte Mathematik, pages 54-81, 1832. LIBRI.PDF.

  2. P. Pepin.
    Etude sur la theórie des residues cubiques.
    Journal de Mathématiques Pures et Appliquées, 2:313-324, 1876. PEPINCUB.PDF.

  3. P. Pepin.
    Sur divers tentatives de demonstration du theóreme de Fermat.
    Comptes Rendus de l'Académie des Sciences Paris, PEPINFERMAT.PDF.

  4. A. E. Pellet.
    Memorire sur la theórie algebrique des equations.
    Bulletin de la societe Mathematique de France, pages 61-103, 1887. PELLET.PDF.

  5. L. E. Dickson.
    Lower limit for the number of sets of solutions of $x^n+y^n+z^n\equiv 0 \pmod p$.
    Journal für die reine und angewandte Mathematik, pages 181-189, 1909. DICKSONLOWER.PDF.

  6. G. Cornacchia.
    Sulla congruenza $x^n+y^n+z^n\equiv 0 \pmod p$.
    Giornale di matematiche di Battaglini, pages 219-268, 1909. CORNACHIA.HTML

  7. A. Hurwitz.
    Uber die kongruenz $ax^e+by^e+cz^e\equiv 0 \pmod p$.
    Journal für die reine und angewandte Mathematik, pages 272-292, 1909. HURWITZ.PDf




next up previous
Next: About this document ...
William Gasarch 2011-05-06