2

Let $S$ be a finite set and $f \colon S \to S$ be an arbitrary function. How can we find all functions $g \colon S \to S$ with $f = g \circ g$?

If $f$ and $g$ are both required to be invertible, the question is simple (but not completely trivial).

I know also about versions of this question where $S = \mathbb C$ or $\mathbb R$ and $f$ and $g$ are at least continuous, but this changes the question to something completely different.

(And is there an easy method to check whether $f$ has a square root?)

gmvh
  • 2,758
rimu
  • 749
  • 1
    For permutations, see https://www.findstat.org/StatisticsDatabase/St000811 and in particular the reference to https://mathoverflow.net/q/41784/3032 – Martin Rubey Mar 29 '21 at 08:43
  • It might be interesting to find explicit square roots of some of the classical maps which seem to have a square root. A quick check yields the following maps: https://www.findstat.org/Mp00113, https://www.findstat.org/Mp00161, https://www.findstat.org/Mp00188, https://www.findstat.org/Mp00194, https://www.findstat.org/Mp00091, https://www.findstat.org/Mp00176, https://www.findstat.org/Mp00158, https://www.findstat.org/Mp00123, https://www.findstat.org/Mp00126 (for some of these a square root is known, but I did not check all) – Martin Rubey Mar 29 '21 at 11:00
  • 3
    There seem to be $\sum_{k=1}^n \binom nk k^{n-k}$ square roots of a constant function, which is http://oeis.org/A000248 but this interpretation is not given there. – Brendan McKay Mar 29 '21 at 12:00
  • @MartinRubey How did you know that these functions should have a square root? – rimu Mar 29 '21 at 12:28
  • 1
    @rimu I/SageMath computed, for each, the cycle type for the first few levels (e.g., Dyck paths of length 2, 3, 4 and 5) and used findstat.org/StatisticsDatabase/St000811 to determine whether a square root exists. Of course, it is quite possible that a square root exists only on the first few levels. – Martin Rubey Mar 29 '21 at 13:41

0 Answers0