The linear complexity of generalized cyclotomic binary sequences of period \(p^n\) (Q2414940)

Let \(s^{\infty}=(s_0, s_1, s_2, \dots)\) be a binary sequence of period \(N\) and the polynomial \(S(x)\) be defined as \(S(x)=s_0+s_1x+\dots+s_{N-1}x^{N-1}\). The linear complexity \(L\) of \(s^{\infty}\) is the length of the shortest linear feedback shift register that generates \(s^{\infty}\). In terms of \(S(x)\), this is given as \(L = N - \deg (\gcd(x^N-1, S(x)))\). If \(\beta\) is a primitive \(N\)th root of unity in an extension field of \(\mathbb{F}_2\), then the linear complexity can also be expressed as \(L=N - |\{i \in \mathbb{Z}_N : S(\beta^i) = 0\}|\). Let \(p\) be an odd prime and \(p=ef+1\) with \(e,f\) being positive integers. Let \(g\) be a primitive root modulo \(p^2\), i.e., \(g\) is a generator for the multiplicative group of \(\mathbb{Z}_{p^2}\). Using the lifting the exponent lemma, it can be shown that \(g\) is also a generator for the multiplicative group of \(\mathbb{Z}_{p^j}\) for each \(j \geq 1\). Let \(n\) be a positive integer. For each \(j=1,\dots,n\), let \(d_j=fp^{j-1}\) and define the generalized cyclotomic classes of order \(d_j\) as the sets \[ D_0^{(p^j)}=\{g^{td_j}: t=0,\dots, d_j-1\} \] and \[ D_i^{(p^j)}=\{g^{i+td_j}: t=0,\dots, d_j-1\}. \] For an integer \(n\geq 1\), we can represent \(\mathbb{Z}_{p^n}\) as \[ \mathbb{Z}_{p^n}=\bigcup_{j=1}^n\bigcup_{i=0}^{d_j-1} p^{n-j} D_i^{p^j} \cup \{0\}. \] To define a binary sequence, first, an even integer \(f\) and another integer \(b\) with \(0 \leq b <p^{n-1}f\) are fixed. Then \(\mathbb{Z}_{p^n}\) is divided into two subsets \(\mathcal{C}_0^{p^n}\) and \(\mathcal{C}_1^{p^n}\) which are defined as \[ \mathcal{C}_0^{p^n} = \bigcup_{j=1}^{n} \bigcup_{i=d_j/2}^{d_j-1}p^{n-j}D_{(i+b)}^{p^j}, \] \[ \mathcal{C}_1^{p^n}=\bigcup_{j=1}^{n} \bigcup_{i=0}^{d_j/2-1}p^{n-j}D_{(i+b)}^{p^j} \cup \{0\}. \] Using this partition, a family of sequences \(s^{\infty}=(s_0, s_1, s_2,\dots)\) is defined as \[ s_i=\begin{cases} 0, & \text{if}\; i \mod p^n \in \mathcal{C}_0^{p^n}, \\ 1 & \text{if}\; i \mod p^n \in \mathcal{C}_1^{p^n}.\end{cases} \] This sequence is almost balanced since \(|\mathcal{C}_0^{p^n}|=\frac{p^n-1}{2}\) and \(|\mathcal{C}_1^{p^n}|=\frac{p^n+1}{2}\). In this paper, the authors determine the linear complexity of the resulting sequence using a method which is different from the one used in [\textit{Z. Xiao et al}, ibid. 86, 1483--1497 (2018; Zbl 1391.94718)]. This new method enables them to prove the conjecture in [Z. Xiao et al., loc. cit.] and allows them to calculate the linear complexity for more general cases.