summaryrefslogtreecommitdiff
path: root/web/reduce/rweb/appl/liesuper.web
blob: c760f2da6e10657952770b4f51b4ab68ef9f6d13 (plain)
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
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777
2778
2779
2780
2781
2782
2783
2784
2785
2786
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2950
2951
2952
2953
2954
2955
2956
2957
2958
2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
3038
3039
3040
3041
3042
3043
3044
3045
3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
3065
3066
3067
3068
3069
3070
3071
3072
3073
3074
3075
3076
3077
3078
3079
3080
3081
3082
3083
3084
3085
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133
3134
3135
3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
3202
3203
3204
3205
3206
3207
3208
3209
3210
3211
3212
3213
3214
3215
3216
3217
3218
3219
3220
3221
3222
3223
3224
3225
3226
3227
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
3240
3241
3242
3243
3244
3245
3246
3247
3248
3249
3250
3251
3252
3253
3254
3255
3256
3257
3258
3259
3260
3261
3262
3263
3264
3265
3266
3267
3268
3269
3270
3271
3272
3273
3274
3275
3276
3277
3278
3279
3280
3281
3282
3283
3284
3285
3286
3287
3288
3289
3290
3291
3292
3293
3294
3295
3296
3297
3298
3299
3300
3301
3302
3303
3304
3305
3306
3307
3308
3309
3310
3311
3312
3313
3314
3315
3316
3317
3318
3319
3320
3321
3322
3323
3324
3325
3326
3327
3328
3329
3330
3331
3332
3333
3334
3335
3336
3337
3338
3339
3340
3341
3342
3343
3344
3345
3346
3347
3348
3349
3350
3351
3352
3353
3354
3355
3356
3357
3358
3359
3360
3361
3362
3363
3364
3365
3366
3367
3368
3369
3370
3371
3372
3373
3374
3375
3376
3377
3378
3379
3380
3381
3382
3383
3384
3385
3386
3387
3388
3389
3390
3391
3392
3393
3394
3395
3396
3397
3398
3399
3400
3401
3402
3403
3404
3405
3406
3407
3408
3409
3410
3411
3412
3413
3414
3415
3416
3417
3418
3419
3420
3421
3422
3423
3424
3425
3426
3427
3428
3429
3430
3431
3432
3433
3434
3435
3436
3437
3438
3439
3440
3441
3442
3443
3444
3445
3446
3447
3448
3449
3450
3451
3452
3453
3454
3455
3456
3457
3458
3459
3460
3461
3462
3463
3464
3465
3466
3467
3468
3469
3470
3471
3472
3473
3474
3475
3476
3477
3478
3479
3480
3481
3482
3483
3484
3485
3486
3487
3488
3489
3490
3491
3492
3493
3494
3495
3496
3497
3498
3499
3500
3501
3502
3503
3504
3505
3506
3507
3508
3509
3510
3511
3512
3513
3514
3515
3516
3517
3518
3519
3520
3521
3522
3523
3524
3525
3526
3527
3528
3529
3530
3531
3532
3533
3534
3535
3536
3537
3538
3539
3540
3541
3542
3543
3544
3545
3546
3547
3548
3549
3550
3551
3552
3553
3554
3555
3556
3557
3558
3559
3560
3561
3562
3563
3564
3565
3566
3567
3568
3569
3570
3571
3572
3573
3574
3575
3576
3577
3578
3579
3580
3581
3582
3583
3584
3585
3586
3587
3588
3589
3590
3591
3592
3593
3594
3595
3596
3597
3598
3599
3600
3601
3602
3603
3604
3605
3606
3607
3608
3609
3610
3611
3612
3613
3614
3615
3616
3617
3618
3619
3620
3621
3622
3623
3624
3625
3626
3627
3628
3629
3630
3631
3632
3633
3634
3635
3636
3637
3638
3639
3640
3641
3642
3643
3644
3645
3646
3647
3648
3649
3650
3651
3652
3653
3654
3655
3656
3657
3658
3659
3660
3661
3662
3663
3664
3665
3666
3667
3668
3669
3670
3671
3672
3673
3674
3675
3676
3677
3678
3679
3680
3681
3682
3683
3684
3685
3686
3687
3688
3689
3690
3691
3692
3693
3694
3695
3696
3697
3698
3699
3700
3701
3702
3703
3704
3705
3706
3707
3708
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
3721
3722
3723
3724
3725
3726
3727
3728
3729
3730
3731
3732
3733
3734
3735
3736
3737
3738
3739
3740
3741
3742
3743
3744
3745
3746
3747
3748
3749
3750
3751
3752
3753
3754
3755
3756
3757
3758
3759
3760
3761
3762
3763
3764
3765
3766
3767
3768
3769
3770
3771
3772
3773
3774
3775
3776
3777
3778
3779
3780
3781
3782
3783
3784
3785
3786
3787
3788
3789
3790
3791
3792
3793
3794
3795
3796
3797
3798
3799
3800
3801
3802
3803
3804
3805
3806
3807
3808
3809
3810
3811
3812
3813
3814
3815
3816
3817
3818
3819
3820
3821
3822
3823
3824
3825
3826
3827
3828
3829
3830
3831
3832
3833
3834
3835
3836
3837
3838
3839
3840
3841
3842
3843
3844
3845
3846
3847
3848
3849
3850
3851
3852
3853
3854
3855
3856
3857
3858
3859
3860
3861
3862
3863
3864
3865
3866
3867
3868
3869
3870
3871
3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
3882
3883
3884
3885
3886
3887
3888
3889
3890
3891
3892
3893
3894
3895
3896
3897
3898
3899
3900
3901
3902
3903
3904
3905
3906
3907
3908
3909
3910
3911
3912
3913
3914
3915
3916
3917
3918
3919
3920
3921
3922
3923
3924
3925
3926
3927
3928
3929
3930
3931
3932
3933
3934
3935
3936
3937
3938
3939
3940
3941
3942
3943
3944
3945
3946
3947
3948
3949
3950
3951
3952
3953
3954
3955
3956
3957
3958
3959
3960
3961
3962
3963
3964
3965
3966
3967
3968
3969
3970
3971
3972
3973
3974
3975
3976
3977
3978
3979
3980
3981
3982
3983
3984
3985
3986
3987
3988
3989
3990
3991
3992
3993
3994
3995
3996
3997
3998
3999
4000
4001
4002
4003
4004
4005
4006
4007
4008
4009
4010
4011
4012
4013
4014
4015
4016
4017
4018
4019
4020
4021
4022
4023
4024
4025
4026
4027
4028
4029
4030
4031
4032
4033
4034
4035
4036
4037
4038
4039
4040
4041
4042
4043
4044
4045
4046
4047
4048
4049
4050
4051
4052
4053
4054
4055
4056
4057
4058
4059
4060
4061
4062
4063
4064
4065
4066
4067
4068
4069
4070
4071
4072
4073
4074
4075
4076
4077
4078
4079
4080
4081
4082
4083
4084
4085
4086
4087
4088
4089
4090
4091
4092
4093
4094
4095
4096
4097
4098
4099
4100
4101
4102
4103
4104
4105
4106
4107
4108
4109
4110
4111
4112
4113
4114
4115
4116
4117
4118
4119
4120
4121
4122
4123
4124
4125
4126
4127
4128
4129
4130
4131
4132
4133
4134
4135
4136
4137
4138
4139
4140
4141
4142
4143
4144
4145
4146
4147
4148
4149
4150
4151
4152
4153
4154
4155
4156
4157
4158
4159
4160
4161
4162
4163
4164
4165
4166
4167
4168
4169
4170
4171
4172
4173
4174
4175
4176
4177
4178
4179
4180
4181
4182
4183
4184
4185
4186
4187
4188
4189
4190
4191
4192
4193
4194
4195
4196
4197
4198
4199
4200
4201
4202
4203
4204
4205
4206
4207
4208
4209
4210
4211
4212
4213
4214
4215
4216
4217
4218
4219
4220
4221
4222
4223
4224
4225
4226
4227
4228
4229
4230
4231
4232
4233
4234
4235
4236
4237
4238
4239
4240
4241
4242
4243
4244
4245
4246
4247
4248
4249
4250
4251
4252
4253
4254
4255
4256
4257
4258
4259
4260
4261
4262
4263
4264
4265
4266
4267
4268
4269
4270
4271
4272
4273
4274
4275
4276
4277
4278
4279
4280
4281
4282
4283
4284
4285
4286
4287
% Copyright (c) 1991 Marcel Roelofs, University of Twente, Enschede,
% The Netherlands.
%
% $Header: liesuper.web,v 1.5 92/02/26 14:22:25 roelofs Exp $
%
\input specification
\def\Version$#1Revision: #2 ${Version #2}
\def\title{LIESUPER}
\font\titlefont=cmcsc10 scaled\magstep3
\font\ttitlefont=cmtt10 scaled\magstep4
\def\topofcontents{\null\vfill
\centerline{\titlefont The {\ttitlefont LIESUPER} package for REDUCE}
\vskip15pt\centerline{\Version$Revision: 1.5 $}
\vskip15pt\centerline{\sc Marcel Roelofs}\vfill}
\def\concl{\bigskip\narrower\narrower\narrower\noindent
          {\bf SPECIFICATIONS}:\hskip1em\ignorespaces}
\def\endconcl{\par\leftskip=0pt\rightskip=0pt\noindent\ignorespaces}
\def\enditem{\medskip\noindent\ignorespaces}
\def\lie{{\it lie}}
\def\newpage{\vfill\eject}

@*= Introduction. In this \.{WEB} file we will describe a REDUCE package for 
symbolic computations in (free) Lie (super)algebras.  For this purpose
we will introduce a new rtype liebracket, which satisfies the
bilinearity and the (graded) skew-symmetry of the liebracket.
Moreover, we will implement a mechanism to check the (graded) Jacobi
identity and add sufficient bells and whistles to facilitate the usage
of various kinds of gradings.

Although we call it a rtype there is a difference with the usual
rtypes in REDUCE like arrays or matrices. Elements of an array or a
matrix can be accessed through a get-element-function and always have
a value (which can be and actually is simplified before returning it).
Elements of a liebracket, however, need not always have a value, in
which case the element itself should be returned in a canonical form
(in this way it resembles the REDUCE operator |df|). Hence access to
elements of a liebracket must necessarily be through a simplification
function, in order to avoid infinite loops on simplification.

On the other hand a liebracket isn't an algebraic operator in the
usual sense either, because we don't want to use the standard
mechanism for storing elements of algebraic operators, since this
generates a linear list containing all values, which is too time
consuming if a large number of values have to be stored. Instead we
will use a vector structure which is better suited to the structure of
a liebracket.  Therefore we are enforced to use a set-element-function
to assign values to elements of a liebracket. The only way to
accomplish this is to define liebracket to be a rtype.

Another bottleneck for operators with a large number of used elements
is the use of the so called klist. On this list all operator elements
are stored which at least have occured once in an algebraic expression.
Therefore we shall extend some standard REDUCE procedures which take
care of or use the klist mechanism, in such a way that for liebrackets
the klist is replaced by an additional field in the vector structure.

It is well known that commutators are normally represented by a pair
of square brackets $[\,\ldotp\,,\,\ldotp\,]$ in mathematics. Since we
explicitly want to allow more liebrackets at a time, it is impossible
for us to denote all commutators in this notation. We will, however,
facilitate the use of square brackets for a specific liebracket, which
can be used in all cases where one only needs to work with one
liebracket.

\medskip
The ``banner line'' defined here is intended for indentification
purposes on loading. It should be changed whenever this file is
modified. System dependent changes, however, should be made in a
separate change file.

@d banner="Lie (super)algebra package for REDUCE 3.4, $Revision: 1.5 $"

@ We define the following macros for clarity.
@d change_to_symbolic_mode =symbolic
@d change_to_algebraic_mode =algebraic
@d stop_with_error(string_1,expr_1,string_2,expr_2) = @/
  msgpri(string_1,expr_1,string_2,expr_2,t) @;
@d message(string_1,expr_1,string_2,expr_2) = @/
  msgpri(string_1,expr_1,string_2,expr_2,nil) @;
@d operator_name_of=car
@d arguments_of=cdr
@d first_argument_of=cadr
@d second_argument_of=caddr
@d first_element_of=car
@d second_element_of=cadr
@d rest_of=cdr
@d skip_list=cdr   %Skip the |'list| in front of an algebraic list%
@d independent_part_of=cadr %For use with lists returned by |operator_coeff|%
@d kernel_coeff_list_of=cddr %For use with lists returned by |operator_coeff|%
@d kernel_of=cadr  %For use with a kernel-coefficient list%
@d coefficient_of=caddr %For use with a kernel-coefficient list%

@ The following macros are intended as common programming idioms.
@d incr(x) = (x:=x+1)@;
@d decr(x) = (x:=x-1)@;

@ A new REDUCE switch can be introduced using the following code.

@d initialize_global(global_name,value)=@/
global '(global_name)$@/
global_name:=value

@d new_switch(switch_name,value)=@/
initialize_global(!* @& switch_name,value)$@/
flag('(switch_name),'switch)

@ We do all initializations in the beginning of the package.  
@u
change_to_symbolic_mode$@/ 
write banner$terpri()$@/
@<Check if the TOOLS package is already loaded@>$
@<Lisp initializations@>@/
change_to_algebraic_mode$

@ For a proper function of some procedures of this \.{WEB} file we
need a number of procedures from the TOOLS package. Therefore we will
check if the TOOLS package has already been loaded. We do this by
verifying that |operator_coeff| is defined as function.

@<Check if the TOOLS...@>=
if not getd 'operator_coeff then
message("LIESUPER_INIT: load the TOOLS package before continuing",nil,nil,nil) @;


@*= Implementing free Lie superalgebras.  For $m,n\geq 0$ let ${\sl
Lib}={\sl Lib}(x_1,\dots,x_m,\xi_1,\dots,\xi_n)$ be the free algebra
on generators $x_1,\dots,x_m,\xi_1,\dots,\xi_n$. We introduce a {\bf
Z}$_2$-grading $\vert\,\ldotp\vert$ on {\sl Lib\/} by defining $\vert
x_i\vert=0$ $(i=1,\dots,m)$, $\vert \xi_j\vert=1$ $(j=1,\dots,n)$ and
$\vert xy\vert=\vert x\vert+\vert y\vert$ for all homogeneous $x,y\in
{\sl Lib}$. We define $L=L(x_1,\dots,x_m,\xi_1,\dots,\xi_n)$ to be the
quotient algebra ${\sl Lib}/I$ where $I$ is the ideal, which for all
homogeneous $x,y,z\in {\sl Lib}$ is generated by the elements
$xy+(-1)^{\vert x\vert \cdot\vert y\vert}yx$ and $(-1)^{\vert
  x\vert\cdot\vert z\vert }x(yz)+
  (-1)^{\vert y\vert \cdot\vert x\vert}y(zx)+ 
  (-1)^{\vert z\vert \cdot\vert y\vert }z(xy)$.

On $L$ we define a bracket $[x,y]\equiv xy$. Then from the definition
above it is clear that this bracket satisfies the graded skew-symmetry
$$[x,y]=-(-1)^{\vert x\vert \cdot\vert y\vert}[y,x]$$ 
and the graded Jacobi identity 
$$(-1)^{\vert x\vert\cdot\vert z\vert }[x,[y,z]]+ 
  (-1)^{\vert y\vert \cdot\vert x\vert}[y,[z,x]]+ 
  (-1)^{\vert z\vert \cdot\vert y\vert }[z,[x,y]]=0.$$
Moreover it is bilinear because of the bilinearity of the multiplication
in {\sl Lib}. Therefore $L$ defines a Lie superalgebra, the so called
{\it free Lie superalgebra\/} on even generators $x_1,\dots,x_m$ and odd
generators $\xi_1,\dots,\xi_n$. It is obvious that for $m>1$ or $n>1$ 
$L$ is infinite dimensional.

From this free Lie superalgebra we can get some specific Lie
(super)algebra by imposing additional relations on top of the graded
skew-symmetry and the graded Jacobi identity. For instance, we can get a
finite dimensional simple Lie algebra by imposing appropriate Serre
relations.

As a last point we have to mention gradings of Lie (super)algebras,
because these can be very helpful when working on Lie (super)algebras.
A Lie (super)algebra can admit more than one grading, for example,
the free Lie (super)algebra on $n$ generators admits a {\bf
Z}$_2$-grading, but also admits the length of ``words'' as a grading,
or a multigrading where the degree of $x_i$ is the $n$-tuple
$(0,\dots,1,\dots,0)$ (1 on the $i$-th place). 

\bigskip
There is one fact about free Lie superalgebras which is very useful if
we want to implement a free Lie superalgebra in REDUCE.  To explain
this, let $L_1=L(x_1,\dots,x_n)$ be the free Lie superalgebra on
generators $x_1,\dots,x_n$ for some $n>1$.  Then it is easy to prove
that $L_1$ is isomorphic to
$L_2=L(x_1,\dots,x_{n+1})/I(x_{n+1}-[x_1,x_2])$ where
$I(x_{n+1}-[x_1,x_2])$ is the ideal in $L_2$ generated by
$x_{n+1}-[x_1,x_2]$.
This means that we can avoid expressions containing commutators like
$[x_1,x_2]$ just by introducing a new generator $x_{n+1}$ and imposing
one additional relation $[x_1,x_2]=x_{n+1}$.
\newpage
@ In the sections that follow we will take some decisions about how we are
planning to introduce a structure in REDUCE suitable to deal with free
Lie superalgebras. From what we have said in the previous section it is
clear that the following points have to be taken into account:\medskip

\item{1.} the bilinearity of the bracket.
\item{2.} the graded skew-symmetry of the bracket.
\item{3.} the number of generators and the possibility to introduce new
          generators as new names for unknown commutators.
\item{4.} the Jacobi identity.
\item{5.} the ability to use various kinds of gradings.

@*2 Representation of Lie algebras. The first point we have to take
care of is how to represent commutators and generators in REDUCE.
Generators we want to represent by an algebraic operator. For example,
we could represent $x_i$ by an operator $x(i)$. We should, however, be
able to discriminate between even and odd generators. There are a few
solutions to this problem:\medskip
\item{1.} use different operators for even and odd generators.
\item{2.} for each generator keep record of its grade.  \item{3.} use
different ranges for even and odd generators. For instance, use $x(i)$
with $i>0$ for even generators and $x(i)$ with $i<0$ for odd
generators.  \enditem We have chosen the third solution, since it
seems the most practical one.  Namely, it offers a very easy way to
test whether a generator is odd or even.

@ Commutators can simply be represented by an algebraic operator with
two arguments. If we use, for example, the operator \lie\ for
commutators and $x$ for generators, $[x_i,x_j]$ will be represented by
$\lie(x(i),x(j))$. For this kind of expression, however, it seems
useful to introduce a shorthand notation $\lie(i,j)$, since these
expressions will be playing a very important role. We have found:

\concl To each liebracket we assign two algebraic operators to
represent the commutators and the generators, respectively. If $x$ is
the operator assigned to some liebracket as generator, the elements
$x(i)$ for $i<0$ represent the odd generators of the Lie superalgebra,
the elements $x(i)$ for $i>0$ represent the even generators.
Commutators are represented by an algebraic operator with two
arguments. If \lie\ is this operator, $\lie(i,j)$ with $i$ and $j$
integer will be a shorthand notation for $\lie(x(i),x(j))$.
\bigskip
\endconcl
If in the sequel we want to explain things about liebrackets by giving
an example, we will always use the pair |@!lie|, |@!x| to represent
the commutators and generators, respectively.

@ We have seen that we are allowed to set an unknown commutator
$\lie(i,j)$ equal to $x(p)$ for some new generator $x(p)$ and still
keep the same algebra (up to isomorphism).  Hence in ordinary cases we
need not assign values to expressions like $\lie(\lie(i,j),q)$, because
with the above substitution for $\lie(i,j)$ it can be simplified to
$\lie(p,q)$.

It seems like a good idea to adopt the introduction of new generators
for unknown commutators as a very useful strategy, because it prevents
nested commutators to be represented in REDUCE by very lengthy and
deeply nested expressions. This may become very important for it
takes significantly more time to simplify deeply nested expressions
than simple expressions like $\lie(i,j)$ with $i$ and $j$ integer.
Moreover, the points raised above make the following simplifications
possible:\medskip
\item{1.} Using the bilinearity we see that $\lie(10*x(1),x(2)+x(3))$
is equal to $10*\lie(1,2)+10*\lie(1,3)$. This means that there is no
need to store commutators of linear combinations of generators.
\item{2.} From the graded skew-symmetry we see that $\lie(j,i)$ is
equal to $-\lie(i,j)$ if $\vert x_i\vert\cdot\vert x_j\vert=0$ and
equal to $\lie(i,j)$ otherwise. So our first observation is that there
must be a mechanism to store values of $\lie(i,j)$ for $j\geq i$.
\enditem
Although most Lie (super)algebras under consideration will be infinite
dimensional, it will only be possible to compute a finite dimensional
part of it by computer. Following our strategy of introducing new
generators for unknown commutors, this boils down to the fact that we
can only compute finitely many commutators of two generators. 
So it's no real restriction to impose upperbounds on the number of
generators beforehand. 

For practical problems, however, these upperbounds may still be
rather big, let's say 100 odd and 100 even generators.  In principle
all commutators of these generators may get a value, but if we assume
that only a quarter of all commutators is known, in our example with
200 generators this still means that about 5000 values have to be
stored.

This already indicates that it isn't a good idea to store the values
of commutators of generators on the standard REDUCE kvalue list, which
is an association list. Access to an association list is by comparing
the |car| of all its elements with the wanted expression until both
are equal.  Hence it will take more and more time to access an element
of an association list as it grows.

For practical problems like the example above, access to an
association list will already be too time consuming.  Therefore we
will choose to store values of commutators of generators in a vector
structure, a lisp object which is more directly accessible. Because a
vector is a static object, we need the upperbounds on the number of
generators right at this place. Resuming we have found:

\concl We impose upperbounds on the number of even and odd
generators (these upperbounds should include the number of generators
which we want to introduce as new names for unknown commutators).
If these upperbounds are $m$ and $n$, respectively, we store
the values of $\lie(i,j)$ for $-n\leq i\leq j\leq m$ in a vector
structure.
\endconcl

@ For some applications we sometimes need to allow more general
expressions as element of a Lie (super)algebra than just the
generators.  For instance, this is the case if we want to do
computations in (super)prolongation theory, where we are working with
Lie (super)algebra valued functions.

Nevertheless we should be able to assign values to commutators
containing such expressions or to commutators containing nested
commutators, to which we don't want or cannot assign a value, for
whatever reason.  But this means that we can't just do with the vector
structure, because these ``irregular'' commutators don't fit into it.
The most appropriate way to store such kind of commutators is to use
the standard REDUCE kvalue list.

However, we have to impose some restrictions on the kind expressions
which we allow to act as algebra elements. We should, for instance, be
able to recognize it as an algebra element.  In view of the way we
will decompose a commutator into its smallest components later on, the
first restriction must be that we can only allow operator expressions
to act as algebra elements.
Therefore the easiest way to allow for more general algebra elements
is to add to a liebracket a list of operatornames, elements of which
are regarded to be elements of that Lie (super)algebra.

There is one more restriction we have to impose, namely for each
algebra element we want to know if it is odd or even (nonhomogenous
elements we can split up into an odd and an even part). The reason that
we want to know this will become clear in the following section.
This can also be achieved very easily: if $f(a_1,\dots)$ is some
general algebra element, not being a commutator or a generator, we
demand its first argument $a_1$ to be a positive or negative integer,
indicating if the algebra element is even or odd, respectively.

\concl To each liebracket we add a list of operators, elements of
which will be regarded to be elements of the Lie (super)algebra. The
first argument of such an element should be a positive or negative
integer, indicating if it is an even or even algebra element. The
values of commutators containing algebra elements, which are not
generators, will be stored on the standard REDUCE kvalue list.
\endconcl 

