12
$\begingroup$

Is there a function $f : \mathbb N \rightarrow \mathbb P$, where $\mathbb P = \{p \in \mathbb N \mid \ p$ is prime$\}$, such that $f$ is injective? It is known that no such polynomial function exists. Also, I wish to exclude functions defined as $f(n) = \text{the $n$th prime}$, which requires one to find primes in advance.

$\endgroup$
  • 30
    $\begingroup$ $f(n)=p_n$ seems to be an extremely explicit definition of the function. How much more explicit do you want? $\endgroup$ – Henning Makholm Feb 22 '15 at 17:50
  • 7
    $\begingroup$ @Jobin: You say your function need not generate only primes, yet your question states $f:\Bbb N\to\Bbb P$? $\endgroup$ – Regret Feb 22 '15 at 17:57
  • 2
    $\begingroup$ Oh, you're right. And I just realized the blunder in that statement. If that function need not generate only primes, then something as simple as $f(n) = n$ would do. So I apologize and take that back. I'm back to looking for an injective function that generates only primes. $\endgroup$ – Train Heartnet Feb 22 '15 at 18:01
  • 2
    $\begingroup$ @HenningMakholm: I realize it's as explicit as it gets, but I was hoping for a function that doesn't require me to know any primes in advance. $\endgroup$ – Train Heartnet Feb 22 '15 at 18:03
  • 4
    $\begingroup$ The title is misleading. I was tempted to answer. "Sure. Associate to each n the n-th prime number" $\endgroup$ – Luis Mendo Feb 23 '15 at 15:48
33
$\begingroup$

Have you heard of Mills' constant? The function defined below, with $A$ being Mills' constant, always gives a prime:

$$f(n)=\left\lfloor A^{3^n}\right\rfloor$$

$\endgroup$
  • 4
    $\begingroup$ Oh, I hadn't heard of this function before! And it is injective too. Upon reading the Wikipedia article though, the calculation of the value of $A$ seems to require finding primes in advance. $\endgroup$ – Train Heartnet Feb 22 '15 at 18:08
  • $\begingroup$ @Jobin: I imagine this function to not be of much practical use for now, but it is nonetheless an example of a prime-representing function. Also, this page may be of interest to you. $\endgroup$ – Regret Feb 22 '15 at 18:15
  • $\begingroup$ It's probably never of any practical use, given that the existence of an $A$ is equivalent to saying that there is a sequence $s_n$ of primes such that $s_n^3 \leq s_{n+1} < (s_n+1)^3$. (But nevertheless, this is one of my favorite facts about number theory) $\endgroup$ – Milo Brandt Feb 22 '15 at 18:20
  • $\begingroup$ @JobinIdiculla Advance calculation of primes is not necessary if RH is true. $\endgroup$ – Elliot Gorokhovsky Feb 23 '15 at 16:42
13
$\begingroup$

Coming from theoretical computer science, I'd formalize your question as

Is there a bijection $f: \mathbb{N} \to P$ so that $f(n)$ can be computed in time polynomial in $\lceil \log_2 n\rceil$ (the number of bits of $n$)?

This is a standard way to formulate such "explicit indexing" questions. The requirement that $f$ be efficiently computable is a strong version of requiring that $f$ is "explicit". It also excludes things like computing all the primes up to $n$.

The question stated above is certainly open! The closest result I know to it is a recent paper that shows how to explicitly index irreducible polynomials of a given degree in a finite field. Such polynomials are the "primes" in the ring of polynomials but have much more structure than the primes in the ring of integers.

