indice, relative degree and normality of Boolean function

We report the numerical experiments related to the degree of restriction of Boolean function on affine subspace

normality

Let m be a positive integer a Boolean function f in B(m) is said to be normal if it is constant on some affine subspace V of dimension [(m+1)/2]. 

 
Normal Boolean functions
Pascale Charpin
Journal of Complexity 20 (2004) 245–265

And it is said r-normal if it is constant on some affine subspace V of dimension r.

Let m be a positive integer a Boolean function f in B(m) is said to be weakly normal if it is affine on some affine subspace V of dimension [(m+1)/2].

relative degree

For an affine subspace A := t + V of dimension r, we consider the restriction of f to A. It is the Boolean function g on V defined by :
g( v ) = f( t + v )
The degree of g, is the degree of f relatively to A, and we propose to denote it by deg_A( f ).
deg_r( f ) = min_{ dim(A) = r } deg_A( f ).

We want to explore the numbers :
D( r, k, m) = max_{ deg(f) <= k } deg_r( f )
In her thesis, Sylvie Dubuc proved that all Boolean function in 6 or 7 variables are 3-normal, in term of relative degree :
D(3, 6, 6 ) = D( 3, 7, 7) = 0.

5-bits function


>
relative degree in dimension 5 :

 4 :   -    0    2    2    3    2
 3 :   -    0    1    1    1    1
 2 :   -    0    0    0    0    0

6-bits function


relative degree in dimension 6
 5 :   -    0    2    3    4    3    4
 4 :   -    0    2    2    2    2    2
 3 :   -    0    0    0    0    0    0
 2 :   -    0    0    0    0    0    0

7-bits function



relative degree in dimension 7
                           ----   random   ----                   
 6 :   -    0    2    3    4?    4?    5?   4? 
 5 :   -    0    2    3    3?    3?    3?   3? 
 4 :   -    0    1    1    1?    1?    1?   1? 
 3 :   -    0    0    0    0     0     0     0

8-bits function


Work i progress...
Valérie Gillot, Philippe Langevin, imath,
last modification : spring 2024.