Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/lib/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 18.9.2025 mit Größe 18 kB image not shown  

Quelle  ctbllatt.gd   Sprache: unbekannt

 
Spracherkennung für: .gd vermutete Sprache: Unknown {[0] [0] [0]} [Methode: Schwerpunktbildung, einfache Gewichte, sechs Dimensionen]

#############################################################################
##
##  This file is part of GAP, a system for computational discrete algebra.
##  This file's authors include Thomas Breuer, Ansgar Kaup.
##
##  Copyright of GAP belongs to its developers, whose names are too numerous
##  to list here. Please refer to the COPYRIGHT file for details.
##
##  SPDX-License-Identifier: GPL-2.0-or-later
##
##  This file contains the declaration of functions that mainly deal with
##  lattices in the context of character tables.
##


#############################################################################
##
#F  LLL( <tbl>, <characters>[, <y>][, "sort"][, "linearcomb"] )
##
##  <#GAPDoc Label="LLL">
##  <ManSection>
##  <Func Name="LLL" Arg='tbl, characters[, y][, "sort"][, "linearcomb"]'/>
##
##  <Description>
##  <Index Subkey="for virtual characters">LLL algorithm</Index>
##  <Index>short vectors spanning a lattice</Index>
##  <Index Subkey="for virtual characters">lattice basis reduction</Index>
##  <Ref Func="LLL"/> calls the LLL algorithm
##  (see <Ref Func="LLLReducedBasis"/>) in the case of
##  lattices spanned by the virtual characters <A>characters</A>
##  of the ordinary character table <A>tbl</A>
##  (see <Ref Oper="ScalarProduct" Label="for characters"/>).
##  By finding shorter vectors in the lattice spanned by <A>characters</A>,
##  i.e., virtual characters of smaller norm,
##  in some cases <Ref Func="LLL"/> is able to find irreducible characters.
##  <P/>
##  <Ref Func="LLL"/> returns a record with at least components
##  <C>irreducibles</C> (the list of found irreducible characters),
##  <C>remainders</C> (a list of reducible virtual characters),
##  and <C>norms</C> (the list of norms of the vectors in <C>remainders</C>).
##  <C>irreducibles</C> together with <C>remainders</C> form a basis of the
##  <M>&ZZ;</M>-lattice spanned by <A>characters</A>.
##  <P/>
##  Note that the vectors in the <C>remainders</C> list are in general
##  <E>not</E> orthogonal (see <Ref Oper="ReducedClassFunctions"/>)
##  to the irreducible characters in <C>irreducibles</C>.
##  <P/>
##  Optional arguments of <Ref Func="LLL"/> are
##  <P/>
##  <List>
##  <Mark><A>y</A></Mark>
##  <Item>
##      controls the sensitivity of the algorithm,
##      see <Ref Func="LLLReducedBasis"/>,
##  </Item>
##  <Mark><A>"sort"</A></Mark>
##  <Item>
##      <Ref Func="LLL"/> sorts <A>characters</A> and the <C>remainders</C>
##      component of the result according to the degrees,
##  </Item>
##  <Mark><A>"linearcomb"</A></Mark>
##  <Item>
##      the returned record contains components <C>irreddecomp</C>
##      and <C>reddecomp</C>, which are decomposition matrices of
##      <C>irreducibles</C> and <C>remainders</C>,
##      with respect to <A>characters</A>.
##  </Item>
##  </List>
##  <P/>
##  <Example><![CDATA[
##  gap> s4:= CharacterTable( "Symmetric", 4 );;
##  gap> chars:= [ [ 800, -10 ], [ 60202 ],
##  >     [ 120, -400 ], [ 60, -200 ], [ 240000 ],
##  >     [ 120400 ], [ 6020, -2 ], [ 12, -2000 ],
##  >     [ 80020 ], [ 122000 ], [ 11111 ] ];;
##  gap> LLL( s4, chars );
##  rec(
##    irreducibles :=
##      [ Character( CharacterTable( "Sym(4)" ), [ 202, -10 ] ),
##        Character( CharacterTable( "Sym(4)" ), [ 11111 ] ),
##        Character( CharacterTable( "Sym(4)" ), [ 31, -10, -1 ] ),
##        Character( CharacterTable( "Sym(4)" ), [ 3, -1, -101 ] ),
##        Character( CharacterTable( "Sym(4)" ), [ 1, -111, -1 ] ) ],
##    norms := [  ], remainders := [  ] )
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareGlobalFunction( "LLL" );


