# Number of integer functions satisfying three constraints

I am trying to understand how many functions $\mathbb{Z^+}\to \mathbb{Z^+}$ which satistfy the three following constraints exist:

• For every $n \in \mathbb{Z^+}$ $$f(f(n))\leq\frac{n+f(n)}{2}$$

• For every $n \in \mathbb{Z^+}$ $$f(n)\leq f(n+1)$$

• For every $(n,m)\in \mathbb{Z}^{+}\times\mathbb{Z}^+$ such that $n \neq m$

$$\text{GCD}(f(n),f(m))=1$$

One of these functions is indeed $f(n)=1$ for every $n \in \mathbb{Z}^+$, but any other constant function does not satisfy the third constraint, which is probably the strongest.

My first intuition about other functions was something on the lines of $f(n)=\text{the n-th prime number}$, but this functions (or any of its multiples) does not satisfy the first constraint, already for $n=2$.

Are there any other functions that satisfy these constraints? How can they be found?

• What is $MCD$ in the third constraint? – Redundant Aunt Aug 27 '15 at 16:34
• @user109899 edited! I meant GCD. – Lonidard Aug 27 '15 at 16:36
• In the third constraint, if you don't specify $n \not = m$, then indeed $f(n)=1$ is the only solution – user261263 Aug 27 '15 at 17:41
• @EugenCovaci Yes, you are right. I'll fix it! – Lonidard Aug 27 '15 at 17:43

The constant function $f(n)=1$ is indeed the only solution, even if we weaken the first condition to: $f(f(n)) \le C(n+f(n))$ for some fixed $C>0$ (no matter how large).

As a proof-of-concept, we prove: there is no such solution with $f(1)>1$. Note that if $f(1)>1$ then $f(n+1)>f(n)$ (strictly) for all $n$, because of the gcd condition. In particular, $f(n)>n$; so it suffices to show there is no solution even if we replace $f(f(n)) \le C(n+f(n))$ by $f(f(n)) \le 2Cf(n)$. To do so, it suffices to show that $\lim_{k\to\infty} \frac{f(k)}k = \infty$.

Each of the values $f(1),\dots,f(k)$ is divisible by at least one prime, and these primes are distinct by the gcd condition; therefore $f(k)$ is at least as large as the $k$th prime. In particular, $f(k) > k\ln k$ by Rosser's theorem, and so indeed $\lim_{k\to\infty} \frac{f(k)}k = \infty$.

This shows that there is no such solution with $f(1)>1$. To consider any solution with $f(1)=1$: If $f(n)$ is not constant, then choose $K$ such that $f(K+1)>1$, and redo the above proof with the values $f(K+1), \dots, f(K+k)$ instead of $f(1),\dots,f(k)$.

Suppose $\exists n$ so that $f(n) \gt n$. Then, from the second condition we get: $$f(f(n)) \ge f(n) \tag 1$$ and, using (1) and the first condition: $$f(n) \le f(f(n))\leq\frac{n+f(n)}{2} \tag 2$$ from (2) we get: $$f(n) \le \frac{n+f(n)}{2} \tag 3$$ which contradicts our assumption $f(n) \gt n$.

We just proved that $f(n) \le n, \forall n$.

Now let's suppose there is $m$ so that $f(m)>1$. We have $$n \ge f(n) \ge f(m) \gt 1, \forall n \gt m \tag 5$$ and because of the third condition: $$n \ge f(n) \gt f(m) \gt 1, \forall n \gt m \tag 6$$ We can also extend (6): $$n \ge f(n)\gt f(n -1)\gt f(n -2)\gt .. \gt f(m + 1) \gt f(m) \tag 7$$ Let's define $A = \lbrace f(m+1),f(m+2), .. ,f(n) \rbrace$ and $B=\lbrace f(m) + 1, .. ,n \rbrace$

Then A has $n-m$ elements, B has $n-f(m)$ elements and $A \subset B$.

Let's take $n$ so that $n > (m+1)f(m) \tag 8$

Because of the third condition, all multiples of $f(m)$ are not in $A$, therefore we can define $C=B\setminus\lbrace kf(m)| 2 \le k \le m + 1 \rbrace$ and still having: $$A \subset C \tag 9$$ But $C$ has $n - f(m) - m$ elements while A has $n-m$ elements, so the inclusion (9) is not possible, therefore the assumption there is $m$ so that $f(m)>1$ is false.