Let $Z$ be a non real complex number such that $Z^{11}=1$. If $$N = \sum_{k=1}^{10} \frac{1}{Z^{8k}+Z^{k}+1}]$$ Then find N.

$\DeclareMathOperator{cis}{cis}$ My trial

$Z = \cos(\theta) + i \sin(\theta) \Rightarrow Z=\cis(\theta) = \cis(\frac{2c\pi}{11})$ where $c=1,2....11$.

Now $$\begin{align}Z^{8k} + Z^{k} +1 &=\left(\cis\frac{2c\pi}{11}\right)^{8k}+\left(\cis \frac{2c\pi}{11}\right)^{k} +1\\&= \cis \frac{16kc\pi}{11}+\cis \frac{2kc\pi}{11}+1\\&= \left(\cos \frac{16kc\pi}{11}+\cos\frac{2kc\pi}{11}+1\right) +i\left(\sin\frac{16kc\pi}{11}+\sin\frac{2kc\pi}{11}\right)\end{align}$$

I am unable to simplify further after this step.

Trial 2

$Z^{8k} + Z^{k} +1 = Z^{-3k} +Z^{k} +1=\frac{Z^{3k}}{Z^{4k}+ Z^{3k} +1}$

...... Struck up after this. I even tried changing the denominator to the form $Z^{k} -1$ but was unable to do so. In all the ways I am stuck up after few steps. Any hints/help will be appreciated. Thanks in advance

  • $\begingroup$ math.stackexchange.com/questions/3610673/… $\endgroup$ Apr 17 '20 at 5:25
  • $\begingroup$ The answer is incomplete ,moreover a direct computation has been done in the above link@lab bhattacharjee $\endgroup$ Apr 17 '20 at 5:58
  • $\begingroup$ By calculating $Res( y(1+x+x^8) -1, (x^11-1)/(x-1))$, the answer is 40/23. $\endgroup$
    – Calvin Lin
    Apr 17 '20 at 6:20
  • $\begingroup$ @karthikeyakurella It links to a different problem (though with a similar setup). $\endgroup$
    – Calvin Lin
    Apr 17 '20 at 6:20
  • $\begingroup$ Are we working pre-calculus? The other question is similar, but the difference makes that question simpler than this. That summand there can be represented as $$\frac {z^k-1}{z^{3k} - 1}$$ which doesn't work here. $\endgroup$ Apr 17 '20 at 13:50

Working with a Smaller Denominator

Note that $$ \begin{align} \sum_{z^{11}=1}\frac1{z^8+z+1} &=\sum_{z^{11}=1}\frac{z^3}{z^4+z^3+1}\\ \end{align} $$ Furthermore, $$ \begin{align} p(z) &=\frac{z^{44}+12z^{33}+44z^{22}+11z^{11}+1}{z^4+z^3+1}\\ &=z^{40}-z^{39}+z^{38}-z^{37}+z^{35}-2z^{34}+3z^{33}-3z^{32}+2z^{31}\\ &\phantom{=\ }+9z^{29}-6z^{28}+4z^{27}-4z^{26}-5z^{25}+11z^{24}-15z^{23}+19z^{22}-14z^{21}\\ &\phantom{=\ }+3z^{20}+12z^{19}+13z^{18}+z^{17}-4z^{16}-8z^{15}-5z^{14}+4z^{13}+8z^{11}\\ &\phantom{=\ }-3z^{10}-z^9+z^8+2z^7+z^6-z^4-z^3+1\\ &\equiv-20z^{10}+4z^9+13z^8+25z^7-5z^6+z^5-14z^4-11z^3+16z^2-17z+31\\ &=q(z)\quad\left(\text{mod }z^{11}-1\right) \end{align} $$ Thus, $$ \begin{align} \sum_{z^{11}=1}\frac{69\,z^3}{z^4+z^3+1} &=\sum_{z^{11}=1}\frac{\left(z^{44}+12z^{33}+44z^{22}+11z^{11}+1\right)z^3}{z^4+z^3+1}\\[3pt] &=\sum_{z^{11}=1}q(z)z^3\\ &=11\left[z^8\right]q(z)\\[9pt] &=143 \end{align} $$ which means $$ \sum_{z^{11}=1}\frac{z^3}{z^4+z^3+1}=\frac{143}{69} $$ Subtracting $\frac13$ for the $z=1$ term, we get an answer of $$ \sum_{\substack{z^{11}=1\\z\ne1}}\frac1{z^8+z+1}=\frac{40}{23} $$

Using the Extended Euclidean Algorithm

It finally dawned on me that what we are looking for is $$ \frac1{z^8+z+1}\quad\left(\text{mod }x^{11}-1\right) $$ and the easiest way to get that is with the Extended Euclidean Algorithm. Using Mathematica, the command



{1,{1/69(-56+17z-16z^2+11z^3+14z^4-z^5+5z^6-25z^7), 1/69(13+4z-20z^2+31z^3-17z^4+16z^5-11z^6-14z^7+z^8-5z^9+25z^10)}}

which says that $$ \bbox[5px,border:2px solid #C0A000]{\textstyle\frac1{z^8+z+1}\equiv\frac{25z^{10}-5z^9+z^8-14z^7-11z^6+16z^5-17z^4+31z^3-20z^2+4z+13}{69}\quad\left(\text{mod }z^{11}-1\right)} $$ Using the algorithm outlined in this answer, and applying it to polynomials, we can see what Mathematica did: $$ \begin{array}{|c|c|c|c|c|} \hline{\begin{array}{c}\text{linear combination}\\[-6pt]\text{of $z^{11}-1$}\\[-6pt]\text{and $z^8+z+1$}\end{array}}&\text{coefficient of $z^{11}-1$}&\text{coefficient of $z^8+z+1$}&{\begin{array}{c}\text{quotient of}\\[-6pt]\text{the previous two}\\[-6pt]\text{linear combinations}\end{array}}\\\hline z^{11}-1&1&0\\ z^8+z+1&0&1\\ -z^4-z^3-1&1&-z^3&z^3\\ z^3-z^2+2z+1&z^4-z^3+z^2-z&-z^7+z^6-z^5+z^4+1&-z^4+z^3-z^2+z\\ 5z+1&z^5+z^4-z^3+z^2-2z+1&-z^8-z^7+z^6-z^5+2z^4-z^3+z+2&-z-2\\ \color{#090}{\frac{69}{125}}&\frac{-25z^7+5z^6-z^5+14z^4+11z^3-16z^2+17z-56}{125}&\color{#C00}{\frac{25z^{10}-5z^9+z^8-14z^7-11z^6+16z^5-17z^4+31z^3-20z^2+4z+13}{125}}&\frac{25z^2-30z+56}{125}\\ \textstyle 0&\frac{125}{69}\left(z^8+z+1\right)&-\frac{125}{69}\left(z^{11}-1\right)&\frac{125}{69}(5z+1)\\\hline \end{array} $$

The first two rows are given.

Each new row is computed by computing the rightmost element as the quotient of the leftmost elements in the previous two rows. The other elements are computed by subtracting the quotient just computed times the previous row from the row prior to that.

The colored elements in the table above say that $$ \textstyle\frac{\color{#090}{\frac{69}{125}}}{z^8+z+1}\equiv\color{#C00}{\frac{25z^{10}-5z^9+z^8-14z^7-11z^6+16z^5-17z^4+31z^3-20z^2+4z+13}{125}}\quad\left(\text{mod }z^{11}-1\right) $$ Dividing by the green term, we get the boxed result we got from Mathematica.

  • $\begingroup$ Nice - how did you find a multiple of $z^4 + z^3 + 1$ in powers of $z^{11}$? $\endgroup$ Apr 17 '20 at 16:12
  • $\begingroup$ Look at $\left\{1,z^{11},z^{22},z^{33}\right\}\left(\text{mod }z^4+z^3+1\right)$. These form a basis for polynomials mod $z^4+z^3+1$. Write $z^{44}\left(\text{mod }z^4+z^3+1\right)$ as a linear combination of these basis elements (using a $4\times4$ matrix inversion). $\endgroup$
    – robjohn
    Apr 17 '20 at 16:20
  • $\begingroup$ Thanks - always good to learn a new trick. $\endgroup$ Apr 17 '20 at 16:21
  • $\begingroup$ @PaulSinclair: I added the same solution without changing the denominator. This requires inverting an $8\times8$ matrix. $\endgroup$
    – robjohn
    Apr 17 '20 at 23:30
  • $\begingroup$ Ahh, what wonderful days we live in, where inverting an $8\times 8$ matrix is something one is willing to do on a whim. $\endgroup$ Apr 18 '20 at 0:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.