Simple Functions in Generating Primes

Probability Level 4

Let $p_n$ be the $n$ -th prime

Are there any polynomial functions $F(x_1, x_2, \ldots, x_k)$ in $k$ variables such that

$F(p_{n-1}, p_{n-2}, p_{n-3}, ... , p_{n-k}) = p_n \, \forall n >k?$

Maybe Yes No

1 solution

Julian Poon
Aug 21, 2017

I posted a note which is pretty much the solution here for 2 reasons:

From previous experiences, a note does not get enough attention to garner many responses. Given the length of the proof, there is bound to be some error in the proof and if so, why not have it found faster?
This result is so kwelllll

If I am reading your argument correctly, you are saying:

for any function (please remove the word algorithm, which is misleading, as we have discussed - it led me to pick "maybe") of the desired type, the sequence of values modulo $B$ must be eventually periodic for any $B \in \mathbb{N}$ .
there are arbitrarily long sequences of consecutive primes in arithmetic progression.
this is not possible.

I have removed your discussion of fully periodic sequences, and linear recurrence relations, which won't fit the bill - if a linear recurrence relation did the business, we could solve it to obtain an explicit formula for $p_n$ as an explicit linear combination of $k$ exponential terms. Let's stick with "eventually" periodic sequences.

I am not convinced as to how the two parts of your argument fit together. Arithmetic progressions of numbers will have a much shorter period modulo $B$ (consider the odd integers modulo $2$ ), and so arbitrarily long arithmetic progressions could fit within shorter periodic sequences of states. Add to this the fact that we can only say the state sequences are eventually periodic, and we never know whether a failure to be periodic is because we haven't reached the "eventually" part of the state sequence or not, and where are we?

Mark Hennings - 3 years, 9 months ago

In addition, it is possible that $t(n) \equiv t(n + k ) \equiv t(n+2k) \ldots \pmod{N}$ , even though $t(n), t(n+k) , \ldots$ do not form an arithmetic progression.

The machinery that I'm thinking of to show that the primes are not eventually periodic is high power, involving representation theory and characters, tying into the start of Riemann Hypothesis. Essentially, if a sequence is eventually periodic, then it can be presented as a finite sum (for the initial part) + linear combination of characters (for the periodic part). This means that the sequence has to be pretty well behaved, which we "know" that the primes are not.

Calvin Lin Staff - 3 years, 9 months ago

Updating this comment, it seems that Lucia's entry here shows that the primes are not eventually periodic, using some pretty high-powered Analytic Number Theory.

The problem with the question remains that the answer is "yes" if we allow algorithms, and "no" if we insist on functions (as I think Julian intends).

Mark Hennings - 3 years, 9 months ago

@Mark Hennings – Lucia's entry is what I am thinking about (and similar to the proof that I first saw about primes not being eventually periodic mod p). It does use a ton of machinery in representation theory though, and I haven't seen an elementary number theory approach.

@Julian Poon We can clarify the functions to be "polynomial functions in the $k$ variables $x_i$ , such that $F(p_{n-1} , \ldots ) = p_n$ ". That greatly simplifies what " $(+ , - , \times )$ is, and doesn't require the examples/non-examples".

Calvin Lin Staff - 3 years, 9 months ago

Simple Functions in Generating Primes

1 solution

0 pending reports