Comm. Algebra 36 (3) (2008) 1110-1114

REMARKS ON POLYNOMIAL PARAMETRIZATION

OF SETS OF INTEGER POINTS

Sophie Frisch

Abstract. If, for a subset S of ℤ^{k}, we compare the conditions of being parametrizable (a) by a single k-tuple of polynomials with integer coefficients, (b) by a single k-tuple of integer-valued polynomials and (c) by finitely many k-tuples of polynomials with integer coefficients (variables ranging through the integers in each case), then a ⇒ b (obviously), b ⇒ c, and neither implication is reversible. Condition

(b) is equivalent to S being the set of integer k-tuples in the range of a k-tuple of polynomials with rational coefficients, as the variables range through the integers. Also, we show that every co-finite subset of ℤ^{k} is parametrizable a single k-tuple of polynomials with integer coefficients.

If f = (f_{1}, …, f_{k}) ∈ (ℤ[x_{1}, …, x_{n}])^{k} is a k-tuple of polynomials with integer coefficients in several variables, we call range or image of f the range of the function f: ℤ^{n} ⟶ ℤ^{k} defined by substitution of integers for the variables; and likewise for a k-tuple of integer-valued polynomials (f_{1}, …, f_{k}) ∈ (Int(ℤ^{n}))^{k}, where

Int(ℤ^{n}) = {g ∈ ℚ[x_{1}, …, x_{n}] | ∀a ∈ ℤ^{n} : g(a) ∈ ℤ}.

If S ⊆ ℤ^{k} is the range of f = (f_{1}, …, f_{k}), we say that f parametrizes S.

We want to compare two kinds of polynomial parametrization of sets of integers or k-tuples of integers: by integer-valued polynomials and by polynomials with integer coefficients. Consider for instance the set of integer Pythagorean triples: it takes two triples of polynomials with integer coefficients, (c(a^{2} − b^{2}), 2cab, c(a^{2} + b^{2})) and (2cab, c(a^{2} − b^{2}), c(a^{2} + b^{2})) to parametrize the set of integer triples (x, y, z)

2000 Mathematics Subject Classification. Primary 11D85; Secondary 11C08, 13F20. Key words and phrases. polynomial parametrization, integer-valued polynomial, range, image

of a polynomial, polynomial mapping..

This note was written while the author was enjoying hospitality at Université de Picardie, Amiens.

Typeset by AMS-TEX

satisfying x^{2} + y^{2} = z^{2}, but the same set can be parametrized by a single triple of integer-valued polynomials [2]. Another reason for studying parametrization by integer-valued polynomials are various sets of integers in number theory and combinatorics that come parametrized by integer-valued polynomials in a natural way, for example, the polygonal numbers

p(n, k) = \frac{(n − 2)k^{2} − (n − 4)k}{2}

where p(n, k) represents the k-th n-gonal number [3].

Now for our comparison of different kinds of polynomial parametrization of sets of integer points.

Theorem. For a set^{1} S ⊆ ℤ^{k} consider the conditions:

(A) S is parametrizable by a k-tuple of polynomials with integer coefficients, i.e., there exists f = (f_{1}, …, f_{k}) in (ℤ[x_{1}, …, x_{n}])^{k} (for some n) such that S = f(ℤ^{n}).

(B) S is parametrizable by a k-tuple of integer-valued polynomials, i.e., there exists g = (g_{1}, …, g_{k}) in (Int(ℤ^{m}))^{k} (for some m) such that S = g(ℤ^{m}).

(C) S is a finite union of sets, each parametrizable by a k-tuple of polynomials with integer coefficients.

(D) S is the set of integer k-tuples in the range of a k-tuple of polynomials with rational coefficients, as the variables range through the integers, i.e., there exists h = (h_{1}, …, h_{k}) in (ℚ[x_{1}, …, x_{r}])^{k} (for some r) such that S = h(ℤ^{r}) ∩ ℤ^{k}.

Then the following implications hold:

