I and my friends Ahn and Jackson were talking about this problem Rubik's Cube Proof. Apparently, we had both thought of the problem and solved it independently, and were discussing what other problems can the proof in that problem be used in. Eventually, we drifted into properties of prime numbers and hence the creation of this note. The proofs presented in this note will be very similar to that of the Rubik's Cube Proof, so it might be useful to read that first.
In this note, we will be proving 2 statements, the second a generalisation of the first. Thereafter, we'll move on to proving the title.
The first: There are no linear recurrence that define a sequence of integers such that where is the nth prime. In other words, there are no recurrence relations of the form For some constants such that . Loosely speaking, you can't generate all and only the prime numbers through a linear recurrence relation.
Second (real deal): There are no recurrence relations that uses only the operators (+, -, ×) that define a sequence of integers such that . In other words, there are no recurrence relations of the form where uses only the operators such that . From now on, such reccurence relations will be called mod-conserved recurrence relations. Such functions will also be called simple algorithms.
In this note, will be a sequence of integers defined by a recurrence relation, while will be the sequence of primes
The second is an obvious generalisation of the first, however, it is much harder, and I've only been able to think of a solution that is "overkill", involving the Green-Tao Theorem.
To proof these statements, it would be helpful to first establish 2 lemmas on recurrence relations:
Lemma 1: , defined by any mod-conserved recurrence relation, repeats for some integer . By repeat, it means that for some and .
Proof: Define to be a sequence of integers where for some integer B. Define the nth state of a recurrence relation to be the set of numbers . After 1 iteration of the recurrence formula, the nth state would progress into the (n+1)th state:
Lemma 1.1: Given state , 1 iteration of the mod-conserved recurrence relation can only lead to state , which is unique
Proof: Since for a mod-conserved recurrence formula, . Hence if lemma 1.1 isn't true, there would be more than 1 value for , which can't be true. Hence proved by contradiction.
Lemma 1.2: There are a finite number of states.
Proof: Since , . Hence, there is a maximum of different states which is finite. Hence proved
Given lemma 1.1 and 1.2, we can now proof lemma 1.
Since via lemma 1.2 (there are a finite number of states), a state must equal to another state where through pigeon-hole principle. Since via lemma 1.1, state must progress to only state , we conclude that repeats: eventually repeats . Hence proved.
Upon proving Lemma 1, we are to consider 2 cases: returns back to its first state Case 2: returns back to some other state that is not its first state.Case 1:
Lemma 2: eventually returns back to the first state if is defined by a linear recurrence relation.
To proof lemma 2, we essentially have to eliminate case 2.
If you look picture, you'll see that case 2 loops back to state n. This means that 2 arrows are pointing to state n (2 different states lead to state n). The only way for this to be the case is if
Since for a linear recurrence relation,
we get that
Therefore doesn't exist as and we conclude that case 2 is impossible via contradiction. Hence proved.
With the 2 lemmas proved, we can now move onto proving the actual statements.
Proof of the first statement:
Assume that there are linear recurrence relations such that . Then via lemma 2, must repeat for all and go back to it's starting position. By having , all primes apart from are odd. Hence doesn't return back to its starting position, which contradicts lemma 2. Hence proved that there are no such linear recurrence relations.
Proof of the second statement:
Lemma 2 doesn't apply to mod-conserved recurrence. So we can't use lemma 2. We can, however, use lemma 1. Assume there exists mod-conserved recurrence relations such that . Then via lemma 1 we have that repeats , but not necessarily return back to its starting position. Via the Green-Tao theorem, there exists arbitrarily long sequences of primes in arithmetic progression. If repeats, we have 2 cases.
The cycle of which repeats does not contain these arithmetic sequences. This is impossible as these sequences are arbitrarily long so the cycle must start when is arbitrarily large. i.e. the cycle happens so late that it doesn't happen.
The cycle of which repeats contains these arithmetic sequences. This is also impossible as these sequences are arbitrarily long so the cycle will be arbitrarily long. i.e. the cycle is so large there is no cycle
Hence, such a cycle doesn't exist: doesn't repeat. This is in direct contradiction to lemma 1, and hence such a mod-conserved recurrence doesn't exist.
Function , a mod-conserved recurrence can be seen as a "simple" algorithm for generating the next prime using the values of the primes preceding it as it only uses the simple operators (+, -, ×) (hence the name: simple algorithm). Since such doesn't exist, we can conclude that there are no simple algorithms for generating primes.
This is a pretty sad result tbh, that we need more complex math than (+, -, ×) to generate the primes. Also, I'm not very happy that this solution requires Green-Tao. If you find any mistakes/more elementary methods please feel free to post them in the comments.