Mots avec Lettres Répétées dans une Grille

Informations Fondamentales

• ID de l'article : 2511.19678
• Titre : Words with Repeated Letters in a Grid
• Auteurs : Zachary Halberstam, Carl Schildkraut
• Classification : math.CO (Combinatoire)
• Date de publication : 24 novembre 2025 (prépublication arXiv)
• Lien de l'article : https://arxiv.org/abs/2511.19678

Résumé

Cet article étudie le problème du nombre maximal d'occurrences d'un mot donné w dans une grille de dimension d, lorsqu'on lit consécutivement selon des « directions de recherche de mots » (c'est-à-dire des vecteurs directeurs dans {-1,0,1}^d{0}). Patchell et Spiro ont d'abord proposé ce problème, et Alon et Kravitz l'ont complètement résolu pour les mots sans lettres répétées. Cet article étudie le cas général contenant des lettres répétées, révélant une structure et une complexité beaucoup plus riches (même pour d=1), et mettant au jour des connexions profondes avec des problèmes combinatoires classiques comme le problème des n reines.

Contexte et Motivation de la Recherche

1. Problème Central

Étant donné un mot w et une dimension d, comment placer les lettres dans une grille toroïdale de dimension d de taille n₁×n₂×...×n_d (chaque coordonnée modulo n_i) pour maximiser le nombre d'occurrences de w ? Ici, une « occurrence » signifie lire w consécutivement selon l'une des 3^d-1 directions de recherche possibles.

2. Importance du Problème

• Signification théorique : Ce problème relie la combinatoire additive, l'analyse de Fourier et la théorie des graphes
• Optimisation combinatoire : Implique des problèmes de configuration extrémale sous contraintes
• Connexions avec des problèmes classiques : Liens profonds avec la conjecture de pavage périodique, le problème des n reines et autres problèmes célèbres

3. Limitations des Travaux Existants

Alon et Kravitz 1 ont complètement résolu le cas des mots « bien comportés », incluant :

• Les mots sans lettres répétées
• Les mots satisfaisant des contraintes spécifiques (par exemple, les lettres n'apparaissent qu'aux positions paires ou impaires, sans blocs de deux lettres répétées)

Cependant, pour les mots généraux contenant des lettres répétées, le problème reste non résolu et révèle une structure beaucoup plus complexe.

4. Motivation de la Recherche

• Explorer les configurations extrémales pour les mots avec lettres répétées
• Classifier quels mots sont « d-empilables » ou « d-inclinables »
• Établir des connexions avec d'autres problèmes combinatoires

Contributions Fondamentales

