Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
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
add comment

3 Answers

up vote 12 down vote accepted

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*}. $$

share|improve this answer
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
show 9 more comments

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.

share|improve this answer
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
add comment

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.