| Presentation | 2023-12-22 The ultimate signs of second-order holonomic sequences Akitoshi Kawamura, Fugen Hagihara, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A real-valued sequence ${f(n)} _{n in mathbb{N}}$ is said to be second-order holonomic if it satisfies a linear recurrence $P _2 (n) f (n + 2) = P _1 (n) f (n + 1) + P _0 (n) f (n)$, where $P _0$, $P _1$, $P _2$ are polynomials and $P _2 neq 0$．We study the ultimate signs of such a sequence, i.e., the repeated pattern that the signs of $f (n)$ follow for sufficiently large $n$．We classify all possible ultimate signs in terms of the degrees and the first few coefficients of $P _0$, $P _1$ and $P _2$, completing prior work by Neumann, Ouaknine, and Worrell who have settled some restricted cases．As a corollary, it follows that when $P_0$, $P_1$, $P_2$ have rational coefficients, $f$ either has an ultimate sign of length $1$, $2$, $3$, $4$, $6$, $8$ or $12$, or never falls into a repeated sign pattern．We also give an algorithm that, given $P_0$, $P_1$, $P_2$, the initial values and some additional information of them, outputs when $f$ reaches the ultimate state. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | holonomic / P-finite / linear recurrence / ultimate sign / decidability |
| Paper # | COMP2023-25 |
| Date of Issue | 2023-12-15 (COMP) |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2023/12/22(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Miyazaki Univ. Machinaka Campus |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Theoretical Computer Science, etc |
| Chair | Hiroyuki Uno(Osaka Metropolitan Univ.) |
| Vice Chair | Shuji Kijima(Shiga Univ.) |
| Secretary | Shuji Kijima(Hosei Univ.) |
| Assistant | Ei Ando(Senshu Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | The ultimate signs of second-order holonomic sequences |
| Sub Title (in English) | |
| Keyword(1) | holonomic |
| Keyword(2) | P-finite |
| Keyword(3) | linear recurrence |
| Keyword(4) | ultimate sign |
| Keyword(5) | decidability |
| 1st Author's Name | Akitoshi Kawamura |
| 1st Author's Affiliation | Kyoto University(Kyoto Univ.) |
| 2nd Author's Name | Fugen Hagihara |
| 2nd Author's Affiliation | Kyoto University(Kyoto Univ.) |
| Date | 2023-12-22 |
| Paper # | COMP2023-25 |
| Volume (vol) | vol.123 |
| Number (no) | COMP-325 |
| Page | pp.pp.56-60(COMP), |
| #Pages | 5 |
| Date of Issue | 2023-12-15 (COMP) |