In this project, we propose to study a large number of seemingly disjoined topics, which we have grouped together under the neologism "statistical topology", by a team of research mathematicians, physicists, and computer scientists from France and Russia. From the mathematical viewpoint, the main objects of study are one-dimensional entities embedded in space (such as knots, links, braids, tangles, ribbon graphs, meanders, plane binary trees), often randomly generated or involved in random processes. From the viewpoint of theoretical physics, they are for the most part discrete or continuous statistical models coming from a wide range of sources: not only physics, but also combinatorics, chemistry and biology. From the point of view of computer science, the classification of these objects and the computation of their invariants are computer accessible combinatorial problems to be solved by non-traditional methods, e.g. via calculations involving Hopf algebras, various ki! nds of diagrams, and non-commutative geometry, rather than integrals and differential equations.
Most, but not all, the participants come from two laboratories (the LPTMS in Orsay and the J.-V.Poncelet Laboratory in Moscow), and in many cases have a substantial experience of joint work (not only with collaborators of the same laboratory). At first glance, the list of topics studied may seen overly diversified (if not eclectic), but the project, we believe, has a strong underlying unity, provided in part by the mathematical similarity of some the models considered, but mostly by the unity of its methods.
This is not the traditional situation where a set of mathematical methods is developed by professional mathematicians and then applied to various branches of science. In our case, the methods are being developed by all the participants in the context of their specific field of interest, but turn out to be very similar. This state of affairs was confirmed recently in the conference "Geometry and Combinatorics in Physics" (Moscow, 2-7 of March, 2004), attended by many of the participants of this grant proposal. During this conference, it become obvious that its speakers (who come from different areas of science) not only understand each other but were struck by the closeness of the methods used and were able to profit from it.
Since the 1980s knot theory has been intimately connected to statistical physics. Four years ago, a new bridge was created by P.Zinn-Justin and J.-B.Zuber, who observed that Feynman diagrams of an appropriate matrix model can encode the geometry of a knot projection: indeed, knots, links, and tangles projected on the plane form four-valent graphs. The idea is then to utilise existing methods for the computation of matrix integrals to solve certain knot enumeration problems (see Zinn-Justin, Zuber, [1]).
Another fruitful line of research is related to the interpretation of higher orders in the expansion in 1/N of the matrix integrals related to knots (see Zinn-Justin [2]). This interpretation exactly corresponds to L.Kauffman's notion of virtual knots (which, roughly speaking, live on fattened higher order Riemann surfaces). Zinn-Justin and Zuber have postulated several rather technical conjectures which would imply that the topological development of the corresponding matrix integrals exactly reproduces the enumerations of alternating virtual tangles.
One may want to obtain the asymptotics (and eventually the scaling laws) for the number of objects of large size. Here the transfer matrix method has not been conclusive, and numerical simulations (using the Monte Carlo method) have been undertaken (see G.Schaeffer, P.Zinn-Justin [3]). Recently discovered bijections between decorated trees and planar maps allow to randomly generate link diagrams in linear time w.r.t. the number of crossings. The results of this simulation has led the above-mentioned authors to formulate a conjecture on the asymptotics of the number of (isotopy classes of) knots as the number of crossings tends to infinity.
Numerous extensions of these works can and will be pursued, ranging from enumeration problems in the strict sense to problems related to what may be called "probabilistic knot theory"; a first step in this latter direction was made at the end of the paper mentioned in the previous paragraph.
Growth processes are ubiquitous in nature. The past few decades have seen extensive research on a wide variety of both discrete and contiuous growth models. A large class of these growth models such as the Eden model, restricted solid on solid (RSOS) models, directed polymers, polynuclear growth models (PNG) and ballistic deposition models (BD) are believed to belong to the same universality class as that of the Kardar-Parisi-Zhang (KPZ) equation describing the growth of interface fluctuations.
This universality is, however, somewhat restricted in the sense that it refers only to the width or the second moment of the height fluctuations characterized by two independent exponents (the growth exponent β and the dynamical exponent z) andthe associated scaling function. Moreover, even this restricted universality hasbeen only established numerically in most cases. Only in very few special discrete (1+1)-D models, the exponents β=1/3 and z=3/2 can be computed exactly via the Bethe ansatz technique. A natural and important question is whether this universality can be extended beyond the second moment of height fluctuations. For example, is the full distribution of the height fluctuations (suitably scaled) universal, i.e. is it the same for different growth models belonging to the KPZ class? Moreover, the KPZ-type equations are usually attributed to models with small gradients in the height profile and the question whether the models with large gradients (such as the BD models) belong to the KPZ universality class is still open. The connection between the discrete BD models and the continuum KPZ equation has recently been elucidated.
The purpose of this part is to investigate the class of BD models that can be related to the LIS (Longest Increasing Subsequence) problem and hence could share the same Tracy-Widom distribution as the PNG model. We would like to mention the connection of our model with the so-called Ulam problem, extensively discussed in the literature in the last 5 years. The general setting of the Ulam problem is as follows. Take the unit interval [0,1] and choose from it one after another with uniform probability distribution N random numbers (N>>1). From this sequence of N random numbers, let us extract the longest increasing subsequence (the entries of this subsequence are not necessarily nearest neighbors). There are two questions of interest: (i) what is the average length of the increasing subsequence and (ii) what are the fluctuations of the mean length of this subsequence.
The first question was answered already in 1975 by A.Vershik and S.Kerov [4], who reduced the problem to the investigation of the mean length of the first line in the random Young tableau averaged over the Plancherel measure. A breakthrough treatment of fluctuations was achieved in recent works of Tracy, Deift, Johannson, Okunkov, Aldous, Spohn and Praehofer. The exact results, in combination with the results of Johansson and Spohn-Praehofer, lends support to the conjecture that perhaps all different BD-type growth models, at least in (1+1) dimensions, share the same universal Tracy-Widom distribution for scaled height. This conjecture, if true, puts the universality on a much stronger footing, going beyond the second moment. In recent contribution by S.Majumdar and S.Nechaev [5] the asymptotic distribution of scaled height in a (1+1)--dimensional anisotropic ballistic deposition model has been computed by mapping it onto the Ulam problem. The approach developed in [5] estab lished also a deep connection to another wide class of statistical problems related to so-called "directed percolation" in (2+1) dimensions studied by R.Rajesh and D.Dhar. In our project we suppose to consider the last connection in more details.
Large networks of queues in series can be represented in terms of certain directed percolation problems; these problems concern paths of maximum weight in the quadrant Z+2 with random weights at the vertices. Such problems can also be represented in terms of certain growth models: the models concern a subset of the quadrant growing randomly over time according to local interactions at its boundary. The existence of an asymptotic "throughput" for the queueing network corresponds to the existence, under appropriate scaling, of an "asymptotic shape" for the growth model. Deep and beautiful connections have been discovered in recent years between such models, random matrix theory, and certain particle systems (see, J.Mairesse [6]).
Heap models in which pieces pile up according to the "Tetris"» game mechanism are another growth model of interest. There are links with ballistic deposition models or sandpile models. In computer science, heap models are a good paradigm for the study of parallelism (pieces which commute correspond to tasks executed in parallel, and pieces which do not commute to tasks executed sequentially). The dynamic of heap models can be represented by means of iterated systems of max-plus linear maps. This enables to get a variety of qualitative properties for optimization problems, as well as for randomly growing heaps, where successive pieces are chosen randomly and independently according to some distribution (J.Mairesse, [7]). Obtaining quantitative results, for instance formulas for the rate of growth of a random heap, is a far more difficult and challenging problem, that we want to address. One direction currently investigated is to consider some related models of transient random walks on finitely generated groups, where the rate of escape to infinity can be explicitly computed.
In a recent talk, I.M.Gelfand pointed out that, in his opinion, one of the most promising branches of mathematics and its applications are noncommutative symmetric functions. In mathematical physics, one of the crucial breakthroughs of the past decades was related to results coming from what Alain Connes has called noncommutative geometry. Besides the word "noncommutative", these two fields have in common the study of the same combinatorial objects, which may be called combinatorial Hopf algebras. Among them are Loday's plane binary tree algebras, the algebras studied by Kraemer and Connes, classical and quantum noncommutative symmetric function algebras studied by Thibon, Novelli and F.Hivert (see [8]); heuristically, Feynman diagrams play the role of such an algebras. These objects have numerous applications, e.g. they yield explicit renormalization formulas for Feynman integrals in quantum electrodynamics and quantum field theory. In this connection, also see Vershinin [9].
One of the reasons we expect significant advances in this topic, is that F.Hivert, jointly with N.Thiery, has developed a very efficient software (called MuPad) for treating combinatorial objects. This software has been used with success by members of our team (S.Lando, S.Nechaev, P.Zinn-Justin, and F.Hivert himself) to perform computations in their respective areas of study.
Moreover, this software can also be applied to other "diagrammatic" algebras, e.g. to the Temperly-Lieb algebra (regarded as a combinatorial geometric object in the spirit of Chapter 8 of the Prasolov-Sossinsky book [10]. This should lead to a combinatorial version of various instances of the Jones-Witten invariants, equivalent to those coming from representation theory and quantum groups.
In connection with the state sum invariant for Wilson lines in manifolds (defined heuristically by Witten), the work of S.Matveev on Turaev-Viro invariants (a rigorous mathematical construction based on 6j-symbols) is quite significant (see Matveev [11]). Matveev's version of these invariants is purely topological and is a kind of Kirby calculus (see Chapter 3 of the Sossinsky-Prasolov book [10] with the so-called Matveev-Petronio move playing the role of the Fenn-Rourke move), and it has allowed him and his collaborators to develop a software package performing effective computations of these invariants. The question that will be addressed here is to find the relationship between Matveev's approach and physics: it appears to be a kind of duality, with the Matveev-Petronio move dual to a move studied by L.Chekhov and others in statistical physics.
Research on knots and braids will be concentrated on the study of knot and braid invariants and related invariants of graphs. A rich class of graph invariants producing invariants of knots, of finite order (Vassiliev invariants), has been introduced in S.Lando [12]. It is a graph counterpart of the finite order invariants of knots. It contains many important graph invariants, and its appearance clarified their origins. The structure of this class is simpler than the structure of the class of finite order knot invariants, and it presumably admits a complete and efficient description. The underlying algebraic structures of the corresponding Hopf algebras also are of great importance. Some quantum invariants of knots and braids are known to be pushed forward to graphs. We are planning to look for a complete description of all such quantum invariants of graphs. Strong hopes are for constructing the theory of complex invariants of finite order, complexifying the Vassiliev theory.
Another important application of braids is the braid group action on the spaces of meromorphic functions by braiding of the critical values of the function. This action leads to the topological classification of meromorphic functions (see S.Lando [13]). The latter is very closely related to the theory of Gromov-Witten invariants of complex manifolds and quantum cohomology. One can hope that there is a relationship between quantum cohomology of manifolds and quantum invariants of braids. The expected results can be presumably applied to quantum computations.
The investigation of probabilistic properties of random braids is important from many points of view. Besides the relevance of this subject at the purely algebraic level, its usefulness in statistical physics of entangled lines, independent on their physical nature, is also undeniable. Statistics of ensembles of uncrossing linear objects with topological constraints has a very broad application area and can play a crucial role in macroscopic physical properties ranging from problems of self-diffusion of directed polymer chains in flows and nematic-like textures to dynamical and topological aspects of vortex glasses in high-Tc superconductors. Let us mention only two physical examples that we are presently investigating: (i) The elastic properties of polymer networks strongly depend on the initial degree of entanglement between subchains forming the sample and, hence, the elastic properties of the rubbers can be controlled by different initial conditions of sample preparation; (ii) In Cu02-based high-Tc superconductors in fields less than the critical magnetic field Hc2, there exists a region where the Abrikosov flux lattice is molten, but the sample of the superconductor demonstrates the absence of conductivity. This effect is explained by the highly entangled state of flux lines due to their topological constraints.
The theory of knots, since the work of Artin, Alexander, Markov (jr.) and others, was traditionally connected to the braid group Bn and polynomial invariants; essential subsequent progress (achieved by V.Jones and others) in knot theory was based on representations of braid groups and Hecke algebras. But alongside with the well-known problem of construction of topological invariants of knots and links, a number of similar but much less investigated problems should be noted. We mean, in particular, the calculation of the probability of knot formation in a given homotopy type with respect to a uniform measure on a set of all closed nonselfintersecting contours of a fixed length on a lattice. The given problem, known as the "knot entropy problem" did not have an adequate mathematical apparatus, and until recently has been studied mainly by numerical methods.
Nevertheless, it is clear that the above-mentioned problem (and similar ones) is connected to random walks on noncommutative groups. The last years have been marked by occurrence of a great number of problems of physical origin, dealing with probabilistic processes on noncommutative groups. Let us mention some examples, important for us, which we are studying. First of all, there are the problems of statistics and topology of chain molecules and related statistical problems of knots, as well as the classical problems of random matrix theory and localization phenomena. In several recent works, the problem concerning the calculation of the expectation of the "complexity" of randomly generated knots was formulated, with the degree of known algebraic invariants (e.g. the polynomials of Jones, Alexander, HOMFLY and others) in the role of complexity. As to the theory of random walks on braid groups, a number of particular results devoted to the investigation conditional limiting behavior of Brownian bridges on the group B3 is known. Thus, neither the Poisson boundary, nor the explicit expression of harmonic functions for braid groups have been found so far. In our investigations based on the contributions by A.Vershik and S.Nechaev [14,15,16], we will further consider the statistical properties of locally free and braid groups paying attention to their application in physics in connection with the problems mentioned above.
We also propose to develop a systematical approach to the computation of various numerical characteristics of countable groups, which involves the simultaneous consideration of three numerical constants, properly characterizing the logarithmic volume, the entropy and the escape (the drift) of uniform random walks on the group. Essential contributions to that subject can be found in recent works by J.Mairesse [7]. It turns that the inequality which relates these three constants displays the deep statistical properties of local groups and deeply reflects the so-called "multifractal" behavior of the statistical processes on corresponding groups. The evaluation of the number of words, the entropy and other statistical characteristics for the locally free groups permits one to estimate the appropriate characteristics for the braid groups. The study of locally free groups has appeared to be useful for other models of statistical physics, connected with problems of directed growth, theory of parallel computations and etc. All these aspects shall be studied in our project.
In order to have a representative and physically clear image for a system of fluctuating lines with non-Abelian topology, we can formulate the corresponding problems in terms of entangled Brownian trajectories. Such a representation serves also as a geometrically clear image of Wilson loops in the (2+1)-dimensional nonabelian field-theoretic path integral formalism. In particular, we intend to pay attention to the geometrical and algebraic properties of the simplest noncommutative braid group. One of the goals in the present project consists in the explicit geometrical construction of a "elian generalization of the Gauss invariant"he configurational space, characterized by the fundamental group π1=G. In particular, we pay special attention to the case in which G coincides with the braid group B3. To be more specific, we propose to construct explicitly a non-Abelian flat connection for a given noncommutative group G. On this way we expect to be able to establish a direct relationship with conformal field theory. The corresponding part of the project develops the preliminary results obtained in the work [17] by S.Nechaev and R.Voituriez.
New interesting problems often arise in the intermediate regions between traditional fields. This is clearly illustrated by the statistical physics of macromolecules, which arose due to the interpenetration of solid state physics, statistical physics, and biophysics. Another example of a new, currently forming field is provided by statistical topology, which was born as the result of the merging of statistical physics, the theory of integrable systems, algebraic topology, and group theory. The scope of statistical topology includes, on the one hand, mathematical problems involved in the construction of topological invariants of knots and links based on certain solvable models and, on the other hand, the physical problems related to the determination of the entropy of random knots and links. In this project, we are mainly interested in problems of the latter kind, which can be included in the subfield of "probabilistic-topological" problems (S.Nechaev [18]). Let us dwell on this class of problems in more detail. Based on the above definitions, it is easy to note that the probabilistic-topological problems are similar to those encountered in the physics of disordered systems and sometimes, of the thermodynamics of spin glasses. Indeed, the topological state plays the role of a "quenched disorder" in the coupling constant of some spin-glass-like model. In the context of this analogy, one may ask whether the concepts and methods developed over many years of disordered statistical systems can be carried over to the class of probabilistic-topological problems. On this way we intend to study the topological correlations in knot diagrams using the statistical-mechanical approaches.
A great deal of the mathematical methods involved in this project are new and/or in the stage of development. They will be elaborated further along rigorous mathematical lines, both within the framework of the topics listed above and as internally evolving fundamental mathematics (possibly also motivated by external needs).
The mathematical objects considered are mainly one-dimensional entities embedded in space, e.g. knots, links (considered either per se or as codes presenting 3-manifolds), braids, ribbon graphs, planar trees, meanders, tangles, etc., as well as various invariants related to these objects. The random generation of these objects will require the further advancement of probabilistic methods.
Concerning knots, if we leave aside the methods of study coming from physical models (see Section 1 above and Zinn-Justin [1-3]), at least three sophisticated algebraic aspects of mathematical knot theory are relevant here: the Hopf algebra of chord diagrams, the Vassiliev spectral sequence, and the energy of knots. Concerning the first, it is expected that successful computations may be performed with the use of the Hivert-Thiery MuPad software (see Section 3 above) and used to study finite type knot invariants. As to the Vassiliev spectral sequence for knots (see Vassiliev [19]), which has recently been generalized (see V.Vassiliev [20]) to knots in manifolds (known as Wilson lines in physics), it is actually a much more general and in fact universal construction, and can be carried over to the other one-dimensional objects relevant to this project; for example graphs, where work is already in progress (see Section 1 above and S.Lando [21]). Finally, the study of the energy of knots, initiated by Moffat and Arnold, and developed by O'Hara, Michael Friedman and others (see in particular O.Karpenkov [22]) can be advanced further by our team.
Besides the Hopf algebra of chord diagrams, there are many other "diagrammatic" algebras which could be usefully studied (see Section 3 above), in particular in their computational aspect via the MuPad software.
The work of I.Dynnikov (see [23]) on the presentations of tangles by three-page books has unified knots, long knots, links, braids, pure braids (all of which are particular cases of tangles) into one combinatorial formalism, leading to their description by finitely presented semigroups and groups; this very novel subject is also rapidly developing.
Concerning braids, Vershik's results on random walks on braids, in which he claimed stabilization phenomena for Garside normal forms, simply beg to be carried over to other normal forms (related to handle reduction, see P.Dehornoy [24]) and to the canonical order on braids (see P.Dehornoy, I.Dynnikov, et al [25]).
A significant breakthrough was achieved in the theory of 3-manifolds by S.Matveev (see Matveev [26]), who succeeded in classifying graph manifolds and Haken manifolds (by using a kind of four valent ribbon graph with additional structure - the action of Z/2 and Z/3 at the vertices). Our expectations here are related to the possible generalization of this approach to other classes of manifolds.
[1] P.Zinn-Justin, The General O(n) Quartic Matrix Model and its application to Counting Tangles and Links, Commun. Math. Phys., 238 (2003), 287-304
[2] P.Zinn-Justin et J.-B.Zuber, Matrix Integrals and the Generation and Counting of Virtual Tangles and Links, accepté pour publication dans J. Knot Theor. Ramif. (preprint math-ph/0303049).
[3] G.Schaeffer et P.Zinn-Justin, On the Asymptotic Number of Plane Curves and Alternating Knots, accepté pour publication dans J. Exp. Math. (preprint math-ph/0304034).
[4] A.M. Vershik and S.V. Kerov, Sov. Math. Dokl. 18, 527 (1977)
[5] S.N. Majumdar, S.Nechaev, Anisotropic ballistic deposition model with links to the Ulam problem and the Tracy-Widom distribution, Phys.Rev.E, 69, 011103 (2004)
[6] D.Krob, J.Mairesse, and I.Michos, Computing the average parallelism in trace monoids. Discrete Math., 273, 131-162 (2003)
[7] J.Mairesse and L.Vuillon, Asymptotic behavior in a heap model with two pieces, Theoret. Comput. Sci., 270, 525-560 (2002)
[8] F. Hivert, J.-C. Novelli, J.-Y. Thibon, The Algebra of Binary Search Trees preprint: math.CO/0401089
[9] V.Vershinin, On Poisson-Malcev structures. Acta Appl. Math. 75, 281-292 (2003)
[10] V.Prasolov, A.Sossinski, Knots, Links, Braids and 3-Manifolds (AMS: Providence R.I., 1997)
[11] S.Matveev, Algorithmic Topology and Classification of 3-Manifolds (Springer: Berlin, 2003)
[12] S.K.Lando, On a Hopf algebra in graph theory, J. Comb. Theory, Ser. B, 80, 104-121 (2000)
[13] S.K.Lando, Ramified coverings of the two-dimensional sphere and the intersection theory in spaces of meromorphic functions on algebraic curves, Russ. Math. Surveys, 57, 463-533 (2002)
[14] A.M.Vershik, S.Nechaev, R.Bikbov, Statistical properties of locally free groups with application to braid groups and growth of heaps, Comm. Math. Phys., 212, 469-501 (2000)
[15] A.M. Vershik, Dynamic theory of growth in groups: Entropy, boundaries, examples Russian Mathematical Surveys, 55, 667 (2000)
[16] R. Bikbov, S. Nechaev, Topological relaxation of entangled flux lattices: Single vs collective line dynamics, Phys. Rev. Lett., 87, 150602 (2001)
[17] S. Nechaev, R. Voituriez, Random walks on 3-strand braid and related hyperbolic groups, J. Phys. A: Math. Gen. 36, 43-66 (2003)
[18] S.K. Nechaev, Statistics of Knots and Entangled Random Walks, (WSPC: Singapore, 1996) ; O. Vasilyev, S. Nechaev, Thermodynamics and topology of disordered systems: Statistics of random knot diagrams on finite lattices, JETP, 93, 1119 (2001)
[19] V.Vassiliev, Cohomology of knot spaces, Advances in Soviet Mathematics, vol.1, 23-69, 1990
[20] V.Vassiliev, Complements of discriminants of smooth maps, Revised Edition, Amer.Math.Soc., Providence RI, 1994. [21] S.K. Lando, A.K. Zvonkin, Graphs on Surfaces and Their Applications, with an Appendix by D.Zagier, (Springer : Berlin, 2004)
[22] O.Karpenkov, Energy of a knot: variational principles, Russ. J. Math. Phys., vol.9 No.3, 2002
[23] I.A.Dynnikov, Three-page approach to knot theory. Universal semigroup, Funktsional'nyi Analiz i Prilozhenija, 34, 29-40 (2000) (Russian); English translation in Functional analysis and its Appl. 34, 24-32 (2000)
[24] P. Dehornoy, Braids and self-distributivity, Progress in Math vol. 192, Birkhauser (2000).
[25] P. Dehornoy, I. Dynnikov, D. Rolfsen, B. Wiest, Why are braids orderable? Panomramas & Syntheses vol 14, Soc. Math. de France (2002).
[26] S. Matveev, Algorithmic Topology and Classification of 3-Manifolds (Springer: Berlin, 2003)