Freeness of a Z[x]-module

Definition: Call a mapping $f: \mathbb{Z} \rightarrow \mathbb{Z}$ a generalized polynomial if for any distinct integers $m$ and $n$ we have $(m - n)|(f(m)-f(n))$.

It is easy to check that polynomial functions $f \in \mathbb{Z}[x]$ are generalized polynomials, that not all generalized polynomials are polynomials and that the generalized polynomials form a ring under pointwise addition and multiplication. Call the latter ring $R$.

Question: Is $R$, viewed as a $\mathbb{Z}[x]$-module, free? And if yes, how does a basis look like?

-
Do you know a spanning set? – Steven Landsburg Jun 10 '13 at 17:33
Not a precise comment, but my gut says it's not free, and not even free as a $\mathbb{Z}$-module. The same gut suggests trying to find a $\mathbb{Z}$-submodule which is obviously not free, such as a countable product of copies of $\mathbb{Z}$ or something along similar lines. – Todd Trimble Jun 10 '13 at 18:23
@Steven: No. -- However I guess a spanning set would (roughly) have to contain a set of representatives of "growth classes", i.e. equivalence classes consisting of generalized polynomials which have, up to multiplication by polynomials, the same rate of growth. – Stefan Kohl Jun 10 '13 at 19:42
Let me add a remark: the values of a generalized polynomial $f$ on an interval $\{a,a+1, \dots, b\}$ determine $f(b+1)$ modulo ${\rm lcm}(1, \dots, b-a+1)$ -- apart from this, the value can be anything. – Stefan Kohl Jun 10 '13 at 19:47
Similar question (and answer) on MSE: math.stackexchange.com/questions/33521/… – Bill Dubuque Jul 13 '14 at 14:35

Following Todd Trimble's comment and Stefan Kohl's remark, we can show that $R$ is isomorphic to $\mathbf{Z}^{\mathbf{Z}}$ as a $\mathbf{Z}$-module. Since the product of countably many copies of $\mathbf{Z}$ is not free as a $\mathbf{Z}$-module — see this MO question — we deduce that $R$ is not free over $\mathbf{Z}$, which implies in particular that $R$ is not free over $\mathbf{Z}[x]$.

Let us endow $\mathbf{Z}$ with the following well-ordering : $0, 1, -1, 2, -2, 3, -3\dots$ The map $\phi : \mathbf{Z}^{\mathbf{Z}} \to R$ will have the form $(a_n)_{n \in \mathbf{Z}} \mapsto f$ where $f(n)$ is defined as a finite linear combination of the $a_m$ where $m$ runs trough the indices which are at most $n$ with respect to this well-ordering.

In order to give the idea of the construction, assume we work with functions defined on $\mathbf{N}$ instead of $\mathbf{Z}$, and give $\mathbf{N}$ the usual ordering. Define a map $(a_n)_{n \in \mathbf{N}} \mapsto f$ by putting $f(0)=a_0$, $f(1)=a_1$, $f(2)=a_0+2a_2$, $f(3)=3a_1-2a_0+6a_3$… The coefficients are chosen using the Bézout identity in such a way that the needed congruences hold, e.g. $f(3) \equiv f(0) \pmod{3}$.

In more detail, assume $f(n-k),\ldots,f(n-1)$ have been already defined, and let us define $f(n)$. (We proceed in an analogous way when defining $f(n)$ assuming $f(n+1),\ldots,f(n+k)$ are already defined.) Put $M=\operatorname{lcm}(1,\ldots,k) = p_1^{\alpha_1} \cdots p_r^{\alpha_r}$. We must have $p_i^{\alpha_i} \leq k$ for each $i$. There exist integers $\lambda_1,\ldots,\lambda_r \in \mathbf{Z}$ such that $\lambda_i \equiv 1 \pmod{p_i^{\alpha_i}}$ and $\lambda_i \equiv 0 \pmod{p_j^{\alpha_j}}$ for $j \neq i$. Then we put $f(n) = \sum_{i=1}^r \lambda_i f(n-p_i^{\alpha_i})+M \cdot a_n$. We check that $f(n) \equiv f(n-j) \pmod{j}$ for each $j$, and $f(n)$ is clearly linear with respect to the sequence $(a_n)$.

