\documentstyle[doublespace,11pt,fullpage]{article}

\marginparwidth 0pt
\oddsidemargin  0pt
\evensidemargin  0pt
\marginparsep 0pt
\topmargin  0pt
\textwidth   6.3in
\textheight  8.1in
\setstretch{1.5}


\begin{document}
\mbox{ }\\
\begin{center}
{\bf
When Does ${\bf m-n}$ Divide ${\bf f(m)-f(n)}$?
\\
A Look at Column-Finite Matrices
}

\vspace{5mm}

DAVID CALLAN  \\
Department of Statistics  \\
University of Wisconsin-Madison  \\
1210 W. Dayton St   \\
Madison, WI \ 53706-1693  \\
{\bf callan@stat.wisc.edu}  \\

\end{center}
\newtheorem{lemma}{Lemma}          
\newtheorem{example}{Example}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\vspace{10mm}

In this paper, we consider the {\bf Z}-module of 
integer-valued functions $f$ defined on the nonnegative integers
(respectively on all integers),
and characterize the submodule determined by the divisibility
relation of the title, and also, as a corollary, by
the divisibility relation $m+n|f(m)+f(n)$.
Our results suggest some rather 
basic questions about such modules (equivalently,
about infinite matrices of integers in which each
column has only finitely many nonzero entries).
We discuss these questions and pose a conjecture.

%\vspace{15mm}

The functions $f$ from the nonnegative integers {\bf N}
to the integers {\bf Z} satisfying
\begin{equation}
m-n \, | \, f(m)-f(n)\ \ \ \ \ \ \ \ {\it all}\ m,n \in {\rm dom}\,f
\label{one}
\end{equation}
are mentioned in Apostol's textbook \cite{apostol}.
A Monthly problem \cite{myerson} observes that integer-coefficient
polynomials $f$ certainly satisfy
(\ref{one}) and asks for a {\em nonpolynomial}
function from {\bf Z} to {\bf Z} that does so. 
Problem 4 on the 1995 U.S.A. Mathematical Olympiad asks one to show
that nonpolynomial functions from ${\bf N}$ to ${\bf Z}$
satisfying (\ref{one}) never exhibit polynomial growth \cite{news}.
For sharper results on their growth, including an open question, see
\cite{poonen}.

Our main result is that
in both cases, {\bf N}
to {\bf Z} and {\bf Z} to {\bf Z}, there is a simple
characterization of {\em all} functions satisfying (\ref{one});
in fact in each case these functions form a {\bf Z}-module for which we
can give a  ``basis''. (In the 
present context the term basis, defined below,
has the usual connotations of linearly spanning and
being linearly independent, 
but infinite 
linear combinations are allowed.) 

Let $M_{{\bf N}} $  (resp. $M_{{\bf Z}})$
denote the ${\bf Z}$-module of functions ${\bf N}$ to ${\bf Z}$
(resp. ${\bf Z}$ to ${\bf Z}).$
Let $M$ be any submodule of $M_{{\bf N}}$ or $M_{{\bf Z}}$ and
let us define a {\em basis} for $M
$ as a finite or countably infinite set $\{ f_{0},f_{1},
f_{2},\dots \}$ in $M$ for
which each $f \in M$ has a unique
expression (up to order of summands) as an integral linear
combination $f=\sum_{k \geq 0}c_{k}f_{k}.$
Naturally $(\sum_{k = 0}^{\infty}c_{k}f_{k})(n)$ means
$\sum_{k = 0}^{\infty}c_{k}f_{k}(n)$ and, to converge, the series must
have only finitely many nonzero terms for any specific value of $n$
(and hence of course order of summation does not matter).
Equivalently, we may identify $f \in M_{\bf N}$ with
the infinite sequence (row vector)$\ (f(j))_{j \geq 0},$
identify $M_{\bf N}$ with the set of all infinite sequences
of integers, and view $\{f_{i}\}$ as an infinite matrix $F$ with row $i$
the sequence for $f_{i}.$
Then $\sum_{k \geq 0}c_{k}f_{k}$ is the vector-matrix product
${\bf c}F$ and $F$ must be column-finite (that is, only finitely many
nonzero entries in each column) to ensure ${\bf c}F$ is defined 
for arbitrary ${\bf c}$.
The conditions for $\{f_{i}\}$ to be a basis translate into:
the rows of $F$ (i) span $M_{\bf N}$, and (ii) are linearly
independent 
(both conditions over ${\bf Z}$ and 
in the sense of infinite 
linear combinations).
For example, the identity matrix corresponds to the ``natural''
basis $\{e_{i}\}_{i \geq 0}$ for $M_{\bf N}$ with
$e_{i}(j)=\delta_{ij}$ (Kronecker delta). Pascal's matrix, 
given by $P
=({{j}\choose{i}})_{i,j \geq 0},$
corresponds to the basis 
$C_{\bf N}:= \{f_{i}\}_{i \geq 0}$ with
$f_{i}(j)={{j}\choose{i}}.$ The $f_{i}$ form a basis because
in fact $f=\sum_{i \geq 0}c_{i}f_{i}$ if and only if
$c_{j}=\sum_{i=0}^{j} (-1)^{j-i} {{j}\choose{i}}f(i),\ j \geq 0.$

