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: