11
$\begingroup$

Can you provide a proof or a counterexample to the following claim :

Let $n$ be a natural number greater than one and let $T_{n}(x)$ be Chebyshev polynomial of the first kind , then $n$ is prime if and only if :$\displaystyle\sum_{k=0}^{n-1}2T_{n-1}\left(\frac{k}{2}\right) \equiv -1 \pmod n$ .

You can run this test here .

I have tested this claim up to 10000 .

I was searching for counterexample using the following two Pari/GP codes :

Chebyshev1(lb,ub)={
forprime(n=lb,ub,
if(!(Mod(sum(k=0,n-1,2*polchebyshev(n-1,1,k/2)),n)==n-1),print(n)))
}

Chebyshev2(lb,ub)={
forcomposite(n=lb,ub,
if((Mod(sum(k=0,n-1,2*polchebyshev(n-1,1,k/2)),n)==n-1),print(n)))
}
$\endgroup$
  • $\begingroup$ Mathematica code: n = 2; While[PrimeQ[n]==(Mod[Sum[2ChebyshevT[n-1,k/2],{k,0,n-1}],n]==n-1),n++]. It will only halt if it founds a counter-example. None was found for $2\le n\le 10784$. $\endgroup$ – AccidentalFourierTransform Jan 29 '18 at 21:58
  • $\begingroup$ Note that $-1\equiv p-1 \mod p $ which is equal the Euler function $\varphi(p)$ for prime $p$. Here's a bit wider guess checked for $n\le 5000$: $\mathrm{lhs}(n)\mod n=\varphi(n)$ iff $n=2^k$ or $n=p^{2k-1}$, $k\in \mathbb N$ for prime $p\ge3$. $\endgroup$ – Andrew Jan 30 '18 at 9:51
  • $\begingroup$ On the other hand, there are many $n$ such that lhs($n$) $\mod n = 0$. This seems to occur for about $1/4$ of all integers, e.g. 499 times for $n \le 2000$. $\endgroup$ – Hans Engler Jan 30 '18 at 14:21
4
+50
$\begingroup$

This is a partial answer.

This answer proves that if $n$ is prime, then $$\sum_{k=0}^{n-1}2T_{n-1}\left(\frac{k}{2}\right) \equiv -1 \pmod n\tag1$$

For $n=2$, $(1)$ holds since $$\sum_{k=0}^{1}2T_{1}\left(\frac{k}{2}\right)=2T_1(0)+2T_1\left(\frac 12\right)=2\cdot 0+2\cdot\frac 12\equiv -1\pmod 2$$

For $n=3$, $(1)$ holds since $$\small\sum_{k=0}^{2}2T_{2}\left(\frac{k}{2}\right)=2T_2(0)+2T_2\left(\frac 12\right)+2T_2(1)=2\cdot (-1)+2\cdot\left(-\frac 12\right)+2\cdot 1\equiv -1\pmod 3$$

In the following, $n$ is prime greater than three.

For $2\le k\le n-1$, using that $\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)=1$, we have $$\small\begin{align}&T_{n-1}\left(\frac{k}{2}\right)\\\\&=\frac 12\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n-1}+\frac 12\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n-1}\\\\&=\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)\left(\frac 12\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n-1}+\frac 12\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n-1}\right)\\\\&=\frac 12\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^n+\frac 12\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^n\\\\&=\frac k4\left(\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n}+\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n}\right)\\\\&\qquad\quad +\frac 12\sqrt{\left(\frac{k}{2}\right)^2-1}\ \left(\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n}-\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n}\right)\end{align}$$

By the binomial theorem, $$\small\begin{align}T_{n-1}\left(\frac{k}{2}\right)&=\frac 12\cdot \frac k2\sum_{i=0}^{n}\binom ni\cdot \left(\frac k2\right)^{n-i}\left(\left(-\sqrt{\left(\frac k2\right)^2-1}\right)^i+\left(\sqrt{\left(\frac k2\right)^2-1}\right)^i\right)\\\\&\qquad\quad +\frac 12\sqrt{\left(\frac k2\right)^2-1}\ \sum_{i=0}^{n}\binom ni\cdot \left(\frac k2\right)^{n-i}\left(\left(-\sqrt{\left(\frac k2\right)^2-1}\right)^i-\left(\sqrt{\left(\frac k2\right)k^2-1}\right)^i\right)\\\\&=\frac 12\cdot \frac k2\sum_{j=0}^{(n-1)/2}\binom{n}{2j}\cdot \left(\frac k2\right)^{n-2j}\cdot 2\left(\sqrt{\left(\frac k2\right)^2-1}\right)^{2j}\\\\&\qquad\quad +\frac 12\sqrt{\left(\frac k2\right)^2-1}\ \sum_{j=1}^{(n+1)/2}\binom{n}{2j-1}\cdot \left(\frac k2\right)^{n-(2j-1)}\cdot (-2)\left(\sqrt{\left(\frac k2\right)^2-1}\right)^{2j-1}\\\\&=\sum_{j=0}^{(n-1)/2}\binom{n}{2j}\cdot \left(\frac k2\right)^{n-2j+1}\left(\left(\frac k2\right)^2-1\right)^{j}-\sum_{j=1}^{(n+1)/2}\binom{n}{2j-1}\cdot \left(\frac k2\right)^{n-(2j-1)}\left(\left(\frac k2\right)^2-1\right)^{j}\end{align}$$

