# Do there exist functions that grow faster than $ax+b$, slower than $a^x$ and still posses these nice congruence properties?

Functions like $f(x)=2x+3$ and $f(x)=3^x-8$ have some very nice properties if it comes to congruences. In particular, if you pick any $n\in\Bbb{N}$ and write down $f(x)\mod n$, you'll see that it's a repeating pattern, with no numbers occuring more than once in each cycle.

A clearer, more formal definition due to Greg Martin:

A function $h$ defined on the positive integers is called faithfully periodic with period $q$ if it has the property $h(m)=h(n)$ if and only if $n\equiv m\pmod q$.

A function $f:\Bbb{N}\to\Bbb{Z}$ is now normal if for every modulus $k\geq 2$, the function $\pi_k\circ f$ is faithfully periodic, where $\pi_k:\Bbb{N}\to\Bbb{Z}/k\Bbb{Z}$ is the natural quotient map. Also, for every modulus $k\geq 2$, let $f_q(k)$ be the period of $\pi_k\circ f$.

I have not been able to find any normal functions which grow faster than a linear function, but slower than an exponential function, In particular normal functions $f(n)=O(n^\alpha)$ with $\alpha>1$

Question: Do there exist any such functions?

## What I've proven so far

1) This is quite obvious, but if $f$ is a normal function with $f(0)=0$, then $\forall n,m\in\Bbb{Z}: f_q(n)\mid m\implies m\mid f(n)$

Proof: set $\pi_k\circ f=h_k$. cleary for all $k$, we have $h_k(0)=0$. Now $h_k(n)=0$ if and only if $f_q(k)\mid n$.

## Some Intuition about why linear and exponential functions are normal

Short and simple: they can be defined as sequences $\{a_n\}_{n=1}^{\infty}$ in such a way that, for all $k\in\Bbb{N}$, we don't need to know the value of $n$ or $a_{n-1}$ to compute $a_n\pmod k$, we only need $a_{n-1}\pmod k$. To be clear, this is just my intuiton. I think it will be easy to prove that such functions are always normal, but not easy to prove that all normal functions 'look' like this.

• Are you sure about function g(x)=(-3)/2? – Med Nov 2 '16 at 13:42
• I think the following wording of the definition would be clearer: Say a function $h$ defined on positive integers is faithfully periodic with period $q$ when it has the property: $h(m)=h(n)$ if and only if $m\equiv n\pmod q$. (Regular periodic functions satisfy the "if" but not necessarily the "only if".) Then your "normal" function is just a function $f\colon\Bbb N\to\Bbb Z$ such that, for every modulus $k\ge2$ the reduced function $\pi_k\circ f$ is faithfully periodic, where $\pi_k\colon\Bbb N\to\Bbb Z/k\Bbb Z$ is the natural quotient map. – Greg Martin Nov 3 '16 at 18:40
• No, I couldn't think of one. One observation though: if $f$ ever takes the same value twice, then it takes that value on an infinite arithmetic progression. (Proof: if $f(m)=f(n)$, then $f(m)\equiv f(n)\pmod k$, and hence $f_q(k)\mid(m-n)$, for every $k$. In particular, if $z-n$ is a multiple of $m-n$, then $f(z)\equiv f(n)\pmod k$ for every $k$, which implies that $f(z)=f(n)$.) – Greg Martin Nov 3 '16 at 23:01
• Somewhat similar question: math.stackexchange.com/questions/1934482/… – Gerry Myerson Nov 5 '16 at 12:01
• Might be worth looking at A. Perelli, U. Zannier, On periodic mod p sequences, Journal of Number Theory 15 (August 1982) 77-82. "In this paper we characterize completely the integral valued arithmetical functions, periodic mod $p$ for every large prime $p$, which take incongruent values mod $p$ in every period." – Gerry Myerson Nov 5 '16 at 12:04

I think a stronger result is given in the Perelli-Zannier paper I mention in the comments. A sequence of integers is "arithmetically periodic" if it is periodic modulo $p$ for all sufficiently large primes $p$.

Theorem. Let $f:{\bf N}\to{\bf Z}$ be arithmetically periodic, with period $r_p$ for prime $p>p_0$. Suppose there exists a set $J_p\subseteq{\bf Z}/p{\bf Z}$ such that $|J_p|=r_p$ and $$f({\bf N})\cap(a+p{\bf Z})\ne\emptyset{\qquad\rm whenever\qquad}a\in J_p$$ Then three cases can occur:

(i) $r_p$ is constant for large $p$, and $f$ is periodic.

(ii) $r_p=p$ for large $p$, and $f$ is a polynomial of degree 1.

(iii) There exists an integer $a$ and rational numbers $A$ and $B$ such that $f(n)=Aa^n+B$.

The paper is available from http://www.sciencedirect.com/science/article/pii/0022314X8290083X

• Thank you for the link to the paper, I'm looking at it right now. It seems that I've found cases ii and iii already and a periodic function obviously doesn't grow at the rate I want, hence such a function (growing at about the same rate as $n^\alpha$) does not exist. Correct? – Mastrem Nov 5 '16 at 12:27
• That would be my interpretation. – Gerry Myerson Nov 5 '16 at 12:29
• Allright then. I think this gives a good answer to my question. The bounty is yours. – Mastrem Nov 5 '16 at 12:31
• in 2 hours apperentely – Mastrem Nov 5 '16 at 12:31