z-logo
open-access-imgOpen Access
Three parameters of Boolean functions related to their constancy on affine spaces
Author(s) -
Claude Carlet,
Serge Feukoua
Publication year - 2019
Publication title -
advances in mathematics of communications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.601
H-Index - 26
eISSN - 1930-5346
pISSN - 1930-5338
DOI - 10.3934/amc.2020036
Subject(s) - mathematics , hyperplane , norm (philosophy) , affine transformation , dimension (graph theory) , combinatorics , discrete mathematics , pure mathematics , political science , law
The \begin{document}$ k $\end{document} -normality of Boolean functions is an important notion initially introduced by Dobbertin and studied in several papers. The parameter related to this notion is the maximal dimension of those affine spaces contained in the support \begin{document}$ supp(f) $\end{document} of the function or in its co-support \begin{document}$ cosupp(f) $\end{document} . We denote it by \begin{document}$ norm\,(f) $\end{document} and call it the norm of \begin{document}$ f $\end{document} . The norm concerns only the affine spaces contained in either the support or the co-support; the information it provides on \begin{document}$ f $\end{document} is then somewhat incomplete (for instance, two functions constant on a hyperplane will have the same very large parameter value, while they can have very different complexities). A second parameter which completes the information given by the first one is the minimum between the maximal dimension of those affine spaces contained in \begin{document}$ supp(f) $\end{document} and the maximal dimension of those contained in \begin{document}$ cosupp(f) $\end{document} (while \begin{document}$ norm\,(f) $\end{document} equals the maximum between these two maximal dimensions). We denote it by \begin{document}$ cons\,(f) $\end{document} and call it the (affine) constancy of \begin{document}$ f $\end{document} . The value of \begin{document}$ cons\,(f) $\end{document} gives global information on \begin{document}$ f $\end{document} , but no information on what happens around each point of \begin{document}$ supp(f) $\end{document} or \begin{document}$ cosupp(f) $\end{document} . We define then its local version, equal to the minimum, when \begin{document}$ a $\end{document} ranges over \begin{document}$ \Bbb{F}_2^n $\end{document} , of the maximal dimension of those affine spaces which contain \begin{document}$ a $\end{document} and on which \begin{document}$ f $\end{document} is constant. We denote it by \begin{document}$ stab\,(f) $\end{document} and call it the stability of \begin{document}$ f $\end{document} . We study the properties of these three parameters. We have \begin{document}$ norm\,(f)\geq cons\,(f)\geq stab\,(f) $\end{document} , then for determining to which extent these three parameters are distinct, we exhibit four infinite classes of Boolean functions, which show that all cases can occur, where each of these two inequalities can be strict or large. We consider the minimal value of \begin{document}$ stab\, (f) $\end{document} (resp. \begin{document}$ cons\,(f) $\end{document} , \begin{document}$ norm\,(f) $\end{document} ), when \begin{document}$ f $\end{document} ranges over the Reed-Muller code \begin{document}$ RM(r,n) $\end{document} of length \begin{document}$ 2^n $\end{document} and order \begin{document}$ r $\end{document} , and we denote it by \begin{document}$ stab\, _{RM(r,n)} $\end{document} (resp. \begin{document}$ cons\, _{RM(r,n)} $\end{document} , \begin{document}$ norm\, _{RM(r,n)} $\end{document} ). We give upper bounds for each of these three integer sequences, and determine the exact values of \begin{document}$ stab\, _{RM(r,n)} $\end{document} and \begin{document}$ cons\, _{RM(r,n)} $\end{document} for \begin{document}$ r\in\{1,2,n-2,n-1,n\} $\end{document} , and of \begin{document}$ norm\, _{RM(r,n)} $\end{document} for \begin{document}$ r = 1,2 $\end{document} .

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom