Search

In the first part of this paper, we discuss the classical W-algebra $\mathcal{W}(\mathfrak{g}, F)$ associated with a Lie superalgebra $\mathfrak{g}$ and the nilpotent element $F$ in an $\mathfrak{sl}_2$-triple. We find a generating set of $\mathcal{W}(\mathfrak{g}, F)$ and compute the Poisson brackets between them. In the second part, which is the main part of the paper, we discuss supersymmetric classical W-algebras. We introduce two different constructions of a supersymmetric classical W-algebra $\mathcal{W}(\mathfrak{g}, f)$ associated with a Lie superalgebra $\mathfrak{g}$ and an odd nilpotent element $f$ in a subalgebra isomorphic to $\mathfrak{osp}(1|2)$. The first construction is via the SUSY classical BRST complex and the second is via the SUSY Drinfeld-Sokolov Hamiltonian reduction. We show that these two methods give rise to isomorphic SUSY Poisson vertex algebras. As a supersymmetric analogue of the first part, we compute explicit generators and Poisson brackets between the generators.

The canonical ideal for Harbater Katz Gabber covers satisfying the conditions of Petri's theorem is studied and an explicit non-singular model of the above curves is given., Comment: 17 pages

A zig-zag order is like a directed path, only with alternating directions. A generating set of minimal size for the semigroup of all full transformations on a finite set preserving the zig-zag order was determined by Fenandes et al. in 2019. This paper deals with generating sets of the semigroup $F_{\mathbb{N}}$ of all full transformations on the set of all natural numbers preserving the zig-zag order. We prove that $F_{\mathbb{N}}$ has no minimal generating sets and present two particular infinite decreasing chains of generating sets of $F_{\mathbb{N}}$., Comment: 17 pages

Invariable generation is a topic that has predominantly been studied for finite groups. In 2014, Kantor, Lubotzky, and Shalev produced extensive tools for investigating invariable generation for infinite groups. Since their paper, various authors have investigated the property for particular infinite groups or families of infinite groups. A group is invariably generated by a subset $S$ if replacing each element of $S$ with any of its conjugates still results in a generating set for $G$. In this paper we investigate how this property behaves with respect to wreath products. Our main work is to deal with the case where the base of $G\wr_X H$ is not invariably generated. We see both positive and negative results here depending on $H$ and its action on $X$., Comment: 11 pages; to appear in J. Group Theory

A fence is a particular partial order on a (finite) set, close to the linear order. In this paper, we calculate the rank of the semigroup $$\mathscr {FI}_{n}$$ of all order-preserving partial injections on an n-element fence. In particular, we provide a minimal generating set for $$\mathscr {FI}_{n}$$ . In the present paper, n is odd since this problem for even n was already solved by I. Dimitrova and J. Koppitz.

Traditionally introduced in terms of advanced topological constructions, many link invariants may also be defined in much simpler terms given their values on a few initial links and a recursive formula on a skein triangle. Then the crucial question to ask is how many initial values are necessary to completely determine such a link invariant. We focus on a specific class of invariants known as nonzero determinant link invariants, defined only for links which do not evaluate to zero on the link determinant. We restate our objective by considering a set $\mathcal{S}$ of links subject to the condition that if any three nonzero determinant links belong to a skein triangle, any two of these belonging to $\mathcal{S}$ implies that the third also belongs to $\mathcal{S}$. Then we aim to determine a minimal set of initial generators so that $\mathcal{S}$ is the set of all links with nonzero determinant. We show that only the unknot is required as a generator if the skein triangle is unoriented. For oriented skein triangles, we show that the unknot and Hopf link orientations form a set of generators., Comment: 8 figures, 22 pages

Denote by $m(G)$ the largest size of a minimal generating set of a finite group $G$. We estimate $m(G)$ in terms of $\sum_{p\in \pi(G)}d_p(G),$ where we are denoting by $d_p(G)$ the minimal number of generators of a Sylow $p$-subgroup of $G$ and by $\pi(G)$ the set of prime numbers dividing the order of $G$., Comment: 11 pages

We study an impartial game introduced by Anderson and Harary. The game is played by two players who alternately choose previously-unselected elements of a finite group. The first player who builds a generating set from the jointly-selected elements wins. We determine the nim-numbers of this game for finite groups of the form $T \times H$, where $T$ is a $2$-group and $H$ is a group of odd order. This includes all nilpotent and hence abelian groups., Comment: 10 pages, 2 figures

In this paper, we study the desingularization problem in the first q-Weyl algebra. We give an order bound for desingularized operators, and thus derive an algorithm for computing desingularized operators in the first q-Weyl algebra. Moreover, an algorithm is presented for computing a generating set of the first q-Weyl closure of a given q-difference operator. As an application, we certify that several instances of the colored Jones polynomial are Laurent polynomial sequences by computing the corresponding desingularized operator.

We construct explicit examples of geodesics in the mapping class group and show that the shadow of a geodesic in mapping class group to the curve graph does not have to be a quasi-geodesic. We also show that the quasi-axis of a pseudo-Anosov element of the mapping class group may not have the strong contractibility property. Specifically, we show that, after choosing a generating set carefully, one can find a pseudo-Anosov homeomorphism f, a sequence of points w_k and a sequence of radii r_k so that the ball B(w_k, r_k) is disjoint from a quasi-axis a of f, but for any projection map from mapping class group to a, the diameter of the image of B(w_k, r_k) grows like log(r_k)., Comment: 16 pages, 3 figures

We give a new proof of a theorem of D. Calegari that says that the Cayley graph of a surface group with respect to any generating set lying in finitely many mapping class group orbits has infinite diameter. This applies, for instance, to the generating set consisting of all simple closed curves., Comment: 8 pages, 2 figures; to appear in Proc. Roy. Soc. Edinburgh Sect. A

Let G be a group and let S be a generating set of G. In this article,we introduce a metric dC on G with respect to S, called the cardinal metric.We then compare geometric structures of (G, dC ) and (G, dW ), where dW denotes the word metric. In particular, we prove that if S is finite, then (G, dC ) and (G, dW ) are not quasiisometric in the case when (G, dW ) has infinite diameter and they are bi-Lipschitz equivalent otherwise. We also give an alternative description of cardinal metrics by using Cayley color graphs. It turns out that colorpermuting and color-preserving automorphisms of Cayley digraphs are isometries with respect to cardinal metrics.

In this article we have shown that the quantum isometry group of $C_r^*(\mathbb{Z})$, denoted by $\mathbb{Q}(\mathbb{Z},S)$ as in \cite{gos_man}, with respect to a symmetric generating set $S$ does not depend on the generating set $S$. Moreover, we have proved that the result is no longer true if the group $\mathbb{Z}$ is replaced by $\underbrace{\mathbb{Z} \times \mathbb{Z} \times\cdots \times \mathbb{Z}}_{n \ copies}$ for $n>1$., 15 pages. few changes are done

We analyse a continuous-time quantum walk on a chimera graph, which is a graph of choice for designing quantum annealers, and we discover beautiful quantum walk features such as localization that starkly distinguishes classical from quantum behaviour. Motivated by technological thrusts, we study continuous-time quantum walk on enhanced variants of the chimera graph and on diminished chimera graph with a random removal of vertices. We explain the quantum walk by constructing a generating set for a suitable subgroup of graph isomorphisms and corresponding symmetry operators that commute with the quantum walk Hamiltonian; the Hamiltonian and these symmetry operators provide a complete set of labels for the spectrum and the stationary states. Our quantum walk characterization of the chimera graph and its variants yields valuable insights into graphs used for designing quantum-annealers.

We prove that there exists a positive, explicit function $F(k, E)$ such that, for any group $G$ admitting a $k$-acylindrical splitting and any generating set $S$ of $G$ with $\mathrm{Ent}(G,S), Comment: 38 pages, 6 figures; added a finiteness result concerning non-geometric 3-manifolds. Comments are welcome!

In this work we study the generalized Weierstrass semigroup $\widehat{H} (\mathbf{P}_m)$ at an $m$-tuple $\mathbf{P}_m = (P_{1}, \ldots , P_{m})$ of rational points on certain curves admitting a plane model of the form $f(y) = g(x)$ over $\mathbb{F}_{q}$, where ${f(T),g(T)\in \mathbb{F}_q[T]}$. In particular, we compute the generating set $\widehat{\Gamma}(\mathbf{P}_m)$ of $\widehat{H} (\mathbf{P}_m)$ and, as a consequence, we explicit a basis for Riemann-Roch spaces of divisors with support in $\{P_{1}, \ldots , P_{m}\}$ on these curves, generalizing results of Maharaj, Matthews, and Pirsic., Comment: 17 pages

This paper addresses several structural aspects of the insertion–elimination algebra \({\mathfrak{g}}\), a Lie algebra that can be realized in terms of tree-inserting and tree-eliminating operations on the set of rooted trees. In particular, we determine the finite-dimensional subalgebras of \({\mathfrak{g}}\), the automorphism group of \({\mathfrak{g}}\), the derivation Lie algebra of \({\mathfrak{g}}\), and a generating set. Several results are stated in terms of Lie algebras admitting a triangular decomposition and can be used to reproduce results for the generalized Virasoro algebras.

We study random torsion-free nilpotent groups generated by a pair of random words of length $\ell$ in the standard generating set of $U_n(\mathbb{Z})$. Specifically, we give asymptotic results about the step properties of the group when the lengths of the generating words are functions of $n$. We show that the threshold function for asymptotic abelianness is $\ell = c \sqrt{n}$, for which the probability approaches $e^{-2c^2}$, and also that the threshold function for having full-step, the same step as $U_n(\mathbb{Z})$, is between $c n^2$ and $c n^3$., Comment: 21 pages

We introduce a new invariant of finitely generated groups, the ambiguity function, and prove that every finitely generated acylindrically hyperbolic group has a linearly bounded ambiguity function. We use this result to prove that the relative exponential growth rate $\lim \limits_{n \rightarrow \infty} \sqrt[n]{\vert B^{X}_H(n) \vert}$ of a subgroup $H$ of an acylindrically hyperbolic group $G$ exists with respect to every finite generating set $X$ of $G$, if $H$ contains a loxodromic element of $G$. Further we prove that the relative exponential growth rate of every finitely generated subgroup $H$ of a right-angled Artin group $A_{\Gamma}$ exists with respect to every finite generating set of $A_{\Gamma}$., Comment: 23 pages

A proper subsemigroup of a semigroup is maximal if it is not contained in any other proper subsemigroup. A maximal subsemigroup of a finite semigroup has one of a small number of forms, as described in a paper of Graham, Graham, and Rhodes. Determining which of these forms arise in a given finite semigroup is difficult, and no practical mechanism for doing so appears in the literature. We present an algorithm for computing the maximal subsemigroups of a finite semigroup given knowledge of its Green's structure, and the ability to determine maximal subgroups of certain subgroups. For a finite semigroup $S$ represented by a generating set $X$, in many examples, if it is practical to compute the Green's structure of $S$ from $X$, then it is also practical to find the maximal subsemigroups of $S$ using the algorithm we present. The generating set $X$ for $S$ may consist, for example, of transformations, or partial permutations, of a finite set, or of matrices over a semiring. In such examples, the time taken to determine the Green's structure of $S$ is comparable to that taken to find the maximal subsemigroups. Certain aspects of the problem of finding maximal subsemigroups reduce to other well-known computational problems, such as finding all maximal cliques in a graph and computing the maximal subgroups in a group. The algorithm presented comprises two parts. One part relates to computing the maximal subsemigroups of a special class of semigroups, known as Rees 0-matrix semigroups. The other part involves a careful analysis of certain graphs associated to the semigroup $S$, which, roughly speaking, capture the essential information about the action of $S$ on its $\mathscr{J}$-classes., Comment: 26 pages, 9 figures, 4 tables (further revised according to referee's comments, in particular to include an analysis of the performance of the presented algorithms)

Polar codes form a very powerful family of codes with a low complexity decoding algorithm that attain many information theoretic limits in error correction and source coding. These codes are closely related to Reed-Muller codes because both can be described with the same algebraic formalism, namely they are generated by evaluations of monomials. However, finding the right set of generating monomials for a polar code which optimises the decoding performances is a hard task and channel dependent. The purpose of this paper is to reveal some universal properties of these monomials. We will namely prove that there is a way to define a nontrivial (partial) order on monomials so that the monomials generating a polar code devised fo a binary-input symmetric channel always form a decreasing set. This property turns out to have rather deep consequences on the structure of the polar code. Indeed, the permutation group of a decreasing monomial code contains a large group called lower triangular affine group. Furthermore, the codewords of minimum weight correspond exactly to the orbits of the minimum weight codewords that are obtained from (evaluations) of monomials of the generating set. In particular, it gives an efficient way of counting the number of minimum weight codewords of a decreasing monomial code and henceforth of a polar code., Comment: 14 pages * A reference to the work of Bernhard Geiger has been added (arXiv:1506.05231) * Lemma 3 has been changed a little bit in order to prove that Proposition 7.1 in arXiv:1506.05231 holds for any binary input symmetric channel

We investigate the extent to which the exchange relation holds in finite groups $G$. We define a new equivalence relation $\equiv_{\mathrm{m}}$, where two elements are equivalent if each can be substituted for the other in any generating set for $G$. We then refine this to a new sequence $\equiv_{\mathrm{m}}^{(r)}$ of equivalence relations by saying that $x \equiv_{\mathrm{m}}^{(r)}y$ if each can be substituted for the other in any $r$-element generating set. The relations $\equiv_{\mathrm{m}}^{(r)}$ become finer as $r$ increases, and we define a new group invariant $\psi(G)$ to be the value of $r$ at which they stabilise to $\equiv_{\mathrm{m}}$. Remarkably, we are able to prove that if $G$ is soluble then $\psi(G) \in \{d(G), d(G) +1\}$, where $d(G)$ is the minimum number of generators of $G$, and to classify the finite soluble groups $G$ for which $\psi(G) = d(G)$. For insoluble $G$, we show that $d(G) \leq \psi(G) \leq d(G) + 5$. However, we know of no examples of groups $G$ for which $\psi(G) > d(G) + 1$. As an application, we look at the generating graph of $G$, whose vertices are the elements of $G$, the edges being the $2$-element generating sets. Our relation $\equiv_{\mathrm{m}}^{(2)}$ enables us to calculate $\mathrm{Aut}(\Gamma(G))$ for all soluble groups $G$ of nonzero spread, and give detailed structural information about $\mathrm{Aut}(\Gamma(G))$ in the insoluble case., Comment: 23 pages

Polyak proved that the set $\{\Omega1a,\Omega1b,\Omega2a,\Omega3a\}$ is a minimal generating set of oriented Reidemeister moves. One may distinguish between forward and backward moves, obtaining $32$ different types of moves, which we call directed oriented Reidemeister moves. In this article we prove that the set of $8$ directed Polyak moves $\{ \Omega{1a}^\uparrow, \Omega{1a}^\downarrow, \Omega{1b}^\uparrow, \Omega{1b}^\downarrow, \Omega{2a}^\uparrow, \Omega{2a}^\downarrow, \Omega{3a}^\uparrow, \Omega{3a}^\downarrow \}$ is a minimal generating set of directed oriented Reidemeister moves. We also specialize the problem, introducing the notion of a $L$-generating set for a link $L$. The same set is proven to be a minimal $L$-generating set for any link $L$ with at least $2$ components. Finally, we discuss knot diagram invariants arising in the study of $K$-generating sets for an arbitrary knot $K$, emphasizing the distinction between ascending and descending moves of type $\Omega3$., Comment: 18 pages, 17 figures

© 2016 by De Gruyter. It is not known whether Thompson's group F is automatic. With the recent extensions of the notion of an automatic group to graph automatic by Kharlampovich, Khoussainov and Miasnikov and then to C-graph automatic by the authors, a compelling question is whether F is graph automatic or C-graph automatic for an appropriate language class C. The extended definitions allow the use of a symbol alphabet for the normal form language, replacing the dependence on generating set. In this paper we construct a 1-counter graph automatic structure for F based on the standard infinite normal form for group elements.

We present two conjectures concerning the diameter of a direct power of a finite group. The first conjecture states that the diameter of G^n with respect to any generating set is at most n(|G|-rank(G)); and the second one states that there exists a generating set A, of minimum size, for G^n such that the diameter of G^n with respect to A is at most n(|G|-rank(G)). We will establish evidence for each of the above mentioned conjectures., Comment: 11 pages, extensively revised, unchanged results except proposition 5.9, removed section 5.4

Given a finite group with a generating subset there is a well-established notion of length for a group element given in terms of its minimal length expression as a product of elements from the generating set. Recently, certain quantities called $\lambda_{1}$ and $\lambda_{2}$ have been defined that allow for a precise measure of how stable a group is under certain types of small perturbations in the generating expressions for the elements of the group. These quantities provide a means to measure differences among all possible paths in a Cayley graph for a group, establish a group theoretic analog for the notion of stability in nonlinear dynamical systems, and play an important role in the application of groups to computational genomics. In this paper, we further expose the fundamental properties of $\lambda_{1}$ and $\lambda_{2}$ by establishing their bounds when the underlying group is a dihedral group. An essential step in our approach is to completely characterize so-called symmetric presentations of the dihedral groups, providing insight into the manner in which $\lambda_{1}$ and $\lambda_{2}$ interact with finite group presentations. This is of interest independent of the study of the quantities $\lambda_{1},\; \lambda_{2}$. Finally, we discuss several conjectures and open questions for future consideration.

Given a matrix $A\in SL(N,\Z)$, form the semidirect product $G=\Z^N\rtimes_A \Z$ where the $\Z$ factor acts on $\Z^N$ by $A$. Such a $G$ arises naturally as the fundamental group of an $N$-dimensional torus bundle which fibers over the circle. In this paper we prove that if $A$ has distinct eigenvalues not lying on the unit circle, then there exists a finite index subgroup $H\leq G$ possessing rational growth series for some generating set. In contrast, we show that if $A$ has at least one eigenvalue not lying on the unit circle, then $G$ is not almost convex for any generating set., Comment: 31 pages. Added a reference and a remark concerning previous work on the result in Theorem 1.2

The study of the entanglement entropy and entanglement spectrum has proven to be very fruitful in identifying topological phases of matter. Typically, one performs numerical studies of finite-size systems. However, there are few rigorous results for finite-size systems. We revisit the problem of determining the rank of the "particle entanglement spectrum" of the Laughlin states. We reformulate the problem into a problem concerning the ideal of symmetric polynomials that vanish under the formation of several clusters of particles. We give an explicit generating family of this ideal, and we prove that polynomials in this ideal have a total degree that is bounded from below. We discuss the difficulty in proving the same bound on the degree of any of the variables, which is necessary to determine the rank of the particle entanglement spectrum., Comment: 20 pages, 1 figure; v2: minor changes and added references

We investigate the structure of the twisted Brauer monoid $\mathcal B_n^\tau$, comparing and contrasting it to the structure of the (untwisted) Brauer monoid $\mathcal B_n$. We characterise Green's relations and pre-orders on $\mathcal B_n^\tau$, describe the lattice of ideals, and give necessary and sufficient conditions for an ideal to be idempotent-generated. We obtain formulae for the rank (smallest size of a generating set) and (where applicable) the idempotent rank (smallest size of an idempotent generating set) of each principal ideal; in particular, when an ideal is idempotent-generated, its rank and idempotent rank are equal. As an application of our results, we also describe the idempotent-generated subsemigroup of $\mathcal B_n^\tau$ (which is not an ideal) as well as the singular ideal of $\mathcal B_n^\tau$ (which is neither principal nor idempotent-generated), and we deduce a result of Maltcev and Mazorchuk that the singular part of the Brauer monoid $\mathcal B_n$ is idempotent-generated., Comment: v2 - 16 pages, 5 figures (post refereeing, to appear in PRSE). v1 - 17 pages, 7 figures

Let $G$ be a finitely generated group equipped with a finite symmetric generating set and the associated word length function $\vert \cdot\vert $. We study the behavior of the probability of return for random walks driven by symmetric measures $\mu$ that are such that $\sum\rho(\vert x\vert )\mu(x)0$. For this purpose, we develop new relations between the isoperimetric profiles associated with different symmetric probability measures. These techniques allow us to obtain a sharp $L^{2}$-version of Erschler’s inequality concerning the Følner functions of wreath products. Examples and assorted applications are included.

We introduce the depth parameters of a finite semigroup, which measure how hard it is to produce an element in the minimum ideal when we consider generating sets satisfying some minimality conditions. We estimate such parameters for some families of finite semigroups, and we obtain an upper bound for wreath products and direct products of two finite (transformation) monoids. Keywords: semigroup, generating set, minimum ideal, A-depth of a semigroup, Comment: 29 pages

A marked graph diagram is a link diagram possibly with marked $4$-valent vertices. S. J. Lomonaco, Jr. and K. Yoshikawa introduced a method of representing surface-links by marked graph diagrams. Specially, K. Yoshikawa gave local moves on marked graph diagrams, nowadays called Yoshikawa moves. It is now known that two marked graph diagrams representing equivalent surface-links are related by a finite sequence of these Yoshikawa moves. In this paper, we provide some generating sets of Yoshikawa moves on marked graph diagrams representing unoriented surface-links, and also oriented surface-links. We also discuss independence of certain Yoshikawa moves from the other moves., Comment: 22 pages, 22 figures

A palindrome is a word that reads the same left-to-right as right-to-left. We show that every simple group has a finite generating set $X$, such that every element of it can be written as a palindrome in the letters of $X$. Moreover, every simple group has palindromic width $pw(G,X)=1$, where $X$ only differs by at most one Nielsen-transformation from any given generating set. On the contrary, we prove that all non-abelian finite simple groups $G$ also have a generating set $S$ with $pw(G,S)>1$. As a by-product of our work we also obtain that every just-infinite group has finite palindromic width with respect to a finite generating set. This provides first examples of groups with finite palindromic width but infinite commutator width., Changes according to referee report

We study various ideals arising in the theory of system reliability. We use ideas from the theory of divisors, orientations and matroids on graphs to describe the minimal polyhedral cellular free resolutions of these ideals. In each case we give an explicit combinatorial description of the minimal generating set for each higher syzygy module in terms of the acyclic orientations of the graph, the $q$-reduced divisors and the bounded regions of the graphic hyperplane arrangement. The resolutions of all these ideals are closely related, and their Betti numbers are independent of the characteristic of the base field. We apply these results to compute the reliability of their associated coherent systems., Comment: to appear in Journal of Algebraic Combinatorics

We study two impartial games introduced by Anderson and Harary and further developed by Barnes. Both games are played by two players who alternately select previously unselected elements of a finite group. The first player who builds a generating set from the jointly selected elements wins the first game. The first player who cannot select an element without building a generating set loses the second game. After the development of some general results, we determine the nim-numbers of these games for abelian and dihedral groups. We also present some conjectures based on computer calculations. Our main computational and theoretical tool is the structure diagram of a game, which is a type of identification digraph of the game digraph that is compatible with the nim-numbers of the positions. Structure diagrams also provide simple yet intuitive visualizations of these games that capture the complexity of the positions., Comment: 28 pages, 44 figures. Revised in response to comments from referee

We give new upper bounds for the diameters of finite groups which do not depend on a choice of generating set. Our method exploits the commutator structure of certain profinite groups, in a fashion analogous to the Solovay-Kitaev procedure from quantum computation. We obtain polylogarithmic upper bounds for the diameters of finite quotients of: groups with an analytic structure over a pro-$p$ domain (with exponent depending on the dimension); Chevalley groups over a pro-$p$ domain (with exponent independent of the dimension) and the Nottingham group of a finite field. We also discuss some consequences of our results for random walks on groups., Comment: 37 pages. Comments and questions welcome

Let $S = (S_1, \ldots, S_d)$ denote the compression of the $d$-shift to the complement of a homogeneous ideal $I$ of $\mathbb{C}[z_1, \ldots, z_d]$. Arveson conjectured that $S$ is essentially normal. In this paper, we establish new results supporting this conjecture, and connect the notion of essential normality to the theory of the C*-envelope and the noncommutative Choquet boundary. The unital norm closed algebra $\mathcal{B}_I$ generated by $S_1,\ldots,S_d$ modulo the compact operators is shown to be completely isometrically isomorphic to the uniform algebra generated by polynomials on $\overline{V} := \overline{\mathcal{Z}(I) \cap \mathbb{B}_d}$, where $\mathcal{Z}(I)$ is the variety corresponding to $I$. Consequently, the essential norm of an element in $\mathcal{B}_I$ is equal to the sup norm of its Gelfand transform, and the C*-envelope of $\mathcal{B}_I$ is identified as the algebra of continuous functions on $\overline{V} \cap \partial \mathbb{B}_d$, which means it is a complete invariant of the topology of the variety determined by $I$ in the ball. Motivated by this determination of the C*-envelope of $\mathcal{B}_I$, we suggest a new, more qualitative approach to the problem of essential normality. We prove the tuple $S$ is essentially normal if and only if it is hyperrigid as the generating set of a C*-algebra, which is a property closely connected to Arveson's notion of a boundary representation. We show that most of our results hold in a much more general setting. In particular, for most of our results, the ideal $I$ can be replaced by an arbitrary (not necessarily homogeneous) invariant subspace of the $d$-shift., Comment: 28 pages

