Deformations of the Taylor Formula

Emmanuel Ferrand Institut Mathématique de Jussieu UMR 7586 du CNRS Université Pierre et Marie Curie 4, place Jussieu 75252 Paris Cedex France

                    ferrand@math.jussieu.fr

Abstract

Given a sequence x = {x_{n}, n ∈ ℕ} with integer values, or more generally with values in a ring of polynomials with integer coefficients, one can form the generalized binomial coefficients associated with x, \binom{n}{m}_{x} = ∏_{l=1}^{m} \frac{x_{n−l+1}}{x_{l}}. In this note we introduce several sequences that possess the following remarkable feature: the fractions \binom{n}{m}_{x} are in fact polynomials with integer coefficients.

1 Introduction

By a deformation of the integers we mean a sequence x = {x_{n}, n ∈ ℕ} of polynomials in one or more variables and with integral coefficients, having the property that there exists some value q_{0} of the variables such that ∀n ∈ ℕ, x_{n}(q_{0}) = n. The quantum integers x_{n} = ∑_{l=0}^{n−1} q^{l} are a typical example of a deformation of the integers. Another example is given by the version of the Chebyshev polynomials defined by x_{n}(cos(θ)) = \frac{sin(nθ)}{sin(θ)}.

In this note we consider some deformations of the factorial function and of the binomial coefficients that are induced by such deformations of the integers. This situation can be interpreted as a deformation of the Taylor formula, as explained below. Given a polynomial P of degree n with complex coefficients, the Taylor expansion at some point X gives

P (X + 1) = P (X) + 1 · \frac{dP}{dX} (X) + \frac{1^{2}}{2!} · \frac{d^{2}P}{dX^{2}} (X) + ⋯ + \frac{1^{n}}{n!} · \frac{d^{n}P}{dX^{n}} (X).

In other words, if one denotes by τ : ℂ[X] → ℂ[X] the “translation by one” operator, defined by τ(P)(X) = P (X + 1), then τ = exp(\frac{d}{dX}). A matrix version of this fact can be stated as follows. Denote by P and D the semi-infinite matrices whose coefficients are, respectively, P_{i,j} = \binom{i}{j} and D_{i,j} = i if i = j + 1 and 0 otherwise, (i, j) ∈ ℕ^{2}. Then P = exp(D).

P = (\begin{matrix}1 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & … \\ 1 & 2 & 1 & 0 & … \\ 1 & 3 & 3 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) D = (\begin{matrix}0 & 0 & 0 & 0 & … \\ 1 & 0 & 0 & 0 & … \\ 0 & 2 & 0 & 0 & … \\ 0 & 0 & 3 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix})

This suggests the following way to deform the Taylor formula. Replace the sequence ℕ of the integers which appears as the non-zero coefficients of D by the terms of a sequence x = {x_{n}, n ∈ ℕ} with values in some polynomial ring. Denote by D_{x} the corresponding matrix. Given some integer n, define n!_{x} to be the polynomial n!_{x} = ∏_{l=1}^{n} x_{l}. Define exp_{x} to be the formal series exp_{x}(t) = ∑_{k=0}^{∞} \frac{t^{k}}{k!_{x}}. Observe that the matrix exp_{x}(D_{x}) is well defined since, coefficients-wise, the summation is finite. Its coefficients exp_{x}(D_{x})_{i,j} will be denoted by the symbols \binom{i}{j}_{x} and will be called the generalized binomial coefficients associated with the sequence x. Note that

\binom{i}{j}_{x} = ∏_{l=1}^{j} \frac{x_{i−l+1}}{x_{l}}

if i ≥ j, and 0 otherwise.

This definition has appeared already in several contexts; see, for example, Knuth and Wilf [4] for an introduction to the relevant literature. Note that the fractions \binom{i}{j}_{x} have no a priori reason to be polynomials with integer coefficients. In fact, such a phenomenon appears only for very specific sequences x.

