# Existence of a polynomial $Q$ of degree $\geq (p-1)/4$ in $\mathbb F_p[x]$ such that $QQ'$ factorizes into distinct linear factors

For all primes up to $$p=89$$ there exists a product $$Q=\prod_{j=1}^d(x-a_j)$$ involving $$d\geq (p-1)/4$$ distinct linear factors $$x-a_j$$ in $$\mathbb F_p[x]$$ such that $$Q'$$ has all its roots in $$\mathbb F_p$$. Since $$Q$$ has only simple roots, the product $$QQ'$$ has also only simple roots.

(It is obvious that a factorization into distinct linear factors of $$QQ'$$ implies that $$Q$$ has degree at most $$(p+1)/2$$. My computations suggest however that it seems to be hard to go substantially beyond $$p/4$$.)

An example for $$p=53$$ is given by $$Q=x(x^2-5^2)(x^2-8^2)(x^2-10^2)(x^2-12^2)(x^2-14^2)(x^2-16^2)$$ with derivative $$Q'=13(x^2-4^2)(x^2-13^2)(x^2-19^2)(x^2-20^2)(x^2-21^2)(x^2-22^2).$$

Similar examples of the form $$x\prod_{j=1}^7(x^2-a_j^2)$$ for $$59$$ and $$61$$ are given by $$\{a_1,\ldots,a_7\}=\{1,3,12,15,17,18,22\}$$ for $$59$$ and by $$\{1,3,6,8,11,21,22\}$$ for $$61$$.

For $$p=67$$ we have $$x\prod_{j=1}^8(x^2-a_j^2)$$ with $$\{a_1,\ldots,a_8\}=\{1,2,5,9,15,23,31,32\}$$.

For $$p=71$$ and $$73$$, we have $$\prod_{j=1}^9(x^2-a_j^2)$$ with $$\{a_1,\ldots,a_9\}$$ given by $$\{1,2,3,5,18,20,29,30,33\}$$ for $$p=71$$ and by $$\{1,2,5,17,19,22,27,32,33\}$$ for $$p=73$$.

For $$p=79$$, we have $$\prod_{j=1}^{10}(x^2-a_j^2)$$ with $$\{a_1,\ldots,a_{10}\}=\{1,2,6,10,15,17,18,20,33,37\}$$.

For $$p=83$$, we have $$x\prod_{j=1}^{10}(x^2-a_j^2)$$ with $$\{a_1,\ldots,a_{10}\}=\{1,2,3,5,12,16,21,33,36,41\}$$.

For $$p=89$$, we have $$\prod_{j=1}^{11}(x^2-a_j^2)$$ with $$\{a_1,\ldots,a_{11}\}=\{1,10,14,15,18,33,34,36,37,43,44\}$$.

(I did a search over all polynomials up to $$p=23$$ and restricted then my attention to polynomials which are either even or odd for all primes up to $$89$$.)

Adopting a very naive viewpoint, the existence of such a polynomial of degree $$\geq \lambda p$$ for some $$\lambda>0$$ and for almost all primes would be somewhat surprising: There are $${p\choose \lambda p}$$ such polynomials of degree $$\lambda p$$ given as a product of $$\lambda p$$ distinct linear factors in $$\mathbb F_p[x]$$. Adopting the very naive viewpoint that derivatives of these polynomials behave randomly with respect to decomposition into irreducible factors, the probability for such a polynomial $$Q\in\mathbb F_p[x]$$ (with $$QQ'$$ factorizing completely into distinct linear factors) to exist should be roughly given by $$\left(\lambda^{2\lambda}(1-\lambda)^{2(1-\lambda)}p^\lambda\right)^{-p}$$ (up to polynomial contributions) which decays exponentially fast.

Question: Can this naive argument be made rigourous or do such polynomials of degree at least $$(p-1)/4$$ (or perhaps of degre at least $$\lambda p$$ for some $$\lambda >0$$) exist for all primes?

Remark (added after adding additional examples up to $$83$$): The outlook for the existence of such polynomials (of degre at least $$(p-1)/4$$) for all primes starts to look better: Indeed, for $$p=83$$, the naive argument given above (slightly improved) yields a fairly small probability: $${41\choose 10}{31\choose 10}83^{-10}\sim 0.0032\ .$$ This suggests that we should have ended up empty-handed at this point. (End of added remark.)

Motivation: The analogous question is open for degree $$7$$ over $$\mathbb Z[x]$$ (existence of a polynomial $$Q\in\mathbb Z[x]$$ of degree $$7$$ such that $$QQ'$$ has $$13$$ distinct roots in $$\mathbb Z$$), see proposition 27 of Proposals for polymath projects.

A stronger question (over finite fields) is to ask for polynomials of maximal degree in $$\mathbb F_p[x]$$ such that $$Q$$ and all its derivatives $$Q^{(1)},Q^{(2)},\ldots$$ factorize into distinct linear factors. One can either admit or forbid common roots among different derivatives. Forbidding them gives of course the trivial upper bound $$O(\sqrt{p})$$ on the maximal degree. I guess that admitting them does not allow substantially higher degrees.

Given an integer $$d$$, I guess that such polynomials of degree $$\geq d$$ exist in $$\mathbb F_p[x]$$ except for a finite number of small primes. (A bug in my code made me think that there are no such polynomials of degree $$\geq 6$$ which prompted me to post a now deleted question on MO.)

It would of course be interesting to have information on the maximal degree $$d_p$$ for (the two versions of) this stronger question. (Interestingly, the stronger question is computationally slightly easier since the set of all such polynomials (not necessarily of maximal degree) is closed under derivation.)

• $Q$ and $Q'$ have common roots if and only if $Q$ has multiple roots. Sep 7 at 7:45

Such polynomials always exist, examples are Dickson polynomials of the first kind (with parameter $$1$$). For a positive integer $$n$$ these degree $$n$$ polynomials $$D_n$$ are most conveniently defined implicitly by $$D_n(z+1/z)=z^n+1/z^n$$.
For $$p=4m\pm1$$ the polynomial $$D_m(x)$$ has the required property, which is to say that $$D_m(x)\cdot D_m'(x)$$ divides $$x^p-x$$.
In fact, using $$D_n'(z+1/z)=n\frac{z^n-1/z^n}{z-1/z}$$ we verify the identity (which holds in any characteristic) $$$$D_m(x)\cdot D_m'(x)\cdot D_{2m\pm1}'(x)\cdot(x^2-4)=m\cdot(2m\pm1)\cdot(D_{4m\pm1}(x)-x),$$$$ and the claim follows since $$D_p(x)=x^p$$ in characteristic $$p$$.
Remark: I have no idea about the strong version of the other question for the higher derivatives. The polynomials which achieve maximal degrees for given $$p$$ do not seem to be of a particular form (even in those cases when they are unique up to trivial transformations).
• Nice, this works! To add the details: $D_m(z+z^{-1}) = 0$ iff $z^m$ is a square root of $-1$ and $D'_m(z+z^{-1}) = m \tfrac{z^m-z^{-m}}{z-z^{-1}}$ so $D'_m(z+z^{-1})=0$ iff $z^m = \pm 1$ and $z \neq \pm 1$. So, either way, we are looking at $4m$-th roots of unity. Oct 27 at 17:49
• If $p=4m+1$, all $4m$-th roots of unity are in $\mathbb{F}_p$, so the values of $z+z^{-1}$ are likewise. If $p = 4m-1$, then the $4m$-th roots of unity are in $\mathbb{F}_{p^2}$, but they all obey $z^p = z^{-1}$ so, for $z$ a $4m$-th root of unity, the value of $z+z^{-1}$ is Frobenius fixed and hence in $\mathbb{F}_p$. Oct 27 at 17:50