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

Условие задачи

Решётчатым назовём куб, все восемь вершин которого принадлежат $\mathbb Z^3$. Пусть $C(n)$ — число различных решётчатых кубов, целиком помещающихся в $[0,n]^3$, а $S(n)$ — сумма числа решётчатых точек во всех этих кубах, включая границу. Полное условие находится на странице Project Euler 579.

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

Куб задаётся тремя целочисленными рёбрами

Перенесём одну вершину куба в начало координат и обозначим выходящие из неё рёбра через $u,v,w\in\mathbb Z^3$. Это куб тогда и только тогда, когда

$$ u\cdot v=u\cdot w=v\cdot w=0, \qquad \lVert u\rVert^2=\lVert v\rVert^2=\lVert w\rVert^2. $$

Все вершины после этого уже определены:

$$ 0,\ u,\ v,\ w,\ u+v,\ u+w,\ v+w,\ u+v+w. $$

Это описание сразу убирает большую часть геометрического шума. Больше не нужно проверять расстояния между двадцатью восемью парами вершин: достаточно трёх норм и трёх скалярных произведений.

Почему длина ребра обязательно целая

Сначала я машинально оставлял длину в виде $\sqrt m$, потому что квадрат нормы целочисленного вектора равен целому числу. В трёх измерениях наличие сразу трёх ортогональных рёбер даёт гораздо более сильное ограничение.

Составим целочисленную матрицу $M$, столбцами которой являются $u,v,w$, и положим

$$m=\lVert u\rVert^2=\lVert v\rVert^2=\lVert w\rVert^2.$$

Ортогональность означает

$$M^{\mathsf T}M=mI_3.$$

Берём определители:

$$(\det M)^2=m^3.$$

Левая часть — квадрат целого числа. Если простое $p$ входит в $m$ в степени $e$, то в $m^3$ оно входит в степени $3e$. Эта степень должна быть чётной, значит чётно и $e$. Все показатели в разложении $m$ чётны, поэтому $m=L^2$ для некоторого целого $L$. Следовательно,

$$\boxed{\lVert u\rVert=\lVert v\rVert=\lVert w\rVert=L\in\mathbb Z_{>0}.}$$

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

Первый способ перечисления: прямой эталон

Для фиксированной целой длины $L$ можно перебрать все целочисленные векторы $u$ на сфере

$$u_x^2+u_y^2+u_z^2=L^2,$$

затем все такие же $v$ с условием $u\cdot v=0$. Третье направление уже почти не оставляет выбора:

$$w=\frac{u\times v}{L}.$$

Если компоненты $u\times v$ не делятся на $L$, целочисленного третьего ребра нет. Если делятся, полученная тройка независимо проверяется по скалярным произведениям и нормам. Такой перебор медленный, зато предельно прозрачный. Я использую его как эталон для малых длин: если более быстрый генератор пропустил ориентацию или создал лишнюю, разница видна как конкретное множество вершин.

Как удалять повторы без сомнительного коэффициента

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

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

Быстрый способ: Эйлер—Родригес и кватернионы

Прямой перебор тратит слишком много времени на поиск ортогональных пар. Рациональные ортогональные матрицы удобнее порождать целочисленным кватернионом $q=(a,b,c,d)$. Обозначим его норму через

$$N=a^2+b^2+c^2+d^2.$$

Формула Эйлера—Родригеса даёт матрицу

$$ R(q)= \begin{pmatrix} a^2+b^2-c^2-d^2 & 2(bc-ad) & 2(bd+ac)\\ 2(bc+ad) & a^2-b^2+c^2-d^2 & 2(cd-ab)\\ 2(bd-ac) & 2(cd+ab) & a^2-b^2-c^2+d^2 \end{pmatrix}. $$

Её строки попарно ортогональны, а длина каждой строки равна $N$. Обратите внимание: $N$ здесь уже длина сырого ребра, а $N^2$ — квадрат этой длины.

Почему появляется делитель \(g\in\{1,2,4\}\)

