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) :=
```
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.