OKlibrary  0.2.1.6
Numbers.hpp File Reference

Plans regarding van der Waerden numbers. More...

Go to the source code of this file.


Detailed Description

Plans regarding van der Waerden numbers.

Todo:
Connections to other modules
Todo:
General organisation
  • We have several, redundant sources for vdW-numbers: it seems best to actually use them, since they provide additional certificates.
Todo:
Improving exactf_tau_arithprog
  • DONE (package boolsimp does this job) How do we get Maxima to evaluate simple terms?
    exactf_tau_arithprog(1,n);
     if n < 1 then 0 elseif 1 = 1 then n elseif 1 = 2 then n-1 elseif n <= 1 and evenp(1)
               then (if n = 1 then 2 else 1) elseif n <= 2 and oddp(1) then (if n = 2 then 2 else 1)
               else unknown
       
    --- this should yield "if n < 1 then 0 else n" ?!
Todo:
Improving initial_sequence_vdWt
  • initial_sequence_vdWt(k) should proceed until the first result returned by greentaot(m,k) appears which is not an integer.
  • The computation is very slow: greentaot(m,k) needs a more efficient algorithm.
Todo:
The LRC-formula
  • DONE (the "m" from the paper was not correctly used) Using
    testf(M,K) := 
     for m : 1 thru M do
      for k : m+2 thru K do
       block([res1 : vanderwaerdent_lrc(m,k), res2 : vanderwaerdent(m,k)],
         if not listp(res1) and res2 # unknown and res1 # res2 then
           print(m,k,res1,res2)
       )$
       
    we get
    testf(10,30);
    2 4 10 11
    4 6 18 27
    6 8 26 51
       
  • DONE (see above) So for r in {3,5,7} and for the minimal allowed k the formula is not correct. Contact the authors.
Todo:
Transversal and independence numbers
  • tau_arithprog_hg(k,n) is the transversal number of arithprog_hg(k,n), while alpha_arithprog_hg(k,n) is the independence number of arithprog_hg(k,n).
  • For fixed k, we want to easily extract the sequences tau_arithprog_hg(k,-) and alpha_arithprog_hg(k,-), and likely it's also best to specify the values by providing the known initial sequences (and potentially sporadic values).
  • Perhaps we provide the initial sequences as values of tau_arithprog_seq[k] and alpha_arithprog_seq[k] (perhaps best starting with index 1):
    tau_arithprog_seq[3] : [
    0,0,1,1,1,2,3,4,4,5,
    5,6,6,6,7,8,9,10,11,11,
    12,13,14,14,15,15,16,17,18,18,
    19,19,20,21,22,22,23,24,25,25,
    25,26,27,28,29,30,31,32,33,34,
    34,35,36,36,37,38,39,39,40,41
    ]$
       
  • Perhaps these lists are then transferred into a hash-map, which additionally contains the other "sporadic" values.
  • Methods for lower bounds on tau_arithprog_hg(k,n):
    • For natural numbers 0 <= p, q with p+q=n we have tau_arithprog_hg(k,n) >= tau_arithprog_hg(k,p) + tau_arithprog_hg(k,q).
    • This method yields for the above sequence tau_arithprog_seq[3]:
      lb(n) := block([L : tau_arithprog_seq[3], l, m:0],
       l : length(L),
       for k : max(1,n-l) thru min(n-1,l) do block(
        [v : L[k] + L[n-k]],
         if v > m then m:v),
       m)$
      map(lb,create_list(i,i,1,60)) - tau_arithprog_seq[3];
      [
      0,0,-1,0,0,0,-1,-1,0,-1,
      0,-1,0,0,0,0,-1,-1,-1,0,
      -1,-1,-1,0,-1,0,-1,-1,-1,0,
      -1,0,-1,-1,-1,0,-1,-1,-1,0,
      0,0,-1,-1,-1,-1,-1,-1,-1,-1,
      0,-1,-1,0,-1,-1,-1,0,-1,-1
      ]
           
    • At exactly the indices 15,42 do we get a non-trivial lower bound (at these places we actually have exactly one minimum-transversal before, thus the transversal number should(?) increase by one).
    • Namely, L[15] = 7 = L[12] + L[3] = L[8] + L[7], and L[42] = 26 = L[39] + L[3].
    • Otherwise the bound is trivial.
  • Methods for upper bounds on tau_arithprog_hg(k,n):
    • tau_arithprog_hg(k,n) <= n.
    • More generally, for 0 <= p <= n we have tau_arithprog_hg(k,n) <= tau_arithprog_hg(k,p) + (n - p).
    • Alternatively, for p >= 0 we have tau_arithprog_hg(k,n) <= tau_arithprog_hg(k,n+p) - tau_arithprog_hg(k,p) (from this by tau_arithprog_hg(k,n+p) <= tau_arithprog_hg(k,p)+n we obtain the upper bound n).
    • It seems that the last bound is hardly useful; so all what we get is the trivial bound that advancing one steps costs at most one.
    • For natural numbers n >= 0 and k >= 2 the following functions checks whether the base-k representation of n contains the digit k-1:
      maxdigitp(k,n) := 
       some_s(lambda([d],is(d=k-1)),int2polyadic(n,k))$
           
      while
      maxdigits(k,n) := subset(setmn(0,n-1),lambda([x],maxdigitp(k,x)))$
           
      is the set of all such numbers from 0 to n-1. The basic fact here is, that for prime numbers k, maxdigits(k,n) is a transversal of arithprog_hg(k,n), but where the vertex set is {0,...,n-1} (instead of {1,...,n}, as it is).
    • Thus
      transdig_ap(k,n) := map(lambda([x],x+1), maxdigits(k,n))$
           
      yields a transversal of arithprog_hg(k,n) for n >= 0.
    • A counter-example for non-prime k is given by transdig_ap(10,19) = {10}, which is not a transversal of arithprog_hg(10,19), since the hyperedge {1,3,5,7,9,11,13,15,17,19} is missed:
      transversal_p(transdig_ap(10,19),arithprog_hg(10,19));
       false
           
    • In other words, tau_arithprog_hg(k,n) <= ubmd(k,n)) for prime numbers k, where
      ubmd(k,n) := length(transdig_ap(k,n))$
           
    • For k=3 and n <= 60 this upper bound coincides with the above lower bound lb exactly for [1,2,4,5,6,11,13,14,15,16,40,41,42].
    • For natural numbers k and a we have ubmd(k,((k-2)*k^a+1)/(k-1)) = ((k-2)*k^a+1)/(k-1) - (k-1)^a.
    • Using
      ubmda(k,a) := block([n : ((k-2)*k^a+1)/(k-1)], [n, n-(k-1)^a])$
           
      for [n,b] = ubmda(k,a) we have tau_arithprog_hg(k,n) <= b.
    • For k=3 this yields tau_arithprog_hg(3,(3^a+1)/2) <= (3^a+1)/2 - 2^a.
      map(lambda([a],ubmda(3,a)),create_list(i,i,1,6));
       [[2,0],[5,1],[14,6],[41,25],[122,90],[365,301]]
           
      (one sees that for a <= 4 the upper bound is sharp, and coincides with the lower bound).
    • It should be possible to at least compute tau_arithprog_hg(3,122), so that we can determine whether this bound is still sharp (in general it is not).
    • But perhaps we should use the general function ubmd(k,n), and not just the computation of special values via ubmda(k,a).
  • For our stored values, we should always have that they are best relatively to the current knowledge (so that no further calculations are needed for them).

Definition in file Numbers.hpp.