Möbius functions and semigroup representation theory

This paper explores several applications of Möbius functions to the representation theory of finite semigroups. We extend Solomon's approach to the semigroup algebra of a finite semilattice via Möbius functions to arbitrary finite inverse semigroups. This allows us to explicitly calculate the orthogonal central idempotents decomposing an inverse semigroup algebra into a direct product of matrix algebras over group rings. We also extend work of Bidigare, Hanlon, Rockmore and Brown on calculating eigenvalues of random walks associated to certain classes of finite semigroups; again Möbius functions play an important role.     

A groupoid approach to discrete inverse semigroup algebras

Let K be a commutative ring with unit and S an inverse semigroup. We show that the semigroup algebra KS can be described as a convolution algebra of functions on the universal étale groupoid associated to S by Paterson. This result is a simultaneous generalization of the author's earlier work on finite inverse semigroups and Paterson's theorem for the universal C^∗-algebra. It provides a convenient topological framework for understanding the structure of KS, including the center and when it has a unit. In this theory, the role of Gelfand duality is replaced by Stone duality.Using this approach we construct the finite dimensional irreducible representations of an inverse semigroup over an arbitrary field as induced representations from associated groups, generalizing the case of an inverse semigroup with finitely many idempotents. More generally, we describe the irreducible representations of an inverse semigroup S that can be induced from associated groups as precisely those satisfying a certain “finiteness condition.” This “finiteness condition” is satisfied, for instance, by all representations of an inverse semigroup whose image contains a primitive idempotent.     

Möbius inversion formulas for flows of arithmetic semigroups

We define a convolution-like operator which transforms functions on a space X via functions on an arithmetical semigroup S, when there is an action or flow of S on X. This operator includes the well-known classical Möbius transforms and associated inversion formulas as special cases. It is defined in a sufficiently general context so as to emphasize the universal and functorial aspects of arithmetical Möbius inversion. We give general analytic conditions guaranteeing the existence of the transform and the validity of the corresponding inversion formulas, in terms of operators on certain function spaces. A number of examples are studied that illustrate the advantages of the convolutional point of view for obtaining new inversion formulas.     

Pseudogroups and their étale groupoids

A pseudogroup is a complete infinitely distributive inverse monoid. Such inverse monoids bear the same relationship to classical pseudogroups of transformations as frames do to topological spaces. The goal of this paper is to develop the theory of pseudogroups motivated by applications to group theory, C^∗$C^{\ast }$-algebras and aperiodic tilings. Our starting point is an adjunction between a category of pseudogroups and a category of étale groupoids from which we are able to set up a duality between spatial pseudogroups and sober étale groupoids. As a corollary to this duality, we deduce a non-commutative version of Stone duality involving what we call boolean inverse semigroups and boolean étale groupoids, as well as a generalization of this duality to distributive inverse semigroups. Non-commutative Stone duality has important applications in the theory of C^∗$C^{\ast }$-algebras: it is the basis for the construction of Cuntz and Cuntz–Krieger algebras and in the case of the Cuntz algebras it can also be used to construct the Thompson groups. We then define coverages on inverse semigroups and the resulting presentations of pseudogroups. As applications, we show that Paterson’s universal groupoid is an example of a booleanization, and reconcile Exel’s recent work on the theory of tight maps with the work of the second author.     

Lower bounds for real solutions to sparse polynomial systems

We show how to construct sparse polynomial systems that have non-trivial lower bounds on their numbers of real solutions. These are unmixed systems associated to certain polytopes. For the order polytope of a poset P this lower bound is the sign-imbalance of P and it holds if all maximal chains of P have length of the same parity. This theory also gives lower bounds in the real Schubert calculus through the sagbi degeneration of the Grassmannian to a toric variety, and thus recovers a result of Eremenko and Gabrielov.     

Automorphisms and isotone self-maps of ordered sets with top and bottom

For an ordered setP letP ^P denote the set of all isotone self-maps on P, that is, all mapsf fromP toP such thatxy impliesf(x)f(y), and let Aut (P) the set of all automorphisms onP, that is, all bijective isotone self-maps inP ^P . We establish an inequality relating ¦P ^P ¦ and ¦Aut(P)¦ in terms of the irreducibles ofP. As a straightforward corollary, we show that Rival and Rutkowski's automorphism conjecture is true for lattices. It is also true for ordered sets with top and bottom whose covering graphs are planar.Supported in part by NSERC (Grant no. A2507).Supported under an NSERC International Research Fellowship.     

Character theory of symmetric groups, subgroup growth of Fuchsian groups, and random walks

