Question

Lagrange proved that every nonnegative integer is a sum of 4 squares.

Gauss proved that every nonnegative integer is a sum of 3 triangular numbers.

Is there a 2-variable polynomial $f(x,y) \in \mathbf{Q}[x,y]$ such that $f(\mathbf{Z} \times \mathbf{Z})=\mathbf{N}$?

Answer 1

This is a cute problem! I toyed with it and didn't really get anywhere - I got the strong impression that it requires fields of mathematics that I am not expert in.

Indeed, given that the problem seems related to that of counting integer solutions to the equation $f(x,y) = c$, one may need to use arithmetic geometry tools (e.g. Faltings' theorem). In particular if we could reduce to the case when the genus is just 0 or 1 then presumably one could kill off the problem. (One appealing feature of this approach is that arithmetic geometry quantities such as the genus are automatically invariant (I think) with respect to invertible polynomial changes of variable such as $(x,y) \mapsto (x,y+P(x))$ or $(x,y) \mapsto (x+Q(y),y)$ and so seem to be well adapted to the problem at hand, whereas arguments based on the raw degree of the polynomial might not be.)

Of course, Faltings' theorem is ineffective, and so might not be directly usable, but perhaps some variant of it (particularly concerning the dependence on c) could be helpful. [Also, it is overkill - it controls rational solutions, and we only care here about integer ones.] This is far outside of my own area of expertise, though...

The other thing that occurred to me is that for fixed c and large x, y, one can invert the equation $f(x,y) = c$ to obtain a Puiseux series expansion for y in terms of x or vice versa (this seems related to resolution of singularities at infinity, though again I am not an expert on that topic; certainly Newton polytopes seem to be involved). In some cases (if the exponents in this series expansion are favourable) one could then use Archimedean counting arguments to show that f cannot cover all the natural numbers (this is a generalisation of the easy counting argument that shows that a 1D polynomial of degree 2 or more cannot cover a positive density set of integers), but this does not seem to work in all cases, and one may also have to use some p-adic machinery to handle the other cases. One argument against this approach though is that it does not seem to behave well with respect to invertible polynomial changes of variable, unless one works a lot with geometrical invariants.

Anyway, to summarise, it seems to me that one has to break out the arithmetic geometry and algebraic geometry tools. (Real algebraic geometry may also be needed, in order to fully exploit the positivity, though it is also possible that positivity is largely a red herring, needed to finish off the low genus case, but not necessary for high genus, except perhaps to ensure that certain key exponents are even.)

EDIT: It occurred to me that the polynomial $f(x,y)-c$ might not be irreducible, so there may be multiple components to the associated algebraic curve, each with a different genus, but presumably this is something one can deal with. Also, the geometry of this curve may degenerate for special c, but is presumably stable for "generic" c (or maybe even all but finitely many c).

It also occurs to me that one use of real algebraic geometry here is to try to express f as something like a sum of squares. If there are at least two nontrivial squares in such a representation, then f is only small when both of the square factors are small, which is a 0-dimensional set and so one may then be able to use counting arguments to conclude that one does not have enough space to cover all the natural numbers (provided that the factors are sufficiently "nonlinear"; if for instance $f(x,y)=x^2+y^2$ then the counting arguments barely fail to provide an obstruction, one has to use mod p arguments or something to finish it off...)

Answer 2

The search turned up a 1981 paper by John S.Lew (in the Unsolved problems section)

• Polynomials in Two Variables Taking Distinct Integer Values at Lattice-Points

which discusses related problems, and ends up stating this one. The author's problems are:

• Problem A. Classify bijections $\mathbb N\times\mathbb N \to \mathbb N$.
• Problem B. Classify bijections $\mathbb Z\times\mathbb Z \to \mathbb Z$.
• Problem C. Classify surjections $\mathbb Z\times\mathbb Z \to \mathbb N$.

His main conjecture is that the only solutions to A are Cantor's $x+ \frac12(x+y-1)(x+y-2)$, which apparently goes to the time of Polya. Lew states C independently from empirical observations.

Answer 3

What can be said about the following stronger question? Let $f(x,y)\in \mathbf{Q}[x,y]$ such that $f(\mathbf{Z}\times \mathbf{Z})$ is a subset of $\mathbf{N}$. Let $g(n)$ be the number of elements of $f(\mathbf{Z}\times \mathbf{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)}$.

Answer 4

After thinking about this problem for a bit using rather a naive approach, looking at regions where f grows faster than quadratically (as mentioned in Qiaochu's attempt), it certainly appears that obtaining a negative answer to this problem is very difficult. To obtain a positive answer might be easier since we only need to exhibit a single polynomial with $f(\mathbb{Z}\times\mathbb{Z})=\mathbb{N}$ although, in all likelihood, there do not exist such examples. However, even using the naive approach, it quickly becomes clear what kind of behaviour could lead to a polynomial f having the required properties. Polynomials of degree less than four can be quickly dismissed. Then, assuming f has degree 2n, look at the leading order terms $f_{2n}$, which is a homogeneous polynomial of degree 2n. Away from the zeros of $f_{2n}$, it grows at rate $R^{2n}$ ($R=\sqrt{x^2+y^2}$) and dominates the lower order terms, so f cannot cover a strictly positive density of the integers. The difficulties occur when we look close to certain curves which are asymptotic to the zeros of $f_{2n}$ (being homogeneous, the zeros of $f_{2n}$ lie on a finite set of lines radiating out from the origin). On such curves, $f_{2n}$ will grow at a rate less than $O(R^{2n})$ and cancellation with lower order terms can occur. Looking at how much cancellation can occur seems to lead to difficult problems of Diophantine approximation.

The kind of polynomial which are plausible candidates for a polynomial mapping onto the positive integers are as follows. $$ f(x,y)=a\prod_{i=1}^d\left(x-\alpha_iy\right)^{2n} - q(x,y)\qquad\qquad{\rm(1)} $$ where $\alpha$ is a real algebraic integer with minimal polynomial of degree $d > 2$ over the rationals and conjugates $\alpha_1,\cdots,\alpha_d$, $a$ is a positive integer, and $q(x,y)$ is a polynomial of degree $2n(d-2)$. By Dirichlet's theorem, we know that there are infinitely many integer x,y such that $\vert x/y-\alpha_i\vert < y^{-2}$, so the leading order term of (1) is less than some fixed multiple of $R^{2n(d-2)}$ infinitely often. So there will be some cancellation with q. On the other hand, by the Thue-Siegel-Roth theorem, we know that $\vert x/y-\alpha\vert > y^{-2-\epsilon}$ for all large x,y, so the leading order terms of (1) grow at least as fast as $O(R^{2n(d-2)-\epsilon})$ which, at least, means that (1) cannot go negative very quickly. The question then, is there an algebraic number $\alpha$ such that $\vert x/y-\alpha\vert\ge cy^{-2}$ for some positive constant c and all integer x,y? In that case, the leading order term of (1) would be bounded below by a multiple $R^{2n(d-2)}$ and q could be chosen such that $f(\mathbb{Z}\times\mathbb{Z})\subseteq\mathbb{N}$. It is then possible, but still unlikely, that (1) gives a polynomial mapping onto the positive integers. Looking in my copy of Hindry & Silverman (Diophantine Geometry, An Introduction) it mentions that it is an open problem whether there exist such algebraic numbers (and there are no known examples or counterexamples with $d > 2$) but it is conjectured that there aren't any. So, polynomials such as (1) appear unlikely to do what we want, but proving this seems to be very difficult. Of course, that f actually covers $\mathbb{N}$ would be a much stronger statement than $\vert x/y-\alpha\vert \ge cy^{-2}$ so, maybe an expert in this area could actually rule out such examples, but it still looks like a very tricky problem.

We can also try polynomials such as $$ f(x,y)=a\prod_{i=1}^d\left((x-\alpha_iy)^r-p(\alpha_i)y^s\right)^{2n} - q(x,y)\qquad\qquad{\rm(2)} $$ where, now, p is a polynomial with integer coefficients,r,s are positive integers and q has degree less than $2n$. This is even more difficult than (1) to deal with and whether or not such polynomials can provide what the question is asking for depends on how small $(x/y-\alpha)-p(\alpha)^{1/r}y^{s/r-1}$ can be. This also looks like a very difficult problem in Diophantine approximation.

So, although I expect that the answer to this is no, there are no such $f$, any method of proving this has to cope with possibilities such as (1) and (2). Just these two cases look extremely difficult to handle. Maybe it is possible though, and an expert on such areas would be able to say something more about them than I can.

Answer 5

I don't think so (but I haven't checked this argument very thoroughly):

First we claim that any such $f$ has degree two. Clearly the leading term of $f$ cannot be odd, so suppose by contradiction that $f$ has degree at least four. Pick a constant $R$ large enough so that in the region $D_1$ consisting of points satisfying $|x|, |y| \ge R$, there exists a constant $c$ such that $f(x, y) \ge c \text{ min}(|x|, |y|)^4$. (Edit: This isn't always possible, but I think it can be salvaged.) Then it's not hard to see that $\sum_{D_1} \frac{1}{f(x, y)}$ converges. But $D_2 = \mathbb{Z}^2 - D_1$ can be partitioned into $4R - 2$ not necessarily disjoint lines in which one of $x$ or $y$ is fixed. On any of these regions $f$ cannot be linear, so it either grows at least quadratically or is a constant; we can ignore the lines on which $f$ is constant. It follows that $\sum_L \frac{1}{f(x, y)}$ converges for any line $L$ on which $f$ is nonconstant, hence $\sum \frac{1}{f(x, y)}$ converges if we sum over every point of $\mathbb{Z}^2$ except the lines on which $f$ is constant. Since we have only thrown out finitely many of the values of $f$ in this sum, those values cannot contain every positive integer.

But if $f$ is quadratic, it is a constant plus the sum of squares of two polynomials with rational coefficients and there are many integers not representable as the sum of squares of two rational numbers.

Answer 6

How about an alternative question: does there exist a polynomial $f\in\mathbb{Q}[x,y]$ with integer values at lattice points, and of degree at least two on each variable, such that for any prime $p$, the map $f:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ composing with $\mathbb{Z}\to\mathbb{F}_p$ is surjective? Or more specifically, does a degree two such polynomial exist? The last part shouldn't be too hard, but I don't know how to solve it.

Answer 7

If we can make a (single variable) polynomial function $g(x)$ from $\mathbb{Z}$ onto $\mathbb{N}$, we could compose it with the Cantor pairing function, but such a $g(x)$ seems implausible for some reason...

Answer 8

I have thinked over this question for about one year occationally. I think it may be related to the Hilbert Polynomial, a reason is that the Gauss Number is a kind of this type.