Beautiful one I think . Let $R_f$ and $R_g$ be the range of $f$ and $g$ respectively and let $P(x,y)$ be the assertion. Now,if $c\in R_f$,let $f(b)=c$,then $P(x,b-g(x))\implies g(\text{......})=c$,thus $R_f\subseteq R_g$,similarly $R_g\subseteq R_f$,hence $R_f=R_g$.And since $f$ is bounded,$g$ must be bounded too.Therefore $|R_f|=|R_g|$ must be finite. If $f(x)\equiv 0$ then we clearly have $g(x)\equiv 0$ too,and it is clearly periodic.So we can assume that there exists integer $t$ such that $f(t)\neq 0$. Let $n=|R_f|=|R_g|$ and $f(t)=a\neq 0$,then for any $x_1,x_2$ such that $g(x_1)=g(x_2)$,$P(x_1,t),P(x_2,t)\implies g(a+x_1)=g(a+x_2)$ too. Now,for any $h\in\{0,1,2,...,a-1\}$,consider the function $q_h:\mathbb{Z}\rightarrow \mathbb{Z}$ define by $q_h(x)=g(h+xa)$,then by pigeonhole principle there must exists two integer $0\le i<j\le n$ such that $q_h(i)=q_h(j)$,and thus the function $q_h(x)$ must be eventually periodic. Let the least period of the sequence $q_h(i),q_h(i+1),q_h(i+2),...$ be $c_h$,now for any integer $r<i$,by pigeonhole principle there must exists $r-n\le u<v\le r$ such that $q_h(u)=q_h(v)$,then we must have $q_h(r)=q_h(r+d)=q_h(r+2d)=q_h(r+3d)=...$ where $d=v-u$,and thus for integer $N>\frac{i-r}{c_hd}$,we have $q_h(r)=q_h(r+Nc_hd)=q_h(i+[(r-i)\pmod{c_h}])$.Hence $q_h(x)$ is periodic with period $c_h$. Finally,we can clearly see that $g(x)=g(x+lcm(c_0,c_1,...,c_{a-1})a)$ for all integers $x$ and hence $g(x)$ must be periodic.

TLP.39 wrote: thus the function $q_h(x)$ must be eventually periodic. Why ? Sorry if this is silly question.I am not good at integer functions...

tenplusten wrote: TLP.39 wrote: thus the function $q_h(x)$ must be eventually periodic. Why ? Sorry if this is silly question.I am not good at integer functions... $q_h(i)=q_h(j)\implies g(h+ia)=g(h+ja)\implies g(h+(i+1)a)=g(h+(j+1)a)\implies q_h(i+1)=q_h(j+1)$, continuing these step,we got that $q_h(i+x)=q_h(j+x)$ for all nonnegative integers $x$.

Cool, Thank you ! But it seems I could not understand how you used Pigeonhole principle.Can you please explain why are they true by Pigeonhole? (I meant if not what will happen?)

tenplusten wrote: Cool, Thank you ! But it seems I could not understand how you used Pigeonhole principle.Can you please explain why are they true by Pigeonhole? (I meant if not what will happen?) All $n+1$ numbers in $\{q_h(0),q_h(1),...,q_h(n)\}$ must be in the range of $g$,but since there are $n$ different values in $R_g$,there must exists at least $2$ of them which are equal.

