Fermat conjectured that $2^{2^n}+1$ is prime for every $n \in \mathbb{N}.$ Before even knowing about Euler's counterexample (that $2^{32}+1 = 641 \cdot 6700417$), you could possibly say that Fermat was mistaken, for this is too good to be true. I wish to rigorize the notion that anyone with an "elementary" formula for prime numbers is mistaken.
It is well-known that every non-constant integer-valued polynomial $f: \mathbb{N} \to \mathbb{N}$ cannot produce just primes. Just how much can we generalize this? I kept building up and up and eventually came to a very general conjecture.
An $m$-ary natural elementary function is a function $f: \mathbb{N}^m \to \mathbb{N}$ finitely generated by $\{0,1,+,\cdot, \text{exp},x_1,\dots,x_m\}.$ For example, $f(x_1, x_2) = 2^{3x_2+x_1^7}+1729x_2x_1^{11x_2^{x_1^{x_2}}}$ is a binary natural elementary function. Let $P$ be the set of primes. For $S \subseteq \mathbb{N},$ define the complexity $k(S)$ to be the smallest $m$ such that there exist a $m$-ary natural elementary function $f$ with $\text{Im}(f) = S \cup S'$ where $S'=\emptyset$ if $S$ is finite and $S'$ is allowed to be any finite set otherwise.
Conjecture 1: $k(P) \ne 1.$
It would simply be too good to be true if we found a single variable natural elementary function that produced all primes, and just primes with only finitely many exceptions.
Some may argue that concerns like these are unoriginal, since it has already been shown from Matiyasevich's theorem (see https://en.wikipedia.org/wiki/Formula_for_primes) that there is a polynomial inequality in $26$ variables, and there is no further interest in trying to raise up lower bounds and push down upper bounds. However, this does not actually imply $k(P) < 26,$ for when $<0$ (the LHS and inequality sign shown in the article) is removed from the equation, infinitely many negative numbers appear in the image.
Moving on, it seems natural to relax the requirements, and ask for what happens if we merely require $\text{Im}(f) \subseteq S \cup S'$ plus the additional requirement that $f$ is non-constant*. Let the corresponding number be $k'(S).$
Conjecture 2: $k'(Q) \ne 1$ for any infinite subset $Q \subseteq P.$
This is even stronger. Even the notion that your formula produces only primes, even allowing finitely many exceptions, implies that you must be using up a lot of variables. However, at least we have
Conjecture 3 (?): $k'(S)$ exists for any computable set $S.$
I put (?) because I'm not sure which of these 2 scenarios holds: this immediately follows from more careful consideration of Matiyasevich's theorem, or this is wide open and possibly harder to resolve than the previous conjectures. Out of curiosity,
If conjectures (2) and (3) hold, what is the value of $k'(P)$? Can we determine the value of $k'(Q)$ for some arbitrary infinite subset $Q \subseteq P$?
The set $S_m$ of $m$-ary NEFs is clearly closed under addition, multiplication, exponentiation, and composition, and contains an additive, multiplicative, exponentiative, and (both left and right) compositive identity ($0, 1, 1, \text{id}$ respectively). Associativity, commutativity, and distributivity all follow for appropriate operations as well. In particular, $(S_m, +, \cdot)$ is a semiring. What else can be said about $S_m$ (I hope this isn't too broad)?
*Is there a better condition to put here? We wish to avoid functions like $f(x_1,\dots,x_m) = 257.$ Perhaps we should just use a new symbol: $A \sim B$ if either $A = B$, or $A \subseteq B \cup C,$ with $A, B$ infinite and $C$ finite. Then the condition defining $k'(S)$ becomes $\text{Im}(f) \sim S.$
I don't expect there to be any conclusive answers to the questions or resolutions of the conjectures, so I'm asking about what people have found so far, and how we may generalize these conjectures even further in the spirit of Grothendieck.
