Ehrhartův polynom - Ehrhart polynomial

v matematika, an integrální polytop má přidružené Ehrhartův polynom který kóduje vztah mezi objemem a polytop a počet celočíselné body polytop obsahuje. Na teorii Ehrhartových polynomů lze pohlížet jako na vícerozměrné zobecnění Pickova věta v Euklidovské letadlo.

Tyto polynomy jsou pojmenovány po Eugène Ehrhart kteří je studovali v 60. letech.

Definice

Neformálně, pokud $P$ je polytop, a $tP$ je polytop vytvořený roztažením $P$ faktorem $t$ tedy v každé dimenzi $L (P, t)$ je počet celočíselná mřížka body v $tP$ .

Více formálně zvažte a mříž ${ displaystyle { mathcal {L}}}$ v Euklidovský prostor ${ displaystyle mathbb {R} ^ {n}}$ a a $d$ -dimenzionální polytop $P$ v ${ displaystyle mathbb {R} ^ {n}}$ s vlastností, že všechny vrcholy polytopu jsou body mřížky. (Běžným příkladem je ${ displaystyle { mathcal {L}} = mathbb {Z} ^ {n}}$ a mnohostěn, pro který mají všechny vrcholy celé číslo souřadnice.) Pro jakékoli kladné celé číslo $t$ , nechť $tP$ být $t$ -násobná dilatace $P$ (Polytop vytvořený vynásobením každé souřadnice vrcholu na základě mřížky faktorem $t$ ) a nechte