Multiplying the both sides by $2^{n+1}$, we get $$2^{n+1}T_{n-1}\left(\frac{k}{2}\right)=\sum_{j=0}^{(n-1)/2}\binom{n}{2j}\cdot k^{n-2j+1}\left(k^2-4\right)^{j}-\sum_{j=1}^{(n+1)/2}\binom{n}{2j-1}\cdot k^{n-(2j-1)}\left(k^2-4\right)^{j}$$ Since $k^{n+1}=k^2\cdot k^{n-1}\equiv k^2\cdot 1\equiv k^2\pmod n$ for $2\le k\le n-1$ by Fermat's little theorem, and $\binom nj\equiv 0\pmod n$ for $1\le j\le n-1$, we have, for $2\le k\le n-1$, $$4T_{n-1}\left(\frac{k}{2}\right)\equiv k^{n+1}-(k^2-4)^{(n+1)/2}\equiv k^2-(k^2-4)^{(n+1)/2}\pmod n$$

Since this holds for $k=0,1$ as well, we have, letting $N:=\frac{n+1}{2}$, $$\begin{align}\sum_{k=0}^{n-1}4T_{n-1}\left(\frac k2\right)&\equiv \sum_{k=0}^{n-1}\left(k^2-(k^2-4)^{N}\right)\equiv \frac{(n-1)n(2n-1)}{6}-\sum_{k=0}^{n-1}(k^2-4)^{N}\pmod n\\\\&\stackrel{*}\equiv -\sum_{k=0}^{n-1}(k^2-4)^{N}\equiv -(-4)^N-\sum_{k=1}^{n-1}(k^2-4)^{N}\pmod n\\\\&\equiv (-1)^{N+1}\cdot 2^{n+1}-\sum_{k=1}^{n-1}\sum_{j=0}^{N}\binom Nj(k^2)^{j}\cdot (-4)^{N-j}\pmod n\\\\&\equiv (-1)^{N+1}\cdot 4-\sum_{j=0}^{N}\binom Nj(-4)^{N-j}S_{2j}\pmod n\tag2\end{align}$$ where $\stackrel{*}\equiv $ comes from that $(n-1)(2n-1)\equiv 0\pmod 6$, and we defined $S_i$ as $\displaystyle\sum_{k=1}^{n-1}k^i$.

Now, we use the following lemma :

Lemma : $S_0\equiv S_{n-1}\equiv -1\pmod n, S_{n+1}\equiv 0\pmod n$ and $S_i\equiv 0\pmod n$ for $1\le i\le n-2$.

Proof for the lemma :

We have $S_0\equiv \displaystyle\sum_{k=1}^{n-1}1\equiv -1\pmod n$. By Fermat's little theorem, $S_{n-1}\equiv S_0\equiv -1\pmod n$.

Next, let us prove $S_i\equiv 0\pmod n$ for $1\le i\le n-2$ by induction.

The base case : $S_1\equiv \displaystyle\sum_{k=1}^{n-1}k^1\equiv \frac{(n-1)n}{2}\equiv 0\pmod n$.

Suppose that $S_i\equiv 0\pmod n$ for $1\le i\le j$. Since we have $$2^{j+2}-1^{j+2}=\sum_{i=0}^{j+1}\binom{j+2}{i}1^i$$ $$3^{j+2}-2^{j+2}=\sum_{i=0}^{j+1}\binom{j+2}{i}2^i$$ $$\vdots$$ $$n^{j+2}-(n-1)^{j+2}=\sum_{i=0}^{j+1}\binom{j+2}{i}(n-1)^i$$ adding these, we get $$n^{j+2}-1=\sum_{k=1}^{n-1}\sum_{i=0}^{j+1}\binom{j+2}{i}k^i=\sum_{i=0}^{j+1}\binom{j+2}{i}S_i=n-1+(j+2)S_{j+1}+\sum_{i=1}^{j}\binom{j+2}{i}S_i$$ from which we have $$S_{j+1}=\frac{1}{j+2}\left(n^{j+2}-n-\sum_{i=1}^{j}\binom{j+2}{i}S_i\right)$$ By the inductive hypothesis, we see that $S_{j+1}\equiv 0\pmod n$ if $j\le n-3$.

Finally, by Fermat's little theorem, $S_{n+1}\equiv \displaystyle\sum_{k=1}^{n-1}k^{n+1}\equiv \displaystyle\sum_{k=1}^{n-1}k^{2}\equiv S_2\equiv 0\pmod n.\qquad\blacksquare$

Using the lemma, we have, from $(2)$,

$$\begin{align}\sum_{k=0}^{n-1}4T_{n-1}&\equiv (-1)^{N+1}\cdot 4-\sum_{j=0}^{N}\binom Nj(-4)^{N-j}S_{2j}\pmod n\\\\&\equiv (-1)^{N+1}\cdot 4-(-4)^{N}\cdot (-1)-\binom{N}{(n-1)/2}(-4)^{N-(n-1)/2}(-1)\pmod n\\\\&\equiv -\frac{n+1}{2}\cdot (-4)\cdot (-1)\equiv -2\pmod n\end{align}$$ It follows from $\gcd(n,2)=1$ that $$\sum_{k=0}^{n-1}2T_{n-1}\left(\frac k2\right)\equiv -1\pmod n$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Stupid question. How is in the case of $n=2$, $1\equiv -1\ (\text{mod} 2)$? Thanks. $\endgroup$ – pisoir Jan 30 '18 at 22:19
  • $\begingroup$ @pisoir: $a\equiv b\pmod 2$ means that $a-b$ is divisible by $2$. You might want to see here. $\endgroup$ – mathlove Jan 31 '18 at 3:42
  • $\begingroup$ This direction follows from the simple fact that the polynomial $2T_n(x/2)$ is monic and the coefficients are integers... $\endgroup$ – user141614 Jan 31 '18 at 8:10

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.