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?

  • 1
    $\begingroup$ Do you know a spanning set? $\endgroup$ – Steven Landsburg Jun 10 '13 at 17:33
  • 2
    $\begingroup$ 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. $\endgroup$ – Todd Trimble Jun 10 '13 at 18:23
  • $\begingroup$ @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. $\endgroup$ – Stefan Kohl Jun 10 '13 at 19:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Stefan Kohl Jun 10 '13 at 19:47
  • $\begingroup$ Similar question (and answer) on MSE: math.stackexchange.com/questions/33521/… $\endgroup$ – 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*}. $$

  • 2
    $\begingroup$ 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}}$? $\endgroup$ – David E Speyer Jun 11 '13 at 12:52
  • 3
    $\begingroup$ @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/… $\endgroup$ – François Brunault Jun 11 '13 at 14:01
  • 1
    $\begingroup$ 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. $\endgroup$ – François Brunault Jun 11 '13 at 15:41
  • 1
    $\begingroup$ And a reference for the last fact is : mathoverflow.net/questions/10239/… $\endgroup$ – François Brunault Jun 11 '13 at 17:14
  • 1
    $\begingroup$ 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). $\endgroup$ – 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.

  • $\begingroup$ Thank you very much! (Though I'd hoped an answer would need to reveal a little more of the structure of $R$ ...). $\endgroup$ – Stefan Kohl Jun 10 '13 at 21:01
  • 4
    $\begingroup$ 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. $\endgroup$ – David E Speyer Jun 10 '13 at 23:41
  • 1
    $\begingroup$ 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. $\endgroup$ – Theo Johnson-Freyd Jun 11 '13 at 2:33
  • $\begingroup$ @David: no, so far I don't know a $\mathbb{Z}$-basis for $R \cap \mathbb{Q}[x]$. $\endgroup$ – 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.

  • $\begingroup$ 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.) $\endgroup$ – Thomas Jul 13 '14 at 16:01
  • $\begingroup$ 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$. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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