Here's my solution which is quite similar to @TLP.39's solution. Let $F=f(\mathbb Z)$ and $G=g(\mathbb Z)$. Since $f$ is bounded, $F$ is finite. Plug in $(x,y) = (x-f(0),0)$ to get $g(x) = f\big(g(x-f(0))\big) \in F$ for all $x\in\mathbb Z$, so $G\subseteq F$. Similarly, $F\subseteq G$, so $F=G$. Now let $d = \gcd F$. Fix a $k\in\{0,1,2,\ldots,d-1\}$. Consider the set $f(d\mathbb Z + k)$, which is finite. Hence for some $t,t'$, $f(dt+k)=f(dt'+k)$. Plug in $y=dt+k$ and $dt'+k$, and compare to get $$f(g(x)+dt+k)=f(g(x)+dt'+k)$$so $f(dy+k)=f(dy+d(t'-t)+k)$ for all $dy$ of the form $dt+\sum g(x)$. If $F=G$ contain both positive and negative values then the above implies $f(d\mathbb Z+k)$ is periodic for any $k$, so by taking the $\mathrm{lcm}$, $f$ is periodic as well. Similarly $g$ is also periodic and we're done. We're left with the case where $F=G$ contain only nonnegative or nonpositive integers. Let's assume it contains only nonnegative integers since the proof works the same. If $F=G=\{0\}$ both $f$ and $g$ are identically zero and obviously periodic. Else, any sufficiently large $dy$ (say $y\geqslant N$) can be written as $\sum g(x)$. Hence $f(d\mathbb Z+k)$ is periodic for sufficiently large arguments (say for all $dy+k$ with $y\geqslant M$) with minimal period $dp\mid d(t-t')$. Now, for each $y_0 < M$ and $T\in\mathbb Z_{>0}$, by Pigeonhole there must be some $\ell < \ell' < y_0 - N$ such that $pT\mid \ell-\ell'$ and $f(d\ell +k) = f(d\ell'+k)$. Since $d(y_0-\ell)$ can be written as $\sum g(x)$, $$f(dy_0+k) = f(d\ell +d(y_0-\ell) + k) $$$$= f(d\ell' + d(y_0-\ell) + k) = f(d(y_0+ pTs) + k)$$for some $s>0$. Similarly we have $f(d(y_0+p) + k) = f(d(y_0 + p + pTs')+k)$ for some $s'>0$. Now choose $T$ big enough so that $y_0+ pTs$ and $y_0 + p + pTs'$ are both more than $M$ to get $$f(dy_0+k) = f(d(y_0+p)+k),$$therefore $f(d\mathbb Z+k)$ is periodic with period $dp$. By taking the $\mathrm{lcm}$ of all the periods for $k=0,1,\ldots,d-1$, it follows that $f$ is periodic. Similarly, this also holds for $g$ as well, so we're done. $\blacksquare$

It's not hard to show that $R_f=R_g$ where both denote the range of $f$ and $g$, respectively. So, both range of $f$ and $g$ are bounded. Also, if $f\equiv 0$, we easily get $g\equiv 0$, done. WLOG that there's $\ell\in \mathbb{Z}$ that $f(l)> 0$ (actually we can't write WLOG but I'm too lazy to do the negative case lol; smn says it's the same). By Pigeonhole, For fixed positive integer $N>\max_{n\in \mathbb{Z}} \{ f(n)\}$, there exists positive integer $a$ and $L$ that $g(a+i)=g(a+i+L)$ for all $i\in [N]$. Let $S$ denote the set of positive integer $n$ that $g(n)=g(n+L)$. We've $a+1,a+2,...,a+N\in S$. We get that $g(f(y)+a+i)=g(f(y)+a+i+L)$. So $a+1,a+2,...,a+N+f(\ell )\in S$. We can inductively see that $a+1,a+2,...,a+N+sf(\ell )\in S$ for all $s\in \mathbb{Z}^+$. Hence $b\in S$ for all integer $b>a$. This is equivalent to $g(n)=g(n+L)$ for all integer $n>a$. Now for any integers $x,y,z$, we have $f(g(x)+y)+z=g(f(y)+x)+z$, so $f(f(g(x)+y)+z)=f(g(f(y)+x)+z)$. In our latest equation, we've $RHS=g(f(z)+f(y)+x)$. Hence, swapping $y,z$, we get $f(f(g(x)+y)+z)=f(f(g(x)+z)+y)$. Also, all equations are symmetric when swapping $f,g$, so $g(g(f(x)+y)+z)=g(g(f(x)+z)+y)$ for all $x,y,z\in \mathbb{Z}$. Since $R_f=R_g$, we can replace $f(x)$ by $g(x)$. So, we've $g(g(g(x)+y)+z)=g(g(g(x)+z)+y)$ for all $x,y,z\in \mathbb{Z}$. Note that it's enough to show that $g(a)=g(a+L)$ (please read til the end before questioning why). Since $g(g(g(x)+y)+z)=g(g(g(x)+z)+y)$, we get $g(g(g(x)+y)+z+L)=g(g(g(x)+z+L)+y)$ for all $x,y,z\in \mathbb{Z}$. So, $g(a+L)=g(g\Big( a-g(g(x)+y)+g(x)+L\Big) +y)$ for all $x,y\in \mathbb{Z}$. If $g$ is not constant, which in that case will finish the problem, there exists $p,q\in \mathbb{Z}$ that $g(p)<g(q)$. So, $a-g(p)+g(q)>a$, this gives $g\Big( a-g(p)+g(q)+L\Big) =g\Big( a-g(p)+g(q)\Big)$. So, $g(g\Big( a-g(g(x)+y)+g(x)+L\Big) +y)=g(g\Big( a-g(p)+g(q)\Big) +p-g(q))=g(g(g(q)+(p-g(q)))+(a-g(p)))=g(a)$. Note that the second last equality, we substitute $x$ by $q$, $y$ by $p-g(q)$ and $z$ by $a-g(p)$ in $g(g(g(x)+y)+z)=g(g(g(x)+z)+y)$. Finally, we get $g(a)=g(a+L)$, this finish the problem cause we can extend the periodic interval backward. Note that this finish the problem because we didn't use any relation between $L$ and $a$, so we can extend backward without any problem.

It is clear that $f(\mathbb{Z}) = g(\mathbb{Z})$, so denote $f(\mathbb{Z}) = g(\mathbb{Z}) = \{a_1, \dots, a_n\}$. Let $M$ be a positive integer such that $|a_i - a_j| < M$ for all $i, j$. Fix $x$ and let $y$ vary. The LHS of the functional equation takes on the values $a_1, \dots, a_n$, and the RHS takes on $g(x + a_1), \dots, g(x + a_n)$. It follows that $\{g(x + a_1), \dots, g(x + a_n)\} = \{a_1, \dots, a_n\}$ for any $x$; in particular $g(x + a_1), \dots, g(x + a_n)$ are mutually distinct. Thus given $g(x), \dots, g(x + M - 1)$, the values of $g(x + M)$ and $g(x - 1)$ are uniquely determined (*). Let $a$ be a fixed integer. Then there exist $d_1, d_2 \in [1, n^M + 1]$ with $d_1 < d_2$ and $g(a + d_1+ t) = g(a + d_2 + t)$ for $t = 0, \dots, M - 1$. Let $d = d_2 - d_1$: then an easy forward induction implies $g(x) = g(x + d)$ for all $x \ge a + n^M$. Using (*) and backward induction, $g$ is periodic with period $d$.

By fixing $y$ and varying $x$, we see that the image of $g$ is contained in the image of $f$. Similarly, the image of $f$ is contained in the image of $g$. So let us denote by $S$ the common image of the two functions. We color each $x \in {\mathbb Z}$ one of $|S|$ colors according to the value of $g(x)$; our aim is to show this coloring is periodic. Fix an element $N \in S$ and assume $N > 0$ (since the case $N < 0$ is analogous, and if $S = \{0\}$ there is nothing to prove). We will only need to remember the following combinatorial information: Claim: If $p$ and $q$ are the same color, then $p+N$ and $q+N$ are the same color. Proof. We have $f(g(x)+p) = g(f(p)+x) = g(f(q)+x) = f(g(x)+q)$ and $g(x)$ may take any value in $S$. $\blacksquare$ Indeed, it's enough to show the coloring is periodic on $N{\mathbb Z}+i$, for $i=0,1,\dots,N$; since then the entire coloring will have period at most $N \cdot \operatorname{lcm}(P_0, \dots, P_{n-1})$ where $P_i$ was the period on $N{\mathbb Z}+i$. It is enough to show this for the $i=0$ case by shifting. Suppose $aN$ and $bN$ are the same color. Then $(a+1)N$ and $(b+1)N$ are the same color, and so on; an easy induction now shows the coloring is periodic mod $b-a$. Since there are finitely many colors, there is some color whose elements are arbitrarily negative and that is enough to imply the result. Remark: Let $t \colon {\mathbb Z} \to {\mathbb Z}$ be any $2017$-periodic function such that $t(n) \equiv n \pmod{2017}$. Then $f(x) = t(x+13)$ and $g(x) = t(x+37)$ is an example of a solution.

v_Enhance wrote: We color each $x \in {\mathbb Z}$ one of $|S|$ colors according to the value of $g(x)$; our aim is to show this coloring is periodic. Fix an element $N \in S$ and assume $N > 0$ (since the case $N < 0$ is analogous, and if $S = \{0\}$ there is nothing to prove). We will only need to remember the following combinatorial information: Fantastic Idea Dear v_Enhance , but how can you ensure that we can color an infinite set , Denombrability ? thank you .

oty wrote: but how can you ensure that we can color an infinite set , Denombrability ? thank you . Sorry, I'm not sure I understand the question. Formally, a coloring of a set $\mathcal A$ with a choice of colors $C$ is nothing more than a function $\mathcal A \to C$. In this case, we are coloring $\mathbb Z$ with $S$ according to the function $g \colon \mathbb Z \to S$.

It is easy to show $\text{Im}f = \text{Im}g$. Denote $\text{ker}_m(f)=\text{ker}(f(x)-m)$. Let $k\in \text{Im}g$. Setting $x \in \text{ker}_k(g)$ we get that $$f(y)+x \in \text{ker}_{f(k+y)}(g).$$Since $\text{Im}f = \text{Im}g$ there exists $y=y_k$ such that $f(k+y_k)=k$. Then $f(y_k) + x\in \text{ker}_k(g)$ so $\text{ker}_k(g)$ is the union of some number of infinite arithmetic sequences with common difference $f(y_k)$ (which is periodic with period $f(y_k)$), for any $k$. It follows that $g$ is periodic with period $\underset{k\in \text{Im}g}{\text{lcm}}f(y_k)$. EDIT: ignore, this solution is wrong

Take the least nonnegative integer $a$ such that $f(a)=d \ne 0$. Let $h(x)=f(x+a)$. Then it's easy to see that $f,g,h$ all have the same image set $S$. Now, by applying $P(x,a)$ we have $g(x+nd)=h^n(d)$. So starting from any $d$ consecutive integers, all subsequent integers have $g$ determined. Since $f$ is bounded, the image set is finite. Then the graph of $h$ over $S$ will have exactly one cycle in each connected component where you must land after finitely many iterations of $h$. So for a given $x$, the sequence $g(x+nd)$ as $n$ increases will eventually be periodic. Taking the lcm of these periods, we get a period for all of $g$. This period arises after finitely many terms, so by starting with arbitrarily low integers we can say that all of $g$ is periodic. (QED) Not sure if something is missing, because this feels pretty simple compared to the routes in most of the above solutions. That might just be me glossing over the details though. Would love if anyone could point out any mistakes in my proof. I was led by someone describing the problem as "combinatorial" (no doubt after seeing v_enhance's proof) to experiment, detailing $f$ and trying to construct $g$. I eventually found that g is determined by a single band, and it becomes periodic due to functional iteration. You can actually get away without shifting to $h$ with an even simpler proof as long as $f(0) \ne 0$

As far as I am concerned, some of the final arguments presented above are wrong, namely that "starting with arbitrary low integers we get that g is periodic". I am going to show that this is not the case. Firstly, be aware that if we construct arbitrary long contiguous gaps of $0$'s in a sequence in which all the values are $0$'s and $1$'s, that sequence cannot have a period formed by $1$'s. This is obvious because as the period is finite, we can find a contiguous gap of $0$'s of length strictly greater than the period and we are done. So the example is this: $$(a_n)_{n\in\mathbb Z}$$$$a_n=1 \forall n \ge 0$$$$a_{-(2^1+...+2^k)}=1,\ \forall k\ge 1$$$$a_n=0 \ \ \ \text{ for any other integer index} $$ There are arbitrarily low integers from which we can start a periodic sequence of period $2^k$, for any $k$...

dragonx111 wrote: As far as I am concerned, some of the final arguments presented above are wrong, namely that "starting with arbitrary low integers we get that g is periodic". I am going to show that this is not the case. $$(a_n)_{n\in\mathbb Z}$$$$a_n=1 \forall n \ge 0$$$$a_{-(2^1+...+2^k)}=1,\ \forall k\ge 1$$$$a_n=0 \ \ \ \text{ for any other integer index} $$ ... Well, there wasn't any complete proof of those final parts, there were just words, so something was rotten in the state of Denmark. I do not understand the counterexample: you cannot have a periodic sequence which is eventually constant but not constant. In my solution in #11, the claim amounts to the following: let $(a_n)_{n \in \mathbb Z}$ be a sequence of colors. Assume for arbitrarily large $D > 0$, the sequence $(a_n)_{n \ge -D}$ is periodic (with the length of the period $p = p(D)$ possibly depending on $D$). Then $(a_n)_n$ is itself periodic. And indeed, let $T$ be the minimal period of $(a_n)_{n \ge 0}$. As for any $-D < n < 0$, we have \[ a_{n} = a_{n + rp(D)} = a_{n + T + rp(D)} = a_{n+T} \]for $r$ large enough (such that $n + r p(D) \ge 0$). So $T$ is a universal period, the end. Is there a mistake?

I am sorry for my previous message, I just did not see how that worked. No, there is no mistake, you are right, v_Enhance.

Combinatorics in disguise, but why do combinatorics when you can do algebra? My solution: Allow $x$ to vary. We get the fact that $g$ is bounded and its range is a subset of that of $f$. Doing it the other way round gives range of $f$ is a subset of $g$. So ranges of $f,g$ are identical. Suppose $g(x)=r$. Then $g(f(y)+x)=f(r+y)$. Since the images of $f,g$ are identical, there exists a number $\alpha_r$ with $f(r + \alpha_r) = r$. So $g(f(\alpha_r)+x) = r$, which means that, by induction in both directions, $g(x+nf(\alpha_r))=r$. So $g$ is periodic with period as the lcm of $f(\alpha_r)$s.

mofumofu wrote: Functions $f,g:\mathbb{Z}\to\mathbb{Z}$ satisfy $$f(g(x)+y)=g(f(y)+x)$$for any integers $x,y$. If $f$ is bounded, prove that $g$ is periodic. (Solution found together with Ankoganit, SimplyComplex, p_square, AmitKVS) Special thanks to Shubham Saha for lending me his laptop Observe that $R(f)=R(g)$. Note that by symmetry, whatever we obtain for $f$ will apply for $g$ as well. Let $R(f) \overset{\text{def}}{:=} \{p_1, \dots, p_s\}$ and suppose $f(q_i)=p_i$ for all $1 \le i \le s$. Now we prove the following lemma. Lemma. For all $x \in \mathbb{Z}$ if $f(x+p_i)=f(x+p_j)$ then $i=j$. (Proof) Replace $x$ by $f(x)$ and swap $x,y$; we obtain $$f(g(f(x))+y)=g(f(y)+f(x))=f(g(f(y))+x).$$Now fix $x \in \mathbb{Z}$ and put $y=q_i-g(f(x))$. Thus, $f(x+g(f(y)))=p_i$ for all $1\le i \le s$. Note that $f$ maps each $x+p_j$ to some $p_i$; since the image set has the same size, we conclude that $f(x+p_i)$ permutes $R(f)$ as $i$ varies. $\blacksquare$ Suppose $f(a)=f(b)$. Then $f(g(x)+b)=g(f(b)+x)=g(f(a)+x)=f(g(x)+a)$ proving that $f(x+a)=f(x+b)$ for all $x\in R(f)$. Now observe that $$f(g(x)+(a-g(x)))=f(g(x)+(b-g(x))) \implies g(f(a-g(x))+x)=g(f(b-g(x))+x)$$so by the lemma, we have $f(a-g(x))=f(b-g(x))$. Therefore, $f(-x+a)=f(-x+b)$ for all $x \in R(f)$. Now let $d=\gcd\{p_1, \dots, p_s\}$. Then $f(n+a)=f(n+b)$ for all $n \equiv 0 \pmod{d}$. Indeed note that $f(a+z)=f(b+z)$ where $z$ is obtained by taking linear combinations of $R(f)$. For any residue class $r \pmod{d}$ consider the chain $\dots \rightarrow r-2d \rightarrow r-d \rightarrow r \rightarrow r+d \rightarrow r+2d \rightarrow \dots$ and note that we can find $f(r+di)=f(r+dj)$ for $i \ne j$. Therefore, $f$ is periodic on $d\mathbb{Z}+r$ with period $\ell_r$ for all $1 \le r \le d$. Thus, $f$ is periodic with period $\ell=\operatorname{lcm}(\ell_1, \dots, \ell_d)$. $\blacksquare$

Lemma. Let $G$ be a balanced directed multi-graph on $n$ vertices. Suppose that $\text{deg}(v)=\text{deg}(u) \ge n$ for any $u,v \in G$. Then there exists a cycle starting and ending at every $v \in G$. WLOG $G$ is connected. Suppose that the hypothesis is not true, then there exists a vertex $v_0\in G$ for which $G=A\cup B$ and $A\cap B= \emptyset$ such that you can reach $v_0$ from any vertex in $B$ and any vertex in $A$ from $v_0$. Note that this partition implies that $\sum_{v\in A} \text{deg}^{-}(v)=\sum_{v\in A} \text{deg}^{+}(v)$, but $$\sum_{v\in A} \text{deg}^{-}(v)=\sum_{v\in A} \text{deg}^{+}(v)+\text{deg}^{+}(v_0)>\sum_{v\in A} \text{deg}^{+}(v)$$Thus, we reach a contradiction and the Lemma is proven. Back to the problem, note that $f(\mathbb{Z})=g(\mathbb{Z})=\{d_1,d_2, \cdots d_m\}$ for some $d_j$ and let $f(S_i)=g(T_i)=d_i$ for $1\le i \le m$, where $\cup S_i$ and $\cup T_i$ are partitions of $\mathbb{Z}$. Suppose that $x_i, x_j \in T_m$, then the following relation holds $$g(x_i+f(y))=f(y+g(x_i))=f(y+g(x_j))=g(x_j+f(y))$$Equivalently, we have that $g(x_i+d_l)=g(x_j+d_l)$ for any $x_i, x_j \in T_k$, where $1\le l,k \le m$. Note that this implies that for any $1\le i,l \le m$ there exists an $j$ such that $T_i+d_l \equiv T_j$. Let $G$ be a directed multi-graph on $n$ vertices and draw an arrow from $v_i$ to $v_j$ if there exists an $l$ such that $T_i+d_l \equiv T_j$. This graph satisfies the conditions of the Lemma, thus for any $v_0$ there exists a cycle $v_0 \rightarrow v_{l_1} \rightarrow \cdots \rightarrow v_{l_k}\rightarrow v_0$ for some $k$, which means that $T_i+d_{c_1}+d_{c_2}+\cdots +d_{c_k}\equiv T_i$ for some $c_i$'s, implying that $g(x+D)=g(x)$, where $D$ is the product of all sums of $d_i$'s

First, note that, by fixing $x$ and varying $y$, $g$ can achieve all values in the range of $f$, and by fixing $y$ and varying $x$, we see the opposite. So, $f$ and $g$ have identical ranges. Note that if this range only contains $0$, then we are obviously done. Otherwise, call it $\{r_1,r_2,\ldots,r_k\}$ with $r_1\neq 0$. For each $r_i$, denote $A_i$ as the set of all $x$ such that $g(x)=r_i$. Obviously, $A_1\cup A_2\cup\ldots\cup A_k=\mathbb{Z}$. Suppose we fix $y$ such that $y\in A_1$, and vary $x$. Note that the RHS varies over all numbers in the range, but the LHS's argument can only take on $k$ values. So, each unique value of $g(x)$ corresponds to a unique value of $f$. Now, if we vary $x$ over $A_i-r_1$ for some $i$, note that the RHS is fixed, and as the LHS corresponds to a unique value of $g(x)$, we must have that $A_i-r_1\subseteq A_j$ for some $j$. If we cycle through all $i$, we can produce $k$ such pairs of the form $(A_i,A_j)$. Note that, when $x\in A_i-r_1$, we also have $x\in A_j$. However, as $i$ varies, $x$ goes over all the integers, so every $A_j$ appears on the right of an ordered pair at some point. So, these pairs essentially form a bijection. So, we essentially have that $A_i-r_1\subseteq A_{\sigma(i)}$ where $\sigma$ is some permutation $[k]\to [k]$. However, the union of all the $A_i-r_1$ is the same as the union of all the $A_i$, namely exactly the integers. In order for this to occur, then, all the $\subseteq$s should actually be equality. So, we have $A_i-r_1=A_{\sigma(i)}$. Now, consider the graph on $k$ vertices where $i,j$ are connected by an edge $i\to j$ iff $A_i-r_1=A_j$. As $\sigma$ is a permtuation, the graph formed consists of numerous directed cycles. If we consider an arbitrary $A_i$, in a directed cycle of length $d$, then we have that $A_i-dr_1\subset A_i$, from which it is not hard to show that $A_i$ is a cyclic shift of itself - namely it is periodic. Repeating for all the $A_i$, we get that all $A$s are periodic, implying $g$ is periodic, as desired.

Let $P(x,y)$ denote the assertion of \[ f(g(x) + y) = g(f(y) + x) \] Let $\text{Im}_f$ denote the set of images of function $f$. First, notice that $\text{Im}_f \subseteq \text{Im}_g$ by fixing $x$ and vary $y$. Similarly, by fixing $y$ and vary $x$, we get that $\text{Im}_g = \text{Im}_f$. Consider a value $a$ such that $g(a) = r$, $r \in \text{Im}_g$. Therefore, we have \[ P(a, a - f(a)) : f(a - f(a) + r) = g(a) = r \]Therefore, $P(a - f(a), a)$ gives us \[ g(f(a - f(a)) + a) = f(g(a) + a - f(a)) = f(a - f(a) + r) = r \]Hence, we get that if $g(a) = r$, then $g(a + f(a - f(a)) ) = r$ as well. Notice that for any $y$ such that $g(y) = r$, we have \[ g(f(a - f(a)) + y) = f(g(y) + a - f(a)) = f(a - f(a) + r) = r \]Hence, we must have \[ g(a + nf(a - f(a)) ) = r \]for any $n \in \mathbb{N}$. Since $\text{Im}_f$ is finite, then we could just take the period as $\text{LCM}_{a \in \text{Im}_f} f( a - f(a))$ Therefore, $g$ is periodic.

We know that $f(\mathbb{Z})=g(\mathbb{Z})$. If this set is $\{0\}$, we are done. So we can find $a$ such that $f(a)\ne0$, and assume $f(a)>0$. Let $|f(\mathbb{Z})|=n, T=lcm(1, 2, \cdots, n)$. First, if $g(x)=g(y)$, $g(x+f(a))=f(g(x)+a)=f(g(y)+a)=g(y+f(a))\cdots(*)$ For an arbitary integer $x$, by pigeanhole principle in $g(x-if(a))(1\leq i\leq n+1),$ We can find $1\leq i<j\leq n+1$ such that $g(x-if(a))=g(x-jf(a))$. And by $(*)$, $g(x)=g(x+(j-i)f(a))=\cdots=g(x+k(j-i)f(a))$. Since $1\leq j-i\leq n$, $j-i|T$. Hence $g(x)=g(x+\frac{T}{j-i}(j-i)f(a))=g(x+Tf(a))$ $\quad\blacksquare$

Solved with nukelauncher. Evidently \(f(\mathbb Z)=g(\mathbb Z)\); i.e.\ \(f\) and \(g\) have the same range. Let this range be the finite set \(S\). Now fix \(x\) and vary \(y\) to obtain \[g(x+S)=f(\mathbb Z)=S,\]so \(s\mapsto g(x+s)\) is a bijection \(S\to S\). Let \(S=\{s_1<\cdots<s_n\}\) and let \(r=s_n-s_1\). Clearly \(g(x-s_n+s_1)\), \ldots, \(g(x-s_n+s_{n-1})\) uniquely determine \(g(x)\), so \(g(x-r)\), \ldots, \(g(x-1)\) uniquely determine \(g(x)\). There are finitely many possible tuples \((g(x-r),\ldots,g(x-1))\), so by Pigeonhole, \(g\) is periodic.

oops long. Let $f(\mathbb Z) = M$. Note that by varying $x,y$, we also have $g(\mathbb Z) = M$. Color $\mathbb Z$ as follows: for each $t\in\mathbb Z$, color it $g(t)$. If $M=\{0\}$, we are immediately done because then $g$ has period $1$. Now, let $n\in M$ be nonzero. Then for $x_1, x_2$ with the same color, plugging them into the functional equation in place of $x$ implies that $x_1+n$ and $x_2+n$ are also the same color. Now, for each residue $t$ in $\mathbb Z/n\mathbb Z$, consider the sequence \[S_t = \dots, -2n+t, -n+t, t, n+t, 2n+t, \dots\]of all integers congruent to $t$ mod $n$. By the pigeonhole principle, two elements of $S_t$ have the same value after applying $g$. WLOG we have $g(t) = g(kn+t)$ for $k>0$. We claim that $g(-kn+t)$ (and thus $g(-akn+t)$ for integer $a>0$ by the same argument) is equal to these two. By the condition from before, we see $g(t) = g(kn+t) = g(2kn+t) = g(3kn+t) = \cdots$. Suppose $g(-kn+t)\ne g(t)$ for proof by contradiction. We must have $g(-2kn+t)\ne g(-kn+t)$ because $g(-kn+t)\ne g(t)$ and $g(-2kn+t)\ne g(t)$ because $g(-kn+t)\ne g(kn+t)$. Analogously, $g(-3kn+t)$ cannot be equal to $g(akn+t)$ for $a\ge -2$ by the same argument. But iterating this way yields a contradiction, because $g(akn+t)$ can only assume a finite number of values. So we have a contradiction and so $g(akn+t) = g(t)$ for $a\in\mathbb Z$. Shifting by $n$ as many times as is necessary, we see that $g(kn + qn + t) = g(qn + t)$ for all $q$. So doing this for all values of $t$ means we can partition $\mathbb Z$ into infinite arithmetic sequences with arbitrarily small (that is, less than say $-10^{100}$) and arbitrarily large elements that have the same value under $g$. Taking the least common multiple of the lengths of these arithmetic progressions, we have a period.

It is easy to see that $f,g$ have same finite range. If $g(n)=m$ then, there exists $M$ such that $f(m+M)=m.$ And so $g(n+f(M))=m$ and by iterating, $g(n+kf(M))=m.$ So $g$ has period $\text{lcm}(f(M)),$ as desired.

Let $P(x,y)$ denote the assertion that$$f(g(x)+y)=g(f(y)+x)$$Notice $f$ and $g$ have the same image. Since $f$ is bounded, this image is finite. Let this common image be denoted as $S$. By fixing $x$ and varying $y$, we have $g(x+S) = S$, so the mapping $k\to g(x+k)$ for $k\in S$ is a bijection $S\to S$. If $S = \{0\}$, the result is obvious, now assume otherwise. If $g(a)= g(b)$, then $P(a,x)$ and $P(b,x)$ give that $g(a+k) = g(b+k)$ for any $k\in S$. We can iterate this and get $g(a + nk) = g(b + nk)$ for any $n\ge 0$, so $g(i) = g(i + (b-a))$ for all $i\equiv a\pmod k$ and $i\ge a$ (if $k> 0$). Fix an $m\in S$. WLOG that $m> 0$ (we may proceed similarly if $m<0$). Let $N$ be a sufficiently large positive integer greater than $(m\cdot |S|)^{4434}$. Claim: For each residue $r\pmod m$, there exists an arbitrarily small integer $r\pmod m$ for which $g(r) = g(s)$ for some $s$ satisfying $0<s-r< N$. Proof: Consider $|S| + 1$ sufficiently small integers $r\pmod m$ such that no two of them are more than a distance of $m\cdot |S|$ apart (they form an arithmetic sequence with common difference $m$). By PHP, two of them have the same $g$ value and we may choose $s$ to be the larger one. $\square$ Claim: $g(x) = g(x + \mathrm{lcm}(1,2,\ldots, N))$ for all integers $x$ (which proves $g$ is periodic). Proof: By our earlier claim, choose $r$ and $s$ so that $r\equiv x\pmod m$, $r<x$, $g(r) = g(s)$, $m\mid s-r$, and $0<s-r<N$. We get that $g(x) = g(x+(s-r))$. We can now repeat this because $m\mid s-r$ and get \[g(x) = g(x + (s-r)) = g((x + s-r) + (s-r)) = g(x +n(s-r))\]for any positive integer $n$, which means $g(x) = g(x + \mathrm{lcm}(1,2,\ldots, N))$. $\square$

I thought that surely this would not be the actual solution but I guess I was wrong Let $P(x,y)$ denote the assertion. By fixing $y$ and varying $x$, every number in the range of $g$ is also in the range of $f$, and by fixing $x$ and varying $y$, every number in the range of $f$ is also in the range of $g$, hence the ranges are the same set; call it $S$. If $S=\{0\}$, then we are clearly done, so suppose otherwise. If we have $g(a)=g(b)$ for some $a,b$, then by comparing $P(a,y)$ and $P(b,y)$ where $y$ is free to vary, we find that $g(a+s)=g(b+s)$, where $s \in S$ is arbitrary. By Bezout's, we can express every multiple of $\gcd(S):=d$ as some integer linear combination of the elements of $S$. If $S$ has both negative and positive elements, it is clear that we can then convert any integer linear combination into a nonnegative integer combination. Then, by finding some distinct $a,b \in d\mathbb{Z}+i$ such that $g(a)=g(b)$ for each $1 \leq i \leq d$ (independently), we immediately get that $g$ is periodic with period (not necessarily minimal) equal to the lcm of the $|a-b|$. Otherwise, WLOG $S$ has no negative elements. We still have the fact that every sufficiently large (only depending on $S$) multiple of $d$ can be written as a nonnegative linear combination of the elements of $S$. But we can actually repeat the argument from before, this time getting that $g$ is eventually periodic. The onset of this eventual periodicity on $d\mathbb{Z}+i$ occurs at most a fixed distance past $\min\{a,b\}$, where $(a,b)$ is the pair that we found with $g(a)=g(b)$. However, we can clearly find arbitrarily small pairs $(a,b)$ (i.e. for any $N$ there exists some pair with $a,b<N$), so it turns out that it is still true that $g$ is periodic over $d\mathbb{Z}+i$, hence it is periodic in general. $\blacksquare$

It's not hard to see that $f(\mathbb{Z}) = g(\mathbb{Z})$, thus $g(\mathbb{Z})$ is finite. Now consider the following claim: Claim: If $g(x) = g(x + c)$ for some $c$, then $g(x + f(y)) = g(x + f(y) + c)$ for all $y \in \mathbb{Z}$. Proof. $g(f(y) + x + c) = f(g(x + c) + y) = f(g(x) + y) = g(f(y) + x)$, so we're done. $\blacksquare$ Now let $T = f(y)$ and for all $0 \le i \le T-1$, consider the set $g(T\mathbb{Z} + i)$. By pigeonhole principle, there exist $m ,n$ such that $g(Tn + i) = g(Tm + i)$. Moreover $|m-n| \le |g(\mathbb{Z}) + 1|$. Therefore $g(T\mathbb{Z} + i)$ is periodic and let the period be $p_i$. Then $g$ has period $p_0p_1 \cdots p_{T-1}$, so we're done. $\blacksquare$

$ $

Attachments:

(Sorry for bad English and TeX skills.) It is obvious that $f(\mathbb{Z})=g(\mathbb{Z})$. Indeed, for $s\in f(\mathbb{Z})$ let $f(t)=s$ and $x,y\in\mathbb{Z}$ such that $y=t-g(x)$, then $f(g(x)+y)=g(f(y)+x)=s$, indicating that $s\in g(\mathbb{Z})$. Due to the arbitrariness of $s$ we have $f(mathbb{Z})\subseteq g(\mathbb{Z})$ and similarly $g(\mathbb{Z})\subseteq f(\mathbb{Z})$, hence $f(\mathbb({Z}))=g(\mathbb{Z})$. Now, if $f(\mathbb{Z})=\{0\}$, then $\forall x\in\mathbb{Z}, g(x)=0$, and $g$ is periodic. If $\f(\mathbb{Z})\ne\{0\}$ (I don't know how to correct it in TeX) we do a case analysis: \textit{a)}~If $f(0)\ne 0$ let $y=0$ in the original equation, we have $g(x+f(0))=f(g(x))$. Let $f^{0}(x)=x$ for all integers $x$ and let $f^{m+1}:=f\circ f^{m}$ for all natural numbers $m$, then $f(\mathbb{Z})\supseteq f^2(\mathbb{Z})\supseteq f^3(\mathbb{Z})\supseteq\dots$ Also, $g(x+n\cdot f(0))=f^{n}(g(x))$ for all integers $x$. Since $f$ is bounded, $f(\mathbb{Z})$ is a finite yet nonempty subset of $\mathbb{Z}$. Hence there is a positive integer $N$, such that $f^{N}(\mathbb{Z})=f^{N+1}(\mathbb{Z})$. $\forall k>N, f^{k}(\mathbb{Z})=f^{N}(\mathbb{Z})$ (a simple induction can show it). Let $S:=f^{N}(\mathbb{Z})$, then $f$ acts as a permutation on the finite set $S$, and hence there is an integer $m$, such that $\forall s\in S, f^{N+m}(s)=f^{m}(f^{N}(s))=f^{N}(s)$. Then $g(x+(N+m)\cdot f(0))=f^{N+m}(x)=f^{N}(x)=g(x+N\cdot f(0))$. Hence $g$ is periodic and one of its period is $T=m\cdot \left| f(0)\right|$. \textit{b)}~If $f(0)=0$, since $f(\mathbb{Z})\ne\{0\}$ we can take $c\in\mathbb{Z}$ such that $f(c)\ne 0$. Let $h(x)=f(x+c)$, then $f(x)=h(x-c)$. At this time, $h(0)\ne 0$, $h$ is bounded and $h(g(x)+y-c)=g(h(y-c)+x)$. From \textit{a)} we know that $g$ is periodic. Therefore $g$ is always periodic.