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

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

Proof: Define XnX_n to be a sequence of integers where xnXnmod Bx_n \equiv X_n \operatorname{mod} \text{ } B for some integer B. Define the nth state=Sn=S_n of a recurrence relation xn=f(xn1,xn2,xn3,...,xnk)x_n = f(x_{n-1}, x_{n-2}, x_{n-3},...,x_{n-k}) to be the set of numbers (Xnk,Xnk+1,...,Xn) (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:

Sn=(Xnk,Xnk+1,...,Xn)Sn+1=(Xnk+1,Xnk+2,...,Xn+1) 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 SnS_n, 1 iteration of the mod-conserved recurrence relation can only lead to state Sn+1S_{n+1}, which is unique

Proof: Since for a mod-conserved recurrence formula, Xn=f(Xn1,Xn2,Xn3,...,Xnk)mod B 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 Xn+1X_{n+1}, which can't be true. Hence proved by contradiction.

Lemma 1.2: There are a finite number of states.

Proof: Since xnXnmod Bx_n \equiv X_n \operatorname{mod} \text{ } B, 1XnB1 \le X_n \le B. Hence, there is a maximum of Bk+1B^{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 SnS_n must equal to another state SkS_k where kjk \neq j through pigeon-hole principle. Since via lemma 1.1, state SnS_n must progress to only state Sn+1S_{n+1}, we conclude that XnX_n repeats: xnx_n eventually repeats mod B\operatorname{mod} \text{ } B. Hence proved.

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

Lemma 2: SnS_n eventually returns back to the first state if xnx_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

Xn=f(Xn1,Xn2,Xn3,...,Xnk)=f(Xn1,Xn2,Xn3,...,A)mod BX_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 AXnkmod BA \neq X_{n-k} \operatorname{mod} \text{ } B.

Since for a linear recurrence relation,

f(Xn1,Xn2,Xn3,...,Xnk)=j=1kAjXnj\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

Xn=f(Xn1,Xn2,Xn3,...,Xnk)=f(Xn1,Xn2,Xn3,...,A)mod BX_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

Xnk=1Ak(Xnj=1k1AjXnj)=Amod 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 AA doesn't exist as Xnk=Amod BX_{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 xn=pnx_n = p_n. Then via lemma 2, pnp_n must repeat mod B\operatorname{mod} \text{ } B for all BB and go back to it's starting position. By having B=2B=2, all primes apart from 22 are odd. Hence pnp_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 xn=pnx_n=p_n. Then via lemma 1 we have that pnp_n repeats mod B\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 pnp_n repeats, we have 2 cases.

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

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

Function ff, 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 ff 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.

Note by Julian Poon
3 years, 11 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link]( link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


There are no comments in this discussion.


Problem Loading...

Note Loading...

Set Loading...