Plans on the module on computing GreenTao numbers (and related quantities)
More...
Go to the source code of this file.
Detailed Description
Plans on the module on computing GreenTao numbers (and related quantities)
 Todo:
 Connections
 Todo:
 Generator for GreenTao problems

DONE (see OKlib/Combinatorics/Hypergraphs/Generators/GreenTao.cpp) We need to write a program with functionality like arithprog_primes_hg from the Maxima/Lisp level (and all the other functions there in ComputerAlgebra/Satisfiability/Lisp/Generators/RamseyTheory/GreenTaoProblems.mac).

See Experimentation/Investigations/RamseyTheory/GreenTaoProblems/plans/general.hpp for experiments.

Best we provide this functionality as Unix tools as well as at library level.

DONE Perhaps this hypergraph creation happens in OKlib/Combinatorics/Hypergraphs, while here we plug these hypergraphs together to get a clauseset.

DONE The hypergraph can be output as a positive clauseset, in DIMACS format, into a file.

From OKlib/Satisfiability/Transformers we get the tools for standardising the names.

On the other hand, there should be a standard mapping from the original variables to natural numbers, so no general tools should be used here.

This problem needs to be fixed at Maxima/Lisp level, and here supported.

For boolean problems there aren't any choices (except of the symmetrybreaking unitclause).

But for the nonboolean problems we might consider different translations from nonboolean to boolean problems.

And the special case of progressionlength 2 could be handled differently.

Perhaps the numbertheoretical tools should go to OKlib/Structures/NumberTheory.

Enumerating the primes:

Gmp has a "mpz_nextprime" function, by which we first create the complete list of primes and the corresponding boolean array (for the primality predicate).

Optionally, if one of the randomised tests is not secure, then the whole computation is checked via a simple sieve of Erathostenes.

But we should ask the Gmppeople(?), up to which prime number the results are known to be correct  likely this is big enough!

Also important to be able to compute the various statistics on arithmetical progressions of primes (without creating hypergraphs or clausesets); see below.
 Todo:
 Statistics on the number of arithmetic progressions

A simple application is needed, which for inputs k, n prints in Rformat for i from 1 to n the sizes of the hypergraphs for (k,i).

This should be based on the hypergraph computed by Generators::GreenTao, to which then a function as sizes_cstrata_indmon_ohg is applied.

So two rangetransformations are to be provided, specified by sizes_strata_indmon_ohg and accumulate_l (in ComputerAlgebra/Hypergraphs/Lisp/Stratification.mac).

Perhaps calling this application "CountProgressions_GreenTao".
 Todo:
 Computing minimum transversals

DONE Similar to Applications/RamseyTheory/plans/MinimumTransversals_VanderWaerden.cpp we need MinimumTransversals_GreenTao.cpp.

Decomposition into the connected components is needed for k>=4; see decomp_minimum_transversals_bvs_hg and minimum_transversals_decomp_gen in ComputerAlgebra/Hypergraphs/Lisp/Transversals/Bounded/MaintainingBound.mac for Maximaspecifications and simple algorithms.

And the output should report only changes, as with minimum_transversals_decomp_gen.

Application tests are needed for Applications/RamseyTheory/plans/MinimumTransversals_GreenTao.cpp.

The problem is that currently we cannot compile this application automatically, due to the build dependencies not expressible, and thus yet we cannot create application tests.

It seems that there is some unnecessary copy operation at the end: the numbers are output, but nevertheless memory consumption doubles?
Definition in file GreenTaoProblems.hpp.