| (This is not a solution, just a clarification of what is being asked
for here, to show that it's a sensible question that's been posed.)
> Given a prime m, consider the group G = <{1,...,m-1}, * (mod m)>.
> The multiplication table for G, when the rows of the table are
> interpreted as permutations of {1,...,m-1}, is a group K of order
> m-1 (a subgroup of all permutations). Show that, for each left
> coset of K (with respect to all permutations) the sum of the number of
> left-to-right maxima of all elements of the coset is O(m log m).
Fr'instance, let m be 5, then the "multiplication table" for G looks like
this:
1234
2413
3142
4321
Now, we are told to take each row as denoting a perm of {1,2,3,4}, yielding
K = {I,(1243),(14)(23),(1342)}. K is isomorphic as an abstract group to C4.
The full perm group on four objects is of course, S4, with order 24. Each
coset will have 6 elements.
Forgetting about the coset partition for the moment, and looking at
the full group, what is the average number of left-to-right maxima? Call
this G(n), where n=m-1.
G(0) = 0
G(n) = 1 + (1/n)*sum(j=1..n, G(j))
=> G(n) = sum(j=1..n, 1/j)
So, G(n) clearly is O(ln(n)).
Now, Alex' question involves looking at a finer level of granularity.
If we examine each coset, does the coset have the same average, of about
ln(n)? Or do the cosets vary in average? I guess that this is all about
some proposed resource allocation algorithm across symmetric multiprocessors,
where the number of left-to-right maxima is some measure of load.
If I've seized it right, each left coset corresponds to some column
permutation of the multiplication matrix shown above. The perm group is
generated by transposition of adjacent columns, which might be a useful way to
look at the problem, since any one such transposition can have but a limited
effect on the average number of left-to-right maxima.
Cheers,
Andrew.
|
| re .1,
> Fr'instance, let m be 5, then the "multiplication table" for G looks like
>this:
> 1234
> 2413
> 3142
> 4321
>Now, we are told to take each row as denoting a perm of {1,2,3,4}, yielding
>K = {I,(1243),(14)(23),(1342)}. K is isomorphic as an abstract group to C4.
I see this; the row 1234 corresponds to the permutation
1234 -> 1234 which is the identity I; the row 2413
corresponds to the permutation 1234 -> 2413 which as a
product of cycles is (1243); and 1234 -> 3142 is (1342)
and 1234 -> 4321 is (14)(23).
You then go on to say without proof that the set of these
four permutations is a four element subgroup of the full
permutation group on 4 elements S4. But I checked and in
fact the four permutations are indeed closed under
"multiplication" and inverses and contain the identity,
so they do make up a subgroup.
If you now consider the general case of prime m and the
rows of the multiplication table mod m of {1,...,m-1},
you get a subset of m-1 permutations of the full
permutation group S(m-1). These m-1 permutations will of
course generate a smallest subgroup of S(m-1) containing
them.
Can you give an asymptotic formula for the size of this
subgroup as a function of m, as the prime m -> oo?
Dan
|
| Dan,
I've no idea whether you're taking the Mickey or not. Let me assume
that you were serious.
Every group has a representation as a permutation group. If the
group happens to be the multiplicative group mod p, then the permutation group
is exhibited by the "multiplication table". So, it's obvious that the
set of perms exhibited by this multiplication table is closed.
Further, the multiplicative group mod p is well-known to be cyclic of
order p-1. So, the permutation group which is a faithful representation of
the underlying group will have the same structure as the abstract group.
The point of my obvious remarks in that paragraph of .1 were to show
the simple behaviour of the example p=5, to help understanding of the neglected
.0.
Andrew.
|
| Well, I checked the set in .1 for closure, then realized this
was just an example of Cayley's theorem about isomorphically
embedding any group into the full permutation group on its
domain, then stopped again to ask if the very explicit
representation which you used really was the one used in the
proof of Cayley's theorem. I satisfied myself that it was.
It seemed there was enough math going on behind the scenes
here to call a little bit of attention to it, so I did.
Dan
|
| re .1-.6
Thanks for bootstrapping the discussion -- I haven't checked this
conf. in a couple of months.
The average analysis in .1 is correct. (Given this, if we can show
that the numbers of left-to-right maxima in each coset differ by,
for example, a constant factor, then this is sufficient to prove
the conjecture in .0.)
Regrettably, I cannot report any progress. However I performed several
exhaustive searches of the groups in question. All indications are
that the conjecture ought to be correct.
To answer the question of .1 on the relation to multiprocessor
scheduling:
- There are m-1 processors and m-1 tasks (p is the prime)
- Each number in the table represent a task; row i represents
the schedule of processor i
- The permutation that generates a coset corresponds to an
adversary that allows the tasks to be performed in a
particular order
- The number of left-to-right maxima of a coset is the amount
of redundant work performed by processors, i.e., when two
processors perform the same task, the work of one of the
two processors is wasted.
Although I have stopped working on this problem, I believe that
a solution will be a very interesting result. My strengths are
not that much in group theory and combinatorics, so I do not have
a good idea of how difficult this can be.
Regards,
Alex
|