Given a set $S\subseteq \mathbb{Z}$, and $f:S \rightarrow \mathbb{Z}$, we will say that $f$ is a "congruent function on $S$" if it has the property: $$\forall x,y\in S: x-y\mid f(x)-f(y)$$
Equivalently: $$\forall x,y\in S: f(x) \equiv f(y) \pmod {x-y}$$
Equivalently: $$\forall n\in\mathbb{N}, x,y\in S: x\equiv y \pmod n \text{ implies } f(x)\equiv f(y) \pmod n$$
We will define $\operatorname{Cong}(S)$ to be the set of congruent functions on $S$.
A long time ago, I wondered if this property was peculiar to integer polynomials, or if there were other examples of congruent functions in the case when $S=\mathbb{Z}$.
Theorem: $\operatorname{Cong}(S)$ is a commutative ring.
Proof: Easy.
Lemma: If $S$ is infinite, $f\in \operatorname{Cong}(S)$, and if $f$ is zero at infinitely many values of $S$, then $f$ is zero everywhere on $S$.
Proof: Easy.
Theorem: If $S$ is infinite, then $\operatorname{Cong}(S)$ is an integral domain and the natural map of $\mathbb{Z}[x] \rightarrow \operatorname{Cong}(S)$ is an injection of rings.
Proof: If $f(x)g(x)=0$ for all $x\in S$, then one of $f$ or $g$ must have infinitely many zeros, so if $f$ and $g$ are congruent, then one of $f$ or $g$ must be identically zero. Also, if $p\in \mathbb{Z}[x]$ such that $p(s)=0$ for all $s\in S$, then $p$ must be the zero polynomial.
For the most part, we will be interested only in infinite $S$, and will assume $S$ is infinite from now on.
Enumerate $S=\{s_0,s_1,s_2,...\}$. Define the polynomials $q_{S,k}(x)$ as: $$q_{S,0}(x)= 1$$ $$q_{S,n+1}(x) = (x-s_n)q_{S,n}(x)$$
This is a slight misnomer, because the $q$ are defined in terms of the enumeration of $S$, rather than $S$ itself. Different enumerations lead to different $q$.
Then given any infinite sequence of integers $(a_0,a_1,a_2,...)$, we can define a function $f$ on $S$ as: $$f(s) = \sum_{i=0}^\infty {a_i q_{S,i}(s)}$$
This is well defined because if $s\in S$ then $s=s_m$ for some $m$, and if $n>m$, $q_{S,n}(s_m)=0$. So for any particluar $s\in S$, this sum is finite.
Theorem: $f\in \operatorname{Cong}(S)$.
Proof: If $s_n,s_m\in S$, then we want to show that $(s_n-s_m) \mid (f(s_n)-f(s_m))$. But for $k>\max(n,m)$, we can define an integer polynomial: $$g(x) = \sum_{i=0}^k {a_i q_{S,i}(x)}$$
And this has the property that $g(s_n)=f(s_n)$ and $g(s_m)=f(s_m)$. So $f(s_n)-f(s_m)=g(s_n)-g(s_m)$, which, since $g$ is an integer polynomial, must be divisible by $s_n-s_m$, and hence we are done.
Essentially, these functions are "locally" integer polynomials.
Theoream: There are uncountable many congruent functions on an infinite set $S$.
Proof: It is not hard to show, inductively, that each distinct sequence $(a_0,a_1,...)$ determines a unique function $f$.
The case $S=\mathbb{N}$ is relatively simple. Using the standard enumeration, $\mathbb{N} = \{0,1,2,...\}$, we get that the $q$ polynomials are just the "falling factorials:" $$q_{\mathbb{N},k}(x) = (x)_k = x(x-1)...(x-(k-1))$$
Define $\operatorname{lcm}[n] = \operatorname{lcm}(1,2,...,n)$ to be the least common multiple of the first $n$ positive natural numbers.
Theorem: A function $f$ is congruent on $\mathbb{N}$ if and only if $f$ can be written as: $$f(n) = \sum_{k=0}^\infty a_k {\frac{\operatorname{lcm}[k]}{k!}} (n)_k = \sum_{k=0}^\infty a_k \operatorname{lcm}[k] {n \choose k}$$
And such a form for $f$ is unique.
Proof: That the polynomials: $$g_k(x)=\frac{\operatorname{lcm}[k]}{k!}(x)_k$$ are congruent is proven in a separate article. This gives us some polynomials without integer coeffiecients that are congruent functions, for example $$g_4(x)=\frac{x(x-1)(x-2)(x-3)}{2}$$
Now, given a congruent function $f$ on $\mathbb{N}$, we will define $a_k$ inductively so that $f(k) = \sum_{i=0}^{k} a_i g_i(k)$.
Define $a_0=f(0)$.
Assume $a_0,..,a_{k-1}$ are defined so that the function:
$$p_k(x) = \sum_{i=0}^{k-1} a_i g_i(x)$$has the property that $p_k(i) = f(i)$ for $0\leq i < k$.
Since $p_k(x)$ is a finite integer combination of congruent functions $g_i$, $p_k(x)$ is congruent on all of $\mathbb{N}$. In particular, then, we have that: $p_k(k) \equiv p_k(i) \pmod {k-i}$ for $i=0,...,k-1$. But we know that, since $f$ is congruent, that $f(k) \equiv f(i) \pmod {k-i}$ for $i=0,...,k-1$. Since $f(i)=p_k(i)$ for $0\leq i<k$, we have that $f(k)\equiv p_k(k) \pmod {k-i}$ for all such $i$. By the Chinese Remainder Theorem, that means that $$p_k(k) \equiv f(k) \pmod {\operatorname{lcm}[k]}$$
Let $$a_k=\frac{f(k)-p_k(k)}{\operatorname{lcm}[k]}$$
Then $p_{k+1}(x) = p_{k}(x) + a_k g_k(x)$, and we see that $$p_{k+1}(i)=p_k(i) = f(i)$$ for $i=0,...,k-1.$ And we see that $$p_{k+1}(k) = p_k(k) + a_k g_k(k)$$
But $g_k(k) = \operatorname{lcm}[k]$, so $p_{k+1}(k) = p_k(k) + a_k {\operatorname{lcm}[k]} = f(k)$.
Note: Mahler's theorem says that any continuous $p$-adic function can be written as: $$f(n) = \sum_{k=0}^\infty (\Delta^k f)(0) {n \choose k}$$ Where: $$(\Delta g)(n) = g(n+1) - g(n)$$
Congruent functions on $\mathbb{N}$ are uniformly continuous in nice ways as $p$-adic functions for all $p$, and the above classification proves that $(\Delta^k f)(0)$ must be divisible by $\operatorname{lcm}[k]$.
The case of $\mathbb{Z}$ is only slightly harder than $\mathbb{N}$. Here, our enumeration is $\{0,1,-1,2,-2,3,-3....\}$, and our $q$ functions are shifted falling factorials: $$q_k(x) = \left(x+ \left\lfloor {\frac{k-1}{2}} \right\rfloor\right)_k$$ where $\left\lfloor y \right\rfloor$ is the floor function.
The essentially same argument can be used to show that any congruent function on $\mathbb{Z}$ can be represented uniquely in the form: $$f(n) = \sum_{k=0}^\infty a_k \frac{\operatorname{lcm}[k]}{k!} \left(x+ \left\lfloor {\frac{k-1}{2}} \right\rfloor\right)_k$$
We can define a small category with the objects equal to the non-empty subsets of $\mathbb{Z}$ and the morphisms equal to the congruent functions between two subsets. Composition of congruent functions is a congruent function, so this forms a category, which we'll call $\mathbb{Cong}$. The ring we've been calling $\mathbb{Cong}(S)$ can be seen as $\operatorname{Hom}_{\mathbb{Cong}}(S,\mathbb{Z})$, and this gives a co-variant functor from $\mathbb{Cong}$ to $\mathbb{CRing}$, the category of commutative rings.
We might prefer to restrict the objects of $\mathbb{Cong}$ to be the infinite subsets of $\mathbb{Z}$ and the singleton subsets. Since the range of a congruent function on an infinite set is either infinite or a single value, this restriction would still allow us to explore all the interesting cases, and it would ensure that $\operatorname{Cong}(S)$ is always an integral domain.
If $S\subsetneq T$, is the natural homomorphism $\operatorname{Cong}(T)\rightarrow \operatorname{Cong}(S)$ ever an isomorphism? When is there a congruent function on $S$ that cannot be extended to $T$?
The answer is "no," and we can answer this using a concept I call the obstruction ring.
If $f\in\operatorname{Cong}(S_1)$ and $g\in\operatorname{Cong}(S_2)$, with $S_1\cap S_2$ infinite, and $f$ and $g$ agree on $S_1 \cap S_2$, are $f$ and $g$ necessarily compatible? The answer is, perhaps surprisingly, no.
Therefore, given an $f\in\operatorname{Cong}(S)$, the set of $T\supset S$ to which $f$ can be extended might be an interesting set. It is a "lower set" on the boolean algebra of subsets of $\mathbb{Z}-S$, but how complicated can it get?
If $S$ is suitably dense, say, if for every $m.n\notin S$, and every $p^\alpha\mid (m-n)$ there is an $s\in S$ such that $s\equiv m \equiv n \pmod {p^\alpha}$, then any extensions of $f$ are compatible.
In particular, then, if $S$ is co-finite, then any two extensions of $f$ are compatible. So for this set to be interesting, $S$ and $\mathbb{Z}-S$ both need to be infinite.
If $m,n\notin S$, we might define a relationship R: $(m,n)\in R$ if an only if any congruent function on $S$ which can be extended to $S\cup\{m\}$ and $S\cup\{n\}$ can be extended to $S\cup\{m,n\}$. Clearly, this is reflexive and symmetric, but it is not necessarily transitive: since $(n,n+1)\in R$ for all $n,n+1\notin S$, but in the proof that there are incompatible extensions, we found an $S$ with $0,1,2\notin S$, and $(0,2)\notin R$.
Obstruction rings again let us answer the question of when two $m,n\notin S$ are compatible. It turns out that $mRn$ if and only if for any prime power $p^k\mid (m-n)$, $\exists s\in S: p^k\mid m-s)$.
When $S$ is infinite, and $T\cap S=\emptyset$, when can we find an $f$ congruent on $S$ which cannot be extended to any $t\in T$?
In particular, can we always find a congruent function on $S$ that cannot be extended to any value of $\mathbb{Z}-S$?
If $T=\{t_1,t_2,...,t_n\}$ is finite, we can solve this problem by defining $f_i\in \operatorname{Cong}(S\cup T - \{t_i\})$ which cannot be extended to $t_i$, and then define $f(s)=\sum_{i=1}^n f_i(s)$. It's pretty easy to show that for each $t\in T$, $f$ cannot be extended to $t$.
Theorem: Given $n\in\mathbb{N}$, there exists $f\in\operatorname{Cong}(\mathbb{Z}-\{0\})$ which cannot be extended to $0$, and such that $f(k)=0$ when $|k|\leq n$.
Proof: First define $g\in\operatorname{Cong}(\mathbb{N}^{+})$ so that $g$ cannot be extended to $0$. By our classification, we know that we can write$$g(m) = \sum_{k=0}^\infty a_k \frac{\operatorname{lcm}[k]}{k!}(m-1)_k$$
Now let $$h_n(m) = \sum_{k=n^2}^\infty a_k \frac{\operatorname{lcm}[k]}{k!}(m-1)_k$$ Then $g-h_n$ is congruent on all of $\mathbb{Z}$, so in particular can be extended to $0$. So $h_n$ is congruent on $\mathbb{N}^+$, cannot be extended to $0$, and $h_n(m)=0$ for $m\leq n^2$.
So, define $f\in \operatorname{Cong}(\mathbb{Z}-\{0\})$ by $f(m)=h_n(m^2)$. Can we extend $f$ to $0$? If so, then for all $m>0$, $f(0)\equiv f(m) \equiv h_n(m^2) \equiv h_n(m) \pmod m$, so we'd have an extension of $h_n$ to $0$.
So $f$ has no extension to $0$,and for $|m|\leq n$, $f(m)=h_n(m^2)=0$. So we are done.
Corrolary: For any $t\in\mathbb{Z}$, and any $n\geq 0$, there is an $f\in\operatorname{Cong}(\mathbb{Z}-\{t\})$ so that $f$ cannot be extended to $t$, and $f(m)=0$ for $|m|\leq n$.
Proof: Using the previous theorem, find a $g$ so that $g$ cannot be extended to $0$ and such that $g(m)=0$ for $|m|\leq n+|t|$. Then define $f(m)=g(m-t)$.
Theorem: Let $S$ be an infinite set. Then there is an $f\in\operatorname{Cong}(S)$ which cannot be extended to any element of $\mathbb{Z}-S$.
Proof: Enumerate the set $\mathbb{Z}-S=\{t_1,t_2,...\}$, and for each $i$, define an $f_i\in\operatorname{Cong}(\mathbb{Z}-\{t_i\})$ so that $f_i$ cannot be extended to $t_i$ and $f_i(m)=0$ for $m\leq i$.
The sum $f=\sum_{i>0} f_i$ is defined and congruent on $S$ because only finitely many are needed to evaluate on any $s\in S$. On the other hand, for any particular $i$, $f-f_i$ is defined and congruent on $S\cup \{t_i\}$. Since $f_i$ cannot be extended to $t_i$, then $f = (f-f_i) + f_i $ cannot be extended to $t_i$.
If $\mathcal{F}$ is a filter on $\mathbb{Z}$, then we can define the set, $\operatorname{Cong}(\mathcal{F})$, of congruent functions on $\mathcal{F}$ as any congruent function on an element of $\mathcal{F}$ with an equivalence relation that $f$ on $S\in \mathcal{F}$ and $g$ on $T\in \mathcal{F}$ are equivalent if $f=g$ on $S\cap T\in \mathcal{F}$.
This forms a ring, and it is again an integral domain if all $S\in\mathcal{F}$ are infinite. $\operatorname{Cong}(\mathcal{F})$ can also be defined as the direct limit of $\operatorname{Cong}(S)$ , taken over $S\in\mathcal{F}$.
For example, take the filter generated by the subsets $n\mathbb{Z}$ - that is, $S\in \mathcal{F}$ if an only if there is an $n\neq 0$ such that $n\mathbb{Z}\subset S$. What is $\operatorname{Cong}(\mathcal{F})$?
Every element $f\in\operatorname{Cong}(n\mathbb{Z})$ can be written uniquely as: $$f(nk) = f_0 + n f_1(k) $$
Where $f_0\in\mathbb{Z}$ and $f_1\in \operatorname{Cong}(\mathbb{Z})$ with $f_1(0)=0$.
Definition: If $h\in \operatorname{Cong}(\mathbb{Z})$ with $h(0)=0$, and $d\in\mathbb{Z}$, $d\neq 0$, then define $(d*h)(n)=h(dn)/d$
Lemma: $d*h\in\operatorname{Cong}(\mathbb{Z})$
Proof: Easy.
Lemma: If $d_1,d_2\in\mathbb{Z}$, then $d_1*(d_2*h) = (d_1d_2)*h$.
Proof: Easy.
Lemma: If $f\in\operatorname{Cong}(m\mathbb{Z})$ is written as: $$f(mk) = f_0 + m f_1(k)$$ then the image of $f$ in $\operatorname{Cong}(nm\mathbb{Z})$ is: $$f(mnk) = f_0 + mn(n*f_1)(k)$$
Proof: Easy.
If $f\operatorname{Cong}(m\mathbb{Z})$ corresponsed to $(f_0,f_1)$ and $g\in\operatorname{Cong}(n\mathbb{Z})$ corresponsed to $(g_0,g_1)$, then $$(f+g)(mnk) = f(nmk) + g(mnk) = (f_0+g_0)+mn((n*f_1)(k) + (m*g_1)(k)$$ So $f+g\in\operatorname{Cong}(mn\mathbb{Z})$ corresponds to $(f_0+g_0, n*f_1 + m*g_1)$.
For products, $$(fg)(mnk)=f(mnk)g(mnk) = (f_0+mn(n*f_1)(k))(g_0+mn(m*g_1)(mk))$$ $$=f_0g_0 + mn [g_0(n*f_1)(k) + f_0 (m*g_1)(k) + (n*(mf_1))(m*(ng_1))]$$
So $fg$ corresponds to $(f_0g_0,n*(g_0f_1) + m*(f_0g_1) + (n*(mf_1))(m*(ng_1)))$
If $\mathcal{F}$ is the principal filter for a set $S$, then $\operatorname{Cong}(\mathcal{F}) \cong \operatorname{Cong}(S)$.
The case when $\mathcal{F}$ is a non-principal ultrafilter might be particularly interesting.
In this case, we can define $\mathcal{J}_{\mathcal{F},n}$ for all $n\in\mathbb{Z}$ as the ideal of $\operatorname{Cong}(\mathcal{F})$ consisting of those $f\in\operatorname{Cong}(S)$ for some $S\in\mathcal{F}$ such that $n\in S$ and $f(n)=0$. What is $\operatorname{Cong}(\mathcal{F})/{\mathcal{J}_{\mathcal{F},n}}$?