Многочлен Эрхарта - Ehrhart polynomial

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

Эти полиномы названы в честь Эжена Эрхарта , изучавшего их в 1960-х годах.

Определение

Неформально, если $P$ - многогранник , а $tP$ - многогранник, образованный расширением $P$ в $t раз$ в каждом измерении, то $L (P, t)$ - это количество целочисленных точек решетки в $tP$ .

Более формально, рассмотрим решетку в евклидовом пространстве и $д$ - мерный многогранник $P$ в с тем свойством , что все вершины многогранника являются точками решетки. (Типичным примером является многогранник, у которого все вершины имеют целочисленные координаты.) Для любого положительного целого числа $t$ пусть $tP$ будет $t-$ кратным расширением $P$ (многогранник, образованный умножением каждой координаты вершины в базисе решетки, в $t раз$ ), и пусть ${\ Displaystyle {\ mathcal {L}}}$ ${\ Displaystyle \ mathbb {R} ^ {п}}$ ${\ Displaystyle \ mathbb {R} ^ {п}}$ ${\ Displaystyle {\ mathcal {L}} = \ mathbb {Z} ^ {п}}$

{\ Displaystyle L (P, t) = \ # \ left (tP \ cap {\ mathcal {L}} \ right)}

- количество узлов решетки, содержащихся в многограннике $tP$ . Эрхарт показал в 1962 году , что $L$ является рациональной многочлен степени $д$ в $т$ , т.е. существуют рациональные числа , такие , что: ${\ Displaystyle L_ {0} (P), \ точки, L_ {d} (P)}$

{\ Displaystyle L (P, t) = L_ {d} (P) t ^ {d} + L_ {d-1} (P) t ^ {d-1} + \ cdots + L_ {0} (P) }

для всех натуральных чисел $t$ .

Полином Эрхарта внутренней части замкнутого выпуклого многогранника $P$ можно вычислить как:

{\ Displaystyle L (\ Operatorname {int} (P), t) = (- 1) ^ {d} L (P, -t),}

где $d$ есть размерность $P$ . Этот результат известен как взаимность Эрхарта – Макдональда.

Примеры

Это вторая дилатация единичного квадрата. Он имеет девять целых точек.

{\ displaystyle t = 2}

Пусть $P$ - $d$ -мерный единичный гиперкуб , вершинами которого являются точки целочисленной решетки, все координаты которых равны 0 или 1. В терминах неравенств,

{\ displaystyle P = \ left \ {x \ in \ mathbb {R} ^ {d}: 0 \ leq x_ {i} \ leq 1; 1 \ leq i \ leq d \ right \}.}

Тогда $t-$ кратное расширение $P$ представляет собой куб со стороной $t$ , содержащий $(t + 1) d$ целых точек. То есть полином Эрхарта гиперкуба равен $L (P, t) = (t + 1) d$ . Кроме того, если мы оценим $L (P, t)$ как отрицательные целые числа, то

{\ Displaystyle L (P, -t) = (- 1) ^ {d} (t-1) ^ {d} = (- 1) ^ {d} L (\ operatorname {int} (P), t) ,}

как и следовало ожидать от взаимности Эрхарта-Макдональда.

Многие другие фигурные числа можно выразить полиномами Эрхарта. Например, квадратные пирамидальные числа задаются полиномами Эрхарта квадратной пирамиды с целым единичным квадратом в качестве основания и с высотой единица; полином Эрхарта в этом случае равен $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} 1/6( t + 1) ( t + 2) (2 t + 3)$ .

Квазиполиномы Эрхарта

Пусть $P$ - рациональный многогранник. Другими словами, предположим

{\ displaystyle P = \ left \ {x \ in \ mathbb {R} ^ {d}: Ax \ leq b \ right \},}

где и (эквивалентно, $P$ - выпуклая оболочка конечного числа точек в ). Тогда определим ${\ displaystyle A \ in \ mathbb {Q} ^ {k \ times d}}$ ${\ displaystyle b \ in \ mathbb {Q} ^ {k}.}$ ${\ displaystyle \ mathbb {Q} ^ {d}.}$

