\documentclass[russian]{intsys}


\usepackage{tikz}
\usepackage{thmtools}

\usepackage{pgfplots}
\usetikzlibrary{positioning, arrows.meta}
\pgfplotsset{compat=1.9}
\usepackage{longtable}

\newcommand{\cT}{\mathcal T} 
\newcommand{\PP}{\mathbb P}
\newcommand{\F}{\mathbb F}
\newcommand{\Fq}{\mathbb F_q}
\newcommand{\cC}{\mathcal C}

\renewcommand{\phi}{\varphi}


\newcommand{\sufficiency}{
  \par\noindent\hspace*{2em}\emph{Достаточность.}\, %
}


\newcommand{\necessity}{
  \par\noindent\hspace*{2em}\emph{Необходимость.}\, %
}

\TitleRU{Оценки характеристик кодов Таннера на графе проективного пространства}
\TitleEN{Bounds on the parameters of Tanner codes on the graph of projective space}

\AbstractRU{
В работе рассматриваются коды Таннера, построенные на графе инцидентности точек и гиперплоскостей проективного пространства, с проективными кодами Рида-Маллера в качестве компонентных кодов. Сопоставление битов локальных кодов рёбрам производится таким образом, чтобы получаемый код Таннера обладал симметрией проективного пространства. В работе получены нижние оценки минимального расстояния и размерности таких кодов. В частности, показано, что при определённых значениях параметров эти коды являются асимптотически хорошими.
}
\AbstractEN{
This paper considers Tanner codes constructed on the incidence graph of points and hyperplanes of a projective space, with projective Reed–Muller codes as component codes. The assignment of bits of local codes to edges is performed so that the resulting Tanner code inherits the symmetry of the projective space. Lower bounds on the minimum distance and dimension of such codes are obtained. In particular, it is shown that, for certain parameter values, these codes are asymptotically good.
}
\KeywordsRU{
коды Таннера, граф инцидентности, проективное пространство, минимальное расстояние, размерность кода%
}
\KeywordsEN{
Tanner codes, incidence graph, projective space, minimum distance, code dimension%
}
\Author{Юсуфова Алина Алмасовна}
       {студент магистратуры, филиал МГУ в г. Ташкенте}
       {Yusufova Alina Almasovna}
       {Master’s student, Lomonosov Moscow State University branch in Tashkent}
       {yusufova.alinochka@mail.ru}{0009-0007-4090-8215}
       
\Author{Калачев Глеб Вячеславович}
       {канд. физ.-мат. наук, науч. сотр. каф. математической теории интеллектуальных систем мех.-мат. ф-та МГУ}
       {Kalachev Gleb Vyacheslavovich}
       {Candidate of Physical and Mathematical Sciences, Researcher, Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Chair of Mathematical Theory of Intellectual Systems}
       {gleb.kalachev@yandex.ru}{0000-0003-2695-3179}

\ShortTitle{Коды Таннера на графе проективного пространства}
\IntSetShortAuthor{А.А. Юсуфова, Г.В. Калачев}

\begin{document}
\section{Введение}
В данной работе изучаются коды Таннера, построенные на графе инцидентности точек и гиперплоскостей проективного пространства $\mathbb{P}_q^D$ над конечным полем $\mathbb{F}_q$. В качестве локальных кодов используются проективные коды Рида–Маллера, а сопоставление битов локальных кодов рёбрам графа производится таким образом, чтобы получаемый код обладал симметрией проективного пространства: группа изометрий кода включает в себя группу проективных преобразований $\mathrm{PGL}(D+1,q)$. Такая симметрия важна для потенциальных применений этих кодов в качестве локальных кодов в симплициальных комплексах с соответствующими локальными симметриями.

Одна из основных мотиваций для изучения таких кодов связана с задачей построения локально тестируемых и квантовых LDPC кодов на основе симплициальных комплексов Рамануджана типа $\widetilde{A}_d$ \cite{Lubotzky}. Графы инцидентности проективных пространств возникают как локальные структуры (линки) в таких комплексах, а коды Таннера, определённые на линках, играют ключевую роль при определении глобального кода на комплексе. Для построения хорошего глобального кода необходимо, чтобы локальные коды Таннера обладали необходимой симметрией, достаточной размерностью, минимальным расстоянием, а также свойством тестируемости на согласованность (agreement testability). Симплициальные комплексы Рамануджана потенциально могли бы дать семейства хороших локально тестируемых или квантовых LDPC кодов с высокой симметрией, чего пока не удаётся достичь с использованием конструкций, основанных на произведениях кодов (например, \cite{kalachev2023}). В данной работе мы фокусируемся на исследовании размерности и минимального расстояния.

Двумерный случай ($D=2$), то есть конструкции на графах инцидентности аффинных и проективных плоскостей, изучен достаточно подробно. Оценки размерности кодов Таннера на таких графах получены в \cite{HoholdtJustesen2006, BeelenHoholdtPineroJustesen2013, Pinero2015}, а оценки минимального расстояния — в \cite{JanwaLal2003, HoholdtJustesen2011, Pinero2015}. В \cite{DinurHDE} для кодов на аффинной плоскости, помимо расстояния и размерности, исследуется также свойство тестируемости на согласованность, важное для построения локально тестируемых кодов. Многомерный случай изучался только для локальных кодов степени один \cite{RodierFlagVarieties}. Настоящая работа рассматривает одно из естественных обобщений: проективные пространства произвольной размерности с локальными кодами более высокой степени.

Основные результаты работы состоят в следующем. Для кода Таннера на графе инцидентности проективного пространства с произвольными локальными кодами с достаточно большим минимальным расстоянием получена нижняя оценка минимального расстояния глобального кода, основанная на спектральном расширении графа и оценке Сипсера–Спилмана. Для кодов с проективными кодами Рида–Маллера в качестве локальных кодов получена нижняя оценка размерности, а также нижние оценки минимального расстояния как в случае проективной плоскости, так и в больших размерностях. Из полученных оценок следует, что при определённых соотношениях между параметрами эти коды являются асимптотически хорошими. Также проверено, что предложенная конструкция действительно наследует симметрию проективного пространства.

Статья организована следующим образом. В разделе \ref{sec:main-results} приведены основные определения и обозначения, относящиеся к кодам Таннера, построенным на графе инцидентности проективного пространства, и формулируются основные результаты работы. Раздел \ref{sec:aux-results} содержит вспомогательные сведения о кодах Рида--Маллера, графах-расширителях и спектре графа инцидентности, необходимые для дальнейших доказательств. В разделе \ref{sec:proof} приведены доказательства оценок минимального расстояния и размерности рассматриваемых кодов, а также исследуется их инвариантность относительно действия групп симметрий. В разделе \ref{sec:conclusion} сформулированы основные выводы. В приложении \ref{sec:numeric-results} приведены результаты численного эксперимента, посвящённого вычислению размерности кода в двумерном случае.


\section{Основные определения и результаты}\label{sec:main-results}
\newcommand{\PGL}{\mathrm{PGL}}
\newcommand{\GL}{\mathrm{GL}}
\subsection{Линейные коды}

\noindent Обозначим через $\mathbb{F}_q^n$ — $n$-мерное векторное пространство над $\mathbb{F}_q$.
Ниже приведём основные определения (см., например, \cite[стр. 3]{gashkov2009}, \cite[стр. 198]{Chashkin}). 

\emph{Линейным} $\mathcal{C}$ кодом длины $n$ и размерности $k$ (сокращённо $[n,k]$-кодом) называется произвольное линейное $k$-мерное подпространство $n$-мерного векторного пространства $\mathbb{F}_q^n$. 
Элементы линейного кода $\mathcal{C} \subseteq \mathbb{F}_q^n$ называются \emph{кодовыми словами}.
Отношение $R =  k /  n$ линейного кода $\mathcal{C}\subseteq\mathbb{F}_q^n$ называется \emph{скоростью кода (code rate)}. 
\emph{Вес вектора} $v  \in \mathbb{F}_q^n$ --- количество ненулевых элементов вектора. Вес будем обозначать через $|v|$. 
\emph{Расстояние Хэмминга} между векторами $x, y  \in \mathbb{F}_q^n$ определим как \[ d(x,y) = |x-y|,\]
то есть как число позиций, в которых $x$ и $y$ не совпадают.
Минимальное расстояние между различными кодовыми словами кода $\mathcal{C}\subseteq \mathbb{F}_q^n$ называется \emph{расстоянием кода}. Обозначим его через $d_{\min}(\mathcal{C})$. Иногда удобнее использовать \emph{относительное минимальное расстояние} $\delta_{\min}(\mathcal{C}):=d_{\min}(\mathcal{C})/n$.
\noindentЛегко показать, что в линейном коде $\mathcal{C}$ кодовое расстояние равно весу его минимального ненулевого элемента:
\[
d_{\min}(\mathcal{C}) = \min_{c\in \mathcal{C}\setminus\{0\}}  | c |.
\]

\subsection{Коды Таннера}
Нас будет интересовать класс линейных кодов, которые определяются на графах через набор локальных проверок. В дальнейшем будем следовать изложению определения таких кодов из работы \cite{Tanner1981}.

Пусть \(A\) и \(B\) — произвольные множества. Через \(A^B\) понимаются множества всех функций (отображений), определённых на \(B\) и принимающих значения в \(A\). 

\begin{definition}[Код Таннера]
Пусть $G=(V,E)$ --- $w$-регулярный граф, в котором все рёбра, выходящие из вершины $v$, занумерованы от $1$ до $w$, обозначим их $e_{v,1},\ldots,e_{v,w}$. Пусть также есть набор линейных кодов $\mathcal{C}=(\mathcal{C}_v)_{v\in V}$, $\mathcal{C}_v\subseteq \mathbb{F}_q^w$. \emph{Код Таннера} $\mathcal{T}(G, \mathcal{C})$ --- это линейный код, состоящий из всех кодовых слов $c\in \mathbb{F}_q^E$, таких что $c_v\in \mathcal{C}_v$ для всех вершин $v\in V$, где $c_v=(c(e_{v,1}),\ldots,c(e_{v,w}))$.
\end{definition}


\subsubsection{Граф инцидентности проективного пространства}
\newcommand{\Gr}{\mathsf{Gr}}
Мы будем исследовать коды Таннера на двудольном графе $\Gamma_{D,q}$ инцидентности прямых и гиперплоскостей $(D+1)$-мерного пространства $\mathbb{F}_q^{D+1}$ (который можно также интерпретировать как граф инцидентности точек и гиперплоскостей $D$-мерного проективного пространства над полем $\mathbb{F}_q$). Определим этот граф в том виде, как нам будет удобно его использовать, приводя заодно некоторые вспомогательные определения из \cite[стр. 9]{graph_theory}.

