\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}{Proposition}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{lemma}{Lemma}[section] \def \shar{{= \hskip-4mm / \hskip-1mm / \hskip-4mm =}} \def \RM{\mathbb{R}}% corps des reels \def \NM{\mathbb{N}}% entiers naturels \def \ZM{\mathbb{Z}}% entiers relatifs \def \CM{\mathbb{C}}% nombres complexes \def \QM{\mathbb{Q}}% nombres rationnels \newtheorem{prop}{Proposition} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Deformations of the Taylor Formula } \vskip 1cm \large Emmanuel Ferrand\\ Institut Math{\'e}matique de Jussieu\\ UMR 7586 du CNRS\\ Universit{\'e} Pierre et Marie Curie\\ 4, place Jussieu \\ 75252 Paris Cedex\\ France\\ \href{mailto:ferrand@math.jussieu.fr}{\tt ferrand@math.jussieu.fr}\\ \end{center} \vskip .2 in \begin{abstract} Given a sequence $x=\{x_n, \ n \in \NM \}$ with integer values, or more generally with values in a ring of polynomials with integer coefficients, one can form the {\it generalized binomial coefficients} associated with $x$, ${\binom nm}_x=\prod_{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 nm_x$ are in fact polynomials with integer coefficients. \end{abstract} \section{Introduction} By a {\it deformation of the integers} we mean a sequence $x=\{x_n, \ n \in \NM \}$ 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 $\forall n \in \NM, x_n(q_0)=n$. The {\it quantum integers} $x_n=\sum_{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(\theta))=\frac{\sin(n\theta)}{\sin(\theta)}$. 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 \cdot \frac{dP}{dX}(X)+\frac{1^2}{2!}\cdot\frac{d^2P}{dX^2}(X)+ \cdots +\frac{1^n}{n!}\cdot\frac{d^nP}{dX^n}(X).$$ In other words, if one denotes by $\tau:\CM[X] \rightarrow \CM[X]$ the ``translation by one" operator, defined by $\tau (P) (X)=P(X+1)$, then $\tau=\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) \in \NM^2$. Then $P=\exp(D)$. $$ P~=\begin{pmatrix} 1 & 0 & 0 & 0 & \dots\\ 1 & 1 & 0 & 0 & \dots \\ 1 & 2 & 1 & 0 & \dots \\ 1 & 3 & 3 & 1 & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix} \ \ \ \ D~=\begin{pmatrix} 0 & 0 & 0 & 0 & \dots\\ 1 & 0 & 0 & 0 & \dots \\ 0 & 2 & 0 & 0 & \dots \\ 0 & 0 & 3 & 0 & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix} \ \ \ $$ This suggests the following way to deform the Taylor formula. Replace the sequence $\NM$ of the integers which appears as the non-zero coefficients of $D$ by the terms of a sequence $x=\{x_n, \ n \in \NM \}$ 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=\prod_{l=1}^n x_l$. Define $\exp_x$ to be the formal series $\exp_x(t)= \sum_{k=0}^\infty \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 {\em the generalized binomial coefficients associated with the sequence $x$}. Note that $$\binom{i}{j}_x=\prod_{l=1}^{j} \frac{x_{i-l+1}}{x_l}$$ if $i \geq j$, and $0$ otherwise. This definition has appeared already in several contexts; see, for example, Knuth and Wilf \cite{KW} 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 \ref{q-bin}) is a variation on the classical theme of {\em quantum integers} and {\em q-binomials}. It deals with sequences that satisfy a second order linear recurrence relation. In the second part, (section \ref{iter}), we deform the integers and the $q$-binomials in a less standard way, using a sequence that satisfies a first order {\it non-linear} recurrence relation. In the third part (section \ref{fermat}), 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 \cite{KW} 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. \section{$q$-binomials}\label{q-bin} The properties of the so-called ``quantum integers'' $$[n]_q=\sum_{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 \cite{CK}). We rephrase below an approach developed by Carmichael \cite{Car} (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 $\ZM[a,b]$ defined by the following linear recurrence relation of order $2$: $$ x_0=0, \ x_1=1, \, x_{n+1}=a \cdot x_n+b\cdot 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$). \bigskip \noindent {\bf Remark.} $x_n$ is given by the following explicit formula: $$x_n=\sum_{l=1}^n \binom{l-1}{n-l}a^{2l-n-1}b^{n-l}$$ as one can check by induction. $\Box$ \bigskip \begin{prop} (rephrased from \cite{Car}). \begin{itemize} \item $x:\NM \rightarrow \ZM[a,b]$ is a $\gcd$-morphism: $$ \gcd(x_n,x_m)=x_{\gcd(n,m)}.$$ \item The associated binomial coefficients $\binom{n}{m}_x$ are polynomials in $a$ and $b$ with integral coefficients. \end{itemize} \end{prop} $\Box$ \bigskip The first few rows of the corresponding deformation of Pascal's triangle are as follows: $$ \begin{pmatrix} 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{pmatrix}$$ 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. \bigskip {\bf Example 1.} For $a=b=1$, the sequence $x$ specializes to the {\em Fibonacci sequence} (\seqnum{A000045} in \cite{OEIS}), and the triangle looks as follows: $$ \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & \dots\\ 1 & 1 & 0 & 0 & 0 & 0 & \dots \\ 1 & 1 & 1 & 0 & 0 & 0 &\dots \\ 1 & 2 & 2 & 1 & 0 & 0 &\dots \\ 1 & 3 & 6 & 3 & 1 & 0 &\dots \\ 1 & 5 & 15 & 15 & 5 & 1&\dots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix}.$$ \bigskip {\bf Example 2.} For $a=3$ and $b=-2$, the sequence $x$ specializes to the {\em Mersenne numbers} (\seqnum{A000225} of \cite{OEIS}), $x_n=2^n-1$. The triangle then looks like $$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & \dots\\ 1 & 1 & 0 & 0 & 0 & 0 & \dots \\ 1 & 3 & 1 & 0 & 0 & 0 &\dots \\ 1 & 7 & 7 & 1 & 0 & 0 &\dots \\ 1 & 15 & 35 & 15 & 1 & 0 &\dots \\ 1 & 31 & 155 & 155 & 31 & 1&\dots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix}.$$ \bigskip {\bf Example 3.} For $a=2s$ and $b=-1$, the sequence $x_n=U_{n-1}(s)$, where $U_n$ is the $n-$th {\em Chebyshev polynomial of the second kind}. This implies that, for any $(n,m) \in \ZM^2$, the polynomial $\prod_{l=0}^m U_{n-l}$ is always divisible by $\prod_{l=0}^m U_{l}$ in $\ZM[s]$. \section{Iterations of a polynomial} \label{iter} Fix some parameter $d \in \NM$. Consider the polynomial $$p(X,a_0,\dots,a_{d})=\sum_{k=0}^d a_kX^k$$ and the sequence $x$ with values in $\ZM[a_0,\dots,a_d]$ defined by the following recurrence relation: $$x_0~=0, \ x_n=p(x_{n-1},a_0,\dots, 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}$). \begin{prop} \begin{itemize} \item $x: \NM \rightarrow \ZM[a_0,\dots,a_d]$ is a $\gcd$-morphism: $x_{\gcd(n,m)}=\gcd(x_n,x_m).$ \ \item The associated binomial coefficients $\binom{n}{m}_x$ are polynomials of the variables $a_0,\dots, a_d$, with integral coefficients. \end{itemize} \end{prop} {\it Proof.} Denote by $\phi_a$ the function $x \rightarrow p(x,a_0,\dots,a_n)$ and by $\phi_a^{\circ n}$ its $n-$th iterate, so that $x_n=\phi_a^{\circ n}(0)$. For any $k\leq n$, $x_n=\phi_a^{\circ k}(x_{n-k})$. Writing $\phi_a^{\circ k}(x)=\phi_a^{\circ k}(0)+x\cdot Q(x)$ gives $x_n=\phi_a^{\circ k}(0)+x_{n-k}\cdot Q(x_{n-k})$. In other words, for any $k \leq n$, there exists a polynomial $R_{n,k}$ in $\ZM[a_0,\dots,a_n]$ such that $$ x_n=x_k + x_{n-k}\cdot R_{n,k}.$$ This implies that, for any $(k,l) \in \ZM^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 \cdot \frac{x_{n-1} \cdot \dots \cdot x_{n-k+1}}{1 \cdot x_2 \cdot \dots \cdot x_k} =\binom{n-1}{k-1}_x+ R_{n,k} \cdot \binom{n-1}{k}_x.$$ Denote by $\delta$ the $\gcd$ of $n$ and $k$. We already know that $x_d$ is a divisor of $\gcd(x_n,x_k)$. Write $\delta=\alpha \cdot n + \beta \cdot k$, with $\alpha\geq 0$ and $\beta \leq 0$, so that $x_{\alpha n}=x_\delta+x_{\beta k}\cdot R_{\alpha n, \delta}$. Any common divisor of $x_n$ and $x_k$ is also a common divisor of $x_{\alpha n }$ and $x_{\beta k}$, and hence a divisor of $x_\delta$. This proves that $x_\delta=\gcd(x_n,x_k)$. $\Box$ 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{pmatrix} 1 & 0 & 0 & \dots \\ 1 & 1 & 0 & \dots \\ 1 & 1+q & 1 & \dots\\ 1 & 1+q^2+q^3 & 1+q^2+q^3 & \dots\\ 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) & \dots \\ \vdots & \vdots & \vdots & \ddots \\ \end{pmatrix}.$$ {\bf Remark.} Consider now a polynomial $p(X,a_1,\dots,a_{d})=\sum_{k=1}^d a_kX^k$ whose constant term vanishes, and the sequence $x$ with values in $\ZM[a_0,\dots,a_d]$ defined by the following recurrence relation: $$x_0~=a_0, \ x_n=p(x_{n-1},a_1,\dots, a_d).$$ The corresponding $\binom{n}{m}_x$ are also polynomials in the variables $a_0,\dots, a_1$ with integral coefficients, for all $(n, m) \in \ZM^2$. This is due to the fact that, if $n\geq 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 {\em not} a deformation of the integers, since $ \forall n \geq m$, $x_m$ divides $x_n $. \section{Fermat polynomials}\label{fermat} The sequence of polynomials considered in this section is not a deformation of the integers, but is related to the Fermat numbers (\seqnum{A000215} of \cite{OEIS}). It is defined explicitly by the formula $$ x_n= \sum_{l=0}^{n-1} (\binom{n-1}{l} \mod \ 2) \cdot X^l.$$ If $n>0$, $x_n$ is the unique element of $\ZM[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 \cite[Ex.\ 61, p\. 248]{GKP}), the parity of $\binom{n}{m}$ is determined by the binary decomposition of $n$ and $m$ as follows: Write $n=\sum_{l\in \NM} \epsilon_l 2^l$ and $m=\sum_{l\in \NM} \eta_l 2^l$, with $\epsilon_l, \eta_l \in \{0,1\}, \forall l \in \NM$. Then $$ \binom nm=\prod_{l \in \NM} \binom{\epsilon_l}{\eta_l} \ \mod \ 2.$$ Since $\binom{\epsilon_l}{\eta_l}= 1+\eta_l\cdot(\epsilon_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=\sum_{l\in K_n}2^l$ and $m=\sum_{l\in K_m}2^l$. Then $\binom{n}{m}$ is odd if and only if $ K_m \subset K_n$. For example, if $n-1=2^k$ is a power of $2$, $\binom{n-1}{l}$ is even for any $1 \leq l \leq 2^k-1$. Hence $x_{2^k+1}=1+X^{2^k}$, and $x_{2^k+1}$ specializes to the $k-$th {\it 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 \leq l \leq 2^k-1$. Hence $x_{2^k}=\sum_{0}^{2^k-1}X^l=\frac{X^{2^k}-1}{X-1}$. In particular, for all $k \in \NM, x_{2^k+1}=2+(X-1)x_{2^k}$. \begin{prop} \begin{itemize} \item $x_{n+1}= \prod_{l \in K_n}(1+X^{2^l})$, and $x_m$ divides $x_n$ in $\ZM[X]$ if and only if $\binom{n-1}{m-1}$ is odd. \\ \item The associated binomial coefficients $\binom{n}{m}_x$ are polynomials in $X$, with integral coefficients. \end{itemize} \end{prop} {\it Proof.} Observe that, for any $(l,m) \in \NM^2$, $$(1+X)^{2^l+m}=(1+X)^{2^l}(1+X)^m \equiv (1+X^{2^l})(1+X)^m \ \mod \ 2. $$ This imply that $$(1+X)^{(\sum_{l \in K_n}2^l)} \equiv \prod_{l \in K_n}(1+X^{2^l}) \ \mod \ 2. $$ On the other hand $\prod_{l \in K_n}(1+X^{2^l})$ is an element of $\ZM[X]$ whose coefficients are in $\{0,1\}$. But $x_{n+1}$ is by definition the unique element of $\ZM[X]$ whose coefficients are in $\{0,1\}$ and which is congruent to $(1+X)^n$ modulo $2$. Hence $x_{n+1}= \prod_{l \in K_n}(1+X^{2^l})$. From this factorization it follows that $x_m$ divides $x_n$ in $\ZM[X]$ if and only if $K_{m-1} \subset 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 $\alpha_l(n,m)$ of each factor $(1+X^{2^l})$ in the decomposition $\binom{n}{m}_x= \prod_{l \in \NM}(1+X^{2^l})^{\alpha_l(n,m)}$. Denote by $\epsilon_l: \NM \rightarrow \{0,1\}$ the function such that $\epsilon_l(p)=1 $ iff $l \in K_p$, so that $p=\sum_{l \in \NM} \epsilon_l(p)2^l$. It follows that $\alpha_l(n,m)=\sum_{p=1}^m \epsilon_l(n-p+1-1) - \epsilon_l(p-1)$. The function $\epsilon_l$ is periodic, of period $2^{l+1}$. Hence, when estimating $\alpha_l(n,m)$, one can assume that $m$ is smaller than $2^{l+1}$. Observe that $\epsilon_l(p)=0$ for $p \in \{0, \dots, 2^l-1\}$, and that $\epsilon_l(p)=1$ for $p \in \{2^l, \dots, 2^{l+1}-1\}$. The sum $\sum_{p \in \{r,\dots,r+m-1\}} \epsilon_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 $\sum_{p=1}^m \epsilon_l(n-p) \geq \sum_{p=1}^m \epsilon_l(p-1)$, and hence that $\alpha_l(n,m) \geq 0$. $\Box$ \bigskip {\bf Example.} The first few rows of the corresponding triangle are as follows: $$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & \dots\\ 1 & 1 & 0 & 0 & 0 & 0 & \dots \\ 1 & 1+X & 1 & 0 & 0 & 0 &\dots \\ 1 & 1+X^2 & 1+X^2 & 1 & 0 & 0 &\dots \\ 1 & 1+X+X^2+X^3 & (1+X^2)^2 & 1+X+X^2+X^3 & 1 & 0 &\dots \\ 1 & 1+X^4 & (1+X^2)(1+X^4) & (1+X^2)(1+X^4) & 1+X^4 & 1&\dots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix}.$$ 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,\dots$ 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$ (\seqnum{A000120} of \cite{OEIS}). \begin{thebibliography}{99} \bibitem{Car} R. D. Carmichael, { On the numerical factors of the arithmetic forms $\alpha^n \pm \beta^n$}, {\it Ann. Math.} {\bf 15} (1913--1914), 30--70. \bibitem{CK} P. Cheung and V. Kac, {\it Quantum Calculus}, Springer-Verlag, New York, 2002. \bibitem{GKP} R. L. Graham, D. E. Knuth and O. Patashnik, {\it Concrete Mathematics}, 2nd edition, Addison-Wesley, 1994. \bibitem{KW} D. E. Knuth, H. S. Wilf, The power of a prime that divides a generalized binomial coefficient, {\it J. Reine Angew. Math} {\bf 396} (1989), 212--219. \bibitem{OEIS} N.~J.~A.\ Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, \href{http://www.research.att.com/~njas/sequence/}{\tt http://www.research.att.com/$\sim$njas/sequences/}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A10; Secondary 05A30, 11B39, 11B65. \noindent \emph{Keywords: } generalized binomial coefficients. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000045}, \seqnum{A000120}, \seqnum{A000215}, \seqnum{A000225}, and \seqnum{A000317}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received September 22 2005; revised version received October 8 2006. Published in {\it Journal of Integer Sequences}, December 31 2006. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}