OKlibrary  0.2.1.6
Numbers.mac
Go to the documentation of this file.
```00001 /* Oliver Kullmann, 3.4.2009 (Swansea) */
00002 /* Copyright 2009, 2010, 2011, 2012, 2013 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/DataStructures/Lisp/Lists.mac")\$
00024 oklib_include("OKlib/ComputerAlgebra/RamseyTheory/Lisp/Sequences.mac")\$
00025
00026
00027 /* ***************************
00028    * Van der Waerden numbers *
00029    ***************************
00030 */
00031
00032 /* The main function, which handles all parameter-values (gathering all
00033    knowledge from all our sources). */
00034 /* Prerequisites: L ascendingly sorted list of natural numbers >= 1 */
00035 vanderwaerden(L) := if emptyp(L) then 1
00036  elseif first(L) = 1 then vanderwaerden(rest(L))
00037  elseif vanderwaerdend_a(L)#[] then apply(vanderwaerdend,vanderwaerdend_a(L))
00038  elseif vanderwaerdent_a(L)#[] then apply(vanderwaerdent,vanderwaerdent_a(L))
00039  elseif vanderwaerden3k_a(L)#[] then apply(vanderwaerden3k,vanderwaerden3k_a(L))
00040  elseif vanderwaerden4k_a(L)#[] then apply(vanderwaerden4k,vanderwaerden4k_a(L))
00041  elseif vanderwaerden5k_a(L)#[] then apply(vanderwaerden5k,vanderwaerden5k_a(L))
00042  elseif vanderwaerden6k_a(L)#[] then apply(vanderwaerden6k,vanderwaerden6k_a(L))
00043  elseif vanderwaerdents_a(L)#[] then apply(vanderwaerdents,vanderwaerdents_a(L))
00044  elseif vanderwaerden33k_a(L)#[] then apply(vanderwaerden33k,vanderwaerden33k_a(L))
00045  elseif vanderwaerden34k_a(L)#[] then apply(vanderwaerden34k,vanderwaerden34k_a(L))
00046  elseif vanderwaerden35k_a(L)#[] then apply(vanderwaerden35k,vanderwaerden35k_a(L))
00047  elseif vanderwaerden44k_a(L)#[] then apply(vanderwaerden44k,vanderwaerden44k_a(L))
00048 /* For the above special solutions the palindromic solutions must have been taken into account. */
00049  else block([palsol : pdvanderwaerden(L)],
00050  if palsol#unknown then (
00051    palsol : second(palsol),
00052    if listp(palsol) then palsol : first(palsol),
00053    palsol : [palsol, inf-1]
00054  ),
00055  return(palsol))\$
00056
00057 /* Remark: If L is not sorted, use vanderwaerden(sort(L)). */
00058
00059 /* Checking whether L is a valid input: */
00060 vanderwaerden_p(L) := listp(L) and
00061  every_s(integerp,L) and every_s(lambda([x],is(x >= 1)),L) and
00062  ascending_p(L)\$
00063 /* Extended parameter tuples also allow 0: */
00064 extvanderwaerden_p(L) := listp(L) and
00065  every_s(integerp,L) and every_s(lambda([x],is(x >= 0)),L) and
00066  ascending_p(L)\$
00067
00068
00069 /* ****************
00070    * Binary cases *
00071    ****************
00072 */
00073
00074 vanderwaerden3k(k) :=
00075  if k <= 39 then [
00076   3,6,9,18,22,32,46,58,77,97,
00077   114,135,160,186,218,238,279,312,349,[389,inf-1],
00078   [416,inf-1],[464,inf-1],[516,inf-1],[593,inf-1],[656,inf-1],[727,inf-1],[770,inf-1],[827,inf-1],[868,inf-1],[902+1,inf-1],
00079   [930+1,inf-1],[1006+1,inf-1],[1063+1,inf-1],[1143+1,inf-1],[1204+1,inf-1],[1257+1,inf-1],[1338+1,inf-1],[1378+1,inf-1],[1418+1,inf-1]
00080  ][k]
00081  else unknown\$
00082 vanderwaerden3k_a(L) := if length(L)#2 then [] else
00083  block([S : setify(L)],
00084   if elementp(3,S) then
00085     if length(S)=1 then [3] else [first(listify(disjoin(3,S)))]
00086   else [])\$
00087 /* For the precise values see [Ahmed 2009, 2010], and for the lower bounds see
00088    Investigations/RamseyTheory/VanderWaerdenProblems/plans/3-k/.
00089 */
00090
00091 vanderwaerden4k(k) :=
00092  if k <= 17 then [
00093   4,7,18,35,55,73,109,146,309,[328+1,inf-1],
00094   [358+1,inf-1],[401+1,inf-1],[569+1,inf-1],[681+1,inf-1],[747+1,inf-1],[871+1,inf-1],[1112+1,inf-1]
00095  ][k]
00096  else unknown\$
00097 vanderwaerden4k_a(L) := if length(L)#2 then [] else
00098  block([S : setify(L)],
00099   if elementp(4,S) then
00100     if length(S)=1 then [4] else [first(listify(disjoin(4,S)))]
00101   else [])\$
00102 /* For the precise values see [Ahmed 2009; Ahmed 2011], and for the lower
00103    bounds see Investigations/RamseyTheory/VanderWaerdenProblems/plans/4-k/.
00104 */
00105
00106 vanderwaerden5k(k) :=
00107  if k <= 13 then [
00108   5,10,22,55,178,206,260,[331,inf-1],[472+1,inf-1],[668+1,inf-1],
00109   [766+1,inf-1],[962+1,inf-1],[1204+1,inf-1]
00110  ][k]
00111  else unknown\$
00112 vanderwaerden5k_a(L) := if length(L)#2 then [] else
00113  block([S : setify(L)],
00114   if elementp(5,S) then
00115     if length(S)=1 then [5] else [first(listify(disjoin(5,S)))]
00116   else [])\$
00117 /* For 260 see [Ahmed 2013]. */
00118
00119 vanderwaerden6k(k) :=
00120  if k <= 9 then [
00121  6,11,32,73,206,1132,[1155+1,inf-1],[1167+1,inf-1],[1381+1,inf-1]
00122  ][k]
00123  else unknown\$
00124 vanderwaerden6k_a(L) := if length(L)#2 then [] else
00125  block([S : setify(L)],
00126   if elementp(6,S) then
00127     if length(S)=1 then [6] else [first(listify(disjoin(6,S)))]
00128   else [])\$
00129
00130 vanderwaerden7k_a(L) := if length(L)#2 then [] else
00131  block([S : setify(L)],
00132   if elementp(7,S) then
00133     if length(S)=1 then [7] else [first(listify(disjoin(7,S)))]
00134   else [])\$
00135
00136
00137 /* *****************
00138    * Ternary cases *
00139    *****************
00140 */
00141
00142 vanderwaerden33k(k) :=
00143  if k <= 10 then [
00144   9,14,27,51,80,107,[149+1,inf-1],[185+1,inf-1],[221+1,inf-1],[265+1,inf-1]
00145  ][k]
00146  else unknown\$
00147 vanderwaerden33k_a(L) := if length(L)#3 then [] else
00148  if L=[1,3,3] then [1]
00149  elseif L=[2,3,3] then [2]
00150  elseif rest(L,-1)#[3,3] then []
00151  else [last(L)]\$
00152 /* For the precise values and the lower bounds see [Ahmed 2011].
00153 */
00154
00155 vanderwaerden34k(k) :=
00156  if k <= 10 then [
00157   18,21,51,89,[163+1,inf-1],[177+1,inf-1],[229+1,inf-1],[290+1,inf-1],[365+1,inf-1],[387+1,inf-1]
00158  ][k]
00159  else unknown\$
00160 vanderwaerden34k_a(L) := if length(L)#3 then [] else
00161  if L=[1,3,4] then [1]
00162  elseif L=[2,3,4] then [2]
00163  elseif L=[3,3,4] then [3]
00164  elseif rest(L,-1)#[3,4] then []
00165  else [last(L)]\$
00166 /* For the lower bounds see
00167    - [Ahmed 2011]
00168    - [Yong Li, Some Lower Bounds for Three Color Van Der Waerden Numbers,
00169      2013].
00170 */
00171
00172 vanderwaerden35k(k) :=
00173  if k <= 5 then [
00174   22,32,80,[163+1,inf-1],[243+1,inf-1]
00175  ][k]
00176  else unknown\$
00177 vanderwaerden35k_a(L) := if length(L)#3 then [] else
00178  if L=[1,3,5] then [1]
00179  elseif L=[2,3,5] then [2]
00180  elseif L=[3,3,5] then [3]
00181  elseif L=[3,4,5] then [4]
00182  elseif rest(L,-1)#[3,5] then []
00183  else [last(L)]\$
00184 /* For the lower bounds see [Ahmed 2011].
00185 */
00186
00187 vanderwaerden44k(k) :=
00188  if k <= 4 then [
00189   35,40,89,[292+1,inf-1]
00190  ][k]
00191  else unknown\$
00192 vanderwaerden44k_a(L) := if length(L)#3 then [] else
00193  if L=[1,4,4] then [1]
00194  elseif L=[2,4,4] then [2]
00195  elseif L=[3,4,4] then [3]
00196  elseif rest(L,-1)#[4,4] then []
00197  else [last(L)]\$
00198
00199
00200 /* *********************
00201    * The diagonal case *
00202    *********************
00203 */
00204
00205 /* The "diagonal case", i.e., m parts, arithmetic progressions of length k
00206    (as usual, k >= 1):
00207 */
00208 vanderwaerdend(m,k) := if m=0 then 1
00209  elseif m=1 then k
00210  elseif k=1 then 1
00211  elseif k=2 then m+1
00212  elseif m=2 then vanderwaerdend2(k)
00213  elseif m=3 then vanderwaerdend3(k)
00214  elseif m=4 then vanderwaerdend4(k)
00215  elseif m=5 then vanderwaerdend5(k)
00216  elseif m=6 then vanderwaerdend6(k)
00217  else [ceiling(m^(k-1)/(4*k)),inf-1]\$
00218 /* vanderwaerdend(m,k) = vanderwaerden(create_list(k,i,1,m)) */
00219 /* Remarks: The general lower bound is from [Rabung, 1979]. */
00220
00221 /* The corresponding argument check for a vdW parameter-list L,
00222    checking whether a parameter tuple applies, returning [m,k]
00223    in the positive case and [] otherwise: */
00224 vanderwaerdend_a(L) := if emptyp(L) then [0,unknown]
00225  elseif not lconstant_p(L) then [] else [length(L),first(L)]\$
00226 /* Remark: So a vdW-tuple L falls into the range of vanderwaerdend iff
00227    vanderwaerdend_a(L) # [], and in the positive case we have
00228    vanderwaerden(L) = apply(vanderwaerdend,vanderwaerdend_a(L)).
00229    This principle is also applied for all other such special cases.
00230 */
00231
00232 /* The diagonal cases with two parts: */
00233 vanderwaerdend2(k) :=
00234  if k <= 12 then [
00235   1,3,9,35,178,1132,[3703+1,inf-1],[11495+1,inf-1],[41265+1,inf-1],[103474+1,inf-1],
00236   [178631+1,inf-1],[638144+1,inf-1]
00237  ][k]
00238  else [max(638144+1,(k-1)*2^(k-1)+1),inf-1]\$
00239 /* Remarks:
00240  - The precise numbers have been verified/computed by SAT solving
00241    methods; especially k=6 is from [Kouril, Paul, 2008].
00242  - The lower bounds for k=7,10,11,12 are computed by the method of
00243    [Rabung, 1979] (where the number for k=12 has been improved due to
00244    recomputation with greater computational power, while the number for k=11
00245    is false in the paper (what can be computed by the method is less)).
00246    See the function rabung_search in the Maxima-system.
00247  - The other bounds are in [Herwig, Heule, Lambalgen, Maaren, 2005].
00248  - The general lower bound is in [Berlekamp, 1968].
00249 */
00250 vanderwaerdend2_a(L) := if length(L)=2 and lconstant_p(L) then first(L)
00251  else []\$
00252
00253 /* The diagonal cases with three parts: */
00254 vanderwaerdend3(k) :=
00255  if k <= 9 then [
00256   1,4,27,293,[2173+1,inf-1],[11191+1,inf-1],[48811+1,inf-1],[238400+1,inf-1],[932745+1,inf-1]
00257  ][k]
00258  else [max(932745+1,ceiling(3^(k-1)/(4*k))),inf-1]\$
00259 /* Remark: The precise numbers have been verified/computed by SAT solving
00260    methods (where k=4 is from [Kouril 2012]).
00261    The bounds for k=5,6 are in [Herwig, Heule, Lambalgen, Maaren,
00262    2007], for k=7 in [Heule, Walsh, 2010], and for k=4,8,9 using the method of
00263    [Rabung, 1979] (improving the numerical values of the paper for k=8,9; see
00264    rabung_search).
00266    The general lower bound is from [Rabung, 1979].
00267 */
00268 vanderwaerdend3_a(L) := if length(L)=3 and lconstant_p(L) then first(L)
00269  else []\$
00270
00271 /* The diagonal cases with four parts: */
00272 vanderwaerdend4(k) :=
00273  if k <= 7 then [
00274   1,5,76,[1048+1,inf-1],[17705+1,inf-1],[91331+1,inf-1],[420217+1,inf-1]
00275  ][k]
00276  else [max(420217,ceiling(4^(k-1)/(4*k))),inf-1]\$
00277 /* Remark: The precise numbers have been verified/computed by SAT solving
00278    methods. The bounds are in [Herwig, Heule, Lambalgen, Maaren, 2005],
00279    except for k=7, which is in [Heule, Walsh, 2010], and for k=4 in
00280    [Rabung, 1979].
00282    The general lower bound is from [Rabung, 1979].
00283 */
00284 vanderwaerdend4_a(L) := if length(L)=4 and lconstant_p(L) then first(L)
00285  else []\$
00286
00287 /* The diagonal cases with five parts: */
00288 vanderwaerdend5(k) :=
00289  if k <= 7 then [
00290   1,6,[170+1,inf-1],[2254+1,inf-1],[98740+1,inf-1],[540025+1,inf-1],[1381687+1,inf-1]
00291  ][k]
00292  else [max(1381687+1,ceiling(5^(k-1)/(4*k))),inf-1]\$
00293 /* Remark: The bounds are in [Herwig, Heule, Lambalgen, Maaren, 2007],
00294    except for k=4,7 using the method of [Rabung, 1979] (improving the
00295    numerical values of the paper for k=7; see rabung_search).
00297    The general lower bound is from [Rabung, 1979].
00298 */
00299 vanderwaerdend5_a(L) := if length(L)=5 and lconstant_p(L) then first(L)
00300  else []\$
00301
00302 /* The diagonal cases with six parts: */
00303 vanderwaerdend6(k) :=
00304  if k <= 6 then [
00305   1,7,[223+1,inf-1],[9778+1,inf-1],[98748+1,inf-1],[816981+1,inf-1]
00306  ][k]
00307  else [max(816981+1,ceiling(6^(k-1)/(4*k))),inf-1]\$
00308 /* Remark: The bounds are in [Herwig, Heule, Lambalgen, Maaren, 2007],
00309    except for k=4, which is from [Rabung, 1979].
00311 */
00312 vanderwaerdend6_a(L) := if length(L)=6 and lconstant_p(L) then first(L)
00313  else []\$
00314
00315
00316 /* ************************
00317    * The transversal case *
00318    ************************
00319 */
00320
00321 /* The "transversal case", i.e., m parts with arithmetic progressions of
00322    length 2, one part with length k (gathering all our knowledge regarding
00323    transversal vdW-numbers).
00324    Prerequisites: m >= 0, k >= 1: */
00325 vanderwaerdent(m,k) := if m=0 then k
00326  elseif k=1 then m+1
00327  elseif m=1 then if evenp(k) then 2*k-1 else 2*k
00328  elseif k=2 then m+2
00329  else block([res : vanderwaerdenttau(m,k)],
00330   if res#unknown then return(res)
00331   else if k >= m+2 then return(vanderwaerdent_lrc(m,k))
00332   else return(unknown))\$
00333 /* vanderwaerdent(m,k) = vanderwaerden(endcons(k,create_list(2,i,1,m))) */
00334 /* The corresponding applicability check (and conversion into an argument
00335    list): */
00336 vanderwaerdent_a(L) := block([l : length(L)],
00337  if l=0 then []
00338  elseif l=1 then [0,first(L)]
00339  elseif first(L)=1 then
00340    if second(L)#2 or last(L)#2 then [] else [l-1,1]
00341  elseif first(L)#2 or L[l-1]#2 then []
00342  else [l-1,last(L)])\$
00343 /* Remark: Note that for vanderwaerdent(m,k) we have altogether m+1 parts. */
00344
00345 /* Only using the list of transversal numbers: */
00346 vanderwaerdenttau(m,k) := block([n : 1, t],
00347   t : tau_arithprog(k,n),
00348   while not listp(t) and t <= m do (
00349     n : n+1, t : tau_arithprog(k,n)
00350   ),
00351   if listp(t) then return(unknown) else return(n))\$
00352
00353
00354 /* *******************************************************
00355    * The formula from [Landman, Robertson, Culver, 2005] *
00356    *******************************************************
00357 */
00358
00359 /* The minimal natural number j>=0 which needs to be subtracted from k
00360    to yield a number coprime to the product of the primes at most r.
00361    k,r natural numbers, r, k >= 1; the meaning of r: r = m+1 (where
00362    m is the number of 2's as above).
00363 */
00364 lrc_j(r,k) := block([j : 0, pr : product_primes(r)],
00365   while gcd(k-j, pr) # 1 do j : j+1,
00366   return(j))\$
00367 /* The tests which are expressed in the paper by the
00368    function "l_{k,r}"; r, k >= 1 natural numbers.
00369 */
00370 lrc_l0p(r,k) := is(gcd(k, product_primes(r)) = r)\$
00371 lrc_l1p(r,k) := is(gcd(k-1, product_primes(r)) = r)\$
00372 /* The minimum with j: */
00373 lrc_lmin(r,k,j) := block([l : 0, pr : product_primes(r)],
00374   while l < j and gcd(k-l, pr) # r do l : l+1,
00375   return(l))\$
00376
00377 /* The formula according to the paper. */
00378 /* m >= 1, k >= m+2 */
00379 vanderwaerdent_lrc(m,k) := block([r : m+1, j],
00380  j : lrc_j(r,k),
00381  if j=0 then return(r*k),
00382  if j=1 then return(r*k-r+1),
00383  if primep(r) then
00384    if lrc_l0p(r,k) then return(r*k-r+1) else
00385    block([m : lrc_lmin(r,k,j), res],
00386     res : r*k-m*(r-2),
00387     if lrc_l1p(r,k)
00388       or (m=2 and k>=2*r-3)
00389       or (m>=3 and k >= count_primes(r)^3*(r-2))
00390     then return(res)
00391     else return([res,inf-1]))
00392  else
00393    block([res : r*k-j*(r-2)],
00394     if (j=2 and k>=2*r-3)
00395       or (j>=3 and k>= count_primes(r)^3*(r-2))
00396     then return(res)
00397     else return([res,inf-1]))
00398  )\$
00399
00400
00401 /* ********************************
00402    * Generalised transversal case *
00403    ********************************
00404 */
00405
00406 /* The generalised transversal case with suffix S, that is
00407    (m,S,k) -> L = append(create_list(2,i,1,m),S,[k]).
00408    Non-degeneracy conditions:
00409     S non-empty vdW-tuple, m >= 1, min(S) >= 3, max(S) <= k.
00410 */
00411 vanderwaerdents(m,S,k) :=
00412  if S=[3] and k=3 then
00413    if m <= 18 then [
00414     14,17,20,21,24,25,28,31,33,35,37,39,42,44,46,48,50,51 /* for 31,..51 see [Ahmed 2013] */
00415    ][m] else unknown
00416 /* this is http://oeis.org/A217005 */
00417  elseif S=[3] and k=4 then
00418    if m <= 11 then [
00419     21,25,29,33,36,40,42,45,48,52,55 /* for 40 see [Ahmed 2011], for 42,...,55 see [Ahmed 2013] */
00420    ][m] else unknown
00421 /* this is http://oeis.org/A217058 */
00422  elseif S=[3] and k=5 then
00423    if m <= 8 then [
00424     32,43,44,50,55,61,65,70 /* for 55 see [Ahmed 2011], for 61,65,70 see [Ahmed 2013] */
00425    ][m] else unknown
00426 /* this is http://oeis.org/A217059 */
00427  elseif S=[3] and k=6 then
00428    if m <= 6 then [
00429     40,48,56,60,65,71 /* for 65,71 see [Ahmed 2013] */
00430    ][m] else unknown
00431 /* this is http://oeis.org/A217060 */
00432  elseif S=[3] and k=7 then
00433    if m <= 3 then [
00434     55,65,72
00435    ][m] else unknown
00436  elseif S=[3] and k=8 then
00437    if m <= 3 then [
00438     72,83,88
00439    ][m] else unknown
00440  elseif S=[3] and k=9 then
00441    if m <= 3 then [
00442     90,99,107 /* for 107 see [Kouril 2012] */
00443    ][m] else unknown
00444  elseif S=[3] and k=10 then
00445    if m <= 2 then [
00446     108,119
00447    ][m] else unknown
00448  elseif S=[3] and k=11 then
00449    if m <= 2 then [
00450     129, 141 /* for 141 see [Schweitzer 2009] */
00451    ][m] else unknown
00452  elseif S=[3] and k=12 then
00453    if m <= 1 then [
00454     150
00455    ][m] else unknown
00456  elseif S=[3] and k=13 then
00457    if m <= 1 then [
00458     171
00459    ][m] else unknown
00460  elseif S=[3] and k=14 then
00461    if m <= 1 then [
00462     202 /* for 202 see [Kouril 2012] */
00463    ][m] else unknown
00464   elseif S=[4] and k=4 then
00465    if m <= 6 then [
00466     40,53,54,56,66,67 /* for 66,67 see [Ahmed 2013] */
00467    ][m] else unknown
00468 /* this is http://oeis.org/A217007 */
00469   elseif S=[4] and k=5 then
00470    if m <= 3 then [
00471     71,75,79
00472    ][m] else unknown
00473   elseif S=[4] and k=6 then
00474    if m <= 3 then [
00475     83,93,101 /* for 101 see [Kouril 2012] */
00476    ][m] else unknown
00477   elseif S=[4] and k=7 then
00478    if m <= 2 then [
00479     119,143 /* for 143 see [Kouril 2012] */
00480    ][m] else unknown
00481   elseif S=[4] and k=8 then
00482    if m <= 1 then [
00483     157 /* for 157 see [Kouril 2012] */
00484    ][m] else unknown
00485   elseif S=[5] and k=5 then
00486    if m <= 1 then [
00487     180
00488    ][m] else unknown
00489   elseif S=[5] and k=6 then
00490    if m <= 1 then [
00491     246 /* for 246 see [Kouril 2012] */
00492    ][m] else unknown
00493   elseif S=[3,3] and k=3 then
00494    if m <= 6 then [
00495     40,41,42,45,49,52 /* for 49,52 see [Ahmed 2013] */
00496    ][m] else unknown
00497 /* this is http://oeis.org/A217008 */
00498   elseif S=[3,3] and k=4 then
00499    if m <= 2 then [
00500     60,63
00501   ][m] else unknown
00502   elseif S=[3,3] and k=5 then
00503    if m <= 1 then [
00504     86
00505    ][m] else unknown
00506  else unknown\$
00507 vanderwaerdents_a(L) :=
00508  if length(L) <= 2 or first(L)#2 or last(L)=2 then [] else
00509  block([m : 1],
00510   while L[m]=2 do m:m+1,
00511   m : m-1,
00512   S : rest(L,m), if length(S)=1 then return([]),
00513   S : rest(S,-1),
00514   return([m,S,last(L)]))\$
00515
00516
00517 /* ******************************************************************
00518    * Transversal numbers of hypergraphs of arithmetic progresssions *
00519    ******************************************************************
00520 */
00521
00522 /* For 3 <= k <= exactk_tau_arithprog we provide initial sequences: */
00523 define_variable(
00524   exactk_tau_arithprog,
00525   22,
00526   fixnum)\$
00527 /* Note that these sequences (for tau_arithprog(k,n)) start with n=1. */
00528
00529 /* The following data has been computed by
00530    "VdWTransversalsInc 3 1 0 OutputFile" (i.e.,
00531    using SAT solvers):
00532 */
00533 tau_arithprog_seq[3] : [
00534 0,0,1,1,1,2,3,4,4,5,
00535 5,6,6,6,7,8,9,10,11,11,
00536 12,13,14,14,15,15,16,17,18,18,
00537 19,19,20,21,22,22,23,24,25,25,
00538 25,26,27,28,29,30,31,32,33,34,
00539 34,35,36,36,37,38,39,39,40,41,
00540 42,43,43,44,45,46,47,48,49,50,
00541 50,51,52,52,53,54,55,56,57,58,
00542 59,59,60,60,61,62,63,64,65,66,
00543 67,67,68,69,69,70,71,72,73,73,
00544 74,75
00545 ]\$
00546 /* The following data has been computed by
00547    "VdWTransversalsInc 4 1 0 OutputFile":
00548 */
00549 tau_arithprog_seq[4] : [
00550 0,0,0,1,1,1,2,2,2,2,
00551 3,4,4,5,5,6,6,7,7,8,
00552 8,9,9,10,10,11,11,11,12,12,
00553 13,14,14,14,15,16,16,17,18,18,
00554 19,20,20,21,21,22,23,23,24,24,
00555 25,26,26,26,27,28,29,29,30,30,
00556 31,32,33,33,34,34,35,35,36,36,
00557 37,38,39,39,40,41,41,42,42,43
00558 ]\$
00559 /* The following data has been computed by
00560    "VdWTransversalsInc 5 1 0 OutputFile":
00561 */
00562 tau_arithprog_seq[5] : [
00563 0,0,0,0,1,1,1,1,1,2,
00564 2,2,2,2,3,3,3,3,3,4,
00565 5,6,7,7,7,8,8,8,8,9,
00566 9,10,10,10,11,11,11,11,11,12,
00567 12,12,12,12,13,14,15,16,16,17,
00568 17,17,18,18,19,19,19,19,19,20,
00569 20,20,20,20,21,21,21,21,21,22,
00570 23,24,25,26,27,27,27,27,27,28,
00571 28,28,28,28,29,29,29,29,29,30,
00572 30,30,30,30,31,32,33,34,35,36,
00573 37,38,39
00574 ]\$
00575 /* The following data has been computed by
00576    "VdWTransversalsInc 6 1 0 OutputFile":
00577 */
00578 tau_arithprog_seq[6] : [
00579 0,0,0,0,0,1,1,1,1,1,
00580 2,2,2,2,2,3,3,3,3,3,
00581 4,4,4,4,4,4,5,6,6,7,
00582 8,8,8,9,9,9,9,10,10,10,
00583 10,11,12,12,12,12,13,13,13,13,
00584 13,14,15,15,16,16,17,17,17,18,
00585 18,18,19,19,19,19,20,20,21,21,
00586 21,22,22,22,22,22,23,24,25,25,
00587 26,26,26,27,27,27
00588 ]\$
00589 /* The following data has been computed by
00590    "VdWTransversalsInc 7 1 0 OutputFile":
00591 */
00592 tau_arithprog_seq[7] : [
00593 0,0,0,0,0,0,1,1,1,1,
00594 1,1,1,2,2,2,2,2,2,2,
00595 3,3,3,3,3,3,3,4,4,4,
00596 4,4,4,4,5,5,5,5,5,5,
00597 5,6,7,8,9,9,10,10,11,11,
00598 11,11,11,12,12,12,12,13,13,13,
00599 13,14,14,14,14,15,15,15,15,16,
00600 16,16,16,16,16,16,17,17,17,17,
00601 17,17,17,18,18,18,18,18,18,18,
00602 19,20,21,22,22,23,24,24,25,25,
00603 25,25,25,25,26,26,26,27,27,27,
00604 27
00605 ]\$
00606 /* The following data has been computed by
00607    "VdWTransversalsInc 8 1 0 OutputFile":
00608 */
00609 tau_arithprog_seq[8] : [
00610 0,0,0,0,0,0,0,1,1,1,
00611 1,1,1,1,2,2,2,2,2,2,
00612 2,3,3,3,3,3,3,3,4,4,
00613 4,4,4,4,4,5,5,5,5,5,
00614 5,5,6,6,6,6,6,6,6,6,
00615 7,8,9,9,10,10,11,11,11,12,
00616 12,12,12,13,13,13,13,13,13,14,
00617 14,14,15,15,15,15,15,15,16,16,
00618 17,17,17,17,17,18,18,18,18,18,
00619 18,18,19,19,19,19,19,19,19,20,
00620 21,22,23,23
00621 ]\$
00622 /* The following data has been computed by
00623    "VdWTransversalsInc 9 1 0 OutputFile":
00624 */
00625 tau_arithprog_seq[9] : [
00626 0,0,0,0,0,0,0,0,1,1,
00627 1,1,1,1,1,1,1,2,2,2,
00628 2,2,2,2,3,3,3,3,3,3,
00629 3,4,4,4,4,4,4,4,5,5,
00630 5,5,5,5,5,6,6,6,6,6,
00631 6,6,7,7,7,7,7,8,9,9,
00632 9,10,10,10,10,11,11,11,11,11,
00633 11,12,12,13,13,13,14,14,14,14,
00634 15,15,15,15,15,15,16,16,16,16,
00635 17,17,17,17,17,17,18,18,18,18,
00636 18,19,19,19,19,20,20,20,20,21,
00637 21,21,21,21,21
00638 ]\$
00639 /* The following data has been computed by
00640    "VdWTransversalsInc 10 1 0 OutputFile":
00641 */
00642 tau_arithprog_seq[10] : [
00643 0,0,0,0,0,0,0,0,0,1,
00644 1,1,1,1,1,1,1,1,2,2,
00645 2,2,2,2,2,2,2,2,3,3,
00646 3,3,3,4,4,4,4,4,4,4,
00647 5,5,5,5,5,5,5,6,6,6,
00648 6,6,6,6,7,7,7,7,7,7,
00649 7,8,8,8,9,9,9,9,10,10,
00650 10,10,10,11,11,11,11,11,12,12,
00651 12,12,12,12,13,13,13,13,14,14,
00652 14,15,15,15,15,16,16,16,16,16,
00653 17,17,17,17,17,18,18,18,18,19,
00654 19,19,19,19,19
00655 ]\$
00656 /* The following data has been computed by
00657    "VdWTransversalsInc 11 1 0 OutputFile":
00658 */
00659 tau_arithprog_seq[11] : [
00660 0,0,0,0,0,0,0,0,0,0,
00661 1,1,1,1,1,1,1,1,1,1,
00662 1,2,2,2,2,2,2,2,2,2,
00663 2,2,3,3,3,3,3,3,3,3,
00664 3,3,3,4,4,4,4,4,4,4,
00665 4,4,4,4,5,5,5,5,5,5,
00666 5,5,5,5,5,6,6,6,6,6,
00667 6,6,6,6,6,6,7,7,7,7,
00668 7,7,7,7,7,7,7,8,8,8,
00669 8,8,8,8,8,8,8,8,9,9,
00670 9,9,9,9,9,9,9,9,9,10,
00671 11,12,13,14,14,15,15,16,17,17,
00672 18,18,18,18,18,18,18,18,19,19,
00673 19
00674 ]\$
00675 /* The following data has been computed by
00676    "VdWTransversalsInc 12 1 0 OutputFile":
00677 */
00678 tau_arithprog_seq[12] : [
00679 0,0,0,0,0,0,0,0,0,0,
00680 0,1,1,1,1,1,1,1,1,1,
00681 1,1,2,2,2,2,2,2,2,2,
00682 2,2,2,3,3,3,3,3,3,3,
00683 3,3,3,3,4,4,4,4,4,4,
00684 4,4,4,4,4,5,5,5,5,5,
00685 5,5,5,5,5,5,6,6,6,6,
00686 6,6,6,6,6,6,6,7,7,7,
00687 7,7,7,7,7,7,7,7,8,8,
00688 8,8,8,8,8,8,8,8,8,9,
00689 9,9,9,9,9,9,9,9,9,9,
00690 10,10,10,10,10,10,10,10,10,10,
00691 10,10,11,12,13,14,15,15,16,17,
00692 17,17,18,18
00693 ]\$
00694 /* The following data has been computed by
00695    "VdWTransversalsInc 13 1 0 OutputFile":
00696 */
00697 tau_arithprog_seq[13] : [
00698 0,0,0,0,0,0,0,0,0,0,
00699 0,0,1,1,1,1,1,1,1,1,
00700 1,1,1,1,1,2,2,2,2,2,
00701 2,2,2,2,2,2,2,2,3,3,
00702 3,3,3,3,3,3,3,3,3,3,
00703 3,4,4,4,4,4,4,4,4,4,
00704 4,4,4,4,5,5,5,5,5,5,
00705 5,5,5,5,5,5,5,6,6,6,
00706 6,6,6,6,6,6,6,6,6,6,
00707 7,7,7,7,7,7,7,7,7,7,
00708 7,7,7,8,8,8,8,8,8,8,
00709 8,8,8,8,8,8,9,9,9,9,
00710 9,9,9,9,9,9,9,9,9,10,
00711 10,10,10,10,10,10,10,10,10,10,
00712 10,10,11,11,11,11,11,11,11,11,
00713 11,11,11,11,11,12,13,14,15,16,
00714 16,17,18
00715 ]\$
00716 /* The following data has been computed by
00717    "VdWTransversalsInc 14 1 0 OutputFile":
00718 */
00719 tau_arithprog_seq[14] : [
00720 0,0,0,0,0,0,0,0,0,0,
00721 0,0,0,1,1,1,1,1,1,1,
00722 1,1,1,1,1,1,2,2,2,2,
00723 2,2,2,2,2,2,2,2,2,3,
00724 3,3,3,3,3,3,3,3,3,3,
00725 3,3,4,4,4,4,4,4,4,4,
00726 4,4,4,4,4,5,5,5,5,5,
00727 5,5,5,5,5,5,5,5,6,6,
00728 6,6,6,6,6,6,6,6,6,6,
00729 6,7,7,7,7,7,7,7,7,7,
00730 7,7,7,7,8,8,8,8,8,8,
00731 8,8,8,8,8,8,8,9,9,9,
00732 9,9,9,9,9,9,9,9,9,9,
00733 10,10,10,10,10,10,10,10,10,10,
00734 10,10,10,11,11,11,11,11,11,11,
00735 11,11,11,11,11,11,12,12,12,12,
00736 12,12,12,12,12,12,12,12,12,12,
00737 13,14,15,16,17,18,18
00738 ]\$
00739 /* The following data has been computed by
00740    "VdWTransversalsInc 15 1 0 OutputFile":
00741 */
00742 tau_arithprog_seq[15] : [
00743 0,0,0,0,0,0,0,0,0,0,
00744 0,0,0,0,1,1,1,1,1,1,
00745 1,1,1,1,1,1,1,1,1,2,
00746 2,2,2,2,2,2,2,2,2,2,
00747 2,2,3,3,3,3,3,3,3,3,
00748 3,3,3,3,3,4,4,4,4,4,
00749 4,4,4,4,4,4,4,4,5,5,
00750 5,5,5,5,5,5,5,5,5,5,
00751 5,6,6,6,6,6,6,6,6,6,
00752 6,6,6,6,7,7,7,7,7,7,
00753 7,7,7,7,7,7,7,8,8,8,
00754 8,8,8,8,8,8,8,8,8,8,
00755 9,9,9,9,9,9,9,9,9,9,
00756 9,9,9,10,10,10,10,10,10,10,
00757 10,10,10,10,10,10,11,11,11,11,
00758 11,11,11,11,11,11,11,11,11,12,
00759 12,12,12,12,12,12,12,12,12,12,
00760 12,12,13,13,13,13,13,13,13,13,
00761 13,13,13,14,15,16,16,17,18
00762 ]\$
00763
00764 /* Alternative representations using tau-skiplists
00765    (the list contains the last entry where tau=0, 1, ...).
00766 */
00767 /* The following data has been computed by
00768    "VdWTransversalsInc 16 1 0 VDW_16 VDW_16_SAT", and then using
00770 */
00771 tau_steplist_arithprog_seq[16] : [
00772  15,30,46,57,70,83,96,109,122,135,
00773  148,161,174,187,196,198,199,201
00774 ]\$
00775 tau_arithprog_seq[16] : transform_threshold_l(tau_steplist_arithprog_seq[16])\$
00776 /* The following data has been computed by
00777    "VdWTransversalsInc 17 1 0 VDW_17 VDW_17_SAT", and then using
00779 */
00780 tau_steplist_arithprog_seq[17] : [
00781  16,33,50,67,84,101,118,135,152,169,
00782  186,203,220,237,254,271,272,273,274,275,
00783  276
00784 ]\$
00785 tau_arithprog_seq[17] : transform_threshold_l(tau_steplist_arithprog_seq[17])\$
00786 /* The following data has been computed by
00787    "VdWTransversalsInc 18 1 0 VDW_18 VDW_18_SAT", and then using
00789 */
00790 tau_steplist_arithprog_seq[18] : [
00791  17,34,51,68,85,102,119,136,153,170,
00792  187,204,221,238,255,272,290,291,292,293,
00793  294
00794 ]\$
00795 tau_arithprog_seq[18] : transform_threshold_l(tau_steplist_arithprog_seq[18])\$
00796 /* The following data has been computed by
00797    "VdWTransversalsInc 19 1 0 VDW_19 VDW_19_SAT", and then using
00799 */
00800 tau_steplist_arithprog_seq[19] : [
00801  18,37,56,75,94,113,132,151,170,189,
00802  208,227,246,265,284,303,322,341,342,343,
00803  344,345,346
00804 ]\$
00805 tau_arithprog_seq[19] : transform_threshold_l(tau_steplist_arithprog_seq[19])\$
00806 /* The following data has been computed by
00807    "VdWTransversalsInc 20 1 0 VDW_20 VDW_20_SAT", and then using
00809 */
00810 tau_steplist_arithprog_seq[20] : [
00811  19,38,57,76,95,114,133,152,171,190,
00812  209,228,247,266,285,304,323,342,362,363,
00813  364,365,366
00814 ]\$
00815 tau_arithprog_seq[20] : transform_threshold_l(tau_steplist_arithprog_seq[20])\$
00816 /* The following data has been computed by
00817    "VdWTransversalsInc 21 1 0 VDW_21 VDW_21_SAT", and then using
00819 */
00820 tau_steplist_arithprog_seq[21] : [
00821  20,41,60,79,98,117,136,155,174,193,
00822  212,231,250,269,288,307,326,345,364,381,
00823  382,383,384
00824 ]\$
00825 tau_arithprog_seq[21] : transform_threshold_l(tau_steplist_arithprog_seq[21])\$
00826 /* The following data has been computed by
00827    "VdWTransversalsInc 22 1 0 VDW_22 VDW_22_SAT", and then using
00829 */
00830 tau_steplist_arithprog_seq[22] : [
00831  21,42,64,81,100,119,138,157,176,195,
00832  214,233,252,271,290,309,328,347,366,385,
00833  400,401,403
00834 ]\$
00835 tau_arithprog_seq[22] : transform_threshold_l(tau_steplist_arithprog_seq[22])\$
00836
00837
00838 /* Alternative data for transversal numbers, given as "steplists" of
00839    independence numbers, that is, the entry for index i (starting with 1)
00840    is the first n such that the independence number is i.
00841    From such a steplist L one obtains the initial list of independence numbers,
00842    starting with n=0, via transform_threshold_l(L).
00843 */
00844
00845 /* Data from Bestk3.txt, taken from
00846    http://www.math.uni.wroc.pl/~jwr/non-ave.htm:
00847 */
00848 alpha_steplist_arithprog_seq[3] : [
00849 1,2,4,5,9,11,13,14,20,24,
00850 26,30,32,36,40,41,51,54,58,63,
00851 71,74,82,84,92,95,100,104,111,114,
00852 121,122,137,145,150,157,163,165,169,174,
00853 194
00854 ]\$
00855
00856 /* Letting tau_arithprog_seq[k] be the larger of the two alternatives: */
00857 block([A : alphastep2tau(alpha_steplist_arithprog_seq[3])],
00858  if length(A) > length(tau_arithprog_seq[3]) then
00859    tau_arithprog_seq[3] : A)\$
00860
00861
00862 /* For n <= exactv_tau_arithprog(k) we have stored exact values
00863    in tau_arithprog_seq[k]: */
00864 exactv_tau_arithprog(k) :=
00865  if k<=2 or k > exactk_tau_arithprog then 0
00866  else length(tau_arithprog_seq[k])\$
00867
00868
00869 /* Exact (trivial) formulas (returns unknown if no exact formula applies;
00870    for natural numbers k, n): */
00871 exactf_tau_arithprog(k,n) :=
00872  if n < k then 0
00873  elseif k=1 then n
00874  elseif k=2 then n-1
00875  elseif n <= 2*k-1 and evenp(k) then
00876    if n = 2*k-1 then 2 else 1
00877  elseif n <= 2*k and oddp(k) then
00878    if n = 2*k then 2 else 1
00879  else unknown\$
00880 /* The following inclusion enables simplification of for example
00881     exactf_tau_arithprog(k,n):
00882 */
00883 oklib_plain_include(boolsimp)\$
00884
00885
00886 /* The pair of nearest n-value downward and its transversal-value where we have
00887    exact values stored (using only stored *transversal-values* besides the
00888    trivial formulas).
00889    Prerequisite: The exact formulas don't apply (directly).
00890 */
00891 nearest_tau_arithprog(k,n) := block([maxn : exactv_tau_arithprog(k)],
00892   if n <= maxn then return([n, tau_arithprog_seq[k][n]])
00893   elseif maxn > 0 then return([maxn, tau_arithprog_seq[k][maxn]])
00894   elseif evenp(k) then return([2*k-1,2])
00895   else return([2*k,2]))\$
00896
00897 /* The best known values (using only stored transversal-values): */
00898 /* Prerequisites: k, n natural numbers >= 1 */
00899 tau_arithprog(k,n) := block([e : exactf_tau_arithprog(k,n)],
00900  if e#unknown then return(e),
00901  block([nn,v],
00902    [nn,v] : nearest_tau_arithprog(k,n),
00903    if nn=n then return(v)
00904    else return([v, (n - nn) + v])))\$
00905
00906
00907 /* *********************************
00908    * Analysing transversal numbers *
00909    *********************************
00910 */
00911
00912 /* The independence numbers (for natural numbers k, n; also known as r_k(n)):
00913 */
00914 alpha_arithprog(k,n) := block([t : tau_arithprog(k,n)],
00915  if listp(t) then return(reverse(n-t)) else return(n-t))\$
00916 /* The list of all known values (from n=1, as long as there are no gaps, and
00917    using only the stored transversal-numbers) for k >= 3: */
00918 alphal_arithprog(k) := if k > exactk_tau_arithprog then []
00919  else alphatau_l(tau_arithprog_seq[k])\$
00920
00921 /* The relative transversal number (for natural numbers k, n): */
00922 rtau_arithprog(k,n) := tau_arithprog(k,n) / n\$
00923 /* The relative independence number (for natural numbers k, n): */
00924 ralpha_arithprog(k,n) := alpha_arithprog(k,n) / n\$
00925 /* The list of all known values (from n=1, as long as there are no gaps, and
00926    using only the stored transversal-numbers) for k >= 3: */
00927 ralphal_arithprog(k) := if k > exactk_tau_arithprog then []
00928  else block([L : tau_arithprog_seq[k], N],
00929   N : create_list(i,i,1,length(L)),
00930   return((N - L) / N))\$
00931
00932 /* Analysing the list of ratios of alpha-values */
00933
00934 /* Plotting the alpha-ratios (k >= 3): */
00935 plot_ralpha_arithprog(k) := block([L : ralphal_arithprog(k)],
00936   if not emptyp(L) then
00937     plot2d([discrete, create_list(i,i,1,length(L)), L]))\$
00938
00939 /* "Approximating" the index n such that for all n' >= n we have
00940    alpha(arithprog_hg(k,n))/n < 1/q by considering ralphal_arithprog.
00941    Prerequisites: k, q natural numbers, k, q >= 1.
00942    "cr" stands for "convergence ratio".
00943 */
00944 approx_cralpha_arithprog(k,q) :=
00945  if k=1 then 1
00946  elseif k=2 then q+1 else block([L, i],
00947   L : ralphal_arithprog(k),
00948   i : find_last_l(lambda([x],is(x >= 1/q)), L),
00949   if i=minf then return(inf-1) else (
00950     i : i+1,
00951     if i>length(L) then return(inf-1) else return(i)))\$
00952
00953 /* The "approximated" upper bound on vanderwaerdend(m,k) given by
00954    approx_cralpha_arithprog (if this value is exact, then the upper
00955    bounds holds true).
00956    Prerequisites: m, k natural numbers >= 1.
00957 */
00958 upper_vanderwaerdend_approxcralpha(m,k) :=
00959  approx_cralpha_arithprog(k,m)\$
00960
00961
00962 /* Transformations between the various forms of (gapless, initial)
00963    sequences of numbers
00964 */
00965
00966 /* The initial sequence of transversal vdW-numbers for progression-length k
00967    (as far as there are stored tau-values; the number m of 2's starts with 0).
00968    If no sequence is stored, then m <= k-1 is considered.
00969    k natural number >= 0.
00970 */
00971 initial_sequence_vdWt(k) :=
00972   create_list(vanderwaerdent(m,k),m,0,last(tau_arithprog_seq[k])-1);
00973
00974 /* The subsequence of initial_sequence_vdWt(k) given by the precise
00975    LRC-formula, extended as far as possibly correct results seem to
00976    be produced, plus one more entry (while the guaranteed entries are
00977    those with m <= k-2, where in case of a pair-value this means (as
00978    usual) a pair of bounds):
00979 */
00980 initial_sequence_vdWt_lrc(k) :=
00981   create_list(vanderwaerdent_lrc(m,k),m,0,if k=3 then 3+1 elseif evenp(k) then k-2+1 else k-1+1);
00982
00983
00984 /* Considering the question, how small the coefficient gamma in
00985    vdW_{m+1}(2,...,2,k) <= gamma * (m+1)
00986    can be if m is big enough (we know by Szemeredi that gamma can be
00987    arbitrarily close to 1 if m is big enough, and the question is about
00988    precise numerical knowledge).
00989 */
00990 /* Motivated by [Khodkar, Landman, INTEGERS, 2007], evaluating for each k the
00991    best possible gamma given the data we have, when considering only m >= k
00992    (returning the list of pairs [k,gamma]):
00993 */
00994 bestgamma_vdWt() := block([res : []],
00995  for k : 3 thru exactk_tau_arithprog do block(
00996   [L : initial_sequence_vdWt(k)],
00997    if length(L) <= k then res : cons([k,unknown], res)
00998    else res : cons([k,lmax(rest(L,k)/create_list(m+1,m,k,length(L)-1))], res)
00999  ),
01000  reverse(res))\$
01001 /* For a list A as returned by bestgamma_vdWt(), plot the values k-1 minus
01002    these gamma-values (where pairs with unknown gamma-values are removed):
01003 */
01004 show_bestgamma_vdWt(A) := block(
01005  [B : sublist(A,lambda([p],is(second(p)#unknown)))],
01006   plot2d(
01007    [discrete,
01008     map(lambda([p], [first(p), (first(p)-1)-second(p)]), B)],
01009    [x,first(first(B))-1,first(last(B))+1],
01010    [style,[linespoints,1,5]],
01011    [xlabel, "k"],
01012    [ylabel, "gamma"]))\$
01013 /* By [Khodkar, Landman, INTEGERS, 2007] it is known that if for
01014    3/2*k - 5/2 <= m <= 2*k we have vdw_{m+1}(2,...,2,k) <= (k-1)*(m+1),
01015    then this upper bounds actually holds for all m >= k.
01016    For all k for which we might have values this condition is now
01017    checked, and the list of pairs [k, evaluation_result] is retured:
01018 */
01019 condition_kl_vdWt() := block([res : []],
01020  for k : 3 thru exactk_tau_arithprog do block(
01021   [begin : ceiling(3/2*(k-1))-1, end : 2*k, eval_res : true],
01022    for m : begin thru end unless eval_res#true do block(
01023     [t : vanderwaerdent(m,k)],
01024      if t=unknown then eval_res : unknown
01025      else if t > (k-1)*(m+1) then eval_res : false
01026    ),
01027    res : cons([k,eval_res],res)
01028  ),
01029  reverse(res))\$
01030
01031
```