5
$\begingroup$

Let $A \subset \{0,1\}^n$ be a set of $n$-bit bit vectors. Let me call a bit vector $b = (b^{(1)}, b^{(2)}, \dotsc, b^{(n)}) \in \{0,1\}^n$ a "bit combination" of the vectors in $A$ if: $$\forall i \in \{1, 2, \dotsc, n\}\ \exists a_i \in A: b^{(i)} = a_i^{(i)}.$$

That is, $b$ is a "bit combination" of the bit vectors in $A$ if and only if each bit of $b$ matches the corresponding bit of at least one bit vector in $A$.

Is there an accepted name for such a bit vector $b$, or for the set $B_A \subset \{0,1\}^n$ of all such bit vectors?

Geometrically, identifying $\{0,1\}^n$ with the vertices of an $n$-dimensional hypercube, $B_A$ is the smallest sub-hypercube of $\{0,1\}^n$ that contains all the vertices in $A$. Intuitively, this concept would seem sort of analogous to that of the convex hull, except that, instead of convex combinations, we have "bit combinations" as defined above. It seems like something that should have a name, but I can't seem to find one.

Ps. For what it's worth, this question arose while I was writing this answer about forging Lamport one-time signatures on crypto.SE.

$\endgroup$
3
$\begingroup$

For a bitstring $a$, you can consider its graph $$\newcommand{\graph}{\operatorname{graph}}\graph a := \{ (k, a_k) : k \in [n] \} \subset [n] \times \{0,1\}.$$ Here $[n] := \{1,2,\dots, n\}$. (For a formal set theory point of view, $a$ and $\graph a$ are actually the same object.)

Then your condition reads $$\graph b \subset \bigcup_{a \in A} \graph a.$$

$\endgroup$
1
  • $\begingroup$ Huh... so, once I've explained that a bitstring may be represented as a vector, which may be represented as a function from $\{1, 2, \dotsc, n\}$ to $\{0,1\}$, which may be identified with is graph... I could simply write $b \subset \bigcup A$. Nice, even if somewhat liable to confuse a more applied-math oriented audience. If someone doesn't come up with an even better answer, I'll accept yours. $\endgroup$ – Ilmari Karonen Mar 27 '14 at 0:26
1
$\begingroup$

Your "bit combination" vectors can be interpreted as so-called choice functions in the context of set theory. Maybe that is not exactly what you're asking for, but the similarity is overwhelming.

More precise:
Let us at first transform your set $A$ into $n$ sets $A_{i}$, where each set $A_{i}$ contains the $i$-th bits of all vectors in $A$. For example $A_{1}$ contains every (different) first bit of all vectors in $A$. With this definition we can interpret your "bit combination" vector as a choice function of those sets $A_{i}$ and the set $B_{A}$ can be interpreted as the set of all possible choice functions to the sets $A_{i}$.

$\endgroup$
1
  • $\begingroup$ Thanks! Alas, the doesn't seem to really get me much closer to what I'm looking for, i.e. a convenient way to say "$b$ is in the __________ of $A$". $\endgroup$ – Ilmari Karonen Mar 26 '14 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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