Proof. Let \(\operatorname{DFT}(\mathbb{F}_q^n)\) denote the image of \(\mathbb{F}_q^n\) under the Discrete Fourier Transform. Define the set \[\mathcal{S}=\big\{\,\boldsymbol{y} \in \mathbb{F}_{q^m}^n : y_k^q = y_{qk} \text{ for all } k\in [n]\,\big\}.\] For any \(\boldsymbol{x}\in\mathbb{F}_q^n\), we have \[(\widehat{\boldsymbol{x}}_k)^q=\left(\sum_{j=0}^{n-1}x_j\omega^{jk}\right)^q=\sum_{j=0}^{n-1}x_j^q\omega^{qjk}=\sum_{j=0}^{n-1}x_j\omega^{qjk}=\widehat{\boldsymbol{x}}_{qk}.\] Consequently, \(\operatorname{DFT}(\mathbb{F}_q^n)\subset \mathcal{S}\).

Conversely, take an arbitrary \(\boldsymbol{y}\in \mathcal{S}\). We compute the \(q\)-th power of \(x_j\) as follows: \[x_j^q = \left( \frac{1}{n} \sum_{k=0}^{n-1} y_k \omega^{-jk} \right)^q = \left(\frac{1}{n}\right)^q \sum_{k=0}^{n-1} y_k^q (\omega^{-jk})^q = \frac{1}{n} \sum_{k=0}^{n-1} y_{qk} \omega^{-jqk} =\frac{1}{n} \sum_{l=0}^{n-1} y_l \omega^{-jl} = x_j,\] where \(l=qk\). Hence \(x_j \in \mathbb{F}_q\) for all \(j\), which implies \(\boldsymbol{x} \in \mathbb{F}_q^n\) and \(\boldsymbol{y} = \operatorname{DFT}(\boldsymbol{x})\). Consequently, \(\mathcal{S}\subset \operatorname{DFT}(\mathbb{F}_q^n)\). ◻

Proof. Since \(\tau(\boldsymbol{x})_j = x_{j-1}\) for \(j = 0,1,\dots,n-1\), where all subscripts are taken modulo \(n\), we obtain \[\widehat{\tau(\boldsymbol{x})}_k= \sum_{j=0}^{n-1} \tau(\boldsymbol{x})_j \omega^{jk}= \sum_{j=0}^{n-1} x_{j-1} \omega^{jk} = \sum_{i=0}^{n-1} x_i \omega^{(i+1)k}= \omega^k \cdot \sum_{i=0}^{n-1} x_i \omega^{ik}= \omega^k \cdot \widehat{\boldsymbol{x}}_k.\] ◻

Proof. We proceed by direct computation. \[(\boldsymbol{x},\boldsymbol{y})=\sum_{i=0}^{n-1}x_iy_i=\sum_{i=0}^{n-1}\left(\frac{1}{n}\sum_{k=0}^{n-1}\widehat{\boldsymbol{x}}_k\omega^{-ik}\right)\left(\frac{1}{n}\sum_{l=0}^{n-1}\widehat{\boldsymbol{y}}_l\omega^{-il}\right)=\frac{1}{n^2}\sum_{k=0}^{n-1}\sum_{l=0}^{n-1}\widehat{\boldsymbol{x}}_k\widehat{\boldsymbol{y}}_l\sum_{i=0}^{n-1}\omega^{-i(k+l)}.\] By the orthogonality relations of the \(n\)-th roots of unity, we have \[\sum_{i=0}^{n-1}\omega^{-i(k+l)}= \begin{cases} n, & k+l\equiv 0\pmod{n}, \\ 0, & \text{otherwise}. \end{cases}\] Thus, the inner sum is non-zero if and only if \(l\equiv -k\pmod{n}\). Substituting this into the expression yields \[(\boldsymbol{x},\boldsymbol{y})=\frac{1}{n}\sum_{k=0}^{n-1}\widehat{\boldsymbol{x}}_k\widehat{\boldsymbol{y}}_{-k}.\] ◻

Proof. We first prove that \(\mathbb{F}_q^n = W_1+W_2+\cdots+W_r\). For each integer \(1\le i\le r\), define the auxiliary polynomial \(g_i(x)=\prod_{j\neq i}f_j(x).\) It is immediate that \(f_i(x)g_i(x)=x^n-1\). Since all \(f_i(x)\) are pairwise coprime, we have \(\gcd\big(g_1(x),g_2(x),\dots,g_r(x)\big)=1\). Thus, there exist polynomials \(a_1(x),a_2(x),\dots,a_r(x)\in\mathbb{F}_q[x]\) satisfying \[\sum_{i=1}^r a_i(x)g_i(x)=1.\] Substituting the cyclic shift operator \(\tau\) for the indeterminate \(x\) yields the operator identity \[\sum_{i=1}^r a_i(\tau)g_i(\tau)=I,\] where \(I\) denotes the identity operator on \(\mathbb{F}_q^n\). For an arbitrary vector \(\boldsymbol{v}\in\mathbb{F}_q^n\), we have \[\boldsymbol{v}=I(\boldsymbol{v})=\sum_{i=1}^r a_i(\tau)g_i(\tau)(\boldsymbol{v}).\] Set \(\boldsymbol{v}_i=a_i(\tau)g_i(\tau)(\boldsymbol{v})\). A direct calculation gives \[f_i(\tau)(\boldsymbol{v}_i) = f_i(\tau)a_i(\tau)g_i(\tau)(\boldsymbol{v}) = a_i(\tau)\cdot\big(f_i(\tau)g_i(\tau)\big)(\boldsymbol{v}) = a_i(\tau)\cdot(\tau^n-I)(\boldsymbol{v}) = a_i(\tau)(\boldsymbol{0}) = \boldsymbol{0}.\] Hence \(\boldsymbol{v}_i\in W_i\), which implies every vector \(\boldsymbol{v}\) can be written as a sum of elements from \(W_1,W_2,\dots,W_r\), i.e., \(\mathbb{F}_q^n=W_1+W_2+\cdots+W_r\).

We now verify this sum is direct, namely \[W_i\cap\left(\sum_{j\neq i}W_j\right)=\{\boldsymbol{0}\},\quad \forall\,1\le i\le r.\] Take any \(\boldsymbol{v}\in W_i\cap\left(\sum_{j\neq i}W_j\right)\). Since \(\boldsymbol{v}\in W_i\), we have \(f_i(\tau)(\boldsymbol{v})=\boldsymbol{0}\). Meanwhile, \(\boldsymbol{v}\in\sum_{j\neq i}W_j\) ensures there exist \(\boldsymbol{v}_j\in W_j\) (\(j\neq i\)) such that \(\boldsymbol{v}=\sum_{j\neq i}\boldsymbol{v}_j\), with \(f_j(\tau)(\boldsymbol{v}_j)=\boldsymbol{0}\) for all \(j\neq i\). Recall \(g_i(x)=\prod_{j\neq i}f_j(x)\); then \[g_i(\tau)(\boldsymbol{v})=g_i(\tau)\left(\sum_{j\neq i}\boldsymbol{v}_j\right)=\sum_{j\neq i}g_i(\tau)(\boldsymbol{v}_j)=\boldsymbol{0}.\] As \(\gcd\big(f_i(x),g_i(x)\big)=1\), there exist polynomials \(a(x),b(x)\in\mathbb{F}_q[x]\) such that \[a(x)f_i(x)+b(x)g_i(x)=1.\] Applying the same operator substitution: \[\boldsymbol{v} = I(\boldsymbol{v}) = a(\tau)f_i(\tau)(\boldsymbol{v}) + b(\tau)g_i(\tau)(\boldsymbol{v}) = a(\tau)(\boldsymbol{0}) + b(\tau)(\boldsymbol{0}) = \boldsymbol{0}.\] Therefore \(W_i\cap\big(\sum_{j\neq i}W_j\big)=\{\boldsymbol{0}\}\) holds for all indices \(i\), so the decomposition is a direct sum. ◻

Proof. This follows from the equality below: \[(\widehat{\boldsymbol{x}}_k)^q=\left(\sum_{j=0}^{n-1}x_j\omega^{jk}\right)^q=\sum_{j=0}^{n-1}x_j^q\omega^{qjk}=\sum_{j=0}^{n-1}x_j\omega^{qjk}=\widehat{\boldsymbol{x}}_{qk}.\] ◻

Proof. Since \(\boldsymbol{x}\in W_i\), we have \(f_i(\tau)(\boldsymbol{x})=\boldsymbol{0}\). Given \(\widehat{\tau^i(\boldsymbol{x})}_k=\omega^{ik}\widehat{\boldsymbol{x}}_k\), it yields \[\widehat{f_i(\tau)(\boldsymbol{x})}_k=f_i(\omega^k)\cdot\widehat{\boldsymbol{x}}_k=0.\] Hence, \(\widehat{\boldsymbol{x}}_k\) can be non-zero only if \(f_i(\omega^k)=0\). Consequently, \(\operatorname{supp}(\widehat{\boldsymbol{x}})\subset C(i)\). Since \(\boldsymbol{x}\neq \boldsymbol{0}\), we have \(\operatorname{supp}(\widehat{\boldsymbol{x}})\neq\emptyset\). Combining Lemma 9, we have \(\operatorname{supp}(\widehat{\boldsymbol{x}})=C(i)\).

Suppose \(\boldsymbol{x}\in W_{i_1}\oplus\cdots\oplus W_{i_s}\), then \(\boldsymbol{x}=\boldsymbol{\alpha}_1+\cdots+\boldsymbol{\alpha}_s\), where each \(\boldsymbol{\alpha}_t\neq\boldsymbol{0}\) and \(\boldsymbol{\alpha}_t\in W_{i_t},1\leq t\leq s\). We have \(\widehat{\boldsymbol{x}}=\widehat{\boldsymbol{\alpha}}_1+\cdots+\widehat{\boldsymbol{\alpha}}_s\), and \(\operatorname{supp}(\widehat{\boldsymbol{\alpha}}_t)\cap\operatorname{supp}(\widehat{\boldsymbol{\alpha}}_k)=\emptyset\) for \(t\neq k\). Hence \[\operatorname{supp}(\widehat{\boldsymbol{x}})=\bigcup_{t=1}^s\operatorname{supp}(\widehat{\boldsymbol{\alpha}}_t)\subset \bigcup_{t=1}^s C(i_t).\] Combining Lemma 9, we have \(\operatorname{supp}(\widehat{\boldsymbol{x}})=\bigcup_{t=1}^s C(i_t)\), \(1\leq i_1,...,i_s\leq r\). ◻

Proof. Since \(\widehat{\tau^i(\boldsymbol{u})}_k=\omega^{ik}\widehat{\boldsymbol{u}}_k\) and \(\omega^{ik}\neq 0\), we get \(\widehat{\tau^i(\boldsymbol{u})}_k\neq 0 \iff \widehat{\boldsymbol{u}}_k\neq 0\). Thus \(\operatorname{supp}(\widehat{\tau^i(U)})=\operatorname{supp}(\widehat{U})\). ◻

Proof. For any \(\boldsymbol{\alpha}\in W\setminus\{\boldsymbol{0}\}\), let \(m_{\boldsymbol{\alpha}}(x)\in\mathbb{F}_q[x]\) denote the minimal polynomial of \(\boldsymbol{\alpha}\) satisfying \(m_{\boldsymbol{\alpha}} (\tau)(\boldsymbol{\alpha})=\boldsymbol{0}\). Since \(f(\tau)(\boldsymbol{\alpha})=\boldsymbol{0}\), write the polynomial division \(f(x)=q(x)m_{\boldsymbol{\alpha}}(x)+r(x)\) with \(\deg r(x)<\deg m_{\boldsymbol{\alpha}}(x)\). Substitute the operator \(\tau\) and act on \(\alpha\): \[\boldsymbol{0}=f(\tau)(\boldsymbol{\alpha})=q(\tau)m_{\boldsymbol{\alpha}}(\tau)(\boldsymbol{\alpha})+r(\tau)(\boldsymbol{\alpha})=r(\tau)(\boldsymbol{\alpha}).\] By minimality of \(m_{\boldsymbol{\alpha}}(x)\), we deduce \(r(x)=0\), hence \(m_{\boldsymbol{\alpha}}(x)\mid f(x)\). As \(f(x)\) is irreducible, \(m_{\boldsymbol{\alpha}}(x)=f(x)\).

Suppose there exist \(a_0,a_1,\dots,a_{d-1}\in\mathbb{F}_q\) such that \[a_0\boldsymbol{\alpha}+a_1\tau(\boldsymbol{\alpha})+\cdots+a_{d-1}\tau^{d-1}(\boldsymbol{\alpha})=\boldsymbol{0}.\] Define \(g(x)=a_0+a_1x+\cdots+a_{d-1}x^{d-1}\), so \(\deg g(x)\le d-1\) and \(g(\tau)(\boldsymbol{\alpha})=\boldsymbol{0}\). From \(m_{\boldsymbol{\alpha}}(x)=f(x)\) with \(\deg f(x)=d\), we get \(g(x)=0\), which yields linear independence of \(\{\boldsymbol{\alpha},\tau(\boldsymbol{\alpha}),\dots,\tau^{d-1}(\boldsymbol{\alpha})\}\). Since \(\dim W=d\), this set forms a basis of \(W\). The above argument holds for all nonzero \(\boldsymbol{\alpha}\in W\).

