If an augmented algebra K over Q is filtered by powers of its augmentation ideal I, the associated graded algebra grK need not in general be quadratic: although it is generated in degree 1, its relations may not be generated by homogeneous relations of degree 2. In this thesis we give a sufficient criterion (called the PVH Criterion) for grK to be quadratic. When K is the group algebra of a group G, quadraticity is known to be equivalent to the existence of a (not necessarily homomorphic) universal finite type invariant for G. Thus the PVH Criterion also implies the existence of a universal finite type invariant for the group G. We apply the PVH Criterion to the group algebra of the pure virtual braid group (also known as the quasi-triangular group), and show that the corresponding associated graded algebra is quadratic, and hence that these groups have a universal finite type invariant.

If an augmented algebra K over Q is filtered by powers of its augmentation ideal I, the associated graded algebra grK need not in general be quadratic: although it is generated in degree 1, its relations may not be generated by homogeneous relations of degree 2. In this thesis we give a sufficient criterion (called the PVH Criterion) for grK to be quadratic. When K is the group algebra of a group G, quadraticity is known to be equivalent to the existence of a (not necessarily homomorphic) universal finite type invariant for G. Thus the PVH Criterion also implies the existence of a universal finite type invariant for the group G. We apply the PVH Criterion to the group algebra of the pure virtual braid group (also known as the quasi-triangular group), and show that the corresponding associated graded algebra is quadratic, and hence that these groups have a universal finite type invariant.

For a oriented genus g surface with one boundary component, S_g, the Torelli group is the group of orientation preserving homeomorphisms of S_g that induce the identity on homology. The Magnus representation of the Torelli group represents the action on F/F'' where F=π_1(S_g) and F'' is the second term of the derived series. I show that the kernel of the Magnus representation, Mag(S_g), is highly non-trivial and has a rich structure as a group. Specifically, I define an infinite filtration of Mag(S_g) by subgroups, called the higher order Magnus subgroups, M_k(S_g). I develop methods for generating nontrivial mapping classes in M_k(S_g) for all k and g≥2. I show that for each k the quotient M_k(S_g)/M_{k+1}(S_g) contains a subgroup isomorphic to a lower central series quotient of free groups E(g-1)_k/E(g-1)_{k+1}. Finally I show that for g≥3 the quotient M_k(S_g)/M_{k+1}(S_g) surjects onto an infinite rank torsion free abelian group. To do this, I define a Johnson-type homomorphism on each higher order Magnus subgroup quotient and show it has a highly non-trivial image.

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第24328号 / 情博第812号 / 新制||情||137(附属図書館) / 京都大学大学院情報学研究科数理工学専攻 / (主査)准教授 柴山 允瑠, 教授 矢ヶ崎 一幸, 教授 山下 信雄, 教授 田口 智清 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

A configuration space is a space whose points represent the possible states of a given physical system. As such they appear naturally both in theoretical physics and technical applications. For an example of the former, in analytical mechanics, the Lagrangian and Hamiltonian formulations of classical mechanics depend heavily on the use of a physical system’s configuration space for the description of its kinematical and dynamical behavior, and importantly, its evolution in time. As an example of a technical application, consider robotics, where the space of possible configurations of the mechanical linkages that make up a robot is an important tool in motion planning. In this case it is of particular interest to study the singularities of these mechanical linkages, to see if a given configuration is singular or not. This can be done with the help of configuration spaces and their topological properties. Arguably, the simplest configuration space possible arises when the system is just a collection of point-like particles in a plane. Despite its simplicity, the corresponding configuration space has substantial complexity and is of great interest in mathematics, physics and technology: For instance, it arises naturally in the mathematical modelling of robots performing tasks in a warehouse. In this thesis we go through the mathematics necessary to study the behaviour of paths in this space, which corresponds to motions of the particles. We use the theory of groups, algebraic topology, and manifolds to examine the properties of the configuration space of point-like particles in a plane. An important role in the discussion will be played by braids, which are certain collections of curves, interlaced in three-space. They are connected to many different topics in algebra, geometry, and mathematical physics, such as representation theory, the Yang-Baxter equation and knot theory. They are also important in their own right. Here we focus on their relation to configurations of points.

