Return to Answer

I believe this can be evaluated by expanding cos as a sum of exponentials.

Let $\zeta=\exp(2i\pi/n)$. Consider the set $X$ of $n$-tuples $x_0,\dots,x_{n-1}\in\{+,-,1,-m\}$ where for each $j$ we require $x_j=1$ if and only if $x_{j-1}=-m$. Subscripts are modulo $n$.

Define $w_j(+)=\zeta^j$ and $w_j(-)=\zeta^{-j}$ and $w_j(1)=1$ and $w_j(-m)=-m$. Expanding $2\cos\frac{2j\pi}{n}=w_j(+)+w_j(-)$ gives the desired trace as $\sum_{x\in X}w(x)$ where $w(x)=\prod_{j=0}^{n-1}w_j(x_j)$.

Cyclicly permuting by moving the end element to the start has the effect of multiplying $w(x)$ by $\zeta^{N_+(x)-N_-(x)}$ where $N_+$ and $N_-$ are the number of $+$'s and $-$'s. The total weight from sequences with $N_+(x)-N_-(x)\not\in\{-n,0,n\}$ is therefore zero.

Now we need another group action. Given $x\in X$ that is not all $+$'s, for each maximal run of $+$'s, move the $-$ or $-m,1$ after the run to the beginning. Each replacement multiplies $w(x)$ by $zeta^{2k}$ where $k$ is the length of the run, so this procedure gives a sequence $x'$ with $w(x')=w(x)\zeta^{2N_+(x)}$. This shows that the total contribution from all sequences with $(N_+(x),N_-(x))=(a,b)$ is zero whenever $a\not\in\{0,n/2,n\}$. A similar argument applies when $b\not\in\{0,n/2,n\}$.

The only non-constant terms not accounted for are those containing no $+$'s or $-$'s, i.e. $1,-m,1,-m,\dots,1,-m$ and $-m,1,-m,\dots,1,-m,1$ for even $n$, which contribute the $2(-m)^{n/2}$.

I believe this can be evaluated by expanding cos as a sum of exponentials.

Let $\zeta=\exp(2i\pi/n)$. Consider the set $X$ of $n$-tuples $x_0,\dots,x_{n-1}\in\{+,-,1,-m\}$ where for each $j$ we require $x_j=1$ if and only if $x_{j-1}=-m$. Subscripts are modulo $n$.

Define $w_j(+)=\zeta^j$ and $w_j(-)=\zeta^{-j}$ and $w_j(1)=1$ and $w_j(-m)=-m$. Expanding $2\cos\frac{2j\pi}{n}=w_j(+)+w_j(-)$ gives the desired trace as $\sum_{x\in X}w(x)$ where $w(x)=\prod_{j=0}^{n-1}w_j(x_j)$.

Cyclicly permuting by moving the end element to the start has the effect of multiplying $w(x)$ by $\zeta^{N_+(x)-N_-(x)}$ where $N_+$ and $N_-$ are the number of $+$'s and $-$'s. The total weight from sequences with $N_+(x)-N_-(x)\not\in\{-n,0,n\}$ is therefore zero.

Now we need another group action. Given $x\in X$ that is not all $+$'s, for each maximal run of $+$'s, move the $-$ or $-m,1$ after the run to the beginning. Each replacement multiplies $w(x)$ by $\zeta^{2k}$ where $k$ is the length of the run, so this procedure gives a sequence $x'$ with $w(x')=w(x)\zeta^{2N_+(x)}$. This shows that the total contribution from all sequences with $(N_+(x),N_-(x))=(a,b)$ is zero whenever $a\not\in\{0,n/2,n\}$. A similar argument applies when $b\not\in\{0,n/2,n\}$.

The only non-constant terms not accounted for are those containing no $+$'s or $-$'s, i.e. $1,-m,1,-m,\dots,1,-m$ and $-m,1,-m,\dots,1,-m,1$ for even $n$, which contribute the $2(-m)^{n/2}$.

I believe this can be evaluated by expanding cos as a sum of exponentials.

Let $\zeta=\exp(2i\pi/n)$. Consider the set $X$ of $n$-tuples $x_0,\dots,x_{n-1}\in\{+,-,1,-m\}$ where for each $j$ we require $x_j=1$ if and only if $x_{j-1}=-m$. Subscripts are modulo $n$.

Define $w_j(+)=\zeta^j$ and $w_j(-)=\zeta^{-j}$ and $w_j(1)=1$ and $w_j(-m)=-m$. Expanding $2\cos\frac{2j\pi}{n}=w_j(+)+w_j(-)$ gives the desired trace as $\sum_{x\in X}w(x)$ where $w(x)=\prod_{j=0}^{n-1}w_j(x_j)$.

Cyclicly permuting by moving the end element to the start has the effect of multiplying $w(x)$ by $\zeta^{N_+(x)-N_-(x)}$ where $N_+$ and $N_-$ are the number of $+$'s and $-$'s. The total weight from sequences with $N_+(x)-N_-(x)\not\in\{-n,0,n\}$ is therefore zero.

Now we need another group action. Observe is that swapping a "+" with a consecutive "-" is just like swapping a "+" with a "-m, 1" - both multiply $w(x)$ by $\zeta^2$. So it makes sense to try to permute $x$ holding "the pattern of $-$, $1$ and $-m$'s" constant.

Given a sequence $x$ and an index $j$ such that $x_j$ is not $1$, the following procedure defines two lists, the "plus or not" list, and the "- or -m" list.

• The index $J$ is initialized to $j$.
• If $x_J$ is $+$, append "plus" to the "plus or not" list, and increase $J$ by $1$.
• If $x_J$ is $-$, append "not" to the "plus or not" list, append "-" to the "- or -m" list, and increase $J$ by $1$.
• If $x_J$ is $-m$, append "not" to the "plus or not" list, append "-" to the "- or -m" list, and increase $J$ by $2$.
• Repeat until $J$ comes back round to its original value $j$.

Note that for fixed $j$ we can reconstruct $x$ from these two lists. Moving the last item on the "plus or not" list to the start (fixing $j$ and the "- or -m" list) multiplies $w(x)$ by $\zeta^{2N_+(x)}$. This shows that the total contribution from sequences with $N_+(x)\notin\{0,n/2,n\}$ is zero. A similar argument applies to sequences with $N_-(x)\notin\{0,n/2,n\}$, also restricting to $N_+(x)\in\{0,n/2,n\}$.

The only non-constant terms not accounted for are those containing no $+$'s or $-$'s, i.e. $1,-m,1,-m,\dots,1,-m$ and $-m,1,-m,\dots,1,-m,1$ for even $n$, which contribute the $2(-m)^{n/2}$.

I believe this can be evaluated by expanding cos as a sum of exponentials.

Let $\zeta=\exp(2i\pi/n)$. Consider the set $X$ of $n$-tuples $x_0,\dots,x_{n-1}\in\{+,-,1,-m\}$ where for each $j$ we require $x_j=1$ if and only if $x_{j-1}=-m$. Subscripts are modulo $n$.

Define $w_j(+)=\zeta^j$ and $w_j(-)=\zeta^{-j}$ and $w_j(1)=1$ and $w_j(-m)=-m$. Expanding $2\cos\frac{2j\pi}{n}=w_j(+)+w_j(-)$ gives the desired trace as $\sum_{x\in X}w(x)$ where $w(x)=\prod_{j=0}^{n-1}w_j(x_j)$.

Cyclicly permuting by moving the end element to the start has the effect of multiplying $w(x)$ by $\zeta^{N_+(x)-N_-(x)}$ where $N_+$ and $N_-$ are the number of $+$'s and $-$'s. The total weight from sequences with $N_+(x)-N_-(x)\not\in\{-n,0,n\}$ is therefore zero.

Now we need another group action. Given $x\in X$ that is not all $+$'s, for each maximal run of $+$'s, move the $-$ or $-m,1$ after the run to the beginning. Each replacement multiplies $w(x)$ by $zeta^{2k}$ where $k$ is the length of the run, so this procedure gives a sequence $x'$ with $w(x')=w(x)\zeta^{2N_+(x)}$. This shows that the total contribution from all sequences with $(N_+(x),N_-(x))=(a,b)$ is zero whenever $a\not\in\{0,n/2,n\}$. A similar argument applies when $b\not\in\{0,n/2,n\}$.

The only non-constant terms not accounted for are those containing no $+$'s or $-$'s, i.e. $1,-m,1,-m,\dots,1,-m$ and $-m,1,-m,\dots,1,-m,1$ for even $n$, which contribute the $2(-m)^{n/2}$.

I believe this can be evaluated by expanding cos as a sum of exponentials.

Let $\zeta=\exp(2i\pi/n)$. Consider the set $X$ of $n$-tuples $x_0,\dots,x_{n-1}\in\{+,-,1,-m\}$ where for each $j$ we require $x_j=1$ if and only if $x_{j-1}=-m$. Subscripts are modulo $n$.

Define $w_j(+)=\zeta^j$ and $w_j(-)=\zeta^{-j}$ and $w_j(1)=1$ and $w_j(-m)=-m$. Expanding $2\cos\frac{2j\pi}{n}=w_j(+)+w_j(-)$ gives the desired trace as $\sum_{x\in X}w(x)$ where $w(x)=\prod_{j=0}^{n-1}w_j(x_j)$.

