J. Algebra 211 (1999) 562–577.

INTERPOLATION

by

INTEGER-VALUED POLYNOMIALS

Sophie Frisch

Abstract. Let R be a Krull ring with quotient field K and a_{1}, …, a_{n} in R. If and only if the a_{i} are pairwise incongruent mod every height 1 prime ideal of infinite index in R does there exist for all values b_{1}, …, b_{n} in R an interpolating integer-valued polynomial, i.e., an f ∈ K[x] with f(a_{i}) = b_{i} and f(R) ⊆ R. If S is an infinite subring of a discrete valuation ring R_{v} with quotient field K and a_{1}, …, a_{n} in S are pairwise incongruent mod all M_{v}^{k} ∩ S of infinite index in S, we derive a formula (depending on the distribution of the a_{i} among residue classes of the ideals M_{v}^{k} ∩ S) for the minimal d, such that for all b_{1}, …, b_{n} ∈ R_{v} there exists a polynomial f ∈ K[x] of degree at most d with f(a_{i}) = b_{i} and f(S) ⊆ R_{v}.

1. Introduction.

Suppose D is an integral domain with quotient field K. Unless D is a field, it is not always possible, given a_{0}, …, a_{n} (distinct) and b_{1}, …, b_{n} in D, to find a polynomial f ∈ D[x] with f(a_{i}) = b_{i}. This is so because the function induced on D by a polynomial with coefficients in D must preserve congruences mod every ideal of D. One might say that the next best thing to interpolation with polynomials in D[x] is interpolation with polynomials in K[x] that map every element of D into D and thus induce a function on D.

We will show that this kind of interpolation is possible for arbitrary arguments and values in D whenever D is a Dedekind ring all of whose residue fields are finite, such as the ring of algebraic integers in a number field. (For D = ℤ this is easy to see, and for D = 𝔽_{q}[x] it has been shown by Carlitz [5].)

More generally, we find that distinct elements a_{0}, …, a_{n} of a Krull ring R have the property that for all b_{0}, …, b_{n} in R there exists a polynomial f ∈ K[x] with f(a_{i}) = b_{i} and f(R) ⊆ R if and only if the a_{i} are pairwise incongruent mod every height 1 prime ideal P of R with [R: P] = ∞.

integer-valued polynomial interpolation

We use the customary notation Int(E, D) = {f ∈ K[x] | f(E) ⊆ D} and Int(D) = Int(D, D), where D is a domain with quotient field K and E a subset of K. A polynomial f ∈ K[x] that maps E into D is called “integer-valued” on E, following Pólya [15] and Ostrowski [14], who studied Int(D) where D is the ring of algebraic integers in a number field. More recently, integer-valued polynomials have been investigated by Cahen [2,3], Chabert [6], McQuillan [12,13], Gilmer, Heinzer and Lantz [9], and others. For a survey of the subject, see the monograph by Cahen and Chabert [4].

1991 Math. Subj. Classification: Primary 13B25, 11S05, 13G05; Secondary 11B65, 05A10.

To interpolate at arguments a_{0}, …, a_{n}, we use linear combinations of the polynomials f_{k}(x) = ∏_{i=0}^{k−1}(x − a_{i})/∏_{i=0}^{k−1}(a_{k} − a_{i}), 0 ≤ k ≤ n. For this purpose we introduce, when R is an infinite subring of a discrete valuation ring R_{v}, special sequences (a_{k}) ⊆ R that ensure that the polynomials f_{k} constructed from them are in Int(R, R_{v}) and then show how to embed a finite subset of R in a sequence of this kind.

This approach seems justified by the result that the minimal length of such a sequence containing α_{0}, …, α_{m} ∈ R is equal to the minimal d such that for all β_{0}, …, β_{m} ∈ R_{v} there exists an f ∈ Int(R, R_{v}) with f(α_{i}) = β_{i} and deg f ≤ d. It also yields a formula for this minimal d, depending on the distribution of the α_{i} among the residue classes of R ∩ M_{v}^{k} in R.

2. Sequences.

In this section, R may be any commutative ring with identity. We denote the set of non-negative integers {0, 1, 2, …} by ℕ_{0}. The kind of sequences below has already been used in [7]; we need to develop some more of their properties.

2.1 Definition. For a set I of ideals in a commutative ring with identity R, we define a partial I-sequence to be an indexed set (a_{n})_{n∈N}, with N ⊆ ℕ_{0}, of elements in R, such that for all I ∈ I and all n, m ∈ N

a_{n} ≡ a_{m} mod I ⟺ [R: I] | n − m.

(If [R : I] is infinite, we regard it as dividing 0, but no other integer.) A partial I-sequence is called an I-sequence if N is an initial segment of ℕ_{0}.

2.2 Convention. The length of a finite partial sequence (a_{n})_{n∈N} is max(N).

2.3 Proposition. For every descending chain I = {I_{n} | n ∈ ℕ} of ideals in R (a) every finite partial I-sequence can be completed to an I-sequence,

(b) every finite I-sequence can be extended to an infinite I-sequence,

(c) every finite set A ⊆ R of elements pairwise incongruent mod I_{n+1}, where [R : I_{n}] is finite, can be embedded in a finite I-sequence, and one of length less than [R: I_{n+1}], if [R: I_{n+1}] is also finite.

Proof. Given (a_{n})_{n∈N}, and l ≥ max(N), we show how to complete (a_{n}) to an I-sequence of length l. General principle: For a finite sequence of length l to be an I-sequence (I being a descending chain of ideals), it suffices that it satisfy the requirements with respect to I_{1}, …, I_{k}, if k satisfies [R: I_{k}] > l or for all m ≥ k, I_{m} = I_{k}.

Case 1: there exists I_{k} of finite index with [R: I_{k}] > l or I_{m} = I_{k} for m ≥ k. For j = 1, …, k inductively, we assign a different residue class of I_{j} in R to every residue class mod [R: I_{j}] in ℤ such that 1) for all n ∈ N, n + [R: I_{j}]ℤ is assigned a_{n} + I_{j} (this is consistent because (a_{n})_{n∈N} is a partial I-sequence) and 2) if r + I_{j−1} was assigned to m + [R: I_{j−1}]ℤ, then the residue classes of I_{j} in r + I_{j−1} are assigned to the residue classes of [R: I_{j}]ℤ in m + [R: I_{j−1}]ℤ.

