Consider the sequence of prime numbers: $2,3,5,7, \cdots$. Now reduce this sequence modulo $k$ for some integer $k > 2$. Show the resulting sequence is not periodic. :

EDIT: As noted in the comments, what I really mean is that the sequence is not pre-periodic; i.e. it is not periodic with some prefix attached. So Jeff Strom's argument doesn't work; and I said that $k>2$ which rules out that case.

Dirichlet's theorem on primes would imply that if it was periodic, then the period would contain each admissible residue class (mod $k$) with equal frequency. For $k=4$, I think there's some result that the quantity $\pi_{1,4}(n) - \pi_{3,4}(n)$ alternates between positive and negative values infinitely often. (Here $\pi_{i,j}(n)$ counts the number of primes less than $n$, congruent to $i$ (mod $j$).) This result settles the question for $k=4$; and perhaps there are generalizations of this to $k>4$. But maybe there's an easier, more elementary approach.

Re Comments: Lucia, thanks for your answers! Your second proof seems elementary (and the result in the first proof is very interesting); but you can include more details? Why does periodicity imply that $\text{log} L(s, \chi)$ is analytic; and why does the corresponding $L$-function have no non-trivial zeros?

  • 9
    $\begingroup$ This seems like a perfectly fine question to me. Why the down & close vote? $\endgroup$ – Lucia May 28 '14 at 0:27
  • 15
    $\begingroup$ Here are two proofs but neither is very elementary. First, Daniel Shiu has shown that there are arbitrarily long strings of consecutive primes congruent to any given $a \pmod q$. Second, if the primes were periodic $\pmod q$, then pick a non-trivial complex character $\pmod q$ and the criterion implies that $\log L(s,\chi)$ is analytic in Re$(s)>1/3$ say, and hence the corresponding $L$-function cannot have any non-trivial zeros. (You can also argue with the quadratic $L$-function, but then the prime squares have to be kept in mind.) Probably I'm missing the obvious elementary proof! $\endgroup$ – Lucia May 28 '14 at 0:42
  • 14
    $\begingroup$ The question should ask whether the sequence is preperiodic rather than periodic. $\endgroup$ – Douglas Zare May 28 '14 at 3:16
  • 2
    $\begingroup$ Related (in view of Lucia's comments): mathoverflow.net/questions/13647/… $\endgroup$ – Terry Tao May 28 '14 at 15:35
  • 2
    $\begingroup$ In particular, Lucia's answer there looks adaptable: Show that it is impossible for both $\sum_{n \leq N} \chi(n)$ and $\sum_{p \leq N} \chi(p) \log p$ to be $O(N^{1/2-\delta})$, for some Dirichlet character $\chi$. $\endgroup$ – David E Speyer May 28 '14 at 17:12

Here is an elaboration of my comment to the question. Suppose that the primes are (pre)-periodic $\pmod k$ (with $k>2$). Let $\chi$ be a non-trivial character $\pmod k$. Then the assumption on the primes implies that $$ S(x,\chi) = \sum_{p\le x} \chi(p), $$ is bounded.

Now consider $$ \log L(s,\chi) = \sum_{j=1}^{\infty} \frac{1}{j} \sum_{p} \frac{\chi(p)^j}{p^{js}}. $$ A priori this is well defined and analytic in Re$(s)>1$. The terms with $j\ge 2$ are analytic in Re$(s)>1/2$. The assumption on the periodicity of the primes gives that $$ \sum_{p} \frac{\chi(p)}{p^s} = \int_{1}^{\infty} S(x,\chi) \frac{s}{x^{s+1}} dx, $$ is analytic in Re$(s)>0$. Thus we conclude that $\log L(s,\chi)$ is analytic in Re$(s)>1/2$ (this is the Riemann Hypothesis, but of course a false assumption implies many things!).

Now suppose that $\chi$ is a non-trivial quadratic character. Then from above we see that for Re$(s)>1/2$ we have $$ \log L(s,\chi) = O(1)+ \frac{1}{2} \sum_{p} \frac{\chi(p)^2}{p^{2s}} = O(1) + \frac{1}{2} \sum_{p} \frac{1}{p^{2s}}, $$ since $\chi$ is quadratic. If we let $s$ take real values tending to $1/2$ from above, this gives a contradiction (as $L(1/2,\chi)$ is bounded, whereas exponentiating the above would imply that it goes to infinity).

Alternatively take $\chi$ to be a complex character (this works for $k\neq 3, 4, 6, 8$) and then the prime square terms above are also bounded (for Re$(s)>0$) and we conclude that $\log L(s,\chi)$ is analytic in Re$(s)>1/3$. Hence the $L$-function is non-zero in that region, and by the functional equation (say $\chi$ is primitive) we conclude that the $L$-function can only have trivial zeros. This is a contradiction.

Thirdly, as noted before Daniel Shiu's result on Strings of Congruent primes (JLMS 2000) also gives the result (although this is harder than the proof above). Nowadays the Maynard(-Tao) machinery gives relatively easy access to such results (and in a stronger form).

Finally, as Terry Tao observes in the comments, Gowers's question on why the Riemann zeta function has zeros is certainly relevant here, and see also my answer to that question. In that spirit, one may say that the primes are not periodic $\pmod k$, because the integers are!

  • $\begingroup$ Dear Lucia, isn't there a $\chi(p)^j$ missing on the RHS of the second displayed math, and a $\chi(p)$ missing in the LHS of the third? $\endgroup$ – Joël May 28 '14 at 20:07
  • $\begingroup$ @Joël: Dear Joel, Thanks! I've fixed that now. $\endgroup$ – Lucia May 28 '14 at 20:15

Suppose the primes are periodic mod $k$, and let $p$ be a prime divisor of $k$. Then there must be infinitely many primes of the form $p + nk$, which is divisible by $p$. Bad news.


More precision: we define $q: \mathbb{Z}\to \mathbb{Z}/k$ to be the canonical quotient and $f: \mathbb{N}\to \mathbb{Z}$ by $f(n) = p_n$, the $n^\mathrm{th}$ prime. Suppose that $g= q\circ f: \mathbb{N}\to \mathbb{Z}/k$ is periodic, with period $t$ and $k> 1$. Let's say $p_m = f(m)$ divides $k$. Then $$ p_{m+t} = f(m+t) \equiv f(m) = p_m\qquad \mathrm{mod}\ k $$ which means $p_{m+t} = p_m + nk$ for some $n$, and this forces $p_m$ to divide $p_{m+t}$, which is impossible. So $g$ cannot be periodic.

This leaves the question: can the primes be eventually periodic?

And of course the dumb answer is yes: mod $2$, the primes are eventually $1,1,1,1,\ldots$.

  • $\begingroup$ All that shows is that $p$ is NOT a prime divisor mod $k$... $\endgroup$ – Igor Rivin May 28 '14 at 2:28
  • 3
    $\begingroup$ Try this then: let p be a prime divisor of k. Then p mod k is 0 or p. No other prime has that residue mod k. $\endgroup$ – The Masked Avenger May 28 '14 at 3:04
  • $\begingroup$ Here is another. By Bertrand and Finsler there are ( for k large) at least two primes between k and 2k. But then they have to be k+2 and k+3. $\endgroup$ – The Masked Avenger May 28 '14 at 3:24
  • 1
    $\begingroup$ Showing eventual nonperiodicity mod k for large k is harder, but one might look at prime free regions (near nk! perhaps) and possibly reach a contradiction. $\endgroup$ – The Masked Avenger May 28 '14 at 3:28
  • 2
    $\begingroup$ This answer correctly solves the question as initially posted, so I don't understand the down votes. $\endgroup$ – Joël May 28 '14 at 20:01

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.