Solvabilité du remplissage matriciel

La matrice a la dimension . Nous voulons remplir utilisant des entiers compris entre et , inclus. $A$ $n \times n(n-1)$ $A$ $1$ $n$

Exigences:

Chaque colonne de est une permutation de . $A$ $1, \dots, n$
Toute sous-matrice formée de deux rangées de ne peut pas avoir de colonnes identiques. $A$

Question:

Est-il possible de remplir la matrice répondant aux exigences?

Relation avec la cryptographie:

Chaque numéro de ligne correspond à un texte en clair. Chaque colonne correspond à une clé. Puisqu'une clé définit une injection, chaque colonne doit être une permutation. La deuxième exigence est le secret parfait pour deux messages.

co.combinatorics cr.crypto-security coding-theory Cyker
la source

Étant donné que vous avez marqué cela avec cr.crypto-security, cela améliorerait la question si vous pouviez indiquer comment cela se rapporte à crypto / security.

Dave Clarke

Observations simples: une telle matrice existe pour n≤4. Pour n≤3, prenez toutes les permutations. Pour n = 4, les seules solutions prennent toutes les permutations paires ou toutes les permutations impaires.

Tsuyoshi Ito

Merci, Ito. En fait, j'ai trouvé la réponse lorsque

à la main. Mais les choses deviennent beaucoup plus difficiles lorsque

. Une explosion exponentielle se produit.

n \leq 4

$n \leq 4$

n \geq 5

$n \geq 5$

Cyker

(1) Je pense que le problème est lié à la théorie du codage et l'a ajouté comme balise. (2) Une autre observation: le problème peut également être énoncé comme suit. Trouvez une matrice B de taille n × (n ^ 2) telle que chacune des n premières colonnes de B soit les n répétitions du même nombre et telle que B remplisse la condition 2 de la question. Si un tel B existe, alors chacune des n (n − 1) dernières colonnes de B doit être une permutation. Inversement, toute matrice A satisfaisant aux conditions 1 et 2 peut être convertie en matrice B en attachant les n colonnes indiquées à gauche de A.

Tsuyoshi Ito

Réponses:

Tsuyoshi, belle observation dans ton commentaire! Je pense que cela résout presque le problème.

Considérez les deux questions suivantes

Existe-t-il lignes de longueur sorte qu'aucun nombre n'apparaisse deux fois dans une colonne, et pour chaque paire de lignes, toutes les paires ordonnées données par les colonnes sont distinctes? $k$ $n(n-1)$
Existe-t-il lignes de longueur pour que pour chaque paire de lignes, toutes les paires ordonnées données par les colonnes soient distinctes? $k$ $n^2$

L'observation de Tsuyoshi dans son commentaire montre que si vous pouvez atteindre une valeur pour la question (1), vous pouvez atteindre la même valeur pour la question (2). Nous montrons maintenant que si nous pouvons atteindre une valeur pour la question (2), nous pouvons atteindre la valeur pour la question (1). Ainsi, la réponse à ces deux questions est presque la même. $k$ $k$ $k$ $k-1$

La construction se déroule comme suit: Ignorez la première ligne, sauf mettez tous les dans les premières positions. Vous pouvez maintenant appliquer une permutation des valeurs à chacune des lignes restantes de sorte que, à l'exception de la première entrée, chacune des premières colonnes contient des valeurs identiques, et par l'observation de Tsuyoshi dans le commentaire, cela vous donne un ensemble de lignes satisfaisant votre condition. $1$ $n$ $\lbrace 1, 2, \ldots, n \rbrace$ $k-1$ $n$ $k-1$

Maintenant, si vous avez un ensemble de lignes de longueur avec chaque paire de lignes contenant toutes les paires ordonnées dans chaque colonne, alors cela équivaut à un ensemble de carrés latins orthogonaux . Chacune des lignes , , , donne un carré latin. Pour obtenir le carré latin associé à la ligne , mettez la valeur dans la ème colonne de la ligne dans la cellule dont les coordonnées sont données par la paire ordonnée dans la ème colonne des deux premières lignes. $k$ $n^2$ $k-2$ $3$ $4$ $\ldots$ $k$ $j$ $i$ $j$ $i$

