Asymptotique d'une bijection de $\Bbb N^*$
Réponses
-
En tout cas, bravo à tous ! :-)
-
(tu)
-
voilà l'explication un peu mieux écrite , j'ai pris a=2
les suites géométriques $(a_n), a_n=a.(2^2)^n$ et $(b_n), b_n=a^2.(2^2)^n$ définissent les sommets d'un carré et ces deux suites n'ont pas de valeurs communes, chaque carré définit une transposition, qui commute avec toutes les autres
et ces suites ne recouvrent pas $\mathbb{N}$ sur ce schéma la transposition permute les sommets oranges dans chaque carrés. Je pense que l'on peut modifier cela pour toutes les pentes rationnelles et leur inverses, quitte à changer le carré du nombre premier (là j'ai pris 2) pour les homothéties successives . -
Tous et notamment Champ-Pot-Lion : Voilà ce que j'avais fait pour répondre à la dernière question. J'avais écrit cette preuve avant d'initier ce fil car je n'étais suffisamment confiant en elle et j'avais besoin de la mettre au propre pour la vérifier. Le principe de départ est toujours le même : prendre une suite dense dans le fermé voulu. C'est assez long, mais c'est parce que j'ai un peu détaillé. Seul le cas $1.1$ apporte de nouvelles idées ; le reste ne vous dépaysera pas.
C'est partiiiii (:D
$\bullet\ \textbf{Cas 1.1 :}$ Soit $F\subset [0,\infty ]$ fermé tel que $F\cap \,]0,1[\, \neq \varnothing $ et $F\cap \,]1,\infty [\, \neq \varnothing $ et tel que $0$ ou $\infty $ ne sont pas des points isolés (dans le cas où ils sont effectivement dans $F$). Idée : partitionner $\Bbb N^*$ en parties de densité asymptotique $d_k$ (ce seront les $\{a_{k,i}\mid i\in\Bbb N^*\}$) et échanger les entiers entre ces parts. Soient $\ln$ le logarithme prolongé par continuité sur $[0,\infty]$ et :- $(x_{k} )\in (\ln(F)\cap \,[0,+\infty [)^{\mathbb{N}}$ dense dans $\ln(F)\cap [0,+\infty ] $
- $(y_{k} )\in (\ln(F)\cap \,]-\infty ,0])^{\mathbb{N}}$ dense dans $\ln(F)\cap [-\infty ,0] $
Ensuite, soit $a : \mathbb{Z}\times \mathbb{N}^* \rightarrow \mathbb{N}^{*}$ bijective telle que : $\forall (k,i,\ell ,j) \in (\mathbb{Z}\times \mathbb{N}^*)^2 , \frac{i}{d_{k}} < \frac{j}{d_{\ell }} \Rightarrow a_{i,k} < a_{j,\ell }$. Les formules $$\sigma (a_{k,i} ) \triangleq a_{k+1,i} \quad \quad f(a_{k,i} ) \triangleq \frac{i}{d_{k}} \quad \quad r(a_{k,i} ) \triangleq \frac{d_{k} }{d_{k+1}}$$ définissent respectivement une permutation de $\mathbb{N}^*$ et deux fonctions sur $\mathbb{N}^*$. La relation $\frac{i/d_{k+1} }{i/d_{k} } = \frac{d_{k} }{d_{k+1}}$ induit $\frac{f(\sigma (n))}{f(n)} = r(n)$.
On a : $$ \forall x>0, \ \ \# \{(\ell,j)\in \mathbb{Z}\times \mathbb{N}^* \mid \frac{j}{d_\ell} <x\} = \sum _{\ell\in \mathbb{Z}} \lceil xd_\ell -1\rceil \quad \text{ et } \quad \# \{(\ell,j)\in \mathbb{Z}\times \mathbb{N}^* \mid \frac{j}{d_\ell} \leqslant x\} = \sum _{\ell\in \mathbb{Z}} \lfloor {xd_\ell }\rfloor \leqslant x.$$
Donc, en l'applicant à $x\triangleq \frac{i}{d_k}$ : $$\forall(k,i),\ \sum _{\ell \in \mathbb{Z}} \left\lceil \frac{i}{d_{k}} \, d_{\ell } -1 \right\rceil \leqslant a_{k,i} \leqslant \frac{i}{d_{k}} \quad \text{ i.e. } \quad \forall n,\ \sum _{\ell \in \mathbb{Z}} \left\lceil f(n) d_{\ell } -1\right\rceil \leqslant n \leqslant f(n).$$
Or $\displaystyle \sum _{\ell \in \mathbb{Z}} \frac{\lceil xd_{\ell } -1\rceil}x \underset{x\rightarrow \infty }{\longrightarrow} 1$ par cvd et $f(n) \rightarrow \infty $, donc $n \sim f(n)$. De même, $\sigma (n) \sim f(\sigma (n))$ car $\sigma (n) \rightarrow \infty $. D'où $\frac{\sigma (n)}{n} \sim r(n)$, puis $( \frac{\sigma (n)}{n} )$ et $(r(n))$ ont les mêmes valeurs d'adhérence. Or $\frac{d_{k} }{d_{k+1}} = e^{x_{k}} \text{ ou } e^{y_{-k-1}}$ (suivant le signe de $k$), donc cette adhérence est $F$.
$\bullet\ \textbf{Cas 1.2 :}$ Soit $F\subset [0,\infty ]$ fermé tel que $F\cap \,]0,1[\, \neq \varnothing $ et $F\cap \,]1,\infty [\, \neq \varnothing $ tel que $0$ ou $\infty$ est un point isolé de $F$. Par exemple, si $\infty$ est un point isolé, on veut l'ajouter à la construction précédente. Soit $\sigma $ donnée par le point précédent pour $\overline{F \setminus \{0,\infty \}}$. Il existe deux uniques bijections croissantes : $$\left\{ \begin{array}{cccc} \varphi :& A_{2} \triangleq \mathbb{N}^* \setminus \{m^2 \mid m\in \mathbb{N}^*\} &\rightarrow & \mathbb{N}^* \\
\psi :& \mathbb{N}^* &\rightarrow & A_{3} \triangleq \mathbb{N}^* \setminus \{m^{3} \mid m\in \mathbb{N}^*\} \end{array} \right.$$
On pose : $$\tau : \left\{ \begin{array}{ccc} m^2 &\mapsto & m^{3} \\
n\in A_{2} &\mapsto & \psi \circ \sigma \circ \varphi (n) \in A_{3} \end{array} \right.$$
$\forall n, |\varphi (n)-n|\leqslant \sqrt{\varphi (n)} \text{ et } |\psi (n)-n|\leqslant \sqrt[3]{n}$ donc $\frac{\tau (n)}{n} \underset{n\in A_{2} }{\sim } \frac{\sigma (\varphi (n))}{\varphi (n)}$. Et $\frac{\tau (m^2 )}{m^2 } \rightarrow \infty $, donc on a ajouté $\infty $ à l'adhérence. Et on n'a pas enlevé de valeur d'adhérence $a\in F \setminus \{0,\infty \}$ car $A_{2}$ est de densité asymptotique 1 tandis que, pour tout point $b$ arbitrairement proche de $a$, il existe une suite extraite de $( \frac{\sigma (n)}{n} )$ convergeant vers $b$ et dont le support est de densité asymptotique non nulle (un $\{a_{k,i}\mid i\in\Bbb N^*\}$ de densité $d_{k}$ par construction).
De même, en envoyant $m^{5}$ sur $m^{4}$ on peut ajouter la valeur d'adhérence 0 si besoin (sans perdre la valeur d'adhérence $\infty $ car $m^{5} \gg m^{3}$).
$\bullet\ \textbf{Cas 2.1 :}$ Soit un fermé $1\in F\subset [1,\infty ]$ tel que $\infty $ n'est pas un point isolé. Soit $(r_{n} )\in ([1,+\infty[)^{\mathbb{N}}$ dont $F$ est l'ensemble des valeurs d'adhérence. Soient $A_{2}$ défini ci-dessus et $A'=\mathbb{N}^* \setminus \{\lceil r_{m} m^2 \rceil \mid m\in \mathbb{N}^* \}$. Soit $\sigma \in \mathfrak{S}(\mathbb{N}^*)$ telle que $\forall m\in \Bbb N^* ,\sigma (m^2 )= \lceil {r_{m} m^2 }\rceil $ et $\sigma _{|A_{2}} ^{|A'}$ est une bijection croissante. En réalité, il faut faire attention au fait que certains $\lceil {r_{n} m^2 }\rceil $ tombant ex æquo peuvent obliger à décaler une partie des $\sigma(m)$ ; mais ce n'est pas très grave car, les $r_n$ étant tous $\geqslant 1$, on n'a jamais plus de $m =o( m^2)$ ex æquo en même temps, donc $\{\sigma(m^2)\mid m\in\Bbb N^*\}$ reste de densité asymptotique nulle. Alors $$\left| \frac{\sigma (m^2 )}{m^2 } - r_{n} \right| \leqslant \frac{| \sigma (m^2 ) -\lceil {r_{n} m^2 }\rceil |}{m^2 } + \frac{|\lceil r_{n} m^2 \rceil -r_{n} m^2|}{m^2 } \leqslant \frac{m}{m^2 } + \frac{1}{m^2 } \xrightarrow[m\to\infty]{} 0$$
donc $F$ est l'ensemble des valeurs d'adhérences de $( \frac{\sigma (m^2 )}{m^2 } )$. Pour le reste, le rapport tend vers $1$ car $A_{2}$ et $A'$ sont de densité asymptotique $1$.
$\bullet\ \textbf{Cas 2.2 :}$ Soit un fermé $1\in F\subset [1,\infty ]$ tel que $\infty $ est un point isolé. On prend $\sigma $ donnée par le cas $2.1$ et on lui applique une transformation du même type qu'au cas $1.2$ (le lieu de la transformation doit être un sous-ensemble de $\mathbb{N}^*$ de densité nulle et disjoint de $\{m^2 \mid m\in \mathbb{N}^*\}$).
$\bullet\ \textbf{Cas 2.3 :}$ Soit un fermé $1\in F\subset [0,1]$. $\{A_\sigma \mid\sigma\in\mathfrak{S}(\Bbb N^*)\}$ est stable par inversion car $A_{\sigma ^{-1}} = A_{\sigma } ^{-1} \triangleq \{x^{-1}\mid x\in A_\sigma\}$ (où $x\mapsto x^{-1}$ est prolongée par continuité sur $[0,\infty]$). Donc les cas $2.1$ et $2.2$ résolvent aussi le cas présent.
$\bullet\ \textbf{Cas 3.1 :}$ Soit un fermé $F$ qui est la réunion de $\{\infty \}$ et d'un fermé de $[0,1]$ qui contient $1$. Prendre le fermé du cas $2.3$ et lui ajouter $\infty$ comme en $1.2$ résout l'affaire.
$\bullet\ \textbf{Cas 3.2 :}$ Soit un fermé $F$ qui est la réunion de $\{\infty \}$ et d'un fermé de $[0,1]$ qui ne contient pas $1$. Soient $\alpha \triangleq \max ( F\cap [0,1])<1$ et $A\subset \mathbb{N}^*$ de densité asymptotique $1-\alpha $. Soit $\sigma _{1}$ l'unique bijection de $\mathbb{N}^*$ coïncidant avec la fonction carré sur $A$ et croissante sur $\mathbb{N}^* \setminus A$. Alors $\frac{\sigma _{1} (n)}{n} \xrightarrow[{n\in A}]{} \infty $ et $\frac{\sigma _{1} (n)}{n} \xrightarrow[{n\not\in A}]{} \alpha $. Puis soit $\sigma _{2}$ telle que $A_{\sigma _{2}} = \frac{1}{\alpha } (F\cap [0,1])$ (donnée par le cas $2.3$). Comme $\sigma _{1} (A)$ est de densité asymptotique nulle, on peut supposer qu'en fait $\sigma _{1} \in \mathfrak{S}(\mathbb{N}^* \setminus A)$ (quitte à bricoler comme en $1.2$). Alors $\sigma = \sigma _{2} \circ \sigma _{1}$ convient.
$\bullet\ \textbf{Cas 3.3 :}$ La remarque en $2.3$ et les cas $3.1$ et $3.2$ permettent de résoudre le cas où $F$ est la réunion de $\{0\}$ et d'un fermé de $[1,\infty ]$. -
callipiger : Ce que tu proposes là a bien l'air de donner une bijection, mais j'ai l'impression que tu n'agis que sur des droites de pente $a^{\pm 1}$, $a\in\Bbb N^*$, i.e. sur un ensemble de droite dont les pentes ne sont pas denses dans $[0,\infty]$. C'est gênant.
Je ne sais pas si peut utiliser ton idée pour créer un $\sigma$ tel que $A_\sigma = [0,\infty]$. Je ne vois pas comment on pourrait faire (ce qui ne dit évidemment pas que c'est impossible). -
À tous,Conjecture a écrit:Soit $F$ un fermé de $[0,\infty]$. Il existe une involution $\sigma\in\mathfrak{S}(\Bbb N^*)$ (i.e. $\sigma^2={\rm id}$) telle que $F=A_\sigma$ si et seulement si $F$ est non vide et stable par inversion (i.e. $\forall x\in [0,\infty], x\in F \Leftrightarrow x^{-1}\in F\}$ où $x\mapsto x^{-1}$ est prolongée par continuité sur $[0,\infty]$).
Il me semble que toutes les idées déjà présentées dans ce fil s'adaptent parfaitement bien pour prouver ça, donc je n'ai pas très envie de le faire plus en détail. 8-) -
Bonsoir à tous,
j'avoue ne pas avoir tout lu le fil bien qu'il soit très intéressant mais je voulais tout de même vous poser une question sur un exemple qui me semble intéressant.
On associe à chaque $n\in\mathbf{N}^*$ l'entier classé à la même position dans l'ordre de Charkovski (voir ici).
Il me semble que l'ensemble des valeurs d'adhérences est "très grand" mais je n'arrive pas à le prouver ; auriez-vous des idées ? -
Bonsoir totocov,
Tu veux envoyer $n$ sur le $n$-ième entier dans l'ordre de Charkovski ? Ce ne sera pas une surjection car, par exemple, 6 ne sera pas atteint puisqu'il est précédé d'une infinité de nombres (tous les nombres impairs). -
Bonsoir Calli,
Je viens de voir ton message, merci. Je le lirai demain.
Pour la conjecture que tu donnes, en effet elle est vraie. En tout cas je crois qu'on obtient une preuve en modifiant un peu ce que j'ai donné (je n'ai pas regardé en détail mais j'imagine que dans la construction avec les suites de $+$ et de $-$, quand $a=b^{-1}$, on va pouvoir prendre deux fois la même suite, ce qui produira une involution).
Quels sont les $A_{\sigma}$ si on demande que $\sigma^3 = \operatorname{id}$ ? Et si on demande que $\sigma$ soit d'ordre fini ? -
Bonjour,
J'ai modifié mes trucs d'avant , et j'ai essayé d'écrire proprement ...
Lemme (existence d’une involution $\sigma$ de $\mathbb{N} $ telle que $A_{\sigma}$ soit $\{a,a^{-1}\}$ avec $a \in \mathbb{Q}$)
Pour $a=\frac{q}{p}$ avec $ p,q \in \mathbb{N^*} $ et $b=a^{-1}$ où $\frac{q}{p}$ est la fraction irréductible qui représente $a$ il existe une permutation $\sigma$ d’ordre 2 de $\mathbb{N}$ ayant pour $A_{\sigma}$ l'ensemble $\{a,b\}$
preuve : $\sigma$ étant d’ordre 2 c’est un produit de transpositions de $\mathbb{N}$ à supports disjoints .
Définissons la transposition de $\mathbb{N}$ , $\sigma_{a_{k}}$ avec $\sigma_{a_{k}}(kp)=kq$ et donc $\sigma_{a_{k}}(kq)=kp$ ,
supposons qu’il existe un ensemble d’entiers de cardinal $2l$ i.e $\{k_1p,k_1q,…,k_lp,k_lq\}$ dès lors $\prod_{k’\in \{k_1,...k_l\}}\sigma_{a_{k’}}$ est une involution de $\mathbb{N}$.
Il existe un tel ensemble de cardinal 2 , il suffit de prendre $k=1$.
On peut rajouter les éléments $Kp,Kq$ à $\{k_1p,k_1q,…,k_lp,k_lq\}$ de façon à obtenir une famille de cardinal $2l+2$ il suffit de prendre
$K \in \mathbb{N}$ avec $K \geq max(k_1p,k_1q,…,k_lp,k_lq)+1]$ et l’on pose $K=k_{l+1}$
la suite $(max(k_1p,k_1q,…,k_lp,k_lq))_{l}$ a pour limite $+\infty$, donc $\sigma=\prod_{i=1}^{\infty}\sigma_{a_{k’}}$ vérifie ce qui est demandé pour le lemme.
je voudrais répondre au problème posé par CalliConjecture a écrit:Soit $F$ un fermé de $[0,\infty]$. Il existe une involution $\sigma\in\mathfrak{S}(\Bbb N^*)$ (i.e.$\sigma^2={\rm id}$) telle que $F=A_\sigma$ si et seulement si $F$ est non vide et stable par inversion (i.e. $\forall x\in [0,\infty], x\in F \Leftrightarrow x^{-1}\in F\}$ où $x\mapsto x^{-1}$ est prolongée par continuité sur$[0,\infty]$). -
Bonjour,
Je tente de rebondir sur la question de Champ-pot-lion (Quels sont les $A_\sigma$ si $\sigma$ est d'ordre fini?).
En faisant un petit raisonnement à base de $\overline{\mathbb{R}^+}$ compact, de suite extraite et d'un peu d'absurde et de propriété comme "toute partie de $\mathbb{N}$ majorée est finie" et en récurrant un peu (avec deux "r", pas un seul, j'ai fini mon ménage), on peut montrer le truc suivant:
$\forall x, \sigma$ ($\sigma$ d'ordre $n$), $x\in A_\gamma$ implique qu'il existe $\phi$ application strictement croissante de $\mathbb{N}^*$ dans lui même, tel que, $\forall k <n$, $\sigma^k\circ \phi$ est (strictement) croissante et $\forall k\in |[0,n-1]| $, $(\left(\frac{(\sigma^{k+1}\circ \phi) (m)}{(\sigma^k\circ \phi)(m)} \right)_{m\in\mathbb{N}^*}$ converge.
De là, on attrape cette propriété: si $\sigma$ est d'ordre $n$ et $x\in A_\sigma$, il existe une famille $(x_i)_{i\in |[1,n]|}$ d'éléments de $A_\sigma$ telle que $\exists i\in |[1,n]|, x=x_i$ et $\displaystyle \prod_{i=1}^n x_i = 1$.
En ce qui concerne la démonstration de la réciproque (tout fermé tel que la dernière propriété est un $A_\sigma$), je parie très fort sur sa véracité, mais ça a l'air vachement dur. Je jette l'éponge (palsambleu! ce ménage influence encore beaucoup mes expressions). -
Champ-Pot-Lion a écrit:Quels sont les $A_{\sigma}$ si on demande que $\sigma^3 = \operatorname{id}$ ? Et si on demande que $\sigma$ soit d'ordre fini ?
Oula, ça se corse. Une condition nécessaire est que si $A_\sigma\neq\{1\}$, alors $A_\sigma$ n'est inclus ni dans $[0,1]$ ni dans $[1,\infty]$. En effet, si $\sigma^m={\rm id}$ et $\varphi$ est une extractrice telle que $\frac{\sigma(\varphi(n))}{\varphi(n)} \longrightarrow a_0 \neq 1$, alors quitte à réextraire on peut supposer $\forall k\in[\![1,m-1]\!], \exists a_k\in A_\sigma, \frac{\sigma^{k+1}(\varphi(n))}{\sigma^k(\varphi(n))}\longrightarrow a_k$. Puisque $\forall n, \prod\limits_{k=0}^{m-1} \frac{\sigma^{k+1}(\varphi(n))}{\sigma^k(\varphi(n))} =1$, on a deux possibilités :- Soit l'un des $a_k$ est nul et un autre est infini. Dans ce cas c'est bon.
- Soit le produit $\prod\limits_{k=0}^{m-1} a_k$ existe et vaut $1$. Dans ce cas l'un des $a_k$ est strictement de l'autre côté de $1$ que $a_0$.
Edit : J'ai posté presque en même temps que Titi ; je n'avais pas vu son message. Je constate qu'on a dit à peu près la même chose.
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