in: Applications of Fibonacci Numbers, Vol. 7 (Graz 1996 Conf.) G. E. Bergum, A. N. Philippou, A. F. Horadam (eds.), Kluwer 1998, pp 133 – 144

BINOMIAL COEFFICIENTS GENERALIZED

WITH RESPECT TO A DISCRETE VALUATION

Sophie Frisch

1. Introduction. There is a fine Theorem of Kummer on the power to which a prime appears in the prime factorization of a binomial coefficient:

Theorem. (Kummer [10]) If p is a prime, then the exact power of p dividing the binomial coefficient \binom{n}{k} is equal to the number of carries that occur in the addition of k and n − k in base p arithmetic.

One objective of this paper is to show an analogue of this result for a certain generalization of the binomial coefficients that arises naturally in the study of integer-valued polynomials. Recall that a polynomial with coefficients in the quotient field K of an integral domain D is called integer-valued if f(d) ∈ D for all d ∈ D. The starting point of this generalization is the following well known fact.

Fact 1. (folklore) Let (x)_{n} = x(x − 1) … (x − n + 1), (x)_{0} = 1. The binomial polynomials

\binom{x}{n} = \frac{(x)_{n}}{n!} (n ∈ ℕ_{0})

form a basis of the free ℤ-module Int(ℤ) = {f ∈ ℚ[x] | f(ℤ) ⊆ ℤ}.

To be able to generalize the falling factorials (x)_{n} = x(x − 1) … (x − n + 1), we need a sequence with nice distribution properties with respect to a discrete valuation to take the place of the sequence of natural numbers.

Before we make this precise, we state the second objective of this paper, namely to show that in certain cases, in particular when R is the ring of algebraic integers in a number field, these sequences can be chosen to enumerate R bijectively. For this, we introduce ℤ-bases with special properties with respect to a prime p ∈ ℤ for the ring of algebraic integers in a number field in section 5.

binomial coefficients

2. Definitions. Integer-valued polynomials are much studied objects; we mention only the seminal work by Pólya [16] and Ostrowski [15], and, as more recent examples, the papers by Cahen [1, 2], Chabert [3], McQuillan [13, 14] and Gilmer, Heinzer and Lantz [6]. We use the common notation of Int(R, D) for {f ∈ K[x] | f(R) ⊆ D}, where R is a subset of the quotient field K of an integral domain D, and Int(D) for Int(D, D). The technique of constructing integer-valued polynomials by replacing the natural numbers in the definition of the binomial polynomials by a specially chosen sequence of ring elements goes back to Pólya [16]. We first define sequences in arbitrary commutative rings. (We will specialize to discrete valuation rings later.) All (finite or infinite) sequences are indexed by an initial segment N of ℕ = {1, 2, …} or ℕ_{0} = {0, 1, 2, …} and quantifiers over indices of such a sequence are always assumed to range over precisely the index-set.

Definition. For a set I of ideals in a commutative ring R we define an I-sequence in R to be a sequence (a_{n}) of elements in R with the property

∀I ∈ I ∀n, m ( a_{n} ≡ a_{m} mod I ⟺ [R: I] | n − m ).

(Any infinite [R:I] we regard as dividing 0, but no other integer.) We define a homogeneous I-sequence to be one with the additional property

∀I ∈ I ∀n ≥ 1 ( a_{n} ∈ I ⟺ [R: I] | n ).

Note that every I-sequence with a_{0} = 0 is homogeneous. Also note that a sequence in R is an I-sequence if and only if every [R: I] consecutive elements form a complete system of residues mod I for every I ∈ I of finite index, and the elements of the sequence are pairwise incongruent modulo every I ∈ I of infinite index.

It is not hard to see [4, Proposition 2.1] that I-sequences exist for every descending chain of ideals I = {I_{n} | n ∈ ℕ}, I_{n+1} ⊆ I_{n}, in a commutative ring R. We can therefore count on having an I-sequence with respect to the set I of all ideals of R, whenever it forms a descending chain. This is our motivation for turning to discrete valuation rings.

Recall that a discrete valuation on a field K is a function v from K \ {0} onto ℤ (supplemented by the convention v(0) = ∞) satisfying v(ab) = v(a) + v(b) and v(a + b) ≥ min(v(a), v(b)). A discrete valuation ring is a ring R_{v} = {a ∈ K | v(a) ≥ 0}, where v is a discrete valuation on K. It is a local ring with maximal ideal M_{v} = {a ∈ K | v(a) > 0} (see, e.g. [12]).

