For some positive integer $n,$ Elmo writes down the equation \[x_1+x_2+\dots+x_n=x_1+x_2+\dots+x_n.\]Elmo inserts at least one $f$ to the left side of the equation and adds parentheses to create a valid functional equation. For example, if $n=3,$ Elmo could have created the equation \[f(x_1+f(f(x_2)+x_3))=x_1+x_2+x_3.\]Cookie Monster comes up with a function $f: \mathbb{Q}\to\mathbb{Q}$ which is a solution to Elmo's functional equation. (In other words, Elmo's equation is satisfied for all choices of $x_1,\dots,x_n\in\mathbb{Q})$. Is it possible that there is no integer $k$ (possibly depending on $f$) such that $f^k(x)=x$ for all $x$? Srinivas Arun
Problem
Source: ELMO 2024/3
Tags: Elmo, functional equation, algebra
YaoAOPS
21.06.2024 19:25
You can use the fact that $f$ is bijective but I am a clown. We claim that such a $k$ always exists. Take an equation. First, delete all $x_i$ that are unwrapped on both sides of the equation. Represent the LHS as a tree in a standard way such that leafs are $f(x_1 + \dots + x_k)$ and an expression $f(f^a(\dots) + f^b(\dots) + f^c(\dots))$ has $3$ childrens. Mark each edge of the tree with the number of wrapped layers there are. Define the jump of a node to its ancestor as the sum of the numbers on each edge. Define the depth of a leaf or $x_n$ as the jump to the base node. This is how many "layers" of $f$ it is wrapped under. If the gcd of all jumps is not $1$, we can WLOG replace $f$ with $f^{gcd}$ and induct down. Claim: $f$ is surjective. Proof. Suppose that the equation is $f(\dots) + f(\dots) + \dots + f(\dots) = x_1 + \dots + x_n$. Set all $x_i$ not in the first term on the LHS to constants, the result follows. $\blacksquare$ Claim: $f^{a_i}$ is linear for each depth $a_i$. Proof. Set everything else to $0$ which is possible surjectively. $\blacksquare$ Claim: For any prime $p$, there exist terms $a, x, y$ such that $x, y$ are children of $a$ in the tree of $f^a(\dots)$ such that the depth of $a$ and $x, y$ to $a$ have a gcd not divisible by $p$. Proof. If some depth in this tree isn't divisible by $p$, take that leaf as $x, y$ to finish. Else, perform a DFS to find some $a$ with a depth not divisible by $p$, which must exist as the gcd of all jumps is $1$. $\blacksquare$ Claim: The functional equation $f^a(f^b(x) + f^c(y)) = x + y + C_2$ implies that $f^{\gcd(a, b, c)}$ is linear. Proof. Note that this implies that $\gcd(a+b, a+c) \mid b-c$ is linear so we can instead solve \[ f^a(f^b(x) + f^b(y) + C_1) = x + y + C_2 \]where $b$ is redefined as $\gcd(b,c)$. We then get that $f^{a+b}$ is linear so it is equivalent to solve $f^a(x + y + C_1) = f^{-b}(x) + f^{-c}(y) + C_2$ which is just $f^a(x + y + C_1) = f^{a}(x) + f^{a}(y) + C_3$ so $f^a$ is linear. As such, this implies that $f^{\gcd(a,b)}$ is linear which finishes. $\blacksquare$ Claim: Given an equation $f^a(\dots) = x_1 + \dots + x_n + C$ such that the gcd of the jumps is $d$, we can get that $f^d$ is linear. Proof. It's equivalent to solve the case of $d = 1$. If the tree has exactly one leaf, the result is obvious. For each prime $2, 3, \dots, p, \dots$, we can use the above two claims to get $f^C_p$ such that $p \nmid C_p$ is linear. Then $f^{\gcd(C_2, C_3, C_5, \dots)} = f^{1}$ is linear. $\blacksquare$ Now, this implies that for the expression \[ f^{a_1}(x) + f^{a_2}(x) + \dots + f^{a_k}(x) = x_1 + \dots + x_n \]where $f^{a_i}(x)$ has a jump gcd of $d_i$, we have that $f^{\gcd(d_1, d_2, \dots, d_k)} = f$ is linear. Since this equation is then linear in $x_1, \dots, x_n$, coefficient matching implies that $f(x) = \pm x + b$ for some fixed choice of sign. If it's the negative sign, we get that $f(f(x)) = x$. If it's the positive sign, then we must have that $b = 0$, so $f(x) = x$.
pieater314159
21.06.2024 19:32
The answer is no. In fact, we will show that the answer is no even when $\mathbb Q$ is replaced by an arbitrary group $G$, and addition is replaced by the group operation. We will also show that such an integer $k$ can be explicitly computed from the functional equation. We'll denote the group operation by concatenation, so Elmo's example equation becomes \[f(x_1f(f(x_2)x_3))=x_1x_2x_3.\]We'll first understand the structure of the functional equations Elmo can create. Note that every character before a "$)$" is either a "$)$" or some $x_i$. For each $i$, let $r_i$ be the number of "$)$" following $x_i$. Also, let $d_i$ be the depth of $x_i$, i.e. the level of the parentheses in which $x_i$ is encased. Note that $d_n=r_n$. Letting $\mathsf A="f("$ and $\mathsf B=")"$, Elmo's functional equation is then \[\mathsf A^{d_1}x_1\mathsf B^{r_1}\mathsf A^{d_2-d_1+r_1}x_2\mathsf B^{r_2}\mathsf A^{d_3-d_2+r_2}x_3\cdots x_n\mathsf B^{d_n}=x_1\cdots x_n.\]For example, Elmo's example equation is described by \[(d_1,d_2,d_3;r_1,r_2)=(1,3,2;0,1).\]We shall let $\mathbf 1$ denote the identity element of the group. Call an expression that Elmo can write on the left side, with variables $t_1,\ldots,t_\ell$, a functional expression in the variables $t_1,\ldots,t_\ell$. Given a functional expression $\mathcal E$ described by $(d_1,d_2,\ldots,d_\ell;r_1,\ldots,r_{\ell-1})$, we define \[M(\mathcal E)=\{0,d_1,d_2,\ldots,d_\ell,r_1,\ldots,r_{\ell-1}\}.\]A functional expression $\mathcal E$ in $\ell$ variables and a function $f$ define a function $\mathcal E^f:G^\ell\to G$, given by evaluating $\mathcal E$ using the function $f$. Throughout the solution, we will let $\mathcal E_0$ denote the expression on the left side of Elmo's functional equation. We will show that, if $\mathcal E_0^f(x_1,\ldots,x_n)=x_1\cdots x_n$, then \[f^{\operatorname{lcm}(d_1,\;\gcd(d_1,\ldots,d_n)(r_1+\cdots+r_n))}(x)=x\]for all $x\in G$. The following set of functions $G\to G$ will be quite useful: \[\mathcal H=\big\{x\mapsto \varphi(x)u\mid \varphi\text{ an automorphism of }G,\ u\in G\big\}.\] Claim 1. The set $\mathcal H$ forms a group under function composition.
We must show that $\mathcal H$ is closed under function composition and function inversion. If $g,h\in\mathcal H$, then there exist automorphisms $\varphi_1$ and $\varphi_2$ of $G$ and elements $u_1,u_2\in G$ with $g(x)=\varphi_1(x)u_1$ and $h(x)=\varphi_2(x)u_2$. Then
\[(g\circ h)(x)=\varphi_1(\varphi_2(x)u_2)u_1=(\varphi_1\circ\varphi_2)(x)\big(\varphi_1(u_2)u_1\big),\]so $g\circ h\in\mathcal H$. Also, we can write
\[g^{-1}(x)=\varphi_1^{-1}\big(xu_1^{-1}\big)=\varphi^{-1}(x)\cdot\varphi^{-1}(u_1^{-1}),\]so $g^{-1}\in\mathcal H$.
Next we prove a claim about functions which satisfy slightly more general versions of Elmo's functional equations. Claim 2. Let $\mathcal E$ be a functional expression in variables $x_1,\ldots,x_\ell$ where $\ell\geq 1$, and suppose that $\mathcal E$ contains at least one copy of $f$. If \[\mathcal E^f(x_1,\ldots,x_\ell)=h(x_1\cdots x_\ell)\]for some $h\in\mathcal H$, then $f$ is bijective.
Let $x_j$ be a variable which is contained in some copy of $f$. Consider replacing each variable $x_i$ for $i\neq j$ in $\mathcal E$ with $\mathbf 1$. The result is an expression in $x_j$ which is a product of values of $f$, and only one depends on $x_i$. So, there are functions $g_1,g_2:G\to G$ and constants $c_1,c_2\in G$ for which
\[c_1g_1(f(x))c_2=c_1f(g_2(x))c_2=h(x)\]for all $x\in G$. Since $h\in \mathcal H$, $h$ is bijective. So, the first equality implies that $f$ is injective, since $h(x)$ is a function of $f(x)$. The second equality implies that $f$ is surjective, since $c_1^{-1}h(x)c_2^{-1}$ is in the image of $f$ for each $x$.
We now state and prove the key claim. Claim 3. In the setting of Claim 2, $f^{\gcd M(\mathcal E)}\in\mathcal H$.
By Claim 2, $f^m:G\to G$ is a well-defined function for all $m\in\mathbb Z$. Let $T\subset\mathbb Z$ be the set of integers $m$ for which $f^m\in\mathcal H$. By Claim 1, $T$ is a subgroup. It thus suffices to show that $M(\mathcal E)\subset T$.
We'll prove this by induction on the number of variables $\ell$. In the base case of $\ell=1$, the functional expression is $f^m(x_1)$ for some $m\geq 1$, in which case the conclusion is vacuously true. For the inductive step, we let $m$ be the largest nonnegative integer so that $\mathcal E=f^m(\mathcal E')$ for some functional expression $\mathcal E'$. Since $\mathcal E'$ contains more than one variable and is not $f(\mathcal E")$ for some $\mathcal E"$, we can write
\[\mathcal E=f^m(\mathcal E_1\mathcal E_2)\]for some functional expressions $\mathcal E_1$ and $\mathcal E_2$ depend on disjoint sets of variables $\{x_1,\ldots,x_j\}$ and $\{x_{j+1},\ldots,x_\ell\}$ where $1\leq j<\ell$. We can see that
\[m=\min(d_1-r_1,\ldots,d_{\ell-1}-r_{\ell-1})\]and that $j$ is an index so that $d_j-r_j=m$. Then
\begin{align*}
M(\mathcal E_1)&=\{0,d_1-m,d_2-m,\ldots,d_j-m,r_1,\ldots,r_{j-1}\};\\
M(\mathcal E_2)&=\{0,d_{j+1}-m,\ldots,d_\ell-m,r_{j+1},\ldots,r_{\ell-1}\}.
\end{align*}If we can show that $m\in T$ and $M(\mathcal E_1),M(\mathcal E_2)\subset T$, then we will be done. Indeed, since $T$ is a subgroup of $\mathbb Z$, we will have $d_i\in T$ for all $i$ and $r_i\in T$ for all $i\neq j$ by the above. We also have $r_j=d_j-m\in T$ since $d_j,m\in T$. So, we will have $M(\mathcal E)\subset T$, as desired. It thus remains to show
\[M(\mathcal E_1),M(\mathcal E_2),\{m\}\subset T.\]
We have
\[f^m\left(\mathcal E_1^f(x_1,\ldots,x_j)\mathcal E_2^f(x_{j+1},\ldots,x_\ell)\right)=h(x_1\cdots x_\ell).\]Since $f$ is injective, $ \mathcal E_1^f(x_1,\ldots,x_j)\mathcal E_2^f(x_{j+1},\ldots,x_\ell)$ depends only on $x_1\cdots x_\ell$. In particular, if $x_1\cdots x_j=x_1'\cdots x_j'$, then $\mathcal E_1^f(x_1,\ldots,x_j)=\mathcal E_1^f(x_1',\ldots,x_j')$. So, there exists a function $g_1:G\to G$ with
\[g_1(x_1\cdots x_j)=\mathcal E_1^f(x_1,\ldots,x_j).\]Similarly, there is a function $g_2:G\to G$ with
\[g_2(x_{j+1}\cdots x_\ell)=\mathcal E_2^f(x_{j+1},\ldots,x_\ell).\]We claim that $f^m,g_1,g_2\in\mathcal H$. From here and our previous discussion, the inductive hypothesis will imply the conclusion. We have shown
\[\tag{$\star$}f^m(g_1(a)g_2(b))=h(ab).\]Applying ($\star$) to $(t,\mathbf 1)$ and $(\mathbf 1,t)$ and using the injectivity of $f$ (Claim 2) gives
\[g_1(t)g_2(\mathbf 1)=g_1(\mathbf 1)g_2(t).\]Let $g_1(\mathbf1)=c_1$ and $g_2(\mathbf1)=c_2$, and write $\pi(x)=g_2(x)c_2^{-1}$. The above equation becomes that $c_1\pi(x)=g_1(x)$. From this, ($\star$) becomes
\[f^m\big(c_1\pi(a)\pi(b)c_2\big)=h(ab).\]Applying this at $(a,b)$ and $(ab,\mathbf 1)$ and using the injectivity of $f$ gives $\pi(a)\pi(b)=\pi(ab)\pi(\mathbf 1)$. However, $\pi(\mathbf 1)=\mathbf 1$, so $\pi$ is an automorphism of $G$. This clearly implies $g_2\in\mathcal H$; to get $g_1\in\mathcal H$ we note that
\[g_1(x)=c_1\pi(x)=\big(c_1\pi(x)c_1^{-1}\big)c_1\]and that $x\mapsto c\pi(x)c^{-1}$ is an automorphism of $G$ whenever $\pi$ is and $c\in G$. Now, let $g(x)=g_1(x)c_2$, so that $g\in\mathcal H$. We have $f^m\circ g=h$ and $g,h\in\mathcal H$, so $f^m\in\mathcal H$ as well.
Since the only automorphisms of $\mathbb Q$ as an additive group are multiplications by a nonzero constant, we have $\mathcal H=\{x\mapsto ax+b\colon a\neq 0\}$. So, by Claim 3, there exist $a,b\in\mathbb Q$ with $f^K(x)=ax+b$, where $K=\gcd M(\mathcal E_0)$. Plugging this into Elmo's functional equation gives
\[C+\sum_{i=1}^n a^{d_i/K}x_i=x_1+\cdots+x_n\]for some constant $C$. In particular, some nonzero power of $a$ is $1$, and thus $a=\pm 1$. If $a=-1$, then $f^{2K}(x)=x$ for all $x$. If $a=1$, expanding Elmo's functional equation gives that $b=0$, so $f^K(x)=x$ for all $x$.
We will have to do slightly more work to treat the more general case. Henceforth, we'll assume $K=\gcd M(\mathcal E_0)$ is $1$; this is with no loss of generality, since we can replace each occurrence of $f^K$ in the equation with the symbol $f'$ and the solutions to the original equation will be those with $f^K=f'$ for some $f'$ satisfying the new equation. If $f'$ satisfies the problem's property, then $f$ will as well. Using $K=1$, by Claim 3, we can write $f(x)=\varphi(x)u$ for some automorphism $\varphi$ of $G$ and some $u\in G$. Begin with $\mathcal E_0$, and replace each occurrence of $f^K(\cdot)$ with $\varphi(\cdot)u$. Then, repeatedly distribute using $\varphi(xy)=\varphi(x)\varphi(y)$, until no instance of $\varphi$ contains a group operation. From this procedure, we obtain \[\varphi^{d_1}(x_1)c_1\varphi^{d_2}(x_2)c_2\cdots \varphi^{d_n}(x_n)c_n=x_1\cdots x_n\tag{$\dagger$},\]where \[c_i=\varphi^{d_i-1}(u)\varphi^{d_i-2}(u)\cdots \varphi^{d_i-r_i}(u).\]By plugging in $x_1=\cdots=x_n=\mathbf 1$, we have \[c_1c_2\cdots c_n=\mathbf 1.\]Plugging in $x_2=\cdots=x_n=\mathbf 1$, we get $\varphi^{d_1}(x)=x$ for all $x$. We now make our last claim, which lets us "forget" that $G$ is abelian. Define \[D=\gcd(d_1,\ldots,d_n)\qquad R=\gcd(r_1,\ldots,r_n);\]note that $\gcd(D,R)=\gcd M(\mathcal E_0)=1$. Claim 4. Let $t=\varphi^{R-1}(u)\cdots\varphi(u)u$. Then $\varphi^D(t)=t$, and there exists an abelian subgroup $H\subset G$ which is closed under $\varphi$ and contains $t$.
For each $1\leq j\leq n$, write $b_j=c_1\cdots c_{j-1}$. Plugging into ($\dagger$) $x_i=\mathbf 1$ for all $i\leq j$ and using $c_1\cdots c_n=\mathbf 1$ gives
\[b_j\varphi^{d_j}(x_j)b_j^{-1}=x_j\]for all $x_j\in G$. This means that
\[\varphi^{d_j}(x_j)=b_j^{-1}x_jb_j.\]Let $D=\gcd(d_1,\ldots,d_n)$. Composing relations of the above form and using Bézout's lemma gives that $\varphi^D(x)=\alpha^{-1}x\alpha$ for some $\alpha\in G$ (in other words, $\varphi^D$ is an inner automorphism of $G$). We now claim that $\alpha$ and $\varphi^i(\alpha)$ commute for each $i$. Indeed,
\[\varphi^i(\alpha)=\varphi^i\left(\varphi^D(\alpha)\right)=\varphi^D\left(\varphi^i(\alpha)\right)=\alpha^{-1}\varphi^i(\alpha)\alpha.\]Since $\varphi$ is an automorphism, this implies that $\varphi^i(\alpha)$ and $\varphi^j(\alpha)$ commute for all $i$ and $j$. Let $H$ be the subgroup of $G$ generated by the center $Z(G)$ of $G$ and $\{\varphi^i(\alpha)\colon i\in\mathbb Z\}$. Since all of these generators commute, $H$ is abelian. Since $\varphi$ preserves $Z(G)$, $H$ is closed under $\varphi$. We now must show that $t\in H$. We first claim that $b_j\in H$ for each $1\leq j\leq n$. Indeed, we have
\[\alpha^{-d_j/D}x\alpha^{d_j/D}=\varphi^{d_j}(x)=b_j^{-1}xb_j\]for all $x\in G$, so $b_j\alpha^{-d_j/D}$ commutes with all $x\in G$. This means it is in $Z(G)$, so $b_j\in H$. Using the definition of $b_j$, this implies that $c_j\in H$ for all $j$ (induct on $j$). Since $H$ is closed under $\varphi$, this gives us that
\[\varphi^{r_j-d_j}(c_j)=\varphi^{r_j-1}(u)\cdots\varphi(u)u\in H.\]Let $S$ be the set of nonnegative integers $n$ for which $t_n:=\varphi^{n-1}(u)\cdots\varphi(u)u\in H$. By the above, we have $r_j\in S$ for all $j$. Also, if $n_1,n_2\in S$, then
\[t_{n_1+n_2}=\varphi^{n_1}(t_{n_2})t_{n_1}\in H,\]and similarly $t_{n_1-n_2}\in H$ whenever $n_1>n_2$. So, Bézout's lemma implies that $S$ contains $\gcd(r_1,\ldots,r_n)$. So, $t\in H$. Finally, $\varphi^D(t)=t$ since $t,\alpha\in H$ commute.
We can now, finally, prove the main result. Let $t=\varphi^{R-1}(u)\cdots\varphi(u)u$. We compute \[\mathbf 1=c_1\cdots c_n=\prod_{i=1}^n\left(\varphi^{d_i-1}(u)\cdots \varphi^{d_i-r_i}(u)\right)=\prod_{i=1}^n\varphi^{d_i-r_i}\left(\varphi^{r_i-1}(u)\cdots \varphi(u)u\right)=\prod_{i=1}^n\prod_{j=0}^{r_i/R-1}\varphi^{d_i-r_i+jR}(t).\]Let $U$ be the multiset of numbers $\{d_i-r_i+jR\}$ for $1\leq i\leq n$ and $0\leq j<r_i/R$, so that $\prod_{s\in U}\varphi^s(t)=1$ (this product is well-defined since $t$ lies in the abelian group $H$ and $H$ is closed under $\varphi$). Now, using $\varphi^D(t)=t$, \[\mathbf 1=\prod_{k=0}^{D-1}\varphi^k\left(\prod_{s\in U}\varphi^s(t)\right)=\prod_{s\in U}\prod_{k=0}^{D-1}\varphi^{k+s}(t)=\prod_{s\in U}\prod_{k'=0}^{D-1}\varphi^{k'}(t)=\left(\prod_{k=0}^{D-1}\varphi^k(t)\right)^{|U|}=\prod_{k=0}^{|U|D-1}\varphi^k(t).\]The sets $\{0,\ldots,|U|D-1\}$ and $\{0,R,\ldots,(|U|D-1)R\}$ both form $|U|$ complete residue systems modulo $D$, since $\gcd(D,R)=1$. So, we can write \[1=\varphi^{R(|U|D-1)}(t)\cdots\varphi^R(t)t.\]Using the definition of $t$, this implies \[1=\varphi^{R|U|D-1}(u)\cdots \varphi(u)u.\]Since $f^k(x)=\varphi^k(x)\varphi^{k-1}(u)\cdots\varphi(u)u$, we have \[f^{\operatorname{lcm}(R|U|D,d_1)}(x)=x\]for all $x$, as desired.