We digress to give one reason why $C_{\bf N}$ is a good basis to
work with. Note $f_{k}(x)={{x}\choose{k}}$ is a {\em polynomial} in
$x$ of degree $k$ with
rational coefficients; thus any {\em finite} integral linear
combination of the $f_{k}$ is a polynomial in the polynomial
ring ${\bf Q}[x]$ that assumes integral values at the integers.
Conversely, suppose $f(x) \in {\bf Q}[x]$ has this property.
Let $\deg f=m.$ Now $\{1,x,\dots,x^{m}\}$ is a basis for the
${\bf Q}$-vector space $P_{m}=\{g(x) \in {\bf Q}[x]: \deg g
\leq m\}$, and since $\deg f_{k}=k,$
the set $\{f_{k}\}_{0 \leq k \leq m}$ is also a basis
for $P_{m}.$ Hence $f=\sum_{k=0}^{m} c_{k} f_{k}$
with $c_{k} \in {\bf Q}.$ In fact $c_{k} \in {\bf Z}$ by the integrality
property of $f$ and
the last sentence of the preceding paragraph.
It follows that the polynomial functions in $M_{\bf N}$
are precisely the finite integral linear combinations of
the $f_{i}.$ (It also follows that if $f \in {\bf Q}[x]$
assumes integral values at the nonnegative integers, then
$f$ assumes integral values at all integers, and hence the
polynomial functions in $M_{\bf Z}$ are the same as the
polynomial functions in $M_{\bf N}.$)


An analogous basis for $M_{{\bf Z}}$ is
$C_{{\bf Z}}:=\{g_{k}\}_{k \geq 0} \cup \{h_{k}\}_{k \geq 1}$ where
$g_{k}(n)={{n+k}\choose{2k}}$ and $h_{k}(n)=
{{n+k-1}\choose{2k-1}}.$ In
this case, $f \in M_{\bf Z}$ can be (uniquely) expressed as
$\sum_{k=0}^{\infty} c_{k} g_{k} +
\sum_{k=1}^{\infty} d_{k}h_{k}$ with
$c_{n} =\sum_{k=-n}^{n} (-1)^{n-k} 
{{2n}\choose{n-k}}f(k)$ for $n \geq 0$ and $d_{n}=
\sum_{k=-n}^{n-1} (-1)^{n-k-1} {{2n-1}\choose{n-k-1}}
f(k)$ for $n \geq 1.$
By arranging $C_{\bf Z}$ in the order $g_{0},h_{1},g_{1},
h_{2},g_{2},\dots,$ and evaluating at the integers in the order
 $0,-1,1,-2,2,\dots,$ 
verification becomes equivalent to showing
that the upper triangular matrices
$({{\lfloor i/2 \rfloor +(-1)^{j} \lceil j/2
\rceil}\choose{i}})_{i,j \geq 0}$ and
$((-1)^{\lceil i/2 \rceil + \lfloor j/2 \rfloor}
{{j}\choose{\lceil (i+j)/2 \rceil}})_{i,j \geq 0}$
are inverses of one another. 
This doesn't particularly facilitate a proof
by hand (and we leave the combinatorial
identities on which a formal proof rests to the interested reader),
 but a few minutes checking finite sections by
computer will convince you these two matrices are indeed inverse  
to one another.

Note that $h_{k}$ is an odd function, that is,
$h_{k}(-n)=-h_{k}(n),\ n \in {\bf Z},$ and for $k \geq 1, \ 
2g_{k}-h_{k}$ is an even function, as is $g_{0}.$ Also,
from the above formulas for $c_{n}$ and $d_{n},$ if $f \in  
M_{\bf Z}$ is odd, it follows $c_{k}=0$ for $k \geq 0,$ and
thus the $h_{k}$ span the {\em odd} functions
in $M_{\bf Z}.$
Similarly if $f \in M_{\bf Z}$ is even, $c_{k}=-2d_{k}$
for $k \geq 1,$ yielding    a spanning set for the even
functions.

Summarizing, we have the following theorem.
\begin{theorem}
Let $f_{k}(n)={{n}\choose{k}},\,g_{k}(n)={{n+k}\choose{2k}},\,
h_{k}(n)={{n+k-1}\choose{2k-1}}$ as above.

Then

$(i)$ $C_{{\bf N}}=\{ f_{k}\}_{k \geq 0}$ is a basis
for $M_{{\bf N}}.$

$(ii)$ $C_{{\bf Z}}=\{g_{k}\}_{k \geq 0} \cup \{h_{k}\}_{k \geq 1}$
is a basis for $M_{{\bf Z}}.$

$(iii)$ $C_{\rm odd}=\{h_{k}\}_{k \geq 1}$ is a basis for
$\{ f \in M_{\bf Z}: f$ is odd\};
\\
.\ \ \ \ \ \ \ $C_{\rm even} = \{g_{0}\} \cup 
\{2g_{k}-h_{k} \}_{k \geq 1}$ 
is a basis for
$\{f \in M_{\bf Z}: f$ is even \}.
\end{theorem}

\vspace{1mm}

Just as for $C_{\bf N},$ the finite integral linear combinations
in $C_{\bf Z}, C_{\rm odd},C_{\rm even}$ comprise the polynomial functions
in the respective modules. The latter facts---at least for $C_{\bf N},
C_{\rm odd},C_{\rm even}$---are noted in P\'{o}lya and Szeg\"{o}
\cite{polya}.



For the sake of clarity, we mostly use the function interpretation for
$M_{\bf N}$ and $M_{\bf Z}$ in the first part of the paper---Theorems
1 through 4---and then work with 
sequences and matrices in the second part.
We are now ready to state our main result. Let ${\rm lcm}[n]$
denote the least common multiple of the first $n$ positive
integers (and set ${\rm lcm}[0]=1$).
\begin{theorem}
Let $M_{{\bf N}}'$ (resp. $ M_{{\bf Z}}'$) denote the 
submodule of functions  $f$ in $M_{{\bf N}}$ (resp.
$M_{{\bf Z}}$) that satisfy $(1):\ m-n|f(m)-f(n) \, 
$ for all $ m,n \in \, {\rm dom}\,f$.

Then 

$(i)$ $M_{{\bf N}}'$
has a basis    
$C_{{\bf N}}'=\{{\rm lcm}[k]f_{k}\}_{k \geq 0}.$   

