On the number of polynomials that divide $x^{q-1}-1$ in some subspaces of $\mathbb F_q[x]$

Question

Let $\mathbb F_q$ be a finite field (where $q$ is in general a power of a prime), and let $e, k$ be positive integers with $k \leq e < q-1$. Let $f_0(x), \ldots, f_k(x) \in \mathbb F_q[x]$ be polynomials such that $$e= \deg f_0 > \deg f_1 > \cdots > \deg f_k,$$ and let us define $W:= \langle f_0, f_1, \ldots, f_k \rangle$ the subspace of dimension $k+1$ of $\mathbb F_q[x]_{\leq e}$ seen as vector space over $\mathbb F_q$. Furthermore let $T_e$ be the set defined by $$T_e:=\left\{p(x) \in \mathbb F_q[x] \;|\; \deg p =e \;, lc(p)=1, \; p(x)|x^{q-1}-1 \right\}. $$ I'd like to find $$ M_{e,k,q}:=\max | W \cap T_e|, $$ where the maximum is over all the subspaces of the form described above. Three simple cases are:

When $e=k$ then $M_{e,e,q}= \binom{q-1}{e}$.

When $e=q-2$ then $M_{q-2, k, q} =k+1$.

When $k=1$ then $M_{e,1,q}=q-e$.

When $k=0$ then $M_{e,0,q}=1$.

Maybe it could be useful the fact that, for $e<q-1$, $T_e$ is a set of generators of $\mathbb F_q[x]_{\leq e}$.

I think it's a quite difficult question, but i'd just like to know some non-obvious bounds on $|W \cap T_e|$.

EDIT: Of course $M_{e,k,q}\geq\dbinom{q-1-e+k}{k}$. Let us take $$f_k(x)= \prod_{i=1}^{e-k}(x- \alpha_i),$$ where $\alpha_i \in \mathbb F_q^*$ for every $i=1, \ldots, e-k$ and $\alpha_i \neq \alpha_j$ for every $i \neq j$. Moreover let us take, for $j=0, \ldots, k-1$, $$ f_j(x)= x^{k-j}f_k(x).$$ Then $W:=\langle f_0, \ldots, f_k \rangle$ has exactly $\dbinom{q-1-e+k}{k}$ elements of $T_e$.

I suppose that $M_{e,k,q}$ is exactly $\dbinom{q-1-e+k}{k}$. In fact in the three cases described above it seems to work. Could anyone help me to prove it?

Thanks.

Answer 1

Generalize your definition slightly - Let $M_{e,k,q,r}$ be the max over $W$ and $S \subseteq \mathbb F_q^\times$ of cardinality $q-1-r$ of the number of squarefree monic polynomials over $\mathbb F_q$ lying in $W$ whose roots all lie in $S$.

Your lower bound clearly becomes

$$M_{e,k,q,r} \geq {q-1-e-r+k\choose k} $$

This is sharp when $e=k$ by the same argument you gave.

I claim this is sharp (for $k\leq e$ and $e+r \leq q-1$ so this is well-defined). This follows inductively from the following inequality:

$$M_{e,k,q,r} \leq \max \left( M_{e-1,k,q,r+1} , \frac{q-1-r}{e}M_{e-1,k-1,q,r+1} \right)$$

The argument is induction on $e$, with case $e=0$ trivial, and induction step

$$M_{e,k,q,r} \leq \max \left( {q-1-e-r+k\choose k} , \frac{q-1-r}{e}{q-1-e-r+k-\choose k-1} \right)= \max\left( 1,\frac{q-1-r}{e} \frac{k}{q-1-e-r+k}\right){q-1-e-r+k\choose k} $$

If we let $a=k$, $b=e-k$, $c=q-1-e-r$ then $a,b,c \geq 0$ so $(a+b+c)a \leq (a+b) (a+c)$ so $\frac{a+b+c}{a+b} \frac{a}{c+a} \leq 1$ so we get $M_{e,k,q,r} = {q-1-e-r+k\choose k}$ as desired.

It suffices to verify that inequality. There is either an element $\alpha$ in $S$ such that all elements of $W$ vanish on $S$ or not.

If there is, then we divide each element of $W$ by $(x-\alpha)$, and all elements that previously had roots lying in $S$ now have roots lying in $S - \{\alpha\}$. Thus we reduce the degree by $1$, leave the dimension of the subspace fixed, and increase $r$ by one, without reduceing the number of solutions.

If there is not, then we bound the number of pairs of an element of $W$ monic, squarefree, with all roots in $S$ and a root $\alpha$ of $W$. The number of these pairs is exactly $e$ times the number of $W$ monic, squarefree, with all roots in $S$, so we will divide by $e$ afterwards. For each element $\alpha \in S$, a codimension $1$ subspace of $W$ vanishes on it. Then, as in the previous case, we can divide all elements of that subspace by $x-\alpha$, producing a new space of polynomials one degree lower, and one dimension lower, where we are counting squarefree monic polynomials whose roots all lie in $S- \{\alpha\}$. Multiplying by $|S|$, we obtain the number of ordered pairs, and dividing by $e$, we get the upper bound.