# An operation with respect to which the set of prime numbers is closed

Like every (semi-)decidable set of natural numbers the set $P$ of prime numbers is diophantine, i.e. there are two polynomials $p(x)$, $q$ with natural coefficients and exponents – the first of them containing a variable $x$ (next to other variables $\mathbf{n} = n_1, \dots ,n_k$), the second one eventually too (next to other variables $\mathbf{m} = m_1, \dots ,m_l$)– such that

$$P = \lbrace x \in \mathbb{N}\ |\ (\exists \mathbf{n}, \mathbf{m})\ p(x) = q\ \rbrace$$

[Note that a polynomial with natural coefficients and exponents is nothing but a term in the language of Peano arithmetic.]

My question does not concern the definability of the set $P$ of prime numbers by polynomials but the existence of an operation with respect to which $P$ is closed:

Question: Is there a binary operation $\odot$ on the natural numbers – defined by a term in the language of Peano arithmetic with exactly two variables $x,y$ – such that

$$x,y \in P \rightarrow x \odot y \in P$$

i.e. the set $P$ of prime numbers is closed with respect to $\odot$?

• For the set $N\!P = \mathbb{N}\setminus P$ of non-prime numbers everything is obvious. As a diophantine set it is defined by the two polynomials $p(x) = x$ and $q = (n_1+2)\cdot(n_2+2)$. The natural binary operation $x \odot y$ with respect to which $N\!P$ is closed is $x\cdot y$ — expressing the fact that the product of two non-prime numbers is non-prime.

• For the set $P$ of prime numbers the defining polynomials/terms $p(x)$ and $q$ are not obvious at all: they are highly complex - having big or even huge orders and numbers of variables - and hard to find. So it is at first glance not obvious that there might be a binary operation $x \odot y$ (with respect to which $P$ is closed) that is simple - having a small order - and easy to find - or at all.

• maximum and minimum? – Hayden Jul 13 '14 at 0:29
• @Hans Stricker : As I said, I am not a logician, so no, sorry :(. Your notion of "term" is not clear to me. Do you mean a polynomial function $f : P \times P \to P$ such that $f(x,y)$ is a polynomial in $x$ and $y$? – Patrick Da Silva Jul 13 '14 at 0:38
• @HansStricker I think the fact that you're using multiple different phrases for the same thing somewhat unnecessarily confuses (and your phrasing effectively defines a polynomial as a term, rather than the other way around). It might be clearer to simply ask 'is there a polynomial function $f(x,y)$ such that for all $p,q\in P$, $f(p,q)\in P$?' - the motivation can still be clearly expressed, I think. (And FWIW, I think the question is a great one!) – Steven Stadnicki Jul 13 '14 at 0:48
• @StevenStadnicki, there must be more to it, as otherwise the constant polynomial $f(x,y)=2$ would do the trick. – Barry Cipra Jul 13 '14 at 0:58
• @Patrick: I tried to rule out your case by saying that f(x,y) is a polynomial in exactly two variables. – Hans-Peter Stricker Jul 13 '14 at 7:58

[There may be some details to make sure the following goes through, but I think it does provided the polynomial is really in two variables. But also maybe some special care is needed when the degree is small.]

Let $f(x,y)$ be a two variable polynomial of the desired type. Choose a fixed prime, e.g. $2$, then the one variable polynomial $p(x)=f(x,2)$ would have to be prime whenever $x$ is a prime. Next take some prime $a$ and evaluate $p(a)$, which is by assumption a prime. It is necessary here to assume that $p(a) \neq \pm a$ but that seems it would be easy to ensure. We now have $\gcd(a,p(a))=1.$ Now it is known from one of the standard proofs that no polynomial can represent only primes, that given what we have set up so far, $p(a)$ is a divisor of $p(kp(a)+a).$ Since the gcd is $1$ here, the inside $kp(a)+a$, $k=1,2,3...$ is an arithmetic progression satisfying the hypothesis of Dirichlet's theorem, and so a value of $k$ may be chosen so that it is a prime.

Overall then, we have that $f(kp(a)+a,2)$ is composite, being divisible by $p(a).$ (Or maybe the second entry $2$ is some other prime chosen at the start.)

About the choice of $p(x)$ (to ensure there is a prime $a$ for which $p(a)\neq a$):

Instead of using a fixed prime as one of the arguments, define $p(x)=f(x,x)$, which could be called the diagonal of the given $f(x,y)$ representing the binary operation. By the assumptions of the OP, all cooeficients of $f(x,y)$ are nonnegative integers. This means the only way one could have $p(x)=x$ (as a polynomial) would be if $f(x,y)=x$ or $f(x,y)=y$ (as polynomials). Any higher coefficients in $f(x,y)$ would produce higher coefficients in the diagonal polynomial $p(x),$ since the coefficients are all nonnegative. The OP is explicitly ruling the choices $f(x,y)=x,\ f(x,y)=y$ out, by the phrase "in exactly two variables". This phrase also rules out any constant polynomial such as $f(x,y)=17.$ So using this "diagonal" polynomial $p(x)=f(x,x)$ ensures that as a polynomial, $p(x)$ is neither $x$ nor a constant. To start out the argument above, we need a prime value a for which $p(a) \neq a.$ To ensure this, note that the poloynomial $p(x)-x$ has degree at least $1$ [since $p(x)$ is not the polynomial $x$]. So this last polynomial can have only a bounded number of zeros, and there being infinitely many primes to use for $a$ one can therefore find one for which $p(a)-a \neq 0,$ which gives the desired "starting point" $p(a) \neq a$ for the remainder of the argument given above.

• This argument looks just fine to me, and in fact, seems like it shows that the result holds for $n$-variable polynomials, too - you can just set $n-1$ of your variables to your favorite prime to get a univariate polynomial, which must take a non-prime value at some prime. – Steven Stadnicki Jul 13 '14 at 4:43
• @StevenStadnicki I agree about going down from an $n$ variable polynomial to one of degree $1.$ The only thing I worried about is where I assumed $p(a) \neq \pm a$. I think here it might be obviously so, but if not it might be easily guaranteed by changing the initial prime 2, and/or the choice of the prime $a$. – coffeemath Jul 13 '14 at 4:57
• That's not a problem if you assume that the polynomial isn't trivial - you just choose some prime $a$ for which $p(a)\neq a$. (If $p()$ is of degree $\gt 1$ then the polynomial $q(x) = p(x)-x$ will be either eventually positive or eventually negative; in either case, there'll be some prime value at which $q(x)\neq 0$ - i.e., $p(x)\neq x$. If $p()$ is of degree 1 then it's even more trivial.) – Steven Stadnicki Jul 13 '14 at 5:07
• @Steven Actually if $p(x)=x$ (or a constant prime) there is a problem, and this can happen even for arbitrary initial polynomials $f(x,y)$ if one sticks to only one choice of a fixed prime $y$ to get the one variable poly $p(x).$ However it can be shown this cannot occur if one is allowed to try various primes $y$ until one gets a case wherein $p(x)$ doesn't turn out to be $x$ or constant; the argument involves use of a Vandermonde determinant. If you want this included let me know... – coffeemath Jul 13 '14 at 13:32
• @Steven I've added an alternate choice of the one variable polynomial for which it is easier to rule out constants or $p(x)=x$ cases. In my opinion doing things the way I did at first by fixing one variable got too involved to make really rigorous. – coffeemath Jul 13 '14 at 18:04