Now take arbitrary \(\boldsymbol{\beta}\in W\), then \[\boldsymbol{\beta}=k_0\boldsymbol{\alpha}+k_1\tau(\boldsymbol{\alpha})+\dots+k_{d-1}\tau^{d-1}(\boldsymbol{\alpha})=g(\tau)(\boldsymbol{\alpha}),\] where \(g(x)=k_0+k_1x+\dots+k_{d-1}x^{d-1}\in\mathbb{F}_q[x]\). We have \(\widehat{\boldsymbol{\beta}}_k=\widehat{g(\tau)(\boldsymbol{\alpha})}_k=g(\omega^k)\widehat{\boldsymbol{\alpha}}_k\), hence \(\operatorname{supp}(\widehat{\boldsymbol{\beta}})\subseteq\operatorname{supp}(\widehat{\boldsymbol{\alpha}})\). If \(\boldsymbol{\beta}\neq\boldsymbol{0}\), then \(\{\boldsymbol{\beta},\tau(\boldsymbol{\beta}),\dots,\tau^{d-1}(\boldsymbol{\beta})\}\) is also a basis for \(W\). Repeating the above reasoning gives \(\operatorname{supp}(\widehat{\boldsymbol{\alpha}})\subseteq\operatorname{supp}(\widehat{\boldsymbol{\beta}})\). Consequently, \(\operatorname{supp}(\widehat{\boldsymbol{\alpha}})=\operatorname{supp}(\widehat{\boldsymbol{\beta}})\) for all nonzero \(\boldsymbol{\alpha},\boldsymbol{\beta}\in W\setminus\{\boldsymbol{0}\}\). It is now immediate that \(\operatorname{supp}(\widehat{W})=\operatorname{supp}(\widehat{\boldsymbol{\alpha}})\). ◻

Proof. To prove that \(V_{\boldsymbol{\alpha}}\) is not a cyclically covering subspace of \(\mathbb{F}_q^n\), it suffices to show that there exists an element \(\boldsymbol{x}\in\mathbb{F}_q^n\) such that \(\bigl(\boldsymbol{x},\tau^i(\boldsymbol{\alpha})\bigr)\neq 0\) for all \(0\le i\le n-1\). We have \[\bigl(\boldsymbol{x},\tau^i(\boldsymbol{\alpha})\bigr) =\frac{1}{n}\sum_{k=0}^{n-1}\widehat{\boldsymbol{x}}_k \,\widehat{\tau^i(\boldsymbol{\alpha})}_{-k} =\frac{1}{n}\sum_{k=0}^{n-1}\widehat{\boldsymbol{x}}_k \widehat{\boldsymbol{\alpha}}_{-k}\omega^{-ik}.\] Since \(-j \in \operatorname{supp}(\widehat{\boldsymbol{\alpha}})\), we have \(\widehat{\boldsymbol{\alpha}}_{-j} \neq 0\). By Lemma 5, we have \((\widehat{\boldsymbol{\alpha}}_{-j})^q = \widehat{\boldsymbol{\alpha}}_{q(-j)}= \widehat{\boldsymbol{\alpha}}_{-qj}.\) Since \(C_j = \{j\}\) is a singleton cyclotomic coset, we have \(qj \equiv j \pmod{n}\). This immediately yields \(q(-j) \equiv -j \pmod{n}\). Consequently, \[(\widehat{\boldsymbol{\alpha}}_{-j})^q = \widehat{\boldsymbol{\alpha}}_{-qj} = \widehat{\boldsymbol{\alpha}}_{-j},\] which implies \(\widehat{\boldsymbol{\alpha}}_{-j} \in \mathbb{F}_q\). Set \(\widehat{\boldsymbol{x}}_j = (\widehat{\boldsymbol{\alpha}}_{-j})^{-1}\) and \(\widehat{\boldsymbol{x}}_k = 0\) for all \(k\neq j\). As \(C_j=\{j\}\), we get \(qj\equiv j\pmod{n}\), which implies \(\widehat{\boldsymbol{x}}_{qj}=\widehat{\boldsymbol{x}}_j\). Thus \((\widehat{\boldsymbol{x}}_k)^q = \widehat{\boldsymbol{x}}_{qk}\) holds for all \(k\in [n]\). It follows that \(\widehat{\boldsymbol{x}}\) uniquely corresponds to some \(\boldsymbol{x}\in\mathbb{F}_q^n\), namely \(\boldsymbol{x} = \operatorname{IDFT}(\widehat{\boldsymbol{x}})\in\mathbb{F}_q^n\). Substituting yields \[\bigl(\boldsymbol{x},\tau^i(\boldsymbol{\alpha})\bigr) =\frac{1}{n}\sum_{k=0}^{n-1}\widehat{\boldsymbol{x}}_k \widehat{\boldsymbol{\alpha}}_{-k}\omega^{-ik} =\frac{1}{n}\widehat{\boldsymbol{x}}_j\widehat{\boldsymbol{\alpha}}_{-j} \omega^{-ij} =\frac{1}{n}\omega^{-ij}\neq 0.\] Therefore, \(V_{\boldsymbol{\alpha}}\) is not a cyclically covering subspace of \(\mathbb{F}_q^n\). ◻

Proof. For any positive integer \(n\) and prime power \(q\), \(C_0 = \{0\}\) is a singleton cyclotomic coset. The desired result follows from Lemma 13. ◻

Proof. If \(V_{\boldsymbol{\alpha}}\) is not a cyclically covering subspace of \(\mathbb{F}_q^n\), then there exists some \(\boldsymbol{x} \in \mathbb{F}_q^n\) such that \(\left(\boldsymbol{x}, \tau^i(\boldsymbol{\alpha})\right) \neq 0\) for all \(0 \le i \le n-1\). Define \(\widehat{\boldsymbol{c}}_k = \widehat{\boldsymbol{x}}_k \widehat{\boldsymbol{\alpha}}_{-k}\in\mathbb{F}_{q^m}\). Since \(\boldsymbol{x}, \boldsymbol{\alpha} \in \mathbb{F}_q^n\), we have \((\widehat{\boldsymbol{c}}_k)^q = \widehat{\boldsymbol{c}}_{qk}\) for all \(k\in[n]\), so \(\widehat{\boldsymbol{c}} \in \operatorname{DFT}(\mathbb{F}_q^n)\) and \(\operatorname{supp}(\boldsymbol{c}) \subseteq -\operatorname{supp}(\widehat{\boldsymbol{\alpha}})\). For all \(0\le i\le n-1\), we have \[0\neq \bigl(\boldsymbol{x},\tau^i(\boldsymbol{\alpha})\bigr) =\frac{1}{n}\sum_{k=0}^{n-1}\widehat{\boldsymbol{x}}_k \,\widehat{\tau^i(\boldsymbol{\alpha})}_{-k} =\frac{1}{n}\sum_{k=0}^{n-1}\widehat{\boldsymbol{x}}_k \hat{\boldsymbol{\alpha}}_{-k}\omega^{-ik}= \frac{1}{n} \sum_{k=0}^{n-1} \widehat{\boldsymbol{c}}_k \omega^{-ik}=\operatorname{IDFT}(\widehat{\boldsymbol{c}})_i.\] This yields that there exists \(\widehat{\boldsymbol{c}}\in\operatorname{DFT}(\mathbb{F}_q^n)\) satisfying \(\operatorname{supp}(\widehat{\boldsymbol{c}}) \subseteq -\operatorname{supp}(\widehat{\boldsymbol{\alpha}})\) such that \[\operatorname{wt}(\boldsymbol{c})=\operatorname{wt}(\operatorname{IDFT}(\widehat{\boldsymbol{c}}))=n,\] where \(\boldsymbol{c}=\operatorname{IDFT}(\widehat{\boldsymbol{c}})\) and \(\operatorname{wt}(\boldsymbol{c})=|\operatorname{supp}(\boldsymbol{c})|\).

If there exists \(\widehat{\boldsymbol{c}}\in\operatorname{DFT}(\mathbb{F}_q^n)\) with \(\operatorname{supp}(\widehat{\boldsymbol{c}}) \subseteq -\operatorname{supp}(\widehat{\boldsymbol{\alpha}})\) such that \(\operatorname{wt}(\operatorname{IDFT}(\widehat{\boldsymbol{c}}))=n\), we construct \(\widehat{\boldsymbol{x}}\) as follows: set \[\widehat{\boldsymbol{x}}_k= \begin{cases} \widehat{\boldsymbol{c}}_k (\widehat{\boldsymbol{\alpha}}_{-k})^{-1}, & -k\in\operatorname{supp}(\widehat{\boldsymbol{\alpha}}),\\ 0, & -k\notin\operatorname{supp}(\widehat{\boldsymbol{\alpha}}). \end{cases}\] Then \(\widehat{\boldsymbol{c}}_k = \widehat{\boldsymbol{x}}_k \widehat{\boldsymbol{\alpha}}_{-k}\) holds for every \(k\in[n]\). It is easy to verify that \((\widehat{\boldsymbol{x}}_k)^q=\widehat{\boldsymbol{x}}_{qk}\) for all \(k\in[n]\), which implies \(\widehat{\boldsymbol{x}}\in\operatorname{DFT}(\mathbb{F}_q^n)\). By the Inverse Discrete Fourier Transform, there exists a unique \(\boldsymbol{x}\in\mathbb{F}_q^n\) such that \(\operatorname{DFT}(\boldsymbol{x})=\widehat{\boldsymbol{x}}\). For all \(0\le i\le n-1\), we have \[\bigl(\boldsymbol{x},\tau^i(\boldsymbol{\alpha})\bigr) =\frac{1}{n}\sum_{k=0}^{n-1}\widehat{\boldsymbol{x}}_k \,\widehat{\tau^i(\boldsymbol{\alpha})}_{-k} =\frac{1}{n}\sum_{k=0}^{n-1}\widehat{\boldsymbol{x}}_k \widehat{\boldsymbol{\alpha}}_{-k}\omega^{-ik}=\frac{1}{n}\sum_{k=0}^{n-1}\widehat{\boldsymbol{c}}_k\omega^{-ik}=\operatorname{IDFT}(\widehat{\boldsymbol{c}})_i\neq0.\] Therefore, there exists \(\boldsymbol{x}\in\mathbb{F}_q^n\) satisfying \(\bigl(\boldsymbol{x},\tau^i(\boldsymbol{\alpha})\bigr)\neq 0\) for every \(0\le i\le n-1\), which implies that \(V_{\boldsymbol{\alpha}}\) is not a cyclically covering subspace of \(\mathbb{F}_q^n\). ◻

Proof. Let \(\widehat{\boldsymbol{c}}\in\operatorname{DFT}(\mathbb{F}_q^n)\) satisfy \(\operatorname{supp}(\widehat{\boldsymbol{c}}) \subseteq -\operatorname{supp}(\widehat{\boldsymbol{\alpha}})\). Define the polynomial \(P(t) = \sum\limits_{k=0}^{n-1} \widehat{\boldsymbol{c}}_k t^k\). As \(0\notin\operatorname{supp}(\widehat{\boldsymbol{\alpha}})\), it follows that \(\widehat{\boldsymbol{c}}_0 = 0\). With the identity \((\widehat{\boldsymbol{c}}_k)^q = \widehat{\boldsymbol{c}}_{qk}\), \(P(t)\) can be rewritten as \[\begin{align} P(t) &= \widehat{\boldsymbol{c}}_1 t + \widehat{\boldsymbol{c}}_2 t^2 + \cdots + \widehat{\boldsymbol{c}}_{n-1} t^{n-1} \\ &=\sum_{j\in\mathcal{R}} \left( \widehat{\boldsymbol{c}}_j t^j + \widehat{\boldsymbol{c}}_{jq} t^{jq} + \widehat{\boldsymbol{c}}_{jq^2} t^{jq^2} + \cdots + \widehat{\boldsymbol{c}}_{jq^{m_j-1}} t^{jq^{m_j-1}} \right)\\ &=\sum_{j\in\mathcal{R}} \left( \widehat{\boldsymbol{c}}_j t^j + (\widehat{\boldsymbol{c}}_j t^j)^q + (\widehat{\boldsymbol{c}}_j t^j)^{q^2} + \cdots + (\widehat{\boldsymbol{c}}_j t^j)^{q^{m_j-1}} \right)\\ &=\sum_{j\in\mathcal{R}}\operatorname{Tr}_{\mathbb{F}_q}^{\mathbb{F}_{q^{m_j}}}(\widehat{\boldsymbol{c}}_jt^j)=P_{\widehat{\boldsymbol{c}}}(t), \end{align}\] where the sum \(\displaystyle\sum_{j\in\mathcal{R}}\) runs over all minimal representatives in \(\bigcup_{t=1}^s C(i_t)\). By Lemma 14, \(\operatorname{wt}(\boldsymbol{c})=\operatorname{wt}(\operatorname{IDFT}(\widehat{\boldsymbol{c}}))=n\) is equivalent to \(P_{\widehat{\boldsymbol{c}}}(\omega^i) \neq 0\) for all \(0 \le i \le n-1\). ◻

Proof. It follows directly from Lemma 10 and Lemma 14. ◻

Proof. This follows from Corollary 1 and Lemma 15. ◻

Proof. This follows from Corollary 2 and Theorem 1. ◻

Proof. Since \(U=\bigcap_{j=1}^k V_{\boldsymbol{\alpha}_j}=\big\{\,\boldsymbol{x}\in\mathbb{F}_q^n : (\boldsymbol{x},\boldsymbol{\alpha}_1)=\cdots=(\boldsymbol{x},\boldsymbol{\alpha}_k)=0\,\big\},\) if \(U\) is a cyclically covering subspace of \(\mathbb{F}_{q}^n\), then for any \(\boldsymbol{x}\in\mathbb{F}_q^n\), there exists \(i\in [n]\) such that \(\big(\boldsymbol{x},\tau^i(\boldsymbol{\alpha}_1)\big)=\cdots=\big(\boldsymbol{x},\tau^i(\boldsymbol{\alpha}_k)\big)=0.\) The proof of Theorem 2 follows from the Discrete Fourier Transform and Theorem 1. ◻

