Формула Пика

Исторически формула Пика вписывается в длинную линию задач о решётчатых фигурах. Антон фон Мейстер ещё в 1769 году описал «формулу шнурования» площади многоугольника по координатам вершин^[8][9], которая является аналитическим предшественником формулы Пика. Параллельно в аналитической теории чисел развивались задачи подсчёта узлов целочисленной решётки внутри заданных областей. Классическим примером служит задача о круге Гаусса, восходящая к работам Карла Фридриха Гаусса^[10]. Однако, в отличие от теоремы Пика, дающей точное значение для многоугольников, в задаче Гаусса (и её современных обобщениях на евклидовы шары) исследуются асимптотические оценки остаточного члена при приближении числа решётчатых точек площадью или объёмом области с криволинейной границей^[11].

Опубликованная в 1899 году теорема Пика изначально формулировалась для простых многоугольников. Однако константа ${\displaystyle -1}$ в равенстве ${\displaystyle S=I+{\frac {B}{2}}-1}$ имеет глубокий топологический смысл: она представляет собой эйлерову характеристику ${\displaystyle \chi =1}$ односвязного многоугольника (топологически эквивалентного диску). Понятие эйлеровой характеристики, заложенное Леонардом Эйлером и обобщённое Анри Пуанкаре до фундаментального топологического инварианта, оказалось ключевым для исторического развития и обобщения теоремы.

Для решётчатого многоугольника с ${\displaystyle h}$ дырками эйлерова характеристика равна ${\displaystyle \chi =1-h}$, благодаря чему обобщённая формула Пика записывается в инвариантном виде ${\displaystyle S=I+{\frac {B}{2}}-\chi }$ (или ${\displaystyle S=I+{\frac {B}{2}}+h-1}$), где ${\displaystyle B}$ подсчитывается по всем компонентам границы, включая контуры отверстий^[12]. В современной дискретной геометрии такой подход позволяет связывать комбинаторное перечисление узлов решётки с топологическими свойствами полиэдральных комплексов.

Теорему доказал австрийский математик Георг Александр Пик (1859, Вена — 1942, Терезиенштадт). Пик получил докторскую степень в Венском университете в 1880 году, после чего был назначен ассистентом физика Эрнста Маха в Карло-Фердинандовском (Немецком) университете в Праге. В 1881 году он получил право преподавания (хабилитацию) в Праге, в 1888 году стал экстраординарным профессором, а в 1892 году — ординарным (полным) профессором математики Немецкого университета в Праге. В 1910 году Пик возглавил комитет, рекомендовавший Альберта Эйнштейна на кафедру математической физики этого университета; Эйнштейн занимал эту должность с 1911 по 1913 год, и в пражский период они с Пиком были близкими друзьями — именно Пик обратил внимание Эйнштейна на абсолютное дифференциальное исчисление, ставшее математическим языком общей теории относительности^[13].

Формула появилась в его статье «Geometrisches zur Zahlenlehre» («К геометрии теории чисел»), опубликованной в 1899 году в пражском журнале Lotos^[1]. Работа осталась почти незамеченной математическим сообществом. В 1927 году Пик вышел в отставку и вернулся в Вену. После аншлюса Австрии (1938) он переехал обратно в Прагу, где был избран членом Чешской академии наук и искусств; однако после немецкой оккупации Чехословакии в 1939 году был из неё исключён. 13 июля 1942 года 82-летний Пик был депортирован в концлагерь Терезиенштадт, где скончался 26 июля 1942 года^[13].

Известность формуле принёс польский математик Гуго Штейнгауз, включивший её в свою книгу «Kalejdoskop matematyczny»^[2]. Первое польское издание вышло в 1938 году, английское — в 1939-м под названием «Mathematical Snapshots» (3-е издание, 1969), а русское — под названием «Математический калейдоскоп». С тех пор формула Пика — один из самых популярных результатов, предлагаемых школьникам и студентам: она не требует иного аппарата, кроме арифметики, и служит стандартным упражнением в математических кружках и на олимпиадах^[14].

Вторая половина XX века принесла глубокий анализ границ применимости формулы. В 1957 году Джон Рив построил свои знаменитые тетраэдры, показав, что прямого трёхмерного аналога формулы не существует^[4]. В начале 1960-х годов Эжен Эрхарт создал общую теорию полиномов, считающих узлы решётки в кратных многогранниках, — теорию полиномов Эрхарта, двумерным частным случаем которой и является формула Пика^[5].

Пусть ${\displaystyle P}$ — простой (не имеющий самопересечений) многоугольник, все вершины которого имеют целочисленные координаты (иначе говорят, что ${\displaystyle P}$ является решётчатым многоугольником, или целочисленным многоугольником). Обозначим через ${\displaystyle I(P)}$ количество узлов целочисленной решётки ${\displaystyle \mathbb {Z} ^{2}}$, лежащих строго внутри ${\displaystyle P}$, а через ${\displaystyle B(P)}$ — количество узлов решётки, лежащих на границе ${\displaystyle P}$ (включая вершины и узлы на сторонах). Тогда площадь ${\displaystyle P}$ выражается формулой^[1][6][15]:

${\displaystyle A(P)=I(P)+{\frac {B(P)}{2}}-1.}$

Количество граничных узлов можно эффективно вычислять: на отрезке с концами в целочисленных точках ${\displaystyle (x_{1},y_{1})}$ и ${\displaystyle (x_{2},y_{2})}$ лежит ${\displaystyle \gcd(|x_{2}-x_{1}|,\,|y_{2}-y_{1}|)+1}$ узлов решётки (включая оба конца); суммируя по всем сторонам (и не забывая, что вершины посчитаны дважды), получают ${\displaystyle B(P)}$.

Формула применима к любым простым многоугольникам — выпуклым и невыпуклым, с любым числом сторон, — если только их вершины лежат в узлах решётки. Координаты вершин могут быть произвольными целыми числами (положительными, отрицательными, нулём). Для многоугольников с дырками (см. раздел Многоугольники с дырками) формула модифицируется. Для трёхмерных многогранников и выше прямой аналог формулы не существует (см. раздел Тетраэдры Рива)^[16].

• Единичный квадрат со сторонами, параллельными осям: ${\displaystyle I=0}$, ${\displaystyle B=4}$; формула даёт ${\displaystyle 0+4/2-1=1}$.
• Прямоугольник ${\displaystyle p\times q}$ со сторонами вдоль осей: ${\displaystyle I=(p-1)(q-1)}$, ${\displaystyle B=2(p+q)}$; формула даёт ${\displaystyle (p-1)(q-1)+(p+q)-1=pq}$ — в точности площадь.
• Прямоугольный треугольник с катетами ${\displaystyle p}$ и ${\displaystyle q}$ вдоль осей: получается как половина прямоугольника ${\displaystyle p\times q}$, разрезанного диагональю. На диагонали лежит ${\displaystyle d=\gcd(p,q)+1}$ узлов (включая концы). Для треугольника: ${\displaystyle B=p+q+d-1=p+q+\gcd(p,q)}$ (минус 1, чтобы не считать дважды вершину прямого угла), ${\displaystyle I={\frac {(p-1)(q-1)-(\gcd(p,q)-1)}{2}}}$; формула даёт ${\displaystyle pq/2}$.
• «Элементарный» треугольник (не содержащий узлов решётки, кроме своих трёх вершин): ${\displaystyle I=0}$, ${\displaystyle B=3}$; формула даёт площадь ${\displaystyle 1/2}$ — минимально возможную ненулевую площадь решётчатого треугольника.
• Невыпуклый пятиугольник с вершинами (0,0), (3,0), (3,2), (1,3), (0,2): периметр состоит из отрезков длин 3, 2, ${\displaystyle {\sqrt {5}}}$, ${\displaystyle {\sqrt {2}}}$, 2. На стороне (3,2)→(1,3) лежит ${\displaystyle \gcd(2,1)+1=2}$ узла (только концы, так как ${\displaystyle \gcd =1}$); аналогично для (1,3)→(0,2). Итого ${\displaystyle B=3+2+1+1+2=9}$, ${\displaystyle I=4}$, площадь ${\displaystyle A=4+4{,}5-1=7{,}5}$, что совпадает с результатом, полученным по формуле шнурования.

