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/Hypergraphs/Lisp/Basics.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Generators/VanderWaerden.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/BasicNotions.mac")$
00027 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/Groups/CyclicGroups.mac")$
00028 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/Groups/SymmetricGroups.mac")$
00029 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/InvertibleElements.mac")$
00030 
00031 
00032 /* *******************
00033    * Schur's theorem *
00034    *******************
00035 */
00036 
00037 /* The hypergraph with vertex set {1, ..., n} (n >= 0) and hyperedges {x,y,z}
00038    with x+y=z (note that x=y is possible, while z notin {x,y}).
00039    The order is monotonic (larger n add hyperedges to the end), with first
00040    z increasing, and second x increasing.
00041 */
00042 schurtriples_ohg(n) :=
00043  [create_list(i,i,1,n), create_list({x,z-x,z}, z,2,n, x,1,floor(z/2))]$
00044 schurtriples_hg(n) := ohg2hg(schurtriples_ohg(n))$
00045 /* Without subsumptions ("me" for "minimal elements"):
00046    Precisely the hyperedges {x,2x} with 3x <= n subsume other hyperedges,
00047    namely precisely the hyperedge {x,2x,3x}.
00048 */
00049 schurtriples_me_ohg(n) :=
00050  [create_list(i,i,1,n),
00051   delete(0,create_list(if x#z/3 then {x,z-x,z} else 0, z,2,n, x,1,floor(z/2)))]$
00052 schurtriples_me_hg(n) := ohg2hg(schurtriples_me_ohg(n))$
00053 
00054 /* The "weak" form, now not allowing x=y: */
00055 wschurtriples_ohg(n) :=
00056  [create_list(i,i,1,n), create_list({x,z-x,z}, z,2,n, x,1,floor((z-1)/2))]$
00057 wschurtriples_hg(n) := ohg2hg(wschurtriples_ohg(n))$
00058 /* wschurtriples_ohg(n) is obtained from schurtriples_ohg(n) by removing
00059    hyperedges of length 2. So wschurtriples_hg(n) is 3-uniform.
00060 */
00061 
00062 /* Statistics functions: */
00063 
00064 nver_schurtriples_hg(n) := n$
00065 nver_schurtriples_ohg(n) := n$
00066 nver_wschurtriples_hg(n) := n$
00067 nver_wschurtriples_ohg(n) := n$
00068 
00069 nhyp_list_schurtriples_hg(n) := if n <= 1 then [] elseif n=2 then [[2,1]] else
00070  [[2, floor(n/2)], [3, floor((n-1)/2) * ceiling((n-1)/2)]]$
00071 nhyp_list_schurtriples_ohg(n) := nhyp_list_schurtriples_hg(n)$
00072 nhyp_list_schurtriples_me_hg(n) := if n <= 1 then [] elseif n<=3 then [[2,1]]
00073  else [[2, floor(n/2)], [3, floor((n-1)/2)*ceiling((n-1)/2) - floor(n/3)]]$
00074 nhyp_list_schurtriples_me_ohg(n) := nhyp_list_schurtriples_me_hg(n)$
00075 nhyp_list_wschurtriples_hg(n) := if n <= 2 then [] else
00076  [[3, floor((n-1)/2) * ceiling((n-1)/2)]]$
00077 nhyp_list_wschurtriples_ohg(n) := nhyp_list_wschurtriples_hg(n)$
00078 
00079 nhyp_schurtriples_hg(n) := floor(n/2) + nhyp_wschurtriples_hg(n)$
00080 nhyp_schurtriples_ohg(n) := nhyp_schurtriples_hg(n)$
00081 nhyp_schurtriples_me_hg(n) := nhyp_schurtriples_hg(n) - floor(n/3)$
00082 nhyp_schurtriples_me_ohg(n) := nhyp_schurtriples_me_hg(n)$
00083 nhyp_wschurtriples_hg(n) := floor(((n-1)/2)^2)$
00084 /* We have
00085    nhyp_wschurtriples_hg(n) = floor((n-1)/2) * ceiling((n-1)/2).
00086 */
00087 nhyp_wschurtriples_ohg(n) := nhyp_wschurtriples_hg(n)$
00088 
00089 
00090 /* Testing whether the set S contains a Schur triple (that is, whether there
00091    are x,y in S with x+y in S).
00092    Works if S is a set of integers. In general we need + and order, while
00093    the precise general assumptions have to be investigated.
00094 */
00095 has_schurtriple(S) :=
00096  if emptyp(S) then false
00097  else block([x : first_element(S)],
00098    if subsetp({x,x+x}, S) then return(true),
00099    S : disjoin(x,S),
00100    some_s(lambda([y], subsetp({y,x+y}, S)), S) or has_schurtriple(S))$
00101 
00102 /* Now not considering the cases where x=y: */
00103 has_wschurtriple(S) :=
00104  if emptyp(S) then false
00105  else block([x : first_element(S)],
00106    S : disjoin(x,S),
00107    some_s(lambda([y], subsetp({y,x+y}, S)), S) or has_wschurtriple(S))$
00108 
00109 
00110 
00111 /* ************
00112    * Symmetry *
00113    ************
00114 */
00115 
00116 /* The palindromic versions of the Schur-triples hypergraphs, with
00117    colexicographical order (note that this is different from
00118    schurtriples_ohg) and with subsumptions eliminated:
00119 */
00120 
00121 mirrorfold_schur(n) := block([div:ceiling(n/2)],
00122  if mod(n+1,3)#0 then buildq([n,div],
00123      lambda([v], if v >= div+1 then n-v+1 else v))
00124  else buildq([n,div,excl:2*(n+1)/3],
00125      lambda([v], if v >= div+1 and v#excl then n-v+1 else v)))$
00126 
00127 ver_schurtriples_pd_ohg(n) :=
00128   if mod(n+1,3)#0 then create_list(i,i,1,ceiling(n/2))
00129   else endcons(2*(n+1)/3, create_list(i,i,1,ceiling(n/2)))$
00130 
00131 schurtriples_pd_ohg(n) := block(
00132  [G : schurtriples_ohg(n), m : mirrorfold_schur(n)],
00133   [ver_schurtriples_pd_ohg(n),
00134    map(setify,
00135        sort(map(listify,
00136               min_elements_l(unique(
00137                 map(lambda([H], map(m, H)), second(G))))),
00138             colex_lessp_l))])$
00139 schurtriples_pd_hg(n) := ohg2hg(schurtriples_pd_ohg(n))$
00140 
00141 /* Remarks:
00142  - If the direct construction, as for wschurtriples_pd_ohg, would be
00143    employed here, then exactly in case of 3 divides n+1 a unit-hyperedge would
00144    be created, namely {(n+1)/3}, from {(n+1)/3, 2(n+1)/3}.
00145  - In [Symmetric Sum-Free Partitions and Lower Bounds for Schur Numbers;
00146    Fredricksen and Sweet, 2000] these unit-hyperedges (which make the
00147    hypergraphs non-colourable) are excluded, apparently by not contracting
00148    (n+1)/3 and 2(n+1)/3, and this is what we do with schurtriples_pd_ohg.
00149 */
00150 
00151 /* The palindromic versions of the weak Schur-triples hypergraphs, with
00152    colexicographical order (note that this is different from
00153    wschurtriples_ohg) and with subsumptions eliminated: */
00154 
00155 mirrorfold_wschur(n) := mirrorfold_vdw(n)$
00156 ver_wschurtriples_pd_ohg(n) := create_list(i,i,1,ceiling(n/2))$
00157 wschurtriples_pd_ohg(n) := block(
00158  [G : wschurtriples_ohg(n), m : mirrorfold_wschur(n)],
00159   [ver_wschurtriples_pd_ohg(n),
00160    map(setify,
00161        sort(map(listify,
00162               min_elements_l(unique(
00163                 map(lambda([H], map(m, H)), second(G))))),
00164             colex_lessp_l))])$
00165 wschurtriples_pd_hg(n) := ohg2hg(wschurtriples_pd_ohg(n))$
00166 
00167 /* Remarks:
00168  - wschurtriples_pd_ohg(n) = palindromise_vdw_ohg(wschurtriples_ohg(n)).
00169 */
00170 
00171 
00172 /* Statistics functions: */
00173 
00174 nver_schurtriples_pd_hg(n) :=
00175  if mod(n+1,3)#0 then ceiling(n/2) else ceiling(n/2)+1$
00176 nver_schurtriples_pd_ohg(n) := nver_schurtriples_pd_hg(n)$
00177 
00178 nver_wschurtriples_pd_hg(n) := ceiling(n/2)$
00179 nver_wschurtriples_pd_ohg(n) := nver_wschurtriples_pd_hg(n)$
00180 
00181 
00182 /* *****************
00183    * Group triples *
00184    *****************
00185 */
00186 
00187 /* Generalisation (in some form) via using a group (G,*,e):
00188    The hyperedges are now of the form {x,y,x*y} with x,y,x*y # e.
00189 */
00190 
00191 /* Creating the hyperedges by running through all x,y and removing hyperedges
00192    containing the neutral elemenet:
00193 */
00194 grouptriples_ougrp2ohg(G) := block(
00195  [V : rest(first(G)), compo_ : second(G), e : third(G)],
00196   [V,
00197    sublist(create_list({x,y,compo_(x,y)}, x,V, y,V),
00198            lambda([H], not elementp(e, H)))])$
00199 /* Note that here in general we have multiple occurrences of hyperedges. */
00200 grouptriples_ugrp2hg(G) := ohg2hg(grouptriples_ougrp2ohg(ugrp2ougrp(G)))$
00201 
00202 /* Eliminating subsumptions: */
00203 grouptriples_me_ougrp2ohg(G) := block([H : grouptriples_ougrp2ohg(G)],
00204  [first(H), min_elements_l(second(H))])$
00205 grouptriples_me_ugrp2hg(G) := block([H : grouptriples_ugrp2hg(G)],
00206  [first(H), min_elements(second(H))])$
00207 
00208 /* The sub-hypergraphs containing exactly the hyperedges of length 3: */
00209 wgrouptriples_ougrp2ohg(G) := block(
00210  [V : rest(first(G)), compo_ : second(G), e : third(G)],
00211   [V,
00212    sublist(create_list({x,y,compo_(x,y)}, x,V, y,V),
00213            lambda([H], not elementp(e, H) and length(H)#2))])$
00214 wgrouptriples_ugrp2hg(G) := ohg2hg(wgrouptriples_ougrp2ohg(ugrp2ougrp(G)))$
00215 
00216 
00217 /* Statistics functions: */
00218 
00219 nver_grouptriples_ougrp2ohg(G) := length(first(G)) - 1$
00220 nver_grouptriples_ugrp2hg(G) := length(first(G)) - 1$
00221 nver_grouptriples_me_ougrp2ohg(G) := length(first(G)) - 1$
00222 nver_grouptriples_me_ugrp2hg(G) := length(first(G)) - 1$
00223 nver_wgrouptriples_ougrp2ohg(G) := length(first(G)) - 1$
00224 nver_wgrouptriples_ugrp2hg(G) := length(first(G)) - 1$
00225 
00226 nhyp_grouptriples_ougrp2ohg(G) := block([n : length(first(G))], (n-1)*(n-2))$
00227 nhyp_wgrouptriples_ougrp2ohg(G) := block([n : length(first(G))],
00228  (n-1)*(n-3) + length(involutions_ugrd(ougrd2ugrd(G))))$
00229 /* Remark: Compared to nhyp_grouptriples_ougrp2ohg, we have to subtract
00230    the 2-hyperedges {x,x*x}, where now the involutions are doubly-counted
00231    (also as hyperedges {x,e}).
00232 */
00233 
00234 
00235 /* Special cases: */
00236 
00237 /* Modular Schur-triples (n >= 0): */
00238 mschurtriples_ohg(n) := grouptriples_ougrp2ohg(cyclic_ougrp(n+1))$
00239 mschurtriples_hg(n) := grouptriples_ugrp2hg(cyclic_ugrp(n+1))$
00240 mschurtriples_me_ohg(n) := grouptriples_me_ougrp2ohg(cyclic_ougrp(n+1))$
00241 mschurtriples_me_hg(n) := grouptriples_me_ugrp2hg(cyclic_ugrp(n+1))$
00242 wmschurtriples_ohg(n) := wgrouptriples_ougrp2ohg(cyclic_ougrp(n+1))$
00243 wmschurtriples_hg(n) := wgrouptriples_ugrp2hg(cyclic_ugrp(n+1))$
00244 
00245 nver_mschurtriples_ohg(n) := n$
00246 nver_mschurtriples_hg(n) := n$
00247 nver_mschurtriples_me_ohg(n) := n$
00248 nver_mschurtriples_me_hg(n) := n$
00249 nver_wmschurtriples_ohg(n) := n$
00250 nver_wmschurtriples_hg(n) := n$
00251 
00252 nhyp_mschurtriples_ohg(n) := n*(n-1)$
00253 /* Remark: This is (basically) http://oeis.org/A002378 . */
00254 /* nhyp_mschurtriples_hg(n) := unknown$ */
00255 /* nhyp_mschurtriples_me_ohg(n) := unknown$ */
00256 /* nhyp_mschurtriples_me_hg(n) := unknown$ */
00257 nhyp_wmschurtriples_ohg(n) := n*(n-2) + mod(n,2)$
00258 /* Remark: This is http://oeis.org/A137932 = n^2 - 2*n + mod(n,2).
00259    For every x#0 there are two y which do not lead to acceptable z = x + y,
00260    namely y = x and y = -x; this coincides in case of x = -x <=> 2x = 0,
00261    which is a unique solution in case n is odd, and no solution for even n.
00262    This is a special case of nhyp_wgrouptriples_ougrp2ohg(G).
00263 */
00264 /* nhyp_wmschurtriples_hg(n) := unknown$ */
00265 
00266 
00267 /* Symmetric groups (n >= 0): */
00268 symmetrictriples_ohg(n) := grouptriples_ougrp2ohg(sym_l_ougrp(n))$
00269 symmetrictriples_hg(n) := grouptriples_ugrp2hg(sym_l_ugrp(n))$
00270 symmetrictriples_me_ohg(n) := grouptriples_me_ougrp2ohg(sym_l_ougrp(n))$
00271 symmetrictriples_me_hg(n) := grouptriples_me_ugrp2hg(sym_l_ugrp(n))$
00272 wsymmetrictriples_ohg(n) := wgrouptriples_ougrp2ohg(sym_l_ougrp(n))$
00273 wsymmetrictriples_hg(n) := wgrouptriples_ugrp2hg(sym_l_ugrp(n))$
00274 
00275 nver_symmetrictriples_ohg(n) := n!-1$
00276 nver_symmetrictriples_hg(n) := n!-1$
00277 nver_symmetrictriples_me_ohg(n) := n!-1$
00278 nver_symmetrictriples_me_hg(n) := n!-1$
00279 nver_wsymmetrictriples_ohg(n) := n!-1$
00280 nver_wsymmetrictriples_hg(n) := n!-1$
00281 
00282 nhyp_symmetrictriples_ohg(n) := block([f : n!], (f-1)*(f-2))$
00283 nhyp_wsymmetrictriples_ohg(n) := block([f : n!],
00284  (f-1)*(f-3) + numinvolutions_symgrp(n) - 1)$
00285 
00286 
00287 /* ****************
00288    * Schur tuples *
00289    ****************
00290 */
00291 
00292 /* k >= 3 */
00293 /* To be completed. */
00294 linequations_ohg(k,n) := block([V : setn(n)],
00295   0)$
00296 /* Remark: linequations_ohg(3,n) = schurtriples_ohg(3). */
00297