Ebook: Physics and Theoretical Computer Science

As a part of the NATO Security Through Science Programme, the goal of the Advanced Study Institute Physics and Computer Science was to reinforce the interface between physical sciences, theoretical computer science, and discrete mathematics.

No one can dispute the current importance of applied as well as theoretical Computer Science in the development and the practice of Physical Sciences. Physicists of course use computers in communication as well as in teaching tasks and research: software for symbolic calculus, data processing, programming, modeling and numerical simulations, learning and teaching with the aid of computers…

On the other hand, and besides the fundamental role played by mathematics in physics, methods imported from computer science are of increasing importance in theoretical physics: algorithmics, symbolic calculus, non-standard numeration systems, algebraic combinatorics, automata, cryptography… Some of them, like numeration, tilings and their associated dynamical systems, algebraic combinatorics, have already played an important role in recent developments in physics, like those accompanying the emergence of new materials (e.g. quasicrystals, uncommensurate structures) or the research around quantum information and cryptography (entanglement), or yet around quantum spin systems and related questions of integrability, and more generally in statistical physics. The intersection of combinatorics and statistical physics has been an area of great activity over the past few years, fertilized by an exchange not only of techniques but of objectives. Spurred by computing theoreticians interested in approximation algorithms, statistical physicists and discrete mathematicians have overcome language problems and found a wealth of common ground in probabilistic and algebraic combinatorics. Close connections between percolation and random graphs, between graph morphisms and hard-constraint models, and between slow mixing and phase transition have led to new results and new perspectives. These connections can help in understanding typical, as opposed to extremal, behavior of combinatorial phenomena such as graph coloring and homomorphisms. Some of the topics of particular interest are: percolation, random coloring, mixing, homomorphisms from and to fixed graph, phase transitions, threshold phenomena.

Hence, this NATO ASI School was aimed at assembling theoretical physicists and specialists of theoretical informatics and discrete mathematics in order to learn more about recent developments in cryptography, algorithmics, symbolic calculus, non-standard numeration systems, algebraic combinatorics, automata …which could reveal themselves to be of crucial interest in natural sciences. In turn, the School offered specialists in statistical physics or dynamical systems or in quantum information and quantum cryptography, or yet in new materials (e.g. quasicrystals, uncommensurate structures), the opportunity to describe aspects of their research in which new approaches imported from computer science are particularly needed.

Therefore, nearly 70 participants (students + lecturers + organizers), coming from 20 different countries (actually more than 25 nationalities), most of them being PhD students or in post-doctoral positions working in various fields, have attended courses given by 16 specialists in algorithmics, numeration systems, algebraic combinatorics, automata, languages, cryptography, quantum information, graphs and statistical mechanics.

Generally, the lectures have been introductory and pedagogical. They perfectly complied with the objective of a real transmission of knowledge between the various communities attending the Institute.

During the ten working days of the School, a total of 40 hours was reserved for lectures, and two half days were devoted to short presentations (30 or 45 min) mainly by young researchers and PhD participants. Around 35 participants presented their own research on posters displayed during the whole duration of the School. The list ofparticipants is given in the annex of this book.

Three Lectures and one concert were organized with the support of the Institut Scientifique de Cargèse:

• Roman OPALKA, Artist, France, Poland, The River of Time,

• Pierre SIMONNET, Université de Corse, Automata and games,

• Jaroslav NEŠETŘIL and Xavier VIENNOT, Arbres et Formes, Art et Mathématiques,

• Maria COLOMÉ (flute) and Jean-Yves THIBON (piano): Sonate, F. Poulenc, Sonate en si mineur, J.S. Bach.

They were aimed to attract a wide audience from Cargèse region. Moreover, the pupils of the Cargèse primary school enjoyed two pedagogical and playful presentations of the combinatorics of trees.

During the last auditorium meeting, the participants discussed important question of the relations, on a pedagogical as well as institutional level, between physics and computer science in higher education.

This volume is organized along the following rough thematic divisions:

• Physics,

• Chaos and Fractals,

• Quasi-Crystals and Tilings,

• Numeration, Automata, and Languages,

• Algebraic Combinatorics,

• Graphs and Networks.

Acknowledgements

This NATO-ASI “PHYSICS AND COMPUTER SCIENCE” has also been supported by l'ITI-DIMATIA, Charles University, Prague, the Collectivité Territoriale de Corse (Corsica Region), the French Ministry of Foreign Affairs, the University of Marne-La-Vallée and the GDR 673 (CNRS) “Algorithmique, Langage et Programmation”.

Jean-Pierre Gazeau, Jaroslav Nešetřil, and Branislav Rovan, Co-directors of the Advanced Study Institute Physics and Computer Science

In this chapter we give a brief, self-contained introduction to quantum information theory, which is the theory of information processing using systems that obey the laws of quantum mechanics. These processing systems exploit the purely quantum effect of entanglement as a novel resource, and we give a short overview of entanglement and its characterisations. The stress here is on the mathematical framework, rather than on the physical or engineering aspects.

In these lectures I explain a connection between geometric invariant theory and entanglement, and give a number of examples how this approach works.

This is a very brief introduction to the theory of phase transitions. Only few topics are chosen with a view on possible connection with discrete mathematics. Cluster expansion theorem is presented with a full proof. Finite-size asymptotics and locations of zeros of partition functions are discussed among its applications to simplest lattice models. A link with the study of zeros of the chromatic polynomial as well as the Lovász local lemma is mentioned.

