Characterising functions $f$ that can be created as $f = g \circ g$?

I would certainly such as to qualify the functions that 'have square origins' in the function make-up feeling. That is, can an offered function $f$ be created as $f = g \circ g$ (where $\circ$ is function make-up )?

As an example, the function $f(x) = x+10$ has a square root $g(x) = x+5$.

In a similar way, the function $f(x) = 9x$ has a square root $g(x) = 3x$.

I do not recognize if the function $f(x) = x^2 + 1$ has a square root, yet I could not consider any kind of.

Exists a means to establish which functions have square origins? To maintain points less complex, I would certainly enjoy simply to take into consideration functions $f: \mathbb R \to \mathbb R$.

2019-05-07 13:12:43
Source Share
Answers: 1

I revealed you the link to the MO inquiry primarily to encourage you that this is a tough inquiry. I will certainly "address" it in the grandfather clause that $f$ is a bijection.

Remember that offered a bijection $f : S \to S$, where $S$ is a set, a cycle of $f$ size $n$ is a set of distinctive factors $x, f(x), ... f^{n-1}(x)$ such that $f^n(x) = x$. A cycle of boundless size is a set of distinctive factors $x, f(x), f^2(x), ...$. It is not tough to see that $S$ is a disjoint union of cycles of $f$.

Case : A bijection $f : S \to S$ has a square origin if and also just if there are an also variety of cycles of $f$ of any kind of offered also size. (For the objectives of this outcome, infinity is an also number ; so there can be a boundless variety of cycles, and also you require to take into consideration cycles of boundless size.)

Evidence. First we show that any kind of bijection with a square origin has this building. Allow $g : S \to S$ be a bijection such that $g(g(x)) = f(x)$. After that each cycle of $g$ represents either 1 or 2 cycles of $f$, as adheres to. If the cycle has weird size, it represents one cycle of $f$. As an example, the cycle $1 \to 2 \to 3 \to 1$ of $g$ would certainly represent the cycle $1 \to 3 \to 2 \to 1$ of $f$. If the cycle has also size, it represents 2 cycles of $f$. As an example, the cycle $1 \to 2 \to 1$ of $g$ would certainly represent both of cycles $1 \to 1$ and also $2 \to 2$, and also the cycle $1 \to 2 \to 3 \to ... $ would certainly represent both of cycles $1 \to 3 \to ... $ and also $2 \to 4 \to ...$. Specifically, cycles of $f$ of weird size can originate from cycles of $g$ individually or 2 at once, yet cycles of $f$ of also size can just originate from cycles of $g$ 2 at once.

Currently we show the reverse effects. Offered a cycle of $f$ of weird size $2k+1$, take into consideration the equivalent cycle of $f^{k+1}$ of weird size. Given that $f^{2k+2} = f$ when limited to this cycle, make this a cycle of $g$. Offered a set of cycles of $f$ of the very same also size, simply weave them with each other to get a cycle of $g$.

I claim "solution" as opposed to solution due to the fact that it's not noticeable if you can constantly locate the cycle disintegration of some difficult bijection on a boundless set. Regardless, if $f$ isn't thought to be a bijection this inquiry comes to be much tougher ; the analogue of cycle disintegration is far more hard to collaborate with. I recommend you consider some instances where $S$ is limited if you actually intend to get a grasp on this instance ; ideal of good luck.

2019-05-09 08:59:27