Полином Эрхарта

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

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

Определение [ править ]

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

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

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

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

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

для всех положительных целых чисел $t$ . ^[1]

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

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

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

Примеры [ править ]

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

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

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

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{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/6 + т ( т + 1)( 2 )(2 т + 3)$ . ^[5]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ehrhart series Эрхарта editСерия

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

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

Этот ряд можно выразить как рациональную функцию . В частности, Эрхарт доказал (1962), что существуют комплексные числа. $h_{j}^{*}$ , $0\leq j\leq d$ , такой, что ряд Эрхарта $P$ равен ^[1]

\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.

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

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

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

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

\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}}},

где $h_{j}^{*}$ по-прежнему являются неотрицательными целыми числами. ^[10]^[11]

неведущего Границы коэффициента

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

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

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

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

где $\left[{\begin{smallmatrix}n\\k\end{smallmatrix}}\right]$ является числом Стирлинга первого рода . Нижние границы также существуют. ^[13]

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

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

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

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

Обобщения [ править ]

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

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

См. также [ править ]

Ссылки [ править ]

^ Jump up to: Перейти обратно: ^а ^б Эрхарт, Эжен (1962), «О гомотетических рациональных многогранниках в n измерениях», Comptes Rendus de l'Académie des Sciences , 254 : 616–618, MR 0130860
^ Макдональд, Ян Г. (1971), «Полиномы, связанные с конечными клеточными комплексами», Журнал Лондонского математического общества , 2 (1): 181–192, doi : 10.1112/jlms/s2-4.1.181
^ Де Лоэра, Хесус А .; Рамбау, Йорг; Сантос, Франциско (2010), «Полиномы Эрхарта и унимодулярные триангуляции», Триангуляции: структуры для алгоритмов и приложений , Алгоритмы и вычисления в математике, том. 25, Спрингер, с. 475, ISBN 978-3-642-12970-4
^ Матар, Ричард Дж. (2010), Подсчет очков $D_{k}$ и некоторые $A_{k}$ и $E_{k}$ целочисленные решетки внутри гиперкубов , arXiv : 1002.3844 , Bibcode : 2010arXiv1002.3844M
^ Бек, Матиас; Де Лоэра, Хесус А .; Девелин, Майк ; Пфайфл, Джулиан; Стэнли, Ричард П. (2005), «Коэффициенты и корни полиномов Эрхарта», Целые точки в многогранниках — геометрия, теория чисел, алгебра, оптимизация , современная математика, том. 374, Провиденс, Род-Айленд: Американское математическое общество , стр. 15–36, MR 2134759.
^ Бек, Матиас; Робинс, Синай (2007), Дискретное вычисление непрерывного числа: перечисление целочисленных точек в многогранниках , Тексты для студентов по математике , Нью-Йорк: Springer-Verlag, стр. 46–47 , ISBN 978-0-387-29139-0 , МР 2271992
^ Бетке, Ульрих; Кнезер, Мартин (1985), «Разложения и оценки решетчатых многогранников», Журнал чистой и прикладной математики , 358 : 202–208, MR 0797683
^ Стэнли, Ричард (1993), «Свойство монотонности $h$ -векторы и $h^{*}$ -векторы», European Journal of Combinatorics , 14 (3): 251–258, doi : 10.1006/eujc.1993.1028.
^ Афанасиадис, Христос А. (2004), « h *-векторы, эйлеровы полиномы и стабильные многогранники графов» , Электронный журнал комбинаторики , 11 (2), doi : 10.37236/1863
^ Стэнли, Ричард П. (1980), «Разложение рациональных выпуклых многогранников», Annals of Discrete Mathematics , 6 : 333–342, doi : 10.1016/s0167-5060(08)70717-9 , ISBN 9780444860484
^ Бек, Матиас; Соттиле, Франк (январь 2007 г.), «Иррациональные доказательства трех теорем Стэнли», European Journal of Combinatorics , 28 (1): 403–409, arXiv : math/0501359 , doi : 10.1016/j.ejc.2005.06.003 , S2CID 7801569
^ Бетке, Ульрих; МакМаллен, Питер (1985-12-01), «Точки решетки в решетчатых многогранниках», Monthly Books for Mathematics , 99 (4): 253–265, doi : 10.1007/BF01312545 , ISSN 1436-5081 , S2CID 119545615
^ Хенк, Мартин; Тагами, Макото (01 января 2009 г.), «Нижние границы коэффициентов полиномов Эрхарта», Европейский журнал комбинаторики , 30 (1): 70–83, arXiv : 0710.2665 , doi : 10.1016/j.ejc.2008.02. 009 , ISSN 0195-6698 , S2CID 3026293
^ Браун, Бенджамин; Девелин, Майк (2008), Корни полинома Эрхарта и теорема Стэнли о неотрицательности , Современная математика, том. 452, Американское математическое общество , стр. 67–78, arXiv : math/0610399 , doi : 10.1090/conm/452/08773 , ISBN 9780821841730 , S2CID 118496291
^ Хигашитани, Акихиро (2012), «Классификация полиномов Эрхарта интегральных симплексов» (PDF) , DMTCS Proceedings : 587–594
^ Бек, Маттиас (январь 2002 г.), «Многомерная взаимность Эрхарта», Журнал комбинаторной теории , серия A, 97 (1): 187–194, arXiv : math/0111331 , doi : 10.1006/jcta.2001.3220 , S2CID 195227
^ Лисонек, Петр (2007), «Комбинаторные семейства, перечисляемые квазиполиномами», Журнал комбинаторной теории , серия A, 114 (4): 619–630, doi : 10.1016/j.jcta.2006.06.013

