On quantitative aspects of trace polynomials

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 $\varphi^n$, where $\varphi$ 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 $\Omega(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$.