Intereting Posts

Is Scrabble's method of determining turn order fair?
algebra – matrices and polynoms
The extension of smooth function
Possible Class equation for a group
How to search the internet for strings that consist mostly of math notation?
Minimal polynomial of $\frac{\sqrt{2}+\sqrt{5}}{\sqrt{3}}$
Expressing $\cos\theta – \sqrt{3}\sin\theta = r\sin(\theta – \alpha)$
A compact operator is completely continuous.
Expected value of infinite sum
Trigonometric Triangle Equality
Units of p-adic integers
Irreducible solvable equation of prime degree
Hessian matrix for convexity of multidimensional function
Name of this convex polyhedron?
How to solve vector-valued first order linear pde?

I’d like to characterise the functions that ‘have square roots’ in the function composition sense. That is, can a given function $f$ be written as $f = g \circ g$ (where $\circ$ is function composition)?

For instance, the function $f(x) = x+10$ has a square root $g(x) = x+5$.

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

- Why does the Dedekind Cut work well enough to define the Reals?
- Countable set having uncountably many infinite subsets
- How to prove that $\mathbb{Q}$ ( the rationals) is a countable set
- Why cannot a set be its own element?
- Cardinal equality: $\;\left|\{0,1\}^{\Bbb N}\right|=\left|\{0,1,2,3\}^{\Bbb N}\right|$
- What is the right way to define a function?

I don’t know if the function $f(x) = x^2 + 1$ has a square root, but I couldn’t think of any.

Is there a way to determine which functions have square roots? To keep things simpler, I’d be happy just to consider functions $f: \mathbb R \to \mathbb R$.

- Cardinality of the set of all pairs of integers
- If $A \subseteq C$ and $B \subseteq D$ then $A \times B \subseteq C \times D$
- Proving the inverse of a relation exists
- Show that $A∩B∩C= ∅$ is only true when $A∩B = ∅, A∩C = ∅$ or $B∩C = ∅$ or show a counterexample.
- Is there a notation for being “a finite subset of”?
- Why is there this strange contradiction between the language of logic and that of set theory?
- How do I prove that there doesn't exist a set whose power set is countable?
- Natural Numbers and Well ordering
- Example of $\sigma$-algebra
- Basic examples of ordinals

I showed you the link to the MO question mostly to convince you that this is a hard question. I will “answer” it in the special case that $f$ is a bijection.

Recall that given a bijection $f : S \to S$, where $S$ is a set, a cycle of $f$ length $n$ is a set of distinct points $x, f(x), … f^{n-1}(x)$ such that $f^n(x) = x$. A cycle of infinite length is a set of distinct points $x, f(x), f^2(x), …$. It is not hard to see that $S$ is a disjoint union of cycles of $f$.

**Claim:** A bijection $f : S \to S$ has a square root if and only if there are an even number of cycles of $f$ of any given even length. (For the purposes of this result, infinity is an even number; so there can be an infinite number of cycles, and you need to consider cycles of infinite length.)

*Proof.* First we show that any bijection with a square root has this property. Let $g : S \to S$ be a bijection such that $g(g(x)) = f(x)$. Then each cycle of $g$ corresponds to either one or two cycles of $f$, as follows. If the cycle has odd length, it corresponds to one cycle of $f$. For example, the cycle $1 \to 2 \to 3 \to 1$ of $g$ would correspond to the cycle $1 \to 3 \to 2 \to 1$ of $f$. If the cycle has even length, it corresponds to two cycles of $f$. For example, the cycle $1 \to 2 \to 1$ of $g$ would correspond to the pair of cycles $1 \to 1$ and $2 \to 2$, and the cycle $1 \to 2 \to 3 \to … $ would correspond to the pair of cycles $1 \to 3 \to … $ and $2 \to 4 \to …$. In particular, cycles of $f$ of odd length can come from cycles of $g$ one at a time or two at a time, but cycles of $f$ of even length can only come from cycles of $g$ two at a time.

Now we show the reverse implication. Given a cycle of $f$ of odd length $2k+1$, consider the corresponding cycle of $f^{k+1}$ of odd length. Since $f^{2k+2} = f$ when restricted to this cycle, make this a cycle of $g$. Given a pair of cycles of $f$ of the same even length, just weave them together to get a cycle of $g$.

I say “answer” instead of answer because it’s not obvious if you can always find the cycle decomposition of some complicated bijection on an infinite set. In any case, if $f$ isn’t assumed to be a bijection this question becomes much harder; the analogue of cycle decomposition is much more difficult to work with. I suggest you look at some examples where $S$ is finite if you really want to get a grip on this case; best of luck.

- Dividing an angle into $n$ equal parts
- Why don't elliptic PDE's have a time coordinate?
- How can I show that the polynomial $p = x^5 – x^3 – 2x^2 – 2x – 1$ is irreducible over $\Bbb Q$?
- Is there a way of intuitively grasping the magnitude of Graham's number?
- What is the value of $\lim_{x\to 0}x^x$?
- Dominos ($2 \times 1$ on $2 \times n$ and on $3 \times 2n$)
- Showing $ \times $ is a manifold with boundary
- Matrix is either null or similar to the elementary matrix $E_{2,1}$
- Is there any famous number theory conjecture proven impossible to be find out the truth or false?
- Differentiating a boundary condition at infinity
- Morphism from a line bundle to a vector bundle
- Eigenvalues for $3\times 3$ stochastic matrices
- How closely can we estimate $\sum_{i=0}^n \sqrt{i}$
- The $n$th term of this infinitely nested radical sequence
- Meaning of $f:\to\mathbb{R}$