Proof. Case 1: Let \(q\) be an odd prime and \(n > q\) a prime. Suppose that \(q\) is a primitive root modulo \(n\). To prove \(h_q(n) = 0\), it suffices to show that no \((n-1)\)-dimensional subspace \(V_{\boldsymbol{\alpha}}\) is a cyclically covering subspace of \(\mathbb{F}_q^n\). Since \(q\) is a primitive root modulo \(n\), we have \(\gcd(q,n) = 1\) and \(\operatorname{ord}_n(q) = n-1\). Over \(\mathbb{F}_q[x]\), the polynomial \(x^n - 1\) factors as \[x^n - 1 = (x-1)\big(1+x+\cdots+x^{n-1}\big),\] which yields exactly two cyclotomic cosets: \(C_0 = \{0\}\) and \(C_1 = \{1,2,\dots,n-1\}\). By Corollary 1, \(V_{\boldsymbol{\alpha}}\) cannot be a cyclically covering if \(0 \in \operatorname{supp}(\widehat{\boldsymbol{\alpha}})\). We therefore focus on the case where \(0 \notin \operatorname{supp}(\widehat{\boldsymbol{\alpha}})\). In this setting, \(\operatorname{supp}(\widehat{\boldsymbol{\alpha}}) = C_1\), and \(-\operatorname{supp}(\widehat{\boldsymbol{\alpha}}) = -C_1 = C_1\).

According to Lemma 15, to prove that \(V_{\boldsymbol{\alpha}}\) is not a cyclically covering subspace of \(\mathbb{F}_q^n\), we only need to construct a vector \(\widehat{\boldsymbol{c}} \in \operatorname{DFT}(\mathbb{F}_q^n)\) satisfying the two conditions below: \(\operatorname{supp}(\widehat{\boldsymbol{c}}) \subseteq C_1~(\text{i.e.,}~ \widehat{\boldsymbol{c}}_0 = 0),\) and \(P_{\widehat{\boldsymbol{c}}}(\omega^i) \neq 0~\text{for all } 0 \leq i \leq n-1,\) where \(P_{\widehat{\boldsymbol{c}}}(t)=\operatorname{Tr}_{\mathbb{F}_q}^{\mathbb{F}_{q^{n-1}}}(\widehat{\boldsymbol{c}}_1 t)\) and \(\widehat{\boldsymbol{c}}_1\in\mathbb{F}_{q^{n-1}}\).

We consider two cases for the construction of \(\widehat{\boldsymbol{c}}_1\).

(i) When \(q\nmid n-1\), we take \(\widehat{\boldsymbol{c}}_1 = 1\), so that \(P_{\widehat{\boldsymbol{c}}}(t) = \operatorname{Tr}_{\mathbb{F}_q}^{\mathbb{F}_{q^{n-1}}}(t)\). For \(i = 0\), we have \(P_{\widehat{\boldsymbol{c}}}(\omega^0) = \operatorname{Tr}_{\mathbb{F}_q}^{\mathbb{F}_{q^{n-1}}}(1) = n-1\). Since \(q \nmid n-1\), it follows that \(n-1 \not\equiv 0 \pmod{q}\), and thus \(\operatorname{Tr}_{\mathbb{F}_q}^{\mathbb{F}_{q^{n-1}}}(1) \neq 0\). For \(1 \leq i \leq n-1\), \(\omega^i\) is also a primitive \(n\)-th root of unity, and since \(q\) is a primitive root modulo \(n\), we compute \[\operatorname{Tr}_{\mathbb{F}_q}^{\mathbb{F}_{q^{n-1}}}(\omega^i) = \sum_{k=0}^{n-2} \omega^{i q^k} = \sum_{j=1}^{n-1} \omega^{i j} = \left( \sum_{j=0}^{n-1} \omega^{i j} \right) - 1 = 0 - 1 = -1.\] As \(q\) is an odd prime, \(-1 \not\equiv 0 \pmod{q}\), so \(\operatorname{Tr}_{\mathbb{F}_q}^{\mathbb{F}_{q^{n-1}}}(\omega^i) \neq 0\). Therefore, \(P_{\widehat{\boldsymbol{c}}}(\omega^i) \neq 0\) for all \(i\).

(ii) When \(q \mid n-1\), we have \(\operatorname{Tr}_{\mathbb{F}_q}^{\mathbb{F}_{q^{n-1}}}(1) = n-1 \equiv 0 \pmod{q}\). In this case, we take \(\widehat{\boldsymbol{c}}_1 = 1 + \omega\), so that \(P_{\widehat{\boldsymbol{c}}}(t) = \operatorname{Tr}_{\mathbb{F}_q}^{\mathbb{F}_{q^{n-1}}}((1+\omega)t)\). For \(i = 0\), we get \[P_{\widehat{\boldsymbol{c}}}(\omega^0) = \operatorname{Tr}_{\mathbb{F}_q}^{\mathbb{F}_{q^{n-1}}}(1+\omega) = \operatorname{Tr}_{\mathbb{F}_q}^{\mathbb{F}_{q^{n-1}}}(1) + \operatorname{Tr}_{\mathbb{F}_q}^{\mathbb{F}_{q^{n-1}}}(\omega) = 0 + (-1) = -1 \neq 0.\] For \(i = n-1\), we have \[P_{\widehat{\boldsymbol{c}}}(\omega^{n-1}) = \operatorname{Tr}_{\mathbb{F}_q}^{\mathbb{F}_{q^{n-1}}}((1+\omega)\omega^{n-1}) = \operatorname{Tr}_{\mathbb{F}_q}^{\mathbb{F}_{q^{n-1}}}(\omega^{n-1}) + \operatorname{Tr}_{\mathbb{F}_q}^{\mathbb{F}_{q^{n-1}}}(\omega^n) = -1 + 0 = -1 \neq 0.\] For \(1 \leq i \leq n-2\), we obtain \[P_{\widehat{\boldsymbol{c}}}(\omega^i) = \operatorname{Tr}_{\mathbb{F}_q}^{\mathbb{F}_{q^{n-1}}}(\omega^i) + \operatorname{Tr}_{\mathbb{F}_q}^{\mathbb{F}_{q^{n-1}}}(\omega^{i+1}) = -1 + (-1) = -2.\] Since \(q\) is an odd prime, \(-2 \not\equiv 0 \pmod{q}\). Thus, \(P_{\widehat{\boldsymbol{c}}}(\omega^i) \neq 0\) for all \(i\).

By Lemma 15, we conclude that \(V_{\boldsymbol{\alpha}}\) is not a cyclically covering subspace of \(\mathbb{F}_q^n\).

Case 2: Suppose \(n>3\) is prime and \(2\) is a primitive root modulo \(n\). We prove \(h_2(n)\geq2\) in two steps.

Step 1: We start with the proof that \(h_2(n) \ge 1\). Choose \(\boldsymbol{\alpha}\) such that \(\operatorname{supp}(\widehat{\boldsymbol{\alpha}}) = C_1\). For instance, we may take \(\boldsymbol{0}\neq\boldsymbol{\alpha} \in \ker\big(1+\tau+\cdots+\tau^{n-1}\big)\). Then \(0 \notin \operatorname{supp}(\widehat{\boldsymbol{\alpha}})\) and \(-\operatorname{supp}(\widehat{\boldsymbol{\alpha}}) = C_1\). We aim to prove that for any vector \(\widehat{\boldsymbol{c}} \in \operatorname{DFT}(\mathbb{F}_2^n)\) satisfying \(\operatorname{supp}(\widehat{\boldsymbol{c}}) \subseteq -\operatorname{supp}(\widehat{\boldsymbol{\alpha}})\), there exists an index \(i \in [n]\) such that \(P_{\widehat{\boldsymbol{c}}}(\omega^i) = 0\), where \(P_{\widehat{\boldsymbol{c}}}(t)=\operatorname{Tr}_{\mathbb{F}_2}^{\mathbb{F}_{2^{n-1}}}(\widehat{\boldsymbol{c}}_1 t)\) and \(\widehat{\boldsymbol{c}}_1\in\mathbb{F}_{2^{n-1}}\). We compute the sum \[\sum_{i=0}^{n-1} P_{\widehat{\boldsymbol{c}}}(\omega^i)= \sum_{i=0}^{n-1} \operatorname{Tr}_{\mathbb{F}_2}^{\mathbb{F}_{2^{n-1}}}(\widehat{\boldsymbol{c}}_1 \omega^i) = \operatorname{Tr}_{\mathbb{F}_2}^{\mathbb{F}_{2^{n-1}}}\left(\widehat{\boldsymbol{c}}_1 \sum_{i=0}^{n-1} \omega^i\right)= \operatorname{Tr}_{\mathbb{F}_2}^{\mathbb{F}_{2^{n-1}}}(\widehat{\boldsymbol{c}}_1 \cdot 0) = 0.\] Thus, the number of indices \(i\) for which \(P_{\widehat{\boldsymbol{c}}}(\omega^i) = 1\) is even. Since \(n\) is odd, these values cannot all equal \(1\). It follows that there exists at least one \(i\) such that \(P_{\widehat{\boldsymbol{c}}}(\omega^i) = 0\). Thus, \(V_{\boldsymbol{\alpha}}\) is a cyclically covering subspace, so \(h_2(n) \ge 1\).

Step 2: We now show that \(h_2(n) \ge 2\). We proceed by explicit construction. Let \(U = V_{\boldsymbol{\alpha}} \cap V_{\boldsymbol{\beta}}\), where \(\boldsymbol{\alpha}, \boldsymbol{\beta} \in \mathbb{F}_2^n\) are linearly independent over \(\mathbb{F}_2\), and \(0 \notin \operatorname{supp}(\widehat{\boldsymbol{\alpha}})\), \(0 \notin \operatorname{supp}(\widehat{\boldsymbol{\beta}})\). Since there is exactly one non-zero cyclotomic coset, it follows that \(\operatorname{supp}(\widehat{\boldsymbol{\alpha}}) = \operatorname{supp}(\widehat{\boldsymbol{\beta}}) = C_1\).

Choose any \(\widehat{\boldsymbol{\alpha}}\) such that \(\widehat{\boldsymbol{\alpha}}_1 \neq 0\). The remaining components are automatically determined by the DFT image condition \((\widehat{\boldsymbol{\alpha}}_{2^k} = \widehat{\boldsymbol{\alpha}}_1^{2^k})\), ensuring that \(\boldsymbol{\alpha} \in \mathbb{F}_2^n\). Let \(t = \frac{n-1}{2}\). Choose any \(\lambda \in \mathbb{F}_{2^t} \setminus \{0,1\},\) which exists because \(n>3\) implies \(t \ge 2\). Define \(\widehat{\boldsymbol{\beta}}\) with support \(C_1\) by setting \(\widehat{\boldsymbol{\beta}}_1 = \lambda \widehat{\boldsymbol{\alpha}}_1,\) so that \(\widehat{\boldsymbol{\beta}}_{-1} = \lambda \widehat{\boldsymbol{\alpha}}_{-1}\). Indeed, since \(-1 \equiv 2^t \pmod{n}\), we have \[\widehat{\boldsymbol{\beta}}_{-1} = \widehat{\boldsymbol{\beta}}_{2^t} = (\widehat{\boldsymbol{\beta}}_1)^{2^t} = \left(\lambda \widehat{\boldsymbol{\alpha}}_1\right)^{2^t} = \lambda^{2^t} (\widehat{\boldsymbol{\alpha}}_1)^{2^t} = \lambda \widehat{\boldsymbol{\alpha}}_{-1}.\] Then \(\boldsymbol{\beta}\in\mathbb{F}_2^n\), and \(\boldsymbol{\beta}\) is linearly independent of \(\boldsymbol{\alpha}\) over \(\mathbb{F}_2\) owing to \(\lambda\neq1\).

