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?


  • $\begingroup$ In other words, $M_{e,k,q}$ is the maximum number of elements of $T_e$ that span a space of dimension at most $k+1$, right? Also, since $T_e$ is closed under multiplication by $\mathbb F_q^*$, $M_{e,k,q}$ must be divisible by $q-1$, so I don’t see how you could get $k+1$ in the second example, unless you actually meant for the polynomials in $T_e$ to be monic. $\endgroup$ Jan 31 '14 at 19:55
  • 1
    $\begingroup$ @Emil Jeřábek: you're right. I forgot to write it in the definition of $T_e$. Now it should be right. $\endgroup$
    – Sfarla
    Jan 31 '14 at 20:15

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.

  • $\begingroup$ Thank you. The proof seems very clean amd elegant. I had to wait almost 3 years for an answer but at the end you solved my problem $\endgroup$
    – Sfarla
    Jan 25 '17 at 18:39

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.