| | |
| | |
Stat |
Members: 3645 Articles: 2'500'096 Articles rated: 2609
19 April 2024 |
|
| | | |
|
Article overview
| |
|
Computing the period of an Ehrhart quasi-polynomial | Kevin M. Woods
; | Date: |
9 Nov 2004 | Subject: | Combinatorics | math.CO | Abstract: | If P is a rational polytope in R^d, then $i_P(t):=#(tPcap Z^d)$ is a quasi-polynomial in t, called the Ehrhart quasi-polynomial of P. A period of i_P(t) is D(P), the smallest positive integer D such that D*P has integral vertices. Often, D(P) is the minimum period of i_P(t), but, in several interesting examples, the minimum period is smaller. We prove that, for fixed d, there is a polynomial time algorithm which, given a rational polytope P in R^d and an integer n, decides whether n is a period of i_P(t). In particular, there is a polynomial time algorithm to decide whether i_P(t) is a polynomial. We conjecture that, for fixed d, there is a polynomial time algorithm to compute the minimum period of i_P(t). The tools we use are rational generating functions. | Source: | arXiv, math.CO/0411207 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |