# Do the solutions to functional equation $f(f(z))=f(z-c)+c$ necessarily have a fixed point?

Let a function $f(z)$ defined for all $z\in\mathbb{Z}$ (without any further restrictions) satisfy the equation: $$f(f(z))=f(z-c)+c,\tag{1}$$ where $c\ne0$ is an integer constant. Is the following statement valid:

There exists $z_0$ such that: $$f(z_0)=z_0.\tag{*}$$ Provided that such a point exists it can be shown that the equation (*) is satisfied in fact for all points: $$z_k=z_0+kc,\quad k\in\mathbb{Z}.\tag{2}$$

Initially the conjecture was formulated for complex domain, but appears to be false. By similar argument it should fail also in real domain, though the counterexample shall be obviously a bit trickier. However can the conjecture still be valid for integer functions?

• Do you have an example of a solution which is not $f(z)=z$? I'm just curious, since so far I don't know how to find it – Yuriy S Feb 15 '18 at 14:05
• If $f(z)=\Re (z)$ then any $c\in \mathbb R$ works. – lulu Feb 15 '18 at 14:06
• @lulu, thank you for the example – Yuriy S Feb 15 '18 at 14:17
• @Yuriy S Assume set (2) exists. For points $z'_k=z'_0+kc$ lying outside the set define $f(z'_k)=z_0+kc$. Clearly $f(z'_k)\ne z'_k$ but (1) is satisfied for all $z'_k$. – user Feb 15 '18 at 15:20

No. Let me first consider a structure that may seem unrelated but whose relevance will be made clearer later. Let $G$ be the group of affine automorphisms of $\mathbb{R}$: that is, maps $\mathbb{R}\to\mathbb{R}$ of the form $x\mapsto ax+b$ for $a\neq 0$. Let $f\in G$ be the map $x\mapsto x+1$ and let $c\in G$ be the map $x\mapsto 2x$. Note that these group elements satisfy the relation $$f^2=cfc^{-1}$$ (the choice of variables $f$ and $c$ is not a coincidence, and hopefully this is starting to look familiar!).

Now let $H$ be the subgroup of $G$ generated by $c$ and let $H$ act on $G$ by left translation. As an $H$-set, $G$ is an disjoint union of $2^{\aleph_0}$ copies of $H$ (namely, all the cosets of $H$).

Now let $H$ also act on $\mathbb{C}$, with $c$ acting as the map $z\mapsto z+c$ (this is a well-defined action since $c$ has infinite order). Once again, as an $H$-set, $\mathbb{C}$ is just a disjoint union of $2^{\aleph_0}$ copies of $H$. So there is an isomorphism of $H$-sets $F:G\to \mathbb{C}$.

Now we define our map $f:\mathbb{C}\to\mathbb{C}$ by just transferring multiplication by the element $f\in G$ along the isomorphism $F$. That is, we define $$f(z)=F(f\cdot F^{-1}(z)).$$ The relation $f^2=cfc^{-1}$ on $G$ then exactly turns into the functional equation $$f(f(z))=f(z-c)+c.$$ Moreover, there does not exist any $z\in\mathbb{C}$ such that $f(z)=z$, since that would mean that $f\cdot F^{-1}(z)=F^{-1}(z)$ which is impossible because $f$ is not the identity element of $G$.

The larger insight here is that your functional equation involves no structure of the set $\mathbb{C}$ other than the map $z\mapsto z+c$. That is, it depends only on the structure of $\mathbb{C}$ as an $H$-set. That structure is quite simple: it's just a huge disjoint union of copies of $H$, and the group $H$ is isomorphic to $\mathbb{Z}$. So you can more easily construct solutions to the functional equation by forgetting all the irrelevant structure of $\mathbb{C}$ and just thinking of it as a giant disjoint union of copies of $\mathbb{Z}$, with the map $z\mapsto z+c$ corresponding to adding $1$ on each copy of $\mathbb{Z}$.

The use of the group $G$ above is a particularly elegant way to harness this to construct a counterexample to your question, but you could also construct one by just messing around with a big disjoint union of copies of $\mathbb{Z}$ directly. For instance, you could start by picking one copy of $\mathbb{Z}$, and say that $f$ should map one element of it to a different copy of $\mathbb{Z}$, and then see what further properties of $f$ are forced by the relation $f^2=cfc^{-1}$. With a bit of work you can work out a countable collection of copies of $\mathbb{Z}$ which $f$ can map to each other while satisfying the functional equation*. Partitioning the $2^{\aleph_0}$ copies of $\mathbb{Z}$ into countable pieces, you can then use this recipe on each piece to get the desired $f$.

*This essentially amounts to constructing the free monoid with elements $f$ and an invertible element $c$ satisfying $f^2=cfc^{-1}$, and verifying that the subgroup generated by $c$ acts freely on it and $f$ has no fixed points. The trick of using the group $G$ as I did is that it provides a ready-made monoid satisfying these relations with the subgroup generated by $c$ acting freely and $f$ having no fixed points, so you don't have to construct one combinatorially.

• Thank you very much for this deep insight into the problem. Can the explicit expression for the function $f$ of your counterexample be given? – user Feb 15 '18 at 17:44
• That would be rather messy, as there's not going to be a nice formula for the isomorphism $F$ (in fact, there are $2^{2^{\aleph_0}}$ choices of $F$ you could make). Here's one choice of $F$ you can describe "explicitly". For simplicitly, let us suppose $c=1$. Let $X\subset G$ be the set of maps $x\mapsto ax+b$ with $|a|\in [1,2)$. Let $Y\subset\mathbb{C}$ be the set of all $z$ with $\operatorname{Re}(z)\in [0,1)$. Choose a bijection $F_0:X\to Y$. Note that every element of $G$ can be written uniquely as $c^nx$ for some $x\in X$, and so we can define $F$ by $F(c^nx)=F_0(x)+n$. – Eric Wofsey Feb 15 '18 at 17:50
• You can even make the bijection $F_0$ fairly nice in this case: you could let it send $x\mapsto ax+b$ to $a-1+bi$. You could in principle then unravel the definition $f(z)=F(f\cdot F^{-1}(z))$ to get an explicit description of $f$. I think it would end up being something like $f(x+iy)=x+i(y+2^{-n})$ where $n$ is the floor of $x$. – Eric Wofsey Feb 15 '18 at 17:55
• OK, that worked out to be less messy than I thought! Yeah, so $f(x+iy)=x+i(y+2^{-\lfloor x\rfloor})$ is an explicit example with $c=1$ you can get out of this construction. – Eric Wofsey Feb 15 '18 at 18:00
• Thank you once more. And again the question. Can the claim of the question still be valid for integer functions $f: \mathbb{Z}\rightarrow\mathbb{Z}$? – user Feb 15 '18 at 18:01