For an important class of rings including all Dedekind rings and all unique factorization domains, R is the intersection of a family of discrete valuation rings in its quotient field, R = ⋂_{v∈V} R_{v}. For Dedekind rings, the relevant discrete valuation rings are the localizations at maximal ideals, for UFDs the localizations at principal prime ideals. One can then study Int(R) = ⋂_{v∈V} Int(R, R_{v}) by first considering each Int(R, R_{v}) individually, which we will do here, and then combining the information to obtain results on Int(R), which we will omit, since the combinatorial properties we are interested in only appear in Int(R, R_{v}).

If R is an infinite subring of a discrete valuation ring, there is a straightforward generalization (defined below) of the binomial polynomials. They form a basis of the R_{v}-module Int(R, R_{v}) (cf. [4], Theorem 2.8).

Definition. If R is an infinite subring of a discrete valuation ring R_{v}, we define a vsequence for R to be an I-sequence with I = {M_{v}^{n} ∩ R | n ∈ ℕ}. In other words, (a_{n})_{n∈N} ⊆ R is a v-sequence for R if and only if for all n ∈ ℕ and all i, j ∈ N,

v(a_{i} − a_{j}) ≥ n ⟺ [R: M_{v}^{n} ∩ R] | i − j .

If [R: M_{v}^{n} ∩ R] is infinite, the elements of a v-sequence must be pairwise incongruent mod M_{v}^{n} ∩ R.

Notation. From now on, R_{v} will be a discrete valuation ring (with value group ℤ and v(0) = ∞), M_{v} its maximal ideal, K its quotient field and R (unless otherwise specified) an infinite subring of R_{v}. For brevity, we write P_{n} for M_{v}^{n} ∩ R, from this point on.

Note that since R is infinite and by the Krull Intersection Theorem ⋂_{n=0}^{∞} P^{n} = (0), the indices [R: P_{n}] grow arbitrarily large or are infinite from some n on.

Definition. The falling factorials with respect to a v-sequence (a_{n})_{n≥0} are

⟨x⟩_{n} = (x − a_{0})(x − a_{1}) … (x − a_{n−1})

and the binomial polynomials constructed from the v-sequence (a_{n})_{n≥0} are

b_{0} = 1  and  b_{n}(x) = \frac{⟨x⟩_{n}}{⟨a_{n}⟩_{n}} for n > 0.

These binomial polynomials were introduced in [4]. They generalize a construction of Pólya [16] that has also been employed by Cahen [2], Gunji and McQuillan [7, 13] and others.

If R = ℤ, p is a prime and v_{p} is p-adic valuation, then the classical v_{p}-sequence for ℤ is a_{n} = n. The corresponding binomial polynomials are b_{k}(x) = \binom{x}{k}, and b_{k}(a_{n}) = \binom{n}{k}. Therefore, if (a_{n}) is a v-sequence and b_{k} is the binomial polynomial of degree k constructed from it, we may regard b_{k}(a_{n}) as a generalization of \binom{n}{k}.

3. A carry theorem. As before, R is an infinite subring of a discrete valuation ring R_{v} and P_{n} = M_{v}^{n} ∩ R. For j, k ∈ ℕ_{0}, let r_{j}(k) be the remainder of k under integral division by [R: P_{j}] if [R: P_{j}] is finite, and r_{j}(k) = k if [R: P_{j}] is infinite.

Lemma 1. Let (a_{n})_{n=0}^{N} be a v-sequence for R and (b_{n})_{n=0}^{N} the binomial polynomials constructed from it. Then for all r ∈ R and all k = 0, …, N,

v(b_{k}(r)) = |{j ≥ 1 | for some l < r_{j}(k), r ≡ a_{l} mod P_{j}}|

and, in particular, b_{k} ∈ Int(R, R_{v}).

Proof. v(b_{k}(r)) = v(⟨r⟩_{k}) − v(⟨a_{k}⟩_{k}). For any s ∈ R, v(⟨s⟩_{k}) = ∑_{i=0}^{k−1} v(s − a_{i}), so

v(⟨s⟩_{k}) = ∑_{j≥1}|{i | 0 ≤ i < k, v(s − a_{i}) ≥ j}| = ∑_{j≥1}|{i | 0 ≤ i < k, s ≡ a_{i} mod P_{j}}|.

Since every [R:P_{j}] consecutive terms of a v-sequence form a complete set of representatives mod P_{j}, |\{i | 0 ≤ i < k, s ≡ a_{i} mod P_{j}\}| is either [\frac{k}{[R:P_{j}]}] or [\frac{k}{[R:P_{j}]}] + 1. The extra “1” appears for each j such that s ≡ a_{i} mod P_{j} for some i with 0 ≤ i < r_{j}(k), and never appears at all if s = a_{k}. □

We now introduce the number system associated to the valuation v that will appear in our generalization of Kummer’s theorem. We call it v-ary number system but note that it depends not only on v, but also on the subring R of R_{v}. It is the Cantor (or mixed-radix) number system to the basis b_{n} = [R : P_{n}], 0 ≤ n < ∞, cf. [8] 192 ff. Since the indices [R: P_{n}] either grow arbitrarily large while remaining finite (the non-degenerate case of our number system) or are finite at first, at least for P_{0} = R, and infinite from some n on (the degenerate case), every n ∈ ℕ_{0} has a unique representation n = ∑_{l=0}^{∞} ε_{l}(n)[R : P_{l}], with 0 ≤ ε_{l}(n) < [P_{l} : P_{l+1}]. (We use the convention that 0 · [R: P_{l}] = 0 even if [R: P_{l}] = ∞.)

Definition. If n = ∑_{l=0}^{∞} ε_{l}(n)[R : P_{l}], where 0 ≤ ε_{l}(n) < [P_{l} : P_{l+1}], we call ε_{l}(n) the l-th digit of n in the v-ary number system. Addition of numbers in v-ary arithmetic is performed by addition with carry on the vectors of digits, where a carry from position l to position l + 1 occurs when the l-th digit reaches or exceeds [P_{l} : P_{l+1}].

If [R_{v}: M_{v}] is finite, then [P_{l}: P_{l+1}] divides [M_{v}^{l}: M_{v}^{l+1}] = [R_{v}: M_{v}]; if R_{v}/M_{v} is infinite, however, the digits need not be uniformly bounded or bounded at all. In the degenerate case, if N is maximal with [R : P_{N}] finite, the N-th digit may be arbitrarily large, while for all l > N, ε_{l}(n) = 0 for all n.

If n = ∑_{l=0}^{∞} ε_{l}(n)[R: P_{l}], we set r_{j}(n) = ∑_{l=0}^{j−1} ε_{l}(n)[R: P_{l}]. This is consistent with our earlier use of r_{j}(n) as the remainder of n under integral division by [R: P_{j}], if [R: P_{j}] is finite, and n otherwise.

Theorem 1. Let (a_{i})_{i=0}^{n} be a v-sequence for R and for 0 ≤ k ≤ n let b_{k} be the binomial polynomial of degree k constructed from it. Then

(a) v(b_{k}(a_{n})) = |{l ≥ 1 | r_{l}(k) > r_{l}(n)}|,

(b) v(b_{k}(a_{n})) is the number of carries occurring in the addition of k and n − k in v-ary arithmetic,

(c) v(b_{k}(a_{n})) = 0 ⟺ ∀ l ε_{l}(k) ≤ ε_{l}(n) in the v-ary number system.

Proof. The condition a_{n} ≡ a_{i} mod P_{l} with 0 ≤ i < r_{l}(k) is equivalent to r_{l}(n) < r_{l}(k), such that (a) follows from Lemma 1. For all l, either r_{l}(k) + r_{l}(n − k) = r_{l}(n), in which case no carry occurs at the l-th digit in the addition of k and n − k, or r_{l}(k) + r_{l}(n − k) = [R: P_{l+1}] + r_{l}(n), in which case a carry does occur. In the first case, r_{l}(k) ≤ r_{l}(n); in the second case, r_{l}(k) > r_{l}(n) since r_{l}(n − k) < [R : P_{l+1}]. Thus (b) follows from (a). Since ∀ l ε_{l}(k) ≤ ε_{l}(n) is clearly the criterion for no carry to occur, (c) follows from (b). □

Note that Theorem 1 (b) implies v(b_{k}(a_{n})) = v(b_{n−k}(a_{n})) for all k ≤ n.

In the case where R = ℤ, v = v_{p} and a_{n} = n, we retrieve Kummer’s theorem that v_{p}(\binom{n}{k}) is equal to the number of l ≥ 1 such that the remainder of k mod p^{l} is strictly greater than the remainder of n mod p^{l}, which number is also equal to the number of carries in the addition of k and n − k in base p arithmetic [10; pp 115–119]. For an account of related facts about the classical binomial coefficients, see [17], for a different generalization, [9]. There is another version of Kummer’s theorem that also carries over to generalized binomial coefficients in some cases.

Variant of Kummer’s Theorem. Let p be a prime, and 0 ≤ k ≤ n. Then

v_{p} (\binom{n}{k}) = \frac{1}{p − 1} ∑_{l≥0} ε_{l}(k) + ε_{l}(n − k) − ε_{l}(n),

