Polynomial Points

E. F. Cornelius, Jr. College of Engineering and Science University of Detroit Mercy Detroit, MI 48221-3038 USA

                efcornelius@comcast.net

Phill Schultz School of Mathematics and Statistics The University of Western Australia Nedlands 6009 Australia

                schultz@math.uwa.edu.au

Abstract

We determine the infinite sequences (a_{k}) of integers that can be generated by polynomials with integral coefficients, in the sense that for each finite initial segment of length n there is an integral polynomial f_{n}(x) of degree < n such that a_{k} = f_{n}(k) for k = 0, 1, …, n − 1.

Let P be the set of such sequences and Π the additive group of all infinite sequences of integers. Then P is a subgroup of Π and Π/P ≅ ∏_{n=2}^{∞} ℤ/n!ℤ. The methods and results are applied to familiar families of polynomials such as Chebyshev polynomials and shifted Legendre polynomials.

The results are achieved by extending Lagrange interpolation polynomials to power series, using a special basis for the group of integral polynomials, called the integral root basis.

1 Introduction

In [4], we characterized the finite sequences (a_{1}, a_{2}, …, a_{n}) of integers for which there exists a polynomial f(x) ∈ ℤ[x] such that f(i) = a_{i} for i = 1, …, n. Let P_{n} denote the set of all such sequences, which we call polynomial sequences or polynomial points, and let ℤ^{n} be the set of all integer sequences of length n, where ℤ represents the ring of integers. Further, let ℤ[x] denote the ring of polynomials over the integers and ℤ[x]_{n} the group of integral polynomials of degree < n; let ℕ denote the natural numbers, and ℕ^{+} the positive integers. Finally, let ℚ denote the rationals.

The main results of [4] were the following two theorems:

Theorem 1.1. Let a = (a_{1}, a_{2}, …, a_{n}) ∈ ℤ^{n}. Let ℓ_{a}(x) be the Lagrange interpolation polynomial for the sequence a. Let B_{n} be the n × n rational matrix whose (i, j)–entry is \frac{(−1)^{i+j}}{i!} \binom{i}{j} for 0 ≤ i, j ≤ n − 1. The following are equivalent:

1. a ∈ P_{n}

2. ℓ_{a}(x) ∈ ℤ[x]_{n}

3. B_{n}a ∈ ℤ^{n}

Remarks 1.2. 1. In (3) above, a is treated as a column vector. Explicitly, a ∈ P_{n} if and only if for all i = 0, 1, …, n − 1,

∑_{j=0}^{i} \frac{(−1)^{i+j}}{j!(i − j)!}a_{j+1} is an integer.

2. The matrices B_{n}, as n varies, have the property that B_{m} is the upper left m×m corner of B_{n} for all m ≤ n.

3. It is easy to see that if a sequence a is not generated by a unique polynomial of degree < n, then it cannot be generated by any polynomial at all.

4. The theorem determines a duality between the coefficients of an integral polynomial and its initial sequence of values.

Theorem 1.3. P_{n} is a rank n subgroup of the free abelian group ℤ^{n}. P_{1} = ℤ, P_{2} = ℤ^{2} and for n > 2, ℤ^{n}/P_{n} ≅ ℤ/2!ℤ ⊕ ℤ/3!ℤ ⊕ ⋯ ⊕ ℤ/(n − 1)!ℤ.

The purpose of this paper is to extend these results to the infinite realm by replacing ℤ^{n} by Π = ∏_{i∈ℕ} ℤ_{i}, ℤ_{i} = ℤ, known as the Baer–Specker group. The three clauses of Theorem 1.1 suggest possibly different ways of extending the theorem by defining a suitable subgroup of Π as the analog of the P_{n}.

To simplify the notation, we index finite and infinite sequences, sums, products and matrices by natural numbers beginning with zero except where indicated. This slight change in notation from that in [4] does not of course make any substantive changes to the results of that paper.

If M is an n × n or ω × ω matrix over the integers, we write M = (m_{ij}) where m_{ij} is an expression representing an integer, i represents the row index and j the column index. In matrix–vector multiplication, the matrix acts on the left with the vector considered as a column. If necessary to render division by non–zero integers meaningful, we consider a torsion–free abelian group to be imbedded in its divisible hull [6, p 107].

The paper is organized as follows:

In Section 2, we define the integral root basis for ℤ[x] and use it to find stacked bases for ℤ^{n} and P_{n}, n ≥ 1. We describe the transition matrices between these bases and the standard bases, and apply them to determine a duality between the coefficients and the values of Lagrange interpolation polynomials. An interesting consequence is that for every positive integer n, there are infinitely many polynomials f(x) ∈ ℤ[x] of degree < n whose sequences of values (f(0), f(1), …, f(n − 1)) consist entirely of primes.

In the short Section 3, we deal in a similar manner with some special classes of integral polynomials, namely Chebyshev polynomials and shifted Legendre polynomials.

The major results of the paper are in Section 4. We expand integral polynomials to integral power series with respect to the integral root basis and extend the duality between coefficients and values mentioned above. We extend our earlier results from free groups of finite rank to Π and its subgroup P, the infinite analog of P_{n}. We then compute the factor group Π/P and the product of the factor groups ∏_{n∈ℕ^{+}} ℤ^{n}/P_{n}.

