# Compositional “square roots”

Let $A$ be a set and $f\colon A\to A$ a function.

The primary and general question is: What conditions are necessary so that there exists $g$ such that for each $x$ in $A$, $g(g(x))=f(x)$?

This is a rather broad question, so a few more specific questions that result:

Is there actually some primary literature or result for this problem? Or perhaps for some subproblem such as functions on the reals?

Edit to clarify where the questions below arise from: Consider the case of $f$ bijective. For this case, Qiaochu Yuan demonstrated here that $f$ has a compositional square root exactly when the number of even (or infinite) cycles occuring in iteration of $f$ is even or infinite. For infinite cycles: $\{..., x_{-2}, x_{-1}, x_0, x_1, x_2, ...\}$ where $x_{i+1} = f(x_i)$. If this already covers $A$ and specifically, there is only one of these structures, there also is no compositional square root: Assume there was $g$ with $g(g)=f$, then $g(x_0) = x_n$ for some $0 \neq n \in \mathbb{Z}$, and then $g(x_1) = g(f(x_0)) = g(g(g(x_0))) = g(g(x_n)) = f(x_n) = x_{n+1}$. Inductively, then, $g(x_i) = x_{n+i}$ for all $i>0$, but then $g(g(x_{n}))=f(x_{n})=x_{n+1}=g(x_{n})$ and that's a contradiction. An example of such a function is $f: \mathbb{Z}\to\mathbb{Z}$, $f(x) = x+1$.

However, if A actually partitions into two components of the double-sided path form $\{..., x_{-2}, x_{-1}, x_0, x_1, x_2, ...\}$ and $\{..., y_{-2}, y_{-1}, y_0, y_1, y_2, ...\}$, then we can create $g$ by defining it through $g(x_i)=y_i$ and $g(y_i)=x_{i+1}$. An example for this is $f: \mathbb{Z}\to\mathbb{Z}$, $f(x) = x+2$ - the components here are the even and odd numbers, and we create $g$ by jumping between even and odd: $g(x)=x+1$.

There was some discussion on another forum a while ago, which brought some partial results (such as: For $f\colon \mathbb{R}\to\mathbb{R}$ bijective and strictly monotonic such a $g$ exists); it seems that any such conditions are related to a kind of "pairability" of graphs generated by iterated application of $f$ (so that $g$ can "jump" between such graphs) and thus to graph theory, specifically infinite pseudo-trees. All literature on those seems to be algorithmically motivated and thus only for the (comparatively simple) finite case; i.e. finite A. Is there any literature on infinite pseudo-trees that might be relevant?

Another aspect leads to set theoretic questions: The mentioned graphs are going to be equivalence classes under the equivalence relation $S$ on $A$ defined as $$xSy \iff\text{ There is }n \in \mathbb{N}\text{ with }f^n(x) = y\text{ or }f^n(y) = x.$$ These subsets are then, under iteration of $f$, the mentioned pseudo-trees, and the cardinalities of each preimage matter (since bijections are needed for said "pairing" of such trees). But even when acting on the reals, without CH it is not clear which cardinalities can be "paired off". And similarly, the cardinality of the height of such graphs seems relevant. Assuming CH for any relevant statement seems rather strong though, so the set-theoretic question is which other strengthenings of ZFC might be relevant here?

An example to explain the above question:

$A = B \bigcup C \bigcup \{d\} \bigcup \{e\}$, $B$ and $C$ countable with fixed enumeration and $f: A \to A$ with $f(b_i) := c_i$, $f(c_i) := d$, $f(d) := e$ and $f(e):=d$

Claim: Then $f$ does not have a compositional square root.

Assume $g$ with $g(g)=f$. For arbitrary $b \in B$ consider $g(b)$.

Cases: $g(b) = d$ or $g(b) = e$ lead to immediate contradictions due to $g(g(b_i)) = f(b_i)$ being different for different i.

Assume $g(b) = c$ for some $c \in C$. Then $g(c) = f(b) \in C$ and thus $d = f(g(c)) = g(f(c)) = g(d)$, but then $g(g(d)) = d \neq f(d)$, contradiction.

Thus, $g(b) \in B$ for all b, but this is a contradiction as well, and so no such g can exist.

But now consider two copies of our set: $A^1 = B^1 \bigcup C^1 \bigcup \{d^1\} \bigcup \{e^1\}$ and $A^2 = B^2 \bigcup C^2 \bigcup \{d^2\} \bigcup \{e^2\}$ and f defined on $A = A^1 \bigcup A^2$ as above for $A^1$ and $A^2$.

Now $g(g)=f$ exists: $g(b^1_i) = b^2_i$, $g(b^2_i) = d^1$ , $g(d^1) = d^2$, $g(d^2) = e^1$, $g(e^1) = e^2$ and $g(e^2) = d^1$.

Note that $A^1$ and $A^2$ are equivalence classes under S and that these satisfy the definition of "pairability" below.

And now, finally, here is where cardinalities matter: This construction does not work if $card(B^1) = card(C^1) \neq card(B^2) = card (C^2)$ as it assumes bijections. CH greatly simplifies which cardinalities there are to consider, but it is a rather strong assumption. The question, then, is which axioms in addition to ZFC help with simplifying the cardinalities to consider in scenarios like this, especially considering that the structures defined here can be seen as directed trees.

Lastly, while it seems that the definition of "pairable" can be made rigorous like this: two such equivalence classes $R$ and $S$ are pairable for $f$ if and only if there exists functions $h\colon S\to T$ and $j\colon T\to S$ such that for all $s \in S$, $j(h(s))=f(s)$ and for all $t \in T$, $h(j(t))=f(t)$. But then it gets a bit murky: what we need is that every equivalence class can be paired with another one (or itself), but is stating that there exists a partition of the equivalence classes into groups of pairables equivalent to the existence of $g(g)=f$? It seems that "$\Rightarrow$" holds, but the other direction is less clear. Is it possible to have a case where $g$ can jump between more than two classes that would not be reducible to a "pairable" case? Perhaps even infinitely many, in which case the cardinality issues mentioned above come into play again?

-
This question seems to me to be very hard. There was some previous discussion at math.stackexchange.com/questions/1118/… and math.stackexchange.com/questions/3633/… . – Qiaochu Yuan Mar 15 '12 at 7:21
These links and the references therein should tell you almost everything that is known about the problem: 1 2 3 4 5. – Ragib Zaman Mar 15 '12 at 7:24
The last two paragraphs make absolutely no sense to me. – Asaf Karagila Mar 15 '12 at 7:32
Yuan, Ragib, thanks for those links - while I knew some of those, there's a lot of material there. Asaf - sorry if I wasn't clear. I'll try to edit the questions to make them more clear. Austin - I'm not sure why you removed the graph theory tag; I'd really be interested in results about infinite directed 1-pseudo-trees, as they do seem rather relevant for the general problem? – Desiato Mar 15 '12 at 15:38
Asaf: I've edited in an example about bijective functions. Does that help to illustrate what the further questions refer to? – Desiato Mar 15 '12 at 17:36