Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2014
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/1409.3669 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913786485538816 |
|---|---|
| author | Bostan, Alin Bousquet-Mélou, Mireille Kauers, Manuel Melczer, Stephen |
| author_facet | Bostan, Alin Bousquet-Mélou, Mireille Kauers, Manuel Melczer, Stephen |
| contents | Many recent papers deal with the enumeration of 2-dimensional walks with prescribed steps confined to the positive quadrant. The classification is now complete for walks with steps in $\{0, \pm 1\}^2$: the generating function is D-finite if and only if a certain group associated with the step set is finite.
We explore in this paper the analogous problem for 3-dimensional walks confined to the positive octant. The first difficulty is their number: there are 11074225 non-trivial and non-equivalent step sets in $\{0, \pm 1\}^3$ (instead of 79 in the quadrant case). We focus on the 35548 that have at most six steps.
We apply to them a combined approach, first experimental and then rigorous. On the experimental side, we try to guess differential equations. We also try to determine if the associated group is finite. The largest finite groups that we find have order 48 -- the larger ones have order at least 200 and we believe them to be infinite. No differential equation has been detected in those cases.
On the rigorous side, we apply three main techniques to prove D-finiteness. The algebraic kernel method, applied earlier to quadrant walks, works in many cases. Certain, more challenging, cases turn out to have a special Hadamard structure, which allows us to solve them via a reduction to problems of smaller dimension. Finally, for two special cases, we had to resort to computer algebra proofs. We prove with these techniques all the guessed differential equations.
This leaves us with exactly 19 very intriguing step sets for which the group is finite, but the nature of the generating function still unclear. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1409_3669 |
| institution | arXiv |
| publishDate | 2014 |
| record_format | arxiv |
| spellingShingle | On 3-dimensional lattice walks confined to the positive octant Bostan, Alin Bousquet-Mélou, Mireille Kauers, Manuel Melczer, Stephen Combinatorics Many recent papers deal with the enumeration of 2-dimensional walks with prescribed steps confined to the positive quadrant. The classification is now complete for walks with steps in $\{0, \pm 1\}^2$: the generating function is D-finite if and only if a certain group associated with the step set is finite. We explore in this paper the analogous problem for 3-dimensional walks confined to the positive octant. The first difficulty is their number: there are 11074225 non-trivial and non-equivalent step sets in $\{0, \pm 1\}^3$ (instead of 79 in the quadrant case). We focus on the 35548 that have at most six steps. We apply to them a combined approach, first experimental and then rigorous. On the experimental side, we try to guess differential equations. We also try to determine if the associated group is finite. The largest finite groups that we find have order 48 -- the larger ones have order at least 200 and we believe them to be infinite. No differential equation has been detected in those cases. On the rigorous side, we apply three main techniques to prove D-finiteness. The algebraic kernel method, applied earlier to quadrant walks, works in many cases. Certain, more challenging, cases turn out to have a special Hadamard structure, which allows us to solve them via a reduction to problems of smaller dimension. Finally, for two special cases, we had to resort to computer algebra proofs. We prove with these techniques all the guessed differential equations. This leaves us with exactly 19 very intriguing step sets for which the group is finite, but the nature of the generating function still unclear. |
| title | On 3-dimensional lattice walks confined to the positive octant |
| topic | Combinatorics |
| url | https://arxiv.org/abs/1409.3669 |