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?

  • $\begingroup$ 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 $\endgroup$ – Yuriy S Feb 15 '18 at 14:05
  • 1
    $\begingroup$ If $f(z)=\Re (z)$ then any $c\in \mathbb R$ works. $\endgroup$ – lulu Feb 15 '18 at 14:06
  • $\begingroup$ @lulu, thank you for the example $\endgroup$ – Yuriy S Feb 15 '18 at 14:17
  • $\begingroup$ @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$. $\endgroup$ – 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.

  • $\begingroup$ Thank you very much for this deep insight into the problem. Can the explicit expression for the function $f$ of your counterexample be given? $\endgroup$ – user Feb 15 '18 at 17:44
  • 1
    $\begingroup$ 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$. $\endgroup$ – Eric Wofsey Feb 15 '18 at 17:50
  • $\begingroup$ 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$. $\endgroup$ – Eric Wofsey Feb 15 '18 at 17:55
  • $\begingroup$ 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. $\endgroup$ – Eric Wofsey Feb 15 '18 at 18:00
  • $\begingroup$ 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}$? $\endgroup$ – user Feb 15 '18 at 18:01

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.