$\endgroup$
  • 2
    $\begingroup$ Interesting! But seems the most natural interpretation of the OP is asking whether there is a polynomial-time injection, not a polynomial time bijection. Do you known anything about whether a polynomial time injection exists? $\endgroup$ – 6005 Feb 23 '15 at 10:37
  • $\begingroup$ @C-S you are right, the question does say injection. I was misled by the title which says "one to one". I am pretty sure the question is open for injections too, unless we somehow considerably weaken the requirement to allow for some randomness. $\endgroup$ – Sasho Nikolov Feb 23 '15 at 15:54
  • $\begingroup$ @SashoNikolov well, if we had an injective function that was log computable on the bits of n, then given a prime p, we know that somewhere between f(0) and f(p) must lie p (we can probably get a much smaller range, but this seems sufficient for proofs sake). Then we can binary search between these two function points. $\endgroup$ – Cruncher Feb 23 '15 at 16:41
  • 1
    $\begingroup$ @Cruncher I don't understand your comment. What is the point you are making? I see no reason that $p$ must be between $f(1)$ ($0 \not \in \mathbb{N}$) and $f(p)$. For example it's totally possible that $f(1) = 3$ and $f(2^89 - 1) = 2$. $\endgroup$ – Sasho Nikolov Feb 23 '15 at 18:21
  • 1
    $\begingroup$ @SashoNikolov FYI, "one-to-one" means injective. E.g. it redirects to injective function on Wikipedia. I have never heard anyone use "one to one" to mean bijective. $\endgroup$ – 6005 Feb 23 '15 at 19:15
4
$\begingroup$

Here is something that I have established a long time ago.

The answer to your question is $P_n$, but please note that it is "computationally worthless".


Is $n$ prime:

$$F_n=\left\lfloor\frac{\left(\sum\limits_{k=2}^{n-1}\left\lceil\frac{{n}\bmod{k}}{n}\right\rceil\right)+2\cdot\left\lceil\frac{n-1}{n}\right\rceil}{n}\right\rfloor$$


How many primes until $n$:

$$G_n=\sum\limits_{k=2}^{n}F_k$$


What is the $n$th prime number:

$$P_n=\sum\limits_{k=n}^{n^2+1}{k}\cdot{F_k}\cdot\left(1-\left\lceil\frac{(G_k-n)^2}{(G_k+n)^2}\right\rceil\right)$$

$\endgroup$
2
$\begingroup$

We cannot completely rule out the possibility that a "simple" and "natural" function exists which very quickly enumerates a (possibly very thin) infinite subset of the primes.

For example it is not known if Catalan–Mersenne numbers are all primes, 2, 3, 7, 127, 170141183460469231731687303715884105727, ... (OEIS A007013). It would be a tremendous surprise if they were.

The practise of competing to find the largest known prime, and prizes like the EFF Cooperative Computing Awards, would become meaningless if someone could prove that all Catalan–Mersenne numbers are prime.

I have not heard of any mathematician believing that huge primes can be found that easily.

$\endgroup$
1
$\begingroup$

The restatement by Sasho Nikolov seems to make more sense. Though you can probably drop the bijection requirement.

Otherwise the answer to the original question as stated is yes. There are at $\mathfrak{c}$-many injective functions from $\mathbb{N}$ to $\mathbb{P}$ since both of the sets in question have size $\aleph_0$.

There are even computable such functions (since deciding whether a number is prime is not only computable but actually in P).

While writing this I wonder whether a little bit of work using some knowledge about prime density and the poly time deterministic primality prover you couldn't get an almost P algorithm just by finding the closest prime to a suitably chosen power of $n$.

The following springs to mind; compute $n^{2}$, use poly time primality prover to check $n^2+i$ for primality for $i>1$. For each $i$ this is then polynomial in $\log_2(n)$ and given that $$\lim_{x\rightarrow\infty}\frac{\pi(x)}{x/\ln(x)}=1$$ assymptotically the number of $i$'s tested will also be polynomial .

As far as I can tell this give an injective polynomial time function from $\mathbb{N}$ to $\mathbb{P}$. If anyone sees a problem please comment.

$\endgroup$
  • $\begingroup$ I think as far as current knowledge of number theory goes, it could be that there is no prime between $n^2$ and $n^2 + n$. The Riemann hypothesis implies that the gaps between primes in $[n, 2n]$ are no bigger than $\sqrt{n}$. Check the discussion in this polymath paper arxiv.org/pdf/1009.3956v4.pdf. The methods to find primes based only on their density and primality checking usually involve random sampling. $\endgroup$ – Sasho Nikolov Feb 24 '15 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.