Suppose \(U= V_{\boldsymbol{\alpha}} \cap V_{\boldsymbol{\beta}}\) is not a cyclically covering subspace. Then there exists some \(\boldsymbol{x} \in \mathbb{F}_2^n\) such that \(\boldsymbol{x} \notin \tau^i(U)\) for every \(i \in [n]\). This implies that \(( \boldsymbol{x}, \tau^i(\boldsymbol{\alpha}) ) \neq 0\) or \(( \boldsymbol{x}, \tau^i(\boldsymbol{\beta}) ) \neq 0,\) for every \(i \in [n]\). In other words, there is no index \(i\) for which both inner products vanish simultaneously. Since \(\operatorname{supp}(\widehat{\boldsymbol{\alpha}}) = \operatorname{supp}(\widehat{\boldsymbol{\beta}}) = C_1\), we have \[( \boldsymbol{x}, \tau^i(\boldsymbol{\alpha}) ) = \operatorname{Tr}_{\mathbb{F}_2}^{\mathbb{F}_{2^{n-1}}}(a \omega^{-i}), ~~ ( \boldsymbol{x}, \tau^i(\boldsymbol{\beta}) ) = \operatorname{Tr}_{\mathbb{F}_2}^{\mathbb{F}_{2^{n-1}}}(b \omega^{-i}),\] where \(a = \widehat{\boldsymbol{x}}_1 \widehat{\boldsymbol{\alpha}}_{-1}\in\mathbb{F}_{2^{n-1}}\) and \(b = \widehat{\boldsymbol{x}}_1 \widehat{\boldsymbol{\beta}}_{-1}=\lambda a\in\mathbb{F}_{2^{n-1}}\). As \(i\) runs over all indices, we may identify \(\omega^{-i}\) with \(\omega^i\), so the condition reduces to: for every \(i\), \(\left(\operatorname{Tr}_{\mathbb{F}_2}^{\mathbb{F}_{2^{n-1}}}(a \omega^i), \operatorname{Tr}_{\mathbb{F}_2}^{\mathbb{F}_{2^{n-1}}}(\lambda a \omega^i)\right) \neq (0, 0).\) We first define \(x_i = \operatorname{Tr}_{\mathbb{F}_2}^{\mathbb{F}_{2^{n-1}}}(a \omega^i)\) and \(y_i = \operatorname{Tr}_{\mathbb{F}_2}^{\mathbb{F}_{2^{n-1}}}(\lambda a \omega^i)\), both taking values in \(\{0,1\}\). It is straightforward to verify that \[\sum_{i=0}^{n-1} x_i = \sum_{i=0}^{n-1} \operatorname{Tr}_{\mathbb{F}_2}^{\mathbb{F}_{2^{n-1}}}(a \omega^i) = 0,\] and similarly \(\sum_{i=0}^{n-1} y_i = 0\). Furthermore, we compute \[\begin{align} \sum_{i=0}^{n-1} x_i y_i &= \sum_{i=0}^{n-1} \operatorname{Tr}_{\mathbb{F}_2}^{\mathbb{F}_{2^{n-1}}}(a\omega^i)\operatorname{Tr}(\lambda a\omega^i)\\ &= \sum_{i=0}^{n-1} \left( \sum_{k=0}^{n-2} (a\omega^i)^{2^k} \right) \left( \sum_{l=0}^{n-2} (\lambda a\omega^i)^{2^l} \right)\\ &= \sum_{k=0}^{n-2} \sum_{l=0}^{n-2} a^{2^k} (\lambda a)^{2^l} \sum_{i=0}^{n-1} \omega^{i(2^k + 2^l)}. \end{align}\] Note that \[\sum_{i=0}^{n-1} \omega^{i(2^k + 2^l)} = \begin{cases} 1, & \text{if } 2^k + 2^l \equiv 0 \pmod{n},\\ 0, & \text{otherwise}. \end{cases}\] The condition \(2^k + 2^l \equiv 0 \pmod{n}\) is equivalent to \(2^{k-l} \equiv -1 \pmod{n}\), which in turn holds if and only if \(k-l \equiv t \pmod{n-1}\), where \(t = \frac{n-1}{2}\) satisfies \(2^t \equiv -1 \pmod{n}\). When \(k = l\), we have \(2^k + 2^l = 2^{k+1} \not\equiv 0 \pmod{n}\), so these terms contribute nothing. Suppose there exists a pair \((k_0, l_0)\) with \(k_0 \neq l_0\) such that \(2^{k_0} + 2^{l_0} \equiv 0 \pmod{n}\). By symmetry, the pair \((l_0, k_0)\) also satisfies the same condition, so all such pairs occur in symmetric pairs. The contribution of each such pair is \[a^{2^k} (\lambda a)^{2^l} + a^{2^l} (\lambda a)^{2^k}= a^{2^k + 2^l} \left( \lambda^{2^l} + \lambda^{2^k} \right).\] Since \(k - l \equiv t \pmod{n-1}\), we may write \(k \equiv l+t \pmod{n-1}\). Then \(\lambda^{2^k} = (\lambda^{2^t})^{2^l} = \lambda^{2^l},\) where the last equality holds because \(\lambda \in \mathbb{F}_{2^t}\) satisfies \(\lambda^{2^t} = \lambda\). Hence the bracketed term vanishes in characteristic 2, so the contribution of each pair is zero. All non-zero terms therefore cancel pairwise, and the total sum is zero. Thus, \(\sum_{i=0}^{n-1} x_i y_i = 0\) for any a.

Suppose for all \(i\), \((x_i, y_i) \neq (0,0)\). Then the only possible non-zero pairs are \((1,0)\), \((0,1)\) and \((1,1)\). Let \(n_1, n_2, n_3\) denote the number of occurrences of these three pairs respectively, so \(n_1 + n_2+ n_3 = n\). From the vanishing sums above, we obtain \[\sum x_i = n_1 + n_3 \equiv 0 \pmod{2}, \quad \sum y_i = n_2 + n_3 \equiv 0 \pmod{2}, \quad \sum x_i y_i = n_3 \equiv 0 \pmod{2}.\] It follows that \(n_3\) is even, and hence both \(n_1\) and \(n_2\) are even. This yields a contradiction, since \(n = n_1 + n_2 + n_3\) is an odd prime. Therefore, there must exist some \(i\) such that \(x_i = y_i = 0\), which implies \(\boldsymbol{x} \in \tau^i(U)\). Thus \(U\) is a cyclically covering subspace, and we conclude that \(h_2(n) \ge 2\). ◻

Proof. Let \(d=\operatorname{ord}_n(3)\). Since \(\operatorname{ord}_n(3)\) is odd, \(3\) cannot be a primitive root modulo \(n\). Take the non-zero cyclotomic coset \(C_1=\{1,3,3^2,\dots,3^{d-1}\}\). As \(\operatorname{ord}_n(3)\) is odd, we have \(C_1\neq -C_1\), which means \(C_1\cap (-C_1)=\emptyset\). Let \(C=-C_1\), and let \(W_C\) be the subspace of \(\mathbb{F}_3^n\) corresponding to the cyclotomic coset \(C\). By Lemma 16, it suffices to prove that \(W_C\) contains no full-weight codewords. Suppose, for contradiction, that there exists a full-weight codeword \(\boldsymbol{x}\in W_C\), i.e., \(x_i\in\mathbb{F}_3^\times=\{1,-1\}\) for all \(i\in[n]\). For the standard inner product, we have \[(\boldsymbol{x},\boldsymbol{x}) = \sum_{i=0}^{n-1} x_i^2 = \sum_{i=0}^{n-1} 1 = n \neq 0.\] By Lemma 10, \(\boldsymbol{x}\in W_C\) implies \(\operatorname{supp}(\widehat{\boldsymbol{x}})=C\). Combining this with Lemma 7 and the condition \(C\cap (-C)=\emptyset\), we get \[(\boldsymbol{x},\boldsymbol{x}) = \frac{1}{n}\sum_{k=0}^{n-1}\widehat{\boldsymbol{x}}_k \widehat{\boldsymbol{x}}_{-k} = 0.\] This is a contradiction. Hence, \(W_C\) has no full-weight codewords. Accordingly, by Lemma 16, we obtain \(h_3(n)\geq1\). ◻

Proof. It follows from Theorem 3.1.3 in [13] or Section 5.1 in [14] that the natural density of primes \(p\) for which \(\operatorname{ord}_p(3)\) is odd is equal to \(\frac{1}{3}\). While this immediately yields that there are infinitely many such primes, we present a short direct proof below.

Let \(\ell\) be an odd prime. We have \[3^\ell-1=(3-1)\big(1+3+3^2+\cdots+3^{\ell-1}\big).\] The sum \(1+3+3^2+\cdots+3^{\ell-1}\) is odd, so \(3^\ell-1\) has at least one odd prime divisor. Pick an odd prime divisor \(n\) of \(3^\ell-1\). Then \(3^\ell \equiv 1 \pmod{n}\), which implies \(\operatorname{ord}_n(3) \mid \ell\). Since \(\ell\) is prime, \(\operatorname{ord}_n(3)\) is either \(1\) or \(\ell\). If \(\operatorname{ord}_n(3)=1\), then \(3 \equiv 1 \pmod{n}\), i.e., \(n \mid 2\). This contradicts the fact that \(n\) is an odd prime. Hence \(\operatorname{ord}_n(3)=\ell\). Thus, for any given odd prime \(\ell\), we can construct an odd prime \(n\) such that \(\operatorname{ord}_n(3)\) is odd.

Now take two distinct odd primes \(\ell_1\) and \(\ell_2\). It holds that \[\gcd\big(3^{\ell_1}-1,\,3^{\ell_2}-1\big) = 3^{\gcd(\ell_1,\ell_2)}-1 = 3^1-1 = 2.\] This means the sets of odd prime divisors of \(3^{\ell_1}-1\) and \(3^{\ell_2}-1\) are disjoint. Since each \(3^\ell-1\) possesses at least one odd prime divisor, letting \(\ell\) run over all odd primes yields infinitely many distinct odd primes \(n\) for which \(\operatorname{ord}_n(3)\) is odd. ◻

Proof. Since \(\operatorname{ord}_n(q)=\dfrac{n-1}{2}\), there exist exactly three cyclotomic cosets \(C_0,C_1,C_2\), where \(C_0=\{0\}\), \(C_1\) is the set of all quadratic residues, and \(C_2\) is the set of all quadratic non-residues. Consequently, \(\mathbb{F}_q^n\) admits the direct sum decomposition \(W_0\oplus W_1\oplus W_2\) with \(\operatorname{supp}(\widehat{W}_i)=C_i\) for \(i=0,1,2\). By Lemma 16, to establish \(h_q(n)=0\), it suffices to verify that each of \(W_1\), \(W_2\) and \(W_1\oplus W_2\) contains at least one full-weight codeword.

We first focus on the subspace \(W_1\). Define \[\widehat{\boldsymbol{c}}_k= \begin{cases} 1, & k\in C_1,\\ 0, & k\notin C_1. \end{cases}\] It is clear that \(\widehat{\boldsymbol{c}}\in \operatorname{DFT}(\mathbb{F}_q^n)\). Let \(\boldsymbol{c}=\operatorname{IDFT}(\widehat{\boldsymbol{c}}).\) Then \[c_i=\frac{1}{n}\sum_{k\in C_1}\omega^{-ik}.\] When \(i=0\), we have \(c_0=\frac{|C_1|}{n}=\frac{d}{n}.\) Therefore, provided that \(q\nmid d,\) or equivalently, \(n\not\equiv 1\pmod{q},\) we deduce that \(c_0\neq 0.\)

For \(i \neq 0\), the set \(-iC_1\) is either \(C_1\) or \(C_2\). Let \[\eta_1 = \sum_{j\in C_1}\omega^j, \qquad \eta_2 = \sum_{j\in C_2}\omega^j.\] Hence \(c_i\) is equal to either \(\frac{\eta_1}{n}\) or \(\frac{\eta_2}{n}\). They satisfy the relation \[\eta_1 + \eta_2 = -1.\] We need to show that both \(\eta_1\) and \(\eta_2\) are nonzero, which is equivalent to \(\eta_1 \eta_2 \neq 0\).

Define the quadratic Gauss sum \[G(n) = \sum_{k=0}^{n-1} \left(\frac{k}{n}\right) \omega^k,\] where \(\left(\frac{k}{n}\right)\) denotes the Legendre symbol. It follows immediately that \[G(n) = \eta_1 - \eta_2.\] Since \(G(n)^2 = \left(\frac{-1}{n}\right) n\), we have \[(\eta_1 - \eta_2)^2 = \left(\frac{-1}{n}\right) n = (-1)^{\frac{n-1}{2}} n.\] Using the identity \(\eta_1 \eta_2 = \frac{(\eta_1 + \eta_2)^2 - (\eta_1 - \eta_2)^2}{4}\) and the fact that \(\eta_1 + \eta_2 = -1\), we obtain \[\eta_1 \eta_2 = \frac{1 - (-1)^{\frac{n-1}{2}} n}{4}.\] Thus, \[\eta_1 \eta_2 \neq 0 \quad \Longleftrightarrow \quad \frac{1 - (-1)^{\frac{n-1}{2}} n}{4} \neq 0 \quad \Longleftrightarrow \quad (-1)^{\frac{n-1}{2}} n \not\equiv 1 \pmod{q}.\] This proves that \(W_{1}\) contains a full-weight codeword whenever \(n \not\equiv 1 \pmod{q}\) and \((-1)^{\frac{n-1}{2}} n \not\equiv 1 \pmod{q}\). The same construction applies verbatim to \(W_{2}\).

On the other hand, \(\boldsymbol{c} \in W_1 \oplus W_2\) if and only if \(0 \notin \operatorname{supp}(\widehat{\boldsymbol{c}})\), i.e., vectors with coordinate sum zero modulo \(q\). Since \(q\) is an odd prime, \(2\) is invertible modulo \(q\), so the congruence \(2r \equiv n \pmod{q}\) has a unique solution \(r \in \{1, 2, \dots, q-1\}\). We construct a vector with \(r\) coordinates equal to 1 and the remaining \(n-r\) coordinates equal to \(-1\). This vector has all coordinates nonzero and sum of coordinates equal to \(r - (n - r) = 2r - n \equiv 0 \pmod{q}\), hence it is a full-weight codeword in \(W_{1} \oplus W_{2}\).

Therefore, it follows from Lemma 16 that \(h_q(n) = 0\). ◻

Proof. This is an immediate corollary of Theorem 5. ◻

Proof. Since \(q>3\), there exists a quadratic residue \(u\in\mathbb{F}_q^\ast\) such that \[u\not\equiv 1 \pmod q.\] By the Chinese remainder theorem, choose a residue class \(a \pmod{4q}\) satisfying \[a\equiv 1 \pmod 4,\qquad a\equiv u \pmod q.\] We first observe that every prime \(n\equiv a\pmod{4q}\) automatically satisfies the two congruence conditions in Theorem 5. Indeed, \[n\equiv a\equiv u\not\equiv 1\pmod q,\] so \[n\not\equiv 1\pmod q.\] Moreover, \(n\equiv a\equiv1\pmod4\) implies that the integer \(\frac{n-1}{2}\) is even, hence \[(-1)^{\frac{n-1}{2}}=1,\] and consequently \[(-1)^{\frac{n-1}{2}}n\equiv n\equiv u\not\equiv1\pmod q.\] It remains to verify the order condition \[\operatorname{ord}_n(q)=\frac{n-1}{2}.\] For a prime \(n\), this equality is equivalent to \(q\) generating the subgroup of all quadratic residues modulo \(n\), or equivalently, \(q\) being a near-primitive root of index \(2\) modulo \(n\).

The congruence class \(a\pmod{4q}\) is compatible with this order condition. Indeed, if \(n\equiv a\pmod{4q}\), then \(n\equiv1\pmod4\) and \(n\equiv u\pmod q\). By quadratic reciprocity, \[\left(\frac{q}{n}\right)=\left(\frac{n}{q}\right)=\left(\frac{u}{q}\right)=1.\] This shows that \(q\) is a quadratic residue modulo \(n\), so it is possible for \(q\) to generate the subgroup of quadratic residues modulo \(n\).

We now invoke the GRH-conditional Artin-type theorem for near-primitive roots in arithmetic progressions: for the fixed prime \(q>3\) and the congruence class \(a\pmod{4q}\) defined above, assuming the Generalized Riemann Hypothesis holds, there exist infinitely many primes \(n\equiv a\pmod{4q}\) such that \(q\) is a near-primitive root of index \(2\) modulo \(n\), i.e., \[\operatorname{ord}_n(q)=\frac{n-1}{2}.\] This result follows from Moree’s density theory for near-primitive roots [15], combined with the Artin-type density framework for arithmetic progressions established by Lenstra, Moree, and Stevenhagen [16].

Therefore there are infinitely many primes \(n > q\) for which \(q\) fails to be a primitive root modulo \(n\) and \(h_q(n) = 0\). ◻

Proof. Let \(\tau_n\) and \(\tau_m\) denote the cyclic shift operators on \(\mathbb{F}_q^n\) and \(\mathbb{F}_q^m\), respectively. As \(m\mid n\), write \(n = md\). For any \(\boldsymbol{x}=(x_0,...,x_{n-1})\in\mathbb{F}_q^n\), define the map \(\pi: \mathbb{F}_q^n\to\mathbb{F}_q^m\) by \[\pi(\boldsymbol{x})_k = \sum_{j=0}^{d-1} x_{k+jm}.\] Take arbitrary \(\boldsymbol{x},\boldsymbol{y}\in\mathbb{F}_q^n\) and \(a,b\in\mathbb{F}_q\). We have \[\pi(a\boldsymbol{x}+b\boldsymbol{y})_k = \sum_{j=0}^{d-1}\big(ax_{k+jm}+by_{k+jm}\big)= a\sum_{j=0}^{d-1}x_{k+jm} + b\sum_{j=0}^{d-1}y_{k+jm}= a\pi(\boldsymbol{x})_k + b\pi(\boldsymbol{y})_k.\] This implies \(\pi(a\boldsymbol{x}+b\boldsymbol{y})=a\pi(\boldsymbol{x})+b\pi(\boldsymbol{y})\), so \(\pi\) is a linear map. For any \(\boldsymbol{y}=(y_0,y_1,\dots,y_{m-1})\in\mathbb{F}_q^m\), construct \(\boldsymbol{x}\in\mathbb{F}_q^n\) as follows: \[x_i= \begin{cases} y_k, & i=k,\;0\le k\le m-1,\\ 0, & \text{otherwise}. \end{cases}\] It is easy to verify that \(\pi(\boldsymbol{x})=\boldsymbol{y}\). Hence \(\pi\) is surjective.

We now prove \[\pi \circ \tau_n = \tau_m \circ \pi,\] which means the following diagram commutes. \[\begin{tikzcd} \mathbb{F}_q^{n} \arrow[r, "\pi"] \arrow[d, "\tau_{n}"'] & \mathbb{F}_q^m \arrow[d, "\tau_m"'] \\ \mathbb{F}_q^{n} \arrow[r, "\pi"] & \mathbb{F}_q^m \end{tikzcd}\] It suffices to prove that for any \(\boldsymbol{x}\in\mathbb{F}_q^n\) and \(k\in[m]\), the equality \[\big(\pi(\tau_n(\boldsymbol{x}))\big)_k = \big(\tau_m(\pi(\boldsymbol{x}))\big)_k\] holds. First, we compute \[\big(\pi(\tau_n(\boldsymbol{x}))\big)_k = \sum_{j=0}^{d-1} \big(\tau_n(\boldsymbol{x})\big)_{k+jm} = \sum_{j=0}^{d-1} x_{(k+jm-1)\bmod n}.\] Similarly, \[\big(\tau_m(\pi(\boldsymbol{x}))\big)_k = \pi(\boldsymbol{x})_{(k-1)\bmod m} = \sum_{j=0}^{d-1} x_{((k-1)\bmod m) + jm}.\] When \(k \neq 0\), since \[0 \leq k + jm - 1 \leq m - 2 + (d-1)m = n - 2,\] it follows that \[k + jm - 1 \pmod{n} = k + jm - 1.\] Therefore, in this case, \[\{k + jm - 1 \pmod{n} : j = 0, \dots, d-1\} = \{((k-1) \bmod m) + jm : j = 0, \dots, d-1\}.\] When \(k = 0\), the same conclusion holds. Hence, \[\big(\pi(\tau_n(\boldsymbol{x}))\big)_k = \big(\tau_m(\pi(\boldsymbol{x}))\big)_k,\] and consequently, \[\pi \circ \tau_n = \tau_m \circ \pi.\]

Let \(U\) be an arbitrary cyclically covering subspace of \(\mathbb{F}_q^m\). Define the set \[V = \pi^{-1}(U) = \big\{\boldsymbol{x}\in\mathbb{F}_q^n : \pi(\boldsymbol{x})\in U\big\}.\] We first verify that \(V\) is a subspace of \(\mathbb{F}_q^n\). It follows that \[\begin{align} &\bigcup_{i=0}^{n-1}\tau_n^i(V)=\bigcup_{i=0}^{n-1}\tau_n^i\big(\pi^{-1}(U)\big)=\bigcup_{i=0}^{n-1}\pi^{-1}\big(\tau_m^i(U)\big) \\ =&~\pi^{-1}\left(\bigcup_{i=0}^{n-1}\tau_m^i(U)\right)=\pi^{-1}\left(\bigcup_{i=0}^{m-1}\tau_m^i(U)\right)=\pi^{-1}(\mathbb{F}_q^m)=\mathbb{F}_q^n. \end{align}\] Hence \(V\) is a cyclically covering subspace of \(\mathbb{F}_q^n\).

Since \(\pi\) is surjective, it follows from the dimension formula that \[\dim\mathbb{F}_q^n = \dim\ker\pi + \dim\mathbb{F}_q^m,\] which yields \(\dim\ker\pi = n-m\). Consider the restriction \(\pi|_V: V\to U\) of \(\pi\) to \(V\). This map is surjective: for any \(\boldsymbol{y}\in U\), the surjectivity of \(\pi\) guarantees the existence of \(\boldsymbol{x}\in\mathbb{F}_q^n\) such that \(\pi(\boldsymbol{x})=\boldsymbol{y}\), and hence \(\boldsymbol{x}\in V\) by definition. Moreover, \(\ker(\pi|_V) = \ker\pi\), since \(\ker\pi = \pi^{-1}(\{\boldsymbol{0}\}) \subseteq \pi^{-1}(U) = V\).

Applying the dimension formula again, we have \[\dim V = \dim\ker\pi + \dim U = n-m+\dim U.\] We then compute the codimension \[\operatorname{codim} V = n - \dim V = n - \big(n-m+\dim U\big) = m - \dim U = \operatorname{codim} U.\] This implies that there exists at least one cyclically covering subspace of \(\mathbb{F}_q^n\) whose codimension equals \(h_q(m)\). Consequently, we obtain \[h_q(n) \ge h_q(m).\] ◻

Proof. We first prove that \(\mathbb{F}_q^m \otimes \mathbb{F}_q^n \cong \operatorname{Mat}_{m\times n}(\mathbb{F}_q)\). Let \(\{\boldsymbol{e}_i\}\) and \(\{\boldsymbol{f}_j\}\) be the standard bases of \(\mathbb{F}_q^m\) and \(\mathbb{F}_q^n\), respectively. Then, the set \[\{\boldsymbol{e}_i \otimes \boldsymbol{f}_j : 0 \leq i \leq m-1, 0 \leq j \leq n-1\}\] forms a basis for \(\mathbb{F}_q^m \otimes \mathbb{F}_q^n\). Let \(E_{i,j} \in \operatorname{Mat}_{m\times n}(\mathbb{F}_q)\) denote the matrix with a \(1\) in the \((i,j)\) position and zeros elsewhere; then, the set \[\{E_{i,j} : 0 \leq i \leq m-1, 0 \leq j \leq n-1\}\] forms a basis for \(\operatorname{Mat}_{m\times n}(\mathbb{F}_q)\). Define a linear map \[\rho_1: \mathbb{F}_q^m \otimes \mathbb{F}_q^n \to \operatorname{Mat}_{m\times n}(\mathbb{F}_q),\quad \boldsymbol{e}_i \otimes \boldsymbol{f}_j \mapsto E_{i,j},\] and extend it linearly to the entire space. It is easy to verify that this is an isomorphism.

Let \(\{\boldsymbol{g}_k : 0 \le k \le mn-1\}\) be a standard basis for \(\mathbb{F}_q^{mn}\). Let \(\rho_2 : \mathbb{F}_q^{mn} \longrightarrow \mathbb{F}_q^m \otimes \mathbb{F}_q^n\) be a linear isomorphism defined on the standard basis as \[\rho_2(\boldsymbol{g}_k) = \boldsymbol{e}_a \otimes \boldsymbol{f}_b, \quad \text{if and only if }~~ \phi(k) = (a,b),\] and extend it linearly to the entire space. Here, \(\phi\) is the bijection \(\mathbb{Z}_{mn} \to \mathbb{Z}_m \times \mathbb{Z}_n\) given by the CRT. It is easy to verify that \(\rho_2\) is a linear isomorphism. ◻

Proof. It suffices to verify the equality on arbitrary basis element \(\boldsymbol{e}_i\otimes \boldsymbol{f}_j\). On the one hand, we have \[\begin{align} &\rho_1\circ (\tau_m\otimes \tau_n)(\boldsymbol{e}_i\otimes \boldsymbol{f}_j)=\rho_1\big((\tau_m \boldsymbol{e}_i)\otimes(\tau_n \boldsymbol{f}_j)\big)\\ &=\rho_1\big(\boldsymbol{e}_{(i+1)\bmod m}\otimes \boldsymbol{f}_{(j+1)\bmod n}\big)=E_{(i+1)\bmod m,\,(j+1)\bmod n}. \end{align}\] On the other hand, \[\begin{align} &(T_m\odot T_n)\circ \rho_1(\boldsymbol{e}_i\otimes \boldsymbol{f}_j)=(T_m\odot T_n)(E_{i,j})=T_m E_{i,j}T_n^{T}\\ &=T_m \boldsymbol{e}_i \boldsymbol{f}_j^{T}T_n^{T}=(T_m \boldsymbol{e}_i)(T_n \boldsymbol{f}_j)^{T}=\boldsymbol{e}_{(i+1)\bmod m}\cdot\boldsymbol{f}_{(j+1)\bmod n}^{T}\\ &=E_{(i+1)\bmod m,\,(j+1)\bmod n}. \end{align}\] Since the two mappings agree on all basis vectors \(e_i\otimes f_j\), we obtain \[\rho_1\circ (\tau_m\otimes \tau_n)=(T_m\odot T_n)\circ \rho_1.\] ◻

Proof. It suffices to verify the equality on every basis vector \(\boldsymbol{g}_k\). Since all mappings are linear, equality on a basis implies equality over the entire ambient vector space. Fix an arbitrary integer \(k\in\{0,1,\dots,mn-1\}\), and set \[a = k\bmod{m},\quad b = k\bmod{n},\] so that \(\rho_2(\boldsymbol{g}_k)=\boldsymbol{e}_a\otimes \boldsymbol{f}_b\). We first evaluate the composition \(\rho_2\circ \tau_{mn}\) at \(\boldsymbol{g}_k\): \[\begin{align} \rho_2\big(\tau_{mn}(\boldsymbol{g}_k)\big) &= \rho_2\big(\boldsymbol{g}_{(k+1)\bmod mn}\big)\\ &= \boldsymbol{e}_{(k+1)\bmod m}\otimes \boldsymbol{f}_{(k+1)\bmod n}\\ &= \boldsymbol{e}_{(a+1)\bmod m}\otimes \boldsymbol{f}_{(b+1)\bmod n}. \end{align}\] Next compute \((\tau_m\otimes\tau_n)\circ\rho_2\) acting on \(\boldsymbol{g}_k\): \[\begin{align} (\tau_m\otimes\tau_n)\big(\rho_2(\boldsymbol{g}_k)\big) &= (\tau_m\otimes\tau_n)(\boldsymbol{e}_a\otimes\boldsymbol{f}_b)\\ &=\tau_m(\boldsymbol{e}_a)\otimes\tau_n(\boldsymbol{f}_b)\\ &=\boldsymbol{e}_{(a+1)\bmod{m}}\otimes \boldsymbol{f}_{(b+1)\bmod{n}}. \end{align}\] The two computations produce exactly the same result. Therefore \(\rho_2\big(\tau_{mn}(\boldsymbol{g}_k)\big)=(\tau_m\otimes\tau_n)\big(\rho_2(\boldsymbol{g}_k)\big)\) holds for every basis element \(\boldsymbol{g}_k\). Extending linearly to the whole space, we arrive at the identity \[\rho_2\circ\tau_{mn}=(\tau_m\otimes\tau_n)\circ\rho_2.\] ◻