In Section 5, we apply these results to study various familiar subgroups of the Baer– Specker group, and describe the torsion part of Π/P.

Finally, in Section 6, we consider consider formal and analytic properties of power series with respect to the integral root basis.

2 The Integral Root Basis

The methodology in [4] is based upon the integral root basis of ℤ[x], R = {ρ_{j}(x) : j ∈ ℕ} where ρ_{0}(x) ≡ 1 and ρ_{j+1}(x) = ρ_{j}(x)(x − j) for j ∈ ℕ. Each initial segment of R, R_{n} = {ρ_{j}(x) : j = 0, 1, …, n − 1}, forms a basis for ℤ[x]_{n}, n ∈ ℕ^{+}, which we refer to as the integral root basis of ℤ[x]_{n}.

Let a be the initial segment of length m of an integer sequence b of length n, m ≤ n. The integral root basis has the property that the Lagrange interpolation polynomial for a is the initial segment of degree < m of the Lagrange interpolation polynomial for b, when the polynomials are expressed as linear combinations of that basis.

The valuation map v : ℤ[x] → ℤ^{n}, defined by

f(x) ↦ (f(0), f(1), …, f(n − 1))

has kernel ρ_{n}(x)ℤ[x]. When restricted to ℤ[x]_{n}, v determines an isomorphism of ℤ[x]_{n} with P_{n}, under which the integral root basis of ℤ[x]_{n} is mapped to a basis of P_{n} that we call the Gamma basis. Specifically, ρ_{j}(x) ↦ γ_{j} = ((0)_{j}, (1)_{j}, …, (n − 1)_{j}) where (i)_{j} is the falling factorial j!\binom{i}{j}. Since γ_{j} is divisible by j!, we may set α_{j} = γ_{j}/j! = (\binom{0}{j}, \binom{1}{j}, …, \binom{n−1}{j}). Consequently, we obtain a basis of ℤ^{n}, which we call the Alpha basis. The Alpha and Gamma bases are stacked bases [3; 6, Lemma 15.4] that readily reveal the structure of ℤ^{n}/P_{n}.

The transition matrix from the Alpha basis for ℤ^{n} to the standard basis is Pascal’s matrix A_{n} [5], a lower-triangular matrix, the (i, j)–entry of which is \binom{i}{j}, i, j = 0, 1, …, n − 1. A_{n} is easily seen to be invertible with lower-triangular inverse whose (i, j)–entry is (−1)^{i+j}\binom{i}{j}, i, j = 0, 1, …, n − 1.

As the dimension increases from n to n + 1, the valuation map induces a canonical injection of P_{n} into P_{n+1}, under which the Gamma basis of P_{n} is mapped into the first n elements of the Gamma basis of P_{n+1}, which, together with the image of ρ_{n}(x), form the Gamma basis of P_{n+1}. Conversely, the Gamma basis of P_{n} is the canonical projection of the first n elements of the Gamma basis of P_{n+1} into P_{n}. Similarly, the Alpha basis of ℤ^{n+1} is derived from the Alpha basis of ℤ^{n}, and conversely. Consequently, no confusion arises from using the symbols α_{j} and γ_{j} without reference to dimension.

The matrix C_{n} whose columns are the Gamma basis of P_{n} is not integrally invertible for n > 2, but is invertible over ℚ. If D_{n} is the diagonal matrix whose jth diagonal entry is j!, for j = 0, 1, …, n−1, then C_{n} = A_{n}D_{n}. Moreover the matrix B_{n} defined in the Introduction is C_{n}^{−1} = D_{n}^{−1}A_{n}^{−1}. Note that for m ≤ n, the top left m × m corner of A_{n} is A_{m} and similarly for C_{n} and C_{m}.

The following result is implicit in [4]. It is convenient to spell it out explicitly, since it provides the motivation for generalizations to the infinite case.

Proposition 2.1. Let a = (a_{0}, a_{1}, …, a_{n−1}) ∈ ℤ^{n} and let f(x) = ∑_{i=0}^{n−1} a_{i}ρ_{i}(x). Then C_{n}a is the sequence (f(0), f(1), …, f(n − 1)).

Conversely, let a ∈ ℤ^{n} and let b = B_{n}a. Then b is the sequence of (rational) coefficients with respect to the integral root basis of the Lagrange interpolation polynomial ℓ_{a}(x) of a.

Proof. For j = 0, …, n−1, the jth of column of C_{n} is the sequence of values (ρ_{j}(0), ρ_{j}(1), …, ρ_{j}(n − 1)) of the jth element of the integral root basis of ℤ[x]_{n}. Hence C_{n}a is the sequence of values of f(x) at 0, …, n − 1.

Conversely, the coefficients of ℓ_{a}(x), with respect to the integral root basis, are precisely the terms of the sequence B_{n}a.

Proposition 2.1 can be expressed in terms of the standard basis S_{n} = {x^{i} : i = 0, …, n − 1} of ℤ[x]_{n}. Let L_{n} be the n × n matrix

(i^{j}), i, j = 0, 1, …, n − 1, with 0^{0} = 1,

and let M_{n} be the n × n matrix

(∑_{k=0}^{n−1}(−1)^{i+k} [\begin{matrix}k \\ i \end{matrix}] (k)_{j}) , i, j = 0, …, n − 1,

