Determine all functions $f:\mathbb{Z}\to\mathbb{Z}$ such that $f\big(f(n)\big)=-(q-p)\,f(n)+pq\,n$ for all $n\in\mathbb{Z}$.

Question

Let $p$ and $q$ be integers. Let $S$ be a subset of $\mathbb{Z}$, and $f:S\to S$. Consider the functional equation of the form $$f\big(f(n)\big)=-(q-p)\,f(n)+pq\,n\text{ for each }n\in S\,.\tag{*}$$ If $p$ and $q$ satisfy $0<p<q$, and $S=\mathbb{Z}_{\geq 0}$ or $S=\mathbb{Z}_{>0}$, then the only solution is known to be $$f(n)=pn\text{ for all }n\in S\,.$$ See here and here for references.

The case of my particular interest is when $S=\mathbb{Z}$. We know that there are at least two solutions: $$f(n)=pn\text{ for all }n\in\mathbb{Z}$$ and $$f(n)=-qn\text{ for all }n\in\mathbb{Z}\,.$$

Are there other solutions when $S=\mathbb{Z}$?

What happens if $p<q$ does not hold (but they are still positive integers)? What can happen if we simply allow $p$ and $q$ to be any integer? How would these changes affect the cases $S=\mathbb{Z}_{\geq 0}$, $S=\mathbb{Z}_{>0}$, and $S=\mathbb{Z}$? (For example, when $p=1$ and $q=-1$, then there can be other solutions such as $f(n)=n+1$ for all $n\in S$.)

If you feel particularly enthusiastic today, then you can also consider the case where $p$ and $q$ are nonintegral, not necessarily real, algebraic integers such that $q-p$ and $pq$ are both integers. In this version of the problem (except for a few pairs $(p,q)$), I do not expect a solution in any of the cases $S=\mathbb{Z}_{\geq 0}$, $S=\mathbb{Z}_{>0}$, and $S=\mathbb{Z}$.

The trivial case $p=q=0$ is completely solved. Other known trivial cases are $p=q=1$ and $p=q=\sqrt{-1}$. However, I do not know other results even when $p=q$.

Here is a nontrivial example for a nonintegral pair $(p,q)$. When $S=\mathbb{Z}_{\geq0}$ or $S=\mathbb{Z}_{>0}$, there exists a strictly increasing function $f:S\to S$ such that $$f\big(f(n)\big)=3n\text{ for all }n\in S\,.$$ (This is an example when $p=q=\sqrt{3}$.)

This may be (or may not be) helpful. Here, $f^0:=\text{id}_S$ and $$f^k:=f\circ f^{k-1}$$ for $k\in\mathbb{Z}_{\geq 1}$. If $p+q\neq 0$, then $$f^k(n)=p^k\,\left(\frac{qn+f(n)}{p+q}\right)+(-q)^k\,\left(\frac{pn-f(n)}{p+q}\right)$$ for all $n\in S$ and $k\in\mathbb{Z}_{\geq 0}$. On the other hand, if $q=-p$ and $p\neq 0$, $$f^{k}(n)=p^k\,n+k\,p^{k-1}\,\big(f(n)-pn\big)$$ for all $n\in S$ and $k\in\mathbb{Z}_{\geq 0}$.

Answer 1

Here is another solution: $p=2,q=3,f(n)=\begin{cases} 2n \text{ if } n \text{ is even}\\ -3n\text{ if } n \text{ is odd}\end{cases}$

Use the technique from your first link, it can be shown that all solutions to the functional equation are of the form $f(n)=\begin{cases} pn \text{ if } n\in T\\ -qn\text{ if } n\in \mathbb{Z}\setminus T \end{cases}$