Proof. Let \(\boldsymbol{x}= \rho_2^{-1}(\boldsymbol{u}\otimes \boldsymbol{v})\), \(\boldsymbol{u}\in\mathbb{F}_q^m,\boldsymbol{v}\in\mathbb{F}_q^n\). Recall that \[\rho_2(\boldsymbol{g}_k)=\boldsymbol{e}_{k\bmod m}\otimes \boldsymbol{f}_{k\bmod n}= \boldsymbol{e}_a\otimes\boldsymbol{f}_b\] with \(\phi(k)=(a,b)\), which implies \[\rho_2^{-1}(\boldsymbol{e}_a\otimes\boldsymbol{f}_b)=\boldsymbol{g}_{\phi^{-1}(a,b)}.\] Here the inverse mapping is given by \[\phi^{-1}(a,b)=ant+bms \pmod{mn},\] where integers \(s,t\) satisfy \(sm+tn=1\). Write the vectors as basis expansions \[\boldsymbol{u}=\sum_{a=0}^{m-1}u_a \boldsymbol{e}_a,\quad \boldsymbol{v}=\sum_{b=0}^{n-1}v_b \boldsymbol{f}_b.\] By bilinearity of the tensor product, \[\boldsymbol{u}\otimes\boldsymbol{v}= \biggl(\sum_{a=0}^{m-1}u_a \boldsymbol{e}_a\biggr)\otimes\biggl(\sum_{b=0}^{n-1}v_b \boldsymbol{f}_b\biggr)=\sum_{a=0}^{m-1}\sum_{b=0}^{n-1}u_a v_b\,(\boldsymbol{e}_a\otimes\boldsymbol{f}_b).\] Applying \(\rho_2^{-1}\) to both sides yields \[\boldsymbol{x}= \rho_2^{-1}(\boldsymbol{u}\otimes\boldsymbol{v})=\sum_{a=0}^{m-1}\sum_{b=0}^{n-1}u_a v_b\,\rho_2^{-1}(\boldsymbol{e}_a\otimes\boldsymbol{f}_b)=\sum_{a=0}^{m-1}\sum_{b=0}^{n-1}u_a v_b \,\boldsymbol{g}_{\phi^{-1}(a,b)}.\] Therefore for every index \(k\in[mn]\), the entry of \(\boldsymbol{x}\) reads \[x_k = u_{k\bmod m}\cdot v_{k\bmod n}.\] From the definition of Discrete Fourier Transform, \[\widehat{\boldsymbol{x}}_k=\sum_{j=0}^{mn-1}x_j \omega^{jk},\quad k=0,1,\dots,mn-1,\] and substituting the above component formula we obtain \[\widehat{\boldsymbol{x}}_k=\sum_{j=0}^{mn-1}u_{j\bmod m}\cdot v_{j\bmod n}\,\omega^{jk}.\] Since \(\gcd(m,n)=1\), as \(j\) ranges from \(0\) to \(mn-1\), the pair \((a,b)=(j\bmod m,j\bmod n)\) exhausts all elements of \(\mathbb{Z}_m\times\mathbb{Z}_n\) bijectively, with the index inversion \[j=\phi^{-1}(a,b)=ant+bms\pmod{mn}.\] Changing summation variables to \(a,b\), we rewrite \[\widehat{\boldsymbol{x}}_k=\sum_{a=0}^{m-1}\sum_{b=0}^{n-1}u_a v_b \,\omega^{\phi^{-1}(a,b)\cdot k}.\] Set \((c,d)=\phi(k)\), so \(k=\phi^{-1}(c,d)=cnt+dms\pmod{mn}\). Compute the exponent modulo \(mn\): \[\begin{align} \phi^{-1}(a,b)\cdot k &= \big(ant+bms\big)\big(cnt+dms\big)\\ &\equiv acn^2t^2+bdm^2s^2 \pmod{mn}\\ &\equiv acnt+bdms \pmod{mn}. \end{align}\] Substituting back into the DFT expression, \[\begin{align} \widehat{\boldsymbol{x}}_k &=\sum_{a=0}^{m-1}\sum_{b=0}^{n-1}u_a v_b \,\omega^{acnt+bdms}\\ &=\sum_{a=0}^{m-1}\sum_{b=0}^{n-1}u_a v_b \,\omega_m^{act}\cdot\omega_n^{bds}\\ &=\biggl(\sum_{a=0}^{m-1}u_a \omega_m^{act}\biggr)\biggl(\sum_{b=0}^{n-1}v_b \omega_n^{bds}\biggr)\\ &=\widehat{\boldsymbol{u}}_{ct}\cdot \widehat{\boldsymbol{v}}_{ds}\\ &=\widehat{\boldsymbol{u}}_{kt\bmod m}\cdot \widehat{\boldsymbol{v}}_{ks\bmod n}. \end{align}\] From the identity \(\widehat{\boldsymbol{x}}_k=\widehat{\boldsymbol{u}}_{kt\bmod m}\cdot \widehat{\boldsymbol{v}}_{ks\bmod n}\), we have the equivalence \[\widehat{\boldsymbol{x}}_k\neq 0 \iff \widehat{\boldsymbol{u}}_{kt\bmod m}\neq 0 \text{ and } \widehat{\boldsymbol{v}}_{ks\bmod n}\neq 0.\] The above condition is equivalent to the existence of \(a\in \operatorname{supp}(\widehat{\boldsymbol{u}})\), \(b\in \operatorname{supp}(\widehat{\boldsymbol{v}})\) such that \[\begin{cases} kt\equiv a \pmod{m}\\ ks\equiv b \pmod{n}. \end{cases}\] Recall \(sm+tn=1\). For any fixed \(a\in\mathbb{Z}_m\), \(b\in\mathbb{Z}_n\), this system of congruences has the unique solution \[k\equiv an+bm \pmod{mn}.\] Consequently, \[\operatorname{supp}(\widehat{\boldsymbol{x}})=\bigl\{an+bm\pmod{mn} : a\in\operatorname{supp}(\widehat{\boldsymbol{u}}),\,b\in\operatorname{supp}(\widehat{\boldsymbol{v}})\bigr\}.\] ◻

The proof of Theorem 7. Let \(k=h_q(m)\) and \(l=h_q(n)\). We prove Theorem 7 by constructing a cyclically covering subspace of \(\mathbb{F}_q^{mn}\) with codimension \(k+l\).

Since \(k=h_q(m)\) and \(l=h_q(n)\), there exist two families of vectors \[\boldsymbol{\alpha}_1,\dots,\boldsymbol{\alpha}_k\in\mathbb{F}_q^m,\qquad \boldsymbol{\beta}_1,\dots,\boldsymbol{\beta}_l\in\mathbb{F}_q^n\] satisfying \[V_m=\bigcap_{i=1}^k V_{\boldsymbol{\alpha}_i},\qquad V_n=\bigcap_{j=1}^l V_{\boldsymbol{\beta}_j},\] where \(V_m\subset\mathbb{F}_q^m\) and \(V_n\subset\mathbb{F}_q^n\) are cyclically covering subspaces of codimension \(k\) and \(l\), respectively. Furthermore, by Theorem 2, we may assume \(0\notin\operatorname{supp}(\widehat{\boldsymbol{\alpha}}_i)\) and \(0\notin\operatorname{supp}(\widehat{\boldsymbol{\beta}}_j)\) for all integers \(1\le i\le k\) and \(1\le j\le l\).

We define two families of new vectors in \(\mathbb{F}_q^{mn}\) via the tensor product: \[\boldsymbol{\gamma}_i = \rho_2^{-1}(\boldsymbol{\alpha}_i \otimes \boldsymbol{1}_n) \quad (1\le i\le k),\qquad \boldsymbol{\delta}_j = \rho_2^{-1}(\boldsymbol{1}_m \otimes \boldsymbol{\beta}_j) \quad (1\le j\le l),\] where \(\boldsymbol{1}_m,\boldsymbol{1}_n\) denote the all-one vectors of \(\mathbb{F}_q^m\) and \(\mathbb{F}_q^n\), respectively. For the all-one vector, its Discrete Fourier Transform satisfies \(\operatorname{supp}(\widehat{\boldsymbol{1}}_n)=\{0\}\). By Lemma 21, we obtain \[\operatorname{supp}(\widehat{\boldsymbol{\gamma}}_i) = \bigl\{ an+bm \pmod{mn} : a\in\operatorname{supp}(\widehat{\boldsymbol{\alpha}}_i),\;b\in\{0\} \bigr\} = \bigl\{ an \pmod{mn} : a\in\operatorname{supp}(\widehat{\boldsymbol{\alpha}}_i) \bigr\}.\] Similarly, \[\operatorname{supp}(\widehat{\boldsymbol{\delta}}_j) = \bigl\{ bm \pmod{mn} : b\in\operatorname{supp}(\widehat{\boldsymbol{\beta}}_j) \bigr\}.\] Since \(0\notin\operatorname{supp}(\widehat{\boldsymbol{\alpha}}_i)\) and \(\gcd(m,n)=1\), the congruence \(an\equiv0\pmod{mn}\) holds if and only if \(a\equiv0\pmod{m}\). This implies \(0\notin\operatorname{supp}(\widehat{\boldsymbol{\gamma}}_j)\). By symmetry, \(0\notin\operatorname{supp}(\widehat{\boldsymbol{\delta}}_j)\). Suppose \(an\equiv bm\pmod{mn}\). Reducing modulo \(m\), we get \(an\equiv0\pmod{m}\), hence \(a\equiv0\pmod{m}\), which leads to a contradiction. Therefore the two families of support sets are mutually disjoint. The Discrete Fourier Transform is a linear isomorphism; vectors with pairwise disjoint supports are linearly independent. Consequently, the set \(\{\boldsymbol{\gamma}_1,\dots,\boldsymbol{\gamma}_k,\boldsymbol{\delta}_1,\dots,\boldsymbol{\delta}_l\}\) is linearly independent.

Define \[W = \biggl(\bigcap_{j=1}^k V_{\boldsymbol{\gamma}_j}\biggr)\bigcap \biggl(\bigcap_{j=1}^l V_{\boldsymbol{\delta}_j}\biggr).\] It follows that \(\operatorname{codim} W = h_q(m)+h_q(n)\).

Assume for contradiction that W is not a cyclically covering subspace. By Theorem 2, there exists a common vector \(\boldsymbol{x}\in\mathbb{F}_q^{mn}\), together with a collection of corresponding vectors \[\boldsymbol{c}_{\gamma_1},\dots,\boldsymbol{c}_{\gamma_k},\boldsymbol{c}_{\delta_1},\dots,\boldsymbol{c}_{\delta_l}\in \mathbb{F}_{q^M}^{mn},\] satisfying the three conditions below:

(1) Support condition: \[\operatorname{supp}(\boldsymbol{c}_{\gamma_i}) \subseteq -\operatorname{supp}(\widehat{\boldsymbol{\gamma}}_i)\;\;(1\le i\le k),\quad \operatorname{supp}(\boldsymbol{c}_{\delta_j}) \subseteq -\operatorname{supp}(\widehat{\boldsymbol{\delta}}_j)\;\;(1\le j\le l);\]

(2) Common-vector condition: \[(\boldsymbol{c}_{\gamma_i})_s = \widehat{\boldsymbol{x}}_s \cdot (\widehat{\boldsymbol{\gamma}}_i)_{-s}\;\;(1\le i\le k),\quad (\boldsymbol{c}_{\delta_j})_s = \widehat{\boldsymbol{x}}_s \cdot (\widehat{\boldsymbol{\delta}}_j)_{-s}\;\;(1\le j\le l);\]

(3) No-common-zero condition: There is no index \(i_0\in[mn]\) such that \(P_{\boldsymbol{c}_{\gamma_i}}(\omega^{i_0})=0\) and \(P_{\boldsymbol{c}_{\delta_j}}(\omega^{i_0})=0\) hold simultaneously for all \(1\le i\le k\), \(1\le j\le l\).

We now define vectors associated with the smaller spaces: \[\text{For each}~\boldsymbol{c}_{\gamma_i},~\text{set}~\boldsymbol{u}_i\in \operatorname{DFT}(\mathbb{F}_q^m)~\text{via}~(\boldsymbol{u}_i)_{k_1} = (\boldsymbol{c}_{\gamma_i})_{k_1n\pmod{mn}};\] \[\text{For each}~\boldsymbol{c}_{\delta_j},~\text{set}~\boldsymbol{v}_j\in \operatorname{DFT}(\mathbb{F}_q^n)~\text{via}~(\boldsymbol{v}_j)_{k_2} = (\boldsymbol{c}_{\delta_j})_{k_2m\pmod{mn}}.\] It is immediate that \[\operatorname{supp}(\boldsymbol{u}_i)\subseteq -\operatorname{supp}(\widehat{\boldsymbol{\alpha}}_i),\qquad \operatorname{supp}(\boldsymbol{v}_j)\subseteq -\operatorname{supp}(\widehat{\boldsymbol{\beta}}_j).\]

