Asymptotique d'une bijection de $\Bbb N^*$
Bonjour à tous,
Je partage un problème que j'ai bien aimé. Soit $\sigma$ une bijection de $\Bbb N^*$. Comment se comporte asymptotiquement la suite $(\frac{\sigma(n)}n)$ ?
Au plaisir de vous lire
Je partage un problème que j'ai bien aimé. Soit $\sigma$ une bijection de $\Bbb N^*$. Comment se comporte asymptotiquement la suite $(\frac{\sigma(n)}n)$ ?
- Converge-t-elle forcément vers 1 ?
- Si non, vers quelles limites peut-elle converger ?
- Peut-elle diverger ?
- Ne pas être bornée ?
- Est-ce que 1 est toujours valeur d'adhérence ?
- À quel point l'ensemble de ses valeurs d'adhérence peut-il être grand ? (a priori en termes de tout ce que vous voulez : cardinalité, mesure...)
- Quelles sont toutes les adhérences possibles dans $\overline{\Bbb R}$ ? En d'autres termes, si $A_\sigma$ désigne l'ensemble des valeurs d'adhérence de $(\frac{\sigma(n)}n)$ dans $\overline{\Bbb R}$, que vaut $\{ A_\sigma \mid \sigma\in\mathfrak{S}(\Bbb N^*)\}$ ?
Au plaisir de vous lire
Réponses
-
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. -
Salut
J'ai une idée assez précise pour répondre à l'avant-dernière question et soupçonne un truc pour la dernière, mais avant d'être un peu plus précis, j'aimerais savoir si mes intuitions sont bonnes, quelqu'un pourrait-il confirmer ou infirmer ces deux suppositions, je précise que si c'est non, c'est juste non (je les mets en blanc pour ne pas embêter ceux qui veulent le faire vraiment seul).
Outre quelques connaissances sur la topologie de $\mathbb{R}$, peut-on répondre à l'avant-dernière question juste avec le théorème de Cantor-Bernstein et un ou deux petits coups tordus ?
La réponse à la dernière question est-elle : n'importe quel fermé (évidemment non vide), de $\overline{\mathbb{R}^+}$ dont le minimum est inférieur ou égal à 1 et le maximum supérieur ou égal à 1 ? (notons bien que $\overline{\mathbb{R^+}}$ est le compactifié d'Alexandrov de $\mathbb{R}^+$)
Je me permets de donner une indication toute bête à ceux qui pourraient galérer sur certaines des premières questions.
On peut démontrer que toute bijection $\sigma$ de $\mathbb{N}$ dans $\mathbb{N}$ vérifie les deux formules suivantes: $\forall k,\ \exists n,\ n>k \wedge \sigma(n)\leq n$ et $\forall k,\ \exists n,\ n> k \wedge \sigma(n)\geq n$
Edit: Viens de lire le message privé. Merci Calli. -
Je t'ai envoyé un message pour te répondre, Titi.
-
Si je n'ai pas fait d'erreurs, 1 est toujours valeur d'adhérence.
Edit : je me corrige la question est toujours ouverte : j'ai juste obtenu que $\liminf \dfrac{\sigma(n)}{n} \leqslant 1 \leqslant \limsup \dfrac{\sigma(n)}{n}$ :-(
PS. toujours si pas d'erreurs... -
Pour liminf :
si $\liminf \dfrac{\sigma(n)}{n} > 1$ alors il existe $N>0$ tel que $\forall n \geq N$, $\sigma(n)> n$. On en déduit que $\sigma$ induit une bijection de $1,N-1$ et $\sigma$ induit aussi une bijection de $1,N$. Par conséquent $\sigma(N)=N$ ce qui est absurde.
Pour limsup :
Ah je viens de lire ton message @Calli, ok tu m'épargne la peine d'écrire le limsup cool ! (tu) -
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$. -
J'ajoute : je ne l'ai pas encore vérifié, mais je pense que la suite des rapports de ma bijection tend effectivement vers $10$. Du coup, en faisant la même construction que moi, mais en remplaçant $10$ par un autre nombre entier, on peut fabriquer une bijection dont la suite des rapports tend vers n'importe quel entier naturel non nul.
Avec $2$ :
$1 \longmapsto 2$
$2 \longmapsto 1$
$3 \longmapsto 4$
$4 \longmapsto 3$
$5 \longmapsto 8$
etc.
Si on regarde $\bigg( \dfrac{\sigma(2^n + 1)}{2^n + 1}\bigg)$, ça tend vers $2$. Donc $\bigg( \dfrac{\sigma(n)}{n}\bigg)$ ne peut pas tendre vers $1$.
J'imagine que toutes les bijections qu'on fabrique comme ça fonctionnent pareil. Donc il faudrait calculer la limite proprement pour l'une d'entre elles. -
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. -
J'ai du mal à écrire explicitement ma bijection, donc pour calculer sa limite, je suis bloqué...
-
Homo Topi : Effectivement 10 est bien valeur d'adhérence pour ta bijection (tu). En revanche, je doute qu'elle converge vers 10 car $\dfrac{\sigma_{HT}(10)}{10} = \dfrac1{10}$, $\dfrac{\sigma_{HT}(100)}{100} = \dfrac{11}{10} \approx \dfrac1{10}$, etc. (je me permets de lui donner un nom).
Poirot : N'a-t-on pas $\{k_n \mid n \geq 1\} = \Bbb N^*$ si $l>1$ et $\{\lfloor k_n l \rfloor \mid n \geq 1\}=\Bbb N^*$ si $l<1$ et des inclusions strictes en renversant les inégalités sur $l$ ? C'est gênant pour définir une bijection qui envoie $\{k_n \mid n \geq 1\} $ sur $\{\lfloor k_n l \rfloor \mid n \geq 1\}$ et le complémentaire du premier sur celui du second. :-S
Et en posant $\sigma(n^2)=n$ on ne risque pas d'obtenir une bijection ! -
Bon, quoi qu'il en soit, la mienne ne tend déjà pas vers $1$, donc j'ai réglé la première question. Par contre, au vu de ce que tu dis, on trouve deux valeurs d'adhérence distinctes pour la mienne, donc elle ne converge pas du tout, ce qui règle la troisième question.
Quant à celle de Poirot, j'ai honnêtement la flemme de comprendre sa construction. Un truc avec des $\min$ de parties entières "remplies n'importe comment entre les trous", au secours. Si ça se trouve, sa bijection permet de tout régler d'un coup, mais je la trouve beaucoup trop moche :-D -
@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. -
Si tu ne conserves qu'un $k_n$ sur deux, ok je veux bien. Je vois en gros ce que tu veux dire pour un nombre dénombrable de valeurs d'adhérence prescrites maintenant.Poirot a écrit: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 $\Bbb N^*$ de manière quelconque.
Mais $\sigma_{|\{n^2 \mid n\in\Bbb N^*\}}$ est déjà surjective ! Tu ne peux pas la prolonger en une injection... Enfin, en posant ta formule uniquement pour les $n$ qui sont déjà des carrés parfaits et en "remplissant n'importe comment le reste", ça va marcher. -
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. ;-)
-
Je poste ici une autre démo (si pas d'erreurs) du fait que tout nombre appartenant à $[0, +\infty[$ est valeur d'adhérence.
On reprend la bijection définie par Poirot $\sigma(n^4) = n^2$ et on note $S:=\{n^4 \,|\, n\in \mathbb{N}^{*}\}$. Alors pour tout $x\geqslant 0$, la bijection $\sigma_x$ définie par $\sigma_x(n):=\sigma(n)+\lceil nx\rceil$ pour tout $n\in S$ et ce qu'il faut sur le complémentaire de $S$, a bien $x$ comme valeur d'adhérence.
$\sigma_x$ peut être défini comme ci-dessus car le complémentaire de $\sigma_x(S)$ est infini. -
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 pasLorsque notre cher Nico, le professeur, intervient dans une question d'analyse, c'est une véritable joie pour les lecteurs.. -
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. -
Titi, je ne vois pas grand chose de concret dans ce que tu as écrit. D'accord pour ton préliminaire topologique, mais ensuite tu parles de repousser des objectifs à passer et de coller de la poussière au plafond... Qu'est-ce que c'est que cette histoire ? Je n'y comprends strictement rien.
-
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 ? -
Désolé, j'ai fait trop de ménage aujourd'hui et ça m'a obsédé. Et puis, je voulais rester vague, parce que je trouve l'exercice chouette et que personnellement, ça m'aurait fait suer que quelqu'un soit un peu trop clair sur cette dernière partie.
Bon tant pis, je la refais:
On a un fermé $F$, non vide de $\overline{\mathbb{R}^+}$ avec $m=\min(F)\leq 1$ et $M=\max(F)\geq 1$. On sait qu'il existe une suite de rationnel $(u_n)_{n\in\mathbb{N}}$ telle que $\forall n\in\mathbb{N}, m<u_n<M$ (on met de côté le cas $F=\{1\}$ parce qu'il est pas ouf) et dont l'adhérence est précisément $F$.
Voilà une recette pour construire la bijection $\sigma$ telle que $(\sigma(n)/n)_{n\in \mathbb{N}}$ possède une suite extraite qui soit une permutation de $u$ (pas grave, ça ne change pas l'adhérence) et dont l'adhérence de la suite extraite "complémentaire" est edit: pas "est", "est contenue", voir les cas $m=1$ $\{m,M\}$ (j'avais pris un autre truc à la base, où on surveillait beaucoup ce qui se passait autour de $m$, mais ça empêchait de prévoir "les objectifs" à l'avance, pour celle-là je n'ai pas vérifié que la suite extraite "complémentaire" a les bonnes valeurs d'adhérence, mais ça doit le faire, enfin je suppose):
a) On fixe les "objectifs", c'est-à-dire où on doit atteindre la valeur $\sigma/id$ doit atteindre $u_n$ pour chaque $n$, on va les nommer $(q_n,p_n)$, il faut que l'ensemble de ces couples soit plongeable dans une bijection de $\mathbb{N}^*$ et $\forall n p_n/q_n=u_n$.
On va les définir par récurrence de cette manière: $\forall n\in \mathbb{N}^*, q_n=\min \{ q\in \mathbb{N}^*| \exists p>2^n, p/q=u_n \wedge \forall k<n,( p\geq 2 p_k \wedge q\geq 2 g_k) \}$, en mettant les objectifs à l'avance, je suis moins confiant, c'est pourquoi j'ai mis tout plein de condition minorations, on est pas absolument sûr que ça marche, mais ce ne serait pas de bol, parce qu'on a laissé un truc assez aéré pour que ça le fasse.
b) Construction de la suite extraite complémentaire: On la construit par récurrence, On nomme $\forall n\in \left(\mathbb{N}\backslash \{q_k, k\in \mathbb{N}^* \}\right) $ $G(n)=\mathbb{N}^*\backslash \left( \{\sigma_k, k<n\} \cup \{p_k, k\in \mathbb{N}^*\} \right)$. On notera que $\forall n$ $G(n)$ est "infini".
- À chaque fois que $\min(G(n)$ est plus petit qu'un truc qui dépend de $n$, on prend $\sigma_n=\min(G_n)$ (typiquement, ça va être $nm$ où m est le minorant de $F$, sauf si c'est 0, dans ce cas, je propose par exemple la racine carré de $n$, ou n'importe quoi d'autre, le principe, c'est que le rapport entre les deux tendent vers 0 quand $n$ devient grand mais que personne ne soit oublié).
- Si ce n'est pas le cas, on prend $\sigma_n=\min\{p\in G(n), p\geq Mn \}$ ($M$ le majorant de $F$, si c'est $\infty$, on prendra juste le plus petit élément $p$ de $G(n)$ tel que $p/n$ majore tout les $\sigma_k/k$ avec $k<n$). -
@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.
-
Bonjour Titi,
Ce que tu fais est plus simple que moi.
Mais je ne suis toujours pas convaincu... Enfin ce n'est pas important. -
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. -
@Champ-Pot-Lion Ah OK ! j'avais mal compris la construction de $\sigma$ (tu)
-
Ok, faisons un point :
- $(\frac{\sigma(n)}n)$ converge-t-elle forcément vers 1 ? Non d'après Homo Topi, Poirot et Raoul.
- Si non, vers quelles limites peut-elle converger ? 1 est la seul limite possible d'après Raoul qui a montré $\liminf \frac{\sigma(n)}n \leqslant 1\leqslant \limsup \frac{\sigma(n)}n$.
- Peut-elle diverger ? Oui d'après notamment Homo Topi.
- Ne pas être bornée ? Oui d'après Poirot.
- Est-ce que 1 est toujours valeur d'adhérence ? Non d'après Champ-Pot-Lion qui a montré qu'on peut avoir $A_\sigma = \{a,b\}$ avec $0<a<1<b<+\infty$.
- À quel point l'ensemble de ses valeurs d'adhérence peut-il être grand ? C'est bien parti pour devenir un corollaire de la dernière question. Pourtant on peut expliciter une bijection simple qui donne une adhérence maximale !
- Quelles sont toutes les adhérences possibles $A_\sigma$ dans $\overline{\Bbb R}$ ? Les $A_\sigma$ sont toutes des fermés de $[0,+\infty]$ tels que $\min A_\sigma\leqslant1\leqslant\max A_\sigma$ d'après Raoul. Prouver la réciproque est à l'étude.
-
Champ-Pot-Lion et Titi : Votre idée de partir sur une base $A_\sigma = \{a,b\}$ et de perturber $\sigma$ est intéressante ! (enfin, plus exactement Champ-Pot-Lion a fait dans ce sens-là et Titi dans l'ordre contraire). Je n'avais pas fait comme ça.
Je m'avoue quand même pas totalement convaincu. Ça mériterait plus de détails et de justifications. Par exemple, je ne suis pas sûr que vous couvriez tous les cas de figures (suivant si on veut $A_\sigma \cap[0,1] = \{0\}$, $A_\sigma \cap[0,1] = \{1\}$, $A_\sigma \cap\,]0,1[\,\neq\varnothing$... et idem à droite de 1). C'est assez fastidieux, je sais, je m'y suis aussi collé. À vous de voir si vous avez envie de paufiner.
Mais ce que vous avez fait doit en gros marcher, modulo l'écriture des détails (qui constitue quand même une bonne partie de la difficulté !).
Champ-Pot-Lion :Champ-Pot-Lion a écrit:Et on continue ainsi de suite jusqu'à l'infini, en s'approchant à chaque étape de plus en plus de $x_i$.
Oui, enfin c'est un peu plus compliqué que ça parce qu'il faut s'approcher une infinité de fois de chaque $x_i$. S'approcher de $x_1$, puis de $x_2$, ensuite $x_3$ etc. ne suffit parce qu'ainsi on ne revient pas à $x_1$.
Et si on fait les choses mal, on risque d'obtenir des valeurs d'adhérence qu'on ne veut pas. En effet, si pour tout $i\in\Bbb N$, on a une extractrice $\varphi_i$ telle que $\frac{\sigma(\varphi_i(n))}{\varphi_i(n)} \xrightarrow[n\to\infty]{} x_i$, qui dit que la suite extraite diagonale $\left(\frac{\sigma(\varphi_n(n))}{\varphi_n(n)}\right)_n$ ne fait pas n'importe quoi ? Le problème se résout bien, mais il faut quand même le soulever et vérifier qu'on l'évite.
Pour ta question sur une mesure de proba, un continuum, etc., je n'ai pas vraiment de réponse à t'apporter. Je ne sais pas exactement ce que tu as dans la tête en parlant de ce continuum. En tout cas, pour répondre au problème, on est forcé de montrer concrètement l'existence de la bijection voulue à un moment.
Titi le curieux : C'est malin de prendre une suite $(u_n)$ de rationnels dont l'ensemble des valeurs d'adhérences est le fermé voulu ; ça donne un bon contrôle. Est-ce que ç'a vraiment une importance de prendre $m=\min F$ et $M=\max F$ et pas juste $m,M\in F$ avec $m\leqslant 1\leqslant M$ ? -
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). -
Calli a écrit:Oui, enfin c'est un peu plus compliqué que ça parce qu'il faut s'approcher une infinité de fois de chaque $x_i$. S'approcher de $x_1$, puis de $x_2$, ensuite $x_3$ etc. ne suffit parce qu'ainsi on ne revient pas à $x_1$.
Je crois que Titi fait la même chose, du moins c'est ce que j'ai compris en lisant : on prend $(x_n)_n$ telle que les valeurs d'adhérence de cette suite soit $A$ (je ne parle pas de l'adhérence de l'ensemble $\{x_n\mid n\in \N\}$).
Pour répondre à ta deuxième objection, on a une partition de $\N$ : une sous-suite extraite $\varphi$ telle que $(\sigma(\varphi(n))/\varphi(n))_n$ converge vers $1$ (la plus grosse partie de $\N$), et une sous-suite extraite $\phi$ telle que $(\sigma(\phi(n))/\phi(n) - x_n)_n$ converge vers $0$. Sous ces conditions, l'adhérence est l'union des adhérences des deux sous-suites, donc ce qu'on veut...Calli a écrit:En tout cas, pour répondre au problème, on est forcé de montrer concrètement l'existence de la bijection voulue à un moment.
J'aimerais bien que non, mais tu dois avoir raison. Il faut bien rêver un peu !
J'ajoute des détails dans ce que j'ai fait. On sépare en plusieurs cas.
1) Cas où $1 \in A$ : perturbation de la suite identité.
2) Cas où $a=\max (A \cap [0,1]) > 0$ et $b=\min (A \cap [1,+\infty]) < +\infty$ : construction de la suite avec les histoires de $+$ et de $-$, puis perturbation pour récupérer les autres valeurs.
3) Cas où $a=0$ et $1<b<\infty$ : cas limite dans la construction des suites de $+$ et de $-$. La première suite aura une proportion de $+$ tendant vers $1$. La deuxième aura une proportion de $-$ tendant vers $1/b$. (Il faut prendre les cas limites dans la résolution des équations pour "deviner" qu'il faut prendre ça.) Puis on perturbe la sous suite dont l'item numéro $k$ est la position du $k$ième $+$ dans la première suite, comme dans le cas (1), pour récupérer les valeurs au-dessus de $b$. (En fait on pourrait aussi récupérer n'importe quelle autre valeur avec.)
4) Cas où $0<a<1$ et $b=+\infty$ similaire.
5) Cas où $a=0$ et $b=+\infty$ : on prend dans la première suite une proportion asymptotique de $+$ égale à $1$ et dans la deuxième une proportion asymptotique de $-$ égale à $0=1/b$. -
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$ ?Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
-
Re,
@Foys, on a $A_\sigma=[0,1]$, il rentre bien dans les clous qu'on a défini.
Edit: oups! À l'ouest le titi, merci raoul. -
Jolie construction Foys (tu)
-
Champ-Pot-Lion :
Ah d'accord, j'avais mal compris. Je pensais que $\overline{\{x_n\mid n\in \N\}}=A$. Mais si $A$ est l'ensemble des valeurs d'adhérence de $(x_n)$, pas de soucis sur ce point.Champ-Pot-Lion a écrit:Pour répondre à ta deuxième objection, on a une partition de $\N$ : une sous-suite extraite $\varphi$ telle que $(\sigma(\varphi(n))/\varphi(n))_n$ converge vers $1$ (la plus grosse partie de $\N$), et une sous-suite extraite $\phi$ telle que $(\sigma(\phi(n))/\phi(n) - x_n)_n$ converge vers $0$. Sous ces conditions, l'adhérence est l'union des adhérences des deux sous-suites, donc ce qu'on veut...
Si tu n'as qu'un nombre fini d'extractrice, tout va bien. Le problème se pose si on en a un nombre infini. En l’occurrence, on sait que pour tout $x\in A$, il existe $\varphi_x$ telle que $\frac{\sigma(\varphi_x(n))}{\varphi_x(n)} \xrightarrow[n\to\infty]{} x$. Prenons $(x_i)_{i\in\Bbb N}\in A^{\Bbb N}$. Alors on pourrait avoir par exemple $\forall (i,n), \frac{\sigma(\varphi_{x_i}(n))}{\varphi_{x_i}(n)} = x_i + \frac{i^2}n$, et donc $\frac{\sigma(\varphi_{x_n}(n))}{\varphi_{x_n}(n)} = x_n + n\longrightarrow +\infty$. Ça peut être gênant si on ne veut pas avoir $+\infty$ dans $A_\sigma$. Mais si ça trouve il n'y a aucun problème. Il faudrait mieux connaitre la construction pour en être sûr.
Avec la disjonction de cas que tu as écrite, me voilà plus convaincu que tu n'a pas oublié de cas. :-) Il y a juste la perturbation évoquée dans le point 2) dont je ne sais pas vraiment comment elle marche. -
Foys : Ta bijection répond efficacement à l'avant-dernière question. (tu) Elle est similaire à celle d'Homo Topi en fait (voir http://www.les-mathematiques.net/phorum/read.php?4,1972456,1972824#msg-1972824).
Tiens, en parlant d'Homo Topi, as-tu lu le message que je t'ai envoyé ? (la technique diabolique de le demander devant tout le monde pour avoir plus de chance d'obtenir une réponse :-D)
Tous : Voici une autre solution à l'avant dernière question. Tout nombre $n$ s'écrit sous la forme $2^{a} 3^{b} 5^{c} d$ avec $d$ premier avec $2\times 3\times 5$. On pose alors $\sigma (n)=2^{b} 3^{c} 5^{a} d$. Cela donne $\frac{\sigma (n)}{n} =2^{b-a} 3^{c-b} 5^{a-c} = ( \frac{2}{5} )^{b-a} ( \frac{3}{5} )^{c-b}$. Or $\{ (b-a,c-b) \mid (a,b,c)\in \mathbb{N}^{3} \}=\mathbb{Z}^2 $ car $$\left\{ \begin{array}{l} i=b-a\\ j=c-b \end{array} \right. \Leftrightarrow \left\{ \begin{array}{l} b=a+i\\ c=a+i+j \end{array} \right.$$ et il suffit de prendre $a$ assez grand pour que $b$ et $c$ soient positifs. On conclut par densité de $\ln( \frac{2}{5} )\, \mathbb{Z}+\ln( \frac{3}{5} )\, \mathbb{Z}$ dans $\mathbb{R}$. -
Très joli ! (tu)
-
Titi : D'accord. Je n'ai toujours pas compris pourquoi tu parles de poussière.
-
Tout ce qui traîne doit finir par disparaître.
-
@Calli Je n'ai pas compris ce que tu as dit. Si on a deux suites $(u_n)_n$ et $(v_n)_n$ avec $u_n - v_n \to 0$, alors $u_n$ et $v_n$ ont les mêmes valeurs d'adhérence. J'utilise ce fait appliqué avec $v_n=x_n$ dont l'adhérence est supposée être $A$ et $u_n$ une suite extraite de $\sigma(n)/n$. On partitionne la suite des $\sigma(n)/n$ en deux : la première partie converge vers $1$ et la deuxième est la suite extraite proche de $x_n$.
Il n'y a que deux suites extraites auxquelles j'applique la propriété que l'adhérence des unions est l'union des adhérences. Un nombre fini, donc pas de problème.
Je vais essayer de faire quelque chose de plus détaillé.
Lemme. Soit $f : \N^* \to \N^*$ strictement croissante et $g : \N^* \to \N^*$ injective. Supposons que $g(n+1)/g(n) \to 1$ et que $g(n)/f(n) \to a$. Soit $A \subseteq [a,+\infty]$ un fermé contenant $a$. Alors on peut choisir $g' : \N^* \to \N^*$ injective et de même image que $g$ telle que l'ensemble des valeurs d'adhérence de $(g'(n)/f(n))_n$ soit égale à $A$.
Preuve. Soit $(x_n)_n$ une suite dont l'ensemble des valeurs d'adhérence soit $A$. Par injectivité, $g(n)$ tend vers l'infini. Soit $n_0$ très grand. On a donc $g(n_0)/f(n_0)$ très proche de $a$. En échelle logarithmique, $g(n_0), g(n_0+1), g(n_0+2), \dots$ avance par incréments bornés et tend vers l'infini, donc on peut choisir $m_0>n_0$ tel que $g(m_0)/f(n_0)$ est très proche de $x_0$. Si on n'est pas assez proche, on prend $n_0$ encore plus grand de sorte à ce que l'incrément logarithmique entre $g(n_0+i)$ et $g(n_0+i+1)$ soit assez petits. Mais pour faire ça précisément, il faut faire des calculs...
Une fois qu'on a ce $n_0$ et ce $m_0$, on définit $g'$ partiellement par :- $g'(n) = g(n)$ pour $n<n_0$,
- $g'(n_0) = g(m_0)$
- $g'(k) = g(k-1)$ pour $n_0<k\geq m_0$
La suite $(g'(n)/f(n))_n$ se partitionne en deux sous-suites : celle constituée des indices $n$ tels que $g'(n)$ a été définie comme étant égal à $g(n)$ ou $g(n-1)$, et celle constituée des indices $n$ tels que $g'(n)$ a été définie comme un certain $g'(m)$ de sorte à rendre $g'(n)/f(n)$ proche d'un certain $x_i$. La première sous-suite converge vers $a$ et la deuxième a les mêmes valeurs d'adhérence que $x_i$, donc on a bien ce qu'on veut.
On peut appliquer ce lemme aux deux sous-suites de l'identité constituées des nombres pairs d'une part et des nombres impairs d'autre part, afin de construire des suites dont l'adhérence est n'importe quel $B$ fermé contenant $1$.
Explicitement, on applique le lemme avec
1) $f(n) = 2n = g(n)$ avec $A=[1,+\infty]\cap B$ pour avoir $g'(n)$,
2) $f(n) = 2n+1 = g(n)$ avec $A=[1,+\infty]\cap \{1/b\mid b\in B\}$ pour avoir $g''(n)$.
Puis on définit $\sigma(2n) = g(n)$ et $\sigma(g''(n)) = 2n+1$.
Ce lemme peut aussi s'appliquer à la construction avec les suites de $+$ et de $-$. Mais franchement je ne sais pas si ça vaut le coup de rédiger ça. C'est beaucoup de complexité pour pas grand chose, non ? -
Champ-Pot-Lion : Je trouve plus clair de présenter les choses ainsi. Je vois mieux ce qui se passe. Effectivement, ça marche bien comme ça ; mais tant que je n'ai pas de construction suffisamment complète sous les yeux, j'ai des doutes.
-
Tu comptes poster ta solution, Calli ?
Ça vaut le coup que je rédige pour le cas où $A_\sigma$ ne contient par $1$ ? -
Oui, je finirai par poster ce que j'ai fait, quoique ça n'est pas plus intelligent que ce que vous avez trouvé.
Comme tu veux pour ta seconde question (moi ça m'intéresse). -
Bonjour
une idée pour trouver un $\sigma$ avec un $A_{\sigma}$ égal à $[0;+\infty[$:
on prend l'ensemble dénombrable des droites passant par (0,0) qui passent par un point à coordonnée entière, ceux les droites à pentes rationnelles.
Pour tout rationnel positif on prend une suite infinie de points où les distances entre les abscisses consécutives augmentent indéfiniment et strictement, on retire ces abscisses ,
il reste alors encore une infinité de points pour toutes les autres droites à pentes rationnelles, et on réitère, avec les points restants.
Pour s'assurer que c'est bien une bijection de $\mathbb{N}$ on impose dans la construction que toutes les ordonnées sont atteintes, je ne sais si le raisonnement est correct. ( et ce n'est qu'une réécriture partielle de quelques idées déjà mentionnées dans ce fil )
bien sûr la droite y=x y joue un rôle particulier , d'une certaine façon , c'est elle qui impose le fait que 1 est compris entre les liminf et limsup de $A_{\sigma}$ , dans la contrainte passer par toutes les abscisses puis récupérer toutes les ordonnées. -
Bonjour callipiger,
SI j'ai bien compris ton application envoies les abscisses de certains points sur leur ordonnée. Comment est-tu sûr d’obtenir une surjection ? -
oui Calli
Justement je ne sais pas construire la surjection, et je me demande si il y a une façon de l'obtenir quitte à reconstruire les termes précédents , l'idée était d'utiliser la densité des points rationnels du cercle unité dans le cercle unité, mais oui le côté surjectif n'est pas assuré du tout dans cette construction , mais je voulais tenter cette direction là , et je voudrais penser aux "coordonnées rationnelles du "cercle à l'infini" " , en gros assurer la surjection pour une partie finie et passer à la limite ... :-S je ne prétends pas avoir construit , juste partagé une idée.
en revanche le procédé est bon pour exhiber une involution de $\mathbb{N}$ avec les extémités Nord-Ouest et Sud-Est échangées de carrés dont une diagonale est sur la droite y=x, il suffit juste que les autres diagonales soient supportées par des droites strictement parallèles , où la liminf est $ a \in \mathbb{Q}<1$ et la limsup est $b=\frac{1}{a}$
nouvel edit:
Finalement je réalise que l'on peut obtenir de cette façon une involution de $\mathbb{N}$ avec deux involutions qui permutent, pourvu que les support des couples de valeur échangées soient disjoints , et quitte à indexer les longueurs des carrés par des multiples de nombres premiers , pour chaque involution qui permute 2 limites ... on peut une involution pour toute les valeurs de $\mathbb{Q}$ -
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. -
Champ-Pot-Lion : Ah... Je n'avais pas vu que le lemme permet aussi de perturber comme on le souhaite le $\sigma$ tel que $A_\sigma =\{a,b\}$. Je pensais qu'on aurait besoin d'encore autre chose. Il est bien pratique ce lemme, assez polyvalent. (tu)
Pour moi tu as bouché tous les trous (si je puis dire) de ta preuve ! (:Dcallipiger a écrit:en revanche le procédé est bon pour exhiber une involution de $\mathbb{N}$ avec les extémités Nord-Ouest et Sud-Est échangées de carrés dont une diagonale est sur la droite y=x, il suffit juste que les autres diagonales soient supportées par des droites strictement parallèles , où la liminf est $ a \in \mathbb{Q}<1$ et la limsup est $b=\frac{1}{a}$
Je n'ai pas compris callipiger.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 164.7K Toutes les catégories
- 44 Collège/Lycée
- 22.1K Algèbre
- 37.4K Analyse
- 6.3K Arithmétique
- 57 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 19 CultureMath
- 49 Enseignement à distance
- 2.9K Fondements et Logique
- 10.6K Géométrie
- 80 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 73 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 331 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 792 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres