Точки сетки в решеточных кубах

Введение

Рассмотрим решётчатый куб (lattice cube) – это правильный куб в трёхмерном пространстве $\mathbb{R}^3$, все вершины которого имеют целочисленные координаты. Иными словами, 8 вершин куба лежат в узлах целочисленной решётки $\mathbb{Z}^3$. Такая геометрическая фигура обладает примечательными арифметическими свойствами, связывающими геометрию с теорией чисел. Основная задача, которую мы обсуждаем, – это подсчёт значения $S(n)$, определённого как сумма количества решётчатых точек (то есть точек с целочисленными координатами), содержащихся во всех различных трёхмерных решётчатых кубах, координаты всех вершин которых лежат в диапазоне от $0$ до $n$ включительно.

Формально, пусть $C(n)$ обозначает число различных решётчатых кубов, все вершины которых имеют координаты в диапазоне $0\le x,y,z\le n$. Под “различными” мы будем понимать не совпадающие по множеству координат вершин кубы (каждый куб определяется совокупностью координат своих 8 вершин). Тогда $S(n)$ можно записать как

$$ S(n) \;=\; \sum_{K} |K\cap\mathbb{Z}^3|, $$

где сумма берётся по всем таким кубам $K$ (с вершинами в $[0,n]^3$), а $|K\cap\mathbb{Z}^3|$ – число решётчатых точек внутри куба $K$ (включая точки на границе куба). Задача вычисления $S(n)$ требует учёта всех возможных ориентаций решётчатых кубов и подсчёта точек решётки внутри них. Для небольших $n$ можно напрямую перебрать все кубы, однако при росте $n$ задача быстро становится нетривиальной из-за стремительного увеличения числа возможных кубов. Например, $C(1)=1$, $C(2)=9$, $C(4)=100$, $C(5)=229$, $C(10)=4469$ и $C(50)=8154671$ различных кубов, а соответствующие значения $S(n)$ равны $S(1)=8$, $S(2)=91$, $S(4)=1878$, $S(5)=5832$, $S(10)=387003$, $S(50)=29948928129$. Видно, что разные кубы (даже с одинаковой длиной ребра) могут содержать различное количество решётчатых точек. Например, куб со сторонами, выровненными по осям координат, длиной $3$ (координаты вершин $(0,0,0)$, $(3,0,0)$, $(0,3,0)$, $(0,0,3)$ и т.д.) содержит $(3+1)^3=64$ решётчатых точки (8 вершин, 56 других точек на поверхности и 8 внутренних точек). В то же время куб с той же длиной ребра $3$, но повернутый относительно осей (например, с вершинами $(0,2,2)$, $(1,4,4)$, $(2,0,3)$, $(2,3,0)$, $(3,2,5)$, $(3,5,2)$, $(4,1,1)$, $(5,3,3)$) содержит лишь $40$ решётчатых точек (20 на поверхности и 20 внутри). Таким образом, ориентация куба относительно решётки существенно влияет на количество решётчатых точек внутри него, и для вычисления $S(n)$ необходимо учитывать все возможные ориентации.

В данном тексте я попробую дать академическое изложение данной проблемы. Сначала формально определим ключевые понятия: что такое решётчатый куб, примитивный (неприводимый) куб и ортонормированный базис (orthonormal basis) в $\mathbb{Z}^3$. Затем обсудим связь между целочисленными ортонормированными базисами и существованием решётчатых кубов, используя аппарат кватернионов (quaternions) и ортогональных матриц. Сформулируем основные теоремы о свойствах решётчатых кубов – в частности, о целочисленности длины их рёбер, о классификации кубов на эквивалентные классы по ориентации, а также теорему об Эрхартовском многочлене (Ehrhart polynomial), описывающем зависимость числа решётчатых точек внутри куба от масштаба. В настоящем изложении ключевыми являются следующие теоретические источники. В работе Ионаску и Маркова предложена конструкция решётчатых кубов с помощью ортогональных матриц и кватернионной параметризации, лежащая в основе всей геометрической части. Теорема Пала позволяет строго описать орбиты эквивалентных ориентаций посредством арифметики кватернионов. Классическое тождество Эйлера о произведении сумм четырёх квадратов используется при анализе структуры параметров и построении примитивных кубов. По ходу изложения дам подробные доказательства основных фактов, включая доказательства свойств решётчатых кубов и параметризации всех таких кубов с помощью кватернионов. Выведем необходимые формулы (формулу Эрхарта для числа точек внутри куба, формулы для подсчёта кубов через представления чисел четырьмя квадратами, и т.д.), а также обсудим сложность перебора всех кубов и структуру решения задачи $S(n)$.

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

Определения и предварительные сведения

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

Решётчатый куб.

Решётчатым кубом называется куб (в смысле правильного многогранника в $\mathbb{R}^3$ с 6 квадратными гранями), все вершины которого имеют целочисленные координаты. Эквивалентно, решётчатый куб – это образ единичного куба с ребром длины $1$ при некотором ортогональном преобразовании и целочисленном сдвиге, так что образ снова совпадает с подмножеством решётки $\mathbb{Z}^3$. Если $K$ – решётчатый куб, то существуют восемь точек $(x_i,y_i,z_i)\in\mathbb{Z}^3$ ($i=1,\dots,8$), являющиеся его вершинами, причём эти точки образуют геометрическую форму куба.

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

$$ \mathbf{v}_1 = (a_1,a_2,a_3), \quad \mathbf{v}_2 = (b_1,b_2,b_3), \quad \mathbf{v}_3 = (c_1,c_2,c_3), $$

где $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3\in\mathbb{Z}^3$. Эти векторы являются рёбрами куба (отрезками между парами вершин). Для куба они должны удовлетворять следующим условиям:

1. $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3$ ортогональны друг другу (перпендикулярны попарно): $\mathbf{v}_i\cdot \mathbf{v}_j = 0$ для $i\neq j$. Здесь $\mathbf{v}_i\cdot \mathbf{v}_j$ – скалярное произведение векторов.

2. Они имеют равную длину: $||\mathbf{v}_1|| = ||\mathbf{v}_2|| = ||\mathbf{v}_3||$, где $||\mathbf{v}||$ – обычная евклидова норма (длина) вектора. Обозначим через $\ell$ общую длину ребра куба. Поскольку $\mathbf{v}_i$ имеют целые координаты, длина $\ell$ выражается как $\ell = \sqrt{L}$, где

$$ L = ||\mathbf{v}_i||^2 = a_1^2+a_2^2+a_3^2 = b_1^2+b_2^2+b_3^2 = c_1^2+c_2^2+c_3^2 $$

— целое число, являющееся суммой трёх квадратов целых чисел.

Пусть заданы такие три вектора $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3\in\mathbb{Z}^3$, удовлетворяющие (1) и (2). Тогда множество из восьми точек

$$ \{\mathbf{0},\ \mathbf{v}_1,\ \mathbf{v}_2,\ \mathbf{v}_3,\ \mathbf{v}_1+\mathbf{v}_2,\ \mathbf{v}_1+\mathbf{v}_3,\ \mathbf{v}_2+\mathbf{v}_3,\ \mathbf{v}_1+\mathbf{v}_2+\mathbf{v}_3 \} $$

является совокупностью вершин решётчатого куба (после переноса так, чтобы $\mathbf{0}$ совпала с некоторой требуемой точкой решётки). В частности, указанные условия (ортогональность и равенство длины рёбер) являются не только необходимыми, но и достаточными для того, чтобы параллелепипед, построенный на $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3$, оказался правильным кубом. Таким образом, изучение решётчатых кубов сводится к поиску целочисленных ортонормированных троек векторов.

Ортонормированный базис

В стандартном евклидовом пространстве $\mathbb{R}^3$ ортонормированным базисом называют тройку попарно перпендикулярных единичных векторов. Нас будет интересовать понятие целочисленного ортонормированного базиса: это тройка векторов $(\mathbf{e}_1,\mathbf{e}_2,\mathbf{e}_3)$ из $\mathbb{Z}^3$ такая, что они ортогональны друг другу и имеют одинаковую длину (необязательно $1$, но все равны по длине). Строго говоря, такая тройка не может состоять из единичных векторов (кроме тривиального случая стандартного базиса $(1,0,0)$, $(0,1,0)$, $(0,0,1)$, который задаёт вырожденный случай ребра длины $1$). Поэтому обычно будем говорить о целочисленном ортогональном базисе равной длины: $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3\in\mathbb{Z}^3$, где $\mathbf{v}_i\cdot \mathbf{v}_j=0$ при $i\neq j$ и $||\mathbf{v}_1||=||\mathbf{v}_2||=||\mathbf{v}_3||=\sqrt{L}$ для некоторого целого $L$. Отметим, что наличие такой тройки векторов эквивалентно существованию решётчатого куба: если $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3$ удовлетворяют этим условиям, то они как раз и образуют рёбра решётчатого куба с длиной ребра $\ell=\sqrt{L}$, как описано выше.

Примитивный (неприводимый) куб

В дальнейшем под примитивным кубом (иногда говорят неприводимый куб) будем понимать решётчатый куб, который не является масштабным увеличением меньшего решётчатого куба. Формально: решётчатый куб называется примитивным, если его рёбра заданы примитивными целочисленными векторами, то есть координаты каждого ребра $(a_1,a_2,a_3)$ не имеют общего нетривиального делителя кроме $\pm 1$. Эквивалентно, примитивный куб не может быть получен из другого решётчатого куба меньшего размера путём гомотетии с целым коэффициентом $m>1$. Если же куб можно представить как масштабирование на $m$ некоего меньшего решётчатого куба, то такой куб является $m$-кратным (по масштабу) и его называем кратным или произведённым масштабированием от более простого куба. Например, куб с рёбрами длины $2$ по координатным осям не примитивен, так как это масштабирование на $2$ единичного куба.

Для дальнейшего важно отметить, что любой решётчатый куб может быть представлен как масштабирование примитивного. Действительно, если куб имеет ребро длины $\ell=\sqrt{L}$, то все координаты его образующих векторов имеют общий делитель $d=\gcd(a_1,a_2,a_3,\dots,c_3)$ . Тогда, вынеся $d$, мы представляем $\mathbf{v}_i = d,\mathbf{u}_i$, где $\mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3$ – целочисленные векторы, удовлетворяющие ортогональности и равной длине, причём $\mathbf{u}_i$ уже примитивны (не имеют общего делителя >1). Эти $\mathbf{u}_i$ задают примитивный решётчатый куб (неприводимый), а исходный куб получается из него масштабированием в $d$ раз. Таким образом, классификация решётчатых кубов сводится к классификации примитивных кубов, а затем учёту всех целочисленных масштабирований.

Стоит сразу отметить пару важных ограничений на сторону примитивного куба:

• Целочисленность квадрата длины ребра. Если существует решётчатый куб с длиной ребра $\ell$, то $\ell^2$ обязано быть целым числом. Это очевидно из того, что $\ell^2=||\mathbf{v}||^2$ для любого ребра $\mathbf{v}\in\mathbb{Z}^3$. Таким образом, длина ребра решётчатого куба имеет вид $\ell=\sqrt{L}$, где $L\in\mathbb{N}$.
• Примитивные кубы имеют нечётную сторону. Менее очевидным фактом является то, что если куб примитивен и $\ell^2=L$, то $L$ должно быть нечётным числом. Эквивалентно, $\ell^2$ не делится на $2$. Другими словами, все неприводимые решётчатые кубы имеют нечётную длину ребра (в единицах длины решётки). Например, первые неприводимые кубы имеют сторону $\ell=1,3,5,7,9,11,\dots$ (то есть $\ell=1$ – тривиальный единичный куб, $\ell=3$ – первый нетривиальный повёрнутый куб, $\ell=5$ – следующий, и т.д.). Если сторона куба чётная (например, $2,4,6,\dots$), то соответствующий куб обязательно оказывается кратным (масштабированным) вариантом куба с меньшей стороной. В частности, куб со стороной $2$ – это масштабирование единичного, со стороной $4$ – масштабирование куба со стороной $2$ (а значит дважды масштабирование единичного), и т.д. Это утверждение будем обосновывать позднее.

Ортогональные матрицы и параметризация кубов

Для удобства описания ориентации куба введём язык ортогональных матриц. Напоминаю, что Ортогональная матрица — это матрица $Q \in \operatorname{Mat}_{3 \times 3}(\mathbb{R})$, столбцы (и строки) которой образуют ортонормированный базис в $\mathbb{R}^3$. Эквивалентно, $Q$ удовлетворяет $Q^T Q = E$, где $E$ – единичная матрица. Если к тому же $\det Q = 1$, то есть определитель матрицы $Q$.} (это номер сноски, не квадрат), то $Q$ является специальной ортогональной матрицей (элементом группы вращений $\mathrm{SO}(3)$), но в нашем контексте отражения также можно допускать, поэтому требование $\det=1$ несущественно. Координаты вершины решётчатого куба можно получить из координат вершин некоторого эталонного куба с помощью ортогонального преобразования. Например, если взять единичный куб $[0,1]^3$ (ось-ориентированный), то поворот или зеркальное отражение, заданное ортогональной матрицей $Q$, переместит вершины этого куба в новое положение. При этом, если $Q$ имеет рациональные элементы, то после масштабирования на некоторый знаменатель мы получим положения вершин с целыми координатами. Этот принцип лежит в основе общего описания всех решётчатых кубов: любой решётчатый куб можно отождествить с ортогональной матрицей с рациональными элементами (с точностью до переноса координат). Более конкретно, как отмечено у Ионаску, всякий куб в $\mathbb{Z}^3$ можно сдвинуть так, чтобы одна из его вершин совпала с началом координат, после чего три ребра из этой вершины задаются тремя строками (или столбцами) некоторой $3\times 3$ ортогональной матрицы $Q$ с рациональными записями. Строки матрицы (после домножения на общий знаменатель) будут именно целыми ортогональными векторами $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3$, определяющими наш куб. В частности, если

