OKlibrary  0.2.1.6
Hindman.hpp File Reference

Plans regarding hypergraphs generators related to Hindman's theorems and conjectures. More...

Go to the source code of this file.


Detailed Description

Plans regarding hypergraphs generators related to Hindman's theorems and conjectures.

Todo:
Implement iterator-forms
  • Implement the form of a hypergraph generator, where not the hyperedges are produced, but just a "range" (in the C++ sense) is computed, where then iterators are used to create the hyperedges one after another.
  • Using the general concepts in ComputerAlgebra/AbstractDataTypes/Lisp/plans/general.hpp we have the following natural implementation of a forward iterator:
    hindman_a1k2_ohg_ver(n) := create_list(i,i,1,n)$
    hindman_a1k2_ohg_hypit(n) := if n<=1 then [done] else
     buildq([n,s:floor(sqrt(n))], 
     [1,
      lambda([it], block([x:it[4], y:it[5]], {x,y,x+y,x*y})),
      lambda([it], block([x:it[4], y:it[5]],
       it[1] : it[1]+1,
       if x=1 then
         if y < n-1 then it[5]:y+1
         elseif s=1 then it[1]:done
         else (it[4]:2, it[5]:2)
       elseif y+1<=n/x then it[5]:y+1
       elseif x<s then (it[4]:x+1, it[5]:x+1)
       else it[1]:done)),
      1,1])$
       
Todo:
Implement general functionality (arbitrary k)
  • hindman_ohg_0(a,k,n) and hindmani_ohg_0(a,k,n) need to improved.
  • Not all tuples [x_1, ..., x_k] have their sums and products in {1, ..., n} --- actually most won't.
    1. Perhaps we solve first the problem with "all products" (only; see 'Implement "all products"' below), since except of trivial cases the product dominates the sum.
    2. And then we add the summands to the hyperedges, filtering out the unsuitable ones.
  • stable_unique is rather slow.
  • DONE (achieved by all_ord_tuples) We need a function producing all tuples [x_1, ..., x_k] over {1, ..., m} with x_1 <= ... <= x_k (while x_1 < ... < x_k is obtained by computing all k-subsets and listifying the result).
    1. Simplest is to compute all k-tuples, and then to sort the results.
    2. This is obtained by setify(map(sort,all_tuples_l(setn(m),k))).
    3. This is wasteful, but a simple solution, and it yields the canonical order.
  • DONE A simple first implementation ignores all efficiency considerations.
    1. First a "generic" hyperedge is constructed, e.g. for k=3 the hyperedge {x1,x2,x3,x1+x2,x1+x3,x2+x3,x1+x2+x3,x1*x2,x1*x3,x2*x3,x1*x2*x3}.
    2. This is likely best achieved as a union of the sums-only and the products-only case:
      union(
        map(sum_l,map(listify,disjoin({},powerset({x1,x2,x3})))),
        map(prod_l,map(listify,disjoin({},powerset({x1,x2,x3}))))
      );
        {x1,x2,x1*x2,x2+x1,x3,x1*x3,x3+x1,x2*x3,x3+x2,x1*x2*x3,x3+x2+x1}
           
    3. Then [x1,x2,x3] runs through all possibilities, and the substitution is performed.
Todo:
Implement "all products"
  • As with Folkman-hypergraphs, but now using "all products" instead of "all sums".

Definition in file Hindman.hpp.