Dans de nombreux phénomènes régis par le hasard, le résultat de l'observation provient de la combinaison aléatoire d'événements élémentaires : le gain d'un joueur au jeu de pile ou face est le résultat de parties successives, mélanger un jeu de cartes s'effectue en plusieurs battages consécutifs, l'enchevêtrement d'une molécule d'ADN dans une cellule est le produit, entre autres, de croisements successifs. Ces événements élémentaires ont la particularité d'être réversibles (gagner/perdre au pile ou face, croiser/décroiser des brins d'ADN) et l'aléa régissant leur combinaison possède une certaine indépendance (l'issue d'une partie de pile ou face n'a a priori aucune influence sur la suivante). Un modèle possible pour ces phénomènes consiste à considérer un groupe G, fini ou dénombrable, que l'on munit d'une mesure de probabilité μ. On effectue des tirages successifs d'éléments dans G avec les hypothèses suivantes : les tirages sont indépendants, et, pour chaque tirage, μ(g) est la probabilité de tirer l'élément g. Si g1, g2,...,gn est le résul- tat de n tirages, on forme le produit g1.g2. ... . gn. C'est, par définition, la position à l'instant n de la marche aléatoire sur G de loi μ, et la question est : que peut-on dire du comportement asymptotique de g1.g2. ... .gn lorsque n augmente in- définiment ? La marche aléatoire s'en va-t'elle à l'infini ? Si oui, dans quelle direction ? Et à quelle vitesse ? Mes travaux depuis 2003 sont consacrés, pour l'essentiel, à l'étude du comportement asymptotique des marches aléatoires dans trois familles de groupes infinis, non abéliens et de type fini : les produits libres de groupes finis, les groupes d'Artin diédraux, ainsi que certaines extensions des groupes libres. Ils sont le fruit de collaborations avec Jean Mairesse (CNRS, Paris VI) et François Gautero (Université de Nice). Dans le cas des produits libres de groupes finis, nous décrivons précisément la mesure harmonique pour les marches aléatoires au plus proche voisin dans ces groupes, ce qui permet de calculer la vitesse et l'entropie asymptotique. En particulier, ces quantités dépendent de façon analytique des coefficients de μ. Considérant l'inégalité fondamentale de Yves Guivarc'h entre vitesse, entropie et croissance, nous montrons que les générateurs canoniques des produits libres de groupes finis sont extrémaux au sens de Vershik. Les groupes d'Artin diédraux forment une classe de groupes d'Artin qui généralise le groupe de tresses à trois brins B3 et pour laquelle nous donnons une description précise des géodésiques. La connaissance de la vitesse de fuite des marches aléatoires au plus proche voisin dans le groupe B3 est un premier outil de mesure de la complexité asymptotique d'une tresse aléatoire. Dans ce cas, on montre que la vitesse dépend de façon lipschitzienne mais non différentiable de μ, faisant apparaître certaines transitions de phase. Enfin, en ce qui concerne les extensions du groupe libre, nous montrons que, dans certains cas (comprenant notamment les extensions cycliques) les fonctions μ-harmoniques bornées sont entièrement décrites via le bord du groupe libre sous-jacent. La preuve repose sur l'existence d'actions non triviales de ces groupes sur des arbres réels, couplée à des critères généraux sur les compactifications des groupes développés par Vadim Kaimanovich.

A distinguishing colouring of a graph G is a labelling of the vertices of G with colours such that no non-trivial automorphism of G preserves all colours. The distinguishing number of G is the minimum number of colours in a distinguishing colouring. This thesis presents a survey of the history of distinguishing colouring problems and proves new bounds and computational results about distinguishability. An algorithm to generate all labellings of a graph up to isomorphism is presented and compared to a previously published algorithm. The new algorithm is shown to have performance competitive with the existing algorithm, as well as being able to process automorphism groups far larger than the previous limit. A specialization of the algorithm is used to generate all minimal distinguishing colourings of a set of graphs with large automorphism groups and compute their distinguishing numbers. / Graduate / 0984 / 0405 / bbird@uvic.ca

We broaden the theory of dynamical interpretation, investigate the property of commutativity and explore the subject of subgroups forming free products in Thompson's group V. We expand Brin's terminology for a revealing pair to an any tree pair. We use it to analyse the dynamical behaviour of an arbitrary tree pair which cannot occur in a revealing pair. Hence, we design a series of algorithms generating Brin's revealing pair from any tree pair, by successively eliminating the undesirable structures. To detect patterns and transitioning between tree pairs, we introduce a new combinatorial object called the chains graph. A newly defined, unique and symmetrical type of a tree pair, called a balanced tree pair, stems from the use of the chains graphs. The main theorem of Bleak et al. in "Centralizers in the R. Thompson's Group V_n" states the necessary structure of the centraliser of an element of V. We provide a converse to this theorem, by proving that each of the predicted structures is realisable. Hence we obtain a complete classification of centralisers in V. We give an explicit construction of an element of V with prescribed centraliser. The underlying concept is to embed a Cayley graph of a finite group into the flow graph (introduced in Bleak et al.) of the desired element. To reflect the symmetry, we present the resulting element in terms of a balanced tree pair. The group V is conjectured to be a universal coCF group, which generates interest in studying its subgroups. We develop a better understanding of embeddings into V by providing a necessary and sufficient dynamical condition for two subgroups (not both torsion) to form a free product in V. For this, we use the properties, explored in Bleak and Salazar-Díaz "Free Products in Thompson's Group V", of sets of so--called important points, and the Ping-Pong action induced on them.

The Lyons group denoted by Ly is a Sporadic Simple Group of order 51765179004000000 = 28 37 56 7 11 31 37 67. It(Ly) has a trivial Schur Multiplier and a trivial Outer Automorphism Group. Its maximal subgroups are G2(5) of order 5859000000 and index 8835156, 3 McL:2 of order 5388768000 and index 9606125, 53 L3(5) of order 46500000 and index 1113229656, 2 A11 of order 29916800 and index 1296826875, 51+4 + :4S6 of order 9000000 and index 5751686556, 35:(2 M11) of order 3849120 and index 13448575000, 32+4:2 A5 D8 of order 699840 and index 73967162500, 67:22 of order 1474 and index 35118846000000 and 37:18 of order 666 and index 77725494000000. Its existence was suggested by Richard Lyons. Lyons characterized its order as the unique possible order of any nite simple group where the centralizer of some involution is isomorphic to the nontrivial central extension of the alternating group of degree 11 by the cyclic group of order 2. Sims proved the existence of this group and its uniqueness using permutations and machine calculations. In this dissertation, we compute the (p; q; t)-generations of the Lyons group for dis- tinct primes p, q and t which divide the order of Ly such that p < q < t. For computations, we made use of the Computer Algebra System GAP / Mathematical Sciences / M.Sc. (Mathematics)

Orientador: Prof. Dr. Antônio Cândido Faleiros / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional, 2015. / The main goal of this work is to show that it is very benecial to the students to use logical thinking games in the mathematics classes, particularly the one known as Rubik Cube, closely related to the group theory. We present a historical study on the developing of this game, as well as the practical aspects we use in its solution. We also present the group theory and show what are the relations between it and the Rubik Cube. Finally, we show a quiz the students answered after learning this game, in order to analyse in what aspects the game may contributed to the students activities in the school and in the learning process. This non-traditional classes are a good way of increasing the self-esteem of the students and, also, their sociability. It's also a good way of training the logical thinking and concentration, two of the main requisites for learning mathematics, as could be realized in all the groups which did this activities. It is possible to teach notions of group theory to the basic student, because the Rubik Cube may be shown to be a set of elements with a binary operation, which, in this game, is the movements sequence. Furthermore, it is possible to verify the associative, neutral element and inverse element properties. It is usually said that the \Education is the most powerful weapon you can use to change the world"(Nelson Mandela), that is, it is seen as a powerful social transformation instrument. However, our experience shows that goals and laws does not change the reality by themselves. We also need the society as a whole working and contributing, not only the directly interested people, teachers and other school professionals. When we have an education of high quality we can easily see the economic and cultural consequences for our country, as well as in the daily activities. In this work I will present the conclusions I obtained proposing the mathematical games for my students, specially the Rubik Cube, but also other games, like the Sudoku and the Rummikub.

Cette thèse concerne le groupe T de Thompson. Ce groupe simple infini et finiment présenté est généralement vu comme un sous-groupe du groupe des homéomorphismes dyadiques du cercle unité qui sont linéaires par morceaux et préservent l'orientation («T linéaire par morceaux»). Cependant, T peut aussi être vu comme: 1.- le groupe des classes d'équivalence des paires équilibrées d'arbres binaires finis («T combinatoire»), 2.- un sous-groupe du groupe des homéomorphismes de la droite projective réelle qui préservent l'orientation et sont «PSL(2,Z) par morceaux» («T projectif par morceaux»), et 3.- le groupe modulaire asymptotique de l'épaissi, dans le plan hyperbolique, de l'arbre régulier de valence 3 («T modulaire»).On montre d'abord que la copie canonique de PSL(2,Z) obtenue à partir de «T projectif par morceaux» est un sous-groupe non distordu de T. Pour cela, on transporte ce sous-groupe pour obtenir une caractérisation dans le «T combinatoire», ce qui permet d'estimer la longueur des mots de ses éléments. La non-distorsion est alors une conséquence des propriétés métriques de T établies par Burillo-Cleary-Stein-Taback. Comme corollaire, T a des sous-groupes non distordus isomorphes au groupe libre engendré par deux éléments. Qui plus est, PSL(2,Z) est aussi donné explicitement sous forme «linéaire par morceaux».Le deuxième résultat utilise «T modulaire» pour prouver qu'il y a exactement f(n) classes de conjugaison d'éléments d'ordre n dans T, où f est l'indicatrice d'Euler. Étant donné un élément de torsion t de T d'ordre n, on trouve une triangulation du disque de Poincaré qui est invariante sous l'action de T sauf dans un polygone convexe à n côtés. On construit ensuite un complexe cellulaire C contractile et simplement connexe sur lequel le groupe T agit par automorphismes, et qui est minimal pour ces propriétés. Le groupe d'automorphismes de C est essentiellement T lui même (c'est une extension de T par le groupe d'ordre 2). Ce complexe cellulaire peut être vu comme une généralisation des associaèdres deStasheff dans le cas d'un polygone convexe à une infinité de côtés. L'action de T sur C est transitive sur les arêtes et les sommets, et plus généralement, sur les cellules «de type associaèdre» de toute dimension.La partie finale décrit les premières étapes d'un programme de recherche. On utilise l'interprétation géométrique du 1-squelette de C en termes de triangulations dyadiques du disque de Poincaré pour définir un bord géométrique à l'infini. Bien qu'on ait prouvé auparavant que le 1-squelette de C n'est pas hyperbolique, la construction s'inspire de celle de Gromov et permet la description de certains points du bord. / This PhD thesis is concerned with Thompson's group T. This infinite, finitely presented, simple group is usually seen as a subgroup of the group of dyadic, piecewise linear, orientation-preserving homeomorphisms of the unit circle (piecewise linear T). However, T can also be identified to: 1.- a group of equivalence classes of balanced pairs of finite binary trees (combinatorial T), 2.- a subgroup of piecewise PSL(2,Z), orientation-preserving homeomorphisms of the projective real line (piecewise projective T), and 3.- the asymptotic mapping class group of a fattened complete trivalent tree in the hyperbolic plane (modular T). The first result shows that the canonical copy of PSL(2,Z) obtained from the piecewise projective T is a non-distorted subgroup of T. For this, one carries over this subgroup to obtain a characterization into combinatorial T, from which the word length of its elements can be estimated. Then, non-distortion follows from the metric properties of T established by Burillo-Cleary-Stein-Taback. As a corollary, T has non-distorted subgroups isomorphic to the free non-abelian group of rank 2. Furthermore, PSL(2,Z) is also explicitly given in the piecewise linear form.The second result uses modular T to state that there are exactly f(n) conjugacy classes of elements of order n, where f is the Euler function. Given a torsion element t of T of order n, a dyadic triangulation of the Poincaré disc which is invariant under the action of t modulo a convex polygon with n sides is found.The third result constructs a minimal simply-connected contractible cellular complex C on which the group T acts by automorphisms. The automorphism group of C is essentially T itself (strictly speaking it is an extension of T by the group of order 2). The cellular complex C can be seen as a generalization of Stasheff's associahedra for an infinitely sided convex polygon. The action of T on C is transitive on vertices and edges and, plus generally, on associahedral type cells in all dimensions.The final part deals with the first steps of a research project. One uses the geometric interpretation of the 1-skeleton of C in term of dyadic triangulations of the Poincaré disc to define a geometric boundary at infinity. Although the 1-skeleton of C is proved not to be hyperbolic, the construction imitates Gromov's construction of the boundary of hyperbolic spaces, and allows the description of the nature of some of the boundary points.

Neste trabalho apresentamos um novo algoritmo quântico eficiente para o Problema do Subgrupo Oculto (PSO) sobre uma classe especial de grupos metacíclicos, Z_p times Z_q^s, com q | (p-1) e p/q= poli(log p), onde p, q são números primos ímpares distintos e s um inteiro positivo qualquer. Em um contexto mais geral, sem impor uma relação entre p e q obtemos um algoritmo quântico com complexidade de tempo 2^{O(sqrt{log p})}. Em qualquer caso, esses resultados são melhores que qualquer algoritmo clássico para o mesmo fim, cuja complexidade é Omega(sqrt{p}). Apresentamos também, algoritmos quânticos para o PSO sobre grupos não abelianos de ordem 2^{n+1} que possuem subgrupos cíclicos de índice 2 e para certos produtos semidiretos de grupos Z_N^m times Z_p, com m, N inteiros positivos e N fatorado de forma especial. / We present a new polynomial-time quantum algorithm that solves the hidden subgroup problem (HSP) for a special class of metacyclic groups, namely Z_{p} times _{q^s}, with q mid (p-1) and p/q= up{poly}(log p), where p, q are any odd prime numbers and s is any positive integer. This solution generalizes previous algorithms presented in the literature. In a more general setting, without imposing a relation between p and q, we obtain a quantum algorithm with time and query complexity 2^{O(sqrt{log p})}. In any case, those results improve the classical algorithm, which needs {Omega}(sqrt{p}) queries. We also present quantum algorithms for the HSP over non-abelian groups of order 2^{n+1} which have a cyclic subgroup of index 2 and for some semidirect product _N^m times _p, where N has a special prime factorization.

CAPES / A resolução de equações polinomiais com coeficientes racionais consiste em parte significativa da história do desenvolvimento da álgebra. O problema era encontrar fórmulas que expressassem uma raiz por meio de operações aritméticas efetuadas sobre a equação original, isto é, determinar a resolubilidade por radicais da equação. O trabalho de vários matemáticos culminou, no século XVI, com a obtenção das fórmulas para a resolução de equações polinomiais de grau menor ou igual a 4. Três séculos depois, Niels Abel mostrou que não é possível obter uma fórmula para a equação geral de grau 5. Finalmente, Evariste Galois resolveu completamente o problema estudando o grupo de permutação das raízes e estabelecendo as condições exatas para a resolubilidade de uma equação polinomial. Neste trabalho apresentamos um breve histórico da obtenção de fórmulas para as raízes das equações de grau menor ou igual a 4 e a essência da matemática envolvida no estudo da resolubilidade por radiciais de equações polinomiais de grau maior ou igual a 5. / The solvability by radicals of polynomial equations with rational coefficients is an important part of the history of algebra. The problem was to express a root by means of basic arithmetic operations and radicals. Formulas to solve polynomial equations of degree lower than or equal to 4 were obtained in XVIth century. About three centuries later, Niels Abel showed that it is not possible to find a formula for the general equation of degree 5. Finally, Evariste Galois solved the problem by studying the permutations groups, establishing the exact conditions for the solvability of a polynomial equation. In this work we present a brief history of the classic formulas for the roots of equations with degree lower or equal to 4. Then we study solvability by radicals of polynomial equations of degree higher than or equal to 5.

CAPES / A resolução de equações polinomiais com coeficientes racionais consiste em parte significativa da história do desenvolvimento da álgebra. O problema era encontrar fórmulas que expressassem uma raiz por meio de operações aritméticas efetuadas sobre a equação original, isto é, determinar a resolubilidade por radicais da equação. O trabalho de vários matemáticos culminou, no século XVI, com a obtenção das fórmulas para a resolução de equações polinomiais de grau menor ou igual a 4. Três séculos depois, Niels Abel mostrou que não é possível obter uma fórmula para a equação geral de grau 5. Finalmente, Evariste Galois resolveu completamente o problema estudando o grupo de permutação das raízes e estabelecendo as condições exatas para a resolubilidade de uma equação polinomial. Neste trabalho apresentamos um breve histórico da obtenção de fórmulas para as raízes das equações de grau menor ou igual a 4 e a essência da matemática envolvida no estudo da resolubilidade por radiciais de equações polinomiais de grau maior ou igual a 5. / The solvability by radicals of polynomial equations with rational coefficients is an important part of the history of algebra. The problem was to express a root by means of basic arithmetic operations and radicals. Formulas to solve polynomial equations of degree lower than or equal to 4 were obtained in XVIth century. About three centuries later, Niels Abel showed that it is not possible to find a formula for the general equation of degree 5. Finally, Evariste Galois solved the problem by studying the permutations groups, establishing the exact conditions for the solvability of a polynomial equation. In this work we present a brief history of the classic formulas for the roots of equations with degree lower or equal to 4. Then we study solvability by radicals of polynomial equations of degree higher than or equal to 5.

Les sous-décalages sont des ensembles de coloriages d'un groupe définis en excluant certains motifs, et munis d'une action de décalage. Ces objets apparaissent naturellement comme discrétisations de systèmes dynamiques : à partir d'une partition de l'espace, on associe à chaque point de ce-dernier la suite des partitions visitées sous l'action du système.Plusieurs résultats récents ont mis en évidence la riche interaction entre la dynamique des sous-décalages et leur propriétés algorithmiques. Un exemple remarquable est la classification des entropies des sous-décalages multidimensionnels de type fini comme l'ensemble des nombres récursivement énumérables à droite. Cette thèse s'intéresse aux sous-décalages avec une approche double : d'un côté on s'intéresse à leurs propriétés dynamiques et de l'autre on les étudie comme des modèles de calcul.Cette thèse contient plusieurs résultats : une condition combinatoire suffisante prouvant qu'un sous-décalage dans un groupe dénombrable est non-vide, un théorème de simulation qui réalise une action effective d'un groupe de type fini comme un facteur d'une sous-action d'un sous-décalage de type fini, une caractérisation de l'effectivité à l'aide de machines de Turing généralisées et l'indécidabilité du problème de torsion pour deux groupes, qui sont invariants de systèmes dynamiques.Comme corollaires de nos résultats, nous obtenons d'abord une preuve courte de l'existence de sous-décalages fortement apériodiques sur tout groupe dénombrable. Puis, dans le cas d'un produit semi-direct de la grille bidimensionnelle avec un groupe de type fini avec problème du mot décidable, nous montrons que le sous-décalage obtenu est de type fini. / Shift spaces are sets of colorings of a group which avoid a set of forbidden patterns and are endowed with a shift action. These spaces appear naturally as discrete versions of dynamical systems: they are obtained by partitioning the phase space and mapping each element into the sequence of partitions visited by its orbit.Severa! breakthroughs in this domain have pointed out the intricate relationship between dynamics of shift spaces and their computability properties. One remarkable example is the classification of the entropies of multidimensional subshifts of finite type as the set of right recursively enumerable numbers. This work explores shift spaces with a dual approach: on the one hand we are interested in their dynamical properties and on the ether hand we studythese abjects as computational models.Four salient results have been obtained as a result of this approach: (1) a combinatorial condition ensuring non-emptiness of subshifts on arbitrary countable groups; (2) a simulation theorem which realizes effective actions of finitely generated groups as factors of a subaction of a subshift of finite type; (3) a characterization of effectiveness with oracles using generalized Turing machines and (4) the undecidability of the torsion problem for two group invariants of shift spaces.As byproducts of these results we obtain a simple proof of the existence of strongly aperiodic subshifts in countable groups. Furthermore, we realize them as subshifts of finite type in the case of a semidirect product of a d-dimensional integer lattice with a finitely generated group with decida ble word problem whenever d> 1.