Fast discrete Fourier transform on local fields of zero characteristic (Q2303903)

A local field is locally compact, non-discrete, totally disconnected complete topological space with continuous operations of addition \((\dot{+})\) and multiplication \((\cdot)\), which satisfy the field axioms. The local field \(K\) of zero characteristic is a finite extension of the degree \(n=se\) of the field \(\mathbb{Q}_p\) of \(p\)-adic numbers, where \(p\) is a prime number and depends on two parameters \(s, e\in\mathbb{N}\). The Rademacher function is defined as the character \(r_m\in G^{\bot}_{m+1} \backslash G^{\bot}_{m}\) in a zero-dimensional group \(G\) with a basic chain of subgroups \((G_m)\). Let \(\overline{\alpha}_m=(\alpha_{m,0}, \alpha_{m,1},\ldots, \alpha_{m,s-1})\in GF(p^s)\). Then the generalized Walsh functions are defined as \(\mathbf{r}_m^{\overline{\alpha}_m}:=r_{ms+0}^{\alpha_{m,0}} r_{ms+1}^{\alpha_{m,1}} \ldots r_{ms+s-1}^{\alpha_{m,s-1}}\), where \(r_{ms+j}, \ 0\le j< s, m\in\mathbb{Z}\) are Rademacher functions. Here, \(\mathfrak{D}_{K_{(N)}}(K_{(-M)})\) denotes the set of functions \(f\in L_2(K)\) such that (i) supp \(f\subset K_{(-M)}\), and (ii) \(f\) is constant on cosets \(K_{(N)}\dot{+} g\) holds. Each function \(f^{(N+1)}\in \mathfrak{D}_{K_{(N+1)}}(K_{(0)})\) can be represented by a finite sum \(f^{(N+1)}=\sum\limits_{\overline{\alpha}_0,\ldots,\overline{\alpha}_N \in GF(p^s)}c_{\overline{\alpha}_0\ldots\overline{\alpha}_N}\mathbf{r}^{\overline{\alpha}_0}_0\ldots \mathbf{r}^{\overline{\alpha}_N}_N\). In this paper, the authors obtain the explicit form of Rademacher functions in the field \(K\) and describe a representation of the characters of the field \(K\) in terms of Rademacher functions. They obtain a fast algorithm for calculating the coefficients \(c_{\overline{\alpha}_0\ldots\overline{\alpha}_N}\) and thus give the calculation formulas for the inverse and direct Fourier transforms in the field \(K\). The total number of operations required to complete the algorithm is found to be \((s+1)p^s \frac{N^2}{e}p^{s(N+1)}\) which gives the complexity of both direct and inverse transforms as \(M \log^2 M\) which can be further reduced to \(M \log M\).