In this note we are interested in deformations of the integers x that possess this property. The first part of the paper (section 2) is a variation on the classical theme of quantum integers and q-binomials. It deals with sequences that satisfy a second order linear recurrence relation. In the second part, (section 3), we deform the integers and the q-binomials in a less standard way, using a sequence that satisfies a first order non-linear recurrence relation. In the third part (section 4), we introduce a sequence related to the Fermat numbers (which is not a deformation of the integers), and we show that the corresponding generalized binomial coefficients are polynomials with integer coefficients.

Let us mention that Knuth and Wilf [4] showed that if a sequence x with integral values is a gcd-morphism (that is, x_{gcd(n,m)} = gcd(x_{n}, x_{m})), then the associated binomial coefficients are integers.

2 q-binomials

The properties of the so-called “quantum integers”

[n]_{q} = ∑_{l=0}^{n−1} q^{l} = \frac{1 − q^{n}}{1 − q}

and the associated “q-binomials” were investigated long before the introduction of quantum mechanics (see [2]). We rephrase below an approach developed by Carmichael [1] (and probably already implicit in earlier works). It deals with a slightly more general, two-variable version of the quantum integers.

Consider the sequence x with values in ℤ[a, b] defined by the following linear recurrence relation of order 2:

x_{0} = 0, x_{1} = 1, x_{n+1} = a · x_{n} + b · x_{n−1}.

This sequence specializes to the quantum integers when a = q + 1 and b = −q (and to the usual integers for a = 2 and b = −1).

Remark. x_{n} is given by the following explicit formula:

x_{n} = ∑_{l=1}^{n} \binom{l − 1}{n − l}a^{2l−n−1}b^{n−l}

as one can check by induction. □

Proposition 1. (rephrased from [1]).

• x : ℕ → ℤ[a, b] is a gcd-morphism:

gcd(x_{n}, x_{m}) = x_{gcd(n,m)}.

• The associated binomial coefficients \binom{n}{m}_{x} are polynomials in a and b with integral coefficients.

□

The first few rows of the corresponding deformation of Pascal’s triangle are as follows:

(\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & a & 1 & 0 & 0 & 0 \\ 1 & a^{2} + b & a^{2} + b & 1 & 0 & 0 \\ 1 & a^{3} + 2ba & (a^{2} + 2b)(a^{2} + b) & a^{3} + 2ba & 1 & 0 \\ 1 & a^{4} + 3ba^{2} + b^{2} & (a^{4} + 3ba^{2} + b^{2})(a^{2} + 2b) & (a^{4} + 3ba^{2} + b^{2})(a^{2} + 2b) & a^{4} + 3ba^{2} + b^{2} & 1 \end{matrix})

Many classical sequences of integers or polynomials arise as solutions of second order recurrence relations with the appropriate initial conditions. The corresponding deformations of the Pascal triangle have often been considered separately in the literature. They receive a unified treatment through Carmichael’s approach.

Example 1. For a = b = 1, the sequence x specializes to the Fibonacci sequence (\underline{A000045} in [5]), and the triangle looks as follows:

(\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 1 & 0 & 0 & 0 & … \\ 1 & 2 & 2 & 1 & 0 & 0 & … \\ 1 & 3 & 6 & 3 & 1 & 0 & … \\ 1 & 5 & 15 & 15 & 5 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) .

Example 2. For a = 3 and b = −2, the sequence x specializes to the Mersenne numbers (\underline{A000225} of [5]), x_{n} = 2^{n} − 1. The triangle then looks like

(\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 3 & 1 & 0 & 0 & 0 & … \\ 1 & 7 & 7 & 1 & 0 & 0 & … \\ 1 & 15 & 35 & 15 & 1 & 0 & … \\ 1 & 31 & 155 & 155 & 31 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) .

Example 3. For a = 2s and b = −1, the sequence x_{n} = U_{n−1}(s), where U_{n} is the n−th Chebyshev polynomial of the second kind. This implies that, for any (n, m) ∈ ℤ^{2}, the polynomial ∏_{l=0}^{m} U_{n−l} is always divisible by ∏_{l=0}^{m} U_{l} in ℤ[s].