$$ Q = \begin{pmatrix} r_{11} & r_{12} & r_{13} \\ r_{21} & r_{22} & r_{23} \\ r_{31} & r_{32} & r_{33} \end{pmatrix}, $$

то $\mathbf{v}\times1=(r_{11},r_{12},r_{13})$, $\mathbf{v}\times2=(r_{21},r_{22},r_{23})$, $\mathbf{v}\times3=(r_{31},r_{32},r_{33})$ с точностью до общего рационального масштаба. Требование целочисленности куба означает, что $r_{ij} = \frac{m_{ij}}{d}$ для некоторых целых $m_{ij},d$, причём после умножения $Q$ на $d$ получим матрицу с целочисленными строками $M = d,Q = (m_{ij})$. Эта целочисленная матрица $M$ удовлетворяет $M^T M = d^2 E$ (поскольку $Q$ ортогональна). Таким образом $M$ – это целочисленная матрица, у которой скалярные произведения строк дают либо $d^2$ (для скалярного произведения строки самой на себя) либо $0$ (для скалярных произведений разных строк). Строки $M$ – как раз искомые целочисленные ортогональные векторы $\mathbf{v}_i$ длины $d$ (то есть $||\mathbf{v}_i||^2=d^2$), описывающие решётчатый куб с ребром длины $d$. Из этого рассуждения видно, что существование решётчатого куба со стороной $\sqrt{L}$ эквивалентно существованию целой матрицы $M$, для которой $M^T M = L E$

Эквивалентность кубов

При классификации решётчатых кубов удобно факторизовать эквивалентные случаи. Будем говорить, что два решётчатых куба $K_1$ и $K_2$ эквивалентны, если один можно перевести в другой посредством целочисленного ортогонального преобразования, то есть преобразования пространства, заданного матрицей $U\in \mathrm{O}(3,\mathbb{Z})$. Здесь $\mathrm{O}(3,\mathbb{Z})$ обозначает группу $3$ трёх матриц с целыми элементами, ортогональных (то есть $U^TU=E$) – фактически это группа симметрий куба, включающая повороты и зеркальные отражения, которые переводят решётку $\mathbb{Z}^3$ в себя. Группа $\mathrm{O}(3,\mathbb{Z})$ конечна; она состоит из матриц, в каждой строке и каждом столбце которых стоит ровно одна из координат ${+1;-1}$, а остальные нули (то есть перестановочные матрицы с произвольными расстановками знаков). По сути $\mathrm{O}(3,\mathbb{Z})$ – это группа симметрий правильного куба, и её порядок равен $3! \cdot 2^3 = 48$ (24 из них – собственно вращения с $\det=1$, и ещё 24 – вращения с отражениями с $\det=-1$). Эквивалентные кубы имеют одинаковую форму и отличаются лишь поворотом или отражением решётки; при подсчёте $S(n)$ они, как правило, дают одинаковое число решётчатых точек внутри, однако могут занимать разные положения в границах $[0,n]^3$.

При решении задачи часто бывает полезно рассматривать кубы с точностью до такой эквивалентности. Например, выясняя, какие длины ребра возможны для неприводимых кубов, достаточно проверять существование хотя бы одного представителя класса эквивалентности для данной длины. Аналогично, при вычислении Эрхартова многочлена для куба (см. ниже) достаточно взять любой куб из класса – коэффициенты многочлена будут одинаковы. Тут надо отметить, что при подсчёте $C(n)$ или $S(n)$ мы, однако, считаем каждый куб, независимо от его ориентации, как отдельный, даже если существует другой ему эквивалентный куб в другом месте области $[0,n]^3$. Поэтому понятие эквивалентности будем использовать как вспомогательное для классификации и понимания структуры решения, но не для непосредственного объединения при суммировании $S(n)$

Эрхартовский многочлен

Эрхартов многочлен – это понятие из геометрической комбинаторики, которое мы будем активно использовать для подсчёта решётчатых точек. Эрхартовским многочленом $L(P,t)$ называется многочлен, описывающий число решётчатых точек в целочисленном политопе. Политоп - это многомерный аналог многогранника, двумерный — многоугольник, трёхмерный — привычный многогранник, в общем случае — выпуклая фигура, заданная конечным числом точек в $\mathbb{R}^d$ $P$ при его масштабировании. Более точно, если $P$ – выпуклый многогранник в $\mathbb{R}^d$ с вершинами в узлах решётки $\mathbb{Z}^d$, то Эжен Эрхарт доказал, что функция

$$ L(P,t) = |\,tP \cap \mathbb{Z}^d\,|, \qquad t\in \mathbb{N}, $$

является многочленом от $t$ степени $d$. Здесь $tP = {t\mathbf{x} : \mathbf{x}\in P}$ – растянутый в $t$ раз многогранник (гомотетия с центром в начале координат). Коэффициенты этого многочлена связаны с геометрическими характеристиками $P$. В частности, ведущий коэффициент равен объёму $P$ (нормированному к объёму элементарного параллелепипеда решётки), а второй по старшинству коэффициент равен половине площади поверхности $P$ (также нормированной). Формально, если $\dim P = d$, ) — обозначение размерности объекта, например, $\dim P = d$ означает, что политоп $P$ живёт в $d$-мерном пространстве}то

$$ L(P,t) = \mathrm{Vol}(P)\,t^d + \frac{1}{2}\mathrm{Vol}(\partial P)\, t^{d-1} + \cdots + \chi(P), $$

где $\mathrm{Vol}(P)$ – $d$-мерный объём $P$$ (от англ. volume) — обозначение объёма (или меры) множества в нужной размерности: $d$-мерный для $P$, $(d{-}1)$-мерный для $\partial P$}, $\mathrm{Vol}(\partial P)$ – $(d-1)$-мерный объём (площадь) поверхности $P$, а $\chi(P)$ – характеристическая функция Эйлера (которая равна $1$ для выпуклого многогранника). Остальные коэффициенты тоже имеют комбинаторно-геометрический смысл, но в общем случае вычислять их сложно. Тем не менее, для некоторых симметричных политопов эти многочлены принимают простую форму.