Case 2: there is I_{k−1} with [R : I_{k−1}] < l and [R : I_{k}] = ∞. We proceed as above for j = 0, …, k − 1 and then assign a different residue class of I_{k} to every n ≤ l, n ∈ ℕ_{0}, such that 1) every n ∈ N is assigned a_{n} + I_{k} and 2) if r + I_{k−1} was assigned to m + [R: I_{k−1}]ℤ, every n ∈ m + [R: I_{k−1}]ℤ is assigned a residue class of I_{k} in r + I_{k−1}.

We now define sequence elements for indices m ∉ N, 0 ≤ m ≤ l, by choosing a_{m} from the residue class of I_{k} assigned to m+[R:I_{k}]ℤ (in case 1) or to m (in case 2). The resulting sequence (a_{n})_{n=0}^{l} satisfies the I-sequence requirements with respect to I_{1}, … I_{k}, which is all we need by the general principle stated above. We can extend (a_{n})_{n=0}^{l} to an I-sequence of length l′ > l, and inductively to an infinite I-sequence by iterating the construction. This shows (a) and (b). It also shows that I-sequences of arbitrary length exist, since we can start with any a_{0} ∈ R and extend it to an infinite I-sequence.

For (c), if [R : I_{n+1}] is finite, we take an I-sequence of length [R : I_{n+1}] − 1 and swap every member of A with the unique sequence element congruent to it mod I_{n+1}. Otherwise, we take an I-sequence of length c · [R: I_{n}] − 1, c being the maximal number of elements of A in any residue class of I_{n}, and swap every a ∈ A with a sequence element in a + I_{n}, choosing the one in a + I_{n+1}, if such exists. □

2.4 Definition. For a set I of ideals in a commutative ring with identity R, we define a weak I-sequence to be a sequence (a_{n})_{n∈N}, where N is an initial segment of ℕ_{0}, such that for all I ∈ I and all k ≥ 0 the sequence elements a_{i} with k[R: I] ≤ i < (k + 1)[R: I] are pairwise incongruent mod I. (For infinite [R: I], we use the convention 0[R: I] = 0.)

We could also define partial weak I-sequences and show an analogue of Proposition 2.3, but we will not need this. To compare I-sequences and weak I-sequences, we note that

1) An infinite sequence is an I-sequence if and only if for every I ∈ I of finite index, every [R: I] consecutive terms of the sequence form a complete system of residues mod I and the terms of the sequence are pairwise incongruent mod every I ∈ I of infinite index.

2) An infinite sequence is a weak I-sequence if and only if for every I ∈ I of finite index, every [R:I] consecutive terms of the sequence starting at an index divisible by [R: I] form a complete system of residues mod I and the terms of the sequence are pairwise incongruent mod every I ∈ I of infinite index.

2.5 Example. In the ring of integers ℤ, for every fixed k ∈ ℤ, the sequence a_{n} = k + n for n ≥ 0 is an I-sequence for the set of all ideals of ℤ.

2.6 Example. If 𝔽_{q} is the finite field of order q then a weak I-sequence for the set of all ideals of 𝔽_{q}[x] that runs through 𝔽_{q}[x] bijectively can be constructed as follows (Wagner [16], see also Amice [1]): Let 𝔽_{q} = {r_{0}, …, r_{q−1}}, where r_{0} = 0. If n=∑_{i=0}^{N} c_{i}q^{i} with 0≤c_{i} <q, set a_{n} =∑_{i=0}^{N} r_{c_{i}}x^{i}. This is a weak I-sequence, since a_{0}, …, a_{q^{m}−1} are precisely the elements of 𝔽_{q}[x] of degree less than m and thus form a system of residues mod every ideal generated by an element of degree m, and the q^{m} sequence elements starting at index kq^{m} (with 0 ≤ k < q) are just the first q^{m} elements shifted by r_{k}x^{m}: a_{kq^{m}} = r_{k}x^{m} +a_{0}, …, a_{(k+1)q^{m}−1} = r_{k}x^{m} +a_{q^{m}−1}.

2.7 Example. An infinite I-sequence exists for every descending chain I of ideals in a ring R. (Apply Proposition 2.3 (b) to a_{0} =0.) If R is a countably infinite ring and I a descending chain of ideals of finite index in R with ⋂_{n∈ℕ} I_{n} = (0) then there exists an I-sequence that runs through R bijectively [8].

3. Binomial Polynomials.

Let R_{v} be a discrete valuation ring (with value group ℤ and v(0) = ∞), M_{v} its maximal ideal, K its quotient field and R an infinite subring of R_{v}. (Throughout this paper, discrete valuation always means discrete rank one valuation.) We will define some useful polynomials in Int(R, R_{v}), which are modeled after the polynomials

\binom{x}{n} = \frac{x(x − 1) … (x − n + 1)}{n!}

in Int(ℤ) and which we therefore call “binomial polynomials”. These polynomials were introduced in [7], generalizing a construction of Pólya [15] that has also been employed by Cahen [3], Gunji and McQuillan [10,12] and others. The sequence a_{i} of elements of R that will replace the sequence of natural numbers in the definition of the binomial polynomials will have to be nicely distributed with respect to the residue classes of R ∩ M_{v}^{n} in R, in the following sense:

3.1 Definition. A [partial] v-sequence for R is a [partial] I-sequence with I = {M_{v}^{n} ∩ R | n ∈ ℕ}. In other words, (a_{n})_{n∈N} ⊆ R is a partial 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 .

Similarly, a weak v-sequence for R is defined to be a weak I-sequence with I = {M_{v}^{n} ∩ R | n ∈ ℕ}. In other words, (a_{n})_{n≥0} is a weak v-sequence for R if and only if for all n ∈ ℕ and all i, j and k ∈ ℕ_{0},

k [R: M_{v}^{n} ∩ R] ≤ i < j < (k + 1) [R: M_{v}^{n} ∩ R] ⟹ v(a_{i} − a_{j}) < n

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

For brevity, we write I_{n} for M_{v}^{n} ∩ R from this point on.

Note that by the Krull Intersection Theorem, ⋂_{k=0}^{∞} I_{k} = (0). Therefore, there exists for every finite subset A of R an n ∈ ℕ such that distinct elements of A are incongruent mod I_{n}. Since R is infinite, the indices [R: I_{k}] grow arbitrarily large or are infinite from some k on.

3.2 Definition. The binomial polynomials constructed from a weak v-sequence (a_{n}) are

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