$(ii)$ $M_{{\bf Z}}'$ 
has a basis
$C_{{\bf Z}}'=\{{\rm lcm}[2k]g_{k}\}_{k \geq 0} \cup \{
{\rm lcm}[2k-1]h_{k}\}_{k \geq 1}. $  
\end{theorem}

Proof. First we develop a couple of lemmas. 
Let $[a,b]$ denote the
interval of integers $a,a+1,\dots,b.$ For prime $p$ and
positive integer $n,$ let $\nu_{p}(n)$ denote the exponent
of the largest power of $p$ that divides
$n;$ thus  
$p^{\nu_{p}(n)}|n$ but $p^{\nu_{p}(n)+1} \not| n$. 
It is trivial that $\lfloor \frac{a}{c}
\rfloor + \lfloor \frac{b}{c} \rfloor \leq \lfloor
\frac{a+b}{c} \rfloor$ for positive integers $a,b,c.$
Hence for $n \geq k \geq 1$ and $r \geq 1,\ \lfloor k/p^{r
} \rfloor \leq \lfloor n/p^{r} \rfloor - \lfloor (n-k)/p^{r}
\rfloor.$
This says that for each $r$ the number of integers in $[1,k]$
divisible by $p^{r}$ is $\leq $ the number in $[n-k+1,n]$
so divisible. This fact 
allows the construction in an obvious way of a bijection
$\phi:[1,k] \rightarrow [n-k+1,n]$ such that $\nu_{p}(i)
\leq \nu_{p}(\phi(i))$ for $1 \leq i \leq k.$ (Consider first
the integers in $[1,k]$ divisible by the highest power of
$p$ that divides $k.$ Let $\phi$ be any one-to-one map
from these integers to the integers in $[n-k+1,n]$ divisible
by this power of $p$ and then proceed 
in turn to the smaller powers of $p.$)
Let $n^{\underline k}$ denote the falling factorial
$n(n-1)(n-2)\cdots$ to $k$ factors.
 \begin{lemma}  . \\
$($i$)$ For $n \geq k \geq 1$ and $p$ prime, $p^{\nu_{p}(k!)} | 
n^{\underline {k}}.$ \\
$($ii$)$ If $i\ (1 \leq i < k)$ factors are removed from the 
 product                     
$n^{\underline{k}},$ then the resulting
product is divisible by
$p^{\nu_{p}(k!)-i\nu_{p}({\rm lcm}[k])}.$                 
\end{lemma}

Proof. (i)
Since ${{n}\choose{k}}=\frac{n^{\underline{k}}}{k!}$ is an integer,
$p^{\nu_{p}(k!)}|n^{\underline{k}}.$    

\hspace{10mm}
 (ii) This assertion follows from
part (i) and the existence of the bijection $\phi$
which says, so far as divisibility by $p$ goes, the effect of tossing
the factor $\phi(i)$ out of the product $n^{\underline{k}}$ is
no worse than the effect of tossing the factor $i$ out of $k!,$
and $\nu_{p}(i) \leq \nu_{p}({\rm lcm}[k]).$

{\vspace{3mm}}

We also need a result on divisibility of binomial coefficients.
\begin{lemma}
If $p$ is a prime which does not divide $r$, and if $i>j \geq 0,$ then
\[
p^{i-j} | {{p^{i}q}\choose{p^{j}r}}.
\]
\end{lemma}

 Proof. An often-quoted result of Kummer (see \cite{wong} for a proof)
says that the exact power of $p$ that divides a binomial
coefficient ${{n}\choose{k}}$ is the
number of ``borrows'' when $k$ is subtracted from $n$
in base $p.$ For example in base 5, $(375)_{5}=3000,
\ (330)_{5}=2310,$ and we have the subtraction
\[
%\begin{center}
\begin{array}{rlllll}
n & = & 3 & 0 & 0 & 0 \\
k & = & 2_{1} & 3_{1} & 1 & 0 \\
n-k & = &  & 1 & 4 & 0
\end{array}
%\end{center}
\]
with 2 borrows. Note that if (as here) the number of trailing zeros in $n$
exceeds that in $k,$ the number of borrows will always 
be at least 
the excess (here, 2). Since $k=p^{j}r$ has exactly $j$ trailing 
zeros, this observation translates immediately into Lemma 2.

Now to the proof of the theorem. First we must show the elements of
$C_{{\bf N}}'$ actually satisfy (\ref{one}). 
Thus let $f_{k}'(n)={\rm lcm}[k]{{n}\choose{k}}$ denote
a typical element of $C_{\bf N}'$ and we must show for
$m,n,k \geq 1,$ that
$m|f_{k}'(n+m)-f_{k}'(n),$ that is,
$m|{\rm lcm}[k]((n+m)^{\underline{k}}-n^{\underline{k}})/k!$ or,
equivalently, for each prime divisor $p$ of $m$
\begin{equation}
p^{\nu_{p}(m)+\nu_{p}(k!)-\nu_{p}({\rm lcm}[k])}|
(n+m)^{\underline{k}}-n^{\underline{k}}
\label{two}
\end{equation}
If $\nu_{p}(m) \leq \nu_{p}({\rm lcm}[k]),$ (\ref{two})
is an immediate consequence of Lemma 1(i).
So suppose $\nu_{p}(m)> \nu_{p}({\rm lcm}[k])$ and consider the cases
$k>n$ and $k \leq n$ separately. If $k>n,$ then $m$ is one of 
the factors in $(n+m)^{\underline{k}}$ and
$n^{\underline{k}}=0.$
But $p^{\nu_{p}(m)}|m$ by definition, and
$p^{\nu_{p}(k!)-\nu_{p}({\rm lcm}[k])}| \frac{(n+m)^{\underline{k}}}{m}$
by Lemma 1(ii), and (\ref{two}) is obtained by multiplying
these divisibility relations. On the other hand,
if $k \leq n$ consider the powers of $m$ in the expansion
$(n+m)^{\underline{k}}-n^{\underline{k}}=
\sum_{i=1}^{k} [\Sigma \pi(k-i)]m^{i},$ where,
in the inner sum, the summand $\pi(k-i)$ runs over all
products of $k-i$ factors from $[n-k+1,n].$
We have $p^{\nu_{p}(k!)-i\nu_{p}({\rm lcm}[k])}|
\pi(k-i)$ by Lemma 1(ii) and trivially $p^{\nu_{p}(m)i}|
m^{i}.$ This yields $p^{\nu_{p}(k!)+i
(\nu_{p}(m)-\nu_{p}({\rm lcm}[k]))}|
\pi(k-i)m^{i}$ and hence
certainly $p^{\nu_{p}(k!)+
\nu_{p}(m)-\nu_{p}({\rm lcm}[k])} |
\pi(k-i)m^{i}$ since $i \geq 1$ and,
by supposition,
$\nu_{p}(m) > \nu_{p}({\rm lcm}[k]).$ Summing over $i$
we obtain (\ref{two}). Thus $C_{{\bf N}}' \subseteq M_{{\bf N}}',$ and
the proof that $C_{{\bf Z}}' \subseteq M_{{\bf Z}}'$ is very similar.