Для куба, выровненного по решётке (ось-ориентированного), легко получить Эрхартов многочлен: если ребро куба содержит $m$ единичных отрезков (т.е. длина ребра $m$ в решёточных единицах), то $(t$-кратно увеличенный$)$ куб будет иметь сторону $tm$ и, следовательно, число решётчатых точек $(tm+1)^3$. Таким образом, $L_{\text{осев.куб}}(t) = (mt+1)^3 = m^3 t^3 + 3m^2 t^2 + 3m t + 1$. Здесь $m^3$ – это, очевидно, объём куба, $3m^2$ – полусумма площадей граней (у осевого куба каждая грань имеет площадь $m^2$, всего 6 граней, нормированный фундаментальный параллелограмм на грани – единичный квадрат, так что $\frac{1}{2}\cdot 6 m^2 = 3m^2$), $3m$ – коэффициент при $t$ и $1$ – свободный член (равный $\chi(P)=1$).

Интереснее обстоит дело для повёрнутого куба. Как показали Ионаску с соавторами, Эрхартов многочлен любого решётчатого куба имеет достаточно простой вид. Если $C$ – примитивный решётчатый куб с длиной ребра $\ell$ (например, $\ell=2k-1$ нечётная, как выяснится далее), то \begin{equation} L(C,t) = \ell^3 t^3 + \lambda_1 t^2 + \lambda_2 t + 1 \end{equation}

где $\lambda_1$ и $\lambda_2$ – некоторые целые коэффициенты, зависящие от ориентации куба. В частности, $\lambda_1 = \frac{1}{2}\sum_{f} \mathrm{Area}(f) / \mathrm{Area}(D_f)$$ (от англ. area) — обозначение площади геометрической фигуры, в том числе нормированной площади в задачах на решётку}, где сумма берётся по всем 6 граням $f$ куба $C$, $\mathrm{Area}(f)$ – площадь грани $f$, а $\mathrm{Area}(D_f)$ – площадь фундаментального домена подрешётки, индуцированной на грани $f$.

Давайте тут подробнее остановимся, чтобы не потерять нить рассуждения в терминах. Когда мы смотрим на грань куба (то есть двумерную плоскость в $\mathbb{R}^3$), и она лежит не «по осям», а как-то наклонена, то на ней тоже есть решётка — это все целочисленные точки, лежащие в этой плоскости. Эти точки образуют подрешётку — то есть решётку меньшей размерности, «вырезанную» из трёхмерной решётки. Собственно, фундаментальный домен — это минимальный по площади параллелограмм, с помощью которого можно замостить всю эту плоскость решётки без пропусков и перекрытий. Он как бы играет роль «ячейки» этой двумерной решётки на грани куба. Можно представить, что у нас есть бесконечная решётка из точек на листе бумаги, и мы хотим её «покрыть» одинаковыми плитками — фундаментальный домен — это одна такая базовая плитка, которую мы можем много раз сдвигать (по векторам решётки), чтобы покрыть всю плоскость.

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

Важно, что для одного класса эквивалентности кубов (т.е. кубов, которые можно получить друг из друга симметрией решётки) многочлен $L(C,t)$ будет один и тот же. Таким образом, ориентированные кубы одной формы имеют одинаковое распределение решётчатых точек при масштабировании. Это позволяет сначала вычислить Эрхартов многочлен для каждого типа ориентации, а затем, зная его, находить, сколько точек содержится в каждом конкретном представителе этого типа при данных $t$ (масштабе).

Как это всё связано с задачей и чем нам поможет, если нам удастся классифицировать все типы решётчатых кубов (вплоть до эквивалентности) и узнать формулы $L(C,t)$ для каждого типа, то можно просуммировать по всем кубам внутри $[0,n]^3$ число точек, используя эти формулы при $t=1$ (то есть фактически $t$ – это масштаб, но кубы внутри $[0,n]^3$ могут иметь разный масштаб относительно примитивного типа). Подробнее эта стратегия будет раскрыта ниже, после того как мы разберём арифметику решений условий ортогональности.

Теорема 1. Нечётность квадрата длины ребра неприводимого куба

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

Теорема 1

Если в $\mathbb{Z}^3$ существует примитивный решётчатый куб с длиной ребра $\ell=\sqrt{L}$, то $L$ является нечётным числом. Другими словами, квадрат длины ребра неприводимого куба нечетен.

Доказательство теоремы 1

Это утверждение можно проиллюстрировать примерами. Например, для длины ребра $\ell = 3$ (то есть $L = 9$) мы имеем вектор $\mathbf{v}_1 = (3,0,0)$, и соответствующий куб ориентирован по осям. Однако такой куб является масштабированием единичного (примитивного) куба с длиной ребра 1 и не даёт нового примитивного класса. То же касается $\ell = 6$, $\ell = 8$, и других чётных значений: они всегда соответствуют масштабированию примитивных кубов с меньшими нечётными сторонами.

Давайте разберём, что происходит с $\ell = 9$, можно ли при этом получить примитивный решётчатый куб, и как это согласуется с теоремой. Дело в том, что в первоначальном приближении у меня возникла ошибочная интерпретация. Например, можно подумать, что если длина ребра равна $\ell = 9$, то соответствующая длина вектора $\mathbf{v}_1 = (3,3,3)$ приводит к $\|\mathbf{v}_1\|^2 = 3^2 + 3^2 + 3^2 = 27$, и, поскольку 27 якобы не представимо как сумма трёх квадратов, это якобы исключает возможность построения остальных ортогональных векторов такой же длины. Однако это рассуждение некорректно: оно подменяет геометрическую задачу (о существовании ортогональных целочисленных векторов одинаковой длины) задачей о разложении одного числа на сумму трёх квадратов. На деле же нас интересует представимость самого $L = \ell^2$ как суммы четырёх квадратов $a^2 + b^2 + c^2 + d^2$, а она всегда возможна благодаря теореме Лагранжа.

Что происхдоит когда $\ell = 9$, то есть $L = 81$. Является ли $L = 81$ нечётным? Да, а значит, теорема 1 не запрещает существование примитивного куба с длиной ребра $\ell = 9$. Мы ищем, существует ли он на самом деле. Можно ли разложить 81 как сумму четырёх квадратов? Да, по тождеству Лагранжа любое натуральное число $L$ представимо как сумма четырёх квадратов:

$$ 81 = 9^2 + 0^2 + 0^2 + 0^2, \quad \text{или} \quad 81 = 6^2 + 3^2 + 0^2 + 0^2, \quad \text{или и т.д.} $$

Это важно потому, что, как мы видели ранее, все примитивные кубы можно параметризовать кватернионами (в следующей теореме разберём подробнее), т.е. четырьмя целыми числами $(a, b, c, d)$ таких, что: $a^2 + b^2 + c^2 + d^2 = L$

Существуют ли примитивные кватернионы с нормой 81? Да, более того, формула Якоби для $r_4(n)$ (важно не путать с Формулой Якоби не из теории чисел, связывающей определитель матрицы, удовлетворяющей дифференциальному уравнению, в начале интервала интегрирования с определителем матрицы в конце интервала интегрирования, это о другом) говорит, что:

