# Hermite polynomials and primality testing

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

Inspired by Agrawal's conjecture 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 $$H_n(x)$$ be Hermite polynomial , then $$n$$ is either a prime number or Fermat pseudoprime to base $$2$$ if and only if $$H_n(x) \equiv 2x^n \pmod {x^r-1,n}$$ .

You can run this test here .

Mathematica implementation of test :

n=31;
r=3;
While[Mod[n,r]==0 || PowerMod[n,2,r]==1,r=NextPrime[r]];
If[PolynomialMod[PolynomialRemainder[HermiteH[n,x],x^r-1,x],n]-PolynomialRemainder[2*x^n,x^r-1,x]===0,Print["probably prime"],Print["composite"]];


The claim is not true.

It is not true that if $$H_n(x) \equiv 2x^n \pmod {x^r-1,n}$$, then $$n$$ is either a prime number or Fermat pseudoprime to base $$2$$.

Proof :

Let us consider the case where $$n$$ is an even number greater than $$2$$.

So, $$n$$ is neither a prime number nor Fermat pseudoprime to base $$2$$.

Using the following expression $$H_{2k}=(-1)^k2^k(2k-1)!!\left(1+\sum_{j=1}^{k}\frac{(-4k)(-4k+4)\cdots (-4k+4j-4)}{(2j)!}x^{2j}\right)$$ we have, using $$(n-1)!!\cdot 2^{\frac n2}(\frac n2)!=n!$$, \begin{align}H_{n}&=(-1)^{\frac n2}2^{\frac n2}(n-1)!!\left(1+\sum_{j=1}^{\frac n2}\frac{(-2n)(-2n+4)\cdots (-2n+4j-4)}{(2j)!}x^{2j}\right) \\\\&=(-1)^{\frac n2}2^{\frac n2}(n-1)!!\bigg(1+\frac{(-2n)(-2n+4)\cdots (-4)}{n!}x^{n} \\&\qquad\qquad\qquad\qquad\qquad+\sum_{j=1}^{\frac n2-1}\frac{(-2n)(-2n+4)\cdots (-2n+4j-4)}{(2j)!}x^{2j}\bigg) \\\\&=(-1)^{\frac n2}2^{\frac n2}(n-1)!!\bigg(1+\frac{(-4)^{\frac n2}(\frac n2)!}{n!}x^{n}+\sum_{j=1}^{\frac n2-1}\frac{(-4)^j(\frac n2)!}{(\frac{n-2j}{2})!(2j)!}x^{2j}\bigg) \\\\&=2x^n+(2^n-2)x^n+\frac{(-1)^{\frac n2}n!}{(\frac n2)!}+n(-1)^{\frac n2}\sum_{j=1}^{\frac n2-1}\frac{(n-2j-1)!}{(\frac{n-2j}{2})!}\binom{n-1}{2j}(-4)^j \end{align}

So, there is a polynomial $$f$$ with integer coefficients such that $$H_n(x)=2x^n+(2^n-2)x^n+(x^r-1)\times 0+nf$$ Now, if $$n$$ is an even pseudoprime to base 2, then we get $$2^n-2\equiv 0\pmod n$$, so it follows that $$H_n(x) \equiv 2x^n \pmod {x^r-1,n}$$.

Therefore, $$n=161038$$ is a counterexample.$$\qquad\blacksquare$$

It is true that if $$n$$ is either a prime number or Fermat pseudoprime to base $$2$$, then $$H_n(x) \equiv 2x^n \pmod {x^r-1,n}$$.

Proof :

For $$n=3$$, we have $$H_3(x)=2x^3+(x^r-1)\times 0+3(2x^3-4x)\equiv 0\pmod {x^r-1,3}$$

In the following, $$n$$ is an odd number greater than $$3$$.

Using the following expression $$H_{2k+1}(x)=(-1)^k\cdot 2^{k+1}(2k+1)!!\bigg(x+\sum_{j=1}^{k}\frac{(-4k)(-4k+4)\cdots (-4k+4j-4)}{(2j+1)!}x^{2j+1}\bigg)$$ we have, using $$n!!\cdot 2^{\frac{n-1}{2}}(\frac{n-1}{2})!=n!$$,

