1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436
|
#############################################################################
##
#W ctblmaps.gd GAP library Thomas Breuer
##
#H @(#)$Id: ctblmaps.gd,v 4.32.2.1 2005/05/09 08:49:08 gap Exp $
##
#Y Copyright (C) 1997, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany
#Y (C) 1998 School Math and Comp. Sci., University of St. Andrews, Scotland
#Y Copyright (C) 2002 The GAP Group
##
## This file contains the declaration of those functions that are used
## to construct maps (mostly fusion maps and power maps).
##
## 1. Maps Concerning Character Tables
## 2. Power Maps
## 3. Class Fusions between Character Tables
## 4. Utilities for Parametrized Maps
## 5. Subroutines for the Construction of Power Maps
## 6. Subroutines for the Construction of Class Fusions
##
Revision.ctblmaps_gd :=
"@(#)$Id: ctblmaps.gd,v 4.32.2.1 2005/05/09 08:49:08 gap Exp $";
#############################################################################
##
## 1. Maps Concerning Character Tables
#1
## Besides the characters, *power maps* (see~"Power Maps") are an important
## part of a character table.
## Often their computation is not easy, and if the table has no access to
## the underlying group then in general they cannot be obtained from the
## matrix of irreducible characters;
## so it is useful to store them on the table.
##
## If not only a single table is considered but different tables of a group
## and a subgroup or of a group and a factor group are used,
## also *class fusion maps* (see~"Class Fusions between Character Tables")
## must be known to get information about the embedding or simply to induce
## or restrict characters (see~"Restricted and Induced Class Functions").
##
## These are examples of functions from conjugacy classes which will be
## called *maps* in the following.
## (This should not be confused with the term mapping, see~"Mappings".)
## In {\GAP}, maps are represented by lists.
## Also each character, each list of element orders, centralizer orders,
## or class lengths are maps,
## and for a permutation <perm> of classes, `ListPerm( <perm> )' is a map.
##
## When maps are constructed without access to a group, often one only knows
## that the image of a given class is contained in a set of possible images,
## e.g., that the image of a class under a subgroup fusion is in the set of
## all classes with the same element order.
## Using further information, such as centralizer orders, power maps and the
## restriction of characters, the sets of possible images can be restricted
## further.
## In many cases, at the end the images are uniquely determined.
##
## Because of this approach, many functions in this chapter work not only
## with maps but with *parametrized maps* (or paramaps for short).
## More about parametrized maps can be found in Section~"Parametrized Maps".
##
## The implementation follows~\cite{Bre91},
## a description of the main ideas together with several examples
## can be found in~\cite{Bre99}.
##
#############################################################################
##
## 2. Power Maps
#2
## The $n$-th power map of a character table is represented by a list that
## stores at position $i$ the position of the class containing the $n$-th
## powers of the elements in the $i$-th class.
## The $n$-th power map can be composed from the power maps of the prime
## divisors $p$ of $n$,
## so usually only power maps for primes $p$ are actually stored in the
## character table.
##
## For an ordinary character table <tbl> with access to its underlying group
## $G$,
## the $p$-th power map of <tbl> can be computed using the identification of
## the conjugacy classes of $G$ with the classes of <tbl>.
## For an ordinary character table without access to a group,
## in general the $p$-th power maps (and hence also the element orders) for
## prime divisors $p$ of the group order are not uniquely determined
## by the matrix of irreducible characters.
## So only necessary conditions can be checked in this case,
## which in general yields only a list of several possibilities for the
## desired power map.
## Character tables of the {\GAP} character table library store all $p$-th
## power maps for prime divisors $p$ of the group order.
##
## Power maps of Brauer tables can be derived from the power maps of the
## underlying ordinary tables.
##
## For (computing and) accessing the $n$-th power map of a character table,
## `PowerMap' (see~"PowerMap") can be used;
## if the $n$-th power map cannot be uniquely determined then `PowerMap'
## returns `fail'.
##
## The list of all possible $p$-th power maps of a table in the sense that
## certain necessary conditions are satisfied can be computed with
## `PossiblePowerMaps' (see~"PossiblePowerMaps").
## This provides a default strategy, the subroutines are listed in
## Section~"Subroutines for the Construction of Power Maps".
##
#############################################################################
##
#O PowerMap( <tbl>, <n>[, <class>] )
#O PowerMapOp( <tbl>, <n>[, <class>] )
#A ComputedPowerMaps( <tbl> )
##
## Called with first argument a character table <tbl> and second argument an
## integer <n>,
## `PowerMap' returns the <n>-th power map of <tbl>.
## This is a list containing at position $i$ the position of the class of
## <n>-th powers of the elements in the $i$-th class of <tbl>.
##
## If the additional third argument <class> is present then the position of
## <n>-th powers of the <class>-th class is returned.
##
## If the <n>-th power map is not uniquely determined by <tbl> then `fail'
## is returned.
## This can happen only if <tbl> has no access to its underlying group.
##
## The power maps of <tbl> that were computed already by `PowerMap'
## are stored in <tbl> as value of the attribute `ComputedPowerMaps',
## the $n$-th power map at position $n$.
## `PowerMap' checks whether the desired power map is already stored,
## computes it using the operation `PowerMapOp' if it is not yet known,
## and stores it.
## So methods for the computation of power maps can be installed for
## the operation `PowerMapOp'.
##
## % For power maps of groups, see~"PowerMapOfGroup".
##
DeclareOperation( "PowerMap", [ IsNearlyCharacterTable, IsInt ] );
DeclareOperation( "PowerMap", [ IsNearlyCharacterTable, IsInt, IsInt ] );
DeclareOperation( "PowerMapOp", [ IsNearlyCharacterTable, IsInt ] );
DeclareOperation( "PowerMapOp", [ IsNearlyCharacterTable, IsInt, IsInt ] );
DeclareAttributeSuppCT( "ComputedPowerMaps",
IsNearlyCharacterTable, "mutable", [ "class" ] );
#############################################################################
##
#O PossiblePowerMaps( <tbl>, <p>[, <options>] )
##
## For the ordinary character table <tbl> of the group $G$, say,
## and a prime integer <p>,
## `PossiblePowerMaps' returns the list of all maps that have the following
## properties of the $p$-th power map of <tbl>.
## (Representative orders are used only if the `OrdersClassRepresentatives'
## value of <tbl> is known, see~"OrdersClassRepresentatives".)
## \beginlist%ordered
## \item{1.}
## For class $i$, the centralizer order of the image is a multiple of
## the $i$-th centralizer order;
## if the elements in the $i$-th class have order coprime to $p$
## then the centralizer orders of class $i$ and its image are equal.
## \item{2.}
## Let $n$ be the order of elements in class $i$.
## If <prime> divides $n$ then the images have order $n/p$;
## otherwise the images have order $n$.
## These criteria are checked in `InitPowerMap' (see~"InitPowerMap").
## \item{3.}
## For each character $\chi$ of $G$ and each element $g$ in $G$,
## the values $\chi(g^p)$ and $`GaloisCyc'( \chi(g), p )$ are
## algebraic integers that are congruent modulo $p$;
## if $p$ does not divide the element order of $g$ then the two values
## are equal.
## This congruence is checked for the characters specified below in
## the discussion of the <options> argument;
## For linear characters $\lambda$ among these characters,
## the condition $\chi(g)^p = \chi(g^p)$ is checked.
## The corresponding function is `Congruences'
## (see~"Congruences!for character tables").
## \item{4.}
## For each character $\chi$ of $G$, the kernel is a normal subgroup
## $N$, and $g^p \in N$ for all $g \in N$;
## moreover, if $N$ has index $p$ in $G$ then $g^p \in N$ for all
## $g \in G$, and if the index of $N$ in $G$ is coprime to $p$ then
## $g^p \not\in N$ for each $g \not\in N$.
## These conditions are checked for the kernels of all characters
## $\chi$ specified below,
## the corresponding function is `ConsiderKernels'
## (see~"ConsiderKernels").
## \item{5.}
## If $p$ is larger than the order $m$ of an element $g \in G$ then
## the class of $g^p$ is determined by the power maps for primes
## dividing the residue of $p$ modulo $m$.
## If these power maps are stored in the `ComputedPowerMaps' value
## (see~"ComputedPowerMaps") of <tbl> then this information is used.
## This criterion is checked in `ConsiderSmallerPowerMaps'
## (see~"ConsiderSmallerPowerMaps").
## \item{6.}
## For each character $\chi$ of $G$, the symmetrization $\psi$
## defined by $\psi(g) = (\chi(g)^p - \chi(g^p))/p$ is a character.
## This condition is checked for the kernels of all characters
## $\chi$ specified below,
## the corresponding function is `PowerMapsAllowedBySymmetrizations'
## (see~"PowerMapsAllowedBySymmetrizations").
## \endlist
##
## If <tbl> is a Brauer table, the possibilities are computed from those for
## the underlying ordinary table.
##
## The optional argument <options> must be a record that may have the
## following components:
## \beginitems
## `chars': &
## a list of characters which are used for the check of the criteria
## 3., 4., and 6.;
## the default is `Irr( <tbl> )',
##
## `powermap': &
## a parametrized map which is an approximation of the desired map
##
## `decompose': &
## a Boolean;
## a `true' value indicates that all constituents of the
## symmetrizations of `chars' computed for criterion 6. lie in `chars',
## so the symmetrizations can be decomposed into elements of `chars';
## the default value of `decompose' is `true' if `chars' is not bound
## and `Irr( <tbl> )' is known, otherwise `false',
##
## `quick': &
## a Boolean;
## if `true' then the subroutines are called with value `true' for
## the argument <quick>;
## especially, as soon as only one possibility remains
## this possibility is returned immediately;
## the default value is `false',
##
## `parameters': &
## a record with components `maxamb', `minamb' and `maxlen' which
## control the subroutine `PowerMapsAllowedBySymmetrizations';
## it only uses characters with current indeterminateness up to
## `maxamb',
## tests decomposability only for characters with current
## indeterminateness at least `minamb',
## and admits a branch according to a character only if there is one
## with at most `maxlen' possible symmetrizations.
## \enditems
##
DeclareOperation( "PossiblePowerMaps", [ IsCharacterTable, IsInt ] );
DeclareOperation( "PossiblePowerMaps", [ IsCharacterTable, IsInt,
IsRecord ] );
#############################################################################
##
#F ElementOrdersPowerMap( <powermap> )
##
## Let <powermap> be a nonempty list containing at position $p$, if bound,
## the $p$-th power map of a character table or group.
## `ElementOrdersPowerMap' returns a list of the same length as each entry
## in <powermap>, with entry at position $i$ equal to the order of elements
## in class $i$ if this order is uniquely determined by <powermap>,
## and equal to an unknown (see Chapter~"Unknowns") otherwise.
##
DeclareGlobalFunction( "ElementOrdersPowerMap" );
#############################################################################
##
#F PowerMapByComposition( <tbl>, <n> ) . . for char. table and pos. integer
##
## <tbl> must be a nearly character table, and <n> a positive integer.
## If the power maps for all prime divisors of <n> are stored in the
## `ComputedPowerMaps' list of <tbl> then `PowerMapByComposition' returns
## the <n>-th power map of <tbl>.
## Otherwise `fail' is returned.
##
DeclareGlobalFunction( "PowerMapByComposition" );
#############################################################################
##
#3
## The permutation group of matrix automorphisms (see~"MatrixAutomorphisms")
## acts on the possible power maps returned by `PossiblePowerMaps'
## (see~"PossiblePowerMaps")
## by permuting a list via `Permuted' (see~"Permuted")
## and then mapping the images via `OnPoints' (see~"OnPoints").
## Note that by definition, the group of table automorphisms acts trivially.
##
#############################################################################
##
#F OrbitPowerMaps( <map>, <permgrp> )
##
## returns the orbit of the power map <map> under the action of the
## permutation group <permgrp>
## via a combination of `Permuted' (see~"Permuted") and `OnPoints'
## (see~"OnPoints").
##
DeclareGlobalFunction( "OrbitPowerMaps" );
#############################################################################
##
#F RepresentativesPowerMaps( <listofmaps>, <permgrp> )
##
## returns a list of orbit representatives of the power maps in the list
## <listofmaps> under the action of the permutation group <permgrp>
## via a combination of `Permuted' (see~"Permuted") and `OnPoints'
## (see~"OnPoints").
##
DeclareGlobalFunction( "RepresentativesPowerMaps" );
#############################################################################
##
## 3. Class Fusions between Character Tables
#4
## For a group $G$ and a subgroup $H$ of $G$,
## the fusion map between the character table of $H$ and the character table
## of $G$ is represented by a list that stores at position $i$ the position
## of the $i$-th class of the table of $H$ in the classes list of the table
## of $G$.
##
## For ordinary character tables <tbl1> and <tbl2> of $H$ and $G$,
## with access to the groups $H$ and $G$,
## the class fusion between <tbl1> and <tbl2> can be computed using the
## identifications of the conjugacy classes of $H$ with the classes of
## <tbl1> and the conjugacy classes of $G$ with the classes of <tbl2>.
## For two ordinary character tables without access to its underlying group,
## or in the situation that the group stored in <tbl1> is not physically a
## subgroup of the group stored in <tbl2> but an isomorphic copy,
## in general the class fusion is not uniquely determined by the information
## stored on the tables such as irreducible characters and power maps.
## So only necessary conditions can be checked in this case,
## which in general yields only a list of several possibilities for the
## desired class fusion.
## Character tables of the {\GAP} character table library store various
## class fusions that are regarded as important,
## for example fusions from maximal subgroups (see~"ComputedClassFusions"
## and "ctbllib:Maxes" in the manual for the {\GAP} Character Table Library).
##
## Class fusions between Brauer tables can be derived from the class fusions
## between the underlying ordinary tables.
## The class fusion from a Brauer table to the underlying ordinary table is
## stored when the Brauer table is constructed from the ordinary table,
## so no method is needed to compute such a fusion.
##
## For (computing and) accessing the class fusion between two character
## tables,
## `FusionConjugacyClasses' (see~"FusionConjugacyClasses") can be used;
## if the class fusion cannot be uniquely determined then
## `FusionConjugacyClasses' returns `fail'.
##
## The list of all possible class fusion between two tables in the sense
## that certain necessary conditions are satisfied can be computed with
## `PossibleClassFusions' (see~"PossibleClassFusions").
## This provides a default strategy, the subroutines are listed in
## Section~"Subroutines for the Construction of Class Fusions".
##
## It should be noted that all the following functions except
## `FusionConjugacyClasses' (see~"FusionConjugacyClasses")
## deal only with the situation of class fusions from subgroups.
## The computation of *factor fusions* from a character table to the table
## of a factor group is not dealt with here.
## Since the ordinary character table of a group $G$ determines the
## character tables of all factor groups of $G$, the factor fusion to a
## given character table of a factor group of $G$ is determined up to table
## automorphisms (see~"AutomorphismsOfTable") once the class positions of
## the kernel of the natural epimorphism have been fixed.
##
#############################################################################
##
#O FusionConjugacyClasses( <tbl1>, <tbl2> )
#O FusionConjugacyClasses( <H>, <G> )
#O FusionConjugacyClasses( <hom>[, <tbl1>, <tbl2>] )
#O FusionConjugacyClassesOp( <tbl1>, <tbl2> )
#A FusionConjugacyClassesOp( <hom> )
##
## Called with two character tables <tbl1> and <tbl2>,
## `FusionConjugacyClasses' returns the fusion of conjugacy classes between
## <tbl1> and <tbl2>.
## (If one of the tables is a Brauer table,
## it will delegate this task to the underlying ordinary table.)
##
## Called with two groups <H> and <G> where <H> is a subgroup of <G>,
## `FusionConjugacyClasses' returns the fusion of conjugacy classes between
## <H> and <G>.
## This is done by delegating to the ordinary character tables of <H> and
## <G>,
## since class fusions are stored only for character tables and not for
## groups.
##
## Note that the returned class fusion refers to the ordering of conjugacy
## classes in the character tables if the arguments are character tables
## and to the ordering of conjugacy classes in the groups if the arguments
## are groups (see~"ConjugacyClasses!for character tables").
##
## Called with a group homomorphism <hom>,
## `FusionConjugacyClasses' returns the fusion of conjugacy classes between
## the preimage and the image of <hom>;
## contrary to the two cases above,
## also factor fusions can be handled by this variant.
## If <hom> is the only argument then the class fusion refers to the
## ordering of conjugacy classes in the groups.
## If the character tables of preimage and image are given as <tbl1> and
## <tbl2>, respectively (each table with its group stored),
## then the fusion refers to the ordering of classes in these tables.
##
## If no class fusion exists or if the class fusion is not uniquely
## determined, `fail' is returned;
## this may happen when `FusionConjugacyClasses' is called with two
## character tables that do not know compatible underlying groups.
##
## Methods for the computation of class fusions can be installed for
## the operation `FusionConjugacyClassesOp'.
##
DeclareOperation( "FusionConjugacyClasses",
[ IsNearlyCharacterTable, IsNearlyCharacterTable ] );
DeclareOperation( "FusionConjugacyClasses", [ IsGroup, IsGroup ] );
DeclareOperation( "FusionConjugacyClasses", [ IsGeneralMapping ] );
DeclareOperation( "FusionConjugacyClasses",
[ IsGeneralMapping, IsNearlyCharacterTable, IsNearlyCharacterTable ] );
DeclareAttribute( "FusionConjugacyClassesOp", IsGeneralMapping );
DeclareOperation( "FusionConjugacyClassesOp",
[ IsNearlyCharacterTable, IsNearlyCharacterTable ] );
DeclareOperation( "FusionConjugacyClassesOp",
[ IsGeneralMapping, IsNearlyCharacterTable, IsNearlyCharacterTable ] );
#############################################################################
##
#A ComputedClassFusions( <tbl> )
##
## The class fusions from the character table <tbl> that have been computed
## already by `FusionConjugacyClasses' (see~"FusionConjugacyClasses") or
## explicitly stored by `StoreFusion' (see~"StoreFusion")
## are stored in the `ComputedClassFusions' list of <tbl1>.
## Each entry of this list is a record with the following components.
## \beginitems
## `name' &
## the `Identifier' value of the character table to which the fusion
## maps,
##
## `map' &
## the list of positions of image classes,
##
## `text' (optional) &
## a string giving additional information about the fusion map,
## for example whether the map is uniquely determined by the character
## tables,
##
## `specification' (optional, rarely used) &
## a value that distinguishes different fusions between the same tables.
## \enditems
##
## Note that stored fusion maps may differ from the maps returned by
## `GetFusionMap' and the maps entered by `StoreFusion' if the table
## <destination> has a nonidentity `ClassPermutation' value.
## So if one fetches a fusion map from a table <tbl1> to a table <tbl2>
## via access to the data in the `ComputedFusionMaps' list <tbl1> then the
## stored value must be composed with the `ClassPermutation' value of <tbl2>
## in order to obtain the correct class fusion.
## (If one handles fusions only via `GetFusionMap' and `StoreFusion'
## (see~"GetFusionMap", "StoreFusion") then this adjustment is made
## automatically.)
##
## Fusions are identified via the `Identifier' value of the destination
## table and not by this table itself because many fusions between
## character tables in the {\GAP} character table library are stored on
## library tables, and it is not desirable to load together with a library
## table also all those character tables that occur as destinations of
## fusions from this table.
##
## For storing fusions and accessing stored fusions,
## see also~"GetFusionMap", "StoreFusion".
## For accessing the identifiers of tables that store a fusion into a
## given character table, see~"NamesOfFusionSources".
##
DeclareAttributeSuppCT( "ComputedClassFusions",
IsNearlyCharacterTable, "mutable", [ "class" ] );
#############################################################################
##
#F GetFusionMap( <source>, <destination> )
#F GetFusionMap( <source>, <destination>, <specification> )
##
## For two ordinary character tables <source> and <destination>,
## `GetFusionMap' checks whether the `ComputedClassFusion' list of <source>
## (see~"ComputedClassFusions") contains a record with `name' component
## `Identifier( <destination> )', and returns returns the `map' component
## of the first such record.
## `GetFusionMap( <source>, <destination>, <specification> )' fetches
## that fusion map for which the record additionally has the `specification'
## component <specification>.
##
## If both <source> and <destination> are Brauer tables,
## first the same is done, and if no fusion map was found then
## `GetFusionMap' looks whether a fusion map between the ordinary tables
## is stored; if so then the fusion map between <source> and <destination>
## is stored on <source>, and then returned.
##
## If no appropriate fusion is found, `GetFusionMap' returns `fail'.
## For the computation of class fusions, see~"FusionConjugacyClasses".
##
DeclareGlobalFunction( "GetFusionMap" );
#############################################################################
##
#F StoreFusion( <source>, <fusion>, <destination> )
##
## For two character tables <source> and <destination>,
## `StoreFusion' stores the fusion <fusion> from <source> to <destination>
## in the `ComputedClassFusions' list (see~"ComputedClassFusions")
## of <source>,
## and adds the `Identifier' string of <destination> to the
## `NamesOfFusionSources' list (see~`NamesOfFusionSources')
## of <destination>.
##
## <fusion> can either be a fusion map (that is, the list of positions of
## the image classes) or a record as described in~"ComputedClassFusions".
##
## If fusions to <destination> are already stored on <source> then
## another fusion can be stored only if it has a record component
## `specification' that distinguishes it from the stored fusions.
## In the case of such an ambiguity, `StoreFusion' raises an error.
##
DeclareGlobalFunction( "StoreFusion" );
#############################################################################
##
#A NamesOfFusionSources( <tbl> )
##
## For a character table <tbl>, `NamesOfFusionSources' returns the list of
## identifiers of all those character tables that are known to have fusions
## to <tbl> stored.
## The `NamesOfFusionSources' value is updated whenever a fusion to <tbl>
## is stored using `StoreFusion' (see~"StoreFusion").
##
DeclareAttributeSuppCT( "NamesOfFusionSources",
IsNearlyCharacterTable, "mutable", [] );
#############################################################################
##
#O PossibleClassFusions( <subtbl>, <tbl>[, <options>] )
##
## For two ordinary character tables <subtbl> and <tbl> of the groups $H$
## and $G$, say,
## `PossibleClassFusions' returns the list of all maps that have the
## following properties of class fusions from <subtbl> to <tbl>.
## \beginlist%ordered
## \item{1.}
## For class $i$, the centralizer order of the image in $G$ is a
## multiple of the $i$-th centralizer order in $H$,
## and the element orders in the $i$-th class and its image are equal.
## These criteria are checked in `InitFusion' (see~"InitFusion").
## \item{2.}
## The class fusion commutes with power maps.
## This is checked using `TestConsistencyMaps'
## (see~"TestConsistencyMaps").
## \item{3.}
## If the permutation character of $G$ corresponding to the action of
## $G$ on the cosets of $H$ is specified (see the discussion of the
## <options> argument below) then it prescribes for each class $C$ of
## $G$ the number of elements of $H$ fusing into $C$.
## The corresponding function is `CheckPermChar'
## (see~"CheckPermChar").
## \item{4.}
## The table automorphisms of <tbl> (see~"AutomorphismsOfTable") are
## used in order to compute only orbit representatives.
## (But note that the list returned by `PossibleClassFusions' contains
## the full orbits.)
## \item{5.}
## For each character $\chi$ of $G$, the restriction to $H$ via the
## class fusion is a character of $H$.
## This condition is checked for all characters specified below,
## the corresponding function is `FusionsAllowedByRestrictions'
## (see~"FusionsAllowedByRestrictions").
## \item{6.}
## The class multiplication coefficients in <subtbl> do not exceed the
## corresponding coefficients in <tbl>.
## This is checked in `ConsiderStructureConstants'
## (see~"ConsiderStructureConstants", and see also the comment on the
## parameter `verify' below).
## \endlist
##
## If <subtbl> and <tbl> are Brauer tables then the possibilities are
## computed from those for the underlying ordinary tables.
##
## The optional argument <options> must be a record that may have the
## following components:
## \beginitems
## `chars' &
## a list of characters of <tbl> which are used for the check of~5.;
## the default is `Irr( <tbl> )',
##
## `subchars' &
## a list of characters of <subtbl> which are constituents of the
## retrictions of `chars', the default is `Irr( <subtbl> )',
##
## `fusionmap' &
## a parametrized map which is an approximation of the desired map,
##
## `decompose' &
## a Boolean;
## a `true' value indicates that all constituents of the restrictions
## of `chars' computed for criterion 5. lie in `subchars',
## so the restrictions can be decomposed into elements of `subchars';
## the default value of `decompose' is `true' if `subchars' is not
## bound and `Irr( <subtbl> )' is known, otherwise `false',
##
## `permchar' &
## (a values list of) a permutation character; only those fusions
## affording that permutation character are computed,
##
## `quick' &
## a Boolean;
## if `true' then the subroutines are called with value `true' for
## the argument <quick>;
## especially, as soon as only one possibility remains
## then this possibility is returned immediately;
## the default value is `false',
##
## `verify' &
## a Boolean;
## if `false' then `ConsiderStructureConstants' is called only if more
## than one orbit of possible class fusions exists, under the action
## of the groups of table automorphisms;
## the default value is `false' (because the computation of the
## structure constants is usually very time comsuming, compared with
## checking the other criteria),
##
## `parameters' &
## a record with components `maxamb', `minamb' and `maxlen'
## which control the subroutine `FusionsAllowedByRestrictions';
## it only uses characters with current indeterminateness up to
## `maxamb',
## tests decomposability only for characters with current
## indeterminateness at least `minamb',
## and admits a branch according to a character only if there is one
## with at most `maxlen' possible restrictions.
## \enditems
##
DeclareOperation( "PossibleClassFusions",
[ IsNearlyCharacterTable, IsNearlyCharacterTable ] );
DeclareOperation( "PossibleClassFusions",
[ IsNearlyCharacterTable, IsNearlyCharacterTable, IsRecord ] );
#############################################################################
##
#5
## The permutation groups of table automorphisms
## (see~"AutomorphismsOfTable")
## of the subgroup table <subtbl> and the supergroup table <tbl> act on the
## possible class fusions returned by `PossibleClassFusions'
## (see~"PossibleClassFusions"),
## the former by permuting a list via `Permuted' (see~"Permuted"),
## the latter by mapping the images via `OnPoints' (see~"OnPoints").
##
## If the set of possible fusions with certain properties was computed
## that are not invariant under the full groups of table automorphisms
## then only a smaller group acts.
## This may happen for example if a permutation character or if an explicit
## approximation of the fusion map is prescribed in the call of
## `PossibleClassFusions'.
##
#############################################################################
##
#F OrbitFusions( <subtblautomorphisms>, <fusionmap>, <tblautomorphisms> )
##
## returns the orbit of the class fusion map <fusionmap> under the
## actions of the permutation groups <subtblautomorphisms> and
## <tblautomorphisms> of automorphisms of the character table of the
## subgroup and the supergroup, respectively.
##
DeclareGlobalFunction( "OrbitFusions" );
#############################################################################
##
#F RepresentativesFusions( <subtblautomorphisms>, <listofmaps>,
#F <tblautomorphisms> )
#F RepresentativesFusions( <subtbl>, <listofmaps>, <tbl> )
##
## returns a list of orbit representatives of class fusion maps in the list
## <listofmaps> under the action of maximal admissible subgroups
## of the table automorphisms <subtblautomorphisms> of the subgroup table
## and <tblautomorphisms> of the supergroup table.
## Both groups of table automorphisms must be permutation groups.
##
## Instead of the groups of table automorphisms, also the character tables
## <subtbl> and <tbl> may be entered.
## In this case, the `AutomorphismsOfTable' values of the tables are used.
##
DeclareGlobalFunction( "RepresentativesFusions" );
#############################################################################
##
## 4. Utilities for Parametrized Maps
#6
## A *parametrized map* is a list whose $i$-th entry is either unbound
## (which means that nothing is known about the image(s) of the $i$-th
## class) or the image of the $i$-th class
## (i.e., an integer for fusion maps, power maps, element orders etc.,
## and a cyclotomic for characters),
## or a list of possible images of the $i$-th class.
## In this sense, maps are special parametrized maps.
## We often identify a parametrized map <paramap> with the set of all maps
## <map> with the property that either `<map>[i] = <paramap>[i]' or
## `<map>[i]' is contained in the list `<paramap>[i]';
## we say then that <map> is contained in <paramap>.
##
## This definition implies that parametrized maps cannot be used to describe
## sets of maps where lists are possible images.
## An exception are strings which naturally arise as images when class names
## are considered.
## So strings and lists of strings are allowed in parametrized maps,
## and character constants (see Chapter~"Strings and Characters")
## are not allowed in maps.
##
#############################################################################
##
#F CompositionMaps( <paramap2>, <paramap1>[, <class>] )
##
## The composition of two parametrized maps <paramap1>, <paramap2> is
## defined as the parametrized map <comp> that contains
## all compositions $f_2 \circ f_1$ of elements $f_1$ of <paramap1> and
## $f_2$ of <paramap2>.
## For example, the composition of a character $\chi$ of a group $G$ by a
## parametrized class fusion map from a subgroup $H$ to $G$ is the
## parametrized map that contains all restrictions of $\chi$ by elements of
## the parametrized fusion map.
##
## `CompositionMaps(<paramap2>, <paramap1>)' is a parametrized map with
## entry `CompositionMaps(<paramap2>, <paramap1>, <class>)' at position
## <class>.
## If `<paramap1>[<class>]' is an integer then
## `CompositionMaps(<paramap2>, <paramap1>, <class>)' is equal to
## `<paramap2>[ <paramap1>[ <class> ] ]'.
## Otherwise it is the union of `<paramap2>[<i>]' for <i> in
## `<paramap1>[ <class> ]'.
##
DeclareGlobalFunction( "CompositionMaps" );
#############################################################################
##
#F InverseMap( <paramap> ) . . . . . . . . . . inverse of a parametrized map
##
## For a parametrized map <paramap>,
## `InverseMap' returns a mutable parametrized map whose $i$-th entry is
## unbound if $i$ is not in the image of <paramap>,
## equal to $j$ if $i$ is (in) the image of `<paramap>[<j>]' exactly for
## $j$, and equal to the set of all preimages of $i$ under <paramap>
## otherwise.
##
## We have `CompositionMaps( <paramap>, InverseMap( <paramap> ) )'
## the identity map.
##
DeclareGlobalFunction( "InverseMap" );
#############################################################################
##
#F ProjectionMap( <fusionmap> ) . . . . projection corresp. to a fusion map
##
## For a map <fusionmap>, `ProjectionMap' returns a parametrized map
## whose $i$-th entry is unbound if $i$ is not in the image of <fusionmap>,
## and equal to $j$ if $j$ is the smallest position such that $i$ is
## the image of `<fusionmap>[<j>]'.
##
## We have `CompositionMaps( <fusionmap>, ProjectionMap( <fusionmap> ) )'
## the identity map, i.e., first projecting and then fusing yields the
## identity.
## Note that <fusionmap> must *not* be a parametrized map.
##
DeclareGlobalFunction( "ProjectionMap" );
#############################################################################
##
#O Indirected( <character>, <paramap> )
##
## For a map <character> and a parametrized map <paramap>, `Indirected'
## returns a parametrized map whose entry at position $i$ is
## `<character>[ <paramap>[<i>] ]' if `<paramap>[<i>]' is an integer,
## and an unknown (see Chapter~"Unknowns") otherwise.
##
DeclareOperation( "Indirected", [ IsList, IsList ] );
#############################################################################
##
#F Parametrized( <list> )
##
## For a list <list> of (parametrized) maps of the same length,
## `Parametrized' returns the smallest parametrized map containing all
## elements of <list>.
##
## `Parametrized' is the inverse function to `ContainedMaps'
## (see~"ContainedMaps").
##
DeclareGlobalFunction( "Parametrized" );
#############################################################################
##
#F ContainedMaps( <paramap> )
##
## For a parametrized map <paramap>, `ContainedMaps' returns the set of all
## maps contained in <paramap>.
##
## `ContainedMaps' is the inverse function to `Parametrized'
## (see~"Parametrized") in the sense that
## `Parametrized( ContainedMaps( <paramap> ) )' is equal to <paramap>.
##
DeclareGlobalFunction( "ContainedMaps" );
#############################################################################
##
#F UpdateMap( <character>, <paramap>, <indirected> )
##
## Let <character> be a map, <paramap> a parametrized map, and <indirected>
## a parametrized map that is contained in
## `CompositionMaps( <character>, <paramap> )'.
##
## Then `UpdateMap' changes <paramap> to the parametrized map containing
## exactly the maps whose composition with <character> is equal to
## <indirected>.
##
## If a contradiction is detected then `false' is returned immediately,
## otherwise `true'.
##
DeclareGlobalFunction( "UpdateMap" );
#############################################################################
##
#F MeetMaps( <paramap1>, <paramap2> )
##
## For two parametrized maps <paramap1> and <paramap2>, `MeetMaps' changes
## <paramap1> such that the image of class $i$ is the intersection of
## `<paramap1>[<i>]' and `<paramap2>[<i>]'.
##
## If this implies that no images remain for a class, the position of such a
## class is returned.
## If no such inconsistency occurs, `MeetMaps' returns `true'.
##
DeclareGlobalFunction( "MeetMaps" );
#############################################################################
##
#F ImproveMaps( <map2>, <map1>, <composition>, <class> )
##
## `ImproveMaps' is a utility for `CommutativeDiagram' and
## `TestConsistencyMaps'.
##
## <composition> must be a set that is known to be an upper bound for the
## composition $( <map2> \circ <map1> )[ <class> ]$.
## If $`<map1>[ <class> ]' = x$ is unique then $<map2>[ x ]$ must be a set,
## it will be replaced by its intersection with <composition>;
## if <map1>[ <class> ] is a set then all elements `x' with empty
## `Intersection( <map2>[ x ], <composition> )' are excluded.
##
## `ImproveMaps' returns
## \beginlist
## \item{0}
## if no improvement was found,
## \item{-1}
## if <map1>[ <class> ] was improved,
## \item{<x>}
## if <map2>[ <x> ] was improved.
## \endlist
##
DeclareGlobalFunction( "ImproveMaps" );
#############################################################################
##
#F CommutativeDiagram( <paramap1>, <paramap2>, <paramap3>, <paramap4>[,
#F <improvements>] )
##
## Let <paramap1>, <paramap2>, <paramap3>, <paramap4> be parametrized maps
## covering parametrized maps $f_1$, $f_2$, $f_3$, $f_4$ with the property
## that $`CompositionMaps'( f_2, f_1 )$ is equal to
## $`CompositionMaps'( f_4, f_3 )$.
##
## `CommutativeDiagram' checks this consistency, and changes the arguments
## such that all possible images are removed that cannot occur in the
## parametrized maps $f_i$.
##
## The return value is `fail' if an inconsistency was found.
## Otherwise a record with the components `imp1', `imp2', `imp3', `imp4'
## is returned, each bound to the list of positions where the corresponding
## parametrized map was changed,
##
## The optional argument <improvements> must be a record with components
## `imp1', `imp2', `imp3', `imp4'.
## If such a record is specified then only diagrams are considered where
## entries of the $i$-th component occur as preimages of the $i$-th
## parametrized map.
##
## When an inconsistency is detected,
## `CommutativeDiagram' immediately returns `fail'.
## Otherwise a record is returned that contains four lists `imp1', $\ldots$,
## `imp4':
## `imp<i>' is the list of classes where <paramap_i> was changed.
##
DeclareGlobalFunction( "CommutativeDiagram" );
#############################################################################
##
#F CheckFixedPoints( <inside1>, <between>, <inside2> )
##
## Let <inside1>, <between>, <inside2> be parametrized maps,
## where <between> is assumed to map each fixed point of <inside1>
## (that is, `<inside1>[<i>] = <i>') to a fixed point of <inside2>
## (that is, <between>[<i>] is either an integer that is fixed by <inside2>
## or a list that has nonempty intersection with the union of its images
## under <inside2>).
## `CheckFixedPoints' changes <between> and <inside2> by removing all those
## entries violate this condition.
##
## When an inconsistency is detected,
## `CheckFixedPoints' immediately returns `fail'.
## Otherwise the list of positions is returned where changes occurred.
##
DeclareGlobalFunction( "CheckFixedPoints" );
#############################################################################
##
#F TransferDiagram( <inside1>, <between>, <inside2>[, <improvements>] )
##
## Let <inside1>, <between>, <inside2> be parametrized maps
## covering parametrized maps $m_1$, $f$, $m_2$ with the property
## that $`CompositionMaps'( m_2, f )$ is equal to
## $`CompositionMaps'( f, m_1 )$.
##
## `TransferDiagram' checks this consistency, and changes the arguments
## such that all possible images are removed that cannot occur in the
## parametrized maps $m_i$ and $f$.
##
## So `TransferDiagram' is similar to `CommutativeDiagram'
## (see~"CommutativeDiagram"),
## but <between> occurs twice in each diagram checked.
##
## If a record <improvements> with fields `impinside1', `impbetween' and
## `impinside2' is specified, only those diagrams with elements of
## `impinside1' as preimages of <inside1>, elements of `impbetween' as
## preimages of <between> or elements of `impinside2' as preimages of
## <inside2> are considered.
##
## When an inconsistency is detected,
## `TransferDiagram' immediately returns `fail'.
## Otherwise a record is returned that contains three lists `impinside1',
## `impbetween', and `impinside2' of positions where the arguments were
## changed.
##
DeclareGlobalFunction( "TransferDiagram" );
#############################################################################
##
#F TestConsistencyMaps( <powermap1>, <fusionmap>, <powermap2>[, <fus_imp>] )
##
## Let <powermap1> and <powermap2> be lists of parametrized maps,
## and <fusionmap> a parametrized map,
## such that for each $i$, the $i$-th entry in <powermap1>, <fusionmap>,
## and the $i$-th entry in <powermap2> (if bound) are valid arguments for
## `TransferDiagram' (see~"TransferDiagram").
## So a typical situation for applying `TestConsistencyMaps' is that
## <fusionmap> is an approximation of a class fusion, and <powermap1>,
## <powermap2> are the lists of power maps of the subgroup and the group.
##
## `TestConsistencyMaps' repeatedly applies `TransferDiagram' to these
## arguments for all $i$ until no more changes occur.
##
## If a list <fus_imp> is specified then only those diagrams with
## elements of <fus_imp> as preimages of <fusionmap> are considered.
##
## When an inconsistency is detected,
## `TestConsistencyMaps' immediately returns `false'.
## Otherwise `true' is returned.
##
DeclareGlobalFunction( "TestConsistencyMaps" );
#############################################################################
##
#F Indeterminateness( <paramap> ) . . . . the indeterminateness of a paramap
##
## For a parametrized map <paramap>, `Indeterminateness' returns the number
## of maps contained in <paramap>, that is, the product of lengths of lists
## in <paramap> denoting lists of several images.
##
DeclareGlobalFunction( "Indeterminateness" );
#############################################################################
##
#F IndeterminatenessInfo( <paramap> )
##
DeclareGlobalFunction( "IndeterminatenessInfo" );
#############################################################################
##
#F PrintAmbiguity( <list>, <paramap> ) . . . . ambiguity of characters with
## respect to a paramap
##
## For each map in the list <list>, `PrintAmbiguity' prints its position in
## <list>,
## the indeterminateness (see~"Indeterminateness") of the composition with
## the parametrized map <paramap>,
## and the list of positions where a list of images occurs in this
## composition.
##
DeclareGlobalFunction( "PrintAmbiguity" );
#############################################################################
##
#F ContainedSpecialVectors( <tbl>, <chars>, <paracharacter>, <func> )
#F IntScalarProducts( <tbl>, <chars>, <candidate> )
#F NonnegIntScalarProducts( <tbl>, <chars>, <candidate> )
#F ContainedPossibleVirtualCharacters( <tbl>, <chars>, <paracharacter> )
#F ContainedPossibleCharacters( <tbl>, <chars>, <paracharacter> )
##
## Let <tbl> be an ordinary character table,
## <chars> a list of class functions (or values lists),
## <paracharacter> a parametrized class function of <tbl>,
## and <func> a function that expects the three arguments <tbl>, <chars>,
## and a values list of a class function, and that returns either `true' or
## `false'.
##
## `ContainedSpecialVectors' returns
## the list of all those elements <vec> of <paracharacter> that
## have integral norm,
## have integral scalar product with the principal character of <tbl>,
## and that satisfy `<func>( <tbl>, <chars>, <vec> ) = true',
##
## \indextt{IntScalarProducts}\indextt{NonnegIntScalarProducts}
## \indextt{ContainedPossibleVirtualCharacters}
## \indextt{ContainedPossibleCharacters}\indextt{ContainedSpecialVectors}
## Two special cases of <func> are the check whether the scalar products in
## <tbl> between the vector <vec> and all lists in <chars> are integers or
## nonnegative integers, respectively.
## These functions are accessible as global variables `IntScalarProducts'
## and `NonnegIntScalarProducts',
## and `ContainedPossibleVirtualCharacters' and
## `ContainedPossibleCharacters' provide access to these special cases of
## `ContainedSpecialVectors'.
DeclareGlobalFunction( "ContainedSpecialVectors" );
DeclareGlobalFunction( "IntScalarProducts" );
DeclareGlobalFunction( "NonnegIntScalarProducts" );
DeclareGlobalFunction( "ContainedPossibleVirtualCharacters" );
DeclareGlobalFunction( "ContainedPossibleCharacters" );
#############################################################################
##
#F ContainedDecomposables( <constituents>, <moduls>, <parachar>, <func> )
#F ContainedCharacters( <tbl>, <constituents>, <parachar> )
##
## For these functions,
## let <constituents> be a list of *rational* class functions,
## <moduls> a list of positive integers,
## <parachar> a parametrized rational class function,
## <func> a function that returns either `true' or `false' when called
## with (a values list of) a class function,
## and <tbl> a character table.
##
## `ContainedDecomposables' returns the set of all elements $\chi$ of
## <parachar> that satisfy $<func>( \chi ) = `true'$
## and that lie in the $\Z$-lattice spanned by <constituents>,
## modulo <moduls>.
## The latter means they lie in the $\Z$-lattice spanned by <constituents>
## and the set
## $$
## \{ <moduls>[i] . e_i; 1 \leq i \leq n \},
## $$
## where $n$ is the length of <parachar> and $e_i$ is the $i$-th standard
## basis vector.
##
## One application of `ContainedDecomposables' is the following.
## <constituents> is a list of (values lists of) rational characters of an
## ordinary character table <tbl>,
## <moduls> is the list of centralizer orders of <tbl>
## (see~"SizesCentralizers"),
## and <func> checks whether a vector in the lattice mentioned above has
## nonnegative integral scalar product in <tbl> with all entries of
## <constituents>.
## This situation is handled by `ContainedCharacters'.
## Note that the entries of the result list are *not* necessary linear
## combinations of <constituents>,
## and they are *not* necessarily characters of <tbl>.
##
DeclareGlobalFunction( "ContainedDecomposables" );
DeclareGlobalFunction( "ContainedCharacters" );
#############################################################################
##
## 5. Subroutines for the Construction of Power Maps
##
#############################################################################
##
#F InitPowerMap( <tbl>, <prime> )
##
## For an ordinary character table <tbl> and a prime <prime>,
## `InitPowerMap' returns a parametrized map that is a first approximation
## of the <prime>-th powermap of <tbl>,
## using the conditions 1.~and 2.~listed in the description of
## `PossiblePowerMaps' (see~"PossiblePowerMaps").
##
## If there are classes for which no images are possible, according to these
## criteria, then `fail' is returned.
##
DeclareGlobalFunction( "InitPowerMap" );
#############################################################################
##
#7
## In the argument lists of the functions `Congruences', `ConsiderKernels',
## and `ConsiderSmallerPowerMaps',
## <tbl> is an ordinary character table,
## <chars> a list of (values lists of) characters of <tbl>,
## <prime> a prime integer,
## <approxmap> a parametrized map that is an approximation for the
## <prime>-th power map of <tbl>
## (e.g., a list returned by `InitPowerMap', see~"InitPowerMap"),
## and <quick> a Boolean.
##
## The <quick> value `true' means that only those classes are considered
## for which <approxmap> lists more than one possible image.
##
#############################################################################
##
#F Congruences( <tbl>, <chars>, <approxmap>, <prime>, <quick> )
##
## `Congruences' replaces the entries of <approxmap> by improved values,
## according to condition 3.~listed in the description of
## `PossiblePowerMaps' (see~"PossiblePowerMaps").
##
## For each class for which no images are possible according to the tests,
## the new value of <approxmap> is an empty list.
## `Congruences' returns `true' if no such inconsistencies occur,
## and `false' otherwise.
##
DeclareGlobalFunction( "Congruences" );
#############################################################################
##
#F ConsiderKernels( <tbl>, <chars>, <approxmap>, <prime>, <quick> )
##
## `ConsiderKernels' replaces the entries of <approxmap> by improved values,
## according to condition 4.~listed in the description of
## `PossiblePowerMaps' (see~"PossiblePowerMaps").
##
## `Congruences' returns `true' if the orders of the kernels of all
## characters in <chars> divide the order of the group of <tbl>,
## and `false' otherwise.
##
DeclareGlobalFunction( "ConsiderKernels" );
#############################################################################
##
#F ConsiderSmallerPowerMaps( <tbl>, <approxmap>, <prime>, <quick> )
##
## `ConsiderSmallerPowerMaps' replaces the entries of <approxmap>
## by improved values,
## according to condition 5.~listed in the description of
## `PossiblePowerMaps' (see~"PossiblePowerMaps").
##
## `ConsiderSmallerPowerMaps' returns `true' if each class admits at least
## one image after the checks, otherwise `false' is returned.
## If no element orders of <tbl> are stored
## (see~"OrdersClassRepresentatives") then `true' is returned without any
## tests.
##
DeclareGlobalFunction( "ConsiderSmallerPowerMaps" );
#############################################################################
##
#F MinusCharacter( <character>, <prime_powermap>, <prime> )
##
## Let <character> be (the list of values of) a class function $\chi$,
## <prime> a prime integer $p$, and <prime_powermap> a parametrized map
## that is an approximation of the $p$-th power map for the character table
## of $\chi$.
## `MinusCharacter' returns the parametrized map of values of $\chi^{p-}$,
## which is defined by $\chi^{p-}(g) = ( \chi(g)^p - \chi(g^p) ) / p$.
##
DeclareGlobalFunction( "MinusCharacter" );
#############################################################################
##
#F PowerMapsAllowedBySymmetrizations( <tbl>, <subchars>, <chars>,
#F <approxmap>, <prime>, <parameters> )
##
## Let <tbl> be an ordinary character table,
## <prime> a prime integer,
## <approxmap> a parametrized map that is an approximation of the <prime>-th
## power map of <tbl>
## (e.g., a list returned by `InitPowerMap', see~"InitPowerMap"),
## <chars> and <subchars> two lists of (values lists of) characters of
## <tbl>,
## and <parameters> a record with components
## `maxlen', `minamb', `maxamb' (three integers),
## `quick' (a Boolean),
## and `contained' (a function).
## Usual values of `contained' are `ContainedCharacters' or
## `ContainedPossibleCharacters'.
##
## `PowerMapsAllowedBySymmetrizations' replaces the entries of <approxmap>
## by improved values,
## according to condition 6.~listed in the description of
## `PossiblePowerMaps' (see~"PossiblePowerMaps").
##
## More precisely, the strategy used is as follows.
##
## First, for each $\chi \in <chars>$,
## let `minus:= MinusCharacter($\chi$, <approxmap>, <prime>)'.
## \beginlist%unordered
## \item{--}
## If $`Indeterminateness( minus )' = 1$ and
## `<parameters>.quick = false' then the scalar products of `minus' with
## <subchars> are checked;
## if not all scalar products are nonnegative integers then
## an empty list is returned,
## otherwise $\chi$ is deleted from the list of characters to inspect.
## \item{--}
## Otherwise if `Indeterminateness( minus )' is smaller than
## `<parameters>.minamb' then $\chi$ is deleted from the list of
## characters.
## \item{--}
## If `<parameters>.minamb' $\leq$ `Indeterminateness( minus )' $\leq$
## `<parameters>.maxamb' then
## construct the list of contained class functions
## `poss:= <parameters>.contained(<tbl>, <subchars>, minus)'
## and `Parametrized( poss )',
## and improve the approximation of the power map using `UpdateMap'.
## \endlist
##
## If this yields no further immediate improvements then we branch.
## If there is a character from <chars> left with less or equal
## `<parameters>.maxlen' possible symmetrizations,
## compute the union of power maps allowed by these possibilities.
## Otherwise we choose a class $C$ such that the possible symmetrizations of
## a character in <chars> differ at $C$,
## and compute recursively the union of all allowed power maps with image
## at $C$ fixed in the set given by the current approximation of the power
## map.
##
DeclareGlobalFunction( "PowerMapsAllowedBySymmetrizations" );
DeclareSynonym( "PowerMapsAllowedBySymmetrisations",
PowerMapsAllowedBySymmetrizations );
#############################################################################
##
## 6. Subroutines for the Construction of Class Fusions
##
#############################################################################
##
#F InitFusion( <subtbl>, <tbl> )
##
## For two ordinary character tables <subtbl> and <tbl>,
## `InitFusion' returns a parametrized map that is a first approximation
## of the class fusion from <subtbl> to <tbl>,
## using condition~1.~listed in the description of `PossibleClassFusions'
## (see~"PossibleClassFusions").
##
## If there are classes for which no images are possible, according to this
## criterion, then `fail' is returned.
##
DeclareGlobalFunction( "InitFusion" );
#############################################################################
##
#F CheckPermChar( <subtbl>, <tbl>, <approxmap>, <permchar> )
##
## `CheckPermChar' replaces the entries of the parametrized map <approxmap>
## by improved values,
## according to condition~3.~listed in the description of
## `PossibleClassFusions' (see~"PossibleClassFusions").
##
## `CheckPermChar' returns `true' if no inconsistency occurred, and `false'
## otherwise.
##
DeclareGlobalFunction( "CheckPermChar" );
#############################################################################
##
#F ConsiderTableAutomorphisms( <approxmap>, <grp> )
##
## `ConsiderTableAutomorphisms' replaces the entries of the parametrized map
## <approxmap> by improved values, according to condition~4.~listed in the
## description of `PossibleClassFusions' (see~"PossibleClassFusions").
##
## Afterwards exactly one representative of fusion maps (contained in
## <approxmap>) in each orbit under the action of the permutation group
## <grp> is contained in the modified parametrized map.
##
## `ConsiderTableAutomorphisms' returns the list of positions where
## <approxmap> was changed.
##
DeclareGlobalFunction( "ConsiderTableAutomorphisms" );
#############################################################################
##
#F FusionsAllowedByRestrictions( <subtbl>, <tbl>, <subchars>, <chars>,
#F <approxmap>, <parameters> )
##
## Let <subtbl> and <tbl> be ordinary character tables,
## <subchars> and <chars> two lists of (values lists of) characters of
## <subtbl> and <tbl>, respectively,
## <approxmap> a parametrized map that is an approximation of the class
## fusion of <subtbl> in <tbl>,
## and <parameters> a record with components
## `maxlen', `minamb', `maxamb' (three integers),
## <quick> (a Boolean),
## and `contained' (a function).
## Usual values of `contained' are `ContainedCharacters' or
## `ContainedPossibleCharacters'.
##
## `FusionsAllowedByResrictions' replaces the entries of <approxmap>
## by improved values,
## according to condition 5.~listed in the description of
## `PossibleClassFusions' (see~"PossibleClassFusions").
##
## More precisely, the strategy used is as follows.
##
## First, for each $\chi \in <chars>$,
## let `restricted:= CompositionMaps( $\chi$, <approxmap> )'.
## \beginlist%unordered
## \item{--}
## If $`Indeterminateness( restricted )' = 1$ and
## `<parameters>.quick = false' then the scalar products of `restricted'
## with <subchars> are checked;
## if not all scalar products are nonnegative integers then
## an empty list is returned,
## otherwise $\chi$ is deleted from the list of characters to inspect.
## \item{--}
## Otherwise if `Indeterminateness( minus )' is smaller than
## `<parameters>.minamb' then $\chi$ is deleted from the list of
## characters.
## \item{--}
## If `<parameters>.minamb' $\leq$ `Indeterminateness( restricted )'
## $\leq$ `<parameters>.maxamb' then construct
## `poss:= <parameters>.contained( <subtbl>, <subchars>, restricted )'
## and `Parametrized( poss )',
## and improve the approximation of the fusion map using `UpdateMap'.
## \endlist
#T Would it help to exploit that the restriction of a *linear* character
#T is again a linear character (not only a linear combination of linear
#T characters?
#T Branching in these cases would yield a short list of possibilities,
#T so it should be recommended ...
##
## If this yields no further immediate improvements then we branch.
## If there is a character from <chars> left with less or equal
## `<parameters>.maxlen' possible restrictions,
## compute the union of fusion maps allowed by these possibilities.
## Otherwise we choose a class $C$ such that the possible restrictions of a
## character in <chars> differ at $C$,
## and compute recursively the union of all allowed fusion maps with image
## at $C$ fixed in the set given by the current approximation of the fusion
## map.
##
DeclareGlobalFunction( "FusionsAllowedByRestrictions" );
#############################################################################
##
#F ConsiderStructureConstants( <subtbl>, <tbl>, <fusions>, <quick> )
##
## Let <subtbl> and <tbl> be ordinary character tables and <fusions> be a
## list of possible class fusions from <subtbl> to <tbl>.
## `ConsiderStructureConstants' returns the list of those maps $\sigma$ in
## <fusions> with the property that for all triples $(i,j,k)$ of class
## positions, $`ClassMultiplicationCoefficient'( <subtbl>, i, j, k )$ is not
## bigger than $`ClassMultiplicationCoefficient'( <tbl>, \sigma[i],
## \sigma[j], \sigma[k] )$;
## see~"ClassMultiplicationCoefficient!for character tables" for the
## definition of class multiplication coefficients/structure constants.
##
## The argument <quick> must be a Boolean; if it is `true' then only those
## triples are checked for which for which at least two entries in <fusions>
## have different images.
##
DeclareGlobalFunction( "ConsiderStructureConstants" );
#############################################################################
##
#E
|