3.3 Proposition. Let (a_{i})_{i=0}^{m} be a weak v-sequence for R and (f_{i})_{i=0}^{m} the binomial polynomials constructed from it. For j, k ∈ ℕ_{0} let r_{j}(k) be the remainder of k under integral division by [R: I_{j}], if [R: I_{j}] is finite, and r_{j}(k) = k otherwise. Then for all r ∈ R and 0 ≤ k ≤ m

(a) v(f_{k}(r)) = |{j ≥ 1 | r ≡ a_{l} mod I_{j} for some l with k − r_{j}(k) ≤ l < k}|,

(b) in particular, f_{k} ∈ Int(R, R_{v}).

Proof. Let g_{k}(x) = ∏_{i=0}^{k−1}(x − a_{i}), then v(f_{k}(r)) = v(g_{k}(r)) − v(g_{k}(a_{k})). For any s ∈ R, v(g_{k}(s)) = ∑_{j≥1} |\{i | 0 ≤ i < k, s ≡ a_{i} mod I_{j}\}|. Let q_{j}(r) = [\frac{k}{[R:I_{j}]}], then k = q_{j}(k)[R: I_{j}] + r_{j}(k), and the sequence a_{0}, …, a_{k−1} consists of q_{j}(r) complete systems of residues mod I_{j} comprising a_{0}, …, a_{k−r_{j}(k)−1} and r_{j}(k) extra terms a_{l} for k − r_{j}(k) ≤ l < k, pairwise incongruent mod I_{j}.

Now |{i | 0 ≤ i < k, s ≡ a_{i} mod I_{j}}| is either q_{j}(k) or q_{j}(k) + 1, the latter being the case if and only if s is congruent mod I_{j} to one of the elements a_{l} with k−r_{j}(k) ≤ l < k. This extra +1 never occurs with s = a_{k}, since a_{k} is not congruent to any a_{l} with k − r_{j}(k) ≤ l < k by definition of weak v-sequence. □

3.4 Remark. It is easy to see that the binomial polynomials f_{k} constructed from a weak v-sequence (a_{i}) for R, where R is an infinite subring of a discrete valuation ring R_{v}, give a basis of the free R_{v}-module Int(R, R_{v}), cf. [7]. Indeed, deg f_{k} = k shows that the f_{k} are a K-basis of K[x]. Since they are in Int(R, R_{v}), they form a basis of a free R_{v}-module F ⊆ Int(R, R_{v}). To see Int(R, R_{v}) ⊆ F, consider f =∑ d_{k}f_{k} with d_{k} ∈K. A simple induction shows that for f ∈Int(R, R_{v}) the d_{k} are actually in R_{v}: d_{0} = f(a_{0}), and d_{k} = f(a_{k}) − ∑_{i=0}^{k−1} d_{i}f_{i}(a_{k}) (by the facts that f_{k}(a_{k}) = 1 and f_{j}(a_{k}) = 0 for j > k). The last argument also shows that for a polynomial f ∈ K[x] with deg f < m to be in Int(R, R_{v}) it suffices that f(a_{i}) ∈ R_{v} for 0 ≤ i < m.

If a domain S with quotient field K is the intersection of a family of discrete valuation rings in K, S = ⋂_{v∈V} R_{v}, then for every subring R of S we have Int(R, S) = ⋂_{v∈V} Int(R, R_{v}). In particular this holds if S is a Krull ring and V the set of its essential valuations.

3.5 Theorem. Let R be an infinite subring of a Krull ring S. If a_{0}, …, a_{n} ∈ R is a weak v-sequence for R for all essential valuations v of S simultaneously then for all b_{0}, …, b_{n} ∈ S there exists f ∈ Int(R, S) with f(a_{i}) = b_{i} (0 ≤ i ≤ n) and deg f ≤ n.

Proof. Let (f_{i})_{i=0}^{n} be the binomial polynomials constructed from (a_{i})_{i=0}^{n}. For every essential valuation v of S, we know from Proposition 3.3 (b) that the f_{i}, and therefore R_{v}-linear combinations of them, are in Int(R, R_{v}). Therefore S-linear combinations of the f_{i} are in ⋂_{v} Int(R, R_{v}) = Int(R, S). We define coefficients d_{k} ∈ S inductively, such that f = ∑_{k=0}^{n} d_{k}f_{k} maps a_{i} to b_{i} for 0 ≤ i ≤ n: let d_{0} = b_{0}, and d_{m} = b_{m} − ∑_{k=0}^{m−1} d_{k}f_{k}(a_{m}). Since f_{k}(a_{k}) = 1 and f_{m}(a_{k}) = 0 for m > k, we get f(a_{m}) = d_{m} + ∑_{k=0}^{m−1} d_{k}f_{k}(a_{m}) = b_{m} as required. □

3.6 Corollary. (Carlitz [5]) Let α_{1}, …, α_{k} be distinct elements of 𝔽_{q}[x] and d = max_{1≤i≤k} deg_{x} α_{i}. Then for all β_{1}, …, β_{k} ∈ 𝔽_{q}[x] there exists f(t) ∈ Int(𝔽_{q}[x]) with deg_{t} f < q^{d} and f(α_{i}) = β_{i} for i = 1, …, k.

Proof. Wagner’s sequence (Example 2.6) is a weak I-sequence for the set of all ideals of 𝔽_{q}[x] and therefore a fortiori a weak v-sequence for all essential valuations of 𝔽_{q}[x]. Its initial segment a_{0}, …, a_{q^{d}−1} consists of all elements of 𝔽_{q}[x] of degree at most d, with α_{1}, …, α_{k} among them. □

Carlitz proved this by showing that a polynomial f ∈𝔽_{q}(x)[t] with deg_{t}(f)<q^{m} is in Int(𝔽_{q}[x]) if and only if it maps all α ∈ 𝔽_{q}[x] with deg_{x}(α) < m to values in 𝔽_{q}[x] ([5] Theorem 7.1). Since there are q^{m} elements of degree less than m in 𝔽_{q}[x], the Lagrange interpolation polynomial for these arguments will be of degree q^{m} − 1 or less and will therefore be in Int(𝔽_{q}[x]) provided the values prescribed for the q^{m} arguments are in 𝔽_{q}[x]. To relate Carlitz’s proof to the one using Wagner’s sequence, note that a polynomial f ∈ K[x] with deg f < m that takes values f(a_{i}) ∈ R_{v} on a v-sequence a_{0}, …, a_{m−1} for R is (by the argument in 3.4) an R_{v}-linear combination of the binomial polynomials f_{0}, …, f_{m−1} constructed from the v-sequence and therefore in Int(R, R_{v}).

