2025-11-20T04:37:14.527636

On the number of partitions of the hypercube ${\bf Z}_q^n$ into large subcubes

Tarannikov
We prove that the number of partitions of the hypercube ${\bf Z}_q^n$ into $q^m$ subcubes of dimension $n-m$ each for fixed $q$, $m$ and growing $n$ is asymptotically equal to $n^{(q^m-1)/(q-1)}$. For the proof, we introduce the operation of the bang of a star matrix and demonstrate that any star matrix, except for a fractal, is expandable under some bang, whereas a fractal remains to be a fractal under any bang.
academic

Sur le nombre de partitions de l'hypercube Zqn{\bf Z}_q^n en grands sous-cubes

Informations fondamentales

  • ID de l'article: 2411.04479
  • Titre: Sur le nombre de partitions de l'hypercube Zqn{\bf Z}_q^n en grands sous-cubes
  • Auteur: Yuriy Tarannikov (Institut de Mathématiques Sobolev, Branche sibérienne de l'Académie russe des sciences; Université d'État de Moscou Lomonosov)
  • Classification: math.CO (Combinatoire), cs.DM (Mathématiques discrètes)
  • Date de publication: Novembre 2024 (prépublication arXiv)
  • Lien de l'article: https://arxiv.org/abs/2411.04479

Résumé

Cet article démontre que pour qq, mm fixés et nn croissant, le nombre de partitions de l'hypercube Zqn{\bf Z}_q^n en qmq^m sous-cubes de dimension n−mn-m est asymptotiquement égal à n(qm−1)/(q−1)n^{(q^m-1)/(q-1)}. Pour prouver ce résultat, l'auteur introduit l'opération « bang » sur les matrices étoilées et démontre que, à l'exception des matrices fractales, toute matrice étoilée est extensible sous une certaine opération bang, tandis que les matrices fractales conservent leur caractère fractal sous toute opération bang.

Contexte et motivation de la recherche

Contexte du problème

  1. Problème central: Étudier le nombre de partitions de l'hypercube Zqn{\bf Z}_q^n en sous-cubes de même dimension, en particulier pour les sous-cubes de grande dimension
  2. Pertinence pratique:
    • Relation avec les formules CNF insatisfaisables de fonctions booléennes, notamment le problème k-SAT
    • Relation avec la théorie des conceptions de blocs associatifs (ABD), applications aux algorithmes de hachage
    • Importance capitale dans la théorie des conceptions combinatoires

Motivation de la recherche

  1. Perfectionnement théorique: Les recherches existantes se concentrent principalement sur les partitions en sous-cubes de petite dimension, manquant d'analyse asymptotique précise pour les cas de grande dimension
  2. Innovation méthodologique: Nécessité de nouveaux outils techniques pour traiter les problèmes complexes de comptage combinatoire
  3. Motivation applicative: Relation avec les problèmes pratiques en théorie de la complexité computationnelle et en cryptographie

Contributions principales

  1. Théorème principal: Démonstration de la formule asymptotique précise Pcoordq(n,m)∼n(qm−1)/(q−1)P_{coord}^q(n,m) \sim n^{(q^m-1)/(q-1)}
  2. Innovation technique: Introduction de l'opération « bang » sur les matrices étoilées, un nouvel outil de transformation matricielle
  3. Caractérisation structurelle: Caractérisation complète de la structure des matrices étoilées non-extensibles, démonstration que seules les matrices fractales sont non-extensibles
  4. Valeurs exactes: Détermination des valeurs exactes des paramètres clés: rcoordq(m)=qm−1q−1r_{coord}^q(m) = \frac{q^m-1}{q-1} et Pcoord∗q(qm−1q−1,m)=(qm−1q−1)!P_{coord*}^q\left(\frac{q^m-1}{q-1}, m\right) = \left(\frac{q^m-1}{q-1}\right)!

Détail des méthodes

Définition de la tâche

Entrée: Paramètres q≥2q \geq 2, m≥0m \geq 0, n≥mn \geq mSortie: Nombre de partitions non-ordonnées distinctes de Zqn{\bf Z}_q^n en qmq^m sous-cubes de dimension n−mn-mContraintes: Considération des partitions A-primitives (chaque coordonnée est fixée dans au moins un sous-cube)

Concepts fondamentaux

Motifs étoilés et matrices étoilées

  • Motif étoilé: Vecteur de longueur nn dont les éléments appartiennent à Zq∪{∗}{\bf Z}_q \cup \{*\}, où ∗* désigne une composante « libre »
  • Matrice étoilée: Matrice dont les lignes contiennent tous les motifs étoilés des sous-cubes de la partition
  • A-primitivité: La matrice étoilée ne contient pas de colonne entièrement composée de ∗*

Matrices étoilées fractales

Matrice spéciale définie récursivement Mq,mM_{q,m}:

  • Mq,0M_{q,0}: Matrice avec une ligne et zéro colonne
  • Mq,mM_{q,m} construite récursivement à partir de Mq,m−1M_{q,m-1}:
undefined