Chebyshev polynomials of the first kind and primality testing

Question

Can you provide a proof or a counterexample for the claim given below ?

Inspired by Agrawal's conjecture in this paper and by Theorem 4 in this paper I have formulated the following claim :

Let $n$ be a natural number greater than two . Let $r$ be the smallest odd prime number such that $r \nmid n$ and $n^2 \not\equiv 1 \pmod r$ . Let $T_n(x)$ be Chebyshev polynomial of the first kind , then $n$ is a prime number if and only if $T_n(x) \equiv x^n \pmod {x^r-1,n}$ .

You can run this test here .

I have tested this claim up to $5 \cdot 10^4$ and there were no counterexamples .

EDIT

Algorithm implementation in Sage without directly computing $T_n(x)$ .

Python script that implements this test can be found here.

The Android app that implements this test can be found on Google Play.

ADDED

I offer $100$ € for a proof of this claim. The proof must be published in one of the following journals: Journal of Number Theory , Algebra & Number Theory , Moscow Journal of Combinatorics and Number Theory .

Answer 1

Wow. This deserves a separate answer.

As I mentioned in a comment, motivated by the question, in a previous comment, by Igor Rivin whether an efficient primality test can be made if the statement in the question is true, I asked a separate question about whether one could efficiently compute $T_n(x)$ modulo $x^r-1,n$. That question got a brilliant answer by Lucia, which enables to really demonstrate that if the statement in the question is true, one indeed obtains a very efficient primality test based on it.

I made this quick-and-dirty Mathematica code

polmul[f_, g_, r_, n_] := Mod[f.NestList[RotateRight, g, r - 1], n]

matmul[a_, b_, r_, n_] :=  Mod[
 {{polmul[a[[1, 1]], b[[1, 1]], r, n] + polmul[a[[1, 2]], b[[2, 1]], r, n], 
   polmul[a[[1, 1]], b[[1, 2]], r, n] + polmul[a[[1, 2]], b[[2, 2]], r, n]}, 
  {polmul[a[[2, 1]], b[[1, 1]], r, n] + polmul[a[[2, 2]], b[[2, 1]], r, n], 
   polmul[a[[2, 1]], b[[1, 2]], r, n] + polmul[a[[2, 2]], b[[2, 2]], r, n]}}, n]

matsq[a_, r_, n_] := matmul[a, a, r, n]

matpow[a_, k_, r_, n_] := If[k == 1, a,
 If[EvenQ[k],
  matpow[matsq[a, r, n], k/2, r, n], 
  matmul[a, matpow[matsq[a, r, n], (k - 1)/2, r, n], r, n]
 ]
]

xmat[r_, n_] :=
 {{PadRight[{0, 2}, r], PadRight[{n - 1}, r]},
  {PadRight[{1}, r], ConstantArray[0, r]}}

isprime[n_] := With[{r = smallestr[n]}, 
 If[r == 0, n == 2,
  With[{xp = matpow[xmat[r, n], n - 1, r, n]},
   Mod[RotateRight[xp[[1, 1]]] + xp[[1, 2]], n]
    === PadRight[Append[ConstantArray[0, Mod[n, r]], 1], r]
  ]
 ]
]

where smallestr is as in my other answer.

Running this on $n$ up to 100000 (all answers correct) gives the following timing:

Seems that it is of at worst logarithmic order (as that answer by Lucia suggests) - actually the graph of $\log(\operatorname{time}(n))/\log\log(n)$ looks almost like going to be bounded above:

Since the algorithm involves a recursive procedure for matrix powers, in principle one also has to check memory use. Here I must confess results are strange, maybe it is something hardware-specific. $$ \begin{array}{r|l} \text{amount of memory}&\text{number of cases (out of 100000)}\\ \hline 32&1407\\ 64&94408\\ 80&1\\ 288&1\\ 320&42\\ 352&3\\ 392&8\\ 424&2316\\ 456&1812\\ 3452552&1 \end{array} $$ This last amount 3452552 corresponds to $n=65969$, I have no idea why it needed so much memory. As I said this might be something machine specific - maybe some garbage collection occurred at that point or something like that. Anyway, as opposed to memory measurement timing data seem to be very accurate, I used the Mathematica command AbsoluteTiming and documentation says it gives actual processor time used for the calculation with quite high precision.

Answer 2

Decided to make a cw answer with an illustration of time growth.

I've tried on Mathematica this:

isprime[n_] := 
 With[{r = smallestr[n]}, 
  If[r == 0, n == 2, 
   PolynomialMod[PolynomialRemainder[ChebyshevT[n, t] - t^n, t^r - 1, t], n] === 0
  ]
 ]

where

smallestr[n_] := Module[{r},
  If[n==1 \[Or] EvenQ[n], Return[0]];
  For[r = 3, MemberQ[{0, 1, r - 1}, Mod[n, r]], r = NextPrime[r + 1],
   If[r < n \[And] Mod[n, r] == 0, Return[0]]
  ];
  r
 ]

I've run it on $n$ up to about 31000 (all answers are correct); here is the graph of time needed as a function of $n$.

Growth looks like faster than polynomial - the graph of $\log(\text{time}(n))/\log(n)$ does not seem to stabilize:

On the other hand a rough upper bound on growth can be deduced from the fact that $\log(\text{time}(n))/(n\log(n))$ seems to go down:

Some additional remarks.

(0)

Datapoints are only for those $n$ which have positive value of smallestr, i. e. such that the corresponding $r$ is smaller than any nontrivial divisor of $n$. Understandably, for other $n$ calculation is qualitatively quicker.

(1)

Finding $r$ is very efficient: $$ \begin{array}{c|c} r&\text{smallest $n$ that requires this $r$}\\ \hline 11&29\\ 13&419\\ 19&1429\\ 23&315589\\ 29&734161\\ 31&1456729 \end{array} $$

(2)

Seems like $n$ is prime iff all coefficients of $T_n(x)-x^n$ are divisible by $n$. If true, this must be well known of course, but I don't know. Should be provable from the explicit form of coefficients of $T_n$.

(2')

Given (2), it is obvious that at prime $n$ the algorithm gives correct answer. To also prove that it detects composite $n$ one has to show the following. Denote by $a_0$, ..., $a_n$ the coefficients of $T_n(x)-x^n$. Then, if some of the $a_i$ is not divisible by $n$, then also one of the sums $s_j:=a_j+a_{j+r}+a_{j+2r}+...$, $j=0,...,r-1$ is not divisible by $n$. Seemingly if $a_j$ is not divisible by $n$ then $j$ is not coprime to $n$; maybe this can help.

Answer 3

I do not share excitement about this test and believe it admits false positives (i.e., pseudoprimes). Here are some supporting arguments.

Assuming that $n\equiv 2\text{ or }3\pmod{5}$, we will have $r=5$. A square-free composite integer $n$ will pass the test for $r=5$ if $T_n(x)\equiv x^n\pmod{x^5-1,p}$ for every prime $p\mid n$. At the same time, it can be seen that \begin{split} T_n(x) \equiv x^n\pmod{x^5-1,\ 3}\quad&\Longleftrightarrow\quad n\equiv 3,\ 27,\ 38,\text{ or } 137\pmod{205}\\ T_n(x) \equiv x^n\pmod{x^5-1,\ 7}\quad&\Longleftrightarrow\quad n\equiv 7,\ 343,\ 858,\text{ or } 4797\pmod{6005}\\ T_n(x) \equiv x^n\pmod{x^5-1,\ 13}\quad&\Longleftrightarrow\quad n\equiv 13,\ 2197,\ 14268,\text{ or } 54927\pmod{71405} \end{split} and so on. In general, for a prime $p\equiv 2,3\pmod5$ $$T_n(x) \equiv x^n\pmod{x^5-1,\ p}\quad\Longleftrightarrow\quad n\equiv p,\ p^3,\ p^5,\text{ or } p^7\pmod{5q_p},$$ where $q_p$ is the period of $T_n(x)\pmod{x^5-1,\ p}$. (Similar congruences hold for $r=7$.)

It is not clear why certain $n$ cannot satisfy such congruences modulo every $p\mid n$. I do not say that it is easy to find such $n$, but its existence seems quite plausible.

P.S. Also, notice that in the AKS test the value of $r$ is taken satisfying $r>\log(n)^2$ (in fact, even the order $o_r(n)>\log(n)^2$), and this makes huge difference. Perhaps, the present test can be saved from pseudoprimes as well by requiring $r$ be of the magnitude of $\log(n)$ or so.

UPDATE (2021-10-02). Congruences above have been corrected. Here is a Sage code for computing $q_p$.