54
$\begingroup$

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 PARI/GP without directly computing $T_n(x)$ .

Python script that implements this test can be found here.

An Android app that implements this test can be found here.

ADDED

I offer $100$ € for a proof of this claim. Proof must be published in Journal of Number Theory.

$\endgroup$
  • 3
    $\begingroup$ @მამუკა ჯიბლაძე A stack overflow error has occurred . $\endgroup$ – Peđa Terzić Nov 17 '17 at 16:04
  • 2
    $\begingroup$ 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$ $\endgroup$ – Igor Rivin Nov 17 '17 at 17:07
  • 3
    $\begingroup$ @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. $\endgroup$ – მამუკა ჯიბლაძე Nov 21 '17 at 12:29
  • 3
    $\begingroup$ I've now posted a separate question about that $\endgroup$ – მამუკა ჯიბლაძე Nov 21 '17 at 13:38
  • 2
    $\begingroup$ @IgoRivin We tried implementing the algorithm in C++ here without directly computing T_n(x) github.com/dendisuhubdy/Chebyshev-primality-test/blob/master/…. This is really cool! $\endgroup$ – Dendi Suhubdy Dec 7 '17 at 5:10
28
+50
$\begingroup$

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:

enter image description here

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:

enter image description here

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.

$\endgroup$
  • 3
    $\begingroup$ That IS amazing, thanks for investigating! $\endgroup$ – Igor Rivin Nov 21 '17 at 19:39
  • 1
    $\begingroup$ 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). $\endgroup$ – Ryan O'Donnell Nov 22 '17 at 3:24
  • 4
    $\begingroup$ @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. $\endgroup$ – Vít Tuček Nov 22 '17 at 13:48
  • 2
    $\begingroup$ @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. $\endgroup$ – მამუკა ჯიბლაძე Nov 23 '17 at 8:13
  • 3
    $\begingroup$ @მამუკაჯიბლაძე 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. $\endgroup$ – Vít Tuček Nov 23 '17 at 15:06
8
$\begingroup$

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

enter image description here

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

enter image description here

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Nov 20 '17 at 5:41
  • $\begingroup$ @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). $\endgroup$ – მამუკა ჯიბლაძე Nov 20 '17 at 5:49
  • $\begingroup$ 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. $\endgroup$ – მამუკა ჯიბლაძე Nov 20 '17 at 6:03
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Nov 20 '17 at 6:19
0
$\begingroup$

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

$\endgroup$

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.