where ε_{l}(j) means the l-th digit of j in base p.

We look at falling factorials: If (a_{i})i=0^{N} is a v-sequence and α_{i} = a_{N} − a_{N−i}, i = 0, …, N, then (α_{i})i=0^{N} is a v-sequence with α_{0} = 0, and therefore homogeneous. Let (α_{i})i=0^{N} be a homogeneous v-sequence and n ≤ N, then α_{1} … α_{n} is a v-analogue of n!, since, for n = ∑_{l=0}^{m} ε_{l}(n)[R: P_{l}]

v(α_{1} … α_{n}) = ∑_{j=1}^{m} [\frac{n}{[R: P_{j}]}] = ∑_{j=1}^{m} ∑_{l=j}^{m} ε_{l}(n)[P_{j} : P_{l}] = ∑_{l=1}^{m} ε_{l}(n) ∑_{j=1}^{l}[P_{j} : P_{l}].

If [P_{j}: P_{j+1}] = q for all j (for instance, if R_{v} is the localization of R at a maximal ideal of finite index) this further simplifies to

∑_{l=1}^{m} ε_{l}(n)\frac{(q^{l} − 1)}{q − 1} = \frac{1}{q − 1} (∑_{l=1}^{m} ε_{l}(n)q^{l} − ∑_{l=1}^{m} ε_{l}(n)) = \frac{1}{q − 1} (n − ∑_{l=0}^{m} ε_{l}(n)) ,

and we can generalize the above variant of Kummer’s theorem:

Theorem 2. Let (a_{i})_{i=0}^{n} be a v-sequence for R and for 0 ≤ k ≤ n let b_{k} be the binomial polynomial of degree k constructed from it. If [P_{l} : P_{l+1}] = q for all l ≥ 0 then

v(b_{k}(a_{n})) = \frac{1}{q − 1} ∑_{l≥0} ε_{l}(k) + ε_{l}(n − k) − ε_{l}(n) ,

where ε_{l}(j) denotes the l-th digit of j in base q.

Proof. This follows from the preceding calculations, since b_{k}(a_{n}) =

= \frac{∏_{i=0}^{n−1}(a_{n} − a_{i})}{∏_{i=0}^{k−1}(a_{k} − a_{i}) ∏_{i=k}^{n−1}(a_{n} − a_{i})} = \frac{∏_{i=1}^{n}(a_{n} − a_{n−i})}{∏_{i=1}^{k}(a_{k} − a_{k−i}) ∏_{i=1}^{n−k}(a_{n} − a_{n−i})},

and α_{i} = a_{n} − a_{n−i} (0 ≤ i ≤ n), β_{i} = a_{k} − a_{k−i} (0 ≤ i ≤ k) and γ_{i} = a_{n} − a_{n−i} (0 ≤ i ≤ n − k) are v-sequences, and homogeneous ones, since α_{0} = β_{0} = γ_{0} = 0. □

4. Enumerating R Bijectively as an I-Sequence. It is often possible to arrange all of R bijectively as a v-sequence. This has applications to interpolation by integer-valued polynomials.

Theorem 3. If R is a countably infinite ring and I = {I_{n} | n ∈ ℕ} a descending chain of ideals of finite index in R with ⋂_{n∈ℕ} I_{n} = (0) then there exists an I-sequence which enumerates R bijectively.

Proof. Consider the elements of R labeled by natural numbers. (Such a label will be called the “number” of an element, not to be confused with the index at which it occurs in the sequence.) As the first step of constructing our sequence, we put a_{0} = 0 and assign the different residue classes of I_{1} other than I_{1} itself to the indices i = 1, …, [R: I_{1}] − 1 in any order. We then define a_{i} to be the element with the smallest number in the residue class of I_{1} assigned to i.

Assuming a_{0}, …, a_{[R:I_{n−1}]−1} already defined, we define a_{[R:I_{n−1}]}, …, a_{[R:I_{n}]−1} as follows. For 0 ≤ i ≤ [R: I_{n−1}] − 1, assign the residue classes of I_{n} contained in a_{i} + I_{n−1} but different from a_{i} +I_{n} to the [I_{n−1} :I_{n}]−1 indices i+j[R:I_{n−1}] with 0 < j ≤ [I_{n−1} :I_{n}]−1; then for k = [R : I_{n−1}], …, [R : I_{n}] − 1, define a_{k} to be the element with the smallest number in the residue class of I_{n} assigned to index k.

This procedure inductively defines an I-sequence with the property that every sequence element a_{i} with i < [R : I_{n}] is the element of lowest number in its residue class mod I_{n}. Since every [R: I_{n}] consecutive sequence elements form a complete set of representatives mod I_{n}, every element of smallest number in its residue class mod I_{n} occurs among a_{0}, …, a_{[R:I_{n}]−1}.

