Project of Andreas Weiermann

If anybody wants to join - students are welcome -, please let me know. I plan to built a group of approximately ten (to start with) collaborateurs. In particular I would like to integrate a mathematical physicist. There seem to be analogues of renormalizationand universality in this new branch of logic.

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.