# What's the solution of the functional equation

I need help with this:

"Find all functions $f$, $g : \mathbb{Z} \rightarrow \mathbb{Z}$, with $g$ injective and such that: $$f(g(x)+y) = g(f(x)+y), \mbox{ for all } x, y \in \mathbb{Z}.$$

-
Did you mean all functions? –  1015 Feb 13 '13 at 18:46
italic bold YES –  user62189 Feb 13 '13 at 19:20
A few random remarks: Notice that if we set $y=0$, we get $f(g(x))=g(f(x))$ for every $x\in\mathbb{Z}$. $f$ is injective: we can write every $x\in\mathbb{Z}$ as $g(0) + y$ for some $y = y(x)\in\mathbb{Z}$, and thus $f(x) = f(g(0) + y) = g(f(0)+y)$, and both $g$ and $y$ are injective. If there is some $x\in\mathbb{Z}$ with $n = f(x) = g(x)$, then we have $f(n+k)=f(g(x)+k)=g(f(x)+k)=g(n+k)$, and thus $f = g$. In this case, any injective $f:\mathbb{Z}\rightarrow\mathbb{Z}$ solves the problem, by setting $g=f$. –  Daniel Robert-Nicoud Feb 13 '13 at 20:21

Suppose $f,g:\Bbb Z\to\Bbb Z$ with $g$ injective and $$f(g(x)+y)=g(f(x)+y)\tag{#}$$ for all $x,y\in\Bbb Z$.

Note that $$f(0)=f(g(x)-g(x))=g(f(x)-g(x))\tag{1}$$ for all $x$, so since $g$ is injective, then $f(x)-g(x)$ is constant. In particular, then $$f(x)=g(x)+c\tag{2}$$ for some $c\in\Bbb Z$. Note that it then follows that $f$ is injective.

It follows from $(1)$ and $(2)$ that $$g(c)=g(f(x)-g(x))=f(0)=g(0)+c.$$ Suppose $g(x+c)=g(x)+c$ for some $x\in\Bbb Z$. Then $$g(x+1+c)=g(f(0)-g(0)+x+1)=f(g(0)-g(0)+x+1)=f(x+1)=g(x+1)+c,$$ and similarly, $$g(x-1+c)=g(x-1)+c.$$ By $2$-directional induction on $x$, we have $$g(x+c)=g(x)+c\tag{3}$$ for all $x\in\Bbb Z$. Using $(3)$, another quick $2$-directional induction on $m$ will show that $$g(y+mc)=g(y)+mc\tag{4}$$ for all $m,y\in\Bbb Z.$

Now, if $c=0$, then we must have $f=g$ by $(2)$. Suppose $c\neq 0$. Given any $x\in\Bbb Z$, there is a unique $0\leq y<|c|$ such that $x=y+mc$ for some $m\in\Bbb Z$ (why?)--denote this $y$ by $r(x)$--so by $(4)$, we have $$g(x)=g(r(x)+mc)=g(r(x))+mc=g(r(x))+x-r(x),$$ so $$g(x)-x=g(r(x))-r(x).$$ Defining $h(x):=g(x)-x$, we have $$h(x)=h(r(x))\tag{5}$$ for all $x\in\Bbb Z$. Observing that $r(x+mc)=r(x)$ for all $x,m\in\Bbb Z$ (why?), it follows that $h$ is a periodic function $\Bbb Z\to \Bbb Z$, with $c$ a period of $h$.

The above gives us necessary conditions for $f,g$ to satisfy. We will see that they are sufficient, as well. Specifically, we prove the following:

Claim: Suppose $f,g:\Bbb Z\to\Bbb Z$ with $g$ injective. Then $f,g$ satisfy $(\#)$ if and only if one of the following holds:

(a) $f=g$, or

(b) there is some non-$0$ $c\in\Bbb Z$ and some periodic function $h:\Bbb Z\to\Bbb Z$ such that $h$ has $c$ as a period, $g(x)=h(x)+x$, and $f(x)=g(x)+c$ for all $x\in\Bbb Z$.

Proof: We saw above that if $f,g$ satisfy $(\#)$, then (a) or (b) holds. If (a) holds, then it's easily seen that $f,g$ satisfy $(\#)$, so suppose that (b) holds. Then \begin{align}f(g(x)+y) &= g(g(x)+y)+c\\ &= h(g(x)+y)+g(x)+y+c\\ &= h(g(x)+y+c)+g(x)+y+c\\ &= g(g(x)+y+c)\\ &= g(g(x)+c+y)\\ &= g(f(x)+y),\end{align} as desired. $\Box$

-

How about $f(x)=g(x)=x?$......

-