We next verify that each \(\boldsymbol{u}_i\) satisfies the common-vector condition from Theorem 2 over \(\mathbb{F}_q^m\). From the common-vector condition, \[(\boldsymbol{c}_{\gamma_i})_{k_1n} = \widehat{\boldsymbol{x}}_{k_1n}\cdot (\widehat{\boldsymbol{\gamma}}_i)_{-k_1n}.\] Using the explicit DFT formula in Lemma 21 to evaluate \((\widehat{\boldsymbol{\gamma}}_i)_{-k_1n}\): \[(\widehat{\boldsymbol{\gamma}}_i)_{-k_1n} = (\widehat{\boldsymbol{\alpha}}_i)_{(-k_1n)t \bmod m}\cdot (\widehat{\boldsymbol{1}}_n)_{(-k_1n)s \bmod n}= (\widehat{\boldsymbol{\alpha}}_i)_{-k_1 \bmod m}\cdot (\widehat{\boldsymbol{1}}_n)_{0}=n\cdot (\widehat{\boldsymbol{\alpha}}_i)_{-k_1 \bmod m}.\] Substitution into the common-vector identity gives \[(\boldsymbol{u}_i)_{k_1} = \widehat{\boldsymbol{x}}_{k_1n}\cdot n\cdot (\widehat{\boldsymbol{\alpha}}_i)_{-k_1\pmod{m}}.\] Set \(\widehat{\boldsymbol{y}}_{k_1} = n\cdot \widehat{\boldsymbol{x}}_{k_1n}\). Then \[(\boldsymbol{u}_i)_{k_1} = \widehat{\boldsymbol{y}}_{k_1}\cdot (\widehat{\boldsymbol{\alpha}}_i)_{-k_1\pmod{m}},\] which is exactly the common-vector condition of Theorem 2 for the space \(\mathbb{F}_q^m\). Furthermore, one can readily verify that \((\widehat{\boldsymbol{y}}_{k_1})^q = \widehat{\boldsymbol{y}}_{qk_1}\) and \(\big(({\boldsymbol{u}}_i)_{k_1}\big)^q = ({\boldsymbol{u}}_i)_{qk_1}\) for all \(k_1\in[m]\). Therefore, by the Inverse Discrete Fourier Transform, \(\widehat{\boldsymbol{y}}\) corresponds to a vector \(\boldsymbol{y}\in\mathbb{F}_q^m\). By symmetry, each \(\boldsymbol{v}_j\) satisfies the analogous common-vector condition of Theorem 2 over \(\mathbb{F}_q^n\).

Now we analyze the associated trace polynomials. For a vector \(\boldsymbol{c}\in\mathbb{F}_{q^M}^{mn}\) the trace polynomial is defined by \[P_{\boldsymbol{c}}(t) = \sum_{s=0}^{mn-1} c_s t^s.\] Since entries of \(\boldsymbol{c}_{\gamma_i}\) vanish except at indices of the form \(s=k_1n\), we have \[P_{\boldsymbol{c}_{\gamma_i}}(t) = \sum_{k_1=0}^{m-1} (\boldsymbol{u}_i)_{k_1} t^{k_1n}= P_{\boldsymbol{u}_i}(t^{\,n}),\] where \(P_{\boldsymbol{u}_i}(z)=\sum_{k_1} (\boldsymbol{u}_i)_{k_1} z^{k_1}\) is the trace polynomial of \(\boldsymbol{u}_i\) in \(\mathbb{F}_q^m\). Analogously, \[P_{\boldsymbol{c}_{\delta_j}}(t) = \sum_{k_2=0}^{n-1} (\boldsymbol{v}_j)_{k_2} t^{k_2m}= P_{\boldsymbol{v}_j}(t^{\,m}),\] with \(P_{\boldsymbol{v}_j}(z)=\sum_{k_2} (\boldsymbol{v}_j)_{k_2} z^{k_2}\) being the trace polynomial of \(\boldsymbol{v}_j\) in \(\mathbb{F}_q^n\).

Since \(V_m\) is a cyclically covering subspace of \(\mathbb{F}_q^m\), by Theorem 2, there exists some \(a_0\in\mathbb{Z}_m\) such that \[P_{\boldsymbol{u}_i}(\omega_m^{a_0}) = 0 ~~ \text{for all }~1\le i\le k.\] Similarly, as \(V_n\) is cyclically covering in \(\mathbb{F}_q^n\), there exists \(b_0\in\mathbb{Z}_n\) satisfying \[P_{\boldsymbol{v}_j}(\omega_n^{b_0}) = 0 \quad \text{for all }1\le j\le l.\] By the Chinese Remainder Theorem, there is a unique integer \(i_0\in[mn]\) with \[i_0\equiv a_0\pmod{m},\qquad i_0\equiv b_0\pmod{n}.\] We evaluate the trace polynomials at \(\omega^{i_0}\). For each \(\boldsymbol{c}_{\gamma_i}\): \[P_{\boldsymbol{c}_{\gamma_i}}(\omega^{i_0})= P_{\boldsymbol{u}_i}\big((\omega^{i_0})^{n}\big)= P_{\boldsymbol{u}_i}\big(\omega^{n i_0}\big)= P_{\boldsymbol{u}_i}\big((\omega^n)^{i_0}\big)= P_{\boldsymbol{u}_i}(\omega_m^{a_0}) = 0.\] For each \(\boldsymbol{c}_{\delta_j}\): \[P_{\boldsymbol{c}_{\delta_j}}(\omega^{i_0})= P_{\boldsymbol{v}_j}\big((\omega^{i_0})^{m}\big)= P_{\boldsymbol{v}_j}\big(\omega^{m i_0}\big)= P_{\boldsymbol{v}_j}\big((\omega^m)^{i_0}\big)= P_{\boldsymbol{v}_j}(\omega_n^{b_0}) = 0.\]

We have thus produced a common index \(i_0\) annihilating all trace polynomials simultaneously, which directly contradicts the no-common-zero condition from our initial contradictory assumption. Hence our contrary assumption fails, and \(W\) is a cyclically covering subspace of \(\mathbb{F}_q^{mn}\). We have constructed a cyclically covering subspace of \(\mathbb{F}_q^{mn}\) with codimension \(h_q(m)+h_q(n)\). By definition of the maximal codimension, we have \[h_q(mn)\ge h_q(m)+h_q(n).\] This completes the proof of Theorem 7. ◻

Proof. These four properties can be verified directly; we only supply proofs for the last two. For Property (3), we have \[\begin{align} \boldsymbol{v} \in (\tau^i U)^\perp &\iff (\boldsymbol{v}, \tau^i \boldsymbol{u}) = 0,\;\forall \boldsymbol{u} \in U \\ &\iff (\tau^{-i} \boldsymbol{v}, \boldsymbol{u}) = 0,\;\forall \boldsymbol{u} \in U \\ &\iff \tau^{-i} \boldsymbol{v} \in U^\perp \\ &\iff \boldsymbol{v} \in \tau^i(U^\perp). \end{align}\]

Next, we establish Property (4). Let \(U_0 \subseteq \mathbb{F}_q^n\) be an \(\mathbb{F}_q\)-linear subspace. We regard \(U_0 \otimes_{\mathbb{F}_q} \mathbb{F}_{q^m}\) canonically as the \(\mathbb{F}_{q^m}\)-linear subspace of \(\mathbb{F}_{q^m}^n\) spanned by \(U_0\). We first establish the inclusion relation. If \(\boldsymbol{v} \in U_0^\perp\), then \((\boldsymbol{u},\boldsymbol{v})=0\) holds for all \(\boldsymbol{u} \in U_0\). Accordingly, for arbitrary \(a,b \in \mathbb{F}_{q^m}\), we have \((a\boldsymbol{u},b\boldsymbol{v})=ab(\boldsymbol{u},\boldsymbol{v})=0\), which implies \[U_0^\perp \otimes_{\mathbb{F}_q} \mathbb{F}_{q^m} \subseteq \left(U_0 \otimes_{\mathbb{F}_q} \mathbb{F}_{q^m}\right)^\perp.\]

We then compare the dimensions of both sides. Let \(\dim_{\mathbb{F}_q} U_0 = r\). It follows that \(\dim_{\mathbb{F}_{q^m}} \left(U_0 \otimes_{\mathbb{F}_q} \mathbb{F}_{q^m}\right) = r\), so \(\dim_{\mathbb{F}_{q^m}} \left(U_0 \otimes_{\mathbb{F}_q} \mathbb{F}_{q^m}\right)^\perp = n-r\). On the other hand, \(\dim_{\mathbb{F}_q} U_0^\perp = n-r\), hence \(\dim_{\mathbb{F}_{q^m}} \left(U_0^\perp \otimes_{\mathbb{F}_q} \mathbb{F}_{q^m}\right) = n-r\). Since we have derived the inclusion above and the two \(\mathbb{F}_{q^m}\)-linear subspaces share identical dimensions, then \[\left(U_0 \otimes_{\mathbb{F}_q} \mathbb{F}_{q^m}\right)^\perp = U_0^\perp \otimes_{\mathbb{F}_q} \mathbb{F}_{q^m}.\] ◻

Proof. This is a standard result; we refer the reader to [17]. ◻

Proof. Let \(k = h_{q^m}(n)\). By definition, there exists a cyclically covering subspace \(U \subseteq \mathbb{F}_{q^m}^n\) of codimension \(k\). We will construct a cyclically covering subspace of \(\mathbb{F}_q^n\) with codimension at least \(k\), which implies \(h_q(n) \ge k\).

Let \(A = U^\perp \subseteq \mathbb{F}_{q^m}^n\) be the orthogonal complement of \(U\). Then \[\dim_{\mathbb{F}_{q^m}} A = \operatorname{codim}_{\mathbb{F}_{q^m}} U = k.\] We define the Galois closure of \(A\) as \[B = \sum_{\sigma \in G} \sigma(A) = \operatorname{span}_{\mathbb{F}_{q^m}} \big\{\sigma(\boldsymbol{\alpha}) \,\big|\, \boldsymbol{\alpha} \in A,\;\sigma \in G\big\}.\] Clearly, \(B\) is a \(G\)-invariant subspace. By Galois descent (Lemma 23), there exists a unique \(\mathbb{F}_q\)-subspace \(B_0 \subseteq \mathbb{F}_q^n\) such that \[B = B_0 \otimes_{\mathbb{F}_q} \mathbb{F}_{q^m},\] and \[\dim_{\mathbb{F}_q} B_0 = \dim_{\mathbb{F}_{q^m}} B \ge \dim_{\mathbb{F}_{q^m}} A = k.\] Let \(V = B_0^\perp \subseteq \mathbb{F}_q^n\) denote the orthogonal complement of \(B_0\) in \(\mathbb{F}_q^n\). It follows that \[\operatorname{codim}_{\mathbb{F}_q} V = \dim_{\mathbb{F}_q} B_0 \ge k.\]

To prove that \(V\) is a cyclically covering subspace of \(\mathbb{F}_q^n\), we need to verify \[\bigcup_{i=0}^{n-1} \tau^i(V) = \mathbb{F}_q^n.\] Equivalently, for any \(\boldsymbol{x} \in \mathbb{F}_q^n\), there exists some \(i \in [n]\) satisfying \(\boldsymbol{x} \in \tau^i(V)\).

Since \(\boldsymbol{x} \in \mathbb{F}_q^n \subset \mathbb{F}_{q^m}^n\) and \(U\) is a cyclically covering subspace of \(\mathbb{F}_{q^m}^n\), the definition yields an index \(i \in [n]\) such that \(\boldsymbol{x} \in \tau^i(U)\). Recall that \[\tau^i(U) = \tau^i(A^\perp) = \big(\tau^i A\big)^\perp.\] Hence \((\boldsymbol{x},\, \tau^i \boldsymbol{\alpha}) = 0\) holds for all \(\boldsymbol{\alpha} \in A\).

For any \(\sigma \in G\), we compute: \[\begin{align} \big(\boldsymbol{x},\, \tau^i \sigma(\boldsymbol{\alpha})\big)= \big(\boldsymbol{x},\, \sigma(\tau^i \boldsymbol{\alpha})\big) = \big(\sigma(\boldsymbol{x}),\, \sigma(\tau^i \boldsymbol{\alpha})\big) = \sigma\big((\boldsymbol{x},\, \tau^i \boldsymbol{\alpha})\big) = \sigma(0) = 0. \end{align}\] This means that \(\boldsymbol{x}\) is orthogonal to every vector of the form \(\tau^i \sigma(\boldsymbol{\alpha})\).

As \(B = \sum_{\sigma\in G} \sigma(A)\), \(\boldsymbol{x}\) is orthogonal to all elements in \(\tau^i B\), i.e., \(\boldsymbol{x} \in \big(\tau^i B\big)^\perp.\) Moreover, \[B^\perp = \big(B_0 \otimes_{\mathbb{F}_q} \mathbb{F}_{q^m}\big)^\perp = B_0^\perp \otimes_{\mathbb{F}_q} \mathbb{F}_{q^m} = V \otimes_{\mathbb{F}_q} \mathbb{F}_{q^m}.\] Combining these relations yields \(\boldsymbol{x} \in \tau^i\big(V \otimes_{\mathbb{F}_q} \mathbb{F}_{q^m}\big).\) Note that \(\boldsymbol{x} \in \mathbb{F}_q^n\) and \(\tau^i(V) \subset \mathbb{F}_q^n\). We then obtain \[\boldsymbol{x} \in \tau^i\big(V \otimes_{\mathbb{F}_q} \mathbb{F}_{q^m}\big) \cap \mathbb{F}_q^n = \tau^i(V).\] We have constructed a cyclically covering subspace \(V\) of \(\mathbb{F}_q^n\) whose codimension is at least \(k\). Consequently, \[h_q(n) \ge \operatorname{codim}_{\mathbb{F}_q} V \ge k = h_{q^m}(n),\] which implies the inequality \[h_{q^m}(n) \le h_q(n)\] holds for all cases. This completes the proof of Theorem 8. ◻

Proof. Let \(q\) be a prime power, \(m\) a positive integer, and \(h \mid q-1\) such that \(\gcd\left(\dfrac{q^m-1}{q-1},\,h\right)=\gcd\left(m, h\right)=1\). Denote \[n = \frac{q^m-1}{h}.\]

The multiplicative group \(\mathbb{F}_{q^m}^\ast\) of the finite field \(\mathbb{F}_{q^m}\) is a cyclic group of order \(q^m-1\). Let \(\gamma\) be a generator of \(\mathbb{F}_{q^m}^\ast\). Define the subgroup \(H = \langle \gamma^n \rangle\). From \(n = \dfrac{q^m-1}{h}\), we have \(|H|=h\). Since \(h \mid q-1\), it follows that \(H \subseteq \mathbb{F}_q^\ast\). Construct the quotient group \(G = \mathbb{F}_{q^m}^\ast / H\), which is also cyclic of order \(n\), generated by \(\bar{\gamma} = \gamma H\).

Take \(\beta = \gamma^h\). The order of \(\beta\) is \[\frac{q^m-1}{\gcd(q^m-1,\,h)} = n,\] so \(\beta^n=1\) and \(\bar{\beta} = \beta H = \bar{\gamma}^h\).

Let \[\Phi: \mathbb{F}_q^n \to \mathbb{F}_{q^m},\quad \Phi(\boldsymbol{v}) = \sum_{i=0}^{n-1} v_i\, \beta^i.\]

If \(m=1\), then \(\mathbb{F}_{q^m}=\mathbb{F}_q\), and \(\Phi\) is clearly surjective as its image is the entire field \(\mathbb{F}_q\).

If \(m\ge 2\), we have \[n = \frac{q^m-1}{h} \geq \frac{q^m-1}{q-1} \ge q^{m-1}+1.\] This implies the order of \(\beta\) is greater than \(q^{m-1}\), so \(\beta\) does not lie in any proper subfield of \(\mathbb{F}_{q^m}\). Consequently, the minimal polynomial of \(\beta\) over \(\mathbb{F}_q\) has degree \(m\), and \(\{1,\beta,\beta^2,\dots,\beta^{m-1}\}\) forms an \(\mathbb{F}_q\)-basis for \(\mathbb{F}_{q^m}\). The set \(\{\beta^i \mid 0\le i\le n-1\}\) therefore spans the entire extension field, which means \(\Phi\) is surjective.

By the dimension formula for linear maps, we get \[\dim \ker \Phi = n - m.\]

Take an arbitrary \(1\)-dimensional \(\mathbb{F}_q\)-subspace \(W\) of \(\mathbb{F}_{q^m}\) (a typical choice is \(W=\mathbb{F}_q\)). Define \[U = \big\{\, \boldsymbol{v}\in\mathbb{F}_q^n : \Phi(\boldsymbol{v})\in W \,\big\}.\] By properties of linear maps, \(U\) is a linear subspace. The restriction of \(\Phi\) to \(U\) has kernel \(\ker\Phi\) and image \(W\), so \[\dim U = \dim\ker\Phi + 1 = n - m + 1.\] The codimension of \(U\) is then \[\operatorname{codim}U = m-1.\]

For any vector \(\boldsymbol{v}\), compute the image of its shift under \(\Phi\): \[\begin{align} \Phi(\tau \boldsymbol{v}) &= \sum_{i=0}^{n-1} (\tau \boldsymbol{v})_i\, \beta^i= v_{n-1} + \sum_{i=1}^{n-1} v_{i-1}\, \beta^i \\ &= v_{n-1} + \beta\sum_{j=0}^{n-2} v_j\, \beta^j \\ &= \beta\sum_{j=0}^{n-1} v_j\, \beta^j + v_{n-1}\big(1-\beta^n\big). \end{align}\] Since \(\beta^n=1\), the last term vanishes. Hence for all \(\boldsymbol{v}\in\mathbb{F}_q^n\), \[\Phi(\tau \boldsymbol{v}) = \beta\,\Phi(\boldsymbol{v}).\] Define the map \(T\colon \mathbb{F}_{q^m}\to\mathbb{F}_{q^m}\) by \(T(x) = \beta x\). Then we have the following commutative diagram: \[\begin{tikzcd} \mathbb{F}_q^{n} \arrow[r, "\Phi"] \arrow[d, "\tau"'] & \mathbb{F}_{q^m} \arrow[d, "T"'] \\ \mathbb{F}_q^{n} \arrow[r, "\Phi"] & \mathbb{F}_{q^m} \end{tikzcd}\]

We now verify that for any nonzero vector \(\boldsymbol{v}\in \mathbb{F}_q^n\), there exists an integer \(i\in[n]\) such that \(\tau^i \boldsymbol{v}\in U\). By definition, \[\tau^i \boldsymbol{v}\in U \iff \Phi(\tau^i \boldsymbol{v})\in W.\] Recall that \(\Phi(\tau^i \boldsymbol{v})=\beta^i\Phi(\boldsymbol{v})\), which further implies \[\Phi(\tau^i \boldsymbol{v})\in W \iff \beta^i \Phi(\boldsymbol{v})\in W.\] Let \(\boldsymbol{v}\in \mathbb{F}_q^n\) be a nonzero vector. If \(\Phi(\boldsymbol{v})=0\), then \(\boldsymbol{v}\in\ker\Phi\subseteq U\), and we may take \(i=0\). If \(\Phi(\boldsymbol{v})\neq 0\), it suffices to find an integer \(i\) such that \(\tau^i \boldsymbol{v}\in U\), which is equivalent to \[\beta^i \Phi(\boldsymbol{v}) \in W = \mathbb{F}_q.\]

Introduce the projective space \[\mathbb{P} = \big\{\, [y] = \mathbb{F}_q^\ast\cdot y : y\in\mathbb{F}_{q^m}^\ast \big\},\] with cardinality \(|\mathbb{P}| = \dfrac{q^m-1}{q-1}\). The group \(G=\mathbb{F}_{q^m}^\ast/H\) acts on \(\mathbb{P}\) by \((gH)\cdot [y] = [gy]\). The stabilizer of \([1]\) is \[S = \operatorname{Stab}_G([1]) = \mathbb{F}_q^\ast / H,\quad |S| = \frac{q-1}{h}.\] We have \[\frac{|G|}{|S|} = \dfrac{n}{\frac{q-1}{h}} = \frac{q^m-1}{q-1} = |\mathbb{P}|,\] so \(G\) acts transitively on \(\mathbb{P}\).

Let \[A = \frac{q^m-1}{q-1},\qquad B = \frac{q-1}{h},\] so \(n=AB\), and the given condition is \(\gcd(A,h)=1\).

Let \(K=\langle \bar{\beta} \rangle\) be the subgroup generated by \(\bar{\beta}=\bar{\gamma}^h\). The order of \(K\) is \(\dfrac{n}{\gcd(n,h)}\). Using \(\gcd(A,h)=1\), we obtain \[\gcd(n,h) = \gcd(AB,h) = \gcd(B,h).\] Set \(d=\gcd(B,h)\), then \(|K|=\dfrac{n}{d}\).

Direct computation in the cyclic group \(G\) gives \(|K\cap S|=\dfrac{B}{d}\). By the formula for the order of a product of groups: \[|KS| = \frac{|K|\cdot |S|}{|K\cap S|} = \frac{\frac{n}{d}\cdot B}{\frac{B}{d}} = n,\] which implies \(KS=G\). Thus \(K\) acts transitively on the coset space \(G/S \cong \mathbb{P}\).

By transitivity, there exists an integer \(i\) such that \(\bar{\beta}^i\cdot [1] = [\Phi(\boldsymbol{v})]\), i.e. \[\beta^{-i} \Phi(\boldsymbol{v}) \in \mathbb{F}_q^\ast.\] This yields \(\tau^{-i} \boldsymbol{v}\in U\). Therefore \(U\) is a cyclically covering subspace of \(\mathbb{F}_q^n\).

In summary, \(U\) is a cyclically covering subspace, which yields the lower bound \(h_q(n)\ge m-1\). Combining this with the upper bound \[h_q(n)\le\left\lfloor \log_q\left( \frac{q^m - 1}{h} \right) \right\rfloor = m-1,\] we eventually conclude that \(h_q(n)=m-1\). ◻

Proof. By the results in [5] (see Lemma 2), we have \[h_q(mn) \ge h_q(m) + h_q(n) \qquad\text{for all positive integers } m,n.\] In particular, if \(\operatorname{rad}(n) = \prod_{p\mid n}p\) denotes the radical of \(n\), then \[h_q(n) \ge h_q(\operatorname{rad}(n)) \ge \sum_{p\mid n} h_q(p).\] Let \(w_{\mathcal{P}}(n)\) be the number of distinct prime factors of \(n\) that belong to \(\mathcal{P}\), i.e., \(w_{\mathcal{P}}(n) = \displaystyle\sum_{\substack{p \in \mathcal{P} \\ p\mid n}} 1\). Since \(h_q(p) \ge c_q\) for all \(p\in \mathcal{P}\), we immediately get \[h_q(n) \ge c_q \, w_{\mathcal{P}}(n).\]

Summing over all integers \(n\le X\) gives \[\sum_{n\le X} h_q(n) \ge c_q \sum_{n\le X} w_{\mathcal{P}}(n).\] Interchanging the order of summation yields \[\sum_{n\le X} w_{\mathcal{P}}(n)= \sum_{\substack{p\in \mathcal{P}\\ p\le X}} \sum_{\substack{n\le X\\ p\mid n}} 1 =\sum_{\substack{p\in \mathcal{P}\\ p\le X}} \Bigl\lfloor \frac{X}{p} \Bigr\rfloor.\] Writing \[\left\lfloor \frac{X}{p} \right\rfloor = \frac{X}{p} - \left\{\frac{X}{p}\right\}\] with \(0\le \left\{\frac{X}{p}\right\}<1\), we obtain \[\label{eq:main-ineq} \sum_{n\le X} h_q(n) \ge c_q \Bigl( X \sum_{\substack{p\in \mathcal{P}\\ p\le X}} \frac{1}{p}-\sum_{\substack{p\in \mathcal{P}\\ p\le X}} \Bigl\{ \frac{X}{p} \Bigr\} \Bigr).\tag{1}\] Next, we evaluate the sum \(\displaystyle\sum_{\substack{p \in \mathcal{P} \\ p \le X}} \frac{1}{p}\) by means of Abel’s summation formula. Define \[a_p = \begin{cases} 1, & \text{if } p \in \mathcal{P} \text{ and } p \text{ is prime}, \\ 0, & \text{otherwise}, \end{cases}\] and let \(A(t) = \displaystyle\sum_{p \le t} a_p = \pi_{\mathcal{P}}(t)\), which counts the number of primes in \(\mathcal{P}\) up to \(t\). Set \(f(t) = \dfrac{1}{t}\). By Abel’s summation formula, \[\sum_{p \le X} a_p f(p) = A(X)f(X) - \int_{2}^{X} A(t) f'(t) dt.\] Substituting the corresponding expressions, we get \[\sum_{\substack{p\in \mathcal{P}\\ p\le X}} \frac{1}{p}= \frac{\pi_P(X)}{X} + \int_{2}^{X} \frac{\pi_P(t)}{t^2}\,dt.\] Substituting \(\pi_P(t) = A_q \pi(t) + R(t)\) with \(R(t)=o\left(\frac{t}{\log t}\right)\), we obtain \[\sum_{\substack{p\in \mathcal{P}\\ p\le X}} \frac{1}{p}= A_q\Bigl( \frac{\pi(X)}{X} + \int_{2}^{X} \frac{\pi(t)}{t^2}\,dt \Bigr)+ \frac{R(X)}{X} + \int_{2}^{X} \frac{R(t)}{t^2}\,dt.\] Recall Mertens’ second theorem: \[\sum_{p \le X} \frac{1}{p} = \log\log X + M + o(1),\] where \(M\) is the Meissel-Mertens constant. Applying Abel’s summation formula once again (with \(a_n=1\) for prime \(n\) and \(a_n=0\) otherwise, and \(f(t)=\frac{1}{t}\)) verifies that \[\frac{\pi(X)}{X} + \int_{2}^{X} \frac{\pi(t)}{t^2} dt = \sum_{p \le X} \frac{1}{p}.\] Moreover, \(\frac{R(X)}{X} = o\left(\frac{1}{\log X}\right) \to 0\) and, because \(R(t)=o\left(\frac{t}{\log t}\right)\), \[\int_{2}^{X} \frac{R(t)}{t^2}\,dt = \int_{2}^{X} o\!\left(\frac{1}{t\log t}\right)dt = o(\log\log X).\] Consequently, \[\label{eq:recip-sum} \sum_{\substack{p\in \mathcal{P}\\ p\le X}} \frac{1}{p} = A_q \log\log X + o(\log\log X).\tag{2}\]

For the fractional part sum we use the trivial estimate \[\label{eq:frac-sum} \sum_{\substack{p\in \mathcal{P}\\ p\le X}} \Bigl\{ \frac{X}{p} \Bigr\}\le \sum_{\substack{p\in \mathcal{P}\\ p\le X}} 1 = \pi_{\mathcal{P}}(X) \sim A_q \frac{X}{\log X}= o(X\log\log X).\tag{3}\] Inserting 2 and 3 into 1 gives \[\sum_{n\le X} h_q(n)\ge c_q \Bigl( X\bigl(A_q \log\log X + o(\log\log X)\bigr) - o(X\log\log X) \Bigr)= c_q A_q X \log\log X + o(X\log\log X).\] Dividing by \(X\) we finally obtain \[\frac{1}{X}\sum_{n\le X} h_q(n) \ge (c_q A_q + o(1))\log\log X.\] ◻

Proof. We take the set of primes \(\mathcal{P}\) in Theorem 10 as \[\mathcal{P}=\{p \text{ prime} : p>3 ~\text{ and }~ 2~ \text{ is a primitive root modulo } p\}.\] In this case, \(c_2=2\). Consequently, Corollary 6 follows from Theorem 10. ◻

Proof. In Theorem 4 and Lemma 17, we show that for any prime \(n>3\) with \(\operatorname{ord}_n(3)\) odd, the inequality \(h_3(n)\ge 1\) holds. Such primes make up a proportion of \(\frac{1}{3}\) among all primes. Define the set of primes \[\mathcal{P}=\{p \text{ prime} : p>3~ \text{ and } ~\operatorname{ord}_p(3)~\text{is odd}\}.\] Consequently, Corollary 7 follows from Theorem 10. ◻