# Writing a set as a sum of cartesian products

Informally, I am given a subset $Q$ of a Cartesian product $A_1\times\ldots \times A_n$ and I would like to write $Q$ as a disjoint sum of Cartesian products of subsets of the $A_i$. I would like the decomposition to be optimal in some sense—e.g. the number of terms in the disjoint sum is as small as possible.

Here's a formal statement of the problem:

Given a collection of finite disjoint sets $A_1, \ldots, A_n$ and a subset $Q$ of the Cartesian product $A_1 \times A_2 \times \ldots \times A_n$, find an integer $k$ and subsets $\{ B_{i,j} \subseteq A_j\;: \; i\in [1,k], j\in[1,n]\}$ such that

$$Q \equiv \bigcup_{i=1}^k B_{i,1} \times \ldots B_{i,n}$$

and where $k$ is the smallest integer for which such a decomposition is possible.

I feel like this problem must have been asked before, but I haven't been able to find a solution online, perhaps because I lack the necessary terminology.

• A note on terminology: It's not sum, but rather union. – Justin Benfield Jan 5 '17 at 4:50
• Are the $A_i$'s supposed to be finite, because if not, I'm pretty sure I can construct an example where you need infinitely many $i$'s. – Justin Benfield Jan 5 '17 at 4:57
• If $n=2$ and $A_1=A_2$ and $Q=\{(a,a):a\in A\}$ then the best you can do is use one term in the disjoint sum for each element of $A.$ Are you looking for a general theorem or are you looking for an algorithm to find an optimal decomposition for a given set $Q$ in the case where all the sets are finite? – bof Jan 5 '17 at 5:12
• Ultimately, I'm looking for an algorithm for finite sets. I'm not sure if that counts as a math question, but I figure even finding the right terminology would help if this sort of problem is well-known. – user326210 Jan 5 '17 at 5:27