where the [\begin{matrix}k \\ i \end{matrix}] are the Stirling cycle numbers, also known as Stirling numbers of the first

kind [10, pp 65–68].

Corollary 2.1. Let f(x) = ∑_{i=0}^{n−1} c_{i}x^{i} ∈ ℤ[x]_{n} and let a be its sequence of values. Then a = L_{n}c, where c = (c_{0}, …, c_{n−1}).

Conversely, let a ∈ ℤ^{n}. Then c = M_{n}a is the (rational) sequence of coefficients of the Lagrange interpolation polynomial for a, with respect to the standard basis of ℤ[x]_{n}. Moreover, a ∈ P_{n} if and only if c ∈ ℤ^{n}.

Proof. The expansion of the integral root basis polynomials ρ_{i}(x) as polynomials in the standard basis and vice versa are computed in [10, p 65, (40) and (41)]. The corresponding transition matrices appear in slightly different form on page 66 of the same work.

The transition matrix from R_{n} to S_{n} is K_{n} = ((−1)^{i+j} [\begin{matrix}j \\ i \end{matrix}]). Its inverse is J_{n} = (\begin{cases}j \\ i \end{cases}\})

[10, p 67, (43)], where the \begin{cases}j \\ i \end{cases}\} are Stirling subset numbers, also known as Stirling numbers

of the second kind.

Then L_{n} = B_{n}J_{n} and M_{n} = K_{n}C_{n}, so the result follows from Proposition 2.1.

The integral root basis has important properties not shared by the standard basis:

1. Its evaluation provides stacked bases for P_{n} ⊆ ℤ^{n} for every positive integer n, as shown above.

2. Every integral coefficient power series, expressed with respect to the integral root basis, converges at every non–negative integer. We exploit this property in Section 4 below.

An interesting consequence of Proposition 2.1 concerns the representation of primes by polynomials, a topic of current interest in number theory. Green and Tao [9] have shown that for every positive integer n, there are infinitely many arithmetic progressions of length n consisting entirely of primes. Since every arithmetic progression of length n is a polynomial point, P_{n} abounds with such sequences. A weaker but still interesting result can be obtained with only the techniques employed here.

Proposition 2.2. For each n ∈ ℕ^{+}, there are infinitely many sequences of primes in P_{n}.

Proof. Fix n ∈ ℕ^{+} and let a = (a_{i} : i = 0, …, n−1) be a sequence of primes in the arithmetic progression {1 + kn! : k ∈ ℕ}. There are infinitely many choices of such sequences, by Dirichlet’s theorem on primes in arithmetic progressions.

Each a_{i} = 1 + k_{i}n! for some k_{i} ∈ ℕ. Let k = (k_{i}) and let 1 = (1, 1, …, 1)^{T} (n terms) so that B_{n}a = B_{n}1 + n!B_{n}k. By Proposition 2.1, B_{n}1 = (1, 0, …, 0)^{T} and by Remark 1.2 (1), B_{n}k ∈ ℤ^{n}. Hence B_{n}a ∈ ℤ^{n}, so by Theorem 1.1, a ∈ P_{n}. Hence a is v(f(x)) for some polynomial f(x) of degree < n.

3 Special polynomials

The foregoing techniques also can be used to study familiar families of integral polynomials. For example, let

T_{n}(x) = \frac{n}{2} ∑_{r=0}^{⌊n/2⌋} \frac{(−1)^{r}}{n − r} \binom{n − r}{r}(2x)^{n−2r}

denote the nth Chebyshev polynomial, a useful tool in approximation theory, solution of differential equations and numerical analysis. Let T [x] denote the subgroup of ℤ[x] that these polynomials generate. Let T [x]_{n} = T [x] ∩ ℤ[x]_{n} be the subgroup of the polynomials in T [x] of degree < n. For n ∈ ℕ^{+}, let T P_{n} denote the image in ℤ^{n} of T [x]_{n} under the valuation map v.

Proposition 3.1. With the notation above, Chebyshev polynomials have these properties:

1. {1, x, …, 2^{n−1}x^{n}, … } is a basis of T [x].

2. ℤ[x]_{n}/T [x]_{n} ≅ P_{n}/T P_{n} ≅ ⊕_{i=2}^{n−1}ℤ/2^{i−1}ℤ

3. ℤ^{n}/T P_{n} ≅ ⊕_{i=2}^{n−1}ℤ/2^{i−1}i!ℤ

Proof. (1) It is clear that {1} and {1, x} are bases for T_{1}(x) and T_{2}(x), respectively. From this fact and the recurrence satisfied by the Chebyshev polynomials, T_{n+1}(x) = 2xT_{n}(x)−T_{n−1}(x), the general result follows.

(2) The first isomorphism is induced by v, and the second follows from (1).

(3) follows from (2) and Theorem 1.3.

Similarly, let

L_{n}(x) = (−1)^{n} ∑_{k=0}^{n} \binom{n}{k}\binom{n + k}{k}(−x)^{k}

denote the nth shifted Legendre polynomial, used in the solution of certain differential equations that arise in physics. Let L[x] denote the subgroup of ℤ[x] that these polynomials generate, and let L[x]_{n} = L[x] ∩ ℤ[x]_{n} be the subgroup of polynomials in L[x] of degree < n. For n ∈ ℕ^{+}, let LP_{n} denote the image in ℤ^{n} of L[x]_{n} under the valuation map v.

