18
$\begingroup$

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?

$\endgroup$
22
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – feralin Dec 6 '16 at 8:02
  • $\begingroup$ Sorry, that was a remnant of an earlier iteration of the definition. $\endgroup$ – Robert Israel Dec 6 '16 at 8:03
19
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – feralin Dec 6 '16 at 8:20
  • 1
    $\begingroup$ Why does infinitely many steps, each one with infinitely many choices, result in uncountable many choices? This seem non-trivial to me. $\endgroup$ – Pedro A Dec 6 '16 at 11:30
  • 4
    $\begingroup$ @Hamsteriffic Because N^N=R. Even if we had two choices at each step, 2^N still would be R. $\endgroup$ – Serge Seredenko Dec 6 '16 at 12:44
  • 1
    $\begingroup$ @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 $\endgroup$ – djechlin Dec 7 '16 at 1:02
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.