Partitions and finite sets - MathOverflow

Partitions and finite sets

2011-12-05T01:47:50Z

Hello everybody,

if we considere a partition ${\mathcal X}=(X_1,\dots,X_n)$ of a finite set $X$ and a partition ${\mathcal Y}=\left(Y_1,\dots,Y_m\right)$ of another finite set $Y$, then $(X_i\times Y_j)_{i=1,...,n,j=1,...,m}$ is a patition of $X\times Y$. I will call this partition "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 knoow a partial answer to my question? In some particular case?

Thanks you in advance.

Best wishes

Answer by Boris Novikov for Partitions and finite sets

2011-12-05T03:22:33Z

In your notation:

Let $$ |X|=p,\ |Y|=q, \ |X_i|=p_i,\ |Y_j|=q_j,\ \ \ (1) $$ so that $$ \sum_ip_i=p,\ \sum_jq_j=q.\ \ \ (2) $$

If the partition ${\mathcal Z}$ is ``isomorphic'' (in your sense) to ${\mathcal X}\times{\mathcal Y}$, then one can enumerate its members by double subscripts so that

$$ {\mathcal Z}=(Z_{ij})_{i\le n, j\le m},\ \ \ (3) $$

$$ \mid Z_{ij}\mid=p_iq_j\ \ \ (4) $$ and in addition (2) is fulfilled.

So the conditions (2)--(4) are necessary. But now it is seen easily that they are sufficient too: if you have $Z$ and ${\mathcal Z}$, take arbitrary $X$ and $Y$ with partitions as in (1) and (2), and write arbitrary bijections $X_i\times Y_j\leftrightarrow Z_{ij}$.

Answer by Aaron Meyerowitz for Partitions and finite sets

2011-12-05T07:20:41Z

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

$a_1b_1=c_1$ and
$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
$\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.