\begin{matrix}A \\ ⇓ \\ B & ⇔ & D \\ ⇓ \\ C \end{matrix}

and C ⇏ B, B ⇏ A.

Of the implications in the theorem, A ⇒ B and B ⇒ D are trivial. We now show the nontrivial ones.

For D ⇔ B, we first construct, for any f ∈ ℚ[x_{1}, …, x_{n}], a parametrization of f^{−1}(ℤ) by polynomials with integer coefficients, which we then plug into f to obtain an integer-valued polynomial.

1Correction after publication: we need S ≠ ∅. Thanks to Youssef Fares for pointing this out.

REMARKS ON POLYNOMIAL PARAMETRIZATION OF SETS OF INTEGER POINTS 3

Lemma 1. If q_{1}, …, q_{r} are powers of different primes and for each i, S_{i} is a union of residue classes of q_{i}ℤ^{k} in ℤ^{k} then ⋂_{i=1}^{r} S_{i} ⊆ ℤ^{k} is parametrizable by a k-tuple of polynomials with integer coefficients.

Proof. We will first parametrize a union of residue classes of qℤ^{k} in ℤ^{k} for a single prime power q. Let a_{0}, …, a_{s} ∈ ℤ^{k} be representatives of the residue classes in question,^{2} and let t such that 2^{t} > s. Expressing l ∈ {0, 1, …, s} in base 2, we obtain a sequence of digits [l]_{2} = (ε_{0}^{(l)}, …, ε_{t−1}^{(l)}). Let m be a natural number such that z^{m} is either congruent to 0 or to 1 mod q for every integer z. Then

(qy_{1}, …, qy_{k}) + ∑_{l=0}^{s} a_{l} ∏_{i=0}^{t−1} e_{i}^{(l)}(x_{i}), with e_{i}^{(l)}(x_{i}) = \{ \begin{matrix}x_{i}^{m} & if ε_{i}^{(l)} = 1 \\ 1 − x_{i}^{m} & if ε_{i}^{(l)} = 0 \end{matrix}

parametrizes ⋃_{l=0}^{s}(qℤ^{k} + a_{l}).

Now let q_{1}, …, q_{r} be powers of different primes, and for 1 ≤ i ≤ r let S_{i} be a union of residue classes mod q_{i}ℤ^{k} parametrized by a k-tuple of polynomials g_{i}. By Chinese remainder theorem there are c_{1}, …, c_{r} with c_{i} ≡ 1 mod q_{i} and c_{i} ≡ 0 mod q_{j} for j ≠ i. We may choose c_{1}, …, c_{r} with gcd(c_{1}, …, c_{r}) = 1. (E.g. by applying Dirichlet’s theorem on primes in arithmetic progressions to find primes p_{i} ∈ b_{i} + q_{i}ℤ, where b_{i} is the inverse of ∏_{j≠i} q_{j} mod q_{i}, and setting c_{i} = p_{i} ∏_{j≠i} q_{j}, with p_{1}, …, p_{r} different primes coprime to all q_{j}.) Finally, we set h = ∑_{i=1}^{r} c_{i}g_{i}. Then h parametrizes ⋂_{i=1}^{r} S_{i}. □

Lemma 2 (B ⇔ D). Let S ⊆ ℤ^{k}. Then there exists a k-tuple of integer-valued polynomials whose range is S if and only if there exists a k-tuple of polynomials with rational coefficients such that S is the set of integer points in its range (as the variables range through the integers).

Proof. The “only if” direction (that’s B ⇒ D) is trivial. For the other direction, D ⇒ B, first consider the case k = 1 of a single rational polynomial f(x_{1}, …, x_{n}) = g(x_{1}, …, x_{n})/c with g(x_{1}, …, x_{n}) ∈ ℤ[x_{1}, …, x_{n}] and c ∈ ℕ.

Let T = {a ∈ ℤ^{n} | f(a) ∈ ℤ}. If c = q_{1} · . . . · q_{r} is the factorization of c into prime powers and T_{i} = {a ∈ ℤ^{n} | g(a) ∈ q_{i}ℤ}, then T = ⋂_{i=1}^{r} T_{i}. For each i, T_{i} is a union of residue classes of q_{i}ℤ^{n}. Hence T is parametrizable by an n-tuple of polynomials (h_{1}, …, h_{n}) ∈ ℤ[\underline{x}]^{n}. Substituting h_{i} for x_{i} in f, we obtain an integer-valued polynomial p(\underline{x}) = f(h_{1}(\underline{x}), …, h_{n}(\underline{x})) whose range is exactly the set of integers in the range of f.

In the case k > 1, the argument for the set of integer points in the range of a ktuple of rational polynomials (f_{1}, …, f_{k}), with f_{j}(x_{1}, …, x_{n}) = g_{j}(x_{1}, …, x_{n})/c, is similar, using T_{i} = {a ∈ ℤ^{n} | ∀j : g_{j}(a) ∈ q_{i}ℤ}. □

2Correction after publication: we need s = 2^{t} − 1. Thanks to Arnaud Bodin for pointing this out. No problem, we just repeat some of the a_{i}.

Lemma 3 (B ⇒ C). If a set S ⊆ ℤ^{k} is parametrizable by a single k-tuple of integer-valued polynomials, it is parametrizable by a finite number of k-tuples of polynomials with integer coefficients.

Proof. First consider an integer-valued polynomial f(x) in one variable of degree d. Recall that the binomial polynomials \binom{x}{n} = \frac{x(x−1)...(x−n+1)}{n!} form a basis of the ℤ-module Int(ℤ), so that there exist integers a_{0}, …, a_{d} with f = ∑_{n=0}^{d} a_{n}\binom{x}{n}.

It is easy to see that \binom{cy+j}{n} ∈ ℤ[y] for any j whenever c is a common multiple of 1, 2, …, n. Therefore for c = lcm(1, 2, …, d) and arbitrary j,

f_{j}(y) = f(cy + j) = ∑_{n=0}^{d} a_{n}\binom{cy + j}{n}

is in ℤ[y]; and clearly the image of f is the union of the images of f_{j}, for j = 0, …, c − 1.

Regarding integer-valued polynomials in several variables, products of binomial polynomials in one variable each ∏_{i=1}^{n} \binom{x_{i}}{n_{i}} form a basis of Int(ℤ^{n}) [1, Prop. XI.1.12]. So, if f ∈ Int(ℤ^{n}) is of degree d_{i} in x_{i}, and c_{i} is a common multiple of 1, 2, …, d_{i} then for each choice of j_{1}, …, j_{n}, f_{j_{1},... ,j_{n}} = f(c_{1}y_{1}+j_{1}, …, c_{n}y_{n}+j_{n}), as a ℤ-linear combination of polynomials ∏_{i=1}^{n} \binom{c_{i}y_{i}+j_{i}}{n_{i}} ∈ ℤ[y_{1}, …, y_{n}], is a polynomial with integer coefficients and the image of f is the union of the images of the polynomials f_{j_{1},... ,j_{n}} with 0 ≤ j_{m} < c_{m}.

The same argument shows that the image of a vector of polynomials (g_{1}, …, g_{k}) in (Int(ℤ^{n}))^{k} is the union of the images of c_{1} · . . . · c_{n} vectors of polynomials in (ℤ[y_{1}, …, y_{n}])^{k}, where c_{i} = lcm(1, 2, …, d_{i}), d_{i} denoting the highest degree of any g_{m} in the i-th variable. □

Remark. B ⇏ A and C ⇏ B: Finite sets of more than one element witness C ⇏ B. The set of integer Pythagorean triples mentioned above is parametrizable by a single triple of polynomials in Int(ℤ^{4}), but not by any triple of polynomials with integer coefficients in any number of variables [2] therefore B ⇏ A.

This completes the proof of the theorem. The remainder of this note is devoted to the fact that every co-finite set is parametrizable by a single vector of polynomials with integer coefficients. (I was asked by Leonid Vaserstein in connection with a remark in [4] to publish a proof of this.)

Proposition. Let S ⊆ ℤ^{k} such that ℤ^{k} \ S is finite. Then there exists a k-tuple of polynomials with integer coefficients whose range is S.

Proof. We may suppose that the complement of S in ℤ^{k} is contained in a cuboid ∏_{i=1}^{k}[0, n_{i}] = [0, n_{1}] × … × [0, n_{k}], with n_{i} a non-negative integer for 1 ≤ i ≤ k. We will first construct a polynomial vector whose image is ℤ^{k} \ ∏_{i=1}^{k}[0, n_{i}], by induction on k. k = 1: for n ≥ 0, the range of the polynomial f below is ℤ \ [0, n]:

f = −x_{5}^{2}(x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + x_{4}^{2} + 1) + (1 − x_{5}^{2})(x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + x_{4}^{2} + n + 1).

Once we have a polynomial vector (f_{1}, …, f_{k−1}) parametrizing ℤ^{k−1} \ ∏_{i=1}^{k−1}[0, n_{i}] and a polynomial f with range ℤ \ [0, n_{k}], we set

g_{i} = (1 + x_{i}^{2})(1 − z^{2})^{2m}f_{i} + z^{2}x_{i} (1 ≤ i < k)
and g_{k} = (1 + y^{2})z^{2m}f + (1 − z^{2})y

with m sufficiently large, see below, and check that the range of (g_{1}, …, g_{k}) is ℤ^{k} \ ∏_{i=1}^{k}[0, n_{i}]: For z = x_{1} = … = x_{k−1} = 0 we get (f_{1}, …, f_{k−1}, y), while for z ∈ {1, −1} and y = 0, we have (x_{1}, …, x_{k−1}, f), so that (g_{1}, …, g_{k}) certainly covers the desired range.

Also, we stay within the desired range. Indeed, for z = 0, the first k − 1 coordinates become (1 + x_{i}^{2})f_{i}, and their image lies within the image of (f_{1}, …, f_{k−1}), and for z ∈ {1, −1} the last coordinate is (1 + y^{2})f, whose image is contained in the image of f.

Let n = max_{i}{n_{i}}. By choosing m sufficiently large such that

|(1 + x^{2})(1 − z^{2})^{2m}| > |z^{2}x| + n and |(1 + y^{2})z^{2m}| > |(1 − z^{2})y| + n

for all z with |z| ≥ 2 and all values of x and y, we make sure that (g_{1}, …, g_{k}) stays within the desired range also for |z| ≥ 2.

Having constructed a polynomial vector with range ℤ^{k} \ ∏_{i=1}^{k}[0, n_{i}], we can add additional values to the range, one by one, as follows.

If g = (g_{1}, …, g_{k}) is a polynomial vector whose image contains ℤ^{k} \ ∏_{i=1}^{k}[0, n_{i}], but does not contain 0 ∈ ℤ^{k}, and c is in ∏_{i=1}^{k}[0, n_{i}], let

h = w^{2t}g + (1 − w^{2})c,

with t such that 2^{2t−2} > max_{i}{n_{i}} then the range of h is exactly the range of g together with the (possibly additional) value c. If the value c = 0 ∈ ℤ^{k} is to be added to the range of g, it must be added last. □

References

1. Paul-Jean Cahen and Jean-Luc Chabert, Integer-valued polynomials, Amer. Math. Soc., Providence, RI, 1997.

2. Sophie Frisch and Leonid Vaserstein, Parametrization of Pythagorean triples by a single triple of polynomials, J. Pure Appl. Algebra 212 (2008) 271–274.

3. Melvyn B. Nathanson, Additive number theory. The classical bases., Springer, New York, 1996.

4. Leonid Vaserstein, Polynomial parametrization for the solutions of Diophantine equations and arithmetic groups, to appear in Ann. of Math..

Institut für Mathematik A, Technische Universität Graz, A-8010 Graz, Austria

   frisch@tugraz.at