We develop a number of statistical aspects of symmetric groups (mostly dealing with the distribution of cycles in various subsets of Sn), asymptotic properties of (ordinary) characters of symmetric groups, and estimates for the multiplicities of root number functions of these groups. As main applications, we present an estimate for the subgroup growth of an arbitrary Fuchsian group, a finiteness result for the number of Fuchsian presentations of such a group (resolving a long-standing problem of Roger Lyndon), as well as a proof of a well-known conjecture of Roichman concerning the mixing time of random walks on symmetric groups.     

Topology of dynamical systems in finite groups and number theory

We study and develop a very new object introduced by V.I. Arnold: a monad is a triple consisting of a finite set, a map from that finite set to itself and the monad graph which is the directed graph whose vertices are the elements of the finite set and whose arrows lead each vertex to its image (by the map). We consider the case in which the finite set entering in the monad definition is a finite group G and the map is the Frobenius map, for some k∈Z. We study the Frobenius dynamical system defined by the iteration of the monad fk, and also study the combinatorics and topology (i.e., the discrete invariants) of the monad graph. Our study provides useful information about several structures on the group associated to the monad graph. So, for example, several properties of the quadratic residues of finite commutative groups can be obtained in terms of the graph of the Frobenius monad .     

Symmetry classes of tensors via semigroup operands

The symmetry of tensors, such as the symmetric or antisymmetric ones (built on a finite-dimensional complex vector space) may be described by a complex-valued homomorphism of the symmetric group with the specification that its action equal scalar multiplication by the value, e.g. by 1 or sign. This condition may be construed as a universalizing operand (over the symmetric group with 0) homomorphism from the unsymmetrized tensors—a restructuring which permits a clearer and more effective treatment of these symmetries; freed from the multilinear setting in which they arose, it also points the way to a development of semigroup symmetries on more general universal algebras.     

Majorization and relative concavity

In this paper, some results established in [H.-N. Shi, Refinement and generalization of a class of inequalities for symmetric functions, Math. Practice Theory 29 (4) (1999) pp. 81-84] are extended from the classical majorization preordering to group-induced cone orderings. To this end the notion of relative concavity introduced in [C.P. Niculescu, F. Popovici, The extension of majorization inequalities within the framework of relative convexity, J. Inequal. Pure Appl. Math. 7 (1) (2005) (Article 27)] is used. In addition, some Ky Fan’s inequalities are discussed.     

The lumpability property for a family of Markov chains on poset block structures

We construct different classes of lumpings for a family of Markov chain products which reflect the structure of a given finite poset. We essentially use combinatorial methods. We prove that, for such a product, every lumping can be obtained from the action of a suitable subgroup of the generalized wreath product of symmetric groups, acting on the underlying poset block structure, if and only if the poset defining the Markov process is totally ordered, and one takes the uniform Markov operator in each factor state space. Finally we show that, when the state space is a homogeneous space associated with a Gelfand pair, the spectral analysis of the corresponding lumped Markov chain is completely determined by the decomposition of the group action into irreducible submodules.     

Chu duality theory and coalgebraic representation of quantum symmetries

Building upon Vaughan Pratt's work on applications of Chu space theory to Stone duality, we develop a general theory of categorical dualities on the basis of Chu space theory and closure conditions, which encompasses a variety of dualities for topological spaces, convex spaces, closure spaces, and measurable spaces (some of which are new duality results on their own). It works as a general method to generate analogues of categorical dualities between frames (locales) and topological spaces beyond topology, e.g., for measurable spaces, convex spaces, and closure spaces. After establishing the Chu duality theory, we apply the state-observable duality between quantum lattices and closure spaces to coalgebraic representations of quantum symmetries, showing that the quantum symmetry groupoid fully embeds into a purely coalgebraic category, i.e., the category of Born coalgebras, which refines, through the quantum duality that follows from Chu duality theory, Samson Abramsky's fibred coalgebraic representations of quantum symmetries (which, in turn, builds upon his Chu representations of symmetries).     

Étale groupoids and their quantales

We establish close and previously unknown relations between quantales and groupoids. In particular, to each étale groupoid, either localic or topological, there is associated a unital involutive quantale. We obtain a bijective correspondence between localic étale groupoids and their quantales, which are given a rather simple characterization and here are called inverse quantal frames. We show that the category of inverse quantal frames is equivalent to the category of complete and infinitely distributive inverse monoids, and as a consequence we obtain a (non-functorial) correspondence between these and localic étale groupoids that generalizes more classical results concerning inverse semigroups and topological étale groupoids. This generalization is entirely algebraic and it is valid in an arbitrary topos. As a consequence of these results we see that a localic groupoid is étale if and only if its sublocale of units is open and its multiplication map is semiopen, and an analogue of this holds for topological groupoids. In practice we are provided with new tools for constructing localic and topological étale groupoids, as well as inverse semigroups, for instance via presentations of quantales by generators and relations. The characterization of inverse quantal frames is to a large extent based on a new quantale operation, here called a support, whose properties are thoroughly investigated, and which may be of independent interest.     

