🔢 mathematics

Subsequence Sums in Permutations

Cet article établit que pour $n$ suffisamment grand, toute permutation de $\{1, 2, \ldots, n\}$ contient une sous-suite 2-additive de toute longueur fixe $k \geq 3$ , fournit des bornes polynomiales pour le $n$ requis, détermine le seuil exact $n=18$ pour les sous-suites 2-additives monotones de longueur trois, et étend ces résultats aux produits et aux sommes inverses en utilisant des techniques de la théorie de Ramsey arithmétique.

Auteurs originaux : Collier Gaiser, Paul Horn

Publié 2026-05-29

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Collier Gaiser, Paul Horn

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous avez un jeu de cartes numérotées de 1 à $n$ , mélangé dans un ordre complètement aléatoire. Ce jeu mélangé est ce que les mathématiciens appellent une permutation.

Depuis longtemps, les mathématiciens se posent une question précise concernant ces jeux mélangés : Peu importe la manière dont vous les mélangez, si le jeu est suffisamment grand, pourrez-vous toujours trouver un petit groupe de cartes caché à l'intérieur qui suit une règle mathématique spéciale ?

Cet article, écrit par Collier Gaiser et Paul Horn, répond « Oui », mais avec une nuance. Ils ont découvert un nouveau type de règle qui apparaît toujours dans des jeux suffisamment grands, et ils ont déterminé exactement la taille que doit avoir le jeu pour garantir que cela se produise.

Voici la décomposition de leur découverte en utilisant des analogies simples :

1. La règle du « Doublez votre argent »

Les auteurs recherchent un motif spécifique qu'ils appellent une sous-suite 2-additive.

Pensez-y comme à un tour de magie avec trois nombres : $A, B, C$ .

Si vous les additionnez tous ( $A + B + C$ ), le total doit être exactement le double du premier nombre ( $2 \times A$ ) OU le double du dernier nombre ( $2 \times C$ ).

La grande découverte :
L'article prouve que si vous avez un jeu de cartes « suffisamment grand » (la taille exacte dépend du nombre de cartes que vous souhaitez dans votre groupe), vous êtes garanti de trouver un groupe de $k$ cartes qui suit cette règle.

La particularité : Les cartes ne doivent pas être adjacentes dans le jeu. Elles doivent simplement apparaître dans le bon ordre de gauche à droite.
Le résultat : Pour n'importe quelle taille de groupe $k$ (tant que $k \ge 3$ ), il existe un « nombre magique » $n$ . Si votre jeu contient plus de $n$ cartes, vous ne pouvez pas les mélanger de manière à éviter ce motif. C'est inévitable.

2. Quelle taille doit avoir le jeu ?

Les auteurs n'ont pas simplement dit « c'est grand » ; ils ont calculé les limites.

