# Which integer polynomials represent fewer primes, in terms of order of magnitude, when shifted by a constant integer?

Let $f(x_1,\dots,x_n) \in \mathbb{Z}[x_1,\dots,x_n]$ be a polynomial for which the set of integers not represented by it is infinite. I'm curious about cases in which there exists an integer $c$ such that the density of primes represented by $f$ and those represented by $f+c$ differ in their orders of magnitude.

[EDIT: It seems that the previous condition on the set of integers not represented by $f$ needs to be improved to: not $o(N/\log N)$. The example of $f(x,y,z)=2x^2+xy+3y^2+z^3-z$ in this interesting question, Integers not represented by $2x^2+xy+3y^2+z^3-z$, makes one aware of this. Thank you for the hint!]

[EDIT: A slightly more specific and maybe better way to phrase the question is: For which $f\in \mathbb{Z}[x_1,\dots,x_n]$ do we have $f$, $f+1$ both representing an infinite amount of primes and

$$\sum_{\substack{p \leq N\\p-1 = f(x_1,\dots,x_n)}} 1 = o\left(\sum_{\substack{p \leq N\\p = f(x_1,\dots,x_n)}} 1\right)?$$

Thanks to js who points out that if one believes the Bateman-Horn conjecture, then this phenomenon is specific to multivariate polynomials.]

Motivation: These two questions, Integers represented by the polynomial $a^2+b^3+c^6$ and Primes $1+x^2+y^2$, made me wonder. In the second linked question, the integers less than $N$ represented by $x^2+y^2+a^2$ for any $a\in\mathbb{Z}$ are asymptotically the same, namely

$$\frac{0.7642\dots N}{\sqrt{\log N}}.$$

Yet the primes less than $N$ representable by $x^2+y^2$ are asymptotically

$$\frac{N}{2\log N}$$

while those less than $N$ representable by $x^2+y^2+1$ have order of magnitude

$$\asymp \frac{N}{(\log N)^{3/2}}.$$

Question: Is there a really good way to characterize which polynomials $f$ behave somewhat like this?

Intuitively, it seems that the above difference is due to the phenomenon that the more factors $x^2+y^2=m$ has, then the more "collisions" as well - many $(x,y)$ map to the same $m$. As in here. And $p-1$ is always composite, except $p=2,3$. But I don't know if this is the right way to think of the question, or whether other $f$ which are like this, behave like this for the same reason.

Note: Let's exclude the cases where the polynomial becomes reducible over $\mathbb{Z}[x_1,\dots,x_n]$ after being shifted. I.e., let's stick to cases where both $f$ and $f+c$ still represent an infinite amount of primes.

Thank you.

EDIT: I'm not really sure about this, but perhaps one possible way is to consider norm forms for algebraic number fields, generalizing the case of $f(x,y)=x^2+y^2$ corresponding to $\mathbb{Q}[i]$. If $f$ is the norm of elements in the ring of integers of some number field, then the primes less than $N$ represented by it will have order of magnitude

$$\asymp\frac{N}{\log N}.$$

The exact constant depends on the degree and class number of the field. Then the task is to understand how often it takes values in $\mathbb{P}-1$. In the case of $f(x,y)=x^2+y^2$, it seems we had

$$\sum_{\substack{p\leq N\\p-1=x^2+y^2}}1 = o(N/\log N)$$

because the integers of the form $x^2+y^2$ were characterised by being divisible by even powers of primes $q\equiv 3 \bmod 4$ with no condition on the primes $q \equiv 1 \bmod 4$. This is in turn was due to the properties of $f$ coming from a number field, in this case, $\mathbb{Q}[i]$. We then had to estimate the number of primes $p\leq N$ for which the factorization of $p-1$ has only even powers of $q \equiv 3 \bmod 4$ occuring. Found something helpful on binary quadratic forms in the whole of section 4 of these notes by Pete Clark and Proposition 4.1 of these course notes of Andrew Granville. They give the analogue of this phenomena for binary quadratic forms. This motivates:

Question 2: For any form $f$ that is the norm of elements in the ring of integers of a number field, is there a general statement that will characterise the set of integers represented by it in such a way that will allow us to conclude that

$$\sum_{\substack{p\leq N\\p-1=f(x_1,\dots,x_n)}}1 = o(N/\log N)?$$

Thank you.

EDIT: It seems that Question 2 is nicely thought of in the following light: Motivated by the comment by Greg Martin in this interesting question, Average orders of multiplicative functions, one is led to consider Theorem 1 of this paper, Counting numbers in multiplicative sets: Landau versus Ramanujan of Moree on multiplicatively-closed sets, and also this MO question, Density of a set of integers. These indicate that the primes in such multiplicatively-closed sets occur more frequently than what would be expected from applying the heuristics on the likelihood of an integer being prime derived from the Prime Number Theorem to a "random" set which is the same size as the multiplicatively-closed set in question. The integers represented by the function $f$ in Question 2 are a multiplicatively-closed set, but shifting them by a constant integer removes this property. Guess that accounts for Question 2. Now, this interesting question, What is the geometry of an undecidable diophantine equation?, shows that the general case is really not straightforward!

-
If one believes the Bateman-Horn Conjecture, this phenomenon is specific to multivariate polynomials. On the other hand, even an appropriate conjecture in the multivariate case remains elusive (as far as I know). –  js21 Dec 3 '12 at 7:43
Hi @js, and thanks for your comment. It indeed seems elusive. And from the comments in the first question linked to here, it seems that even the question of which integers are represented by multivariate polynomials is not all that straightforward... –  Timothy Foo Dec 3 '12 at 9:27