\noindentНапомним, что \emph{степенью вершины} $v$ в графе $G$ называется число инцидентных ей рёбер. Граф $G$ называется \emph{регулярным (или однородным)} графом, если степени всех его вершин равны.

Нам будет удобно задавать двудольный граф тройкой $G=(V_0,V_1,E)$, где $V_0, V_1$ --- множества вершин первой и второй доли, $E\subseteq V_0\times V_1$ --- множество рёбер.

Обозначим $\Gr_q(D,k):=\{V\subseteq \mathbb{F}_q^D\mid \dim V=k\}$ --- множество всех $k$-мерных подпространств $D$-мерного пространства над полем $\mathbb{F}_q$.

Тогда $\Gamma_{D,q}=(\Gr_q(D+1,1),\Gr_q(D+1,D),E)$, где 
\begin{align*}
E&=\{(\ell,h)\in \Gr_q(D+1,1)\times\Gr_q(D+1,D)\mid \ell\subseteq h\}.
\end{align*}

Определим скалярное произведение $\langle\alpha,\beta\rangle:=\sum_{i=0}^{D}\alpha_i\beta_i$ векторов $\alpha,\beta\in \mathbb{F}_q^{D+1}$. Каждую прямую $\ell\in\Gr_q(D+1,1)$ можно однозначно задать ненулевым вектором (\emph{представителем}) $\hat{\ell}\in \mathbb{F}_q^{D+1}$ на этой прямой, а каждую гиперплоскость $h\in \Gr_q(D+1,D)$ можно задать ненулевым вектором (\emph{представителем}) $\hat h$, ортогональным данной гиперплоскости. Поскольку представители $\hat \ell$ и $\hat h$ определены с точностью до умножения на константу, для определённости потребуем, чтобы у представителей первая ненулевая координата была равна $1$.

Представители прямых и гиперплоскостей можно естественным образом взаимно-однозначно отождествить с точками проективного пространства 
\[\mathbb{P}^D_q=(\mathbb{F}_q^{D+1}\setminus \{0\})/\sim,\] 
где $x\sim y$, если $x=\gamma y$ для некоторого $\gamma\in\mathbb{F}_q\setminus\{0\}$ для $x,y\in \mathbb{F}_q^{D+1}\setminus\{0\}$.
Каждой точке $x\in \PP_q^D$ сопоставляется вектор длины $D+1$ её однородных координат.

Теперь мы можем ввести чуть более удобное определение $\Gamma_{D,q}=(\PP_{q}^{D}, \PP_{q}^{D}, E)$, где
\begin{align*}
E&=\{(x,y)\in \PP_q^{D}\times \PP_q^{D} \mid \langle x,y\rangle=0\}.
\end{align*}

\subsubsection{Код на графе проективного пространства}
Введём ещё несколько необходимых определений и обозначений.
Пусть $f \in \mathbb{F}_q[x_1, \ldots, x_n]$ --- полином, тогда его \emph{степень $\deg_{x_{i_1}, x_{i_2}, \ldots, x_{i_m}} f$ по переменным} $x_{i_1}, x_{i_2}, \ldots, x_{i_m}$ определим как максимальную степень его монома по этим переменным, где степень монома определяется как
\[
\deg_{x_{i_1},\ldots, x_{i_m}}
  \bigl(c x_1^{d_1} x_2^{d_2}\cdots x_n^{d_n}\bigr) = \\[-0.3em]
 d_{i_1} + d_{i_2} + \cdots + d_{i_m}.
\] 
В частности, \emph{степенью} полинома $f$ называется степень по всем его переменным:
\[
\deg f = \deg_{x_1, \ldots, x_n} f.
\]
Полином называется \emph{однородным по переменным $x_{i_1}, \ldots, x_{i_m}$}, если для любого монома, входящего в данный полином, его степень по переменным $x_{i_1}, \ldots, x_{i_m}$ равна одной и той же величине $d$. Полином называется \emph{однородным степени $d$}, если степень всех его мономов равна $d$.

Введём несколько обозначений.
\begin{enumerate}
    \item $\mathbb{F}_q[x_1,\ldots,x_n]$ --- кольцо полиномов от переменных $x_1,\dots,x_n$ над полем $\F_q$;
    \item $\mathbb{F}_q[x_1,\ldots,x_n]_{\le \nu}$ --- множество полиномов степени не выше $\nu$ над полем $\F_q$;
    \item $\mathbb{F}_q[x_1,\ldots,x_n]_{\nu}$ --- множество однородных полиномов степени $\nu$ над полем $\F_q$, включающее в себя нулевой полином.
\end{enumerate}

Зафиксируем $D\ge 2$, $m < q(D-1)$. Определим код $\mathcal{C}_{D,q,m}$ как множество функций $c:E(\Gamma_{D,q})\to \mathbb{F}_q$ таких, что для любого $\gamma\in \PP_q^{D}$ существуют однородные полиномы $f_{\gamma}$, $f^{\gamma}\in\F_q[x_0,\dots,x_D]_m$ такие, что $c(\alpha,\beta)=f_\alpha(\beta)=f^\beta(\alpha)$ для всех рёбер $(\alpha,\beta)\in E(\Gamma_{D,q})$.
\begin{remark*}
     Код \( \mathcal{C}_{D,q,m} \) является кодом Таннера на графе $\Gamma_{D,q}$, в котором для различных вершин могут использоваться различные локальные коды.
\end{remark*}

\subsection{Полученные результаты}
\begin{restatable}{theorem}{ThDistance}\label{th:dist}
Пусть для каждой вершины $v \in V$ графа \(\Gamma_{D,q}\) выбран локальный код 
$\mathcal{C}_v \subseteq \mathbb{F}_q^{w}$, $w=\frac{q^D-1}{q-1}$. Обозначим за $\mathcal{C} = \{\mathcal{C}_v\}_{v \in V}$ --- семейство таких кодов, где длина каждого кода составляет \(w\) и расстояние не меньше \(\varepsilon w\). Тогда относительное минимальное расстояние кода $\cT=\cT(\Gamma_{D,q}, \mathcal{C})$ удовлетворяет оценке:
\[
\delta_{\min}(\mathcal{T}) 
\ge 
\varepsilon\left(\varepsilon - \sqrt{q^{1-D}}\right).
\]
\end{restatable}


\begin{restatable}{theorem}{ThDistanceCqm}\label{th:c2qm}
Пусть $0\le m < q$. Тогда 
$\delta_{\min}(\mathcal{C}_{2,q,m})\ge \varepsilon^3$, где $\varepsilon=\frac{q-m}{q}$.
\end{restatable}

\begin{restatable}{theorem}{ThDistanceCDqm}
\label{th:cdqm}
Пусть $m<q$, $D\ge 3$. Тогда
\[
\delta_{\min}(\mathcal{C}_{D,q,m})\ge \frac{(q-m)^2(q-2)}{q^3}.
\]
\end{restatable}

\begin{restatable}{theorem}{Dimension}\label{th:dimension}
Пусть $1 \leq m < q / 2$. Тогда
\[
\dim {\mathcal{C}_{D,q,m}} \geq \frac{2m+D}{D}\binom{m+D-1}{D-1}^2.
\]
\end{restatable}

Таким образом, для случая проективной плоскости ($D=2$) получаем следствие
\begin{corollary}
Пусть $1 \leq m < q / 2$. Тогда
\begin{equation}\label{eq:dim-2qm}
\dim {\mathcal{C}_{2,q,m}} \geq (m+1)^3.
\end{equation}
\end{corollary}
\noindent
Отметим, что аналогичные результаты для кодов на графах аффинных плоскостей получены в работах \cite{HoholdtJustesen2006,BeelenHoholdtPineroJustesen2013,DinurHDE,Pinero2015}. В \cite{HoholdtJustesen2006} также без доказательства упомянуто, что оценки для аффинного случая переносятся на проективный, однако это не всегда выполняется и требует дополнительного исследования\footnote{в частности, при $q=9,m=3$ в аффинном случае размерность $66$ \cite{BeelenHoholdtPineroJustesen2013}, а в проективном $64$ (см. Приложение \ref{sec:numeric-results})}. 
Более того, на основании результатов численного эксперимента, в котором размерность кода \(\mathcal{C}_{2,q,m}\) оценивалась по рангу его проверочной матрицы, можно также выдвинуть следующее предположение:

\begin{hypothesis}
Пусть $q/2 \leq m < q$. Тогда
\[
\dim {\mathcal{C}_{2,q,m}} \ge (2m+1-q)(q^2+q+1) + (q-m)^3.
\]
\end{hypothesis}
Заметим, что в случае $q=9,m=4$ размерность равна $131$, что выше оценки \eqref{eq:dim-2qm}. В \cite{BeelenHoholdtPineroJustesen2013,Pinero2015} детально исследован аффинный случай и показано, что для кодов на графе аффинной плоскости для $q=9,k=4$ (в наших обозначениях это соответствует $m=3$): размерность равна $66$, что выше общей нижней оценки $k^3=64$.


Для линейных кодов $\cC_1,\cC_2\subseteq \F_q^n$ линейное отображение $\phi:\cC_1\to\cC_2$ называется \emph{изометрией} кодов $\cC_1$ и $\cC_2$, если $\phi(\cC_1)=\cC_2$ и $\phi$ сохраняет вес Хэмминга, то есть $|\phi(x)|=|x|$ для любого $x\in \cC_1$. Коды $\cC_1$ и $\cC_2$ называются \emph{эквивалентными}, если между ними существует изометрия. 
\emph{Мономиальным преобразованием} пространства $\F_q^n$ называется композиция перестановки координат и умножения каждой координаты на ненулевой элемент поля. Любое мономиальное преобразование является изометрией кодов.


Следующее утверждение показывает, что код $\cC_{D,q,m}$ обладает определённой симметрией.

Для любого вектора \(\alpha = (\alpha_0,\dots,\alpha_D) \in \F_q^{D+1}\setminus\{0\}\) обозначим через \( \hat{\alpha}\) нормированный вектор, где первая ненулевая компонента равна 1. Здесь 
\[\hat{\alpha} =\frac{\alpha}{\alpha_i}=\Bigl(0,\dots,0,\underbrace{1}_{i},\tfrac{\alpha_{i+1}}{\alpha_i},\dots,\tfrac{\alpha_{D}}{\alpha_i}\Bigr),\]
где \(i = \min\{k\in\{0,\dots,D\}\mid \alpha_k\neq 0\}\). Таким образом, $\hat\alpha$ --- однородные координаты точки проективного пространства $\PP_q^D$, соответствующей прямой, проходящей через точку $\alpha$.