Ключевое наблюдаемое свойство обеих частей формулы — их аддитивность: если решётчатый многоугольник ${\displaystyle P}$ разрезан общей стороной на два решётчатых многоугольника ${\displaystyle P_{1}}$ и ${\displaystyle P_{2}}$, то ${\displaystyle A(P)=A(P_{1})+A(P_{2})}$, и величина ${\displaystyle F(P)=I(P)+B(P)/2-1}$ также удовлетворяет ${\displaystyle F(P)=F(P_{1})+F(P_{2})}$. Действительно, узлы на общей стороне до разреза были граничными для ${\displaystyle P}$, а после разреза становятся граничными для обеих частей; внутренние узлы общей стороны (если они есть) становятся граничными для частей. Аккуратный подсчёт показывает, что слагаемые балансируются ровно так, чтобы аддитивность ${\displaystyle F}$ выполнялась.

Отсюда следует стандартная схема доказательства:

1. Любой простой решётчатый многоугольник можно триангулировать на элементарные треугольники — треугольники, не содержащие узлов решётки, кроме своих трёх вершин (то есть с ${\displaystyle I=0}$ и ${\displaystyle B=3}$).
2. Площадь элементарного треугольника равна ${\displaystyle 1/2}$: это следует из того, что удвоенный параллелограмм, составленный из двух его копий, не содержит узлов решётки внутри и на сторонах, кроме четырёх вершин, а потому образует фундаментальную область решётки ${\displaystyle \mathbb {Z} ^{2}}$ и имеет площадь 1.
3. Поскольку ${\displaystyle F=0+3/2-1=1/2}$, формула верна для каждого элементарного треугольника, а по аддитивности — и для всего многоугольника^[6][14][17].

Классическое доказательство, связывающее формулу Пика с формулой Эйлера для плоских графов: ${\displaystyle V-E+F=2}$. Рассмотрим триангуляцию многоугольника ${\displaystyle P}$ на ${\displaystyle T}$ элементарных треугольников; вершинами этого плоского графа служат все узлы решётки, попавшие в ${\displaystyle P}$, — всего ${\displaystyle V=I+B}$. Подсчитаем рёбра двумя способами. Каждый из ${\displaystyle T}$ треугольников имеет 3 стороны, итого ${\displaystyle 3T}$ «сторона-треугольников». Каждое внутреннее ребро входит в два треугольника, а каждое граничное — в один; граничных рёбер ровно ${\displaystyle B}$ (поскольку каждый граничный узел отделён от следующего ровно одним узлом решётки на отрезке). Поэтому ${\displaystyle 3T=2(E-B)+B=2E-B}$, откуда ${\displaystyle E=(3T+B)/2}$. Грани графа — это ${\displaystyle T}$ треугольников плюс одна внешняя грань, итого ${\displaystyle F=T+1}$. Подставляя в формулу Эйлера:

${\displaystyle (I+B)-{\frac {3T+B}{2}}+(T+1)=2\quad \Longrightarrow \quad T=2I+B-2.}$

Площадь многоугольника равна ${\displaystyle A=T/2}$ (так как каждый элементарный треугольник имеет площадь ${\displaystyle 1/2}$), откуда ${\displaystyle A=I+B/2-1}$^[6][14][18].

Формулу можно доказать индукцией по числу сторон многоугольника. База: для треугольника формула проверяется непосредственно (любой решётчатый треугольник либо элементарен, либо разбивается отрезком из вершины на части с меньшим числом сторон). Переход: для многоугольника с ${\displaystyle n\geq 4}$ сторонами существует диагональ, целиком лежащая внутри него (в выпуклом многоугольнике — любая диагональ; в невыпуклом — диагональ из внутренней вершины). Эта диагональ разбивает многоугольник на два с меньшим числом сторон; формула для частей (по предположению индукции) складывается в формулу для целого (по аддитивности).

Формула Пика эквивалентна формуле шнурования (формуле Гаусса) для площади многоугольника по координатам вершин:

${\displaystyle A={\frac {1}{2}}\left|\sum _{i=1}^{n}(x_{i}y_{i+1}-x_{i+1}y_{i})\right|,}$

где суммирование ведётся по всем сторонам с замыканием многоугольника: ${\displaystyle (x_{n+1},y_{n+1})=(x_{1},y_{1})}$. Эквивалентность понимается в следующем смысле: и площадь, и величина ${\displaystyle F(P)=I+B/2-1}$ аддитивны относительно склеивания решётчатых многоугольников по общей стороне, и обе дают ${\displaystyle 1/2}$ для элементарного треугольника (не содержащего узлов решётки, кроме вершин). Поскольку любой решётчатый многоугольник триангулируется на элементарные треугольники, оба выражения совпадают на всяком решётчатом многоугольнике — то есть формула Пика является дискретным аналогом формулы шнурования. Почленного совпадения вкладов отдельных сторон у двух формул нет: согласие возникает лишь после суммирования по всему многоугольнику (его триангуляции). На практике формулы взаимно дополняют друг друга: площадь вычисляют по координатам формулой шнурования, число граничных узлов — как ${\displaystyle B=\sum _{i=1}^{n}\gcd(|x_{i+1}-x_{i}|,\,|y_{i+1}-y_{i}|)}$, а тогда формула Пика даёт число внутренних узлов ${\displaystyle I}$; обратно, зная ${\displaystyle I}$ и ${\displaystyle B}$, площадь находят без координат^[6][19].

Формула Пика допускает интерпретацию в терминах математического анализа: подсчёт узлов решётки внутри многоугольника можно выразить через ряды Фурье, интегралы и производящие функции. В этом подходе каждый узел решётки рассматривается как дельта-функция, а сумма по узлам внутри области представляется интегралом от характеристической функции, разложенной в ряд Фурье; вычисление коэффициентов и применение формулы суммирования Пуассона приводят к формуле Пика как следствию сходимости кратных рядов Фурье^[20]. Комплексно-аналитические методы используют производящие функции для подсчёта решётчатых точек: характеристическая функция области представляется интегралом Коши, а вычеты в полюсах дают вклады от внутренних и граничных узлов. Наиболее систематический аналитический подход даёт теория полиномов Эрхарта, где формула Пика возникает как значение при ${\displaystyle t=1}$ полинома ${\displaystyle L_{P}(t)}$, считающего узлы в $t$-кратном многоугольнике; закон взаимности Эрхарта — Макдональда ${\displaystyle I_{P}(t)=(-1)^{n}L_{P}(-t)}$ показывает, что формула Пика является двумерным случаем глубокого аналитического тождества^[6].

• Методом «без слов». Известно несколько визуальных доказательств, где площадь подсвечивается цветом или разбивается на квадраты и треугольники единичной площади, и соответствие с числом узлов становится очевидным.
• Через теорему о дивергенции (теорему Гаусса — Остроградского). Если каждой решётчатой точке сопоставить единичный квадрат, центрированный в ней, и рассмотреть сумму характеристических функций таких квадратов, пересекающихся с многоугольником, формула возникает из дискретного аналога теоремы о дивергенции.
• Через производящие функции и теорию Эрхарта. Формула Пика естественно возникает как значение при ${\displaystyle t=1}$ полинома Эрхарта ${\displaystyle L(P,t)=At^{2}+{\frac {B}{2}}t+1}$, считающего узлы решётки в ${\displaystyle t}$-кратном многоугольнике.

Если область ограничена внешним решётчатым контуром и содержит ${\displaystyle h}$ попарно непересекающихся решётчатых «дырок» (каждая дырка — решётчатый многоугольник, узлы на её границе не считаются внутренними), то площадь равна^[6]

${\displaystyle A=I+{\frac {B}{2}}+h-1.}$

