Question

This question is a reposting of a comment I made on http://mathoverflow.net/questions/9731/polynomial-representing-all-nonnegative-integers. Let $f(x,y)\in \mathbb Q[x,y]$ such that $f(\mathbb Z\times \mathbb Z)$ is a subset of $\mathbb N$ (the nonnegative integers). Let $g(n)$ be the number of elements of $f(\mathbb Z\times \mathbb Z)\cap \lbrace 0,1,\dots, n\rbrace$. How fast can $g(n)$ grow? Is it always true that $g(n)=O(n/\sqrt{\log(n)})$? If true this is best possible since if $f(x,y)=x^2+y^2$ then $g(n)\sim cn/\sqrt{\log(n)}$.

Answer 1

I would certainly expect $g(N)$ to be rather small when $f$ has larger degree. Let us consider the special case where $f(x,y)=x^d+y^d$, for $d\geq 3$. Consider the arithmetic function $r(n)$, which counts the number of $(x,y)\in \mathbb{N}^2$ such that $n=f(x,y)$. The first moment of $r(n)$ is easily understood via the geometry of numbers. The second moment was looked at by Hooley (On another sieve method and the numbers that are a sum of two $h$th powers. Proc. London Math. Soc. 43 (1981), 73-109).

As a consequence of this there exists an explicit constant $c>0$ such that there are asymptotically $c N^{2/d}$ integers $n\leq N$ which can be written as $x^d+y^d$, and furthermore, almost all of these have essentially just one representation.