GreenTaoProblems.hpp File Reference

Plans on the module on computing Green-Tao numbers (and related quantities) More...

Go to the source code of this file.

Detailed Description

Plans on the module on computing Green-Tao numbers (and related quantities)

Generator for Green-Tao 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 clause-set.
  • DONE The hypergraph can be output as a positive clause-set, in DIMACS format, into a file.
  • From OKlib/Satisfiability/Transformers we get the tools for standardising the names.
    1. 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.
    2. This problem needs to be fixed at Maxima/Lisp level, and here supported.
    3. For boolean problems there aren't any choices (except of the symmetry-breaking unit-clause).
    4. But for the non-boolean problems we might consider different translations from non-boolean to boolean problems.
    5. And the special case of progression-length 2 could be handled differently.
  • Perhaps the number-theoretical tools should go to OKlib/Structures/NumberTheory.
    1. Enumerating the primes:
      1. 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).
      2. Optionally, if one of the randomised tests is not secure, then the whole computation is checked via a simple sieve of Erathostenes.
      3. But we should ask the Gmp-people(?), 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 clause-sets); see below.
Statistics on the number of arithmetic progressions
  • A simple application is needed, which for inputs k, n prints in R-format 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 range-transformations 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".
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 Maxima-specifications 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.