Soit \( n \in \mathbb{N}^{*} \). Le patron de factorisation de \( n \), que nous noterons \( \mbox{FP}(n) \), s'obtient par la méthode suivante :
Exemple : \[ \mbox{FP}(220) = \mbox{FP}(2^{2} \times 5 \times 11) = p^2 q r \]
Soit \( n \in \mathbb{N}^{*} \). Le patron de factorisation de la suite des diviseurs de \( n \), que nous noterons \( \mbox{FPSD}(n) \), s'obtient par la méthode suivante :
Exemple : \( n = 220 \) a pour liste de diviseurs : \[ L = \{ 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110, 220 \} \] \[ L = \{ 1, 2, 2^2, 5, 2 \times 5, 11, 2^2 \times 5, 2 \times 11, 2^2 \times 11, 5 \times 11, 2 \times 5 \times 11, 2^2 \times 5 \times 11 \} \] L'ensemble de substitutions \( \{ 2 \to p, 5 \to q, 11 \to r \} \) permet d'obtenir : \[ \mbox{FPSD}(220) = \{ 1, p, p^2, q, p q, r, p^2 q, p r, p^2 r, q r, p q r, p^2 q r \} \]
Le patron de factorisation de la suite des diviseurs d'un nombre \( n \) N'EST PAS la liste des patrons de factorisation des diviseurs de \( n \). Pour un \( \mbox{FPSD} \), la substitution "nombre \( \to \) lettre" est la même pour tous les diviseurs de \( n \), et c'est la raison pour laquelle peuvent apparaître des expressions lacunaires, comme \( p r \), où il manque \( q \).
D'aucuns pourraient critiquer le fait qu'un nombre fini de lettres \( (p, q, r, \dots, z) \) est insuffisant. Dans ce cas, il nous suffirait d'utiliser une notation "indicée" à la place.
Exemple : \[ \mbox{FPSD}(220) = \{ 1, p_1, p_1^2, p_2, p_1 p_2, p_3, p_1^2 p_2, p_1 p_3, p_1^2 p_3, p_2 p_3, p_1 p_2 p_3, p_1^2 p_2 p_3 \} \] Autre syntaxe possible, ne garder que les exposants des \( p_i \) : \[ \mbox{FPSD}(220) = \{ (0,0,0), (1,0,0), (2,0,0), (0,1,0), (1,1,0), (0,0,1), (2,1,0), (1,0,1), (2,0,1), (0,1,1), (1,1,1), (2,1,1) \} \]
Nous appellerons dimension d'un nombre entier \( n \in \mathbb{N}^{*} \) (ou d'un \( \mbox{FP} \), ou d'un \( \mbox{FPSD} \)), le nombre \( k \) de nombres premiers distincts qui le composent.
Exemple : \[ \mbox{dim}(12) = \mbox{dim}(p^2 q) = \mbox{dim} \left ( \{ 1, p, q, p^2, pq, p^2 q \} \right ) = 2 \] D'habitude, cette valeur est notée \( \omega(n) \). La justification du terme "dimension" vient de la notation \( \mbox{FPSD}(n) = \{ (0,\dots,0), (1,\dots,0), \dots \} \) où les diviseurs sont représentés par des vecteurs de dimension k (ou des points dans un repère cartésien de dimension \( k \)).
| \[ 1 \] | \[ 1 \] | \[ 11 \] | \[ 1, p \] | \[ 21 \] | \[ 1, p, q, pq \] | \[ 31 \] | \[ 1, p \] |
|---|---|---|---|---|---|---|---|
| \[ 2 \] | \[ 1, p \] | \[ 12 \] | \[ 1, p, q, p^2, pq, p^2q \] | \[ 22 \] | \[ 1, p, q, pq \] | \[ 32 \] | \[ 1, p, p^2, p^3, p^4, p^5 \] |
| \[ 3 \] | \[ 1, p \] | \[ 13 \] | \[ 1, p \] | \[ 23 \] | \[ 1, p \] | \[ 33 \] | \[ 1, p, q, pq \] |
| \[ 4 \] | \[ 1, p, p^2 \] | \[ 14 \] | \[ 1, p, q, pq \] | \[ 24 \] | \[ 1, p, q, p^2, pq, p^3, p^2q, p^3 q \] | \[ 34 \] | \[ 1, p, q, pq \] |
| \[ 5 \] | \[ 1, p \] | \[ 15 \] | \[ 1, p, q, pq \] | \[ 25 \] | \[ 1, p, p^2 \] | \[ 35 \] | \[ 1, p, q, pq \] |
| \[ 6 \] | \[ 1, p, q, pq \] | \[ 16 \] | \[ 1, p, p^2, p^3, p^4 \] | \[ 26 \] | \[ 1, p, q, pq \] | \[ 36 \] | \[ 1, p, q, p^2, pq, q^2, p^2q, pq^2, p^2q^2 \] |
| \[ 7 \] | \[ 1, p \] | \[ 17 \] | \[ 1, p \] | \[ 27 \] | \[ 1, p, p^2, p^3 \] | \[ 37 \] | \[ 1, p \] |
| \[ 8 \] | \[ 1, p, p^2, p^3 \] | \[ 18 \] | \[ 1, p, q, pq, q^2, pq^2 \] | \[ 28 \] | \[ 1, p, p^2, q, pq, p^2q \] | \[ 38 \] | \[ 1, p, q, pq \] |
| \[ 9 \] | \[ 1, p, p^2 \] | \[ 19 \] | \[ 1, p \] | \[ 29 \] | \[ 1, p \] | \[ 39 \] | \[ 1, p, q, pq \] |
| \[ 10 \] | \[ 1, p, q, pq \] | \[ 20 \] | \[ 1, p, p^2, q, pq, p^2q \] | \[ 30 \] | \[ 1, p, q, r, pq, pr, qr, pqr \] | \[ 40 \] | \[ 1, p, p^2, q, p^3, pq, p^2q, p^3 q \] |
Couleur fonction du \( \mbox{FP} \).
Aucune logique n'est apparente de prime abord dans la liste des premiers FPSD, un peu comme pour les nombres premiers. Existe-t-il un ensemble, une structure, qui permettrait d'énumérer les FPSD intelligemment ? J'ai du mal à me satisfaire de méthodes consistant à énumérer les FPSD dans l'ordre de leur découverte, "essayer un nouvel \( n \) et ignorer le FPSD obtenu s'il est déjà connu" comme dans :
| \( n \) | \( \mbox{FP}(n) \) | \( \mbox{FPSD}(n) \) |
|---|---|---|
| 12 | \(p^2q\) | \( (1,p,q,p^2,pq,p^2q) \) |
| 20 | \(p^2q\) | \( (1,p,p^2,q,pq,p^2q) \) |
Existe-t-il d'autres nombres \( n \) dont le FP est \( p^2 q \) et dont le FPSD n'est ni celui de 12, ni celui de 20 ? Dans le cas général, étant donné un FP, combien de FPSD qui lui correspondent peut-on trouver ?
Quand la dimension est égale à 2, les FPSD peuvent être illustrés à l'aide de dessins en zigzag. Exemple :
| \( n \) | \( \mbox{FP}(n) \) | \( \mbox{FPSD}(n) \) |
|---|---|---|
| 12 | \(p^2q\) | |
| 20 | \(p^2q\) |
Cette idée est généralisable à toute dimension \( k \) : un FPSD peut être représenté à l'aide d'un zigzag inscrit dans un parallélotope de dimension \( k \). Ces dessins m'évoquent les courbes de Peano, les courbes qui remplissent l'espace, ... (l'analogie n'est pas très rigoureuse).
Dans les chapitres qui viennent, nous allons essayer de déterminer le nombre de FPSD distincts qui ont le même FP. Nous procéderons par ordre croissant de la dimension.
Nous pourrions, peut-être, attaquer d'entrée de jeu le cas général, mais je pense que commencer de manière modeste nous aidera à nous forger une intuition.
\( k = 0 \) implique \( n = 1 \), dont le FPSD est (1). Le nombre de FPSD distincts pour \( k = 0 \) est donc 1.
\( k = 1 \) implique que \( n \) est de la forme \( p ^ \alpha \), avec \( p \) premier, et \( \alpha \) valuation \(p\)-adique de \( n \).
Les diviseurs de \( n \) sont les nombres \( p ^ a \), \( a \) entier, \( 0 \leq a \leq \alpha \). Il n'y a qu'une seule façon d'ordonner ces nombres, c'est : \[ 1 \lt p \lt p^2 \lt \dots \lt p^{\alpha - 1} \lt p ^ \alpha \] Il y a un FPSD pour chaque \( \alpha \) :
Appelons \( f \) la fonction
Les résultats précédents s'écrivent alors :
Attaquons le cas où \( k = 2 \). \( n \) peut s'écrire sous la forme \( p ^\alpha q ^ \beta \).
Prenons un exemple : \( \alpha = 3\) et \( \beta = 2 \). Les diviseurs de \( n \) peuvent être représentés par le graphe suivant :
où une arête d'un noeud D vers un noeud D' signifie : \( \frac{D'}{D} \) est un nombre premier. Par transitivité, si un chemin existe de D à D', alors D divise D'. Il convient de remarquer que : \[ D | D' \implies D \leq D' \] Une autre information peut être ajoutée à ce graphe : celle comme quoi : \[ p \lt q \] Bien entendu, cette inégalité est compatible avec la multiplication ; nous avons en fait un ensemble d'inégalités équivalentes : \[ p \lt q, pq \lt q^2, p^2 \lt pq, p^2q \lt pq^2, p^3 \lt p^2q, p^3q \lt p^3q^2 \]
On remarque un lien entre :
| Exemple 1 : le fait \( p \lt p^2 q^2 \) est démontrable, et un chemin d'arêtes au trait plein suffit à l'illustrer | Pente positive ou nulle | |
| Exemple 2 : on ne sait pas dire qui de \( pq \) ou de \( p^3 \) est le plus grand | Pente comprise entre -1 et 0 (exclus tous deux) | |
| Exemple 3 : le fait \( p^2 \lt pq^2 \) est démontrable, et tout chemin illustrant ce fait comporte au moins une arête en trait pointillé | Pente comprise entre \( - \infty \) et \( -1 \) (inclus) |
Interprétation qualitative : les "pentes vertes" et les "pentes bleues" représentent des contraintes d'ordre ( \( \lt \) ) entre diviseurs que tous les FPSD de même FP satisfont. Les "pentes rouges" : voilà où se situe notre marge de manoeuvre !
Remarquons aussi qu'on ne change pas la véracité d'une affirmation \( D \lt D' \) en divisant les deux côtés de l'inégalité par le PGCD de D et de D'. Sur le schéma, une telle opération revient à translater le segment de droite qui joint D à D' le plus possible vers l'angle inférieur gauche. La pente du segment reste inchangée et sa "couleur" (vert | rouge | bleu), de ce fait, également.
Lorsqu'ils sont "rouges", les segments translatés ainsi obtenus, avec une extrêmité sur chaque axe de coordonnées, peuvent alors être vus comme des tentatives de comparaison entre des \( p^a \) et des \( q^b \) aux ingrédients antagonistes,
L'idée est maintenant qu'à \(a\) et \( b \) fixés, nous pouvons choisir \( p \) et \( q \). Et,
La fonction logarithme s'impose pour passer d'un graphe de diviseurs à un schéma où les exposants croissent linéairement avec les coordonnées cartésiennes.
Mais comparer \( p^a \) et \( q^b \) revient à comparer \( a \ln(p) \) et \( b \ln(q) \), ou, ce qui revient au même (si l'on suppose que \( a \neq 0 \)), à comparer \[ - \frac{b}{a} \longleftrightarrow - \frac{\ln(p)}{\ln(q)} \] Or, \( - \frac{b}{a} \) est la pente du segment de droite qui relie \( (a, 0) \) à \( (0, b) \). En supposant que ce segment est rouge,
Les valeurs \( - \frac{b}{a} \) jouant le rôle de valeurs-seuil pour la quantité \( - \frac{\ln(p)}{\ln(q)} \), il existe autant de FPSD que de subdivisions de l'intervalle \( \left] -1, 0 \right[ \) par des valeurs \( - \frac{b}{a} \)
Après élimination du signe "moins" et reformulation : il y a autant de FPSD qu'il y a d'intervalles \( \left] \frac{b_1}{a_1}, \frac{b_2}{a_2} \right[ \) inclus dans \( \left] 0, 1 \right[ \).
Pour affirmer cela, nous devons admettre l'hypothèse que l'ensemble des nombres premiers est suffisamment "riche" pour que, quelles que soient les deux fractions \( \frac{b_1}{a_1} \) et \( \frac{b_2}{a_2} \) rangées dans cet ordre, l'on puisse toujours choisir \( p \) et \( q \) premiers satisfaisant : \[ \frac{b_1}{a_1} \lt \frac{\ln(p)}{\ln(q)} \lt \frac{b_2}{a_2} \] (en d'autres termes, nous admettons que tout FPSD a des représentations concrètes) (cf. cette conversation sur Mathematics Stack Exchange et des preuves proposées par d'autres personnes).
L'intervalle des pentes \( \left] 0, 1 \right[ \), se subdivise en 6 sous-intervalles délimités par 5 valeurs-seuil \( \{ \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4} \} \). Il est possible de trouver des couples de nombres premiers \( (p, q) \), comme par exemple ceux représentés sur le schéma ci-dessus par des points "p&q" de coordonnées \( (\ln(q), \ln(p) ) \), tels que le ratio \( \frac{\ln(p)}{\ln(q)} \) appartienne à chacun de ces sous-intervalles.
| Borne min de l'intervalle | Borne max de l'intervalle | Un couple \( (p,q) \) représentatif | Ratio \( \frac{\ln(p)}{\ln(q)} \) | Nombre \(n\) | FPSD |
|---|---|---|---|---|---|
| \( 0 = 0. \) | \( \frac{1}{4} = 0.25 \) | \( (2, 29) \) | \( \frac{\ln(2)}{\ln(29)} = 0.205... \) | \( n = 390224 = 2^4 \times 29^3 \) | \( (1, p, p^2, p^3, p^4, q, p q, p^2 q, p^3 q, p^4 q, q^2, p q^2, p^2 q^2, p^3 q^2, p^4 q^2, q^3, p q^3, p^2 q^3, p^3 q^3, p^4 q^3) \) |
| \( \frac{1}{4} = 0.25 \) | \( \frac{1}{3} = 0.333... \) | \( (2, 13) \) | \( \frac{\ln(2)}{\ln(13)} = 0.270... \) | \( n = 35152 = 2^4 \times 13^3 \) | \( (1, p, p^2, p^3, q, p^4, p q, p^2 q, p^3 q, q^2, p^4 q, p q^2, p^2 q^2, p^3 q^2, q^3, p^4 q^2, p q^3, p^2 q^3, p^3 q^3, p^4 q^3) \) |
| \( \frac{1}{3} = 0.333... \) | \( \frac{1}{2} = 0.5 \) | \( (2, 5) \) | \( \frac{\ln(2)}{\ln(5)} = 0.430... \) | \( n = 2000 = 2^4 \times 5^3 \) | \( (1, p, p^2, q, p^3, p q, p^4, p^2 q, q^2, p^3 q, p q^2, p^4 q, p^2 q^2, q^3, p^3 q^2, p q^3, p^4 q^2, p^2 q^3, p^3 q^3, p^4 q^3) \) |
| \( \frac{1}{2} = 0.5 \) | \( \frac{2}{3} = 0.666... \) | \( (3, 7) \) | \( \frac{\ln(3)}{\ln(7)} = 0.564... \) | \( n = 27783 = 3^4 \times 7^3 \) | \( (1, p, q, p^2, pq, p^3, q^2, p^2 q, p^4, p q^2, p^3 q, q^3, p^2 q^2, p^4 q, p q^3, p^3 q^2, p^2 q^3, p^4 q^2, p^3 q^3, p^4 q^3) \) |
| \( \frac{2}{3} = 0.666... \) | \( \frac{3}{4} = 0.75 \) | \( (3, 5) \) | \( \frac{\ln(3)}{\ln(5)} = 0.682... \) | \( n = 10125 = 3^4 \times 5^3 \) | \( (1, p, q, p^2, pq, q^2, p^3, p^2 q, p q^2, p^4, q^3, p^3 q, p^2 q^2, p q^3, p^4 q, p^3 q^2, p^2 q^3, p^4 q^2, p^3 q^3, p^4 q^3) \) |
| \( \frac{3}{4} = 0.75 \) | \( 1 = 1. \) | \( (5, 7) \) | \( \frac{\ln(5)}{\ln(7)} = 0.827... \) | \( n = 214375 = 5^4 \times 7^3 \) | \( (1, p, q, p^2, p q, q^2, p^3, p^2 q, p q^2, q^3, p^4, p^3 q, p^2 q^2, p q^3, p^4 q, p^3 q^2, p^2 q^3, p^4 q^2, p^3 q^3, p^4 q^3) \) |
Conclusion de cet exemple, \[ f(4,3) = 6 \]
On peut voir pentes et fractions comme des paires d'entiers \( (a, b) \) telles que \( \mbox{PGCD}(a, b) = 1 \). Ainsi, le nombre de FPSD qui partagent le même FP égal à \( p^\alpha q^\beta \) est le cardinal de l'ensemble : \[ S_{\alpha, \beta} = \{ (a, b) \in \mathbb{N}^2; 1 \leq a \leq \alpha, 1 \leq b \leq \beta, a \geq b, \mbox{PGCD}(a, b) = 1 \} \]
Exemple d'implémentation (Mathematica) :
Generate[alpha_, beta_] :=
Flatten[Table[List[a, b], {a, 1, alpha}, {b, 1, beta}], 1]
TestQ[{a_, b_}] :=
(a >= b) && (GCD[a, b] == 1)
F[alpha_, beta_] :=
Select[Generate[alpha, beta], TestQ] // Length
Table[F[alpha, beta], {alpha, 1, 10, {beta, 1, 10}] // MatrixForm
Résultat :
| \(\beta \to \) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| \(\alpha \) | ||||||||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| 4 | 4 | 5 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
| 5 | 5 | 7 | 9 | 10 | 10 | 10 | 10 | 10 | 10 | 10 |
| 6 | 6 | 8 | 10 | 11 | 12 | 12 | 12 | 12 | 12 | 12 |
| 7 | 7 | 10 | 13 | 15 | 17 | 18 | 18 | 18 | 18 | 18 |
| 8 | 8 | 11 | 15 | 17 | 20 | 21 | 22 | 22 | 22 | 22 |
| 9 | 9 | 13 | 17 | 20 | 24 | 25 | 27 | 28 | 28 | 28 |
| 10 | 10 | 14 | 19 | 22 | 26 | 27 | 30 | 31 | 32 | 32 |
Remarquer que la diagonale de ce tableau, \[ 1, 2, 4, 6, 10, 12, 18, 22, 28, 32, \dots \] est la suite des sommes de la fonction indicatrice d'Euler, \[ f(\alpha, \alpha) = \sum_{a = 1}^\alpha \phi(a) \] Cette suite est référencée A002088 sur OEIS.
Abordons le cas \( k = 3 \). \(n\) peut être écrit sous la forme : \( p^\alpha q^\beta r^\gamma \).
Considérons l'exemple \( n = p^2 q r \). Pour quels couples de diviseurs \( (d, d') \) de \( n \) sommes-nous capables d'affirmer l'une des 3 propositions suivantes :
? Si l'une de ces 3 propositions est affirmable, nous dirons que \(d\) et \(d'\) sont comparables ; dans le cas contraire, que \(d\) et \(d'\) sont incomparables. (Attention, ces définitions de "comparable" et "incomparable" sont un abus de langage par rapport aux définitions usuelles ; le sens que nous venons de donner reste spécifique à notre contexte). On peut dresser un tableau :
| \(1\) | \(p\) | \(q\) | \(r\) | \(p^2\) | \(pq\) | \(pr\) | \(qr\) | \(p^2q\) | \(p^2r\) | \(pqr\) | \(p^2qr\) | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(1\) | = | < | < | < | < | < | < | < | < | < | < | < |
| \(p\) | > | = | < | < | < | < | < | < | < | < | < | < |
| \(q\) | > | > | = | < | ? | < | < | < | < | < | < | < |
| \(r\) | > | > | > | = | ? | ? | < | < | ? | < | < | < |
| \(p^2\) | > | > | ? | ? | = | < | < | < | < | < | < | < |
| \(pq\) | > | > | > | ? | > | = | < | < | < | < | < | < |
| \(pr\) | > | > | > | > | > | > | = | < | ? | < | < | < |
| \(qr\) | > | > | > | > | > | > | > | = | ? | ? | < | < |
| \(p^2q\) | > | > | > | ? | > | > | ? | ? | = | < | < | < |
| \(p^2r\) | > | > | > | > | > | > | > | ? | > | = | < | < |
| \(pqr\) | > | > | > | > | > | > | > | > | > | > | = | < |
| \(p^2qr\) | > | > | > | > | > | > | > | > | > | > | > | = |
Certains couples de diviseurs incomparables \( ( d, d' ) \) satisfont la propriété \( \mbox{PGCD}(d, d') \neq 1 \), comme par exemple \( ( p^2q, pr ) \). Ils ne sont pas très intéressants, car n'apportent pas d'information par rapport à leurs équivalents réduits (\( ( pq, r ) \)). Oublions-les, pour le moment. De même, si \( (d, d') \) est un couple de diviseurs incomparables, alors \((d', d)\) en est un. Finalement, ce qu'il reste à étudier sont des paires réduites de diviseurs. Ici, il en reste 4 :
\[ \{p^2, q\}, \{p^2, r\}, \{ pq, r \}, \{ p^2q, r \} \]Avec une utilisation intuitive du symbole \( \gtrless \) pour signifier "on ne sait pas si c'est \( \lt \), \( = \) ou \( \gt \)", on peut dire que ces paires d'incomparables reviennent à se demander si :
Enhardis par nos expérimentations en dimension 2, prenons le logarithme de ces expressions. Nous obtenons :
Supposons nous libres de choisir continûment \( \ln(p) \), \( \ln(q) \) et \( \ln(r) \), en oubliant un instant que \(p\), \(q\) et \(r\) sont des nombres premiers. Nous pourrions noter \( x = \ln(p) \), \( y = \ln(q) \) et \( z = \ln(r) \). Il serait possible d'atteindre l'égalité ( \(\gtrless\) remplacé par \(=\) ). Ecrivons cela :
Ces équations sont des équations de plans. Ces plans sont des délimiteurs de régions, en dimension 3, de la même manière que des droites étaient les délimiteurs de régions, en dimension 2 tout à l'heure. Il est relativement difficile de visualiser du 3D, mais il y a une chose que nous pouvons faire :
Considérons l'intersection des plans (vectoriels) précédents avec le plan \( P \) (affine) d'équation
\[ x + y + z = 1 \]
et soient \( A, B, C, G \) les points de coordonnées \( (1, 0, 0) \), \( (0, 1, 0) \), \( (0, 0, 1) \) et \( ({1 \over 3}, {1 \over 3}, {1 \over 3}) \).
Dans le repère \( (G, GB, GC) \) (choisi quelque peu arbitrairement), les équations de plans vectoriels en dimension 3 deviennent des équations de droites affines en dimension 2, avec par exemple Y et Z pour coordonnées :
(je passe les calculs)
\( Y \) et \( Z \) devant satisfaire \( 0 \leq Y \leq Z \leq 1 - Y \), la simple transcription du fait que \( x \lt y \lt z \). On obtient alors le schéma suivant :
Chaque polygone convexe délimité par ces droites est associé à un FPSD. On voit en un coup d'oeil qu'il y a 7 FPSD distincts dans le cas \( \alpha = 2, \beta = 1, \gamma = 1 \). Autrement dit, \(f(2,1,1) = 7\). Un programmeur réalise assez vite que ce n'est pas une tâche aisée que de compter automatiquement ces polygones, ou (si on revient en 3 dimensions), de compter les régions pyramidales de l'espace dont ces polygones sont la base, et l'origine l'apex.
Deux difficultés sont survenues lors de nos expérimentations en dimension 3 :
Le travail à la main et la visualisation graphique ont leurs limites... surtout si l'on souhaite augmenter la dimension. Nous avons besoin de progresser sur deux aspects :
Supposons que \( n = p q r^2 s t u^2 \) et que nous essayions de comparer les deux diviseurs suivants de \( n \) :
\[ p r^2 u^2 \gtrless qrs \]Pour essayer de prouver que \( p r^2 u^2 \leq qrs \), par exemple, nous pouvons essayer d'apparier les lettres en faisant usage des inégalités \( 1 \lt p \lt q \lt r \lt s \lt t \lt u \) :
| Etape | Progression |
|---|---|
| \( p \) dans \( \underline{p}r^2u^2 \) est plus petit que \( q \) dans \( \underline{q}rs \) | \( \boxed{p} r^2 u^2\) comparé à \( \boxed{q} rs \) |
| Le premier \( r \) dans \( \boxed{p}\underline{r}ru^2 \) est égal à \( r \) dans \( \boxed{q}\underline{r}s \) | \( \boxed{pr} r u^2 \) comparé à \( \boxed{qr}s \) |
| Le deuxième \( r \) dans \( \boxed{pr}\underline{r}u^2 \) est plus petit que \( s \) dans \( \boxed{qr}\underline{s} \) | \( \boxed{pr^2} u^2 \) comparé à \( \boxed{qrs} \) |
Malheureusement, la progression s'arrête là, le premier \( u \) dans \( \boxed{pr^2}\underline{u}u \) n'a aucun homologue possible dans \( \boxed{qrs} \). Essayons plutôt de prouver que \( qrs \leq pr^2u^2 \) :
| Etape | Progression |
|---|---|
| \( q \) dans \( \underline{q}rs \) est plus petit que le premier \( r \) dans \( p \underline{r}ru^2 \) | \( \boxed{q} rs \) comparé à \( p \boxed{r} ru^2 \) |
| \( r \) dans \( \boxed{q}\underline{r}s \) est égal au deuxième \( r \) dans \( p \boxed{r}\underline{r}u^2 \) | \( \boxed{qr} s \) comparé à \( p \boxed{r^2} u^2 \) |
| \( s \) dans \( \boxed{qr}\underline{s} \) est plus petit que le premier \( u \) dans \( p \boxed{r^2}\underline{u}u \) | \( \boxed{qrs} \) comparé à \( p \boxed{r^2u} u \) |
Et c'est gagné ! Les lettres du comparande de gauche ont toutes été "consommées" par des homologues dans le comparande de droite. Et ainsi, \( qrs \leq pr^2u^2 \) a été prouvé.
Une autre façon d'aborder le critère de comparabilité est de dire que \( qrs \gtrless pr^2q^2 \) est équivalent à :
\[ p^{+1} q^{-1} r^{+1} s^{-1} t^{0} u^{+2} \gtrless 1 \]ce qui peut être schématisé comme suit ("un profil en long") :
L'algorithme d'appariemment du paragraphe précédent a sa représentation graphique sur ce schéma : pour que \( qrs \leq pr^2u^2 \) soit prouvable, chaque descente doit être (au moins) compensée par une montée située sur sa droite. En termes imagés : à chaque fois que l'on descend, le nécessaire doit être fait par la suite pour remonter suffisamment, pour rétablir, avant la fin, (au moins) l'altitude que l'on avait avant de descendre. En d'autres termes, l'altitude au point d'arrivée U doit être un maximum global, son altitude doit être supérieure ou égale aux altitudes des points O, P, Q, R, S, T situés sur sa gauche.
Les altitudes des points du schéma précédent sont :
| O | \( 0 = \) |
|---|---|
| P | \( 1 = +1 \) |
| Q | \( 0 = +1 -1 \) |
| R | \( 1 = +1 -1 +1 \) |
| S | \( 0 = +1 -1 +1 +1 \) |
| T | \( 0 = +1 -1 +1 +1 +0 \) |
| U | \( 2 = +1 -1 +1 +1 +0 +2 \) |
Elles sont les sommes partielles de la série constituée des valuations présentes dans \( p^{+1} q^{-1} r^{+1} s^{-1} t^0 u^{+2} \) :
\[ y_j = \sum_{i=1}^j \overline{a}_i \]avec
\[ \overline{a}_i = a_i - a'_i \]où les \( a_i \) sont les valuations dans le comparande de gauche \( (qrs) \), et les \( a'_i \) les valuations dans le comparande de droite \( (pr^2q^2) \).
Soit un nombre entier \( n \) et soient \( d \) et \( d' \) deux diviseurs de \( n \). On pose :
\[ n = \prod_{i=1}^k p_i ^ {\alpha_i} \] \[ d = \prod_{i=1}^k p_i ^ {a_i} \] \[ d' = \prod_{i=1}^k p_i ^ {a'_i} \]\( d \) et \( d' \) sont comparables et l'on sait que \( d \leq d' \) si et seulement si
\[ \forall j \in \{ 1, \dots, k \}, \sum_{i=1}^j (a_i - a'_i) \leq \sum_{i=1}^k (a_i - a'_i) \]De même, \( d \) et \( d' \) sont comparables et l'on sait que \( d \geq d' \) si et seulement si
\[ \forall j \in \{ 1, \dots, k \}, \sum_{i=1}^j (a_i - a'_i) \geq \sum_{i=1}^k (a_i - a'_i) \]\( d \) et \( d' \) seront incomparables si les 2 critères ci-dessus sont niés simultanément :
\[ \neg \left( \forall j \in \{ 1, \dots, k \}, \sum_{i=1}^j (a_i - a'_i) \leq \sum_{i=1}^k (a_i - a'_i) \right) \land \neg \left( \forall j \in \{ 1, \dots, k \}, \sum_{i=1}^j (a_i - a'_i) \geq \sum_{i=1}^k (a_i - a'_i) \right) \]ce qui peut s'écrire aussi :
\[ \bbox[white, 10px, border: 3px solid black]{ \left( \exists j_1 \sum_{j_1 \lt i \leq k} a_i \lt \sum_{j_1 \lt i \leq k} a'_i \right) \land \left( \exists j_2 \sum_{j_2 \lt i \leq k} a_i \gt \sum_{j_2 \lt i \leq k} a'_i \right) } (1) \] Les paires d'incomparables \( \{ d, d' \} \) fourniront des hyperplans qui délimiteront des régions de même \( \mbox{FPSD} \) dans l'espace de dimension \( k \).Soit un \( FP \) défini par la décomposition en facteurs premiers symbolique :
\[ n = \prod_{i=1}^k p_i ^ {\alpha_i} \]Nos artifices de calcul introduisent des diviseurs de ce \( n \),
\[ d = \prod_{i=1}^k p_i ^ {a_i} \] \[ d' = \prod_{i=1}^k p_i ^ {a'_i} \]avec
\[ (a_i, a'_i) \in \{ 0, \dots, \alpha_i \}^2 \]On peut écrire :
\[ \frac{d}{d'} = \prod_{i=1}^k p_i^{a_i-a'_i} \] \[ \ln \left( \frac{d}{d'} \right) = \sum_{i=1}^k (a_i-a'_i) \ln\left(p_i\right) \]Le FPSD de \( n \) change à chaque fois que \( d \lt d' \) se transforme en \( d \gt d' \). Si nous étions libres de choisir continûment les \( p_i \) pour atteindre l'égalité, alors nous aurions :
\[ 0 = \sum_{i=1}^k (a_i-a'_i) x_i \]où les \( x_i \) sont des coordonnées dans lesquelles les \( \ln(p_i) \) évoluent. Les \( x_i \) partagent avec les \( p_i \) la propriété :
\[ 0 \lt x_1 \lt x_2 \lt \dots \lt x_k \]Cette propriété définit une région \( R \) de \( \mathbb{R}^k \). Nous pouvons définir :
\[ \overline{a_i} = a_i - a'_i \]avec
\[ \overline{a_i} \in \{ -\alpha_i, \dots, \alpha_i \}^2 \]On obtient :
\[ \sum_{i=1}^k \overline{a}_i x_i = 0 \]Le nombre de \( \mbox{FPSD} \) qui ont le même \( \mbox{FP} \) est égal au nombre de régions de \( R \) délimitées par ces hyperplans de coefficients \( \overline{a}_i \). On peut effectuer un changement de coordonnées :
\[ X_1 = x_ 1 \] \[ X_{i+1} = x_{i+1} - x_i \]qui a pour effet de transformer les équations d'hyperplans comme suit :
\[ \sum_{i=1}^k \left( \sum_{j=i}^k \overline{a}_j \right) X_i = 0 \]On définit alors :
\[ \overline{A}_i = \sum_{j=i}^k \overline{a}_j \]pour avoir
\[ \sum_{i=1}^k \overline{A}_i X_i = 0 \]Les \( X_i \) satisfont : \( X_1 \gt 0, X_2 \gt 0, \dots, X_k \gt 0 \). La région \( R \) en coordonnées \( x_i \) a été transformée en l'orthant positif, en coordonnées \( X_i \).
Le nombre de \( \mbox{FPSD} \) qui ont le même \( \mbox{FP} \) est égal au nombre de régions de l'orthant positif délimitées par les hyperplans de coefficients \( \overline{A}_i \).
Les hyperplans qui importent vraiment sont ceux qui traversent cet orthant positif. Compte tenu de (1), ces hyperplans sont caractérisés par la propriété : au moins l'un des \( \overline{A}_i \) est \( \lt 0 \) et au moins l'un des \( \overline{A}_i \) est \( \gt 0 \).
LR, 22/11/2019.