@ Now we know how all possible algebra elements look like, we want to
have a canonical representation of all commutators. In this way REDUCE
will always correctly recognize sums of commutators to be zero, which
otherwise might possibly have slipped through because of the
bilinearity or the skew-symmetry of the bracket.
To get a commutator in canonical representation we apply the
following rules:\medskip
\item{1.} decompose the commutator into its smallest components
using the bilinearity of the bracket.
\item{2.} commutators $\lie(x(i),f(a_1,\dots))$, where $f$ is
some operator allowed as algebra element (including generators and nested
commutators), are represented by its shorthand notation
$\lie(i,f(a_1,\dots))$. The same applies to the second argument.
\item{3.} if one of the arguments is 0, the commutator is 0. This
follows directly from the bilinearity. From this we see the necessity
not to allow $x(0)$ as a generator, because its shorthand notation in
a commutator would be 0 and all commutators with $x(0)$ would become 0
applying the rule stated above.
\item{4.} using the standard REDUCE procedure |ordp(x,y)|, the
arguments $x$ and $y$ of $\lie(x,y)$ are orderded canonically.
If we have to switch $x$ and $y$ the result is
provided with a minus sign if not both $x$ and $y$ are odd algebra
elements. This actually is the reason, why for every algebra element
we need to know if it is odd or even.

@*1 Jacobi identities. The Jacobi identity expresses the fact that not
all commutators are linear independent. To explain this, we look at
the Jacobi identity for $x(1)$, $x(2)$ and $x(3)$. It reads
$\lie(1,\lie(2,3))-\lie(2,\lie(1,3))+\lie(3,\lie(1,2))=0$, where we
have used graded skew-symmetry to get the second term. Further suppose
that we have introduced new generators $\lie(1,2)=x(4)$,
$\lie(1,3)=x(5)$ and $\lie(2,3)=x(6)$, then this Jacobi identity
implies that $\lie(1,6)-\lie(2,5)+\lie(3,4)=0$. But this is nothing
else than to say that $\lie(1,6)$, $\lie(2,5)$ and $\lie(3,4)$ are
linear dependent.  If, moreover, $\lie(1,6)$, $\lie(2,5)$ and
$\lie(3,4)$ all are a sum of generators, the Jacobi identity might
either be zero or otherwise lead to a linear dependency for some
generators of the Lie (super)algebra.

It is clear that for each triple of algebra elements the
Jacobi identity is either zero or leads to a relation between algebra
elements and/or commutators of algebra elements. If we have $N$ linear
independent and homogeneous (w.r.t.\ the {\bf Z}$_2$ grading) algebra
elements (generators as well as the more general operator expressions
allowed as algebra element), the number of Jacobi identities amounts
to $N\choose 3$ if all algebra elements are even, and slightly more if
some of the elements are odd. Hence we conclude that the number of
Jacobi identities grows very fast for increasing $N$.

Just if only a small part of the Jacobi identities would lead to new
relations this still means that quite a lot of values would have to be
stored. If we were to store these values on the kvalue list of the
operator representing the commutator, we would be facing an increasing
access time for that kvalue list very soon.  This indicates that it is
only useful to compute and solve those Jacobi identities which don't
lead to storing of values on the kvalue list of the commutator.
Therefore we should only check those Jacobi identities that
(eventually) lead to new relations for commutators of two generators
(since these are stored in a vector structure) or to relations between
some generators (since this kind of relation cannot be avoided).

Hence the first remark that can be made, is that we only have to check
Jacobi identities for triples of generators $x(i)$, $x(j)$ and $x(k)$,
since these are the only ones to lead without too much difficulty to
the desired kind of relation.
Furthermore, if we want to satisfy the condition stated above, it is
easy to see that all three commutators $\lie(i,j)$, $\lie(j,k)$ and
$\lie(i,k)$ are to be entirely expressed in terms of some other
generators.  Therefore we have found:

\concl 
There must be a mechanism to compute and solve the Jacobi
identities for all triples of generators $x(i)$, $x(j)$ and $x(k)$
which satisfy the condition that all three commutators $\lie(i,j)$,
$\lie(j,k)$ and $\lie(i,k)$ are a linear combination of generators.

\bigskip \endconcl It is well known that one can give a basis of a
free Lie (super)algebra seen as a linear space, the so called Hall
basis. Consequently, this Hall basis respects the linear dependencies
caused by the Jacobi identity and the graded skew-symmetry.  

Now suppose that we start off with a free Lie (super)algebra on $n$
generators, i.e., a Lie (super)algebra without any additional
relations, and suppose that we want to compute a basis of this algebra
as a linear space in REDUCE. It is not difficult to see that we can
construct this basis upto ``words'' of a certain length $L$ by
executing a cycle of introducing new generators for still unknown
commutators of length $l$ and trying to solve Jacobi identities for
$l=2,\dots,L$. The result in each step of solving the Jacobi
identities is that all linear dependencies for commutators of length
$l+1$ are found and solved. Hence in the step for $l+1$ only the
remaining independent commutators will be renamed.

From this we see that solving Jacobi identities the way we are
planning to, is a means to get a minimal set of generators of a Lie
(super)algebra up to a certain length.

@*2 Gradings. The next point we should say something about are
gradings. As we have already seen, a Lie (super)algebra can have more
than one grading.  However, all gradings together constitute a
multigrading.  Although not all gradings adopt integer values (for
example the grading belonging to the root space decomposition of
Kac-Moody algebras), we can, at least for finitely generated algebras,
represent them by an appropriate multigrading with integer values.

If for each generator we store its multigrade, we can retrieve the
grade of every commutator (of two generators), since it is the sum of
the grades of its arguments.

\concl
There must be a mechanism to store and retrieve integer valued
multigrades of every generator of the Lie (super)algebra. With help of
these the multigrade of every commutator can be determined.
\endconcl

@ Then finally, we want to introduce a shorthand notation to be able
to input nested commutators more easily, which can be very useful when
actually working on Lie (super)algebras. For this suppose, for
example, that we want to compute the commutator
$[[x_1,x_2],[x_2,[x_3,x_4]]]$. Using the rules described above, it can
be represented by the expression $\lie(\lie(1,2),\lie(2,\lie(3,4)))$
in REDUCE. This is a rather lengthy expression and, moreover, it
doesn't express the structure of the commutator very clearly. If we
denote the bracket by a $\cdot$, the above commutator reads $(x_1\cdot
x_2)\cdot(x_2\cdot(x_3\cdot x_4))$ or $(x_1\cdot x_2)\cdot x_2\cdot
x_3\cdot x_4$, if we define $\cdot$ to be right associative (by this
we mean that $x_1\cdot x_2\cdot x_3\equiv x_1\cdot(x_2\cdot x_3)$).

In our opinion this is the most simple and easy to understand
expression representing the above commutator, and we want to introduce
a counterpart of this representation in REDUCE.  Therefore, let for
$N\geq 3$ the expression $\lie(x_1,\dots,x_N)$ be a shorthand notation for 
$\lie(x_1,\lie(x_2,\dots,\lie(x_{N-1},x_N)\dots))$, where
$x_1,\dots,x_N$ are algebra elements.
Moreover, to avoid lengthy expressions, we will allow (algebraic) list
expression as nested commutators.
With these simplifications the above commutator may be represented by
the REDUCE expression $\lie(\{1,2\},2,3,4)$. 

Of course, if one is working with the ``default'' liebracket which may
be represented by square brackets (mentioned in the introduction), it
may also be represented by $[[1,2],2,3,4]$ or even by
$[\{1,2\},2,3,4]$.

\concl
For $N\geq 3$ the expression 
$\lie(x_1,\dots,x_N)$ is defined to be a shorthand notation for 
$\lie(x_1,\lie(x_2,\dots,\lie(x_{N-1},x_N)\dots))$, where
$x_1,\dots,x_N$ are algebra elements.
Algebraic list expressions are allowed as nested commutators.
\endconcl

@*= Simplification of commutators. In the introduction we have already
explained that the requirements stated above, force us to use a
simplification function to retrieve values of commutators.  We have
gathered enough material now to outline this simplification function.
It should be noted that the procedure |simp_liebracket| expects the
|car| of its argument to be the name of the liebracket. To achieve
this, the liebracket under consideration must be flagged |full|.

A simplification function, hence also the procedure |simp_liebracket|,
should return the value of its argument as a standard quotient.

@u
lisp procedure simp_liebracket val;
if length val=3 then @<Simplify commutator |val|@>
else if length val>3 then @<Simplify nested commutator |val|@>
else rederr("SIMP_LIEBRACKET: wrong number of arguments")$

@ We simplify a commutator as explained in the previous sections. The
procedure |simp_liebracket_vector| checks if a commutator with two
integer arguments has a value, or otherwise returns it in canonical
form. We simplify both arguments before continuing in order to be able
to recognize negative integer arguments. It is easily verified that
this has almost no influence on the timings.

@<Simplify commutator |val|@>=
begin scalar bracketname,arg1,arg2;
  bracketname:=operator_name_of val;
  arg1:=mk!*sq simp!* first_argument_of val;
  arg2:=mk!*sq simp!* second_argument_of val;
  return
    if fixp arg1 and fixp arg2 then simp_liebracket_vector(bracketname,arg1,arg2)
    else @<Simplify |bracketname(arg1,arg2)| using the bilinearity@>;
end @;

@ To decompose a commutator into its smallest components using the
bilinearity we will use the procedures of the TOOLS package
implemented to deal with operators which are multilinear w.r.t.\ some
specified operators. We recall that this implementation consists of a
simplification procedure |simp_multilinear| together with a
resimplification procedure for the smallest constituent parts of the
operator $O$ under consideration, which name is to be found on the
property list of $O$ as the property |resimp_fn|. The list of operators
w.r.t.\ which $O$ is multilinear has to be stored as the property
|oplist|. Hence essentially it suffices to write an appropriate
resimplification procedure in our case.

There are, however, a few minor points which have to be taken into
account. First we allowed sole integers as a shorthand notation for
generators. To make |simp_multilinear| work properly we have to undo
this simplification temporarily. The name of this generator is stored
on the property list of the liebracket as the property |generatorname|.
Moreover, we allowed algebraic lists to denote nested commutators.
Since algebraic list are represented by the operator |list|
internally, this can be dealt with by putting |list| on the |oplist|
of a liebracket.

@<Simplify |bracketname(arg1,arg2)| using the bilinearity@>=
simp_multilinear list(bracketname,
  if fixp arg1 and arg1 neq 0 then list(generatorname,arg1) @+else arg1,
  if fixp arg2 and arg2 neq 0 then list(generatorname,arg2) @+else arg2)@/
