Factoring a multiset into a product of two multisets

Question

Given a multiset $S$ of $mn$ numbers, how hard is to find multisets $A$ and $B$, of $m$ and $n$ numbers respectively, such that $$ S = \{ xy \mid x\in A, y\in B \}~~~~\text{(multiset sense)}, $$ or prove that there are none?

For example, if I give you $S=\{6,8,15,15,20,20\}, m=2,n=3$, you will tell me $A=\{3,4\}$, $B=\{2,5,5\}$.

I used the vague word "numbers" to mean anything you like. Choose "positive integers", "integers", "real numbers", "elements of my favourite quasigroup" as you please. Personally I think "real numbers" grabs the essence of the problem, as the subtask of factoring integers is a distraction. Assume you can do exact arithmetic in constant time per basic operation.

If you are working in a ring, the task looks the same as that of arranging the $mn$ numbers in an $m\times n$ matrix so that the rank is 1.

If your numbers are "positive reals", then you can take logarithms to convert the multiplication into addition, in which case the question is a bit like this one. But I don't care about finding all factorizations, just whether there is none or more than none.

I don't any more have an application for this. I just thought it might disturb your sleep like it disturbed mine.

Answer 1

I assume the positive integers case and rely on existence of unique prime factorizations and linear order for them.

Let $P$ be the product of all elements of $S$.

Assuming we can find prime factorization of each element of $S$ (and thus $P$), here are some quick tests for the "None" answer:

1. Test whether we can represent $P$ as the product of $m$-th and $n$-th powers. That is, the answer is "None" if for some prime $p\mid P$, we cannot represent $\nu_p(P)$ as a linear combination of $m$ and $n$ with nonnegative integer coefficients.

2. Let $k_p$ be the number of elements of $S$ divisible by $p$. For each prime $p\mid P$, the number $mn-k_p$ must be equal to $x\cdot y$, where $x$ and $y$ would be the number of elements not divisible by $p$ in $A$ and $B$, respectively. That is, $mn-k_p$ must be the product of two numbers below $n$ and $m$, respectively. If not, the answer is "None".

Now, let me describe a simple backtracking algorithm that tries to fill up an empty $m\times n$ table $M$ with the elements of $S$ to turn it into a multiplication table. We assume that the elements of $S$ are sorted in non-decreasing order.

1. We place the first (smallest) element of $S$ to $M_{1,1}$.

2. For each subsequent element $s$ of $S$, we will try to place it to empty cells that are adjacent to the occupied ones (e.g., we can place the second element of $S$ either to $M_{1,2}$ and $M_{2,1}$), subject to the following constraints.

3. Placing an element $s$ to $M_{i,j}$ is allowed only if the following conditions hold:

   (i) $s$ must divide $$\gcd(M_{i,1},M_{i,2},\dots,M_{i,{j-1}})\cdot \gcd(M_{1,j},M_{2,j},\dots,M_{i-1,j});$$ and

   (ii) if $\gcd(M_{i,1},M_{i,2},\dots,M_{i,{j-1}},s)<\gcd(M_{i,1},M_{i,2},\dots,M_{i,{j-1}})$, then we re-test as in (i) that each $M_{i,k}$ remains allowed at its position with $s$ placed at $M_{i,j}$; and

   (iii) similarly we check the inequality $\gcd(M_{1,j},M_{2,j},\dots,M_{i-1,j},s)<\gcd(M_{1,j},M_{2,j},\dots,M_{i-1,j})$ and that all these elements remain allowed at their positions.

4. If conditions (i)-(iii) hold, we place $s$ to $M_{i,j}$ and iterate to step 2. If not, we go to the next potential placement for $s$. If all placements are exhausted, we return to the previous element and try to find it a new placement, etc. If this way we ever return to the first element of $S$, the answer is "None".

When the whole table is filled, we try to recover the elements of $A$ and $B$ from linear algebra on the prime exponents for each prime $p\mid P$ (perhaps, something can be done here even if we cannot factor $P$). Notice that $\gcd$'s of rows and columns give multiples of the corresponding elements of $A$ and $B$ (if they exist). If the product of $\gcd$ of $i$-th row and $\gcd$ of $j$-th column give $M_{i,j}$, then these $\gcd$'s are the elements of $A$ and $B$.