Proposition 3.2. With the notation above, Legendre polynomials have these properties:

1. {1, 2x, …, (2n)!/(n!)^{2}x^{n}, … } is a basis of L[x].

2. ℤ[x]_{n}/L[x]_{n} ≅ P_{n}/LP_{n} ≅ ⊕_{i=1}^{n−1}ℤ/(2i)!/(i!)^{2}ℤ

3. ℤ^{n}/LP_{n} ≅ ⊕_{i=1}^{n−1}ℤ/(2i)!/i!ℤ

Proof. (1) A straightforward induction argument reveals that the kth coefficient of L_{n}(x) is a multiple of (2k)!/(k!)^{2}.

(2) is clear from (1).

(3) In general, if S[x]_{n} is a subgroup of Z[x]_{n} that satisfies S[x]_{n} = ⊕_{i=0}^{n−1}⟨k_{i}x^{i}⟩ for k_{i} ∈ ℤ, i = 0, …, n − 1, then ℤ^{n}/v(S[x]_{n}) ≅ ⊕_{i=0}^{n−1}ℤ/k_{i}i!ℤ, where v is the valuation map.

4 Extensions to infinite sequences of integers

The first step in generalizing Theorems 1.1 and 1.3 to the infinite case is to extend the valuation map v to v^{∗} : ℤ[x] → Π by v^{∗} : f(x) ↦ (f(n) : n ∈ ℕ). Let P_{ω} denote the image of v^{∗} in Π and let Σ denote those sequences in Π that are eventually zero; Σ is a countable free subgroup of Π. Further, let P_{∗} denote the pure subgroup of Π generated by P_{ω}.

Next, extend the Gamma basis elements to elements of Π by the valuation map v^{∗} : ρ_{n}(x) ↦ γ_{n} = ((k)_{n} : k ∈ ℕ) for all n ∈ ℕ. Similarly, extend the Alpha basis elements to α_{n} = γ_{n}/n! = (\binom{k}{n} : k ∈ ℕ). These extensions yield:

Theorem 4.1. 1. The valuation map v^{∗} : f(x) ↦ (f(n) : n ∈ ℕ) is an isomorphism of ℤ[x] onto P_{ω}.

2. P_{ω} is a countable free subgroup of Π and the extended Gamma basis is a basis of P_{ω}.

3. P_{∗} also is a countable free subgroup of Π and the extended Alpha basis is a basis of P_{∗}.

4. The extended Alpha and Gamma bases are stacked bases [3] of P_{∗} and P_{ω} and P_{∗}/P_{ω} ≅ ⊕_{n≥2}ℤ/n!ℤ.

Proof. (1) The valuation map v^{∗} is epic by definition of P_{ω} and v^{∗} is certainly monic, since only the zero polynomial has infinitely many zeros. Thus v^{∗} is an isomorphism.

(2) Clearly ℤ[x] ≅ Σ ≅ P_{ω}, so that P_{ω} is a countable free subgroup of Π. Since v^{∗} is an isomorphism, it carries the integral root basis of ℤ[x] to a basis for P_{ω}, which by definition is the Gamma basis.

(3) P_{∗} is countable because it is the pure subgroup of Π generated by the countable subgroup P_{ω} [6, p 116], and it is free because all countable subgroups of Π are free. The independence of the Alpha basis elements of P_{∗} follows from the fact that α_{n} = γ_{n}/n! for all n ∈ ℕ and the γ_{n} are themselves independent.

All that remains is to demonstrate that the α_{n} span P_{∗}. From n!α_{n} = γ_{n} it follows that each α_{n} ∈ P_{∗}. Suppose that mx = j_{0}γ_{0} + ⋯ + j_{k}γ_{k} ∈ P_{ω} is a linear combination of the γ_{n}, so that x ∈ P_{∗} by purity.

Then mx = j_{0}0!α_{0} + ⋯ + j_{k}k!α_{k}. From the finite dimensional case, we know that m divides each term j_{n}n! in this sum, since α_{0}, …, α_{k} is a basis of ℤ^{k+1}. Thus x = (j_{0}0!/m)α_{0}+ ⋯ + (j_{k}k!/m)α_{k}, so that the α_{n} span P_{∗} and hence form a basis.

(4) The Alpha and Gamma bases are stacked so that P_{∗}/P_{ω} ≅ ⊕_{n∈ℕ} ℤ/n!ℤ. Because 0! = 1 = 1!, the first two factors are degenerate, leaving the required result.

The ω × ω matrix whose columns are the extended Alpha basis is the infinite Pascal matrix A = (\binom{i}{j} : i, j ∈ ℕ) which has integral inverse A^{−1} = ((−1)^{i+j}\binom{i}{j} : i, j ∈ ℕ)[1, p 2]. Similarly, the matrices C_{n} can be extended to an ω × ω matrix C, the top left n × n corner of which, for all n ∈ ℕ^{+}, is C_{n}; and the matrices B_{n} can be extended to an ω × ω matrix B, the top left n × n corner of which, for all n ∈ ℕ^{+}, is B_{n}; then C = B^{−1}. Likewise, the diagonal matrices D_{n} can be extended to a diagonal ω × ω matrix D, so that C = AD. Since A, B, C and D are row finite, they act by left multiplication on Π. B of course is not integral.

