**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?
> 
> 
> 



Freeness of a Z[x]-module
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](https://mathoverflow.net/questions/10239/is-it-true-that-as-z-modules-the-polynomial-ring-and-the-power-series-ring-over) — 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\*}.
$$


