OKlibrary  0.2.1.6
GreenTao.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 17.10.2009 (Swansea) */
00002 /* Copyright 2009, 2010 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/Generators/VanderWaerden.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/NumberTheory/Lisp/PrimeNumbers.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Basics.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/Combinatorics/Lisp/Enumeration/Subsets.mac")$
00027 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")$
00028 
00029 
00030 /* *****************************************
00031    * Arithmetic progressions in the primes *
00032    *****************************************
00033 */
00034 
00035 /* The list of arithmetic progressions of length k amongst the first
00036    prime numbers up to prime number p, and finishing with p;
00037    sorted by decreasing slope (that is, increasing start-value).
00038 */
00039 /* Prerequisite k >= 3, p > k. */
00040 /* Inherits prp = product_primes(k) and prk = primep(k). */
00041 arithprog_primes_finish[k,p] := arithprog_primes_finish_nm(k,p)$
00042 /* Without memoisation: */
00043 arithprog_primes_finish_nm(k,p) := block([res : []],
00044   for d : prp step prp thru (p-k)/(k-1) do block([prog : arpr(k,p,-d)],
00045     if every_s('primep, prog) then res : cons(reverse(prog),res)
00046   ),
00047   if prk then block([d : divide(p-k,k-1)],
00048     if d[2] = 0 then block([prog : arpr(k-1,k+d[1],d[1])],
00049       if every_s('primep, prog) then res : cons(cons(k,prog),res)
00050   )),
00051   return(res))$
00052 
00053 /* The list of all arithmetic progressions of length k amongst the first n
00054    prime numbers (memo=true means memoisation of arithmetic progressions).
00055    The order is first by increasing end-value of the sequence, and second
00056    by inreasing start-value.
00057 */
00058 arithprog_primes(k,n,memo) := 
00059  if k=0 then [[]] elseif n = 0 then []
00060  elseif k=1 then create_list([p], p,primes_first(n))
00061  elseif k=2 then map(listify,colex_ksubsets_l(setify(primes_first(n)),2))
00062  else block([p : 1, res : [], prp : product_primes(k), prk : primep(k)],
00063    thru n do (
00064      p : next_prime(p),
00065      if p > k then 
00066        if memo then res : append(res,arithprog_primes_finish[k,p])
00067        else res : append(res,arithprog_primes_finish_nm(k,p))
00068    ),
00069    res)$
00070 
00071 /* The hypergraph of all arithmetic progressions of size k in the first
00072    n prime numbers.
00073    Prerequisite: k, n integers, k, n >= 0.
00074    The order of the ordered version is first by increasing end-value, second
00075    by increasing start-value of the arithmetic progressions (in this
00076    way increasing (just) n means that the new hyperedges can just be
00077    appended at the end). In other words, the sorting of hyperedges is
00078    colexicographical.
00079 */
00080 arithprog_primes_ohg(k,n) := 
00081  [primes_first(n), map(setify,arithprog_primes(k,n,true))]$
00082 arithprog_primes_hg(k,n) := ohg2hg(arithprog_primes_ohg(k,n))$
00083 
00084 
00085 /* An arithmetic progressions of size k  is regarding to the structure of
00086    arithmetic progressions of size k' <= k in it isomorphic to the set
00087    {1,...,k}, that is, the arithmetic progressions of size k' in it correspond
00088    exactly to those in arithprog_hg(k',k).
00089    So we gain a better understanding  of arithprog_primes_hg(k,n) if we
00090    find out the maximal progressions in the vertex set, and remove the
00091    contained progressions.
00092    The following functions computes the ordered hypergraph of all maximal
00093    arithmetic progressions of size at least k within the first n prime numbers.
00094    Ordering is first by size, and then alphabetically.
00095    Prerequisite: 0 <= k <= n.
00096 */
00097 arithprog_primes_max_ohg(k,n) := block(
00098  [V : primes_first(n), found_empty, A : okl_make_array(any,n)],
00099   if k=0 then return([V,[{}]]),
00100   A[k] : arithprog_primes(k,n,true),
00101   if emptyp(A[k]) then return [V,[]],
00102   found_empty : false,
00103   for kp : k+1 thru n unless found_empty do (
00104     A[kp] : arithprog_primes(kp,n,true),
00105     if emptyp(A[kp]) then found_empty : true else
00106     for kpp : kp-1 thru k step -1 do  block(
00107        [E : setify(lappend(map(lambda([P],arithmetic_progressions(P,kpp)), A[kp])))],
00108        A[kpp] : sublist(A[kpp], lambda([P], not elementp(P,E)))) 
00109   ),
00110   return([V, map(setify,lappend(delete(false,ary2l(A))))]))$
00111 
00112 
00113 /* **************
00114    * Statistics *
00115    **************
00116 */
00117 
00118 nver_arithprog_primes_ohg(k,n) := n$
00119 nver_arithprog_primes_hg(k,n) := n$
00120 
00121 nhyp_arithprog_primes_ohg(k,n) := 
00122  if n=0 then if k=0 then 1 else 0 else
00123   n_arithprog_primes_c(k,n)$
00124 nhyp_arithprog_primes_hg(k,n) := nhyp_arithprog_primes_ohg(k,n)$
00125 
00126 
00127 /* *******************
00128    * Standardisation *
00129    *******************
00130 */
00131 
00132 /* The following function is to be applied to an ordered hypergraph G
00133    created by arithprog_primes_ohg, and it standardises the vertex set.
00134 
00135    A single translation from a vertex v of G to its standardisation is given
00136    by
00137      rank_primes(v),
00138    while the inverse, given a standardised index i, is given by
00139      unrank_primes(i).
00140 
00141    Faster are the generic functions standardise_ohg(G) and
00142    standardise_ary_ohg.
00143 */
00144 
00145 /* Directly by definition (very slow): */
00146 std_primes_ohg(G) := [create_list(i,i,1,length(G[1])),
00147  map(lambda([H], rank_primes_s(H)), G[2])]$
00148 
00149 arithprog_primes_stdohg(k,n) := standardise_ary_ohg(arithprog_primes_stdohg(k,n))$
00150