Chebyshev polynomials of the first kind and primality testing

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.

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 .

• @მამუკა ჯიბლაძე A stack overflow error has occurred . – Peđa Terzić Nov 17 '17 at 16:04
• This is very cool, but, if true, can it be made into a useful algorithm? As stated it is about an $O(n^2)$ algorithm to determine primality of $n$ – Igor Rivin Nov 17 '17 at 17:07
• @IgorRivin Seems that it depends on how fast one can find $T_n(x)\mod x^r-1$ (for very small $r$, about $\log n$) without computing $T_n(x)$ itself completely. The way it is implemented now, the whole $T_n(x)$ is found first, and I think it is worse than polynomial then. – მამუკა ჯიბლაძე Nov 21 '17 at 12:29
• I've now posted a separate question about that – მამუკა ჯიბლაძე Nov 21 '17 at 13:38
• Not that I think I am going to earn the reward, but could you please choose a non-Elsevier journal? Algebra and Number Theory is an open journal whose standards are at least as high. – David E Speyer Nov 6 '19 at 16:26

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_] :=

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.

• That IS amazing, thanks for investigating! – Igor Rivin Nov 21 '17 at 19:39
• Looks like using the FFT method to multiply polynomials, and assuming r = O(log n), the whole algorithm takes O(log^3 n) time (times some polyloglogs, depending on your exact model of computation). – Ryan O'Donnell Nov 22 '17 at 3:24
• @RyanO'Donnell Which is the same complexity as in the Agrawal et al. paper. I don't understand what, if anything, was gained by using Čebyšev's polynomials. – Vít Tuček Nov 22 '17 at 13:48
• @VítTuček You are right, that one is in fact simpler: have to find $n-1$st power of $x+a$ modulo $x^r-1$ instead of $n-1$st power of a 2$\times$2 matrix. On the other hand, in their case $r$ is larger and one has to test for several $a$s. – მამუკა ჯიბლაძე Nov 23 '17 at 8:13
• @მამუკაჯიბლაძე Look at their conjecture in section six -- the one mentioned by the OP. I mean, it's great that this conjecture seems plausible also for $T_n$ and not only for $(x-1)^n$. Maybe it could be worthwhile to to try to find some large class of polynomials with this property. – Vít Tuček Nov 23 '17 at 15:06

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:

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

• It is clear that n is prime implies the desired mod n congruence. What results do you get for composite n? In particular, are there any composite n for which the mod n congruence hold and the x^r-1 congruence fails? Gerhard "Bidirectionals Are Not Always Symmetric" Paseman, 2017.11.19. – Gerhard Paseman Nov 20 '17 at 5:41
• @GerhardPaseman Experimentally, the mod n congruence holds iff n is prime. I believe it is not difficult to show using explicit expressions for coefficients of $T_n$,$$a_{n-2k}=(-1)^k2^{n-2k}\frac n2\frac{(n-k-1)!}{k!(n-2k)!},$$$k=0,1,...$ (all others zero). – მამუკა ჯიბლაძე Nov 20 '17 at 5:49
• But you probably wanted to ask the opposite, right? Because if the mod n congruence holds, it will also hold mod x^r-1. The nontrivial fact to prove is that if mod n fails then it will also fail mod x^r-1. – მამუკა ჯიბლაძე Nov 20 '17 at 6:03
• I probably did mean the opposite. Yes, if n is composite, then both congruences should fail. Gerhard "Doesn't Work With Ideals Ideally" Paseman, 2017.11.19. – Gerhard Paseman Nov 20 '17 at 6:19

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 prme $$p\mid n$$. At the same time, it can be seen that $$\begin{split} T_n \equiv x^n\pmod{x^5-1,\ 3}\quad&\Longleftrightarrow\quad n\equiv 3,\ 27,\ 243,\text{ or } 342\pmod{625}\\ T_n \equiv x^n\pmod{x^5-1,\ 7}\quad&\Longleftrightarrow\quad n\equiv 7,\ 343,\ 16807,\text{ or } 24878\pmod{42035}\\ T_n \equiv x^n\pmod{x^5-1,\ 13}\quad&\Longleftrightarrow\quad n\equiv 13,\ 2197,\ 371293,\text{ or } 554762\pmod{928265} \end{split}$$ and so on. (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.