This defines our linear map $\phi : \mathbf{Z}^{\mathbf{Z}} \to R$. Now, it is not hard to see that $\phi$ is bijective by working backwards, starting from $f \in R$ and defining $a_n$ inductively, starting from $a_0=f(0)$, $a_1=f(1)$ and so on. We have to check the following : if $f \in R$ then using the notations above, we have $f(n) \equiv \sum_{i=1}^r \lambda_i f(n-p_i^{\alpha_i}) \pmod{M}$. Indeed, this holds modulo each $p_i^{\alpha_i}$ using the property of the $\lambda_i$'s and the assumption on $f$.

To sum up, the general picture is that (after fixing the well-ordering of $\mathbf{Z}$ explained above), the $\mathbf{Z}$-module $R$ is the homomorphic image of $\mathbf{Z}^{\mathbf{N}}$ under some infinite lower-triangular matrix

$$\begin{equation*} \begin{pmatrix} 1 & 0 & 0 & 0 & \cdots \\ 0 & 1 & 0 & 0 & \\ 0 & 1 & 2 & 0 & \\ 3 & -2 & 2 & 6 & \\ \vdots & & & & \ddots \end{pmatrix} \end{equation*}.$$

-
For the benefit of the rest of us, why can't a free $\mathbb{Z}$-module (of some uncounteable rank) contain a copy of $\mathbb{Z}^{\mathbb{Z}}$? – David Speyer Jun 11 '13 at 12:52
@David : This is something I learnt thanks to MO :) If $R$ is a PID, then every submodule of a free $R$-module is also free. For a reference see e.g. the comments to this answer mathoverflow.net/questions/16953/… – François Brunault Jun 11 '13 at 14:01
Also needed is the fact that $\mathbf{Z}^{\mathbf{Z}}$ is not free, the reason I know for this goes as follows : if $\mathbf{Z}^{\mathbf{Z}} \cong \bigoplus_{x \in X} \mathbf{Z}$ then $X$ is uncountable and $\operatorname{Hom}(\mathbf{Z}^{\mathbf{Z}},\mathbf{Z}) \cong \mathbf{Z}^X$, but it is known that the left hand side is isomorphic to the free abelian group with basis $\mathbf{Z}$, thus is countable. – François Brunault Jun 11 '13 at 15:41
And a reference for the last fact is : mathoverflow.net/questions/10239/… – François Brunault Jun 11 '13 at 17:14
Sorry for not making the argument very precise. To define $f$ on the whole of $\mathbf{Z}$, we define $f$ succesively at $0$, $1$, $-1$, $2$, $-2$, $3$, $-3$ and so on. Each time $f(n)$ is defined as $M \cdot a_n$ plus some linear combination of $a_m$ where $m$ ranges over the previously used integers. The point is that in this way we ensure that all possible pairs $\{m,n\}$ are visited, so all necessary congruences hold. I agree that with an arbitrary well-ordering of $\mathbf{Z}$ there might be some problems (I have not checked this). – François Brunault Jun 12 '13 at 10:20

It is not free. Set $f(x) = x(x-1)(x-2)(x-3)/2$.

Claim: $f(x)$ is in $R$.

Proof: We have $$\frac{f(x+N)-f(x)}{N} = \frac{N^3+11 N}{2} + (\mbox{an element of } \mathbb{Z}[x,N]).$$ The fraction $(N^3+11N)/2$ is an integer by checking the two possible parities for $N$, and an element of $\mathbb{Z}[x,N]$ is clearly an integer. $\square$

Let $g(x) = 1$. So $x(x-1)(x-2)(x-3) g = 2 f$. In a free $\mathbb{Z}[x]$ module, this would imply that $2$ divided $g$; since $2$ does not divide $g$, this shows that $R$ is not free. Let me explain this step in more detail. Suppose, for the sake of contradiction, that $h_i$ is a basis for $R$, for $i$ running over some index set $I$. Let $f = \sum_{i \in I} a_i h_i$ and let $g = \sum_{i \in I} b_i h_i$, for $a_i$ and $b_i \in \mathbb{Z}[x]$. Then $2 a_i = x(x-1)(x-2)(x-3) b_i$ for every $i$. In the ring $\mathbb{Z}[x]$, if $2a = x(x-1)(x-2)(x-3) b$ then $2$ divides $b$. Set $b_i = 2 c_i$ for $c_i \in \mathbb{Z}[x]$. Then $\sum c_i h_i$ is an element of $R$ which obeys $2 \sum c_i h_i = g$.

By the way, this also shows that this is not the direct product of some infinite list of free modules, which I would have considered a more natural guess.