⋂_{I∈I} I = (0) together with R being infinite implies that every I-sequence is injective. Given r ∈ R, we show that it appears in the sequence: Since ⋂_{n∈ℕ} I_{n} = (0), there exists N ∈ ℕ, such that r is not congruent mod I_{N} to any element of smaller number. r is therefore the element of smallest number in its residue class mod I_{N}, and will appear among the first [R: I_{N}] sequence elements. □

Theorem 3 implies that every countably infinite subring R of a discrete valuation ring R_{v} can be arranged as a v-sequence, on condition that all intersections of powers of M_{v} with R are of finite index in R. For the application to interpolation, we use the fact that every function from the set A = {a_{i} | i ≥ 0} enumerated by a v-sequence (a_{i})_{i=0}^{∞} to R_{v} can be represented as an infinite R_{v}-linear combination of the binomial polynomials b_{n} constructed from the sequence. (This infinite linear combination reduces to a finite sum upon evaluation at a_{i}, since b_{n}(a_{i}) = 0 for all n > i.)

Fact 2. Let R be an infinite subring of a discrete valuation ring R_{v}, (a_{i})_{i=0}^{∞} a v-sequence for R, A = {a_{i} | i ≥ 0} and

b_{0} = 1  and  b_{n}(x) = \frac{∏_{i=0}^{n−1}(x − a_{i})}{∏_{i=0}^{n−1}(a_{n} − a_{i})} for n > 0

the binomial polynomials constructed from the sequence. Then every function f: A → R_{v} has a unique representation f(x) = ∑_{i=0}^{∞} d_{i}b_{i}(x) with d_{i} ∈ R_{v}.

Proof. From Lemma 1 we know that the b_{n} are in Int(R, R_{v}). By the definition of the binomial polynomials, b_{n}(a_{n}) = 1 and b_{n}(a_{i}) = 0 for n > i.

Every infinite R_{v}-linear combination of the b_{i}, f = ∑_{i=0}^{∞} d_{i}b_{i}, represents a function f: A → R_{v}, since it reduces to the finite sum f(a_{n}) = d_{n} + ∑_{i=0}^{n−1} d_{i}b_{i}(a_{n}) upon evaluation at a_{n} and the b_{i} are in Int(R, R_{v}).

Conversely, given a function f: A → R_{v}, we can define coefficients d_{i} ∈ R_{v} inductively by d_{0} = f(a_{0}) and d_{n} = f(a_{n}) − ∑_{i=0}^{n−1} d_{i}b_{i}(a_{n}), and find that ∑_{i=0}^{∞} d_{i}b_{i} represents the function f. □

We can now give a short proof of the possibility of interpolation by integer-valued polynomials on a discrete valuation ring. (A more involved proof, which, however, has the advantage of determining, for each set of arguments in R, the minimal d such that there exists an interpolating polynomial of degree at most d for every choice of values in R_{v}, will appear in [5].)

Corollary to Theorem 3. Let R be a countably infinite subring of a discrete valuation ring R_{v} with the property that for all n, P_{n} = M_{v}^{n} ∩ R is of finite index in R. Then for all r_{1}, …, r_{m} (distinct) in R and all s_{1}, …, s_{m} ∈ R_{v} there exists f ∈ Int(R, R_{v}) with f(r_{j}) = s_{j} for 1 ≤ j ≤ m.

Proof. By the Krull Intersection Theorem, ⋂_{k=0}^{∞} P_{k} = (0). Therefore there exists n ∈ ℕ such that r_{1}, …, r_{m} are pairwise incongruent mod P_{n}. We show that r_{1}, …, r_{m} can be embedded in a v-sequence as elements of index < [R:P_{n}]. In the proof of Theorem 3, choose the initial numbering of the elements of R in such a way that r_{j} is element number j; each r_{j} is then the element of smallest number in its residue class mod P_{n} and will therefore occur among the first N = [R: P_{n}] elements of the v-sequence (a_{i})_{i=0}^{∞} so constructed. Now let b_{k} be the binomial polynomial of degree k constructed from (a_{i})_{i=0}^{∞}. Let A = {a_{i} | i ≥ 0}. If we consider any function φ: A → R_{v} satisfying φ(r_{j}) = s_{j} for 1 ≤ j ≤ m, it has a representation as ∑_{i=0}^{∞} d_{i}b_{i} with d_{i} ∈ R_{v} by Fact 2. Since b_{k}(a_{i}) = 0 for k > i, the values φ(a_{i}) for i < N, and in particular φ(r_{j}) for 1 ≤ j ≤ m, are determined by d_{0}, …, d_{N−1}. Therefore we can set f = ∑_{i=0}^{N−1} d_{i}b_{i} and still have f(r_{j}) = s_{j} for 1 ≤ j ≤ m. As an R_{v}-linear combination of the b_{i} ∈ Int(R, R_{v}), f is in Int(R, R_{v}). □