Здесь ${\displaystyle I}$ — число узлов строго внутри области (то есть вне дырок), ${\displaystyle B}$ — суммарное число узлов на всех границах (внешней и внутренних). Свободный член ${\displaystyle h-1}$ связан с эйлеровой характеристикой области: для односвязного многоугольника ${\displaystyle \chi =1}$, а для многоугольника с ${\displaystyle h}$ дырками ${\displaystyle \chi =1-h}$. Формула записывается в едином виде

${\displaystyle A=I+{\frac {B}{2}}-\chi .}$

В размерностях 3 и выше прямого аналога формулы Пика не существует. В 1957 году Джон Рив построил семейство тетраэдров, демонстрирующих принципиальную невозможность такой формулы. Тетраэдр Рива ${\displaystyle T_{r}}$ — это тетраэдр с вершинами ${\displaystyle (0,0,0),\ (1,0,0),\ (0,1,0),\ (1,1,r)}$, где ${\displaystyle r}$ — целое положительное число. Все четыре вершины лежат в узлах решётки ${\displaystyle \mathbb {Z} ^{3}}$. Можно проверить, что:

• на рёбрах тетраэдра нет других узлов решётки, кроме вершин;
• строго внутри тетраэдра также нет узлов решётки.

Таким образом, при любом ${\displaystyle r}$ имеем ${\displaystyle I=0}$ и ${\displaystyle B=4}$, тогда как объём тетраэдра равен ${\displaystyle V=r/6}$ и растёт с ростом ${\displaystyle r}$. Следовательно, никакой формулы вида ${\displaystyle V=f(I,B)}$ в трёхмерном пространстве быть не может^[4][6].

Положительные результаты в высших размерностях существуют для специальных классов многогранников — например, для симплициальных многогранников (у которых все грани — симплексы) или для многогранников с дополнительной структурой^[21][22].

Правильным и полным обобщением формулы Пика на произвольную размерность является теория полиномов Эрхарта, разработанная французским математиком Эженом Эрхартом в начале 1960-х годов. Пусть ${\displaystyle P}$ — выпуклый решётчатый многогранник в ${\displaystyle \mathbb {R} ^{n}}$. Для натурального числа ${\displaystyle t}$ обозначим через ${\displaystyle L(P,t)}$ количество узлов решётки ${\displaystyle \mathbb {Z} ^{n}}$, содержащихся в раздутом многограннике ${\displaystyle tP=\{tx:x\in P\}}$. Эрхарт доказал, что функция ${\displaystyle L(P,t)}$ является многочленом от ${\displaystyle t}$ степени ${\displaystyle n}$^[5][6]:

${\displaystyle L(P,t)=c_{n}t^{n}+c_{n-1}t^{n-1}+\dots +c_{1}t+c_{0}.}$

Для двумерного выпуклого многоугольника (${\displaystyle n=2}$) полином Эрхарта имеет вид:

${\displaystyle L(P,t)=A\cdot t^{2}+{\frac {B}{2}}\cdot t+1,}$

где ${\displaystyle A}$ — площадь, ${\displaystyle B}$ — число граничных узлов. При ${\displaystyle t=1}$ получаем ${\displaystyle L(P,1)=I+B=A+B/2+1}$, откуда немедленно следует формула Пика: ${\displaystyle A=I+B/2-1}$.

В общем случае коэффициенты имеют геометрический смысл:

• старший коэффициент ${\displaystyle c_{n}}$ равен объёму многогранника ${\displaystyle P}$;
• коэффициент ${\displaystyle c_{n-1}}$ пропорционален суммарному объёму его граней размерности ${\displaystyle n-1}$;
• свободный член ${\displaystyle c_{0}=1}$ совпадает с эйлеровой характеристикой многогранника (теорема Эрхарта — Макдональда)^[23].

Структурная причина появления эйлеровой характеристики в формуле Пика — закон взаимности для полиномов Эрхарта (взаимность Эрхарта — Макдональда), доказанный в общем виде Макдональдом^[24]: для ${\displaystyle n}$-мерного решётчатого многогранника ${\displaystyle P}$ число ${\displaystyle I_{P}(t)}$ узлов решётки, лежащих строго внутри кратного многогранника ${\displaystyle tP}$, выражается через тот же полином Эрхарта со знаком ${\displaystyle (-1)^{n}}$:

${\displaystyle I_{P}(t)=(-1)^{n}L_{P}(-t).}$

При ${\displaystyle n=2}$, подставляя ${\displaystyle L_{P}(t)=At^{2}+{\tfrac {B}{2}}t+1}$, получаем ${\displaystyle I=A-{\tfrac {B}{2}}+1}$, то есть в точности формулу Пика ${\displaystyle A=I+{\tfrac {B}{2}}-1}$; для области с ${\displaystyle h}$ дырками тот же выклад с постоянным членом ${\displaystyle \chi }$ даёт ${\displaystyle A=I+{\tfrac {B}{2}}-\chi }$. Иными словами, формула Пика (включая обобщение на многоугольники с дырками) является двумерным случаем закона взаимности, а свободный член полинома Эрхарта — это эйлерова характеристика: ${\displaystyle L_{P}(0)=\chi (P)}$.

Сам по себе закон взаимности не восстанавливает объём по одному лишь набору ${\displaystyle (I,B)}$ в размерностях ${\displaystyle \geq 3}$ — это невозможно по контрпримерам Рива. Тем не менее Макдональд показал, что формулы «пикова типа» для трёхмерных решётчатых многогранников возможны, если привлекать дополнительные решётчатые характеристики (помимо узлов самого многогранника — данные о его гранях и сечениях)^[25]; в размерности два эти соотношения сводятся к обычной формуле Пика.

Формула Пика сохраняет силу для любой плоской решётки (не обязательно целочисленной), если площадь измерять в единицах, равных площади фундаментальной области этой решётки^[6]. В частности, для решётки, порождённой векторами ${\displaystyle \mathbf {v} _{1}}$ и ${\displaystyle \mathbf {v} _{2}}$, формула принимает вид

${\displaystyle A(P)=\left(I(P)+{\frac {B(P)}{2}}-1\right)\cdot |\det(\mathbf {v} _{1},\mathbf {v} _{2})|}$

(площадь фундаментальной области решётки равна ${\displaystyle |\det(\mathbf {v} _{1},\mathbf {v} _{2})|}$ — это её определитель в смысле геометрии чисел^[26]).

Теорема Минковского утверждает, что центрально-симметричное выпуклое тело, объём которого больше ${\displaystyle 2^{n}\det(\Lambda )}$, содержит ненулевую точку решётки ${\displaystyle \Lambda }$^[26][27]. Формула Пика даёт точное выражение для площади двумерного выпуклого тела через количество таких точек, и в двумерном случае из неё могут быть выведены различные следствия, связанные с задачами геометрии чисел^[6][26].

Формула Пика — один из классических инструментов геометрических кружков и олимпиад: площадь сложной решётчатой фигуры находится простым подсчётом узлов, без координат, тригонометрии или интегрирования. На её материале строятся занятия с геобордами, клетчатой бумагой и досками для рисования. В частности, формула позволяет быстро отвечать на вопрос: «какую минимальную ненулевую площадь может иметь решётчатый треугольник?» (ответ: ${\displaystyle 1/2}$) или «сколько целочисленных точек может лежать внутри круга радиуса ${\displaystyle R}$?».

Формула даёт быстрый (${\displaystyle O(n)}$ по числу вершин) способ вычисления площади решётчатого многоугольника, если известны координаты вершин: достаточно посчитать узлы на сторонах (через НОД) и внутри (через алгоритм заливки). В растровой графике и обработке изображений площадь пиксельного многоугольника оценивается по числу внутренних пикселей и пикселей границы, что является прямой дискретной аналогией формулы Пика.

Подсчёт целых точек в многогранниках — ядро целочисленного программирования и комбинаторной геометрии. Формула Пика — двумерный базовый случай общей теории Эрхарта и таких алгоритмов, как алгоритм Барвинка для подсчёта точек в выпуклых многогранниках.

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

В ГИС при работе с растровыми данными площадь региона, заданного маской пикселей, естественно оценивается по формуле Пика: внутренние пиксели играют роль узлов ${\displaystyle I}$, граничные — узлов ${\displaystyle B}$.