<p>[Certainly not a complete answer, but too long for a comment]</p>

<p>Testing whether a given DFA accepts the base-2 representation of at least one prime number is <a href="https://cstheory.stackexchange.com/a/22503/129">not known to be computable</a>. If it were uncomputable, that's some kind of weak evidence that there's no "regular-ish" formula for primality. (I mean, we know the set of primes itself is not regular, but here it's about whether there's a formula that's sufficiently simple that you could use it to help decide whether a given DFA accepts any primes.)</p>

<p>In another direction, given that your conjecture is about the difference between cubic and quadratic, it might be reasonable to think about whether the problem is complete for cubic time under sub-cubic reductions (see Vassilevska Williams &amp; Williams). It looks tricky, or even unlikely, since it's so different from the other "cubic-complete" problems, like all-pairs shortest paths, triangle detection, etc., but could be worth considering nonetheless. Their framework was in the context of deterministic algorithms, but it shouldn't be too hard to adapt to randomized...</p>

CC BY-SA 4.0
2020-05-23T20:15:03.840Z
The notion of comparing to other quadratic vs. cubic algorithms is interesting, but unfortunately I think it would miss the part about primes.  E.g., one can define an oracle version of the problem where sample-and-check is optimal and has any desired complexity.  The conjecture is an attempt at saying that’s the right model without mentioning oracles.
Geoffrey Irving
CC BY-SA 4.0
2020-05-23T20:20:25.357Z
To clarify, it seems unlikely that this would relate to quadratic/cubic complete problems, since intuitively it’d only be as strong as adding a random oracle, and that does solve those complete problems.
Geoffrey Irving
CC BY-SA 4.0
2020-05-23T20:27:31.953Z
(Ug: “does solve” should be “doesn’t solve” above)
Geoffrey Irving
CC BY-SA 4.0
2020-05-23T23:49:19.683Z
@GeoffreyIrving: "one can define an oracle version of the problem where sample-and-check is optimal and has any desired complexity" I'm not sure I follow. Is there somewhere I can read about this to clarify? Most of the stuff about subcubic reductions does not relativize as far as I know, because it's about very particular runtimes for very specific (non-relativized) problems.
Joshua Grochow
CC BY-SA 4.0
2020-05-24T06:38:01.267Z
E.g., have an random oracle where $1/\log n$ of $n$-bit inputs map to 1, and consider the function problem of finding an input that maps to 1.
Geoffrey Irving
CC BY-SA 4.0
2020-05-24T07:13:47.493Z
@GeoffreyIrving: Ah. I see that that's a generalized version of generating primes, but it also seems quite far removed from actual prime numbers themselves (except density-wise). My point was to try to give a subcubic reduction from e.g. APSP to generating primes. Perhaps I shouldn't have said "complete for cubic time" (which indeed would relativize), but rather APSP-hard under sub-cubic reductions - would that clear up your objection, or am I missing something?
Joshua Grochow
CC BY-SA 4.0
2020-05-24T07:37:47.753Z
Yep, that would be helpful if it worked, I just have no idea how to do it. :)
Geoffrey Irving
CC BY-SA 4.0
2020-05-24T09:30:46.267Z
"a given DFA accepts the base-2 representation of any prime number", before I followed the source, this sounded like the unbelievable statement of the DFA accepting *every* prime number. Perhaps "at least one prime number" makes it clearer?
ComFreek
CC BY-SA 4.0
2020-05-23T19:39:20.947Z
2020-05-25T12:00:23.000Z
2020-05-25T12:00:23.000Z
Joshua Grochow
<p>I was trying to formalize the intuition is that there is no formula for primes, and this is my best attempt:</p>

<p><strong>Conjecture:</strong> There is no <span class="math-container">$O(n^2)$</span> expected time randomized algorithm to generate <span class="math-container">$\ge n$</span>-bit primes.</p>

<p>Currently I believe the best algorithm has conjectured complexity <span class="math-container">$\tilde{O}(n^3)$</span>: run the <span class="math-container">$\tilde{O}(n^2)$</span> Lucas-Lehmer test on <span class="math-container">$O(n)$</span> Mersenne numbers.  We could go from <span class="math-container">$n^3$</span> to <span class="math-container">$n^2$</span> using the same sample-and-check strategy if a faster <span class="math-container">$\tilde{O}(n)$</span> checking algorithm is found.  (This argument for the choice of 2 as exponent due to Paul Christiano.)</p>

<p>However, if a "formula for primes" existed, and was sufficiently simple, the fact that arithmetic is quasilinear means that we might get a quasilinear time prime generation algorithm, or <span class="math-container">$\tilde{O}(n)$</span>.  Conjecturing that the minimum exponent is 2 roughly approximates "the best strategy is sample-and-check".</p>

