OKlibrary  0.2.1.6
Constructions.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 22.10.2011 (Swansea) */
00002 /* Copyright 2011 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/Algebra/Lisp/Ringframes/Rings/ResidueClasses.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/NumberTheory/Lisp/ModularArithmetic.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/RamseyTheory/Lisp/VanderWaerden/Certificates.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")$
00027 
00028 
00029 /* *******************
00030    * Rabung's method *
00031    *******************
00032 */
00033 
00034 /* m colours, arithmetic progressions of length k, and n vertices: */
00035 rabung_valid_param(m,k,n) := integerp(m) and integerp(k) and integerp(n) and
00036  m >= 2 and k >= 3 and mod(n-1,k-1)=0 and block([p : (n-1)/(k-1)],
00037   primep(p) and p >= k and mod(p,m) = 1)$
00038 
00039 rabung_derived_parameters(m,k,n) := block([p : (n-1)/(k-1)],
00040  [p,smallest_primitive_modular_root(p)])$
00041 
00042 /* The colouring map, defined for inputs in ZZ_n, returning an element
00043    in ZZ_m:
00044 */
00045 rabung_colouring_map(m,k,n) := block([p, r],
00046  [p,r] : rabung_derived_parameters(m,k,n),
00047  buildq([m,p, d : discrete_log_bydef_hash(p,r)], lambda([x],
00048    if mod(x,p)=0 then if x=0 then 0 else 1
00049    else canhom_residues(m)(d(x)))))$
00050 
00051 /* The partition (attempted vdW-certificate) corresponding to the colouring: */
00052 rabung_attempted_certificate(m,k,n) := block([c : rabung_colouring_map(m,k,n)],
00053  seq2certificatevdw(create_list(c(i),i,0,n-1)))$
00054 
00055 rabung_checkdirect_certificate(m,k,n) :=
00056  certificate_vdw_p(create_list(k,i,1,m),n,rabung_attempted_certificate(m,k,n))$
00057 
00058 rabung_checkcriterion(m,k,n) := block(
00059  [p : (n-1)/(k-1), c : rabung_colouring_map(m,k,n), crit : true, A],
00060   if c(-1)=0 then
00061     (if length(map(c,setn(ceiling((k-1)/2)))) = 1 then return(false))
00062   else if length(map(c,setn(k-1))) = 1 then return(false),
00063   A : okl_make_array(fixnum,p-1),
00064   for i : 1 thru p-1 do A[i] : c(i),
00065   for a : 1 thru (p-1)-(k-1) while crit do
00066     if length(setify(create_list(A[i],i,a,a+k-1)))=1 then crit:false,
00067   crit)$
00068 
00069 /* We have rabung_checkdirect_certificate(m,k,n) iff 
00070    rabung_checkcriterion(m,k,n).
00071 */
00072 
00073 
00074 /* Searching for successful parameter values */
00075 
00076 /* Computing the next possible prime > p: */
00077 rabung_next_candidates(m,k,p) := block([pn : max(k,next_prime(p))],
00078  while mod(pn,m)#1 do pn : next_prime(pn),
00079  [pn,pn*(k-1)+1])$
00080 /* Computes the last p with n < N: */
00081 rabung_final_prime(m,k,p,N) := block([n : p*(k-1)+1, pn],
00082  if n >= N then return([]),
00083  [pn,n] : rabung_next_candidates(m,k,p),
00084  while n < N do (p:pn, [pn,n] : rabung_next_candidates(m,k,p)),
00085  return(p))$
00086 
00087 /* Searching for parameter values p,n with n <= N: */
00088 rabung_search(m,k,N) := rabung_search_(m,k,N,0)$
00089 /* Now providing the last p-value (the next is to be considered): */
00090 rabung_search_(m,k,N,p) := block([res:[],r,n:p*(k-1)+1],
00091  if oklib_monitor then print(sconcat("vdw_",m,"(",k,") : ", vanderwaerdend(m,k))),
00092  while n < N do (
00093    r : rabung_search_next(m,k,p,N),
00094    if r#false then (
00095      res : cons(r,res), [p,n] : r, if oklib_monitor then print(p,n)
00096    )
00097    else return()
00098  ),
00099  reverse(res))$
00100 /* Remark: For every n-value returned we have vdw_m(k) > n. */
00101 
00102 rabung_search_next(m,k,p,N) := block([n,res:false],
00103  while res=false do (
00104    [p,n] : rabung_next_candidates(m,k,p),
00105    if n > N then return(),
00106    if rabung_checkcriterion(m,k,n) then res : [p,n]
00107  ),
00108  res)$
00109 
00110