Берём примитивный кватернион, то есть $\gcd(a,b,c,d)=1$. Матрица $R(q)$ может иметь общий множитель, который надо убрать. Он полностью определяется чётностью четырёх параметров:

• если нечётных параметров один или три, то $g=1$;
• если нечётных параметров ровно два, то $g=2$;
• если все четыре параметра нечётны, то $g=4$.

Случая «все четыре чётны» у примитивного кватерниона нет. После деления $R(q)$ на $g$ получаются целочисленные рёбра примитивной ориентации, а их длина равна

$$\boxed{L=\frac{N}{g}.}$$

Именно на этом месте особенно легко перепутать $L$ и $L^2$. В проверяемом ядре после нормировки заново вычисляются все три нормы и все три скалярных произведения, поэтому неверный случай чётности не может незаметно пройти дальше.

Почему нельзя делить число кватернионов на 48

Соблазнительная короткая формула выглядит так: посчитать представления нормы четырьмя квадратами, затем поделить на знак кватерниона, перестановки рёбер и смены знаков. Универсального делителя здесь нет.

Размер орбиты меняется, когда некоторые параметры кватерниона равны нулю, совпадают или отличаются только знаком. У осевой ориентации стабилизатор больше, чем у общего наклонного случая. Поэтому результат деления на постоянный коэффициент может быть даже нецелым — это не «почти число ориентаций», а сигнал, что такой коэффициент неприменим.

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

Две независимые проверки генератора

Для малых $L$ я строю множества канонических ключей двумя способами:

1. прямым перебором целочисленных векторов и ортогональных пар;
2. перебором примитивных кватернионов с нормировкой на $g=1,2,4$.

Сравниваются именно множества вершин. Простого совпадения количества недостаточно: один пропуск и один лишний дубль могли бы взаимно скрыться. Дополнительно для каждой ориентации проверяются целочисленность длины, равенство норм, ортогональность и отсутствие повторного канонического ключа.

Примитивная ориентация и масштаб

Общий делитель всех девяти компонент рёбер задаёт масштаб куба. Если этот НОД равен $t>1$, делим все три ребра на $t$ и получаем единственную примитивную ориентацию. Обратите внимание: требовать примитивности каждого ребра по отдельности слишком сильно. Для разложения по масштабам нужен общий НОД всей матрицы.

Поэтому дальше достаточно перечислить примитивные тройки $(u,v,w)$, а затем рассматривать их целые масштабы

$$(tu,tv,tw),\qquad t=1,2,3,\ldots.$$

Сколько решётчатых точек содержит один куб

Для целочисленного вектора положим

$$\gcd(u)=\gcd(|u_x|,|u_y|,|u_z|),$$

и обозначим

$$G=\gcd(u)+\gcd(v)+\gcd(w).$$

Для куба с целой длиной ребра $L$ точное число решётчатых точек равно

$$\boxed{\operatorname{points}(u,v,w)=L^3+(L+1)G+1.}$$

Вывод через объём, грани, рёбра и вершины

Объём куба равен $L^3$ — это главный трёхмерный вклад. Рассмотрим грань, натянутую на $u$ и $v$. Её нормаль параллельна $w$, а примитивная целочисленная нормаль равна $w/\gcd(w)$. Поэтому нормированная решётчатая площадь этой грани равна

$$\frac{L^2}{L/\gcd(w)}=L\gcd(w).$$

Пара противоположных граней даёт в коэффициенте поверхности ровно $L\gcd(w)$. После циклической суммы по трём направлениям получается $LG$. Четыре параллельных ребра каждого направления после учёта долей прилегающих граней дают линейный вклад $\gcd(u)$, $\gcd(v)$ и $\gcd(w)$, то есть ещё $G$. Совокупный вклад вершин равен $1$. Складывая четыре размерности, получаем

$$L^3+LG+G+1=L^3+(L+1)G+1.$$

Та же формула как многочлен Эрхарта

Теперь растянем фиксированную ориентацию в $t$ раз. Длина станет $tL$, а НОД каждого ребра умножится на $t$. Число точек является многочленом Эрхарта степени $3$:

