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.

  • 2
    $\begingroup$ maximum and minimum? $\endgroup$ – Hayden Jul 13 '14 at 0:29
  • 1
    $\begingroup$ @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$? $\endgroup$ – Patrick Da Silva Jul 13 '14 at 0:38
  • 1
    $\begingroup$ @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!) $\endgroup$ – Steven Stadnicki Jul 13 '14 at 0:48
  • 1
    $\begingroup$ @StevenStadnicki, there must be more to it, as otherwise the constant polynomial $f(x,y)=2$ would do the trick. $\endgroup$ – Barry Cipra Jul 13 '14 at 0:58
  • 1
    $\begingroup$ @Patrick: I tried to rule out your case by saying that f(x,y) is a polynomial in exactly two variables. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – Steven Stadnicki Jul 13 '14 at 4:43
  • $\begingroup$ @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$. $\endgroup$ – coffeemath Jul 13 '14 at 4:57
  • 1
    $\begingroup$ 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.) $\endgroup$ – Steven Stadnicki Jul 13 '14 at 5:07
  • $\begingroup$ @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... $\endgroup$ – coffeemath Jul 13 '14 at 13:32
  • $\begingroup$ @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. $\endgroup$ – coffeemath Jul 13 '14 at 18:04

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.