I'm interested in factoring a finite set of $n$-tuples as the Cartesian product of two "factor sets", of which the first factor is itself the Cartesian product of some of the set's projection images, and the second factor is an unfactorizable "remainder".

To describe the problem more precisely, let $X$ be a non-empty, finite set of $n$-tuples, and let $A_1,...,A_n$ be the images of $X$ upon projection onto its various coordinates. Hence, $X \subset \prod_{i=1}^{n} A_i $. Furthermore, assume that this inclusion is strict; that is, $X \neq \prod_{i=1}^{n} A_i $. (From this it follows that $n > 1$.) If $\sigma$ is some permutation of $\{1,...,n\}$, let $X_\sigma$ denote the set of $n$-tuples derived from $X$ by permuting the coordinates of its elements according to $\sigma$: $X_\sigma = \{(x_{\sigma(1)},...,x_{\sigma(n)})|(x_1,...,x_n)\in X \}$.

For any $n$-permutation $\sigma$, I'm interested in factorizations of $X_\sigma$ having the form $X_\sigma \cong (\prod_{i=1}^{k} A_{\sigma(i)}) \times Z$, where $0 \leq k \lt n$ and $Z \subsetneq \prod_{i=k+1}^{n} A_{\sigma(i)}$. I'm using the $\cong$ here as shorthand to indicates that every $n$-tuple in $X_\sigma$ can be written (obviously uniquely) as the concatenation of one $k$-tuple from $\prod_{i=1}^{k} A_{\sigma(i)}$ and one $(n-k)$-tuple from $Z \subsetneq \prod_{i=k+1}^{n} A_{\sigma(i)}$, and, conversely, every concatenation of such tuples represents some element of $X_\sigma$. (If $k = 0$, then the $\cong$ just means that $Z = X_\sigma$.)

I am primarily interested in factorizations for which the factor $\prod_{i=1}^{k} A_{\sigma(i)}$ has maximal cardinality, over all possible choices of $\sigma$ and $k$. I am also interested in factorizations for which $k$ is maximal, over all possible choices of $\sigma$.

I'm looking for keywords I may use to search for algorithms to compute such maximal factorizations, given some concrete set of $n$-tuples $X$. Do such factorizations, or the problem of computing them, have a name? Any pointers to the relevant literature would be appreciated!


  • $\begingroup$ I suspect that this is related to NP hard problems such as exact cover or 3 dimensional matching. What I find interesting is that you need few witnesses to "block" such factorizations. For example, if for all appropriate partial tuples y the tuple corresponding to a_1,a_2,y is not in X, then X will not be factorizable as A1x A2 x whatever. It reminds me of logic minimization of an almost boolean function (some inputs may receive a don't care value as output) and its (almost) complement. Gerhard "Anyone Remember Programmable Logic Devices?" Paseman, 2011.01.28 $\endgroup$ – Gerhard Paseman Jan 29 '11 at 3:07

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.