$$ \begin{aligned} r_4(81) &= 8 \cdot \sum_{\substack{d \mid 81\\ d \text{ нечётный}}} d \\ &= 8 \cdot (1 + 3 + 9 + 27 + 81) \\ &= 8 \cdot 121 = 968 \end{aligned} $$

Значит, существует 968 кватернионов, и часть из них даёт примитивные кубы (после отбрасывания масштабированных). Есть ли среди них примитивные? Да, например, кватернион $(6, 3, 0, 0)$ даёт ортогональную матрицу и векторы, у которых координаты взаимно просты (gcd = 1), а значит — примитивный куб. Так что для $\ell = 9$, $L = 81$, примитивный куб действительно существует.

Таким образом, примитивные (неприводимые) кубы возникают только для нечётных значений $\ell$, начиная с $\ell = 3$, и соответствующие $L = \ell^2$ также являются нечётными. Именно это и утверждается в теореме: если существует примитивный куб с длиной ребра $\ell = \sqrt{L}$, то число $L$ обязательно нечётно.

В частности, известны примитивные кубы с длинами рёбер $\ell = 3, 5, 7, 11, 13, \dots$. Как будет показано далее, для $\ell = 3, 5, 7, 11$ существует по одному классу ориентаций, а начиная с $\ell = 13$ появляются случаи с несколькими непересекающимися классами.

Следствие из теоремы 1

Если $L$ — чётное натуральное число, то в пространстве $\mathbb{Z}^3$ не существует примитивного решётчатого куба с квадратом длины ребра $L$. Иными словами, для всех чётных $L$ возможны только кратные (масштабированные) кубы, полученные из примитивных кубов с меньшей нечётной длиной.

Это непосредственно вытекает из Теоремы~1, согласно которой квадрат длины ребра любого примитивного решётчатого куба обязан быть нечётным. Таким образом, если $L$ чётно, то куб с длиной $\sqrt{L}$ может существовать лишь как результат целочисленного масштабирования другого куба с меньшей длиной ребра. В частности, если $L = d^2 L_0$ с нечётным $L_0$ и $d > 1$, то куб с $L$ является $d$-кратным масштабом примитивного куба с длиной $\sqrt{L_0}$.

Теорема 2. Параметризация решётчатых кубов при помощи кватернионов

Пара условий ортогональности:

$$ \mathbf{v}_i\cdot \mathbf{v}_j = 0 \ (i\neq j), \qquad ||\mathbf{v}_1||=||\mathbf{v}_2||=||\mathbf{v}_3||=\sqrt{L} $$

задаёт систему диофантовых уравнений относительно координат векторов $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3$. Найти все решения этой системы напрямую непросто, однако существует элегантный метод параметризации посредством кватернионов.

Кватернион $q$ – это выражение вида

$$ q = x_0 + x_1 \mathbf{i} + x_2 \mathbf{j} + x_3 \mathbf{k}, $$

где $x_0,x_1,x_2,x_3\in\mathbb{R}$, а $\mathbf{i},\mathbf{j},\mathbf{k}$ – символы, образующие базис т.н. тела кватернионов $\mathbb{H}$ с соотношениями $\mathbf{i}^2=\mathbf{j}^2=\mathbf{k}^2 = \mathbf{i}\mathbf{j}\mathbf{k} = -1$ (и из них $\mathbf{i}\mathbf{j}=-\mathbf{j}\mathbf{i}=\mathbf{k}$ и циклически другие). Не углубляясь в свойства кватернионов, отметим главное: кватернионы могут использоваться для кодирования вращений в 3-мерном пространстве (аналогично тому, как комплексные числа кодируют вращения на плоскости). Если $q = x_0 + x_1\mathbf{i}+x_2\mathbf{j}+x_3\mathbf{k}$ – единичный кватернион (т.е. $x_0^2+x_1^2+x_2^2+x_3^2=1$), то ему соответствует поворот в $\mathbb{R}^3$ вокруг некоторой оси на некоторый угол, и наоборот, любой поворот можно отобразить на два противоположных кватерниона $\pm q$. В координатном выражении этому соответствует следующее утверждение:

Теорема 2

Все решения системы

$$ \begin{cases} a_1^2+a_2^2+a_3^2 = b_1^2+b_2^2+b_3^2 = c_1^2+c_2^2+c_3^2 = L,\\ a_1 b_1 + a_2 b_2 + a_3 b_3 = a_1 c_1 + a_2 c_2 + a_3 c_3 = b_1 c_1 + b_2 c_2 + b_3 c_3 = 0, \end{cases} $$

где $L$ – заданное натуральное число, могут быть параметризованы с помощью четырёх целых параметров $(p_0,p_1,p_2,p_3)$, удовлетворяющих $p_0^2+p_1^2+p_2^2+p_3^2 = L$. Более точно, пусть $(p_0,p_1,p_2,p_3)\in \mathbb{Z}^4$ – любое решение уравнения

$$ p_0^2+p_1^2+p_2^2+p_3^2 = L $$

Тогда векторы \begin{equation} \begin{aligned} \mathbf{v}_1 &= (p_0^2 + p_1^2 - p_2^2 - p_3^2,\quad 2(p_1 p_2 - p_0 p_3),\quad 2(p_1 p_3 + p_0 p_2)),\\ \mathbf{v}_2 &= (2(p_1 p_2 + p_0 p_3),\quad p_0^2 - p_1^2 + p_2^2 - p_3^2,\quad 2(p_2 p_3 - p_0 p_1)),\\ \mathbf{v}_3 &= (2(p_1 p_3 - p_0 p_2),\quad 2(p_2 p_3 + p_0 p_1),\quad p_0^2 - p_1^2 - p_2^2 + p_3^2) \end{aligned} \end{equation}

удовлетворяют приведённой выше системе и тем самым задают решётчатый куб с длиной ребра $\sqrt{L}$. При этом любое решение системы ортогональности получается (с точностью до перестановки и знаков векторов $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3$) из некоторого набора параметров $(p_0,p_1,p_2,p_3)$ по формуле .

Перед тем как дать доказательство, отметим связь с кватернионами: здесь четырёх $(p_0,p_1,p_2,p_3)$ можно отождествить с целым кватернионом $q = p_0 + p_1\mathbf{i}+p_2\mathbf{j}+p_3\mathbf{k}$. Тогда условия $p_0^2+p_1^2+p_2^2+p_3^2 = L$ означает, что норма кватерниона $q$ равна $\sqrt{L}$. Формулы – это не что иное, как матрица поворота, соответствующая кватерниону $q$. Действительно, известное соответствие (формула Родрига–Гамильтона) между кватернионом $q$ и матрицей $Q\in \mathrm{SO}(3)$ выглядит так: если $q$ нормирован к 1 (т.е. единичный), то поворотное преобразование $\mathbb{R}^3$ задаётся матрицей

