BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Benjamin Steinberg appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
I give a short proof of a recent result due to Kiefer and Ryzhikov showing that a finite irreducible semigroup of $n\times n$ matrices has cardinality at most $3^{n^2}$.
A band is a semigroup in which each element is idempotent. In recent years, there has been a lot of activity on the representation theory of the subclass of left regular bands due to connections to Markov chains associated to hyperplane arrangements, oriented matroids, matroids and CAT(0) cube complexes. We prove here that the integral semigroup algebra of a band is isomorphic to the integral path algebra of a quiver modulo an admissible ideal. This leads to a uniform bound quiver presentation for band algebras over all fields. Also, we answer a question of Margolis, Saliola and Steinberg by proving that the integral semigroup algebra of a CW left regular band is isomorphic to the quotient of the integral path algebra of the Hasse diagram of its support semilattice modulo the ideal generated by the sum of all paths of length two. This includes, for example, hyperplane face semigroup algebras.
Gaschütz (1954) proved that a finite group $G$ has a faithful irreducible complex representation if and only if its socle is generated by a single element as a normal subgroup; this result extends to arbitrary fields of characteristic $p$ so long as $G$ has no nontrivial normal $p$-subgroup. Žmud$'$ (1956) showed that the minimum number of irreducible constituents in a faithful complex representation of $G$ coincides with the minimum number of generators of its socle as a normal subgroup; this result can also be extended to arbitrary fields of any characteristic $p$ such that $G$ has no nontrivial normal $p$-subgroup (i.e., over which $G$ admits a faithful completely reducible representation). Rhodes (1969) characterized the finite semigroups admitting a faithful irreducible representation over an arbitrary field as generalized group mapping semigroups over a group admitting a faithful irreducible representation over the field in question. Here, we provide a common generalization of the theorems of Žmud$'$ and Rhodes by determining the minimum number of irreducible constituents in a faithful completely reducible representation of a finite semigroup over an arbitrary field (provided that it has one). Our key tool for the semigroup result is a relativized version of Žmud$'$'s theorem that determines, given a finite group $G$ and a normal subgroup $N\lhd G$, what is the minimum number of irreducible constituents in a completely reducible representation of $G$ whose restriction to $N$ is faithful.
We show how to recover a discrete twist over an ample Hausdorff groupoid from a pair consisting of an algebra and what we call a quasi-Cartan subalgebra. We identify precisely which twists arise in this way (namely, those that satisfy the local bisection hypothesis), and we prove that the assignment of twisted Steinberg algebras to such twists and our construction of a twist from a quasi-Cartan pair are mutually inverse. We identify the algebraic pairs that correspond to effective groupoids and to principal groupoids. We also indicate the scope of our results by identifying large classes of twists for which the local bisection hypothesis holds automatically.
Twisted étale groupoid algebras have been studied recently in the algebraic setting by several authors in connection with an abstract theory of Cartan pairs of rings. In this paper, we show that extensions of ample groupoids correspond in a precise manner to extensions of Boolean inverse semigroups. In particular, discrete twists over ample groupoids correspond to certain abelian extensions of Boolean inverse semigroups and we show that they are classified by Lausch's second cohomology group of an inverse semigroup. The cohomology group structure corresponds to the Baer sum operation on twists. We also define a novel notion of inverse semigroup crossed product, generalizing skew inverse semigroup rings, and prove that twisted Steinberg algebras of Hausdorff ample groupoids are instances of inverse semigroup crossed products. The cocycle defining the crossed product is the same cocycle that classifies the twist in Lausch cohomology.
We note that the deep results of Grunewald and Segal on algorithmic problems for arithmetic groups imply the decidability of several matrix equivalence problems involving poset-blocked matrices over Z. Consequently, results of Eilers, Restorff, Ruiz and Sørensen imply that isomorphism and stable isomorphism of unital graph C*-algebras (including the Cuntz-Krieger algebras) are decidable. One can also decide flow equivalence for shifts of finite type, and isomorphism of Z-quiver representations (i.e., finite diagrams of homomorphisms of finitely generated abelian groups).
We give a topological proof that a free inverse monoid on one or more generators is neither of type left-$FP_2$ nor right-$FP_2$. This strengthens a classical result of Schein that such monoids are not finitely presented as monoids.
We study a correspondence associating to each subshift $\mathcal X$ of $A^{\mathbb Z}$ a subcategory of the Karoubi envelope of the free profinite semigroup generated by $A$. The objects of this category are the idempotents in the mirage of $\mathcal X$, that is, in the set of pseudowords whose finite factors are blocks of $\mathcal X$. The natural equivalence class of the category is shown to be invariant under flow equivalence. As a corollary of our proof, we deduce the flow invariance of the profinite group that Almeida associated to each irreducible subshift. We also show, in a functorial manner, that the isomorphism class of the category is invariant under conjugacy. Finally, we see that the zeta function of $\mathcal X$ is naturally encoded in the category. These results hold, with obvious translations, for relatively free profinite semigroups over many pseudovarieties, including all of the form $\overline{\mathsf H}$, with $\mathsf H$ a pseudovariety of groups.
We consider two natural models of random walks on a module $V$ over a finite commutative ring $R$ driven simultaneously by addition of random elements in $V$, and multiplication by random elements in $R$. In the coin-toss walk, either one of the two operations is performed depending on the flip of a coin. In the affine walk, random elements $a \in R,b \in V$ are sampled independently, and the current state $x$ is taken to $ax+b$. For both models, we obtain the complete spectrum of the transition matrix from the representation theory of the monoid of all affine maps on $V$ under a suitable hypothesis on the measure on $V$ (the measure on $R$ can be arbitrary).
The representation theory of the symmetric group has been intensively studied for over 100 years and is one of the gems of modern mathematics. The full transformation monoid $\mathfrak T_n$ (the monoid of all self-maps of an $n$-element set) is the monoid analogue of the symmetric group. The investigation of its representation theory was begun by Hewitt and Zuckerman in 1957. Its character table was computed by Putcha in 1996 and its representation type was determined in a series of papers by Ponizovski{\uı}, Putcha and Ringel between 1987 and 2000. From their work, one can deduce that the global dimension of $\mathbb C\mathfrak T_n$ is $n-1$ for $n=1,2,3,4$. We prove in this paper that the global dimension is $n-1$ for all $n\geq 1$ and, moreover, we provide an explicit minimal projective resolution of the trivial module of length $n-1$. In an appendix with V.~Mazorchuk we compute the indecomposable tilting modules of $\mathbb C\mathfrak T_n$ with respect to Putcha's quasi-hereditary structure and the Ringel dual (up to Morita equivalence).
We define two general classes of nonabelian sandpile models on directed trees (or arborescences) as models of nonequilibrium statistical phenomena. These models have the property that sand grains can enter only through specified reservoirs, unlike the well-known abelian sandpile model. In the Trickle-down sandpile model, sand grains are allowed to move one at a time. For this model, we show that the stationary distribution is of product form. In the Landslide sandpile model, all the grains at a vertex topple at once, and here we prove formulas for all eigenvalues, their multiplicities, and the rate of convergence to stationarity. The proofs use wreath products and the representation theory of monoids.
We describe the $C^*$-algebra of an $E$-unitary or strongly 0-$E$-unitary inverse semigroup as the partial crossed product of a commutative $C^*$-algebra by the maximal group image of the inverse semigroup. We give a similar result for the $C^*$-algebra of the tight groupoid of an inverse semigroup. We also study conditions on a groupoid $C^*$-algebra to be Morita equivalent to a full crossed product of a commutative $C^*$-algebra with an inverse semigroup, generalizing results of Khoshkam and Skandalis for crossed products with groups.
This paper studies simplicity, primitivity and semiprimitivity of algebras associated to étale groupoids. Applications to inverse semigroup algebras are presented. The results also recover the semiprimitivity of Leavitt path algebras and can be used to recover the known primitivity criterion for Leavitt path algebras.
The basic character theory of finite monoids over the complex numbers was developed in the sixties and seventies based on work of Munn, Ponizovsky, McAlister, Rhodes and Zalcstein. In particular, McAlister determined the space of functions spanned by the irreducible characters of a finite monoid over $\mathbb C$ and the ring of virtual characters. In this paper, we present the corresponding results over an arbitrary field. As a consequence, we obtain a quick proof of the theorem of Berstel and Reutenauer that the characteristic function of a regular cyclic language is a virtual character of the free monoid. This is a crucial ingredient in their proof of the rationality of the zeta function of a sofic shift in symbolic dynamics.
We develop a general theory of Markov chains realizable as random walks on $\mathscr R$-trivial monoids. It provides explicit and simple formulas for the eigenvalues of the transition matrix, for multiplicities of the eigenvalues via Möbius inversion along a lattice, a condition for diagonalizability of the transition matrix and some techniques for bounding the mixing time. In addition, we discuss several examples, such as Toom-Tsetlin models, an exchange walk for finite Coxeter groups, as well as examples previously studied by the authors, such as nonabelian sandpile models and the promotion Markov chain on posets. Many of these examples can be viewed as random walks on quotients of free tree monoids, a new class of monoids whose combinatorics we develop.
The author has previously associated to each commutative ring with unit $\Bbbk$ and étale groupoid $\mathscr G$ with locally compact, Hausdorff, totally disconnected unit space a $\Bbbk$-algebra $\Bbbk\mathscr G$. The algebra $\Bbbk\mathscr G$ need not be unital, but it always has local units. The class of groupoid algebras includes group algebras, inverse semigroup algebras and Leavitt path algebras. In this paper we show that the category of unitary $\Bbbk\mathscr G$-modules is equivalent to the category of sheaves of $\Bbbk$-modules over $\mathscr G$. As a consequence we obtain a new proof of a recent result that Morita equivalent groupoids have Morita equivalent algebras.
A well-known theorem of Burnside says that if $ρ$ is a faithful representation of a finite group $G$ over a field of characteristic $0$, then every irreducible representation of $G$ appears as a constituent of a tensor power of $ρ$. In 1962, R. Steinberg gave a module theoretic proof that simultaneously removed the constraint on the characteristic, and allowed the group to be replaced by a monoid. Brauer subsequently simplified Burnside's proof and, moreover, showed that if the character of $ρ$ takes on $r$ distinct values, then the first $r$ tensor powers of $ρ$ already contain amongst them all of the irreducible representations of $G$ as constituents. In this note we prove the analogue of Brauer's result for finite monoids. We also prove the corresponding result for the symmetric powers of a faithful representation.
In this paper we introduce the Schützenberger category $\mathbb D(S)$ of a semigroup $S$. It stands in relation to the Karoubi envelope (or Cauchy completion) of $S$ in the same way that Schützenberger groups do to maximal subgroups and that the local divisors of Diekert do to the local monoids $eSe$ of $S$ with $e\in E(S)$. In particular, the objects of $\mathbb D(S)$ are the elements of $S$, two objects of $\mathbb D(S)$ are isomorphic if and only if the corresponding semigroup elements are $\mathscr D$-equivalent, the endomorphism monoid at $s$ is the local divisor in the sense of Diekert and the automorphism group at $s$ is the Schützenberger group of the $\mathscr H$-class of $S$. This makes transparent many well-known properties of Green's relations. The paper also establishes a number of technical results about the Karoubi envelope and Schützenberger category that were used by the authors in a companion paper on syntactic invariants of flow equivalence of symbolic dynamical systems.
We settle an old conjecture of Karrass and Solitar by proving that a finitely generated subgroup of a non-trivial free product $G = A\ast B$ has finite index if and only if it intersects non-trivially each non-trivial normal subgroup of $G$. This holds, more generally, for subgroups of finite Kurosh rank.
We present a beautiful interplay between combinatorial topology and homological algebra for a class of monoids that arise naturally in algebraic combinatorics. We explore several applications of this interplay. For instance, we provide a new interpretation of the Leray number of a clique complex in terms of non-commutative algebra. Résumé. Nous présentons une magnifique interaction entre la topologie combinatoire et l'algèbre homologique d'une classe de monoïdes qui figurent naturellement dans la combinatoire algébrique. Nous explorons plusieurs applications de cette interaction. Par exemple, nous introduisons une nouvelle interprétation du nombre de Leray d'un complexe de clique en termes de la dimension globale d'une certaine algèbre non commutative.
It is shown that membership in rational subsets of wreath products H \wr V with H a finite group and V a virtually free group is decidable. On the other hand, it is shown that there exists a fixed finitely generated submonoid in the wreath product Z \wr Z with an undecidable membership problem.
We define compact automata and show that every language has a unique minimal compact automaton. We also define recognition of languages by compact left semitopological monoids and construct the analogue of the syntactic monoid in this context. For rational languages this reduces to the usual theory of finite automata and finite monoids.
In a highly influential paper, Bidigare, Hanlon and Rockmore showed that a number of popular Markov chains are random walks on the faces of a hyperplane arrangement. Their analysis of these Markov chains took advantage of the monoid structure on the set of faces. This theory was later extended by Brown to a larger class of monoids called left regular bands. In both cases, the representation theory of these monoids played a prominent role. In particular, it was used to compute the spectrum of the transition operators of the Markov chains and to prove diagonalizability of the transition operators. In this paper, we establish a close connection between algebraic and combinatorial invariants of a left regular band: we show that certain homological invariants of the algebra of a left regular band coincide with the cohomology of order complexes of posets naturally associated to the left regular band. For instance, we show that the global dimension of these algebras is bounded above by the Leray number of the associated order complex. Conversely, we associate to every flag complex a left regular band whose algebra has global dimension precisely the Leray number of the flag complex.
In this paper we discuss various aspects of the problem of determining the minimal dimension of an injective linear representation of a finite semigroup over a field. We outline some general techniques and results, and apply them to numerous examples.
The left regular band structure on a hyperplane arrangement and its representation theory provide an important connection between semigroup theory and algebraic combinatorics. A finite semigroup embeds in a real hyperplane face monoid if and only if it is in the quasivariety generated by the monoid obtained by adjoining an identity to the two-element left zero semigroup. We prove that this quasivariety is on the one hand polynomial time decidable, and on the other minimally non-finitely based. A similar result is obtained for the semigroups embeddable in complex hyperplane semigroups.
Geometric semigroup theory is the systematic investigation of finitely-generated semigroups using the topology and geometry of their associated automata. In this article we show how a number of easily-defined expansions on finite semigroups and automata lead to simplifications of the graphs on which the corresponding finite semigroups act. We show in particular that every finite semigroup can be finitely expanded so that the expansion acts on a labeled directed graph which resembles the right Cayley graph of a free Burnside semigroup in many respects.
We give a new proof of the Krohn-Rhodes Theorem using local divisors. The proof provides nearly as good a decomposition in terms of size as the holonomy decomposition of Eilenberg, avoids induction on the size of the state set, and works exclusively with monoids with the base case of the induction being that of a group.
We present here a simple proof of Brown's diagonalizability theorem for certain elements of the algebra of a left regular band, including probability measures.
The aim of this paper is to develop a theory of finite transformation monoids and in particular to study primitive transformation monoids. We introduce the notion of orbitals and orbital digraphs for transformation monoids and prove a monoid version of D. Higman's celebrated theorem characterizing primitivity in terms of connectedness of orbital digraphs. A thorough study of the module (or representation) associated to a transformation monoid is initiated. In particular, we compute the projective cover of the transformation module over a field of characteristic zero in the case of a transitive transformation or partial transformation monoid. Applications of probability theory and Markov chains to transformation monoids are also considered and an ergodic theorem is proved in this context. In particular, we obtain a generalization of a lemma of P. Neumann, from the theory of synchronizing groups, concerning the partition associated to a transformation of minimal rank.
We provide an elementary proof that subgroups of free groups are free via group actions.
We prove that four different notions of Morita equivalence for inverse semigroups motivated by, respectively, $C^{\ast}$-algebra theory, topos theory, semigroup theory and the theory of ordered groupoids are equivalent. We also show that the category of unitary actions of an inverse semigroup is monadic over the category of étale actions. Consequently, the category of unitary actions of an inverse semigroup is equivalent to the category of presheaves on its Cauchy completion. More generally, we prove that the same is true for the category of closed actions, which is used to define the Morita theory in semigroup theory, of any semigroup with right local units.
Necessary and sufficient conditions are given for the endomorphism monoid of a profinite semigroup to be profinite. A similar result is established for the automorphism group.
We develop the representation theory of a finite semigroup over an arbitrary commutative semiring with unit, in particular classifying the irreducible and minimal representations. The results for an arbitrary semiring are as good as the results for a field. Special attention is paid to the boolean semiring, where we also characterize the simple representations and introduce the beginnings of a character theory.
The results of several papers concerning the Černý conjecture are deduced as consequences of a simple idea that I call the averaging trick. This idea is implicitly used in the literature, but no attempt was made to formalize the proof scheme axiomatically. Instead, authors axiomatized classes of automata to which it applies.
We prove the Cerny conjecture for one-cluster automata with prime length cycle. Consequences are given for the hybrid Road-coloring-Cerny conjecture for digraphs with a proper cycle of prime length.
We show that the maximal subgroup of the free profinite semigroup associated by Almeida to an irreducible sofic shift is a free profinite group, generalizing an earlier result of the second author for the case of the full shift (whose corresponding maximal subgroup is the maximal subgroup of the minimal ideal). A corresponding result is proved for certain relatively free profinite semigroups. We also establish some other analogies between the kernel of the free profinite semigroup and the $\J$-class associated to an irreducible sofic shift.
In this paper we characterize the congruence associated to the direct sum of all irreducible representations of a finite semigroup over an arbitrary field, generalizing results of Rhodes for the field of complex numbers. Applications are given to obtain many new results, as well as easier proofs of several results in the literature, involving: triangularizability of finite semigroups; which semigroups have (split) basic semigroup algebras, two-sided semidirect product decompositions of finite monoids; unambiguous products of rational languages; products of rational languages with counter; and Černý's conjecture for an important class of automata.
We prove that the class of closed subgroups of free profinite monoids is precisely the class of projective profinite groups. In particular, the profinite groups associated to minimal symbolic dynamical systems by Almeida are projective. Our result answers a question raised by Lubotzky during the lecture of Almeida at the Fields Workshop on Profinite Groups and Applications, Carleton University, August 2005. We also prove that any finite subsemigroup of a free profinite monoid consists of idempotents.