5. Explicit Construction for the Ring of Algebraic Integers in a Number Field. In some cases there is an explicit and natural bijective arrangement of R as a v-sequence, for instance, when R is the ring of algebraic integers in a number field K, p ∈ ℤ a prime such that only one prime ideal P of R lies above p, and R_{v} is the localization R_{P} of R at P. Since the intersections of the powers of the valuation ideal with R are just the powers of P, we need to construct an I-sequence for I = {P^{n} | n ∈ ℕ} that enumerates R bijectively. We first show the existence of an integral basis of R having special properties with respect to a prime p. (For definitions of the notions related to the splitting of primes in number fields see [11]).

If pR = P^{e} with [R: P] = p^{f} and ω_{1}, …, ω_{n} is a ℤ-basis of R, then

R = ℤω_{1} + … + ℤω_{n} and P^{e} = pR = pℤω_{1} + … + pℤω_{n},

but whether an element of R belongs to P^{k} for 0 < k < n is not readily seen from the coefficients in its representation as a ℤ-linear combination of the ω_{i}. There are, however, ℤ-bases of R with the property that

P^{k} = pℤω_{1} + … + pℤω_{kf} + ℤω_{kf+1} + … + ℤω_{n}.

More generally, we will show in Lemma 2 that if pR = P_{1}^{e_{1}} · . . . · P_{r}^{e_{r}}, and f_{i} denotes the inertial degree of P_{i} | p, there is a ℤ-basis of R such that for 1 ≤ i ≤ r and 0 ≤ k ≤ e_{i},

P_{i}^{k} = ℤω_{1}^{(1)} + … + ℤω_{e_{1}f_{1}}^{(1)} + …

+pℤω_{1}^{(i)} + … + pℤω_{kf_{i}}^{(i)} + ℤω_{kf_{i}+1}^{(i)} + … + ℤω_{e_{i}f_{i}}^{(i)} + …
+ℤω_{1}^{(r)} + … + ℤω_{e_{r}f_{r}}^{(r)}.

Lemma 2. Let K be an algebraic number field with [K : ℚ] = n, R the ring of algebraic integers in K, and p ∈ ℤ a prime that splits in R as pR = P_{1}^{e_{1}} ·. . .·P_{r}^{e_{r}} with [R:P_{i}] = p^{f_{i}}. Then there exists a ℤ-basis of R consisting of blocks ω_{1}^{(i)}, …, ω_{e_{i}f_{i}}^{(i)}, 1 ≤ i ≤ r, such that for all s ∈ R, where

s = m_{1}^{(1)}ω_{1}^{(1)} + … + m_{e_{1}f_{1}}^{(1)}ω_{e_{1}f_{1}}^{(1)} + . . . . . . + m_{1}^{(r)}ω_{1}^{(r)} + … + m_{e_{r}f_{r}}^{(r)}ω_{e_{r}f_{r}}^{(r)}

with m_{j}^{(i)} ∈ ℤ, we have, for 1 ≤ i ≤ r and 1 ≤ k ≤ e_{i},

s ∈ P_{i}^{k} ⟺ p | m_{j}^{(i)} for 1 ≤ j ≤ kf_{i} .

Proof. For 1 ≤ i ≤ r, let V^{(i)} = R/P_{i}^{e_{i}} and V = V^{(1)} × … × V^{(r)}. Also let π: R → R/pR be the canonical projection, φ: R/pR → V the isomorphism of rings φ(s + pR) = (s + P_{1}^{e_{1}}, …, s + P_{r}^{e_{r}}), and ρ_{i}: V → V^{(i)} the projection of V onto the direct factor V^{(i)}. Then the composition ρ_{i}φπ equals the canonical projection π_{i}: R → R/P_{i}^{e_{i}}, π_{i}(s) = s + P_{i}^{e_{i}}.

\begin{matrix}R & \underrightarrow{π} & R/pR & \underrightarrow{φ} & R/P_{1}^{e_{1}} × … × R/P_{r}^{e_{r}} & \underrightarrow{ρ_{i}} & R/P_{i}^{e_{i}} \\ s & ⟼ & s + pR & ⟼ & (s + P_{1}^{e_{1}}, …, s + P_{r}^{e_{r}}) & ⟼ & s + P_{i}^{e_{i}} \end{matrix}

In V^{(i)} the images π_{i}(P_{i}^{k}) = V_{k}^{(i)}, for 0 ≤ k ≤ e_{i}, form a chain of ideals with V_{0}^{(i)} = V^{(i)}, V_{e_{i}}^{(i)} = (0) and [V_{k}^{(i)}: V_{k+1}^{(i)}] = p^{f_{i}}. If we consider them as a chain of subspaces of the ℤ/pℤ vector space V^{(i)}, then dim(V_{k}^{(i)}) = (e_{i} − k)f_{i}. By repeated basis completion, we get a ℤ/pℤ-basis for V^{(i)} with the property that for k = 0, …, e_{i} the last (e_{i}−k)f_{i} basis elements form a basis of V_{k}^{(i)}; so that v ∈ V^{(i)} is in V_{k}^{(i)} if and only if the first k · f_{i} coefficients are zero in the representation of v as a ℤ_{p}-linear combination of the basis elements.

Through the canonical embeddings of the direct factors we get a basis B of the ℤ/pℤ vector space V that consists of r blocks, the i-th of which is a basis of V^{(i)}, and such that v ∈ V is in ρ_{i}^{−1}(V_{k}^{(i)}) if and only if the first k · f_{i} coordinates in the i-th block are zero in the representation of v with respect to basis B.

For 0 ≤ k ≤ e_{i}, an element s ∈ R is in P_{i}^{k} if and only if φπ(s) ∈ ρ_{i}^{−1}(V_{k}^{(i)}). Also, every ℤ-basis Ω of R maps to a ℤ/pℤ-basis C of V under φπ, and the coordinates of φπ(s) with respect to C are just the coordinates of s with respect to Ω reduced mod p.

Therefore, if we can find a ℤ-basis of R that maps to B under φπ, it will have the desired property. Let Ω be any ℤ-basis of R and C its image under φπ. We may assume that the determinant of the basis transformation T̄ of V that maps C to B is 1. (If not, multiply an element of B by the appropriate unit in ℤ/pℤ; this does not affect the subspaces spanned by the blocks of B.) Since reduction mod p is surjective SL(ℤ, n) → SL(ℤ/pℤ, n) (see remark below), we can lift this basis transformation to T ∈ SL(ℤ, n), apply T to Ω and get a ℤ-basis for R that maps to B under φπ, as desired. □

Remark. The easiest way to see that reduction of matrix entries mod p is surjective SL(ℤ, n) → SL(ℤ/pℤ, n) (I thank Paul Gerardin for pointing this out), is to observe that every matrix in SL(ℤ/pℤ, n) is a product of elementary matrices (i.e., matrices with only 1s in the diagonal and only one non-zero off-diagonal entry) which can be lifted individually to elementary matrices over ℤ whose product is the desired lifting to SL(ℤ, n).

Theorem 4. Let [K : ℚ] = n, R the ring of integers in K, and p ∈ ℤ a prime with pR = P^{e}, [R: P] = p^{f}, ef = n. Let ω_{0}, …, ω_{n−1} be a ℤ-basis of R with the property that

P^{k} = pℤω_{0} + … + pℤω_{kf−1} + ℤω_{kf} + … + ℤω_{n−1} for 0 ≤ k ≤ e.

For 0 ≤ m < p^{n}, with m = ∑_{j=0}^{n−1} m_{j}p^{j} (0 ≤ m_{j} < p), define β(m) = ∑_{j=0}^{n−1} m_{j}ω_{j}, and for l ∈ ℕ_{0} with l = ∑_{j≥0} l_{j} p^{nj} (0 ≤ l_{j} < p^{n}) let α(l) = ∑_{j≥0} β(l_{j})(−p)^{j}. Then

(a)  α: ℕ_{0} → R is bijective,
(b)  α(l) ∈ P^{N} ⟺ [R: P^{N}] | l,
(c)  α(l) − α(l′) ∈ P^{N} ⟺ [R: P^{N}] | l − l′.

Proof. First note that for 0 ≤ k ≤ e we have β(m) ∈ P^{k} if and only if m_{j} = 0 for 0 ≤ j < kf, that is if and only if p^{kf} divides m. Also for 0 ≤ k ≤ e, β(m) − β(m′) ∈ P^{k} if and only if m_{j} = m′_{j} for 0 ≤ j < kf, that is if and only if m ≡ m′ mod p^{kf}.

