Are certain integer functions well-defined modulo different primes necessarily polynomials? Call a function $f : \mathbb Z \to \mathbb Z$ consistent if for every prime $p$ and integer $a, b$, when $a \equiv b \pmod p$ then $f(a) \equiv f(b) \pmod p$. The set $C$ of consistent functions is closed under addition, subtraction, composition, translation, and finite difference, and contains all univariate polynomials. Does $C$ contain only univariate polynomials, i.e. $C = \mathbb Z[x]$?
My intuition is that this must be the case. Since $f$ is well-defined $\mod p$ for every prime $p$, then I feel that $f$ must be defined based only on ring operations generically, so that the same definition of $f$ (with ring operations) works for any ring $\mathbb Z / p\mathbb Z$. Since the ring operations include only


*

*using 0, 1, and the variable $x$,

*addition,

*multiplication,


that would mean that $f$ must be a polynomial in $x$ with integer coefficients. Is this indeed the case?
 A: Consider the function
$$ f(z) = z \sum_{m=1}^\infty \prod_{n=1}^m (z^2 - n^2) $$
This is well-defined on the integers, since all but finitely many terms are $0$ at any integer $z$.  Moreover, for any positive integer $p$ (prime or not),  $x \equiv y \mod p$ implies $f(x) \equiv f(y) \mod p$, because that is true for each of the summands $z \prod_{n=1}^m (z^2 - n^2)$.  But $f(z) \ge z!$ for  $z\ge 2$, so this is not a polynomial.
A: There are uncountably many consistent functions, and so they certainly are not all polynomials with integer coefficients.  Consider the process where you define a consistent function $f$ by defining the values $f(0),f(1),f(-1),f(2),f(-2),\dots$ one by one.  At each step, when you are defining $f(n)$, you have a constraint on the value of $f(n)$ mod $p$ for each $p$ such that you have already defined $f(m)$ for some $m$ which is congruent to $n$ mod $p$ (note that there might be multiple such $m$ for any given $p$, but they all give the same constraint because we have constructed $f$ to be consistent up to this point).  But this is a finite set of primes, and so by the Chinese Remainder Theorem these constraints mod $p$ are just equivalent to constraining the value of $f(n)$ mod the product of all these primes.  In particular, there are infinitely many choices for what you can make $f(n)$ be.
So you can construct consistent functions in infinitely steps where at each step you have infinitely many choices, and this gives uncountably many choices.
A: I think I have determined an explicit form for consistent functions $\mathbb N \to \mathbb Z$. (I have proof written down, but it would take a while to write it here.) First, for every integer $N > 0$ and $1 \leq i \leq N$ let $m_{N, i}$ be any integer such that
$$m_{N, i} \equiv 1 \pmod{p_i}$$
and
$$m_{N,i} \equiv 0 \pmod{p_j}$$
for all $1 \leq j \neq i \leq N$. (Here $p_i$ is the $i$-th prime, starting with $p_1 = 2$.) Now define $P : \mathbb N \to \mathbb N$ as
$$P(n) = \prod_{\substack{p \leq n \\ p \text{ prime}}} p,$$
and recursively define the integers $a_{n,k}$ for $n \geq 0$ and $0 \leq k \leq n$ as follows: for every $n \geq 0$, we let
$$a_{n, n} = P(n)$$
and for every $0 \leq k < n$ we let
$$a_{n, k} = \sum_{i=1}^{\pi(n - k)} m_{\pi(n),i}a_{n-p_i,k}.$$
Finally, define the "basis" functions $B_i : \mathbb N \to \mathbb Z$ for every $i \geq 0$ as
$$B_i(n) = \begin{cases}0 &\text{ if } n < i \\ a_{n,i} &\text{ if }n \geq i\end{cases}.$$
It turns out that every consistent function $f : \mathbb N \to \mathbb Z$ may be written in the form
$$f(n) = \sum_{k=0}^n a_{n,k}c_k$$
for some unique sequence of integers $c_0, c_1, \ldots$, and thus also has a unique representation as
$$f(n) = \sum_{i=0}^\infty c_i B_i(n).$$
(This sum is defined since for any $n$, there are only finitely many $i$ where $B_i(n) \neq 0$.)
