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 Meyerowitz Nov 10 '10 at 5:22

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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