Quadratic functions with prescribed spectra (Q1934217): Difference between revisions

Let \(p\) be a prime and let \(f: \mathbb F_{p^n}\to \mathbb F_p\) be a quadratic function. The Walsh transform at \(b\in\mathbb F_{p^n}\) is: \[ \hat f(b)=\sum_{x\in\mathbb F_{p^n}} \varepsilon_p^{f(x)-\text{Tr}(bx)}, \] where \(\varepsilon_p=e^{2\pi i/p}\). It is well-known that \(f\) is \(s\)-plateaued, for some \(0\leq s\leq n-1\), meaning that all \(|\hat f(b)|^2\) lie in \(\{ 0, p^{n+s}\}\). Every quadratic function can be written as a trace form. The authors consider the special class of trace forms where the coefficients are in the base field: \[ \mathcal F_{p,n}(x)=\text{Tr}\left(\sum_{i=0}^k a_ix^{p^i+1}\right), \quad a_i\in\mathbb F_p. \] They consider four problems: -- Given \(s\), determine \(n\) such that all \(\mathcal F_{p,n}\) are \(s\)-plateaued. -- Given \(n\), find possible \(s\) with some \(\mathcal F_{p,n}\) \(s\)-plateaued. -- Given \(n\) and an \(s\) known to give rise to an \(s\)-plateaued \(\mathcal F_{p,n}\), construct an \(s\)-plateaued \(\mathcal F_{p,n}\). -- Given \(n\), for any \(s\), enumerate all \(s\)-plateaued \(\mathcal F_{p,n}\). Numerous partial results are known for all four problems. The authors unify these and extend them to arbitrary characteristic. To be specific, they completely answer (1) and (2). Problem (3) is solved for all \(s\) and all odd \(n\) prime to \(p\). They solve (4) for \(p=2\) and \(n=2^m\), \(m\geq 2\) as well as for odd \(p\) and \(n=q^m\), where \(q\) is an odd prime for which \(p\) is a primitive root modulo \(q^2\). The major tools used are: self-reciprocal factors of cyclotomic polynomials and two algorithms for computing linear complexity, one due to \textit{R. A. Games} and \textit{A. H. Chan} [IEEE Trans. Inf. Theory 29, 144--146 (1983; Zbl 0498.68034)] and the other due to \textit{G. Xiao, S. Wei, K.Y. Lam} and \textit{K. Imamura} [IEEE Trans. Inf. Theory 46, 2203--2206 (2000; Zbl 0997.94013)].