Next we must show that every $f \in M_{{\bf N}}'$ is 
an integral linear
combination of the elements of $C_{{\bf N}}'.$
We already know there exists a unique sequence of integers
$(c_{n})_{n \geq 0}$ (namely, $c_{n}=\sum_{k=0}^{n}
(-1)^{n-k}{{n}\choose{k}}f(k)\,)$ such that $f(n)=
\sum_{k=0}^{n} c_{k} {{n}\choose{k}}.$
So we must show that ${\rm lcm}[k]|c_{k}$ under the hypothesis
that $f$ satisfies (\ref{one}). To get induction (on $n$) working,
we'll prove a little more:
\begin{center}
{\it for all} $\ a \in {\bf N},\ {\rm lcm}[n]$ {\it divides}
$c_{n}(a):=\sum_{k=0}^{n} (-1)^{n-k}
{{n}\choose{k}} f(a+k)$ {\it
when $f$ satisfies $(\ref{one})$}
\end{center}
(Of course, $c_{n}(0)=c_{n}$ and, to numerical analysts,
$c_{n}(a)$ is the $n$th forward difference of $f$ at $a.$)
The base case $n=1$ is trivial. Since $c_{n}(a)=
c_{n-1}(a+1)-c_{n-1}(a)$ we have by the induction hypothesis
that ${\rm lcm}[n-1]|c_{n}(a)$ and need only show $n|c_{n}(a).$
Let $p$ be any prime divisor of $n.$ Write $n=p^{i}r$ and
let $k=p^{j}s$ with $r,s$ relatively prime to $p.$
Now (\ref{one}) implies
$p^{j}|f(a+k)-f(a).$ Also if $i \geq j,$ then
$p^{i-j}|{{n}\choose{k}}$ by Lemma 2. In any case,
$p^{i}|{{n}\choose{k}}[f(a+k)-f(a)].$ 
Since $c_{n}(a)=\sum_{k=0}^{n} (-1)^{n-k}
{{n}\choose{k}}[f(a+k)-f(a)],$ it follows that
$p^{i}|c_{n}(a)$ and since $p$ is arbitrary,
$n|c_{n}(a)$ and the induction is complete. The corresponding
proof that $C_{{\bf Z}}'$ generates $M_{{\bf Z}}'$ is analogous: $c_{n}(a) 
$ and $d_{n}(a)$ are defined analogously 
(except now $a \in {\bf Z}$) and the induction
is based on the recurrence relations
$c_{n}(a)=d_{n}(a+1)-d_{n}(a)$ and $d_{n}(a)=
c_{n-1}(a)-c_{n-1}(a-1).$
This completes the proof of Theorem 2.

Here's one corollary. As noted earlier, the
finite linear combinations in $C_{{\bf N}}$ 
(or $C_{{\bf Z}}$) yield polynomials, and infinite linear combinations
nonpolynomials (by uniqueness---the polynomials are already
exhausted by the finite linear combinations).
The observation (made in the
editorial comment on \cite{myerson}) that there are
uncountably many nonpolynomial functions 
{\bf Z} to {\bf Z} satisfying (\ref{one})
follows immediately.