<p><strong>Two questions:</strong></p>

<ol>
<li>Is there any heuristic evidence beyond the algorithms discovered so far about the optimum primality testing exponent, or the optimal exponent for generating primes?</li>
<li>Are there other attempts at formalizing the "no formula for primes" intuition?</li>
</ol>

<p>I should clarify that of course I know that settling the conjecture is hopeless: I’m looking for heuristics only. </p>

<nt.number-theory><primes>
Formalizing the "no formula for primes" intuition
Geoffrey Irving
# Formalizing the "no formula for primes" intuition

(Asked by: username_0 on 2020-05-23)

I was trying to formalize the intuition is that there is no formula for primes, and this is my best attempt:

**Conjecture:** There is no $O(n^2)$ expected time randomized algorithm to generate $\ge n$-bit primes.

Currently I believe the best algorithm has conjectured complexity $\tilde{O}(n^3)$: run the $\tilde{O}(n^2)$ Lucas-Lehmer test on $O(n)$ Mersenne numbers. We could go from $n^3$ to $n^2$ using the same sample-and-check strategy if a faster $\tilde{O}(n)$ checking algorithm is found. (This argument for the choice of 2 as exponent due to Paul Christiano.)

However, if a "formula for primes" existed, and was sufficiently simple, the fact that arithmetic is quasilinear means that we might get a quasilinear time prime generation algorithm, or $\tilde{O}(n)$. Conjecturing that the minimum exponent is 2 roughly approximates "the best strategy is sample-and-check".

**Two questions:**

1. Is there any heuristic evidence beyond the algorithms discovered so far about the optimum primality testing exponent, or the optimal exponent for generating primes?
2. Are there other attempts at formalizing the "no formula for primes" intuition?

I should clarify that of course I know that settling the conjecture is hopeless: I’m looking for heuristics only.

**Tags:** nt.number-theory, primes


---

## 1 answers

### Answer by username_1 on 2020-05-23. Score: 7

[Certainly not a complete answer, but too long for a comment]

Testing whether a given DFA accepts the base-2 representation of at least one prime number is [not known to be computable](https://cstheory.stackexchange.com/a/22503/129). If it were uncomputable, that's some kind of weak evidence that there's no "regular-ish" formula for primality. (I mean, we know the set of primes itself is not regular, but here it's about whether there's a formula that's sufficiently simple that you could use it to help decide whether a given DFA accepts any primes.)

In another direction, given that your conjecture is about the difference between cubic and quadratic, it might be reasonable to think about whether the problem is complete for cubic time under sub-cubic reductions (see Vassilevska Williams & Williams). It looks tricky, or even unlikely, since it's so different from the other "cubic-complete" problems, like all-pairs shortest paths, triangle detection, etc., but could be worth considering nonetheless. Their framework was in the context of deterministic algorithms, but it shouldn't be too hard to adapt to randomized...

> **Comments:**
> **username_0**: The notion of comparing to other quadratic vs. cubic algorithms is interesting, but unfortunately I think it would miss the part about primes.  E.g., one can define an oracle version of the problem where sample-and-check is optimal and has any desired complexity.  The conjecture is an attempt at saying that’s the right model without mentioning oracles.  
> **username_0**: To clarify, it seems unlikely that this would relate to quadratic/cubic complete problems, since intuitively it’d only be as strong as adding a random oracle, and that does solve those complete problems.  
> **username_0**: (Ug: “does solve” should be “doesn’t solve” above)  
> **username_1**: @GeoffreyIrving: "one can define an oracle version of the problem where sample-and-check is optimal and has any desired complexity" I'm not sure I follow. Is there somewhere I can read about this to clarify? Most of the stuff about subcubic reductions does not relativize as far as I know, because it's about very particular runtimes for very specific (non-relativized) problems.  
> **username_0**: E.g., have an random oracle where $1/\log n$ of $n$-bit inputs map to 1, and consider the function problem of finding an input that maps to 1.  
> **username_1**: @GeoffreyIrving: Ah. I see that that's a generalized version of generating primes, but it also seems quite far removed from actual prime numbers themselves (except density-wise). My point was to try to give a subcubic reduction from e.g. APSP to generating primes. Perhaps I shouldn't have said "complete for cubic time" (which indeed would relativize), but rather APSP-hard under sub-cubic reductions - would that clear up your objection, or am I missing something?  
> **username_0**: Yep, that would be helpful if it worked, I just have no idea how to do it. :)  
> **username_2**: "a given DFA accepts the base-2 representation of any prime number", before I followed the source, this sounded like the unbelievable statement of the DFA accepting *every* prime number. Perhaps "at least one prime number" makes it clearer?  

---