3 Iterations of a polynomial

Fix some parameter d ∈ ℕ. Consider the polynomial

p(X, a_{0}, …, a_{d}) = ∑_{k=0}^{d} a_{k}X^{k}

and the sequence x with values in ℤ[a_{0}, …, a_{d}] defined by the following recurrence relation:

x_{0} = 0, x_{n} = p(x_{n−1}, a_{0}, …, a_{d}).

Note that this sequence is a deformation of the integers that encompasses the quantum integers (i.e., the case d = 1, a_{0} = 1, a_{1} = q, for which x_{n} = [n]_{q}).

Proposition 2. • x : ℕ → ℤ[a_{0}, …, a_{d}] is a gcd-morphism: x_{gcd(n,m)} = gcd(x_{n}, x_{m}).

• The associated binomial coefficients \binom{n}{m}_{x} are polynomials of the variables a_{0}, …, a_{d}, with integral coefficients.

Proof. Denote by ϕ_{a} the function x → p(x, a_{0}, …, a_{n}) and by ϕ_{a}^{∘n} its n−th iterate, so that x_{n} = ϕ_{a}^{∘n}(0). For any k ≤ n, x_{n} = ϕ_{a}^{∘k}(x_{n−k}). Writing ϕ_{a}^{∘k}(x) = ϕ_{a}^{∘k}(0) + x · Q(x) gives x_{n} = ϕ_{a}^{∘k}(0) + x_{n−k} · Q(x_{n−k}). In other words, for any k ≤ n, there exists a polynomial R_{n,k} in ℤ[a_{0}, …, a_{n}] such that

x_{n} = x_{k} + x_{n−k} · R_{n,k}.

This implies that, for any (k, l) ∈ ℤ^{2}, x_{kl} is divisible by x_{k} and by x_{l}. Furthermore this implies the following recurrence relation, from which the polynomiality of \binom{n}{m}_{x} follows by induction:

\binom{n}{k}_{x} = x_{n} · \frac{x_{n−1} · · · · · x_{n−k+1}}{1 · x_{2} · · · · · x_{k}} = \binom{n − 1}{k − 1}_{x} + R_{n,k} · \binom{n − 1}{k}_{x}.

Denote by δ the gcd of n and k. We already know that x_{d} is a divisor of gcd(x_{n}, x_{k}). Write δ = α · n + β · k, with α ≥ 0 and β ≤ 0, so that x_{αn} = x_{δ} + x_{βk} · R_{αn,δ}. Any common divisor of x_{n} and x_{k} is also a common divisor of x_{αn} and x_{βk}, and hence a divisor of x_{δ}. This proves that x_{δ} = gcd(x_{n}, x_{k}). □

Even in the case d = 2, \binom{n}{m}_{x} is a rather complicated polynomial. For example \binom{5}{3}_{x} is of degree 11 in a_{1} and of degree 21 in a_{0} and a_{2}. If one specializes to the case a_{0} = a_{1} = 1 and a_{2} = q − 1, the corresponding one-parameter deformation of Pascal’s triangle (which is recovered at q = 1) looks like

(\begin{matrix}1 & 0 & 0 & … \\ 1 & 1 & 0 & … \\ 1 & 1 + q & 1 & … \\ 1 & 1 + q^{2} + q^{3} & 1 + q^{2} + q^{3} & … \\ 1 & (1 + q)(q^{6} − q^{4} + 2q^{3} − q^{2} + 1) & (1 + q^{2} + q^{3})(q^{6} − q^{4} + 2q^{3} − q^{2} + 1) & … \\ ⋮ & ⋮ & ⋮ & ... \end{matrix}) .

Remark. Consider now a polynomial p(X, a_{1}, …, a_{d}) = ∑_{k=1}^{d} a_{k}X^{k} whose constant term vanishes, and the sequence x with values in ℤ[a_{0}, …, a_{d}] defined by the following recurrence relation:

x_{0} = a_{0}, x_{n} = p(x_{n−1}, a_{1}, …, a_{d}).

The corresponding \binom{n}{m}_{x} are also polynomials in the variables a_{0}, …, a_{1} with integral coefficients, for all (n, m) ∈ ℤ^{2}. This is due to the fact that, if n ≥ m, x_{n} is a multiple of x_{m}, which implies that \binom{n}{m}_{x} is a multiple of \binom{n−1}{m−1}_{x}.

On the other hand, this sequence x is not a deformation of the integers, since ∀n ≥ m, x_{m} divides x_{n}.

4 Fermat polynomials

The sequence of polynomials considered in this section is not a deformation of the integers, but is related to the Fermat numbers (\underline{A000215} of [5]). It is defined explicitly by the formula

x_{n} = ∑_{l=0}^{n−1}(\binom{n − 1}{l} mod 2) · X^{l}.

If n > 0, x_{n} is the unique element of ℤ[X] with coefficients in {0, 1} that is congruent to (1 + X)^{n−1} modulo 2. The first few terms are x_{0} = 0, x_{1} = 1, x_{2} = 1 + X, x_{3} = 1 + X^{2}, x_{4} = 1 + X + X^{2} + X^{3}.

By a theorem of Lucas (see, for example [3, Ex. 61, p˙248]), the parity of \binom{n}{m} is determined by the binary decomposition of n and m as follows: Write n = ∑_{l∈ℕ} ϵ_{l}2^{l} and m = ∑_{l∈ℕ} η_{l}2^{l}, with ϵ_{l}, η_{l} ∈ {0, 1}, ∀l ∈ ℕ. Then

\binom{n}{m} = ∏_{l∈ℕ} \binom{ϵ_{l}}{η_{l}} mod 2.

Since \binom{ϵ_{l}}{η_{l}} = 1 + η_{l} · (ϵ_{l} − 1), this can be rephrased in a compact way as follows. With an integer p, associate the set K_{p} of the exponents that appear in the binary decomposition of p, so that n = ∑_{l∈K_{n}} 2^{l} and m = ∑_{l∈K_{m}} 2^{l}. Then \binom{n}{m} is odd if and only if K_{m} ⊂ K_{n}.

For example, if n − 1 = 2^{k} is a power of 2, \binom{n−1}{l} is even for any 1 ≤ l ≤ 2^{k} − 1. Hence x_{2^{k}+1} = 1 + X^{2^{k}}, and x_{2^{k}+1} specializes to the k−th Fermat number 1 + 2^{2^{k}} at X = 2. If n = 2^{k} is a power of 2, \binom{n−1}{l} is odd for any 0 ≤ l ≤ 2^{k} − 1. Hence x_{2^{k}} = ∑_{0}^{2^{k}−1} X^{l} = \frac{X^{2^{k}} −1}{X−1}. In particular, for all k ∈ ℕ, x_{2^{k}+1} = 2 + (X − 1)x_{2^{k}}.

Proposition 3. • x_{n+1} = ∏_{l∈K_{n}}(1 + X^{2^{l}}), and x_{m} divides x_{n} in ℤ[X] if and only if \binom{n−1}{m−1} is odd.

• The associated binomial coefficients \binom{n}{m}_{x} are polynomials in X, with integral coefficients.

Proof. Observe that, for any (l, m) ∈ ℕ^{2},

(1 + X)^{2^{l}+m} = (1 + X)^{2^{l}}(1 + X)^{m} ≡ (1 + X^{2^{l}})(1 + X)^{m} mod 2.

This imply that

(1 + X)^{(∑_{l∈Kn} 2^{l})} ≡ ∏_{l∈K_{n}}(1 + X^{2^{l}}) mod 2.

