http://people.csail.mit.edu/jaffer/ZxZtoN | |
f(Z×Z) = N? |
Open Question: Let Z be the set of integers, and let N be the set of nonnegative integers. Is there a polynomial f(x,y) such that f(Z×Z) = N?
M. B. Nathanson's A Short Proof of Cauchy's Polygonal Number Theorem defines polygonal numbers as
u_{m}(k)^{ } = | m | (k^{2} - k) + k |
2 |
Every nonnegative integer is the sum of m+2 polygonal numbers of order m+2.When m=0, u_{0}(k)=k. And with nonnegative k we trivially have f(NxN)=N when f(x,y)=x+y. Even simpler is f(N)=N when f(x)=x.
But the open question is for inputs both positive and negative. With positive m, u_{m}(k) is always nonnegative; so f(Z×Z×Z)=N and higher degrees follow. But with u_{0} being the identity function, f produces negative integers.
Because the proof is all about quadratics (as opposed to the two-sided polygonal numbers being linear), and because the number of polygonal-numbers required jumps from 3 to 1 when m goes from 1 to 0, the proof of Cauchy's Polygonal Number Theorem is unlikely to shed any light on the proposition in question.
The 15-theorem closes the universality problem for integer-matrix forms by providing an extremely simple criterion. We no longer need a list of universal quaternaries, because a form is universal provided only that it represent the numbers up to 15. Moreover, this criterion works for larger numbers of variables, where the number of universal forms is no longer finite. (It is known that no form in three or fewer variables can be universal.)The parenthetical remark at the end seems to imply that the degrees of x and y in f(x,y) must be greater than 2. But Professor Poonen points out that quadratic form means "homogeneous polynomial of degree 2"; and his question is not restricted to homogeneous polynomials.
If an integer n is greater than 2, then the equation a^{n}+b^{n}=c^{n} has no solutions in nonzero integers a, b, and c.If f is the simple sum of nth (4 or larger) powers of its two arguments, then Fermat's Last Theorem directs that f is not surjective because there are no input pairs generating c^{n}. It will also rule out the sum of two powers (> 2) of polynomials with no "net" constant term. For example: (x^{2}+y^{2}+1)^{3} + (2 x y-1)^{3}.
The requirement that only nonnegative numbers are produced by f is stringent. Suppose the degree of x in f is odd. If we let y take a value which does not extinguish the leading x term of f, then sufficiently large magnitude of x will dominate any other terms. For sufficiently large magnitudes, that leading term will change sign depending on the sign of x. Thus the degree of x in f must be even. Similarly, the degree of y in f must also be even.
Consider f(x,0). All terms in this polynomial involve x only. By the previous reasoning, the degree of x in f(x,0) must be even. Similarly, the degree of y in f(0,y) must also be even.
What if the degree of x or y in f(x,y) is zero? Then we simply have a polynomial in one variable (the variable whose degree is not zero).
Lemma 1: There is no polynomial f(x) which is surjective from the integers (Z) to the nonnegative integers (N).The degree of x in f must be even. For degree 0, f would be a constant, having only a single value which is not surjective onto N. For even degree k>1 and sufficiently large value of x, f(x) is greater than every value f(0), ..., f(x-1) and f is monotonically increasing and the difference between f(x+1) and f(x) is O(x^{k-1}). Because f is monotonically increasing, it never returns to the values between f(x) and f(x+1). The values of f(-x) similarly become monotonically increasing and spread further and further apart. Thus f is not surjective onto N.
Thus the degrees of x and y in f(x,y) must be even and not less than 2.
Corollary 1: If a polynomial f(x,y) can be rewritten as the composition of an even degree polynomial p with an integer-valued polynomial g(x,y), then f is not surjective from the integers to the nonnegative integers.The set of all possible values returned by g is a subset of the integers. By Lemma 1, p cannot be surjective onto N; thus f(x,y)=p(g(x,y)) cannot be surjective onto N.
What about the total-degree of f? If f exists with an odd total-degree of D, there may be more than one term with total-degree of D (eg. 3x^{2}y+y^{2}x). Consider h(x)=f(x,cx), where c is a nonzero constant chosen (eg. 1 in the example) so that the degree of x in h(x) is D, the total-degree of f. Then h(x) is a polynomial of odd degree and takes on negative values for some x. Thus, the total-degree of f must be even.
This establishes that the total-degree of f must be even and no smaller than 2.
Let b be a positive integer. There are b^{2} x,y pairs in the region 0≤x<b, 0≤y<b. Because f(x,y) is symmetrical, f produces no more than 1/2(b^{2}+b) values when applied to these x,y pairs.
The polynomial f applied to these x,y pairs along with
pairs -x,y, x,-y, and -x,-y produces the only
values of f(x,y) less than b^{4}. But
for b≥2, 1/2(b^{2}+b) is less
than b^{4}.
Thus, f(x,y)=x^{4}+y^{4}
does not produce integers densely enough to cover the natural numbers.
In both these cases the 1/2(b^{2}+b) unique x,y combinations included pairs whose projection through f was larger than b^{4} and b^{2}, respectively. But the source count was less than output range even with these extra pairs.x^{2}+y^{2}
This sort of counting also works for f(x,y)=x^{2}+y^{2}. The polynomial f applied to the 1/2(b^{2}+b) unique x,y combinations produces the only values of f(x,y) falling in the range 0 to b^{2}. For b≥2, 1/2(b^{2}+b) is less than b^{2}. Thus, f(x,y)=x^{2}+y^{2} does not produce integers densely enough to cover the natural numbers.
Definition: Given a positive number H and a polynomial f(x,y), let C(H,f) be the count of integer x,y pairs satisfying 0<f(x,y)<H.From the definition it follows that asymptotically-sparse polynomial functions do not produce integers densely enough to cover the natural numbers. The converse is not necessarily true; even though both do not produce integers densely enough to cover the natural numbers, x^{4}+y^{4} is asymptotically-sparse, while x^{2}+y^{2} is not.A polynomial f(x,y) is asymptotically-sparse if all values of f(x,y) are nonnegative and O(C(H,f))<O(H).
Polynomial functions can also fail to be asymptotically-sparse because they return negative values, or because they are not bivariate. For instance, f(x,y)=x^{4} is not asymptotically-sparse because there are an unbounded number of y values for which f(x,y)<H.
Note that the definition of asymptotically-sparse polynomial functions does not restrict them to be integer-valued.
Lemma 2: The product of an asymptotically-sparse polynomial function with any positive number is asymptotically-sparse.Let H be a large positive number and f(x,y) be an asymptotically-sparse polynomial function. Let g(x,y)=rf(x,y) where r is a positive number. Any x,y pair satisfying 0<g(x,y)<H, also satisfies 0<f(x,y)<H/r. Because O(H)=O(H/r), C(H,rf)<O(H); and rf(x,y) is asymptotically-sparse.
Let b be a positive integer large enough so that u(x≥b) and u(x≤-b) are monotonically increasing and the difference between u(x+1) and u(x) and the difference between u(-x) and u(-x-1) are O(x^{k-1}) for |x|≥b.
There are O(b^{2}) x,y pairs in the region 0≤x<b, 0≤y<b and its negative mirrors. The polynomial f applied to these x,y pairs produces the only values of f(x,y) which fall in the range 0 to O(x^{k}). But for large x and k≥4, O(x^{2}) is smaller than O(x^{k}). Thus, f(x,y)=u(x)+u(y) of degree 4 or more is asymptotically-sparse.
Let b and c be positive integers large enough so that:
There are O(x^{1+j/k}) x,y pairs in the regions 0≤x<b, 0≤y<c and their negative images. The polynomial f applied to these x,y pairs produces the only values of f(x,y) which fall in the range 0 to O(x^{j}). With j≥k, j≥4 and k≥2, O(x^{1+j/k}) is smaller than O(x^{j}). In particular:
Notice that last this case tightened the degree bounds. With the minimum total-degree of 4, one polynomial, v(y), can have degree 2. This leaves only the case where both u(x) and v(y) are quadratic. The counting arguments used previously won't work here because half of the (b^{2}+b) x,y pairs can't be dismissed. Instead, count the integers generated over the range 0 to 11.Both u(x) and v(y) must be positive semi-definite. f(x,y) must be 1 for some x,y; so either there is x_{1} such that f(x_{1},0)=u(x_{1})=1 or there is y_{1} such that f(0,y_{1})=v(y_{1})=1. Without loss of generality, assume that f(x_{1},0)=u(x_{1})=1.
Because u(0)=0, we have u(x)=(ax^{2}+bx)/2 for some integers a and b. ax^{2}+bx≥0 for all x. Thus 0<|b|≤a. So that (ax^{2}+bx)/2 returns only integers, b must be even if and only if a is even. So that (ax^{2}+bx)/2 returns 1, b=±(a-2). Thus x_{1} is 1 or -1. Without loss of generality, let b=a-2 and x_{1}=-1.
Because v(0)=0, we have v(y)=(cx^{2}+dx)/2 for some integers c and d. cx^{2}+dx≥0 for all y. Thus 0<|d|≤c. So that (cx^{2}+dx)/2 returns only integers, d must be even if and only if c is even.
If a>24, then (ax^{2}+bx)/2 has only two values less than 12: u(0)=0 and u(-1)=1.
If c>24, then (cy^{2}+dy)/2 has at most two values less than 12: v(0)=0 and v(1) or v(-1).
- If both a>24 and c>24,
- then f(x,y) generates at most four values between 0 and 11 (0, 1, v(±1), and v(±1)+1). Thus f is not surjective onto N.
- If a>24 and c≤24 or a≤24 and c>24,
- then the maximum number of values generated by f(x,y) between 0 and 11 is twice the number of values generated by v(y) or u(x), respectively. v(y) is the more general case. Of the 168 possible v(y) polynomials with c≤24, four generate the most integers, five [5]:
Four of these polynomials generate five integers in the range 0 to 11. But twice 5 is less than 12, so f is not surjective onto N.( 1 y^2 +1 y)/2: [5] #(0 1 ! 3 ! ! 6 ! ! ! 10 !) ( 2 y^2 +0 y)/2: [4] #(0 1 ! ! 4 ! ! ! ! 9 ! !) ( 2 y^2 +2 y)/2: [3] #(0 ! 2 ! ! ! 6 ! ! ! ! !) ( 3 y^2 +1 y)/2: [5] #(0 1 2 ! ! 5 ! 7 ! ! ! !) ( 3 y^2 +3 y)/2: [3] #(0 ! ! 3 ! ! ! ! ! 9 ! !) ( 4 y^2 +0 y)/2: [3] #(0 ! 2 ! ! ! ! ! 8 ! ! !) ( 4 y^2 +2 y)/2: [5] #(0 1 ! 3 ! ! 6 ! ! ! 10 !) ( 4 y^2 +4 y)/2: [2] #(0 ! ! ! 4 ! ! ! ! ! ! !) ( 5 y^2 +1 y)/2: [5] #(0 ! 2 3 ! ! ! ! ! 9 ! 11) ( 5 y^2 +3 y)/2: [4] #(0 1 ! ! 4 ! ! 7 ! ! ! !) ( 5 y^2 +5 y)/2: [2] #(0 ! ! ! ! 5 ! ! ! ! ! !) ...
- The last case is where a≤24 and c≤24.
- Computer enumeration of these cases finds no surjection onto N. The longest run from 0 is 0 through 20, generated by: (3x^{2}+x+7y^{2}+y)/2.
Prof. Poonen has suggested a simpler proof using quadratic reciprocity which rules out all quadratic polynomials.
Therefore there is no f(x,y) comprised of the sum of univariate polynomials u(x) and v(y) over the integers which is surjective onto the nonnegative integers.
Because j≥k>l, u and v will dominate w for sufficiently large |x| and |y| along any trajectory ax+by=0. Hence the previous asymptotic argument holds that f is asymptotically-sparse.
The contour of height H
is
A(H) = 4H^{1/2}(ln(H^{1/2})-ln(1)) = 2H^{1/2}ln(H)
A(H) does not grow as fast as H; so f(x,y)=x^{2}y^{2} is asymptotically-sparse.
This proof extends to all polynomials in
which x^{2}y^{2} is the only term having
the highest total-degree.
Theorem 1: Let f(x,y) be a polynomial function of two integer variables and q(x) be an integer-valued polynomial function of one integer variable. The set of values returned by f(x,y) for all integer pairs x,y is the same as the set of values returned by g(x,y)=f(x,y+q(x)) for all integer pairs x,y. The same is true for g(x,y)=f(x+q(y),y).If f(x,y)=x^{2}y^{2} and q(y)=y, then f(x+q(y),y)=x^{2}y^{2}+2xy^{3}+y^{4}, which is the same as x^{2}y^{2} with its x rows shifted progressively by y offsets of -1. As with this example, linear q(y) polynomials take homogeneous polynomials h(x,y) to homogeneous polynomials h(x+q(y),y) of the same total degrees.For any integer-valued polynomial function q(x), because x and y are independent, Q(x,y)=[x,y+q(x)] is a bijection from Z×Z to Z×Z; and f(x,y)=g(x,y-q(x)).
When q is not linear, the degree and homogeneity of polynomials are not preserved. For example, f(x,y)=x^{4}+y^{4} and g(x,y)=f(x,y+x^{2})=x^{4}+x^{8}+4x^{6}y+6x^{4}y^{2}+4x^{2}y^{3}+y^{4}. Notice that, although f(x,y)=x^{4}+y^{4} has been analyzed, g(x,y) is not covered by any of the cases analyzed above.
Can we distinguish nonlinearly-shifted polynomials from those which aren't? When f is a nonnegative polynomial of degree 2 or more in both x and y, and q(x) is a polynomial of degree 2 or more, the highest total-degree term of g(x,y)=f(x,y+q(x)) must be a power of x and not y; and the highest total-degree term involving y is linear in y and has a degree in x greater than 3 and a coefficient divisible by the exponent of the highest degree pure y term (by the Binomial Theorem).
This suggests a procedure for reducing nonlinearly-shifted polynomials:
Given g(x,y) with degree in x twice or more its degree in y, and whose highest total-degree term involving y is cnx^{m}y where m≥4 and c is a positive integer and n is the degree of y in g, replace g(x,y) by g(x,y-cx^{n}). This reduction step removes the leading term of q(x). Repeating this process will remove lower degree (but higher degree than 1) terms of q(x). As the result of a reduction, a pure x term may no longer be the highest degree term. The same process may then be carried out with the roles of x and y reversed, unwrapping layer after layer of nonlinear-shift until a minimal degree polynomial is achieved.The coefficient of the x^{m}y term needing to be a multiple of n leaves the great majority of high degree polynomials for which the nonlinear-shifting reduction procedure does not apply. But for the purposes of gaging asymptotic-sparseness, the coefficient can be non-integer. The reduction procedure is then:
Given g(x,y) with degree in x twice or more its degree in y, and whose highest total-degree term involving y is cx^{m}y where m≥4 and c is a real, replace g(x,y) by g(x,y-(c/n)x^{n}) where n is the degree of y in g. This reduction step removes the leading term of q(x). Repeating this process will remove lower degree (but higher degree than 1) terms of q(x). As the result of a reduction, a pure x term may no longer be the highest degree term. The same process may then be carried out with the roles of x and y reversed, unwrapping layer after layer of nonlinear-shift until a minimal degree polynomial is achieved.
Theorem 2: The sum of asymptotically-sparse polynomial functions is asymptotically-sparse.Let H be a large positive number and f(x,y) and g(x,y) be asymptotically-sparse polynomial functions. Because f and g return only nonnegative numbers, any x,y pair satisfying 0<f(x,y)+g(x,y)<H, also satisfies either 0<f(x,y)<H or 0<g(x,y)<H. Thus C(H,f+g)≤C(H,f)+C(H,g)<O(H); and f(x,y)+g(x,y) is asymptotically-sparse.
Theorem 3: The product of an asymptotically-sparse polynomial function and any nonnegative-valued polynomial function is asymptotically-sparse.
Let H be a large positive number and f(x,y) be an asymptotically-sparse polynomial function and g(x,y) be a polynomial function whose values are all nonnegative. Let L be the smallest nonzero value returned by g(x,y) for any integer values of x and y. Then g(x,y)/L will return 0 or values greater or equal to 1.
Any integer x,y pair satisfying 0<f(x,y)g(x,y)/L<H, also satisfies 0<f(x,y)<H. Thus C(H,fg/L)≤C(H,f)<O(H); hence f(x,y)g(x,y)/L is asymptotically-sparse; and by Lemma 2, Lf(x,y)g(x,y)/L=f(x,y)g(x,y) is asymptotically-sparse.
Copyright © 2008, 2009 Aubrey Jaffer. | Geometry |
I am a guest and not a member of the MIT Computer Science and Artificial Intelligence Laboratory. My actions and comments do not reflect in any way on MIT. | |
agj @ alum.mit.edu | Go Figure! |