Дальнейшее чтение [ править ]

Диас, Рикардо; Робинс, Синай (1996), «Полином Эрхарта решёточного n -симплекса», Электронные объявления об исследованиях Американского математического общества , 2 : 1–6, doi : 10.1090/S1079-6762-96-00001-7 , MR 1405963 . Представляет подход к анализу Фурье и дает ссылки на другие статьи по теме.
Мустацэ, Мирча (февраль 2005 г.), «Полиномы Эрхарта», Конспект лекций по торическим многообразиям .

[ehrhart-1] Jump up to: Перейти обратно: ^а ^б Эрхарт, Эжен (1962), «О гомотетических рациональных многогранниках в n измерениях», Comptes Rendus de l'Académie des Sciences , 254 : 616–618, MR 0130860

[2] Макдональд, Ян Г. (1971), «Полиномы, связанные с конечными клеточными комплексами», Журнал Лондонского математического общества , 2 (1): 181–192, doi : 10.1112/jlms/s2-4.1.181

[3] Де Лоэра, Хесус А .; Рамбау, Йорг; Сантос, Франциско (2010), «Полиномы Эрхарта и унимодулярные триангуляции», Триангуляции: структуры для алгоритмов и приложений , Алгоритмы и вычисления в математике, том. 25, Спрингер, с. 475, ISBN 978-3-642-12970-4

[4] Матар, Ричард Дж. (2010), Подсчет очков $D_{k}$ и некоторые $A_{k}$ и $E_{k}$ целочисленные решетки внутри гиперкубов , arXiv : 1002.3844 , Bibcode : 2010arXiv1002.3844M

[5] Бек, Матиас; Де Лоэра, Хесус А .; Девелин, Майк ; Пфайфл, Джулиан; Стэнли, Ричард П. (2005), «Коэффициенты и корни полиномов Эрхарта», Целые точки в многогранниках — геометрия, теория чисел, алгебра, оптимизация , современная математика, том. 374, Провиденс, Род-Айленд: Американское математическое общество , стр. 15–36, MR 2134759.

[MR2271992-6] Бек, Матиас; Робинс, Синай (2007), Дискретное вычисление непрерывного числа: перечисление целочисленных точек в многогранниках , Тексты для студентов по математике , Нью-Йорк: Springer-Verlag, стр. 46–47 , ISBN 978-0-387-29139-0 , МР 2271992

[7] Бетке, Ульрих; Кнезер, Мартин (1985), «Разложения и оценки решетчатых многогранников», Журнал чистой и прикладной математики , 358 : 202–208, MR 0797683

[8] Стэнли, Ричард (1993), «Свойство монотонности $h$ -векторы и $h^{*}$ -векторы», European Journal of Combinatorics , 14 (3): 251–258, doi : 10.1006/eujc.1993.1028.

[9] Афанасиадис, Христос А. (2004), « h *-векторы, эйлеровы полиномы и стабильные многогранники графов» , Электронный журнал комбинаторики , 11 (2), doi : 10.37236/1863

[10] Стэнли, Ричард П. (1980), «Разложение рациональных выпуклых многогранников», Annals of Discrete Mathematics , 6 : 333–342, doi : 10.1016/s0167-5060(08)70717-9 , ISBN 9780444860484

[11] Бек, Матиас; Соттиле, Франк (январь 2007 г.), «Иррациональные доказательства трех теорем Стэнли», European Journal of Combinatorics , 28 (1): 403–409, arXiv : math/0501359 , doi : 10.1016/j.ejc.2005.06.003 , S2CID 7801569

[12] Бетке, Ульрих; МакМаллен, Питер (1985-12-01), «Точки решетки в решетчатых многогранниках», Monthly Books for Mathematics , 99 (4): 253–265, doi : 10.1007/BF01312545 , ISSN 1436-5081 , S2CID 119545615

[13] Хенк, Мартин; Тагами, Макото (01 января 2009 г.), «Нижние границы коэффициентов полиномов Эрхарта», Европейский журнал комбинаторики , 30 (1): 70–83, arXiv : 0710.2665 , doi : 10.1016/j.ejc.2008.02. 009 , ISSN 0195-6698 , S2CID 3026293

[14] Браун, Бенджамин; Девелин, Майк (2008), Корни полинома Эрхарта и теорема Стэнли о неотрицательности , Современная математика, том. 452, Американское математическое общество , стр. 67–78, arXiv : math/0610399 , doi : 10.1090/conm/452/08773 , ISBN 9780821841730 , S2CID 118496291

[15] Хигашитани, Акихиро (2012), «Классификация полиномов Эрхарта интегральных симплексов» (PDF) , DMTCS Proceedings : 587–594

[16] Бек, Маттиас (январь 2002 г.), «Многомерная взаимность Эрхарта», Журнал комбинаторной теории , серия A, 97 (1): 187–194, arXiv : math/0111331 , doi : 10.1006/jcta.2001.3220 , S2CID 195227

[17] Лисонек, Петр (2007), «Комбинаторные семейства, перечисляемые квазиполиномами», Журнал комбинаторной теории , серия A, 114 (4): 619–630, doi : 10.1016/j.jcta.2006.06.013

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]