Cyclicly permuting by moving the end element to the start has the effect of multiplying $w(x)$ by $\zeta^{N_+(x)-N_-(x)}$ where $N_+$ and $N_-$ are the number of $+$'s and $-$'s. The total weight from sequences with $N_+(x)-N_-(x)\not\in\{-n,0,n\}$ is therefore zero.

Now we need another group action. Observe is that swapping a "+" with a "-" is just like swapping a "+" with a "-m, 1" - both multiply $w(x)$ by $\zeta^2$. So it makes sense to try to permute $x$ holding "the pattern of $-$, $1$ and $-m$'s" constant.

Given a sequence $x$ and an index $j$ such that $x_j$ is not $1$, the following procedure defines two lists, the "plus or not" list, and the "- or -m" list.

• The index $J$ is initialized to $j$.
• If $x_J$ is $+$, append "plus" to the "plus or not" list, and increase $J$ by $1$.
• If $x_J$ is $-$, append "not" to the "plus or not" list, append "-" to the "- or -m" list, and increase $J$ by $1$.
• If $x_J$ is $-m$, append "not" to the "plus or not" list, append "-" to the "- or -m" list, and increase $J$ by $2$.
• Repeat until $J$ comes back round to its original value $j$.

Note that for fixed $j$ we can reconstruct $x$ from these two lists. Moving the last item on the "plus or not" list to the start (fixing $j$ and the "- or -m" list) multiplies $w(x)$ by $\zeta^{2N_+(x)}$. This shows that the total contribution from sequences with $N_+(x)\notin\{0,n/2,n\}$ is zero. A similar argument applies to sequences with $N_-(x)\notin\{0,n/2,n\}$, also restricting to $N_+(x)\in\{0,n/2,n\}$.

The only non-constant terms not accounted for are those containing no $+$'s or $-$'s, i.e. $1,-m,1,-m,\dots,1,-m$ and $-m,1,-m,\dots,1,-m,1$ for even $n$, which contribute the $2(-m)^{n/2}$.

I believe this can be evaluated by expanding cos as a sum of exponentials.

Let $\zeta=\exp(2i\pi/n)$. Consider the set $X$ of $n$-tuples $x_0,\dots,x_{n-1}\in\{+,-,1,-m\}$ where for each $j$ we require $x_j=1$ if and only if $x_{j-1}=-m$. Subscripts are modulo $n$.

Define $w_j(+)=\zeta^j$ and $w_j(-)=\zeta^{-j}$ and $w_j(1)=1$ and $w_j(-m)=-m$. Expanding $2\cos\frac{2j\pi}{n}=w_j(+)+w_j(-)$ gives the desired trace as $\sum_{x\in X}w(x)$ where $w(x)=\prod_{j=0}^{n-1}w_j(x_j)$.

Cyclicly permuting by moving the end element to the start has the effect of multiplying $w(x)$ by $\zeta^{N_+(x)-N_-(x)}$ where $N_+$ and $N_-$ are the number of $+$'s and $-$'s. The total weight from sequences with $N_+(x)-N_-(x)\not\in\{-n,0,n\}$ is therefore zero.

Now we need another group action. Observe is that swapping a "+" with a consecutive "-" is just like swapping a "+" with a "-m, 1" - both multiply $w(x)$ by $\zeta^2$. So it makes sense to try to permute $x$ holding "the pattern of $-$, $1$ and $-m$'s" constant.

Given a sequence $x$ and an index $j$ such that $x_j$ is not $1$, the following procedure defines two lists, the "plus or not" list, and the "- or -m" list.

• The index $J$ is initialized to $j$.
• If $x_J$ is $+$, append "plus" to the "plus or not" list, and increase $J$ by $1$.
• If $x_J$ is $-$, append "not" to the "plus or not" list, append "-" to the "- or -m" list, and increase $J$ by $1$.
• If $x_J$ is $-m$, append "not" to the "plus or not" list, append "-" to the "- or -m" list, and increase $J$ by $2$.
• Repeat until $J$ comes back round to its original value $j$.

Note that for fixed $j$ we can reconstruct $x$ from these two lists. Moving the last item on the "plus or not" list to the start (fixing $j$ and the "- or -m" list) multiplies $w(x)$ by $\zeta^{2N_+(x)}$. This shows that the total contribution from sequences with $N_+(x)\notin\{0,n/2,n\}$ is zero. A similar argument applies to sequences with $N_-(x)\notin\{0,n/2,n\}$, also restricting to $N_+(x)\in\{0,n/2,n\}$.

The only non-constant terms not accounted for are those containing no $+$'s or $-$'s, i.e. $1,-m,1,-m,\dots,1,-m$ and $-m,1,-m,\dots,1,-m,1$ for even $n$, which contribute the $2(-m)^{n/2}$.