18
$\begingroup$

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$.)

$\endgroup$
25
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • 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 '17 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$ – Dendi Suhubdy Dec 7 '17 at 5:09
  • 1
    $\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$ – Peter Taylor Sep 12 '19 at 15:09
5
$\begingroup$

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)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ And also zero if the lower index is integer, positive and exceeds the upper index? $\endgroup$ – მამუკა ჯიბლაძე Nov 22 '17 at 8:41
  • $\begingroup$ @მამუკა ჯიბლაძე: As usual $\endgroup$ – Max Alekseyev Nov 22 '17 at 12:26

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.