OKlibrary  0.2.1.6
Schur.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 15.7.2012 (Swansea) */
00002 /* Copyright 2012 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 oklib_include("OKlib/ComputerAlgebra/TestSystem/Lisp/Asserts.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Generators/Schur.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Statistics.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/Groups/CyclicGroups.mac")$
00026 
00027 kill(f)$
00028 
00029 
00030 /* *******************
00031    * Schur's theorem *
00032    *******************
00033 */
00034 
00035 okltest_schurtriples_ohg(f) := (
00036   assert(f(0) = [[],[]]),
00037   assert(f(1) = [[1],[]]),
00038   assert(f(2) = [[1,2], [{1,1,2}]]),
00039   assert(f(3) = [[1,2,3], [{1,2},{1,2,3}]]),
00040   assert(f(4) = [[1,2,3,4], [{1,2},{1,2,3},{1,3,4},{2,2,4}]]),
00041   assert(f(5) = [[1,2,3,4,5],[{1,2},{1,2,3},{1,3,4},{2,2,4},{1,4,5},{2,3,5}]]),
00042   assert(f(6) = [[1,2,3,4,5,6],[{1,2},{1,2,3},{1,3,4},{2,2,4},{1,4,5},{2,3,5},{1,5,6},{2,4,6},{3,6}]]),
00043   true)$
00044 
00045 okltest_schurtriples_hg(f) := (
00046   assert(f(0) = [{},{}]),
00047   assert(f(1) = [{1},{}]),
00048   assert(f(2) = [{1,2}, {{1,1,2}}]),
00049   assert(f(3) = [{1,2,3}, {{1,2},{1,2,3}}]),
00050   assert(f(4) = [{1,2,3,4}, {{1,2},{1,2,3},{1,3,4},{2,2,4}}]),
00051   true)$
00052 
00053 okltest_schurtriples_me_ohg(f) := (
00054   assert(f(0) = [[],[]]),
00055   assert(f(1) = [[1],[]]),
00056   assert(f(2) = [[1,2], [{1,1,2}]]),
00057   assert(f(3) = [[1,2,3], [{1,2}]]),
00058   assert(f(4) = [[1,2,3,4], [{1,2},{1,3,4},{2,2,4}]]),
00059   assert(f(5) = [[1,2,3,4,5],[{1,2},{1,3,4},{2,2,4},{1,4,5},{2,3,5}]]),
00060   assert(f(6) = [[1,2,3,4,5,6],[{1,2},{1,3,4},{2,2,4},{1,4,5},{2,3,5},{1,5,6},{3,6}]]),
00061   true)$
00062 
00063 okltest_schurtriples_me_hg(f) := (
00064   for n : 0 thru if oklib_test_level=0 then 10 else 50 do
00065    block([G : schurtriples_hg(n)],
00066     assert(f(n) = [G[1], min_elements(G[2])])
00067   ),
00068   true)$
00069 
00070 okltest_wschurtriples_ohg(f) := (
00071   assert(f(0) = [[],[]]),
00072   assert(f(1) = [[1],[]]),
00073   assert(f(2) = [[1,2],[]]),
00074   assert(f(3) = [[1,2,3],[{1,2,3}]]),
00075   assert(f(4) = [[1,2,3,4],[{1,2,3},{1,3,4}]]),
00076   assert(f(5) = [[1,2,3,4,5],[{1,2,3},{1,3,4},{1,4,5},{2,3,5}]]),
00077   assert(f(6) = [[1,2,3,4,5,6],[{1,2,3},{1,3,4},{1,4,5},{2,3,5},{1,5,6},{2,4,6}]]),
00078   assert(f(7) = [[1,2,3,4,5,6,7],[{1,2,3},{1,3,4},{1,4,5},{2,3,5},{1,5,6},{2,4,6},{1,6,7},{2,5,7},{3,4,7}]]),
00079   assert(f(8) = [[1,2,3,4,5,6,7,8],[{1,2,3},{1,3,4},{1,4,5},{2,3,5},{1,5,6},{2,4,6},{1,6,7},{2,5,7},{3,4,7},{1,7,8},{2,6,8},{3,5,8}]]),
00080   for n : 0 thru 15 do block([G : schurtriples_ohg(n)],
00081     assert(f(n) = [G[1], sublist(G[2], lambda([H], is(length(H)=3)))])
00082   ),
00083   true)$
00084 
00085 okltest_nhyp_list_schurtriples_ohg(f) := (
00086   for n : 0 thru 10 do
00087     assert(f(n) = nhyp_list_ohg(schurtriples_ohg(n))),
00088   true)$
00089 
00090 okltest_nhyp_list_schurtriples_me_ohg(f) := (
00091   for n : 0 thru 20 do
00092     assert(f(n) = nhyp_list_ohg(schurtriples_me_ohg(n))),
00093   true)$
00094 
00095 okltest_nhyp_list_wschurtriples_ohg(f) := (
00096   for n : 0 thru 10 do
00097     assert(f(n) = nhyp_list_ohg(wschurtriples_ohg(n))),
00098   true)$
00099 
00100 okltest_nhyp_schurtriples_ohg(f) := (
00101   for n : 0 thru 10 do
00102     assert(f(n) = nhyp_ohg(schurtriples_ohg(n))),
00103   true)$
00104 
00105 okltest_nhyp_schurtriples_me_ohg(f) := (
00106   for n : 0 thru 10 do
00107     assert(f(n) = nhyp_ohg(schurtriples_me_ohg(n))),
00108   true)$
00109 
00110 okltest_nhyp_wschurtriples_ohg(f) := (
00111   for n : 0 thru 10 do
00112     assert(f(n) = nhyp_ohg(wschurtriples_ohg(n))),
00113   true)$
00114 
00115 okltest_has_schurtriple(f) := (
00116   assert(f({}) = false),
00117   assert(f({0}) = true),
00118   assert(f({1}) = false),
00119   assert(f({1,2}) = true),
00120   assert(f({1,3}) = false),
00121   assert(f({2,3}) = false),
00122   assert(f({2,4}) = true),
00123   assert(f({1,2,3}) = true),
00124   assert(f({-1,2,3}) = true),
00125   assert(f({-1,2,4}) = true),
00126   assert(f({-1,2,5}) = false),
00127   assert(f({2,4,6,12}) = true),
00128   assert(f({2,4,7,12}) = true),
00129   assert(f({2,5,7,12}) = true),
00130   assert(f({2,6,7,12}) = true),
00131   assert(f({2,6,7,15}) = false),
00132   assert(f({4,5,15,16,22,28,29,39,40,41,42,48,49,59}) = false),
00133   assert(f({1,4,7,10,30}) = false),
00134   assert(f({1,4,7,10,30,37}) = true),
00135   true)$
00136 
00137 okltest_has_wschurtriple(f) := (
00138   assert(f({}) = false),
00139   assert(f({0}) = false),
00140   assert(f({1}) = false),
00141   assert(f({1,2}) = false),
00142   assert(f({1,3}) = false),
00143   assert(f({2,3}) = false),
00144   assert(f({2,4}) = false),
00145   assert(f({1,2,3}) = true),
00146   assert(f({-1,2,3}) = true),
00147   assert(f({-1,2,4}) = false),
00148   assert(f({-1,2,5}) = false),
00149   assert(f({2,4,6,12}) = true),
00150   assert(f({2,4,7,12}) = false),
00151   assert(f({2,5,7,12}) = true),
00152   assert(f({2,6,7,12}) = false),
00153   assert(f({2,6,7,15}) = false),
00154   assert(f({4,5,15,16,22,28,29,39,40,41,42,48,49,59}) = false),
00155   assert(f({1,4,7,10,30}) = false),
00156   assert(f({1,4,7,10,30,37}) = true),
00157   true)$
00158 
00159 
00160 /* ************
00161    * Symmetry *
00162    ************
00163 */
00164 
00165 okltest_schurtriples_pd_ohg(f) := (
00166   assert(f(0) = [[],[]]),
00167   assert(f(1) = [[1],[]]),
00168   assert(f(2) = [[1,2],[{1,2}]]),
00169   assert(f(3) = [[1,2],[{1,2}]]),
00170   assert(f(4) = [[1,2],[{1,2}]]),
00171   assert(f(5) = [[1,2,3,4],[{1,2},{1,4},{2,4}]]),
00172   assert(f(6) = [[1,2,3],[{1,2},{1,3},{2,3}]]),
00173   assert(f(7) = [[1,2,3,4],[{1,2},{2,3},{2,4},{1,3,4}]]),
00174   assert(f(8) = [[1,2,3,4,6],[{1,2},{1,4},{2,4},{3,6}]]),
00175   true)$
00176 
00177 okltest_wschurtriples_pd_ohg(f) := (
00178   assert(f(0) = [[],[]]),
00179   assert(f(1) = [[1],[]]),
00180   assert(f(2) = [[1],[]]),
00181   assert(f(3) = [[1,2],[{1,2}]]),
00182   assert(f(4) = [[1,2],[{1,2}]]),
00183   assert(f(5) = [[1,2,3],[{1,2}]]),
00184   assert(f(6) = [[1,2,3],[{1,2},{1,3},{2,3}]]),
00185   assert(f(7) = [[1,2,3,4],[{1,2},{2,3},{2,4},{1,3,4}]]),
00186   assert(f(8) = [[1,2,3,4],[{1,2},{1,4},{2,4}]]),
00187   true)$
00188 
00189 okltest_nver_schurtriples_pd_ohg(f) := (
00190   for n : 0 thru cokltl(10,20) do
00191     assert(f(n) = nver_ohg(schurtriples_pd_ohg(n))),
00192   true)$
00193 
00194 okltest_nver_wschurtriples_pd_ohg(f) := (
00195   for n : 0 thru cokltl(10,20) do
00196     assert(f(n) = nver_ohg(wschurtriples_pd_ohg(n))),
00197   true)$
00198 
00199 
00200 /* *****************
00201    * Group triples *
00202    *****************
00203 */
00204 
00205 okltest_grouptriples_ougrp2ohg(f) := (
00206   assert(f(cyclic_ougrp(1)) = [[],[]]),
00207   /* XXX */
00208   true)$
00209 
00210 okltest_grouptriples_ugrp2hg(f) := (
00211   assert(f(cyclic_ugrp(1)) = [{},{}]),
00212   /* XXX */
00213   true)$
00214 
00215 okltest_grouptriples_me_ougrp2ohg(f) := (
00216   assert(f(cyclic_ougrp(1)) = [[],[]]),
00217   /* XXX */
00218   true)$
00219 
00220 okltest_grouptriples_me_ugrp2hg(f) := (
00221   assert(f(cyclic_ugrp(1)) = [{},{}]),
00222   /* XXX */
00223   true)$
00224 
00225 okltest_wgrouptriples_ougrp2ohg(f) := (
00226   assert(f(cyclic_ougrp(1)) = [[],[]]),
00227   /* XXX */
00228   true)$
00229 
00230 okltest_wgrouptriples_ugrp2hg(f) := (
00231   assert(f(cyclic_ugrp(1)) = [{},{}]),
00232   /* XXX */
00233   true)$
00234 
00235 okltest_nver_grouptriples_ougrp2ohg(f) := block([C],
00236   assert(f([[0],C]) = 0),
00237   assert(f([[0,1],C]) = 1),
00238   assert(f([[0,1,3],C]) = 2),
00239   true)$
00240 
00241 okltest_nver_grouptriples_ugrp2hg(f) := block([C],
00242   assert(f([{0},C]) = 0),
00243   assert(f([{0,1},C]) = 1),
00244   assert(f([{0,1,3},C]) = 2),
00245   true)$
00246 
00247 okltest_nver_grouptriples_me_ougrp2ohg(f) := block([C],
00248   assert(f([[0],C]) = 0),
00249   assert(f([[0,1],C]) = 1),
00250   assert(f([[0,1,3],C]) = 2),
00251   true)$
00252 
00253 okltest_nver_grouptriples_me_ugrp2hg(f) := block([C],
00254   assert(f([{0},C]) = 0),
00255   assert(f([{0,1},C]) = 1),
00256   assert(f([{0,1,3},C]) = 2),
00257   true)$
00258 
00259 okltest_nver_wgrouptriples_ougrp2ohg(f) := block([C],
00260   assert(f([[0],C]) = 0),
00261   assert(f([[0,1],C]) = 1),
00262   assert(f([[0,1,3],C]) = 2),
00263   true)$
00264 
00265 okltest_nver_wgrouptriples_ugrp2hg(f) := block([C],
00266   assert(f([{0},C]) = 0),
00267   assert(f([{0,1},C]) = 1),
00268   assert(f([{0,1,3},C]) = 2),
00269   true)$
00270 
00271 okltest_nhyp_grouptriples_ougrp2ohg(f) := (
00272   for G in append(create_list(cyclic_ougrp(n),n,1,cokltl(5,20)), create_list(sym_l_ougrp(n),n,1,cokltl(4,5))) do
00273     assert(f(G) = nhyp_ohg(grouptriples_ougrp2ohg(G))),
00274   true)$
00275 
00276 okltest_nhyp_wgrouptriples_ougrp2ohg(f) := (
00277   for G in append(create_list(cyclic_ougrp(n),n,1,cokltl(5,20)), create_list(sym_l_ougrp(n),n,1,cokltl(4,5))) do
00278     assert(f(G) = nhyp_ohg(wgrouptriples_ougrp2ohg(G))),
00279   true)$
00280 
00281 okltest_mschurtriples_ohg(f) := (
00282   assert(f(0) = [[],[]]),
00283   assert(f(1) = [[1],[]]),
00284   assert(f(2) = [[1,2],[{1,2},{1,2}]]),
00285   assert(f(3) = [[1,2,3],[{1,2},{1,2,3},{1,2,3},{1,2,3},{1,2,3},{2,3}]]),
00286   assert(f(4) = [[1,2,3,4],[{1,2},{1,2,3},{1,3,4},{1,2,3},{2,4},{1,2,4},{1,3,4},{1,3},{2,3,4},{1,2,4},{2,3,4},{3,4}]]),
00287   true)$
00288 
00289 okltest_mschurtriples_hg(f) := (
00290   assert(f(0) = [{},{}]),
00291   assert(f(1) = [{1},{}]),
00292   assert(f(2) = [{1,2},{{1,2}}]),
00293   assert(f(3) = [{1,2,3},{{1,2},{1,2,3},{2,3}}]),
00294   assert(f(4) = [{1,2,3,4},{{1,2},{1,2,3},{1,3,4},{2,4},{1,2,4},{1,3},{2,3,4},{1,2,4},{3,4}}]),
00295   true)$
00296 
00297 okltest_mschurtriples_me_ohg(f) := (
00298   assert(f(0) = [[],[]]),
00299   assert(f(1) = [[1],[]]),
00300   assert(f(2) = [[1,2],[{1,2}]]),
00301   assert(f(3) = [[1,2,3],[{1,2},{2,3}]]),
00302   assert(f(4) = [[1,2,3,4],[{1,2},{2,4},{1,3},{3,4}]]),
00303   true)$
00304 
00305 okltest_mschurtriples_me_hg(f) := (
00306   assert(f(0) = [{},{}]),
00307   assert(f(1) = [{1},{}]),
00308   assert(f(2) = [{1,2},{{1,2}}]),
00309   assert(f(3) = [{1,2,3},{{1,2},{2,3}}]),
00310   assert(f(4) = [{1,2,3,4},{{1,2},{2,4},{1,3},{3,4}}]),
00311   true)$
00312 
00313 okltest_wmschurtriples_ohg(f) := (
00314   assert(f(0) = [[],[]]),
00315   assert(f(1) = [[1],[]]),
00316   assert(f(2) = [[1,2],[]]),
00317   assert(f(3) = [[1,2,3],[{1,2,3},{1,2,3},{1,2,3},{1,2,3}]]),
00318   assert(f(4) = [[1,2,3,4],[{1,2,3},{1,3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,4},{2,3,4}]]),
00319   true)$
00320 
00321 okltest_wmschurtriples_hg(f) := (
00322   assert(f(0) = [{},{}]),
00323   assert(f(1) = [{1},{}]),
00324   assert(f(2) = [{1,2},{}]),
00325   assert(f(3) = [{1,2,3},{{1,2,3}}]),
00326   assert(f(4) = [{1,2,3,4},{{1,2,3},{1,3,4},{1,2,4},{2,3,4},{1,2,4}}]),
00327   true)$
00328 
00329 okltest_nver_mschurtriples_ohg(f) := (
00330   for n : 0 thru cokltl(10,20) do
00331     assert(f(n) = nver_ohg(mschurtriples_ohg(n))),
00332   true)$
00333 
00334 okltest_nver_mschurtriples_hg(f) := (
00335   for n : 0 thru cokltl(10,20) do
00336     assert(f(n) = nver_hg(mschurtriples_hg(n))),
00337   true)$
00338 
00339 okltest_nver_mschurtriples_me_ohg(f) := (
00340   for n : 0 thru cokltl(10,20) do
00341     assert(f(n) = nver_ohg(mschurtriples_me_ohg(n))),
00342   true)$
00343 
00344 okltest_nver_mschurtriples_me_hg(f) := (
00345   for n : 0 thru cokltl(10,20) do
00346     assert(f(n) = nver_hg(mschurtriples_me_hg(n))),
00347   true)$
00348 
00349 okltest_nver_wmschurtriples_ohg(f) := (
00350   for n : 0 thru cokltl(10,20) do
00351     assert(f(n) = nver_ohg(wmschurtriples_ohg(n))),
00352   true)$
00353 
00354 okltest_nver_wmschurtriples_hg(f) := (
00355   for n : 0 thru cokltl(10,20) do
00356     assert(f(n) = nver_hg(wmschurtriples_hg(n))),
00357   true)$
00358 
00359 okltest_nhyp_mschurtriples_ohg(f) := (
00360   for n : 0 thru cokltl(10,20) do
00361     assert(f(n) = nhyp_ohg(mschurtriples_ohg(n))),
00362   true)$
00363 
00364 /*
00365 okltest_nhyp_mschurtriples_hg(f) := (
00366   for n : 0 thru cokltl(10,20) do
00367     assert(f(n) = nhyp_hg(mschurtriples_hg(n))),
00368   true)$
00369 */
00370 
00371 /*
00372 okltest_nhyp_mschurtriples_me_ohg(f) := (
00373   for n : 0 thru cokltl(10,20) do
00374     assert(f(n) = nhyp_ohg(mschurtriples_me_ohg(n))),
00375   true)$
00376 */
00377 
00378 /*
00379 okltest_nhyp_mschurtriples_me_hg(f) := (
00380   for n : 0 thru cokltl(10,20) do
00381     assert(f(n) = nhyp_hg(mschurtriples_me_hg(n))),
00382   true)$
00383 */
00384 
00385 okltest_nhyp_wmschurtriples_ohg(f) := (
00386   for n : 0 thru cokltl(10,20) do
00387     assert(f(n) = nhyp_ohg(wmschurtriples_ohg(n))),
00388   true)$
00389 
00390 /*
00391 okltest_nhyp_wmschurtriples_hg(f) := (
00392   for n : 0 thru cokltl(10,20) do
00393     assert(f(n) = nhyp_ohg(wmschurtriples_hg(n))),
00394   true)$
00395 */
00396 
00397 okltest_symmetrictriples_ohg(f) := (
00398   assert(f(0) = [[],[]]),
00399   assert(f(1) = [[],[]]),
00400   assert(f(2) = [[[2,1]],[]]),
00401   assert(f(3)[1] = [[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]),
00402   /* XXX */
00403   true)$
00404 
00405 okltest_symmetrictriples_hg(f) := (
00406   assert(f(0) = [{},{}]),
00407   assert(f(1) = [{},{}]),
00408   assert(f(2) = [{[2,1]},{}]),
00409   assert(f(3)[1] = {[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]}),
00410   /* XXX */
00411   true)$
00412 
00413 okltest_symmetrictriples_me_ohg(f) := (
00414   assert(f(0) = [[],[]]),
00415   assert(f(1) = [[],[]]),
00416   assert(f(2) = [[[2,1]],[]]),
00417   assert(f(3)[1] = [[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]),
00418   /* XXX */
00419   true)$
00420 
00421 okltest_symmetrictriples_me_hg(f) := (
00422   assert(f(0) = [{},{}]),
00423   assert(f(1) = [{},{}]),
00424   assert(f(2) = [{[2,1]},{}]),
00425   assert(f(3)[1] = {[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]}),
00426   /* XXX */
00427   true)$
00428 
00429 okltest_wsymmetrictriples_ohg(f) := (
00430   assert(f(0) = [[],[]]),
00431   assert(f(1) = [[],[]]),
00432   assert(f(2) = [[[2,1]],[]]),
00433   assert(f(3)[1] = [[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]),
00434   /* XXX */
00435   true)$
00436 
00437 okltest_wsymmetrictriples_hg(f) := (
00438   assert(f(0) = [{},{}]),
00439   assert(f(1) = [{},{}]),
00440   assert(f(2) = [{[2,1]},{}]),
00441   assert(f(3)[1] = {[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]}),
00442   /* XXX */
00443   true)$
00444 
00445 okltest_nver_symmetrictriples_ohg(f) := (
00446   for n : 0 thru cokltl(3,4,5) do
00447     assert(f(n) = nver_ohg(symmetrictriples_ohg(n))),
00448   true)$
00449 
00450 okltest_nver_symmetrictriples_hg(f) := (
00451   for n : 0 thru cokltl(3,4,5) do
00452     assert(f(n) = nver_hg(symmetrictriples_hg(n))),
00453   true)$
00454 
00455 okltest_nver_symmetrictriples_me_ohg(f) := (
00456   for n : 0 thru cokltl(3,4,5) do
00457     assert(f(n) = nver_ohg(symmetrictriples_me_ohg(n))),
00458   true)$
00459 
00460 okltest_nver_symmetrictriples_me_hg(f) := (
00461   for n : 0 thru cokltl(3,4,5) do
00462     assert(f(n) = nver_hg(symmetrictriples_me_hg(n))),
00463   true)$
00464 
00465 okltest_nver_wsymmetrictriples_ohg(f) := (
00466   for n : 0 thru cokltl(3,4,5) do
00467     assert(f(n) = nver_ohg(wsymmetrictriples_ohg(n))),
00468   true)$
00469 
00470 okltest_nver_wsymmetrictriples_hg(f) := (
00471   for n : 0 thru cokltl(3,4,5) do
00472     assert(f(n) = nver_hg(wsymmetrictriples_hg(n))),
00473   true)$
00474 
00475 okltest_nhyp_symmetrictriples_ohg(f) := (
00476   for n : 0 thru cokltl(3,4,5) do
00477     assert(f(n) = nhyp_ohg(symmetrictriples_ohg(n))),
00478   true)$
00479 
00480 okltest_nhyp_wsymmetrictriples_ohg(f) := (
00481   for n : 0 thru cokltl(3,4,5) do
00482     assert(f(n) = nhyp_ohg(wsymmetrictriples_ohg(n))),
00483   true)$
00484 
00485