monta@cmu-cs-g.ARPA (Peter Monta) (06/20/85)
This is a very interesting problem; here are some thoughts. I am
*convinced* that there is a polynomial (in m) algorithm.
The problem statement is still not quite right; it should read ``such
that for some n in [0,1], f(x) = floor(x*n) for all x in A.''.
It is useful to view the problem in an algebraic light. The set of
all mappings from A to A (call it M) has the natural structure of a
monoid. You define a certain subset T of M, the truncated multiplications.
Then you ask if given an element h of M, there is a factorization of
h with terms only in T.
Instead of working with h, let us try to characterize the subset of M
consisting of all compositions of elements of T, that is, the ``monoid-
span'' Msp(T) in M. Once this is done, the question reduces to whether
h is in the monoid-span.
Now to specifics. All the truncated multiplications start at zero and
increase with at most unit ``skips''; more precisely, given a truncated
multiplication t, we have t(0) = 0 and t(x+1) = either t(x) or t(x)+1 for
all x in A\{m}. This property carries over to Msp(T); the composite of any
two mappings satisfying this condition again satisfies the condition.
Therefore (by induction) any element of Msp(T) necessarily satisfies this
condition.
It is easily shown that there are exactly 2^m of these mappings,
which is considerably less than the cardinal of M, namely, (m+1)^(m+1).
Unfortunately, plenty of these can't be factored over T. Let's take the
case m=4; the candidate elements of Msp(T) are
00000 (0) 00111 01111 01222
00001 (1/4) 00112 (1/2) 01112 01223
00011 (1/3) 00122 (2/3) 01122 01233
00012 00123 (3/4) 01123 01234 (1)
where the mappings are identified with their lists of values. Which
of these are in Msp(T)? Certainly the ones that are actually in T (these
are marked with a Farey fraction). Notice that the composite of any two
elements of T always occurs *farther up in the table than both*. This
immediately shows that none of the mappings on the right half of the
table is in Msp(T) except the identity.
Consider the ones in the second column (001 prefix). Any factorizations of
these must consist of the composite of one element of T in the right half of
the table and one in the second column, since the only way to get a 001
prefix is to compose 01xxx with 001xx. But there is only the identity to
work with, so 00111 is not in Msp(T).
Now consider the ones with 0001 prefix. Here there is more flexibility,
since 0001x = 001xx composed with 001xx (or 01xxx composed with 0001x,
which merely admits (1/3) to Msp(T)). And indeed, 00012 = (3/4)(3/4),
as was pointed out in the original posting.
My strategy for larger values of m is to generate a table like the one
above marked with Farey fractions, rule off the regions with different
prefixes, and search, working downward from the identity. The nearer
one gets to zero, the more factorizations are possible, but the easier
it is to find one; this is the reason for my belief that there is a
polynomial algorithm (the algorithm that the above loosely expresses is
exponential).
The first nontrivial nonfactorizable mappings occur at m=7: 00012222 and
00011112 are not factorizable.
Peter Monta
monta@cmu-cs-g
..!rochester!cmu-cs-pt!cmu-cs-g!monta