$$E(t)=L^3t^3+LGt^2+Gt+1.$$

Его кубический коэффициент совпадает с объёмом, квадратичный — с половиной нормированной площади границы, $E(0)=1$, а взаимность Эрхарта даёт для внутренности

$$L^3t^3-LGt^2+Gt-1.$$

То есть закрытая и открытая версии согласованы по всем четырём коэффициентам. Подстановка $t=1$ снова даёт ту же формулу для исходного куба.

Два куба с ребром 3

Для осевого куба можно взять

$$u=(3,0,0),\quad v=(0,3,0),\quad w=(0,0,3).$$

Здесь $L=3$ и $G=3+3+3=9$, поэтому

$$27+4\cdot9+1=64=(3+1)^3.$$

Наклонный пример задаётся рёбрами

$$ u=(1,2,2),\qquad v=(2,-2,1),\qquad w=(2,1,-2). $$

Все три нормы равны $3$, скалярные произведения нулевые, но НОД каждого ребра равен $1$. Поэтому

$$27+4\cdot3+1=40.$$

Разница между $64$ и $40$ возникает не из-за объёма — он одинаков, — а из-за того, как грани и рёбра лежат относительно целочисленной решётки.

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

Координатные размахи

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

$$\Delta_x=\max_{p\in V}p_x-\min_{p\in V}p_x,$$

и аналогично для $y,z$. Для вершины куба координата $x$ является суммой некоторого подмножества чисел $u_x,v_x,w_x$. Максимум набирает все положительные компоненты, минимум — все отрицательные. Их разность равна

$$\boxed{\Delta_x=|u_x|+|v_x|+|w_x|,}$$

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

Сколько раз ориентация помещается в \([0,n]^3\)

После нормировки минимальной вершины в ноль по оси $x$ остаётся $n-\Delta_x+1$ допустимых целочисленных сдвигов. Если размах больше $n$, их нет. Координаты сдвига независимы, поэтому

$$ \boxed{ \operatorname{placements}_n(u,v,w)= \prod_{j\in\{x,y,z\}}[n-\Delta_j+1]_+, } $$

где $[r]_+=\max(r,0)$. Для наклонного примера выше все три размаха равны $5$, поэтому в боксе $[0,5]^3$ существует ровно одно размещение, а в $[0,6]^3$ — уже $2^3=8$.

Точная сумма по примитивным ориентациям

Пусть $\mathcal P$ — множество канонических примитивных ориентаций. Для $P=(u,v,w)\in\mathcal P$ обозначим длину ребра через $L_P$, сумму трёх НОД — через $G_P$, а базовые размахи — через $\Delta_{P,j}$. При масштабе $t$ получаем

$$ \operatorname{places}(P,t;n)= \prod_j[n-t\Delta_{P,j}+1]_+ $$

и

$$ \operatorname{points}(P,t)= (tL_P)^3+(tL_P+1)tG_P+1. $$

Отсюда следуют две конечные суммы:

$$ C(n)= \sum_{P\in\mathcal P}\sum_{t\ge1} \operatorname{places}(P,t;n), $$

$$ \boxed{ S(n)= \sum_{P\in\mathcal P}\sum_{t\ge1} \operatorname{places}(P,t;n)\, \operatorname{points}(P,t). } $$

Внутренняя сумма автоматически заканчивается, как только хотя бы один масштабированный размах превышает $n$. Эта запись не требует предполагать, что вся функция $S(n)$ является одним многочленом степени $7$. При росте $n$ в сумму входят новые ориентации и масштабы, поэтому глобально структура кусочная.

Контрольные значения

Одно и то же математическое ядро сначала сравнивает два генератора на малых длинах, затем считает размещения и точки. Оно воспроизводит контрольные значения:

Проверка при $n=50$ особенно полезна: здесь уже одновременно работают разные примитивные ориентации, несколько масштабов, неодинаковые размахи и обе части формулы для числа точек.

Итог

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

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