13
$\begingroup$

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?

  • 4
    This question seems to me to be very hard. There was some previous discussion at http://math.stackexchange.com/questions/1118/characterising-functions-f-that-can-be-written-as-f-g-circ-g/1122#1122 and http://math.stackexchange.com/questions/3633/square-root-of-a-function-in-the-sense-of-composition .2012-03-15
  • 3
    These links and the references therein should tell you almost everything that is known about the problem: [1](http://math.stackexchange.com/questions/103290/is-there-a-real-valued-function-f-such-that-ffx-x) [2](http://mathoverflow.net/questions/17614/solving-ffxgx) [3](http://mathoverflow.net/questions/17605/how-to-solve-ffx-cosx) [4](http://mathoverflow.net/questions/12081/does-the-exponential-function-have-a-square-root) [5](http://reglos.de/lars/ffx.html).2012-03-15
  • 1
    The last two paragraphs make absolutely no sense to me.2012-03-15
  • 0
    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?2012-03-15
  • 0
    Asaf: I've edited in an example about bijective functions. Does that help to illustrate what the further questions refer to?2012-03-15
  • 0
    Why did you undo all the $\LaTeX$ improvements? Was it not for your liking that the huge chunks of text were somewhat more readable?2012-03-15
  • 0
    And to your comment, no. It did not help at all for me to understand what does ZFC and CH have to do with all that.2012-03-15
  • 0
    Argh. Apologies, I had not realized there was a simultanous edit - apparently there's no warning. I must've started my edit before you committed yours. As for ZFC and CH, I will edit another example in later that illustrates why cardinalities of the trees involved matter and how CH comes into play through that.2012-03-15
  • 0
    Okay, I've edited in an example that should illustrate why cardinalities and thus any set theoretic conditions determining the existance of bijections among structures relevant to the problem matter.2012-03-15
  • 0
    You remind me of a student of mine which after hearing about the axiom of choice tried to use it to prove all sort of things, but he had no idea how to use it - so he really didn't do it right. The use of CH is the same here. I don't see any reason or point to bring it up, and frankly I don't see ZFC playing a special role here either. This looks like a relatively naive set theory. I also don't see any "structures relevant to the problem" and the definitions as a whole are murky and ambiguous.2012-03-16
  • 0
    My advice to you, as someone who really did come up with plenty of problems which are neither interesting or useful for anyone - and then tried to research into them: sometimes reducing the case to a previously known result; sometimes finding out that the problem was a known result already; sometimes just giving up. So I can only advise you to let it be for a month, move on and think about other problems in the meantime. Then come back and re-read this thread. If you can understand the problem, try and tackle it again. Otherwise, you'll understand why I am being so adamant here.2012-03-16
  • 0
    I'm, once again, sorry, but I don't follow. I never even mentioned choice apart from being implicit in ZFC. The elementary explanations I gave were due to your claim that you don't understand what I'm asking. The murky definition I mark as murky myself and ask for references of potentially existant discussion on the topic. One relevant point - namely, infinite graph theory - gets edited out of the tags. So all that remains from your comments to me is "I don't find this interesting or useful". You may be right about both, but I find both of those facts rather irrelevant.2012-03-16
  • 0
    There is certainly a deep language barrier here. I gave examples from my *own* life, one about my student and one (more general) about myself. I did not say that your question is uninteresting or that it isn't useful. Also, it is unclear whether you mean the graph of the function or a graph whose vertices are functions or a graph whose vertices are points on the real life. If it is the first one, then this is certainly not graph theory. I should also make a note that until someone comes and understand your question your murky definitions are likely to stay incomprehensible.2012-03-16
  • 0
    Ah, that's the problem? That's easy, though. I'm definitely talking about graph theory. The vertices of the graph are the members of the equivalence class, with a directed edge from a to b if and only if f(a)=b. Then the equivalence classes are, as noted, directed 1 pseudo trees. A pseudo tree is "almost" a tree; it allows one cycle. A 1-pseudo tree has outdegree 1. Does that clarify that and why the structure of those trees are relevant?2012-03-16

0 Answers 0