On the model of simple braids, defined to be the left divisors of Garside's elements Delta_n in the monoid Binfty+, we investigate simple elements in Thompson's monoid F+ and in a larger monoid H+ that is a hybrid of Binfty+ and F+: in both cases, we count how many simple elements left divide the right lcm of the first n - 1 atoms, and characterize their normal forms in terms of forbidden factors. In the case of H+, a generalized Pascal triangle appears.
We establish a new, fairly general cancellativity criterion for a presented monoid that properly extends the previously known related criteria. It is based on a new version of the word transformation called factor reversing, and its specificity is to avoid any restriction on the number of relations in the presentation. As an application, we deduce the cancellativity of some natural extension of Artin's braid monoid in which crossings are colored.
We investigate the padded version of reduction, an extension of multifraction reduction as defined in arXiv:1606.08991, and connect it both with ordinary reduction and with the so-called Property H. As an application, we show that all Artin-Tits groups of sufficiently large type satisfy some weakening Conjecture Apadded of Conjecture A, thus showing that the reduction approach is relevant for these groups.
We investigate gcd-monoids, which are cancellative monoids in which any two elements admit a left- and a right-gcd, and the associated reduction of multifractions (arXiv:1606.08991), a general approach to the Word Problem for the enveloping group. Here we consider the particular case of interval monoids associated with finite posets. In this way, we construct gcd-monoids, in which reduction of multifractions has prescribed properties not yet known to be compatible: semi-convergence of reduction without convergence, semi-convergence up to some level but not beyond, non-embeddability into the enveloping group (a strong negation of semi-convergence).
Multifraction reduction is a new approach to the Word Problem for Artin-Tits groups and, more generally, for the enveloping group U(M) of a monoid M in which any two elements admit a greatest common divisor. This approach is based on a rewrite system R(M) that extends free group reduction. In this paper, we show that for R(M) to satisfy a weak form of convergence called semi-convergence is sufficient for solving the Word Problem for U(M), and we connect semi-convergence with other conditions involving R(M). We conjecture that all these properties are valid when M is an Artin-Tits monoid, and report about numerical experiments supporting this conjecture.
We describe a new approach to the Word Problem for Artin-Tits groups and, more generally, for the enveloping group U(M) of a monoid M in which any two elements admit a greatest common divisor. The method relies on a rewrite system R(M) that extends free reduction for free groups. Here we show that, if M satisfies what we call the 3-Ore condition about common multiples, what corresponds to type FC in the case of Artin-Tits monoids, then the system R(M) is convergent. Under this assumption, we obtain a unique representation result for the elements of U(M), extending Ore's theorem for groups of fractions and leading to a solution of the Word Problem of a new type. We also show that there exist universal shapes for the van Kampen diagrams of the words representing 1.
In the general context of presentations of monoids, we study normalisation processes that are determined by their restriction to length-two words. Garside's greedy normal forms and quadratic convergent rewriting systems, in particular those associated with the plactic monoids, are typical examples. Having introduced a parameter called the class measuring the complexity of the normalisation of length-three words, we analyse the normalisation of longer words and describe a number of possible behaviours. We fully axiomatise normalisations of class (4, 3), show the convergence of the associated rewriting systems, and characterise those deriving from a Garside family.
This text consists of additions to the book "Foundations of Garside Theory'', EMS Tracts in Mathematics, vol. 22 (2015) - see introduction and table of contents in arXiv:1309.0796 - namely skipped proofs and solutions to selected exercises.
(MSC 20F36, 20F55) We show that every finitely generated Artin-Tits group admits a finite Garside family, by introducing the notion of a low element in a Coxeter group and proving that the family of all low elements in a Coxeter system (W, S) with S finite includes S and is finite and closed under suffix and join with respect to the right weak order.
(MSC 20F36, 05A17, 46L54) We count the n-strand braids whose normal decomposition has length at most two in the dual braid monoid B_n+* by reducing the question to a computation of free cumulants for a product of independent variables, for which we establish a general formula.
(MSC 20N02, 20F38, 20M30, 20F55, 57M25) Building on a result by W. Rump, we show how to exploit the right-cyclic law (x.y).(x.z) = (y.x).(y.z) in order to investigate the structure groups and monoids attached with (involutive nondegenerate) set-theoretic solutions of the Yang-Baxter equation. We develop a sort of right-cyclic calculus, and use it to obtain short proofs for the existence both of the Garside structure and of the I-structure of such groups. We describe finite quotients that exactly play for the considered groups the role that Coxeter groups play for Artin-Tits groups.
(MSC 57M27, 17D99, 20N02, 55N35, 06A99) We determine all 2- and 3-cocycles for Laver tables, an infinite sequence of finite structures obeying the left-selfdistributivity law; in particular, we describe simple explicit bases. This provides a number of new positive braid invariants and paves the way for further potential topological applications. Incidentally, we establish and study a partial ordering on Laver tables given by the right-divisibility relation.
(MSC 20F36, 05A05, 18B40, 20B30, 20F10, 20F38, 20F55, 20M05, 20N02, 68Q17) This text consists of the introduction, table of contents, and bibliography of a long manuscript (703 pages) that is currently submitted for publication. This manuscript develops an extension of Garside's approach to braid groups and provides a unified treatment for the various algebraic structures that appear in this context. The complete text can be found at http://www.math.unicaen.fr/~garside/Garside.pdf
(MSC 20F38, 20F55) We attach with every finite, involutive, nondegenerate set-theoretic solution of the Yang-Baxter equation a finite group that plays for the associated structure group the role that a finite Coxeter group plays for the associated Artin-Tits group.
(MSC 20F10, 18B40, 20F36, 68Q17) Garside calculus is the common mechanism that underlies a certain type of normal form for the elements of a monoid, a group, or a category. Originating from Garside's approach to Artin's braid groups, it has been extended to more and more general contexts, the latest one being that of categories and what are called Garside families. One of the benefits of this theory is to lead to algorithms solving effectively the naturally occurring problems, typically the Word Problem. The aim of this paper is to present and solve these algorithmic questions in the new extended framework.
(MSC 20M05, 18B40, 20F10, 20F36) Garside families have recently emerged as a relevant context for extending results involving Garside monoids and groups, which themselves extend the classical theory of (generalized) braid groups. Here we establish various characterizations of Garside families, that is, equivalently, various criteria for establishing the existence of normal decompositions of a certain type.
(MSC 06F15, 20M05, 20F60) We describe a simple scheme for constructing finitely generated monoids in which left-divisibility is a linear ordering and for practically investigating these monoids. The approach is based on subword reversing, a general method of combinatorial group theory, and connected with Garside theory, here in a non-Noetherian context. As an application we describe several families of ordered groups whose space of left-invariant orderings has an isolated point, including torus knot groups and some of their amalgamated products.
(MSC 06B10, 06F15, 20F38, 20M05) We investigate the connection between Tamari lattices and the Thompson group F, summarized in the fact that F is a group of fractions for a certain monoid F+sym whose Cayley graph includes all Tamari lattices. Under this correspondence, the Tamari lattice operations are the counterparts of the least common multiple and greatest common divisor operations in F+sym. As an application, we show that, for every n, there exists a length l chain in the nth Tamari lattice whose endpoints are at distance at most 12l/n.
(MSC 20B30, 20F55, 20F36) We conjecture that the word problem of Artin-Tits groups can be solved without introducing trivial factors ss^{-1} or s^{-1}s. Here we make this statement precise and explain how it can be seen as a weak form of hyperbolicity. We prove the conjecture in the case of Artin-Tits groups of type FC, and we discuss various possible approaches for further extensions, in particular a syntactic argument that works at least in the right-angled case.
(MSC 20F36) We give a simple naming argument for establishing lower bounds on the combinatorial distance between (positive) braid words.
(MSC: 20B30, 05E15, 20F55, 20F36) We prove that the combinatorial distance between any two reduced expressions of a given permutation of {1, ..., n} in terms of transpositions lies in O(n^4). We prove that this bound is sharp, and, using a connection with the intersection numbers of certain curves in van Kampen diagrams, we give a practical criterion for proving that the derivations provided by the reversing algorithm of [Dehornoy, JPAA 116 (1997) 115-197] are optimal. We also show the existence of length l expressions whose reversing requires C l^4 elementary steps.
(MSC: 05C12, 20F38, 52B20) We develop combinatorial methods for computing the rotation distance between binary trees, i.e., equivalently, the flip distance between triangulations of a polygon. As an application, we prove that, for each n, there exist size n trees at distance 2n - O(sqrt(n)).
(MSC: 18B40, 20N02, 20F36) In connection with the emerging theory of Garside categories, we develop the notions of a left-Garside category and of a locally left-Garside monoid. In this framework, the relationship between the self-distributivity law LD and braids amounts to the result that a certain category associated with LD is a left-Garside category, which projects onto the standard Garside category of braids. This approach leads to a realistic program for establishing the Embedding Conjecture of [Dehornoy, Braids and Self-distributivity, Birkhauser (2000), Chap. IX].
(MSC: 03B30, 03F35, 20F36, 91A50) We construct long sequences of braids that are descending with respect to the standard order of braids (``Dehornoy order''), and we deduce that, contrary to all usual algebraic properties of braids, certain simple combinatorial statements involving the braid order are true, but not provable in the subsystems ISigma1 or ISigma2 of the standard Peano system.
(MSC: 20F36, 20M05, 06F05) We describe new types of normal forms for braid monoids, Artin-Tits monoids, and, more generally, all monoids in which divisibility has some convenient lattice properties (``locally Garside monoids''). We show that, in the case of braids, one of these normal forms turns out to coincide with the normal form introduced by Burckel and deduce that the latter can be computed easily. This approach leads to a new, simple description for the canonical well-order of B_n+ in terms of that of B_(n-1)+.
(MSC: 68Q01, 68Q42, 20N02) We describe several technical tools that prove to be efficient for investigating the rewrite systems associated with an equational specification. These tools consist in introducing a monoid of partial maps, listing the monoid relations corresponding to the local confluence diagrams of the rewrite system, then introducing the group presented by these relations, and finally replacing the initial rewrite system with a internal process entirely sitting in the latter group. When the approach can be completed, one typically obtains a practical method for constructing algebras satisfying prescribed equations and for solving the associated word problem. The above techniques have been developed by the first author in a context of general algebra. The goal of this paper is to bring them to the attention of the rewrite system community. We hope that such techniques can be useful for more general rewrite systems.
(MSC: 94A60, 94A62, 68P25, 20F36) Conjugacy is not the only possible primitive for designing braid-based protocols. To illustrate this principle, we describe a Fiat-Shamir-style authentication protocol that be can be implemented using any binary operation that satisfies the left self-distributive law. Conjugation is an example of such an operation, but there are other examples, in particular the shifted conjugation on Artin's braid group B_oo, and the finite Laver tables. In both cases, the underlying structures have a high combinatorial complexity, and they lead to difficult problems.
(MSC: 20N02, 20F36) Define an augmented LD-system, or ALD-system, to be a set equipped with two binary operations, one satisfying the left self-distributivity law x*(y*z) = (x*y)*(x*z) and the other satisfying the mixed laws (xoy)*z = x*(y*z) and x*(yoz) = (x*y)o(x*z). We solve the word problem of the ALD laws, and prove that every element in the parenthesized braid group B• of [2, 3, 5, 6] generates a free ALD-system of rank 1, i.e., that B• is a torsion-free ALD-system.
(MSC: 20F36, 05A05) Many natural counting problems arise in connection with the normal form of braids--and seem to have not been much considered so far. Here we solve some of them. One of the noteworthy points is that a number of different induction schemes appear. The key technical ingredient is an analysis of the normality condition in terms of permutations and their descents, in the vein of the Solomon algebra. As was perfectly summarized by a referee, the main result asserts that the size of the automaton involved in the automatic structure of B_n associated with the normal form can be lowered from n! to p(n), the number of partitions of n.
(MSC: 20F36, 05A05, 20F60) We develop a new approach to the linear ordering of the braid group B_n, based on investigating its restriction to the set Div(Delta_n^d) of all divisors of Delta_n^d in the monoid B_\infty^+, i.e., to positive n-braids whose normal form has length at most d. In the general case, we compute several numerical parameters attached with the finite orders (Div(Delta_n^d), <). In the case of 3 strands, we moreover give a complete description of the increasing enumeration of (Div(Delta_3^d), <). We deduce a new and specially direct construction of the ordering on B_3, and a new proof of the result that its restriction to B_3^+ is a well-ordering of ordinal type omega^omega.
(MSC: 20F36, 20F05, 20F10) It has been conjectured that in a braid group, or more generally in a Garside group, applying any sequence of monotone equivalences and word reversings can increase the length of a word by at most a linear factor depending on the group presentation only. We give a counter-example to this conjecture, but, on the other hand, we establish length upper bounds for the case when only right reversing is involved. We also state a new conjecture which would, like the above one, imply that the space complexity of the handle reduction algorithm is linear.
(MSC: 20F05, 20N02, 57M25, 57S05) We investigate a group B_• that includes Artin's braid group B_infty and Thompson's group F. The elements of B_• are represented by braids diagrams in which the distances between the strands are not uniform and, besides the usual crossing generators, new rescaling operators shrink or strech the distances between the strands. We prove that B_• is a group of fractions, that it is orderable, admits a non-trivial self-distributive structure, i.e., one involving the law x(yz)=(xy)(xz), it embeds in the mapping class group of a sphere with a Cantor set of punctures, and that Artin's representation of B_infty into the automorphisms of a free group extends to B_•.
(MSC: 20F05, 20F36, 20B07) We prove that Thompson's groups F and V are the geometry groups of associativity, and of associativity together with commutativity, respectively. We deduce new presentations of F and V. These presentations lead to considering a certain subgroup of V and an extension of this subgroup. We prove that the latter are the geometry groups of associativity together with the law x(yz) = y(xz), and of associativity together with a twisted version of this law involving self-distributivity, respectively.
(MSC: 20F05, 20F36) We improve and shorten the argument given in [Journal of Algebra, vol. 210 (1998) pp 291-297]. In particular, the fact that Artin braid groups are torsion free now follows from Garside's results almost immediately.
(MSC: 57M25, 20F36) We show that every trivial 3-strand braid diagram contains a disk, defined as a ribbon ending in opposed crossings. Under a convenient algebraic form, the result extends to every Artin-Tits group of type I_2(m), but it fails to extend to braids with 4 strands and more. The proof uses a partition of the Cayley graph and a continuity argument.
Artin's braid groups currently provide a promising background for cryptographical applications, since the first cryptosystems using braids were introduced. A variety of key agreement protocols based on braids have been described, but few authentication or signature schemes have been proposed so far. We introduce three authentication schemes based on braids, two of them being zero-knowledge interactive proofs of knowledge. Then we discuss their possible implementations, involving normal forms or an alternative braid algorithm, called handle reduction, which can achieve good efficiency under specific requirements.
(MSC: 05C25, 20F36, 68Q42) A combinatorial property of positive group presentations, called completeness, is introduced, with an effective criterion for recognizing complete presentations, and an iterative method for completing an incomplete presentation. We show how to directly read several properties of the associated monoid and group from a complete presentation: cancellativity or existence of common multiples in the case of the monoid, or isoperimetric inequality in the case of the group. In particular, we obtain a new criterion for recognizing that a monoid embeds in a group of fractions. Typical presentations eligible for the current approach are the standard presentations of the Artin groups and the Heisenberg group.
(MSC: 05C25, 20F36, 68Q42) A number of properties of spherical Artin groups extend to Garside groups, defined as the groups of fractions of monoids where least common multiples exist, there is no nontrivial unit, and some additional finiteness conditions are satisfied. Here we investigate a wider class of groups of fractions, called thin, which are those associated with monoids where minimal common multiples exist, but they are not necessarily unique. Also, we allow units in the involved monoids. The main results are that all thin groups of fractions satisfy a quadratic isoperimetric inequality, and that, under some additional hypotheses, they admit an automatic structure.
(MSC: 20J06, 18G35, 20M50, 20F36) We describe new combinatorial methods for constructing an explicit free resolution of Z by Z[G]-modules when G is a group of fractions of a monoid where enough least common multiples exist (``locally Gaussian monoid''), and, therefore, for computing the homology of G. Our constructions apply in particular to all Artin groups of finite Coxeter type, so, as a corollary, they give new ways of computing the homology of these groups.
(MSC: 05C25, 20F36, 68Q42) Define a Garside monoid to be a cancellative monoid where right and left lcm's exist and that satisfy additional finiteness assumptions, and a Garside group to be the group of fractions of a Garside monoid. The family of Garside groups contains the braid groups, all spherical Artin groups, and various generalizations previously considered. Here we prove that Garside groups are biautomatic, and that being a Garside group is a recursively enumerable property, i.e., there exists an algorithm constructing the (infinite) list of all small Gaussian groups. The latter result relies on an effective, tractable method for recognizing those presentations that define a Garside monoid.
(MSC: 03D40, 08B20, 20N02) We solve the word problem of the identity x(yz) = (xy)(yz) by investigating a certain group describing the geometry of that identity. We also construct a concrete realization of the free system of rank 1 relative to the above identity.
(AMS: 20F60, 20E08, 20N02) We prove that the group of left self-distributivity, a cousin of Thompson's group $F$ and an extension of Artin's braid group $B_\infty$ that describes the geometry of the identity $x(yz) = (xy)(xz)$, admits a bi-invariant linear ordering. To this end, we define a partial action of this group on finite binary trees that preserves a convenient linear ordering.
(AMS: 20F36, 20N02) We develop a counterpart to Garside's analysis of the braid monoid $B_n^+$ relevant for the monoid $\MLD$ that describes the geometry of the left self-distributivity identity. The monoid $\MLD$ extends $B_\infty^+$, of which it shares many properties, with the exception that it has no natural expression as a direct limit of finitely generated monoids. We introduce a convenient local version of the fundamental words $\D_n$, and prove that right lower common multiples exist in $\MLD$.
(AMS: 20N02, 20F36) Here we introduce new algebraic techniques for the study of left self-distributivity. We establish a selfsimilarity propriety for the terms $\der^k t$ which are counterparts to Garside's fundamental braids $\D_n^k$, and deduce partial answers to several long-standing open questions: convergence of the Polish Algorithm, computation of the normal form, existence of a lattice structure on LD-equivalence classes.
(AMS: 05C25, 20M05, 68Q42) Word reversing is a combinatorial operation on words that detects pairs of equivalent words in monoids that admit a presentation of a certain form. Here we give conditions for this method to be complete in the sense that every pair of equivalent words can be detected by word reversing. In addition, we obtain explicit upper bounds on the complexity of the process. As an application, we show that Artin groups of Coxeter type $B$ embed into Artin groups of type $A$ and are left orderable.
(AMS: 20F36) The infinite braid group B_\infty admits a left self-distributive structure. In particular, it includes a free monogenerated left self-distributive system, and, therefore, it inherits the properties of the latter algebraic object. Here we discuss how such properties translate into the language of braids. We state new results about braids and propose a list of open questions.
(AMS: 20F05, 20F36) Assume that G is a group of fractions of a monoid where lower common multiples exist and where divisibility relations have no infinite descending chain. Then G is torsion free. This result applies in particular to all finite Coxeter type Artin groups.
(AMS: 20E05, 20N02, 20F12, 68R15) Say that an element of a free group is a pure conjugate if it can be expressed from the generators using exclusively the conjugacy operation. We study free reductions in words representing pure conjugates. Using finite state automata, we attribute to the letters in such words levels that live in some free left distributive system. If a certain conjecture about this system is true, then reduction can occur only between letters lying on the same level. Under this conjecture, we establish restrictions on the form of those identities satisfied by group conjugacy, and we construct unique normal forms for large families of pure conjugates. We also show how to use group conjugacy to solve a problem related to the word problem of left self-distributivity.
(AMS: 20F05, 20F36, 20B40, 20M05) It is known that a number of algebraic properties of the braid groups extend to arbitrary finite Coxeter type Artin groups. Here we show how to extend the results to more general groups that we call Garside groups. Define a Gaussian monoid to be a finitely generated cancellative monoid where the expressions of a given element have bounded lengths, and where left and right lower common multiples exist. A Garside monoid is a Gaussian monoid in which the left and right l.c.m.'s satisfy an additional symmetry condition. A Gaussian group and a Garside group are respectively the group of fractions of a Gaussian monoid and of a Garside monoid. Braid groups and, more generally, finite Coxeter type Artin groups are Garside groups. We determine algorithmic criterions in terms of presentations for recognizing Gaussian and Garside monoids and groups, and exhibit infinite families of such groups. We describe simple algorithms that solve the word problem in a Gaussian group, show that theses algorithms have a quadratic complexity if the group is a Garside group, and prove that Garside groups have quadratic isoperimetric inequalities. We construct normal forms for Gaussian groups, and prove that, in the case of a Garside group, the language of normal forms is regular, symmetric, and geodesic, has the 5-fellow traveller property, and has the uniqueness property. This shows in particular that Garside groups are geodesically fully biautomatic. Finally, we consider an automorphism of a finite Coxeter type Artin group derived from an automorphism of its defining Coxeter graph, and prove that the subgroup of elements fixed by this automorphism is also a finite Coxeter type Artin group that can be explicitely determined.
(AMS: 20N02) We prove a result conjectured by J. Jezek, namely that a zeropotent left self-distributive system need not be 3-trivial, i.e., the identity x(yz) = 0 does not follow from the identities x(yz)=(xy)(xz), xx = 0 and x0 = 0x = 0. The argument is a general scheme possibly working for various identities in the context of self-distributivity.
(AMS: 38T15, 03B35) Starting from the intuition given by Wu's algorithm for the resolution of polynomial systems, we construct new efficient resolution strategies for propositional clauses.
(AMS: 20N02) We describe the free objects in the variety of algebras involving several mutually distributive binary operations. Also, we show how an associative operation can be constructed on such systems in good cases, thus obtaining a two way correspondence between LD-monoids (sets with a left self-distributive and a compatible associative operation) and multi-LD-systems (sets with a family of mutually distributive operations).
(AMS: 20F36, 20N02) By completing Artin's braid group B_\infty with some limit points (with respect to a natural topology), we obtain an extended monoid where new left self-distributive operations are defined. This construction provides in particular effective realizations for free algebraic systems involving a left distributive operation and a compatible associative product.
(AMS: 20F36, 57M25) Let us consider a standard braid diagram as a three-dimensional figure viewed from the top; what happens when we look at this figure from the side? We can obtain a new braid, and studying the connection between the initial braid and the derived braid provides a geometrical interpretation and a very simple proof for the existence of the right greedy normal form of positive braids.
(AMS: 20F36, 20M05, 57M05) We describe a new method for comparing braid words which relies both on the automatic structure of the braid groups and on the existence of a linear ordering on braids. This syntactical algorithm is a direct generalization of the classical word reduction used in the description of free groups, and it is more efficient than all previously known methods.
(AMS: 08B20, 20N02, 20F36) We show how operations satisfying the left distributivity identity can be constructed using a convenient structure monoid that describes the geometry of that identity. We finally obtain a realization of the free left distributive systems inside some extension of Artin's braid group with a very simple geometric interpretation.
(AMS: 20N02, 68Q42) Here we investigate the `natural' syntactic algorithm for the word problem of left distributivity, and we establish a sufficient condition which explains the convergence for all terms of a reasonable size. An algorithm for left division is also constructed.
(AMS: 20F36, 20H25, 15A24, 57M05) We study the components of the matrices that belong to the image of the Burau representation of braids, and establish both algebraic and order constraints for a given Laurent polynomial possibly be a component of such a Burau matrix. As an application partial faithfulness results for the Burau representation are deduced.
(AMS: 08A05, 20L10, 20M50) A group of elementary associativity operators is introduced so that the bracketing graphs which are the skeletons of Stasheff's associahedra become orbits and can be constructed as subgraphs of the Cayley graph of this group. A very simple proof of Mac Lane's coherence theorem is given, as well as an oriented version of this result. We also sketch a more general theory and compare the cases of associativity and left selfdistributivity.
(AMS: 20M05, 20F36) Let G be a group given by a presentation. We study the decomposition of the elements of G as quotients of ``positive'' elements (the elements of G that can be expressed without using the inverses of the generators) in the special case when the presentation satisfies some syntactical condition. This approach works in particular for Artin's braid groups, and results in a very simple quadratic algorithm for solving their word problem.
(AMS: 20N02) We construct a new normal form for one variable terms up to left distributivity. The proof that this normal form exists for every term is considerably simpler than the corresponding proof for the forms previously introduced by Richard Laver. In particular the determination of the present normal form can be made in a primitive recursive way.
(AMS: 20N02) We consider the problem of naming the variables of a term so that it becomes equivalent to a given term when left distributivity is assumed, and describe an algorithm for solving this question using conjugacy in a free group. The correctness of the algorithm is reduced to a conjecture involving some particular words. A skew version of the conjecture is established.
(AMS: 20F36, 17A30, 17A50) The decidability of the word problem for the free left distributive law is proved by introducing a structure group which describes the underlying identities. This group is closely connected with Artin's braid group $\Bi$. Braid colourings associated with free left distributive structures are used to show the existence of a unique ordering on the braids which is compatible with left translation and such that every generator sigma_i is preponderant over all sigma_k with k smaller than i. This ordering is a linear ordering.