We proceed to generalize Theorems 1.1 and 1.3. Let a = (a_{i} : i ∈ ℕ) ∈ Π and define the (formal) power series with respect to the integral root basis with coefficient sequence a to be the expression, r_{a}(x) = ∑_{i∈ℕ} a_{i}ρ_{i}(x). Let ℤ[[x]]_{R} denote the group under addition of coefficients of all such power series so that ℤ[[x]]_{R} ≅ Π. Let ℤ[x]_{R} denote those elements of ℤ[[x]]_{R} which have only finitely many non–zero coefficients, i.e., the polynomials in ℤ[[x]]_{R}. As defined here, neither ℤ[x]_{R} nor ℤ[[x]]_{R} is a ring.

Note that for each n ∈ ℕ, ρ_{i}(n) = 0 for all i > n, so that r_{a}(n) is an integer. Thus the sequence of values (r_{a}(0), r_{a}(1), …) is well–defined. As a result, the valuation map ν : ℤ[[x]]_{R} → Π given by r_{a}(x) ↦ (r_{a}(0), r_{a}(1), …) is a monomorphism of ℤ[[x]]_{R} into Π. Analogously with the finite dimensional case, we call the image of ν the group of polynomial points P. Since each f(x) ∈ ℤ[x] can be expressed uniquely as a polynomial in ℤ[x]_{R}, and conversely, ν maps ℤ[x]_{R} isomorphically onto P_{ω} ⊂ P.

We thank the referee for pointing out that P is the closure of P_{ω} with respect to the product topology on Π where ℤ has the discrete topology. For discussion and application of this metrizable topology, see [2].

Let ρ denote the sequence of polynomials (ρ_{0}(x), ρ_{1}(x), …), considered as a row vector, and for all a ∈ Π, let ℓ_{a}(x) = ρBa. Since B is not integral, ℓ_{a}(x) need not lie in ℤ[[x]]_{R}, but nevertheless a = (ℓ_{a}(0), ℓ_{a}(1), …); i.e., ℓ_{a}(x) is an infinite extension of the Lagrange interpolation polynomials with respect to the integral root basis. The following lemma demonstrates that the definition of ℓ_{a}(x) in the infinite case is consistent with that in the finite case.

Lemma 4.1. Let a = (a_{i} : i ∈ ℕ) ∈ Π and for all n ≥ 1, let a_{n} = (a_{0}, a_{1}, …, a_{n−1}). Then the sum of the first n terms of ℓ_{a}(x) is ℓ_{a_{n}}(x).

Proof. The sum of the first n terms of ρBa is

(ρ_{0}(x), ρ_{1}(x), …, ρ_{n−1}(x))B_{n}a_{n},

which equals ℓ_{a_{n}}(x) by [4, Lemma 2.2].

Lemma 4.2. Let a, b ∈ Π. The following are equivalent:

1. Cb = a = (r_{b}(0), r_{b}(1), …)

2. Ba = b

Proof. Both parts follow immediately from Corollary 2.1 and Lemma 4.1.

The following corollary also is immediate.

Corollary 4.1. Let a ∈ Π. Then

1. Ca ∈ P, and P = CΠ

2. a ∈ P if and only if Ba ∈ Π

The following theorems are the promised infinite analogs of Theorems 1.1 and 1.3.

Theorem 4.2. Let a = (a_{i} : i ∈ ℕ) ∈ Π. The following are equivalent:

1. a ∈ P

2. ℓ_{a}(x) ∈ ℤ[[x]]_{R}

3. Ba ∈ Π

Proof. The equivalence of (1) and (3) is just Corollary 4.1 (2).

For a ∈ Π, a = (ℓ_{a}(0), ℓ_{a}(1), …). For a ∈ P, each intial segment a_{n} = (a_{0}, a_{1}, …, a_{n−1}) ∈ P_{n}, so by Theorem 1.1 (2), ℓ_{a_{n}}(x) ∈ ℤ[x]_{n}. That all the coefficients of ℓ_{a}(x) are integral follows from Lemma 4.1.

Theorem 4.3. Π/P ≅ ∏_{n≥2} ℤ/n!ℤ

Proof. Since the lower-triangular matrix A is integrally invertible with columns forming the Alpha basis {α_{n} : n ∈ ℕ}, Π is the product of the α_{n}’s, Π = ∏_{n∈ℕ}⟨α_{n}⟩ [7, p 164, definitions only]. Similarly, by Corollary 4.1 (1), P = CΠ with the columns of the lower-triangular non-singular matrix C forming the Gamma basis {γ_{n} : n ∈ ℕ}, so that P is also a product, P = ∏_{n∈ℕ}⟨γ_{n}⟩. Since γ_{n} = n!α_{n} for all n ∈ ℕ, Π/P ≅ ∏_{n∈ℕ} ℤ/n!ℤ. Because 0! = 1 = 1!, the first two factors are degenerate, leaving the required result.

The following lemma enables us to describe the group ∏_{n∈ℕ^{+}} ℤ^{n}/P_{n}.

Lemma 4.3. For all i ∈ ℕ^{+}, let G_{i} be an abelian group and n_{i} a positive integer such that n_{i} < n_{i+1}. Then ∏_{j∈ℕ^{+}} ⨁_{i=1}^{n_{j}} G_{i} ≅ ∏_{j∈ℕ^{+}} ∏_{i∈ℕ^{+}} G_{i}.

