# Functions $f:\mathbb{N}\rightarrow \mathbb{Z}$ such that $\left(m-n\right) \mid \left(f(m)-f(n)\right)$

A long time back, I wondered what functions other than integer polynomials on $\mathbb{N}$ (or $\mathbb{Z}$) satisfied the property:

$$\forall m,n: \left(m-n\right) \mid \left(f(m)-f(n)\right)$$

Turns out that, on $\mathbb{N}$, you can categorize all such functions, using Chinese remainder theorem, as:

$$f(n)=\sum_{k=0}^{\infty}a_k \operatorname{lcm}[k] {n \choose k}$$

Where $\operatorname{lcm}[k]$ is the least common multiple of $\{1,2,...,k\}$ and the $a_k$ are arbitrary integers. (In particular, there are thus uncountably many of them.)

On $\mathbb{Z}$ a similar 'basis' can be found.

It then occurred to me that really, if we have any set $S\subset\mathbb{Z}$ we can define the set of functions $f:S\rightarrow \mathbb{Z}$ with this property, and that if $S$ is infinite (or if $|S|=1$) then the ring of such functions is an integral domain.

In fact, we can define a small category, with objects equal to non-empty subsets of $\mathbb{Z}$ and with morphisms any functions from one set to the other with this property. Then the ring which we defined above is really just $\operatorname{Hom}(S,\mathbb{Z})$ in this category.

1. If $S$ is infinite, then $\operatorname{Hom}(S,\mathbb{Z})$ contains a sub-ring isomorphic to $\mathbb{Z}[x]$.
2. If $S$ is infinite, the image of $S$ under such a function is either infinite or a set of size $1$, therefore we could just look at the sub-category of sets $S$ which are infinite or singletons, and then, in that case, the ring of functions from $S$ is always an integral domain.
3. $\operatorname{Hom}(S,\mathbb{Z})$ is a covariant functor from this category to the category of rings.
4. When $S_1 \subset S_2$, and $S_1$ is infinite, then the corresponding ring homomorphism is 1-1, but rarely (if ever) onto. This makes this category different than if we had just defined it in terms of integer polynomial functions only.

So, what are these functions? They clearly are functions which have nice $p$-adic proerties for all $p$, but I don't really know what else can be said about them, or about this category, or about these rings.

Edit: For example, are there cases where the rings corresponding to infinite sets $S$ and $T$ are isomorphic, but where the two sets are not translations or reflections of each other?

Edit: So, if you can extend all such functions from $\mathbb{Z}-\{0\}$ to $\mathbb{Z}$, it turns out you can extend any such function on $\mathbb{N}^+$ to $\mathbb{N}$, and then in turn you can extend any function on $\mathbb{N}$ to all of $Z$.

Proof: Assume we can extend any such function on $\mathbb{Z}-\{0\}$ to $\mathbb{Z}$. Let $f$ be such a function on $\mathbb{N}^+$, and define $g(n)=f(n^2)$ on $\mathbb{Z}-\{0\}$. Then $g(0)$ can be defined so that $g(n)-g(0)=f(n^2)-g(0)$ is divisible by $n$ for all $n$. Then for positive integers $n$, $f(n^2)-f(n)$ is divisible by $n$. And $f(n^2)-g(0)$ is divisible by $n$, so $f(n)-g(0)$ is divisible by $n$, so we can extend $f$ to $\mathbb{N}$ by setting $f(0)=g(0)$.

One way to think of these functions it to think of them as being continuous as $p$-adic for all primes $p$. In particular, then, if we are able to find an extension of $f$ on $\mathbb{N}^+$ to $\mathbb{N}$, then for each $p$, the $p$-adic limit, $\lim_{k\rightarrow \infty} f(p^k)$, must converge to a rational integer.

Resolution of the extension question:

Let $f(n) = \sum a_m (n)_m$ where $(x)_m$ is the falling factorial, $(x)_m = m! {x \choose m}$

This defines a suitable $f$ on $\mathbb{N}$. We will find suitable $\{a_m\}$ such that the $f(-1)$ cannot be defined as a rational integer so that it satisfies the condition.

Now, if we just naively tried to put $-1$ into the formula for $f(n)$, we'd see that $(-1)_m = (-1)^m {m!}$

But the nature of our condition on functions is that they are continuous as $p$-adic functions for all $p$. So, if there is an extension of $f$ to $-1$, it can be found by taking p-adic limits. In particular, we can see that in $p$-adic numbers, for all $p$, the "naive" sum must converge to our value $f(-1)$ in p-adic values:

$$f(-1) = \sum (-1)^m a_m {m!}$$

So, we are going to find $\{a_m\}$ such that the right hand sum is $(p-1)/2 \pmod p$ for all $p$. Then the sum cannot converge to an integer value.

We will set $a_m=0$ when $m+1$ is not an odd prime prime.

Now, $\mod p$, the sum only depends on terms $a_m$ with $m<p$. For each prime $p$, we can always find a $a_{p-1}$ such that $a_{p-1}(-1)^{p-1} (p-1)! + \sum (\text{previous terms})$ is $\frac{p-1}{2} \pmod p.$ None of the terms later will affect this fact, so we have that $f(-1) \equiv \frac{p-1}{2} \pmod p$ for all $p$. But then $f(-1)$ cannot be a rational integer.

