Asymptotique d'une bijection de $\Bbb N^*$

Marrant comme problème :-)

J'arrive à montrer que pour tout $l \in [0, +\infty]$ on peut construire une permutation $\sigma_l$ telle que $\left(\frac{\sigma_l(n)}{n}\right)_n$ admette $l$ comme valeur d'adhérence, et en adaptant l'idée, que pour toute partie dénombrable $A$ de $[0, +\infty]$ on peut construire une permutation $\sigma_A$ telle que l'ensemble des valeurs d'adhérence de $\left(\frac{\sigma_A(n)}{n}\right)_n$ contienne $A$. Je suis persuadé qu'on peut faire bien mieux, j'y réfléchirai un peu plus tard.

J'ai essayé de bidouiller un truc. Je fabrique la bijection suivante :

$1 \longmapsto 10$
$2 \longmapsto 9$
...
$10 \longmapsto 1$

$11 \longmapsto 100$
$12 \longmapsto 99$
...
$100 \longmapsto 11$

$101 \longmapsto 1000$

enfin bref vous voyez le truc. Supposons que $\bigg( \dfrac{\sigma(n)}{n} \bigg)$ converge vers $1$. Alors toute sous-suite doit aussi converger vers $1$.

Mais $\bigg( \dfrac{\sigma(10^n + 1)}{10^n + 1} \bigg) = \dfrac{10^{n+1}}{10^n + 1} \longrightarrow 10$. Donc ma bijection ne peut pas tendre vers $1$.

Au début j'avais essayé $1 \longmapsto 10, ..., 10 \longmapsto 1, 11 \longmapsto 20,..., 20 \longmapsto 11$ etc mais vu qu'elle évolue linéairement, le rapport tend bien vers $1$.

Je dévoile ma méthode alors : soit $l > 0$. On définit $k_1 = 1$ et $k_{n+1} = \min \{k > k_n \mid \lfloor kl \rfloor > \lfloor k_n l \rfloor\}$. Ensuite je définis $\sigma_l : k_n \mapsto \lfloor k_n l \rfloor$ et n'importe comment de $\mathbb N^* \setminus \{k_n \mid n \geq 1\}$ dans $\mathbb N^* \setminus \{\lfloor k_n l \rfloor \mid n \geq 1\}$. Alors clairement $l$ est valeur d'adhérence de $\left(\frac{\sigma_l(n)}{n}\right)_n$ puisque $\frac{\sigma_l(k_n)}{k_n} = \frac{\lfloor k_n l \rfloor}{k_n} \underset{n \to +\infty}{\longrightarrow} l$. Pour atteindre $0$, c'est facile, on peut par exemple imposer $\sigma(n^2)=n$ pour tout $n \geq 1$, et pour atteindre $+\infty$ on prescrit $\sigma(n^2) = n^3$ par exemple.

Pour faire la même chose avec un nombre dénombrable de valeurs d'adhérence prescrites, on modifie légèrement la suite $(k_n)_n$ pour faire de la place, c'est-à-dire que $\mathbb N^* \setminus \{\lfloor k_n l \rfloor \mid n \geq 1\}$ soit toujours infini, et on peut ajouter autant de valeurs d'adhérence qu'on veut. Plus précisément, on se débrouille avec une partition dénombrable de $\mathbb N^*$ en ensembles dénombrables, et on fait le même type de construction à l'intérieur de chaque élément de la partition.

@Calli : Tu as raison pour les égalités d'ensemble, mais ce n'est pas très grave, il suffit de dégager un peu de place à $\{k_n \mid n \geq 1\}$ ou à $\{\lfloor k_n l \rfloor \mid n \geq 1\}$ en modifiant un tout petit peu la définition de $(k_n)_n$, par exemple en la restreignant aux carrés ou quelque chose du genre.

Et quand je dis que je définis $\sigma(n^2) = n$ tu n'as pas compris ce que je faisais. Je définis $\sigma$ ainsi sur les carrés et je l'étend en une bijection de $\mathbb N^*$ de manière quelconque.

Ah oui oups :-D À nouveau c'est un problème de place, mais ça se règle en posant $\sigma(n^4) = n^2$ par exemple. ;-)

Bonsoir raoul.S Pourquoi tu exclus le $+\infty$, ce n'est pas une valeur d’adhérence ?
Merci Calli pour l'exercice, si tu en a d'autres, n'hésite pas

Salut,

Je crois que j'ai trouvé un truc qui marche pour montrer la réponse de la dernière question, j'ai bâclé la topologie, mais l'idée m'a l'air correcte.
Je le mets là les lignes directrices pour vérification si certains ont le courage en blanc pour ne pas trop attirer l'œil de ceux qui aurait meilleures idées en cours de construction:


On sait que les $A_\sigma$ sont des fermés non vide avec un minimum plus petit ou égal à 1 et un maximum (dans $\overline{\mathbb{R}^+}$ qui est compact), supérieur ou égal à 1, c'est la réciproque qui est plus dure:

Étape topologique: montrer que tout fermé non vide de $\overline{\mathbb{R}^+}$ est adhérence d'une suite de rationnels strictement positifs (quitte à faire, prenez une suite de rationnels qui se trouve "entre" les bornes fermés, parce que je ne garantie pas le bon fonctionnement de la démonstration autour de la partie "algorithmique" sinon).

Idée de démonstration (à vérifier, j'ai juste esquissé le truc): Plutôt travailler dans $\overline{\mathbb{R}^+}$ (et ajouter $\{+\infty\}$ là où nécessaire, plus tard), rien que le fait d'être un espace métrique à base séparable (ce sont des propriétés qui se transmettent aux parties et la deuxième implique la séparabilité) a l'air suffisant pour montrer que pour tout fermé et toute partie dense et dénombrable, il existe une suite d'élément de la partie dense dont l'adhérence est égale au fermé.

Étape algorithmique: construire pour une suite $u$ de rationnels strictement positifs dont tout les éléments se trouvent entre les bornes de son adhérences dans $\overline{\mathbb{R}^+}$ et dont les bornes se trouve de part et d'autre de "1" (éventuellement dessus), une bijection $\sigma$ de $\mathbb{N}^*$ telle que $u$ soit suite extraite de $\sigma/n$ et que l'adhérence de la suite extraite "complémentaire" ait pour adhérence seulement le minimum et le maximum de l'adhérence de $u$.
Je pense que tout le monde voit comment "passer par des objectifs" à un moment ou un autre, il faut faire attention à "repousser suffisamment les objectifs" pour pouvoir "faire la poussière" (rendre l'application surjective tout en veillant à ce qu'il n'y a pas trop d'éléments $n$ tel que $\sigma_n/n$ soit "trop loin du minimum", la question se pose moins quand ce minimum est 0, à ce moment c'est presque du goutte à goutte) , particulièrement quand le minimum de l'adhérence est égal à 1. Bien sûr quand on a plus de poussière à mettre en bas et que ce n'est pas encore le moment pour l'objectif, on ajoute de la poussière "tout juste au dessus du plafond" (ou de plus en plus haut si le plafond est à l'infini). Un fois qu'on a trouvé un bon algorithme qui fait ça proprement et sait repousser juste comme il faut les "objectifs", on a pas de problème pour montrer que la poussière au plafond ne posera vraiment pas de problème.
Pensez aux antihistaminiques si vous êtes allergiques aux acariens et n'utilisez pas de masque, on en a besoin pour d'autres usages ces temps-ci.

Bonne nuit Calli,

Voilà une solution. Je ne la mets pas en blanc car je n'aime pas lire le blanc, mais je le ferai si quelqu'un pense que c'est mieux.

Premièrement, on montre que si $A \subseteq [0,+\infty]$ est un fermé contenant $1$, alors il est de la forme $A_\sigma$. L'idée est de perturber la suite identité. Soit $(x_n)_{n\geq 1}$ une suite de réels dont l'adhérence est $A$.
On commence par choisir un couple $(n,\sigma(n))$ tel que $\sigma(n)/n$ est "assez proche" de $x_1$. Soit $N$ tel que $N>n,\sigma(n)$. Sur $[0,N] \cap \N$, on effectue la permutation envoyant $n$ sur $\sigma(n)$ et tous les autres éléments sont envoyés dans l'ordre. Ensuite, on choisit $n' > N$ et $\sigma(n') > N$ tel que $\sigma(n')/n'$ est assez proche de $x_2$, puis $N' > n'$ et $N' > \sigma(n')$, et on reproduit la même chose sur $[N,N']$. Et on continue ainsi de suite jusqu'à l'infini, en s'approchant à chaque étape de plus en plus de $x_i$.

Montrons ensuite que si $0<a<1<b<\infty$, alors on peut avoir $A_{\sigma} = \{a,b\}$. Pour voir ce qu'il faut faire, on raisonne de manière "continue". On veut envoyer "localement" une certaine proportion $\alpha$ de $n \in \N$ sur $a n$ et une certaine proportion $\beta$ sur $b n$. Les contraintes sont que $\alpha + \beta = 1$ et aussi $\alpha/a + \beta/b = 1$ : on veut "tout couvrir une et une seule fois" (approximativement). On résout cette équation. Ensuite, on choisit une suite de "plus" et de "moins" comme

$$++++-++++-++++-++++-\cdots$$

telle que la proportion asymptotique de $+$ est $\beta$ et la proportion de $-$ est $\alpha$. On effectue la même chose mais pour la bijection réciproque de $\sigma$ : on résout $\alpha' + \beta' = 1$ et $\alpha' a + \beta' b = 1$. On choisit une suite "cousine" avec une proportion de $+$ égale à $\alpha'$ et une proportion de $-$ égale à $\beta'$. Puis on associe dans l'ordre les $+$ de la première suite aux $-$ de la deuxième et les $-$ de la première aux $+$ de la deuxième. Ça donne notre bijection $\sigma$.

Plus explicitement, si le $k$ième élément de la première suite est un $+$, alors $\sigma(k)$ est le $k$ième $-$ de la deuxième suite (et symétriquement).

Les cas où $a=0$ et/ou $b=\infty$ sont aussi traités en faisant comme si $a$ était de plus en plus petit et/ou $b$ de plus en plus grand au fur et à mesure qu'on construit les suites de $+$ et de $-$.

Ensuite, si on a par exemple $b<\infty$ et qu'on veut ajouter à $A_{\sigma}$ des éléments plus grands que $b$, on fait comme dans le cas traité plus haut où $1 \in A$ : on perturbe la permutation. C'est un peu chiant à expliquer mais c'est la même chose que quand $1 \in A$ (c'est pour ça que j'ai inclus ce cas). Et on a besoin que les valeurs ajoutées soient plus grandes que $b$. On procède symétriquement pour les valeurs plus petites que $a$ qu'on veut ajouter.

---

J'ai rédigé ça plus ou moins "proprement" (edit : heu non pas vraiment en fait, je veux dire par rapport à ce que j'avais en tête au début) mais je suis toujours gêné car j'ai l'impression qu'il manque quelque chose que je ne connais pas et qui permettrait de formaliser plus fidèlement ces "idées floues". Par exemple, l'idée pour l'histoire de l'équation $\alpha/a + \beta/b = 1$ s'explique comme suit. On parcourt nos nombres comme un continuum plutôt qu'un ensemble discret. On a une flèche qui pointe de $n$ vers $an$ avec un coefficient $\alpha$ et une flèche qui pointe vers $bn$, avec un coefficient $\beta$. Plus généralement, on pourrait imaginer avoir toute une multitude de flèches données par une mesure de probabilité $\mu$ sur $\R$, disant que $n$ pointe vers $e^x n$ avec une probabilité $\mu(x)$. L'équation à satisfaire pour "avoir une bijection" est $\int e^{-x} d\mu(x) = 1$. Peut-on directement tirer de ça l'existence des $A_\sigma$ sans avoir besoin de faire quelque chose de plus "concret" ? Peut-on raisonner en termes flous comme ça, avec certaines règles (une logique ??) nous assurant que les choses fonctionnent ? Sauf que non, c'est bien trop compliqué j'imagine.

Par exemple, là j'ai laissé plein de flou dans ce que j'ai dit au-dessus. Je pense notamment à mon histoire de suite de $+$ et de $-$. Pour vérifier que ça fonctionne, il faudrait effectuer un calcul. Sauf que la visualisation "continue" devrait forcer à ce qu'il fonctionne... ce n'est pas une bonne manière de procéder que d'effectuer ce calcul. Je n'ai pas fait la chose de manière intentionnelle : j'ai introduit une autre suite cousine pour que les calculs soient faisables, mais on ne devrait pas faire ça. Alors comment faire ?

@Champ-Pot-Lion désolé de jouer le rabat-joie mais je crois avoir trouvé une erreur dans la première partie de ton message. Tu me diras si je me trompe mais la bijection $\sigma$ que tu construits vérifie $\sigma \circ \sigma = id$ et par suite, si $x$ est valeur d'adhérence de $(\sigma(n)/n)_{n\in \mathbb{N}}$ alors $1/x$ aussi... donc $\sigma$ risque d'ajouter des valeurs d'adhérences qui ne sont pas dans le fermé d'origine.

raoul.S, Tout d'abord merci d'avoir regardé ce que j'ai écrit. La bijection que je construis ne vérifie pas $\sigma \circ \sigma = id$, je ne vois pas pourquoi ce serait le cas.

Peut-être que j'ai mal expliqué. Par exemple, mettons on va envoyer $100$ sur $314$ si on veut approcher $\pi$, et puis on va envoyer $1$ sur $1$, $2$ sur $2$, etc. puis $99$ sur $99$, puis $101$ sur $100$, puis $102$ sur $101$, etc. puis $314$ sur $313$, puis $315$ sur $315$, puis on revient à l'identité. On continue avec l'identité un bout de temps si on veut, puis on réintroduit une perturbation plus tard pour atteindre une autre valeur qu'on veut atteindre, puis on attend de se stabiliser, et on continue.

Enfin bref, ça tourne autour des mêmes idées que ce que dit Titi et ce n'est pas satisfaisant.

Salut,

Pour la question à la fin du dernier message de Calli, je ne sais pas, mais je crois que ça ne change rien (je pense même qu'on est pas obligé d'être aussi sélectif que je l'ai été dans le choix de la suite de rationnel de base, ils ne sont peut-être pas obligé d'être strictement inclus entre les bornes, le fait qu'ils soient tous non nuls est probablement suffisant), et je pense que les raisonnements que j'utilise pour démontrer que ça marche ne changent pas. En fait si 1 est dans $F$ et qu'on ne prend que lui comme dépoussiérant, je crois que si $n$ est un élément "complémentaire" on devrait avoir un truc du genre $|n-\sigma_n|\leq 1 + \log(n)/\log(2)$ (ou vraiment pas loin).

Que se passe-t-il avec $\sigma (p) := (N+1)! +N! -p$ où $N$ est l'unique entier tel que $N! \leq p < (N+1)! $ si $p\geq 1$ et $\sigma (0) := 0$ ?

Jolie construction Foys (tu)

Très joli ! (tu)

Tout ce qui traîne doit finir par disparaître.

@Titi je ne suis pas sur d'avoir compris mais si $1\notin F$ il faut choisir un autre dépoussiérant ? et on ne sait pas lequel c'est ça ? (:D

Proposition. Soit $0\leq a<1<b \leq +\infty$. Alors il existe
1) $f_1:\N^*\to\N^*$ et $f_2:\N^*\to\N^*$ strictement croissantes dont les images partitionnent $\N^*$,
2) $g_1:\N^*\to\N^*$ et $g_2:\N^*\to\N^*$ strictement croissantes et dont les images partitionnent $\N^*$
telles que $g_1(n)/f_1(n) \to a$ et $g_2(n)/f_2(n) \to b$.
On peut aussi faire en sorte que $f_i(n+1)/f_i(n) \to 1$ et pareil pour les $g_i$.

Preuve. Soit $(\alpha,\beta)$ la solution de $\alpha+\beta=1$ et $\alpha/a+\beta/b=1$. On trouve $\alpha = a(b-1)/(b-a)$ et $\beta = b(1-a)/(b-a)$. On prolonge les solutions par continuité si $a=0$ ou $b=+\infty$.
Soit une suite de $+$ et de $-$ telle que la proportion asymptotique de $-$ soit $\alpha$ et celle de $+$ soit $\beta$. Soit $f_1(n)$ la position du $n$ième $-$ et soit $f_2(n)$ la position du $n$ième $+$. On peut faire en sorte que $f_i(n+1)/f_i(n) \to 1$.

Soit $(\alpha',\beta')$ la solution de $\alpha'+\beta'=1$ et $\alpha' a + \beta' b = 1$, avec prolongement par continuité dans les cas limites.
Soit une suite de $+$ et de $-$ telle que la proportion de $+$ soit $\alpha'$ et la proportion de $-$ soit $\beta'$. Soit $g_1(n)$ la position du $n$ième $+$ et soit $g_2(n)$ la position du $n$ième $-$. On fait en sorte que $g_i(n+1)/g_i(n) \to 1$, pareil qu'au-dessus.

Maintenant, il faut vérifier que $g_1(n)/f_1(n) \to a$. On a $n/f_1(n) \to \alpha$ et $n/g_1(n) \to \alpha'$. Donc $g_1(n)/f_1(n) \to \alpha/\alpha'$. Si on fait le calcul, on trouve que $\alpha$ et $\alpha'$ valent pile ce qu'il faut pour que ça fasse $a$. (Il n'y a en particulier pas de problème tel que $+\infty/+\infty$.)
Pareil pour $g_2(n)/f_2(n) \to b$.

On définit ensuite $\sigma(f_i(n)) = g_i(n)$ et on obtient $A_{\sigma} = \{a,b\}$.

Il y a une explication de pourquoi j'ai choisi ces équations à résoudre, alors qu'elle n'apparaît pas du tout dans la preuve. Cette raison n'est pas "pour que les calculs donnent $a$ et $b$"... Donc ce n'est pas complet mais tant pis, le plus simple est de rédiger ainsi.

Si on veut récupérer d'autres valeurs d'adhérence plus grandes que $b$ ou plus petites que $a$, on applique le lemme que j'ai donné plus haut.

edit : orthographe.