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

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

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

Определение

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

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

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

- количество точек решетки, содержащихся в многограннике $tP$ . Эрхарт показал в 1962 году, что $L$ рациональный многочлен степени $d$ в $т$ , т.е. существуют рациональное число ${ 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) }

для всех положительных целых чисел $т$ .

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

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

куда $d$ это размер $п$ . Этот результат известен как взаимность Эрхарта – Макдональда.^[1]

Примеры

Это вторая дилатация,

{ displaystyle t = 2}

, единичной площади. Он имеет девять целых точек.

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

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

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

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

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

Много других фигуральные числа можно выразить в виде полиномов Эрхарта. Например, квадратные пирамидальные числа задаются полиномами Эрхарта квадратная пирамида с целым единичным квадратом в основании и высотой единица; многочлен Эрхарта в этом случае равен $1 / 6 (т + 1)(т + 2)(2 т + 3)$ .^[4]

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

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

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

куда ${ 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 (п, т)$ это квазиполином в $т$ . Как и в случае целочисленных многогранников, имеет место взаимность Эрхарта – Макдональда, т. Е.

{ displaystyle L ( operatorname {int} (P), t) = (- 1) ^ {n} L (P, -t).}

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

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

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

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

Если $п$ является закрыто (т.е. граничные грани принадлежат $п$ ), некоторые из коэффициентов $L (п, т)$ есть простая интерпретация:

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

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

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

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

Ульрих Бетке и Мартин Кнезер^[6] установил следующую характеризацию коэффициентов Эрхарта. Функциональный ${ 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$ -мерный многогранник $п$ в качестве

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

Этот ряд можно выразить как рациональная функция. В частности, Эрхарт доказал (1962)^{[нужна цитата ]} что существуют комплексные числа ${ 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}$ .

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

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

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

{ 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} ^ {*}}$ по-прежнему являются неотрицательными целыми числами.^[8]^[9]

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

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

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

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

{ 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]}$ это Число Стирлинга первого рода. Существуют и нижние оценки.^[11]

Торическое разнообразие

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

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

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

Обобщения

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

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

Смотрите также

Примечания

^ Макдональд, Ян Г. (1971). «Полиномы, связанные с конечными клеточными комплексами» (PDF). Журнал Лондонского математического общества. 2 (1): 181–192. Дои:10.1112 / jlms / s2-4.1.181.
^ Де Лоэра, Рамбау и Сантос (2010)
^ Матар (2010)
^ Beck et al. (2005).
^ Бек, Матиас; Робинс, Синай (2007). Дискретное вычисление непрерывного. Нью-Йорк: Спрингер. стр.46 –47. МИСТЕР 2271992.
^ Бетке, Ульрих; Кнезер, Мартин (1985), "Zerlegungen und Bewertungen von Gitterpolytopen", Журнал für die reine und angewandte Mathematik, 358: 202–208, МИСТЕР 0797683
^ Афанасиадис, Христос А. (2004). "час* -Векторы, многочлены Эйлера и устойчивые многогранники графов ". Электронный журнал комбинаторики. 11 (2).
^ Стэнли, Ричард П. (1980). «Разложения рациональных выпуклых многогранников». Анналы дискретной математики. 6: 333–342. Дои:10.1016 / s0167-5060 (08) 70717-9. ISBN 9780444860484.
^ Бек, Матиас; Соттиль, Франк (январь 2007 г.). «Иррациональные доказательства трех теорем Стэнли». Европейский журнал комбинаторики. 28 (1): 403–409. arXiv:математика / 0501359. Дои:10.1016 / j.ejc.2005.06.003.
^ Бетке, Ульрих; Макмаллен, Питер (1985-12-01). «Решеточные точки в решетчатых многогранниках». Monatshefte für Mathematik. 99 (4): 253–265. Дои:10.1007 / BF01312545. ISSN 1436-5081.
^ Хенк, Мартин; Тагами, Макото (01.01.2009). «Оценки снизу на коэффициенты многочленов Эрхарта». Европейский журнал комбинаторики. 30 (1): 70–83. arXiv:0710.2665. Дои:10.1016 / j.ejc.2008.02.009. ISSN 0195-6698.
^ Браун, Бенджамин; Девелин, Майк (2008). Полиномиальные корни Эрхарта и теорема Стэнли о неотрицательности. Современная математика. 452. Американское математическое общество. С. 67–78. arXiv:математика / 0610399. Дои:10.1090 / conm / 452/08773. ISBN 9780821841730.
^ Хигаситани, Акихиро (2012). "Классификация полиномов Эрхарта интегральных симплексов" (PDF). Протоколы DMTCS: 587–594.
^ Бек, Матиас (январь 2002 г.). «Многомерная взаимность Эрхарта». Журнал комбинаторной теории. Серия А. 97 (1): 187–194. arXiv:математика / 0111331. Дои:10.1006 / jcta.2001.3220.
^ Лисонек, Петр (2007). «Комбинаторные семейства, пронумерованные квазиполиномами». Журнал комбинаторной теории. Серия А. 114 (4): 619–630. Дои:10.1016 / j.jcta.2006.06.013.