On tensor-factorisation problems, I: the combinatorial problem
Peter M. Neumann and Cheryl E. Praeger
Abstract: A k-multiset is an unordered k-tuple,
perhaps with repetitions.
If x is an r-multiset {x1,…,xr}
and y is an s-multiset {y1,…,ys}
with elements from an abelian group A
the tensor product of x and y is defined as the rs-multiset
{xiyj | 1 ≤ i ≤ r,
1 ≤ j ≤ s}.
The main focus of this paper is a polynomial-time algorithm
to discover whether a given rs-multiset
from A can be factorised. The algorithm is not guaranteed
to succeed, but there is an acceptably small upper bound for the probability of failure.
The paper also contains a description of the context
of this factorisation problem, and the beginnings of
an attack on the following division-problem: is a given
rs-multiset divisible by a given r-multiset, and
if so, how can division be achieved in polynomially
bounded time?
|
