Punkty całkowite w wielościanach wypukłych

Czerwone kropki to punkty sieci całkowitej w obrębie niebieskiego wielokąta, przy czym ten ostatni reprezentuje dwuwymiarowy program liniowy

Badanie punktów całkowitych w wypukłych wielościanach jest motywowane pytaniami, takimi jak „ile nieujemnych rozwiązań o wartościach całkowitych ma układ równań liniowych o nieujemnych współczynnikach” lub „ile rozwiązań ma program liniowy liczb całkowitych ”. Liczenie punktów całkowitych w wielościanach lub inne pytania na ich temat pojawiają się w teorii reprezentacji , algebrze przemiennej , geometrii algebraicznej , statystyce i informatyce .

Zbiór punktów całkowitych lub, bardziej ogólnie, zbiór punktów sieci afinicznej w wielościanie nazywa się wielościanem Z , z zapisu matematycznego lub Z dla zbioru liczb całkowitych ${\ Displaystyle \ mathbb {Z}}$ liczby.

Nieruchomości

W przypadku sieci Λ twierdzenie Minkowskiego wiąże liczbę d (Λ) (objętość podstawowego równoległościanu sieci) i objętość danego symetrycznego zbioru wypukłego S z liczbą punktów sieci zawartych w S .

Liczba punktów sieci zawartych w polytopie , którego wszystkie wierzchołki są elementami sieci, jest opisana wielomianem Ehrharta polytopu . Wzory na niektóre współczynniki tego wielomianu obejmują również d (Λ).

Aplikacje

Optymalizacja pętli

W niektórych podejściach do optymalizacji pętli zbiór wykonań ciała pętli jest postrzegany jako zbiór punktów całkowitych w wielościanie zdefiniowanym przez ograniczenia pętli.

Zobacz też

• Wypukła siatka polytope
• Twierdzenie Picka

Dalsza lektura

•    Barwinok, Aleksander ; Beck, Maciej; Haase, chrześcijanin; Reznick, Bruce ; Welker, Volkmar (2005), Integer Points In Polyhedra: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference, która odbyła się w Snowbird, UT, 13–17 lipca 2003 , Współczesna matematyka, tom. 374, Providence, RI: Amerykańskie Towarzystwo Matematyczne, doi : 10.1090/conm/374 , ISBN 0-8218-3459-2 , MR 2134757
•    Barvinok, Alexander (2008), Liczba całkowita w wielościanach , Zurych Wykłady z zaawansowanej matematyki , Zurych: Europejskie Towarzystwo Matematyczne, doi : 10.4171/052 , ISBN 978-3-03719-052-4 , MR 2455889
•    Beck, Maciej; Haase, chrześcijanin; Reznick, Bruce ; Vergne, Michele ; Welker, Volkmar; Yoshida, Ruriko (2008), Całkowite punkty w wielościanach: geometria, teoria liczb, teoria reprezentacji, algebra, optymalizacja, statystyka (PDF) , współczesna matematyka, tom. 452, Providence, RI: Amerykańskie Towarzystwo Matematyczne, doi : 10.1090/conm/452 , ISBN 978-0-8218-4173-0 , MR 2416261