{ displaystyle L (P, t) = # vlevo (tP cap { mathcal {L}} vpravo)}

je počet mřížových bodů obsažených v mnohostěnu $tP$ . Ehrhart to v roce 1962 ukázal $L$ je racionální polynomiální stupně $d$ v $t$ , tj. existují racionální čísla ${ displaystyle L_ {0} (P), tečky, L_ {d} (P)}$ takové, že:

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

pro všechna kladná celá čísla $t$ .

Ehrhartův polynom z interiér uzavřeného konvexního mnohostěnu $P$ lze vypočítat jako:

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

kde $d$ je rozměr $P$ . Tento výsledek je znám jako Ehrhart-Macdonaldova vzájemnost.^[1]

Příklady

Toto je druhý dilatátor,

{ displaystyle t = 2}

, jednotkového čtverce. Má devět celočíselných bodů.

Nechat $P$ být $d$ -dimenzionální jednotka hyperkrychle jejichž vrcholy jsou celočíselné mřížové body, jejichž všechny souřadnice jsou 0 nebo 1. Pokud jde o nerovnosti,

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

Pak $t$ -násobná dilatace $P$ je kostka s délkou strany $t$ , obsahující $(t + 1) d$ celočíselné body. To znamená, že Ehrhartův polynom hyperkrychle je $L (P, t) = (t + 1) d$ .^[2]^[3] Navíc, pokud budeme hodnotit $L (P, t)$ při záporných celých číslech

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

jak bychom očekávali od Ehrhart-Macdonaldovy vzájemnosti.

Mnoho jiných figurativní čísla lze vyjádřit jako Ehrhartovy polynomy. Například čtvercová pyramidová čísla jsou dány Ehrhartovými polynomy a čtvercová pyramida s čtvercem celých jednotek jako základnou a s výškou jedna; Ehrhartův polynom v tomto případě je $1 / 6 (t + 1)(t + 2)(2 t + 3)$ .^[4]

Ehrhartovy kvazi-polynomy

Nechat $P$ být racionálním polytopem. Jinými slovy, předpokládejme

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

kde ${ displaystyle A in mathbb {Q} ^ {k krát d}}$ a ${ displaystyle b in mathbb {Q} ^ {k}.}$ (Ekvivalentně, $P$ je konvexní obal konečně mnoha bodů ${ displaystyle mathbb {Q} ^ {d}.}$ ) Poté definujte

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

V tomto případě, $L (P, t)$ je kvazi-polynom v $t$ . Stejně jako u integrálních polytopů platí Ehrhart-Macdonaldova vzájemnost, tj.

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

Příklady Ehrhartových kvazi-polynomů

Nechat $P$ být mnohoúhelník s vrcholy (0,0), (0,2), (1,1) a (3/2, 0). Počet celočíselných bodů v $tP$ budou počítány kvazi-polynomem ^[5]

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

Interpretace koeficientů

Li $P$ je Zavřeno (tj. hraniční plochy patří $P$ ), některé z koeficientů $L (P, t)$ mít snadnou interpretaci:

přední koeficient, ${ displaystyle L_ {d} (P)}$ , se rovná $d$ -dimenzionální objem z $P$ , děleno $d (L)$ (vidět mříž pro vysvětlení obsahu nebo obsahu $d (L)$ mřížky);

druhý koeficient, ${ displaystyle L_ {d-1} (P)}$ , lze vypočítat takto: mřížka $L$ indukuje mřížku $L F$ na jakékoli tváři $F$ z $P$ ; vzít $(d - 1)$ -rozměrný objem $F$ , vydělit $2 d (L F)$ a přidejte tato čísla pro všechny tváře uživatele $P$ ;

konstantní koeficient $A 0$ je Eulerova charakteristika z $P$ . Když $P$ je uzavřený konvexní polytop, ${ displaystyle L_ {0} (P) = 1}$ .

Věta Betke – Kneser

Ulrich Betke a Martin Kneser^[6] stanovil následující charakterizaci Ehrhartových koeficientů. Funkční ${ displaystyle Z}$ definovaný na integrálních polytopech je ${ displaystyle operatorname {SL} (n, mathbb {Z})}$ a překlad neměnný ocenění právě když existují reálná čísla ${ displaystyle c_ {0}, ldots, c_ {n}}$ takhle

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

Ehrhartova řada

Můžeme definovat a generující funkce pro Ehrhartův polynom integrálu $d$ -dimenzionální polytop $P$ tak jako

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

Tuto řadu lze vyjádřit jako a racionální funkce. Konkrétně prokázal Ehrhart (1962)^{[Citace je zapotřebí ]} že existují komplexní čísla ${ displaystyle h_ {j} ^ {*}}$ , ${ displaystyle 0 leq j leq d}$ , takže Ehrhartova řada $P$ je

{ 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.}

Dodatečně, Richard P. Stanley Věta o negativitě uvádí, že za daných hypotéz ${ displaystyle h_ {j} ^ {*}}$ bude nezáporná celá čísla, pro ${ displaystyle 0 leq j leq d}$ .

Další výsledek Stanleyho^{[Citace je zapotřebí ]} ukazuje, že pokud $P$ je příhradový polytop obsažený v $Q$ , pak ${ displaystyle h_ {j} ^ {*} (P) leq h_ {j} ^ {*} (Q)}$ pro všechny $j$ . The ${ displaystyle h ^ {*}}$ -vector obecně není unimodální, ale je vždy, když je symetrický, a mnohostěn má pravidelnou unimodální triangulaci.^[7]

Ehrhartova řada pro racionální polytopy

Stejně jako v případě polytopů s celočíselnými vrcholy lze definovat Ehrhartovu řadu pro racionální polytop. Pro d-dimenzionální racionální polytop $P$ , kde $D$ je nejmenší celé číslo takové, že $DP$ je celé číslo mnohostěn ( $D$ se nazývá jmenovatel $P$ ), pak jeden má

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

Kde ${ displaystyle h_ {j} ^ {*}}$ jsou stále nezáporná celá čísla.^[8]^[9]

Meze nevodícího koeficientu

Polynomiální nevedoucí koeficienty ${ displaystyle c_ {0}, tečky, c_ {d-1}}$ v reprezentaci

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

může být horní hranice:^[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}}}

kde ${ displaystyle left [{ begin {smallmatrix} n k end {smallmatrix}} right]}$ je Stirlingovo číslo prvního druhu. Existují také dolní hranice.^[11]

Torická odrůda

Pouzdro ${ displaystyle n = d = 2}$ a ${ displaystyle t = 1}$ z těchto výroků výnosy Pickova věta. Vzorec pro ostatní koeficienty je mnohem těžší získat; Toddovy třídy z torické odrůdy, Riemann – Rochova věta stejně jako Fourierova analýza byly použity k tomuto účelu.

Li $X$ je torická odrůda odpovídá normálnímu ventilátoru $P$ , pak $P$ definuje dostatek svazku řádků na $X$ a Ehrhartův polynom z $P$ se shoduje s Hilbertův polynom tohoto svazku řádků.