\begin{restatable}{proposition}{Symmetry}\label{st:symmetry}
Пусть $D\ge 2$, $1\le m< (q-1)D$, $E=E(\Gamma_{D,q})$, $\cC=\cC_{D,q,m}$. Для любой матрицы \(A \in \GL(D+1,q)\) существует набор ненулевых констант \(a=(a_{(\alpha, \beta)})_{(\alpha,\beta)\in E}\in\mathbb{F}_q^E\) такой, что для любого кодового слова \(c\in\mathcal \cC\) существует кодовое слово $c'\in \cC$, удовлетворяющее условию:
\[
c'(\alpha,\beta)
=
a_{(\alpha,\beta)}c\bigl(\widehat{A\alpha},\widehat{A^*\beta}\bigr)\qquad\mbox{ для всех }(\alpha,\beta)\in E,
\]
где $A^*=(A^T)^{-1}$.
\end{restatable}


Из данного утверждения, в частности, следует, что группа изометрий кода $\cC_{D,q,m}$ включает в себя группу проективных преобразований $\PGL(D+1,q)$.

\section{Вспомогательные результаты}\label{sec:aux-results}
\subsection{Коды Рида-Маллера}
Для доказательства основных результатов нам понадобятся известные результаты о размерности и минимальном расстоянии недвоичных кодов Рида-Маллера.
\newcommand{\RM}{\mathrm{RM}}
\newcommand{\PRM}{\mathrm{PRM}}
\newcommand{\PRS}{\mathrm{PRS}}
Пусть $\F_q^D=\{\alpha_1,\dots,\alpha_{q^D}\}$.
Кодом Рида-Маллера порядка $\nu$ длины $q^D$ над полем $\F_q$ называется множество
\[
\RM_q(\nu, D):=\left\{(p(\alpha_i)_{i=1}^{q^D}) \ \middle|\  p\in \F_q[x_1,\ldots,x_D]_{\le\nu}\right\}.
\]
Известно \cite[стр. 1568]{Sorensen1991}, что при $\nu<q$ коды Рида-Маллера имеют следующие параметры:
\begin{align*}
    &\dim\RM_q(\nu, D)=\binom{\nu+D}{D},\\
    &d_{\min}(\RM_q(\nu,D))=(q-\nu)q^{D-1}.
\end{align*}

Теперь определим проективные коды Рида-Маллера. 
Пусть $\PP_q^D=(P_1,\dots,P_{n_D})$, где $n_D:=|\PP_q^D|=\frac{q^{D+1}-1}{q-1}$, $P_i$ --- однородные координаты $i$-й точки проективного пространства. Проективным кодом Рида-Маллера порядка $\nu$ длины $n_D$ называется код
\[
\PRM_q(\nu,D):=\left\{\bigl(p(P_i)\bigr)_{i=1}^{n_D} \ \middle|\  p\in \F_q[x_0,x_1,\ldots,x_D]_{\nu}\right\}
\]
Известно \cite[Раздел III, Теорема 1, стр. 1568--1569]{Sorensen1991}, что при $1\le \nu<q$ проективные коды Рида-Маллера имеют следующие параметры:
\begin{align}
    &\dim\PRM_q(\nu, D)=\binom{\nu+D}{D},\label{eq:dim-prm}\\
    &d_{\min}(\PRM_q(\nu,D))=(q-\nu+1)q^{D-1}.\label{eq:dist-prm}
\end{align}
При этом при $\nu=0$ код содержит только полиномы нулевой степени, то есть константы, поэтому $\PRM_q(0,D)$ --- это просто код с повторением длины $n_D$.

При $D=1$ коды Рида-Маллера соответствуют расширенным кодам Рида-Соломона длины $q$, где значение полинома дополнительно вычисляется в точке $0$. Проективные коды Рида-Маллера при $D=1$ в точности соответствуют проективным кодам Рида-Соломона, где значение полинома дополнительно вычисляется в $0$ и в бесконечно удалённой точке (старший коэффициент полинома), т.е.
\[
\PRS(q,k)=\PRM_q(k-1, 1).
\]
В частности,
\begin{align*}
    &\dim \PRS(q,k)=k,\\
    &d_{\min}(\PRS(q,k)) = q-k+2.
\end{align*}
Как и обычные коды Рида-Соломона, проективные коды Рида-Соломона являются MDS кодами, то есть для них достигается оценка Синглтона.

\subsection{Графы--расширители (expander graphs)}
Приведём определения разных видов расширения графов (см. \cite[стр. 109]{gashkov2009}, \cite[стр. 9]{graph_theory}, \cite[стр. 7]{ExpandersIT}).

Пусть дан регулярный граф $G$ степени $d$ с $n$ вершинами, все вершины которого пронумерованы от $1$ до $n$.
\emph{Матрицей смежности} $A(G)$ порядка $n \times n$ графа $G$ называется симметричная бинарная матрица вида:
\begin{equation*}
\textbf{$A_{ij}$} = 
\begin{cases}
1, & \text{если вершины $i$ и $j$ смежны}; \\
0, & \text{в противном случае}.
\end{cases}
\end{equation*}

Все собственные значения матрицы $A(G)$ упорядочим в виде:
\[
\lambda_1 = d
\;\ge\;
\lambda_2
\ge
\dots
\;\ge\;
\lambda_{n-1}
\;\ge\;
\lambda_n.
\]

Второе по абсолютной величине собственное значение $\max(|\lambda_2|,|\lambda_n|)$ характеризует спектральное расширение графа. Для двудольных регулярных графов $\lambda_n=-d$, и таким образом $\lambda(G)=d$. Поэтому в этом случае используется ослабленный вариант спектрального расширения, которое характеризуется вторым собственным значением $\lambda_2$.

Пусть \(V\) --- множество вершин данного графа $G$ и пусть $S,T\subseteq V$. Обозначим:  
\[
E(S, T) = \{(s, t) \in E \mid s \in S, t \in T\}, \qquad E(S):=|E(S,S)|/2.
\]
Заметим, что в $E(S,S)$ каждое ребро $\{u,v\}$ входит два раза: как $(u,v)$ и как $(v,u)$; поэтому при подсчёте числа рёбер $E(S)$, индуцированных на множестве вершин $S$, мы делим число пар в $E(S,S)$ пополам.

\begin{lemma}[Alon-Chung, \cite{Alon_Chung}]\label{lem:expansion}
Пусть \(G\) --- \(d\)-регулярный граф порядка \(n\), второе собственное значение которого равно \(\lambda\). Пусть \(X\subset V(G)\) --- произвольное подмножество вершин, такое что \(|X| = \gamma n\) для некоторого \(\gamma\in[0,1]\). Тогда число рёбер, индуцированных на \(X\), удовлетворяет неравенству 
\[
E(X) \le \frac{dn}{2}\left(\gamma^2 + \frac{\lambda}{d}\,\gamma\,(1-\gamma)\right).
\]
\end{lemma}

\subsubsection{Спектр графа инцидентности проективного пространства}
\begin{lemma}\label{lemma:proj-incidence-spec}
Матрица смежности графа $\Gamma_{D,q}$ имеет следующие собственные значения:
\begin{enumerate}
    \item $\pm w$ кратности $1$, где $w=\frac{q^D-1}{q-1}$ --- степень вершины;
    \item $\pm q^{\frac{D-1}{2}}$ кратности $n-1$, где $n=\frac{q^{D+1}-1}{q-1}$ --- число вершин в каждой доле.