#############################################################################
##
#F  Extract( <tbl>, <reducibles>, <grammat>[, <missing> ] )
##
##  <#GAPDoc Label="Extract">
##  <ManSection>
##  <Func Name="Extract" Arg='tbl, reducibles, grammat[, missing ]'/>
##
##  <Description>
##  Let <A>tbl</A> be an ordinary character table,
##  <A>reducibles</A> a list of characters of <A>tbl</A>,
##  and <A>grammat</A> the matrix of scalar products of <A>reducibles</A>
##  (see <Ref Oper="MatScalarProducts"/>).
##  <Ref Func="Extract"/> tries to find irreducible characters by drawing
##  conclusions out of the scalar products,
##  using combinatorial and backtrack means.
##  <P/>
##  The optional argument <A>missing</A> is the maximal number of irreducible
##  characters that occur as constituents of <A>reducibles</A>.
##  Specification of <A>missing</A> may accelerate <Ref Func="Extract"/>.
##  <P/>
##  <Ref Func="Extract"/> returns a record <A>ext</A> with the components
##  <C>solution</C> and <C>choice</C>,
##  where the value of <C>solution</C> is a list <M>[ M_1, \ldots, M_n ]</M>
##  of decomposition matrices <M>M_i</M> (up to permutations of rows)
##  with the property that <M>M_i^{tr} \cdot X</M> is equal to
##  the sublist at the positions <A>ext</A><C>.choice[i]</C> of
##  <A>reducibles</A>,
##  for a matrix <M>X</M> of irreducible characters;
##  the value of <C>choice</C> is a list of length <M>n</M> whose entries are
##  lists of indices.
##  <P/>
##  So the <M>j</M>-th column in each matrix <M>M_i</M> corresponds to
##  <M><A>reducibles</A>[j]</M>, and each row in <M>M_i</M> corresponds to an
##  irreducible character.
##  <Ref Func="Decreased"/> can be used to examine the solution for
##  computable irreducibles.
##  <P/>
##  <Example><![CDATA[
##  gap> s4:= CharacterTable( "Symmetric", 4 );;
##  gap> red:= [ [ 51521 ], [ 20220 ], [ 3, -130, -1 ],
##  >            [ 60, -200 ], [ 40012 ] ];;
##  gap> gram:= MatScalarProducts( s4, red, red );
##  [ [ 63202 ], [ 32101 ], [ 21200 ],
##    [ 00021 ], [ 21012 ] ]
##  gap> ext:= Extract( s4, red, gram, 5 );
##  rec( choice := [ [ 25341 ] ],
##    solution :=
##      [
##        [ [ 11002 ], [ 10101 ], [ 01010 ],
##            [ 00101 ], [ 00010 ] ] ] )
##  gap> dec:= Decreased( s4, red, ext.solution[1], ext.choice[1] );
##  rec(
##    irreducibles :=
##      [ Character( CharacterTable( "Sym(4)" ), [ 11111 ] ),
##        Character( CharacterTable( "Sym(4)" ), [ 3, -1, -101 ] ),
##        Character( CharacterTable( "Sym(4)" ), [ 1, -111, -1 ] ),
##        Character( CharacterTable( "Sym(4)" ), [ 31, -10, -1 ] ),
##        Character( CharacterTable( "Sym(4)" ), [ 202, -10 ] ) ],
##    matrix := [  ], remainders := [  ] )
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareGlobalFunction( "Extract" );


#############################################################################
##
#F  OrthogonalEmbeddingsSpecialDimension( <tbl>, <reducibles>, <grammat>,
#F                                                   ["positive",] <dim> )
##
##  <#GAPDoc Label="OrthogonalEmbeddingsSpecialDimension">
##  <ManSection>
##  <Func Name="OrthogonalEmbeddingsSpecialDimension"
##  Arg='tbl, reducibles, grammat[, "positive"], dim'/>
##
##  <Description>
##  <Ref Func="OrthogonalEmbeddingsSpecialDimension"/> is a variant of
##  <Ref Func="OrthogonalEmbeddings"/> for the situation
##  that <A>tbl</A> is an ordinary character table,
##  <A>reducibles</A> is a list of virtual characters of <A>tbl</A>,
##  <A>grammat</A> is the matrix of scalar products
##  (see <Ref Oper="MatScalarProducts"/>),
##  and <A>dim</A> is an upper bound for the number of irreducible characters
##  of <A>tbl</A> that occur as constituents of <A>reducibles</A>;
##  if the vectors in <A>reducibles</A> are known to be proper characters then
##  the string <C>"positive"</C> may be entered as fourth argument.
##  (See <Ref Func="OrthogonalEmbeddings"/> for information why this may
##  help.)
##  <P/>
##  <Ref Func="OrthogonalEmbeddingsSpecialDimension"/> first uses
##  <Ref Func="OrthogonalEmbeddings"/> to compute all orthogonal embeddings
##  of <A>grammat</A> into a standard lattice of dimension up to <A>dim</A>,
##  and then calls <Ref Func="Decreased"/> in order to find irreducible
##  characters of <A>tbl</A>.
##  <P/>
##  <Ref Func="OrthogonalEmbeddingsSpecialDimension"/> returns a record with
##  the following components.
##  <P/>
##  <List>
##  <Mark><C>irreducibles</C></Mark>
##  <Item>
##    a list of found irreducibles, the intersection of all lists of
##    irreducibles found by <Ref Func="Decreased"/>,
##    for all possible embeddings, and
##  </Item>
##  <Mark><C>remainders</C></Mark>
##  <Item>
##    a list of remaining reducible virtual characters.
##  </Item>
##  </List>
##  <P/>
##  <Example><![CDATA[
##  gap> s6:= CharacterTable( "S6" );;
##  gap> red:= InducedCyclic( s6, "all" );;
##  gap> Add( red, TrivialCharacter( s6 ) );
##  gap> lll:= LLL( s6, red );;
##  gap> irred:= lll.irreducibles;
##  [ Character( CharacterTable( "A6.2_1" ),
##      [ 11111111111 ] ),
##    Character( CharacterTable( "A6.2_1" ),
##      [ 91001, -1, -3, -3100 ] ),
##    Character( CharacterTable( "A6.2_1" ),
##      [ 160, -2, -20100000 ] ) ]
##  gap> Set( Flat( MatScalarProducts( s6, irred, lll.remainders ) ) );
##  [ 0 ]
##  gap> dim:= NrConjugacyClasses( s6 ) - Length( lll.irreducibles );
##  8
##  gap> rem:= lll.remainders;;  Length( rem );
##  8
##  gap> gram:= MatScalarProducts( s6, rem, rem );;  RankMat( gram );
##  8
##  gap> emb1:= OrthogonalEmbeddings( gram, 8 );
##  rec( norms := [ 1111111111111111 ],
##    solutions := [ [ 123711121315 ],
##        [ 124810121314 ], [ 12569121316 ] ],
##    vectors :=
##      [ [ -10101010 ], [ 10010100 ],
##        [ 01100011 ], [ 01100010 ],
##        [ 01100000 ], [ 01000010 ],
##        [ 0, -1000001 ], [ 01000000 ],
##        [ 00100011 ], [ 00100001 ],
##        [ 00100000 ], [ 000, -11000 ],
##        [ 00000100 ], [ 00000011 ],
##        [ 00000010 ], [ 00000001 ] ] )
##  gap> emb2:= OrthogonalEmbeddingsSpecialDimension( s6, rem, gram, 8 );
##  rec(
##    irreducibles :=
##      [ Character( CharacterTable( "A6.2_1" ),
##          [ 51, -12, -101, -3, -110 ] ),
##        Character( CharacterTable( "A6.2_1" ),
##          [ 512, -1, -10, -31, -101 ] ),
##        Character( CharacterTable( "A6.2_1" ),
##          [ 10, -21100, -2201, -1 ] ),
##        Character( CharacterTable( "A6.2_1" ),
##          [ 10, -211002, -20, -11 ] ) ],
##    remainders :=
##      [ VirtualCharacter( CharacterTable( "A6.2_1" ),
##          [ 003, -3004, -401, -1 ] ),
##        VirtualCharacter( CharacterTable( "A6.2_1" ),
##          [ 6230012, -20, -1, -2 ] ),
##        VirtualCharacter( CharacterTable( "A6.2_1" ),
##          [ 102112022, -2, -1, -1 ] ),
##        VirtualCharacter( CharacterTable( "A6.2_1" ),
##          [ 1422, -10, -16200, -1 ] ) ] )
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareGlobalFunction( "OrthogonalEmbeddingsSpecialDimension" );


