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.



On the number of polynomials that divide $x^{q-1}-1$ in some subspaces of $\mathbb F_q[x]$
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.