For later use we remark that the divisibility relation (2)
above in fact holds for arbitrary integer $n.$ (This shows that
$f_{k}'(n)={\rm lcm}[k]{{n}\choose{k}},$ if considered as a
function of $n \in {\bf Z}$ rather than just $n \in {\bf N},$
is in $M_{\bf Z}';$ thus each 
element of the basis $C_{\bf N}'$ for $M_{\bf N}'$ extends
to an element of $M_{\bf Z}'.$ We will soon see that not every element of
$M_{\bf N}'$ extends in this fashion.)
The proof of (2) for $n \leq 0$ is similar to that given
above for $n \geq 1: \ n=0$ is easy, so suppose $n<0.$
In case $n+m<0$ the result already established in (2) for  
$n \geq 1$ applies (with the roles of $n+m$ and $n$ reversed);
the case $n+m \geq 0$ should be split into subcases
$k>n+m$ and $k \leq n+m
$ corresponding to the subcases $k>n$ and $k \leq n$ above. The details are
left to the reader.

Now we consider an interesting submodule of
$M_{{\bf N}}'.$
Let $\theta:M_{{\bf Z}}
\rightarrow M_{{\bf N}}$ be given by restriction of domain,
that is, $\theta(f)=f_{|{\bf N}}.$ 
(Interpreting the elements of $M_{{\bf N}}$ and $M_{{\bf Z}}$ as 
sequences, $\theta$ just throws away the left half
of a doubly infinite sequence.)
Let $\psi$ denote the restriction of $\theta $ to $M_{{\bf Z}}';$
then it is clear that $\psi: M_{{\bf Z}}' \rightarrow M_{{\bf N}}'.$
Note that the range of $\psi$ includes at least all the 
finite integral linear combinations of $C_{{\bf N}}',$ 
that is, all the polynomial maps in
$M_{{\bf N}}'.$
This is because each $f_{k}' \in C_{{\bf N}}'$ 
extends, as remarked in the previous paragraph,              
to an element in
$M_{{\bf Z}}'$. 
Of course the map $\theta$
is onto but far from one-to-one.
Contrariwise,  
we have the following result for $\psi.$
\begin{theorem}
Let $\psi:M_{\bf Z}' \rightarrow M_{\bf N}'$ be the map
just defined.
Then

$($i$)$ $\psi$ is one-to-one.

$($ii$)$ $\psi$ is not onto.
\end{theorem}

Proof. (i)
It suffices to show
$\ker \psi   =(0)$ and to see this, view an element of
$\ker \psi  $ as a doubly infinite sequence of integers with a tail of zeros.
Then it cannot have any nonzero term (the standing
divisibility hypothesis (1) implies
any term is divisible by all sufficiently 
large integers). 

\ \ (ii) Recall
$f_{k}(n)={{n}\choose{k}}$ and for
brevity set $u_{k}={\rm lcm}[k],\ k\geq 0.$
Now consider the element of $M_{\bf N}'$ given by
$f=\sum_{k \geq 0}u_{k}f_{k}$
and let us ask if $f$
can be extended backwards, i.e. defined at $-1,$ to yield a
(sequence of integers) $g$ that is still in $M_{{\bf N}}'.$
It suffices to show this cannot be done. Suppose it can.
Then by Theorem 2(i), $g=\sum_{k \geq 0}c_{k}u_{k}f_{k}$ for some 
sequence of integers $(c_{k})$
and $g(n+1)=f(n),\ n \geq 0.$
This readily implies that
 $u_{k}=c_{k}u_{k}+c_{k+1}u_{k+1},\ k \geq 0.$
Multiply by $(-1)^{k}$
and add to obtain $\sum_{k=0}^{n-1} (-1)^{k}u_{k}=
c_{0}u_{0}+(-1)^{n-1}c_{n}u_{n}$ and in particular,
\begin{equation}
\sum_{k=0}^{n} (-1)^{k} u_{k} \equiv c_{0}\,({\rm mod}\,u_{n})
\ \ \ \hspace{10mm} \ n\geq 1
\end{equation}
This infinite set of congruences 
has no solution for $c_{0}$
as follows. Let $s_{n}=\sum_{k=0}^{n} (-1)^{k}u_{k}$ denote the left side
of (3). 
Since $u_{n}=u_{n-1}$ unless $n$ is a prime power, $p^{r},$ in which case
$u_{n}=pu_{n-1}$,
it is easy to show by induction that
$0<s_{n}<u_{n}$ for $n$ even $\geq 2,$ and
$-u_{n}<s_{n}<0$ for $n$ odd $\geq 3.$ Thus if $c_{0} \geq 0$
we have for all sufficiently large even $n,\ 
0 \leq c_{0} < u_{n}$ while $ 0<s_{n} < u_{n}$ and, by (3),
$s_{n} \equiv c_{0}\,({\rm mod}\,u_{n}),$ hence $s_{n}=c_{0}.$
It follows that $s_{n+2}=s_{n}$ and so 
$u_{n+2}=u_{n+1},$ a contradiction since
$u_{n+2}=2 u_{n+1} $ whenever $n+2$ is a power of 2.
A similar contradiction is obtained in case $c_{0}<0,$
completing the proof.
%\hspace{149mm}$\Box$

As a curiosity, we can now ``analyze'' the divisibility
relation $m+n | f(m)+f(n)$ with little extra effort.
Let $M_{\bf N}''=\{f \in M_{\bf N}
:m+n|f(m)+f(n),\ m,n \in {\bf N} \}$ and analogously 
for $M_{\bf Z}''.$
Also let $\rho:M_{\bf Z}'' \rightarrow
M_{\bf N}''$ denote the restriction map analogous to
$\psi:M_{\bf Z}' \rightarrow M_{\bf N}'$ above.
\begin{theorem}
Let $h_{k}(n)={{n+k-1}\choose{2k-1}}$ as
in Theorem 1, and let $h_{k|{\bf N}}$ denote the restriction of
$h_{k}$ to ${\bf N}.$ Then

$(i)$ $\{ {\rm lcm}[2k-1]h_{k|{\bf N}} \}_{k \geq 1}$ is a basis
for $M_{\bf N}''.$

$(ii)$ $ \{ {\rm lcm}[2k-1]h_{k} \}_{k \geq 1}$ is a basis for
$M_{\bf Z}''.$

$(iii)$ $\rho:M_{\bf Z}'' \rightarrow M_{\bf N}''$ is both
one-to-one and onto (unlike the map $\psi$ of Theorem 3).
\end{theorem}

Proof. 
Suppose $f \in M_{\bf Z}''.$ The divisibility hypothesis
with $m=-n$ implies $f$ is odd, and consequently
the divisibility hypothesis is equivalent to
$m-n|f(m)-f(n),\ m,n \in {\bf Z}.$ Hence
$M_{\bf Z}''=M_{\bf Z}' \cap \{f \in M_{\bf Z}:
f$ is odd\} and part (ii) follows from Theorems
1(iii) and 2(ii).
Now                 observe
that $m+n|f(m)+f(n),\ m,n \in {\bf N}$ implies
also
$m-n|f(m)-f(n),\ m,n \in {\bf N},$ or equivalently,
$k|f(\ell +k)-f(\ell),\ k,\ell \in {\bf N}.$
To see this, write $\ell=kq+r$ with $0 \leq r <k$ (division algorithm)
and apply the hypothesis with $m=kq+r$ and $n=k-r$ to obtain
$k|f(kq+r)+f(k-r).$ Replacing $q$ by $q+1$ yields
$k|f(kq+r+k)+f(k-r).$ Hence $k$ divides the difference, that is,
$k|f(\ell+k)-f(\ell),$ as desired.

