I have two alphabets with 3 letters, $\{V,U,U^\dagger\}$ and $\{X_1,X_2,X_3\}$ where
$$ V = X_1 + X_2 + X_3, \, U = X_1 + \omega X_2 + \omega^2 X_3, \, U^\dagger = X_1 + \omega^2 X_2 + \omega X_3 $$
and $\omega = e^{2\pi i /3}$.
The words I can construct in the former alphabet are restricted, such that any letter $U$ can only immediately be followed by a $V$ or a $U^\dagger$, and ultimately in the string, there must be a corresponding $U^\dagger$. Any insertion of $U^\dagger$ must be preceded by either the letter $V$ or $U^\dagger$, with an accompanying $U$ for every $U^\dagger$. Therefore $U$ and $U^\dagger$ come in a pair, and the letter $U$ will always precede the letter $U^\dagger$ in the word they are present in, and there may be multiple letters of $V$ in between them. Furthermore there can be as many pairs of $UU^\dagger$ as the length of the word permits.
Hence, the only possible 2 letter words that can be constructed are $VV$ and $UU^\dagger$.
The 3-letter words that can be constructed are $V V V, V U U^\dagger, U V U^\dagger, U U^\dagger V$.
The 4-letter words that can be constructed are $VVVV, VVUU^\dagger, VUVU^\dagger, UVVU^\dagger, VUU^\dagger V, UVU^\dagger V, UU^\dagger VV$ and $UU^\dagger UU^\dagger$.
The 5-letter words that can be constructed are $VVVVV, VVVUU^\dagger, VVUVU^\dagger, VUVVU^\dagger, UVVVU^\dagger, VVUU^\dagger V, VUVU^\dagger V, UVVU^\dagger V, VUU^\dagger VV, UVU^\dagger VV, UU^\dagger VVV, VUU^\dagger UU^\dagger, UVU^\dagger U U^\dagger, UU^\dagger V UU^\dagger, UU^\dagger UVU^\dagger$ and $UU^\dagger U U^\dagger V$.
In general there $2^{n-1}$ length $n$ words.
I would like to write down the real part of the sum of these words when mapped to the alphabet ${X_1,X_2,X_3}$.
I have explicitly shown that up to $n=6$ this gives
$$ 2^{n-1} \sum_{\sigma_1,\cdots,\sigma_n=1}^{3} \bigg(- \frac{1}{2}\bigg)^{\sum_{r=1}^n (1-\delta(\sigma_r,\sigma_{r+1}))} X_{\sigma_1}\cdots X_{\sigma_n}, \qquad \sigma_{n+1}=\sigma_1, $$
where $\delta(\sigma_r, \sigma_{r+1})$ is the Kronecker delta.
So for example, taking the sum of 2-letter words, listed above, and the expressions for $\{V,U,U^\dagger\}$ in terms of $\{X_1,X_2,X_3\}$, expanding and collecting terms. Then when we take the real part of the final result we find
$$ \text{Re}(VV + UU^\dagger) = 2\bigg(X_1 X_1 + X_2 X_2 + X_3 X_3 + \bigg(-\frac{1}{2}\bigg)^2 X_1 X_2 + \bigg(-\frac{1}{2}\bigg)^2 X_1 X_3+ \bigg(-\frac{1}{2}\bigg)^2 X_2 X_3+ \bigg(-\frac{1}{2}\bigg)^2 X_2 X_1 + \bigg(-\frac{1}{2}\bigg)^2 X_3 X_1 + \bigg(-\frac{1}{2}\bigg)^2 X_3 X_2\bigg) $$
I would like to prove (or disprove) this result for arbitrary $n$.
To do this I am basically using induction, but I have a problem in working out how to express the real part of words of the form $U^\dagger \{\text{length} \, n \, \text{words} \}$.
My question is whether there is a demonstrable way of writing down a closed sum, as above, for the words $U^\dagger \{\text{length} \, n \, \text{words} \}$. If anyone has any insight into how this might work, I would be extremely grateful.
Best Answer
Yes, your formula holds true.
Speaking the "algebraic" language, we identify a set $W$ of words over an alphabet $A$ with the corresponding element $\sum_{w\in W}w$ of a free algebra on $A$ (in our case, the $\mathbb{Z}[\omega]$-algebra). If $W_n$ corresponds to the set of "allowed" words over $\{V,U,U^\dagger\}$ of length $n$ (and we consider the empty word as "allowed", so that $W_0\equiv 1$), then $$W_n=VW_{n-1}+\sum_{k=2}^{n}UV^{k-2}U^\dagger W_{n-k}\qquad(n>0)$$ since each nonempty "allowed" word begins with either $V$ or $UV^{k-2}U^\dagger$ for some $k$, with the remainder also "allowed". Now let the new variables be $X_0,X_1,X_2$ (for convenience); that is, we substitute $$V=\sum_{\sigma\in\Sigma}X_\sigma,\quad U=\sum_{\sigma\in\Sigma}\omega^\sigma X_\sigma,\quad U^\dagger=\sum_{\sigma\in\Sigma}\omega^{-\sigma} X_\sigma\qquad(\Sigma=\{0,1,2\})$$ into $W_n$. Then, if $C_n(\sigma_1,\ldots,\sigma_n)$ is the coefficient of $X_{\sigma_1}\cdots X_{\sigma_n}$ in $W_n$, we have $$C_n(\sigma_1,\ldots,\sigma_n)=C_{n-1}(\sigma_2,\ldots,\sigma_n)+\sum_{k=2}^{n}\omega^{\sigma_1-\sigma_k}C_{n-k}(\sigma_{k+1},\ldots,\sigma_n)$$ for $n>0$. But then $C_n(\sigma_1,\ldots,\sigma_n)=(1+\omega^{\sigma_1-\sigma_2})C_{n-1}(\sigma_2,\ldots,\sigma_n)$ for $n>1$, which is easily verified using induction on $n$. Thus, we arrive at the explicit formula $$\require{action}C_n(\sigma_1,\ldots,\sigma_n)=\texttip{\color{blue}{\prod_{k=1}^{n-1}(1+\omega^{\sigma_k-\sigma_{k+1}})}}{Note that we didn't use any properties of $\omega$ and $\Sigma$ until this place, inclusive}=e^{i\pi(\sigma_1-\sigma_n)/3}\prod_{k=1}^{n-1}2\cos\big(\pi(\sigma_k-\sigma_{k+1})/3\big).$$ It is easy to see that the real part of this equality is equivalent to your result.