<p>Here's a quasi-polynomial-time algorithm, which doesn't fully answer the question but may give ideas and shows that the problem is unlikely to be NP-hard. This is for the variant where <span class="math-container">$d$</span> is given as part of the input, or the variant where <span class="math-container">$d$</span> is not given but must be the same for all subspaces used.</p>
<p><strong>Theorem 1.</strong> <em>For some constant <span class="math-container">$c&gt;0$</span> there is an <span class="math-container">$O(n^c m^{c+\log_2 m})$</span>-time algorithm for the problem.</em></p>
<p><em>Proof.</em> First consider the problem variant where each input instance specifies <span class="math-container">$P=\{x_1, \ldots, x_m\}$</span> and <span class="math-container">$d$</span>.  For brevity, let <em><span class="math-container">$d$</span>-space</em> by a synonym for <em><span class="math-container">$d$</span>-dimensional linear subspace.</em></p>
<ol>
<li><p>In the case that <span class="math-container">$m=0$</span> (that is, <span class="math-container">$P$</span> is empty), the answer is yes (it is the union of zero <span class="math-container">$d$</span>-spaces).</p>
</li>
<li><p>In the case that <span class="math-container">$1\le m &lt; 2^d$</span>, the answer is no (because each <span class="math-container">$d$</span>-space contains <span class="math-container">$2^d$</span> points).</p>
</li>
<li><p>So assume WLOG that <span class="math-container">$m \ge 2^d$</span>.  Let <span class="math-container">$S$</span> contain the <span class="math-container">$d$</span>-spaces that are subsets of <span class="math-container">$P$</span>.  If the union of the subspaces in <span class="math-container">$S$</span> equals <span class="math-container">$P$</span>, then the answer is yes (using the sets in <span class="math-container">$S$</span>).  Otherwise the answer is no (as these subsets do not suffice, but no other subsets can be used).</p>
</li>
</ol>
<p>More specifically, to implement Step 3 in the desired time bound, note that each <span class="math-container">$d$</span>-space is the span of some <span class="math-container">$d$</span> vectors in <span class="math-container">$P$</span>, so there are at most <span class="math-container">$\binom m d &lt; m^d \le m^d$</span> such spaces, and they can be enumerated in time <span class="math-container">$n^{O(1)} m^d$</span>.  Each has size <span class="math-container">$2^d \le m$</span>.  Given that <span class="math-container">$d \le \log_2 m$</span>, it follows that Step 3 can be done in the claimed time bound.</p>
<p>For the variant where <span class="math-container">$d$</span> is not given, note that (assuming <span class="math-container">$P$</span> is not empty, and using the reasoning in Step 2 above) any solution must have <span class="math-container">$d\le \log_2 m$</span>, so one can try each <span class="math-container">$d\le \log_2 m$</span> using the algorithm above, increasing the running time by an <span class="math-container">$O(\log m)$</span> factor.<span class="math-container">$~~~\Box$</span></p>
<p>To speed up the algorithm (maybe achieve polynomial time) it might help to solve the following subproblem faster: <em>given <span class="math-container">$P$</span> and <span class="math-container">$d$</span>, find some <span class="math-container">$d$</span>-space (if there is one) contained in <span class="math-container">$P$</span>.</em></p>

CC BY-SA 4.0
2022-02-25T06:10:10.223Z
Thanks, good idea to just look for bases of the spaces. I'm thinking mostly of the case $m\approx 2^{n-1}$.
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2022-02-24T23:14:02.077Z
2022-02-24T23:14:02.077Z
Neal Young
<p>Given some points <span class="math-container">$P=\{x_1,\dots,x_m\}$</span> in a vector space <span class="math-container">$(Z/2Z)^n$</span>, if <span class="math-container">$P$</span> is a union of linear subspaces all of the same dimension <span class="math-container">$1&lt;d&lt;n$</span>, can we efficiently find these subspaces?</p>
<p>(Any literature on this type of problem?)</p>