This permits us to extend any $f \in M_{\bf N}''$ to
$f \in M_{\bf Z}''$ by defining 
$f(-n)=-f(n),\ n \geq 1,$ (the reader should
check this) and this
is the {\em only} way to extend $f$ since $M_{\bf Z}''$ consists of
odd functions. Thus the restriction map $\rho:M_{\bf Z}''
\rightarrow M_{\bf N}''$ is one-to-one and onto. This is part (iii)
and part (i) follows from parts (ii) and (iii).  

\vspace{2mm}

The preceding results raise the question: to what extent is 
the above notion of ``basis''
analogous to a free basis (of a finitely generated module)?
To begin with,
any finitely generated submodule of $M_{{\bf N}}$ is a free
${\bf Z}$-module and here the notions ``basis'' as above and 
``free basis'' coincide.
Every submodule $M$ of 
$M_{\bf N}$ does possess a basis. To see this, view      
elements of $M_{\bf N}$ as sequences, and for $i \geq 0$
let $c_{i}$ denote the least positive integer occurring
in position $i$ among elements of $M$ having zeros in the positions preceding
$i$ (but if all of these elements have 0 in position $i$, take $c_{i}=0$).
If $c_{i} \neq 0$ let ${\bf u}_{i}$ 
be any such sequence (with first nonzero entry 
$c_{i}$ in position $i$).
Then it is straightforward to verify that these ${\bf u}_{i}$
form a basis for $M.$

Now we switch perspective from functions
and lists of functions to sequences
and matrices, and
henceforth write ${\bf Z}^{\infty}$ instead of
$M_{\bf N}$ for the infinite sequences of integers (and
${\bf Q}^{\infty}$ for the infinite sequences of rationals).
Also ${\bf Z}_{\infty}$ (resp.
${\bf Q}_{\infty}$) will be used to denote the   
set of infinite matrices of integers (resp. rationals).
The terms ``span'' and ``linear independence''
will continue to be used in the sense of infinite
linear combinations.
For $A \in {\bf Z}_{\infty}$ let $R(A)$ denote the set
of rows of $A.$ One basic question is: When does 
$R(A)$ form a basis for ${\bf Z}^{\infty}$?
First, as noted above, $A$ must be                 
column-finite.
Second, for $R(A)$ to span ${\bf Z}^
{\infty},$ it is certainly necessary
for $R(A)$ to span the 
``basic'' vectors $\{e_{k}\},$ equivalently, $A$ must possess
a left inverse in ${\bf Z}_{\infty}$, call it $B$.
Third, $A$ must have a trivial left nullspace 
in ${\bf Z}^{\infty}$
(so $A$'s rows are linearly
independent) and this makes $A$'s left inverse
$B$ unique.
These three conditions, though, do not ensure $R(A)$ spans all of
$M_{\bf N}$.                       
\begin{example}
Let $J$ denote the infinite ``Jordan'' matrix---all 0's 
except 1's just below the main diagonal---and set $
A=I+2J.$ Then $A$ is column-finite
and has a unique left inverse in
${\bf Z}_{\infty},$ but $A$'s  rows do not have ${\bf Z}$-span
${\bf Z}^{\infty}$.
\end{example}

Proof. The column-finiteness of $A$ is obvious.
It is easy to check that $J^{k}$ has 1's on the
$k$th diagonal below and parallel to the main diagonal and
0's elsewhere, and that a left inverse of $A$ in ${\bf Z}_{
\infty}$ is given correctly by the
formal expansion $(I+2J)^{-1}=I-2J+4J^{2}-8J^{3}+ \dots .$
The left nullspace of $A$ in ${\bf Q}^{\infty}$ is spanned by
$(1,-\frac{1}{2},\frac{1}{4},-\frac{1}{8},\dots)$
and so clearly has trivial intersection with
${\bf Z}^{\infty}$, making $A$'s left inverse in ${\bf Z}_{\infty}$
unique. On the other hand, let {\bf e} denote the (row) vector
of all 1's. Then ${\bf e}A =3{\bf e},$
so the general solution of ${\bf x}A={\bf e}$ in ${\bf Q}^{\infty}$
is ${\bf x}= \frac{1}{3}{\bf e}+k(1,-\frac{1}{2},\frac{1}{4},
-\frac{1}{8},\dots)$ (arbitrary $k \in {\bf Q}$) and
clearly ${\bf x} \not\in {\bf Z}^{\infty}$ for any $k$. Thus
${\bf e}$ is not in the ${\bf Z}$-row-span of $A$.

Column-finiteness of $A$'s left inverse (or rather the
lack of it) plays
a role in the preceding example.
Note that a product of column-finite matrices 
is again column-finite,
and associativity holds:
in fact for 
${\bf w} \in {\bf Q}^{\infty}$ 
and $X,Y \in {\bf Q}_{\infty},$ 
if $wX$ is defined and $Y$ is column-finite, then it is easy
to check all four products are defined and
$({\bf w }X)Y={\bf w}(XY).$ 
Three corollaries: (1) If $X,Y$ are column-finite matrices in ${
\bf Q}_{\infty},$ then
$(WX)Y=W(XY)$ for
arbitrary $W \in {\bf Q}_{\infty}.$ 
(2) The column-finite matrices in
${\bf Q}_{\infty}$ form a ring (with identity).
Let us denote this ring by CF$({\bf Q}_{\infty})$ (CF
for column-finite) and analogously for CF(${\bf Z}_{\infty}).$
(3) If $A \in {\rm CF}({\bf Z}_{\infty}
)$ has a unique left inverse $B$ 
in ${\bf Z}_{\infty}$ {\em that happens to be
column-finite}, then we have for arbitrary
${\bf w} \in {\bf Z}^{\infty},\ {\bf w} = {\bf w}(BA) =
({\bf w}B)A$ and thus $R(A)$ 
does indeed have ${\bf Z}$-span ${\bf Z}^{\infty}.$   
Of course 
 this 
