6
$\begingroup$

Which functions satisfy $\forall n,x,y (x \equiv y \pmod n \implies f(x) \equiv f(y) \pmod n )$ ?

I know polynomials do; are there others?

1 Answers 1

3

There are such functions which are not polynomials. We will construct an example of a function $g$ which grows faster than any polynomial, and such that for all integers $m \ge 1$, and all non-negative integers $x$ and $y$, if $x \equiv y \pmod{m}$, then $g(x)\equiv g(y)\pmod{m}$. It will follow immediately that if $f(x)=g(x^2)$, then for all integers $x$, $y$, if $x \equiv y \pmod{m}$ then $f(x) \equiv f(y)\pmod{m}$, and $f$ is not a polynomial.

Let $g(0)=1$. Suppose that we have defined $g(k)$ for all non-negative $k2^n$ (this part is to make sure that $g$ grows faster than any polynomial).

Suppose that $g$ has the desired congruence property for all $x$, $y$ with $0 \le x, y

  • 2
    I haven't checked the details, but I suspect what you are doing is **diagonalizing** out of polynomials. This was in fact the genesis of the diagonalization method, viz. du Bois-Reymond discovered the method for the purpose of diagonalizing on asymptotic growth rates (order of infinity). Only later was it (independently?) discovered by Cantor.2011-03-29
  • 1
    Sort of, I guess. By choosing the $A_n$ appropriately, one can make the values of the function positive or negative in any pattern. So there are continuum many functions that satisfy the condition. Too bad, it would have been nice if there were \emph{some} structure.2011-03-29