Ehrhartovy polynomy lze studovat pro jejich vlastní příčinu. Dalo by se například klást otázky týkající se kořenů Ehrhartova polynomu.^[12] Někteří autoři se dále zabývali otázkou, jak lze tyto polynomy klasifikovat.^[13]

Zobecnění

Je možné studovat počet celočíselných bodů v mnohostěnu $P$ pokud rozšíříme některé aspekty $P$ ale ne ostatní. Jinými slovy, člověk by chtěl znát počet celočíselných bodů v semi-dilatovaných polytopech. Ukazuje se, že taková funkce počítání bude tzv. Vícerozměrný kvazi-polynom. Pro takovou funkci počítání bude také platit Ehrhartova věta o vzájemnosti.^[14]

Počítání počtu celých bodů v semi-dilatacích polytopů má aplikace^[15] při výčtu počtu různých pitev pravidelných polygonů a počtu neizomorfních neomezených kódů, konkrétního druhu kódu v oblasti teorie kódování.

Viz také

Poznámky

^ Macdonald, Ian G. (1971). "Polynomy spojené s komplexy konečných buněk" (PDF). Journal of the London Mathematical Society. 2 (1): 181–192. doi:10.1112 / jlms / s2-4.1.181.
^ De Loera, Rambau a Santos (2010)
^ Mathar (2010)
^ Beck a kol. (2005).
^ Beck, Matthias; Robins, Sinai (2007). Diskrétní výpočet kontinuity. New York: Springer. str.46 –47. PAN 2271992.
^ Betke, Ulrich; Kneser, Martin (1985), „Zerlegungen und Bewertungen von Gitterpolytopen“, Journal für die reine und angewandte Mathematik, 358: 202–208, PAN 0797683
^ Athanasiadis, Christos A. (2004). "h* -Vektory, Euleriánské polynomy a stabilní polytopy grafů ". Electronic Journal of Combinatorics. 11 (2).
^ Stanley, Richard P. (1980). "Rozklady racionálních konvexních polytopů". Annals of Discrete Mathematics. 6: 333–342. doi:10.1016 / s0167-5060 (08) 70717-9. ISBN 9780444860484.
^ Beck, Matthias; Sottile, Frank (leden 2007). „Iracionální důkazy pro tři Stanleyho věty“. European Journal of Combinatorics. 28 (1): 403–409. arXiv:matematika / 0501359. doi:10.1016 / j.ejc.2005.06.003.
^ Betke, Ulrich; McMullen, Peter (1985-12-01). "Mřížové body v mřížových polytopech". Monatshefte für Mathematik. 99 (4): 253–265. doi:10.1007 / BF01312545. ISSN 1436-5081.
^ Henk, Martin; Tagami, Makoto (01.01.2009). "Dolní hranice koeficientů Ehrhartových polynomů". European Journal of Combinatorics. 30 (1): 70–83. arXiv:0710.2665. doi:10.1016 / j.ejc.2008.02.009. ISSN 0195-6698.
^ Braun, Benjamin; Develin, Mike (2008). Ehrhartovy polynomické kořeny a Stanleyho věta o negativitě. Současná matematika. 452. Americká matematická společnost. str. 67–78. arXiv:matematika / 0610399. doi:10.1090 / conm / 452/08773. ISBN 9780821841730.
^ Higashitani, Akihiro (2012). "Klasifikace Ehrhartových polynomů integrálních jednoduchostí" (PDF). Řízení DMTCS: 587–594.
^ Beck, Matthias (leden 2002). "Multidimenzionální Ehrhartova vzájemnost". Journal of Combinatorial Theory. Řada A. 97 (1): 187–194. arXiv:matematika / 0111331. doi:10.1006 / jcta.2001.3220.
^ Lisonek, Petr (2007). "Kombinatorické rodiny vyjmenované kvazi-polynomy". Journal of Combinatorial Theory. Řada A. 114 (4): 619–630. doi:10.1016 / j.jcta.2006.06.013.

Reference