argument breaks down if $B$ is 
not column-finite since
then ${\bf w}B$ might not be defined (and Example 1 shows
the conclusion need not hold).
For $A \in {\rm CF}({\bf Z}_{\infty}),$  
the assertion that $A$ has a unique left inverse in ${\bf Z}_
{\infty}$ that happens to lie in ${\rm CF}({\bf Z}_{\infty})$
is, on the face of it, stronger than saying that $A$ has
a unique left inverse in ${\rm CF}({\bf Z}_{\infty}).$
In fact the two statements are equivalent since if $A$ has a left
inverse $B$ in ${\rm CF}({\bf Z}_{\infty})$ and another
left inverse $C$ in ${\bf Z}_{\infty} \backslash
{\rm CF}({\bf Z}_{\infty}),$ then $B-C$ has a nonzero
row and adding this row to any row of $B$ produces
another left inverse for $A$ in ${\rm CF}({\bf Z}_
{\infty}).$
Furthermore, from elementary ring theory, for $a$ in any
ring with identity $R$, ``$a$ has a unique left inverse in $R$''
is equivalent to ``$a$ is invertible (i.e. a unit) in $R$''. 


These observations suggest the following conjecture.

{\vspace{3mm}}

\noindent {\bf Conjecture} \ \ Let $A$ be a
column-finite infinite matrix   
of integers, that is, $A \in {\rm CF}({\bf Z}_
{\infty}).$

Then the rows of $A$ form a basis for ${\bf Z}^{\infty}$
if and only if
$A$ is a unit                    
in ${\rm CF}({\bf Z}_{\infty}).$

{\vspace{3mm}}

(We have proved the ``if'' part and for the ``only if'' part
we've shown that $A$ has a unique left inverse $B$ in
${\bf Z}_{\infty}.$ The conjecture then is that $B$
must lie in ${\rm CF}({\bf Z}_{\infty}).)$

Motivated by the preceding
observations, let us now consider the subtleties of
the concept of inverse for an infinite matrix.           
In general, we must distinguish between
left and right inverses---indeed over the integers, all nine
combinations of 0,1 or infinitely many left inverses
and 0,1 or
infinitely many right inverses are possible. The following table provides
simple examples ($J$ denotes the Jordan matrix with 1's below the diagonal,
$K$ is given below, 
 $^{t}$ denotes transpose).

\begin{example}

$\begin{array}{ccccc}
 & & \# & {\rm right} & {\rm inverses}  \\
  & & 0 & 1 & \infty  \\
\# & 0 & O & K^{t} & J^{t}   \\
{\rm left} & 1 & K & I & I+J^{t}  \\
{\rm inverses \ \ } & \infty & J & I+J & J+J^{t} 
\end{array}
$
\end{example}

Here the unique left inverse of $K$ and $K$ itself are given respectively by
\[
\left(
\begin{array}{cccccc}
0&1&0&0&0&\dots  \\
0&-1&1&0&0&  \\
0&-1&0&1&0& \\
0&-1&0&0&1&  \\
0&-1&0&0&0&  \\
\vdots & & & & & \ddots
\end{array}
\right) , \left( \begin{array}{cccccc}
1&1&1&1&1&\dots  \\
1&0&0&0&0&  \\
1&1&0&0&0& 
\\
1&0&1&0&0&  \\
1&0&0&1&0&  \\
\vdots & & & & & \ddots
\end{array}
\right)
\]
For $J+J^{t},$ a right inverse is $J-J^{3}+J^{5}-\dots$
(note $J^{t}J=I$), and
a right nullvector is $(1,0,-1,0,1,0,-1,\dots)^{t}.$ These and
the other easy verifications are left to the reader.

We now collect a few simple facts about inverses
of column-finite matrices.

\begin{proposition}
If $A \in {\rm CF}({\bf Z}_{\infty})$
has a {\em unique} left inverse 
$B$
in ${\bf Z}_{\infty}$ and if
$AB$ is defined, then $AB=I.$ 
\label{unique}
\end{proposition}

Proof.  By associativity, $(AB-I)A=A(BA)-A=O.$ Hence $AB-I=O$ by
uniqueness of $A$'s left inverse. 

\vspace{3mm}


A diagonal matrix $D \in {\bf Q}_{\infty}$
with nonzero diagonal entries
obviously has an unambiguous inverse
$D^{-1} \in {\bf Q}_{\infty},$ 
but already with triangular matrices we must be careful.


%\vspace{3mm}

\begin{proposition}
Suppose $U \in {\rm CF}({\bf Q}_{\infty})$ is block 
upper triangular with finite square 
blocks $\{U_{ii}\}$ on
the main diagonal.

If the $U_{ii}$ are invertible, then $U$ has a unique left inverse $V$ in
${\bf Q}_{\infty}
$ and $V$ is block
upper triangular.
Moreover, $V$ is a right inverse for $U$ and it is the only
{\em column-finite} right inverse for $U $
in ${\bf Q}_{\infty},$ 
though $U$ may have other right inverses in ${\bf Q}_{\infty}$                           
and even in ${\bf Z}_{\infty}.$

Also, if $U$ has integer entries and the $U_{ii}$ are
invertible over ${\bf Z}$, then $V$ is actually in ${\bf Z}_{\infty}.$
\end{proposition}

Proof. We can solve $VU=I$ uniquely for the blocks  of $V$ in turn:
first row, left to right, then second row, left to right, etc,
and $V$ has the stated form. In particular, $V$ is
column-finite; so $UV$ is defined and by Prop. 1,
$UV=I.$ 