International audience; We prove that generic elements of braid groups are pseudo-Anosov, in the following sense: in the Cayley graph of the braid group with n $\ge$ 3 strands, with respect to Garside's generating set, we prove that the proportion of pseudo-Anosov braids in the ball of radius l tends to 1 exponentially quickly as l tends to infinity. Moreover, with a similar notion of genericity, we prove that for generic pairs of elements of the braid group, the conjugacy search problem can be solved in quadratic time. The idea behind both results is that generic braids can be conjugated "easily" into a rigid braid.

We investigate the function $d_\mathbf{A}(n)$, which gives the size of a least size generating set for $\mathbf{A}^n$, in the case where $\mathbf{A}$ has a cube term. We show that if $\mathbf{A}$ has a $k$-cube term and $\mathbf{A}^k$ is finitely generated, then $d_\mathbf{A}(n) \in O(\log(n))$ if $\mathbf{A}$ is perfect and $d_\mathbf{A}(n) \in O(n)$ if $\mathbf{A}$ is imperfect. When $\mathbf{A}$ is finite, then one may replace "Big Oh" with "Big Theta" in these estimates., Comment: Second paper in a series of three, but complete in itself

We consider the 33 conjugacy classes of genus zero, torsion-free modular subgroups, computing ramification data and Grothendieck's dessins d'enfants. In the particular case of the index 36 subgroups, the corresponding Calabi-Yau threefolds are identified, in analogy with the index 24 cases being associated with K3 surfaces. In a parallel vein, we study the 112 semi-stable elliptic fibrations over P^1 as extremal K3 surfaces with six singular fibres. In each case, a representative of the corresponding class of subgroups is identified by specifying a generating set for that representative., Comment: 43 pages, 2 figures

A fixed point theorem is proved for inverse transducers, leading to an automata-theoretic proof of the fixed point subgroup of an endomorphism of a finitely generated virtually free group being finitely generated. If the endomorphism is uniformly continuous for the hyperbolic metric, it is proved that the set of regular fixed points in the hyperbolic boundary has finitely many orbits under the action of the finite fixed points. In the automorphism case, it is shown that these regular fixed points are either exponentially stable attractors or exponentially stable repellers., Comment: 29 pages

In this paper we investigate metric properties of the groups $\Gamma_d(q)$ whose Cayley graphs are the Diestel-Leader graphs $DL_d(q)$ with respect to a given generating set $S_{d,q}$. These groups provide a geometric generalization of the family of lamplighter groups, whose Cayley graphs with respect to a certain generating set are the Diestel-Leader graphs $DL_2(q)$. Bartholdi, Neuhauser and Woess in \cite{BNW} show that for $d \geq 3$, $\Gamma_d(q)$ is of type $F_{d-1}$ but not $F_d$. We show below that these groups have dead end elements of arbitrary depth with respect to the generating set $S_{d,q}$, as well as infinitely many cone types and hence no regular language of geodesics. These results are proven using a combinatorial formula to compute the word length of group elements with respect to $S_{d,q}$ which is also proven in the paper and relies on the geometry of the Diestel-Leader graphs., Comment: 19 pages

Let G be a word-hyperbolic group with given finite generating set, for which various standard structures and constants have been pre-computed. A (non-practical) algorithm is described that, given as input two lists A and B, each composed of m words in the generators and their inverses, determines whether or not the lists are conjugate in G, and returns a conjugating element should one exist. The algorithm runs in time O(m mu)$, where mu is an upper bound on the lengths of elements in the two lists. Similarly, an algorithm is outlined that computes generators of the centraliser of A, with the same bound on running time., Comment: 21 pages, 6 figures

