# Finding a vector of maximum Hamming distance from a subspace of $(\mathbb{Z}/2\mathbb{Z})^n$

Let $$W$$ be a linear subspace of the vector space $$V = (\mathbb{Z}/2\mathbb{Z})^n$$. Let $$k = \dim(W)$$. For $$v \in V$$, define the distance from $$v$$ to $$W$$ to be $$d(v,W):=\min_{w\in W} d(v,w)$$ where $$d(v,w)$$ is the Hamming distance.

Given such a subspace $$W$$ (more precisely, receiving a basis of $$k$$ vectors as input), how can I find a vector $$v \in V$$ such that $$d(v,W)$$ is as large as possible?

The cases I'm interested in have $$n$$ in the thousands, but $$k$$ being quite small, usually less than 20. I have been able to solve some smaller instances of this problem ($$n$$ being a few hundred, $$k$$ being at most 6 or so) using the SAT/SMT solver Z3 by creating $$n$$ Boolean variables and explicitly writing out $$d(v,w)\geq r$$ for all $$2^k$$ elements of $$W$$ as clauses. The inequality is encoded using a pseudo-boolean constraint (pb-ge in Z3) stating that at least $$r$$ of the $$n$$ literals must be true in each clause. I then use a binary search to find the maximum value of $$r$$ where the formula is satisfiable.

Example: Let $$n = 100$$ and $$W$$ be the subspace spanned by the following three elements (I'll compress the notation a bit and write a vector like $$(a,b,c)$$ as $$abc$$):

1011000001001001000110000000110010000010111011100101010000010101001000000011001000011001110010000000 0100101000001010101011010000000001001000101111100010000010000001011101000001100100010001000100010010 1110010000000000110001011000110001000010011000001000101001001100100110100001010000011000001000110100

Then a solution to the problem is given by the following vector $$v$$:

1101101110110101010011101111011100111101110000010110110111111011101110011101100011101110110001101011

which has Hamming distance at least 64 from every linear combination of the three vectors above. Distance 65 from every linear combination is not possible.

Some additional questions:

• Does this problem have a name?
• Is there a faster (in practise, not necessarily in theory) algorithm than what I am currently doing?
• If so, is there an implementation that I can use?
• @BernardoSubercaseaux I've added an example
– Ben
Jul 20, 2023 at 7:09

## 2 Answers

Your problem is very likely NP-hard. If you don't add the restriction that $$W$$ is sub-space, but just receive a set of boolean vectors $$W$$, then it is NP-hard and known as a Covering Radius proven NP-hard by Frances and Litman. Of course it might be that $$W$$ being a sub-space somehow makes the problem easier, but I can't see a particular way for that to happen.

You may be interested in some linear algebra over finite field $$\mathbb{F}_2$$. Basically, vectors in the linear complement to $$W$$ should have the maximal Hamming distance. The trouble is that linear algebra over finite fields is not as straightforward as over $$\mathbb{C}$$. Nevertheless, linear algebra over $$\mathbb{F}_2$$ has been applied to Hamming codes.

• I am familiar with linear algebra over $\mathbb{F}_2$, that's actually where this problem originated from. Unfortunately your claim that vectors in the complement of $W$ have maximal Hamming distance is wrong. For instance, the zero vector is in both $W$ and the complement, so that gives a vector of distance 0 from $W$. I don't think being in the complement has anything to do with the distance from $W$.
– Ben
Jul 22, 2023 at 20:15