Classification of Bent Cubics in 8 variables

It is well known there are only 4 affine classes of bent functions in 6 variables. As pointed to us by Xiang-Dong Hou the number of bent cubics in 8 variables is known ( 5386705781653504 x 512 ) but not the number of classes. The objective of the project is to fill this gap.

Affine classes

Let m be a positive integer. The space of boolean functions from GF(2,m) into GF(2) is denoted by RM(k,m). This notation comes from coding theory, it is the Reed-Muller code of order k in m variables. The affine group AG(2, m) acts over the spaces RM(k,m), and thus on RM(k,m)/RM(s,m) when s<=k. Two Boolean functions f and g are said to be equivalent modulo RM(s, m) if there exists an affine transformation A in AG(2,m) such that

g = f o A modulo RM(s,m)
Xiang-Dong Hou gave a formula for the rank n( m, k, s) of the action of AG(2,m) over RM(k,m)/RM(s,m) in the paper :
AGL(m, 2) Acting on R(r, m)/R(s, m)
journal of algebra 171/3 (1995)

Bent function

Let f be a boolean function. Recall that f is a bent function when all its Walsh Fourier coefficient have the same magnitude. The Walsh coefficient at a point y of GF(2,m)

f*( y ) = sum_{x in GF(2,m)} (-1)^( f(x) + y.x )
One can check that if f is bent then f o A + l is bent for all affine transformation A and all affine boolean function l. Two cubics g and f on RM(3,8) are equivalent if there exists a pair (A,l) such that :
g = f o A + l
The objective of the project is to compute the number of classes of bent cubics in 8 variables.

Classification of RM(3,8)*

We start from the partial classification of the GL-action on RM(3,8)*. From this data, computed the first time by Xiang Dong Hou (1996), we deduce the complete classification by a random approah. 
input   
   f    :  form of degree 3
   N    :  orbit size of  f
output  
   G    : fixator of f

   hash := hashtable with 2^30 entries
   goal := #GL(2,8) / N
   G := { 1 }
   while ( #G < goal ) 
      begin
         A := at random in AG( 2, 8 )
         g := f o A
         if  collision at g  
             then
               B := hash[ g ]
               G := < G, A/B >
             else
               hash[ g ] = A 
         fi 
      end 
  return G
The running time depends on the order of the fixator : 
cardinality      time sec
----------------------------------------
192              5490.43      91 minutes
336              3161.40
432              5481.38
768              4529.87
2304             2412.72
3072             1289.77
3072             2158.04
3072             3454.79
10752            1134.07
18432             631.41
24576             849.16
46080             691.06
49152             880.67
82944             370.08
96768             242.83
294912            203.39
393216            133.73
1179648            96.90
1474560            42.01
1548288            62.53
1935360            46.87
2359296            90.66
9437184            31.39
47185920           18.83
88080384           11.91
1056964608          3.67
1387266048          3.91
2972712960          3.12
11890851840         0.96
63417876480         1.04
55046716784640      0.48
5348063769211699200 0.41

Classification of RM(3,8)/RM(1,8)


We say that a homogeneous form fq such that f + q is bent. The ANF a_u of a bentable cubic form satisfies the quadratic equations: 
      For all subset W of {1,2,...,8}, with #W  >=6
      0 = sum_{ u U v = W } a_u a_v

With knowledge of the fixator group it is easy to determine the GL-class of bent cubics modulo affine terms. The fixator group of a cubic form f acts over the quadratic forms by q --> q^A + f_A where f_A is the boundary f^A + f.
Applying plain vanilla with this group action one gets :
[ 11 GL-class of bent functions ] 
real	12m21.386s
user	12m17.661s
sys	0m3.648s

The same can be done with the affine group
[ 9 AG-class of bent functions ] 
real	15m32.983s
user	15m26.343s
sys	0m6.557s

Philippe Langevin Last modification june 2013.