• PDF
• Cite
• Share
Article Contents  Article Contents

# Three parameters of Boolean functions related to their constancy on affine spaces

* The work of this author was partially supported by PRMAIS

• The $k$-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 $supp(f)$ of the function or in its co-support $cosupp(f)$. We denote it by $norm\,(f)$ and call it the norm of $f$.

The norm concerns only the affine spaces contained in either the support or the co-support; the information it provides on $f$ 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 $supp(f)$ and the maximal dimension of those contained in $cosupp(f)$ (while $norm\,(f)$ equals the maximum between these two maximal dimensions). We denote it by $cons\,(f)$ and call it the (affine) constancy of $f$.

The value of $cons\,(f)$ gives global information on $f$, but no information on what happens around each point of $supp(f)$ or $cosupp(f)$. We define then its local version, equal to the minimum, when $a$ ranges over $\Bbb{F}_2^n$, of the maximal dimension of those affine spaces which contain $a$ and on which $f$ is constant. We denote it by $stab\,(f)$ and call it the stability of $f$.

We study the properties of these three parameters. We have $norm\,(f)\geq cons\,(f)\geq stab\,(f)$, 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 $stab\, (f)$ (resp. $cons\,(f)$, $norm\,(f)$), when $f$ ranges over the Reed-Muller code $RM(r,n)$ of length $2^n$ and order $r$, and we denote it by $stab\, _{RM(r,n)}$ (resp. $cons\, _{RM(r,n)}$, $norm\, _{RM(r,n)}$). We give upper bounds for each of these three integer sequences, and determine the exact values of $stab\, _{RM(r,n)}$ and $cons\, _{RM(r,n)}$ for $r\in\{1,2,n-2,n-1,n\}$, and of $norm\, _{RM(r,n)}$ for $r = 1,2$.

Mathematics Subject Classification: 06E30, 94C10, 94A60, 11T71, 05E99.

 Citation: • • ## Article Metrics  DownLoad:  Full-Size Img  PowerPoint