4
$\begingroup$

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?
$\endgroup$
1
  • $\begingroup$ @BernardoSubercaseaux I've added an example $\endgroup$
    – Ben
    Jul 20, 2023 at 7:09

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – Ben
    Jul 22, 2023 at 20:15

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.