If we consider a partition ${\mathcal X}=(X\_1,\dots,X\_n)$ of a finite set $X$ and a partition ${\mathcal Y}=(Y\_1,\dots,Y\_m)$ of another finite set $Y$, then $(X\_i\times Y\_j)\_{i=1,...,n,j=1,...,m}$ is a partition of $X\times Y$. I will call this partition the "product partition" ${\mathcal X}\times{\mathcal Y}$.


On the converse, given a partition ${\mathcal Z}$ of a finite set $Z$ with finite cardinal $n=pq$ ($p$ and $q$ different from $0$ or $1$), how can one know if this partition is isomorphic to a non trivial product partition (i.e. if there exists two sets $X$ and $Y$ whose cardinals at least $2$ and endowed with partitions ${\mathcal X}$ and ${\mathcal Y}$ (respectively) and a bijection of $X\times Y$ on $Z$ such that the images of the elements of ${\mathcal X}\times{\mathcal Y}$ by this bijection are exactly the elements of ${\mathcal Z}$)? 


In the very particular case where one knows that $Z$ is a finite commutative group and that ${\mathcal Z}$ is the set of classes $gH$ for some subgroup $H$ of $Z$, then using the classification of finite commutative groups, one obtains that ${\mathcal Z}$ is a product partition. 


This question seems complicated (at least for me!) in the general case. Does someone know a partial answer to my question? In some particular case?



Partitions and finite sets
Here are comments but not a solution. Boris points out that the problem reduces to this: given a list of positive integers $c\_1 \dots c\_n$ are there lists $a\_1 \cdots a\_u$ and $b\_1\cdots b\_v$ so that the products $a\_ib\_j$ are the $m$ values. One problem is finding the values $u,v$ with $uv=n$ let us assume that $u$ and $v$ are given (for example if $n=899$ then we would have to have $u=29$ and $v=31$ since we desire that $u,v \ge 2$) 


There are many necessary conditions which might rule out most lists of numbers but that does not mean that there could not be difficult cases. If we assume that the lists are ordered (and why not) then 


1. $a\_1b\_1=c\_1$ and
2. $a\_ub\_v=c\_n.$  

this might or might not limit possibilities. Any $c\_k$ with few factorizations limits the possibilities. Also the sum of the $c\_k$ may limit things because
3. $\sum a\_i\sum b\_j=\sum\_1^nc\_k$


If we look at the $\binom{n}{2}$ ratios $\frac{c\_{s}}{c\_t}$ then we must have $\binom{u}{2}$ values (which will be the ratios $\frac{a\_{x}}{a\_{y}}$) which occur at least $v$ times (and involve $2v$ distinct indices) and similarly $\binom{v}{2}$ values which appear at least $u$ times each. 


It is worth looking at the special case that the $c$ values are all powers of a single prime $p.$ That makes it easier to have integer ratios and values with many factors. This is also relevant to the general case. Let $p^{\gamma\_k}=c\_k$ or merely be the (known) power of $p$ dividing $c\_k.$ Then we will need $u+v$ values $\alpha\_i$ and $\beta\_j$ so that the $n$ sums $\alpha\_i+\beta\_j$ are the $\gamma\_k.$ 


Particularly relevant to this case is that me may as well assume that the $c$ values have no common divisor (so in the one prime case we may as well assume $\gamma\_1=\alpha\_1=\beta\_1$.) This is because we can divide out any factor $f$ common to all the $c$ values, solve the reduced problem (if possible) by $a^{'}\_ib^{'}\_j=c^{'}\_k$ then chose any factorization $f=gh$ and let $a\_i=ga^{'}\_i$ and $b\_j=hb^{'}\_j$


**further comment** Replace each integer $c=2^e3^f5^g\dots$ by a monomial $x\_2^ex\_3^fx\_5^g\dots$ where the $x\_{\*}$ are formal variables. Then add. This reduces the problem to factoring a multinomial with positive integer coefficients into two of the same type. Then the single prime case is factoring a polynomial (into factors with positive coefficients). There are algorithms for that.


