Noncommutative rational Pólya series
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2019
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918281613410304 |
|---|---|
| author | Bell, Jason Smertnig, Daniel |
| author_facet | Bell, Jason Smertnig, Daniel |
| contents | A (noncommutative) Pólya series over a field $K$ is a formal power series whose nonzero coefficients are contained in a finitely generated subgroup of $K^\times$. We show that rational Pólya series are unambiguous rational series, proving a 40 year old conjecture of Reutenauer. The proof combines methods from noncommutative algebra, automata theory, and number theory (specifically, unit equations). As a corollary, a rational series is a Pólya series if and only if it is Hadamard sub-invertible. Phrased differently, we show that every weighted finite automaton taking values in a finitely generated subgroup of a field (and zero) is equivalent to an unambiguous weighted finite automaton. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1906_07271 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Noncommutative rational Pólya series Bell, Jason Smertnig, Daniel Combinatorics Number Theory Primary 68Q45, 68Q70, Secondary 11B37 A (noncommutative) Pólya series over a field $K$ is a formal power series whose nonzero coefficients are contained in a finitely generated subgroup of $K^\times$. We show that rational Pólya series are unambiguous rational series, proving a 40 year old conjecture of Reutenauer. The proof combines methods from noncommutative algebra, automata theory, and number theory (specifically, unit equations). As a corollary, a rational series is a Pólya series if and only if it is Hadamard sub-invertible. Phrased differently, we show that every weighted finite automaton taking values in a finitely generated subgroup of a field (and zero) is equivalent to an unambiguous weighted finite automaton. |
| title | Noncommutative rational Pólya series |
| topic | Combinatorics Number Theory Primary 68Q45, 68Q70, Secondary 11B37 |
| url | https://arxiv.org/abs/1906.07271 |