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, for some $n > 1$, 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 $. If $\sigma$ is some permutation of $\{1,...,n\}$, let $X_\sigma$ denote the set $\{(x_{\sigma(1)},...,x_{\sigma(n)})|(x_1,...,x_n)\in X \}$.

For any 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!

~kj

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!

~kj