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

Solution 1:

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.