Return to Answer

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.

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.

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 meant 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.

The $a_i$ must be chosen from those integer ratios which repeat at least $v$ times (and the chosen ratios must use distinct indices) and the $b_v$ from those which appear at least $p$ times. And any value chosen to be an $a_i$ (say) gives a limited list which must include

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.

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.

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 meant 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.

The $a_i$ must be chosen from those integer ratios which repeat at least $v$ times (and the chosen ratios must use distinct indices) and the $b_v$ from those which appear at least $p$ times. And any value chosen to be an $a_i$ (say) gives a limited list which must include

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$

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 meant 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.

The $a_i$ must be chosen from those integer ratios which repeat at least $v$ times (and the chosen ratios must use distinct indices) and the $b_v$ from those which appear at least $p$ times. And any value chosen to be an $a_i$ (say) gives a limited list which must include

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.