Si n'est pas une puissance première, combien de carrés latins mutuellement orthogonaux d'ordre existent est un problème ouvert célèbre, et je ne crois pas qu'aucun ensemble de carrés latins orthogonaux existe pour pas une puissance première; le consensus général est que de tels ensembles n'existent pas. Le seul résultat prouvé jusqu'à présent est qu'un tel ensemble n'existe pas pour . On sait que le nombre de lignes possibles croît au moins comme pour certains $n$ $n$ $n-2$ $n$ $n=6$ $k$ $k=\Omega(n^c)$ $c$ . Je crois qu'il y a 8 carrés latins orthogonaux d'ordre 10 est encore ouvert. (On sait qu'il n'y en a pas 9, mais en raison de la différence possible de dans la réponse aux deux questions, cela ne nous dit rien sur le problème d'origine.) $1$

Pour , le maximum que vous pouvez obtenir est de 3, et il s'avère que vous pouvez obtenir trois lignes pour le problème (1) en regardant n'importe quel carré latin avec une transversale, dont il existe de nombreux exemples non équivalents . Pour , il existe des constructions connues donnant deux carrés latins orthogonaux. Si ces carrés ont une transversale commune, alors vous pouvez obtenir pour le problème (1). $n=6$ $k$ $6\times 6$ $n=10$ $k=4$

Peter Shor
la source

Merci pour l'analyse détaillée, professeur Shor! Donc, à partir de ce raisonnement, 1) S'il n'existe pas un ensemble de

MOLS, nous pouvons affirmer que le problème d'origine n'est pas faisable pour

. 2) S'il existe un ensemble de

MOLS, nous pouvons affirmer que le problème d'origine est faisable pour

. Puisque lorsque

est une puissance première, il existe un ensemble de

MOLS, cela donne une vue alternative de la solution partielle d'Ito. Et nous avons constaté que le problème d'origine n'est pas réalisable lorsque

. Vraiment admirable!

n - 2

$n - 2$

n

$n$

n - 1

$n - 1$

n

$n$

n

$n$

n - 1

$n - 1$

n = 6

$n = 6$

Cyker

Ceci est une très belle connexion. Merci d'avoir répondu! Un point mineur: selon Wikipedia, il est connu que n − 1 carrés latins orthogonaux existent pour n puissance principale, pas seulement pour n premier.

Tsuyoshi Ito

@Tsuyoshi - Oups. Je le savais; Je viens de le dire mal. La construction provient de champs finis. Merci pour la correction. Réparer maintenant.

Peter Shor

Je l'ai deviné. :)

Tsuyoshi Ito

Ceci est une solution partielle. Une telle matrice existe si n est une puissance première.

Soit F le corps fini d'ordre n . Nous construisons une matrice n × n ( n −1) dont les lignes sont étiquetées par F , dont les colonnes sont étiquetées par ( F ∖ {0}) × F , et dont les entrées sont en F comme suit: la i- ème ligne de la la colonne étiquetée ( a , b ) est donnée par ai + b . En d'autres termes, chaque colonne correspond à un polynôme de degré dans une F . Ensuite, chaque colonne contient chaque élément de F exactement une fois, et deux colonnes n'ont pas les mêmes entrées sur plus d'une ligne car les valeurs de deux polynômes de degré un distincts peuvent coïncider au plus en un point.

(Si vous voulez une matrice dont les entrées sont dans {1,…, n } au lieu de dans F , remplacez arbitrairement les éléments de F par {1,…, n }.)

Tsuyoshi Ito
la source

n + 1

$n + 1$

@Artem: Il peut y en avoir, surtout compte tenu de la réponse de Peter reliant cette question aux carrés latins orthogonaux. (Avertissement: à mon avis, les carrés latins orthogonaux, les MUB, les conceptions combinatoires, les conceptions unitaires et les SIC-POVM sont presque indiscernables.)

Tsuyoshi Ito,

Merci beaucoup, Ito! Cette conception est vraiment magnifique!

Cyker