Plans for Maximagenerators related to GreenTao problems.
More...
Go to the source code of this file.
Detailed Description
Plans for Maximagenerators related to GreenTao problems.
 Todo:
 Connections
 Todo:
 Standardisation

As we have it now in output_vanderwaerden, standardisation for all nonstandardised clausesets should be done explicitly.
 Todo:
 Statistics

As discussed in "Accompanying statistics" in Satisfiability/Lisp/Generators/plans/general.hpp in general, we need statistics for all main measurements (and also for all others, if possible).

First the hypergraph measurements needs to be established; see "Statistics" in Hypergraphs/Lisp/plans/Generators.hpp.
 Todo:
 Statistics output for GreenTao problems in the Dimacsfile

Care needs to be taken that these measurements are not too inefficient  currently they are.

One bottleneck is standardisation, which could be done here more efficient by using arrays (instead of hashtables).

And also the statistics regarding variable and literal degrees could be computed more efficiently by using arrays, since here we have standardised clausesets.

If different progressionlengths are involved, then for each involved hypergraph we should have data like standard_statistics_fcs.

This should happen in the hypergraph module.

The data for the whole clauseset could then be obtained by just adding up the numbers.

As discussed above in todo "Statistics", there should be specialised functions (with standardised names) for computing the "standard" statistics.

For GreenTao data this doesn't help much, since there is no faster computation than just "measuring", but we should establish (and follow) a general scheme.

DONE (the general computation now likely can't be improved much further) The computation of standard_statistics_fcs should be made much more efficient.
 Todo:
 Symmetry breaking for GTproblems

For a progressionlength k (relevant for all parts i with k_i=k) we want to use the vertex occurring most often.

Then the current implementations, which just chose prime 3 (let's call it "simple symmetry breaking"), are defective, since only for k=3 this is the right choice.

For k=2 we just have a complete graph, and so all vertices are equal.

For prime k >= 3 it seems that k itself occurs most often. This should be due to the exceptional status of k as basis of progressions of length k (their slopes doesn't need to be a multiple of product_primes(k), as it is otherwise the case).

For nonprime k >= 3 the first impression is, that the vertex with index roughly 0.42*n for k=4 and roughly 0.3*n for k=6 occurs most often; this needs to investigated.

So it seems that one needs a function at hypergraph level which for given k, n determines the vertex occurring most often.

Let's call the resulting symmetry breaking "maxdegree symmetry
breaking".

The only experiments yet to see a potential difference between simple and maxdegree symmetry breaking ist greentao_3(3,4,4) (see RamseyTheory/GreenTaoProblems/plans/GreenTao_334k.hpp).
 Todo:
 Arithmetic progressions for prime numbers

The following needs to go into the docus:

The theorem of GreenTao: "When partitioning the set of prime numbers into m parts, then at least one part contains arithmetic progressions of arbitrary lengths".

Via compactness, this should translate into the property that for m and k there is (a least) n such that for every partitioning of the first n prime numbers into m parts one of the parts contains an arithmetic progressions of length k.

The corresponding numbers are "GreenTao numbers", greentao(m,k).

One should have greentao(m,k) >= vanderwaerden(m,k).

DONE We should create a function "greentao2_fcs(k,n)".

Via primes_first(n) we get the first n prime numbers.

Finding the arithmetic progressions of length k can be done recursively.

DONE Of course, we also need the underlying hypergraphs.
Definition in file GreenTaoProblems.hpp.