Phase transitions in Logic and Combinatorics

Project of Andreas Weiermann

Generous support by DFG (projects We 2178-2,We 2178-3, We 2178-4, We 2178-5,We 2178-6) and NWO (project 613.080.000) is hereby acknowledged. Gyesik Lee's 2005 DFG funded dissertation emerged from the project.

A first selection of project relevant papers:

paper 1, appeared in MDMV 2005.
paper 2 appeared in APAL 2005.
paper 3 appeared in the Proceedings of the MSJ meeting in Okayama 2005. That contribution is an extended version of the paper 1 in German.
paper 4 is accepted for MSCS. It contains the sharpest threshold for subrecursive hierarchies which can be found in the literature.
paper 5 appeared in the JSL. It contains the sharp threshold for Kruskal's theorem and epsilon_0. This paper has been crucial for the genesis of the project.
paper 6 appeared in the Proceedings of the AMS. It contains the sharp threshold for the Paris Harrington theorem.
paper 7 is not yet submitted. It contains the sharp phase transition for the Hydra game and the Goodstein sequences. Some polishing will be incorporated.

paper 8 appeared in DMTCS. It covers a phase transition for Ackermannian functions using Karamata theory and Hardy Ramanujan stuff.

paper 9 appeared in DMTCS. It covers Tauberian methods for exponential codings.

paper 10 will appear in the proceedings of CIE 2006.

paper 11 (joint with Arnoud den Boer)  will appear in the local proceedings of CIE 2006. Missing details can be found on the dvi.file provided on my homepage.

paper 12 (joint with Lorenzo Carlucci and Gyesik Lee)is submitted to TAMS.

paper 13 (joint with Eran Omri)is submitted to APAL.

paper 14 presented at Horizons of Truth 2006 and will appear in the proceedings.

paper 15 joint with Menagem Kojman, Gyesik Lee and Eran Omri. JCTA (in press)

paper 16 joint with Patrick Dehornoy and Lorenzo Carlucci is submitted.

paper 17 joint with Florian Pelupessy (accepted for CiE 2008).

paper 18 joint with Michiel de Smet (accepted for CiE 2008).

paper 19 joint with Wim van Hoof (submitted).

General outline of the project (from 2006):

Phase transition phenomena are ubiquitous in a wide variety of branches of mathematics and neighbouring sciences, in particular, physics and computing. An informal description of a `phase transition effect' is the effect behaviour wherein `small' changes in certain parameters of a system occasion dramatic shifts in some globally observed behaviour of the system, such shifts being marked by a `sharp threshold point'. An everyday life example of this is the change from one material state to a different one as temperature in increased, with the `threshold' being given by melting/boiling point. Similar phenomena occur in mathematical and computational contexts like evolutionary graph theory,percolation theory, computational complexity theory and artificial intelligence. For example there is an unexpected `jump' of the size of the largest component which occurs in the random graph with n vertices when it has about n/2 edges. The purpose of PTLC is to study Phase Transitions in Logic and Combinatorics. We are, e.g., interested in the transition from provability to unprovability of a given assertion by varying a threshold parameter. Thereby we hope to obtain further understanding of difficult open problems in asymptotic Ramsey theory. The goal of PTLC is to bring together researchers in the area of logic, combinatorics, and computer science to obtain substantial advances in this new interdisciplinary line of research by cross fertilization. In order to meet this challenge PTLC innovatively aims at bridging the gap between disparate areas of research: analytic combinatorics, proof theory, and Ramsey theory. There are serious reasons to believe that we are able to provide substantial advances in the near future. The PI established some years ago the extremely sharp phase transition for Kruskal's tree theorem by combining analytic combinatorics with subrecursive hierarchies Since then he opened up new research lines in a series of papers (all which have been published or accepted for publication in highly ranked journals) and obtained new results in proof theory, number theory, analytic combinatorics, and Tauberian theory. However, the field still offers a great many intriguing challenges of varying degrees of difficulty, that it seems ideal as a research topic for a sufficiently large team of experienced researchers, PhD students, and graduate and undergraduate students with interests in logic, combinatorics, computer science, number theory, algebra and probability theory.

A: Description of the proposed research

