On the number of \(k\)-normal elements and \(\mathbb{F}_q\)-practical numbers (Q6565503)

Let \(\mathbb{F}_{q^n}\) be a finite field with \(q^n\) elements, where \(q\) is a prime power and \(n\) is a positive integer. An element \(\alpha \in \mathbb{F}_{q^n}\) is normal over \(\mathbb F_q\) if \(B = \{1, \alpha, \alpha^q, \dots, \alpha^{q^{n-1}}\}\) forms a basis of \(\mathbb F_{q^n}\) over \(\mathbb F_q\). It is known that \(\alpha\) is normal if and only if \(g_{\alpha}(x) = \alpha x^{n-1} + \alpha^q x^{n-2} + \dots + \alpha^{q^{n-1}}\) and \(x^n-1\) are relatively prime over \(\mathbb F_{q^n}\). By the Normal Basis Theorem, normal elements always exist. More generally, for \(0 \le k \le n-1\), \(\alpha \in \mathbb F_{q^n}\) is a \(k\)-normal element if \(\gcd(g_{\alpha}(x), x^n-1)\) has degree \(k\). The case \(k=0\) recovers the normal elements. A natural question asks for the number of \(k\)-normal elements in \(\mathbb F_{q^n}\) when they exist, and it is known that \(k\)-normal elements exist precisely when \(x^n-1\) has a divisor \(f \in \mathbb F_q[x]\) of degree \(n-k\). Some formulas depending on the factorization of \(x^n-1\) into irreducible were developed over time, but they were not easy to handle numerically. Another question asks for which values of \(q\), \(n\) and \(k\) nice formulas can be obtained for the number of \(k\)-normal elements of \(\mathbb F_{q^n}\) over \(\mathbb F_q\). In this way, the following definition plays an important role. We say that a positive integer \(n\) is \(\mathbb F_q\)-practical if, for any \(1 \le k \le n-1\), \(x^n-1\) is divisible by a polynomial of degree \(k\) over \(\mathbb F_q\).\N\NIn this paper, the authors obtain explicit formulas for the number of \(k\)-normal elements of \(\mathbb F_{q^n}\) over \(\mathbb F_q\). After that, they use these formulas to obtain new conditions for the existence of these elements and give an arithmetical characterization of \(\mathbb F_q\)-practical numbers. Finally, they use this characterization to produce explicit examples of important families of these numbers. Their main results are displayed below.\N\NTheorem 3.2. Let \(0 \le k < n\) be an integer. The number of \(k\)-normal elements of \(\mathbb F_{q^n}\) over \(\mathbb F_q\) is \N\[\NN_k = \sum_{(\alpha_{r,i}) \in \mathcal A_k} \prod_{r\mid d} \prod_{\substack{i=1 \\ \alpha_{r,i}>0}}^{v_r} q^{r(\alpha_{r,i})}(q^r-1),\N\]\Nwhere \(\mathcal A_k\) is the set of sequences \((\alpha_{r,i})\), for \(r \mid d\) and \(1 \le i \le v_r\), such that \(0 \le \alpha_{r,i} \le p^s\) and \(\sum_{r \mid d} r \sum_{i=1}^{v_r} \alpha_{r,i} = n-k\). In particular, if \(\gcd(q,n)=1\), then \N\[\NN_k = \sum_{(\alpha_r) \in \mathcal A_k} \prod_{r\mid d} \binom{v_r}{a_r}(q^r-1)^{a_r},\N\]\Nwhere \(\alpha_k\) is the set of sequences \((\alpha_r)_{r \mid d}\) such that \(\sum_{r \mid d} r a_r = n-k\) and \(0 \le a_r \le v_r\).\N\NIn Section 4, for \(k \in \{1,2,3\}\), they also obtain closed expressions for \(N_k\). In Section 5, they defined the set \(\mathcal B_k\) and then provided a criteria for the existence of \(k\)-normal elements in terms of \(\mathcal B_k\). Using this criteria, in Section 6 the authors study the \(\mathbb F_q\)-practical numbers. Let \(n = p^sn_0\), where \(q\) is a power of \(p\) and \(p \nmid n_0\). Some of the results are displayed below.\N\NProposition 6.1. If \(n_0 > 1\) and \(\mathrm{ord}_t(q) > p^s+1\) for each prime divisor \(t\) of \(n_0\), then \(n\) is not \(\mathbb F_q\)-practical.\N\NProposition 6.3. \(n\) is \(\mathbb F_q\)-practical if and only if for every \(r \mid d\), \(r \neq 1\), for which \(v_r \neq 0\), we have \(p^s \sum_{\substack{u \mid d \\ u < r}} uv_u \ge r-1\).\N\NIn particular, there exists \(s_0\) such that \(n\) is \(\mathbb F_q\)-practical for every \(s \ge s_0\).\N\NThey also show that, under certain conditions, the product of \(\mathbb F_q\)-practical numbers is \(\mathbb F_q\)-practical. Moreover, they define strong \(\mathbb F_q\)-practical numbers. These are the numbers \(n\) for which \(\frac{x^n-1}{x-1}\) has a monic factor \(f \in \mathbb F_q[x]\) of degree \(k\) for every \(0 \le k \le n-1\). They prove several similar properties as those for \(\mathbb F_q\)-practical numbers. In particular, they prove that if every prime divisor of \(n\) divides \(p(q-1)\), then \(n\) is strong \(\mathbb F_q\)-practical, and also they exhibit new families of \(\mathbb F_q\)-practical as well as families of strong \(\mathbb F_q\)-practical numbers.