🔢 mathematics

Exact values and exact upper bounds for families of integers with arithmetic progression intersections (Erd\H{o}s Problem #272)

Cet article résout le problème d'Erdős n° 272 pour $3 \leq N \leq 12$ en prouvant que la borne inférieure de Szabó est exacte dans cette plage, établit que cette borne est le maximum pour les familles partageant un élément commun, et réduit la conjecture générale à l'unique question de savoir si une famille extrémale doit toujours contenir un élément commun.

Auteurs originaux : Zhanfu Yang

Publié 2026-07-28

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Zhanfu Yang

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 organisiez une fête immense dans une maison comprenant des pièces numérotées de 1 à $N$ . Vous voulez inviter des groupes d'invités à passer du temps dans ces pièces, mais il existe une règle très spécifique et excentrique pour qui peut faire partie du même groupe : si vous prenez deux groupes quelconques et que vous examinez les personnes qu'ils ont en commun, ce groupe partagé doit former une ligne parfaite et régulièrement espacée. En langage mathématique, cela s'appelle une « progression arithmétique ». C'est comme si le Groupe A avait les invités {2, 5, 8} et le Groupe B avait {5, 8, 11}, leur chevauchement est {5, 8}, ce qui est une ligne parfaite avec un écart de 3. Mais si le chevauchement était {5, 9}, la ligne serait brisée et la règle serait transgressée.

La grande question que les mathématiciens se posent depuis des décennies est la suivante : combien de groupes différents pouvez-vous inviter avant de manquer de façons d'organiser ces groupes sans enfreindre la règle ? C'est un puzzle consistant à faire entrer le plus de pièces possible dans une boîte où chaque pièce doit s'emboîter parfaitement avec toutes les autres selon un motif spécifique. Ce n'est pas seulement un jeu ; c'est un problème fondamental de combinatoire, la branche des mathématiques qui étudie la façon dont les choses peuvent être organisées et comptées. Résoudre cela aide à comprendre les limites cachées de la structure dans le hasard, montrant à quel point nous pouvons imposer de l'ordre dans un système chaotique avant qu'il ne s'effondre.

Pendant longtemps, les experts pensaient connaître la réponse. Ils croyaient que le nombre maximum de groupes était approximativement la moitié du nombre de paires de personnes possibles, plus un tout petit peu. Mais un mathématicien nommé Szabó est arrivé et a dit : « Attendez, vous pouvez en fait caser quelques groupes de plus que cela ! » Il a construit une construction astucieuse qui a prouvé que vous pouviez obtenir légèrement plus haut que l'ancienne conjecture. Cependant, il ne pouvait pas prouver si c'était la limite absolue ou s'il existait une disposition encore plus folle cachée dans l'ombre. Il a également posé une « question de noyau » : existe-t-il toujours une personne spécifique qui est invitée à chaque groupe dans la meilleure disposition possible ?

Cet article, écrit par Zhanfu Yang, plonge profondément dans ce puzzle pour trouver les réponses exactes pour de plus petites tailles de fêtes et pour prouver ce qui se passe lorsque nous forçons une personne spécifique à être présente à chaque fête. L'auteur n'a pas seulement deviné ; il a utilisé de puissants programmes informatiques pour vérifier toutes les combinaisons possibles pour des fêtes allant jusqu'à 12 pièces. Le résultat ? Pour ces petites tailles, la construction astucieuse de Szabó était parfaite. Ce n'était pas seulement une bonne supposition, c'était le maximum absolu. L'article a trouvé les nombres exacts : pour une fête de 12 pièces, vous pouvez avoir exactement 69 groupes. Cette séquence de nombres (4, 7, 12, 17, 23, 30, 39, 48, 58, 69) est si nouvelle qu'elle n'apparaît même pas encore dans la célèbre base de données des séquences numériques.

Mais l'article va plus loin que le simple comptage. Il s'attaque à la « question du noyau » en prouvant un théorème massif : si vous forcez une personne à être dans chaque groupe (une famille « étoilée »), alors la construction de Szabó est définitivement la meilleure que vous puissiez faire. Peu importe la façon dont vous essayez de réorganiser les groupes autour de cette personne centrale, vous ne pouvez pas battre son chiffre. C'est une étape majeure car cela réduit la recherche. La seule façon pour que le maximum absolu soit supérieur au nombre de Szabó est que la meilleure disposition ne possède pas une personne unique dans chaque groupe.

L'auteur a également découvert une règle structurelle fascinante concernant les groupes qui ne suivent pas le motif de la ligne parfaite (appelés membres « tordus » ou « crooked »). Il a prouvé que tout groupe aussi étrange doit contenir une « mauvaise paire » de personnes — une paire qui ne respecte pas la règle de la ligne — que aucun autre groupe de toute la fête ne peut partager. C'est comme un mot de passe secret que seul ce groupe étrange connaît. Cette « paire privée » agit comme un goulot d'étranglement, empêchant ces groupes étranges de s'accumuler trop nombreux sans briser les règles.

Alors, où en sommes-nous ? L'article a résolu le puzzle pour les petits nombres et a prouvé que si un « invité commun » existe, la réponse est connue et exacte. La seule chose restant à résoudre est la question finale et tenace : la fête record ultime possède-t-elle toujours un invité commun ? L'article suggère que si une fête record sans invité commun existe, elle devrait avoir une structure très étrange et très spécifique que l'auteur a déjà commencé à écarter. Bien que l'article n'ait pas fermé le livre sur le tout dernier mystère pour chaque nombre possible, il a transformé une supposition vague en une carte précise, montrant exactement où le trésor est caché et prouvant que l'ancienne carte était fausse. Le voyage vers la réponse finale est désormais beaucoup plus court, le chemin étant clairement marqué par la nouvelle règle de la « paire privée » de l'auteur et par les valeurs exactes confirmées pour les douze premiers cas.

Résumé technique : Valeurs exactes et bornes supérieures exactes pour les familles d'entiers à intersections de progressions arithmétiques

Énoncé du problème
L'article traite du problème d'Erdős n° 272, qui cherche à déterminer la fonction $t(N)$ , définie comme le nombre maximal de sous-ensembles distincts $A_1, \dots, A_t \subseteq \{1, \dots, N\}$ tels que l'intersection de deux ensembles quelconques distincts $A_i \cap A_j$ soit une progression arithmétique (PA) non vide.

Historiquement, Simonovits et Sós ont établi que $t(N) = O(N^2)$ et ont conjecturé que le maximum est atteint par la famille de tous les sous-ensembles de taille au plus 3 contenant un élément fixe, ce qui donne une borne de $\binom{N}{2} + 1$ . Szabó a plus tard infirmé cette conjecture d'exactitude en construisant une famille atteignant $t(N) \ge \binom{N}{2} + 1 + \lfloor (N-1)/4 \rfloor$ . Szabó a ensuite établi le comportement asymptotique $t(N) = N^2/2 + O(N^{5/3}(\log N)^3)$ et a posé deux questions critiques : (i) si $t(N) = \binom{N}{2} + O(N)$ , et (ii) la « question du noyau » (kernel question), demandant si toute famille extrémale (atteignant la taille maximale) doit contenir un élément commun partagé par tous ses ensembles.

Méthodologie
Les auteurs emploient une approche hybride combinant vérification computationnelle exhaustive, combinatoire structurelle et techniques de majoration analytique :

Calcul exact : Pour de petites valeurs de $N$ $N$ ( $N \le 12$ $N \leq 12$ ), le problème est modélisé comme la recherche du maximum de clique dans un graphe où les sommets sont des sous-ensembles non vides de $[N]$ $[N]$ et les arêtes relient des ensembles ayant des intersections de PA non vides.
- Pour $N \le 10$ , un solveur de type branche-et-borne bit-parallèle avec des bornes de coloration gloutonne a été utilisé.
- Pour $N=11$ et $12$, une recherche décisionnelle utilisant la décomposition par racines, l'ordonnancement de dégénérescence, l'épluchage de cœur (core peeling) et une étape rigoureuse d'« élagage par étoile » (star pruning) a été employée pour prouver la non-existence de familles plus grandes.
Décomposition structurelle : La preuve de la borne supérieure générale repose sur la décomposition d'une famille « étoilée » (possédant un élément commun $m$ ) en sous-ensembles de taille $\le 2$ , de taille $3$, et de taille $\ge 4$ .
Inégalité de comptage du défaut un : Un outil technique central est une inégalité de comptage pour les « régions d'escalier » (familles d'intervalles d'entiers contenant 0). Les auteurs prouvent que pour toute famille de ce type, le nombre de membres est borné par le nombre de « paires mauvaises » (paires $\{u,v\}$ telles que $\{0,u,v\}$ n'est pas une PA) qu'elles couvrent, plus un petit terme de défaut. Ceci est vérifié via un programme dynamique exact pour des paramètres allant jusqu'à 500 et un argument asymptotique utilisant des formes quadratiques définies positives pour des paramètres plus grands.
Théorème de la paire privée : Un théorème structurel est établi montrant que chaque membre « tordu » (un ensemble de taille $\ge 4$ qui n'est pas une PA) contient une « paire mauvaise privée » — une paire d'éléments non contenus dans aucun autre membre de la famille. Cela empêche le partage de « kills » (paires mauvaises) entre les membres non-PA, permettant ainsi une borne de comptage serrée.

Contributions clés et résultats

Valeurs exactes pour de petits $N$ : L'article détermine exactement $t(N)$ pour $N = 3, \dots, 12$ . Les valeurs sont $4, 7, 12, 17, 23, 30, 39, 48, 58, 69$. Dans tout cet intervalle, la borne inférieure de Szabó est exacte. La séquence ne figure pas actuellement dans l'OEIS.
Conjecture affinée : Sur la base des preuves computationnelles, les auteurs conjecturent que pour tout $N \ge 1$ :
$t(N) = \binom{N}{2} + 1 + \left\lfloor \frac{N-1}{4} \right\rfloor$
Ceci affine la question asymptotique de Szabó vers une formule exacte.
Borne supérieure exacte pour les familles étoilées : Le principal résultat théorique (Théorème 1.4) prouve que pour toute famille étoilée (où tous les ensembles partagent un élément commun), la taille est bornée par la borne inférieure de Szabó. C'est la première borne supérieure exacte de ce type connue pour tout $N \ge 5$ $N \geq 5$ .
- La preuve combine l'inégalité de comptage du « défaut un » avec le « théorème de la paire privée » pour traiter les membres non-PA.
Réduction à la question du noyau : Les auteurs démontrent que la conjecture affinée (que la formule soit vraie pour tout $N$ ) découle immédiatement si la conjecture du noyau de Szabó est vraie (c'est-à-dire si toute famille extrémale est étoilée). Ainsi, le problème de détermination exacte de $t(N)$ est réduit à la preuve que les familles extrémales doivent posséder un élément commun.
Contraintes structurelles sur les contre-exemples : L'article analyse la structure hypothétique d'une famille extrémale non-étoilée (un contre-exemple à la conjecture du noyau). Il prouve que si une telle famille existe, ses triplets doivent partager un élément commun, et tout membre évitant cet élément doit être une longue progression arithmétique à faibles différences. Les auteurs soutiennent que de telles configurations sont « auto-limitantes » et peu susceptibles d'atteindre la borne conjecturée, bien qu'une preuve complète reste ouverte.

Signification
L'article affirme fournir la première détermination exacte de $t(N)$ pour tout $N \ge 5$ (spécifiquement $N \le 12$ ) et établit la première borne supérieure exacte pour la classe restreinte des familles étoilées. En prouvant que la borne inférieure est exacte pour toutes les familles étoilées, ce travail isole la « propriété de noyau » comme le seul obstacle restant pour résoudre complètement le problème d'Erdős #272. Les auteurs notent que leurs résultats confirment que la construction de Szabó est optimale au sein de la classe des familles partageant un élément commun, et ils fournissent les premières contraintes structurelles rigoureuses sur ce que pourrait être un potentiel contre-exemple non-étoilé. Le travail introduit également de nouvelles techniques combinatoires, spécifiquement l'inégalité de comptage du défaut un et le théorème de la paire privée, qui peuvent être applicables à d'autres problèmes d'intersection.

Articles similaires