Phase transition phenomena are ubiquitous in a wide variety of branches of mathematics and neighbouring sciences, in particular, physics and computing. An informal description of a `phase transition effect' is the effect behaviour wherein `small' changes in certain parameters of a system occasion dramatic shifts in some globally observed behaviour of the system, such shifts being marked by a `sharp threshold point'. An everyday life example of this is the change from one material state to a different one as temperature in increased, with the `threshold' being given by melting/boiling point. Similar phenomena occur in mathematical and computational contexts like evolutionary graph theory,percolation theory, computational complexity theory and artificial intelligence. For example there is an unexpected `jump' of the size of the largest component which occurs in the random graph with n vertices when it has about n/2 edges. The purpose of PTLC is to study Phase Transitions in Logic and Combinatorics. We are, e.g., interested in the transition from provability to unprovability of a given assertion by varying a threshold parameter. Thereby we hope to obtain further understanding of difficult open problems in asymptotic Ramsey theory. Phase transition phenomena appeared historically first in random settings and in statistical physics, subjects which have been considered completely separated from foundational sciences like mathematical logic and proof theory in particular. It has therefore been a great surprise when methods from analytic combinatorics could be applied by the principal investigator (PI) to obtain phase transition classifications for independence results in logic. Moreover he showed how to obtain back transfer results from logic to finite combinatorics. The goal of PTLC is to bring together researchers in the area of logic, combinatorics, and computer science to obtain substantial advances in this new interdisciplinary line of research by cross fertilization. In order to meet this challenge PTLC innovatively aims at bridging the gap between disparate areas of research: analytic combinatorics, proof theory, and Ramsey theory. There are serious reasons to believe that we are able to provide substantial advances in the near future. The PI established some years ago the extremely sharp phase transition for Kruskal's tree theorem by combining analytic combinatorics with subrecursive hierarchies Since then he opened up new research lines in a series of papers (all which have been published or accepted for publication in highly ranked journals) and obtained new results in proof theory, number theory, analytic combinatorics, and Tauberian theory. However, the field still offers a great many intriguing challenges of varying degrees of difficulty, that it seems ideal as a research topic for a sufficiently large team of experienced researchers, PhD students, and graduate and undergraduate students with interests in logic, combinatorics, computer science, number theory, algebra and probability theory.

Technological and socio-economic reasons.

In today's innovation driven world, learning and the command of knowledge have become key factors for international competitiveness. Economic growth relies to a great extent on new and better knowledge. PTLC strengthens the Duch scientific competitiveness through knowledge generation in analytic combinatorics, Ramsey theory and proof theory. PTLC integrates complementary efforts of separated research infrastructures to build a unique centre of excellence for research in exact sciences. It exploits opportunities offered by already existing research infrastructures thereby exploiting and materializing investments in this area. In a wider context PTLC puts emphasis on imparting technical, technological, and communication skills and the ability to learn and teach. Thus PTLC serves as a long term catalyst to improve the Dutch learning infrastructure and participating scientists will have very good chances for a good academic or industrial career.

Timeliness

The research area of PTLC and the advanced methods available constitute a unique combination of facilities ripe for a rich yield of collaborative studies. This will prime the Netherlands for ambitious future research in computer science, mathematics and the foundations of mathematics.

B: State of the art

The origin of independence results goes back to K. Goedel who proved in 1931 that there are statements about the natural numbers that can neither be deduced nor refuted from the Peano axioms. Since then logicians have been searching for mathematically relevant examples of true statements about the natural numbers which do not follow from the Peano axioms. The break through was obtained by J. Paris and L. Harrington. They showed that a variant of the finite Ramsey theorem is unprovable in PA. Quite recently, a classification of the underlying phase transition for hypergraphs of unbounded dimension has been obtained by the team leader. Analytic combinatorics concerns the enumeration of combinatorial structures using tools from analysis and probability theory. Its current state of the art is nicely presented in Flajolet's and Sedgewick's online book on analytic combinatorics. Ramsey theory is the mathematical study of combinatorial objects in which a certain degree of order must occur as the scale of the object becomes large. The state of the art is documented in the classic book by Graham, Rothschild and Spencer. Recent progress on Ramsey theory relevant to the proposal objectives has been made in 2004 and 2005 during NWO funded research workshops in joint research of the PI with L. Carlucci, G. Lee, and Andrey Bovykin. Project objectives and research methods PTLC will cross-fertilize proof theory, Ramsey theory and analytic combinatorics to study phase transitions. These objectives will usually be achieved in three steps. Step one is to classify asymptotically the number of relevant combinatorial objects, e.g. ordinal terms of a given size, using the generating function methodology or other tools from combinatorics. Step two is to relate natural classes of combinatorial objects on the side of logic to independence results. The interdisciplinary step three is to introduce an order parameter and to classify the threshold for the transition from provability to unprovability or from slow to fast growingness of functions under consideration. The NWO funded the phase transition project in 2006 with a visitors grant for Prof. Dr. Lev Gordeev. Moreover there will be in 2006 a miniworkshop in Oberwolfach where phase transitions in logic and combinatorics play a crucial role.