Le but de cette thèse est de fournir une caractérisation topologique de tresses virtuelles. Les tresses virtuelles sont des classes d’équivalence de diagrammes de type tresses tracés sur le plan. La relation d’équivalence est générée par l’isotopie, les mouvements de Reidemeister et les mouvements de Reidemeister virtuels. L’ensemble des tresses virtuelles est munie d’une opération de groupe. On parlera alors du groupe de tresses virtuelles. Dans le Chapitre 1, nous introduisons les notions de base de la théorie de noeuds virtuels, nous évoquons certains propriétés du groupe tresses virtuelles, et des liens qu’il a avec le groupe de tresses classiques. Dans le Chapitre 2, nous introduisons la notion de diagramme de Gauss tressé (ou diagramme de Gauss horizontal), et on démontre qu’il s’agit là d’une bonne réinterprétation combinatoire pour les tresses virtuelles. On généralise en particulier certains résultats connus en théorie de noeuds virtuels. Un application est de retrouver la présentation classique du groupe de tresses virtuelles pures à l’aide des diagrammes de Gauss tressés. Dans le Chapitre 3, on introduit les tresses abstraites et on montre qu’elles sont en correspondance bijective avec les tresses virtuelles. Les tresses abstraites sont des classes d’équivalence des diagrammes de type tresses tracés sur une surface orientable avec deux composantes de bord. La relation d’équivalence est générée par l’isotopie, la compatibilité, la stabilité et les mouvements de Reidemeister. La compatibilité est la relation d’équivalence générée par les difféomorphismes préservant l’orientation. La stabilité est la relation d’équivalence générée par l’addition ou la suppression d’anses à la surface, dans le complémentaire du diagramme. Dans le Chapitre 4, on démontre que tout tresse abstraite admets une unique représentant de genre minimal, à compatibilité et mouvements de Reidemeister prés. En particulier, les tresses classiques se plongent dans les tresses abstraites. / The purpose of this thesis is to give a topological characterization of virtual braids. Virtual braids are equivalence classes of planar braid-like diagrams identified up to isotopy, Reidemeister and virtual Reidemeister moves. The set of virtual braids admits a group structure and is called the virtual braid group. In Chapter 1 we present a general introduction to the theory of virtual knots, and we discuss some properties of virtual braids and their relations with classical braids. In Chapter 2 we introduce braid-Gauss dia- grams, and we prove that they are a good combinatorial reinterpretation of virtual braids. In particular this generalizes some results known in virtual knot theory. As an application, we use braid-Gauss diagrams to recover a well known presentation of the pure virtual braid group. In Chapter 3 we introduce abstract braids and we prove that they are in a bijective cor- respondence with virtual braids. Abstract braids are equivalence classes of braid-like diagrams on an orientable surface with two boundary components. The equivalence relation is generated by isotopy, compatibility, stability and Reidemeister moves. Compatibility is the equivalence relation generated by orientation preserving diffeomorphisms. Stability is the equivalence relation generated by adding handles to or deleting handles from the surface in the complement of the braid-like diagram. In Chapter 4 we prove that for any abstract braid, there is a unique representative of minimal genus, up to compatibility and Reidemeister equivalence. In particular this implies that classical braids embed in abstract braids.

In this dissertation, we study the flows on R3 associated with a nonlinear system differential equation introduced by Clark Robinson in [46]. The periodic orbits are modeled by a semi-flow on the L(−1,−1) template. It is known that these are positive knots, but need not have positive braid presentations. Here we prove that they are fibered. We investigate their linking and we construct a zeta-function that counts periodic orbits according to their twisting. This extends work by M. Sullivan in [55], and [57].