Edit: Closing with my answer below. I've explored these functions some more here.

-
I suspect that if you let $S$ be any set with a finite complement in $\bf Z$, then you get the same functions you get for $S={\bf Z}$. If I'm right, that gives you tons of examples answering the question in your edit. –  Gerry Myerson Apr 18 '11 at 0:06
@Gerry Myerson: Hmm, I am not convinced that this would be true, but it is the case that if there is a function of this sort on $S=\mathbb{Z}-\{0\}$ which cannot be extended to all of $\mathbb{Z}$, then natural homomorphism of rings from any proper inclusion is not an isomorphism. –  Thomas Andrews Apr 18 '11 at 4:23
Okay, I'm pretty sure you can't extend all functions on $\mathbb{N|$ to $\mathbb{N}\cup\{-1\}$. If $f$ is written in the form $f(n)=\sum a_m (k)_m$ where $a_m$ are integers and $(x)_n$ is the falling factorial. Then if $f(x)$ extends to $-1$, then in $p$-adics the value of $f(-1)=\sum (-1)^m{a_m} m!$. But we can construct a sequence $\{a_m\}$ which ensures that this sum is $(p-1)/2 \pmod p$ for all primes $p$, and hence $f(-1)$ cannot be defined as an integer. –  Thomas Andrews Apr 24 '11 at 22:53
Have you seen Bhargava: The Factorial Function and Generalizations, AMM 2000 ? –  Bill Dubuque May 10 '11 at 19:06
@Bill Dubuque - I finally got around to look at the Bhargava article. Fascinating. –  Thomas Andrews May 15 '11 at 5:07

Apologies for answering my own question.

I think I can resolve the general extension question with the following lemma:

Lemma: If $S\subset \mathbb{Z}$ is infinite and $n\notin S$, then either:

(1) $n$ is in the $p$-adic closure of $S$ for some prime $p$.

or

(2) There exists infinitely many primes that divide some element of $\{s-n: s\in S\}$

Proof: Let $P=\{p^k\mid p\text{ prime and }\exists s\in S: p^k\mid(s-n)\}$ So $P$ is the set of prime power divisors of the differences between element of $S$ and $n$.

$P$ must be infinite, because if not, we could take the least common multiple of the elements of $P$ and get a number that must be a common multiple of the elements of $S-n$, which would contradict $S$ being infinite. Now, if (2) is false, then the set of primes in $P$ is finite. But that means for some $p$, infinitely many $p^k$ must be in $P$, which means that $n$ must be in the $p$-adic closure of $S$ for that $p$.

Theorem: If $S\subset \mathbb{Z}$ is infinite, and $n\notin S$, then there exists a function on $S$ with the property defined above which cannot be extended to $n$.

I won't put the entire proof here, but the result is shown using the lemma by breaking it up into the two cases.

In case (1), we can define an $f$ such that the $p$-adic limit of $f(s)$ as $s\rightarrow n$ approaches a $p$-adic number that is not a rational integer. Since the property defined makes $f$ continuous in the $p$-adic topology, there can only be one continuous definition for $f(n)$, and that value is not a rational integer.

In case (2), we define an $f$ such that if $f(n)$ can be defined, it would have the property that $f(n)\equiv \frac{p-1}{2} \pmod p$ for infinitely many primes $p$.

Both cases use the following idea. Enumerate $S=\{s_0,s_1,...\}$. Define the polynomials $q_{S,k}$ as follows:

$$q_{S,0}(x)=1$$ $$q_{S,k+1}(x) = (x-s_k)q_{S,k}(x)$$

These are sort of like the falling factorials for $S$. Given any sequence of integers $(a_0,a_1,...,a_k,...)$ we can define a function:

$$f(s) = \sum_{i=0}^\infty {a_i q_{S,i}(s)}$$

This function is well-defined on $S$ because for any particular $s\in S$, there are only finitely many non-zero terms in the sum, and it satisfies our property because it is "locally" a polynomial - for any finite subset of $S$, there is a polynomial that matches the values of $f$ on that subset.

So we define the $a_i$ inductively so that it forces the properties we need to keep $f(n)$ from being definable.

In the case of (1), we do so by making sure that:

$$\sum_{i=0}^\infty {a_i q_{S,i}(n)}$$

converges in the $p$-adics, that each term is positive, and the $p$-adic digits for the limit have infinitely many zero digits and infinitely many non-zero digits. Then the value cannot be a rational integer.

In case (2), we follow my proof from above for finding a function on $\mathbb{N}$ without continuation to $-1$. It's not much more work.

We let $m_k$ be the product of the odd prime divisors of $s_k-n$ which are not prime divisors of any $s_i-n$ with $i<k$. Then $q_{S,k}(s_k)$ is relatively prime to $m_k$, and so we can choose $a_k$ so that $f(s_k) \equiv \frac{m_k-1}{2} \pmod {m_k}$. But then if $f(n)$ can be defined, then $f(n)\equiv f(s_k) \pmod {m_k}$, since $m_k$ is a factor of $s_k-n$. So $f(n) \equiv \frac{m_k-1}{2} \pmod {m_k}$.

But there must be infinitely many distinct $m_k$ not equal to $1$, so we are done.

-