Dear Forum, dear Simon,

norton@math.binghamton.edu said:
> I have written a GAP program to compute structure constants in
> symmetric groups without computing the whole table. I don't know how
> inefficient I am being, but it took over an hour to show that in S34
> (2^17,3^11.1,6^3.5.4^2.3) was 271/72, this being the simplest test I
> could work out for a rather far-out conjecture I am investigating
> (which this value confirmed).

Can I reasonably expect to go significantly further, and if so how far?

I'm including below some GAP code which you may find useful. After
reading this into GAP the example above can be computed by:

p0 := 0*[1..34]+1;
p1 := 0*[1..17]+2;
p2 := Concatenation( 0*[1..11]+3, [1]);
p3 := [6,6,6,5,4,4,3];

v0 := CharacterValueColumnSymmetric(p0);;time;
v1 := CharacterValueColumnSymmetric(p1);;time;
v2 := CharacterValueColumnSymmetric(p2);;time;
v3 := CharacterValueColumnSymmetric(p3);;time;

strconst := CentralizerOrderPartition(p0) / 
            (CentralizerOrderPartition(p1) *
             CentralizerOrderPartition(p2) *
             CentralizerOrderPartition(p3) ) *
            Sum(List([1..NrPartitions(34)], i-> v1[i]*v2[i]*v3[i]/v0[i]));

This takes on my notebook about 25 seconds. So, it should be possible
to use the programs for some larger examples as well.

Background: The code must be very similar to the code for character
tables of symmetric groups in the GAP library (by Goetz Pfeiffer). The
idea is to use the Murnaghan-Nakayama recursion formula and to read it
as a reduction of the computation of a column of the table of S_n to
the computation of *one* column for some S_m with m<n. We save a lot
of work in the recursion by storing and reusing some intermediate
values.

For more details see the very nice description by Goetz Pfeiffer,
contained in the GAP-3.4.4 distribution in etc/ctweyl.dvi.

With best regards,

Frank Lübeck

------------------  snip  here  ----------------------------------
##############################################################################
## 
##                       cvalsym.g
##  
##  Frank Luebeck          3/2000    Lehrstuhl D fuer Mathematik, RWTH Aachen
##  
##  The main function in this file is:
##  
##      CharacterValueColumnSymmetric(p);
##  
##  Here p is  a partition of some natural  number n. The function returns
##  the list of  character values of the  symmetric group  S_n on elements
##  with  cycle type p.  The ordering  of the  characters (also labeled by
##  partitions of n) is given by the ordering of `Partitions(n);'.
##  
##  Note that the code here is very similar to Goetz Pfeiffers code in the
##  GAP library.  It has the main advantage  that  single columns of large
##  tables can be computed separately.
##    
##  Due to the global caching  the programs here  are also pretty fast for
##  computing all complete character tables in a range [1..n] for some n.
##  

# We cache partitions and their duals
PARTITIONS := [];
DUALPARTITIONS := [];

Partitions1 := function(n)
if not IsBound(PARTITIONS[n]) then
PARTITIONS[n] := Immutable(Partitions(n));
IsSet(PARTITIONS[n]);
fi;
return PARTITIONS[n];
end;

DualPartitions1 := function(n)
if not IsBound(DUALPARTITIONS[n]) then
DUALPARTITIONS[n] := Immutable(List(Partitions1(n), AssociatedPartition));
fi;
return DUALPARTITIONS[n];
end;

# This returns for a partition p of n, its position in `Partitions(n)'
# Arguments are: p[, n]
NrPartition := function(arg)
  local   p,  n;
  p := arg[1];
  if Length(p)=0 then
    return 1;
  fi;
  if Length(arg)>1 then
    n := arg[2];
  else
    n := Sum(p);
  fi;
  return Position(Partitions1(n), p);
end;

# This computes the entry [n, pnr, k] of the result of the GAP command
# `InductionScheme(n)'
# (Here we use pairs of partition and its dual, instead of beta-sets.)
REMOVEHOOKCACHE := [];
RemoveHookInfo := function(n, pnr, k)
local rr, p, pt, km1, res, i, j, pr;

# remove rim hook
rr := function(p, pt, i, j)
  local   prr,  k;
  prr := p{[1..i-1]};
  for k in [i..pt[j]-1] do 
    Add(prr, p[k+1]-1);
  od;
  Add(prr,j-1);
  Append(prr, p{[pt[j]+1..Length(p)]});

  # remove trailing zero's (in case j=1)
  if j=1 then
    k := Length(prr);
    while k>0 and prr[k]=0 do
      Unbind(prr[k]);
      k := k-1;
    od;
  fi;
  return prr;
end;

# caching
if not IsBound(REMOVEHOOKCACHE[n]) then
REMOVEHOOKCACHE[n] := [];
fi;
if not IsBound(REMOVEHOOKCACHE[n][pnr]) then
REMOVEHOOKCACHE[n][pnr] := [];
fi;
if IsBound(REMOVEHOOKCACHE[n][pnr][k]) then
return REMOVEHOOKCACHE[n][pnr][k];
fi;

p := Partitions1(n)[pnr];
pt := DualPartitions1(n)[pnr];
km1 := k-1;

# find k-hooks
res := [];
for i in [1..Length(p)] do
  j := 1;
  while j<=p[i] and p[i]-j+pt[j]-i > km1 do
    j := j+1;
  od;
  if j<=p[i] and p[i]-j+pt[j]-i = km1 then
    pr := NrPartition(rr(p,pt,i,j), n-k);
    Add(res,  (-1)^(pt[j]-i) * pr);
  fi;
od;

  # store in cache
  REMOVEHOOKCACHE[n][pnr][k] := res;
  return res;
end;

# Here we cache columns of character tables of symmetric groups,
# in position [n][i] is the column of the table of S_n and class
# given by `Partitions(n)[i]'.
CSYMVALCOLS := [[[1]]];

CharValSymCol := function(n, cl)
  local   clp,  k,  cln,  coln,  rem,  res,  a,  val,  b;
  if n=0 then
    return [1];
  fi;
  if not IsBound(CSYMVALCOLS[n]) then
    CSYMVALCOLS[n] := [];
  fi;
  if IsBound(CSYMVALCOLS[n][cl]) then
    return CSYMVALCOLS[n][cl];
  fi;
  
  clp := Partitions1(n)[cl];
  k := clp[1];
  cln := NrPartition(clp{[2..Length(clp)]}, n-k);
  coln := CharValSymCol(n-k, cln);
  rem := List([1..Length(Partitions1(n))], i-> RemoveHookInfo(n, i, k));
  res := [];
  for a in rem do
    val := 0;
    for b in a do
      if b>=0 then
        val := val + coln[b];
      else
        val := val - coln[-b];
      fi;
    od;
    Add(res, val);
  od;
  CSYMVALCOLS[n][cl] := res;
  return res;
end;

# The user function, as explained above. For efficiency we compute the
# character degrees in a separate loop (as in the GAP library).
CharacterValueColumnSymmetric := function(pp)
local n, res, ps, pst, i, p, pt, prd, j;
n := Sum(pp);

# case of character degrees
if pp[1]=1 then
  res := [];
  ps := Partitions1(n);
  pst := DualPartitions1(n);
  for i in [1..Length(ps)] do
    p := ps[i];
    pt := pst[i];
    prd := 1;     # product over hook lengths
    for i in [1..Length(p)] do
      for j in [1..p[i]] do
        prd := prd * (p[i]-j+pt[j]-i+1);
      od;
    od;
    Add(res, Factorial(n) / prd);
  od;
  if not IsBound(CSYMVALCOLS[n]) then
    CSYMVALCOLS[n] := [];
  fi;
  CSYMVALCOLS[n][1] := res;
  return res;
fi;

return CharValSymCol(n, NrPartition(pp, n));
end;

# We need this for the structure constants.
CentralizerOrderPartition := function(p)
return CharTableSymmetric.centralizers[1](Sum(p), p);
end;

##  Example: 
##    
##  pp := Partitions(34);;
##  p0 := 0*[1..34]+1;
##  p1 := 0*[1..17]+2;
##  p2 := Concatenation( 0*[1..11]+3, [1]);
##  p3 := [6,6,6,5,4,4,3];
##  
##  v0 := CharacterValueColumnSymmetric(p0);;time;
##  v1 := CharacterValueColumnSymmetric(p1);;time;
##  v2 := CharacterValueColumnSymmetric(p2);;time;
##  v3 := CharacterValueColumnSymmetric(p3);;time;
##  
##  strconst := CentralizerOrderPartition(p0) / 
##              (CentralizerOrderPartition(p1) *
##               CentralizerOrderPartition(p2) *
##               CentralizerOrderPartition(p3) ) *
##              Sum(List([1..NrPartitions(34)], i-> v1[i]*v2[i]*v3[i]/v0[i]));