This is an immediate successor of Chebyshev polynomials of the first kind and primality testing and does not have any other motivation - although original motivation seems to be huge since a positive answer (if not too complicated) would give a very efficient primality test (see the linked question for details).

Recall that the Chebyshev polynomials $T_n(x)$ are defined by $T_0(x)=1$, $T_1(x)=x$ and $T_{n+1}(x)=2xT_n(x)-T_{n-1}(x)$, and there are several explicit expressions for their coefficients. Rather than writing them down (you can find them at the Wikipedia link anyway), let me just give a couple of examples: $$ T_{15}(x)=-15x(1-4\frac{7\cdot8}{2\cdot3}x^2+4^2\frac{6\cdot7\cdot8\cdot9}{2\cdot3\cdot4\cdot5}x^4-4^3\frac{8\cdot9\cdot10}{2\cdot3\cdot4}x^6+4^4\frac{10\cdot11}{2\cdot3}x^8-4^5\frac{12}{2}x^{10}+4^6x^{12})+4^7x^{15} $$ $$ T_{17}(x)=17x(1-4\frac{8\cdot9}{2\cdot3}x^2+4^2\frac{7\cdot8\cdot9\cdot10}{2\cdot3\cdot4\cdot5}x^4-4^3\frac{8\cdot9\cdot10\cdot11}{2\cdot3\cdot4\cdot5}x^6+4^4\frac{10\cdot11\cdot12}{2\cdot3\cdot4}x^8-4^5\frac{12\cdot13}{2\cdot3}x^{10}+4^6\frac{14}{2}x^{12}-4^7x^{14})+4^8x^{17} $$ It seems that $n$ is a prime if and only if all the ratios in the parentheses are integers; this is most likely well known and easy to show.

The algorithm described in the above question requires determining whether, for an odd $n$, coefficients of the remainder from dividing $T_n(x)-x^n$ by $x^r-1$, for some fairly small prime $r$ (roughly $\sim\log n$) are all divisible by $n$. In other words, denoting by $a_j$, $j=0,1,2,...$ the coefficients of $T_n(x)-x^n$, we have to find out whether the sum $s_j:=a_j+a_{j+r}+a_{j+2r}+...$ is divisible by $n$ for each $j=0,1,...,r-1$.

The question then is: given $r$ and $n$ as above ($n$ odd, $r$ a prime much smaller than $n$), is there an efficient method to find these sums $s_j$ without calculating all $a_j$? I. e., can one compute $T_n(x)$ modulo $x^r-1$ (i. e. in a ring where $x^r=1$) essentially easier than first computing the whole $T_n(x)$ and then dividing by $x^r-1$ in the ring of polynomials?

(As already said, only the question of divisibility of the result by $n$ is required; also $r$ is explicitly given (it is the smallest prime with $n$ not $\pm1$ modulo $r$). This might be easier to answer than computing the whole polynomials mod $x^r-1$.)


2 Answers 2


There's a rapid algorithm to compute $T_n(x)$ modulo $(n,x^r-1)$. Note that $$ \pmatrix{T_n(x) \\ T_{n-1}(x)} = \pmatrix { 2x & -1 \\ 1&0} \pmatrix{T_{n-1}(x) \\ T_{n-2}(x)} = \pmatrix { 2x & -1 \\ 1&0}^{n-1} \pmatrix{ x\\ 1}. $$ Now you can compute these matrix powers all modulo $(n, x^{r}-1)$ rapidly by repeated squaring. Clearly $O(\log n)$ multiplications (of $2\times 2$ matrices) are required, and the matrices have entries that are polynomials of degree at most $r$ and coefficients bounded by $n$. So the complexity is a polynomial in $r$ and $\log n$.

  • 1
    $\begingroup$ Thank you very much! I've now implemented your algorithm at another answer and that very primitive implementation seems to really be logarithmically efficient (the actual $r$ needed is itself somewhere near $\log n$) $\endgroup$ Nov 21, 2017 at 19:00
  • 3
    $\begingroup$ We tried implementing the algorithm in C++ here without directly computing T_n(x) github.com/dendisuhubdy/Chebyshev-primality-test/blob/master/… $\endgroup$ Dec 7, 2017 at 5:09
  • 2
    $\begingroup$ And, in the same way that Fibonacci number calculation by matrix powers can be optimised, this can be optimised with the recurrences $T_{2n} = 2 T_n{}^2 - 1$ and $T_{2n+1} = 2 T_n T_{n+1} - x$ $\endgroup$ Sep 12, 2019 at 15:09

The coefficient of $x^j$ in $(T_n(x)\bmod (x^r-1))$ equals the coefficient of $t^{n+r-j-1}$ in $$\frac{(1+t^2)^{r-j}}{2^{r-j}} \frac{((1+t^2)^{r-1}t - 2^{r-1}t^{r-1})}{((1+t^2)^r - 2^rt^r)}.$$ This coefficient can be explicitly computed as $$\sum_{k\geq 0} 2^{rk-r+j} \left( \binom{r-1-j-rk}{\frac{n+r-j-2-rk}{2}} - 2^{r-1}\binom{-j-rk}{\frac{n-j-rk}{2}}\right).$$ (here the binomial coefficients are zero whenever their lower indices are noninteger or negative)

  • $\begingroup$ And also zero if the lower index is integer, positive and exceeds the upper index? $\endgroup$ Nov 22, 2017 at 8:41
  • $\begingroup$ @მამუკა ჯიბლაძე: As usual $\endgroup$ Nov 22, 2017 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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