Ad (b). α(l) ∈ P^{N}, where N = ke + r with 0 ≤ r < e, if and only if β(l_{j}) = 0 for j < k and β(l_{k}) ∈ P^{r}, that is if and only if l_{j} = 0 for j < k and p^{rf} divides l_{k}, or equivalently, p^{kn+rf} divides l. Since ef = n, and therefore p^{kn+rf} = p^{f(ke+r)} = [R: P^{ke+r}] = [R: P^{N}], we are done.

Ad (c). Similarly, α(l) − α(l′) ∈ P^{ke+r} if and only if β(l) = β(l′) for j < k and β(l_{k}) ≡ β(l′_{k}) mod P^{r}. This is equivalent to l_{j} = l′_{j} for j < l and l_{k} ≡ l′_{k} mod p^{rf}, which is the case if and only if l ≡ l′ mod p^{kn+rf} = [R: P^{ke+r}].

Ad (a). Being a P -sequence, α is injective. To show surjectivity, we use the fact that every m ∈ ℤ has a representation m = ∑_{j≥0} m_{j}(−p)^{j} with 0 ≤ m_{j} < p, only finitely many m_{j} ≠ 0. Given a ∈ R, a = a_{0}ω_{0} + … + a_{n−1}ω_{n−1}, with a_{k} ∈ ℤ, a_{k} = ∑_{j≥0} a_{j}^{(k)}(−p)^{j}, 0 ≤ a_{j}^{(k)} < p, let l = ∑_{j≥0}(∑_{k=0}^{n−1} a_{j}^{(k)}p^{k})p^{nj}, then l_{j} = ∑ a_{j}^{(k)}p^{k} for j ≥ 0, so β(l_{j}) = ∑_{k=0}^{n−1} a_{j}^{(k)}ω_{k}, and α(l) = ∑_{j≥0} β(l_{j})(−p)^{j} = ∑_{j≥0} ∑_{k=0}^{n−1} a_{j}^{(k)}ω_{k}(−p)^{j} = ∑_{k=0}^{n−1}(∑_{j≥0} a_{j}^{(k)}(−p)^{j})ω_{k} = a. □

REFERENCES

1. P.-J. Cahen, “Integer-valued polynomials on a subset,” Proc. Amer. Math. Soc. 117 (1993), 919–929.

2. P.-J. Cahen, “Polynômes à valeurs entières,” Canad. J. Math. 24 (1972), 747–754.

3. J.-L. Chabert, “Le groupe de Picard de l’anneau des polynômes à valeurs entières,” J. Algebra 150 (1992), 213–230.

4. S. Frisch, “Integer-valued polynomials on Krull Rings,” Proc. Amer. Math. Soc. 124 (12) (1996) 3595-3604.

5. S. Frisch, “Interpolation by integer-valued polynomials,” to appear in J. Algebra.

6. R. Gilmer, W. Heinzer and D. Lantz, “The Noetherian property in rings of integervalued polynomials,” Trans. Amer. Math. Soc. 338 (1993), 187–199.

7. H. Gunji and D. L. McQuillan, “On a class of ideals in an algebraic number field,” J. Number Theory 2 (1970), 207–222.

8. D. E. Knuth, “The Art of Computer Programming” (second edition) vol. 2: “Seminumerical Algorithms,” Addison-Wesley, Reading, MA, 1981.

9. D. E. Knuth and H. S. Wilf, “The power of a prime that divides a generalized binomial coefficient,” J. reine angew. Math. 396 (1989), 212–219.

10. E. E. Kummer, “Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen,” J. reine angew. Math. 44 (1852), 93–146.

11. D. A. Marcus, “Number Fields,” Springer, New York, 1977.

12. H. Matsumura, “Commutative ring theory,” Cambridge University Press, 1986.

13. D. L. McQuillan, “On Prüfer domains of polynomials,” J. reine angew. Math. 358 (1985), 162–178.

14. D. L. McQuillan, “Split primes and integer-valued polynomials,” J. Number Theory 43 (1993), 216–219.

15. A. Ostrowski, “Über ganzwertige Polynome in algebraischen Zahlkörpern,” J. reine angew. Math. 149 (1919), 117–124.

16. G. Pólya, “Über ganzwertige Polynome in algebraischen Zahlkörpern,” J. reine angew. Math. 149 (1919), 97–116.

17. D. Singmaster, “Notes on binomial coefficients I–III,” J. London Math. Soc. (2) 8 (1974), 545–560.

AMS 1991 Mathematics Subject Classification: 11B65, 05A10, 13G05.

Institut für Mathematik C Technische Universität Graz Steyrergasse 30 A-8010 Graz, Austria e-mail: frisch@blah.math.tu-graz.ac.at