(This question has been substantially revised in an attempt to word it clearly.)
I am wondering if anyone has seen this problem. Let $[n] = \{1,\ldots,n\}$ for an integer $n$. Consider two finite multisets of bitstrings, $$ A=\{a_i\}_{i\in[r]} \quad\text{and} \quad B=\{b_j\}_{j\in[s]} \;,$$ where each $a_i \in \{0, 1\}^n$ and each $b_j \in \{0, 1\}^n$. We may compute from this a "Cartesian bitwise join" $C$, which is also a multiset of bitstrings $C= \{c_{i,j}\}_{(i,j) \in [r] \times [s]}$ for size $|C| = |A| \cdot |B| = rs$, where $$ c_{i,j} = a_i \vee b_j$$ where "$\vee$" is bitwise-OR.
Question. If you are given such a multi-set $C$, without any particular indexing, can you find multi-sets $A$ and $B$ of which $C$ is the Cartesian bit-wise join? Equivalently: given a sequence $C = (c_k)_{k\in[m]}$ consisting of bitstrings in $\{0,1\}^n$, can you find sequences $A = (a_i)_{i\in[r]}$ and $B = (b_j)_{j\in[s]}$ such that $m = rs$, and a bijection $\varphi: [r] \times [s] \to [m]$, such that $$c_{\varphi(i,j)} = a_i \vee b_j$$ for all $(i,j) \in [r] \times [s]$?
This problem is equivalent to the following problem. Consider the ring $R$ whose elements are strings in $\{0,1\}^n$, where addition is done bit-wise by the operation $x + y = x \oplus y \oplus 1$ (where $\oplus$ is parity) with $1^n$ being the identity, and multiplication is the bit-wise OR with $0^n$ being the identity. For some particular ordering of the elements of $A$, we may present $A$ as an element of $R^r$, and similarly present $B$ as an element of $R^s$. The Cartesian bitwise join corresponds to the outer product of $A$ and $B$, $$ C \;=\; A B^\top \;=\; \begin{bmatrix} a_1 \vee b_1 & a_1 \vee b_2 &\cdots& a_1 \vee b_s \\ a_2 \vee b_1 & a_2 \vee b_2 & \cdots & a_2 \vee b_s \\ \vdots & \vdots & & \vdots \\ a_r \vee b_1 & a_r \vee b_2 & \cdots & a_r \vee b_s \end{bmatrix}\;,$$ except interpreted as a multiset rather than a matrix (that is, the elements of $C$ are not assigned to particular coefficients of an $r \times s$ matrix). Given a multiset $C$ with composite cardinality $m \in \mathbb N$, can its elements be mapped to coefficients of an $r \times s$ array (such that $m = rs$) which is an outer product of the above form?
(By interchanging 0s and 1s in all of the bitstrings, we may replace the bit-wise OR "$\vee$" with the bit-wise AND "$\wedge$", in which case we may take $R$ to be the ring whose elements are strings in $\{0,1\}^n$, where addition is as vectors over $\mathbb Z_2$, and multiplication is the bit-wise AND. )
One may consider additional constraints on this problem, such as minimum Hamming weight of the bitstrings in $A$ and $B$ (in the Cartesian join formulation). We certainly require that $A,B \ne \{0^n\}$ to prevent a trivial solution.
- This problem arises in an EE & complexity theory context. I am looking for other cases or analysis of it.
- The problem is somewhat analogous to factoring but does not seem to have a unique factorization.
- Note that bitvectors can be naturally modelled as hypergraphs so maybe something from that theory is applicable. I did research hypergraph products but that theory does not seem to apply directly. The problem translates to finding two hypergraphs $H'$ and $H''$ given a hypergraph $H$, such that the $H$ can be formed by taking all pairwise unions of edges in $H'$ and $H''$.