Near bent functions in dimension 7

Classification of RM(4,7)/RM(2,7)

This page reports a numerical experiment related to the classification of RM(4,7) modulo RM(2,7). Done on 26th January 2012, the running time for this job was about one day, using 32 giga octets of memory. From this data, one can probably derive the classification of near-bent function in seven variables and the number of bent functions in eight variables.

Definitions

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(k, m) if there exists an affine transformation A in AG(2,m) such that

g = f o A modulo RM(k,m)

Affine group

The affine group has order :

#AG(2, m) = 2^m (2^m-1)(2^m-2)...(2^m-2^(m-1) )

it can be generated by three transformations : the shift S, a transvection T and a nontrivial translation U. The affine group acts over RM(k,m) and also over RM(k,m)/RM(s,m). A formula for the rank n( m, s, t) of the action of AG(2,m) over RM(t,m)/RM(s-1,m) ( 0 <= s <=t ) was determined by Xiang-Dong Hou,

AGL(m, 2) Acting on R(r, m)/R(s, m), journal of algebra 171/3 (1995)

It satisfies : n(m, s, t ) = n(m, m - t , m - s )

Objectives

The main objective of this numerical experiment is to provide the datas corresponding to the classification of RM(4,7)/RM(2,7), by Hou formula, we know there are n(7,3,4) = 68433 classes.

Methodology

We use the method described here but adapting the implantantation.

Starting from the orbit description of classification of RM(3,7)*. So there are n(7,3,3) = 12 classes of degree 3.
We compute the fixator groups class-2-3-7.txt. By the complement map, we obtain the orbit description of forms of degree 4 and the corresponding groups class-3-4-7.txt
For cubics, nothing more to to, there are 12 classes of cubics modulo RM(2,7).
Note that the dimension of cubic form is 35, not too large. We compute the action of the fixator of quartics over the space of cubics, there are 68431 classes.
The computation provides 12 + 68431 = 68433 orbits, that is the effectively the total number of orbits of GA(2,7) acting over RM(4,7)/RM(2,7).
We terminate finding generator sets of the fixators class-2-4-7.txt

Application

The covering radius of RM(2,7) into RM(4,7) is equal to 40. As an example, cde+adf+bdf+bef+bdg+aeg+fg+defg

Philippe Langevin, Last modification January 2012.