# This file was created from xpl/multfree.xpl, do not edit!
#############################################################################
##
#W  multfree.g      database of mult.-free perm. characters     Thomas Breuer
#W                                                                  Klaus Lux
##
#H  @(#)$Id: multfree.g,v 1.1 2001/10/16 16:23:26 gap Exp $
##
#Y  Copyright (C)  2000,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
##
##  This file contains the following {\GAP} objects.
##
##  `MultFreeFromTOM'
##      is a function that computes the multiplicity-free permutation
##      characters of a group from its table of marks.
##
##  `MultFree'
##      is a function that can be used for computing multiplicity-free
##      characters that are possible permutation characters,
##      relative to a given table of a subgroup.
##
##  These functions are {\GAP}~4 equivalents of those functions that had
##  been used to compute the characters listed in~\cite{BL96}.
##
Revision.multfree_g :=
    "@(#)$Id: multfree.g,v 1.1 2001/10/16 16:23:26 gap Exp $";


#############################################################################
##
##  Print the banner if wanted.
##
if not QUIET and BANNER then
  Print(
    "--------------------------------------------------------------------\n",
    "Loading Functions to compute Multiplicity-Free (Permutation)\n",
    "Characters;\n",
    "similar functions were used in the classification\n",
    "of the Multiplicity-Free Permutation Characters\n",
    "of the Sporadic Simple Groups and Their Automorphism Groups,\n",
    "by T. Breuer and K. Lux;\n",
    "call `MultFreeFromTOM( <tbl> )' for computing the multiplicity-free\n",
    "permutation characters for the character table <tbl>,\n",
    "call `MultFree( <G>, <H> )' for computing those multiplicity-free\n",
    "possible permutation characters for the character table\n",
    "with identifier <G> that are induced from possible permutation\n",
    "characters of the subgroup whose character table has identifier <H>.\n",
    "--------------------------------------------------------------------\n"  );
fi;


#############################################################################
##
#F  MultFreeFromTOM( <tbl> )
##
##  For a character table <tbl> for which the table of marks is available in
##  the {\GAP} library,
##  `MultFreeFromTOM' returns the list of all multiplicity-free permutation
##  characters of <tbl>.
##
BindGlobal( "MultFreeFromTOM", function( tbl )
    local tom,     # the table of marks
          fus,     # fusion map from `t' to `tom'
          perms;   # perm. characters of `t'

    if IsBound( tbl!.tomidentifier ) or HasUnderlyingGroup( tbl ) then
      tom:= TableOfMarks( tbl );
    else
      Error( "no table of marks for character table <tbl> available" );
    fi;
    fus:= FusionCharTableTom( tbl, tom );
    if ForAll( fus, IsInt ) then
      perms:= PermCharsTom( tbl, tom );
      return Filtered( perms,
                 x -> ForAll( Irr( tbl ),
                              y -> ScalarProduct( tbl, x, y ) <= 1 ) );
    else
      Error( "no unique fusion from <tbl> to the table of marks" );
    fi;
end );


############################################################################
##
#F  MultFree( <G>, <H> )
##
##  Let <G> and <H> be character tables of groups $G$ and $H$, respectively,
##  such that $H$ is a subgroup of $G$ and the class fusion from <H> to <G>
##  is stored on <H>.
##  `MultFree' returns the list of all multiplicity-free characters
##  $\varphi^G$ of $G$ such that $\varphi$ is a possible permutation
##  character of $H$.
##
BindGlobal( "MultFree", function( G, H )
    local triv,     # $1_H$
          permch,   # $(1_H)^G$
          scpr1H,   # decomposition of $(1_H)^G$
          rat,      # rational irreducible characters of $H$
          ind,      # induced rational irreducible characters
          mat,      # decomposition of `ind'
          allowed,  # indices of possible constituents
          S0,       # $S_0$
          scprS0,   # decomposition of characters in $S_0$,
                    # induced to $G$, with $Irr(G)$
          C,        # function that computes $C(S,\psi)$
          cand;     # list of multiplicity-free candidates, result

    # Compute $(1_H)^G$ and its decomposition.
    triv   := TrivialCharacter( H );
    permch := Induced( H, G, [ triv ] );
    scpr1H := MatScalarProducts( G, Irr( G ), permch )[1];

    # If $(1_H)^G$ is not multiplicity-free then we are done.
    if Maximum( scpr1H ) > 1 then
      return [];
    fi;

    # Compute the set $S_0$ of all possible nontrivial
    # rational constituents of a multiplicity free candidate,
    # that is, all those rational irreducible characters of
    # $H$ that induce multiplicity freely to $G$,
    # and orthogonal to $(1_H)^G$.
    rat:= RationalizedMat( Irr( H ) );
    ind:= Induced( H, G, rat );
    mat:= MatScalarProducts( G, Irr( G ), ind );
    allowed:= Filtered( [ 1.. Length( mat ) ],
                        x ->     mat[x] * scpr1H = 0
                             and Maximum( mat[x] ) = 1 );
    S0     := rat{ allowed };
    scprS0 := mat{ allowed };

    # Define the function that does the recursion.
    C:= function( S, psi, scprS, scprpsi )

      local chi,          # $\chi$
            scprchi,      # decomposition of $\chi^G$
            Sprime,       # $S^{\prime}$
            scprSprime,   # decomposition of characters in $S^{\prime}$,
                          # induced to $G$
            allowed;      # indices of possible constituents

      if IsEmpty( S ) then

        # Test whether `psi' is a possible permutation character.
        if     TestPerm1( H, psi ) = 0
           and TestPerm2( H, psi ) = 0
           and TestPerm3( H, [ psi ] ) <> [] then
          return [ psi ];
        else
          return [];
        fi;

      else

        # Construct the set $S^{\prime}$ for a character $\chi$.
        chi        := S[1];
        scprchi    := scprS[1];
        allowed    := Filtered( [ 2 .. Length( S ) ],
                                i -> Maximum( scprchi + scprS[i] ) <= 1 );
        Sprime     := S{ allowed };
        scprSprime := scprS{ allowed };

        # Enter the recursion.
        return Concatenation(
           C( Sprime, psi + chi,
              scprSprime, scprpsi + scprchi ),
           C( S{ [ 2 .. Length( S ) ] }, psi,
              scprS{ [ 2 .. Length( S ) ] }, scprpsi ) );

      fi;
    end;

    # Compute $C( S_0, 1_H )$.
    cand:= C( S0, triv, scprS0, scpr1H );

    # Induce the candidates to $G$, and return the sorted list.
    cand:= Induced( H, G, cand );
    Sort( cand );
    return cand;
end );


#############################################################################
##
#E