partial spread functions

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.

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.