10
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ In general it is a hard problem. For many instances of a product partition, the number of classes as well as many of the sizes of classes are composite. If you have a class with a prime number of elements (or just one) there aren't many ways that it can appear as part of a product partition. Cataloguing the classes by the factorizations of their sizes is a good start to finding a product if one exists. Gerhard "Ask Me About System Design" Paseman, 2011.12.04 $\endgroup$ Dec 5, 2011 at 2:13

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ So everything reduces to the arithmetical condition on the $n$ lists of the exponents in the factorization of the numbers $c_k$ (assuming we have it). Given $n$ lists of non-negative integers $\gamma_k\in\mathbb{N}^m $ for $1\le k \le n$, the problem is to write them as $\alpha_i + \beta_j$ for some $\alpha_i \in\mathbb{N}^m $ and $\beta_j\in\mathbb{N}^m $. $\endgroup$ Dec 5, 2011 at 9:26
  • 2
    $\begingroup$ A necessary condition: Some values among the $n(n-1)$ rational quotients of the form $c_k/c_{k'}$ with $k\not=k'$ must arise with multiplicity $\geq\sqrt{n}$. $\endgroup$ Dec 5, 2011 at 17:13
  • $\begingroup$ Roland makes a good point. We can restrict to the rational quotients which are at least 1. There must be a integers $U,V \gt 1$ such that $UV \ge n$, at least $U$ of the quotients occur with multiplicity $\ge V$ and at least $V$ of the quotients occur with multiplicity $\ge U$. In addition, given a quotient occurring with multiplicity $V$ (or $U$), the $2V$ (or $2U$) elements $c_k$ used in the numerator and denominators must have distinct indices $\endgroup$ Dec 6, 2011 at 17:25
  • $\begingroup$ Thank you for your answers. I have a more precise question in mind but I need to think about it to formulate it properly. I will come back later. Anyway, your necessary conditions will help me to compute examples more efficiently. Thanks again. $\endgroup$
    – Taladris
    Dec 7, 2011 at 6:00
3
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.