On eigenvalues of meet and join matrices associated with incidence functions

Let (P,?,∧) be a locally finite meet semilattice. Let

     

CONNECTEDNESS AND DISCONNECTEDNESS: A DIFFERENT PERSPECTIVE

Abstract

A factorization of a Galois connection investigated earlier is used to give a definition of a connectedness-disconnectedness Galois connection that is free of the notion of constant morphism. A new notion of N-fixed morphism with respect to a class N of monomorphisms is presented. This is used to characterize the connectedness-disconnectedness Galois connection in the case that N is closed under the formation of pullbacks. Some closedness properties of these Galois connections are investigated.     

Some results on embeddings of algebras, after de Bruijn and McKenzie

In 1957, N.G. de Bruijn showed that the symmetric group Sym(Ω) on an infinite set Ω contains a free subgroup on 2^card(Ω) generators, and proved a more general statement, a sample consequence of which is that for any group A of cardinality card(Ω), the group Sym(Ω) contains a coproduct of 2^card(Ω) copies of A, not only in the variety of all groups, but in any variety of groups to which A belongs. His key lemma is here generalized to an arbitrary variety of algebras V, and formulated as a statement about functors Set V. From this one easily obtains analogs of the results stated above with “group” and Sym(Ω) replaced by “monoid” and the monoid Self(Ω) of endomaps of Ω, by “associative K-algebra” and the K-algebra End_K (V) of endomorphisms of a K-vector-space V with basis Ω, and by “lattice” and the lattice Equiv(Ω) of equivalence relations on Ω. It is also shown, extending another result from de Bruijn's 1957 paper, that each of Sym(Ω), Self(Ω) and End_K(V) contains a coproduct of 2^card(Ω) copies of itself.That paper also gave an example of a group of cardinality 2^card(Ω) that was not embeddable in Sym(Ω), and R. McKenzie subsequently established a large class of such examples. Those results are shown here to be instances of a general property of the lattice of solution sets in Sym(Ω) of sets of equations with constants in Sym(Ω). Again, similar results - this time of varying strengths - are obtained for Self(Ω), End_K(V), and Equiv(Ω), and also for the monoid Rel(Ω) of binary relations on Ω.Many open questions and areas for further investigation are noted.     

CONNECTEDNESS,DISCONNECTEDNESS AND CLOSURE OPERATORS: FURTHER RESULTS

Abstract

Let X be an arbitrary category with an (E, M)-factorization structure for sinks. A notion of constant morphism that depends on a chosen class of monomorphisms was previously used to provide a generalization of the connectedness-disconnectedness Galois connection (also called torsion-torsion free in algebraic contexts). This Galois connection was shown to factor through the class of all closure operators on X with respect to M. Here, properties and implications of this factorization are investigated. In particular, it is shown that this factorization can be further factored. Examples are provided.     

A structure theorem for posets admitting a “strong” chain partition:: A generalization of a conjecture of Daykin and Daykin (with connections to probability correlation inequalities)

Suppose a finite poset P is partitioned into three non-empty chains so that, whenever p, q∈P lie in distinct chains and p<q, then every other element of P is either above p or below q.In 1985, the following conjecture was made by David Daykin and Jacqueline Daykin: such a poset may be decomposed into an ordinal sum of posets such that, for 1?i?n, one of the following occurs:

(1)

R_i is disjoint from one of the chains of the partition; or

(2)

if p, q∈R_i are in distinct chains, then they are incomparable.

The conjecture is related to a question of R. L. Graham's concerning probability correlation inequalities for linear extensions of finite posets.In 1996, a proof of the Daykin-Daykin conjecture was announced (by two other mathematicians), but their proof needs to be rectified.In this note, a generalization of the conjecture is proven that applies to finite or infinite posets partitioned into a (possibly infinite) number of chains with the same property. In particular, it is shown that a poset admits such a partition if and only if it is an ordinal sum of posets, each of which is either a width 2 poset or else a disjoint sum of chains. A forbidden subposet characterization of these partial orders is also obtained.     

Quantales and their sheaves

A quantale is a complete lattice provided with a binary multiplication which, in particular, distributes over in each variable. First we study the quantales, their morphisms, their points and the relations with the theory of locales: the case where the multiplication is just the meet. We describe the presheaves and sheaves on a quantale and exhibit a link between the corresponding toposes and quantum logic.Research supported by NATO grant 476/84.