-
Thank you very much! (Though I'd hoped an answer would need to reveal a little more of the structure of $R$ ...). – Stefan Kohl Jun 10 '13 at 21:01
Out of curiosity, do you know a $\mathbb{Z}$-basis for $R \cap \mathbb{Q}[x]$? That seems like a natural first question to me. – David Speyer Jun 10 '13 at 23:41
Incidentally, it is true that $f$ is divisible by $2$ among integer-valued functions. But of course $f(4)/2 = 6$ is not divisible by $4$ among integers. – Theo Johnson-Freyd Jun 11 '13 at 2:33
@David: no, so far I don't know a $\mathbb{Z}$-basis for $R \cap \mathbb{Q}[x]$. – Stefan Kohl Jun 11 '13 at 9:59

A basis for $R\cap\mathbb Q[X]$ was described by Carlitz (see the book of Cahen and Chabert "Integer valued polynomials"). The polynomials $\mathrm{LCM}(1,\cdots,n)\binom{X}{n}$ form a basis. It should be noted that the the ring $R'=\{f:\mathbb N\to\mathbb Z\text{ such that }m-n\mid f(m)-f(n)\text{ for all }m,n\in\mathbb N\}$ is a free $\mathbb Z$-module spanned by the previous polynomials. This result was proved by Rausch.

-
Really? $R'$ contains uncountably many elements, I think. Maybe I'm mistaken, but it seems obvious that if you have any sequence of integers, the function: $$f(x)=\sum_{n\in\mathbb N} a_n(x)_n$$ is defined for all natural numbers, satisfies the property since $f$ is locally integer polynomial, and each different sequence gives a different memeber of $R'$. Maybe you mean $R'\cap \mathbb Q[x]$? ($(x)_n$ being the falling factorial.) – Thomas Jul 13 '14 at 16:01
Another way to see this is to show that the map $R\to R'$ with $f\mapsto f_{\mid \mathbb N}$ is $1-1$, since any $f\in R$ that is zero at infinitely many values is zero everywhere. So, cardinality-wise, $R'$ must be at least as big as $R$. – Thomas Jul 13 '14 at 16:41

I posted a bunch of comments here, but I thought it would be better to write an answer, instead.

First, I've written up a lot about these functions, and functions with the same condition on sets $S\subseteq \mathbb Z$.

If you define $$q_k(x) = \frac{\operatorname{lcm}(1,2,\dots,k)}{k!}\left(x+ \left\lfloor {\frac{k-1}{2}} \right\rfloor\right)_k$$ then these are rational polynomials in $R$ and they have the property that, for all $n\in\mathbb Z$, $q_k(n)\neq 0$ for only finitely many $k$. So given any infinite sequence $(a_k)_{k\in\mathbb N}$ of integers, we get a unique $f\in R$ defined by:

$$f(n)=\sum_{k} a_kq_k(n)$$

A little harder to prove, but not really hard, is that every $f\in R$ is expressed in this form. Essentially, you find $a_k$ by induction.

This gives an explicit abelian group isomorphism between $R$ and $\mathbb Z^{\mathbb N}\cong\mathbb Z^{\mathbb Z}$.

The proof is essentially using Chinese remainder there inductively to determine $a_k$, to match the values of $f(0),f(1),f(-1),f(2),f(-2),\dots.$ This is why you get the term $\operatorname{lcm}(1,2,\dots,k)$.

This also helps show that $R\cap \mathbb Q[x]$ has the $q_k$ as $\mathbb Z$-generators. Given a polynomial $q(x)\in Q[x]\cap R$ is of degree $d$, if $q(n)=\sum_{k\in N} a_k q_k(n)$ then $p(n)=\sum_{k=0}^{d} a_kq_k(n)$ is another polynomial of degree $d$ which agrees at $d+1$ values, so must agree everywhere.

Side note: $R$ is actually an integral domain, not just a ring. If $f\in R$, then $f$ can be zero only for finitely many values, so $fg=0$ implies $f=0$ or $g=0$.

Using $R'=\left\{f:\mathbb N\to \mathbb Z\mid \forall n,m: n-m\mid f(n)-f(m)\right\}$, there is a natural ring homomorphism $R\to R'$ be sending $f\in R$ to $f_{\mid\mathbb N}\in R'$. This is $1-1$ since if $f_{\mid\mathbb N} =0$, then $f$ has infinitely many zeros. The map is not onto - it is possible to define $f\in R'$ such that you can't even extend $f$ to $-1$ and keep the divisibliity property.

-