Beck, Matthias; De Loera, Jesús A.; Develin, Mike; Pfeifle, Julian; Stanley, Richard P. (2005), „Koeficienty a kořeny Ehrhartových polynomů“, Celočíselné body v mnohostěně - geometrie, teorie čísel, algebra, optimalizace, Současná matematika, 374, Providence, RI: Americká matematická společnost, s. 15–36, PAN 2134759.
Beck, Matthias; Robins, Sinai (2007), Výpočet kontinuity diskrétně: Výčet celých bodů v mnohostěnech, Pregraduální texty z matematiky, New York: Springer-Verlag, ISBN 978-0-387-29139-0, PAN 2271992.
De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010), „Ehrhartovy polynomy a unimodulární triangulace“, Triangulace: Struktury pro algoritmy a aplikace Algoritmy a výpočty v matematice, 25, Springer, str. 475, ISBN 978-3-642-12970-4.
Diaz, Ricardo; Robins, Sinai (1996), „Ehrhartův polynom mřížky n-simplex ", Oznámení American Mathematical Society o elektronickém výzkumu, 2: 1–6, doi:10.1090 / S1079-6762-96-00001-7, PAN 1405963. Představuje přístup Fourierovy analýzy a poskytuje odkazy na další související články.
Ehrhart, Eugène (1962), „Sur les polyèdres rationnels homothétiques à n rozměry", Comptes rendus de l'Académie des Sciences, 254: 616–618, PAN 0130860. Definice a první vlastnosti.
Mathar, Richard J. (2010), Počty bodů ${ displaystyle D_ {k}}$ a nějaký ${ displaystyle A_ {k}}$ a ${ displaystyle E_ {k}}$ celočíselné mřížky uvnitř hyperkrychlí, arXiv:1002.3844, Bibcode:2010arXiv1002.3844M
Mustață, Mircea (Únor 2005), "Ehrhartovy polynomy", Poznámky k přednášce o torických odrůdách.

[1] Macdonald, Ian G. (1971). "Polynomy spojené s komplexy konečných buněk" (PDF). Journal of the London Mathematical Society. 2 (1): 181–192. doi:10.1112 / jlms / s2-4.1.181.

[2] De Loera, Rambau a Santos (2010)

[3] Mathar (2010)

[4] Beck a kol. (2005).

[MR2271992-5] Beck, Matthias; Robins, Sinai (2007). Diskrétní výpočet kontinuity. New York: Springer. str.46 –47. PAN 2271992.

[6] Betke, Ulrich; Kneser, Martin (1985), „Zerlegungen und Bewertungen von Gitterpolytopen“, Journal für die reine und angewandte Mathematik, 358: 202–208, PAN 0797683

[7] Athanasiadis, Christos A. (2004). "h* -Vektory, Euleriánské polynomy a stabilní polytopy grafů ". Electronic Journal of Combinatorics. 11 (2).

[8] Stanley, Richard P. (1980). "Rozklady racionálních konvexních polytopů". Annals of Discrete Mathematics. 6: 333–342. doi:10.1016 / s0167-5060 (08) 70717-9. ISBN 9780444860484.

[9] Beck, Matthias; Sottile, Frank (leden 2007). „Iracionální důkazy pro tři Stanleyho věty“. European Journal of Combinatorics. 28 (1): 403–409. arXiv:matematika / 0501359. doi:10.1016 / j.ejc.2005.06.003.

[10] Betke, Ulrich; McMullen, Peter (1985-12-01). "Mřížové body v mřížových polytopech". Monatshefte für Mathematik. 99 (4): 253–265. doi:10.1007 / BF01312545. ISSN 1436-5081.

[11] Henk, Martin; Tagami, Makoto (01.01.2009). "Dolní hranice koeficientů Ehrhartových polynomů". European Journal of Combinatorics. 30 (1): 70–83. arXiv:0710.2665. doi:10.1016 / j.ejc.2008.02.009. ISSN 0195-6698.

[12] Braun, Benjamin; Develin, Mike (2008). Ehrhartovy polynomické kořeny a Stanleyho věta o negativitě. Současná matematika. 452. Americká matematická společnost. str. 67–78. arXiv:matematika / 0610399. doi:10.1090 / conm / 452/08773. ISBN 9780821841730.

[13] Higashitani, Akihiro (2012). "Klasifikace Ehrhartových polynomů integrálních jednoduchostí" (PDF). Řízení DMTCS: 587–594.

[14] Beck, Matthias (leden 2002). "Multidimenzionální Ehrhartova vzájemnost". Journal of Combinatorial Theory. Řada A. 97 (1): 187–194. arXiv:matematika / 0111331. doi:10.1006 / jcta.2001.3220.

[15] Lisonek, Petr (2007). "Kombinatorické rodiny vyjmenované kvazi-polynomy". Journal of Combinatorial Theory. Řada 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]