This question is a reposting of a comment I made on 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)}$.
$\begingroup$
$\endgroup$
asked Nov 10 '10 at 2:32
-
1$\begingroup$ What is known about the sum of a square and a triangular number, $x^2+\frac{y(y-1)}{2}$? They seem to be about twice as dense as sums of two squares, although would just double the constant in $ cn/\sqrt{\log(n)}$. $\endgroup$ – Aaron Meyerowitz Nov 10 '10 at 5:22
$\begingroup$
$\endgroup$
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.
