Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
You mean the same positive values for $x, y$ integers? – Qiaochu Yuan Feb 22 '12 at 1:15
up vote 5 down vote accepted

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.$

share|cite|improve this answer
Makes sense, that is similar to how I was trying to figure it, not knowing the asymptotic estimate. Maybe there is an elementary reason though. I'll add this one to my Dover collection next time I'm at B&N. :) – Dan Brumleve Feb 22 '12 at 1:22
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.