where generatorname=get(bracketname,'generatorname) @;

@ The resimplification procedure |resimp_liebracket| is rather simple.
Each of the arguments can be:\medskip 
\item{1.} an integer: since the shorthand notation of generators is
hidden before simplification, this can only occur if there is an unwanted
mixing of the full and the shorthand notation for generators. Hence we
must stop with an error message in this case.
\item{2.} a generator: we have to strip off the generatorname and
represent it by its shorthand notation.
\item{3.} an algebraic list representing a nested commutator: we have
to replace |list| by the name of the liebracket and simplify the
whole commutator again.
\item{4.} any other algebra element: nothing special has to be done.
\enditem
The definition |update_argument| takes care of the necessary
actions. The variable |resimplify| indicates the necessity of
resimplification due to case 3.\ and should be local to the procedure
|resimp_liebracket|.

@d update_argument(arg)=@/
if fixp arg then rederr("SIMP_LIEBRACKET: argument contains a non algebra element")
else if operator_name_of arg=generatorname then arg:=first_argument_of arg
else if operator_name_of arg='list then @/
  <<resimplify:=t;arg:=bracketname . arguments_of arg>> @;

@ If both arguments are generators we have to check the vectorstructure
for further simplification, otherwise the kvalue list. This is done in
the procedures |simp_liebracket_vector| and |simp_liebracket_kvalue|,
respectively.

@u lisp procedure resimp_liebracket val;
begin scalar bracketname,generatorname,arg1,arg2,resimplify;
  bracketname:=operator_name_of val;
  generatorname:=get(bracketname,'generatorname);
  arg1:=first_argument_of val;arg2:=second_argument_of val;
  update_argument(arg1);update_argument(arg2);
  return 
    if resimplify then simp_liebracket list(bracketname,arg1,arg2)
    else 
      if fixp arg1 and fixp arg2
      then simp_liebracket_vector(bracketname,arg1,arg2)
      else simp_liebracket_kvalue(bracketname,arg1,arg2);
end$

@ Now we have dealt with ordinary commutators satisfactorily, it's
time to aim our attention to the nested commutators.  Notice that we
have defined an expression like $\lie(\{1,2\},2,3,4)$ to be nothing but
the expression $\lie(\lie(1,2),\lie(2,\lie(3,4)))$. Since we have already
treated list expressions as part of ordinary commutators, we only have
to reverse the list of arguments and compute the commutators
repeatedly.

@<Simplify nested commutator |val|@>=
begin scalar bracketname,arguments,result;
  bracketname:=operator_name_of val;
  arguments:=reverse arguments_of val;
  result:=simp_liebracket list(bracketname,second arguments,first arguments);@/
  arguments:=cddr arguments; %Chop first two arguments%
  for each arg in arguments do
    result:=simp_liebracket list(bracketname,arg,mk!*sq result);
  return result;
end @;

@*= Storing and retrieving values of commutators. In the following
sections we will explain how we are planning to store values of
commutators exactly. We recall that we have to make a clear
distinction between commutators of two generators, in which case we
want to store the values in a vector structure, and all other cases,
for which we want to store the values on the kvalue list.

@ We have seen in one of the previous sections that we have to store
$\lie(i,j)$ for $-n\leq i\leq j\leq m$, if $lie$ is a liebracket and
$m$ and $n$ the number even and odd generators, respectively.  There
are a few ways to store the values of these commutators in a vector
structure:\medskip 
\item{1.} put them all together in one vector and
supply a procedure to compute the index for a tuple $(i,j)$.
\item{2.} make a vector of vectors: put for all $i$ the vectors
containing the values of $\lie(i,j)$ for $i\leq j\leq m$ in a vector.
\enditem 
The second alternative has the advantage, that it is rather easy to
compute the indices, but we have to access two vectors to get the
value of a commutator. For the first alternative the index has a more
complex structure, but we have only to access one vector.  We have
compiled and tested both alternatives in a REDUCE version built on top
of Innovus Lisp on a HP9000 series at our site. In this
configuration the second alternative has proven to be the fastest.
Therefore we will use this one to store the values of commutators of
two generators.

The indices of a vector of dimension $N$ run from $0,\dots,N$.  Hence
the dimension of the outer vector structure must be $m+n$, which must
have for $-n\leq i\leq m$ as value at index $n+i$ the vector of
dimension $m-i$ containing the values of $\lie(i,j)$ for $i\leq j\leq
m$.  For each $-n\leq i\leq j\leq m$ we can add to the tuple $(i,j)$ a
couple of indices $(n+i,m-j)$ for the outer and the inner vector,
respectively.  Note that we use the inner vector structure in a
reverse way to keep the indices as short as possible.

@ We will store the vector structure of a liebracket |bracketname| on
the property list as the property |vector_structure|.  The dimensions
$m$ and $n$ of a liebracket are stored on the property list as the
properties |even_dimension| and |odd_dimension|, respectively.

Access to a vector is through the procedures |getv|, to
get a value, and |putv|, to store a value.  One
should be aware of the fact that |putv| doesn't make a new copy of the
vector, but replaces the value at the required index directly in the
physical memory. Therefore it is unnecessary to do a |putv| for the
outer vector structure when storing a commutator, because a |getv| for
the outer vector structure will return a vector, which we can change
directly in the physical memory at the right index with a |putv|.

There is one point which we haven't explained so far, but which
already has to be used here. Namely, to enable the computation of
Jacobi identities to be as efficient as possible, it is not enough for
each commutator just to store its value, but we have to store some
more information. Moreover, as explained in the introduction, we shall
also put the information about possible occurences of commutators in
the vector structure. For ordinary algebraic operators this kind of
information is recorded on the klist.
Therefore for each commutator we will store a dotted
pair of length 3, the |car| being additional information about the
commutator, the |cadr| being the replacement for the klist mechanism,
the |cddr| being its value.  

Although we won't explain the meaning of the two first items right
away, it is enough to know here that the additional information must
be initialized to |nil|. The part meant as the replacement for the klist 
mechanism must must be initialized to |nil|, if it is not present,
otherwise the old value must be taken.

We think that it is convenient to have procedures both to access the
entire vector structure as well as just the values of commutators.
Access to the vector structure is through the macros
|get_vector_structure| and |put_vector_structure|, access to the
values of commutators of two generators is through the macros
|get_commutator| and |put_commutator|, where the last two
simply use the first two.  The procedures don't perform range checking
on their parameters.

@d informative_part_of=car
@d k_info_and_commutator_part_of=cdr
@d k_info_of=cadr
@d commutator_part_of=cddr
@d get_vector_structure(bracketname,i,j)=@/
getv(getv(get(bracketname,'vector_structure),
              get(bracketname,'odd_dimension)+i),@|
         get(bracketname,'even_dimension)-j) @;
@d put_vector_structure(bracketname,i,j,value)=@/
putv(getv(get(bracketname,'vector_structure),
          get(bracketname,'odd_dimension)+i),@|
     get(bracketname,'even_dimension)-j,value) @;
@d get_commutator(bracketname,i,j)=@/
(if entry then commutator_part_of entry) 
  where entry=get_vector_structure(bracketname,i,j) @;
@d put_commutator(bracketname,i,j,value)=@/
(if old_value then 
  put_vector_structure(bracketname,i,j,nil . (k_info_of old_value) . value)
 else put_vector_structure(bracketname,i,j,nil . nil . value))
where old_value=get_vector_structure(bracketname,i,j) @;

@ Before we can write the procedures |simp_liebracket_vector| and
|simp_liebracket_kvalue| we have to explain how to get the arguments of a
commutator in a canonical order.

The macro |not_ordered_commutator| checks whether or not
the arguments of a commutator are well ordered.  It uses the standard
REDUCE procedure |ordp| and is written in such a way that a pair
$(i,j)$ for $i$,$j$ integer, $i\leq j$ is well ordered.

@d not_ordered_commutator(arg1,arg2)= @/
(if fixp arg1 and fixp arg2 then arg1>arg2 @+else
ordp(arg1,arg2) and arg1 neq arg2) @;

@ If the two arguments are not well ordered they must be switched.
Moreover, if not both arguments are odd a minus sign should be added.
Therefore we must have a function |even_element| to check if an
argument is even or not.

We have explained earlier that an argument of a commutator should be
an integer (namely, the number of the generator), a commutator with
two arguments, or another algebra element for which we have to check
the first parameter. Unfortunately, that is not the whole truth. There
is one exceptional situation for some specific application, which
should be added: in prolongation theory we will use Lie (super)algebra
valued functions. So far no problems, but these functions may also be
differentiated, in which case one will get other algebra elements.
However, an expression like |df(f(1),x)| doesn't belong in any of the
classes stated above. We can test if it is even or odd, by testing the
differentiated function. We add this as a special case.

@u
lisp procedure even_element(bracketname,exprn);
    if fixp exprn then exprn>0
    else if operator_name_of exprn=bracketname then
        ((b1 and b2) or (not b1 and not b2)) @| where
           b1=even_element(bracketname,first_argument_of exprn),
           b2=even_element(bracketname,second_argument_of exprn)
      else if operator_name_of exprn='df then
        even_element(bracketname,first_argument_of exprn) 
      else if fixp first_argument_of exprn then 
        first_argument_of exprn>0
      else stop_with_error("EVEN_ELEMENT: impossible to determine sign of",
                           exprn,nil,nil)$

@ Both in |simp_liebracket_vector| and |simp_liebracket_kvalue| the
arguments must be ordered canonically, hence we make that part a
module. Both procedures should have a local variable |sign|,
indicating if a sign must be added.

@<Order |arg1| and |arg2| canonically and possibly set |sign| to |t|@>=
if not_ordered_commutator(arg1,arg2) then
begin scalar h;
  sign:=(even_element(bracketname,arg1) or even_element(bracketname,arg2));@/
  h:=arg1;arg1:=arg2;arg2:=h; %Switch |arg1| and |arg2|%
end @;

@ Once |arg1| and |arg2| are ordered (i.e., |arg1|${}\leq{}$|arg2|), we
still have to check for integer valued |arg1| and |arg2| that
$-n\leq{}$|arg1| and |arg2|${}\leq m$, if $m$ and $n$ are the number
of even and odd generators, respectively.

@<Check if |arg1| and |arg2| are not out of range@>=
if arg1<-get(bracketname,'odd_dimension) or arg2>get(bracketname,'even_dimension) then
  stop_with_error("SIMP_LIEBRACKET:",list(bracketname,arg1,arg2),"out of range",nil) @;

@ After the preparations above the implementation of the procedure
|simp_liebracket_vector| is quite straightforward.  If the commutator
has a value, this value is simplified and returned as a standard
quotient, otherwise the commutator itself is returned as a standard
quotient. This last step is done by the standard REDUCE procedure
|mksq(kernel,pow)|, which returns |kernel| to the power |pow| as a
standard quotient, but also has a side effect that we will explain in
due time.

There is, however, one thing, which we should be well aware of.
Namely, if one of the arguments is zero, the commutator must be zero.
This can be achieved by initializing both $\lie(i,0)$ for
$i=-n,\dots,-1$ and $\lie(0,i)$ for $i=0,\dots,m$ to zero. Moreover
the commutators $\lie(i,i)$ with $i>0$ are zero. Hence these should
also be initialized to zero.  Moreover, as we will explain later on,
in some cases it will be necessary to resimplify the resulting
commutator, in order the get a well ordered standard quotient, which
will be treated in the right way by REDUCE. This case will be treated
in due time.

@u
lisp procedure simp_liebracket_vector(bracketname,arg1,arg2);
begin scalar sign,commutator;
  @<Order |arg1| ...@>;
  @<Check if |arg1| and |arg2|...@>;
  @<Get commutator |bracketname(arg1,arg2)| as a canonical standard quotient@>;
  return
    if sign then negsq commutator
    else commutator;
end$

@ The kvalue list of an algebraic operator is an association list, the
|car| of an element of which is a kernel of that operator, the |cadr|
its value. The kvalue list of an operator is stored on its propery
list as the property |kvalue|. As already explained, access to an
association list is through the procedure |assoc|.  Knowing this, we
can write the procedure |simp_liebracket_kvalue| without difficulty.

@u
lisp procedure simp_liebracket_kvalue(bracketname,arg1,arg2);
begin scalar sign,commutator;
  @<Order |arg1| ...@>;
  commutator:=assoc(list(bracketname,arg1,arg2),get(bracketname,'kvalue));@/
  commutator:=
    if commutator then simp cadr commutator
    else mksq(list(bracketname,arg1,arg2),1);
  return
    if sign then negsq commutator
    else commutator;
end$

@*= Assignment to commutators. With the simplification
procedure written above, we are able to retrieve values of
commutators.  As we have explained in the introduction, we need a
set-element-function |set_liebracket| to assign values to commutators.

This seems to be the appropriate moment to explain how one can assign
|value| to |kernel|. This is done by calling the procedure
|setk(kernel,value)|. If |kernel| is of the form $f(a_1,\dots)$,
where $f$ possesses the property |rtype|, which on its turn possesses a
property |setelemfn| (the set-element-function for that rtype), the
assignment is done by this set-element-function. In all other cases
the procedure |setk1| takes care of it.  So to
make the construction work in our case, we have to declare
any liebracket to be of rtype |liebracket| and assign to |liebracket| the
property |setelemfn|.

@ There is, however, one more thing to explain about rtypes:
commutators should not be recognized as objects of rtype |liebracket|
since this will lead to type mismatch problems throughout REDUCE.  To
get the rtype of an object REDUCE almost anywhere uses the procedure
|getrtype|, which, if provided, uses a rtypefn, to determine the rtype
of an object. Rtypefn's have one argument, which are the arguments of
the object, if this is not an atom, |nil| otherwise.
So if we do not want commutators to be recognized as objects of rtype
|liebracket|, we can simply return |nil| in all cases;

@<Lisp ini...@>=@/
put('liebracket,'rtypefn,'liebracket_rtypefn)$@/
put('liebracket,'setelemfn,'set_liebracket)$

@ 
@u
lisp procedure liebracket_rtypefn u;@/ nil$

@ There are, however, some points, which should be taken into
account, before we can write the procedure.  The first of this is,
that we want commutators only to adopt values which are actually
algebra elements. Hence we should check this condition if an
assignment is made.

The most convenient way to check if some expression is is an element
of the Lie (super)algebra is to use the procedure |independent_part|
of the TOOLS package. If the variable |algebra_elements| is the list
of all operators allowed as algebra elements, then the result of
calling |independent_part(value,algebra_elements)| is the part of
|value| independent of operator allowed as algebra element, hence for
a {\it valid\/} algebra element |value| 0.

@<Check if |value| is a valid algebra element@>= 
if independent_part(value,algebra_elements) neq 0 then
  rederr("SET_LIEBRACKET: assigned value invalid as algebra element") @;

@ We have already explained that it is not necessary or even
undesirable to assign values to commutators, which can be decomposed
into smaller components, using the bilinearity. For such an assignment
will never be used, since the simplification procedure of a liebracket
actually decomposes a commutator into is smallest components, before
trying to find any value.

Therefore both arguments of a commutator, which we want to assign a
value to, either have to be integer (as a shorthand notation for a
generator), or a single algebra element.  If they have the form $x(i)$
where |x| is the generatorname of liebracket |bracketname|, we must
strip off the generator, in order to get the commutator in a canonical
form.  Moreover generators should not exceed the maximal number of odd
or even generators, respectively.

The macro |check_and_strip_argument| checks one argument for its
validity, using the conditions stated in the previous section.
Because we have to satisfy a lot of conditions and we don't want the
procedure merely to exist out of error messages, we use a variable
|error| to indicate whether an error has occured or not.  In this way
we can do with one error message after all tests.  The variable
|error| has to be local at some higher level.  The macro
|wrong_atomic_argument| checks an atomic argument is an integer and
lies within the ranges of the liebracket.

@d wrong_atomic_argument(arg)=@/
((not fixp arg) or arg<-get(bracketname,'odd_dimension)
  or @| arg>get(bracketname,'even_dimension)) @;

@d check_and_strip_argument(arg)=@/
if atom arg then error:=wrong_atomic_argument(arg)
else begin
  error:=not member(operator_name_of arg,algebra_elements);
  if not error and operator_name_of arg=generatorname then
  begin
    arg:=first_argument_of arg;
    error:=not atom arg or wrong_atomic_argument(arg);
  end;
end @;

@<Prepare and check |arg1| and |arg2|@>=@/
check_and_strip_argument(arg1);
if not error then check_and_strip_argument(arg2);
if error then
  rederr("SET_/CLEAR_LIEBRACKET: argument(s) invalid or out of range") @;

@ There are a few ``special'' commutators which are initialized to
zero and should never be changed again. If $\lie$ is a liebracket,
these commutators are $\lie(i,i)=0$ for all $i>0$ (this follows
directly from the (graded) skew-symmetry and the fact that $x(i)$ is
even for $i>0$), $\lie(i,0)$ for $i=-n,\dots,-1$ and $\lie(0,i)$ for
$i=0,\dots,m$ (this has been explained in one of the previous
sections). Moreover, if a commutator has been used to solve other
commutators or generators using the Jacobi identity, it may be
dangerous to change this commutator. In the first case we must give an
error message, in the second case a warning will do.

This kind of information is most conveniently recovered from the
informative part of the vector structure. Without going into detail
right here, the following module will take care of the point raised
above. Note that |arg1| and |arg2| need to be we ordered for this check.

@d special=s

@<Check |arg1| and |arg2| for special or dangerous commutators@>=@/
  error:=@+if fixp arg1 and fixp arg2 then 
    (if entry then informative_part_of entry) 
      where entry=get_vector_structure(bracketname,arg1,arg2);
  if error then
    if car error='special then
      rederr("SET_/CLEAR_LIEBRACKET: commutator can not be changed")
    else message("SET_/CLEAR_LIEBRACKET: changing",
                 list(bracketname,arg1,arg2),"may lead to errors",nil) @;

@ With the modules written above we can implement the procedure
|set_liebracket| at once.  We |reval| both arguments before
continuing.  This is useful, because the simplification procedure does
the same.  Notice that a set-element-function doesn't need to return a
value.

@u
lisp procedure set_liebracket(val,value);
if length val neq 3 then
  rederr("SET_LIEBRACKET: assignment only possible to commutators")
else begin scalar bracketname,generatorname,algebra_elements,arg1,arg2,
                  error,sign;
  bracketname:=operator_name_of val;
  generatorname:=get(bracketname,'generatorname);
  algebra_elements:=bracketname . generatorname . get(bracketname,'algebra_elements);
  arg1:=reval first_argument_of val;
  arg2:=reval second_argument_of val;
  @<Prepare and check |arg1| and |arg2|@>;
  @<Order |arg1| and |arg2|...@>;
  @<Check |arg1| and |arg2| for special or dangerous commutators@>;
  value:=aeval value;
  @<Check if |value| is a valid algebra element@>;
  if sign then value:=mk!*sq negsq simp value;
  @<Store the assignment |bracketname(arg1,arg2):=value@;|@>;
end$

@ Before we can implement the remaining part of the
set-element-function of a liebracket, we have to say something about
the mechanism that controls the reevaluation of algebraic expressions
in REDUCE, the !*SQ prefixform.

An algebraic expression in !*SQ prefixform is a list of the form
(|!*sq| {\it standard\_quotient} [|t|$\vert$|nil|]).  If the last
element is |t|, no assignments have taken place after the last
simplification of the expression, which can affect its value. If it is
|nil|, the expression may have been affected by some assignment that
has taken place, so reevaluation is necessary.  If reevalutation is
necessary, it is clear that the |t|'s must be replaced by |nil| for
all algebraic expressions at a time. At this place it is not necessary
to explain how this can be accomplished, but it is sufficient to say that
the call |rmsubs()| does the job properly.

If a kernel has never been used in any other algebraic expression, it
is clear that it is unnecessary to call |rmsubs| if someone assigns a
value to this kernel. Therefore, for every kernel REDUCE keeps track
if it has been used in some other algebraic expression. For atoms this
is done by flagging them |used!*|, for operator elements it is recorded
on the so called klist of that operator.

Of course the standard REDUCE procedures respect this mechanism. But
we took the simplification of and assignment to commutators in our own
hands. Did we take enough precautions to respect this mechanism? Well,
a few sections ago, when implementing the simplification function of a
liebracket, we mentioned, but did not explain a side effect of the
procedure |mksq| which we used to convert a kernel to a standard
quotient. This seems to be the right moment to explain that this side
effect is the recording of the fact that the kernel is used by
flagging it |used!*| or putting it on the klist. 

This partially solves our problem, for if a unknown commutator is used
in some other algebraic expression it will be simplified by
|simp_liebracket| which makes it a standard quotient by calling
|mksq|. On the other hand, as experience showed, for a liebracket of average 
length, the klist may get a length of about 10000 to 20000 elements
and reduce the performance of the entire system in an quite drastic way.

Therefore we will partially replace the klist mechanism for a
liebracket by storing the klist information as an additional entry in
the vector structure, just for those commutators whose
value is also stored in the vector structure. 

In order to make this new construction work it turns out that two
standard REDUCE procedures have to be adapted. These changes are explained in
the last section of this document.

@ If we do an assignment to a commutator we must call
|rmsubs| if necessary. Without going into the matter too deep right
here, we will simply give a macro definition which checks if an
operator element is used.

@d used_operator_element(opr_el)=@/
   'used!* memq cddr fkern opr_el@;

@ If the two arguments of the commutator which we want to store are
integers, we must use the vector structure to store it and eventually
call |rmsubs| ourselves, otherwise it must be stored on the kvalue
list. In the last case the standard REDUCE procedure |setk1| takes care
of everything.

@<Store the assignment |brack...@>=
if fixp arg1 and fixp arg2 then 
begin
  if used_operator_element(list(bracketname,arg1,arg2)) then rmsubs();
  put_commutator(bracketname,arg1,arg2,value); 
end else
  setk1(list(bracketname,arg1,arg2),value,t)  @;

@*= Clearing liebrackets.  There is one aspect of the access to
liebrackets and/or commutators which we have left out of sight so far
deliberately, namely how to clear these objects.  Clearing expressions
and/or operators in REDUCE is done by the procedures |clear| and
|clear1|, the last one of which does its job by two subsequent calls
of the procedure |let2| with different parameters.

In earlier versions of this package we used the procedure |clear| to
clear commutators, but it seemed impossible to use it to clear an
entire liebracket, because a liebracket isn't just an ordinary rtype.
The only possibility to let this construction work for commutators,
was to jump through some procedures in an obscure and illogical way
and finally let the clearing take place in the simplification
procedure depending on the flag |subfg!*|.  Clearing of an entire
liebracket was done by a procedure of itself.

In this version we will do the job in a more logical way by changing
the standard REDUCE procedure |clear| in such a way that the clearing
of both commutators and liebrackets will take place in a procedure of
itself.  The idea behind this change is quite simple: if the object to
be cleared is of some rtype which on its turn possesses the property
|clearfn|, then apply |clearfn| to it, otherwise proceed as before.
In that way it resembles the procedure |setk|, which uses a
set-element-function for rtypes.

Note that |clear| has the property |stat='rlis| which means that it
can have an arbitrary number of arguments separated by commas, which
the parser will pass to it as a list. Hence also |clear1|, which is
called by |clear|, will have its argument as one list. 

Notice that we can't use |getrtype| to get the rtype of an operator
element since |getrtype| will, for instance, not recognize a
commutator to be an element of the rtype liebracket.

@u
lisp procedure clear1 u;
   begin scalar x,xx;
      while u do
         <<if flagp(x := car u,'share)
             then if not flagp(x,'reserved) then set(x,x) else rsverr x
            else if eqcar(x,'list)
                   then u := nil . append(cdr x,cdr u)
            else if eqcar(x,'replaceby) then rule!-list(list x,nil)
            else if smemq('!~,x)
             then if eqcar(x,'equal) then rule!-list(list x,nil)
                   else rule!-list(list list('replaceby,x,nil),nil)
            else if (xx:=get(if atom x then x @+else car x,'rtype)) 
                    and (xx:=get(xx,'clearfn))
                 then apply1(xx,x)
            else @+<<let2(x,nil,nil,nil); let2(x,nil,t,nil)>>;
           u := cdr u>>
   end$

@ The clearfn of a liebracket will be the procedure |clear_liebracket|.
This has to be placed on the property list of |liebracket|.

@<Lisp ini...@>=@/
 put('liebracket,'clearfn,'clear_liebracket)$ 


@ The procedure |clear_liebracket| is rather simple: if its argument
is an atom, we have to clear an entire liebracket by removing all its
properties, otherwise the argument should be a commutator. 

@u
lisp procedure clear_liebracket val;
if atom val then @<Remove all properties of liebracket |val|@>
else if length val = 3 then @<Clear commutator |val|@>
else rederr("CLEAR_LIEBRACKET: wrong number of arguments to commutator")$


@ Clearing a commutator is almost the same as assigning |nil| to it.
Therefore we have to manipulate the arguments in the same way as in
the procedure |set_liebracket|, except that we need not incorporate a
possible change of sign.  We copy it without comment.

@<Clear commutator |val|@>= 
begin scalar bracketname,generatorname,algebra_elements,arg1,arg2,error,h;
  bracketname:=operator_name_of val;
  generatorname:=get(bracketname,'generatorname);
  algebra_elements:=bracketname . generatorname . get(bracketname,'algebra_elements);
  arg1:=reval first_argument_of val;
  arg2:=reval second_argument_of val;
  @<Prepare and check |arg1| and |arg2|@>;
  if not_ordered_commutator(arg1,arg2) then
  begin
    h:=arg1;arg1:=arg2;arg2:=h;  %Switch |arg1| and |arg2|%
  end;
  @<Check |arg1| and |arg2| for...@>;
  @<Clear commutator |bracketname(arg1,arg2)|@>; 
end @;

@ If |arg1| and |arg2| are integers, we have to clear an entry in the
vector structure, otherwise we have to clear the commutator by
replacing the kvalue list of |bracketname| by the old kvalue list with
one entry removed.  Note that there is no need to update the !*SQ
prefixforms by calling |rmsubs|, since the calling procedure |clear|
has already taken care of that.

@<Clear commutator |bra...@>=@/
val:=list(bracketname,arg1,arg2);
if fixp arg1 and fixp arg2 then
  if get_commutator(bracketname,arg1,arg2) then @|
     put_commutator(bracketname,arg1,arg2,nil)
  else message("CLEAR_LIEBRACKET:",val,"not found",nil)
else begin scalar kvalue;
  kvalue:=get(bracketname,'kvalue);
  if (h:=assoc(val,kvalue)) then
    put(bracketname,'kvalue,delete(h,kvalue))
  else message("CLEAR_LIEBRACKET:",val,"not found",nil);
end @; 

@*= Tools for solving Jacobi identities. We have gathered
enough material now to implement one of the main tasks of this
package, namely the computing and solving of Jacobi identities in
order to find new relations between commutators and generators. To
accomplish this, we have to do the following things in succession:
first we have to find all triples $(i,j,k)$ with $i,j,k$ integer that
satisfy all conditions such that the Jacobi identity for $x(i)$,
$x(j)$ and $x(k)$ may lead to a new relation and secondly, for each
triple $(i,j,k)$ found in the first step, we must compute this Jacobi
identity and solve it.

\bigskip
In the sections where we specified the requirements for a
liebracket, we found that it is interesting to compute and solve the
Jacobi identities for all $x(i)$, $x(j)$ and $x(k)$ such that all
three commutators $\lie(i,j)$, $\lie(j,k)$ and $\lie(i,k)$ are a
linear combination of generators. For these Jacobi identities (may)
lead to new relations between generators and/or commutators of two
generators, which are the main object of our interest.

How must we proceed to find all triples $(i,j,k)$ that satisfy the
conditions stated above? Well, a typical sequence of actions while
trying to compute (part of) a Lie (super)algebra could be: introduce
some new generators as names for unknown commutators (i.e., assign the
generators to these commutators) and try to find new relations implied
by Jacobi identities containing these commutators. Hence we could
proceed as follows: first find all ``new'' commutators $\lie(i,j)$
which are a linear combination of generators (by ``new'' we mean those
commutators which haven't been processed before). Then, if $\lie(i,j)$
is such a commutator, $(i,j,k)$ is a triple for which the Jacobi
identity has to be checked, if both $\lie(i,k)$ and $\lie(j,k)$ are
linear combinations of generators. It is easily seen that proceeding
this way one will find all Jacobi identities solvable until that
stage.

There is one aspect which we haven't explained yet: how do
we recognize commutators which have already been processed. The
observant reader will remember that we used the vector structure not
only to store values of commutators, but also reserved a part for
additional information about the commutator, initialized to |nil|.
It is clear that we can use it right here to mark commutators which
have already been processed.

\bigskip
There is, however, another purpose for which we will use the
``informative'' part of the vector structure, namely to indicate if
the computation of a Jacobi identity can be done more efficiently,
which is very important because of the large amount of Jacobi
identities we have to compute.  For this look at a characteristic term
of a Jacobi identity, say $\lie(i,\lie(j,k))$, and suppose that
$\lie(j,k)=\sum_q a_q*x(q)$, a linear combination of generators. Hence
we have to compute $\lie(i,\sum_q a_q*x(q))$ or using the bilinearity
$\sum_q a_q*\lie(i,q)$.  Computing this kind of expression by simply
applying |simp_liebracket| to it, we (have to) use the procedure
|operator_coeff| to get all $x(q)$'s and $a_q$'s every time we come
across $\lie(j,k)$.

It would be much more efficient, if the value of $\lie(j,k)$ were
stored in such a way, that there is no need to use the procedure
|operator_coeff| to get all $x(q)$'s and $a_q$'s. This can indeed be
done, if we take advantage of the way how standard forms in REDUCE are
build up. Using the procedure |get_all_kernels|, described in the
TOOLS package, and the standard REDUCE procedure |reorder|, it is very
easy to accomplish that the $x(q)$'s occur as leading variable of (a
reduced part of) the value of $\lie(j,k)$ and the $a_q$'s as leading
coefficient.

If $\lie(j,k)$ is a reordered sum of generators and we want to compute
$\lie(i,\lie(j,k))$ using this reordering, we cannot simplify
$\lie(j,k)$ during the computation because this would destroy the
special ordering we imposed. This implies that we should think about
what to do if we find a linear dependency between some generators and
solve it for one of them, let's say $x(q)$. For suppose this $x(q)$
occurs in the value of $\lie(j,k)$, then computing $\lie(i,\lie(j,k))$
using the reordering, would lead to a term $\lie(i,q)$ which is not
desirable because of the linear dependency found. A solution to this
problem would be, if we find a linear dependency and solve it for
$x(q)$, to assign to all $\lie(i,q)$'s a value according to this
linear dependency.

The most convenient way to implement this is by making a Lie
(super)algebra generator a rtype of itself, |algebra_generator|, and
assigning a set-element-function and a clear function to it, which
take care of all the necessary actions. Moreover, this offers us the
possibility do some more checks. For instance, in order to keep the
solving of Jacobi identities act as we intended, we only  want to
allow assignments to a generator, which are linear combinations of
other generators. For if we would allow this, we would possibly get
Jacobi identities, marked as solvable by the process described above,
containing commutators with non-integer arguments, for which we
certainly don't want to solve. We will write these procedures in a
next chapter.

@ In the previous sections we have seen to which purposes we can use
the informative part of the vector structure. Before describing its
contents exactly, we will add one other application. Namely, for
whatever reason, we may want to compute all Jacobi identities again,
so it must be possible to indicate if all Jacobi identities containing
some commutator have to be recomputed. Therefore, we can distinguish
the following three conditions for each commutator:\medskip

\item{1.} the commutator hasn't been reordered and hence hasn't been
checked until now. This is the initial status for every commutator and
is indicated by |nil| (we already used this in the procedure
|put_commutator|).

\item{2.} the commutator has both been reordered and checked. This is
indicated by |'(t)|.

\item{3.} the commutator has been reordered, but must be
checked again. This is indicated by |'(nil)|.  

\enditem
If we want to recompute all Jacobi identities for some liebracket,
|'(t)| has to be replaced by |'(nil)| for each commutator in the
vector structure of this liebracket, which has already been checked.
To accomplish this we will use a mechanism similar to the one used for
!*SQ prefixforms. These are constructed by |cons|'ing 
|'!*sq . @t{\it standard\_quotient}@> . !*sqvar!*|, 
where |!*sqvar!*| is a list |'(t)|.  In doing so, the |t| of !*SQ
prefixforms can be replaced by |nil| {\it globally}, by replacing the
|car| of |!*sqvar!*| by |nil| with the procedure |rplaca|. This
construction works because |rplaca(alist,new_car)| doesn't replace the
|car| of |alist| by making a new copy |new_car . cdr alist|, but
replaces the |car| in the physical memory.

We will also |cons| a variable |!*jacobi_var!*| with value |'(t)| to
each reordered commutator in the vectorstructure of a liebracket.
However, in our case we don't want to replace the |t| by |nil|
globally, but only for one liebracket at a time. Therefore each
liebracket should have its own variable |!*jacobi_var!*|. It should be
placed on the property list of the liebracket under consideration as
the property |!*jacobi_var!*|.

The procedure |recompute_jacobi_identities_of| takes care of this
replacement and also puts a new copy of |!*jacobi_var!*| on the
property list. This procedure should be available in algebraic mode.

We foresee that we have to check if |bracketname| is a liebracket in
a lot of procedures. In order to be able print an appropriate error
message we will make definition to deal with it. For convenience we
will also write a definition which checks the validity of a generator.

@d check_if_bracketname_is_a_liebracket_in(proc)=@/
  if get(bracketname,'rtype) neq 'liebracket then@|
    stop_with_error(proc,bracketname,"is not a liebracket",nil) @;
@d check_if_generatorname_is_a_generator_in(proc)=@/
  if get(generatorname,'rtype) neq 'algebra_generator then@|
    stop_with_error(proc,generatorname,"is not an algebra generator",nil) @;

@u
lisp operator recompute_jacobi_identities_of;

lisp procedure recompute_jacobi_identities_of bracketname;
begin scalar !*jacobi_var!*;
  check_if_bracketname_is_a_liebracket_in("RECOMPUTE_JACOBI_IDENTITIES:");
  !*jacobi_var!*:=get(bracketname,'!*jacobi_var!*);
  rplaca(!*jacobi_var!*,nil);
  put(bracketname,'!*jacobi_var!*,list t);
end$

@*1 Finding the unprocessed commutators. After the introduction above
we are able to take care of the first part of finding the solvable
Jacobi identities, namely collecting all commutators which are a sum
of generators and haven't been processed until now.  If we find such a
commutator we must (a) reorder it in such a way that all generators
occur in it as leading variables, (b) put it on a list of all
commutators which have to be processed and (c) mark it processed in
the vector structure. These three steps are implemented in the
procedure |find_unprocessed_commutators_of|.

In |find_unprocessed_commutators_of| we need quite a lot of
properties of the liebracket under consideration. Some of them we have
already met before, but there are also a few, which need some
explanation right now. 

First of all we will store the list of unprocessed commutators on the
property list as the property |commutator_list|, in order to keep the
system as fool proof as possible.  Namely, if we would keep this list
as a local variable in |find_unprocessed_commutators_of| it could be
destroyed by some user break, while in the vector structure these
commutators were already marked as being processed. In that way we
could loose some Jacobi identities.
Because of the possibility of an user break we must be aware of the fact
that this list may not be empty. Hence in all cases we must |cons| new
commutators in front of it.

Secondly we should be aware of the fact that not all commutators have
to be used. Hence it is useless to check commutators which contain
unused commutators. The number of used even and odd generators is
stored on the property list of a liebracket as the properties
|even_used| and |odd_used| respectively.

The following definition sums up all the properties and variables
necessary to access the vector structure directly, we can use it in
several places. The module following it initializes them. Recall that
we used the letter $m$ for the number of even generators and $n$ for
odd generators.

@d properties_for_direct_access=@/
vector_structure,m,m_used,n,n_used

@<Initialize properties for direct access@>=@/
  vector_structure:=get(bracketname,'vector_structure);@/
  m:=get(bracketname,'even_dimension);n:=get(bracketname,'odd_dimension);@/
  m_used:=get(bracketname,'even_used);n_used:=get(bracketname,'odd_used) @;

@ The properties necessary in the procedure
|find_unprocessed_commutators_of| are listed below. The module
following it initializes them. The variable |non_generators|
represents all operators, except the generator, that are allowed as
algebra element.

@d necessary_properties_for_finding_commutators=@;@/
properties_for_direct_access,generatorname,non_generators,
commutator_list,!*jacobi_var!*

@<Get all necessary properties for finding commutators@>=
  @<Initialize properties for direct access@>;
  generatorname:=get(bracketname,'generatorname);@/
  non_generators:=bracketname . get(bracketname,'algebra_elements);@/
  commutator_list:=get(bracketname,'commutator_list);@/
  !*jacobi_var!*:=get(bracketname,'!*jacobi_var!*) @;

@ The procedure |find_unprocessed_commutators_of| is quite
straightforward. Note that we don't make an exception for the
``special'' commutators |bracketname(i,j)| with $i=0$ or $j=0$ or
$i=j>0$. Of course we don't want these commutators to be processed any
further.  This means that they must be initialized as already being
processed.

Also another category of commutators need not be processed, namely the
commutators of generators which have been found linear dependent.
Checking of Jacobi identities for linear dependent generators boils
down to checking a linear combination of Jacobi identities for linear
independent generators. Thus we shouldn't mark commutators of linear
dependent generators as processed. 

Recall that the data of commutator |bracketname(i,j)| are stored in
the vector structure at indices $n+i$ and $m-j$ for the outer and
inner vector, respectively. 

@u
lisp procedure find_unprocessed_commutators_of bracketname;
begin scalar vector_i,entry_i_j,k_info_i_j,commutator,form,kord!*,
    necessary_properties_for_finding_commutators,comm_list_i,
    dependent_generators;
  @<Get all necessary properties for finding com...@>;
  @<Find the |dependent_generators|@>;
  for i:=-n_used:m_used do 
  if not memq(i,dependent_generators) then
    begin
      vector_i:=getv(vector_structure,n+i);
      for j:=i:m_used do 
      if not memq(j,dependent_generators) then @|
        @<Mark |bracketname(i,j)| processed, if it is a sum of generators@>;
    end;
  return commutator_list;
end$

@ Finding the dependent generators can be easily done using the kvalue
list of |generatorname|. Of course we only need to store the index of
each dependent generator.

@<Find the |dependent_generators|@>=
dependent_generators:=
  for each entry in get(generatorname,'kvalue) collect
    first_argument_of first_element_of entry

@ An entry in the vector structure consists of a informative part (the
|car|) and the klist and commutator part (the |cdr|). The following
definitions translate some conditions of the informative part (which
we have defined in one of the previous sections) into their lisp
equivalents.

@d not_processed=null car
@d recomputation_necessary_for=null caar

@ A standard form belonging to an algebra element is a sum of
generators, if it contains no kernels of all other operators allowed
as algebra elements. We can check this most conveniently by using the
procedure |get_all_kernels|, which acts on standard forms and is
described in the TOOLS package. Recall that the variable
|non_generators| is the list of all operators other then the
generator, allowed as algebra element.

@d sum_of_generators(algebra_element)=@/
   null get_all_kernels(algebra_element,non_generators) @;

@ If a commutator is a sum of generators the following things should
be done:\medskip
\item{1.} it has to be reordered in such a way that all generators
occur as leading variables of (a reduced part of) it. One should
remember that reordering in REDUCE is done by the procedure |reorder|,
which works on standard forms (this is described in more detail in the
TOOLS package). Note that we rebinded the fluid system variable
|kord!*| in the procedure |find_unprocessed_commutators_of|. In doing
so the kernel ordering outside this procedure will not be affected.
The definition |convert_form_into_reordered_commutator| takes care of
the reordering.

\item{2.} the commutator list must be updated. We store the indices
$i$ and $j$ on it, since these contain all the necessary information.
We will, however, use an association list on $i$, i.e., the smallest
index, to store $i$ and $j$, because the number of commutators to be
processed may be rather big.  To keep the system fool proof we put the
updated commutator list on the property list of the liebracket for
each commutator separately.  This part is taken care of by the
definition |update_commutator_list|. Notice the use of |rplacd| to
replace the |cdr| of nested lists. It is easily checked that this
causes no harm. Due to the use of |rplacd| we do not have to store
|commutator_list| on the property list of |bracketname|. If there is,
however, no entry on |commutator_list| for $i$, we have to extend
|commutator_list| with it and do store it.

\item{3.} the entry in the vector structure has to marked as checked.
This can be done by storing |!*jacobi_var!* . k_info_i_j . commutator|
at the right place in the inner vector, where |k_info_i_j| is the
|k_info| value of the $(i,j)$-th entry of the vector structure. The definition
|mark_entry_as_checked| takes care of it.

@d convert_form_into_reordered_commutator=@/
  setkorder get_all_kernels(form,generatorname);@/
  commutator:=!*ff2a(reorder form,denr commutator) @;
@d update_commutator_list=@/
   if (comm_list_i:=assoc(i,commutator_list)) then@/
      (if not member(j,comm_list_i) then
         rplacd(comm_list_i,j . cdr comm_list_i))
   else @+
   <<commutator_list:=list(i,j) . commutator_list;
     put(bracketname,'commutator_list,commutator_list)>> @;
@d mark_entry_as_checked=@/
   putv(vector_i,m-j,!*jacobi_var!* . k_info_i_j . commutator) @;

@ If a commutator has not been checked so far, we should only process
it now, if it is a sum of generators. Commutators, for which
recomputation is necessary, don't have to be reordered, since this has
already been done the first time they were checked.

@<Mark |brac...@>=
begin
entry_i_j:=getv(vector_i,m-j);
if entry_i_j and commutator_part_of entry_i_j then
  if not_processed entry_i_j then 
  begin
    commutator:=simp!* commutator_part_of entry_i_j;
    k_info_i_j:=k_info_of entry_i_j;
    form:=numr commutator;
    if sum_of_generators(form) then begin
       convert_form_into_reordered_commutator;
       update_commutator_list;
       mark_entry_as_checked;
    end;
  end
  else if recomputation_necessary_for entry_i_j then begin
    commutator:=commutator_part_of entry_i_j;
    k_info_i_j:=k_info_of entry_i_j;@/
    update_commutator_list;
    mark_entry_as_checked;
  end;
end @;

@*1 Finding the unsolved Jacobi identities. With help of the procedure
described above we have found a list of unprocessed commutators and
put it on the property list of the liebracket under consideration. Our
next task is for each commutator on this list to find the unsolved
Jacobi identities belonging to it.  If $(i,j)$ is a couple of indices
of the commutator list, the solvable Jacobi identities are represented
by all triples $(i,j,k)$ for which both |bracketname(i,k)| and
|bracketname(j,k)| are a sum of generators, i.e., are marked as
processed in the vector structure.

It is easy to see that the (graded) Jacobi identity
 $$(-1)^{\vert x\vert\cdot\vert z\vert }[x,[y,z]]+
  (-1)^{\vert y\vert \cdot\vert x\vert}[y,[z,x]]+ 
  (-1)^{\vert z\vert \cdot\vert y\vert }[z,[x,y]]=0$$ 
in case of equality of some of the elements $x$, $y$ and $z$ sometimes
is fulfilled automatically, depending if $x$, $y$ and $z$ are odd or
even.  If we want to compute Jacobi identities for $x(i)$, $x(j)$ and
$x(k)$ with $i\leq j\leq k$ the reader should check that only the
following ranges for $i$, $j$ and $k$ give rise to meaningful
identities (i.e., identities which are not fulfilled automatically):
(1) $i\leq j\leq k < 0$, (2) $i\leq j <0<k$, (3) $i<0<j<k$ and (4)
$0<i<j<k$.  Moreover it is easily seen that these conditions are
satisfied if and only if none of the commutators $\lie(i,j)$,
$\lie(i,k)$ and $\lie(j,k)$ is one of the ``special'' commutators
$\lie(p,q)$ with $p=0$ or $q=0$ or $p=q>0$.  We recall that we
expected these ``special'' commutators to be initialized to zero and
to be marked as processed. Now the condition ``marked as processed''
only means that the informative part of an entry in the vector
structure is a list whose |car| is |t| (i.e., has a value) or |nil|
(i.e., has no value), indicating whether or not recomputation of
Jacobi identities for this commutator is necessary.  In the light of
what we have said in this section it seems not a bad idea to mark
these ``special'' commutators as special. We can do this by
initializing the informative part of an entry in the vector structure
to |'(special)|. One can easily check that this does not affect the
condition ``marked as processed''.

Hence if we have to find all meaningful triples $(i,j,k)$ belonging to
an unprocessed commutator represented by the couple $(i,j)$ with
$i\leq j$, we have to check the commutators (1) |bracketname(k,i)| and
|bracketname(k,j)| for $-n_{\rm used}\leq k\leq i-1$, (2)
|bracketname(i,k)| and |bracketname(k,j)| for $i\leq k\leq j-1$ and
(3) |bracketname(i,k)| and |bracketname(j,k)| for $j\leq k\leq m_{\rm
used}$ to be marked as processed, but not special, where $m_{\rm
used}$ and $n_{\rm used}$ are the number of even and odd generators
which have been used so far. The macro |processed_but_not_special|
checks this for an entry of the vectorstructure.

@d processed_but_not_special(entry)=@/
   (car entry and caar entry neq 'special) @;

@ As in the case of finding the unprocessed commutators we will store
the list of solvable Jacobi identities on the property list of the
liebracket under consideration as the property |identity_list|.
In this section we will initialize all necessary properties for
finding Jacobi identities.

@d necessary_properties_for_finding_identities=@/
properties_for_direct_access,commutator_list,identity_list

@<Get all necessary properties for finding identities@>=
  @<Initialize properties for direct access@>;
  commutator_list:=get(bracketname,'commutator_list);@/
  identity_list:=get(bracketname,'identity_list) @;

@ If a Jacobi identity $(i,j,k)$ is solvable, depends on the $(i,k)$-th
and $(j,k)$-th entry of the vector structure and it has only to be stored
if it has not been stored before. These conditions are checked by the
definition |check_and_store_identity|. Its argument is a triple
$i,j,k$ with $i\leq j\leq k$. 

We will store the Jacobi identities to be solved on a double
association list |identity_list|, as the number of them may increase
very rapidly, in which case linear search would be too time consuming.
Storing a Jacobi identity on |identity_list| is taken care of by the
macro |update_identity_list|.

@d check_and_store_identity(i,j,k)=@/
  if processed_but_not_special(entry_i_k) and
     processed_but_not_special(entry_j_k) 
  then update_identity_list(i,j,k) @;
@d update_identity_list(i,j,k)=@/
  if (id_list_i:=assoc(i,identity_list)) then
     if (id_list_i_j:=assoc(j,cdr id_list_i)) then @/
        (if not member(k,cdr id_list_i_j) then
            rplacd(id_list_i_j,k . cdr id_list_i_j))
     else rplacd(id_list_i,list(j,k) . cdr id_list_i)
  else identity_list:=list(i,list(j,k)) . identity_list @;

@ The procedure |find_Jacobi_identities_of| essentially consists of a
double |while| loop in which we try to find solvable Jacobi identities for
each commutator on the |commutator_list| of a liebracket. Commutators
which have been checked may be removed from the |commutator_list|.
As in |find_unprocessed_commutators_of| we will use |rplacd| to alter
the inner lists of |commutator_list|.

@u
lisp procedure find_Jacobi_identities_of bracketname;
begin scalar comm_list_i,i,j,vector_i,vector_j,vector_k,
             entry_i_k,entry_j_k,
             necessary_properties_for_finding_identities,
             id_list_i,id_list_i_j;
  @<Get all necessary properties for finding id...@>;
  while commutator_list do begin
    comm_list_i:=first_element_of commutator_list;
    i:=car comm_list_i;
    while cdr comm_list_i do begin
      j:=cadr comm_list_i;
      @<Find and store all Jacobi identities for |i| and |j|@>;
      rplacd(comm_list_i,cddr comm_list_i);
    end;
    commutator_list:=rest_of commutator_list;@/
    put(bracketname,'commutator_list,commutator_list);
  end;
return identity_list;
end$

@ Finding and storing all Jacobi identity for a couple $i,j$ consists
of three phases which differ in the way they get the $(i,k)$-th
and $(j,k)$-th entry of the vector structure. After we
have found all identities belonging to $i,j$ we must save the updated
|identity_list| on the property list of the liebracket under
consideration. Saving it once for a commutator pair $i,j$ will do
since at this stage the commutator pair has not been removed from
the commutator list yet.

@<Find and store all ...@>=@/
vector_i:=getv(vector_structure,n+i);
vector_j:=getv(vector_structure,n+j);
for k:=-n_used:i-1 do begin
  vector_k:=getv(vector_structure,n+k);
  if (entry_i_k:=getv(vector_k,m-i)) and (entry_j_k:=getv(vector_k,m-j)) then
    check_and_store_identity(k,i,j);
end;
for k:=i:j-1 do begin
  vector_k:=getv(vector_structure,n+k);
  if (entry_i_k:=getv(vector_i,m-k)) and (entry_j_k:=getv(vector_k,m-j)) then
    check_and_store_identity(i,k,j);
end;
for k:=j:m_used do begin
  if (entry_i_k:=getv(vector_i,m-k)) and (entry_j_k:=getv(vector_j,m-k)) then
    check_and_store_identity(i,j,k);
end;@/
put(bracketname,'identity_list,identity_list) @;

@*1 Computing special Jacobi identities. The procedures developed so
far supplied us with a list of triples $(i,j,k)$ with $i\leq j\leq k$
such that all three commutators $\lie(i,j)$, $\lie(i,k)$ and
$\lie(j,k)$ are linear combinations of generators and are stored in a
reordered form, which facilitates a fast computation of the nested
commutators of the Jacobi identity for $x(i)$, $x(j)$ and $x(k)$. In
the following sections we will write the procedure
|special_Jacobi_identity| that performs the next step, namely the
actual computation of a Jacobi identity for a triple $(i,j,k)$
satisfying the requirements stated above.

To explain the idea behind the calculation of the Jacobi identity,
suppose we have a triple $i,j,k$ as stated above. Then by assumption
we have $\lie(j,k)=\sum a^l_{jk}x(l)$ so that
$\lie(i,\lie(j,k))=\sum a^l_{jk}\lie(i,l)$. Now the right hand side of
the last expression can be computed rather easily by using the
reordering imposed on the commutator $\lie(j,k)$ as we will see in
the sequel. One should be aware that is not possible to simplify the
expression for $\lie(j,k)$ before using it, because this will destroy
the reordering. Therefore we have to take into account the following
points:\medskip
\item{1.} In case one of the generators $x(l)$ has been found linear
dependent of other generators, we must see to it that $\lie(i,l)$
evaluates to the right value. As we have already explained this will
be taken care of by the set-element-function for generators.
\item{2.} The coefficient $a^l_{jk}$ must be simplified before usage.
\item{3.} $\sum a^l_{jk}\lie(i,l)$ must be evaluated to the right
value, i.e., we must take care that substitutions for products and
powers take place properly. This can be achieved by calling the
standard REDUCE procedure |subs2| on the simplified expression. A
search for substitution of powers is only performed if the fluid
system variable |!*sub2| is set to |t|.  If necessary this is done
automatically by low level procedures used during ordinary
simplification, depending if a kernel in the simplified expression
occurs on the list of power substitutions, |powlis!*|. After a call of
|subs2| |!*sub2| will always be |nil|, so that it can be used for the
next expression to be simplified. |!*sub2| also occurs on the so
called |initl| of REDUCE. Variables occuring on the |initl| are
initialized to an initial value before every command.

@ The procedure |sub_identity| calculates a general term 
$(-1)^{\vert x(i)\vert\cdot\vert x(k)\vert}\lie(i,\lie(j,k))$ of the
Jacobi identity using the method described above. To achieve this we
must use the numerator of $\lie(j,k)$ (which is a standard form) to
add up all terms of $\lie(i,\lie(j,k))$. If $\lie(j,k)$ is zero,
|sub_identity| also is zero, otherwise by assumption the main variable
|mvar| of the numerator of $\lie(j,k)$ is a generator, the leading
coefficient |lc| its coefficient. The same applies to the reductum
|red| of the standard form. Therefore the summation can simply be
performed in a |while| loop. Standard quotients can be added,
subtracted, multiplied and divided by the procedures |addsq|,
|subtrsq|, |multsq| and |quotsq| respectively.

To simplify the coefficients we can use the procedure |subf1| which
simplifies a standard form to a standard quotient. Its first argument
is the standard form to be simplified, the second argument a list of
substitutions to be performed (in our case |nil|).

Recall that the commutators are stored as !*SQ prefixforms. To get the
unsimplified standard quotient of a !*SQ prefixform we should simply
take its |cadr|.

@d simp_sf_to_sq(sf)=subf1(sf,nil)@;
@d get_sq_of=cadr

@u 
lisp procedure sub_identity(bracketname,i,j,k);
begin scalar comm_j_k,denr_j_k,coeff_l,l,comm_i_l,term;
comm_j_k:=get_commutator(bracketname,j,k);
return if comm_j_k= 0 then nil . 1 else
begin
  comm_j_k:=get_sq_of comm_j_k;
  denr_j_k:=simp_sf_to_sq(denr comm_j_k); 
  comm_j_k:=numr comm_j_k;
  @<Add all terms of $\lie(i,|comm_j_k|)$ up to |term|@>;
  if i<0 and k<0 then term:=negsq term; 
            @+%Add a sign if $x(i)$ and $x(k)$ are odd%
  return quotsq(term,denr_j_k);
end;
end$

@ One should notice that we don't check during the assignment to a
commutator if all generators occuring in the assigned value are valid.
Since the call of |simp_liebracket_vector| checks the validity of
integer arguments of a commutator, we only have to check if the
generators occuring have integer arguments here.

@<Add all terms of $\lie(i,|comm_j_k|)$ up to |term|@>=
  term:=nil . 1; %Initialize |term| as standard quotient%
  while comm_j_k do begin
     l:=first_argument_of mvar comm_j_k;
     coeff_l:=simp_sf_to_sq(lc comm_j_k);
     if not fixp l then
        stop_with_error("SOLVE_JACOBI_IDENTITIES:",list(bracketname,j,k),
                        "contains invalid generator",mvar comm_j_k);
     comm_i_l:=simp_liebracket_vector(bracketname,i,l); 
     term:=addsq(term,multsq(coeff_l,comm_i_l));
     comm_j_k:=red comm_j_k;
  end @;

@ The procedure |special_Jacobi_identity| can now be written at once. We add
an additional minus sign because in most cases this will neutralize a
minus sign in the output. Since |sub_identity| expects its arguments
to be ordered, we have to switch |k| and |i| and the second term. This
gives an additional sign $(-1)^{1+\vert i\vert\cdot\vert j\vert+
\vert i\vert\cdot\vert k\vert+\vert j\vert\cdot\vert k\vert}$, i.e.,
if $j>0$ an additional minus has to be added.

@u
lisp procedure special_Jacobi_identity(bracketname,i,j,k);
mk!*sq subs2 negsq 
       addsq(sub_identity(bracketname,i,j,k),@|
             addsq(multsq((if j>0 then -1 @+else 1) . 1,
                          sub_identity(bracketname,j,i,k)),@|
                   sub_identity(bracketname,k,i,j)))$

@*1 Updating the vector structure. From the last sections it may have
become clear that until now it is impossible to update (i.e., store
the simplified values of) the entries of the vector structure without
deleting all additional information, since the set-element-function of
a liebracket initializes the additional information to |nil|.  As a
consequence of this, updating the vector structure implies
recomputation of all Jacobi identities. The procedure
|update_vector_structure_of| does a better job.

@u
lisp operator update_vector_structure_of;
lisp procedure update_vector_structure_of bracketname;
begin scalar vector_i,entry_i_j,
     commutator,form,kord!*,generatorname,properties_for_direct_access;
  @<Initialize prop...@>;
  generatorname:=get(bracketname,'generatorname);
  for i:=-n_used:m_used do begin
    vector_i:=getv(vector_structure,n+i);
    for j:=i:m_used do begin
      entry_i_j:=getv(vector_i,m-j);
      @<If necessary update |entry_i_j|@>;
    end;
  end;
end$

@ Updating an entry is necessary if it has a value, if it is not processed
or if it is processed but not special. In the last case we must take
care of the proper reordering.

@<If necessary update |entry_i_j|@>=
if entry_i_j and commutator_part_of entry_i_j then
   if not_processed entry_i_j then@|
      putv(vector_i,m-j,nil . k_info_of(entry_i_j) . 
                        aeval commutator_part_of entry_i_j)
   else if processed_but_not_special(entry_i_j) then begin
     commutator:=simp!* commutator_part_of entry_i_j;@/
     form:=numr commutator;
     convert_form_into_reordered_commutator;
     putv(vector_i,m-j,informative_part_of(entry_i_j) .
                       k_info_of(entry_i_j) . commutator);
   end @;

@ As promised in the section where we implemented the simplification
procedure of a liebracket, we will now explain how a (known)
commutator of two generators has to be simplified exactly. Namely, if
the value of a commutator is a sum of generators, the internal
ordering of the standard quotient in the vector structure representing
the commutator may be different from the default kernel ordering used
in REDUCE, because of the reordering we performed intended for the
efficient computation of Jacobi identities. Since differences in
ordering may lead to unexpected results (e.g. zero expressions which
are not represented by 0), we must see to it that we restore the right
ordering of the standard quotient before returning any commutator.

It is easily checked that reordering is necessary if and only if the
condition |processed_but_not_special| is true. The ordinary ordering can
be restored by applying |resimp| on the standard quotient part of the
commutator. In all other cases if is sufficient just to apply |simp|
to the commutator. The difference between both methods is the
following: using the second method the standard quotient will be
returned unchanged if the |cadr| of the !*SQ prefix form is |t| and
simplified if |nil|. The first method, however, will always simplify
and hence reorder the standard quotient before returning it.

@<Get commutator |bracketname(arg1,arg2)| as...@>=@/
  commutator:=get_vector_structure(bracketname,arg1,arg2);@/
  commutator:=
    if commutator and commutator_part_of commutator then
       if processed_but_not_special(commutator) then 
         if commutator_part_of commutator=0 then nil . 1
           else resimp get_sq_of commutator_part_of commutator
       else simp commutator_part_of commutator
    else mksq(list(bracketname,arg1,arg2),1) @;


@*= Analysis of relations in Lie superalgebras. If we have a relation
in a Lie superalgebra we have a few possibilities to solve it:\medskip
\item{1.} The relation contains a commutator, for which we can solve
the relation.  
\item{2.} The relation contains only generators, we have found a
linear dependency which we can solve.
\item{3.} The defining relations of the Lie superalgebra contained
some parameters, which also occur in the relation to solve. In this
case we can proceed as in case 1.\ and 2., but more carefully.  For
instance, suppose that we have found the relation
$a(1)*\lie(1,2)+a(2)*x(1)+x(2)=0$. Then it is dangerous simply to
solve for $\lie(1,2)$ because $a(1)$ eventually may become 0, in which
case the relation becomes a linear dependency between $x(1)$ and
$x(2)$.  Also a relation like $(a(1)-1)*x(1)+a(2)*x(2)=0$ can be
solved in two ways: we can put $a(1)=1$ and $a(2)=0$ or solve the
linear dependency in case $a(1)\neq 1$ or $a(2)\neq 0$.
\enditem 
To be able to recognize these parameters we will add to each
liebracket the property |parameters|, which is an operator, elements of
which may occur as parameters of the Lie superalgebra.

@ To keep the computations as compact as possible we will suppose that
any relation $R$ to be solved is a sum of generators and commutators
of two generators. Taking into account the points raised above we can
deduce the following strategy for finding a solution of a relation:
\medskip
\item{1.} If the relation contains at least one commutator whose
coefficient does not depend on a parameter, choose one and solve for
it.
\item{2.} If the relation contains commutators, but all possessing
coefficients depending on parameters, do not solve the relation.
\item{3.} If the relation does not contain commutators, but at least
one generator whose coefficient does not depend on a parameter, choose
one and solve for it.
\item{4.} If the relation does not contain commutators and all
generators have coefficients depending on parameters, try solve the
relation by solving the set of coefficients regarded as a linear set
of equations in an appropriate set of parameters.
\enditem
These tasks can most conveniently be performed by using the procedures
|operator_coeff|, for finding all generators with their corresponding
coefficients, and |solvable_kernels| from the TOOLS package.
The procedure |operator_coeff| has already been used and described
before. 

The call |solvable_kernels(exprn,k_oplist,c_oplist)| will
return an algebraic list of kernels |x| from operators occuring on
|k_oplist|, such that |x| occurs linearly in |exprn| and the
coefficient of |x| does not depend on any operator occuring on
|c_oplist|. From this it is clear that |solvable_kernels| can
be fruitfully used in step 1, 2 and 4.

The process described above will be performed by the procedure
|relation_analysis|. It returns either the kernel for which the
relation is solved or |'unsolvable| or |'nested_commutator| if the
relation for whatever reason is not solvable or contains nested
commutators.

@d zero_list= '(list 0)@; %List returned by |operator_coeff| applied
to 0%

@u lisp operator relation_analysis;
lisp procedure relation_analysis(relation,bracketname);
begin scalar generatorname,parameters,kernel_list,solvable_kernels,
             test,kernel,optimal_kernel,coefficient,clear_list;
  check_if_bracketname_is_a_liebracket_in("RELATION_ANALYSIS:");
  generatorname:=get(bracketname,'generatorname);
  parameters:=get(bracketname,'parameters);@/
  kernel_list:=operator_coeff(relation,generatorname);
  return
    if kernel_list=zero_list then 0
    else if independent_part_of kernel_list neq 0 then
      @<Solve |relation| for a commutator@>
    else @<Solve |relation| for a generator or parameters@>;
end$

@*1 Solving relations for a commutator. To solve |relation| for a
commutator we must first find out if there are commutators whose
coefficients do not contain parameters. This is performed by calling
|solvable_kernels|. If there are any we have to choose one and solve
for it.

@<Solve |relation| for a com...@>=
begin@/
solvable_kernels:=skip_list solvable_kernels(independent_part_of
    kernel_list,bracketname,parameters);
return
if null solvable_kernels then 'unsolvable
else begin
  @<Find the optimal commutator |optimal_kernel| for which to solve@>;
  return
    if optimal_kernel then@+
       <<linear_solve_and_assign(relation,optimal_kernel);optimal_kernel>>
    else 'nested_commutator;
end;
end
   
@ The main problem in solving a commutator from a relation, is
choosing the most appropriate one to solve. We adopt the idea here
that the grading of a liebracket will possess all necessary
information. For instance, if one of the components of the grading is
the length of the words in the Lie algebra, it is natural to solve for
the longest word. In this view, if a Lie algebra only possesses a zero
grading it doesn't matter for which commutator to solve. 

If a liebracket possesses a multigrading we will assume that the first
component is the most important one. This means that we will first
compare the first components and will only use the further components
if these are equal.

The basic procedure needed for this purpose is |first_degree_higher|
which returns |t| if the first degree is higher than the second one.

@u 
lisp procedure first_degree_higher(degree_1,degree_2);
if null degree_1 then nil
else if car degree_1>car degree_2 then t
else first_degree_higher(cdr degree_1,cdr degree_2)$

@ In case two commutators have the same degree the above procedure
will not give a unique choice independent of the ordering currently
used in REDUCE. However, in order to guarantee an unique choice, we
shall add the indices of the commutator to the degree.

@u 
lisp procedure extended_commutator_degree(commutator,bracketname);
nconc(add_degrees(get_permuted_degree(bracketname,i),
                  get_permuted_degree(bracketname,j)),@|
      list(i,j)) @/
where i=first_argument_of commutator, j=second_argument_of commutator$


@ In case we have to compare two generators we assume the these will
both be odd or even. Since in case of solving it is most natural to
solve for the generator with the highest number we shall add the
absolute value of the generator number to the degree list.

@u
lisp procedure extended_generator_degree(generator,bracketname);
append(get_permuted_degree(bracketname,i),list abs(i)) @/
where i=first_argument_of generator$

@ Getting the highest of two degrees is fairly simple now. We should
only be aware that in the application below the second degree may not
be a list (if there is no second element for which we have to compare
the degrees). In this case we should simply return the first degree.

@u 
lisp procedure highest_degree(degree_1,degree_2);
if atom degree_2 then degree_1
else if first_degree_higher(degree_1,degree_2) then degree_1 
else degree_2$

@ In the code below the variable |optimal_kernel| will be a dotted
pair containing the present highest degree and the present optimal
kernel, until the last line.

We will not solve the relation if it contains a nested commutator. In
this case we set |optimal_kernel| to |nil . nil|.

@<Find the optimal commutator ...@>=@/
  optimal_kernel:= 0 . nil;
  while solvable_kernels and car optimal_kernel do begin
    kernel:=first_element_of solvable_kernels;
    if not fixp first_argument_of kernel or  
       not fixp second_argument_of kernel then optimal_kernel:=nil . nil
    else 
      if not ((test:=highest_degree(extended_commutator_degree(kernel,bracketname),
                                    car optimal_kernel)) eq car optimal_kernel) then 
           optimal_kernel:=test . kernel;
    solvable_kernels:=rest_of solvable_kernels;
  end;@/
  optimal_kernel:=cdr optimal_kernel @;

@*1 Solving relations for a generator or parameters. If |relation|
does not contain commutators we have to find out if there are
generators without parameter coefficients. If so we have a linear
dependency to be solved w.r.t. generator which is optimal in some
sense, otherwise we may try to solve the relation by appropriately
solving parameters.

@<Solve |relation| for a gen...@>=
begin@/
solvable_kernels:=skip_list
     solvable_kernels(relation,generatorname,parameters);
return
if null solvable_kernels then
  @<Solve |relation| by appropiately solving parameters@>
else
  begin
    @<Find the optimal generator |optimal_kernel| for which to solve@>;
    return
      if optimal_kernel then@+
         <<linear_solve_and_assign(relation,optimal_kernel);optimal_kernel>>
      else 'invalid_generator;
  end;
end @;

@ 
@<Find the optimal gene...@>=@/
  optimal_kernel:= 0 . nil;
  while solvable_kernels and car optimal_kernel do begin
    kernel:=first_element_of solvable_kernels;
    if not fixp first_argument_of kernel then
      optimal_kernel:=nil . nil
    else
      if not ((test:=highest_degree(extended_generator_degree(kernel,bracketname),
                                    car optimal_kernel)) eq car optimal_kernel) then 
           optimal_kernel:=test . kernel; @/
    solvable_kernels:=rest_of solvable_kernels;
  end;@/
  optimal_kernel:=cdr optimal_kernel @;

@ Solving parameters boils down to the following actions to be taken
for each |coefficient| of a generator occuring on |kernel_list|, the
list of generators and their coefficients:\medskip
\item{1.} If |coefficient| contains some solvable parameters (i.e.,
occuring linearly in it), choose the first one, solve |coefficient|
w.r.t.  this parameter and put it on |clear_list|. Searching for
solvable parameters can be performed by applying |solvable_kernels|
with appropriate arguments.
\item{2.} If a |coefficient| does not contain a solvable parameter, we
have to clear all the parameters occuring on |clear_list| (i.e., which
had been previously solved) and set |clear_list| equal to |nil|,
indicating that |relation| is not solvable.

@<If possible find and solve the list of parameters |clear_list|@>=
  repeat begin
    coefficient:=coefficient_of first_element_of kernel_list;
    solvable_kernels:=skip_list
       solvable_kernels(coefficient,parameters,parameters);
    if null solvable_kernels then
    begin
      apply1('clear,clear_list);
      clear_list:=nil
    end
    else begin
      kernel:=first_element_of solvable_kernels;
      linear_solve_and_assign(coefficient,kernel);
      clear_list:=kernel . clear_list;
      kernel_list:=rest_of kernel_list;
    end end
  until null kernel_list or null clear_list @;

@ In order to give the user full control over the process of solving
parameters we introduce a switch |solve_parameters|, indicating if
solving of parameters is allowed.

@<Lisp ini...@>=@/
new_switch(solve_parameters,nil)$
 
@ If it is allowed to solve parameters we can do so, otherwise
|relation| is not solvable. The reader should verify that we are sure
that |relation| contains generators at this stage.

@<Solve |relation| by appr...@>=
if !*solve_parameters then
begin
  kernel_list:=kernel_coeff_list_of kernel_list;
  @<If possible find and solve the list of parameters |clear_list|@>;
  return if clear_list then 'list . clear_list else 'unsolvable;
end
else 'unsolvable @;

@*= Solving Jacobi identities. Now we have written all kinds of tools
for solving Jacobi identities and a procedure for analysing Lie
algebraic relations, we are able to implement the top level procedure
|solve_Jacobi_identities_of| for actually solving Jacobi identities,
and some other auxiliary procedures.

Using the procedures |find_unprocessed_commutators_of|,
|find_Jacobi_identities_of| and |relation_analysis|, solving Jacobi
identities is in fact really simple: while there are processable
commutators, find the Jacobi identities belonging to them, try to solve
and if necessary print these identities. Identities which are not
solvable automatically should be stored on the property list of the
liebracket for reconsideration by the user.

Printing of Jacobi identities is controled by a switch
|print_identities|, which is \&{off} by default. If identities are
to be printed only the identities not equal to 0 are printed.

@<Lisp ini...@>=@/
new_switch(print_identities,nil)$

@ The procedure |solve_Jacobi_identities_of| can be written down
without much explanation. We declare it a lisp operator.

Notice that the property |commutator_list| of a liebracket is cleared
by a call of |find_Jacobi_identities_of|. The list of unsolved
identities is stored as the property |unsolved_identities|. After
storing the unsolved identities, the property |identity_list| can be
cleared, since all identities on it have been checked.

We want all message in this procedure to appear with the switch |nat|
turned on. Therefore we will force this and restore the old
environment afterwards.

@u
lisp operator solve_Jacobi_identities_of;
lisp procedure solve_Jacobi_identities_of bracketname;
begin scalar generatorname,stage,identity_list,i,j,identity,
             solution,nr_computed,nr_solved,environment,origin;
  check_if_bracketname_is_a_liebracket_in("SOLVE_JACOBI_IDENTITIES_OF:");@/
  generatorname:=get(bracketname,'generatorname);
  environment:=!*nat; !*nat:=t; stage:=0;
  @<Prepare next stage@>;
  while identity_list do
  @<Perform current stage@>;@/
  print_statistics_of bracketname;@/
  !*nat:=environment;
end$

@ Preparing the next stage of solving Jacobi identities consists of
finding the unprocessed commutators and after that finding all Jacobi
identities following from them.

@<Prepare next stage@>=
@<Print starting message for next stage@>;
find_unprocessed_commutators_of bracketname;@/
@<Report the search for identities@>;
identity_list:=find_Jacobi_identities_of bracketname @;

@ @<Perform current stage@>=
begin
  nr_computed:=0; nr_solved:=0;@/
  @<Report the solving of identities@>;
  @<Compute, solve and print all Jacobi identities in |identity_list|@>;
  put(bracketname,'identity_list,nil);@/
  @<Print the number of identities solved@>;
  @<Prepare next stage@>;
end @;

@ Recall that |identity_list| is a double association list. Hence we
must unfold it before usage. Recursive solving of dependencies may
occur when we are solve a relation. Therefore we have to in- and
decrease |indentation_level!*| beforehand and afterwards.

@<Compute, solve and print all Jacobi identities in |identity_list|@>=
for each id_list_i in identity_list do begin
  i:=car id_list_i; id_list_i:=cdr id_list_i;
  for each id_list_i_j in id_list_i do begin
    j:=car id_list_i_j; id_list_i_j:=cdr id_list_i_j;
    for each k in id_list_i_j do begin
      incr(nr_computed);@/
      identity:=special_Jacobi_identity(bracketname,i,j,k);
      origin:=list('list,i,j,k);@/
      @<If necessary print |identity|@>;
      solution:=relation_analysis(identity,bracketname);
      @<Take the actions appropriate for |solution|@>;
      @<If necessary print |solution|@>;
    end;
  end;
end @;

@ Due the recursive nature of solving linear dependencies we
have to use some indentation to indicate the level of
solving dependencies. Therefore we have to precede |prin2!*| by an
indentation according to a global variable |indentation_level!*|,
which represents the level of indentation necessary, in all messages
at the beginning of a line that are also usable when solving
dependencies. Messages used only when solving Jacobi identities will
only be performed at top level, so no indentation is needed there.

The problem with the |indentation_level!*| is that we must be sure
that it must be zero at start of any command, i.e., at algebraic
level. But how can we be sure this, for something may go wrong at any
level, causing a return to algebraic level without properly decreasing
|indentation_level!*|. Fortunately, there is the |initl| mechanism of
REDUCE, causing global quantities on the (global) list |initl!*| to be
initialized to an initial value at algebraic level. Therefore we will
make |indentation_level!*| a global variable and put it on |initl!*|
with initial value 0.

@d indent_according_to_level=@/
  for i:=1:indentation_level!* do prin2!* "| " @;
@d indented_print(string)=@/
  <<indent_according_to_level; prin2!* string>>@;
@d indented_empty_line=@/
  if indentation_level!*=0 then terpri!* t else
 @+ <<terpri!* nil; indent_according_to_level; terpri!* nil>> @;

@<Lisp ini...@>=@/
global '(indentation_level!*)$@/
initl!*:='indentation_level!* . initl!*$@/
put('indentation_level!*,'initl,0)$

@ The message are rather straightforward and will not be explained in
all detail. 

@<Print starting message for next stage@>=@/
prin2!* "Starting stage "; prin2!* incr(stage); prin2!* ":"; terpri!* nil;
prin2!* "Reordering the commutators..."; terpri!* nil @;

@ @<Report the search for identities@>=@/
prin2!* "Searching for identities..."; terpri!* nil @;

@ @<Report the solving of identities@>=@/
prin2!* "Solving the identities..."; terpri!* nil;
if !*print_identities then @+
<<prin2!* "==========================";
  terpri!* nil>> @;

@ @<If necessary print |identity|@>=
if !*print_identities and identity neq 0 then
begin indent_according_to_level; maprin origin; terpri!* nil; @/
  indent_according_to_level; maprin identity; terpri!* nil;
end @;

@ @<If necessary print |solution|@>=
if !*print_identities and solution neq 0 then
begin 
  if member(solution,'(unsolvable nested_commutator invalid_generator)) 
    then indented_print("Not solved.")
  else @+ <<if car solution=generatorname or car solution='list then
           indented_print("*** Solved for: ")
         else indented_print("Solved for: "); 
         maprin solution>>;@/
  indented_empty_line;
end @;

@ @<Print the number of identities solved@>=@/
indented_print(nr_solved); prin2!* " identities solved of "; 
prin2!* nr_computed; indented_empty_line @;

@ We recall that the procedure |relation_analysis| can only return 0,
|unsolvable|, |nested_commutator|, |invalid_generator| or a list, the
|car| of which is |bracketname|, |generatorname| or |list| (in which
case some parameters of the Lie superalgebra were solved).  The second
third and fourth case give rise to an unsolved identity, which has to
be placed on the list of unsolved identities. The last two cases are
important enough to be mentioned even if |print_identities| is turned
\&{off}.

In the case that we have an unsolved identity we store it together
with its origin in an algebraic list on the |unsolved_identities| list
of the liebracket.

@d update_unsolved_identities_list=@/
put(bracketname,'unsolved_identities,@|
    list('list,origin,identity) . get(bracketname,'unsolved_identities)) @;

@<Take the actions appropriate for |solution|@>=
if solution neq 0 then 
if member(solution,'(unsolvable nested_commutator invalid_generator)) then 
  update_unsolved_identities_list
else if car solution=generatorname or car solution='list then
begin incr(nr_solved);
  if not !*print_identities then 
    <<indented_print("*** Identity "); maprin origin;
      prin2!* " solved for: "; maprin solution; terpri!* nil>>
end
else incr(nr_solved) @;

@*1 Printing unsolved identities and statistics. Users should be able
to take a look at the list of unsolved identities. For this purpose we
will write a procedure |unsolved_identities_of|, which rebuilds the
list of unsolved identities by deleting all entries that have become 0
during the process and returns it as an algebraic list for further
examination by the user. Recall that the identities on the unsolved
identities list are algebraic lists consisting of the origin of the
identity and the identity itself.

The procedure has to be available in algebraic mode.

@u
lisp operator unsolved_identities_of;
lisp procedure unsolved_identities_of bracketname;
begin scalar unsolved_identities,id;@/
  check_if_bracketname_is_a_liebracket_in("UNSOLVED_IDENTITIES_OF:");
  unsolved_identities:=get(bracketname,'unsolved_identities);@/
  unsolved_identities:=@+
    for each identity in unsolved_identities join 
      if (id:=aeval second_argument_of identity) neq 0 then @|
       list list('list,first_argument_of identity,id);
  put(bracketname,'unsolved_identities,unsolved_identities);
  return 'list . unsolved_identities;
end$

@ It may be convenient to get track of some statistics concerning a
Lie superalgebra, for instance if one wants to know if a Lie
superalgebra is solved completely. The procedure |print_statistics_of|
prints the number of used generators, the number of commutators,
generators and parameters solved and the number of unsolved
identities; Of course we don't want to count the {\it special}
commutators in the number of solved commutators. We can check this by
looking at the informative part of an entry of the vectorstructure.

@d not_special(entry)=@/informative_part_of entry neq '(special)@;

@u
lisp operator print_statistics_of;
lisp procedure print_statistics_of bracketname;
begin scalar properties_for_direct_access,vector_i,entry_i_j,nr_solved,total;
  check_if_bracketname_is_a_liebracket_in("PRINTS_STATISTICS_OF:");
  @<Initialize prop...@>;
  nr_solved:=0;
  for i:=-n_used:m_used do begin
    vector_i:=getv(vector_structure,n+i);
    for j:=i:m_used do
      if (entry_i_j:=getv(vector_i,m-j)) and
         commutator_part_of(entry_i_j) and not_special(entry_i_j) 
         then incr(nr_solved);
  end;
  total:=((m_used+n_used)^2-m_used+n_used)/2;
  if total=0 then rederr("PRINT_STATISTICS_OF: first define used area");
  terpri!* t;
  prin2!* "Statistics for liebracket "; maprin bracketname; terpri!* nil;@/
  prin2!* m_used; prin2!* " even and "; prin2!* n_used;
  prin2!* " odd generators used"; terpri!* nil;
  prin2!* nr_solved; prin2!* " commutators solved of ";@/ prin2!* total; 
  prin2!* " ("; prin2!* ((nr_solved*100)/total); prin2!* " %)"; terpri!* nil;@/
  prin2!* length get(get(bracketname,'generatorname),'kvalue);@/
  prin2!* " linear dependencies found"; terpri!* nil;@/
  total:=for each parameter in get(bracketname,'parameters) sum 
     length get(parameter,'kvalue);@/
  prin2!* total; prin2!* " parameters solved"; terpri!* nil;@/
  prin2!* length get(bracketname,'unsolved_identities);
  prin2!* " unsolved identities"; terpri!* t;
end$


@*= Access to generators. In the introduction of the previous chapter
we concluded that it was most convenient to control the access to a
generator of a Lie (super)algebra by an set-element-function and a
clear function. For a detailed description how these procedures should
act we refer to the previous chapter.  In the following sections we will
take care of the set-element-function |set_generator| and the clear
function |clear_generator| belonging to the rtype |algebra_generator|.
Moreover, to let the clear function work properly, |algebra_generator|
must have a rtypefn |generator_rtypefn|.  How a set-element-function,
a clear function and an rtype function work and cooperate exactly, we
have already explained for a liebracket.

The names of all three procedures must be put on the property list of
|algebra_generator|.

@<Lisp ini...@>=@/
put('algebra_generator,'setelemfn,'set_generator)$@/
put('algebra_generator,'clearfn,'clear_generator)$@/
put('algebra_generator,'rtypefn,'generator_rtypefn)$

@ The same remarks that were made for the rtypefn |liebracket_rtypefn|
apply to the rtypefn for a algebra generator, |generator_rtypefn|,
since we don not want particular generators to be recognized as a
|algebra_generator|.

@u
lisp procedure generator_rtypefn u;
nil$

@ The set-element-function |set_generator| of an algebra generator
should do three things: check if |val| is a valid generator and
|value| a sum of generators, do the assignment |val:=value| and adjust
all commutators containing |val|. For the last action we need to know
the name of the liebracket associated to the algebra generator
involved. We expect this name to be stored on the property list of
this generator as the property |bracketname|.

Since we use the standard REDUCE procedure |setk1| to do the
assignment on the kvalue list of the generator we must call |rmsubs()|
ourselves, in order to assure proper reevaluation of algebraic
expressions.

@u lisp procedure set_generator(val,value); if length val neq 2 then
  rederr("SET_GENERATOR: generator must have one integer argument")
else begin scalar generatorname,bracketname,i,valuelist,
                  identity,solution,
                  nr_computed,nr_solved,environment,origin;
  generatorname:=operator_name_of val;
  bracketname:=get(generatorname,'bracketname);
  i:=reval first_argument_of val;
  value:=aeval value;@/
  @<Check that |val| and |value| are valid for assignment@>;
  if used_operator_element(val) then rmsubs();@/
  setk1(val,value,t); %Do the assignment on the kvalue list of |generatorname|%
  @<Adjust commutators |bracketname(i,j)| for $j=-n,\dots,1$ and $j=1,\dots,m$@>;
end$

@ We must check that |val| is a valid generator, i.e., $i$ must be
integer and not out of range. For this purpose we will use the macro
|wrong_atomic_argument| we wrote before. Moreover, we must check
that |value| is a sum of valid generators. This can be done most
conveniently by using |operator_coeff| and |wrong_atomic_argument|. We will
use the variable |valuelist| (local within |set_generator|) to
store the list produced by |operator_coeff|.

@<Check that |val| and |value| are valid for assignment@>=@/
if not atom i or wrong_atomic_argument(i) then @|
  stop_with_error("SET_GENERATOR:",val,"invalid or out of range",nil);
valuelist:=operator_coeff(value,generatorname);
if independent_part_of valuelist neq 0 then 
  stop_with_error("SET_GENERATOR:",@|independent_part_of valuelist,
                  "not a sum of generators",nil);
for each term in kernel_coeff_list_of valuelist do
  if length(term:=kernel_of term) neq 2 or 
     not atom first_argument_of term or @|
     wrong_atomic_argument(first_argument_of term) then @|
  stop_with_error("SET_GENERATOR:",term,"invalid or out of range",nil) @;

@*1 Adjusting commutators. After the assignment we have to adjust
the values of $\\{bracketname}(i,j)$ for $j=-n,\dots,1$ and
$j=1,\dots,m$ according to the assignment made. Hence we have to solve
the identities $\\{bracketname}(i,j)=\\{bracketname}(\\{value},j)$.
This can be done by using the procedure |relation_analysis|.

Recall that we stored the even and odd dimensions $m$ and $n$ on the
property list of a liebracket as the properties |even_dimension| and
|odd_dimension|. 

Note that there are some different cases to distinguish: $\lie(i,i)$
may be set for $i<0$, but not for $i>0$. $\lie(i,0)$ may also not be
set. These cases are already incorporated in the |repeat| statement.
Moreover, note that |value| has been |aeval|'ed, hence is in !*SQ
prefixform.

To stay in line with the procedure |solve_Jacobi_identities_of| we
will take the same actions and print the same kind of information as
we did during the solving of Jacobi identities. Recall that all
message that may occur recursively at deeper levels of solving linear
dependencies are indented according to the global variable
|identation_level!*|. Hence this level must be increased before
we start adjusting commutators.

@<Adjust commuta...@>=@/
environment:=!*nat; !*nat:=t; %Force the switch |nat| to be on%
@<Write a message that adjustment of commutators has begun@>;
incr(indentation_level!*);
nr_computed:=0;nr_solved:=0;
for j:=-get(bracketname,'odd_dimension):get(bracketname,'even_dimension) do
  if j neq 0 and (i neq j or i<0) then 
    begin
    incr(nr_computed);@/
    identity:=@<|bracketname(i,j)-bracketname(value,j)|@>;
    origin:=list('list,i,j);@/
    @<If necessary print |ide...@>;
    solution:=relation_analysis(identity,bracketname);
    @<Take the actions appr...@>;
    @<If necessary print |sol...@>;
    end;
@<Print the number of ident...@>;
decr(indentation_level!*);@/
!*nat:=environment %Restore the original setting of |nat|% @;

@ @<Write a message that ...@>=@/
indented_print("Adjusting the commutators of "); @/ maprin val; prin2!* "..."; 
terpri!* nil;
if !*print_identities then @+
<<indented_print("| ========================");
terpri!* nil;>> @;

@ To get the difference of |bracketname(i,j)| and
|bracketname(value,j)| we use |simp_liebracket| to get both
commutators as standard quotients, |subtrsq| to subtract them and
|mk!*sq| to convert a standard quotient into a !*SQ prefixform.
Because we use the answer to solve an algebra relation we have to
make sure that all substitutions are performed, hence we must apply
|subs2| to the standard quotient.

@<|bracketname(i,j)-bracketname(value,j)|@>=@/
mk!*sq subs2 subtrsq(simp_liebracket(list(bracketname,i,j)),@|
                     simp_liebracket(list(bracketname,value,j))) @;

@*1 Clearing generators. The clear function of an algebra generator is
much easier than its set-element-function, because it is nearly
impossible to backtrace all commutators which have been set by the
assignment to this generator.  To understand this, one should be aware
of the fact that the process of adjusting commutators to linear
dependencies of some generators may be recursive, namely if one the
relations |bracketname(i,j)-bracketname(i,value)| itself is a linear
dependency of some generators. Moreover, the relations caused by this
linear dependency may have introduced new solvable Jacobi identities,
which may already have been solved.  Hence we will only give a warning
that things may get messed up.

@u
lisp procedure clear_generator val;
if atom val then rederr("CLEAR_GENERATOR: clear associated liebracket instead")
else if length val neq 2 then
  rederr("CLEAR_GENERATOR: generator must have one integer argument")
else begin scalar generatorname,kvalue,h;
  generatorname:=operator_name_of val;
  val:=list(generatorname,reval first_argument_of val);
  kvalue:=get(generatorname,'kvalue);
  if (h:=assoc(val,kvalue)) then
    begin
      put(generatorname,'kvalue,delete(h,kvalue));
      message("CLEAR_GENERATOR: clearing",val,"may lead to errors",nil);
    end
  else message("CLEAR_GENERATOR:",val,"not found",nil);
end$

@*= Multigradings, definitions and introduction of new generators. In the
first section we urged the need to store and retrieve integer valued
multigrades of all generators of a Lie algebra. In this section we
will introduce an environment for these multigrades, implement
procedures to find generators and unknown commutators of a certain
degree and a procedure to determine the degree of an given expression.

Moreover, we will write a procedure to introduce a new generator for a
given (unknown) commutator and at the same time determine the degree
of it, i.e., the degree of the commutator.  Besides a grading it will
also be convenient to know the definition and the ``history'' of a
newly introduced generator, i.e., what commutator was used at highest
level to define this generator and which commutators were
recursively used to construct it . This kind of information will
also be stored.

For each generator we will store this information in a vector of
dimension $m+n$ where $m$ and $n$ are the even and odd dimension of
the Lie superalgebra, respectively. Each entry of this vector will be
a dotted pair, consisting of a degree part, a definition part and a
history part. At initialization the entry for a generator |y(i)|
($-n\leq i\leq m$) will be initialized to |'(0) . i . i|, i.e., we
initialize the degree of all generators to a multi degree of length 1
with value 0.

The vector with degree and history information will be stored on the
property list of the liebracket as the property |info_list|. The
information of generator |y(i)| will be contained in this vector at
index $n+i$. Access to this vector can be obtained by using the macros
|get_info| and |put_info|.  The length of the multi degrees
is stored as the property |degree_length|. As stated above it is
initialized to 1.

@d degree_part=car
@d definition_part=cadr
@d history_part=cddr
@d get_degree=degree_part get_info
@d get_definition=definition_part get_info
@d get_history=history_part get_info
@d get_info(bracketname,i)=@/
getv(get(bracketname,'info_list),get(bracketname,'odd_dimension)+i) @;
@d put_info(bracketname,i,value)=@/
putv(get(bracketname,'info_list),get(bracketname,'odd_dimension)+i,value)@;

@ The most important action for manipulating degrees is the
possibility to add them. This is done by the recursive procedure
|add_degrees|, which expects its arguments to be of identical length
and, moreover, expects its arguments to be integer lists.

@u lisp procedure add_degrees(degree1,degree2);
if degree1 then (car degree1 + car degree2) . add_degrees(cdr
degree1,cdr degree2)$

@ From using this package it became apparent that it may be quite
convenient to look at gradings in another order, since during the
process of computing Lie super algebras, different components of a
multigrading may turn out to play an important role. As it is quite
bothersome to change the order of gradings by hand, we will offer a mechanism
here that selects a subset of an actual multigrading in a prescribed
order.

The procedure |degree_component_sequence| will assign a prescibed
sequence of the multigrading to a liebracket by saving this sequence
as the property |degree_sequence|. A degree sequence may be given as
an integer or an algebraic or lisp list of integers. This can be
transformed into a lisp list using the macro |make_oplist| to be
explained below. 

@u lisp operator degree_component_sequence;
lisp procedure degree_component_sequence(bracketname,degree_sequence);
begin scalar degree_length;
  check_if_bracketname_is_a_liebracket_in("DEGREE_COMPONENT_SEQUENCE:");
  degree_sequence:=make_oplist(degree_sequence);
  degree_length:=get(bracketname,'degree_length);
  degree_sequence:=
    for each component in degree_sequence collect
      if fixp component and component >0 and component leq degree_length then
         component
      else 
   stop_with_error("DEGREE_COMPONENT_SEQUENCE: multigrading has no component",
                    component,nil,nil);
  put(bracketname,'degree_sequence,degree_sequence);
end$

@ Given a |degree| the procedure |permuted_degree| returns |degree|
permuted w.r.t.\ a  prescribed |sequence|. If there is no |sequence|
degree should be returned without change.

@d get_permuted_degree(bracketname,i)=
  permuted_degree(degree_part get_info(bracketname,i),
                  get(bracketname,'degree_sequence))

@u lisp procedure permuted_degree(degree,sequence);
if null sequence then degree else permute_degree(degree,sequence)$

lisp procedure permute_degree(degree,sequence);
if sequence then 
   nth(degree,car sequence) . permute_degree(degree,cdr sequence)$

@ If we want to determine the degree of a general Lie algebra element
|element| belonging to a liebracket |bracketname|, we have to
distinguish three cases:\medskip

\item{1.} if |element| is the index number of a generator, we can simply
get the information about |element| and return the degree part of it.

\item{2.} if |element| is a commutator, we can add the degrees of both
components. Because we will use algebraic list to return the
definition a some generator, as explained in one of the next sections,
we will also consider algebraic lists as commutators, in this case.

\item{3.} if |element| is a generator, we can return the degree of the
index number of |element|.  
\enditem 
The procedure |degree_of1| takes care of these cases.  Notice that we
expect commutators to have only two arguments. We can achieve this by
simplifying |element| before applying |degree_of1|.

@u lisp procedure degree_of1(bracketname,element);
if atom element then 
  if wrong_atomic_argument(element) then@|
    stop_with_error("DEGREE_OF: cannot determine degree of",element,nil,nil)
  else get_permuted_degree(bracketname,element)
else 
if operator_name_of element=bracketname or operator_name_of element='list then
  add_degrees(degree_of1(bracketname,first_argument_of element),@|
              degree_of1(bracketname,second_argument_of element))
else if operator_name_of element=get(bracketname,'generatorname) then @|
  degree_of1(bracketname,first_argument_of element)
else stop_with_error("DEGREE_OF: cannot determine degree of",element,nil,nil)$

@ At algebraic level we will return the degree of some Lie algebra
element as an algebraic list. This is done by the procedure
|degree_of|. 

In order to avoid difficulties with linear dependencies of some
generators, we shall also allow linear combinations of Lie algebra
elements and suppose that the sum offered is homogeneous. In this case
we return the degree of the first Lie algebra element encountered.

Notice that |element| is evaluated specifically as requested in the
previous module.

@u lisp operator degree_of;
lisp procedure degree_of element;
begin scalar operatorname,bracketname,check_element;
  if (element:=reval element)=0 then @+return nil;
  if not atom element then 
  begin
    operatorname:=operator_name_of element;
    if get(operatorname,'rtype)='liebracket then bracketname:=operatorname
    else if get(operatorname,'rtype)='algebra_generator then @|
      bracketname:=get(operatorname,'bracketname)
  end;
  if null bracketname then @<Check for linear combinations of Lie algebra elements@>;
  if null bracketname then @|
    stop_with_error("DEGREE_OF: cannot determine degree of",element,nil,nil);
  return 'list . degree_of1(bracketname,element)
end$

@ If a linear combination is a sum we can check the first term. If it
is a quotient we have to examine the numerator. If it is a product we
have to examine the factors until we have encountered a Lie algebra
element.

@<Check for linear combinations of Lie algebra elements@>=
begin 
  check_element:=element;
  while not atom check_element and @|
        member(operator_name_of check_element,'(quotient plus minus difference)) do
     check_element:=first_argument_of check_element;
  if not atom check_element then@/
    (if operator_name_of check_element='times then 
      @<Check all factors for Lie algebra elements@>
    else 
      begin
        operatorname:=operator_name_of check_element;
        if get(operatorname,'rtype)='liebracket then bracketname:=operatorname
        else if get(operatorname,'rtype)='algebra_generator then @|
          bracketname:=get(operatorname,'bracketname);
        if bracketname then element:=check_element
      end)
end

@ @<Check all factors for Lie algebra elements@>=
    while null bracketname and (check_element:=rest_of check_element) do
      <<if not atom first_element_of check_element then
      begin
        operatorname:=operator_name_of first_element_of check_element;
        if get(operatorname,'rtype)='liebracket then bracketname:=operatorname
        else if get(operatorname,'rtype)='algebra_generator then @|
          bracketname:=get(operatorname,'bracketname)
      end;  
      if bracketname then element:=first_element_of check_element>>


@ The next step towards a useful application of gradings is the
availability of a procedure |define_degree| to assign a new value to the
degree of some generator (since a grading with all degrees equal to 0
isn't very useful).  We impose a few requirements on the degrees to be
assigned:\medskip 

\item{1.} A newly assigned degree should have the
proper length, i.e., should have length |degree_length|.  

\item{2.} All entries of a multi degree should be integer valued.

\item{3.} A degree can be entered as an atom, an algebraic list or a
lisp list. This is the same syntax for entering ``lists'' of some
objects which we used for lists of operatornames for multilinear
operatornames, as introduced in the TOOLS package.  Hence we copy the
definition |make_oplist| which transforms one the alternatives
mentioned above in an ordinary lisp list.

@d make_oplist(op_list)=@/if null op_list then op_list else if atom
op_list then list op_list else if
car op_list='list then cdr op_list else op_list @;

@<Check if |degree| is a valid degree@>=@/
if not integer_valued(degree:=make_oplist(degree)) or 
   length degree neq get(bracketname,'degree_length) then 
stop_with_error("DEGREE:",'list . degree,"invalid degree",nil) @;

@ Checking that a list consists of integers can be done with help of
the following recursive procedure.

@u
lisp procedure integer_valued degree;
if null degree then t
else if fixp car degree then integer_valued cdr degree$

@ Assigning a new degree to a generator is really simple now: check if
the generator is indeed a generator, check the degree for its validity
and update the info entry for the generator.

@u lisp operator define_degree;
lisp procedure define_degree(generator,degree);
begin scalar generatorname,bracketname,info;
  @<Check if |generator| is valid, if so find |bracketname|@>;
  @<Check if |degree| is a valid degree@>;
  info:=get_info(bracketname,generator);
  put_info(bracketname,generator,
           degree . definition_part info . history_part info);
end$

@ A generator is valid, if it is an operator element
whose operator is of rtype |algebra_generator| and, moreover, the
argument of which is not out of range. Before checking the argument we
must |reval| it because this is not necessarily done (for instance in
the procedures |definition_of| and |history_of|, which will be
explained in a few sections).

@<Check if |generator| is valid, if so find |bracketname|@>=
  if atom generator then 
    stop_with_error("DEGREE:",generator,"invalid generator",nil);
  generatorname:=operator_name_of generator;
  check_if_generatorname_is_a_generator_in("DEGREE:");
  bracketname:=get(generatorname,'bracketname);
  generator:=reval first_argument_of generator;
  if wrong_atomic_argument(generator) then @|
    stop_with_error("DEGREE: generator index",
                    generator,"out of range",nil) @;

@ Since all procedures concerning degrees check for the proper length
of the degrees, there should be a procedure |change_degree_length| to
change the length of all degrees. The main part of it consists of
adapting the length of all existing degrees. This is necessary because
|add_degrees| expects all degrees to be of the same length. If the new
length of is larger than the old one we must extend all degrees with
an appropriate number of zeros, otherwise we can take the sub degree of
appropriate length.

@u
lisp operator change_degree_length;
lisp procedure change_degree_length(bracketname,degree_length);
begin scalar m,n,old_length,shortage,extension,info,degree;
  check_if_bracketname_is_a_liebracket_in("CHANGE_DEGREE_LENGTH:");
  if not fixp degree_length or degree_length <= 0 then 
    rederr("CHANGE_DEGREE_LENGTH: degree length should be >= 0");@/
  m:=get(bracketname,'even_dimension);
  n:=get(bracketname,'odd_dimension);@/
  old_length:=get(bracketname,'degree_length);
  shortage:=degree_length-old_length;
  if shortage>0 then extension:=@+for i:=1:shortage collect 0;@/
  @<Adapt the |info_list|@>;
  put(bracketname,'degree_length,degree_length);
end$

@ @<Adapt the |info_list|@>=
  for i:=-n:m do
  begin info:=get_info(bracketname,i); @/
    degree:=if extension then append(degree_part info,extension)
               else sub_list(degree_part info,degree_length);
    put_info(bracketname,i,
             degree . definition_part info . history_part info)
  end @;

@ The sub list of a list |l|, consisting of the first $n$ elements,
can be collected using the recursive procedure |sub_list|.

@u 
lisp procedure sub_list(l,n);
if l and n>0 then car l . sub_list(cdr l,n-1)$

@ Finding the definition or the history of some generator is much
easier than the determination of the degree of some Lie algebra
element, and is taken care of by the procedure |definition_of| and
|history_of|, both to be available in algebraic mode.
There is, however, one tricky point which we should take care of in
both cases, namely if some generator is found linear independent, we
still want to be able to retrieve the definition/history of such a
generator. Therefore the arguments of |definition_of| and |history_of|
must not be evaluated. This can be achieved by giving |definition_of|
and |history_of| the property |psopfn|, i.e., the arguments of these
procedures are put on a list and the procedure which name is the value
of the property |psopfn| is applied to this list. For this we will use
the same convention as in the TOOLS package: the |psopfn| is indicated
by a additional 1, the real work, however, is done by a lisp procedure
with the same name and syntax as available in algebraic mode.

The definition of a generator is either an integer, corresponding to the
generator, or an algebraic list with two integer arguments,
corresponding to the commutator used to define the generator.  
We use algebraic lists, because it would be useless to return the
commutator self as the definition, since it will be reevaluated to the
generator immediately. Recall that for this reason we allowed
algebraic lists as a special kind of commutators in |degree_of1|.

The history of a generator is either an integer, corresponding to the
generator, or an algebraic list of arbitrary length, consisting of
possibly nested lists of integers, corresponding to the possibly
nested commutator used to define the generator, where all integers
recursively occuring in the history have integer histories themselves,
in other words the history corresponds to the way a generator was
introduced recursively.

@<Lisp ini...@>=@/
put('definition_of,'psopfn,'definition_of1)$@/
put('history_of,'psopfn,'history_of1)$


@ 
@u lisp procedure definition_of1 listed_generator;
definition_of first_element_of listed_generator$@#

lisp procedure definition_of generator;
begin scalar generatorname,bracketname;
  @<Check if |generator| is valid, if so find |bracketname|@>;
  return get_definition(bracketname,generator);
end$@#

lisp procedure history_of1 listed_generator;
history_of first_element_of listed_generator$@#

lisp procedure history_of generator;
begin scalar generatorname,bracketname;
  @<Check if |generator| is valid, if so find |bracketname|@>;
  return get_history(bracketname,generator);
end$

@*1 Finding commutators and generators of a given degree. The next
important issue is how to get all (independent) generators or unknown
commutators of a given degree. The first question that arises is how
to define a useful notion of objects ``of a given degree''. A rigid
point of view is to allow all objects whose degree is totally equal to
the given degree. A more general, and to our opinion very useful,
point of view is to allow all objects that have a degree the first
part of which matches the given degree, any other elements of it not
being relevant. This notion enables us to use subsets of a
multigrading for selecting Lie algebra objects.

The procedure |sub_degree| takes care of the strategy introduced
above, and returns |t| if |degree1| is a subset of |degree2|, |nil|
otherwise.

@u
lisp procedure sub_degree(degree1,degree2);
if null degree1 then t
else if null degree2 then nil
else if car degree1=car degree2 then 
   sub_degree(cdr degree1,cdr degree2)$

@ Finding all generators of a given degree, is very easy now: first
check if |degree| is a valid degree (if not searching is useless),
then collect all generators whose degree match |degree|.
The result is returned a an algebraic list.

Of course it is not useful to return generators that are linear
dependent of others, therefore we will also check on the kvalue list
of the generator if it has a value.

@u
lisp operator generators_of_degree;
lisp procedure generators_of_degree(bracketname,degree);
begin scalar even_used,odd_used,generatorname,kvalue;
  check_if_bracketname_is_a_liebracket_in("GENERATORS_OF_DEGREE:");@/
  if not integer_valued(degree:=make_oplist(degree)) then @|
     stop_with_error("DEGREE:",'list . degree,"invalid degree",nil);@/
  even_used:=get(bracketname,'even_used);
  odd_used:=get(bracketname,'odd_used);@/
  generatorname:=get(bracketname,'generatorname);
  kvalue:=get(generatorname,'kvalue);
  @<Return the list of generators with right degree@>;
end$

@ We use the |for| \dots |join| construct to get the list of generators
with right degree. In this way we can prevent generators with wrong
degree to cause empty entries in the result list. Since this construct
concatenates lists, we have to surround all entries by an additional
list.

Recall that we prevented the use of 0 as an index of a generator, so
at this place we have to make an exception for it.

@<Return the list of generators with right degree@>=
  return 'list . 
    for i:=-odd_used:even_used join
      if i neq 0 and null assoc(list(generatorname,i),kvalue) and @|
         sub_degree(degree,get_permuted_degree(bracketname,i))
      then
	list list(generatorname,i) @;

@ The procedure |commutators_of_degree| returns an algebraic list of
all unknown commutators of a given degree. It's action is similar to
that of |generators_of_degree|. For efficiency reasons we will access
both the |vector_structure| and the |info_list| directly, i.e.,
without using the macros |get_commutator| and |get_permuted_degree|.
Recall that the degrees may be permuted, thus we have to call
|permuted_degree| at the proper places.

@u
lisp operator commutators_of_degree;
lisp procedure commutators_of_degree(bracketname,degree);
begin scalar properties_for_direct_access,vector_i,entry_i_j,info_list,
             degree_sequence,degree_i;
  check_if_bracketname_is_a_liebracket_in("COMMUTATORS_OF_DEGREE:");
  @<Initialize properties for direct access@>;
  info_list:=get(bracketname,'info_list);
  if not integer_valued(degree:=make_oplist(degree)) then @|
     stop_with_error("DEGREE:",'list . degree,"invalid degree",nil);
  degree_sequence:=get(bracketname,'degree_sequence);
  @<Return the list of commutators with right degree@>;
end$

@ In this case we need not make exceptions for 0 since all $\lie(i,0)$
are initialized to 0, hence have a value.

@<Return the list of commutators with right degree@>=
  return 'list .  
    for i:=-n_used:m_used join
    <<vector_i:=getv(vector_structure,n+i);
      degree_i:=degree_part getv(info_list,n+i);@/
      for j:=i:m_used join
      if (null (entry_i_j:=getv(vector_i,m-j)) or 
          null commutator_part_of(entry_i_j)) and@|
         sub_degree(degree,@|
                    permuted_degree(add_degrees(degree_i,
                                       degree_part getv(info_list,n+j)),
                                    degree_sequence))@/
      then
	list list(bracketname,i,j)
    >> @;

@*1 Introduction of new generators. In the light of all the tools we
made for showing and maintaining the degree, definition and history of
a generator, it will be very convenient to have a procedure
|new_generators| that introduces a new generator for some unknown
commutator and at the same time updates the |info_list|.  Recall that
associated to a liebracket are the properties |even_used| and
|odd_used|, indicating the number of even and odd generators that are
actually used, respectively. It will be clear that we can use these
properties right here to determine first unused index available for a
newly introduced generator, and, moreover, after introducing a new
generator, have to update them.

Keeping in mind that the procedure |commutators_of_degree| may be used
to get a list of unknown commutators, for which new generators may be
introduced, it also seems convenient if |new_generators| is able to
deal with lists of unknown commutators. This can be done by calling
|new_generators| recursively on all elements of the list.

In case of a single commutator we will return the newly introduced
generator, in case of a list of commutators the corresponding list of
newly introduced generators. The second case motivates us not to
produce an error message if, for whatever reason, it impossible to
create an new generator for some object, but simply return it
unchanged, for otherwise it will be impossible to return a list
containing the generators which had already been created.

Hence we can deduce the following strategy:\medskip

\item{1.}
if the object is an atom return it unchanged.

\item{2.} if the object is an algebraic list apply |new_generators| to
all its elements and return the list of results. There is, however,
one tricky point: some commutator may occur several times on the list.
Since we are working in lisp mode this will not be detected
automatically, and thus, for each occurence a new generator would be
introduced. Therefore we must |reval| each entry of the list before
doing anything.

\item{3.} 
if the object is an other operator element but not a commutator,
return it unchanged.

\item{4.}
if the object is a commutator, check if it is possible to introduce a
new generator for it, if so update the |info_list| and return the
newly introduced generator, else return the commutator unchanged.

@u
lisp operator new_generators;
lisp procedure new_generators commutator_list;
begin scalar operatorname,bracketname,arg1,arg2,indx,
             generator,degree,definition,history;
return 
  if atom commutator_list then commutator_list
  else @+<<
    operatorname:=operator_name_of commutator_list;
    if operatorname='list then
      'list . for each commutator in arguments_of commutator_list collect @|
               new_generators reval commutator
    else
    if not get(operatorname,'rtype)='liebracket then commutator_list
    else
    @<If possible introduce and return a new generator, update |info_list|@> >>;
end$

@ It is only possible to introduce new generators for commutators of
two generators which are not out of range.

@<If possible introduce and return a new generator...@>=
begin
  bracketname:=operatorname;@/
  arg1:=first_argument_of commutator_list;
  arg2:=second_argument_of commutator_list;
  if wrong_atomic_argument(arg1) or wrong_atomic_argument(arg2) then
    return commutator_list;
  @<Check if new |generator| is possible, if so update |info_list|@>;
  return if generator then
    setk(commutator_list,generator)
    else commutator_list
end @;

@ Depending if the commutator is even or odd, we must introduce a new
even or odd generator, respectively.

@<Check if new |generator| is possible, if so update |info_list|@>=
if even_element(operatorname,commutator_list) then @|
   @<Update |even_used| and |info_list|, if new |generator| is possible@>
  else 
   @<Update |odd_used| and |info_list|, if new |generator| is possible@>
  
@ A new generator is possible if index of it (i.e., the number of used
elements plus 1) does not exceed the maximal dimension.

@<Update |even_used| and |info_list|, if new |generator| is possible@>=
begin
  indx:=get(operatorname,'even_used)+1;
  if indx<=get(operatorname,'even_dimension)
    then@/ 
      <<put(operatorname,'even_used,indx);
        generator:=list(get(operatorname,'generatorname),indx);
	@<Update the |info_list|@> >>;
end @;

@ @<Update |odd_used| and |info_list|, if new |generator| is possible@>=
begin
  indx:=get(operatorname,'odd_used)+1;
  if indx<=get(operatorname,'odd_dimension)
    then@/ 
      <<put(operatorname,'odd_used,indx);
        indx:=-indx;
        generator:=list(get(operatorname,'generatorname),indx);@/
	@<Update the |info_list|@> >>;
end @;

@ Before updating the |info_list| at index |indx|, we must compute
the degree of the newly introduced generator using |add_degrees|,
construct its definition and its history. The last can be done by
applying the procedure |add_histories|, to be implemented in the next
module.

@<Update the |info_list|@>=
degree:=add_degrees(get_degree(operatorname,arg1),
                    get_degree(operatorname,arg2));@/
history:=add_histories(get_history(operatorname,arg1),
                       get_history(operatorname,arg2));@/
definition:=list('list,arg1,arg2);
put_info(bracketname,indx,degree . definition . history) @;

@ Recall that nested commutators are treated right associative by
|simp_liebracket|. Therefore we can append the second history to the
first.

@u lisp procedure add_histories(history1,history2);
if fixp history2 then list('list,history1,history2)
else 
  if fixp history1 then 'list . history1 . arguments_of history2 
  else 'list . append(list history1,arguments_of history2)$

@ Before we can use the procedure |new_generators| we must be able to
change the properties |even_used| and |odd_used|, because these are
both initialized to 0. For clarity we will in- and output them in the
same way, namely as an algebraic list |{even_used,odd_used}|.  

@u lisp operator list_used;
lisp procedure list_used bracketname; 
<<check_if_bracketname_is_a_liebracket_in("LIST_USED:");
  list('list,get(bracketname,'even_used),get(bracketname,'odd_used))>>$

@ Before defining |even_used| and |odd_used| we must check that they
are integers and not out of range.

@u
lisp operator define_used;
lisp procedure define_used(bracketname,used_list);
begin scalar even_used,odd_used;
  check_if_bracketname_is_a_liebracket_in("DEFINE_USED:");
  if atom(used_list) or operator_name_of(used_list) neq 'list or
     length(used_list) neq 3 then 
     stop_with_error("DEFINE_USED:",used_list,"invalid list of dimensions",nil);
  even_used:=first_argument_of used_list;
  odd_used:=second_argument_of used_list;
  if even_used>get(bracketname,'even_dimension) or
     odd_used>get(bracketname,'odd_dimension)
  then rederr("DEFINE_USED: dimensions out of range");@/
  put(bracketname,'even_used,even_used);
  put(bracketname,'odd_used,odd_used);
end$

@*= Declaration and saving of liebrackets.  Now we know all ins and
outs of liebrackets (especially the list of properties associated to
them), we can finally write the procedures for the declaration and
saving of liebrackets. Moreover, we will write a procedure for
enlarging the dimensions of a liebracket.

@ For the declaration of liebrackets we will use the following syntax
$$\hbox{liebracket bracketname(generatorname,even dimension,odd
dimension[,algebra elements,parameters])}$$ where algebra elements and
parameters may be an identifier or an algebraic or lisp list of
identifiers. For this purpose we can use the macro definition
|make_oplist| defined before.

We give the procedure |liebracket| the property |stat| with value
|rlis| in order to allow more liebracket declarations at a time.
It should be noted that, in doing so, |liebracket| need not be
declared a lisp operator anymore to make it available in algebraic
mode.

Procedures with |stat='rlis| can have an arbirtrary number of
arguments which the parser passes to them on a list. In our case this
means that |liebracket| is offered a list of liebracket declarations.

@<Lisp ini...@>=
put('liebracket,'stat,'rlis)$

@ The outline of the procedure |liebracket| is real simple: for each
declaration offered extract all identifiers and dimensions from it,
check if this gives rise to a valid liebracket declaration and finally
set up the right environment.

@u lisp procedure liebracket decl_list;
begin scalar bracketname,generatorname,m,n,
             algebra_elements,parameters,rtype,vector_structure,info_list;
  for each decl in decl_list do
  begin if length decl < 4 then @|
    stop_with_error("LIEBRACKET:",decl,"invalid liebracket declaration",nil);@/
    @<Get |bracketname|, |generatorname|, |m|, |n|, 
|algebra_elements| and |parameters|@>;
    @<Check the liebracket declaration for its validity@>;
    @<Set up the environment for liebracket |bracketname|@>;
  end;
end$

@ Since |decl| is a list of length at least 4 we can retrieve the
desired variables and dimensions from it. If there are no algebra
elements or parameters specified, |algebra_elements| and |parameters|
will become |nil|. We transform them in orderly lisp lists using
|make_oplist|.

@<Get |bracketname|, |generatorname|, |m|, |n|, |algebra_elements| 
  and |parameters|@>=@/
bracketname:=car decl; generatorname:=cadr decl;@/
m:=reval caddr decl; n:=reval cadddr decl;@/
if decl:=cddddr decl then
<<algebra_elements:=car decl;algebra_elements:=make_oplist(algebra_elements);@/
if cdr decl then parameters:=cadr decl; parameters:=make_oplist(parameters)>>@;

@ For a proper liebracket declaration |bracketname| and
|generatorname| must both be identifiers and may not be any other REDUCE
structure. Moreover |m| and |n| must both be positive integers.
We do not check if all objects offered as algebra
elements or parameters are identifiers, since this cannot do any
harm.

@<Check the liebracket declaration for its validity@>=
if not idp bracketname or not idp generatorname or not fixp m or not
   fixp n or m<0 or n<0 then @|
 stop_with_error("LIEBRACKET:",decl,"invalid liebracket declaration",nil); @/
if get(bracketname,'simpfn) then @|
 stop_with_error("LIEBRACKET: operator",bracketname,
     "invalid as liebracket",nil);@/
if rtype:=get(bracketname,'rtype) then @|
 stop_with_error("LIEBRACKET:",rtype,bracketname,"invalid as liebracket");@/
if get(generatorname,'simpfn) then @|
 stop_with_error("LIEBRACKET: operator",generatorname,
    "invalid as generator",nil);@/
if rtype:=get(generatorname,'rtype) then @|
 stop_with_error("LIEBRACKET:",rtype,generatorname,"invalid as generator") @;

@ If we have a proper liebracket declaration we have to set up an
environment for the liebracket |bracketname|, first by properly
initializing the |vector_structure| and secondly by putting all other
necessary properties on the property list of |bracketname|.

Notice that properties of a liebracket that are lists initially being
empty need not be initialized.  For convenience we will list here the
lists of all properties associated with a liebracket and a Lie algebra
generator, which we will use later on. For an explanation of the
properties we refer to the sections where they were introduced.
We also recall that we have to flag |bracketname| |full| in order to
enable simplification in the way we perform it.

@d list_of_properties_of_a_liebracket=@/
'(vector_structure info_list !*jacobi_var!* even_dimension odd_dimension
even_used odd_used  degree_length degree_sequence algebra_elements
parameters oplist resimp_fn
generatorname rtype simpfn commutator_list identity_list
unsolved_identities kvalue)@;
@d list_of_properties_of_a_generator=@;@/
'(bracketname rtype simpfn kvalue)@;

@<Set up the environment for liebracket |bracketname|@>=
@<Initialize the vectors |vector_structure| and |info_list|@>;
put(bracketname,'vector_structure,vector_structure);@/
put(bracketname,'info_list,info_list);@/
put(bracketname,'!*jacobi_var!*,list t);@/
put(bracketname,'even_dimension,m);@/
put(bracketname,'odd_dimension,n);@/
put(bracketname,'even_used,0);@/
put(bracketname,'odd_used,0);@/
put(bracketname,'degree_length,1);@/
put(bracketname,'algebra_elements,algebra_elements);@/
put(bracketname,'parameters,parameters);@/
put(bracketname,'oplist,
    bracketname . generatorname . 'list . 'df . algebra_elements);@/
put(bracketname,'resimp_fn,'resimp_liebracket);@/
put(bracketname,'generatorname,generatorname);@/
put(bracketname,'rtype,'liebracket);@/
put(bracketname,'simpfn,'simp_liebracket);@/
put(generatorname,'bracketname,bracketname);@/
put(generatorname,'rtype,'algebra_generator);@/
put(generatorname,'simpfn,'simpiden);@/
flag(list bracketname,'full) @;

@ Now we know all properties associated to a liebracket we can also
write the remaining part of the clear function of a liebracket, namely
removing the properties (and flags). Notice that we do not remove the
|klist|'s of the liebracket and the generators since the commutators
and generators may be used elsewhere.

@<Remove all prop...@>=
begin scalar bracketname,generatorname;
 bracketname:=val;
 generatorname:=get(bracketname,'generatorname);
 for each property in list_of_properties_of_a_liebracket do
   remprop(bracketname,property);
 for each property in list_of_properties_of_a_generator do
   remprop(generatorname,property);@/
 remflag(list bracketname,'full);
end @;

@ Recall that the vector structure containing all commutators is a
double vector, the outer of dimension $m+n$, such that for $-n\leq
i\leq m$ at index $n+i$ all commutators $\lie(i,j)$ with $i\leq j\leq
m$ are stored at index $m-j$ in a vector of dimension $m-i$.
Moreover, we have to initialize the ``special'' commutators
$\lie(i,0)$ ($-n\leq i\leq 0$) and $\lie(0,j)$  and
$\lie(j,j)$ ($0<j\leq m$) to 0 and mark them as special.
The second field of each special entry is the klist replacement; it
must be initialized to |nil|.

@<Initialize |vector_structure|@>=
vector_structure:=mkvect(m+n);
for i:=-n:m do putv(vector_structure,n+i,mkvect(m-i));
for i:=-n:0 do putv(getv(vector_structure,n+i),m,'(special) . nil . 0);
for j:=1:m do 
   <<putv(getv(vector_structure,n),m-j,'(special) . nil . 0);
     putv(getv(vector_structure,n+j),m-j,'(special) . nil . 0)>> @;

@ The |info_list| has to be initialized as follows: each generator
|y(i)| has initial degree 0, definition |y(i)| and history $i$.

@<Initialize the vectors |vector...@>=
@<Initialize |vector_...@>;
info_list:=mkvect(m+n);
for i:=-n:m do putv(info_list,n+i,'(0) . i . i) @;

@*1 Saving and printing all values of a liebracket. Saving a
liebracket |bracketname| boils down to saving all properties of
|bracketname| in a file, this time including the |klist|'s of the
liebracket and the generator. Before saving it all we have to call
|rmsubs| in order to enable simplification of algebraic expressions
after being read in. We print the values of all properties using the
procedure |prin1|, which, unlike the procedure |prin2|, prints
rereadable expressions.

One should be aware of the fact that the standard REDUCE token reader
|token1| is not able to recognize and return a vector as a token.
However, on our system |token1| has been replaced by a token reader
based on the lisp underneath REDUCE, which \`{\i}s able to read
vectors. Moreover, on another configuration at our site which did use
|token1| as the token reader, we could patch it in such way that it
was also able to read vectors without too much difficulty.

The implementation of |save_liebracket| beneath explicitly uses the
fact that the token reader used is able to read vectors. If this is
not the case |save_liebracket| has to be rewritten in such a way that
all commutators to be saved are temporarily stored on a list which can
be read by |token1|. In that case the vector structure has to be build
up again. This case will be dealt with in a separate change file
belonging to this package.

The procedure |save_liebracket| has to be available in algebraic mode. 

@d print_this_property_of(bracketname)=@/
<<prin2 "put('"; prin1 bracketname; prin2 ",'"; prin1 property; prin2 ",'"; 
  prin1 get(bracketname,property); prin2 ")$"; terpri(); terpri()>> @;

@u
lisp operator save_liebracket;
lisp procedure save_liebracket(bracketname,savefile);
begin scalar generatorname;
  check_if_bracketname_is_a_liebracket_in("SAVE_LIEBRACKET:");@/
  generatorname:=get(bracketname,'generatorname);@/
  rmsubs();
  out savefile;@/
  write "lisp$"; %Reading the properties should be done in symbolic mode%
  terpri(); terpri();@/ 
  @<Check if this package has been loaded@>;
  for each property in 'klist . list_of_properties_of_a_liebracket do
    print_this_property_of(bracketname);@/
  write "flag('(",bracketname,"),'full)$"; terpri(); terpri();
  for each property in 'klist . list_of_properties_of_a_generator do
    print_this_property_of(generatorname);
  @<Incorporate statements to repair the |vector_structure|@>;
  write "algebraic$ end$";@/
  shut savefile;
end$

@ We can check if this package has been loaded by verifying that the
procedure |simp_liebracket| has a definition, using |getd|.

@<Check if this package has been loaded@>=@/
write "if not getd 'simp_liebracket then";terpri();
write "rederr(",
"""Load the Lie superalgebra package before reading this file""",")$";
terpri();terpri() @;

@ The informative part of some elements in a vector structure may have
the value |(t)|, indicating that the commutator belonging to such an
element has been reordered and the Jacobi identities with the
commutator have been computed. In this case the value of this
informative part is not ordinary |(t)| but in fact it is the value of
|!*jacobi_var!*| belonging to the liebracket under consideration.
After reading the vector structure from file this is not the case
anymore, so we have to replace all occurences of |(t)| by
|!*jacobi_var!*|. This is done by the procedure
|repair_vector_structure_of|.

Notice that due to the procedure |find_unprocessed_commutators_of|
only commutators with |-n_used|${}\leq i,j \leq{}$|m_used| have
been processed, hence these are the only commutators that have to be
repaired.

@u
lisp procedure repair_vector_structure_of bracketname;
begin scalar properties_for_direct_access,!*jacobi_var!*,vector_i,entry_i_j;
  @<Initialize properties for dir...@>;
  !*jacobi_var!*:=get(bracketname,'!*jacobi_var!*);
  for i:=-n_used:m_used do
  begin vector_i:=getv(vector_structure,n+i);
    for j:=i:m_used do
      if (entry_i_j:=getv(vector_i,m-j)) and informative_part_of(entry_i_j)='(t) 
      then @|
         putv(vector_i,m-j,!*jacobi_var!* . k_info_and_commutator_part_of entry_i_j);
  end;
end$

@ @<Incorporate statem...@>=@/
write "repair_vector_structure_of '",bracketname,"$"; terpri(); terpri() @;

@ The result of applying the procedure |save_liebracket| is a file,
which can only be read using this package. It will also be convenient
to have a procedure that lists all known commutators in a rereadable
form. A statement |a:=b| can be printed like that by applying
|varpri(b,list('setk,mkquote a,mkquote b),'only)|. With this knowledge
we can easily implement a procedure |print_liebracket| which print the
definitions of all known commutators $\lie(i,j)$ for |-n_used|${}\leq
i\leq j\leq{}$|m_used|, which are not special. Printing of the
definition of special commutators is not useful since these
commutators will allways be 0. 
 
@u
lisp operator print_liebracket;
lisp procedure print_liebracket bracketname;
begin scalar properties_for_direct_access,vector_i,commutator_i_j;
  check_if_bracketname_is_a_liebracket_in("PRINT_LIEBRACKET:");@/
  @<Initialize properties for dir...@>;
  for i:=-n_used:m_used do
  begin vector_i:=getv(vector_structure,n+i);
    for j:=i:m_used do
      if (i neq 0) and (j neq 0) and (i neq j or i<0) and @|
         (commutator_i_j:=getv(vector_i,m-j)) and 
         (commutator_i_j:=aeval commutator_part_of commutator_i_j) then @|
        varpri(commutator_i_j,@|
               list('setk,mkquote list(bracketname,i,j),mkquote commutator_i_j),
               'only);
  end;
end$
   
@*1 Changing the dimensions of a liebracket. Until now the dimensions
of a liebracket have to be given on declaration and cannot be changed
anymore. It would be very inconvenient if the only way to enlarge the
dimensions is to declare a larger liebracket and do all computations
again.  Therefore we will write a procedure |change_dimensions_of|
which does a better job. It can be used both to enlarge or diminish
the dimensions of the Lie algebra. It should be available in algebraic
mode.

Essentially the only actions necessary for ``enlarging'' a liebracket are
the construction of a larger/smaller |vector_structure|, putting all
information from the old to the new vector structure and update the
properties containing information about the dimensions.

Moreover, if the new dimensions are bigger than the old ones, some of
the newly introduced commutators may have to be adjusted according to
linear dependencies found before and, moreover, the length of the
degrees of the newly introduced generators has to be adapted.

@u
lisp operator change_dimensions_of;
lisp procedure change_dimensions_of(bracketname,m,n);
begin scalar old_vector_structure,old_m,old_n,new_m,new_n,old_vector_i,entry_i_j,
      vector_structure,old_info_list,info_list,vector_i,m_used,n_used,
      degree_length,kernel_list;
  check_if_bracketname_is_a_liebracket_in("CHANGE_DIMENSIONS_OF:");@/
  old_m:=get(bracketname,'even_dimension);
  old_n:=get(bracketname,'odd_dimension);@/
  new_m:=min(m,old_m);new_n:=min(n,old_n);@/
  m_used:=min(new_m,get(bracketname,'even_used));
  n_used:=min(new_m,get(bracketname,'odd_used));@/
  old_vector_structure:=get(bracketname,'vector_structure);
  old_info_list:=get(bracketname,'info_list);
  @<Initialize the vectors |vector...@>;
  @<Transfer all known commutators and degrees to the larger vectors@>;
  put(bracketname,'vector_structure,vector_structure);@/
  put(bracketname,'info_list,info_list);
  put(bracketname,'even_dimension,m);
  put(bracketname,'odd_dimension,n);@/
  put(bracketname,'even_used,m_used);
  put(bracketname,'odd_used,n_used);
  @<Take care of the eventual linear dependencies and the degree length@>;
end$

@ We have to transfer all known commutators |bracketname(i,j)| with
|-new_n|${}\leq i,j\leq{}$|new_m| and also all degrees of
|generatorname(i)| for |-new_n|${}\leq i\leq{}$|new_m|.

@<Transfer all known...@>=
for i:=-new_n:new_m do
begin
  old_vector_i:=getv(old_vector_structure,old_n+i);@/
  vector_i:=getv(vector_structure,n+i);
  for j:=i:new_m do
    if (entry_i_j:=getv(old_vector_i,old_m-j)) then
       putv(vector_i,m-j,entry_i_j);@/
  putv(info_list,n+i,getv(old_info_list,old_n+i));
end @;

@ We take care of eventual linear dependencies in a very pragmatic
way: if the new dimensions are larger than the old ones, we just do
the assignments for the generators again. The adjustment of the new
commutators will then be taken care of automatically.

If |degree_length| is the current degree length, changing the degree
length for the newly introduced generators can be taken care of by two
subsequent calls of |change_degree_length| with |2*degree_length| and
|degree_length|, respectively.

Notice that before taking care of the eventual dependencies the degree
length has to possess its proper length since |relation_analysis| uses
this to decide which kernel to solve for. 

@<Take care of the eventu...@>=
if m>old_m or n>old_n then
begin
degree_length:=get(bracketname,'degree_length);
change_degree_length(bracketname,2*degree_length);
change_degree_length(bracketname,degree_length);
kernel_list:=
  for each dependency in get(get(bracketname,'generatorname),'kvalue) collect@|
    first_element_of dependency;
for each kernel in kernel_list do setk(kernel,aeval kernel);
end

@*= Printing and parsing of commutators. The next subject to be dealt
with is the preparation of facilities for a ``default'' liebracket
whose commutators can be typed in and will be printed out using square
brackets. For this we will introduce a global variable
|default_liebracket!*|, which is the name of the liebracket known to
REDUCE as the default liebracket. We initialize it to |lie|, since
this is the name we usually use.

@<Lisp ini...@>=@/
initialize_global(default_liebracket!*,'lie)$

@ REDUCE input is parsed by the procedure |xread1|, which converts
it to a form that can be translated to lisp by the procedure |form|.
If we want REDUCE to translate expressions in square brackets as
commutators of the default liebracket |default_liebracket!*|, we can
do this by giving the token |![| the property |stat| with value
|liebracket_stat|, indicating to the parser |xread1| that expressions
in square brackets are to be dealt with by a separate procedure
|liebracket_stat|, and flagging |!]| as a delimiter, again indicating
to |xread1| that the expression currently being parsed has ended.

@<Lisp ini...@>=@/
put('![,'stat,'liebracket_stat)$@/
flag(list '!],'delim)$

@ If |xread1| encounters the token |![|, it calls the procedure
|liebracket_stat|, which will take control over the parsing of the
commutator that follows the opening bracket. The argument(s) of the
commutator can be read by recursively calling |xread| which will parse
until it encounters the delimiter |!]| and return the parsed
arguments.

Before returning the list representing the commutator of the default
liebracket we must scan another token in order to keep the parsing
process in a correct state.

@u
lisp procedure liebracket_stat;
begin scalar arguments;
  arguments := xread nil;@/
  arguments :=@+
    if atom arguments or car arguments neq '!*comma!* @| then
      arguments @+
    else cdr arguments;@/
  scan();
  return default_liebracket!* . arguments;
end$

@ If some algebraic operatorname has the property |prifn|, the printing
routines of REDUCE will transfer the control over the printing of an
element of such operatorname to the procedure which name is the value of
the property |prifn|. So by introducing a |prifn| |liebracket_prifn|
we can print the commutators of some liebracket using square brackets.

If we want to print a commutator using square brackets we can print
``['' and ``]'' and in between the arguments of the commutator
separated by commas.

@u
lisp procedure liebracket_prifn commutator;
begin 
  prin2!* "[";@/
  inprint('!*comma!*,0,arguments_of commutator);@/
  prin2!* "]";
end$

@ The operatorname initially declared default liebracket must have the
right |prifn|.

@<Lisp ini...@>=@/
put(default_liebracket!*,'prifn,'liebracket_prifn)$

@ The default liebracket can be changed by using the procedure
|default_liebracket|, which is available in algebraic mode and takes
all necessary actions.

@u lisp operator default_liebracket;

lisp procedure default_liebracket bracketname;
begin 
  remprop(default_liebracket!*,'prifn);@/
  default_liebracket!*:=bracketname;@/
  put(default_liebracket!*,'prifn,'liebracket_prifn);
end$

@*= Basis transformations of Lie superalgebras. If one is working with
a Lie superalgebra, the structure of which is partially determined and
partially is to be determined, it may be very convenient to perform a
basis transformation of this algebra. Proceeding this way the
structure of the remaining part might become clearer.  Of course if we
perform a basis transformation, we also want to have all (known)
commutators expressed in elements of the new basis.  Hence we have to
perform a transformation of the commutator table, i.e., the
vectorstructure, too.

For this suppose we are given a Lie (super)algebra with basis $x_i$
$(i\in I)$, and furthermore suppose we have a basis transformation
given by $y_j=a^i_j x_i$ $(j\in I)$, where we have used the sommation
convention. Then in general a commutator $[x_k,x_l]$ $(k,l\in I,k\leq
l)$ is given by 
$$[x_k,x_l]=c^i_{kl}x_i+\sum_{k',l'} [x_{k'},x_{l'}]_u$$ 
where the subscript $u$ denotes (yet) unknown commutators, i.e.,
commutators having empty entries in the vectorstructure.  Using the
basis transformation given above, we are interested in the commutators
$$[y_p,y_q]=a^k_p a^l_q [x_k,x_l]$$ 
with all commutators on the right hand side expressed in terms of the
new basis $y_j$.  Therefore we can perform the transformation of a Lie
product table in two steps:\medskip

\item{1.} Express all commutators $[x_k,x_l]$ in terms of the new
basis.
\item{2.} Express all commutators $[y_p,y_q]$ in terms of the new
basis using the result of the first step.
\enditem
It seems clear that we need the inverse transformation
$b^j_i=(a^i_j)^{-1}$ in order to perform the first step. Using the
inverse transformation we get
$$[x_k,x_l]=c^i_{kl}b^j_i y_j+\sum b^p_{k'}b^q_{l'}[y_p,y_q]$$

For the implementation in REDUCE of this rather simple exercise there
are some additional points involved. For instance, the newly created
commutators should be stored in another liebracket since the
generatorname changed from, let's say, $x$ to $y$. And, how exactly to
perform the transformation and the inverse transformation. As we will
see later on, we will use some rather tricky temporary demolishing of
the old liebracket structure to get everything right. Moreover, for
reasons of efficiency, we will temporarily bypass all kinds of checks
performed on the assignment of commutators and instead perform one
sufficient check for all assignments beforehand.

@ The first point to be taken care of is how to deal with the
transformation and inverse transformation. Points involved are {\it
a\/}) how to represent the transformation, {\it b\/}) how to compute the
inverse transformation and finally, in the light of the last remark of
the previous section, {\it c\/}) how to see to it that the transformation
leaves no elements untransformed.

By a basis transformation we understand a (possibly empty) algebraic
list of equations of the form $y_j=a^i_j x_j$, where $(a^i_j)$ is
invertible. Notice that we do not require a basis transformation to
comprise all old generators $x_i$, but also a subset is allowed.
Nevertheless if we are transforming commutators to a new basis, such
non occuring generators may appear in the computation of some
commutators. Hence, in order to get a correct new commutator table, 
we must find the remaining non transformed generators and transform
them into new generators. 

In ordinary cases it will be sufficient only to transform the used
generators, by which we mean generators in one of the ranges
$1,\dots,$|even_used| or $-1,\dots,$|odd_used|. However, for whatever
reason, some generator outside these ranges may also be used, in which
case transforming the used generators will not be sufficient.
Therefore we will introduce a switch |full_transformation| indicating
if transformation of the used generators is sufficient or if
transformation of the whole algebra is necessary. We put
|full_transformation| \&{off} be default.

@<Lisp ini...@>=@/
new_switch(full_transformation,nil)$

@ Depending on the switch |full_transformation| we have different
upperbounds for the even and odd generators to be transformed, namely
the properties |even_used| and |odd_used| if |full_transformation| is
\&{off}, or |even_dimension| and |odd_dimension| if
|full_transformation| is \&{on}, of the liebracket under consideration.
In both cases we will use vectors |transform_vector| and
|inverse_vector| to store the basis transformation and its inverse.

@<Get |even_bound| and |odd_bound| and initialize the vectors@>=
  if null !*full_transformation then
    begin even_bound:=get(bracketname,'even_used);
          odd_bound:=get(bracketname,'odd_used);
    end
  else 
    begin even_bound:=get(bracketname,'even_dimension);
          odd_bound:=get(bracketname,'odd_dimension);
    end;@/
  transform_vector:=mkvect(even_bound+odd_bound);
  inverse_vector:=mkvect(even_bound+odd_bound) @;


@ The outline of the top level transformation procedure
|transform_liebracket| is very easy: extend and process the basis
transformation, compute the inverse transformation, and transform
the commutator table using these transformations. 

@u
lisp operator transform_liebracket; 
lisp procedure transform_liebracket(bracketname,new_bracketname,
   new_generatorname,basis_transformation);
begin scalar generatorname,even_bound,odd_bound,transform_vector,inverse_vector,
    new_generator,transformed_sq,splitted_sf,generator_list,x_gap,y_gap,
    new_even_used,new_odd_used,result;
  check_if_bracketname_is_a_liebracket_in("TRANSFORM_LIEBRACKET:");
  generatorname:=get(bracketname,'generatorname);
  @<Get |even_bound|...@>;
  @<Extend and compute the basis transformation and its inverse@>;
  @<Transform the liebracket |bracketname| into |new_bracketname|@>;
end$

@*1 Storage and extension of the transformation. Given the algebraic
list |basis_transformation| representing the basis transformation we
have to fill the vectors |transform_vector| and |inverse_vector|.
Processing the transformation essentially consists of three steps:
read in and process |basis_transformation|, compute the inverse
transformation and extend the transformation to the whole range of
generators that must be transformed.

@<Extend and compute the ...@>=
@<Read in and process |basis_transformation|@>;
@<Compute and store the inverse transformation@>;
@<Extend the transformation to |even_bound| and |odd_bound|@> @;

@ A basis transformation consists of a number of transformation rules
of the form $y_j=a^i_jx_i$, which we have to check for their validity
and store in the vector |transform_vector|. These checks consist of:
\medskip 

\item{1.} checking if the transformation rule is of the
proper form.  

\item{2.} checking that the new generator $y_j$ lies
within the proper range.  

\item{3.} checking that the right hand side of the transformation rule
is indeed a sum of generators. This can for instance be done using
the procedure |operator_coeff|. We will, however, use the low level
procedure |split_form|, which underlies the procedure |operator_coeff|
and acts on standard forms, since we can use the splitted forms
returned by |split_form|, as we will see further on. The right hand
side of the transformation rule is a sum of generators if the
independent part, i.e., the |car|, of the result of |split_form| is
|nil|.
\item{4.} checking that the sign of the generators on the right hand
side of the tranformation rules is the same as on the left hand side.
\enditem 
Moreover, in order to know for which old generators we have to solve
the set of transformation rules we store all occuring generators on
|generator_list|.

For each transformation rule we will store the right hand side as a
standard quotient |transformed_sq| as well as the splitted list returned by
|split_form|, |splitted_sf|. 

@d lhs=cadr
@d rhs=caddr
@d valid_transformation_rule = @/
  (eqexpr transformation_rule and 
  not atom lhs transformation_rule and @|
  operator_name_of lhs transformation_rule = new_generatorname) @;
@d valid_generator(generator) = @/
  (fixp generator and generator neq 0 and generator <= even_bound and
generator >= -odd_bound)@;
@d get_new_generator_ok= @/
   <<new_generator:=first_argument_of lhs(transformation_rule);
     valid_generator(new_generator)>>@;
@d sign_and_bound_check= @/
  for each generator in cdr splitted_sf product
    if (generator:=first_argument_of car generator)*new_generator>0 and @|
       valid_generator(generator) then 1 @+else 0 @;
@d valid_transformed_sq = @/
  null car splitted_sf and sign_and_bound_check=1 @;
@d extend_used_generator_list= @/
  for each generator in cdr splitted_sf do 
    if not member(generator:=car generator,generator_list) then 
      generator_list:=generator . generator_list @;
@d store_transformation_rule(i,value)=@/putv(transform_vector,odd_bound+i,value)@;
@d store_inverse_rule(i,value)=@/putv(inverse_vector,odd_bound+i,value)@;
@d get_transform(i)=@/getv(transform_vector,odd_bound+i) @;
@d get_inverse(i)=@/getv(inverse_vector,odd_bound+i) @;

@ Given |basis_transformation| we need to process
all transformation rules in order to get all generators to solve for.
Solving the resulting system can be done by applying |solve|, but since our
checks computed the transformations in quite a lot of ways and
ensure us that we have a linear system of equations (due to the use of
|split_form| which checks for linearity), we can also use the
underlying solver for systems of linear equations |solvesys|. The
arguments of |solvsys| are a list of standard forms to be solved and a
list of kernels to solve for. Hence we have to generate a list of
standard forms representing the transformation rules.

Recall that the second argument of |split_form| is the list of
operators with respect to which to split. Moreover, notice that the
arguments of |transform_liebracket| are already simplified, since it
is a lisp operator. Therefore, we can use |simp| without harm.

@d return_transformation_as_sf=@/
  numr subtrsq(!*k2q lhs(transformation_rule),transformed_sq) @;

@<Read in and process |bas...@>=
if atom basis_transformation or operator_name_of basis_transformation neq 'list
then stop_with_error("TRANSFORM_LIEBRACKET",basis_transformation,
    "not valid as a basis transformation",nil); @/
basis_transformation:=
for each transformation_rule in arguments_of basis_transformation collect
  <<if not valid_transformation_rule or not get_new_generator_ok
    then @| stop_with_error("TRANSFORM_LIEBRACKET:",lhs(transformation_rule),
        "not allowed as a new generator",nil);@/
    transformed_sq:=simp rhs(transformation_rule);
    splitted_sf:=split_form(numr transformed_sq,list(generatorname));
    if not valid_transformed_sq then
       stop_with_error("TRANSFORM_LIEBRACKET",lhs(transformation_rule),
        "must be a sum of generators with right sign",nil);@/
    extend_used_generator_list;
    store_transformation_rule(new_generator,transformed_sq . splitted_sf);
    return_transformation_as_sf>> @;

@ The result of |solvesys| is a list of a list of standard quotients
being the solutions of the system for the list of kernels given as its
second argument preceded by |t| if the system is found to be linear.
If the system is inconsistent |solvesys| will return with an error.
For the inverse transformation we will also store the standard
quotient as well as the list of splitted standard forms returned by
|split_form|.

If the number of dependent variables of the system does not equal the
number of equations, the system is not consistent and we can stop
without trying to solve it.

@<Compute and store the inverse...@>=
if length generator_list neq length basis_transformation then
  rederr "TRANSFORM_LIEBRACKET: inconsistent transformation";
if basis_transformation then 
  basis_transformation:=caadr solvesys(basis_transformation,generator_list);
for each generator in generator_list do 
   <<transformed_sq:=first_element_of basis_transformation;
     store_inverse_rule(first_argument_of generator,
        transformed_sq . @|split_form(numr transformed_sq,list(new_generatorname)));
     @/ basis_transformation:=rest_of basis_transformation>> @;

@ After the preceding steps we are left with two (possibly partially
filled) vectors |transform_vector| and |inverse_vector| representing
the basis transformation and its inverse. For a proper transformation
of the commutator tables, however, we must be sure that both vectors
are filled completely, as far as some old generators are not already
found to be linear dependent. In other words, we have to extend the
basis transformation to the full range $1,\dots,|even_bound|$ and
$-1,\dots,-|odd_bound|$ of generators.

Since we didn't require that the generators of the preceding steps be
successive in any way, this boils down to filling in the gaps in both
|transform_vector| and |inverse_vector|. Since we want to fill in the gaps
from low to high for both even and odd generators, we have to deal with even
and odd generators separately, that is to say we will use an additional
variable |direction| to indicate whether we look at even or odd gaps and a
variable |bound| being |even_bound| or |odd_bound|, respectively.

So it is our task to go through both positive and negative ranges of
generators and check if there is a gap, i.e., there is no transformation rule
associated to a generator or there is a linear dependency for a generator
(since these generators will never occur again). If we have found a gap
|x_gap| in the transformation for the old generators, then there must 
also be a gap |y_gap| for the new generators, and we can extend the
transformation by transforming |x_gap| into |y_gap| and vice versa.

@d find_next_x_gap=@/
  repeat x_gap:=x_gap+direction 
  until abs(x_gap)>bound or @|(null getv(inverse_vector,odd_bound+x_gap)    
      and @| null assoc(list(generatorname,x_gap),get(generatorname,'kvalue)));
  if abs(x_gap)>bound then x_gap:=nil  @;

@d find_next_y_gap=@/
  repeat y_gap:=y_gap+direction 
  until abs(y_gap)>bound or null getv(transform_vector,odd_bound+y_gap) @;

@d exchange_gaps=@/
  store_inverse_rule(x_gap, mksq(list(new_generatorname,y_gap),1) . @|
       list(nil,list(new_generatorname,y_gap) . 1));@/
  store_transformation_rule(y_gap, mksq(list(generatorname,x_gap),1) . @|
       list(nil,list(generatorname,x_gap) . 1)) @;

@d fill_in_the_gaps=@/
x_gap:=y_gap:=0; find_next_x_gap; find_next_y_gap;
while x_gap do @+<<exchange_gaps; find_next_x_gap; find_next_y_gap>> @;

@<Extend the transform...@>=
<<fill_in_the_gaps; new_even_used:=y_gap-1>> where direction=1,bound=even_bound;
<<fill_in_the_gaps; new_odd_used:=-y_gap-1>> where direction=-1,bound=odd_bound @;

@*1 Transformation of the Lie product table. Now we have dealt with
the most intricate part of the transformation, we can start earning
from our efforts, since the remaining work merely consists of
simplifying expressions. However, in order to save work as much as
possible we will temporarily redefine some of the simplification
functions and data structures associated to the old liebracket
|bracketname|. Since we want to be sure to restore these changes
afterwards, we will perform this part in a procedure |transform_table|
and surround it by |errorset| in order to keep full control over
|transform_table| in case of errors, i.e., if an error occurs
|errorset| will return control to the calling procedure. In this way
we can be sure that the original data structures can be restored.

The result of |errorset| is a list containing the result of the
procedure called by |errorset|.

@<Transform the liebracket...@>=
@<Save the original data structures of |bracketname|@>;
result:=errorset(list('transform_table,mkquote bracketname,mkquote generatorname,
  mkquote new_bracketname,mkquote new_generatorname,
  mkquote even_bound,mkquote odd_bound,
  mkquote new_even_used,mkquote new_odd_used,
  mkquote transform_vector,mkquote inverse_vector),t,t);
@<Restore the data structures of |bracketname|@>;
if result then return 
  list('list,
    @|('list . @+for i:=1:new_even_used collect mk!*sq car get_transform(i)),
    @|('list . @+for i:=1:new_odd_used collect mk!*sq car get_transform(-i))) @;

@ In particular, the vector structure of the old liebracket must be
saved. We save it as the property |save_vector_structure|.

@<Save the original...@>=
put(bracketname,'save_vector_structure,get(bracketname,'vector_structure)) @;

@ Transforming the commutator table can be done in two steps: first we have to
express all old commutators in terms of the new generators, after that
the new commutators can be expressed in terms of the old ones and then
simplified to expressions in new generators.

However, before that we have to declare |new_bracketname| a Lie
(super)algebra. Notice that we have to take the same set of operators
as |algebra_elements| and |parameters|, respectively. Since a
liebracket declaration checks if its generator isn't already an
algebraic operator and if so, returns with an error message, we have
to remove the property |simpfn| for |new_generatorname|. 

Finally we will construct a grading for |new_bracketname|, using the
grading of |bracketname|. Notice that this is only useful when all the
transformation rules are homogeneous.

@u                                                          
lisp procedure transform_table(bracketname,generatorname,
   new_bracketname,new_generatorname,even_bound,odd_bound,
   new_even_used,new_odd_used,
   transform_vector,inverse_vector);
begin scalar m,n,vector_structure,vector_i,
     save_vector_structure,save_vector_i,save_entry_i_j,arg_i,arg_j,degree_length;
  remprop(new_generatorname,'simpfn);
  apply1('liebracket,list list(new_bracketname,new_generatorname,
        even_bound,odd_bound,
     get(bracketname,'algebra_elements),get(bracketname,'parameters)));
  @<Redefine the old vector structure@>;
  @<Compute and store the new vector structure@>;
  @<Construct a grading for |new_bracketname|@>;
end$

@ An entry of the vector structure may or may not have a value. If it
has a value we have to simplify it in such a way that all occurences
of old generators are replaced by new generators. It is clear that we
can use |inverse_vector| to this purpose. More specifically, we will
replace the original |simpfn| |simpiden| by |simp_transform_vector|
that takes it values from |inverse_vector|.

Since we have to be sure that the generators to be simplified lie
within the range covered by |inverse_vector|, we check for this.
Moreover, we need to know where to get |inverse_vector|. For this
purpose we will flag |generatorname| |full|, in which way the
generatorname will be added to the arguments of its simplication
function. We store |inverse_vector| on the property list of
|generatorname|, as well as |bounds|, i.e. the even and odd bound of
before, as we need these quantities to access |inverse_vector|.

Notice that |inverse_vector| may contain empty entries, namely for
those entries that correspond to linear dependent generators. For
these generators, we may simply apply |simpiden| for further
simplification.

@u

lisp procedure simp_transform_vector generator;
begin scalar generatorname,i,bounds,inverse_vector,value;
  generatorname:=car generator;
  i:=cadr generator;
  bounds:=get(generatorname,'bounds);
  inverse_vector:=get(generatorname,'inverse_vector);
  if i<-car bounds or i>cdr bounds then
    stop_with_error("TRANSFORM_LIEBRACKET:",generator,
      "out of the transformation range. Use 'on fulltransformation;'.",nil);
  return 
    if value:=getv(inverse_vector,car bounds+i) then car value
    else simpiden generator
end$

@ Of course we have to put some additional properties on the property
list of |generatorname|. Moreover we have to apply |rmsubs| so that we
can be sure that the result of |simpiden| will be resimplified.

@<Take preparations for temporary simplification@>=@/
put(generatorname,'inverse_vector,inverse_vector);@/
put(generatorname,'bounds,odd_bound . even_bound);@/
put(generatorname,'simpfn,'simp_transform_vector);@/
flag(list generatorname,'full);
rmsubs() @;

@ If an entry of |vector_structure| has no value, i.e., the commutator
corresponding to it is not known, we have to express it in terms of
the new liebracket and generators. To this purpose we will write a
procedure |transform_commutator|, which computes, given two entries of
|transform_vector| or |inverse_vector|, the commutator $[y_i,y_j]$
expressed in old generators or $[x_i,x_j]$ expressed in new
generators, respectively.

The entries of both of the vectors mentioned above contain a dotted
pair, the |car| of which is the generator as standard quotient, the
|cdr| a list applicable by the procedure |build_sum| of the TOOLS
package, used to compute the outcome of a multilinear operator applied
to the numerators of its arguments, as a standard quotient. Therefore,
we have to divide the result by the denominators of the standard
quotients. Notice that the second argument of |build_sum| is a stack
of splitted arguments, hence we have to reverse the arguments.

@u
lisp procedure transform_commutator(bracketname,transformed_i,transformed_j);
quotsq(build_sum(bracketname,list(cdr transformed_j,cdr transformed_i)),@|
       !*f2q multf(denr car transformed_i,denr car transformed_j))$

@ With the above preparations redefining the |vector_structure| is
utterly simple. Recall that entries of a vector structure are dotted
pairs, the |car| of which is the informative part, to be initialized
to |nil|, the |cadr| the klist info part, which for the temporary
vector structure may be also be set to |nil|. Moreover, recall that
|vector_structure| entries whose informative part is |'(special)|
should not be changed.

The reader should be aware that a |arg_i| in the code below
will only be used if has a value, namely all commutators containing
linear dependent generators have a value according to this dependency,
so will be dealt with in the ``known part''. The same applies to the
call of |get_inverse(j)|.

After installing the temporary vector structure, we have to call
|rmsubs| again, in order effectuate the resubstitution of the unknown
commutators into commutators of the new liebracket.

@<Redefine the old vector...@>=
@<Take preparations for ...@>;
save_vector_structure:=get(bracketname,'save_vector_structure);
m:=get(bracketname,'even_dimension); n:=get(bracketname,'odd_dimension);
@<Initialize |vector_structure|@>;
for i:=-odd_bound:even_bound do begin
  save_vector_i:=getv(save_vector_structure,n+i);
  vector_i:=getv(vector_structure,n+i);
  arg_i:=get_inverse(i);
  for j:=i:even_bound do
    if (save_entry_i_j:=getv(save_vector_i,m-j)) and 
       commutator_part_of(save_entry_i_j) then @/
      (if not_special(save_entry_i_j) then @|
          putv(vector_i,m-j,nil . nil . aeval commutator_part_of save_entry_i_j))
    else putv(vector_i,m-j,@|
      nil . nil . mk!*sq transform_commutator(new_bracketname,arg_i,get_inverse(j)))
end;
put(bracketname,'vector_structure,vector_structure);
rmsubs() @;

@ After the redefinition of the vector structure of |bracketname| any
commutator of |bracketname| will be automatically simplified to an
expression in commutators and generators of the new liebracket.  Hence
a commutator $[y_i,y_j]$ of the transformed liebracket can be computed
in two ways: using the transformation it can be expressed in terms of
the old generators, which will be simplified to an expression in the
new generators, or just as |new_bracketname(i,j)|. This gives rise to
relation for |new_bracketname| which can be solved and stored using
|relation_analysis|. As we will use !*SQ prefix forms, which will not
be simplified again, to represent the relation, we must be sure that
full simplication has taken place, i.e., we have to apply |subs2| or
|simp!*| at the right places.

Notice that due to linear dependencies of the old generators the
vector |transform_vector| need not be filled entirely. Due to
|fill_in_the_gaps| we know, however, that with the exception of 0
|transform_vector| is exactly filled from |-new_odd_used| to
|new_even_used|. Of course we don't have to compute commutators
outside of this range.  ``Special'' commutators need to be solved
neither. Since we don't use the vector structure here to see if a
commutator is special we will check using |i| and |j| directly.

Finally we will set |even_used| and |odd_used| to |new_even_used| and
|new_odd_used|, respectively, for the newly created
liebracket, as these are the actual numbers of used even and odd generators.

@d no_special_pair_i_j= @/
  i neq 0 and j neq 0 and (i neq j or i<0) @;

@<Compute and store the new...@>=
for i:=-new_odd_used:new_even_used do
  if (arg_i:=get_transform(i)) then
    for j:=i:new_even_used do
      if (arg_j:=get_transform(j)) and no_special_pair_i_j then @|
  relation_analysis(mk!*sq subtrsq(simp!* list(new_bracketname,i,j),@|
        subs2 transform_commutator(bracketname,arg_i,arg_j)),
      new_bracketname);
put(new_bracketname,'even_used,new_even_used);
put(new_bracketname,'odd_used,new_odd_used)@;

@ Using |transform_vector| and the procedure |degree_of| and
|define_degree| it is not very hard to construct a grading for
|new_bracketname|, under the assumption that the transformation is
homogeneous w.r.t.\ this grading. Notice that all elements of
|transform_vector| are filled consecutively from |-new_odd_used| to
|new_even_used|, with the exception of 0.

Before doing anything we should, however, change the length of the
grading of |new_bracketname| to the length of the grading of
|bracketname|, that is, to the length of the list of currently used
components of the grading of |bracketname|.

@<Construct a grading...@>=@/
degree_length:=if get(bracketname,'degree_sequence) then 
                  length get(bracketname,'degree_sequence)
               else get(bracketname,'degree_length);
change_degree_length(new_bracketname,degree_length);
for i:=-new_odd_used:new_even_used do 
  if i neq 0 then 
    define_degree(list(new_generatorname,i),degree_of(mk!*sq car get_transform(i)))
 
@ @<Restore the data stru...@>=@/
put(bracketname,'vector_structure,get(bracketname,'save_vector_structure));
remprop(bracketname,'save_vector_structure);
put(generatorname,'simpfn,'simpiden);
remprop(generatorname,'inverse_vector);
remflag(list generatorname,'full);
remprop(generatorname,'bounds) @;

@*= Necessary changes to the klist mechanism. In one of the previous
sections we already explained that the ordinary klist mechanism of
REDUCE is not very suited for liebrackets, since all occuring
commutators are stored on a linear list, where the number of
commutators may be quit big. Moreover we made some preparations in the
vector structure of a liebracket, in order to replace the ordinary
klist mechanism with an information system which is based on the
vector structure. 

Here, it is our intention to change two basic procedures of the REDUCE
source in such a way that the outer appearance of the system remains
the same, whereas hidden under the surface for liebrackets the klist
mechanism is replaced by a vector structure based counterpart.

@ The first procedure to be changed is |fkern|. It is used by |mksq| and
checks if there is a klist entry for some kernel, if not, it generates one,
and eventually, returns this entry. 

Changes are obvious: if the operatorname of the kernel is a liebracket
and both arguments are integers, not the klist should be used but the
vector structure of the concerning liebracket. If not both arguments
are integers, we can only use the klist mechanism.

@u
symbolic procedure fkern u;
   begin scalar x,y;
        if atom u then @+return list(u,nil);
        if get(operator_name_of u,'rtype)='liebracket and @|
           fixp first_argument_of u and fixp second_argument_of u then @+
           return fkern_liebracket u;
        y := if atom car u then get(car u,'klist) @+else exlist!*;
        if not (x := assoc(u,y))
          then <<x := list(u,nil);
                 y := ordad(x,y); 
                 if atom car u
                   then <<kprops!* := union(list car u,kprops!*);
                          put(car u,'klist,y)>>
                  else exlist!* := y>>;
        return x
   end$

@ The procedure |fkern_liebracket| is fairly simple. If the
|k_info_of| the vector structure entry of the considered
commutator exists, return it, otherwise construct it and adapt the
vector structure accordingly. For the last action we shall use
|rplaca|. It is easily seen that the use of |rplaca| causes no harm.

Since the |k_info| can be found directly in the vector structure, and
doesn't have to be found by association, one would expect that the
kernel can be removed from the |k_info| entry. This, however, is not
true: the kernel in the |k_info| is used by |mksq| to obtain an identical
address for the considered kernel in all standard quotients. Thus a
lot of memory can be saved.

Notice that the arguments of the considered commutator need not be
checked to lie within proper bounds.  This is due to the fact that
|fkern| (indirectly) only is called from procedures which have already
checked the bounds.

@u symbolic procedure fkern_liebracket commutator;
begin scalar bracketname,i,j,entry_i_j;
  bracketname:=operator_name_of commutator;
  i:=first_argument_of commutator;
  j:=second_argument_of commutator;
  entry_i_j:=get_vector_structure(bracketname,i,j);
  if null entry_i_j then @|entry_i_j:=
     put_vector_structure(bracketname,i,j,nil . list(commutator,nil) . nil)
  else if null k_info_of entry_i_j then @|
    rplaca(k_info_and_commutator_part_of entry_i_j,list(commutator,nil));
  return k_info_of entry_i_j;
end$

@ The procedure |prepsq!*| is used to reorder an algebraic expression
for output. After |factor O;| the expression is ordered w.r.t. all
kernels of the operator $O$. The order of the kernels of the operator
$O$ is governed by its klist. Since the klist of a liebracket is not
complete, in fact it only contains info about commutators containing
non integer arguments, we have to choose a different method here. We
do this as follows: we find all the kernels of the concerning
liebracket using the procedure |find_all_kernels| of the TOOLS package
and order the thus obtained list of kernels w.r.t.\ the standard
kernel ordering of REDUCE, by calling the procedure |ordn|. This list
can now be used as a replacement for the klist.

@u 
symbolic procedure prepsq!* u;
   begin scalar x,!*combinelogs;
        if null numr u then return 0;
        x := setkorder
                  append((for each j in factors!*
                     join if not idp j then nil
                          else if get(j,'rtype)='liebracket then
                            ordn get_all_kernels(numr u,j)
                          else for each k in get(j,'klist) collect car k),
                   append(factors!*,ordl!*));
        if kord!* neq x or wtl!*
          then u := formop numr u . formop denr u;
        u := if !*rat or !*div
                      or upl!* or dnl!*
               then replus prepsq!*1(numr u,denr u,nil)
              else sqform(u,function prepsq!*2);
        setkorder x;
        return u
   end$

@ The end of a REDUCE input file must be marked with |end|.
@u end@+;

@*= Index. This section contains the cross reference index of all
identifiers, together with the numbers of the modules in which they
are used. Underlined entries correspond to module numbers where the
identifier was declared.
\bigskip