On the other hand ∏_{l∈K_{n}}(1+X^{2^{l}}) is an element of ℤ[X] whose coefficients are in {0, 1}. But x_{n+1} is by definition the unique element of ℤ[X] whose coefficients are in {0, 1} and which is congruent to (1 + X)^{n} modulo 2. Hence x_{n+1} = ∏_{l∈K_{n}}(1 + X^{2^{l}}). From this factorization it follows that x_{m} divides x_{n} in ℤ[X] if and only if K_{m−1} ⊂ K_{n−1}. By Lucas’s theorem, this last condition is equivalent to the oddity of \binom{n−1}{m−1}.

To prove that \binom{n}{m}_{x} is a polynomial, we will study the exponent α_{l}(n, m) of each factor (1 + X^{2^{l}}) in the decomposition \binom{n}{m}_{x} = ∏_{l∈ℕ}(1 + X^{2^{l}})^{α_{l}(n,m)}. Denote by ϵ_{l} : ℕ → \{0, 1\} the function such that ϵ_{l}(p) = 1 iff l ∈ K_{p}, so that p = ∑_{l∈ℕ} ϵ_{l}(p)2^{l}. It follows that α_{l}(n, m) = ∑_{p=1}^{m} ϵ_{l}(n − p + 1 − 1) − ϵ_{l}(p − 1).

The function ϵ_{l} is periodic, of period 2^{l+1}. Hence, when estimating α_{l}(n, m), one can assume that m is smaller than 2^{l+1}. Observe that ϵ_{l}(p) = 0 for p ∈ {0, …, 2^{l} − 1}, and that ϵ_{l}(p) = 1 for p ∈ {2^{l}, …, 2^{l+1} − 1}. The sum ∑_{p∈{r,...,r+m−1}} ϵ_{l}(p) over a ”window” of width m is bounded from below by max(0, m − 2^{l}). This minimal value is attained at r = 0. This proves that ∑_{p=1}^{m} ϵ_{l}(n − p) ≥ ∑_{p=1}^{m} ϵ_{l}(p − 1), and hence that α_{l}(n, m) ≥ 0. □

Example. The first few rows of the corresponding triangle are as follows:

(\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 1 + X & 1 & 0 & 0 & 0 & … \\ 1 & 1 + X^{2} & 1 + X^{2} & 1 & 0 & 0 & … \\ 1 & 1 + X + X^{2} + X^{3} & (1 + X^{2})^{2} & 1 + X + X^{2} + X^{3} & 1 & 0 & … \\ 1 & 1 + X^{4} & (1 + X^{2})(1 + X^{4}) & (1 + X^{2})(1 + X^{4}) & 1 + X^{4} & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) .

We have seen that the specialization of x at X = 2 gives a sequence that interpolates in a natural way between the Fermat numbers. The specialization 1, 2, 2, 4, 2, … at X = 1 is also meaningful: x_{n}(1) = 2^{|K_{n−1}|}, where |K_{n−1}| denotes the number of non-vanishing terms in the binary expansion of n − 1 (\underline{A000120} of [5]).

References

[1] R. D. Carmichael, On the numerical factors of the arithmetic forms α^{n} ± β^{n}, Ann. Math. 15 (1913–1914), 30–70.

[2] P. Cheung and V. Kac, Quantum Calculus, Springer-Verlag, New York, 2002.

[3] R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.

[4] D. E. Knuth, H. S. Wilf, The power of a prime that divides a generalized binomial coefficient, J. Reine Angew. Math 396 (1989), 212–219.

[5] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences,

    http://www.research.att.com/∼njas/sequences/.

2000 Mathematics Subject Classification: Primary 05A10; Secondary 05A30, 11B39, 11B65. Keywords: generalized binomial coefficients.

(Concerned with sequences \underline{A000045}, \underline{A000120}, \underline{A000215}, \underline{A000225}, and \underline{A000317}.)

Received September 22 2005; revised version received October 8 2006. Published in Journal of Integer Sequences, December 31 2006.

Return to Journal of Integer Sequences home page.