Proof that there are no simple algorithms for generating primes

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 $x_n$ such that $x_n = p_n$ where $p_n$ is the nth prime. In other words, there are no recurrence relations of the form $x_n = \sum_{k=1}^N A_k x_{n-k}$ For some constants $A_k$ such that $x_n = p_n$. 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 $x_n$ such that $x_n=p_n$. In other words, there are no recurrence relations of the form $x_n = f(x_{n-1}, x_{n-2}, x_{n-3},...,x_{n-k})$ where $f$ uses only the operators $(+, -, ×)$ such that $x_n = p_n$. From now on, such reccurence relations will be called mod-conserved recurrence relations. Such functions $f$ will also be called simple algorithms.

In this note, $x_n$ will be a sequence of integers defined by a recurrence relation, while $p_n$ 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: $x_n$, defined by any mod-conserved recurrence relation, repeats $\operatorname{mod} \text{ } B$ for some integer $B$. By repeat, it means that $x_n \equiv x_{n+j} \operatorname{mod} \text{ } B$ for some $j$ and $B$.

Proof: Define $X_n$ to be a sequence of integers where $x_n \equiv X_n \operatorname{mod} \text{ } B$ for some integer B. Define the nth state$=S_n$ of a recurrence relation $x_n = f(x_{n-1}, x_{n-2}, x_{n-3},...,x_{n-k})$ to be the set of numbers $(X_{n-k}, X_{n-k+1}, ... ,X_{n})$. After 1 iteration of the recurrence formula, the nth state would progress into the (n+1)th state:

$S_n = (X_{n-k}, X_{n-k+1}, ... ,X_{n}) \rightarrow S_{n+1} = (X_{n-k+1}, X_{n-k+2}, ... ,X_{n+1})$

Lemma 1.1: Given state $S_n$, 1 iteration of the mod-conserved recurrence relation can only lead to state $S_{n+1}$, which is unique

Proof: Since for a mod-conserved recurrence formula, $X_n = f(X_{n-1}, X_{n-2}, X_{n-3},...,X_{n-k}) \operatorname{mod} \text{ } B$. Hence if lemma 1.1 isn't true, there would be more than 1 value for $X_{n+1}$, which can't be true. Hence proved by contradiction.

Lemma 1.2: There are a finite number of states.

Proof: Since $x_n \equiv X_n \operatorname{mod} \text{ } B$, $1 \le X_n \le B$. Hence, there is a maximum of $B^{k+1}$ 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 $S_n$ must equal to another state $S_k$ where $k \neq j$ through pigeon-hole principle. Since via lemma 1.1, state $S_n$ must progress to only state $S_{n+1}$, we conclude that $X_n$ repeats: $x_n$ eventually repeats $\operatorname{mod} \text{ } B$. Hence proved.

Upon proving Lemma 1, we are to consider 2 cases: Case 1: $S_n$ returns back to its first state Case 2: $S_n$ returns back to some other state that is not its first state.

Lemma 2: $S_n$ eventually returns back to the first state if $x_n$ 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

$X_n = f(X_{n-1}, X_{n-2}, X_{n-3},...,X_{n-k}) = f(X_{n-1}, X_{n-2}, X_{n-3},...,A) \operatorname{mod} \text{ } B$

where $A \neq X_{n-k} \operatorname{mod} \text{ } B$.

Since for a linear recurrence relation,

$\displaystyle f(X_{n-1}, X_{n-2}, X_{n-3},...,X_{n-k}) = \sum_{j=1}^k A_j X_{n-j}$

we get that

$X_n = f(X_{n-1}, X_{n-2}, X_{n-3},...,X_{n-k}) = f(X_{n-1}, X_{n-2}, X_{n-3},...,A) \operatorname{mod} \text{ } B$

$X_{n-k} = \frac{1}{A_k} \left( X_n - \sum_{j=1}^{k-1} A_j X_{n-j} \right) = A \operatorname{mod} \text{ } B$

Therefore $A$ doesn't exist as $X_{n-k} = A \operatorname{mod} \text{ } B$ 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 $x_n = p_n$. Then via lemma 2, $p_n$ must repeat $\operatorname{mod} \text{ } B$ for all $B$ and go back to it's starting position. By having $B=2$, all primes apart from $2$ are odd. Hence $p_n$ 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 $x_n=p_n$. Then via lemma 1 we have that $p_n$ repeats $\operatorname{mod} \text{ } B$, 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 $p_n$ repeats, we have 2 cases.

1. The cycle of which $p_n$ repeats does not contain these arithmetic sequences. This is impossible as these sequences are arbitrarily long so the cycle must start when $p_n$ is arbitrarily large. i.e. the cycle happens so late that it doesn't happen.

2. The cycle of which $p_n$ 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: $p_n$ doesn't repeat. This is in direct contradiction to lemma 1, and hence such a mod-conserved recurrence doesn't exist.

Function $f$, 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 $f$ 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.