Classification of Partial Spread Functions in eight Variables

This page reports the numerical experiments related to the classification of the Partial Spread Boolean Functions in eight variables that I computed in 2008-2009. This work shows there are

70576747237594114392064 = approx = 2^{75.9}
bent functions in the PS classes of Dillon. The reader will find some details in the preprint .

## Definitions and objectives

Let m = 2t be an even integer. A partial spread of order n is a subset of n subspaces of dimension t in GF(2)^m. The linear group GL(2,m) acts naturally over partial spreads. If f_1, f_2, ..., f_n denote the indicator functions of the subspaces defining a partial spread, the Boolean function f_1 + f_2 + ... + f_n (mod 2) is called a partial spread function. When n = 2^t or n = 2^t+1, these functions are bent. According to Dillon's terminology, they form respectively the PS- and PS+ classes of bent functions. The main purpose of the numerical experiment is to count the number of bent functions in these classes for m = 8.

## Methodology

We proceed by induction, buiding a set of representatives of partial spread functions of order (n+1) from a set of representative of partial spread functions of order n.
• Extension.
• Pre-classification. We apply invariant of forms of degree four to split the collection of partial spread functions in 966 lists of partial spread functions.
• Classification.
• Stabilization.

## Running times

```
extension          classification                    stabilization
n    time    size    time    time   class    time                      psf
4       1       5       1       0       3       1        64374841666437120
5      15     233      55      10      22      10     20267057123180937216
6      69    4893    1162     385     341       6   1339989812392369324032
7     415   29691    7038    7246    3726      62  17833337132662061531136
8    1076   60943   14449   33501    9316     229  46056096661467073413120
9     681   31715    7516    8594    5442   19529  24520650576127040978944
10     219    8871    2109     698    1336      23   4731497045822911021056
11      75    2759     654     148     303       6    713809537614313684992
12      20     675     160      30      42      10     38019657690425327616
13       3      96      23       4       6       2       129740065512357888
14       0      11       3       0       1      59           44213490155520
15       0       3       1       0       1   11186               6579388416
16       0       2       0       0       1       0                   200787
17       0       1       0       0       1       0                        1
```

## file of representatives

For each n, the file psf-n.txt contains the representatives of partial spread functions of order n. The datas are presented as follow :
```psf = (identifier) : (n-3) 16-bits numbers
fix = (order of the fixator group).
anf = (algebraic form)
rnk = private
spec= (spectrum)
```
All the partial spreads of order n that we computed are extensions of the standard partial spread of order 3 : [ I: 0 ] [ 0 : I] [ I : I ]. The information on line psf= describes the generator matrices [ I : A ] of the other subspaces. A 16-bits number (A3 A2 A1 A0) represents a 4x4 matrix whose the rows are A0, A1, A2, A3.
 psf-3.txt psf-4.txt psf-5.txt psf-6.txt psf-7.txt psf-8.txt psf-9.txt psf-10.txt psf-11.txt psf-12.txt psf-13.txt psf-14.txt psf-15.txt psf-16.txt psf-17.txt

## Distribution of fixator sizes

 fix-3.txt fix-4.txt fix-5.txt fix-6.txt fix-7.txt fix-8.txt fix-9.txt fix-10.txt fix-11.txt fix-12.txt fix-13.txt fix-14.txt fix-15.txt fix-16.txt fix-17.txt

## Partial spread of low degree

The degree of a partial spread function is less or equal to 4. It is interesting to notice there are 2 ( and only 2 ! ) classes of n-spread with degree less than 4 ( n < 15 ). They ly both in the PS+ class. One is a cubic :
```psf-9.txt:rnk=999
psf-9.txt-fix=1008
psf-9.txt-anf=+25+135+45+345+126+36+136+46+246+346+27+127+137+47+147+247+347+18+28+38+138+348+358+268+368+278+378+478
psf-9.txt-spec= 136 [-16], 120 [16]
```
and the other one is quadratic :
```psf-9.txt-psf=5442 :  8137 27484 30180 33825 39544 57749 65213
psf-9.txt:rnk=999
psf-9.txt-fix=348364800
psf-9.txt-anf=+25+16+36+46+27+47+28+38
psf-9.txt-spec= 136 [-16], 120 [16],
```

## Conclusion

We know that the number of bent functions is 2^{97.3}. This computation shows that most of the bent functions do not ly in one of the known classes : partial spread of Dillon or Maiorana-Mcfarland.
Philippe Langevin, Last modification on April 4th 2010.