Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.25265 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918528763822080 |
|---|---|
| author | Kapovich, Ilya |
| author_facet | Kapovich, Ilya |
| contents | By the classic results of Fricke and Klein, for every word $w$ in the free group $F(a,b)$ there exists a unique integer \it{trace polynomial} $f_w(x,y,z)\in Z[x,y,z]$ such that $Tr(w(A,B))=f_w(Tr A,Tr B,Tr AB)$. for all $A,B\in SL(2,C)$. We study quantitative aspects of trace polynomials. We prove an exact formula for the leading homogeneous part of $f_w$ for every nontrivial cyclically reduced word $w\in F(a,b)$. In particular, if $w=u_1\cdots u_n$ is cyclically reduced over $\{a,a^{-1},b,b^{-1}\}$, and if $N_{rs}(w)$ is the number of cyclic occurrences of $rs$, then $deg f_w=n-N_{ab}(w)-N_{b^{-1}a^{-1}}(w)=n-\frac{1}{2}(N_{ab}(w)+N_{ba}(w)+N_{a^{-1}b^{-1}}(w)+N_{b^{-1}a^{-1}}(w)).$ We obtain sharp general bounds $\lceil n/2\rceil\le deg f_w\le n$ for $w\in F(a,b)$ with cyclically reduced length $n$. We also study $deg f_w$ for random positive words and for random freely reduced and random cyclically reduced words. We obtain explicit exponential upper bounds for the growth of the $\ell_1$ and $\ell_\infty$ norms of $f_w$ and exhibit examples with exponential coefficient growth at rate $φ^n$, where $φ$ is the golden ratio. We show that for random freely reduced, random cyclically reduced and random positive words $w_n$ of length $n$ in $F(a,b)$, the size of $supp(f_{w_n})$ grows at least quadratically in $n$ and the total bit-size of $f_{w_n}$ grows at least as $cn^3$. Hence, any algorithm computing $f_w$ in totally expanded form has worst-case time complexity as well as generic-case time complexity for the above models bounded below by $Ω(n^3)$. We also give a deterministic algorithm which computes the fully expanded polynomial $f_w$ in time $O(n^5)$ and space $O(n^4)$, in terms of the input word length $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_25265 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On quantitative aspects of trace polynomials Kapovich, Ilya Group Theory Geometric Topology By the classic results of Fricke and Klein, for every word $w$ in the free group $F(a,b)$ there exists a unique integer \it{trace polynomial} $f_w(x,y,z)\in Z[x,y,z]$ such that $Tr(w(A,B))=f_w(Tr A,Tr B,Tr AB)$. for all $A,B\in SL(2,C)$. We study quantitative aspects of trace polynomials. We prove an exact formula for the leading homogeneous part of $f_w$ for every nontrivial cyclically reduced word $w\in F(a,b)$. In particular, if $w=u_1\cdots u_n$ is cyclically reduced over $\{a,a^{-1},b,b^{-1}\}$, and if $N_{rs}(w)$ is the number of cyclic occurrences of $rs$, then $deg f_w=n-N_{ab}(w)-N_{b^{-1}a^{-1}}(w)=n-\frac{1}{2}(N_{ab}(w)+N_{ba}(w)+N_{a^{-1}b^{-1}}(w)+N_{b^{-1}a^{-1}}(w)).$ We obtain sharp general bounds $\lceil n/2\rceil\le deg f_w\le n$ for $w\in F(a,b)$ with cyclically reduced length $n$. We also study $deg f_w$ for random positive words and for random freely reduced and random cyclically reduced words. We obtain explicit exponential upper bounds for the growth of the $\ell_1$ and $\ell_\infty$ norms of $f_w$ and exhibit examples with exponential coefficient growth at rate $φ^n$, where $φ$ is the golden ratio. We show that for random freely reduced, random cyclically reduced and random positive words $w_n$ of length $n$ in $F(a,b)$, the size of $supp(f_{w_n})$ grows at least quadratically in $n$ and the total bit-size of $f_{w_n}$ grows at least as $cn^3$. Hence, any algorithm computing $f_w$ in totally expanded form has worst-case time complexity as well as generic-case time complexity for the above models bounded below by $Ω(n^3)$. We also give a deterministic algorithm which computes the fully expanded polynomial $f_w$ in time $O(n^5)$ and space $O(n^4)$, in terms of the input word length $n$. |
| title | On quantitative aspects of trace polynomials |
| topic | Group Theory Geometric Topology |
| url | https://arxiv.org/abs/2605.25265 |