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.

Connections to other modules
General organisation
  • We have several, redundant sources for vdW-numbers: it seems best to actually use them, since they provide additional certificates.
Improving exactf_tau_arithprog
  • DONE (package boolsimp does this job) How do we get Maxima to evaluate simple terms?
     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" ?!
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.
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
    we get
    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.
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] : [
  • 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),
      map(lb,create_list(i,i,1,60)) - tau_arithprog_seq[3];
    • 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) := 
      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:
    • 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.
      (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.