La borne supérieure : Ils ont prouvé que si votre jeu est approximativement proportionnel à $k^5$ (une taille polynomiale), vous êtes garanti de trouver le motif.
La borne inférieure : Ils ont également montré que si le jeu est trop petit (spécifiquement plus petit qu'une certaine formule), vous pouvez en fait le mélanger pour éviter le motif.

Un exemple spécifique (Le « nombre magique » 18) :
L'article se concentre sur le plus petit groupe possible : un groupe de trois cartes ( $k=3$ ).

Ils se sont demandé : « Quelle est la plus petite taille de jeu où vous êtes forcé de trouver trois cartes dont la somme est le double du premier ou le double du dernier ? »
La réponse : 18.
Si vous avez un jeu de 17 cartes, vous pouvez les mélanger d'une manière très spécifique et astucieuse pour éviter ce motif.
Mais dès que vous ajoutez la 18e carte, peu importe comment vous mélangez, vous trouverez inévitablement trois cartes qui correspondent à la règle.
Analogie : Imaginez essayer d'aligner 17 personnes de manière à ce que trois d'entre elles ne satisfont pas une règle spécifique de somme de tailles. Vous pouvez le faire. Mais si vous ajoutez une 18e personne, il devient mathématiquement impossible de les disposer sans créer ce trio spécifique.

3. La nuance « Monotone »

Les auteurs ont également examiné une version plus stricte du jeu. Et si les trois cartes que vous trouvez devaient également être monotones ?

Monotone signifie qu'elles vont soit strictement vers le haut (comme 2, 5, 8), soit strictement vers le bas (comme 9, 4, 1).
Ils ont prouvé que même avec cette règle plus stricte, le nombre magique reste 18. Si vous avez 18 cartes, vous ne pouvez pas éviter de trouver trois cartes qui sont à la fois dans le bon ordre et qui suivent la règle de la « somme double ».

4. Multiplication et sommes inverses

L'article ne s'arrête pas à l'addition. Les auteurs ont utilisé leurs découvertes pour montrer que des règles similaires s'appliquent à d'autres opérations mathématiques :

Multiplication : Si vous cherchez un groupe où le produit des nombres est égal au carré du premier ou du dernier nombre, la même logique s'applique. Si le jeu est suffisamment grand, ce motif est inévitable.
Sommes inverses : Ils ont également examiné l'addition de fractions (comme $1/A + 1/B + 1/C$ ). Ils ont prouvé que si le jeu est suffisamment grand, vous trouverez un groupe où la somme des fractions est égale au double de la première ou de la dernière fraction.

5. Pourquoi cela compte (en termes mathématiques)

Avant cet article, les mathématiciens savaient que l'on pouvait mélanger un jeu pour éviter les progressions arithmétiques (comme 2, 4, 6 ou 5, 10, 15). Vous pouvez cacher ces motifs.

Cependant, cet article montre que bien que vous puissiez cacher les progressions arithmétiques, vous ne pouvez pas cacher ces motifs « 2-additifs ». C'est comme dire : « Vous pouvez cacher une ligne droite dans un tas de sable en désordre, mais vous ne pouvez pas cacher une forme de triangle spécifique. »

Résumé

Le problème : Pouvez-vous mélanger un jeu de nombres de manière à ce qu'aucun petit groupe ne suive une règle mathématique spécifique ?
La réponse : Non. Si le jeu est suffisamment grand, la règle est inévitable.
La règle : La somme du groupe est égale au double du premier ou du dernier nombre.
Le seuil : Pour un groupe de 3, vous avez besoin d'au moins 18 nombres pour garantir l'apparition de la règle.
L'extension : Cette logique fonctionne également pour la multiplication et les fractions.

L'article fournit le « filet de sécurité » mathématique qui prouve que ces motifs sont inévitables dans des collections de nombres suffisamment grandes, indépendamment de l'apparence chaotique de l'arrangement.

Résumé Technique : Sommes de Sous-séquences dans les Permutations

Énoncé du Problème
Cet article examine l'existence de sous-séquences arithmétiques spécifiques au sein des permutations de l'ensemble $\{1, 2, \dots, n\}$ . Tandis que la théorie de Ramsey arithmétique classique (par exemple, le théorème de van der Waerden) garantit des progressions arithmétiques monochromatiques dans des ensembles colorés suffisamment grands, Entringer et Jackson (1973) ont démontré que les permutations peuvent éviter les progressions arithmétiques monotones à 3 termes (3-AP). Les auteurs se demandent si d'autres propriétés arithmétiques, spécifiquement les sous-séquences « additives », sont inévitables dans les grandes permutations.

Une suite d'entiers positifs $(a_1, a_2, \dots, a_k)$ est définie comme $\ell$ -additive si la somme de ses termes satisfait $\sum_{i=1}^k a_i = \ell a_1$ ou $\sum_{i=1}^k a_i = \ell a_k$ . L'accent principal est mis sur les sous-séquences 2-additives (où la somme est égale au double du premier ou du dernier terme) et leurs variantes monotones. L'article aborde deux questions principales :

Pour une longueur fixe $k \ge 3$ , existe-t-il un $n$ tel que toute permutation de $\{1, \dots, n\}$ contienne une sous-séquence 2-additive de longueur $k$ ?
Quelles sont les seuils et les bornes précis pour l'existence de telles sous-séquences, en particulier lorsqu'elles sont restreintes aux suites monotones ?

Méthodologie
Les auteurs emploient une combinaison d'arguments combinatoires, d'analyse de cas et de techniques issues de la théorie de Ramsey arithmétique.

Construction Combinatoire et Contre-exemple : Les preuves centrales pour l'existence (Théorèmes 1.1 et 1.3) reposent sur la construction de sous-ensembles spécifiques de permutations et l'utilisation de la preuve par l'absurde. En analysant les positions relatives des éléments (en utilisant $L_p(s)$ et $R_p(s)$ pour désigner les éléments à gauche et à droite de $s$ dans une permutation $p$ ), les auteurs démontrent que l'évitement d'une sous-séquence 2-additive force une contradiction structurelle dans la disposition de la permutation.
Techniques de Bornage : Pour établir des bornes supérieures pour le plus petit $n$ (désigné $f(k, 2)$ ), les auteurs définissent un ensemble de sommes « dangereuses » dérivées des $2k-1$ premiers éléments d'une permutation. Ils utilisent le plus petit commun multiple (PPCM) de ces sommes pour déterminer un seuil $N_k$ au-delà duquel une sous-séquence 2-additive est forcée.
Bornes Inférieures et Contre-exemples : Les bornes inférieures sont établies en construisant explicitement des permutations de taille $n-1$ qui manquent des sous-séquences désirées.
Analyse Asymptotique : L'article utilise le Théorème des Nombres Premiers (via les résultats de Rosser) pour dériver des bornes inférieures sur le nombre de telles sous-séquences dans les grandes permutations.
Arguments de Transformation : Pour étendre les résultats aux produits et aux sommes inverses, les auteurs utilisent des transformations standard qui mappent les propriétés additives dans $\{1, \dots, n\}$ vers des propriétés multiplicatives dans $\{2^1, \dots, 2^n\}$ et des propriétés inverse-additives dans $\{L_n/1, \dots, L_n/n\}$ (où $L_n$ est le PPCM de $1 $à$ n$).

Contributions et Résultats Clés

Existence de Sous-séquences 2-Additives (Théorème 1.1) :
Pour tout $k \ge 3$ fixé, si $n$ est suffisamment grand, toute permutation de $\{1, \dots, n\}$ contient une sous-séquence 2-additive de longueur $k$ .
- Bornes : L'article fournit des bornes polynomiales pour le plus petit tel $n$ $n$ , noté $f(k, 2)$ $f (k, 2)$ .
  - Borne inférieure : $f(k, 2) \ge (k-1)(3k-4)/2$ .
  - Borne supérieure : $f(k, 2) \le 9(k-2)(k^2-k)^2/4$ .
- Valeur Exacte pour $k=3$ : Les auteurs prouvent que $f(3, 2) = 5$ . Toute permutation de $\{1, \dots, 5\}$ contient une sous-séquence 2-additive de longueur 3, tandis qu'un contre-exemple existe pour $n=4$ .
Sous-séquences 2-Additives Monotones (Théorème 1.3) :
L'article aborde la condition plus stricte où la sous-séquence doit être monotone.
- Résultat : Si $n \ge 18$ , toute permutation de $\{1, \dots, n\}$ contient une sous-séquence 2-additive monotone de longueur 3.
- Optimalité : La valeur 18 est optimale ; une permutation spécifique de $\{1, \dots, 17\}$ est construite pour éviter de telles sous-séquences.
- Question Ouverte : Il reste inconnu si cela vaut pour les sous-séquences 2-additives monotones de longueur $k \ge 4$ .
Sous-séquences $\ell$ -Additives Générales :
- Si $k = \ell$ , la permutation identité $(1, 2, \dots, n)$ ne contient aucune sous-séquence $\ell$ -additive de longueur $k$ .
- L'article résout deux cas mixtes spécifiques :
  - $f(4, 3) = 8$ (Toute permutation de 8 éléments possède une sous-séquence 3-additive de longueur 4).
  - $f(3, 4) = 13$ (Toute permutation de 13 éléments possède une sous-séquence 4-additive de longueur 3).
- Le cas général pour $k \neq \ell$ avec $k, \ell \ge 4$ est laissé comme une question ouverte.
Comptage des Sous-séquences :
Les auteurs fournissent des bornes sur le nombre minimum de sous-séquences $\ell$ -additives de longueur $k$ dans n'importe quelle permutation de taille $n$ :
- Borne Supérieure : $O(n^{k-1})$ .
- Borne Inférieure : $\Omega(n / \log n)$ (en supposant que $f(k, \ell)$ existe), dérivée en utilisant des arguments de distribution des nombres premiers.
- Des bornes spécifiques pour les sous-séquences 2-additives monotones de longueur 3 sont données sous la forme $n/[18(\log n - \log 18 + 2)] - 6 \le G(3, 2, n) \le \frac{1}{18}n^2 + \frac{7}{6}n$ .
Extensions aux Produits et aux Sommes Inverses :
En utilisant des transformations de la théorie de Ramsey arithmétique, l'article étend les résultats additifs à :
- Multiplicatif : Toute permutation suffisamment grande possède une sous-séquence où le produit est le carré du premier ou du dernier terme (2-multiplicative).
- Inverse-Additif : Toute permutation suffisamment grande possède une sous-séquence où la somme des inverses est le double de l'inverse du premier ou du dernier terme.
- L'article note que pour les sous-séquences 2-multiplicatives monotones de longueur 3, le seuil est au plus 32 (et exactement 32, car un contre-exemple existe pour $n=31$ ).

Signification et Revendications
L'article revendique l'établissement des premiers résultats de type Schur-Rado spécifiquement pour les permutations, démontrant que si les permutations peuvent éviter les progressions arithmétiques monotones (3-AP), elles ne peuvent pas éviter les sous-séquences 2-additives de longueur arbitraire. Le travail fournit les premières bornes polynomiales pour l'existence de ces structures et détermine des seuils exacts pour les petits cas ( $k=3$ ).

Les auteurs présentent modestement leur contribution comme une fondation pour de futures études. Ils soulignent que le cas général pour $k \neq \ell$ reste ouvert et que le comportement des sous-séquences 2-additives monotones pour des longueurs $k > 3$ est inconnu. L'article positionne ces découvertes comme une étape vers la compréhension de l'interplay entre la structure des permutations et les propriétés arithmétiques, suggérant des orientations futures dans les sommes de sous-séquences pondérées et le raffinement des seuils pour les variantes multiplicatives et inverse-additives.