\documentclass[11pt,reqno]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage[colorlinks]{hyperref}
%\usepackage{floatflt}
%\usepackage{wrapfig}
%\usepackage{caption2}
\usepackage{multirow,mathdots}
%\usepackage{ulem}
\usepackage{tikz}
\usetikzlibrary{positioning, arrows, shapes, decorations.pathreplacing, calc}
\usetikzlibrary{matrix}

\tikzset{x=0.9em,y=1.1em} % этими параметрами регулируем шаг ячейки по гориз. и верт.
\def\ccolor#1{ ++(1,0) node [rectangle,  minimum size=1] {\raisebox{-0.25em}[0.2em][0em]{\makebox[0mm][c]{#1}}} }

\usepackage{titlesec}
\titlespacing{\section}{0pt}{2.5ex}{1.5ex}
\titlespacing{\subsection}{0pt}{1.5ex}{1ex}
\titlespacing{\subsubsection}{0pt}{1.5ex}{1ex}
\titleformat{\section}{\large\bfseries\centering}{\thesection}{1em}{}
\titleformat{\subsection}[runin]{\bfseries}{\thesubsection.}{0.5em}{}[.\mbox{\ }]
\titleformat{\subsubsection}[runin]{\bfseries}{\thesubsubsection.}{0.4em}{}[.\mbox{\ }]



%%%%%---------- ORCiD
\newcommand\orcidicon[1]{\href{https://orcid.org/#1}{\includegraphics[scale=0.02]{orcid.pdf}}}

\def\udcs{519.115.5} %Здесь автор определяет УДК своей работы
\def\mscs{05A18} %Здесь автор определяет классификаторы AMS своей работы
\setcounter{page}{1144}

\newtheorem{lemma}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem{definition}{Определение}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}
\newtheorem{observation}{Наблюдение}
\newtheorem{property}{Свойство}
\newtheorem{remark}{Замечание}


\definecolor{myblue}{rgb}{0.03, 0.27, 0.79}

\hypersetup{linkcolor=blue,filecolor=black,urlcolor=blue, citecolor=blue}

\def\logo{\textcolor{blue}{{\bf\Huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}}

\def\semrtop
     {
  \vbox{
     \noindent\logo \hspace{-3mm}  \parbox{12cm}{     \begin{center}
     {\LARGE \textsf{СИБИРСКИЕ ЭЛЕКТРОННЫЕ}} \\[2mm]
     {\LARGE \textsf{МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ}} \\[2mm]
     {\Large \textsf{Siberian Electronic Mathematical Reports}} \\[1mm]
     {\Large\tt{\textcolor{blue}{http://semr.math.nsc.ru}}}\\[1mm]
     \raisebox{1ex}{ISSN 1813-3304 }
     \vspace*{-3mm}
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
}
     \vspace{-1mm}
     \noindent
      \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!} \\
     \hline\hline
     \end{tabular}

     \vspace{3mm}
     {\flushleft\it Том 21, № 2, стр. 1144--1162 (2024) \hspace{\fill}{\rm\small УДК \udcs \hspace{-4mm}}}
     \newline
     	{\rm\small \textcolor{blue}{https://doi.org/10.33048/semi.2024.21.???}}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaa\;}{\rm\small MSC\ \ \mscs }
  }%\vbox
}



\begin{document}
\renewcommand{\refname}{References}


\thispagestyle{empty}

\title[\sc О числе разбиений на большие подкубы]{\large О числе разбиений гиперкуба ${\bf Z}_q^n$ на большие подкубы}
\author[Ю.В. ТАРАННИКОВ]{{\bf \large \textsc{Ю.В. Таранников}}\protect\orcidicon{0000-0001-8827-2630}\\ \\
\textit{Представлено} \textsc{А.В. Пяткиным}
%\textit{(заполняется редактором)}
}%
\address{Yuriy Valer'evich Tarannikov  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} pr. Koptyuga, 4,
\newline\hphantom{iii} 630090, Novosibirsk, Russia,
\newline\hphantom{iii} Mech. \& Math. Department,
\newline\hphantom{iii} Lomonosov Moscow State University,
\newline\hphantom{iii} 119992, Moscow, Russia}%
\email{\textcolor{blue}{yutarann@gmail.com}}%

\thanks{\sc Tarannikov, Yu.V.,
On the number of partitions of the hypercube ${\bf Z}_q^n$ into large subcubes}
\thanks{\copyright \ 2024 Таранников Ю.В}
\thanks{\rm Теоремы \ref{some_tight_values} и \ref{some_asymptotics} получены при финансовой поддержке Минобрнауки России в рамках реализации программы Московского центра фундаментальной и прикладной математики по соглашению \No 075--15--2022--284, теоремы \ref{tight_values} и \ref{th_asymp} получены за счет Российского Научного Фонда, грант \No 22--11--00266, \url{https://rscf.ru/ en/project/22-11-00266/}.}
\thanks{\it Поступила 5 ноября 2024 г., опубликована 31 декабря 2024 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\bf Abstract:} 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.\medskip

\noindent{\bf Keywords:} combinatorics, enumeration, asymptotics, partition, partition of hypercube, subcube, star pattern, star matrix, fractal matrix, associative block design, SAT, $k$-SAT.
 \end{quote}
}

\bigskip

\section{Введение}

Пусть $q,m,n$ --- целые числа, $q\ge 2$, $n\ge m\ge 0$.
Подкубом размерности $n-m$ в ${\bf Z}_q^n$ называется такое подмножество наборов ${\bf Z}_q^n$, у которого некоторые $m$ компонент фиксированы, а каждая из остальных $n-m$ компонент пробегает все возможные значения из ${\bf Z}_q$.

При {\it разбиении на подкубы} каждый набор из ${\bf Z}_q^n$ должен попасть ровно в один подкуб.
Разбиение на подкубы называется {\it Aгиевич-при\-ми\-тив\-ным}, или просто
{\it А-примитивным}\footnote{Агиевич в \cite{Agievich08} ввел для этого понятия (в более общем случае разбиения на аффинные подпространства) термин <<примитивный>>, однако использование этого термина небесспорно, поскольку он характеризует скорее некоторую невырожденность разбиения. Кроме того, подобного рода невырожденность разбиения можно определять разными способами, а слово <<примитивный>> в математике вообще перегружено. В то же время давать другой термин тоже представляется неправильным, поэтому в \cite{Tar22} было предложено называть такое разбиение {\it примитивным по Агиевичу} или {\it А-примитивным}. Заметим, что в \cite{FHKIRSV23} авторы использовали для этого же понятия термин <<{\it tight}>>, который также не представляется нам <<точным>>.}, если каждая компонента зафиксирована хотя бы в одном из подкубов разбиения.


Наиболее известна задача о разбиении на подкубы малой размерности. Так, если все подкубы разбиения булева куба имеют размерность $1$, то эти подкубы являются ребрами, а разбиения называются совершенными паросочетаниями, и задача об их числе хорошо известна. В \cite{ABP24} рассматриваются задачи разбиения булева куба на подкубы, преимущественно малых размерностей, которые в том числе могут быть разными в составе одного разбиения.

Разбиения на подкубы (не обязательно одной размерности) с дополнительным условием неприводимости исследуются в статье \cite{FHKIRSV23} мотивацией которой стало то, что разбиения на подкубы в двоичном случае соответствуют невыполнимым булевым КНФ специального вида. Заметим, что рассматривающиеся в нашей статье разбиения на подкубы коразмерности не более $k$, где $k$ --- константа, в упомянутом контексте соответствуют невыполнимым КНФ специального вида из задачи $k$-SAT.

 Разбиениям на одномерные подкубы в не обязательно двоичном случае посвящена работа \cite{Pot11}.
Разбиение на подкубы одинаковой размерности
является частным случаем $A(n,q,w,t)$-дизайнов, выражение числа которых через многомерные перманенты рассматривалось в \cite{Pot14}.

Главным предметом изучения в \cite{Tar22} были разбиения на аффинные подпространства, а для разбиений на подкубы, являющихся частным случаем разбиений на аффинные подпространства,
доказаны следующие утверждения, ориентированные на разбиения на подкубы одинаковой большой размерности.

\begin{theorem}\label{coord_thm}~\cite{Tar22}
Пусть $q\ge 2$. Для любого натурального $m$ существует наименьшее натуральное $N$, такое что при $n>N$ не существует А-примитивных разбиений ${\bf Z}_q^n$ на $q^m$ подкубов размерности $n-m$.
\end{theorem}

Введем следующие обозначения:
\begin{itemize}
\item{$N^{\rm coord}_q(m)$ --- наименьшее $N$ из теоремы \ref{coord_thm};}
\item{$c^{\rm coord}_q(n,m)$ --- число различных неупорядоченных разбиений ${\bf Z}_q^n$ на $q^m$ подкубов размерности $n-m$;}
\item{$c^{\rm coord*}_q(n,m)$ --- число различных неупорядоченных А-примитивных разбиений ${\bf Z}_q^n$ на $q^m$ подкубов размерности $n-m$.}
\end{itemize}

\begin{theorem}~\cite{Tar22}
Справедлива формула
\begin{equation}\label{eq:coord_formula_modified}
c^{\rm coord}_q(n,m)=\sum\limits_{h=m}^{N^{\rm coord}_q(m)} \binom{n}{h} c^{\rm coord*}_q(h,m).
\end{equation}
\end{theorem}

\begin{theorem}\label{general_form_of_asymptotics}~\cite{Tar22}
Пусть $q$ и $m$ фиксированы, $n\to\infty$. Тогда имеет место асимптотика
\begin{equation*}
c^{\rm coord}_q(n,m)\sim C'n^{N^{\rm coord}_q(m)},
\end{equation*}
где $C'=\frac{c^{\rm coord*}_q(N^{\rm coord}_q(m),m)}{N^{\rm coord}_q(m)!}$.
\end{theorem}

Также в \cite{Tar22} получены оценки $\frac{q^m-1}{q-1}\le N^{\rm coord}_q(m)\le m\cdot q^{m-1}$
и установлены точные значения $N^{\rm coord}_q(2)=q+1$.

Главным результатом настоящей работы является следующая теорема \ref{th_asymp}, полное доказательство
\footnote{Заметим, что в 2024 г. нами были направлены на конференцию <<Проблемы теоретической кибернетики>> следующие теоремы \ref{some_tight_values} и \ref{some_asymptotics} без доказательств.

\begin{theorem}\label{some_tight_values}
Имеют место точные значения $N^{\rm coord}_2(4)=15$, $N^{\rm coord}_2(5)=31$,
$N^{\rm coord}_q(3)=q^2+q+1$,
$c^{\rm coord*}_2(15,4)=15!$,
$c^{\rm coord*}_2(31,5)=31!$,
$c^{\rm coord*}_q(q^2+q+1,3)=(q^2+q+1)!$.
\end{theorem}

\begin{theorem}\label{some_asymptotics}
При $n\to\infty$ справедливы асимптотики
$c^{\rm coord}_2(n,4)\sim n^{15}$,
$c^{\rm coord}_2(n,5)\sim n^{31}$,
$c^{\rm coord}_q(n,3)\sim n^{q^2+q+1}$.
\end{theorem}

Доказательства теорем \ref{some_tight_values} и \ref{some_asymptotics}, полученные первоначально существенно другим методом, в настоящей работе не приводятся, поскольку их утверждения являются частными случаями теорем \ref{tight_values} и \ref{th_asymp}, соответственно.}
которой будет получено в конце работы после введения необходимых понятий и доказательства вспомогательных утверждений.


\begin{theorem}\label{th_asymp}
Пусть $q,m$ --- фиксированные натуральные числа, $q>1$. Тогда при $n\to\infty$ справедлива асимптотика
\begin{equation}\label{eq:main_asymptotics}
c^{\rm coord}_q(n,m)\sim n^{\frac{q^m-1}{q-1}}.
\end{equation}
\end{theorem}




\section{Звездные матрицы разбиений и их свойства}

{\it Звездным паттерном} подкуба гиперкуба ${\bf Z}_q^n$ называется набор длины $n$ над ${\bf Z}_q\cup \{*\}$, где элементы
${\bf Z}_q$ соответствуют зафиксированным компонентам, в то время как $*$ соответствует
<<свободной>> компоненте.

Например, набор $(0,*,1,0,*)$ является звездным паттерном следующего подкуба в ${\bf Z}_2^5$:
\begin{equation*}
\begin{array}{ccc}
\{&(0,0,1,0,0),&\cr
 &(0,0,1,0,1),&\cr
&(0,1,1,0,0),&\cr
&(0,1,1,0,1)&\}.
\end{array}
\end{equation*}
Матрица, по строкам которой выписаны звездные паттерны всех подкубов разбиения, называется {\it звездной матрицей} разбиения.

Например, звездная матрица
\begin{equation*}
\left(
\begin{array}{ccc}
0, & 0, &*\cr
0, & 1, &*\cr
1, & *, &0\cr
1, & *, &1
\end{array}
\right)
\end{equation*}
задает разбиение ${\bf Z}_2^3$ на $2^2$ подкубов размерности $3-2=1$ каждый.

Легко видеть, что разбиение ${\bf Z}_q^n$ на $q^m$ подкубов одинаковой размерности $n-m$ задается звездной матрицей, имеющей в точности $q^m$ строк и $n$ столбцов, и является А-примитивным тогда и только тогда, когда его звездная матрица не содержит столбца из одних $*$. Звездную матрицу А-примитивного разбиения будем
также называть {\it А-примитивной.}

Заметим, что частным случаем разбиения на подкубы являются {\it ассоциативные блок-дизайны (АБД),} которые были введены
Ривестом \cite{Riv1974} для использования в алгоритмах хеширования и изучались в ряде работ (см., например, \cite{Brou1978,vL1985,vLW2001,Pout1986}).
АБД "--- это разбиение ${\bf Z}_2^n$ на подкубы одинаковой размерности с дополнительным требованием: в матрице разбиения каждый столбец содержит одно и то же число звездочек. Из определения очевидно, что АБД является А-примитивным разбиением. В работах по АБД были развиты элементы техники изучения звездных матриц, которые полезны и в более общем, чем АБД, случае.

{\it Размером столбца} звездной матрицы будем называть количество чисел в нем. {\it Перекрытием} двух столбцов будем называть множество строк, в которых эти столбцы одновременно содержат числовые значения, а количество таких строк --- {\it размером перекрытия.} Если размер перекрытия двух столбцов равен нулю, то мы говорим, что эти столбцы {\it не перекрываются,} а если размер перекрытия совпадает с размером одного из столбцов, то мы будем говорить, что столбец меньшего размера {\it вложен} в столбец большего размера.
Подматрицу ширины $1$, состоящую из всех чисел, входящих в столбец, и только из них, будем называть {\it стержнем} столбца.

Утверждение теоремы \ref{th_asymp} явится следствием из теоремы   \ref{tight_values},
в которой будут установлены точные значения величин $N^{\rm coord}_q(m)$ и
$c^{\rm coord*}_q\left(N^{\rm coord}_q(m)\right.$, $\left.m\right)$.
В свою очередь, для установления значений, выписанных в формулировке теоремы   \ref{tight_values},
будет произведен анализ А-при\-ми\-тив\-ных звездных матриц
размера $q^m \times N^{\rm coord}_q(m)$.
Дадим формулировки и доказательства нескольких нужных нам лемм о строении звездных матриц.

\begin{lemma}\label{lemma1}
В звездной матрице разбиения гиперкуба ${\bf Z}_q^n$ для любых двух различных строк найдется столбец, имеющий в этих строках разные значения из ${\bf Z}_q$.
\end{lemma}

\begin{proof}
Предположим противное. Пусть в звездной матрице разбиения найдутся две различные строки, для которых нет  столбца, имеющего в этих строках разные значения из ${\bf Z}_q$. Тогда
можно заменить звездочки в этих строках на числа так, что обе строки станут одинаковыми. Получившийся
набор принадлежит обоим подкубам, задаваемым звездными паттернами строк,
поэтому эти подкубы пересекаются, чего в разбиении быть не может.
\end{proof}

\begin{lemma}\label{equality_in_single_column}
В звездной матрице $M$ разбиения гиперкуба ${\bf Z}_q^n$ на подкубы одинаковой размерности в любом столбце все значения из ${\bf Z}_q$ встречаются одинаковое число раз.
\end{lemma}

\begin{proof}
Рассмотрим $i$-й столбец матрицы $M$. Если некоторая строка звездной матрицы $M$ имеет $*$ в $i$-м столбце, то соответствующий подкуб для каждого $a\in {\bf Z}_q$ содержит в точности $q^{n-m-1}$ наборов со значением $a$ в $i$-м столбце.
Если некоторая строка звездной матрицы имеет $a$ в $i$-м столбце, $a\in {\bf Z}_q$, то
все $q^{n-m}$ наборов соответствующего подкуба имеют $a$ в $i$-м столбце.
Любой набор из ${\bf Z}_q^n$ принадлежит в точности одному подкубу разбиения. Отсюда вытекает утверждение леммы \ref{equality_in_single_column}.
\end{proof}

\begin{lemma}\label{equality_for_sums by_modulo_in_two_columns}
Пусть $M$ --- звездная матрица разбиения гиперкуба ${\bf Z}_q^n$ на подкубы одинаковой размерности, $i$ и $j$ --- номера двух ее различных столбцов и $\pi$ --- некоторая перестановка из $S_q$.
Рассмотрим множество $R$ всех таких строк из $M$, которые одновременно имеют в столбцах $i$ и $j$ числовые значения из ${\bf Z}_q$. Тогда сумма $(m_{r,i}+\pi(m_{r,j}))\pmod{q}$, взятая по всем строкам $r$ из $R$, принимает каждое значение из ${\bf Z}_q$ одинаковое число раз.
\end{lemma}

\begin{proof}
Если для всех наборов $a=(a_1,\dots,a_n)$ из ${\bf Z}_q^n$ рассмотреть сумму $(a_i+\pi(a_j))\pmod{q}$, то эта сумма, очевидно, будет принимать каждое из $q$ значений из ${\bf Z}_q$ одинаковое число раз.
Если рассмотреть такую сумму для всех наборов подкуба, звездный паттерн которого содержит звездочку хотя бы в одном из двух разрядов $i$ и $j$, то эта сумма тоже, очевидно, будет принимать каждое из $q$ значений из ${\bf Z}_q$ одинаковое число раз, потому что наборы из подкуба объединяются в этом случае в подмножества по $q$ наборов, отличающихся только в разряде, соответствующем звездочке, и сумма $(a_i+\pi(a_j))\pmod{q}$ на наборах подмножества принимает каждое из $q$ значений по одному разу (потому что сумма по модулю $q$ --- групповая операция). Следовательно, для совокупности подкубов, соответствующих строкам из $R$, сумма $(a_i+\pi(a_j))\pmod{q}$ по всем наборам из этих подкубов должна принимать каждое из $q$ значений из ${\bf Z}_q$ одинаковое число раз. Однако для наборов из подкуба, соответствующего строке $r$ из $R$ сумма $(a_i+\pi(a_j))\pmod{q}$ принимает одно и то же значение, равное $(m_{r,i}+\pi(m_{r,j}))\pmod{q}$, а подкубы по условию содержат одинаковое количество наборов. Отсюда следует утверждение леммы \ref{equality_for_sums by_modulo_in_two_columns}.
\end{proof}

Леммы, близкие к приведенным выше, в чем-то более общие, в чем-то более частные, содержатся в
\cite{Riv1974,Brou1978,vL1985,vLW2001,Pout1986,Pot22}.

Естественно, мы могли сформулировать наши леммы и в более общем виде (в частности, для совокупностей из более чем двух столбцов), однако не преследовали эту цель, ограничившись формулировкой и доказательством лемм в минимальном виде, нужном для полноты изложения наших последующих результатов.


\section{Очевидная нижняя асимптотическая оценка числа разбиений}\label{sec:asymp_lower_bound}

Нижняя асимптотическая оценка
\begin{equation}\label{eq:asymp_lower_bound}
c^{\rm coord}_q(n,m)\ge n^{\frac{q^m-1}{q-1}}(1+o(1))
\end{equation}
является очевидной. Заметим, что ее необязательно доказывать отдельно, потому что асимптотика
величины $c^{\rm coord}_q(n,m)$, представленная в формуле (\ref{eq:main_asymptotics}) теоремы
\ref{th_asymp}, получится автоматически из теоремы \ref{general_form_of_asymptotics} после того, как мы в теореме \ref{tight_values} установим точные значения величин $N^{\rm coord}_q(m)=\frac{q^m-1}{q-1}$ и
$c^{\rm coord*}_q(\frac{q^m-1}{q-1},m)=\left(\frac{q^m-1}{q-1}\right)!$.
Тем не менее, сейчас мы приведем рассуждения, показывающие справедливость оценки
(\ref{eq:asymp_lower_bound}), поскольку эти рассуждения позволят прочувствовать смысл и важность фрактальной матрицы, определение которой мы дадим в следующем разделе.

Итак, разрежем гиперкуб ${\bf Z}_q^n$ по одной из координат на $q$
подкубов\footnote{Если кого-то смущает, что одним разрезом гиперкуб разделяется на $q$ подкубов,
то можно представить, как после одного срезания корешка книги она распадается на несколько блоков.}
 размерности $n-1$. Это можно сделать $n$ способами. Каждый из $q$ получившихся подкубов разрежем одним из $n-1$ способов по одной из его оставшихся координат на подкубы размерности $n-2$ и т.~д., пока не получим разбиение на $q^m$ подкубов размерности $n-m$ каждый. Описанный выше процесс можно осуществить
$$
\prod\limits_{i=0}^{m-1}\prod\limits_{j=1}^{q^i}(n-i)\sim n^{\frac{q^m-1}{q-1}}
$$
способами.

Заметим, что некоторые из этих способов приведут к разрезам разных подкубов по одной координате. Можно доказать, что доля разбиений с такими повторами будет асимптотически мала. Для этого мы поступим следующим образом: запретим осуществлять разбиение двух разных подкубов по одной координате. Все равно у нас число множителей конечно (потому что $q$ и $m$ конечны), а $n$ стремится к бесконечности.

При таком ограничении разбиения, очевидно, будут получаться разными, а их число равно
$$
\prod\limits_{i=1}^{\frac{q^m-1}{q-1}} (n-i+1)\sim n^{\frac{q^m-1}{q-1}},
$$
т.~е. асимптотически, несмотря на ограничения, окажется тем же самым.

Тем самым справедливость оценки (\ref{eq:asymp_lower_bound}) установлена.

Заметим, что описанными выше процедурами можно получить не все разбиения.
Так, например, в разбиении, задаваемом звездной матрицей, приведенной в статье Ривеста \cite{Riv1974},
разрез исходного гиперкуба по любой из координат приведет к разрезанию некоторых подкубов разбиения, потому что в каждом столбце есть звездочки (см.~рис.~\ref{fig:star_matrix_of_Rivest}). Поэтому вопрос о верхней оценке величины
$c^{\rm coord}_q(n,m)$ требует дополнительного исследования, которое мы проведем в данной работе.

\begin{figure}[ht]
\centering
$$
\left(\begin{array}{cccc}
0&0&*&0\cr
1&0&0&*\cr
*&1&0&0\cr
1&*&1&0\cr
1&1&*&1\cr
0&1&1&*\cr
*&0&1&1\cr
0&*&0&1
\end{array}\right)
$$
\caption{Звездная матрица со звездочками во всех столбцах.}
\label{fig:star_matrix_of_Rivest}
\end{figure}

%\begin{figure}[ht]
%\centering
%\includegraphics[width=0.1\textwidth]{star_matrix_of_Rivest}
%\caption{Звездная матрица со звездочками во всех столбцах.}
%\label{fig:star_matrix_of_Rivest}
%\end{figure}

\section{Фрактальные звездные матрицы и их свойства}

Введем матрицы $M_{q,m}$ рекурсивно следующим образом. Матрица $M_{q,0}$ имеет одну строку и нуль столбцов\footnote{Если матрица с одной строкой и нулем столбцов кому-то кажется казуистической, то можно начинать с матрицы $M_{q,1}$, имеющей $q$ строк и один столбец и представляющей собой вертикальный столбец из выписанных подряд в возрастающем порядке всех чисел из ${\bf Z}_q$.},
матрица $M_{q,m}$, $m=1,\dots,$ определяется через матрицу $M_{q,m-1}$, как представлено на
рис.~\ref{fig:recursive_construction_of_fractal_matrix},
\begin{figure}[ht]
\centering
$$
M_{q,m} =
\begin{tabular}{|c|c|c|c|c|}
    \hline
    $0$ & \multirow{3}{*}{\large $M_{q,m-1}$}&
        \multirow{3}{*}{\large $\scalebox{2}{$*$}_{q,m-1}$}&
        \multirow{3}{*}{\large $\cdots$}&
        \multirow{3}{*}{\large $\scalebox{2}{$*$}_{q,m-1}$}\\
    $\vdots$ &&&&\\
    $0$ &&&& \\ \hline
    $1$ & \multirow{3}{*}{\large $\scalebox{2}{$*$}_{q,m-1}$}&
        \multirow{3}{*}{\large $M_{q,m-1}$}&
        \multirow{3}{*}{\large $\cdots$}&
        \multirow{3}{*}{\large $\scalebox{2}{$*$}_{q,m-1}$}\\
    $\vdots$ &&&&\\
    $1$ &&&& \\ \hline
     \multirow{3}{*}{\large $\vdots$}&
     \multirow{3}{*}{\large $\vdots$}&
        \multirow{3}{*}{\large $\vdots$}&
        \multirow{3}{*}{\large $\ddots$}&
        \multirow{3}{*}{\large $\vdots$}\\
    &&&&\\
    &&&&\\ \hline
    $q{-}1$ & \multirow{3}{*}{\large $\scalebox{2}{$*$}_{q,m-1}$}&
        \multirow{3}{*}{\large $\scalebox{2}{$*$}_{q,m-1}$}&
        \multirow{3}{*}{\large $\cdots$}&
        \multirow{3}{*}{\large $M_{q,m-1}$}\\
    $\vdots$ &&&&\\
    $q{-}1$ &&&& \\ \hline
\end{tabular}
$$
\caption{Рекурсивная конструкция фрактальной матрицы.}
\label{fig:recursive_construction_of_fractal_matrix}
\end{figure}
где $\scalebox{2}{$*$}_{q,m-1}$ --- матрица того же размера, что и $M_{q,m-1}$, но состоящая из одних звездочек.

%\begin{figure}[ht]
%\centering
%\includegraphics[width=0.7\textwidth]{recursive_construction_of_M_qm}
%\caption{Рекурсивная конструкция фрактальной матрицы.}
%\label{fig:recursive_construction_of_fractal_matrix}
%\end{figure}

Матрицы $M_{q,m}$ мы будем называть {\it фрактальными} звездными матрицами, или просто
{\it фракталами\footnote{Такое название выбрано потому, что матрицы $M_{q,m}$ обладают некоторым самоподобием.}.}

Приведем примеры фрактальных звездных матриц (см.~рис.\ref{fig:examples_of_fractal_matrices}):

\begin{figure}[ht]
\centering
\scalebox{0.75}{$
M_{2,2}=\left(\begin{array}{ccc}
0&0&*\cr
0&1&*\cr
1&*&0\cr
1&*&1
\end{array}\right), \qquad
M_{2,3}=\left(\begin{array}{ccccccc}
0&0&0&*&*&*&*\cr
0&0&1&*&*&*&*\cr
0&1&*&0&*&*&*\cr
0&1&*&1&*&*&*\cr
1&*&*&*&0&0&*\cr
1&*&*&*&0&1&*\cr
1&*&*&*&1&*&0\cr
1&*&*&*&1&*&1
\end{array}\right), \qquad
M_{3,2}=\left(\begin{array}{cccc}
0&0&*&*\cr
0&1&*&*\cr
0&2&*&*\cr
1&*&0&*\cr
1&*&1&*\cr
1&*&2&*\cr
2&*&*&0\cr
2&*&*&1\cr
2&*&*&2
\end{array}\right).
$}
\caption{Примеры фрактальных матриц.}
\label{fig:examples_of_fractal_matrices}
\end{figure}

Матрицы, получающиеся из фрактальных перестановкой строк и столбцов, мы также будем называть фрактальными.

\begin{remark}\label{remark_on_permut_of_rows}
Ясно, что перестановка строк звездной матрицы задает другое упорядоченное, но то же самое неупорядоченное разбиение на подкубы.
\end{remark}

\begin{remark}
Можно было бы определить, как фрактальную, звездную матрицу, получающуюся из фрактальной заменой
в некотором ее столбце всех числовых символов в соответствии с некоторой перестановкой $\pi$ из $S_q$,
но делать это необязательно, потому что такая матрица автоматически будет фрактальной в силу уже данных определений, поскольку ее можно получить перестановкой строк и столбцов
исходной звездной матрицы. Действительно, если перестановку $\pi$ числовых символов применить к самому
левому столбцу матрицы $M_{q,m}$ на рис.~\ref{fig:recursive_construction_of_fractal_matrix}, то такого
же результата можно добиться и перестановками $\pi^{-1}$ горизонтальных и вертикальных полос (вертикальные полосы отсчитываются без учета самого левого столбца).
\end{remark}



Несложно проверить, что фрактальная звездная матрица обладает свойствами, которые будут перечислены дальше по ходу этого раздела.

\begin{property}\label{number_of_rows_in_fractal}
Число строк во фрактальной звездной матрице $M_{q,m}$ равно $q^m$.
\end{property}

\begin{proof}
Следует по индукции из рекурсивного определения фрактала.
\end{proof}

\begin{property}\label{number_of_columns_in_fractal}
Число столбцов во фрактальной звездной матрице $M_{q,m}$ равно $\frac{q^m-1}{q-1}$.
\end{property}

\begin{proof}
Индукция по $m$. При $m=0$ число столбцов равно $\frac{q^0-1}{q-1}=0$. Пусть утверждение верно при $m-1$. Тогда для параметра $m$ число столбцов по определению фрактальной матрицы равно
$1+q\cdot \frac{q^{m-1}-1}{q-1}=\frac{q^m-1}{q-1}$, что и требовалось доказать.
\end{proof}

\begin{property}
Фрактальная звездная матрица $M_{q,m}$ задает разбиение гиперкуба ${\bf Z}_q^{(q^m-1)/(q-1)}$ на $q^m$
подкубов размерности $\frac{q^m-1}{q-1}-m$ каждый.
\end{property}

\begin{proof}
Непосредственно следует по индукции из задания рекурсивной конструкции матрицы $M_{q,m}$.
\end{proof}


\begin{observation}
Фрактальная звездная матрица после вставки в нее столбцов из одних звездочек до общего количества столбцов, равного $n$, превращается в звездную матрицу разбиения, получающуюся последовательностью
разрезов, представленной во второй части раздела
\ref{sec:asymp_lower_bound} для доказательства асимптотической нижней оценки (\ref{eq:asymp_lower_bound}).
\end{observation}

\begin{property}\label{number_of_different_partitions_for_fractal}
Число различных неупорядоченных разбиений, задаваемых фрактальными матрицами с параметрами $q$ и $m$,
равно в точности $\left(\frac{q^m-1}{q-1}\right)!$.
\end{property}

\begin{proof}
Мы уже отметили в замечании \ref{remark_on_permut_of_rows}, что перестановка строк не дает нового
неупорядоченного разбиения. В свойстве \ref{number_of_columns_in_fractal} мы установили, что во
фрактальной матрице с указанными параметрами в точности $\frac{q^m-1}{q-1}$ столбцов. То, что все перестановки столбцов дают разные разбиения гиперкуба, можно понять из обдумывания процесса
разрезов гиперкуба, описанного во второй части раздела \ref{sec:asymp_lower_bound}, а можно
воспользоваться индуктивной процедурой построения фрактала. Действительно, пусть утверждение
верно для $m-1$, тогда для $m$ имеем, что число различных разбиений равно
$$
\frac{q^m-1}{q-1}\cdot\binom{\frac{q^m-1}{q-1}-1}{\frac{q^{m-1}-1}{q-1},\dots,\frac{q^{m-1}-1}{q-1}}
\left(\left(\frac{q^{m-1}-1}{q-1}\right)!\right)^q=\left(\frac{q^m-1}{q-1}\right)!,
$$
что и требовалось доказать.
\end{proof}

Будем говорить, что подматрица\footnote{Строки и столбцы подматрицы в исходной матрице не обязаны идти подряд, на некоторых последующих рисунках строки и столбцы подматрицы изображены в исходной матрице идущими подряд исключительно для удобства восприятия.}
$T$ звездной матрицы является {\it трансфракталом,} если она является
фракталом\footnote{Естественно, мы считаем, что у трансфрактала параметр $q$ такой же, как и у содержащей его звездной матрицы.} и
все пересекающиеся с подматрицей $T$ столбцы за пределами подматрицы $T$ состоят из одних звездочек.


На рисунке \ref{fig:example_of_transfractal} черной рамкой выделен трансфрактал.
%\begin{figure}[ht]
%\centering
%\includegraphics[width=0.3\textwidth]{example_of_transfractal}
%\caption{Пример трансфрактала выделен черной рамкой.}
%\label{fig:example_of_transfractal}
%\end{figure}

\begin{figure}[ht]
\centering
$$
\begin{tikzpicture}[baseline=(current bounding box.center)]
\matrix (m) [matrix of nodes,nodes in empty cells,
             left delimiter=(,
             right delimiter=)] {
0&0&0&*&*&*\\
0&0&1&*&*&*\\
0&1&0&*&*&*\\
0&1&1&*&*&*\\
1&*&*&0&0&*\\
1&*&*&0&1&*\\
1&*&*&1&*&0\\
1&*&*&1&*&1\\
};
% Red frame
\draw[thick,red] (m-5-4.north west) rectangle (m-8-5.south west);
% Black frame
\draw[thick] (m-5-4.north west) rectangle (m-8-6.south east);
\end{tikzpicture}
$$
\caption{Пример трансфрактала выделен черной рамкой.}
\label{fig:example_of_transfractal}
\end{figure}

%$$
%\left(\begin{array}{cccccc}
%0&0&0&*&*&*\cr
%0&0&1&*&*&*\cr
%0&1&0&*&*&*\cr
%0&1&1&*&*&*\cr
%1&*&*&0&0&*\cr
%1&*&*&0&1&*\cr
%1&*&*&1&*&0\cr
%1&*&*&1&*&1
%\end{array}\right)
%$$

Число строк в трансфрактале будем называть {\it размером трансфрактала.}
Входящий в состав трансфрактала
столбец, размер которого совпадает с размером трансфрактала,
будем называть {\it ведущим столбцом} трансфрактала. Из определения фрактала легко видеть, что
у любого трансфрактала в точности один ведущий столбец.
Стержень ведущего столбца трансфрактала будем называть также {\it стержнем трансфрактала.}
На рис.~\ref{fig:example_of_transfractal} красным выделен стержень трансфрактала.
{\it Размером стержня трансфрактала} будем называть размер трансфрактала.


\begin{observation}
Все числовые элементы трансфрактала покрываются непересекающимся образом
стержнем ведущего столбца и $q$ трансфракталами меньшего размера.
\end{observation}

\begin{proof}
По построению фрактала.
\end{proof}

\begin{observation}
Каждый столбец фрактала является ведущим столбцом некоторого трансфрактала.
\end{observation}

\begin{proof}
По построению фрактала.
\end{proof}

\begin{lemma}\label{rows_of_transfractal}
Пусть в звездной матрице $M$ разбиения гиперкуба ${\bf Z}_q^n$ на подкубы одинаковой размерности есть подматрица $T$, являющаяся трансфракталом.
Тогда все пересекающиеся с подматрицей $T$ строки за пределами подматрицы $T$ полностью совпадают как строки.
\end{lemma}

\begin{proof}
Доказательство индукцией по размеру трансфрактала. По свойству \ref{number_of_rows_in_fractal} фрактала размер трансфрактала есть степень числа $q$.

Пусть размер трансфрактала $T$ равен $q$. Тогда по лемме \ref{equality_in_single_column} ведущий столбец $\vec{t}$ трансфрактала $T$ содержит каждое число из ${\bf Z}_q$ ровно один раз. Рассмотрим столбец $\vec{s}$, лежащий за пределами трансфрактала $T$. По лемме
\ref{equality_for_sums by_modulo_in_two_columns} размер перекрытия столбцов $\vec{s}$ и $\vec{t}$ должен делиться на $q$. Значит, он или $0$, или $q$. Если размер перекрытия равен $0$, то в строках подматрицы $T$ в столбце $\vec{s}$ стоят одни звездочки, и, значит, все такие строки в столбце $\vec{s}$ совпадают. Пусть размер перекрытия столбцов $\vec{s}$ и $\vec{t}$ равен $q$, т.~е. в строках подматрицы $T$ в столбце $\vec{s}$ стоят только числа. Предположим, в этом перекрытии в столбце $\vec{s}$ найдутся два разных числовых значения:
$m_{r_1,s}\ne m_{r_2,s}$. Мы уже констатировали, что $m_{r_1,t}\ne m_{r_2,t}$, поэтому можно подобрать перестановку $\pi\in S_q$ так, чтобы выполнялось $(m_{r_1,t}+\pi(m_{r_1,s}))\pmod{q}=(m_{r_2,t}+\pi(m_{r_2,s}))\pmod{q}$,
например, положив $\pi(m_{r_1,s})=m_{r_2,t}$, $\pi(m_{r_2,s})=m_{r_1,t}$.
Однако это сразу же приводит к противоречию с утверждением леммы
\ref{equality_for_sums by_modulo_in_two_columns}. Следовательно, оказалось неверным предположение о двух разных числовых значениях в столбце $\vec{s}$ в его перекрытии со столбцом $\vec{t}$. Поэтому все строки трансфрактала $T$ в столбце $\vec{s}$ совпадают. В качестве столбца $\vec{s}$ можно было взять любой столбец за пределами трансфрактала $T$, поэтому утверждение леммы доказано для трансфрактала $T$ с числом строк $q$, что составляет основание индукции.

Докажем теперь индуктивный переход. Пусть утверждение леммы верно для трансфракталов размера $q^{l-1}$. Рассмотрим трансфрактал с $q^l$ строками. По строению фрактала (свойство \ref{number_of_rows_in_fractal}) и лемме \ref{equality_in_single_column}
ведущий столбец $\vec{t}$ трансфрактала содержит каждое значение из ${\bf Z}_q$ ровно $q^{l-1}$ раз. Тем самым трансфрактал $T$ разбивается на $q$ полос с одинаковым значением в столбце $\vec{t}$ внутри каждой полосы. По строению трансфрактала в каждой из полос есть ведущий столбец размера $q^{l-1}$ меньшего трансфрактала. Отсюда по индуктивному предположению для каждой из $q$ полос все строки этой полосы совпадают за пределами трансфрактала $T$. Рассмотрим произвольный столбец $\vec{s}$, лежащий за пределом трансфрактала $T$. Из сказанного выше, внутри каждой из $q$ полос в столбце $\vec{s}$ находится один и тот же элемент (число или звездочка). Отсюда каждая пара элементов $(m_{r,t},m_{r,s})$ в $q^l$ строках трансфрактала $T$ дублируется по $q^{l-1}$ раз. Воспользуемся леммой \ref{equality_for_sums by_modulo_in_two_columns}. Сгруппируем $q^{l-1}$ совпадающих значений в столбцах $\vec{t}$ и $\vec{s}$ в каждой полосе в одно значение. Это не нарушит результат анализа утверждения леммы
\ref{equality_for_sums by_modulo_in_two_columns} применительно к числу совпадающих значений сумм по модулю $q$. Таким образом, мы перешли к двум столбцам высоты $q$ каждый, для которых можно повторить рассуждения из доказательства основания индукции доказываемой нами леммы. Тем самым мы показываем, что все строки трансфрактала $T$ в столбце $\vec{s}$ совпадают. В силу произвольности выбора столбца $\vec{s}$ за пределами трансфрактала $T$ мы доказали индуктивный переход, а с ним и всю лемму.
\end{proof}

\begin{corollary}\label{corollary_rows_of_transfractal}
Пусть $\vec{t}$ --- столбец, входящий в состав трансфрактала $T$, а $\vec{s}$ --- столбец, внешний по отношению к $T$. Тогда столбцы $\vec{t}$ и $\vec{s}$ либо не перекрываются, либо столбец $\vec{t}$ покрывается столбцом $\vec{s}$, причем в последнем случае каждое число столбца $\vec{t}$ лежит в одной строке с одним и тем же числом $a$ в столбце $\vec{s}$.
\end{corollary}


\section{Операция взрыва звездной матрицы}

Введем операцию взрыва звездной матрицы. Операцию определяем только для звездных матриц А-примитивных разбиений на подкубы одинаковой размерности.

Пусть $M$ --- звездная матрица А-примитивного разбиения на подкубы одинаковой размерности.
Выбираем столбец $\vec{i}$ и значение $a$ из ${\bf Z}_q$. Осуществляем следующие действия.

\begin{itemize}
\item{ 1. Удаляем столбец $\vec{i}$.}

\item{ 2. Удаляем все строки, в которых в столбце $\vec{i}$ находилось числовое значение, отличное от $a$.}

\item{ 3. Каждую из строк, в которых в столбце $\vec{i}$ находилось числовое значение $a$, дублируем до $q$ одинаковых строк.}

\item{ 4. Для каждой из образовавшихся полос из $q$ одинаковых строк приписываем к матрице столбец, в котором за пределами полосы одни звездочки, а в пределах полосы --- каждое числовое значение по одному разу.}

\item{ 5. Если в матрице есть столбцы из одних звездочек, то удаляем их.}
\end{itemize}

Описанная последовательность действий определяет {\it операцию взрыва}\footnote{Термин <<взрыв>> для описанного процесса представляется нам точным. Действительно, при взрыве уничтожаются некоторые столбцы и строки, еще часть строк расщепляется, а куски их содержимого улетают в сторону.}
 звездной матрицы $M$. Иногда мы для удобства вместо взрыва матрицы будем говорить о взрыве столбца $\vec{i}$, подразумевая те же самые действия.

Если $i$-й столбец содержал $kq$ чисел, то при его взрыве из матрицы удалилось $k(q-1)$ строк, но столько же и добавилось за счет дублирования, поэтому общее число строк осталось тем же. В строках со звездочками в $i$-м столбце чисел не удалялось и не появлялось, а в строках, получившихся из строки с числом $a$ в $i$-м столбце, это число $a$ исчезло, но добавилось число во вновь приписанном столбце. Таким образом, общее количество чисел во всех строках осталось одинаковым и таким же, как в матрице $M$. Несложно видеть, что любые две строки получившейся матрицы будут содержать разные числа хотя бы в одном столбце --- проблемы по ходу возникали только с дублирующимися строками, но они получили различные числовые значения во вновь приписанном столбце. Наконец, в силу последней операции в матрице не будет столбцов из одних звездочек. Таким образом, в результате взрыва получится А-примитивная звездная матрица, являющаяся матрицей разбиения на такое же число подкубов одинаковой размерности, что и исходная матрица $M$. Однако число столбцов в матрице может измениться.

Опишем неформально, что происходит при взрыве с разбиением. Сначала фактически происходит удаление из пространства $i$-й координаты. Остаются только те наборы, которые имели числовое значение $a$ в $i$-й компоненте. При этом если звездный паттерн подкуба содержал звездочку в $i$-й компоненте, то размерность подкуба уменьшается на $1$; подкубы с числовым значением в $i$-й компоненте, отличным от $a$, полностью пропадают; подкубы с числовым значением в $i$-й компоненте, равным $a$, полностью остаются. Таким образом, в разбиении оказываются подкубы разных размерностей, которые могут отличаться на $1$. Однако приписывание новых столбцов вновь уравнивает размерности --- к звездным паттернам меньших подкубов приписываются одни звездочки, и каждая такая звездочка увеличивает размерность на $1$, а к звездным паттернам больших подкубов один раз припишется число --- и за счет этого размерности уравняются.

Приведем пример взрыва звездной матрицы. Процесс взрыва представлен на рис.~\ref{fig:example_bang}.

%\begin{figure}[ht]
%\centering
%\includegraphics[width=0.7\textwidth]{example_bang}
%\caption{Пример взрыва звездной матрицы.}
%\label{fig:example_bang}
%\end{figure}

\begin{figure}[ht]
\centering
$$
\scalebox{1.35}{
\def\0{\ccolor{$0$}}
\def\2{\ccolor{$*$}}
\def\1{\ccolor{$1$}}
\def\ARR{+(0.5,0.05) [->]edge +(1.5,0.4) +(0.5,-0.05) -- +(1.5,-0.4)}
\begin{tikzpicture}
\draw (0,7) \0\0\2\0 ;
\draw (0,6) \1\0\0\2 ;
\draw (0,5) \2\1\0\0 ;
\draw (0,4) \1\2\1\0 ;
\draw (0,3) \1\1\2\1 ;
\draw (0,2) \0\1\1\2 ;
\draw (0,1) \2\0\1\1 ;
\draw (0,0) \0\2\0\1 ;
\end{tikzpicture}
\raisebox{3.5em}{\ \ $\Longrightarrow\ \ $}
\begin{tikzpicture}
\draw (0,7) \0\0\2\0 \ARR;
\draw (0,6) \1\0\0\2 ;
\draw (0,5) \2\1\0\0 ;
\draw (0,4) \1\2\1\0 ;
\draw (0,3) \1\1\2\1 ;
\draw (0,2) \0\1\1\2 \ARR;
\draw (0,1) \2\0\1\1 ;
\draw (0,0) \0\2\0\1 \ARR;
%% now draw the lines
\draw (1,-0.5)--(1,7.5);
\draw (0.5,6)--(4.5,6);
\draw (0.5,4)--(4.5,4);
\draw (0.5,3)--(4.5,3);
\end{tikzpicture}
\raisebox{3.5em}{\ \ $\Longrightarrow\ \ $}
\begin{tikzpicture}
\draw (0,7) \0\2\0\0\2\2 ;
\draw (0,6) \0\2\0\1\2\2 ;
\draw (0,5) \1\0\0\2\2\2 ;
\draw (0,4) \1\1\2\2\0\2 ;
\draw (0,3) \1\1\2\2\1\2 ;
\draw (0,2) \0\1\1\2\2\2 ;
\draw (0,1) \2\0\1\2\2\0 ;
\draw (0,0) \2\0\1\2\2\1 ;
\end{tikzpicture} }
$$
\caption{Пример взрыва звездной матрицы.}
\label{fig:example_bang}
\end{figure}


Для примера мы взяли матрицу из статьи Ривеста \cite{Riv1974}. Здесь $q=2$.
Взрываем левый столбец со значением $0$.
Взорванный столбец удаляется из матрицы; удаляются также $2$-я, $4$-я и $5$-я строки, как имеющие во
взорванном столбце числовые значения, отличные от $0$; в то же время $1$-я, $6$-я и $8$-я строки, как имеющие во взорванном столбце $0$, расщепляются на две каждая, после чего для каждой пары клонированных строк
справа приписываем свой столбец, в котором в строках из этой пары стоят по разу значения из ${\bf Z}_2$ (т.~е. $0$ и $1$), а в остальных строках звездочки. Таким образом, всего приписано три новых столбца.
Столбцов из одних звездочек в результате взрыва не получилось, поэтому ничего больше удалять не надо.

Получившуюся в результате взрыва звездную матрицу взорвем снова.
Процесс повторного взрыва представлен на рис.~\ref{fig:example_bang_2}.

%\begin{figure}[ht]
%\centering
%\includegraphics[width=0.9\textwidth]{example_bang_2}
%caption{Повторный взрыв.}
%\label{fig:example_bang_2}
%end{figure}



\begin{figure}[ht]
\centering
$$
\scalebox{0.80}{
\def\0{\ccolor{$0$}}
\def\2{\ccolor{$*$}}
\def\1{\ccolor{$1$}}
\def\ARR{+(0.5,0.05) [->]edge +(1.5,0.4) +(0.5,-0.05) -- +(1.5,-0.4)}
\begin{tikzpicture}
\draw (0,7) \0\2\0\0\2\2 ;
\draw (0,6) \0\2\0\1\2\2 ;
\draw (0,5) \1\0\0\2\2\2 ;
\draw (0,4) \1\1\2\2\0\2 ;
\draw (0,3) \1\1\2\2\1\2 ;
\draw (0,2) \0\1\1\2\2\2 ;
\draw (0,1) \2\0\1\2\2\0 ;
\draw (0,0) \2\0\1\2\2\1 ;
\end{tikzpicture}
\raisebox{3.5em}{\ \ $\Longrightarrow\ \ $}
\begin{tikzpicture}
\draw (0,7) \0\2\0\0\2\2 \ARR;
\draw (0,6) \0\2\0\1\2\2 \ARR;
\draw (0,5) \1\0\0\2\2\2 ;
\draw (0,4) \1\1\2\2\0\2 ;
\draw (0,3) \1\1\2\2\1\2 ;
\draw (0,2) \0\1\1\2\2\2 \ARR;
\draw (0,1) \2\0\1\2\2\0 ;
\draw (0,0) \2\0\1\2\2\1 ;
%% now draw the lines
\draw (1,-0.5)--(1,7.5);
\draw (0.5,5)--(6.5,5);
\draw (0.5,4)--(6.5,4);
\draw (0.5,3)--(6.5,3);
\end{tikzpicture}
\raisebox{3.5em}{\ \ $\Longrightarrow\ \ $}
\begin{tikzpicture}
\draw (0,7) \2\0\0\2\2\0\2\2 ;
\draw (0,6) \2\0\0\2\2\1\2\2 ;
\draw (0,5) \2\0\1\2\2\2\0\2 ;
\draw (0,4) \2\0\1\2\2\2\1\2 ;
\draw (0,3) \1\1\2\2\2\2\2\0 ;
\draw (0,2) \1\1\2\2\2\2\2\1 ;
\draw (0,1) \0\1\2\2\0\2\2\2 ;
\draw (0,0) \0\1\2\2\1\2\2\2 ;
%% now draw the lines
\draw (4,-0.5)--(4,7.5);
\end{tikzpicture}
\raisebox{3.5em}{\ \ $\Longrightarrow\ \ $}
\begin{tikzpicture}
\draw (0,7) \2\0\0\2\0\2\2 ;
\draw (0,6) \2\0\0\2\1\2\2 ;
\draw (0,5) \2\0\1\2\2\0\2 ;
\draw (0,4) \2\0\1\2\2\1\2 ;
\draw (0,3) \1\1\2\2\2\2\0 ;
\draw (0,2) \1\1\2\2\2\2\1 ;
\draw (0,1) \0\1\2\0\2\2\2 ;
\draw (0,0) \0\1\2\1\2\2\2 ;
\end{tikzpicture} }
$$
\caption{Повторный взрыв.}
\label{fig:example_bang_2}
\end{figure}

Вновь взрываем левый столбец со значением $0$.
Взорванный столбец удаляется из матрицы; удаляются также $3$-я, $4$-я и $5$-я строки, как имеющие во
взорванном столбце числовые значения, отличные от $0$; в то же время $1$-я, $2$-я и $6$-я строки, как имеющие во взорванном столбце $0$, расщепляются на две, после чего для каждой пары клонированных строк
справа приписываем свой столбец, в котором в строках из этой пары стоят по разу значения из ${\bf Z}_2$ (т.~е. $0$ и $1$), а в остальных строках звездочки. Таким образом, всего приписано три новых столбца.
При этом образовался столбец из одних звездочек --- удаляем его из матрицы.

Если приглядеться, то можно заметить, что получившаяся $8\times 7$ матрица является фрактальной. Как мы поймем в дальнейшем, это не случайно.

\section{Нерасширяемые звездные матрицы}

Звездную матрицу А-примитивного разбиения на подкубы одинаковой размерности назовем {\it расширяемой,} если при некотором взрыве количество столбцов в ней увеличивается. Соответственно, звездную матрицу А-примитивного разбиения на подкубы одинаковой размерности назовем {\it нерасширяемой,} если количество столбцов в ней не увеличивается при любом взрыве.

В этом разделе мы покажем, что нерасширяемыми являются только фрактальные матрицы.

\begin{lemma}\label{only_transfractls}
Пусть А-примитивная звездная матрица $M$ разбиения гиперкуба ${\bf Z}_q^n$ на подкубы одинаковой размерности является нерасширяемой. Тогда всякий ее столбец имеет размер, равный степени числа $q$, и стержень этого столбца является стержнем ведущего столбца некоторого трансфрактала.
\end{lemma}

\begin{proof}
В любом столбце матрицы $M$ по лемме \ref{equality_in_single_column} каждое число встречается одно и то же количество раз, поэтому размер любого столбца имеет вид $kq$. Проведем доказательство индукцией по $k$. При $k=1$ стержень столбца сам является трансфракталом, что дает базу индукции.
Докажем индуктивный переход. Рассмотрим столбец $\vec{s}$ размера $kq$.
По индуктивному предположению для всех столбцов меньшего размера утверждение леммы \ref{only_transfractls} выполнено, докажем его для столбца $\vec{s}$.

Осуществим взрыв столбца $\vec{s}$ при значении $0$. По определению взрыва из матрицы удалится столбец $\vec{s}$ и добавятся $k$ новых столбцов за счет расщепления строк полосы $R_0$, состоящей из всех
строк матрицы $M$, имевших значение $0$ в столбце $\vec{s}$. Также, возможно, удалится некоторое количество столбцов, которые станут состоять из одних звездочек. Оценим количество таких столбцов (см.~рис.~\ref{fig:lemma_proof}).

%\begin{figure}[ht]
%\centering
%\includegraphics[width=0.7\textwidth]{pic_lemma_proof}
%\caption{Рисунок к доказательству леммы \ref{only_transfractls}.}
%\label{fig:lemma_proof}
%\end{figure}


\begin{figure}[ht]
\centering
\begin{tikzpicture}[scale=2.66,
    stripe/.style={minimum height=2cm, minimum width=12cm},
    brace/.style={decoration={brace,mirror,raise=5pt}, decorate},
    arrow/.style={->, thick},
    box/.style={draw, minimum width=0.2cm, minimum height=0.5cm}
]

% Labels outside stripes and braces
\node at (-7,5) {$R_0$};
\node at (-6.2,5) {$k$};
\draw[brace] (-5.7,6) -- (-5.7,4);

\node at (-7,3) {$R_1$};
\node at (-6.2,3) {$k$};
\draw[brace] (-5.7,4) -- (-5.7,2);

\node at (-7,-3) {$R_{q-1}$};
\node at (-6.2,-3) {$k$};
\draw[brace] (-5.7,-2) -- (-5.7,-4);

% Vector s with asterisks
\node at (-5,7) {$\vec{s}$};
\node at (-5,6.7) {$*$};
\node at (-5,6.4) {$*$};
\node at (-5,6.1) {$*$};

\node at (-3,6.7) {$*$};
\node at (-3,6.4) {$*$};
\node at (-3,6.1) {$*$};

\node at (-2,6.7) {$*$};
\node at (-2,6.4) {$*$};
\node at (-2,6.1) {$*$};

\node at (2,6.7) {$*$};
\node at (2,6.4) {$*$};
\node at (2,6.1) {$*$};

\node at (3,6.7) {$*$};
\node at (3,6.4) {$*$};
\node at (3,6.1) {$*$};

% Horizontal lines and column numbers
\draw (-5.8,6) -- (6,6);  % Top line R0
\draw (-5.8,4) -- (6,4);  % Bottom line R0/Top line R1
\draw (-5.8,2) -- (6,2);  % Bottom line R1
\draw (-5.8,-2) -- (6,-2);  % Top line R_{q-1}
\draw (-5.8,-4) -- (6,-4);  % Bottom line R_{q-1}

% Column numbers
\node at (-5,5.5) {$0$};
\node at (-5,5) {$\vdots$};
\node at (-5,4.5) {$0$};

\node at (-3,5.5) {$*$};
\node at (-3,5) {$\vdots$};
\node at (-3,4.5) {$*$};

\node at (-2,5.5) {$*$};
\node at (-2,5) {$\vdots$};
\node at (-2,4.5) {$*$};

\node at (2,5.5) {$*$};
\node at (2,5) {$\vdots$};
\node at (2,4.5) {$*$};

\node at (3,5.5) {$*$};
\node at (3,5) {$\vdots$};
\node at (3,4.5) {$*$};

\node at (-5,3.5) {$1$};
\node at (-5,3) {$\vdots$};
\node at (-5,2.5) {$1$};

\node at (2,3.5) {$*$};
\node at (2,3) {$\vdots$};
\node at (2,2.5) {$*$};

\node at (3,3.5) {$*$};
\node at (3,3) {$\vdots$};
\node at (3,2.5) {$*$};


\node at (-5,0) {$\vdots$};
\node at (-2,0) {$\vdots$};
\node at (-3,0) {$\vdots$};
\node at (2,0) {$\vdots$};
\node at (3,0) {$\vdots$};

\node at (-5,-2.5) {$q-1$};
\node at (-5,-3) {$\vdots$};
\node at (-5,-3.5) {$q-1$};

\node at (-3,-2.5) {$*$};
\node at (-3,-3) {$\vdots$};
\node at (-3,-3.5) {$*$};

\node at (-2,-2.5) {$*$};
\node at (-2,-3) {$\vdots$};
\node at (-2,-3.5) {$*$};


% Fragment in R1
%\node[box] at (-1,3.6) {};
%\node at (0,3.6) {$l_{1,1}$};
%\node at (-0.7,3.8) {$*$};  % Top asterisk
%\node at (-0.7,3.4) {$*$};  % Bottom asterisk

% Diagonal boxes in R1 (closer to column s)
\node[box] at (-3,3.6) {};
\node at (-2.5,3.6) {$l_{1,1}$};

\node[rotate=10] at (-2.5,3.1) {$\ddots$};
\node[box] at (-2,2.4) {};
\node at (-1.4,2.4) {$l_{1,p_1}$};

\node at (-2.0,3.8) {$*$};  % Top asterisk
\node at (-2.0,3.4) {$*$};  % Bottom asterisk

\node at (-3.0,2.6) {$*$};  % Top asterisk
\node at (-3.0,2.2) {$*$};  % Bottom asterisk

%\node[box] at (1,2.4) {};
%\node at (2,2.4) {$l_{1,p_1}$};
%\node at (1.3,2.6) {$*$};  % Top asterisk
%\node at (1.3,2.2) {$*$};  % Bottom asterisk

% Fragment in R_{q-1} (similar layout to R1)
\node[rotate=10] at (2.5,-2.9) {$\ddots$};

\node[box] at (2,-2.4) {};
\node at (2.7,-2.32) {$l_{q-1,1}$};
\node at (3.,-2.2) {$*$};  % Top asterisk
\node at (3.,-2.6) {$*$};  % Bottom asterisk

\node[box] at (3,-3.6) {};
\node at (4.0,-3.6) {$l_{q-1,p_{q-1}}$};
\node at (2.,-3.4) {$*$};  % Top asterisk
\node at (2.,-3.8) {$*$};  % Bottom asterisk

% Diagonal dots between fragments
\node[rotate=45] at (0,0) {$\vdots$};
%\node[rotate=45] at (1.5,0) {$\vdots$};
%\node[rotate=45] at (3,0) {$\vdots$};

% Bang 0 arrow at bottom
\draw[arrow] (-5,-4.3) -- (-5,-4);
\node at (-5,-4.6) {взрыв 0};

\end{tikzpicture}
\caption{Иллюстрация к доказательству леммы \ref{only_transfractls}.}
\label{fig:lemma_proof}
\end{figure}


Пусть в столбце $\vec{t}$ матрицы $M$ все числа пропадают при взрыве. Из определения взрыва легко видеть, что столбец $\vec{t}$ должен покрываться столбцом $\vec{s}$, причем строки c числами столбца $\vec{t}$ не могут иметь разных чисел в столбце $\vec{s}$ по лемме \ref{rows_of_transfractal}, поскольку по индуктивному предположению столбец $\vec{t}$ является ведущим столбцом некоторого трансфрактала, а
столбец $\vec{s}$ по отношению к этому трансфракталу является внешним.
Поэтому стержень столбца $\vec{t}$ должен находиться в одной из $q-1$ полос $R_i$ размера $k$, где $i$-я полоса состоит из всех $k$ строк матрицы $M$, имеющих значение $i$ в столбце $\vec{s}$, $i=1,\dots,k-1$.
Рассмотрим полосу $R_i$ и среди всех лежащих в ней стержней столбцов выберем максимальное по включению множество $T_i$ таких стержней столбцов, которые не покрываются другими такими стержнями. По условию выбора, стержни из $T_i$ являются стержнями ведущих столбцов попарно не содержащихся друг в друге трансфракталов. Следовательно, по следствию \ref{corollary_rows_of_transfractal} стержни из $T_i$ попарно не перекрываются. Пусть их размеры есть $l_{i,1}, \dots, l_{i,p_i}$. Из попарного неперекрывания следует, что
\begin{equation}\label{eq:inequality_for_stripe}
\sum\limits_{j=1}^{p_i}l_{i,j}\le k.
\end{equation}
По индуктивному предположению все стержни из $T_i$ имеют размер, равный степени числа $q$, и являются стержнями ведущих столбцов некоторых трансфракталов, все столбцы которых также пропадут при взрыве. Число столбцов в трансфрактале мы знаем из определений трансфрактала, фрактала и свойства
\ref{number_of_columns_in_fractal}. Поэтому число $N$ столбцов, которые при взрыве будут удалены из матрицы, можно оценить, учитывая (\ref{eq:inequality_for_stripe}), как
\begin{equation}\label{eq:estimation_of cancelled_allstars_columns}
N=1+\sum\limits_{i=1}^{q-1}\sum\limits_{j=1}^{p_i}\frac{q^{\log_q l_{i,j}}-1}{q-1}=
1+\sum\limits_{i=1}^{q-1}\frac{\left(\sum\limits_{j=1}^{p_i}l_{i,j}\right)-p_i}{q-1}\le
1+\sum\limits_{i=1}^{q-1}\frac{k-1}{q-1}=k,
\end{equation}
причем из неравенства в (\ref{eq:estimation_of cancelled_allstars_columns}) легко видеть, что равенство
$N=k$ может достигаться, только если все $p_i=1$ и все $l_{i,1}=k$, $i=1,\dots,q-1$, т.~е. когда все множества $T_i$ состоят из одного стержня, размер которого равен числу строк в полосе $R_i$.
Осуществляя взрыв столбца $\vec{s}$ со значением $1$, получаем такое же требование для полосы $R_0$.

Отсюда следует, что число столбцов в матрице $M$ не увеличится при некотором взрыве столбца $\vec{s}$, только если
столбец $\vec{s}$ является ведущим столбцом трансфрактала и его размер $kq$ есть степень числа $q$.
Тем самым завершено доказательство индуктивного перехода.
\end{proof}

\begin{corollary}\label{non_fractals_are_extendable}
Пусть матрица $M$ является нерасширяемой. Тогда матрица $M$ является фрактальной матрицей.
\end{corollary}

\begin{proof}
По лемме \ref{only_transfractls} каждый столбец матрицы $M$ является ведущим столбцом некоторого
трансфрактала. Предположим, что в матрице $M$ есть два столбца $\vec{t}_1$ и $\vec{t}_2$, не покрывающиеся друг другом и никакими другими столбцами. Тогда по следствию \ref{corollary_rows_of_transfractal} столбцы $\vec{t}_1$ и $\vec{t}_2$ не перекрываются.
Возьмем строку $\vec{r}_1$ с числом в столбце $\vec{t}_1$ и возьмем строку $\vec{r}_2$ с числом в столбце $\vec{t}_2$. Из определения трансфрактала и следствия \ref{corollary_rows_of_transfractal} вытекает, что строки $\vec{r}_1$ и $\vec{r}_2$ не имеют столбца, в котором в этих строках стоят разные числа
(действительно, если такой столбец $\vec{s}$ найдется, то он не вложен ни в $\vec{t}_1$, ни в $\vec{t}_2$, а поэтому является внешним по отношению к трансфракталам, в которых $\vec{t}_1$ и $\vec{t}_2$ являются ведущими столбцами, но тогда по следствию \ref{corollary_rows_of_transfractal} и столбец $\vec{t}_1$, и столбец $\vec{t}_2$ вложены в $\vec{s}$, что противоречит нашему предположению). Таким образом, мы получили противоречие с леммой \ref{lemma1} и сделанным предположением о наличии столбцов $\vec{t}_1$ и $\vec{t}_2$.

Значит, в матрице $M$ есть столбец $\vec{t}_1$, покрывающий все остальные столбцы.
Тогда столбец $\vec{t}_1$ должен содержать числа во всех строках, потому что если он содержит звездочку в некоторой строке $r$, то, ввиду отсутствия в $M$ строки из одних звездочек, найдется столбец $\vec{t}_2$ с числом в строке $r$, но тогда столбец $\vec{t}_2$ не покрывается столбцом $\vec{t}_1$, что противоречит сделанному выше утверждению. Таким образом, столбец $\vec{t}_1$ содержит числа во всех строках и, следовательно,
столбец $\vec{t}_1$ является ведущим столбцом всей матрицы $M$, которая, в свою очередь, является фрактальной матрицей.
\end{proof}

\begin{observation}\label{only_fractal_is_nonextendable}
Фрактальная матрица является нерасширяемой.
\end{observation}

\begin{proof}
Этот факт можно проследить по доказательству леммы \ref{only_transfractls}. Впрочем, делать это не обязательно, поскольку любая другая матрица, кроме фрактальной, по следствию \ref{non_fractals_are_extendable} является расширяемой, а нерасширяемые
матрицы существовать должны ввиду ограниченности по теореме \ref{coord_thm}
числа столбцов в А-примитивных матрицах при фиксированных $q$ и $m$.
\end{proof}

\section{Главные теоремы}

\begin{theorem}\label{tight_values}
Имеют место точные значения $$N^{\rm coord}_q(m)=\frac{q^m-1}{q-1},\quad
c^{\rm coord*}_q\left(\frac{q^m-1}{q-1},m\right)=\left(\frac{q^m-1}{q-1}\right)!.$$
\end{theorem}

\begin{proof}
Вытекает из следствия \ref{non_fractals_are_extendable}, наблюдения \ref{only_fractal_is_nonextendable} и свойства \ref{number_of_different_partitions_for_fractal}.
\end{proof}


 Асимптотическая формула (\ref{eq:main_asymptotics}), выписанная в {\bf теореме \ref{th_asymp}}, вытекает
из теорем
\ref{general_form_of_asymptotics} и \ref{tight_values}.

\begin{corollary}
Пусть $q,m$ --- фиксированные натуральные числа, $q>1$. Тогда при $n\to\infty$
число разбиений гиперкуба ${\bf Z}_q^n$ на подкубы размерности не менее $n-m$ асимптотически равно
$n^{\frac{q^m-1}{q-1}}$.
\end{corollary}

\begin{proof}
Для числа разбиений на подкубы размерности не менее $n-m$, очевидно, справедлива формула,
аналогичная формуле (\ref{eq:coord_formula_modified}), т.~е. вопрос сводится к нахождению
максимального числа столбцов в А-примитивных матрицах, содержащих в каждой строке не более $m$
числовых значений. Однако если какая-то строка содержит менее $m$ числовых значений, то соответствующий
подкуб можно расщепить по новой координате на подкубы меньшей размерности, аналогично тому, как делалось
по ходу операции взрыва, что приводит к увеличению столбцов матрицы. Поэтому максимальное число столбцов может быть достигнуто только на матрице, содержащей ровно $m$ чисел в каждой строке, т.~е. на матрице А-примитивного разбиения на подкубы размерности $n-m$ каждый.
\end{proof}


\section{Заключение}

Любая звездная матрица, за исключением фрактала, при некотором взрыве расширяется, а фрактал остается фракталом при любом взрыве.

Any star matrix, excepting a fractal, expands under some bang, whereas a fractal remains to be a fractal under any bang.





\bigskip
\begin{thebibliography}{100} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).

\bibitem{ABP24}
N. Alon, J. Balogh, V.N. Potapov,
\href{https://doi.org/10.48550/arXiv.2401.00299}{\it Partitioning the hypercube into smaller hypercubes}, ArXiv.org. 2024. arXiv:2401.00299v3 , to appear in: Illinois J. Math. \textbf{68}:4 (2024).
%https://arxiv.org/pdf/2401.0299
\bibitem{FHKIRSV23}
Y. Filmus, E.A. Hirsch, S. Kurz, F. Ihringer, A. Riazanov, A,V. Smal, M. Vinuals,
\href{https://doi.org/10.37236/11862}{\it Irreducible Subcube Partitions}, The Electronic Journal of Combinatorics, \textbf{30}:3 (2023), Article Number P.~3.29.
%https://www.combinatorics.org/ojs/index.php/eljc/article/view/v30i3p29/pdf

\bibitem{Pot11}
V.N. Potapov,
\href{https://doi.org/10.1134/S0037446611020133}{\it Clique matchings in the $k$-ary $n$-dimensional cube}, Siberian Mathematical Journal, \textbf{52}:2 (2011), 303--310.

\bibitem{Pot14}
V.N. Potapov, {\it On the multidimensional permanent and $q$-ary designs}, Siberian Electronic Mathematical Reports, {\bf 11} (2014), 451--456.

%Potapov~V.\,N., Taranenko~A.\,A., Tarannikov~Yu.\,V. An asymptotic lower bound on the number
%of bent functions~// Designs, Codes and Cryptography. 2024.
%Vol.\,92, №\,3. P.\,639--651.
\bibitem{Tar22}
Yu.V. Tarannikov,
\href{https://doi.org/10.1134/S1990478922040202}{\it On the existence of Agievich-primitive partitions}, Journal of Applied and Industrial Mathematics, \textbf{16}:4 (2022), 809--820.


\bibitem{Agievich08}
S. Agievich,
\href{https://doi.org/10.3233/978-1-58603-878-6-3}{\it Bent rectangles}, Proceedings of the NATO advanced study institute on Boolean functions in cryptology and information security, Amsterdam: IOS Press (NATO science for peace and security Series D: Information and communication security), {\bf 18} (2008), 3--22.



\bibitem{Riv1974}
R.L. Rivest,
\href{https://doi.org/10.1109/SWAT.1974.17}{\it On hash-coding algorithms for partial-match retrieval}, Proceedings of the 15th Annual Symposium on Switching and Automata Theory, October 1974, (1974), 95--103.

\bibitem{Brou1978}
A.E. Brouwer, {\it On associative block designs}, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), North-Holland, Amsterdam, {\bf 18} (1978), 173--184.

\bibitem{vL1985}
J.H. van Lint, {\it $\{0,1,*\}$-distance problems in combinatorics}, Surveys in combinatorics: invited papers for the tenth British Combinatorial Conference, Glasgow, UK, July 22-26, 1985, Ed. I. Anderson). 1985. Cambridge: Cambridge University Press, 113--135.

\bibitem{vLW2001}
J.H. van Lint, R.M. Wilson,
\href{https://doi.org/10.1017/CBO9780511987045}{\it A Course in Combinatorics}, Second Edition. Cambridge: Cambridge University Press, 2001.

\bibitem{Pout1986}
J.A. La Poutr\'e,
\href{https://doi.org/10.1016/0012-365X(86)90164-0}{\it A theorem on associative block designs}, Discrete Math, {\bf 58} (1986), 205--208.

\bibitem{Pot22}
V.N. Potapov,
\href{https://doi.org/10.37236/10550}{\it DP-colorings of uniform hypergraphs and splittings of Boolean
hypercube into faces}, Electron. J. Comb, \textbf{29}:3 (2022), ID P3.37. 7 pp.




%\bibitem{1} D.G. Northcott,
%\href{https://doi.org/10.1017/CBO9780511565908}{\it Ideal Theory}, Cambridge University Press, %Cambridge, 1953.

%\bibitem{2} I.I. Ivanov,
%\href{https://doi.org/10.1002/cpa.20282}{\it Some properties of commutative algebras}, Siberian %Electronic
%Mathematical Reports, {\bf 1} (2004), 142--143.

%\bibitem{3} A.V. Tetenov, M. Samuel, D.A. Vauilin,
%\href{https://doi.org/10.21538/0134-4889-2017-23-4-281-291}{\it On dendrites generated by polyhedral %systems and their ramification points}, Trudy Inst. Mat. Mekh. UrO RAN, \textbf{23}:4 (2017), 281--291.

\end{thebibliography}
\end{document}
