Ralf Hemmecke <[EMAIL PROTECTED]> writes:
> >> Summation over cycles is still not gone.
> > But over permutations. That's a lot less!
>
> Arrrggghhh. Of course my sentence should have read:
>
> "Summation over permutations is still not gone."
But it is!?
> > Similarly, if $G$ is a species, the longest cylce of $G[\sigma]$ can only be
> > shorter than the the longest cycle of $\sigma$. (Check this...!)
> > is enough... (apart from the fact, that the final sentence is wrong)
>
> Oh, I have not guessed that
guessed what?
> and the function name "cycleTypeSpecies" tells me nothing at all. Not even
> from the documentation you give I understand the input/output specification.
OK, I try again, maybe this is better.
Martin
Definition~4 in Section~2.2 of \cite{BLL} goes as follows:
\begin{dfn}
Z_F \square Z_G = \sum_{n\ge0}\frac{1}{n!}
\sum_{\sigma\in S_n}
\fix F[(G[\sigma])_1,(G[\sigma])_2,\dots]
x_1^{\sigma_1}x_2^{\sigma_2}\dots
\end{dfn}
We will see that $\fix F[(G[\sigma])_1,(G[\sigma])_2,\dots]$ in fact depends
only on the cycle type of $\sigma$. Thus we can rewrite the above to avoid
summation over all permutations:
\begin{equation*}
Z_F \square Z_G = \sum_{n_1+2n_2+\dots}
\fix(F\square G)[n_1, n_2, \dots]
\frac{x_1^{n_1}x_2^{n_2}\dots}
{1^{n_1}n_1! 2^{n_2}n_2!\dots},
\end{equation*}
We first show how to compute the cycle type of $\sigma^d$ given only the cycle
type of $\sigma$. This can be done using Excercise~2.b of the same section:
\begin{exc}
$$(\sigma^k)_m = \sum_{d\mid k, (m, k/d)=1} d \sigma_{dm}.$$
\end{exc}
Note that taking a permutation to a power can only decrease the length of the
longest cycle: let $\sigma$ be a permutation of $[n]$ and $k\in [n]$. Let $c$
be the cycle of $\sigma$ that contains $k$. Applying $\sigma$ to $k$ maps $k$
to some other element of $c$.
CYCLETYPE ==> List Integer
cycleTypePower(p: CYCLETYPE, k: Integer): CYCLETYPE == {
cycleType: CYCLETYPE := [];
divisorsK: List Integer := divisors k;
for m in #p..1 by -1 repeat {
sum: Integer := 0;
for d in divisorsK | gcd(m, k/d)=1 repeat {
sum := sum + d * p.(d*m)
}
cylceType := cons(sum, cycleType)
}
cycleType
}
We are now ready to compute $(G[\sigma])_k$. Proposition~3 in the same section
reads
\begin{prop}
$$(G[\sigma])_k = \frac{1}{k}\sum_{d\mid k} \mu(k/d) fix G[\sigma^d],$$ where
$\mu$ is the M\"obius function for integers.
\end{prop}
We know already how to compute the cycle type of $\sigma^d$, given the cycle
type of $\sigma$. Furthermore, we remark that the length of the longest cycle
in $F[\sigma]$ is the least common multiple of the cycle lengths of $\sigma$:
Let s be a structure on $[n]$ and let $\sigma$ be a permutation of $[n]$.
We want to know the minimal positive number greater than one with %
$\sigma^o s = s$, which is just the order of $\sigma$. This is well known to be
the least common multiple of the cycle lengths of $\sigma$.
\begin{ToDo}
Give a reference for the order of a permutation.
\end{ToDo}
Thus, the following function returns the cycle type of $F[\sigma]$ given the
cycle type of $\sigma$.
cycleTypeSpecies(p: CYCLETYPE): CYCLETYPE == {
cycleType: CYCLETYPE := [];
s := cycleIndexSeries;
n := lcm([i for i in 1..#p | p.i ~= 0]);
for k in n..1 by -1 repeat {
divisorsK: List Integer := divisors k;
sum: Integer := 0;
for d in divisorsK repeat {
sum := sum + moebiusMu(k/d)
*coefficient(s, cycleTypePower(p, d));
-- this is very rough... is there such a function coefficient? Or count?
}
cycleType := cons(sum/k, cycleType);
}
cycleType;
}
-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys-and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
Aldor-combinat-devel mailing list
Aldor-combinat-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/aldor-combinat-devel