The objective of this research is to develop a framework for multi-robot coordination and control with emphasis on human-swarm and inter-agent interactions. We focus on two problems: in the first we address how to enable a single human operator to externally influence large teams of robots. By directly imposing density functions on the environment, the user is able to abstract away the size of the swarm and manipulate it as a whole, e.g., to achieve specified geometric configurations, or to maneuver it around. In order to pursue this approach, contributions are made to the problem of coverage of time-varying density functions. In the second problem, we address the characterization of inter-agent interactions and enforcement of desired interaction patterns in a provably safe (i.e., collision free) manner, e.g., for achieving rich motion patterns in a shared space, or for mixing of sensor information. We use elements of the braid group, which allows us to symbolically characterize classes of interaction patterns. We further construct a new specification language that allows us to provide rich, temporally-layered specifications to the multi-robot mixing framework, and present algorithms that significantly reduce the search space of specification-satisfying symbols with exactness guarantees. We also synthesize provably safe controllers that generate and track trajectories to satisfy these symbolic inputs. These controllers allow us to find bounds on the amount of safe interactions that can be achieved in a given bounded domain.

Mechanisation of Mathematics refers to use of computers to generate or check proofs in Mathematics. It involves translation of relevant mathematical theories from one system of logic to another, to render these theories implementable in a computer. This process is termed formalisation of mathematics. Two among the many ways of mechanising are: 1 Generating results using automated theorem provers. 2 Interactive theorem proving in a proof assistant which involves a combination of user intervention and automation. In the first part of this thesis, we reformulate the question of equivalence of two Links in first order logic using braid groups. This is achieved by developing a set of axioms whose canonical model is the braid group on infinite strands B∞. This renders the problem of distinguishing knots and links, amenable to implementation in first order logic based automated theorem provers. We further state and prove results pertaining to models of braid axioms. The second part of the thesis deals with formalising knot Theory in Higher Order Logic using the interactive proof assistant -Isabelle. We formulate equivalence of links in higher order logic. We obtain a construction of Kauffman bracket in the interactive proof assistant called Isabelle proof assistant. We further obtain a machine checked proof of invariance of Kauffman bracket.

Nous étudions un certain monoïde défini par une présentation, notée P, qui est un hybride de celles du monoïde de tresses infinies et du monoïde de Thompson. Pour cela, nous utilisons plusieurs approches. On décrit d’abord un système de réécriture convergent pour la présentation P, ce qui fournit en particulier une solution au problème de mots de P et rapproche le monoïde hybride du monoïde de Thompson. Puis, suivant le modèle du monoïde de tresses, on utilise la méthode du retournement de facteur pour analyser la relation de divisibilité à gauche, et montrer en particulier que le monoïde hybride admet la simplification et des ppcm à droite conditionnels. Ensuite, on étudie la combinatoire de Garside de l'hybride: pour chaque entier n, on introduit un élément ∆(n) comme ppcm à droite des (n−1) premiers atomes, et on étudie les diviseurs à gauche des éléments ∆(n), appelés éléments simples. Les principaux résultats sont les dénombrement des diviseurs à gauche de ∆(n) et la détermination effective des formes normales des éléments simples. On termine en construisant des représentations du monoïde hybride dans divers monoïdes, en particulier une représentation dans des matrices à coefficients polynômes de Laurent dont on conjecture qu’elle est fidèle. / We study a certain monoid specified by a presentation, denoted P, that is a hybrid of the classical presentation of the infinite braid monoid and of the presentation of Thompson’s monoid. To this end, we use several approaches. First, we describe a convergent rewrite system for P, which provides in particular a solution to the word problem, and makes the hybrid monoid reminiscent of Thompson’s monoid. Next, on the shape of the braid monoid, we use the factor reversing method to analyze the divisibility relation, and show in particular that the hybrid monoid admits cancellation and conditional right lcms. Then, we study Garside combinatorics of the hybrid: for every integer n, we introduce an element ∆(n) as the right lcm of the first (n−1) atoms, and one investigates the left divisors of the elements ∆(n), called simple elements. The main results are a counting of the left divisors of ∆(n) and a characterization of the normal forms of simple elements. We conclude with the construction of several representations of the hybrid monoid in various monoids, in particular a representation in a monoid of matrices whose entries are Laurent polynomials, which we conjecture could be faithful.