In this paper, we introduce a geometric statistic called the "sprawl" of a group with respect to a generating set, based on the average distance in the word metric between pairs of words of equal length. The sprawl quantifies a certain obstruction to hyperbolicity. Group presentations with maximum sprawl (i.e., without this obstruction) are called statistically hyperbolic. We first relate sprawl to curvature and show that nonelementary hyperbolic groups are statistically hyperbolic, then give some results for products, for Diestel-Leader graphs and lamplighter groups. In free abelian groups, the word metrics asymptotically approach norms induced by convex polytopes, causing the study of sprawl to reduce to a problem in convex geometry. We present an algorithm that computes sprawl exactly for any generating set, thus quantifying the failure of various presentations of Z^d to be hyperbolic. This leads to a conjecture about the extreme values, with a connection to the classic Mahler conjecture., Comment: 14 pages, 5 figures. This is split off from the paper "The geometry of spheres in free abelian groups."

We find a set of generators for the automorphism group of a graph product of finitely generated abelian groups entirely from a certain labeled graph. In addition, we find generators for the important subgroup of star-automorphisms defined in [7]. We follow closely the plan of M. Laurence's paper [11]., Comment: 15 pages

We give the first examples of groups which admit a tame combing with linear radial tameness function with respect to any choice of finite presentation, but which are not minimally almost convex on a standard generating set. Namely, we explicitly construct such combings for Thompson's group F and the Baumslag-Solitar groups BS(1, p) with p \ge 3. In order to make this construction for Thompson's group F, we significantly expand the understanding of the Cayley complex of this group with respect to the standard finite presentation. In particular we describe a quasigeodesic set of normal forms and combinatorially classify the arrangements of 2-cells adjacent to edges that do not lie on normal form paths., Comment: 36 pages, 9 figures

We define the positive diameter of a finite group $G$ with respect to a generating set $A\subset G$ to be the smallest non-negative integer $n$ such that every element of $G$ can be written as a product of at most $n$ elements of $A$. This invariant, which we denote by $\diam_A^+(G)$, can be interpreted as the diameter of the Cayley digraph induced by $A$ on $G$. In this paper we study the positive diameters of a finite abelian group $G$ with respect to its various generating sets $A$. More specifically, we determine the maximum possible value of $\diam_A^+(G)$ and classify all generating sets for which this maximum value is attained. Also, we determine the maximum possible cardinality of $A$ subject to the condition that $\diam_A^+(G)$ is "not too small". Conceptually, the problems studied are closely related to our earlier work and the results obtained shed a new light on the subject. Our original motivation came from connections with caps, sum-free sets, and quasi-perfect codes.

We present two quite different algorithms to compute the number of elements in the sphere of radius $n$ of Thompson's group $F$ with standard generating set. The first of these requires exponential time and polynomial space, but additionally computes the number of geodesics and is generalisable to many other groups. The second algorithm requires polynomial time and space and allows us to compute the size of the spheres of radius $n$ with $n \leq 1500$. Using the resulting series data we find that the growth rate of the group is bounded above by $2.62167...$. This is very close to Guba's lower bound of $\tfrac{3+\sqrt{5}}{2}$ \cite{Guba2004}. Indeed, numerical analysis of the series data strongly suggests that the growth rate of the group is exactly $\tfrac{3+\sqrt{5}}{2}$., Comment: 27 pages, 9 figures, 3 tables

The Ritt problem asks if there is an algorithm that tells whether one prime differential ideal is contained in another one if both are given by their characteristic sets. We give several equivalent formulations of this problem. In particular, we show that it is equivalent to testing if a differential polynomial is a zero divisor modulo a radical differential ideal. The technique used in the proof of equivalence yields algorithms for computing a canonical decomposition of a radical differential ideal into prime components and a canonical generating set of a radical differential ideal. Both proposed representations of a radical differential ideal are independent of the given set of generators and can be made independent of the ranking., Comment: 9 pages

We define an Artin HNN-extension to be an HNN-extension of an Artin group in which the stable letter conjugates a pair of suitably chosen subsets of the standard generating set. We show that some finite index subgroup of any Artin HNN-extension embeds in an Artin group. Similarly, we show that every Coxeter HNN-extension virtually embeds in a Coxeter group.