1. Résolution complète du cas unidimensionnel (Théorème 1.2) : Fournir une forme fermée pour la concentration C₁(w) de tout mot en dimension 1, et classifier toutes les grilles extrémales
2. Établir des bornes dimensionnelles (Proposition 1.3) : Prouver que pour tout mot w et dimension d : $3^{d-1}C_1(w) \leq C_d(w) \leq \frac{3^d-1}{2}C_1(w)$
3. Caractérisation de la d-empilabilité (Théorème 1.4) :
   • Les mots pair-impair (lettres n'apparaissant pas simultanément aux positions paires et impaires) sont d-empilables dans toutes les dimensions
   • Les mots avec lettres répétées conservent la d-empilabilité
   • Caractérisation complète de la 2-empilabilité pour les mots de 4 lettres
   • Preuve que AB^(ℓ-1) (ℓ>3) n'est pas 2-empiable
4. Bornes de d-inclinabilité (Théorème 1.5) :
   • Les mots de longueur ℓ ne peuvent pas être d-inclinables pour d≥8log₂ℓ+47
   • Quand tous les facteurs premiers de ℓ sont ≥2^d, AB^(ℓ-1) est d-inclinable
5. Contributions méthodologiques : Développement de quatre techniques principales
   • Méthode de reconstruction additive
   • Techniques de réduction combinatoire
   • Analyse de programmation linéaire locale
   • Méthode d'analyse de Fourier

Explication Détaillée des Méthodes

Définition des Tâches

Concepts fondamentaux :

• Grille Γ : Fonction de G=∏ᵢ₌₁ᵈ Z/nᵢZ vers l'alphabet Σ
• Occurrence : Pour (p,v)∈G×({-1,0,1}^d{0}), (p,v) est une occurrence de w si les lettres de Γ aux positions {p+iv}_^{len(w)-1} sont exactement les lettres de w
• Concentration : cd(w,Γ) = ct(w,Γ)/|Γ|, c'est-à-dire le nombre d'occurrences divisé par la taille de la grille
• Concentration maximale : Cd(w) = sup_Γ cd(w,Γ)

Problème central : Étant donné un mot w et une dimension d, déterminer la valeur de Cd(w).

Cadre Technique Fondamental

1. Méthode de Reconstruction Additive (Section 3)

Transformer le problème en un problème d'addition d'ensembles. Pour une direction v, définir : $S_v = \{p \in G : (p,v) \text{ est une occurrence de } w\}$

Observation clé : $(S_u - S_v) \cap I_{u,v} = \emptyset$ où $I_{u,v} = \{iv - ju : 0 \leq i,j < len(w), w_i \neq w_j\}$

Cela transforme le problème de comptage en maximisation de $\sum_v |S_v|/|G|$ sous contraintes additives.

Solution complète du cas unidimensionnel :

Définir trois paramètres :

• c_left : longueur du plus long préfixe palindromique
• c_right : longueur du plus long suffixe palindromique
• c_repeat : longueur de la plus longue sous-chaîne qui est à la fois un vrai préfixe et un vrai suffixe

Théorème 3.1 : Pour un mot w de longueur ℓ :

• Si w n'est pas palindromique : $C_1(w) = \max\left(\frac{1}{\ell-c_{repeat}}, \frac{1}{\ell-\frac{c_{left}+c_{right}}{2}}\right)$
• Si w est palindromique : $C_1(w) = \frac{2}{\ell-c_{repeat}}$

Deux constructions extrémales :

1. Construction 1 (chevauchement dans la même direction) : Quand c_repeat est grand, répéter w=vs (s est une sous-chaîne de longueur c_repeat répétée) en chevauchant la partie v
2. Construction 2 (alternance de directions) : Quand c_left+c_right est grand, alterner la lecture directe et inverse de w, en chevauchant les parties palindromiques

2. Techniques de Réduction Combinatoire (Section 4)

Proposition de réduction par projection 4.2 : S'il existe une application π:Σ→Σ' et une grille unidimensionnelle Γ₀ telles que :

• Γ₀ est w-extrémale
• π(Γ₀) est w'-extrémale
• Pour toute grille Γ : ct(w,Γ)/ct(w',π(Γ)) ≤ ct(w,Γ₀)/ct(w',π(Γ₀))

Alors pour tout d : Cd(w)/C₁(w) ≤ Cd(w')/C₁(w')

Exemples d'application :

• Mots pair-impair (Théorème 1.4a) : Projeter les lettres sur {pair, impair}, réduire au cas AB
• Mots avec lettres répétées (Théorème 1.4b) : Via des techniques de sous-échantillonnage, prouver que w^(k) conserve la d-empilabilité
• Réduction de mots courts : Réduire ABCA, ABBC, ABBA, BABB au cas ABB

3. Analyse de Programmation Linéaire Locale (Section 5)

Idée centrale : Pour une région locale fixée S⊂Z^d, optimiser une fonction de poids F.

Proposition 5.2 : Si une fonction de poids F satisfait :

• (i) Pour chaque type de direction, le poids moyen est K
• (ii) Pour toute grille infinie G : $\sum_{(p,v)\in A(w,G)} F(p,v) \leq M$

Alors Cd(w) ≤ M/K

Construction de programmation linéaire :

1. Choisir une région locale S (par exemple, grille 3×3 ou 5×5)
2. Choisir une lettre A, définir l'ensemble des directions réalisables F
3. Optimiser : $\min M \text{ s.t. } \sum_{(p,v)\in A(w,G)} F(p,v) \leq M, \forall G\in\mathcal{G}$ où G est l'ensemble des grilles avec S à l'intérieur et A partout ailleurs

Optimisations clés :

• Utiliser la symétrie pour réduire le nombre de variables
• Ajouter itérativement des contraintes violées
• Vérifier par énumération sur 2^|S| grilles

Cas de succès :

• Prouver que ABB est 2-empiable (C₂(ABB)≤2)
• Prouver que ABCC est 2-empiable (C₂(ABCC)≤6/5)
• Calculer C₂(BABBB)=8/5 (ni 2-empiable ni 2-inclinable)

4. Méthode d'Analyse de Fourier (Section 7)

Application 1 : Grilles de forme (Z/3Z)^d avec ABB

Lemme 7.1 : Pour f:(Z/3Z)^d→0,1, α=𝔼f : $\mathbb{E}_{x,y} f(x)(1-f(x+y))(1-f(x+2y)) \leq \frac{3}{2}\alpha(1-\alpha)^2$

Technique de preuve :

• Développer l'espérance en coefficients de Fourier
• Utiliser les propriétés de ω=e^(2πi/3)
• Appliquer le Lemme 7.2 : Si ℜ(z),ℜ(ωz),ℜ(ω²z)≤β, alors ℜ(z³)≤β³

Application 2 : Borne dimensionnelle pour la d-inclinabilité

Stratégie centrale (preuve du Théorème 1.5a) :

1. Construire une grille quasi-extrémale Θ (Lemme 7.3)
2. Appliquer le résultat de stabilité (Théorème 3.2) : Les lignes de recherche quasi-extrémales ont des distributions de lettres quasi-identiques
3. Contradiction par analyse de Fourier (Lemme 7.4) : Dans (Z/nZ)^d (n<2^d), il est impossible que toutes les lignes de recherche aient la même distribution de lettres

Lemme 7.4 : Dans une grille de forme (Z/nZ)^d (n<2^d), si la lettre A occupe une proportion α, alors il existe deux lignes de recherche dont le nombre de A diffère d'au moins : $\frac{\sqrt{\min(\alpha,1-\alpha)}}{3^{d/2}}n$

La preuve utilise la méthode des moments d'ordre deux et la transformée de Fourier.

Points d'Innovation Technique

1. Cadre unifié : Première étude systématique des mots avec lettres répétées, révélant qu'ils sont beaucoup plus complexes que les cas sans répétition
2. Perspective additive : Transformer les problèmes de grille en problèmes de combinatoire additive, établissant des liens avec le pavage périodique
3. Réductions multi-niveaux : Développer des techniques de réduction combinatoire flexibles, capables de traiter diverses classes de mots
4. Principe local-global : Obtenir des bornes supérieures globales via des contraintes locales de programmation linéaire, atteignant parfois des bornes serrées
5. Combinaison Fourier-stabilité : Combiner innovamment les résultats de stabilité unidimensionnels avec l'analyse de Fourier multidimensionnelle pour obtenir des bornes dimensionnelles
6. Connexion avec les n reines : Révéler les liens profonds entre la d-inclinabilité de AB^(ℓ-1) et le problème des n reines modulo

Configuration Expérimentale

Cet article est un travail mathématique théorique pur, ne comportant pas d'expériences au sens traditionnel, mais incluant de nombreuses vérifications computationnelles :

Vérifications Computationnelles

1. Cas unidimensionnel : Calcul complet de C₁(w) pour tous les mots de longueur ≤5
2. Mots courts bidimensionnels :
   • Classification complète de la 2-empilabilité pour tous les mots de 4 lettres (10 classes d'isomorphisme)
   • Classification partielle pour les mots de 5 lettres (16 sur 31 classes d'isomorphisme)
3. Calculs de programmation linéaire :
   • ABB : Vérification de 512 configurations de grille sur région 3×3 (Lemme A.1 vérifié manuellement)
   • ABCC : Vérification sur région 5×5 (Lemme A.2 vérifié manuellement)
   • BABBB : Vérification par ordinateur sur région plus grande
   • ABBB : Obtention de la borne supérieure C₂(ABBB)≤59526/35459≈1.679

Détails d'Implémentation

Stratégie d'optimisation de programmation linéaire :

• Utiliser le groupe de symétrie (Z/2Z)^d⋊Sd pour réduire les variables
• Fusionner les grilles sur les orbites Π en une seule contrainte
• Résoudre itérativement avec échantillonnage de contraintes
• La symétrie réduit les calculs de 2^|S| à une échelle traitable

Résultats Expérimentaux

Résultats Théoriques Principaux

1. Solution Complète Unidimensionnelle (Théorèmes 3.1, 3.3)

Présentation des résultats :

• SALSA : c_repeat=2, C₁(SALSA)=1/3 (construction : ...SALSALSALSAL...)
• ELEPHANT : c_left=1, c_right=1, c_repeat=0, C₁(ELEPHANT)=1/7 (construction : ...HPELEPHANTNAHPELEPH...)
• ABABAB : c_repeat=4, C₁(ABABAB)=1 (construction : ...ABABABABAB..., chaque lettre utilisée 6 fois)

Caractérisation de structure (Proposition 3.3) :

• Si c_left+c_right<2c_repeat : Seule la construction 1 est extrémale
• Si c_left+c_right>2c_repeat : Seule la construction 2 est extrémale
• Si c_left+c_right=2c_repeat : Les deux constructions sont extrémales, et tous les extrémaux sont leurs combinaisons

2. Classification Complète des Mots de 4 Lettres Bidimensionnels (Théorème 1.4c)

Découverte clé : ABBB (isomorphe à AAAB) est l'unique mot de 4 lettres qui n'est pas 2-empiable.

3. Résultats Partiels pour les Mots de 5 Lettres

d-empilables (8) : ABABA, ABABC, ABACA, ABACD, ABCBA, ABCBD, ABCDA, ABCDE (Théorème 1.4a) AABBA (réduction à AABB)

2-empilables (5 supplémentaires) : AABCC, AABAA (réduction à AAB) ABCAB (réduction à ABB) AABCB, ABBAC (réduction à ABCC)

Non 2-empilables (2) :

• ABBBB : C₂(ABBBB)=8/5>6/5=3C₁(ABBBB)
• BABBB : C₂(BABBB)=8/5>3/2=3C₁(BABBB) (Lemme 5.6)

Non résolus : 15 sur 31 classes d'isomorphisme

4. Résultats de Bornes Dimensionnelles

Vérification du Théorème 1.5 :

• Borne supérieure : Pour les mots de longueur ℓ, d-inclinabilité impossible pour d≥8log₂ℓ+47
• Borne inférieure : Quand tous les facteurs premiers de ℓ sont ≥2^d, AB^(ℓ-1) est d-inclinable
• Optimalité : Par le postulat de Bertrand, la borne supérieure est optimale à facteur constant

Exemples concrets :

• ℓ=5, gcd(5,6)=1 : AB⁴ est 2-inclinable (C₂(AB⁴)=8/5=4C₁(AB⁴))
• ℓ=7, gcd(7,6)=1 : AB⁶ est 2-inclinable (correspondant au problème des 7 reines)

Expériences d'Ablation

Bien que non traditionnelles, les expériences montrent la nécessité de chaque composant technique :

1. Nécessité de la méthode additive : Sans reconstruction additive, il est difficile d'obtenir une forme fermée et une caractérisation de structure pour le cas unidimensionnel
2. Puissance des réductions combinatoires :
   • Sans réductions : Nécessité d'analyser séparément 14 mots de 4 lettres
   • Avec réductions : Analyse directe de seulement quelques cas fondamentaux comme ABB et ABCC
3. Caractère irremplaçable de la méthode locale :
   • 2-empilabilité de ABB : Les autres méthodes ne peuvent pas la traiter
   • Point clé : Obtenir une borne serrée (C₂(ABB)=2 égale exactement 3C₁(ABB))
4. Limitations et avantages de l'analyse de Fourier :
   • Limitations : Ne traite que des structures spéciales (comme (Z/3Z)^d)
   • Avantages : Obtenir des bornes dimensionnelles générales, impossibles avec les méthodes locales

Études de Cas

Cas 1 : Complexité de CROC (Note 3.8)

CROC satisfait c_left+c_right=2c_repeat, appartenant au cas (c) du Théorème 3.3.

• v=CROC, v'=CORO
• Les grilles extrémales peuvent être Grid(v₁...vₘ), où vᵢ∈{v,v'}
• Le nombre de grilles extrémales de taille 3n croît exponentiellement en n
• Exemple : Grid(CROCROCOR) est extrémale mais non équivalente aux constructions 1 ou 2

Cas 2 : Non-monotonicité de BABBB (Lemme 5.6)

Grille Γ (5×5):
A B B B B
B B B A B
B A B B B
B B B B A
B B A B B

• c₂(BABBB,Γ)=8/5
• 3C₁(BABBB)=3×(1/2)=3/2<8/5
• 4C₁(BABBB)=2>8/5
• Conclusion : Ni 2-empiable ni 2-inclinable, montrant un comportement intermédiaire

Cas 3 : AB⁶ et le Problème des 7 Reines (Figures 6-7)

Les 7 configurations de reines non-attaquantes correspondent aux grilles extrémales pour C₂(AB⁶)=4C₁(AB⁶) :

A B B B B B B
B B A B B B B
B B B B A B B
B B B B B B A
B A B B B B B
B B B A B B B
B B B B B A B

Chaque A a 6 B consécutifs dans les 8 directions, totalisant 56 occurrences.

Découvertes Expérimentales

1. Saut de complexité : Du cas sans répétition au cas avec répétition, la complexité augmente significativement
   • Sans répétition : Tous les mots sont d-empilables
   • Avec répétition : Trois types apparaissent (d-empiable, d-inclinable, intermédiaire)
2. Effets dimensionnels :
   • Basses dimensions (d=1,2) : Analyse fine requise pour chaque mot
   • Hautes dimensions (d≥8log₂ℓ) : Résultats généraux montrant qu'aucun mot n'est d-inclinable
3. Complémentarité des méthodes :
   • Méthodes combinatoires : Traiter les mots structurés
   • Programmation linéaire : Traiter quelques cas difficiles clés
   • Analyse de Fourier : Fournir des bornes asymptotiques
4. Richesse des problèmes ouverts :
   • 15 sur 31 mots de 5 lettres non résolus
   • Comportement de ABB pour d≥3 inconnu
   • Valeur exacte de C₂(ABBB) inconnue

Travaux Connexes

1. Recherche de Mots dans les Grilles

Patchell-Spiro 14 (2022) :

• Première formulation systématique du problème
• Résultats partiels et conjectures

Alon-Kravitz 1 (2024) :

• Résolution complète pour les mots sans lettres répétées
• Résultat principal : Pour les mots « bien comportés » w, Cd(w)=3^(d-1)/(len(w)-1)
• Construction extrémale : Alternance directe-inverse, comme ...w₂w₁w₂...wℓwℓ...w₂w₁...
• Méthode : Analyse de Fourier + arguments combinatoires

Extension de cet article :

• Traiter les mots généraux avec lettres répétées
• Révéler une structure plus riche (trois types : d-empiable, d-inclinable, intermédiaire)
• Développer nouvelles méthodes (programmation linéaire locale)

2. Combinatoire Additive

Conjecture de Pavage Périodique :

• Greenfeld-Tao 8 (2024) contre-exemple : Existence de pavages non-périodiques
• Problème 2.5 de cet article : Existence de grilles extrémales ? Similaire à la conjecture de pavage
• Connexion : Le pavage requiert S+T=Z^d, cet article requiert (S-S)∩I=∅

Ensembles de Kravitz 11 :

• Étudier la densité d'ensembles évitant des différences spécifiques
• Lié aux contraintes additives de cet article

3. Combinatoire Extrémale

Algèbres de Drapeaux 16 :

• Méthode de programmation semi-définie de Razborov
• Utilisée pour les densités de sous-graphes et autres problèmes
• La programmation linéaire de cet article est une version simplifiée d'idées similaires

Problèmes Extrémaux Géométriques :

• Ensembles sans distance unité 2,17
• Ensembles de vecteurs orthogonaux sur sphère 3,7
• Point commun : Extrémaux globaux sous contraintes locales

4. Problème des n Reines

Problème des n Reines Classique 4 :

• Problème classique depuis 1848
• Synthèse de Bell-Stevens

Reines Modulo n :

• Pólya 15 (1921) : Existence de n reines non-attaquantes quand gcd(n,6)=1
• Klarner 9, Kunt 10 : Généralisations multidimensionnelles
• Nudelman 13 : Différentes conventions d'attaque

Contribution de cet article :

• Corollaire 8.2 : Pour gcd(n,(2d)!)=1, existence de n^(d-1) reines non-attaquantes
• Cela prouve une direction de la conjecture 25 de Bell-Stevens
• Les Théorèmes 1.4d et 1.5b établissent l'équivalence entre AB^(ℓ-1) et le problème des ℓ reines

5. Applications de l'Analyse de Fourier en Combinatoire

Progressions Arithmétiques :

• Théorème de Roth (3-PA), Théorème de Szemerédi (k-PA)
• Analyse de Fourier d'ordre supérieur 18
• Le problème de cet article est similaire aux PA avec différences restreintes, mais plus difficile

Progrès Récents 5 :

• Bornes effectives pour les 3-PA restreintes
• Le problème de cet article pour ℓ>3 nécessite probablement l'analyse de Fourier d'ordre supérieur

Conclusion et Discussion

Conclusions Principales

1. Solution complète unidimensionnelle : Forme fermée pour C₁(w) de tout mot et classification complète des grilles extrémales
2. Mots courts bidimensionnels : Résolution complète pour les mots de 4 lettres, résolution partielle pour les mots de 5 lettres
3. Bornes dimensionnelles :
   • Bornes générales : 3^(d-1)C₁(w) ≤ Cd(w) ≤ (3^d-1)/2·C₁(w)
   • d-inclinabilité : Les mots de longueur ℓ ne peuvent pas être d-inclinables pour d≥8log₂ℓ+47
4. Théorèmes de structure :
   • Les mots pair-impair sont toujours d-empilables
   • La répétition de lettres conserve la d-empilabilité
   • AB^(ℓ-1) (ℓ>3) n'est pas 2-empiable
5. Méthodologie : Établir une boîte à outils de quatre techniques complémentaires

Limitations

1. Complexité computationnelle :
   • La méthode de programmation linéaire n'est pas praticable pour |S|>25
   • Les vérifications manuelles (comme ABB, ABCC) sont extrêmement fastidieuses
   • Limite la longueur des mots pouvant être traités
2. Couverture incomplète :
   • 48% des mots de 5 lettres restent non résolus
   • Les mots de 6 lettres et plus sont pratiquement non traités
   • Le comportement de ABB pour d≥3 est inconnu
3. Limitations méthodologiques :
   • L'analyse de Fourier nécessite des structures spéciales (comme (Z/3Z)^d)
   • Les réductions combinatoires nécessitent de trouver des « mots de base » appropriés
   • Les méthodes locales ont du mal à prouver les bornes non-serrées
4. Lacunes théoriques :
   • Problème 2.5 (existence de grilles extrémales) résolu seulement pour d=1
   • Les résultats de stabilité en haute dimension (Problème 9.6) sont complètement inconnus
   • Le « comportement typique » des mots généraux n'est pas clair

Directions Futures

Problèmes explicitement posés dans l'article :

1. Existence de Grilles Extrémales (Problème 2.5) :
   • Pour chaque (w,d), existe-t-il une grille w-extrémale ?
   • Analogie : La conjecture de pavage périodique a été réfutée, ce problème pourrait aussi être négatif en haute dimension
2. Classification Complète des Mots Courts :
   • Problème 9.1 : Quels mots de 5 lettres sont 2-empilables ?
   • Problème 9.2 : ABB est-il d-empiable pour tous les d ?
   • Problème 9.3 : C₂(ABBB)=8/5 ?
3. Structure Multidimensionnelle (Problèmes 9.5-9.6) :
   • Toutes les grilles w-extrémales ont-elles la même distribution de lettres ?
   • Existe-t-il des résultats de stabilité similaires au Théorème 3.2 ?
4. Comportement Asymptotique (Problème 9.4) :
   • Proportion de mots d-empilables/d-inclinables parmi les mots longs ?
   • Quel est le comportement « typique » ?

Directions de Recherche Potentielles :

5. Applications de l'Analyse de Fourier d'Ordre Supérieur :
   • Peut-on utiliser les normes de Gowers pour traiter les mots longs ?
   • Connexion précise avec le problème des PA avec différences restreintes ?
6. Améliorations Computationnelles :
   • Résolution plus efficace de programmation linéaire
   • Apprentissage automatique pour trouver les configurations extrémales
   • Vérification symbolique
7. Connexions avec d'Autres Problèmes Combinatoires :
   • Connexions avec la théorie de Ramsey
   • Connexions avec la théorie du codage
   • Généralisation à des structures non-grille (graphes, variétés)
8. Questions Algorithmiques :
   • Complexité algorithmique d'approximer Cd(w) ?
   • Algorithmes efficaces pour construire des grilles quasi-extrémales ?

Évaluation Approfondie

Points Forts

1. Choix de Problème Excellent :
   • Naturel et stimulant
   • Relie plusieurs branches mathématiques
   • Profondeur théorique et calculabilité concrète
2. Innovation Méthodologique :
   • Diversité : Quatre techniques complémentaires, chacune avec ses forces
   • Unité : La reconstruction additive fournit une perspective unifiée
   • Praticité : La programmation linéaire atteint des bornes serrées dans certains cas
3. Profondeur des Résultats :
   • La solution unidimensionnelle complète inclut une caractérisation fine de structure (Théorème 3.3)
   • Les résultats de stabilité (Théorème 3.2) jettent les bases de l'analyse multidimensionnelle
   • La connexion avec le problème des n reines a une valeur indépendante (Corollaire 8.2)
4. Rigueur Technique :
   • Tous les théorèmes principaux ont des preuves complètes
   • Les vérifications computationnelles sont transparentes (Appendice A fournit les vérifications manuelles)
   • Honnêteté sur les limitations et les problèmes ouverts
5. Qualité de Rédaction :
   • Structure claire, organisée par méthode technique
   • Nombreux exemples et illustrations (Figures 5-9)
   • Explications détaillées de la motivation et intuition

Insuffisances

1. Goulot d'Étranglement Computationnel :
   • Scalabilité limitée de la méthode de programmation linéaire
   • La vérification manuelle de ABB (Lemme A.1) est extrêmement fastidieuse, difficile à généraliser
   • Pour BABBB et autres, dépendance sur ordinateur sans preuve élégante
2. Couverture Incomplète :
   • 15/31 mots de 5 lettres non résolus
   • Pratiquement aucun résultat pour les mots longs
   • Cas multidimensionnel (d≥3) très peu traité
3. Lacunes Théoriques :
   • Problème 2.5 (existence d'extrémaux) complètement ouvert pour d≥2
   • Absence de résultats asymptotiques généraux
   • Théorie de stabilité multidimensionnelle manquante
4. Limitations Méthodologiques :
   • L'analyse de Fourier s'applique seulement à des formes spéciales de grille
   • Les réductions combinatoires nécessitent d'identifier des « mots de base », pas de méthode systématique
   • Les méthodes locales ont du mal avec les bornes non-serrées
5. Complexité de Certaines Preuves :
   • La preuve du Théorème 3.3(c) est extrêmement technique
   • La preuve du Théorème 7.4 dépend de multiples estimations fines
   • La lisibilité en souffre parfois

Influence

Contributions Théoriques :

• Ouvre l'étude systématique des mots avec lettres répétées
• Les techniques développées (particulièrement la programmation linéaire locale) pourraient s'appliquer à d'autres problèmes extrémaux
• La connexion avec le problème des n reines pourrait inspirer de nouvelles recherches

Valeur Méthodologique :

• Démontre la complémentarité de plusieurs techniques
• La perspective de reconstruction additive pourrait inspirer des problèmes connexes
• Application réussie du principe local-global

Problèmes Ouverts :

• Propose de nombreux problèmes concrets et attaquables
• Différents niveaux de difficulté, appropriés pour différents chercheurs
• Grand espace pour les preuves assistées par ordinateur

Limitations :

• Difficile de résoudre complètement à court terme (par exemple, Cd(w) pour mots généraux)
• Nécessite de nouvelles idées pour surmonter les goulots d'étranglement computationnels
• Pas d'applications pratiques évidentes (problème purement théorique)

Scénarios d'Application

Applications Directes :

• Optimisation combinatoire : Maximiser les configurations sous contraintes
• Théorie du codage : Potentiellement lié à la distribution des mots de code
• Conception de jeux : Configurations limites pour les jeux de recherche de mots

Outils Théoriques :

• Chercheurs en combinatoire additive : Nouveau type de problème extrémaux
• Analyse de Fourier : Cas d'application concrets
• Programmation linéaire : Démonstration de la méthode locale

Valeur Pédagogique :

• Montre l'utilisation synthétique de plusieurs techniques
• Progression claire du simple au complexe
• Nombreux exemples concrets appropriés pour l'enseignement

Recherche Future :

• Tremplin pour étudier les problèmes extrémaux connexes
• Plateforme pour tester de nouvelles méthodes computationnelles
• Interface avec d'autres domaines (analyse de Fourier d'ordre supérieur)

Références

Références Fondamentales :

1 N. Alon and N. Kravitz. Cats in cubes. Electron. J. Combin., 31(3):Paper No. 3.29, 2024.

• Prédécesseur direct de cet article, résout le cas sans lettres répétées

14 G. Patchell and S. Spiro. The maximum number of appearances of a word in a grid. Amer. Math. Monthly, 129(5):415–434, 2022.

• Formulation originale du problème

8 R. Greenfeld and T. Tao. A counterexample to the periodic tiling conjecture. Ann. of Math., 200(1):301–363, 2024.

• Contre-exemple important lié au Problème 2.5

4 J. Bell and B. Stevens. A survey of known results and research areas for n-queens. Discrete Math., 309(1):1–31, 2009.

• Synthèse complète du problème des n reines

16 A. A. Razborov. Flag algebras. J. Symbolic Logic, 72(4):1239–1282, 2007.

• Outil puissant en combinatoire extrémale, lié à la méthode de programmation linéaire

18 T. Tao. Higher order Fourier analysis. Graduate Studies in Mathematics, vol. 142, AMS, 2012.

• Référence standard pour l'analyse de Fourier d'ordre supérieur, application potentielle discutée

Évaluation Générale : Ceci est un excellent article de mathématiques combinatoires qui étudie systématiquement un problème naturel et profond. En développant plusieurs techniques complémentaires, les auteurs réalisent des progrès substantiels, notamment la résolution complète du cas unidimensionnel et la résolution partielle des mots courts bidimensionnels. L'article révèle des connexions inattendues avec le problème des n reines et d'autres problèmes classiques. Les principales limitations proviennent de la complexité computationnelle qui restreint la scalabilité des méthodes, et de la compréhension limitée des mots longs et des cas multidimensionnels. Néanmoins, cet article établit une base solide pour le domaine, et ses méthodes et résultats inspireront les recherches futures.