CC BY-SA 4.0
2022-02-24T14:03:55.340Z
The related problem where you want to cover points in the Euclidean plane by a small number of lines is NP-complete; see for instance https://link.springer.com/article/10.1007/s00454-004-1108-4
Gamow
CC BY-SA 4.0
2022-02-24T21:46:51.940Z
Is $d$ given as part of the instance, or can the solution use any $d\in [2, n-1]$?
Neal Young
CC BY-SA 4.0
2022-02-24T22:09:20.430Z
@NealYoung Either way is of interest to me... also if the subspaces are not all of the same dimension but the dimensions are restricted to a  certain interval.
Bjørn Kjos-Hanssen
<cc.complexity-theory><computational-geometry>
Finding planes from their points
Bjørn Kjos-Hanssen
# Finding planes from their points

(Asked by: username_0 on 2022-02-24)

Given some points $P=\{x\_1,\dots,x\_m\}$ in a vector space $(Z/2Z)^n$, if $P$ is a union of linear subspaces all of the same dimension $1, can we efficiently find these subspaces?

(Any literature on this type of problem?)

**Tags:** cc.complexity-theory, computational-geometry

> **Comments:**
> **username_1**: The related problem where you want to cover points in the Euclidean plane by a small number of lines is NP-complete; see for instance https://link.springer.com/article/10.1007/s00454-004-1108-4  
> **username_2**: Is $d$ given as part of the instance, or can the solution use any $d\in [2, n-1]$?  
> **username_0**: @NealYoung Either way is of interest to me... also if the subspaces are not all of the same dimension but the dimensions are restricted to a  certain interval.  

---

## 1 answers

### Answer by username_2 on 2022-02-24. Score: 4 | Accepted answer

Here's a quasi-polynomial-time algorithm, which doesn't fully answer the question but may give ideas and shows that the problem is unlikely to be NP-hard. This is for the variant where $d$ is given as part of the input, or the variant where $d$ is not given but must be the same for all subspaces used.

**Theorem 1.** *For some constant $c>0$ there is an $O(n^c m^{c+\log\_2 m})$-time algorithm for the problem.*

*Proof.* First consider the problem variant where each input instance specifies $P=\{x\_1, \ldots, x\_m\}$ and $d$. For brevity, let *$d$-space* by a synonym for *$d$-dimensional linear subspace.*

1. In the case that $m=0$ (that is, $P$ is empty), the answer is yes (it is the union of zero $d$-spaces).
2. In the case that $1\le m < 2^d$, the answer is no (because each $d$-space contains $2^d$ points).
3. So assume WLOG that $m \ge 2^d$. Let $S$ contain the $d$-spaces that are subsets of $P$. If the union of the subspaces in $S$ equals $P$, then the answer is yes (using the sets in $S$). Otherwise the answer is no (as these subsets do not suffice, but no other subsets can be used).

More specifically, to implement Step 3 in the desired time bound, note that each $d$-space is the span of some $d$ vectors in $P$, so there are at most $\binom m d < m^d \le m^d$ such spaces, and they can be enumerated in time $n^{O(1)} m^d$. Each has size $2^d \le m$. Given that $d \le \log\_2 m$, it follows that Step 3 can be done in the claimed time bound.

For the variant where $d$ is not given, note that (assuming $P$ is not empty, and using the reasoning in Step 2 above) any solution must have $d\le \log\_2 m$, so one can try each $d\le \log\_2 m$ using the algorithm above, increasing the running time by an $O(\log m)$ factor.$~~~\Box$

To speed up the algorithm (maybe achieve polynomial time) it might help to solve the following subproblem faster: *given $P$ and $d$, find some $d$-space (if there is one) contained in $P$.*

> **Comments:**
> **username_0**: Thanks, good idea to just look for bases of the spaces. I'm thinking mostly of the case $m\approx 2^{n-1}$.  

---