#############################################################################
##
#F  Decreased( <tbl>, <chars>, <decompmat>[, <choice>] )
##
##  <#GAPDoc Label="Decreased">
##  <ManSection>
##  <Func Name="Decreased" Arg='tbl, chars, decompmat[, choice]'/>
##
##  <Description>
##  Let <A>tbl</A> be an ordinary character table,
##  <A>chars</A> a list of virtual characters of <A>tbl</A>,
##  and <A>decompmat</A> a decomposition matrix, that is,
##  a matrix <M>M</M> with the property that
##  <M>M^{tr} \cdot X = <A>chars</A></M> holds,
##  where <M>X</M> is a list of irreducible characters of <A>tbl</A>.
##  <Ref Func="Decreased"/> tries to compute the irreducibles in <M>X</M> or
##  at least some of them.
##  <P/>
##  Usually <Ref Func="Decreased"/> is applied to the output of
##  <Ref Func="Extract"/> or <Ref Func="OrthogonalEmbeddings"/> or
##  <Ref Func="OrthogonalEmbeddingsSpecialDimension"/>.
##  In the case of <Ref Func="Extract"/>,
##  the choice component corresponding to the decomposition matrix must be
##  entered as argument <A>choice</A> of <Ref Func="Decreased"/>.
##  <P/>
##  <Ref Func="Decreased"/> returns <K>fail</K> if it can prove that no list
##  <M>X</M> of irreducible characters corresponding to the arguments exists;
##  otherwise <Ref Func="Decreased"/> returns a record with the following
##  components.
##  <P/>
##  <List>
##  <Mark><C>irreducibles</C></Mark>
##  <Item>
##      the list of found irreducible characters,
##  </Item>
##  <Mark><C>remainders</C></Mark>
##  <Item>
##      the remaining reducible characters, and
##  </Item>
##  <Mark><C>matrix</C></Mark>
##  <Item>
##      the decomposition matrix of the characters in the <C>remainders</C>
##      component.
##  </Item>
##  </List>
##  <P/>
##  <Example><![CDATA[
##  gap> s4:= CharacterTable( "Symmetric", 4 );;
##  gap> x:= Irr( s4 );;
##  gap> red:= [ x[1]+x[2], -x[1]-x[3], -x[1]+x[3], -x[2]-x[4] ];;
##  gap> mat:= MatScalarProducts( s4, red, red );
##  [ [ 2, -1, -1, -1 ], [ -1200 ], [ -1020 ],
##    [ -1002 ] ]
##  gap> emb:= OrthogonalEmbeddings( mat );
##  rec( norms := [ 111111111111 ],
##    solutions := [ [ 16712 ], [ 25811 ], [ 34910 ] ],
##    vectors := [ [ -1110 ], [ -1101 ], [ 1, -100 ],
##        [ -1011 ], [ -1010 ], [ -1001 ],
##        [ 0, -110 ], [ 0, -101 ], [ 0100 ],
##        [ 00, -11 ], [ 0010 ], [ 0001 ] ] )
##  gap> dec:= Decreased( s4, red, emb.vectors{ emb.solutions[1] } );
##  rec(
##    irreducibles :=
##      [ Character( CharacterTable( "Sym(4)" ), [ 3, -1, -101 ] ),
##        Character( CharacterTable( "Sym(4)" ), [ 1, -111, -1 ] ),
##        Character( CharacterTable( "Sym(4)" ), [ 202, -10 ] ),
##        Character( CharacterTable( "Sym(4)" ), [ 31, -10, -1 ] ) ],
##    matrix := [  ], remainders := [  ] )
##  gap> Decreased( s4, red, emb.vectors{ emb.solutions[2] } );
##  fail
##  gap> Decreased( s4, red, emb.vectors{ emb.solutions[3] } );
##  fail
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareGlobalFunction( "Decreased" );


#############################################################################
##
#F  DnLattice( <tbl>, <grammat>, <reducibles> )
##
##  <#GAPDoc Label="DnLattice">
##  <ManSection>
##  <Func Name="DnLattice" Arg='tbl, grammat, reducibles'/>
##
##  <Description>
##  Let <A>tbl</A> be an ordinary character table,
##  and <A>reducibles</A> a list of virtual characters of <A>tbl</A>.
##  <P/>
##  <Ref Func="DnLattice"/> searches for sublattices isomorphic to root
##  lattices of type <M>D_n</M>, for <M>n \geq 4</M>,
##  in the lattice that is generated by <A>reducibles</A>;
##  each vector in <A>reducibles</A> must have norm <M>2</M>, and the matrix
##  of scalar products (see <Ref Oper="MatScalarProducts"/>) of
##  <A>reducibles</A> must be entered as argument <A>grammat</A>.
##  <P/>
##  <Ref Func="DnLattice"/> is able to find irreducible characters if there
##  is a lattice of type <M>D_n</M> with <M>n > 4</M>.
##  In the case <M>n = 4</M>, <Ref Func="DnLattice"/> may fail to determine
##  irreducibles.
##  <P/>
##  <Ref Func="DnLattice"/> returns a record with components
##  <List>
##  <Mark><C>irreducibles</C></Mark>
##  <Item>
##      the list of found irreducible characters,
##  </Item>
##  <Mark><C>remainders</C></Mark>
##  <Item>
##      the list of remaining reducible virtual characters, and
##  </Item>
##  <Mark><C>gram</C></Mark>
##  <Item>
##      the Gram matrix of the vectors in <C>remainders</C>.
##  </Item>
##  </List>
##  <P/>
##  The <C>remainders</C> list is transformed in such a way that the
##  <C>gram</C> matrix is a block diagonal matrix that exhibits the structure
##  of the lattice generated by the vectors in <C>remainders</C>.
##  So <Ref Func="DnLattice"/> might be useful even if it fails to find
##  irreducible characters.
##  <P/>
##  <Example><![CDATA[
##  gap> s4:= CharacterTable( "Symmetric", 4 );;
##  gap> red:= [ [ 20220 ], [ 40012 ],
##  >            [ 5, -11, -11 ], [ -113, -1, -1 ] ];;
##  gap> gram:= MatScalarProducts( s4, red, red );
##  [ [ 2100 ], [ 121, -1 ], [ 0120 ], [ 0, -102 ] ]
##  gap> dn:= DnLattice( s4, gram, red );
##  rec( gram := [  ],
##    irreducibles :=
##      [ Character( CharacterTable( "Sym(4)" ), [ 202, -10 ] ),
##        Character( CharacterTable( "Sym(4)" ), [ 1, -111, -1 ] ),
##        Character( CharacterTable( "Sym(4)" ), [ 11111 ] ),
##        Character( CharacterTable( "Sym(4)" ), [ 3, -1, -101 ] ) ],
##    remainders := [  ] )
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareGlobalFunction( "DnLattice" );


#############################################################################
##
#F  DnLatticeIterative( <tbl>, <reducibles> )
##
##  <#GAPDoc Label="DnLatticeIterative">
##  <ManSection>
##  <Func Name="DnLatticeIterative" Arg='tbl, reducibles'/>
##
##  <Description>
##  Let <A>tbl</A> be an ordinary character table,
##  and <A>reducibles</A> either a list of virtual characters of <A>tbl</A>
##  or a record with components <C>remainders</C> and <C>norms</C>,
##  for example a record returned by <Ref Func="LLL"/>.
##  <P/>
##  <Ref Func="DnLatticeIterative"/> was designed for iterative use of
##  <Ref Func="DnLattice"/>.
##  <Ref Func="DnLatticeIterative"/> selects the vectors of norm <M>2</M>
##  among the given virtual character, calls <Ref Func="DnLattice"/> for
##  them, reduces the virtual characters with found irreducibles,
##  calls <Ref Func="DnLattice"/> again for the remaining virtual characters,
##  and so on, until no new irreducibles are found.
##  <P/>
##  <Ref Func="DnLatticeIterative"/> returns a record with the same
##  components and meaning of components as <Ref Func="LLL"/>.
##  <P/>
##  <Example><![CDATA[
##  gap> s4:= CharacterTable( "Symmetric", 4 );;
##  gap> red:= [ [ 20220 ], [ 40012 ],
##  >            [ 5, -11, -11 ], [ -113, -1, -1 ] ];;
##  gap> dn:= DnLatticeIterative( s4, red );
##  rec(
##    irreducibles :=
##      [ Character( CharacterTable( "Sym(4)" ), [ 202, -10 ] ),
##        Character( CharacterTable( "Sym(4)" ), [ 1, -111, -1 ] ),
##        Character( CharacterTable( "Sym(4)" ), [ 11111 ] ),
##        Character( CharacterTable( "Sym(4)" ), [ 3, -1, -101 ] ) ],
##    norms := [  ], remainders := [  ] )
##  ]]></Example>
##  </Description>
##  </ManSection>
##  <#/GAPDoc>
##
DeclareGlobalFunction( "DnLatticeIterative" );

[Dauer der Verarbeitung: 0.21 Sekunden, vorverarbeitet 2026-06-10]