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)}$.
-
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 MeyerowitzNov 10, 2010 at 5:22
1 Answer
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.
-
$\begingroup$ Just a comment that it is not just a matter of degree: The $g$ for $f(x,y) = x^2+y^2$ is the same as the $g$ for $f(x,y+x^{100})$, for instance, because $(x,y) \mapsto (x,y+x^{100})$ is an automorphism of the affine plane over $\mathbb{Z}$. $\endgroup$ Mar 14, 2022 at 21:20