Nonlinearity of some invariant Boolean functions (Q2487212): Difference between revisions

One of the hardest problems in coding theory is to evaluate the covering radius of first order Reed-Muller codes \(\text{RM}(1,m)\), and more recently the balanced covering radius for cryptographic purposes. The aim of this paper is to present some new results on this subject. Here Boolean functions invariant under the action of some finite groups have been studied, following the idea of \textit{N. J. Patterson} and \textit{D. H. Wiedemann} [IEEE Trans. Inf. Theory 29, 354--356 (1983; Zbl 0505.94021)]. That idea, already exploited by \textit{J. Constantin}, \textit{B. Courtean} and \textit{J. Wolfmann} in [Algebraic algorithms and error-correcting codes, Proc. 3rd Int. Conf., Grenoble/France 1985, Lect. Notes Comput. Sci. 229, 69--75 (1986; Zbl 0601.94009)] has been translated here in the language of Fourier transforms; it is generalized also to various groups \(G\) admitting linear representations over \(\mathbb F_2\). The following subjects are then connected in the paper: Boolean functions, first-order Reed-Muller-codes, Fourier transforms, bounds, invariant Boolean functions algorithmic considerations, Gray code, Hamiltonian path, numerical experiments, symmetric groups.