Proof. We construct a 1–1 correspondence between the constituent groups G_{i} on the left and those on the right, in such a way that corresponding groups have the same subscript. The identity maps on the G_{i}’s then induce the desired isomorphism between the group on the left (call it L) and the group on the right (call it R).

The proof is essentially combinatorial, and we abuse notation for the sake of simplicity. We display L and R schematically:

L  =  \begin{matrix}G_{1} & ⋯ & G_{n_{1}} \\ G_{1} & … & G_{n_{1}} & … & G_{n_{2}} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ G_{1} & … & G_{n_{1}} & … & G_{n_{2}} & … & G_{n_{k}} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \end{matrix}

and

R  =  \begin{matrix}G_{1} & … & G_{n_{1}} & … & G_{n_{2}} & … & G_{n_{k}} & … \\ G_{1} & … & G_{n_{1}} & … & G_{n_{2}} & … & G_{n_{k}} & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & … \\ G_{1} & … & G_{n_{1}} & … & G_{n_{2}} & … & G_{n_{k}} & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \end{matrix}

Now operate on the array L by “pushing all the columns to the top” to form the array R. This establishes the required isomorphism.

Application of Theorems 1.3 and 4.3 and Lemma 4.3 immediately yields the following result.

Theorem 4.4.

∏_{n∈ℕ^{+}} ℤ^{n}/P_{n} ≅ ∏_{n∈ℕ^{+}} ⨁_{k=1}^{n} ℤ/(k − 1)!ℤ ≅ ∏_{n∈ℕ^{+}} ∏_{k∈ℕ^{+}} ℤ/(k − 1)!ℤ ≅ ∏_{n∈ℕ^{+}} Π/P

5 Subgroups of the Baer–Specker group

The Baer–Specker group Π is a well known source of examples and counter-examples in abelian group theory; see for example [6, Section 19] and [2]. We now relate some of these results to our theory of polynomial points.

Let B denote the subgroup of Π consisting of the bounded sequences of integers; B is a basic subgroup of Π in the sense that it is a pure, free subgroup with divisible quotient [2, p 5771]. Recall that Σ is the subgroup of sequences that are eventually 0; by [2, Theorem 1.5], Σ is a direct summand of B. Furthermore, by [2, p 5770], the quotient Π/Σ is the direct sum of a divisible group and a reduced algebraically compact group, with the reduced summand being isomorphic to the direct product of countably many copies of the groups of p-adic integers for all primes p.

The following results show the relation between Theorems 4.3 and 1.1 and illustrate the power and utility of the integral root basis. Recall that C is the ω ×ω matrix whose columns are the extended Gamma basis.

Theorem 5.1. In the notation above,

1. CΣ = P_{ω}

2. Multiplication by C induces an isomorphism Π/Σ → P/P_{ω}.

3. B ∩ P consists of the constant sequences.

4. (B + P)/P is torsion–free.

Proof. (1) Let a ∈ P_{ω}, say a = (f(k) : k ∈ ℕ), f(x) ∈ ℤ[x]. Write f = c_{0}ρ_{0} +⋯+c_{n}ρ_{n} with respect to the integral root basis and let c = (c_{0}, …, c_{n}, 0, …). Then c ∈ Σ and Cc = a. Thus P_{ω} ⊆ CΣ.

Conversely, let c = (c_{0}, …, c_{n}, 0, …) ∈ Σ and define f(x) ∈ ℤ[x]_{n+1} by f = c_{0}ρ_{0} + ⋯ + c_{n}ρ_{n}. Then the values (f(k)), k ∈ ℕ, form the sequence Cc. Thus CΣ ⊆ P_{ω}, and the two sets are equal.

(2) By Corollary 4.1 (1), P = CΠ, and from (1) above, P_{ω} = CΣ so that C induces an isomorphism Π/Σ → P/P_{ω}.

(3) The constant sequences, being the values of degree zero polynomials, are clearly in B ∩ P. No other sequence occurs there because the values of polynomials of non–zero degree are unbounded.

(4) B is separable so that the constant sequences B ∩ P = (1, 1, …)^{T} ℤ are a direct summand, B = (B ∩ P) ⊕ B′ say. Thus (B + P)/P ≅ B/(B ∩ P) ≅ B′ ⊆ Π.

Recall that a group H is said to be algebraically compact if H is a direct summand of every group G that contains H as a pure subgroup [6, Section 38]. Every bounded group is algebraically compact. In the p–adic topology of a group G, p a prime, the subgroups p^{n}G, n ∈ ℕ, form a base of neighborhoods of 0 [6, p 30]. A group G is cotorsion if every extension of G by a torsion–free group splits; i.e., if Ext(J, G) = 0 for every torsion–free group J [6, Section 54]. An algebraically compact group is cotorsion, but the converse need not be true.

With this terminology, Π/P and its torsion subgroup can be described as follows:

Theorem 5.2. 1. Π/P is a reduced, algebraically compact group and so is of the form Π/P = ∏ A_{p}, the product over all primes p, where each A_{p} is complete in its p–adic topology and is uniquely determined by Π/P.