$$ Q = \begin{pmatrix} p_0^2 + p_1^2 - p_2^2 - p_3^2 &\quad 2(p_1 p_2 - p_0 p_3) &\quad 2(p_1 p_3 + p_0 p_2)\\ 2(p_1 p_2 + p_0 p_3) &\quad p_0^2 - p_1^2 + p_2^2 - p_3^2 &\quad 2(p_2 p_3 - p_0 p_1)\\ 2(p_1 p_3 - p_0 p_2) &\quad 2(p_2 p_3 + p_0 p_1) &\quad p_0^2 - p_1^2 - p_2^2 + p_3^2 \end{pmatrix}, $$

которая и является ортогональной (в действительности, специальной ортогональной, $\det=1$). В нашем случае $p_i$ могут не нормировать к 1, а быть произвольными целыми, дающими нужную сумму квадратов $L$. Тогда матрица $Q$ будет иметь рациональные коэффициенты с общим знаменателем $L$ (точнее, $Q = \frac{1}{L}M$, где $M$ – целая матрица, совпадающая с , но без коэффициентов $2$ там, где они не явно написаны перед $p_0^2$, и с $L$ вместо $p_0^2+p_1^2+p_2^2+p_3^2$). Эта матрица $M$ удовлетворяет $M^T M = L E$ и имеет строки $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3$. Так реализуется соответствие между целыми кватернионами и решётчатыми кубами.

Доказательство теоремы 2

Эта теорема фактически переформулирует тождество Эйлера о сумме четырёх квадратов. Леонард Эйлер ещё в 1748 г. открыл, что произведение сумм четырёх квадратов само по себе выражается как сумма четырёх квадратов (это известное многочленное тождество). В кватернионной форме оно выглядит особенно просто: если $q_1 = a_0+a_1\mathbf{i}+a_2\mathbf{j}+a_3\mathbf{k}$ и $q_2 = b_0+b_1\mathbf{i}+b_2\mathbf{j}+b_3\mathbf{k}$, то

\begin{align*} q_1 q_2 ={}& (a_0 b_0 - a_1 b_1 - a_2 b_2 - a_3 b_3) \\ &+ (a_0 b_1 + a_1 b_0 + a_2 b_3 - a_3 b_2)\mathbf{i} \\ &+ (a_0 b_2 - a_1 b_3 + a_2 b_0 + a_3 b_1)\mathbf{j} \\ &+ (a_0 b_3 + a_1 b_2 - a_2 b_1 + a_3 b_0)\mathbf{k} \end{align*}

и, в частности, норма $||q_1 q_2||^2 = ||q_1||^2 \cdot ||q_2||^2$. В терминах сумм четырёх квадратов это и даёт тождество:

$$ (a_0^2+a_1^2+a_2^2+a_3^2)\,(b_0^2+b_1^2+b_2^2+b_3^2) = c_0^2 + c_1^2 + c_2^2 + c_3^2, $$

где $(c_0,c_1,c_2,c_3)$ определяются вышеописанными билинейными формулами (подобными тем, что в ). Эйлерово тождество послужило фундаментом для доказательства теоремы Лагранжа о четырёх квадратов (1770 г.), утверждающей что любое натуральное число представимо как сумма четырёх квадратов. Применительно к нашей задаче, это означает, что для любого $L$ можно найти целочисленный кватернион $(p_0,p_1,p_2,p_3)$ с $p_0^2+\dots+p_3^2 = L$. Согласно теореме 2, из него получаются векторы , задающие (не обязательно примитивный) решётчатый куб длины $\sqrt{L}$. Это доказывает следующее важное следствие:

Следствие из теоремы 2

Для любого $L \in \mathbb{N}$ существует решётчатый куб в $\mathbb{Z}^3$, длина ребра которого равна $\sqrt{L}$, то есть $\|\mathbf{v}_i\|^2 = L$.

Это следует из того, что любое натуральное число представимо в виде суммы четырёх квадратов, а теорема~2 утверждает, что такое представление порождает ортогональную тройку векторов, задающих решётчатый куб длины $\sqrt{L}$.

Если $L$ чётно, то соответствующий куб не будет примитивным — он представляет собой масштабированный (в $d$ раз) вариант примитивного куба с $\|\mathbf{v}_i\|^2 = L_0$, где $L = d^2 L_0$ и $L_0$ — нечётное число. Таким образом, любой куб в $\mathbb{Z}^3$ может быть представлен как кратный примитивному.

Теорема 3. Эквивалентные классы и число ориентаций примитивных кубов

После того как мы установили условия существования примитивных кубов и их параметризацию через кватернионы, возникает естественный вопрос: сколько различных (неэквивалентных) ориентаций может иметь примитивный куб с заданной длиной ребра? Иными словами, сколько существует классов примитивных кубов с длиной $\ell = \sqrt{L}$, различающихся с точностью до поворотов и отражений решётки? Ответ на этот вопрос даёт следующая теорема.

Теорема 3

Пусть $L$ — нечётное натуральное число. Обозначим через $N_{\text{classes}}(L)$ число различных классов эквивалентности (ориентаций) примитивных решётчатых кубов с квадратом длины ребра $L$. Тогда в общем случае выполняется формула: $$ N_{\text{classes}}(L) = \frac{r_4(L)}{48}, $$

Разберёмся что это за буквы и цифры. Здесь $r_4(L)$ - это число представлений натурального числа $L$ в виде суммы четырёх квадратов:

$$ r_4(L) = \left|\left\{(p_0, p_1, p_2, p_3) \in \mathbb{Z}^4 : p_0^2 + p_1^2 + p_2^2 + p_3^2 = L \right\}\right| $$

Каждое такое представление даёт кватернион $q = p_0 + p_1 i + p_2 j + p_3 k$, а через формулу Эйлера–Родригеса — ортогональную матрицу, строки которой становятся направляющими векторами примитивного куба. Но не каждое такое представление — это разная ориентация куба. Дело в том, что многие кватернионы задают одни и те же ориентации, и их нужно отождествить. А именно: $q \sim -q$ потому что они задают одно и то же вращение → делим на 2.

Когда мы строим ортогональную матрицу из кватерниона, разные перестановки строк и изменения их знаков приводят к одинаковым кубам, просто по-другому сориентированным в пространстве. Такие преобразования образуют группу симметрий куба, которая включает:

• $3! = 6$ способов перестановки строк (или векторов-ребер),
• $2^3 = 8$ способов менять знаки трёх строк.

Итого: $6 \cdot 8 = 48$. Значит всего у нас $r_4(L)$ представлений числа как суммы четырёх квадратов, каждому кубу (ориентации) соответствуют 48 эквивалентных представлений в силу симметрий. Чтобы получить число классов кубов, делим:

$$ N_{\text{classes}}(L) = \frac{r_4(L)}{48} $$

Работает для примитивных кубов, потому что у них нельзя отождествить одинаковые ориентации через масштабирование. В случае непримитивных (кратных) кубов появляются новые симметрии, и счёт становится более сложным — поэтому формула применима именно к примитивным. Например:

• $r_4(9) = 104$, но $104/48 \approx 2.17$, значит не все 48 классов равномерно распределены — есть дополнительные симметрии;
• $r_4(121) = 1064$, и $1064/48 = 22.17$, аналогично — но после отбора только примитивных, может остаться целое число классов.

Исключения составляют вырожденные случаи, в которых некоторые кватернионные представления порождают одну и ту же ориентацию куба. В этих случаях значение $N_{\text{classes}}(L)$ может быть строго меньше $r_4(L)/48$, однако для большинства нечётных $L$ формула даёт точный результат.

Доказательство теоремы 3

Как обсуждалось ранее, каждое целочисленное представление $L = p_0^2 + p_1^2 + p_2^2 + p_3^2$ задаёт кватернион $q = (p_0, p_1, p_2, p_3)$ и, через формулы Эйлера–Родригеса, — ортогональную матрицу, строки которой представляют собой направляющие векторы примитивного куба. Общее число таких представлений равно $r_4(L)$ (см. формулу Якоби~).

При этом:

• Отождествляются кватернионы $q$ и $-q$, поскольку они задают одно и то же вращение. Это даёт деление на $2$.
• Также учитываются все перестановки строк и смены знаков, соответствующие действиям группы симметрий правильного куба (группа порядка $24$).

В совокупности это приводит к делению на $48$, то есть $N_{\text{classes}}(L) = r_4(L)/48$, если отсутствуют дополнительные симметрии представлений. В вырожденных случаях (например, если некоторые координаты $p_i$ равны нулю) возникает дополнительная кратность, и формула даёт переоценку. Тем не менее, для большинства нечётных $L$ все $p_i \ne 0$, и класс ориентации действительно определяется однозначно.

Следствие из теоремы 3

Для большинства нечётных $L$ значение $r_4(L)$ делится на 48 с остатком, и поэтому число различных ориентаций примитивных кубов с длиной ребра $\ell = \sqrt{L}$ приближённо, но не всегда точно, описывается формулой $$ N_{\text{classes}}(L) = \frac{r_4(L)}{48}. $$

Формула точна лишь тогда, когда у представлений нет собственных симметрий. Это происходит чаще всего при достаточно больших $L$, где все четыре координаты $p_i$ отличны от нуля. Примеры:

$$ \begin{aligned} L = 9 &\Rightarrow r_4(9) = 104 \Rightarrow N_{\text{classes}}(9) = \frac{104}{48} \approx 2.17 \\ L = 25 &\Rightarrow r_4(25) = 248 \Rightarrow N_{\text{classes}}(25) = \frac{248}{48} \approx 5.17 \\ L = 49 &\Rightarrow r_4(49) = 456 \Rightarrow N_{\text{classes}}(49) = \frac{456}{48} = 9.5 \\ L = 121 &\Rightarrow r_4(121) = 1064 \Rightarrow N_{\text{classes}}(121) = \frac{1064}{48} \approx 22.17 \\ L = 169 &\Rightarrow r_4(169) = 1464 \Rightarrow N_{\text{classes}}(169) = \frac{1464}{48} = 30.5 \\ L = 225 &\Rightarrow r_4(225) = 3224 \Rightarrow N_{\text{classes}}(225) = \frac{3224}{48} \approx 67.17 \end{aligned} $$

Таким образом, при малых $L$ значения $N_{\text{classes}}(L)$, как правило, нецелые, что говорит о наличии внутренних симметрий среди кватернионных представлений. При больших $L$ значение $r_4(L)$ становится достаточно крупным, и дробное значение $N_{\text{classes}}$ приближается к целому. Однако точный переход к целочисленным значениям зависит от конкретных арифметических свойств $L$ и наличия/отсутствия повторяющихся ориентаций.

Хотя значение $r_4(L)$ редко делится на $48$ точно, формула $$ N_{\text{classes}}(L) \approx \frac{r_4(L)}{48} $$ всё равно даёт корректную оценку количества ориентаций при больших $L$. Это не точное, но асимптотически верное выражение. При малых $L$ симметрий больше, и формула переоценивает число классов. При больших — доля совпадающих представлений становится пренебрежимо малой.

Использование результатов для подсчёта $S(n)$

Теперь, обладая всеми вышеустановленными свойствами, вернёмся к основной задаче – вычислению $S(n)$, суммы числа решётчатых точек во всех кубах с вершинами в пределах $[0,n]^3$. План решения таков:

1. Разбить все такие кубы на группы по значению квадрата длины ребра $L$ и по типу ориентации (классу эквивалентности).

2. Для каждого возможного $L$ определить, какие классы ориентаций существуют. Из теоремы 1 и теоремы 3 следует, что $L$ должно быть нечётным (то есть представимо в виде суммы трёх квадратов целых чисел) для существования примитивного куба с таким ребром. Если $L$ чётно, то куб с таким $L$ будет непримитивным, являясь масштабированной копией куба с меньшим значением $L$.

3. Для каждого класса ориентации куба найти его Эрхартов многочлен . В частности, нас будет интересовать значение $L(C,1)$ – число решётчатых точек внутри самого куба (при масштабе $t=1$). Именно $L(C,1)$ даёт количество точек, содержащихся в кубе данного класса без растяжения.

4. Определить, сколько сдвигов (параллельных переносов) данного куба умещается внутри области $[0,n]^3$. Если куб имеет длину ребра $\sqrt{L}$ и ориентацию, заданную векторами $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3$ (с минимальной начальной вершиной «в углу» области, так что все компоненты $\mathbf{v}_i$ неотрицательны), то при размещении одной из его вершин в точку $(x,y,z)$ он полностью лежит внутри $[0,n]^3$ тогда и только тогда, когда $(x,y,z)$ удовлетворяет неравенствам: $$ \begin{cases} 0 \,\le\, x \,\le\, n - (v_{1x}+v_{2x}+v_{3x})\,,\\[6pt] 0 \,\le\, y \,\le\, n - (v_{1y}+v_{2y}+v_{3y})\,,\\[6pt] 0 \,\le\, z \,\le\, n - (v_{1z}+v_{2z}+v_{3z})\,, \end{cases} $$ где $(v_{ix},v_{iy},v_{iz})$ – координаты вектора~$\mathbf{v}_i$.

Введём обозначения:

$$ \Delta_x = |x_1| + |x_2| + |x_3|,\quad \Delta_y = |y_1| + |y_2| + |y_3|,\quad \Delta_z = |z_1| + |z_2| + |z_3| $$

