Binary Basis Classification

Classification of full-rank N-element subsets of complement pairs in the N-dimensional Boolean hypercube, under coordinate permutation and complement symmetry.

Problem

Fix $N \geq 1$. Let $V = {0,1}^N$ be the vertices of the N-dimensional Boolean hypercube. A complement pair is a set ${v, \bar{v}}$ where $\bar{v}$ is the bitwise negation of $v$. We exclude the trivial pair ${\mathbf{0}, \mathbf{1}}$, leaving $2^{N-1} - 1$ non-trivial complement pairs.

A subset of exactly $N$ complement pairs is full-rank if there exists at least one way to choose one representative vector from each pair such that the resulting $N \times N$ matrix has non-zero determinant over $\mathbb{R}$.

The symmetric group $S_N$ acts on these subsets by permuting the $N$ coordinate axes. $f(N)$ is the number of distinct orbits (equivalence classes) under this action.

Known Values (OEIS sequence, offset 1)

N	f(N)
1	0
2	0
3	1
4	5
5	45
6	1,270
7	107,387
8	29,903,617

Quick Start

# Compile and run the fast C++ enumerator (recommended for N ≥ 5)
g++ -O3 -std=c++17 -fopenmp -o count_bases code/cpp/count_bases.cpp
./count_bases 8          # computes f(2) through f(8)
./count_bases 8 7        # computes only f(7) and f(8)

# Compile and run the Burnside verifier
g++ -O3 -std=c++17 -o burnside_fast code/cpp/burnside_fast.cpp
./burnside_fast 8

# Run the Python reference implementation (correct but slow; N ≤ 5 only)
python code/python/brute_force.py

# Run Burnside experiments in Python (N ≤ 6, verbose Fix tables)
python code/python/burnside.py

# Run correctness tests
python tests/test_correctness.py