Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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)}$. –  Aaron Meyerowitz Nov 10 '10 at 5:22
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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.