Are certain integer functions well-defined modulo different primes necessarily polynomials?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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$.)