— это оценки максимального разброса координат по каждой из осей. Тогда число размещений куба данного типа пределах $[0,n]^3$ с одной фиксированной вершиной в точке решётки равно:

$$ (n - \Delta_x + 1)(n - \Delta_y + 1)(n - \Delta_z + 1) $$

Этот результат следует из анализа всех 8 вершин куба как суммы комбинаций векторов $v_1, v_2, v_3$.

5. Вклад всех кубов данного типа в $S(n)$ равен произведению числа размещений на количество точек в одном таком кубе: $$ L(C,1)\;\cdot\;(n-\Delta_x+1)(n-\Delta_y+1)(n-\Delta_z+1)\,. $$ Просуммировав такие выражения по всем классам ориентации и по всем возможным $L$, получаем искомое $S(n)$.

Разумеется, выписанная выше формула носит скорее концептуальный характер, нежели даёт непосредственный способ вычисления $S(n)$ для больших $n$. Тем не менее, она позволяет оценить асимптотику роста $S(n)$ и сделать выводы о сложности расчёта. Структурно сумма вида

$$ \sum L(C,1)\,\prod_{i\in\{x,y,z\}}(n-\Delta_i+1) $$

распадается на большое число слагаемых, причём степень каждого слагаемого по $n$ не превышает 3 (ведь каждое множитель $(n-\Delta+1)$ вносит фактор порядка $n$).

6. Таким образом, $S(n)$ является многочленом степени 7 от $n$. Это подтверждается и эмпирически: например, $S(50)\approx 2.9949\cdot 10^{10}$, и ведущий порядок роста пропорционален $n^7$. Ведущий член формируется кубами с наименьшими $L$ (преимущественно осево-ориентированными): таких кубов порядка $n^4$, и каждый содержит порядка $n^3$ точек, что суммарно даёт вклад $\sim \frac{1}{24}n^7$. Повёрнутые кубы с более большими $L$ уменьшают коэффициент при $n^7$ лишь незначительно. Полученная суммарная формула для $S(n)$ содержит три линейных сомножителя (по числу осей) и один эрхартовский многочлен третьей степени. В совокупности, максимальная степень по $n$ достигает семи:

$$ S(n) = \sum_{C} (n - \Delta_x + 1)(n - \Delta_y + 1)(n - \Delta_z + 1) \cdot L(C, 1) \Rightarrow \deg S(n) = 7 $$

Это означает, что при больших $n$ количество решётчатых точек внутри всех кубов растёт как $\mathcal{O}(n^7)$. Ведущий вклад дают кубы с наименьшими $\ell$, особенно осевые (выровненные по координатным осям), поскольку таких кубов $\sim n^4$, а каждый содержит $\sim n^3$ точек.

Тем не менее, прямое суммирование миллионов слагаемых при $n=5000$ было бы затруднительно. На помощь приходит теория чисел: можно перегруппировать вычисление по параметру $L$. Заметим, что $\Delta_x = v_{1x}+v_{2x}+v_{3x}$ выражается через компоненты кватерниона решения (см.). В среднем можно ожидать, что величины $\Delta_i$ масштабно сравнимы с $\sqrt{L}$, и потому $(n - \Delta_i + 1) \sim n$ при $L \ll n^2$. Кроме того, число размещений кубов с фиксированным $L$ масштабно оценивается как $O(n^3)$ (пропорционально объёму области размещения). Сумма же по $L$ вплоть до $O(n^2)$ с учётом среднего порядка $L(C,1)\sim L^{3/2}$ (объём куба) возрастает как $\int_0^{n^2} L^{3/2}\,dL = O(n^{5})$, то есть значительно медленнее, чем $n^7$. Отсюда следует, что главный вклад в $S(n)$ действительно дают кубы с небольшими $L$. В частности, осево-ориентированные кубы соответствуют наименьшим возможным $L$ (когда один из параметров $p_i=\sqrt{L}$, а остальные равны нулю, так что $L$ является полным квадратом). Например, для такого куба $\Delta_x=L$, а $\Delta_y=\Delta_z=0$, и он может быть размещён примерно $n^3$ различными способами внутри области ($n+1$ позиций вдоль каждой оси). Наоборот, сильно повёрнутые кубы с более равномерно распределёнными координатами $p_i$ имеют большее $L$, но существенно меньшую область размещения (поскольку $\Delta_x,\Delta_y,\Delta_z$ велики и оставляют мало «запаса» до границы области). Таким образом, кубы с малым $L$ доминируют в сумме.

Практическое вычисление $S(n)$ для конкретного значения $n$ (как требовалось, например, в задаче Project Euler 579 для $n=5000$) можно осуществить, перебирая все решётчатые кубы с использованием описанной классификации. Наивный полный перебор всех кубов имеет сложность $O(n^4)$ (поскольку число кубов растёт как $n^4$), что для $n=5000$ слишком много. Вместо этого стоит применить оптимизированный подход, перебрать возможные значения $L$ (в худшем случае до порядка $n^2$, но фактически значительно меньше за счёт ограничений), и для каждого $L$ перебрать все представления $L = p_0^2+p_1^2+p_2^2+p_3^2$ (число таких представлений в среднем растёт субполиномиально, порядка $O(L^\epsilon)$ ). Для каждого найденного представления (соответствующего определённой ориентации куба) вычислить параметры $\Delta_x,\Delta_y,\Delta_z$ и значение $L(C,1)$ (последнее легко получить по формуле Эрхарта, зная ориентацию ребра куба). Затем проверить, помещается ли куб внутри области $[0,n]^3$ (т.е. неотрицательны ли $n-\Delta_i$ для $i=x,y,z$). Если условие выполняется, то добавить вклад

$$ L(C,1)\,\big(n-\Delta_x+1\big)\big(n-\Delta_y+1\big)\big(n-\Delta_z+1\big) $$

в накопленную сумму. Этот алгоритм требует аккуратного учёта эквивалентных случаев, чтобы не посчитать один и тот же куб несколько раз. Параметризация через кватернионы естественным образом генерирует все кубы, но каждое решение учитывается 48 раз (по числу симметрий куба). Для устранения дублей можно, например, зафиксировать знак одного из параметров ($p_0>0$) и ввести порядок на квартете $(p_0,p_1,p_2,p_3)$, чтобы не различать перестановки координат, или же включить все решения, но разделить полученный результат на 48 .

Вывод

Таким образом, задача подсчёта $S(n)$, на первый взгляд комбинаторно громоздкая, сводится к строго определённой арифметико-геометрической процедуре. Главную роль в ней играют малые примитивные кубы, особенно выровненные по осям, а суммарный вклад всех остальных типов быстро убывает. Это объясняет асимптотику $S(n) \sim \Theta(n^7)$ и делает возможным точный расчёт значений $S(n)$ даже при больших $n$, таких как $5000$, с помощью параметризации через кватернионы и соответствующего учёта симметрий.