# Reconstructing a word

Let $w(a,b)$ be a word in two letter alphabet. Let $$A=\left(\begin{array}{lll}x_1 & x_2 & x_3\\\ x_4 &x_5 & x_6\\\ x_7 & x_8 & x_9\end{array}\right), B=\left(\begin{array}{lll}y_1 & y_2 & y_3\\\ y_4 &y_5 & y_6\\\ y_7 & y_8 & y_9\end{array}\right)$$ where $x_i,y_i$ are commuting variables. Let $f_w=\mathrm{trace}(w(A,B))$, a polynomial in 18 variables.

Question. Is it possible to reconstruct $w$ up to a cyclic shift from $f_w$?

Note that there exists a polynomial in one variable that encodes $w$: $x^{p_1}+...+x^{p_s}+x^{|w|}$ where $p_1,...,p_s$ are the places where $a$ occurs in $w$. Also note that for 2 by 2 matrices the answer is "no". For example if $w=abbaba$ and $w'=ababba$, then $f_w=f_{w'}$ for 2 by 2 matrices. The question is related to the study of the moduli space of representations (of degree 3) of the free group.

Update I think that as George suggested below, one can assume that $A=\mathrm{diag}(a,b,c)$ is a diagonal matrix (otherwise consider a conjugate of the pair $A,B$ over some algebraically complete field). After that the problem reduces to the following problem which seems longer but is in fact easier because we reduce the number of variables to from 18 to 3:

Pick a natural number $n\gg 1$. For every cyclic sequence $p$ (i.e. $p_{n+1}=p_1$) of $\{1,2,3\}$ of length $n$ consider a 9-vector $\phi(p)=($number of occurrences of 11, number of occurrences of 12, ..., number of occurrences of 33$)\in \mathbb{N}^9$. The sum of coordinates of $\phi(p)$ is $n$, so we get a partition of $n$, and the number of different $\phi(p)$ is at most the number of partitions of $n$ into 9 parts, so less than $n^9$. Thus the map $\phi$ has a non-trivial kernel $\mathrm{Ker}(\phi)$ (i.e. the equivalence relation $p\equiv q$ iff $\phi(p)=\phi(q)$ ). Let $S$ be a preimage of a point in $\mathbb{N}^9$ under $\phi$. Let $v=(v_1,...,v_n)$ be a cyclic vector of natural numbers (including 0). For every $p\in S$ consider the monomial $m_p=a^sb^tc^u$ in 3 variables where $s$ is the sum of $v_i$ such that $p_i=1$, $t$ is the sum of $v_i$ such that $p_i=2$, $u$ is the sum of $v_i$ such that $p_i=3$. The sum of all the monomials $m_p$, $p\in S$, is a polynomial $f_S(v)$ in $a,b,c$. That polynomial is the coefficient of the monomial $\prod_{(i,j)} B[i,j]^{\phi(p)[i,j]}$ in $f_w$.

Question Is the sequence $v$ determined by the sequence of polynomials $f_S(v)$ where $S$ runs over the equivalence classes of the partition $\mathrm{Ker}(\phi)$.

• Basically your question amounts to asking if nonconjugate words are separated by characters of semisimple representations of degree 3. If the words have different length 1-dimensional representations suffice. So assume u is a word of length k. Then there are finitely many non conjugate words of length k. To each such word v one can look at the closed subvariety of all representations such that the traces for u,v coincide. By irreducibility one has to show this is a proper subvariety. So you are reduced to the following question: can any two nonconjugate words of the same length be separated Jul 23 '12 at 15:24
• cts... by characters of 3-dim semisimple representations. Jul 23 '12 at 15:25
• That is correct but it makes the problem more complicated than it seems to be. One even can assume that the coefficients are modulo 2, so only the "tropical" data is available, the monomials that occur in $f_w$
– user6976
Jul 23 '12 at 15:30
• $abbab$ and $babba$ are conjugate... Jul 23 '12 at 15:38
• Take $A={\rm diag}(a_1,a_2,a_3)$. If there are $n > 2$ b's in the word, then then the pair $(r,s)$ appears as consecutive distances between b's iff a term $a_1^ta_2^ra_3^sb_{11}^{n-3}b_{12}b_{23}b_{31}$ appears in the trace. Jul 24 '12 at 10:52

Fix an integer $n$. Consider the Hilbert space $H=\ell^2(\{a,b\}^n)$ spanned by the words of length $n$ in $a$ and $b$. The symmetric group $S_n$ acts on $H$. For every permutation $\pi \in S_n$ consider $c(\pi)$, the number of cycles in $\pi^{-1} \tau \pi \tau^{-1}$, where $\tau$ is the cycle $(1 2 \dots n)$. Consider the following operator on $H$: $$T = \sum_{\pi \in S_n} 3^{c(\pi)} \pi.$$
The content of my comment was that for two words of length $n$, $f_w = f_{w'}$ if and only if $T(\delta_w - \delta_{w'})=0$. In particular, it would be sufficient to prove that the kernel of $T$ is just the kernel of $\sum_{k=1}^n \tau^k$ (= the functions on $\{a,b\}^n$ that sum to $0$ on each $\tau$-orbit) to answer positively Marks' question. Unfortunately I could not prove it.
Indeed, take $A$ and $B$ random with entries that are independant centered complex gaussians with variance $1$ (the real and imaginary parts are real gaussians centered with variance $1/2$). Then $\mathbb E[f_w(A,B) \overline{f_{w'}(A,B)}] = \langle T \delta_w, \delta_{w'}\rangle.$ This formula implies that $T$ is a non-negative operator, and that $f_w \mapsto \sqrt T \delta_\omega$ is an isometry from the subspace of $L^2$ spanned by the $f_w$'s to $H$, and hence that $f_w = f_{w'}$ iff $\sqrt T \delta_w = \sqrt T \delta_{w'}$ iff $T \delta_w = T \delta_{w'}$.
I am not sure it is worth writing a precise proof of this equality: if one developps the LHS of the inequality, on gets a big sum of moments of gaussians. To simplify this expression, use some moment-cumulant transformation which yields to the RHS. I can at least say that $3^{c(\pi)}$ appears as the number of pairs of $n$-uples $(i_1,\dots,i_n)$ and $(j_1,\dots j_n)$ such that $(i_k,i_{k+1}) = (j_{\pi(k)},j_{\pi(k)+1})$.