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$,
• multiplication,

that would mean that $f$ must be a polynomial in $x$ with integer coefficients. Is this indeed the case?

• – Bill Dubuque Dec 7 '16 at 2:14
• @BillDubuque thank you, that seems quite relevant. – feralin Dec 7 '16 at 18:21

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.

• What is the significance of the $n$-th prime at the beginning? You don't seem to use it anywhere. Also, I see now why my intuition was incorrect -- when constructing consistent functions, one may use not only finite (syntactical) addition and multiplication, but may also use the integer input to describe how many times to add and/or multiply, thus bringing the set of consistent functions beyond the polynomials. – feralin Dec 6 '16 at 8:02
• Sorry, that was a remnant of an earlier iteration of the definition. – Robert Israel Dec 6 '16 at 8:03

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.

• I was originally trying to work with an argument similar to this, but I didn't realize the (now obvious) idea that we can pick any value for $f(n)$ as long as we meet the requirements of the CNT. Thanks for the thought! – feralin Dec 6 '16 at 8:20
• Why does infinitely many steps, each one with infinitely many choices, result in uncountable many choices? This seem non-trivial to me. – Pedro A Dec 6 '16 at 11:30
• @Hamsteriffic Because N^N=R. Even if we had two choices at each step, 2^N still would be R. – Serge Seredenko Dec 6 '16 at 12:44
• @feralin right... my intuition was, "oh wow, we are starting with an arbitrary function with no structure whatsoever. then adding on a very specific requirement. that should do nothing." this argument is exactly that – djechlin Dec 7 '16 at 1:02

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