Chaotic behavior in a deterministic dynamical system results from the interplay in state space of two geometric mechanisms, stretching and squeezing, which conspire to separate arbitrarily close trajectories while confining the dynamics to a bounded subset of state space, a strange attractor. A topological method has been designed to classify the various ways in which stretching and squeezing can organize chaotic attractors. It characterizes knots and links formed by unstable periodic orbits in the attractor and describes their topological organization with branched manifolds. Its robustness has allowed it to be successfully applied to a number of experimental systems, ranging from vibrating strings to lasers. Knotted periodic orbits can also be used as powerful indicators of chaos when their knot type is associated with positive topological entropy and thus implies mixing in state space. However, knot theory can only be applied to three-dimensional systems. Extension of this approach to higher-dimensional systems will thus require alternate formulations of the principles upon which it is builT, determinism and continuity.

This is a mathematical but non-technical survey on random fractals and random processes on deterministic fractals. We focus on important principles of self-similarity and randomness, and discuss a number of interesting examples.

The paper presents mathematical models of quasicrystals with particular attention given to cut-and-project sets. We summarize the properties of higher-dimensional quasicrystal models and then focus on the one-dimensional ones. For the description of their properties we use the methods of combinatorics on words.

Number systems in Pisot number base are discussed in relation to arithmetic construction of quasi-crystal model. One of the most important ideas is to introduce a ‘dual tiling’ of this system. This provides us a geometric way to understand the ‘algebraic structure’ of the above model as well as dynamical understanding of arithmetics algorithms.

The purpose of this survey is to present the main concepts and results in non-standard number representation, and to give some examples of practical applications. This domain lies at the interface between discrete mathematics (dynamical systems, number theory, combinatorics) and computer science (computer arithmetic, cryptography, coding theory, algorithms). It also plays an important role in the modelization of physical structures like quasicrystals.

These notes give a brief introduction to the theory of finite automata with output, called transducers, and to that end to the part of classical automata theory which is necessary. Themain results that shape the theory and give it its significance are stated, without proofs, and are illustrated with few examples, thus setting the general framework of this theory.

This article is based on a talk given to the participants of the NATO Advanced Study Institute on Physics and Computer Science. It introduces some key concepts in Computer Science intended mainly for a non specialist and illustrates them on aparticular topic of generating languages. Thesecond part, bringing results on g-systems can be of interest also to specialists.

We give asurvey of basic tools and motivations in contemporary enumerative combinatorics. We start with the classical example of binary trees and generating function of Catalan numbers and extend it to “decomposable structures”. A typical but non trivial example is given by the Schaeffer decomposition of planar maps explaining the algebricity of the corresponding generating function. Then we systematically show the correspondence between algebraic operations about formal power series (generating function) and the corresponding operations at the level of combinatorial objects (sum, product, substitution, quasi-inverse, …). A section is given about rational generating functions and a basic inversion lemma (interpreted in physics as the transition matrix methodology). We also investigate the world of q-series and q-analogues, with some example of bijective proof identities and the “bijective paradigm”. We finish with the introduction of the theory of heaps of pieces and some inversion formula as a typical example of the active domain of algebraic combinatorics, in connection with theoretical physics.

We give a short introduction to the theory of Noncommutative Symmetric Functions, including noncommutative Vieta formulae, relations with Solomon's descent algebras, quasi-symmetric functions and Hecke algebras at q=0.

The apparition of combinatorial structures like partitions, trees, graphs in algebraic computation is not new. Two famous earlier examples can be found in the formula of Cayley for integrating vector fields and the theory of Young tableaux in the representation theory of the symmetric group. The fact that combinatorial objects carry naturally some Hopf-algebraic structures has been then widely advertised by Rota. Recently, a large class of examples of very rich algebraic structures (Hopf algebra, Lambda-rings...) appeared naturally in several seemingly unrelated fields of science. One can cite, for example, renormalization of quantum electrodynamics in physics (Connes-Kreimer), category of algebra and operads in algebra (Loday), generalized symmetric functions (Gessel), and generalized generating series in combinatorics. Several of these algebras are closely related to well known algorithms of computer sciences (Schensted algorithm for computing the length of a longest increasing subsequence, Bubble-sort, search-tree insertion). The knowledge of this connection allows one for very simple proofs and very efficient algorithm for computing in these structures. The goal of this course is to present to the audience what kind of algebraic structures, namely the Hopf algebra appears naturally in these fields. In a second time, we will show on two similar examples how two of these Hopf algebras can be naturally constructed in a very efficient way starting from simple computer science algorithms.

The recent discovery that many networks associated with complex systems belong to a new category known as scale-free small-world has led to a surge in the number of new models for these systems. Many studies are based on probabilistic and statistical methods which capture well some of the basic properties of the networks. More recently, a deterministic approach has proven useful to complement and enhance the probabilistic and simulation techniques. In this paper, after a short introduction to the main concepts and models, we survey recent deterministic models.

In this paper we survey the recent results on graph homomorphisms perhaps for the first time in the broad range of their relationship to wide range applications in computer science, physics and other branches of mathematics. We illustrate this development in each area by few results.

We will be walking for some time where the connections between combinatorics and statistical physics lead us.