1
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ A related question would be, given your set $S$, find an affine subspace of maximal size contained in $S$. I wonder whether this question is computationally feasible. $\endgroup$ Aug 4, 2016 at 23:02

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.