\end{enumerate}
\end{lemma}
\begin{proof}
\newcommand{\dotprod}[1]{\langle #1 \rangle}
\newcommand{\abprod}{\dotprod{\alpha,\beta}}
Матрица смежности графа $\Gamma_{D,q}$ имеет вид
\[
A =
\begin{pmatrix}
0 & M \\[6pt]
M^{T} & 0
\end{pmatrix},
\]
где \(M=(M_{\alpha,\beta})_{\alpha,\beta\in \PP_q^D}\), \[
    m_{\alpha,\beta} = \begin{cases}
1, & \abprod=0,\\
0, & \text{иначе}.
\end{cases}
 \]
 Здесь строки и столбцы матрицы $M$ проиндексированы точками проективного пространства $\PP_q^D$.
 
Для $\alpha\in \PP_q^D$ введём обозначение 
\[
    \alpha^\perp:=\{\beta\in \PP_q^D\mid \abprod=0\}.
\]
Заметим, что $\alpha^\perp$ представляет собой $(D-1)$-мерное проективное пространство, поэтому $|\alpha^\perp|=\frac{q^D-1}{q-1}=w$. Для различных $\alpha,\alpha'\in\PP_q^D$ множество $\alpha^\perp\cap\alpha'^\perp$ представляет собой $(D-2)$-мерное проективное пространство. Отсюда
\begin{align}
    &|\alpha^\perp|=\frac{q^D-1}{q-1}=w, \label{eq:1-perp}\\
    &|\alpha^\perp\cap\alpha'^\perp|=\frac{q^{D-1}-1}{q-1}=:s. \label{eq:2-perp}
\end{align}
Вычислим матрицу $MM^T$, используя \eqref{eq:1-perp} и \eqref{eq:2-perp}:
\[
(MM^{T})_{\alpha,\alpha'}
=\bigl|\{\beta: \abprod=\dotprod{\alpha',\beta}=0\}\bigr|=|\alpha^\perp\cap\alpha'^\perp|
=
\begin{cases}
w,& \alpha=\alpha',\\
s,& \alpha\neq\alpha'.
\end{cases}
\]
Таким образом,
\[
MM^{T}
= sJ_n + (w-s)I_{n},
\]
где \(J_n\) --- $n\times n$ матрица из единиц, \(I_n\) --- единичная матрица $n\times n$.

Пусть \(\mathbf{1}\) --- вектор длины $n$, все компоненты которого равны $1$. Легко видеть, что $J_n\mathbf{1}=n\mathbf{1}$, а также $J_nx=0$ для любого вектора $x$, ортогонального $\mathbf{1}$.
Таким образом, матрица $J_n$ имеет однократное собственное значение \(n\) и $(n-1)$-кратное собственное значение \(0\). Значит, \(MM^{T}\) имеет спектр:
\begin{align*}
\lambda_{2} &=\cdots=\lambda_{n} = w-s 
= \frac{q^{D}-q^{D-1}}{q-1}
= q^{D-1},\\
\lambda_{1} &= s n + (w-s)
= \frac{(q^{D+1}-1)(q^{D-1}-1)}{(q-1)^2}+q^{D-1}
=\frac{q^{2D}-2q^D+1}{(q-1)^2}=w^2.
\end{align*}
Поскольку матрица $M$ симметричная, то модули её собственных значений равны корню из собственных значений матрицы \(MM^T\):
\[
\lambda_{1}(M)=w,
\quad
\lambda_{2}(M)=\cdots=\lambda_{n}(M) =\sqrt{q^{D-1}}.
\]
Осталось заметить, что матрица
\[
A=\begin{pmatrix}0&M\\M^{T}&0\end{pmatrix}
\]
имеет в спектре значения \(\pm\lambda_i(M), i=1,\dots,n\). Лемма доказана.
\end{proof}

\section{Доказательство основных результатов}\label{sec:proof}
\subsection{Оценка минимального расстояния}\label{sec:distance}
\noindentСемейство кодов назовём \emph{асимптотически хорошим}, если минимальное расстояние пропорционально длине кода и скорость не меньше некоторого $R > 0$. В свою очередь, это означает, что для каждого кода из семейства минимальное расстояние $d_{\text{min}}$ растёт линейно с длиной $n$, обычно так, что $d_{\text{min}} \geq \alpha n$, где $\alpha > 0$ — фиксированная константа, $k \geq Rn$.

\noindent Приведём нижнюю оценку минимального расстояния, также упоминавшуюся в работах \cite{HoholdtJustesen2006, HoholdtJustesen2011, Pinero2015} для графовых кодов. Здесь мы приведём явное доказательство для графа проективной плоскости $\Gamma_{2,q}$.

\begin{lemma}\label{lemma:qubic_dist}
Пусть для каждой вершины $v \in V$ графа $\Gamma_{2,q}$ выбран локальный код $\mathcal{C}_v \subseteq \mathbb{F}_q^{q+1}$. Через $\mathcal{C} = \{\mathcal{C}_v\}_{v \in V}$ обозначим семейство таких кодов с расстоянием не меньше $d$. Будем считать, что в каждой вершине графа $\Gamma_{2,q}$ фиксирована нумерация инцидентных рёбер. Тогда код $\mathcal{T}(\Gamma_{2,q}, \mathcal{C})$ обладает минимальным расстоянием не меньше:
\[
d_{min}\Bigl(\mathcal{T}\left(\Gamma_{2,q},\mathcal{C}\right)\Bigr)
\ge d(d(d-1)+1).
\]
В частности, при выборе $\mathcal{C}\equiv\mathcal{C}_0$ для всех $v\in V$ получаем конструкцию кода Таннера вида $\mathcal{T}(\Gamma_{2,q},\mathcal{C}_0)$.
\end{lemma}


\begin{figure}[ht]
  \centering
  \resizebox{\linewidth}{!}{%
  \begin{tikzpicture}[x=0.65cm,y=0.65cm, transform shape, >=Stealth]
    \tikzset{v/.style={rectangle, draw, minimum size=0.6cm}}

   
    \foreach \i/\x/\col in {1/0/red, 2/2/white, 3/4/white, 4/6/red, 5/8/white, 6/10/red, 7/12/white, 8/14/red}{
      \node[v, fill=\col] (L\i) at (\x,0) {};
    }
    
    \foreach \i in {1,4,6,8}{
      \node[above=0.1cm of L\i, font=\scriptsize, red] {$\ge d$};
    }

   
    \foreach \i/\x/\col in {1/0/white, 2/2/red, 3/4/red, 4/6/white, 5/8/red, 6/10/red, 7/12/white, 8/14/white}{
      \node[v, fill=\col] (R\i) at (\x,-3) {};
    }
   
    \foreach \i in {2,3,5,6}{
      \node[below=0.1cm of R\i, font=\scriptsize, red] {$\ge d$};
    }

  
    \node at (7,0) {$\ldots$};
    \node at (7,-3) {$\ldots$};

   
    \draw[gray, thick] (L1) -- (R1);
    \draw[red, thick]  (L1) -- (R2);
    \draw[red, thick]  (L1) -- (R3);
    \draw[gray, thick] (L2) -- (R1);

    \draw[gray, thick] (L2) -- (R2);
    \draw[gray, thick] (L2) -- (R3);
    \draw[gray, thick] (L2) -- (R4);

    \draw[gray, thick] (L3) -- (R3);
    \draw[gray, thick] (L3) -- (R4);

    \draw[red,  thick] (L4) -- (R2);
    \draw[red,  thick] (L4) -- (R3);
    \draw[gray, thick] (L4) -- (R4);

    \draw[gray, thick] (L5) -- (R5);
    \draw[gray, thick] (L5) -- (R6);
    \draw[gray, thick] (L5) -- (R7);
    \draw[gray, thick] (L5) -- (R8);

    \draw[red,  thick] (L6) -- (R5);
    \draw[red,  thick] (L6) -- (R6);

    \draw[gray, thick] (L7) -- (R6);
    \draw[gray, thick] (L7) -- (R5);
    \draw[gray, thick] (L7) -- (R7);
    \draw[gray, thick] (L7) -- (R8);

    \draw[red,  thick] (L8) -- (R6);
    \draw[red,  thick] (L8) -- (R5);
  \end{tikzpicture}%
  }
 
  \label{fig:tanner}
\end{figure}

\begin{proof}
Для краткости обозначим $\Gamma:=\Gamma_{2,q}$, $E:=E(\Gamma)$ --- множество рёбер графа $\Gamma$.
Рассмотрим ненулевое кодовое слово $c\in \mathcal{T}(\Gamma, \mathcal{C})$ минимального веса. Напомним, что кодовое слово кода $\mathcal{T}(\Gamma, \mathcal{C})$ --- это функция, определённая на множестве рёбер графа $\Gamma$. \emph{Активными} назовём те рёбра $e\in E$, для которых $c(e)\ne 0$, таким образом $d(\mathcal{T}(\Gamma, \mathcal{C}))=|c|$ равно числу активных рёбер. Вершину графа $\Gamma$ назовём \emph{активной}, если из неё исходит хотя бы одно активное ребро. Напомним, что каждой вершине графа соответствует точка или прямая проективной плоскости. Точку или прямую будем называть \emph{активной}, если соответствующая вершина графа $\Gamma_{2,q}$ активна. 

Так как код Таннера $\mathcal{T}(\Gamma, \mathcal{C})$ состоит из всех кодовых слов $c\in \mathbb{F}_q^E$ таких, что $c_v\in\mathcal{C}_v$ для всех вершин $v\in V$, где $c_v=(c(e_{v,1}),\ldots,c(e_{v,w}))$, то
рассмотрим произвольную активную прямую, из которой исходит не менее $d$ активных рёбер. Поскольку эта прямая инцидентна по меньшей мере $d$ активным точкам, то на ней расположены как минимум $d$ активных точек. В свою очередь, через каждую активную точку рассматриваемой прямой проходит ещё не менее $d - 1$ активных прямых по построению. Тогда всего активных прямых будет не менее $d(d - 1) + 1$. 
Как уже упоминалось ранее, из соответствующих вершин графа исходит как минимум $d$ активных рёбер, таким образом общее число активных рёбер не меньше $d(d(d - 1) + 1)$.
\end{proof}


\begin{lemma}
\label{lemma:expander_distance}
Пусть \(G\) --- \( w\)-регулярный граф порядка $n$ со вторым по величине собственным значением \( \lambda \). Пусть для каждой вершины $v \in V$ графа $G$ сопоставлен линейный код $\mathcal{C}_v$ с длиной $w$ и минимальным расстоянием не меньше \( \varepsilon w \). Обозначим за $\mathcal{C} = \{\mathcal{C}_v\}_{v \in V}$ --- семейство таких кодов, тогда выполнена оценка: 
\[
\delta_{\min}(\mathcal{T}(G, \mathcal{C}))\ge \varepsilon\left(\varepsilon - \frac{\lambda}{w}\right).
\]
\end{lemma}
Эта лемма аналогична \cite[Lemma 15]{ExpandersIT}, но мы не предполагаем, что все локальные коды одинаковые. Приведём здесь доказательство, идея которого полностью аналогична той, что использовалась в \cite[Lemma 15]{ExpandersIT}.
\begin{proof}
Пусть $c$ \(\in \mathcal{T}(G, \mathcal{C})\) --- некоторое ненулевое кодовое слово минимального веса. Обозначим за \(S\) множество рёбер графа $G$ с ненулевыми пометками и \(A\) --- множество вершин, инцидентных рёбрам из $S$. Пусть 
\[
\gamma:=\frac{|A|}{n}.
\]
По лемме \ref{lem:expansion} выполнено 
\[
|S|
\le
\frac{wn}{2}\Bigl(\gamma^2+\tfrac{\lambda}{w}(\gamma-\gamma^2)\Bigr).
\]
Поскольку каждое ребро из \(S\) инцидентно по крайней мере двум вершинам, значит в среднем на одну вершину из \(A\) приходится рёбер
\[
\frac{2|S|}{|A|}
\le
\frac{wn\bigl(\gamma^2+\frac{\lambda}{w}(\gamma-\gamma^2)\bigr)}{\gamma n}
=
w\Bigl(\gamma+\tfrac{\lambda}{w}(1-\gamma)\Bigr).
\]
По условию, из каждого локального кода \(\mathcal C_v\) для $v\in A$ исходит не менее \(\varepsilon w\) рёбер с ненулевыми пометками, поэтому
\[
\gamma+\frac{\lambda}{w}(1-\gamma)\ge \varepsilon
\quad\Longrightarrow\quad
\gamma \ge \frac{\varepsilon-\frac{\lambda}{w}}{1-\frac{\lambda}{w}}\ge \varepsilon - \frac{\lambda}{w}.
\]
Также
\[
|S|\ge \frac12\varepsilon w |A|=\gamma\varepsilon\frac{ w n}{2}= \gamma\varepsilon|E(G)|.
\]
Таким образом, относительное число рассматриваемых рёбер будет не меньше
\[
\frac{|S|}{|E(G)|}\ge \varepsilon\left(\varepsilon - \frac{\lambda}{w}\right),
\]
что и доказывает утверждение леммы.
\end{proof}

\ThDistance*


\begin{proof}
По лемме \ref{lemma:proj-incidence-spec} второе собственное значение графа $\Gamma_{D,q}$ равно $\lambda=\sqrt{q^{D-1}}$.
Согласно лемме~\ref{lemma:expander_distance}, 
для \(\mathcal{T}\) справедливо:
\[
\delta_{\min}(\cT)
\ge 
\varepsilon\left(\varepsilon - \frac{\lambda}{w}\right)=\varepsilon\left(\varepsilon - \frac{\sqrt{q^{D-1}}}{w}\right).
\]
Учитывая, что $w=\frac{q^D-1}{q-1}>q^{D-1}$, имеем
\[
\delta_{\min}(\cT)
\ge 
\varepsilon\left(\varepsilon - \frac{\sqrt{q^{D-1}}}{q^{D-1}}\right)=\varepsilon\left(\varepsilon - \sqrt{q^{1-D}}\right).      \qedhere
\]
\end{proof}

\begin{lemma}\label{lemma:localcode=prm}
    Для кода $\cC_{D,q,m}$ в каждой вершине $v\in V(\Gamma_{D,q})$ локальный код $\cC_v$ эквивалентен проективному коду Рида-Маллера $\PRM_q(m,D-1)$.
\end{lemma}
\begin{proof}
    Обозначим $w:=\frac{q^D-1}{q-1}$ --- степень вершины $\Gamma_{D,q}$.
    В каждой вершине $v$ графа \(\Gamma_{D,q}\), соответствующей точке $\alpha$ проективного пространства, по определению локальный код \(\mathcal{C}_v\subset \mathbb{F}_q^w\) задаётся следующим образом: 
    \[
        \cC_v=\left\{(f_\alpha(\beta))_{\beta\in \PP_q^D:\langle\alpha,\beta\rangle=0}\ \middle|\ f_\alpha\in \F_q[a_0,\dots,a_D]_m\right\}.
    \]
    Поскольку условие \(\langle \alpha,x\rangle = \sum_{i=0}^D\alpha_ix_i=0\) является линейным относительно переменных \(x_0,\dots,x_D\), то, без ограничения общности полагая \(\alpha_0\neq 0\), можно выразить \(x_0\) через \(x_1,\dots,x_D\):
    \[
        x_0 = -\sum_{i=1}^D\frac{\alpha_i}{\alpha_0}x_i.
    \]
    Подставляя это выражение в \(f_\alpha(x_0,\dots,x_D)\), получаем функцию
    \[
        g_\alpha(x_1,\dots,x_D) := f_\alpha\Bigl(-\sum_{i=1}^D\frac{\alpha_i}{\alpha_0}x_i,\ x_1,\dots,x_D\Bigr).
    \]
    Так как исходный полином \(f_\alpha\) являлся однородным полиномом степени \(m\) от $D+1$ переменных, то полученный полином \(g_\alpha\) является однородным полиномом степени \(m\) от $D$ переменных. Таким образом, $\cC_v$ является множеством векторов значений полиномов от $D$ переменных, вычисленных в точках $(D-1)$-мерного проективного пространства, но не на однородных координатах, а на точках, отличающихся в константу раз. Поэтому $\cC_v$ изометричен коду $\PRM_q(m,D-1)$, где изометрия задаётся умножением координат на константы, обусловленные выбором представителей точек $\PP_q^{D-1}$.
    
    В силу симметричности конструкции такие же рассуждения применимы для вершин графа  
    \(\Gamma_{D,q}\), соответствующих гиперплоскостям проективного пространства. 
\end{proof}

Используя известную оценку минимального расстояния проективного кода Рида-Маллера \eqref{eq:dist-prm}, при $m<q$ получаем следствие.
\begin{corollary}\label{col:local-dist}
    Пусть $1\le m<q$, $D\ge 2$.
    Для кода $\cC_{D,q,m}$ в каждой вершине $v\in V(\Gamma_{D,q})$ минимальное расстояние локального кода $\cC_v$ равно $(q-m+1)q^{D-2}$.
\end{corollary}

\ThDistanceCqm*

\begin{proof}
Рассмотрим случай при $m=0$. В этом случае все локальные коды --- коды с повторением, а значит и весь код $\cC_{2,q,m}$ --- код с повторением, значит его относительное минимальное расстояние равно $1$; кроме того, $\varepsilon=\frac{q-m}{q}=1$, таким образом утверждение теоремы выполнено.

Теперь рассмотрим основной случай $m\ge 1$. По лемме \ref{lemma:localcode=prm} все локальные коды кода $\cC_{2,q,m}$ изометричны кодам Рида-Маллера $\PRM_q(m,1)$, то есть кодам Рида-Соломона $\PRS(q,m+1)$. Значит по следствию~\ref{col:local-dist} минимальное расстояние всех локальных кодов равно 
\[
d_0= q + 1 - m  = \varepsilon q+1.
\]
Согласно лемме \ref{lemma:qubic_dist}:
    \[
    d\bigl(\mathcal{C}_{2,q,m}\bigr) \ge d_0\Bigl(d_0(d_0-1)+1\Bigr).
    \]
Так как \( d_0 = \varepsilon\,q + 1\), то получим:
\[
d\bigl(\mathcal{C}_{2,q,m}\bigr) \ge (\varepsilon q + 1)\Bigl((\varepsilon q + 1)(\varepsilon q + 1 - 1) + 1 \Bigr) = (\varepsilon q + 1)\Bigl((\varepsilon q + 1)\varepsilon q + 1 \Bigr) =
\] 
\[
= (\varepsilon q + 1)\Bigl(\varepsilon^2 q^2 + \varepsilon q + 1 \Bigr) \ge
 \varepsilon^3(q + 1)\Bigl(q^2 + q + 1 \Bigr) = \varepsilon^3 n,
\]
где $n=(q + 1)(q^2 + q + 1)$ --- длина кода $\mathcal{C}_{2,q,m}$.
\end{proof}
Теперь докажем оценку расстояния для размерности $D\ge 3$, используя теорему~\ref{th:dist}.

\ThDistanceCDqm*

\begin{proof}
    Заметим, что при $m=0$ все локальные коды --- коды с повторением, а значит и весь код $\cC_{D,q,m}$ --- код с повторением, значит его относительное минимальное расстояние равно $1$, и утверждение теоремы выполнено. Далее предполагаем, что $m\ge 1$.
    
    Пусть $w:=\frac{q^D-1}{q-1}$ --- степень вершины графа $\Gamma_{D,q}$.
    По следствию \ref{col:local-dist} все локальные коды кода $\cC_{D,q,m}$ имеют минимальное расстояние
    \[
        d_0=(q - m + 1)q^{D-2}.
    \]
    Значит относительное минимальное расстояние можно оценить следующим образом:
    \[
        \varepsilon = \frac{d_0}{w}=\dfrac{(q+1-m)q^{D-2}}{\frac{q^D-1}{q-1}}\ge \frac{(q+1-m)(q-1)}{q^2}\ge\frac{q-m}{q}.
    \]
    Здесь мы использовали, что $(q+1-m)(q-1)=(q-m)q+m-1\ge (q-m)q$.
    По теореме \ref{th:dist} получим оценку
    \[
        \delta_{\min}(\cC_{D,q,m})\ge \varepsilon\left(\varepsilon-\sqrt{q^{1-D}}\right).
    \]
    Поскольку $D\ge 3$, то $\sqrt{q^{1-D}}\le 1/q$, значит \[
    \varepsilon-\sqrt{q^{1-D}}\ge\frac{(q+1-m)(q-1)}{q^2}-\frac{1}{q}=\frac{(q + 1-m)(q-1) - q}{q^2}
    \]
    или
    \[
    \varepsilon-\sqrt{q^{1-D}}\ge \frac{(q-m)(q-1) - 1}{q^2}\ge\frac{(q-m)(q-2)}{q^2}.
     \]
    Отсюда \[
        \delta_{\min}(\cC_{D,q,m})\ge \frac{(q - m)}{q}\cdot \frac{(q-m)(q-2)}{q^2} 
        \ge \frac{(q-m)^2(q-2)}{q^3}.\qedhere
    \]
\end{proof}

\subsection{Оценка размерности}\label{sec:dimension}
Далее будем считать, что размер поля $q$, параметр $m\in\mathbb{N}$ и размерность пространства $D\ge 2$ фиксированы. Далее опустим индексы и положим $\Gamma:=\Gamma_{D,q}$, $E:=E(\Gamma)$, $\mathcal{C}:=\mathcal{C}_{D,q,m}$.

Введём 2 группы переменных $x=(x_0,\ldots,x_D)$ и $a=(a_0,\ldots,a_D)$.
Через $P$ обозначим кольцо полиномов от $2(D+1)$ переменных над конечным полем $\mathbb{F}_q$:
\[
P = \mathbb{F}_q[x_0,\dots,x_D, a_0,\dots,a_D].
\]
Обозначим $B(x,a):=\langle x,a\rangle=\sum_{i=0}^Da_ix_i$ --- полином, задающий скалярное произведение.

Для $s\ge 0$ через $P_{s}$ обозначим множество полиномов из $P$, однородных по переменным $x_0,\ldots,x_D$ и по переменным $a_0,\dots,a_D$, таких, что $\deg_{x}(p) = \deg_{a}(p)= s$; также включим в $P_{s}$ нулевой полином, чтобы оно было линейным пространством.

Рассмотрим отображение:
\[
\sigma : P_{m} \to \mathbb{F}_q^E,
\]
где
\[
\sigma(p) = p \big|_E,
\qquad
\sigma(p; \alpha, \beta) = p(\alpha, \beta),
\]
где $(\alpha, \beta) \in E$.



\begin{lemma}\label{lemma:ker-sigma}
Пусть $1 \leq m < q / 2$. Тогда для любого $p \in P_{m}$ выполняется $\sigma(p) = 0$ тогда и только тогда, когда $B \mid p$. Другими словами, $\ker \sigma = P_{m-1}\cdot B$.
\end{lemma}
\begin{proof}\ 
\sufficiency
Докажем, что если для $p \in P_{m}$ выполнено $B \mid p$, то $\sigma(p) = 0$.
Напомним, что множество $E$ представлялось в виде:
\[
E = \{ (\alpha,\beta)\in \PP_q^D\times \PP_q^D \mid B(\alpha,\beta) = 0 \}.
\]
Поскольку $p=B r$ для некоторого $r\in P$, то в силу делимости имеем:
\[
p\big|_E = \underbrace{B\big|_E}_{\equiv 0} \cdot\, r\big|_E\equiv 0.
\]

\necessity
Докажем, что если для $p \in P_{m}$ верно, что $\sigma(p) = 0$, то $B \mid p$. Зафиксируем произвольный многочлен $p\in P_m$ такой, что $\sigma(p)=0$, то есть $p|_E=0$.

Домножим данный многочлен на $a_0^{m}$ и получим:
\[
a_0^{m}p(x,a)
\]
Введём замену:
\[
u = B(x,a).
\]
Выразим:
\begin{equation}\label{eqn:x-from-u}
 a_0x_0 = u - \sum_{i=1}^Da_ix_i.
\end{equation}
Заметим, что
\[
\deg_{x_0}p \le \deg_{x} p = m.
\]
Поскольку $\deg_{x_0} p\le m$, то в каждом мономе $a_0^{m}p$ степень $a_0$ не меньше, чем степень $x_0$. Поэтому существует такой многочлен $\hat{p}\in \mathbb{F}_q[u,x_1,\dots,x_D,a_0,\dots,a_D]$, что 
\[
    \hat{p}(B(x,a),x_1,\dots,x_D,a_0,\dots,a_D) = a_0^{m} p(x, a).
\] 
Каждому моному $\prod_{s=0}^Dx_s^{i_s}a_s^{j_s}$ многочлена $p$ соответствует слагаемое \[
a_0^{m - i_0}(u-\sum_{s=1}^Da_sx_s)^{i_0}a_0^{j_0}\prod_{s=1}^Dx_s^{i_s}a_s^{j_s}\]
в полиноме $\hat{p}$.
Отсюда
\[
\deg_{u,x_1,\dots,x_D} \hat p=\deg_{x} p= m. 
\]
Кроме того, поскольку $\sum_{s=0}^Dj_s=\deg_{a}p= m$, то
\[
\deg_{a}a_0^{m - i_0}(u-\sum_{s=1}^Da_sx_s)^{i_0}a_0^{j_0}\prod_{s=1}^Dx_s^{i_s}a_s^{j_s} = m-i_0+i_0+\sum_{s=0}^D j_s = 2m< q,
\]
значит $\deg_{a}\hat{p}< q$. Таким образом, степень $\hat p$ по каждой переменной не выше $q-1$.

Положим
\[
\tilde E:=\Bigl\{(u,x_1,\dots,x_D,a_0,\dots,a_D)\in \F_q^{2D+2}\ \Bigm|\ u=0\Bigr\}.
\]
Тогда для любой точки
\[
(0,x_1,\dots,x_D,a_0,\dots,a_D)\in \tilde E,\qquad a_0\ne 0
\]
возьмём
\[
x_0=-a_0^{-1}\sum_{i=1}^D a_ix_i,
\]
тогда
\[
(x,a)\in E.
\]
Тогда $p(x,a)=0$, и по определению многочлена $\hat p$ имеем
\[
\hat p(0,x_1,\dots,x_D,a_0,\dots,a_D)=a_0^m p(x,a) = 0.
\]
Осталось рассмотреть случай $a_0=0$. Покажем, что $\hat{p}$ делится на $a_0$.
Сгруппируем в полиноме $p$ все мономы, где $x_0$ входит в степени $m$, не содержащие $a_0$:
\[
p(x,a)=x_0^m h(a_1,\dots,a_D)+a_0q(x,a)+\sum_{s=1}^D x_s q_s(x,a),
\]
где $h$ --- однородный полином степени $m$ по переменным $a_1,\dots,a_D$, а $q,q_1,\dots,q_D$ --- некоторые полиномы.

Покажем, что $h\equiv 0$. Предположим противное. Тогда найдётся набор
\[
(a_1,\dots,a_D)\ne 0
\]
такой, что
\[
h(a_1,\dots,a_D)\ne 0.
\]
Рассмотрим точку
\[
x=(1,0,\dots,0),\qquad a=(0,a_1,\dots,a_D).
\]
Для неё
\[
B(x,a)=a_0x_0+\sum_{s=1}^D a_sx_s
=0\cdot 1+\sum_{s=1}^D a_s\cdot 0=0,
\]
поэтому $(x,a)\in E$. Так как $\sigma(p)=0$, имеем
\[
p(x,a)=0.
\]
С другой стороны, из приведённого разложения следует
\[
p(1,0,\dots,0,\,0,a_1,\dots,a_D)=h(a_1,\dots,a_D)\ne 0,
\]
поскольку $a_0=0$ и $x_1=\dots=x_D=0$. Получено противоречие. Значит,
\[
h\equiv 0.
\]
Тогда в каждом слагаемом полинома $\hat p$
\[
a_0^{m-i_0}\Bigl(u-\sum_{s=1}^D a_sx_s\Bigr)^{i_0}a_0^{j_0}\prod_{s=1}^D x_s^{i_s}a_s^{j_s}
\]
либо $i_0<m$, либо $j_0>0$. 
Следовательно, каждое слагаемое полинома $\hat p$ содержит множитель $a_0$, значит
\[
a_0\mid \hat p.
\]
Таким образом, в случае $a_0=0$, также имеем \[\hat p(0,x_1,\dots,x_D,a_0,\dots,a_D)=0.\]
Следовательно, если
\(
p\big|_E = 0,
\)
то и
\(
\hat{p}\big|_{\tilde E} = 0.
\)

Покажем, что \( u \mid \hat{p} \). Пусть $c_{i_0,\dots, i_D,j_0,\dots,j_D}\in \F_q$ --- коэффициент при мономе $\prod_{s=0}^Dx_s^{i_s}a_s^{j_s}$ в полиноме $\hat p$. 
Тогда 
\begin{equation}\label{f(0, y, z, a, b, c)} 
\hat p(0, x_1,\dots,x_D,a_0,\dots,a_D) = \!\!\!\!\!\sum_{i_1,\dots,i_D,j_0,\dots,j_D}\!\!\!\!\! c_{0,i_1,\dots,i_D,j_1\dots,j_D} \cdot a_0^{j_0}\prod_{s=1}^D x_s^{i_s}a_s^{j_s}.
\end{equation}
Предположим, что существует хотя бы один коэффициент 
\[
c_{0,i_1,\dots,i_D,j_1\dots,j_D} \neq 0 \quad \text{при некоторых } 0\le i_1,\dots,i_D,j_0,\dots,j_D< q.
\]
Зная, что степень $\hat p$ по каждой переменной не выше $q-1$
и используя тот факт, что любая функция, заданная на конечном множестве \(\mathbb{F}_q\), однозначно представима в виде многочлена степени не выше $q-1$, следует, что многочлен
\eqref{f(0, y, z, a, b, c)}
не может быть тождественно равен нулю, если хотя бы один коэффициент \(c_{0,i_1,\dots,i_D,j_0,\dots,j_D}\) не равен нулю. Это противоречит условию \(\hat{p}|_{\tilde E}=0\), а значит все эти коэффициенты должны быть нулевыми, и, следовательно, в $\hat p$ нет мономов, не содержащих $u$. 
Таким образом, \(\hat{p} = u\cdot r\) для некоторого $r\in \F_q[u,x_1,\dots,x_D,a_0,\dots,a_D]$, а значит 
\[
a_0^m p=B\cdot r(B(x,a),x_1,\dots,x_D,a_0,\dots,a_D).
\]
Поскольку $B$ неприводим и $B\nmid a_0^m$, то $B \mid p$,
что и требовалось доказать.
\end{proof}


\begin{lemma}\label{lemma:im-sigma}
Если $p \in P_{m}$, то $\sigma(p) \in \mathcal{C}$, где $0 \leq m \leq q - 1$.
\end{lemma}
\begin{proof} 
Напомним, что код $\mathcal{C}$ определялся как множество функций  \(c: E \to F_q\), для которых для каждой точки \(\alpha \in \PP_q^D\) существуют однородные полиномы \(f_\alpha\) и \(f^\alpha\) степени \(m\) от $D+1$ переменной,
  такие что \(f_\alpha(\beta)=c(\alpha,\beta)=f^\beta(\alpha)\) для всех $(\alpha,\beta)\in E$, то есть удовлетворяющих условию \(\langle \alpha,\beta\rangle = 0\).

Для произвольного \(\alpha \in \PP_q^D\) определим функции $f_\alpha\in \mathbb{F}_q[a_0,\dots,a_D]$, $f^\alpha\in \F_q[x_0,\dots,x_D]$:
\[
f_\alpha(a) := p(\alpha,a),\qquad f^\alpha(x) := p(x,\alpha).
\]
Тогда для всех \(\alpha,\beta\in \PP_q^D\), таких что \(\langle \alpha,\beta \rangle = 0\) верно:
\[
\sigma(p)(\alpha,\beta) = f_\alpha(\beta)=f^\beta(\alpha).
\]
Кроме того, поскольку \(p\) однороден по группам переменных \(a\) и \(x\) и имеет степень \(m\) по каждой из групп, то \(f_\alpha\) и \(f^\alpha\) также являются однородными полиномами степени \(m\).
Таким образом, отображение \(\sigma(p)\) удовлетворяет обоим условиям определения кода \(\mathcal{C}\) и, следовательно,
\[
\sigma(p) \in \mathcal{C},
\]что и требовалось доказать.
\end{proof}

\Dimension*

\begin{proof}
Оценим размерность пространства полиномов \(P_{m}\). Базисом линейного пространства полиномов над $\F_q$ является множество мономов 
\[
    \Bigl\{\prod_{s=0}^Da_s^{i_s}x_s^{j_s}\ \Bigm|\  \sum_{s=0}^D i_s=\sum_{s=0}^D j_s = m\Bigr\}.
\]
Есть $\binom{m+D}{D}$ способов разбить число $m$ в сумму $D+1$ целых неотрицательных слагаемых, а значит мощность базиса и размерность пространства $P_m$ равны
\[
\dim P_m = \binom{m+D}{D}^2.
\]
\newcommand{\im}{\mathop{\mathrm{Im}}}
По лемме \ref{lemma:ker-sigma} выполнено \(\ker\sigma = B\cdot P_{m-1}\), значит
\begin{align*}
\dim \im\sigma &= \dim P_{m} - \dim \ker \sigma =\\
&=\dim P_{m} - \dim P_{m-1} = \\
&= \binom{m+D}{D}^2-\binom{m-1+D}{D}^2.
\end{align*}
Учитывая, что $\binom{m+D}{D}=\frac{m+D}{D}\binom{m+D-1}{D-1}$, $\binom{m+D-1}{D}=\frac{m}{D}\binom{m+D-1}{D-1}$, имеем
\begin{align*}
\dim \im\sigma &= \left(\left(\frac{m+D}{D}\right)^2-\left(\frac{m}{D}\right)^2\right)\binom{m+D-1}{D-1}^2=\\
&=\frac{m^2+2mD+D^2 - m^2}{D^2}\binom{m+D-1}{D-1}^2 =\\
&= \frac{2m+D}{D}\binom{m+D-1}{D-1}^2.
\end{align*}

По лемме \ref{lemma:im-sigma} выполнено $\sigma(P_{m})\subseteq \mathcal{C}_{D,q,m}$, значит \[
\dim \mathcal{C}_{D,q,m}\ge \dim\im\sigma\ge \frac{2m+D}{D}\binom{m+D-1}{D-1}^2.\qedhere
\]
\end{proof}

\subsection{\texorpdfstring{Симметрия кода $\mathcal{C}_{D,q,m}$}{Симметрия кода CD,q,m}}\label{sec:symmetry}

\begin{definition}
\emph{Изометрией} двух линейных кодов \(\mathcal{C}\) и \(\mathcal{C'}\subseteq\mathbb{F}_q^n\) называется биективное линейное отображение:  
\[
\psi\colon \mathbb{F}_q^n \;\to\; \mathbb{F}_q^n,
\]
переводящее \(\mathcal{C}\) в \(\mathcal{C'}\) и при этом сохраняющее вес Хэмминга любого вектора. 
\end{definition}

\begin{definition}
\emph{Автоморфизмом} линейного кода \(\mathcal{C}\subseteq\mathbb{F}_q^n\) называется частный случай изометрии, когда \(\mathcal{C'}=\mathcal{C}\). 
\end{definition}
Можно показать, что это линейное отображение вида: 
\[
\varphi\colon \mathbb{F}_q^n \;\to\; \mathbb{F}_q^n,
\]
переводящее \(\mathcal{C}\) в себя (например, перестановка координат с возможным домножением на ненулевые константы) и сохраняющее вес Хэмминга, а значит и минимальное расстояние кода.  


Напомним, что $\Gamma_{D,q}=(\PP_q^D,\PP_q^D,E)$ --- двудольный граф с множеством рёбер
\[
    E=\{(\alpha,\beta)\in \PP_q^D\times \PP_q^D\mid  \langle\alpha,\beta\rangle=0\}.
\]
Код $\mathcal{C} \subseteq \mathbb{F}_q^E$ понимается как некоторое линейное множество функций $c:E\to \mathbb{F}_q$. 

Каждая невырожденная матрица $A\in \GL(D+1,q)$ определяет
проективное преобразование
\(
   \alpha\mapsto \widehat{A\alpha} 
\)
и
\(
   \beta\mapsto \widehat{A^*\beta}
\), где $A^*=(A^T)^{-1}$, $\alpha\in \PP_q^D$, $\beta\in \PP_q^D$. Введём отображения 
\begin{align*}
    \phi_A&: (\alpha,\beta)\mapsto (A\alpha, A^*\beta)\\
    \hat\phi_A&: (\alpha,\beta)\mapsto (\widehat{A\alpha}, \widehat{A^*\beta}).
\end{align*}
Для любых $(\alpha,\beta)\in E$ выполнено
\[
   \langle A\alpha, A^*\beta\rangle=(A\alpha)^T((A^T)^{-1}\beta)=\alpha^TA^T(A^T)^{-1}\beta=\alpha^T\beta=\langle\alpha,\beta\rangle=0,
\]
а значит и $\langle \widehat{A\alpha}, \widehat{A^*\beta}\rangle=0$, то есть $\hat\phi_A(\alpha,\beta)\in E$. Таким образом, $\hat\phi_A$ задаёт автоморфизм графа $\Gamma_{D,q}$.

Покажем, что любое такое преобразование задаёт некоторый автоморфизм кода $\cC_{D,q,m}$.

\Symmetry*

\begin{proof}
Для вектора $\alpha\in \F_q^{D+1}\setminus\{0\}$ определим величину $\kappa(\alpha)$, равную первой ненулевой координате в векторе $\alpha$. Тогда $\alpha = \kappa(\alpha)\hat\alpha$.

Для каждой пары $(\alpha,\beta)\in E$ положим \[
    a_{(\alpha,\beta)}:=\bigl(\kappa(A\alpha)\cdot \kappa(A^*\beta)\bigr)^m.
\]

Зафиксируем кодовое слово $c\in\cC$ и определим $c'$ как в условии теоремы:
\[
    c'(\alpha,\beta):= a_{(\alpha,\beta)}c\bigl(\widehat{A\alpha},\widehat{A^*\beta}\bigr)\qquad\mbox{для всех } (\alpha,\beta)\in E.
\]
Покажем, что $c'\in \cC$.
Рассмотрим проекции $f'_\alpha$ (соотв., $f'^\alpha$) функции $c'$ на окрестности вершин $\alpha$ левой (соотв., правой) доли графа $\Gamma_{D,q}$, тогда  
\[
    f'_{\alpha}(\beta) = c'(\alpha, \beta) = f'^{\beta}(\alpha)\qquad\mbox{для всех } (\alpha,\beta)\in E.
\]
Убедимся, что для всех $\alpha\in \PP_q^D$ функции $f'_{\alpha}$ и $f'^{\alpha}$ являются кодовыми словами локальных кодов, то есть задаются однородными полиномами степени $m$. Зафиксируем произвольное $\alpha\in \PP_q^D$, тогда для всех $\beta$ таких, что $\langle\alpha,\beta\rangle=0$, выполнено
\[
f'_{\alpha}(\beta) = c'(\alpha,\beta)
=a_{(\alpha,\beta)}\,c(\widehat{A\alpha}, \widehat{A^*\beta})
=\kappa(A\alpha)^m\cdot \kappa(A^*\beta)^m\cdot f_{\widehat{A\alpha}}(\widehat{A^*\beta}).
\]
Поскольку $c\in \cC$, то $f_{\widehat{A\alpha}}$ --- однородный полином степени $m$, значит
\[
    \kappa(A^*\beta)^m\cdot f_{\widehat{A\alpha}}(\widehat{A^*\beta})
    =f_{\widehat{A\alpha}}(\underbrace{\kappa(A^*\beta)\cdot\widehat{A^*\beta}}_{A^*\beta})
    =f_{\widehat{A\alpha}}(A^*\beta).
\]
Поскольку преобразование $x\mapsto A^*x$ задаёт линейную подстановку, то 
\[
    \deg f'_{\alpha}=\deg f_{\widehat{A\alpha}}(A^*x)=\deg f_{\widehat{A\alpha}}=m.
\]
Аналогично для фиксированного $\beta\in \PP_q^D$ и всех $\alpha\in \PP_q^D$ таких, что $\langle\alpha,\beta\rangle=0$, получим
\[
f'^{\beta}(\alpha)
= c'(\alpha,\beta)
= a_{(\alpha,\beta)}\,c\bigl(\widehat{A\alpha},\widehat{A^*\beta}\bigr)
= \kappa(A\alpha)^m\cdot \kappa(A^*\beta)^m\cdot f^{\widehat{A^*\beta}}\bigl(\widehat{A\alpha}\bigr).
\]
Поскольку \(f^{\widehat{A^*\beta}}\) является также однородным полиномом степени \(m\), то
\[
\kappa(A\alpha)^m\cdot f^{\widehat{A^*\beta}}\bigl(\widehat{A\alpha}\bigr)
= f^{\widehat{A^*\beta}}\bigl(\underbrace{\kappa(A\alpha)\cdot\widehat{A\alpha}}_{A\alpha}\bigr)
= f^{\widehat{A^*\beta}}(A\alpha).
\]
В силу линейности преобразования $x\mapsto Ax$ имеем
\[
\deg f'^{\beta}
= \deg f^{\widehat{A^*\beta}}(Ax)
= \deg f^{\widehat{A^*\beta}}
= m.
\]
Это означает, что $c'$ удовлетворяет всем локальным ограничениям кода $\mathcal{C}$, значит $c'\in \mathcal{C}$.
\end{proof}

\section{Заключение}\label{sec:conclusion}
В настоящей работе была рассмотрена конструкция кодов Таннера на графе инцидентности точек и гиперплоскостей \(D\)-мерного проективного пространства \(\PP^D(\F_q)\), где 
в роли локальных проверок --- проективные коды Рида–Маллера. Получены нижние оценки на минимальное расстояние таких кодов и их размерности, а также сформулирована гипотеза для более широкого диапазона параметров на основе результатов численного эксперимента.

Также было показано, что описанные коды инвариантны при действии группы \(\mathrm{PGL}(D+1,\F_q)\), что позволит использовать их как локальные коды при построении кодов с высокой симметрией на комплексах Рамануджана. 


\begin{thebibliographyRU}{17}

\Bibitem{Lubotzky}
\by A. Lubotzky
\paper High dimensional expanders
\inbook Proceedings of the International Congress of Mathematicians (ICM 2018, Rio de Janeiro)
\vol 2
\publ World Scientific
\yr 2019
\pages 705--730
\crossref{https://doi.org/10.1142/9789813272880_0027}

\RBibitem{kalachev2023}
\by Г. В. Калачев, П. А. Пантелеев
\paper Семейство асимптотически хороших квантовых и локально тестируемых классических LDPC-кодов
\inbook Математические вопросы кибернетики
\issueinfo Вып 21
\publ ФИЗМАТЛИТ
\publaddr М
\yr 2023
\pages 111--155
\crossref{https://doi.org/10.20948/mvk-2023-111}

\Bibitem{Pinero2015}
\by F. Pi{\~n}ero
\thesis An algebraic approach to graph codes
\thesisinfo PhD thesis, Technical University of Denmark
\yr 2015

\Bibitem{BeelenHoholdtPineroJustesen2013}
\by P. Beelen, T. H{\o}holdt, F. Pi{\~n}ero, J. Justesen
\paper On the Dimension of Graph Codes with Reed--Solomon Component Codes
\inbook 2013 IEEE International Symposium on Information Theory Proceedings
\publ IEEE
\yr 2013
\pages 1227--1231
\crossref{https://doi.org/10.1109/ISIT.2013.6620422}

\Bibitem{HoholdtJustesen2006}
\by T. H{\o}holdt, J. Justesen
\paper Graph codes with Reed--Solomon component codes
\inbook 2006 IEEE International Symposium on Information Theory
\publ IEEE
\yr 2006
\pages 2022--2026
\crossref{https://doi.org/10.1109/ISIT.2006.261904}

\Bibitem{JanwaLal2003}
\by H. Janwa, A. K. Lal
\paper On Tanner Codes: Minimum Distance and Decoding
\jour Applicable Algebra in Engineering, Communication and Computing
\yr 2003
\vol 13
\pages 335--347
\crossref{https://doi.org/10.1007/s00200-003-0098-4}

\Bibitem{HoholdtJustesen2011}
\by T. H{\o}holdt, J. Justesen
\paper The Minimum Distance of Graph Codes
\inbook Coding and Cryptology (IWCC 2011)
\serial Lecture Notes in Computer Science
\vol 6639
\publ Springer
\yr 2011
\pages 201--212
\crossref{https://doi.org/10.1007/978-3-642-20901-7_12}

\Bibitem{DinurHDE}
\by I. Dinur, S. Liu, R. Y. Zhang
\paper New codes on high dimensional expanders
\inbook 40th Computational Complexity Conference (CCC 2025)
\serial Leibniz International Proceedings in Informatics
\vol 339
\publ Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik
\yr 2025
\pages 27:1--27:42
\crossref{https://doi.org/10.4230/LIPIcs.CCC.2025.27}

\Bibitem{RodierFlagVarieties}
\by F. Rodier
\paper Codes from flag varieties over a finite field
\jour Journal of Pure and Applied Algebra
\yr 2003
\vol 178
\issue 2
\pages 203--214
\crossref{https://doi.org/10.1016/S0022-4049(02)00188-3}

\RBibitem{gashkov2009}
\by С. Б. Гашков
\paper Графы расширители и их применения в теории кодирования
\jour Математическое просвещение
\yr 2009
\issue 13
\pages 104--126

\RBibitem{Chashkin}
\by А. В. Чашкин
\book Лекции по дискретной математике
\publ Физматлит
\publaddr М
\yr 2007
\totalpages 416

\Bibitem{Tanner1981}
\by R. Tanner
\paper A recursive approach to low complexity codes
\jour IEEE Transactions on Information Theory
\yr 1981
\vol 27
\issue 5
\pages 533--547
\crossref{https://doi.org/10.1109/TIT.1981.1056404}

\RBibitem{graph_theory}
\by В. А. Емельичев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич
\book Лекции по теории графов
\publ Наука
\publaddr М
\yr 1990
\totalpages 384

\Bibitem{Sorensen1991}
\by A. B. Sorensen
\paper Projective Reed--Muller Codes
\jour IEEE Transactions on Information Theory
\yr 1991
\vol 37
\issue 6
\pages 1567--1576
\crossref{https://doi.org/10.1109/18.104317}

\Bibitem{ExpandersIT}
\by M. Sipser, D. A. Spielman
\paper Expander codes
\jour IEEE Transactions on Information Theory
\yr 1996
\vol 42
\issue 6
\pages 1710--1722
\crossref{https://doi.org/10.1109/18.556667}

\Bibitem{Alon_Chung}
\by N. Alon, F. R. K. Chung
\paper Explicit construction of linear sized tolerant networks
\jour Discrete Mathematics
\yr 1988
\vol 72
\pages 15--19
\crossref{https://doi.org/10.1016/0012-365X(88)90189-6}

\RBibitem{Ramanujan_graph_about}
\by O. Parzanchevski
\paper Ramanujan graphs and digraphs
\inbook Analysis and Geometry on Graphs and Manifolds
\serial London Mathematical Society Lecture Note Series
\vol 461
\yr 2020
\pages 344--367
\crossref{https://doi.org/10.1017/9781108615259.014}

\end{thebibliographyRU}

\begin{thebibliographyEN}{17}

\Bibitem{Lubotzky}
\by A. Lubotzky
\paper High dimensional expanders
\inbook Proceedings of the International Congress of Mathematicians (ICM 2018, Rio de Janeiro)
\vol 2
\publ World Scientific
\yr 2019
\pages 705--730
\crossref{https://doi.org/10.1142/9789813272880_0027}

\Bibitem{kalachev2023}
\by G. V. Kalachev, P. A. Panteleev
\paper A family of asymptotically good quantum and locally testable classical LDPC codes
\inbook Matematicheskie voprosy kibernetiki
\issueinfo Issue 21
\publ FIZMATLIT
\publaddr M
\yr 2023
\pages 111--155
\lang in Russian
\crossref{https://doi.org/10.20948/mvk-2023-111}

\Bibitem{Pinero2015}
\by F. Pi{\~n}ero
\thesis An algebraic approach to graph codes
\thesisinfo PhD thesis, Technical University of Denmark
\yr 2015

\Bibitem{BeelenHoholdtPineroJustesen2013}
\by P. Beelen, T. H{\o}holdt, F. Pi{\~n}ero, J. Justesen
\paper On the Dimension of Graph Codes with Reed--Solomon Component Codes
\inbook 2013 IEEE International Symposium on Information Theory Proceedings
\publ IEEE
\yr 2013
\pages 1227--1231
\crossref{https://doi.org/10.1109/ISIT.2013.6620422}

\Bibitem{HoholdtJustesen2006}
\by T. H{\o}holdt, J. Justesen
\paper Graph codes with Reed--Solomon component codes
\inbook 2006 IEEE International Symposium on Information Theory
\publ IEEE
\yr 2006
\pages 2022--2026
\crossref{https://doi.org/10.1109/ISIT.2006.261904}

\Bibitem{JanwaLal2003}
\by H. Janwa, A. K. Lal
\paper On Tanner Codes: Minimum Distance and Decoding
\jour Applicable Algebra in Engineering, Communication and Computing
\yr 2003
\vol 13
\pages 335--347
\crossref{https://doi.org/10.1007/s00200-003-0098-4}

\Bibitem{HoholdtJustesen2011}
\by T. H{\o}holdt, J. Justesen
\paper The Minimum Distance of Graph Codes
\inbook Coding and Cryptology (IWCC 2011)
\serial Lecture Notes in Computer Science
\vol 6639
\publ Springer
\yr 2011
\pages 201--212
\crossref{https://doi.org/10.1007/978-3-642-20901-7_12}

\Bibitem{DinurHDE}
\by I. Dinur, S. Liu, R. Y. Zhang
\paper New codes on high dimensional expanders
\inbook 40th Computational Complexity Conference (CCC 2025)
\serial Leibniz International Proceedings in Informatics
\vol 339
\publ Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik
\yr 2025
\pages 27:1--27:42
\crossref{https://doi.org/10.4230/LIPIcs.CCC.2025.27}

\Bibitem{RodierFlagVarieties}
\by F. Rodier
\paper Codes from flag varieties over a finite field
\jour Journal of Pure and Applied Algebra
\yr 2003
\vol 178
\issue 2
\pages 203--214
\crossref{https://doi.org/10.1016/S0022-4049(02)00188-3}

\Bibitem{gashkov2009}
\by S. B. Gashkov
\paper Expander graphs and their applications in coding theory
\jour Matematicheskoe prosveshchenie
\yr 2009
\issue 13
\pages 104--126
\lang in Russian

\Bibitem{Chashkin}
\by A. V. Chashkin
\book Lektsii po diskretnoi matematike
\publ Fizmatlit
\publaddr M
\yr 2007
\totalpages 416
\lang in Russian

\Bibitem{Tanner1981}
\by R. Tanner
\paper A recursive approach to low complexity codes
\jour IEEE Transactions on Information Theory
\yr 1981
\vol 27
\issue 5
\pages 533--547
\crossref{https://doi.org/10.1109/TIT.1981.1056404}

\Bibitem{graph_theory}
\by V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich
\book Lektsii po teorii grafov
\publ Nauka
\publaddr M
\yr 1990
\totalpages 384
\lang in Russian

\Bibitem{Sorensen1991}
\by A. B. Sorensen
\paper Projective Reed--Muller Codes
\jour IEEE Transactions on Information Theory
\yr 1991
\vol 37
\issue 6
\pages 1567--1576
\crossref{https://doi.org/10.1109/18.104317}

\Bibitem{ExpandersIT}
\by M. Sipser, D. A. Spielman
\paper Expander codes
\jour IEEE Transactions on Information Theory
\yr 1996
\vol 42
\issue 6
\pages 1710--1722
\crossref{https://doi.org/10.1109/18.556667}

\Bibitem{Alon_Chung}
\by N. Alon, F. R. K. Chung
\paper Explicit construction of linear sized tolerant networks
\jour Discrete Mathematics
\yr 1988
\vol 72
\pages 15--19
\crossref{https://doi.org/10.1016/0012-365X(88)90189-6}

\Bibitem{Ramanujan_graph_about}
\by O. Parzanchevski
\paper Ramanujan graphs and digraphs
\inbook Analysis and Geometry on Graphs and Manifolds
\serial London Mathematical Society Lecture Note Series
\vol 461
\yr 2020
\pages 344--367
\crossref{https://doi.org/10.1017/9781108615259.014}

\end{thebibliographyEN}

\appendix
\section{Численный эксперимент}\label{sec:numeric-results}
В данном разделе приведены результаты вычисления размерности кода \(\mathcal{C}_{2,q,m}\). 

Исходный код, который использовался в данном эксперименте, доступен по ссылке: \url{https://github.com/Alinemsu/Tanner_matrix}


Результаты подсчёта характеристик проверочных матриц и параметров кода $\cC_{2,q,m}$ для $q\in\{2,3,4,5,7,8,9,11\}$ приведены в таблице ниже.

\pagebreak[4]
% q=2
\begin{longtable}{|c|c||c|c|c|c|}
\hline
\ $q\ $ & $m$ & Ранг & Размерность & Высота & Ширина \\
\hline
2 & 0 & 20 & 1 & 28 & 21 \\
2 & 1 & 13 & 8 & 14 & 21 \\

% % q=3
\hline
3 & 0 & 51 & 1 & 78 & 52 \\
3 & 1 & 44 & 8 & 52 & 52 \\
3 & 2 & 25 & 27 & 26 & 52 \\

% % q=4
\hline
4 & 0 & 104 & 1 & 168 & 105 \\
4 & 1 & 97 & 8 & 126 & 105 \\
4 & 2 & 76 & 29 & 84 & 105 \\
4 & 3 & 41 & 64 & 42 & 105 \\

% % q=5
\hline
5 & 0 & 185 & 1 & 310 & 186 \\
5 & 1 & 178 & 8 & 248 & 186 \\
5 & 2 & 159 & 27 & 186 & 186 \\
5 & 3 & 116 & 70 & 124 & 186 \\
5 & 4 & 61 & 125 & 62 & 186 \\

% % q=7
\hline
7 & 0 & 455 & 1 & 798 & 456 \\
7 & 1 & 448 & 8 & 684 & 456 \\
7 & 2 & 429 & 27 & 570 & 456 \\
7 & 3 & 392 & 64 & 456 & 456 \\
7 & 4 & 315 & 141 & 342 & 456 \\
7 & 5 & 220 & 236 & 228 & 456 \\
7 & 6 & 113 & 343 & 114 & 456 \\

% % q=8
\hline
8 & 0 & 656 & 1 & 1168 & 657 \\
8 & 1 & 649 & 8 & 1022 & 657 \\
8 & 2 & 630 & 27 & 876 & 657 \\
8 & 3 & 593 & 64 & 730 & 657 \\
8 & 4 & 520 & 137 & 584 & 657 \\
8 & 5 & 411 & 246 & 438 & 657 \\
8 & 6 & 284 & 373 & 292 & 657 \\
8 & 7 & 145 & 512 & 146 & 657 \\

% q=9
\hline
9 & 0 & 909 & 1 & 1638 & 910 \\
9 & 1 & 902 & 8 & 1456 & 910 \\
9 & 2 & 883 & 27 & 1274 & 910 \\
9 & 3 & 846 & 64 & 1092 & 910 \\
9 & 4 & 779 & \bf 131 & 910 & 910 \\
9 & 5 & 664 & 246 & 728 & 910 \\
9 & 6 & 519 & 391 & 546 & 910 \\
9 & 7 & 356 & 554 & 364 & 910 \\
9 & 8 & 181 & 729 & 182 & 910 \\

% q=11
\hline
11 & 0 & 1595 & 1 & 2926 & 1596 \\
11 & 1 & 1588 & 8 & 2660 & 1596 \\
11 & 2 & 1569 & 27 & 2394 & 1596 \\
11 & 3 & 1532 & 64 & 2128 & 1596 \\
11 & 4 & 1471 & 125 & 1862 & 1596 \\
11 & 5 & 1380 & 216 & 1596 & 1596 \\
11 & 6 & 1205 & 391 & 1330 & 1596 \\
11 & 7 & 1000 & 596 & 1064 & 1596 \\
11 & 8 & 771 & 825 & 798 & 1596 \\
11 & 9 & 524 & 1072 & 532 & 1596 \\
11 & 10 & 265 & 1331 & 266 & 1596 \\
\hline
\end{longtable}

\end{document}