Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2019
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/1911.12857 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929604273373184 |
|---|---|
| author | Figelius, Michael Lohrey, Markus Zetzsche, Georg |
| author_facet | Figelius, Michael Lohrey, Markus Zetzsche, Georg |
| contents | We show that the following group constructions preserve the semilinearity of the solution sets for knapsack equations (equations of the form $g_1^{x_1} \cdots g_k^{x_k} = g$ in a group $G$, where the variables $x_1, \ldots, x_k$ take values in the natural numbers): graph products, amalgamated free products with finite amalgamated subgroups, HNN-extensions with finite associated subgroups, and finite extensions. Moreover, we study the dependence of the so-called magnitude for the solution set of a knapsack equation (the magnitude is a complexity measure for semi-linear sets) with respect to the length of the knapsack equation (measured in number of generators). We investigate, how this dependence changes under the above group operations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1911_12857 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Closure properties of knapsack semilinear groups Figelius, Michael Lohrey, Markus Zetzsche, Georg Group Theory 20F10, 20F67 We show that the following group constructions preserve the semilinearity of the solution sets for knapsack equations (equations of the form $g_1^{x_1} \cdots g_k^{x_k} = g$ in a group $G$, where the variables $x_1, \ldots, x_k$ take values in the natural numbers): graph products, amalgamated free products with finite amalgamated subgroups, HNN-extensions with finite associated subgroups, and finite extensions. Moreover, we study the dependence of the so-called magnitude for the solution set of a knapsack equation (the magnitude is a complexity measure for semi-linear sets) with respect to the length of the knapsack equation (measured in number of generators). We investigate, how this dependence changes under the above group operations. |
| title | Closure properties of knapsack semilinear groups |
| topic | Group Theory 20F10, 20F67 |
| url | https://arxiv.org/abs/1911.12857 |