2. Let T = ⊕T_{p} be the torsion subgroup of Π/P, where T_{p} is the p–primary component of T for all primes p. Then T_{p} is the torsion subgroup of A_{p} and is isomorphic to the torsion completion of ⊕_{k∈ℕ^{+}} (⊕_{2^{ℵ_{0}}}ℤ/p^{k}ℤ). Thus T is not cotorsion and so is not a direct summand of Π/P.

Proof. (1) Π/P is reduced and algebraically compact because all of the product components ℤ/n!ℤ in Theorem 4.3 are [6, Corollary 38.3]. As a result, it is of the form Π/P = ∏ A_{p} where each A_{p} is complete in its p–adic topology and is uniquely determined [6, Proposition 40.1].

(2) By [7, Theorem 68.4], each T_{p} is torsion–complete since it is the torsion part of the algebraically compact group A_{p}. Hence by the results of [7, Section 68], T_{p} is uniquely determined by any basic subgroup. Thus it remains to determine the Ulm–Kaplansky invariants of T_{p} for each prime p.

For each prime p, the p–component of ∏_{n≥2} ℤ/n!ℤ consists of those sequences a = (a_{n} + n!ℤ) for which there is a positive integer k such that for all n, p^{k}a_{n} is a multiple of n!. For each fixed k, ∏_{n≥2} ℤ/n!ℤ has 2^{ℵ_{0}} independent elements of order p^{k}. For example, let {F_{ν} : ν < 2^{ℵ_{0}}} be a family of 2^{ℵ_{0}} almost disjoint infinite subsets of ℕ; i.e., any two intersect in a finite set. For each ν < 2^{ℵ_{0}} let a_{ν} have n–component (n!/p^{k}) + n!ℤ for each n ≥ p^{k} in F_{ν}, and zero otherwise. Then the a_{ν} are independent elements of the product of order p^{k}. Since |T_{p}| ≤ |Π| = 2^{ℵ_{0}}, T_{p} is the torsion completion of ⊕_{k∈ℕ^{+}} (⊕_{2^{ℵ_{0}}}ℤ/p^{k}ℤ) [6, Section 40].

Since T is unbounded and reduced, it cannot be algebraically compact [6, Corollary 40.3] or cotorsion [6, Corollary 54.4], so it is not a summand of Π/P, since any direct summand of an algebraically compact group is itself algebraically compact and hence cotorsion [6, p 159].

6 Analytic properties of the power series and Pascal’s matrix

Recall from Section 4 the definition of ℤ[[x]]_{R} as the group of power series with respect to the integral root basis; that is, elements of ℤ[[x]]_{R} are formal expressions of the form r_{a}(x) = ∑_{n∈ℕ} a_{n}ρ_{n}(x) with a = (a_{n}) ∈ Π.

We have seen that the elements of ℤ[[x]]_{R} are the infinite analogs of the integral Lagrange interpolation polynomials. We also have seen that there is a natural map Π → ℤ[[x]]_{R} → Π defined by a ↦ r_{a}(x) ↦ (r_{a}(n)). The image is P and as in the proof of Theorem 4.3, Π = ∏_{j∈ℕ}⟨α_{j}⟩ and P = ∏_{j∈ℕ}⟨j!α_{j}⟩ where the α_{j} are the elements of the extended Alpha basis which form the columns of the infinite Pascal matrix A.

Through use of the observation that A can be obtained from the transpose U^{T} of the matrix (with respect to the standard basis) of the translation U : ℤ[x] → ℤ[x], x ↦ x + 1, computations involving A can be greatly simplified. More precisely, let U(t) denote the matrix of the translation x ↦ x + t. Then U(t) = (u_{ij}(t)) where u_{ij}(t) = \binom{j}{i}t^{j−i}, i.e.,

U(t) = [\begin{matrix}1 & t & t^{2} & t^{3} & … \\ 0 & 1 & 2t & 3t^{2} & … \\ 0 & 0 & 1 & 3t & … \\ 0 & 0 & 0 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋯ \end{matrix}]

so that U = U(1).

Since for any numbers m and n, U(m)U(n) = U(m + n), we have for all n ∈ ℤ, U^{n} = U(n). Then defining A(t) = U(t)^{T}, we find for all n ∈ ℤ that A(n) = U(n)^{T} = (U^{n})^{T} = (U^{T})^{n}. In particular, A^{−1} = U(−1)^{T}. Thus computations with A are easier than they first appear.

As with ℤ[[x]]_{R} considered above, there is a natural isomorphism Π → ℤ[[x]] defined by a ↦ ∑_{i∈ℕ} a_{i}x^{i}. In particular, the image of the Alpha basis can be expressed in terms of the standard basis by α_{j}(x) = ∑_{i∈ℕ} \binom{i}{j}x^{i}. It is interesting to note that α_{j}(x) = x^{j}/(1 − x)^{j+1}.

Proposition 6.1. With the notation above, α_{j}(x) = x^{j}/(1 − x)^{j+1}

Proof.

∑_{i∈ℕ} \binom{i}{j}x^{i} = \frac{x^{j}}{j!} \frac{d^{j}}{dx^{j}} ∑_{i∈ℕ}x^{i} = \frac{x^{j}}{j!} \frac{d^{j}}{dx^{j}} (\frac{1}{1 − x}) = \frac{x^{j}}{(1 − x)^{j+1}}

We thank the referee for this short proof, which appeared in [8].

