Un joli problème

Quentino37

Caractériser les fonctions $f:\mathbb N^* \to \mathbb N^*$ telles qu'il existe une fonction $g:\mathbb N^* \to \mathbb N^*$ telle que $f = g \circ g$.

Titi le curieux

Bonsoir,

Aucune idée pour le cas général mais pour les fonctions bijectives, j'ai un truc:

  Soit $f$ une fonction bijective de $\mathbb{N}^*$ dans $\mathbb{N}^*$, on appelle orbite par $f$ les classes d'équivence de la clôture transitive de la relation $\mathcal{R}$ définie par $\forall x,y, x\mathcal{R}y \leftrightarrow f(x) = y \lor f(y) = x$. L'ensemble des orbites, vu qu'il s'agit des classes d'une relation d'équivalence, compose une partition de $\mathbb{N}^*$.

  La condition pour qu'il existe $g$ telle que $g^2 = f$ est celle-ci: pour tout cardinal $\alpha$ strictement supérieur à 1 (Edit: correction, $\alpha$ doit être pair ou infini, un cycle impair peut être écrit comme un carré) le nombre d'orbites de cardinal $\alpha$ est pair ou infini (l'idée c'est que si on peut regrouper des orbites de même cardinal par paire, on peut assez facilement créer une bijection $h$ de l'union de la paire dans elle-même telle que $h^2$ soit égale à la restriction de $f$ sur cet ensemble).

  Peut-être qu'on peut trouver une méthode semblable pour le cas $f$ injective (sans être surjective), mais dans le cas général, j'en doute fort.

Edit: en fait, ça marche vachement bien pour le cas injectif. Il faut juste distinguer deux types d' "orbites" différents pour celles de cardinal infini, les "bijectives" (Soit $x$ un élément de l'orbite, l'application $h$ de $\mathbb{Z}$ dans l'orbite définie par $\forall n \in \mathbb{Z}, h(n) = x^n$ est une bijection) et les "bien fondées" (il existe $x$ tel que tout les élément de l'orbite s'écrive $x^n$ avec $n \in \mathbb{N}$).