Bent functions skip the truth-table search: evolving subspace families finds 285 low-degree 8-variable functions
Synopsis
For partial-spread bent functions, the search object moves from the truth table to the underlying family of subspaces, repaired by an operator that removes conflicting members and rebuilds them exactly. At 8 variables, the spread-set encoding with that operator reaches 100% and 74% success on the two targets, while the subspace encoding and the spread-set encoding without the operator find no solution; on the same encoding a look-ahead greedy heuristic succeeds more often on the hardest target.
Interpretation
Bent functions, the Boolean functions farthest from linear ones, can be sought through the partial spread that supports them, a family of subspaces that pairwise meet only in the zero vector, instead of through the truth table. Earlier evolutionary searches over truth tables or syntax trees behaved differently: truth-table-based evolution strategies and genetic algorithms never found bent functions within the given fitness budget, while symbolic genetic programming did so reliably. At 8 variables both encodings converge in all runs; at 10 variables only the spread-set encoding with ruin-and-rebuild succeeds, at 100% and 74% on the two targets, while every other configuration finds no partial spread within 1800 seconds.
Each subspace is written as the graph of a linear map alongside two fixed subspaces, so two subspaces meet only in the zero vector exactly when the difference of their matrices is invertible. A direct adaptation of the evolution strategy for binary linear codes to families of generator matrices already fails at 8 variables. The ruin-and-rebuild operator builds a new matrix column by column and backtracks as soon as a column makes a difference matrix linearly dependent, so it either inserts exactly or proves none exists; successful runs on the 10-variable target take a median of 241 evaluations.
With algebraic degree added as a second objective, a quality-diversity variant based on MAP-Elites finds 8-variable functions of degree below 4 more reliably than the lexicographic variant. The lexicographic approach keeps only the best degree value, and all its failed runs end at degree 4, a dead end. Within 300 seconds, the quality-diversity evolution strategies reach degree below 4 in 90 and 84 of 100 runs, against 47 and 35 for the lexicographic ones and 27 for the look-ahead greedy; 285 distinct functions result, 278 of degree 3 and 7 of degree 2.
Perspective
The experiments cover both partial-spread targets at 8 and 10 variables plus a 12-variable limit instance; each configuration uses 100 independent runs, and greedy baselines are compared under matched wall-clock time. At 12 variables both methods ran 16 times for 24 hours without finding a partial spread, and the look-ahead greedy stopped at 23 subspaces every time.
On the 10-variable target the evolution strategy succeeds in 74% of runs, and failed runs end with a median of 2 conflicting subspace pairs; on the hardest instance the restarted look-ahead greedy beats every evolution-strategy variant, and greedy initialization does not close the gap. At 12 variables the look-ahead greedy stops at 23 subspaces across about 3770 attempts per run, and some failed insertions of the evolution strategy are cut off by the node budget.
