Highly nonlinear functions (Q2260795): Difference between revisions

For a function \(f\) from \(\mathbb{Z}_q^m\) to \(\mathbb{Z}_q\), the function \(\widehat{f}:\mathbb{Z}_q^m\rightarrow\mathbb{C}\) is defined by \[ \widehat{f}(\lambda) = \frac{1}{q^{m/2}}\sum_{x\in\mathbb{Z}_q^m}\omega^{f(x)-\lambda \cdot x},\quad \omega = e^{2\pi i/q}, \] which can be seen as a generalization of the conventional Walsh transform for Boolean functions. By Parseval's identity, \(\max_{\lambda\in\mathbb{Z}_q^m}|\widehat{f}(\lambda)|\geq 1\), functions for which equality holds are called bent functions in accordance with [\textit{P. V. Kumar} et al., J. Comb. Theory, Ser. A 40, 90--107 (1985; Zbl 0585.94016)]. Bent functions are known to exist for all pairs \((q,m)\) except when \(m\) is odd and \(q\equiv 2\mod 4\), and there is overwhelming evidence that no bent function exists in the latter case. Define \(\mu(q,m) := \min_f\max_{\lambda\in\mathbb {Z}_q^m}|\widehat{f}(\lambda)|\), where the minimum is over all functions from \(\mathbb{Z}_q^m\) to \(\mathbb{Z}_q\). Then, \(1\leq \mu(q,m)\leq \sqrt{q}\) and equality at the left inequality holds if bent functions from \(\mathbb{Z}_q^m\) to \(\mathbb{Z}_q\) exist. As a very interesting main result, the author shows that \[ \mu(q,m) < \cos\frac{\pi}{q} + 15\sin\frac{\pi}{q} \] for all sufficiently large \(q^m\). In particular, \(\lim_{q\rightarrow\infty}\mu(q,m) = 1\). Remark: In some literature, a bent function between abelian groups \(G\), \(H\) is defined as a function \(f: G\to H\) such that for \textit{all} characters of \(G\times H\) which are nonprincipal on \(H\) the character sum over the graph of \(f\) has constant magnitude \(|G|\), see, e.g., [\textit{L. Poinsot}, Cryptogr. Commun. 4, No. 1, 1--23 (2012; Zbl 1282.11165)]. Then, a bent function corresponds to a relative difference set in \(G\times H\).