Finding a set of disjoint affine subspaces such that their union is equal to a given subset of $\mathbb{F}_2^n$

Question

Suppose I'm given a set of point $S = \{x_1, \dots, x_m \} \subseteq \mathbb{F}_2^n$, and the following task. Find a set of disjoint affine subspaces of $\mathbb{F}_2^n$, $A_1, \dots, A_k$ satisfying $S = A_1 \cup A_2 \cup \dots \cup A_k $. Additionally, find such a set with minimal $k$.

Obviously one brute approach is to note that any two points of $\mathbb{F}_2^n$ form an affine subspace, so we can write $S = \{x_1, x_2\} \cup \dots \cup \{x_{m-1}, x_m \}$ if m is even (and the same thing with a singleton set at the end if m is odd). This has $k= \text{ceiling}(\frac{m}{2})$.

I'm interested to know whether this is a known problem in finite geometry, and if so some suggestions for references to it or to related problems.

Thanks in advance!

Answer 1

I expect this would be a difficult problem. It is connected to XOR-SAT problems in computer science.

An affine subspace of $\mathbb F_2^n$ corresponds in boolean logic to the solutions of a conjunction of XOR clauses $(t_1 \oplus \ldots \oplus t_j)$ where each $t_i$ is a variable or "true". Such a conjunction of clauses is easy to check membership, to solve, or to count solutions (by linear algebra over $\mathbb F_2$). You want to break up your set $S$ into a disjoint union of $k$ of these easy problems, thus (if $k$ is polynomial in $n$) making checking membership in $S$, finding a member of $S$, or counting the members of $S$ all easy problems.