OKlibrary  0.2.1.6
Certificates.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/Hypergraphs/Lisp/SetSystems.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Generators/Schur.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/RamseyTheory/Lisp/VanderWaerden/Certificates.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/RamseyTheory/Lisp/Schur/Numbers.mac")$
00027 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lambda.mac")$
00028 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Ringframes/Rings/ResidueClasses.mac")$
00029 
00030 
00031 /* *****************
00032    * Basic notions *
00033    *****************
00034 */
00035 
00036 /*
00037    A "Schur-certificate" P for a natural number r corresponds to a solution of
00038    schur_nbfclud(r,n), that is, certifies that schur(r) > n.
00039 
00040    P is a block partition of {1,...,n} into r blocks, that is, a list of
00041    r disjoint subsets of {1,...,n} whose union is the whole set.
00042 */
00043 certificate_schur_p(r,n,P) := is(r = length(P)) and
00044  blockpartitionp(P,setn(n)) and
00045  every_s(lambda([b], not has_schurtriple(b)), P)$
00046 
00047 certificate_wschur_p(r,n,P) := is(r = length(P)) and
00048  blockpartitionp(P,setn(n)) and
00049  every_s(lambda([b], not has_wschurtriple(b)), P)$
00050 
00051 
00052 /* For a list of subsets of {1,...,n} check whether P is "palindromic",
00053    that is, whether for every element (subset) p of P it is true that
00054    v is in p iff n+1-v is in p, except that in case 3 divides n+1 the
00055    elements (n+1)/3 and 2(n+1)/3 are exempted:
00056 */
00057 schurpalindromic_subsets_p(n,P) :=
00058  if mod(n+1,3)#0 then palindromic_subsets_p(n,P) else
00059   block([palin : true],
00060    for p in P while palin do
00061      for x in setdifference(p,{(n+1)/3,2*(n+1)/3}) while palin do
00062        if not elementp(n+1-x,p) then palin : false,
00063    palin)$
00064 wschurpalindromic_subsets_p(n,P) := palindromic_subsets_p(n,P)$
00065 
00066 
00067 /* Check whether P is a palindromic Schur-certificate for r and n: */
00068 certificate_pdschur_p(r,n,P) := schurpalindromic_subsets_p(n,P) and
00069  certificate_schur_p(r,n,P)$
00070 
00071 certificate_pdwschur_p(r,n,P) := wschurpalindromic_subsets_p(n,P) and
00072  certificate_wschur_p(r,n,P)$
00073 
00074 
00075 /* Checking the "full symmetry-breaking" condition: */
00076 
00077 schurfsb_p(n,P) :=
00078  gelementp(sublist(create_list(schur(i-1),i,1,length(P)), lelb(n)), P)$
00079 wschurfsb_p(n,P) :=
00080  gelementp(sublist(create_list(wschur(i-1),i,1,length(P)), lelb(n)), P)$
00081 pdschurfsb_p(n,P) :=
00082  gelementp(sublist(create_list(schur(i-1),i,1,length(P)), lelb(ceiling(n/2))), P)$
00083 pdwschurfsb_p(n,P) :=
00084  gelementp(sublist(create_list(wschur(i-1),i,1,length(P)), lelb(ceiling(n/2))), P)$
00085 
00086 certificate_schurfsb_p(r,n,P) := schurfsb_p(n,P) and certificate_schur_p(r,n,P)$
00087 certificate_wschurfsb_p(r,n,P) := wschurfsb_p(n,P) and certificate_wschur_p(r,n,P)$
00088 certificate_pdschurfsb_p(r,n,P) := pdschurfsb_p(n,P) and certificate_pdschur_p(r,n,P)$
00089 certificate_pdwschurfsb_p(r,n,P) := pdwschurfsb_p(n,P) and certificate_pdwschur_p(r,n,P)$
00090 
00091 
00092 /* *******************
00093    * Transformations *
00094    *******************
00095 */
00096 
00097 /* Unfolding a compressed palindromic partition (creating an ordinary
00098    (palindromic) partition, where "compressed" means working on the vertices
00099    of the palindromic hypergraph):
00100 */
00101 uncompresss_schurpalindromic_subsets(n,P) :=
00102  if mod(n+1,3)#0 then uncompresss_palindromic_subsets(n,P) else
00103   block([excp : {(n+1)/3,2*(n+1)/3}, m],
00104    m : lambda([v], if elementp(v,excp) then {v} else {v,n+1-v}),
00105    map(lambda([p], lunion(map(m,listify(p)))), P))$
00106 
00107 uncompresss_wschurpalindromic_subsets(n,P) :=
00108  uncompresss_palindromic_subsets(n,P)$
00109 
00110 
00111 /* **************************
00112    * Analysing certificates *
00113    **************************
00114 */
00115 
00116 depth_partition(P) := lmax(map(lmin,P))$
00117 /* For palindromic partitions without empty parts, n >= 1 (or, more generally,
00118    for solutions of the modular Schur-problems, weak or standard): */
00119 edepth_partition(P) := block([n : lmax(map(lmax,P))],
00120  lmax(map(lambda([x], depth_partition(map2(lambda([v], mod(x*v,n+1)), P))), inv_residues(n+1))))$
00121 
00122