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.

  • 1
    $\begingroup$ Are you sure about function g(x)=(-3)/2? $\endgroup$ – Med Nov 2 '16 at 13:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Greg Martin Nov 3 '16 at 18:40
  • 2
    $\begingroup$ 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)$.) $\endgroup$ – Greg Martin Nov 3 '16 at 23:01
  • 1
    $\begingroup$ Somewhat similar question: math.stackexchange.com/questions/1934482/… $\endgroup$ – Gerry Myerson Nov 5 '16 at 12:01
  • 1
    $\begingroup$ 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." $\endgroup$ – 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

  • $\begingroup$ 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? $\endgroup$ – Mastrem Nov 5 '16 at 12:27
  • $\begingroup$ That would be my interpretation. $\endgroup$ – Gerry Myerson Nov 5 '16 at 12:29
  • $\begingroup$ Allright then. I think this gives a good answer to my question. The bounty is yours. $\endgroup$ – Mastrem Nov 5 '16 at 12:31
  • $\begingroup$ in 2 hours apperentely $\endgroup$ – Mastrem Nov 5 '16 at 12:31

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.