Fast Evaluation of Generalized Todd Polynomials: Applications to MacMahon's Partition Analysis and Integer Programming
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913634805874688 |
|---|---|
| author | Xin, Guoce Zhang, Yingrui Zhang, ZiHao |
| author_facet | Xin, Guoce Zhang, Yingrui Zhang, ZiHao |
| contents | The Todd polynomials, denoted as $td_k(b_1,b_2,\ldots,b_m)$, are characterised by their generating functions: $$\sum_{k\ge 0} td_k s^k = \prod_{i=1}^m \frac{b_i s}{e^{b_i s}-1}.$$ These polynomials serve as fundamental components in the Todd class of toric varieties, a concept of significant relevance in the study of lattice polytopes and number theory. We identify that generalised Todd polynomials emerge naturally within the framework of MacMahon's partition analysis, particularly in the context of computing Ehrhart series. We introduce an efficient method for the evaluation of generalised Todd polynomials for numerical values of $b_i$. This is achieved through the development of expedited operations in the quotient ring $\mathbb{Z}_p[[s]]$ modulo $s^{d}$, where $p$ is a large prime. The practical implications of our work are demonstrated through two applications: firstly, we facilitate a recalculated resolution of the Ehrhart series for magic squares of order 6, a problem initially addressed by the first author, reducing computation time from 70 days to approximately 1 day; secondly, we present a polynomial-time algorithm for Integer Linear Programming when the dimension is fixed, exhibiting a notable enhancement in computational efficiency. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_13323 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Fast Evaluation of Generalized Todd Polynomials: Applications to MacMahon's Partition Analysis and Integer Programming Xin, Guoce Zhang, Yingrui Zhang, ZiHao Combinatorics Primary 05-04, Secondary 05E14, 05A15 The Todd polynomials, denoted as $td_k(b_1,b_2,\ldots,b_m)$, are characterised by their generating functions: $$\sum_{k\ge 0} td_k s^k = \prod_{i=1}^m \frac{b_i s}{e^{b_i s}-1}.$$ These polynomials serve as fundamental components in the Todd class of toric varieties, a concept of significant relevance in the study of lattice polytopes and number theory. We identify that generalised Todd polynomials emerge naturally within the framework of MacMahon's partition analysis, particularly in the context of computing Ehrhart series. We introduce an efficient method for the evaluation of generalised Todd polynomials for numerical values of $b_i$. This is achieved through the development of expedited operations in the quotient ring $\mathbb{Z}_p[[s]]$ modulo $s^{d}$, where $p$ is a large prime. The practical implications of our work are demonstrated through two applications: firstly, we facilitate a recalculated resolution of the Ehrhart series for magic squares of order 6, a problem initially addressed by the first author, reducing computation time from 70 days to approximately 1 day; secondly, we present a polynomial-time algorithm for Integer Linear Programming when the dimension is fixed, exhibiting a notable enhancement in computational efficiency. |
| title | Fast Evaluation of Generalized Todd Polynomials: Applications to MacMahon's Partition Analysis and Integer Programming |
| topic | Combinatorics Primary 05-04, Secondary 05E14, 05A15 |
| url | https://arxiv.org/abs/2304.13323 |