# Is there no univariate integer polynomial that takes on the same positive values as the multivariate polynomial $x^2+y^2$?

Is there no univariate integer polynomial that takes on the same positive values as the multivariate polynomial $x^2+y^2$?

The values are numbers such that each prime factor of the form $4k+3$ occurs an even number of times.

How to prove that no univariate polynomial produces the same positive values? Or if there is one, what is it?

-
You mean the same positive values for $x, y$ integers? – Qiaochu Yuan Feb 22 '12 at 1:15

No. I'm sure there is a better way to do this, but if the degree $d$ of the univariate polynomial is 2 or larger, the number of represented numbers up to some positive bound $N$ is no larger than roughly a constant times $N^{1/d},$ because a univariate polynomial is dominated in size by its highest degree term. In comparison, the number of represented numbers, for $x^2 + y^2,$ is asymptotically $$\frac{0.7642... \; N}{\sqrt {\log N}}.$$ I like to think of this as roughly the geometric mean of $N$ and the number of primes up to $N.$ The proof is the final section of the final chapter of Volume 2 of Topics in Number Theory by William J. Leveque, inexpensive and available for sale HERE. The constant I have written as $0.7642... \;$ is given on page 261 by an infinite product, and is called $B$ there. The result is called Theorem 7-28.
So you are left with linear polynomials $a x + b.$ These represent either too much, as in just plain $x,$ or both too much and too little, say $4 x + 1.$ In any case the asymptotic density is too high.
A little culture. The same kind of asymptotic behavior will work for any integral positive form, and any nondegenerate indefinite form $a x^2 + b x y + c y^2$ with $b^2 - 4 a c > 0$ but not a square. Of course, here we are asking about the count of represented numbers between $-N$ and $N.$ Also, we cannot ask about the number of representations of a given number, that becomes infinite.
There is a small trick with degenerate indefinite forms such as $x^2 - y^2.$ As this factors into $(x-y)(x+y),$ we can take $x = y+1$ to represent every odd number as $2y + 1.$ Also, every multiple of 4 with $x = y+2$ as $4y + 4.$ However, whatever we do, we cannot represent any number $n$ with $n \equiv 2 \pmod 4,$ that is twice an odd number, either positive or negative. So, although we have achieved linear density, there is still no single univariate polynomial that represents these numbers and only these numbers. We need to combine, say in a variable $t,$ the separate polynomials $4t$ and $2t+1.$
@Dan, the quadratic form does represent all primes $p \equiv 1 \pmod 4.$ A polynomial in one variable cannot do that unless it is linear, in which it represents too much. – Will Jagy Feb 22 '12 at 3:54