{\ Displaystyle L (P, t) = \ # \ left (\ left \ {x \ in \ mathbb {Z} ^ {n}: Ax \ leq tb \ right \} \ right).}

В этом случае $L (P, t)$ - квазиполином по $t$ . Как и в случае с целочисленными многогранниками, имеет место взаимность Эрхарта – Макдональда, т. Е.

{\ Displaystyle L (\ Operatorname {int} (P), t) = (- 1) ^ {n} L (P, -t).}

Примеры квазиполиномов Эрхарта

Пусть $P$ - многоугольник с вершинами (0,0), (0,2), (1,1) и (3/2, 0). Количество целых точек в $tP$ будет подсчитано квазиполиномом

{\ Displaystyle L (P, t) = {\ frac {7t ^ {2}} {4}} + {\ frac {5t} {2}} + {\ frac {7 + (- 1) ^ {t} } {8}}.}

Интерпретация коэффициентов

Если $P$ будет закрыт (т.е. граничные грани принадлежат $Р$ ), некоторые из коэффициентов $L (P, T)$ имеют простую интерпретацию:

старший коэффициент, , равен $г$ - мерный объем из $Р$ , деленный на $D$ $($ $L$ $)$ (см решетки для объяснения содержания или кообъем $г$ $($ $L$ $)$ решетки); ${\ displaystyle L_ {d} (P)}$

второй коэффициент, может быть вычислен следующим образом : решетка $L$ индуцирует решетку $L$ $F$ на любой грани $F$ из $Р$ ; возьмите $($ $d$ $- 1)$ -мерный объем $F$ , разделите на $2$ $d$ $($ $L$ $F$ $)$ и сложите эти числа для всех граней $P$ ; ${\ Displaystyle L_ {d-1} (P)}$

постоянный коэффициент $0$ является эйлерова характеристика из $P$ . Когда $Р$ является замкнутым выпуклым многогранник, . ${\ displaystyle L_ {0} (P) = 1}$

Теорема Бетке – Кнезера.

Ульрих Бетке и Мартин Кнезер установили следующую характеристику коэффициентов Эрхарта. Функционал определен на целочисленных многогранников является и инвариантно перевод оценка , если и только если существуют действительные числа такие , что ${\ displaystyle Z}$ ${\ Displaystyle \ OperatorName {SL} (п, \ mathbb {Z})}$ ${\ displaystyle c_ {0}, \ ldots, c_ {n}}$

{\ displaystyle Z = c_ {0} L_ {0} + \ cdots + c_ {n} L_ {n}.}

Серия Эрхарт

Мы можем определить производящую функцию для полинома Эрхарта целого $d$ -мерного многогранника $P$ как

{\ displaystyle \ operatorname {Ehr} _ {P} (z) = \ sum _ {t \ geq 0} L (P, t) z ^ {t}.}

Этот ряд можно выразить как рациональную функцию . В частности, Эрхарт доказал (1962) , что существуют комплексные числа , такие , что ряд Эрхарт из $P$ является ${\ displaystyle h_ {j} ^ {*}}$ ${\ Displaystyle 0 \ Leq J \ Leq D}$

{\ displaystyle \ operatorname {Ehr} _ {P} (z) = {\ frac {\ sum _ {j = 0} ^ {d} h_ {j} ^ {\ ast} (P) z ^ {j}} {(1-z) ^ {d + 1}}}, \ qquad \ sum _ {j = 0} ^ {d} h_ {j} ^ {\ ast} (P) \ neq 0.}

Кроме того, теорема Ричарда П. Стэнли о неотрицательности утверждает, что при данных гипотезах будут неотрицательные целые числа, для . ${\ displaystyle h_ {j} ^ {*}}$ ${\ Displaystyle 0 \ Leq J \ Leq D}$

Другой результат Стэнли показывает, что если $P$ - решетчатый многогранник, содержащийся в $Q$ , то для всех $j$ . -Векторных вообще говоря, не унимодально, но всякий раз , когда он симметричен, а многогранник имеет регулярную унимодальную триангуляцию. ${\ displaystyle h_ {j} ^ {*} (P) \ leq h_ {j} ^ {*} (Q)}$ ${\ displaystyle h ^ {*}}$

Ряды Эрхарта для рациональных многогранников

Как и в случае многогранников с целыми вершинами, для рационального многогранника определяется ряд Эрхарта. Для d- мерного рационального многогранника $P$ , где $D$ - наименьшее целое число, такое что $DP$ - целочисленный многогранник ( $D$ называется знаменателем $P$ ), то выполняется

{\ displaystyle \ operatorname {Ehr} _ {P} (z) = \ sum _ {t \ geq 0} L (P, t) z ^ {t} = {\ frac {\ sum _ {j = 0} ^ {D (d + 1)} h_ {j} ^ {\ ast} (P) z ^ {j}} {\ left (1-z ^ {D} \ right) ^ {d + 1}}},}

где по- прежнему неотрицательные целые числа. ${\ displaystyle h_ {j} ^ {*}}$

Границы невыставляющих коэффициентов

Нежелательные коэффициенты многочлена в представлении ${\ displaystyle c_ {0}, \ dots, c_ {d-1}}$

{\ displaystyle L (P, t) = \ sum _ {r = 0} ^ {d} c_ {r} t ^ {r}}

может быть ограничено сверху:

{\ displaystyle c_ {r} \ leq (-1) ^ {dr} {\ begin {bmatrix} d \\ r \ end {bmatrix}} c_ {d} + {\ frac {(-1) ^ {dr- 1}} {(d-1)!}} {\ Begin {bmatrix} d \\ r + 1 \ end {bmatrix}}}

где - число Стирлинга первого рода . Существуют и нижние оценки. ${\ displaystyle \ left [{\ begin {smallmatrix} п \\ k \ end {smallmatrix}} \ right]}$

Торическая разновидность

Случай и этих утверждений дает теорему Пика . Формулы для других коэффициентов получить гораздо труднее; Todd классов из торических многообразий , то Римана-Роха теорема , а также анализ Фурье , были использованы для этой цели. ${\ Displaystyle п = d = 2}$ ${\ displaystyle t = 1}$

Если $X$ - торическое многообразие, соответствующее нормальному вееру $P$ , то $P$ определяет обильное линейное расслоение на $X$ , а многочлен Эрхарта $P$ совпадает с многочленом Гильберта этого линейного расслоения.

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

Обобщения

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

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

Languages

In other projects