Bases of the special form

Question

Let $R = \mathrm{GF}(q)$, $S = \mathrm{GF}(q^n), \ n\geq 2$ be extension of $R$, $h$ be a primitive element of $S$. I want to count or estimate the number $N$ of bases of the following form. Let $$\vec{\beta} = (\beta_0,\beta_1,\ldots,\beta_{n-1})$$ be a basis of the space $_RS$ with the property that there exists $k\in\{1,2,\ldots,n-1\}$ such that $$ \vec{\beta'} = (\beta_0,\ldots,\beta_{k-1},h\beta_k,\ldots,h\beta_{n-1}) $$ is a basis of the space $_RS$.

It is easily to see that $N\geq (q^n-q)\prod_{j=1}^{n-1}(q^n-2q^{j}+q^{j-1})$. This estimation obtained from the case $k = n-1$

It is also easily to see, that the basis of the form $(e,h,\ldots, h^{n-1})$ has the desirable property. My another question is: is there another approches for construction such bases?

Answer 1

Let me estimate the number $N_k$ of such bases for a fixed $k$. Aside remark. The number of bases for $k=k_0$ equals the number of those for $k=n-k_0$, as the bijection $(\beta_0,\dots,\beta_{n-1})\to (\beta_{n-1},\dots,\beta_{k_0},h^{-1}\beta_{k_0-1},\dots,h^{-1}\beta_0)$$ shows.

So let us fix any $k$. The first $k$ elements can be chosen in $\prod_{i=0}^{k-1}(q^n-q^i)$ many ways. Each next element $\beta_i$ should lie outside $V_i=\langle \beta_0,\dots,\beta_{i-1}\rangle$, as well as outside $V_i'=\langle h^{-1}\beta_0,\dots,h^{-1}\beta_{k-1},\beta_k,\dots,\beta_{i-1}\rangle$. If $d_i=\dim(V_i\cap V_i')$, then $\beta_i$ can be chosen in $q^n-2q^i+q^{d_i}$ many ways; notice that $i\geq d_i\geq \max(i-k,2i-n)$. Thus $$ N_k\geq \prod_{i=0}^{k-1}(q^n-q^i)\prod_{i=k}^{n-1}(q^n-2q^i+q^{\max(i-k,2i-n)}). $$

This estimate can be improved by noticing that $d_i\geq d_{i-1}+1$. So, e.g., for $k=1$, if we choose $\beta_1=(h^{-1}+1)\beta_0$, then $V_2=V_2'$, so $d_i=i$ for $i\geq 2$. But it seems appropriate to choose large $k$...

Notice that for $k=n-1$, the estimate gives $$ N_{n-1}\geq (q^n-2q^{n-1}+q^{n-2}).\prod_{i=0}^{n-2}(q^n-q^i), $$ which is $1-\frac1q$ of all bases. Do you need much sharper bounds?