Write $f(f(…(n)..)$ as $f^k(n)$. Then $f^k(n)=-(q-p)f^{k-1}(n)+pqf^{k-2}n$. This is a linear recurrence equation and standard techniques yield a solution of the form $f^k(n)=A(n)p^kn+B(n)(-q)^kn$. Substituting back into the original functional equation tells us that $A+B=1+2AB$. The only integer solutions are $A=1,B=0$ and $A=0,B=1$.

Answer 2

The answer below considers the easiest case where $p=q=\sqrt{b}$ (where $b$ is an integer) and aims to provide the complete solution of this particular sub-problem.

We are looking for functions $f:S\to S$ satisfying the equality $$f\left(f\left(n\right)\right)=b\cdot n$$ for all $n\in S$, where $S$ is a fixed, non-empty set of integers. It is obvious that $S$ must be closed under multiplication by $b$, so this will be assumed from now on.

Evaluating the expression $f\left(f\left(f\left(n\right)\right)\right)$ in two different ways gives us a useful property of $f$:

$$f\left(b\cdot n\right) = f\left(\ f\left(f\left(n\right)\right)\ \right) = f\left(f\left(\ f\left(n\right)\ \right)\right) = b\cdot f(n) $$

which must be satisfied for every $n\in S$.

Now, we are ready to resolve a few special cases:

• $b=0$

  If $T$ denotes the set of integers mapped to zero by $f$, any integer $n\in\left(S-T\right)$ must be mapped to a number from $T$ in order to satisfy $f\left(f\left(n\right)\right)=0$. Since $f(0)=f(0\cdot 0)=0\cdot f(0)=0$, we have $0\in T$. Other than this single restriction, $T$ can be an arbitrary subset of $S$.

  It works the other way round too: If we choose any subset $T$ of $S$ which contains $0$ and any function $g:(S-T)\to (T-\{0\})$, we can define $f$ as $$ f(n)=\begin{cases} 0 & \textrm{ if }n \in T \\ g(n) & \textrm{ if }n \in (S-T) \\ \end{cases}$$

• $b=1$

  We need to satisfy $f\left(f\left(n\right)\right)=n$ which simply says $f$ is an involution and it's clear that any involution on $S$ would work.

• $b=(-1)$

  If $S$ contains zero, we have $f(0)=-f(0)$ and thus $f(0)=0$. For any other integer $n\in S$, we can consider the set of $M=\{n, f\left(n\right), f\left(f\left(n\right)\right), f\left(f\left(f\left(n\right)\right)\right), \ldots\}$. Since we have $f\left(f\left(n\right)\right)=(-n)$, we can simplify it to $M=\{n, f(n), (-n), -f(n)\}$.

  None of the numbers in $M$ can be zero (since that would make all of them zero and we assumed $n$ to be non-zero) and $f(n)=\pm n$ would imply $(-n) = f(f(n))=f(\pm n) = \pm f(n) = n$, all four numbers are distinct and exactly two of them must be positive, where one of them is obtained by applying $f$ to the other one.

  This "pairing" of positive integers of $S$ defined by $f$ can be represented by a bijection and, vice versa, if $S^+$ denotes the subset of positive integers within $S$ and we choose any subset $T\subset S^+$ of them and any bijection $g:T\to (S^+-T)$, we can define $$ f(n)=\begin{cases} g(n) & \textrm{ if }n \in T \\ -g^{-1}(n) & \textrm{ if }n \in (S^+-T)\\ -g(-n) & \textrm{ if }(-n) \in T \\ g^{-1}(-n) & \textrm{ if }(-n) \in (S^+-T)\\ 0 & \textrm{ if }n=0 \textrm{ (only if $0\in S$)} \end{cases}$$

Now we are ready to tackle all the remaining cases. It is easy to see that $f$ must be injective: $$f(x)=f(y)\implies f\left(f\left(x\right)\right) = f\left(f\left(y\right)\right) \implies b\cdot x = b\cdot y \implies x=y$$

If $0\in S$, we have $f(0)=f(b\cdot 0)=b\cdot f(0)$ which implies the only possible value of $f(0)$ is $0$. For any other integer $n\in S$, we have $f(b\cdot n)=b\cdot f(n)$, and thus also $f(b^k\cdot n)=b^k\cdot f(n)$ for any non-negative integer $k$.

Thus, if $S^*$ denotes the set $$S^* = \{n \in S\ |\ (n/b)\not\in S\}$$ the function $f$ is fully determined if we know its values for members of $S^*$. For any $n\in S^*$, there are only three possibilities:

• $f(n)=m\in S^*$ and we have $f(m)=b\cdot n$ in order to satisfy $f(f(n))=b\cdot n$, or
• $f(n)=b\cdot m$ for some $m\in S^*$, where we get $f(m)=n$ since $f$ is injective and we have $f(f(m))=b\cdot m=f(n)$, or
• $f(n)=b^2\cdot m$ for some $m \in S$. Again, the injectivity of $f$ implies $f(b\cdot m)=n$, but in this case we also have $f(b\cdot m)=b\cdot f(m)$. This contradicts the choice of $n$ as member of $S^*$.

Thus, $S^*$ consists of pairs of integers for which $f$ maps one member of the pair to the other one (but not vice versa). Just like before, this implies we can construct any function $f$ by considering a set $T\subset S^*$ and a bijection $g:T\to (S^*-T)$ and defining $$ f(n)=\begin{cases} b^k\cdot g(m) & \textrm{ if }n=b^k\cdot m\textrm{ with }m\in T \\ b^{k+1}\cdot g^{-1}(m) & \textrm{ if }n=b^k\cdot m\textrm{ with }m\in (S^*-T) \\ 0 & \textrm{ if }n=0 \textrm{ (only if $0\in S$)} \end{cases}$$

This completes the analysis of the $p=q$ case and shows that there are more than enough solutions in each case.

As a specific example, if $b\geq 3$ is odd and $S=\mathbb{Z}_{>0}$, we can use the last construction and choose $T$ as the set of positive integers not divisible by $b$ whose leading digit in base-$b$ representation is smaller than $(b/2)$ and $g$ to be a function which increases the leading digit by $\frac{b-1}{2}$. The resulting function $f$ will be strictly increasing and can be extended to $S=\mathbb{Z}_{\geq 0}$ (by setting $f(0)=0$) or $S=\mathbb{Z}$ (by setting $f(n)=-f(-n)$ for $n<0$) without losing this property.