Proposition 6.2. Let F(x) = ∑_{j∈ℕ} a_{j}x^{j} ∈ ℤ[[x]]. Then formally, F(x) = 1/(1−x) ∑_{j∈ℕ} b_{j}(x/(1− x))^{j}, with a = (a_{j}) and b = (b_{j}) = A^{−1}a.

Proof. We view a and b as infinite column vectors. Since Π = ∏_{j∈ℕ}⟨α_{j}⟩ with respect to the Alpha basis and Π ≅ ℤ[[x]], ℤ[[x]] = ∏_{j∈ℕ}⟨α_{j}(x)⟩, where α_{j}(x) = ∑_{i∈ℕ} \binom{i}{j}x^{i} for all j ∈ ℕ.

The coefficients of F(x) with respect to the Alpha basis are given by A^{−1}a = b, so

F(x) = ∑_{j∈ℕ}b_{j}α_{j}(x) = ∑_{j∈ℕ}b_{j} \frac{x^{j}}{(1 − x)^{j+1}} = \frac{1}{1 − x} ∑_{j∈ℕ}b_{j} (\frac{x}{1 − x})^{j}

Remark 6.1. Although the expansion described in Proposition 6.2 is formal, the series may actually converge analytically. In particular, by the ratio test, each α_{j}(x) = ∑ \binom{i}{j}x^{i} converges on the unit disc |x| < 1. Moreover, we can construct a single variable generating function for the entire infinite Pascal matrix as follows:

From the definition of α_{j}(x) and Proposition 6.1,

1. α_{j}(x) = ∑_{i∈ℕ} \binom{i}{j}x^{i} = \frac{x^{j}}{(1 − x)^{j+1}} . Sum equations (1) over j to obtain

2. ∑_{j∈ℕ} α_{j}(x) = ∑_{j∈ℕ} ∑_{i∈ℕ} \binom{i}{j}x^{i} = ∑_{j∈ℕ} \frac{x^{j}}{(1 − x)^{j+1}} . Now reverse the order of summa-

tion in the middle term of (2) and factor out 1/(1 − x) on the right to obtain

3. ∑_{i∈ℕ} ∑_{j∈ℕ} \binom{i}{j}x^{i} = \frac{1}{1 − x} ∑_{j∈ℕ} (\frac{x}{1 − x})^{j}. From (3), factor out x^{i} and use \binom{i}{j} = 0 for j > i on the left, and the sum of a geometric series on the right to conclude that

4. ∑_{i∈ℕ} x^{i} ∑_{j=0}^{i} \binom{i}{j} = \frac{1}{1 − x} (\frac{1}{1 − \frac{x}{1−x}} ) = \frac{1}{1 − 2x}. Substituting 2^{i} for ∑_{j=0}^{i} \binom{i}{j} yields

5. ∑_{j∈ℕ} α_{j}(x) = ∑_{i∈ℕ}(2x)^{i} = \frac{1}{1 − 2x} and the series converges on the smaller disc |x| < 1/2.

To explicate Pascal’s infinite matrix from 1/(1 − 2x), simply reverse the steps: \frac{1}{1 − 2x} → ∑_{i∈ℕ} x^{i}2^{i} → ∑_{i∈ℕ} x^{i} ∑_{j=0}^{i} \binom{i}{j} → ∑_{i∈ℕ} ∑_{j∈ℕ} \binom{i}{j}x^{i}. With this technique, two variables are not required to generate the matrix; compare [10, p 93, Ex. 12 and solution p 494].

References

[1] P. Barry, On integer-sequence-based constructions of generalized Pascal triangles, J. Integer Sequences, 9 (2006), Paper # 06.2.4.

[2] A. Blass and J. Irwin, Free subgroups of the Baer-Specker group, Comm. Alg., 29 (2001), 5769–5794.

[3] J. M. Cohen and H. Gluck, Stacked bases for modules over principal ideal domains, J. Algebra 14 (1970), 493–505.

[4] E. F. Cornelius Jr. and P. Schultz, Sequences generated by polynomials, Amer. Math. Monthly, 115 (2008) 154–158.

[5] G. S. Call and D. J. Velleman, Pascal’s matrices, Amer. Math. Monthly, 100 (1993), 372–376.

[6] L. Fuchs, Infinite Abelian Groups, Vol. 1, Academic Press, New York and London, 1970.

[7] L. Fuchs, Infinite Abelian Groups, Vol. 2, Academic Press, New York and London, 1973.

[8] M. Golomb and A. N. ’t Woord, A disguised zeta function, Amer. Math. Monthly, 103 (1993), 703–704.

[9] B. Green and T. Tao, The primes contain arbitrarily long arithmetic progressions, http://arxiv.org/PS cache/math/pdf/0404/0404188.pdf, 2006.

[10] D. E. Knuth, Fundamental Algorithms, Vol.1 of The Art of Computer Programming, Addison-Wesley, 2nd ed., 1973.

2000 Mathematics Subject Classification: Primary 20K21, 20K25, 20K30; Secondary 13F20, 15A36. Keywords: Mixed abelian groups, Lagrange interpolation polynomials, integral polynomials, integral root basis, Baer–Specker group, Pascal’s matrix.

Received October 30 2006; revised version received March 22 2007. Published in Journal of Integer Sequences, April 2 2007. Minor revision, April 17 2008.

Return to Journal of Integer Sequences home page.