Density of values of polynomials in two variables - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T12:02:50Z http://mathoverflow.net/feeds/question/45511 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/45511/density-of-values-of-polynomials-in-two-variables Density of values of polynomials in two variables Richard Stanley 2010-11-10T02:32:47Z 2013-01-18T20:35:23Z <p>This question is a reposting of a comment I made on <a href="http://mathoverflow.net/questions/9731/polynomial-representing-all-nonnegative-integers" rel="nofollow">http://mathoverflow.net/questions/9731/polynomial-representing-all-nonnegative-integers</a>. 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)}$. </p> http://mathoverflow.net/questions/45511/density-of-values-of-polynomials-in-two-variables/119288#119288 Answer by Tim Browning for Density of values of polynomials in two variables Tim Browning 2013-01-18T20:35:23Z 2013-01-18T20:35:23Z <p>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. <em>Proc. London Math. Soc.</em> <strong>43</strong> (1981), 73-109).</p> <p>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.</p>