Similarly, if $W$ is assumed column-finite, we can solve
$UW=I$  uniquely for the 
(block) columns of $W$ left to right, bottom 
to top. Hence $W$ must equal $V.$
(Alternatively, invoke the result for rings: if $vu=1$
and $uw=1,$ then $w=v.$)
However for the upper triangular matrix $U=I+J^{t}$ 
with $J$ the ``Jordan'' matrix above,
$U(1,-1,1,-1,1,\dots)^{t}={\bf 0}$ showing that $U$ has
multiple right inverses.


With $U,V$ as in Prop. 2,  
uniqueness of $U$'s right inverse may be guaranteed by
$U$'s zero pattern.

%\vspace{3mm}

\begin{proposition}

With $U,V$ as in Prop. 2, suppose $U$ satisfies the following
condition:
\begin{equation}
U{\bf x} {\it \ is \ defined \ 
(i.e. \ involves \ no \ 
infinite \ sums) \   only \ when \ }{\bf x}{\it \ is 
\ \mbox{column-finite}}
\label{def}
\end{equation}
(e.g. $($\ref{def}$)$ certainly holds if $U$'s above-diagonal entries     
are all nonzero.)

Then $V$ is the {\em unique} right inverse for $U $
in ${\bf Q}_{\infty}.$


\end{proposition}

Proof. Suppose $U{\bf x}={\bf 0}.$
By (\ref{def}) there exists $n$ such that $x_{i}=0$ for $i>n.$
Take a large enough square
upper left  submatrix $U_{m}$ consisting of
whole blocks of $U$ 
so its size is $m$ by $m$ with $m \geq n.$
Then $U_{m}(x_{1},x_{2},\dots,x_{m})^
{t}={\bf 0}$ and since $U_{m}$
is a finite invertible matrix, ${\bf x}={\bf 0}$ and $U$ has
trivial right nullspace, making any right inverse for $U$ unique.

\begin{proposition}
With $U,V$ again as in Prop. 2, condition $($\ref{def}$)$ of Prop. 3
is satisfied if and only if there exists $k \geq 1$ such
that the submatrix of $U$ consisting of its first $k$ rows
has only finitely many zero columns.
\end{proposition}

Proof. Exercise.


\vspace{3mm}

\noindent {\bf Corollary}  \  Pascal's matrix of binomial coefficients,
$P=({{j}\choose{i}})_{i,j \geq 0},$ has a unique left inverse and
a unique right inverse, and both are given by
$P^{-1}=
((-1)^{j-i}{{j}\choose{i}}).$ 

\vspace{3mm}

Proof. 
One verifies that $Q=((-1)^{j-i}{{j}\choose{i}})$
is a left inverse for $P,$ unique by Prop. 2, hence $PQ=I$ by
Prop. 1, and $Q$ is $P$'s unique right inverse by Prop. 3.

\vspace{3mm}

Referring back to Example 1, note the matrix $A$ given there has
multiple left inverses in ${\bf Q}_{\infty}.$
This raises the question: does the phenomenon of Example 1
occur in ${\bf Q}_{\infty}$? Perhaps things are nicer over fields
and for a matrix $A \in {\rm CF}({\bf Q}_{\infty})$ with
a unique left inverse $B$ in ${\bf Q}_{\infty
},$ perhaps $B$ must lie in ${\rm CF}({\bf Q}_{\infty}).$


Here are several other questions.         
Is there an effective method to determine which elements of
$M_{\bf N}'$ are in the range of $\psi$? 
When can a subset of $M_{\bf N}$ ($= 
{\bf Z}^{\infty}$) be enlarged
to a basis? 
Could the matrix $K$ of Example 2 be replaced by a 
column-finite matrix, that is, in view of
Prop. 1, 
could a matrix $A
\in {\rm CF}({\bf Z}_{\infty})$ have a unique
left inverse $B$ in ${\bf Z}_{\infty}$ for which $AB$ is not defined?
In the rings 
${\rm CF}({\bf Z}_{\infty})$ and  
${\rm CF}({\bf Q}_{\infty}),$ is there a nice characterization
( or generating set) for the units? 
An answer to the latter question for matrices 
$A$
that are both row- and column-finite and with
entries in a {\em field} was
recently
given in \cite{china}: $A$ is invertible if and only if
both its rows and its columns are (infinitely)
linearly independent.


\vspace{6mm}

{\bf Acknowledgement} The author thanks referees
for helpful remarks and for suggesting
Example 1.




\vspace{15mm}

\begin{thebibliography}{99}

\bibitem{apostol} Tom Apostol, {\em Introduction to Analytic
Number Theory}, Springer-Verlag, 1976, p. 127.

\bibitem{myerson} Gerry Myerson, Solution for Problem 10185,
{\em Amer. Math. Monthly}, 101(1994), p. 85.

\bibitem{news} News and Letters, {\em Math. Magazine}, 69(1996), 233-238.

\bibitem{poonen} Bjorn Poonen, Jim Propp, and Richard Stong,
Problem 10553, {\em Amer. Math. Monthly}, 103(1996), p. 809.

\bibitem{polya} P\'{o}lya and Szeg\"{o}, {\em Problems and Theorems in
Analysis} II, Springer-Verlag, 1990, Chapter 8, Part 2, \S 1.

\bibitem{wong} Warren J. Wong, Powers of a Prime Dividing a Binomial 
Coefficient, {\em Amer. Math. Monthly}, 96(1989), 513-517.


\bibitem{china} Shi Qiang Wang, The Inverses of Infinite Matrices 
over a Field, {\em Beijing Shifan Daxue Xuebao} 29(1993), no. 3, 327-330.
MR {\bf 94k}:15003.

\end{thebibliography}

\vspace{5mm}

AMS Classification numbers: 15A36, 15A09, 15A03.






\end{document}