\begin{align}H_{n}(x)&=(-1)^{\frac{n-1}{2}}\cdot 2^{\frac{n+1}{2}}n!!\bigg(x+\sum_{j=1}^{\frac{n-1}{2}}\frac{(-2n+2)(-2n+6)\cdots (-2n+4j-2)}{(2j+1)!}x^{2j+1}\bigg) \\\\&=(-1)^{\frac{n-1}{2}}\cdot 2^{\frac{n+1}{2}}n!!\bigg(x+\frac{(-2n+2)(-2n+6)\cdots (-4)}{n!}x^{n} \\&\qquad\qquad\qquad\qquad+\sum_{j=1}^{\frac{n-3}{2}}\frac{(-2n+2)(-2n+6)\cdots (-2n+4j-2)}{(2j+1)!}x^{2j+1}\bigg) \\\\&=(-1)^{\frac{n-1}{2}}\cdot 2^{\frac{n+1}{2}}n!!\bigg(x+\frac{(-4)^{\frac{n-1}{2}}(\frac{n-1}{2})!}{n!}x^{n} \\&\qquad\qquad\qquad\qquad\qquad+\sum_{j=1}^{\frac{n-3}{2}}\frac{(-4)^j(\frac{n-1}{2})!}{(2j+1)!(\frac{n-2j-1}{2})!}x^{2j+1}\bigg) \\\\&=(-1)^{\frac{n-1}{2}}\cdot 2^{\frac{n+1}{2}}n!!x+2^nx^{n} \\&\qquad\qquad\qquad\qquad+\sum_{j=1}^{\frac{n-3}{2}}\frac{n!\cdot(-1)^{\frac{n-1}{2}}\cdot 2^{\frac{n+1}{2}}(-4)^{j}}{(2j+1)!\left(\frac{n-2j-1}{2}\right)!\cdot 2^{\frac{n-1}{2}}}x^{2j+1} \\\\&=(-1)^{\frac{n-1}{2}}\cdot 2^{\frac{n+1}{2}}n!!x+2^nx^{n} \\&\qquad\qquad\qquad\qquad+n\sum_{j=1}^{\frac{n-3}{2}}\frac{(n-2j-2)!\binom{n-1}{2j+1}(-1)^{\frac{n-1}{2}}\cdot 2\cdot (-4)^{j}}{\left(\frac{n-2j-1}{2}\right)!}x^{2j+1} \\\\&=2x^n+(2^n-2)x^{n}+2n(-1)^{\frac{n-1}{2}}\sum_{j=\color{red}{0}}^{\frac{n-3}{2}}\frac{(n-2j-2)!}{\left(\frac{n-2j-1}{2}\right)!}\binom{n-1}{2j+1}(-4)^{j}x^{2j+1} \end{align}

So, there is a polynomial $$g$$ with integer coefficients such that $$H_n(x)=2x^n+(2^n-2)x^n+(x^r-1)\times 0+ng$$

Since $$n$$ is either a prime number or Fermat pseudoprime to base $$2$$, we get $$2^n-2\equiv 0\pmod n$$.

It follows that $$H_n(x)\equiv 2x^n\pmod{x^r-1,n}\qquad\blacksquare$$

• Thank you for the clarification, I really appreciate it. – Peđa Terzić Nov 17 '18 at 16:33

Please let me know if this is way off base.

We know $$r\not|n$$ and $$n^{2} \not \equiv 1\ mod\ r$$. Therefore, from the latter part of the statement we know $$r\not| n^{2}-1$$ which is equivalent to $$r\not |(n-1)$$ and $$r\not|(n+1)$$. So for any $$n$$ we have two cases. The first being $$n-1$$ is odd, $$n$$ is even, and $$n+1$$ is odd. The second being $$n-1$$ is even, $$n$$ is odd, and $$n+1$$ is even. Since in both circumstances we have an even integer we know $$n\not = 2$$. Because we have three consecutive integers, that are greater than 2, we must have at least one that is divisible by $$3$$.

So the fact that we cannot have $$3$$, but you state that $$n$$ is a prime number greater than $$2$$ or pseudo-prime to base $$2$$ (smallest is $$341$$?) makes your proof invalid due to a contradiction in your consequent.

Once again, sorry if I am not understanding something.