# Complexity of deciding whether subspaces of Z_2^n cover every point 3*x times

When studying the complexity of checking identities in certain finite algebras, I came across the following decision problem:

Input: A positive integer $$n \in N$$ and a set of affine subspaces $$H_1,H_2,\ldots,H_k$$ of $$\mathbb Z_2^n$$ (where $$\mathbb Z_2$$ is the 2-element field).

Question: For every $$x \in \mathbb Z_2^n$$, let $$n(x) = |\{H_i:x\in H_i \}|$$. Is $$n(x)$$ a multiple of 3 for all $$x$$? Or, in other words, is every point of $$\mathbb Z_2^n$$ covered by $$0$$ modulo $$3$$ many of the affine subspaces?

Note that there are no conditions on $$n$$, $$k$$ and the dimension of the affine subspaces $$H_i$$.

The problem is clearly in coNP, but unfortunately I am not able to prove anything more about its complexity. My hope is for it to be coNP-complete, since this would have nice implications for our research. But also if it was in P or equivalent to some coNP-intermediate problem this would be a really interesting fact to know.

Two observations:

• If we additionally assume that the codimension of all input subspaces $$H_i$$ is bounded by a constant (e.g. if every $$H_i$$ is a hyperplane) then the problem is in P. Thus any encoding of a coNP-complete problem would require using subspaces of arbitrary codimension.
• I tried to encode the complement of some classical NP-complete problems, but did not succeed. In particular 'covering problems' like the Set cover problem seemed to be a natural choice. But that we count here 'modulo 3' seemed to be an obstacle in this approach.

Thanks for every hint! :) In particular references to possibly related problems in the literature would be very welcome!

• Note, this question is equivalent to determining that a given MOD3-AND-MOD2 circuit is a tautology (all assignments are satisfying ones). So e.g. the comment about codimension can be seen as each AND having constant fan-in; in that case each AND can be written as a short mod3 sum of MOD2s, and the circuit just becomes a multilinear polynomial over F3 (where satisfiabilty is very easy). – Ryan Williams Sep 26 '18 at 14:24
• @RyanWilliams: Thanks, this seems to be a helpful different point of view! Also there is plenty of literature on such circuits. I will update my post, if I find anything useful – user50712 Oct 1 '18 at 8:16