🔢 mathematics

Degree-Four Vector-Coordinate SoS Cannot Detect the MUB Upper Bound

Cet article établit que les relaxations de somme de carrés de degré quatre utilisant des formulations en coordonnées vectorielles ne parviennent pas à détecter la borne supérieure connue sur le nombre de bases mutuellement non biaisées (même pour $m > d+1$ ), alors que les formulations en coordonnées de projecteurs récupèrent avec succès cette borne au même degré.

Auteurs originaux : Shreyhaan Sarkar

Publié 2026-06-15

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Shreyhaan Sarkar

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

La Vue d'Ensemble : Un Jeu d'Amis « Parfaitement Impartials »

Imaginez que vous essayiez d'organiser une fête dans une pièce à haute dimension (un espace de $d$ dimensions). Vous voulez inviter des groupes de personnes (des bases) à se tenir selon des motifs spécifiques.

La règle pour une « Base Mutuellement Impartiale » (MUB) ressemble un peu à un jeu d'équilibre parfait :

À l'intérieur d'un groupe : Tout le monde doit se tenir à des angles droits parfaits les uns par rapport aux autres (orthonormaux).
Entre les groupes : Si vous choisissez une personne du Groupe A et une personne du Groupe B, l'« angle » entre elles doit être exactement le même pour chaque paire possible. Elles sont « impartiales » les unes envers les autres.

Les mathématiciens connaissent une limite stricte à ce jeu : vous ne pouvez jamais avoir plus de $d + 1$ groupes. Par exemple, dans une pièce de 6 dimensions ( $d=6$ ), vous pouvez avoir au maximum 7 groupes. C'est un mystère ouvert célèbre de savoir si vous pouvez réellement atteindre cette limite de 7 dans une pièce de 6 dimensions, ou si les règles s'effondrent avant d'y parvenir.

Le Problème : Un Ordinateur peut-il « Voir » la Limite ?

Le papier pose une question spécifique sur un type d'algorithme informatique appelé Somme de Carrés (SoS). Voyez le SoS comme un détective très intelligent, mais légèrement myope. Il essaie de prouver qu'un certain arrangement de personnes est impossible en examinant les équations mathématiques qui décrivent leurs positions.

Le détective a une limite de « degré ». Un détective de degré 4 ne peut examiner que les relations impliquant jusqu'à quatre variables à la fois (comme la façon dont la position de quatre personnes interagit).

La question spécifique (tirée de l'« Open Problem 23 ») était : Un détective de degré 4 peut-il prouver que 7 groupes de personnes ne peuvent pas exister dans une pièce de 6 dimensions ?

La Découverte : Le Détective Utilise la Mauvaise Carte

L'auteur, Shreyhaan Sarkar, a découvert que la réponse dépend entièrement de la manière dont vous décrivez les personnes au détective.

1. La Carte « Vecteur » (L'Échec)

Dans la première méthode, on donne au détective les coordonnées brutes de la tête, des mains et des pieds de chaque personne (les parties réelles et imaginaires des vecteurs).

L'Astuce : L'auteur a construit une « fausse réalité » en utilisant des groupes de personnes aléatoires et indépendants. Dans ce monde factice, les groupes ne sont pas parfaitement impartiaux au sens strict, mais si vous les observez uniquement à travers la « lentille de degré 4 », ils semblent parfaitement impartiaux.
L'Analogie : Imaginez regarder une photo floue d'une foule. De loin (degré 4), la foule semble parfaitement équilibrée et aléatoire. Le détective vérifie les mathématiques, voit que tout s'additionne à zéro, et dit : « Hé, cet arrangement est possible ! »
Le Résultat : Parce que le détective peut être trompé par cette « fausse réalité » (appelée pseudo-espérance), il ne peut pas prouver que 7 groupes sont impossibles. Il ne voit pas la limite de $d+1$ . Il pense que 100 groupes pourraient être possibles dans une pièce de 6 dimensions, alors que nous savons que c'est faux.

2. La Carte « Projecteur » (Le Succès)

L'auteur a ensuite essayé une autre façon de décrire les personnes. Au lieu de donner au détective les coordonnées des membres, il lui a donné une description de l'ombre ou de la projection que chaque personne projette (mathématiquement, $P = vv^*$ ).

La Différence : Dans ce langage de « Projecteur », les règles d'« impartialité » deviennent beaucoup plus simples (quadratiques plutôt que quartiques).
Le Résultat : Lorsque le détective utilise cette carte, l'astuce de la « fausse réalité » ne fonctionne plus. Le détective de degré 4 peut maintenant voir clairement la contradiction mathématique. Il réussit à prouver que vous ne pouvez pas avoir plus de $d+1$ groupes.

La Conclusion Principale

Le papier conclut que l'échec de la résolution du problème ne vient pas du fait que les mathématiques sont trop difficiles, mais du fait que la description était trop faible.

Coordonnées de Vecteurs : Comme essayer de résoudre un puzzle en regardant les pièces une par une. Le détective de degré 4 est confus et pense que le puzzle est soluble alors qu'il ne l'est pas.
Coordonnées de Projecteurs : Comme regarder l'image sur la boîte du puzzle. Le détective de degré 4 peut immédiatement voir le motif et réaliser que le puzzle est impossible.

Pourquoi Cela Importe pour la Question Spécifique

Le papier traite spécifiquement du « Randomstrasse101 Open Problem 23 », qui portait sur les deux méthodes « Vecteur ».

Réponse : Non. Une preuve par Somme de Carrés de degré 4 utilisant ces descriptions vectorielles spécifiques ne peut pas prouver que 7 Bases Mutuellement Impariales n'existent pas en 6 dimensions.
Nuance : Cela ne signifie pas qu'aucune preuve n'existe. Cela signifie simplement que cette façon spécifique et directe d'écrire le problème est trop faible pour un algorithme de degré 4. Si vous passez à la méthode du « Projecteur », l'algorithme devient assez fort pour trouver la limite.

En bref : Le papier montre que si vous décrivez le problème en utilisant les coordonnées brutes, un ordinateur avec une « vision » limitée (degré 4) sera trompé en pensant que l'impossible est possible. Mais si vous décrivez le problème en utilisant des « ombres » (projecteurs), ce même ordinateur peut voir la vérité.

Résumé Technique : L'SoS de degré quatre en coordonnées vectorielles ne peut détecter la borne supérieure des MUB

Énoncé du problème
L'article traite du Problème ouvert de Randomstrasse101, n° 23, qui demande s'il existe une preuve Sum-of-Squares (SoS) de degré quatre démontrant que sept bases mutuellement non biaisées (MUB) n'existent pas dans $\mathbb{C}^6$ . Le problème est formulé en utilisant deux encodages spécifiques de coordonnées vectorielles :

Formulation d'égalité quartique : Les contraintes sont encodées sous forme de relations quartiques sur les parties réelles et imaginaires des composantes vectorielles, spécifiquement $|\langle v, w \rangle|^2 = 1/d$ .
Formulation semi-définie hermitienne $2 \times 2$ : Les conditions de bases croisées sont encodées comme des contraintes semi-définies sur des matrices hermitiennes $2 \times 2$ impliquant le produit scalaire quadratique $\langle v, w \rangle$ .
Le contexte plus large concerne la borne supérieure connue $m \le d + 1$ pour le nombre de MUB dans une dimension $d$ . Alors que l'égalité est vérifiée pour les dimensions de puissance première, le cas $d=6$ reste ouvert, avec la conjecture que $m=7$ est impossible.

Méthodologie
Les auteurs analysent la puissance des relaxations SoS de degré quatre en construisant des pseudo-espérances de degré quatre. Une pseudo-espérance de degré quatre est une fonctionnelle linéaire $\tilde{\mathbb{E}}$ sur les polynômes de degré au plus quatre qui satisfait la positivité ( $\tilde{\mathbb{E}}[f^2] \ge 0$ ) et la cohérence avec les contraintes. Si une telle pseudo-espérance existe pour un système, aucune réfutation SoS de degré quatre (preuve d'infaisabilité) n'existe.

La méthodologie centrale implique :

Construction de type Haar-aléatoire : Les auteurs définissent une pseudo-espérance basée sur l'espérance sur des matrices unitaires de type Haar indépendantes. Spécifiquement, pour $m$ bases dans $\mathbb{C}^d$ , les vecteurs sont pris comme colonnes de matrices unitaires aléatoires indépendantes.
Vérification des contraintes :
- Contraintes de même base : L'orthonormalité est vérifiée point par point (exactement) pour la construction aléatoire.
- Contraintes de bases croisées : Pour des vecteurs unitaires de Haar-aléatoires indépendants $x, y$ , l'espérance est $\mathbb{E}[|\langle x, y \rangle|^2] = 1/d$ .
Analyse du multiplicateur affine : Pour la formulation semi-définie, les auteurs prouvent une borne spécifique sur la norme d'opérateur de la multiplication par le produit scalaire $z = \langle x, y \rangle$ agissant sur des fonctions affines-linéaires. Ils montrent que $|\mathbb{E}[p z q]| \le \frac{1}{d} \sqrt{\mathbb{E}[|p|^2]\mathbb{E}[|q|^2]}$ .
Comparaison des formulations : L'article contraste la formulation en coordonnées vectorielles avec une formulation en coordonnées de projecteurs où les variables sont des projecteurs de rang un $P = vv^*$ . Dans ce cadre, la condition d'unbiasedness croisée devient quadratique ( $\text{Tr}(P_i^{(k)} P_j^{(\ell)}) = 1/d$ ).

Contributions clés et résultats

Borne inférieure pour les formulations en coordonnées vectorielles :
Le résultat principal (Théorèmes 5.1 et 7.1) établit que pour toute dimension $d$ et pour tout nombre de bases $m$ proposé, le système MUB standard en coordonnées vectorielles admet une pseudo-espérance de degré quatre dérivée de bases de Haar-aléatoires indépendantes.
- Égalité quartique : La pseudo-espérance satisfait les contraintes quartiques car la valeur espérée du terme quartique $|\langle x, y \rangle|^2 - 1/d$ est nulle. Puisque les contraintes sont de degré quatre, une réfutation de degré quatre ne peut que multiplier ces termes par des constantes, ce que la pseudo-espérance annule.
- Formulation semi-définie : En utilisant la borne du multiplicateur affine (Théorème 6.1), les auteurs montrent que la pseudo-espérance satisfait les contraintes de localisation de degré quatre pour les matrices hermitiennes $2 \times 2$ .
- Conséquence : Le SoS de degré quatre dans ces formulations de coordonnées vectorielles ne peut pas réfuter l'existence de $m$ MUB, même lorsque $m > d + 1$ (où les MUB sont connues ou conjecturées comme impossibles). Spécifiquement, pour $d=6, m=7$ , aucune preuve de non-existence par SoS de degré quatre n'existe dans ces encodages.
Séparation des formulations (Projecteur vs Vecteur) :
L'article démontre que cet échec est spécifique à l'encodage en coordonnées vectorielles. Dans une formulation en coordonnées de projecteurs (Théorème 8.1), où les variables sont des projecteurs centrés $Q = P - I/d$ , les contraintes d'unbiasedness croisée sont quadratiques.
- Les auteurs construisent une réfutation SoS de degré quatre pour le système de projecteurs chaque fois que $m > d + 1$ .
- Cette réfutation repose sur une identité de matrice de Gram impliquant la trace des sommes de carrés de projecteurs, ce qui produit une constante négative modulo les contraintes quand $m > d + 1$ .
- Résultat : Le SoS de degré quatre peut récupérer la borne supérieure élémentaire $m \le d + 1$ dans la formulation de projecteurs.

Signification et affirmations
L'article revendique une séparation dépendante de la formulation dans la puissance des hiérarchies SoS de faible degré pour le problème des MUB :

Réponse négative au Problème ouvert 23 : Pour les deux encodages de coordonnées vectorielles spécifiques décrits dans l'énoncé du problème (équations quartiques et LMI $2 \times 2$ ), la réponse est négative. Le SoS de degré quatre est intrinsèquement trop faible pour détecter l'obstruction de comptage élémentaire ( $m \le d + 1$ ).
Sensibilité à la formulation : L'incapacité du degré quatre SoS à résoudre le problème n'est pas une limitation universelle de la méthode, mais une limitation de la relaxation directe en coordonnées vectorielles. Le même degré de relaxation est strictement plus fort lorsqu'il est appliqué aux coordonnées de projecteurs, où il récupère avec succès la borne supérieure connue.
Implication pour $d=6$ : Bien que la formulation de projecteur récupère $m \le 7$ pour $d=6$ , l'article note que le cas $d=6, m=7$ est la frontière "serrée" de cette borne. Par conséquent, le résultat de séparation ne répond pas définitivement si une preuve de degré quatre plus forte en variables de projecteurs peut exclure exactement sept MUB en $\mathbb{C}^6$ , mais qu'elle peut exclure huit MUB ou plus.

Le travail isole une obstruction spécifique de degré quatre pour le SoS en coordonnées vectorielles, suggérant que toute approche réussie par SoS de faible degré au problème des MUB en dimension six doit utiliser une formulation levée (telle que les projecteurs) plutôt que les coordonnées vectorielles directes.