GreenTaoProblems.hpp File Reference

Plans for Maxima-generators related to Green-Tao problems. More...

Go to the source code of this file.

Detailed Description

Plans for Maxima-generators related to Green-Tao problems.

  • As we have it now in output_vanderwaerden, standardisation for all non-standardised clause-sets should be done explicitly.
  • 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.
Statistics output for Green-Tao problems in the Dimacs-file
  • Care needs to be taken that these measurements are not too inefficient --- currently they are.
    1. One bottleneck is standardisation, which could be done here more efficient by using arrays (instead of hash-tables).
    2. And also the statistics regarding variable and literal degrees could be computed more efficiently by using arrays, since here we have standardised clause-sets.
  • If different progression-lengths 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 clause-set 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 Green-Tao 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.
Symmetry breaking for GT-problems
  • For a progression-length 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 non-prime 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 "max-degree symmetry breaking".
  • The only experiments yet to see a potential difference between simple and max-degree symmetry breaking ist greentao_3(3,4,4) (see RamseyTheory/GreenTaoProblems/plans/GreenTao_3-3-4-k.hpp).
Arithmetic progressions for prime numbers
  • The following needs to go into the docus:
    1. The theorem of Green-Tao: "When partitioning the set of prime numbers into m parts, then at least one part contains arithmetic progressions of arbitrary lengths".
    2. 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.
    3. The corresponding numbers are "Green-Tao numbers", greentao(m,k).
    4. One should have greentao(m,k) >= vanderwaerden(m,k).
  • DONE We should create a function "greentao2_fcs(k,n)".
    1. Via primes_first(n) we get the first n prime numbers.
    2. 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.