Unfortunately, weak v-sequences for all essential valuations of a Krull ring simultaneously seem to be rare, and we will use a different approach to interpolation with integer-valued polynomials on Krull rings in section 6.

Locally, however, we can use v-sequences to construct interpolating integervalued polynomials as follows: Let α_{1}, …, α_{k} be elements of an infinite subring R of a discrete valuation ring R_{v} that are pairwise incongruent mod all M_{v}^{n} ∩ R of infinite index in R. By Proposition 2.3, α_{1}, …, α_{k} can be embedded in a v-sequence a_{0}, …, a_{ℓ}. Therefore there exists for arbitrary values β_{1}, …, β_{k} ∈ R_{v} an f ∈ Int(R, R_{v}) with deg f ≤ ℓ that maps α_{i} to β_{i}, by Theorem 3.5.

In section 5 we will see that the minimal length ℓ of a v-sequence for R containing α_{1}, …, α_{k} coincides with the minimal d such that for arbitrary values β_{1}, …, β_{k} in R_{v} there exists an f ∈ Int(R, R_{v}) with deg f ≤ d that maps α_{i} to β_{i}; so that, in a sense, interpolation by polynomials in Int(R, R_{v}) using v-sequences yields interpolation polynomials of best possible degree.

4. Embedding sets in v-sequences of minimal length.

As before, R is an infinite subring of a discrete valuation ring R_{v}, I_{n} = M_{v}^{n}∩R and I = {I_{n} | n ≥ 0}. Recall that the length of a sequence (a_{i})_{i=0}^{n} is n, by convention.

4.1 Definition. Let A be a finite subset of R.

1. We define d(A) to be the minimal d ∈ ℕ_{0} such that for every choice of values r_{a} ∈ R_{v} for a ∈ A there exists f ∈ Int(R, R_{v}) with f(a) = r_{a} for all a ∈ A and deg f ≤ d, if such a d exists; otherwise d(A) = ∞.

2. If A is not embeddable in any v-sequence in R then ℓ(A) = ∞; otherwise we define ℓ(A) to be the minimal ℓ such that there exists a v-sequence a_{0}, …, a_{ℓ} in R containing A.

4.2 Corollary to Theorem 3.5. For every finite subset A of R, d(A) ≤ ℓ(A).

We will show that d(A) = ℓ(A) in section 5; but before, we want to derive a formula for ℓ(A). In order to do this, we first consider sets that have a simple structure with respect to the chain of ideals I_{n} = M_{v}^{n} ∩ R, n ≥ 0.

4.3 Definition. We call a non-empty set L ⊆ R an I-lattice of dimensions (d_{k})_{k≥0} if, for all k ≥ 0, L intersects exactly d_{k} residue classes of I_{k+1} in every residue class of I_{k} that it intersects. If L is finite, then d_{k} = 1 for all but finitely many k, and we speak of dimensions d_{0}, …, d_{n}, meaning d_{k} = 1 for k > n.

4.4 Definition. To every finite set A ⊆ R whose elements are pairwise incongruent mod I_{n+1}, where [R: I_{n}] is finite, we associate dimensions (d_{k})_{k≥0} and an I-lattice L_{A} ⊆ A, the spanning lattice of A, inductively as follows:

– L_{n} = A and d_{k} = 1 for k > n,

– d_{k} is the maximal number of residue classes of I_{k+1} that L_{k} intersects in any residue class of I_{k}, for 0 ≤ k ≤ n;

– L_{k−1} consists of the elements of L_{k} in those residue classes of I_{k} that L_{k}

intersects in d_{k} residue classes of I_{k+1}, for 1 ≤ k ≤ n; and L_{A} is L_{0}, which is easily seen to be an I-lattice of dimensions d_{0}, …, d_{n}.

The minimal length of a v-sequence into which a finite set can be embedded is most conveniently expressed in the mixed radix number system given by the sequence [R: I_{l}], l ≥ 0:

Every n ∈ ℕ_{0} has a unique representation n = ∑_{l=0}^{∞} ε_{l}(n)[R : I_{l}], where 0 ≤ ε_{l}(n) < [I_{l}: I_{l+1}]. Addition of numbers 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 [I_{l} : I_{l+1}]. We will call this the I-ary number system and ε_{l}(n) the l-th digit in the I-ary representation of n.

If [R_{v}:M_{v}] is finite, then [I_{l}:I_{l+1}] divides [M_{n}^{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 even bounded at all. If infinite indices [R : I_{l}] occur, the system is somewhat degenerate, with 0 ≤ ε_{N}(n) < ∞ for the maximal N ∈ ℕ_{0} with [R: I_{N}] finite and ε_{l}(n) = 0 for all n, if l > N. (We use the convention that 0 · [R: I_{l}] = 0 even if [R: I_{l}] = ∞.)

Recall that by Proposition 2.3 (a) every partial v-sequence can be completed to a v-sequence of the same length. Therefore, ℓ(A) is equal to the minimal ℓ such that A can be arranged as a partial v-sequence of length ℓ.

4.5 Lemma. Let L be an I-lattice of dimensions d_{0}, …, d_{m}, with [R : I_{m}] finite. For every partial v-sequence (l_{n})_{n∈N} of minimal length formed by L, we have N = {n ∈ ℕ_{0} | ε_{i}(n) < d_{i} for all i }. Consequently, ℓ(L) = ∑_{k=0}^{m}(d_{k} −1)[R:I_{k}].

Proof. Induction on m. For m=0, L consists of d_{0} elements mutually incongruent modulo I_{1}. Any shortest partial v-sequence is just a listing of the elements of L, in any order, as l_{0}, …, l_{d_{0}−1}, therefore N = {0, …, d_{0} − 1} and ℓ(L) = d_{0} − 1.

Now let L be an I-lattice of dimensions d_{0}, …, d_{m}, m > 0. We can arrange L as a partial v-sequence with index set N = {n ∈ ℕ_{0} | ∀i ε_{i}(n) < d_{i}} as follows: Choose a system of representatives L′ ⊆ L of the residue classes of I_{m} that L intersects. L′ is an I-lattice of dimensions d_{0}, …, d_{m−1}. Arrange L′ as a partial v-sequence (l_{n})_{n∈N′} of minimal length and for each n ∈ N′ assign indices n + j[R : I_{m}], j = 1, …, d_{m} − 1 to the elements of L \ L′ in l_{n} + I_{m}. Since by induction hypothesis N′ is the set of all n = ∑_{j=0}^{m−1} k_{j}[R: I_{j}] with 0 ≤ k_{j} < d_{j}, N is the set of all n = ∑_{j=0}^{m} k_{j}[R : I_{j}] with 0 ≤ k_{j} < d_{j}. The length of this partial v-sequence is max(N) = ∑_{k=0}^{m}(d_{k} − 1)[R: I_{k}].

Now, given any v-sequence of minimal length (l_{n})_{n∈N} formed by L, we show that it must be of this kind: From every residue class of I_{m} that L intersects, take the element of lowest index. These elements form a lattice L′ of dimensions d_{0}, …, d_{m−1}, arranged as a partial v-sequence with index set N′ ⊆ N. The indices of the d_{m} elements of L in each residue class of I_{m} are part of an arithmetic progression of period [R: I_{m}] starting at n ∈ N′. If, for some n ∈ N′, the elements of L in l_{n} + I_{m} do not have indices n + j[R : I_{m}], j = 0, …, d_{m} − 1, then some index is at least n + d_{m}[R : I_{m}] ≥ d_{m}[R : I_{m}] > ∑_{k=0}^{m}(d_{k} − 1)[R : I_{k}], which is more than the length of the sequence constructed earlier. Therefore, we must have N = {n + j[I : I_{m}] | n ∈ N′, 0 ≤ j < d_{m}}, the length of the sequence being max(N′) + (d_{m} − 1)[R: I_{m}]. This is minimal only if max(N′) is minimal, i.e., if L′ forms a partial v-sequence of minimal length. □

4.6 Theorem. Let A⊆R be a finite set whose elements are pairwise incongruent mod I_{n+1}, where [R : I_{n}] is finite, and d_{0}, …, d_{n} the dimensions of A. Then ℓ(A) = ∑_{j=0}^{n}(d_{j} − 1)[R: I_{j}].

Proof. We know ℓ(A) ≥ ℓ(L_{A}) = ∑_{j=0}^{n}(d_{j} − 1)[R : I_{j}]. By Proposition 2.3 (a) it suffices to arrange A as a partial v-sequence of length ∑_{j=0}^{n}(d_{j} − 1)[R : I_{j}]. We define a chain of subsets of A that allows us to do this inductively. Let A_{n} = A and for 0 < k ≤ n let A_{k−1} ⊆ A_{k} be a system of representatives of those residue classes of I_{k} that A_{k} intersects in the maximal number of elements. It is clear that this maximal number is d_{k}. A_{0} consists of d_{0} elements mutually incongruent mod I_{1}. Listing A_{0} as a_{0}, …, a_{d_{0}−1} in any order makes A_{0} into a partial v-sequence of length d_{0} − 1. Assuming we have arranged A_{k−1} as a partial v-sequence (a_{n})_{n∈N} of length ∑_{j=0}^{k−1}(d_{j} − 1)[R : I_{j}], we will extend it to an arrangement of A_{k} as a partial v-sequence of length ∑_{j=0}^{k}(d_{j} − 1)[R: I_{j}].

A_{k} contains d_{k} elements in a_{n} + I_{k} for each n ∈ N, plus less than d_{k} elements each in some further residue classes of I_{k}. Let B ⊆ A_{k} be a system of representatives of these further classes. By considering a completion of (a_{n})_{n∈N} to a v-sequence of length [R : I_{k}] − 1 (which exists by Proposition 2.3) and assigning each b ∈ B the index of the unique sequence element congruent to it mod I_{k}, we get a partial v-sequence arrangement of A_{k−1} ∪ B of length less than [R : I_{k}]. We assign consecutive indices in an arithmetic progression of period [R : I_{k}], starting at the representative in A_{k−1} ∪ B, to the elements of A_{k} in each residue class of I_{k}. The highest index in this partial v-sequence arrangement of A_{k} is the highest index in a progression starting at a representative in A_{k−1}, namely max(N) + (d_{k} − 1)[R: I_{k}] = ∑_{j=0}^{k}(d_{j} − 1)[R: I_{j}], since a progression starting at b ∈ B with index n < [R: I_{k}] and containing the l < d_{k} elements of (b + I_{k}) ∩ A_{k} only reaches index n + (l − 1)[R: I_{k}] < l[R: I_{k}] ≤ (d_{k} − 1)[R: I_{k}]. □

5. The degree of the interpolating polynomial.

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

5.1 Proposition. Let (a_{n}) be a v-sequence for R (of length at least k) and f_{k} the binomial polynomial of degree k constructed from it. Then

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

(b) v(f_{k}(a_{n})) = 0 ⟺ ∀ l ε_{l}(k) ≤ ε_{l}(n).

Proof. (a) is true for k >n, since then v(f_{k}(a_{n}))=v(0)=∞ and there are infinitely many l with r_{l}(k) = k > n = r_{l}(n). (The indices [R: I_{l}] are unbounded because R is infinite and ⋂_{l≥0} I_{l} = (0).) Now assume k ≤ n.

a_{n} ≡a_{i} mod I_{l} for at most one i with k−r_{l}(k)≤i<k−r_{l}(k)+[R:I_{l}], by definition of weak v-sequence. Since (a_{n}) is really a v-sequence and n ≡ k − r_{l}(k) + r_{l}(n) mod [R: I_{l}], we know that a_{n} ≡ a_{k−r_{l}(k)+r_{l}(n)} mod I_{l}. The condition a_{n} ≡ a_{i} mod I_{l} for some i with k − r_{l}(k) ≤ i < k is therefore equivalent to r_{l}(k) > r_{l}(n), such that (a) follows from Proposition 3.3 (a).

If r_{l}(k) > r_{l}(n) then ∃m ≤ l with ε_{m}(k) > ε_{m}(n) and if ε_{m}(k) > ε_{m}(n) then r_{m}(k) > r_{m}(n). Therefore, ∀l r_{l}(k) ≤ r_{l}(n), which is equivalent to v(f_{k}(a_{n})) = 0 by (a), is equivalent to ∀ l ε_{l}(k) ≤ ε_{l}(n). Thus (b) follows from (a). □

From Proposition 5.1 one can easily derive that v(f_{k}(a_{n})) equals the number of carries that occur in the addition of k and n − k in the I-ary number system. For a_{n} = n and v = v_{p} this is Kummer’s result [11] that the exact power of p dividing the binomial coefficient \binom{n}{k} equals the number of carries that occur in the addition of k and n − k in base p arithmetic. Kummer’s expression of v_{p}(\binom{n}{k}) in terms of the digits of n, k and n−k in base p also generalizes, provided [I_{n}:I_{n+1}] = [R:I_{1}] for all n, cf. [8].

5.2 Lemma. For n ≥ 0, let I_{n} = M_{v}^{n} ∩ R. If [R : I_{n}] = ∞ and a, b ∈ R are congruent mod I_{n+m}, m ≥ 0, then f(b) ≡ f(a) mod I_{m+1} for all f ∈ Int(R, R_{v}).

Proof. Extend a = a_{0} to an infinite v-sequence (a_{k})_{k=0}^{∞} for R and construct binomial polynomials f_{k} ∈ Int(R, R_{v}) from it. Let f ∈ Int(R, R_{v}), then f = ∑_{k≥0} d_{k}f_{k} with d_{k} ∈ R_{v}, since the f_{k} are an R_{v}-basis of Int(R, R_{v}). Also, d_{0} = f(a_{0}) = f(a).

By Proposition 3.3, v(f_{k}(b)) equals the number of j ≥ 1 such that for some l with k−r_{j}(k) ≤ l < k, b ≡ a_{l} mod I_{j}. For k > 0, every j with n ≤ j ≤ n+m satisfies this condition, because b ≡ a_{0} mod I_{j} and r_{j}(k) = k. We see that v(f_{k}(b)) ≥ m+1 for all k > 0. Therefore f(b) ≡ d_{0}f_{0} = d_{0} = f(a) mod I_{m+1}. □

5.3 Corollary. Let α_{1}, …, α_{n} ∈ R. Only if the α_{i} are pairwise incongruent mod all I_{n} = M_{v}^{n} ∩ R with [R: I_{n}] = ∞ can there exist for all β_{1}, …, β_{n} ∈ R_{v} an f ∈ Int(R, R_{v}) with f(α_{i}) = β_{i}.

5.4 Lemma. Let L be a finite I-lattice embedded in a v-sequence a_{0}, …, a_{l} of minimal length l =ℓ(L), as L={a_{n} | n∈N }, and (f_{k})_{k=0}^{l} the binomial polynomials constructed from a_{0}, …, a_{l}. If n ∈ N and k ∉ N then v(f_{k}(a_{n})) > 0.

Proof. If k ∉ N then ε_{i}(k) ≥ d_{i} > ε_{i}(n) for some i by Lemma 4.5; therefore v(f_{k}(a_{n})) > 0 by Proposition 5.1. □

5.5 Remark. If A is a finite subset of R then d(A) is finite if and only if the elements of A are pairwise incongruent mod all I_{n} = M_{v}^{n} ∩R with [R:I_{n}] = ∞ and ℓ(A) is finite under precisely the same conditions: We know from Theorem 3.5 that d(A) ≤ ℓ(A). Now if a, b ∈ A are congruent mod I_{n} with [R: I_{n}] = ∞ then by Lemma 5.2 there does not exist f ∈ Int(R, R_{v}) with f(a) = 0 and f(b) = 1, so d(A) = ∞. Conversely, if the elements of A are pairwise incongruent mod all I_{n} of infinite index then ℓ(A) is finite by Theorem 4.6.

5.6 Theorem. For every finite subset A of R, d(A) = ℓ(A).

Proof. d(A) and ℓ(A) are each finite if and only if A is a finite set that does not contain two elements congruent mod any I_{n} = M_{v}^{n} ∩ R of infinite index. Let A be such a set. In view of Theorem 3.5, we need only show d(A) ≥ ℓ(A). Let a_{0}, …, a_{l} be a v-sequence containing A with l = ℓ(A). By Lemma 4.5, this is also the minimal length for a v-sequence containing the spanning lattice L of A, therefore a_{0} ∈ L and a_{l} ∈ L (otherwise we could chop off the ends of the sequence and re-index starting with 0 to get a shorter v-sequence containing L). Let the sequence (a_{j})_{j=0}^{l} be extended to an infinite v-sequence and let f_{j} be the binomial polynomial of degree j constructed from it.

Suppose f ∈ Int(R, R_{v}) with f(a_{l}) = 1 and f(a_{i}) = 0 for all a_{i} ∈ L with i < l; we claim that deg f ≥ l. The f_{j} form an R_{v}-basis of Int(R, R_{v}), so f = ∑_{j≥0} d_{j}f_{j} with d_{j} ∈ R_{v}. We show for k ≤ l that if a_{k} ∈ L then d_{k} ≡ δ_{k,l} mod I_{1}. Induction on k: if k = 0 then d_{0} = f(a_{0}) = δ_{0,l}. For any k with a_{k} ∈ L, every j < k satisfies (by Lemma 5.4) either a_{j} ∈ L, in which case d_{j} ≡ 0 mod I_{1} by induction hypothesis, or f_{j}(a_{k}) ∈ I_{1}. Therefore f(a_{k}) = d_{k} + ∑_{j=0}^{k−1} d_{j}f_{j}(a_{k}) shows d_{k} ≡ f(a_{k}) = δ_{k,l} mod I_{1}. In particular, we have shown d_{l} ≠ 0, which implies deg f ≥ l. □

We combine this with the formula for ℓ(A) from Theorem 4.6 and the corollary to Lemma 5.2. (The dimensions of a finite subset of R are defined in 4.4.)

5.7 Corollary. Let R be an infinite subring of a discrete valuation ring R_{v}, I_{n} = M_{v}^{n} ∩ R and α_{1}, …, α_{k} (distinct) in R.

1. If and only if the α_{i} are pairwise incongruent mod all I_{n} of infinite index in R there exists for all β_{1}, …, β_{k} ∈ R_{v} an f ∈ Int(R, R_{v}) with f(α_{i}) = β_{i}.

2. In that case, the minimal d such that for all β_{1}, …, β_{k} ∈ R_{v} there exists an f ∈ Int(R, R_{v}) with f(α_{i}) = β_{i} and deg f ≤ d, is d = ∑_{j=0}^{n}(d_{j} − 1)[R : I_{j}], where d_{0}, …, d_{n} are the dimensions of the set {α_{1}, …, α_{k}}.

6. Interpolation by integer-valued polynomials on Krull rings

We now turn to Krull rings and characterize those arguments r_{1}, …, r_{n} ∈R that for every choice of values s_{1}, …, s_{n} ∈ R admit an interpolating polynomial f ∈ Int(R). We denote the set of prime ideals of height 1 in R by Spec^{1}(R).

6.1 Lemma. Let v be a discrete valuation on a field K. Suppose f = ∑_{k=0}^{n} a_{k}x^{k} in K[x] splits over K as f(x) = a_{n}(x − b_{1}) … (x − b_{m})(x − c_{1}) … (x − c_{l}), where v(b_{i}) < 0 and v(c_{i}) ≥ 0. Let μ = min_{0≤k≤n} v(a_{k}) and set f_{+}(x) = (x−c_{1}) … (x−c_{l}) then v(f(r)) = μ + v(f_{+}(r)) for all r ∈ R_{v}.

Proof. If r ∈ R_{v}, v(r − b_{i}) = v(b_{i}) and v(f(r)) = v(a_{n}) + ∑_{i=1}^{m} v(b_{i}) + v(f_{+}(r)). We will show that ∑_{i=1}^{m} v(b_{i}) = μ−v(a_{n}). Let a_{n}^{−1}f(x) = x^{n} +a′_{n−1}x^{n−1} +…+a′_{0} then μ − v(a_{n}) = min_{0≤k≤n} v(a′_{k}) and a′_{k} is up to sign the elementary symmetric polynomial of degree n − k in the b_{i} and c_{i}, so that min_{0≤k≤n} v(a′_{k}) = v(a′_{n−m}) = v(e_{m}(b_{1}, …, b_{m}, c_{1}, …, c_{l})) = ∑_{i=1}^{m} v(b_{i}). □

6.2 Lemma. Let R be a domain, r_{1}, …, r_{n+1} ∈ R and a_{j} = r_{j} −r_{n+1} (1 ≤ j ≤ n). Then there exists f ∈ Int(R) with f(r_{j}) = 0 (1 ≤ j ≤ n) and f(r_{n+1}) = 1 if and only if there exists g ∈ Int(R) with g(a_{j}) = 0 (1 ≤ j ≤ n) and g(0) = 1.

Proof. (⇒) g(x): = f(x + r_{n+1}) (⇐) f(x): = g(x − r_{n+1}) □

6.3 Theorem. Let R be a Krull ring and let r_{1}, …, r_{n+1} (distinct) ∈ R such that r_{i} ≢ r_{n+1} mod P (1 ≤ i ≤ n) for all P ∈ Spec^{1}(R) with [R: P] = ∞. Then there exists f ∈ Int(R) with f(r_{i}) = 0 (1 ≤ i ≤ n) and f(r_{n+1}) = 1.

Proof. Let a_{j} = r_{j} − r_{n+1} for 1 ≤ j ≤ n. The a_{j} are distinct non-zero elements of R, none of which are contained in any P ∈ Spec^{1}(R) with [R : P] = ∞. By Lemma 6.2, we want an f ∈ Int(R) with f(a_{j}) = 0 for 1 ≤ j ≤ n and f(0) = 1. We will first construct a polynomial g ∈ K[x] with g(a_{j}) = 0 for 1 ≤ j ≤ n, such that for every essential valuation v of R and every r ∈ R, v(g(r)) ≥ v(g(0)) and then set f(x) = g(x)/g(0).

Let P = {P ∈ Spec^{1}(R) | ∃j a_{j} ∈ P } then P is a finite set of maximal ideals of finite index. Also let, for P ∈ P, m_{P} = max{m ∈ ℕ | ∃j a_{j} ∈ P^{m}} and define I = ⋂_{P ∈P} P^{m_{P}} = ∏_{P ∈P} P^{m_{P}}. Let N = [R : I]. Using the Chinese Remainder Theorem mod P^{m_{P} +1} for P ∈ P, we can get a system of representatives (b_{i})_{i=1}^{N} of R mod I with the property that for all i and all P ∈ P, b_{i} ∉ P^{m_{P} +1}. Note that for P ∈ P and k ≤ m_{P}, the number of b_{i} in any given residue class of P^{k} is N/ [R: P^{k}], since I is an ideal contained in P^{k}. In other words,

∀r ∈ R ∀P ∈ P ∀k ≤ m_{P}  |\{i | v_{P} (r − b_{i}) ≥ k\}| = \frac{N}{[R: P^{k}]} .

Let Q = {Q ∈ Spec^{1}(R) \ P | ∃i b_{i} ∈ Q} and for Q ∈ Q let l_{Q} be the maximal l ∈ ℕ such that b_{i} ∈ Q^{l} for some i. Let c ∈ R with v_{Q}(c) = l_{Q} + 1 for all Q ∈ Q, and v_{P} (c) = 0 for all P ∈ P. Also, let Q′ = {Q ∈ Spec^{1}(R) | v_{Q}(c) > 0}, then Q ⊆ Q′ and Q′ ∩ P = ∅.

We set b′_{i} = c^{−1}b_{i}. Then v_{Q}(b′_{i}) < 0 for all Q ∈ Q′ and 0 ≤ v_{P} (b′_{i}) < m_{P} + 1 for all P ∈ P. If P ∈ P and r ∈ R, we have v_{P} (r − b′_{i}) = v_{P} (c^{−1}(cr − b_{i})) = v_{P} (cr − b_{i}). Therefore, for all r ∈ R,

∀P ∈ P ∀k ≤ m_{P}  |\{i | v_{P} (r − b′_{i}) ≥ k\}| = |\{i | v_{P} (cr − b_{i}) ≥ k\}| = \frac{N}{[R: P^{k}]}

and in particular |{i | v_{P} (b′_{i}) ≥ k}| = N/ [R: P^{k}].

Let m be the maximal number of a_{i} in any residue class of I in R and set h(x) = ∏_{i=1}^{N}(x − b′_{i})^{m}. To get a polynomial g with g(a_{j}) = 0 for 1 ≤ j ≤ n, we now replace certain roots of h with the elements a_{1}, …, a_{n}. Since the b_{i} are a complete system of residues mod I in R, there exists for every j ∈ {1, …, n} an i_{j} with b_{i_{j}} ≡ ca_{j} mod I.

Let g(x) = ∏_{i=1}^{mN}(x − c_{i}) be the polynomial resulting from h by replacing, for each j ∈ {1, …, n}, one copy of b′_{i_{j}} in the multiset of roots of h by a_{j}. (If i_{j} = i_{k} for k ≠ j this means ca_{j} ≡ ca_{k} mod I and therefore a_{j} ≡ a_{k} mod I, and by the definition of m, b′_{i_{j}} occurs with sufficient multiplicity as a root of h that every a_{k} ∈ a_{j} + I can be exchanged for a different copy of b′_{i_{j}}.) Note that for P ∈ P, 0 ≤ v_{P} (c_{i}) < m_{P} + 1 for all i.

We claim that for all essential valuations v of R and all r ∈R, v(g(r))≥v(g(0)). First, assume P ∈ P. For all r ∈ R, if k ≤ m_{P} then

v_{P} (r − b′_{i_{j}}) ≥ k ⟺ v_{P} (r − a_{j}) ≥ k  (∗)

(and consequently |{i | v_{P} (c_{i}) ≥ k}| = m |{i | v_{P} (b′_{i}) ≥ k}|). This is so because v_{P} (r − b′_{i_{j}}) = v_{P} (c^{−1}(cr − b_{i_{j}})) = v_{P} (cr − b_{i_{j}}) = v_{P} (cr − ca_{j} + d) with d ∈ I, and then v_{P} (d) ≥ m_{P} ≥ k implies that v_{P} (cr − ca_{j} + d) ≥ k if and only if v_{P} (r − a_{j}) = v_{P} (cr − ca_{j}) ≥ k. We abbreviate ∑_{i=1}^{m_{P}} \frac{N}{[R:P^{k}]} by γ_{P} and get

v_{P} (g(r)) = ∑_{i=1}^{mN} v_{P} (r − c_{i}) = ∑_{k≥1}|{i | v_{P} (r − c_{i}) ≥ k}| ≥

≥ ∑_{k=1}^{m_{P}}|{i | v_{P} (r − c_{i}) ≥ k}| =^{(∗)} m ∑_{k=1}^{m_{P}}|{i | v_{P} (r − b′_{i}) ≥ k}| = mγ_{P} ,

while v_{P} (g(0)) =

= ∑_{k≥1}|{i | v_{P} (c_{i}) ≥ k}| = ∑_{k=1}^{m_{P}}|{i | v_{P} (c_{i}) ≥ k}| =^{(∗)} m ∑_{k=1}^{m_{P}}|{i | v_{P} (b′_{i}) ≥ k}| = mγ_{P} .

Now consider Q ∈ Q′. For all i, j, v_{Q}(b′_{i}) < 0 and v_{Q}(a_{j}) = 0. If g(x) = ∑_{k=0}^{mN} d_{k}x^{k} and μ = min_{1≤k≤mN} v_{Q}(d_{k}) then for all r ∈ R we have (using Lemma 6.1)

v_{Q}(g(r)) = μ + v_{Q}(∏_{j=1}^{n}(r − a_{j})) ≥ μ = μ + v_{Q}(∏_{j=1}^{n} a_{j}) = v_{Q}(g(0)).

For the remaining essential valuations v of R, v(c_{i}) = 0 for all i. Therefore, if r ∈ R, v(g(r)) = ∑_{i=1}^{mN} v(r − c_{i}) ≥ 0 = ∑_{i=1}^{mN} v(c_{i}) = v(g(0)).

Now let f(x) = g(x)/g(0). For j = 1, …, n, f(a_{j}) = 0 because g(a_{j}) = 0, and clearly f(0) = 1. Also, f ∈ Int(R), because for all r ∈ R and every essential valuation v of R, v(g(r)) ≥ v(g(0)) and therefore v(f(r)) ≥ 0. □

6.4 Remark. If P is a prime ideal in a domain R with [R : P] = ∞ it is well known that Int(R, R_{P}) = R_{P} [x]. Every f ∈ Int(R, R_{P}) of degree n is determined by its values at n + 1 arguments a_{0}, …, a_{n} ∈ R and is therefore equal to the Lagrange interpolation polynomial

φ(x) = ∑_{i=0}^{n} f(a_{i})\frac{∏_{j≠i}(x − a_{j})}{∏_{j≠i}(a_{i} − a_{j})} .

If the a_{i} are chosen pairwise incongruent mod P, then φ(x) is clearly in R_{P} [x].

6.5 Corollary. Let r_{1}, …, r_{n} be distinct elements of a Krull ring R. If and only if the r_{i} are pairwise incongruent mod all P ∈ Spec^{1}(R) with [R : P] = ∞ there exists for all s_{1}, …, s_{n} ∈ R an f ∈ Int(R) with f(r_{i}) = s_{i} for 1 ≤ i ≤ n.

Proof. The “if” part follows from the Theorem, since R-linear combinations of polynomials in Int(R) are again in Int(R). Conversely, if a, a′ ∈ R are congruent mod P ∈ Spec^{1}(R) with [R: P] = ∞ then there is no f ∈ Int(R, R_{P}) with f(a) = 0 and f(a′) = 1, since f(a) ≡ f(a′) mod P for all f ∈ Int(R, R_{P}) ⊇ Int(R), by Lemma 5.2 (or by the fact that Int(R, R_{P}) = R_{P} [x], see 6.4). □

References

1. Y. Amice, Interpolation p-adique, Bull. Soc. Math. France 92 (1964) 117–180.

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

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

4. P.-J. Cahen and J.-L. Chabert, Integer-Valued Polynomials (Mathematical Surveys and Monographs vol. 48), Amer. Math. Soc., Providence RI, 1997.

5. L. Carlitz, Finite sums and interpolation formulas over GF[p^{n}, x], Duke Math. J. 15 (1948) 1001–1012.

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

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

8. S. Frisch, Binomial Coefficients Generalized with respect to a Discrete Valuation, to appear in Proc. of 7^{th} Int’l Conf. on Fibonacci Numbers and Their Applications in Graz, Austria, 1996, G. E. Bergum, ed.

9. R. Gilmer, W. Heinzer and D. Lantz, The Noetherian property in rings of integer-valued polynomials, Trans. Amer. Math. Soc. 338 (1993), 187–199.

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

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

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

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

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

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

16. C. G. Wagner, Interpolation series for continuous functions on π-adic completions of GF(q, x), Acta Arith. 17 (1971), 389–406.

Institut für Mathematik C Technische Universität Graz Steyrergasse 30

integer-valued polynomial interpolation

A-8010 Graz, Austria

e-mail: frisch@blah.math.tu-graz.ac.at