## 512 Algebra

### Refine

#### Document Type

- Doctoral Thesis (8)
- Master's Thesis (2)

#### Keywords

- Darstellungstheorie (6)
- Sphärische Varietäten (2)
- Algebraische Geometrie (1)
- Algebraische Kombinatorik (1)
- Allgemeine lineare Gruppe (1)
- Category Theory (1)
- Coalgebra (1)
- Funktor (1)
- Harish–Chandra modules (1)
- Hauptreihe <Mathematik> (1)

#### Institute

The theory of coalgebras provides a uniform view on state-based systems, which are omnipresent throughout computer science. The notion of coalgebras is parametric in the choice of a functor F on a category. Depending on this choice, the notion of an F-Coalgebra instanitates to different kinds of state-based systems, for example, Markov chains, deterministic automata, and transition systems. The present thesis contributes to the coalgebraic framework in two aspects: 1. the characterization of more systems in coalgebraic terms, and 2. the development of generic methods applicable to different systems that are coalgebras.
In the preliminaries, we recall the basic coalgebraic definitions and further categorical notions that are needed later. We illustrate the notions using the well-studied examples of coalgebras in sets.
Part I is dedicated to the semantics of two new (families of) instances of the generic framework of coalgebras beyond sets. By embedding these systems into the coalgebraic framework, we make existing generic coalgebraic methods applicable for the respective kind of state-based systems:
In Chapter 3 in Part I, we characterize the orbit-finite coalgebraic behaviours in nominal sets by relating them to the well-understood finite behaviours in sets, where orbit-finite is the canonical finiteness notion in nominal sets. Concretely, we define a special class of functors on nominal sets and call them localizable liftings of a set-functor. Then we characterize the rational fixpoint of such a functor, which captures the semantics of finitary coalgebras, i.e. orbit-finite coalgebras in nominal sets. We prove that the rational fixpoint of localizable liftings lifts from the rational fixpoint of the corresponding set functor. Secondly, we establish a sufficient property on functors F on nominal sets such that the rational fixpoint of quotient functors is given by quotienting the rational fixpoint of F . By combining these two observations, we obtain an explicit description of the rational fixpoint, i.e. the finitary semantics, of a large family of functors involving name binding, exponentiation, finite branching, and polynomial constructs. Their orbit-finite behaviours are thus equivalence classes of the finite coalgebra semantics of their set-theoretic representation. For example, for the functor modelling λ-terms, the orbit-finite behaviours are α-equivalence classes of rational λ-trees, which are possibly infinite λ-terms that have a finite representation as a coalgebra in sets.
In Chapter 4 in Part I, we model coalgebraic systems with upgrades. These are systems that run in a specific version. For each version, only a certain set of transitions are available, and the higher the version, the more transitions are available. The corresponding notion of bisimilarity, called ‘conditional bisimulation’, has been defined previously for a particular type of system called conditional transition system. In Chapter 4 we define it generically for a functor that satisfies certain axioms, generalizing the concrete notion. For this, we consider functors on the Kleisli category of the reader monad on the category of partially ordered sets. In this Kleisli category, we prove for coalgebras satisfying a sufficient condition called ‘upgrade preservation’ that the generic notion of coalgebraic bisimilarity is characterized precisely by conditional bisimilarity. Furthermore, we reduce the computation of the behavioural equivalence in the Kleisli category to that in the base category of partially ordered sets.
Part II is dedicated to the development of minimization methods for state-based systems on a coalgebraic level of generality. The minimization of a system consists of two tasks. One task is to restrict the system to those states that are reachable from a distinguished initial state. This task is called reachability construction or simply reachability. The other task of minimization is to identify states that exhibit the same behaviour. This task removes the redundancy from the system and is usually called bisimilarity minimization or also partition refinement, describing the algorithm scheme often used to solve this task. The presented methods range from abstract categorical constructions to efficient algorithmic implementations.
In Chapter 5 in Part II, we construct the reachable subcoalgebra of a given pointed coalgebra. The point of the coalgebra serves as the initial state. The construction is iterative, has at most countably many steps, works in a general categorical setting, and is proven correct for an existing concise definition of reachability of a pointed coalgebra. We discuss instances in sets and beyond. In the special case of Set, the reachability in a coalgebra is equivalent to the usual graph-theoretical reachability in the so-called canonical graph of the coalgebra. Furthermore, our construction resembles the standard breadth-first search that computes the reachable hull in the canonical graph. We also discuss examples beyond sets. While instances in nominal sets or multisorted sets are direct, more assumptions need to be fulfilled to instantiate the construction in Kleisli categories. As an alternative, we reduce the reachability problem for coalgebras in the Kleisli category to reachability in the base category.
In Chapter 6 in Part II, we discuss the task of bisimilarity minimization of coalgebras using partition refinement algorithms. We solve this task by a categorical construction that is subsequently refined towards an efficient algorithmic implementation and a running partition refinement tool, CoPaR. For many concrete system types, concrete partition refinement algorithms have been developed throughout the past 50 years. These efficient algorithms typically run in O((m + n) ⋅ log n) time, where n is the number of states in the system and m is the number of edges. It is a common assumption that every state is involved in at least one edge, m ≥ n, and so one typically calls them m ⋅ log n algorithms. In Chapter 6 we start by showing their similarities looking at two concrete example runs of the respective algorithms for (labelled) transition systems and Markov chains. We then formalize the most significant similarities by defining a categorical partition refinement construction that works in every regular category and computes the behavioural equivalence in a coalgebra. The construction is parametric in a heuristic that tells the algorithm which information to process next in the partition refinement. By a special choice for this heuristic, we obtain an existing partition refinement algorithm for coalgebras by König and Küpper [84] as an instance. By another heuristic that involves size considerations, we formalize the so-called ‘process the smaller half’ strategy that is used in all efficient partition refinement algorithms and that contributes to their low run-time complexity. As a next step towards a generic and efficient algorithm for coalgebras, we introduce zippable functors and instantiate the construction to sets. These assumptions allow us to make an optimization where we compute the refined partitions incrementally. Finally, we formalize the remaining functor specific aspects of the algorithm in a so-called refinement interface that we implement for many functors of interest.
We then design a generic algorithm in pseudocode that is only given as parameters the input coalgebra and an implementation of the abstract refinement interface of the functor. This algorithm is proven correct on the generic level, i.e. that it indeed computes the behavioural equivalence in the input coalgebra. Moreover, we analyse the run-time complexity of the algorithm and show that it runs in O((m + n) ⋅ log n) time, where n is the number of states and m the number of edges in the input coalgebra. This directly instantiates to m⋅log n partition refinement algorithms for transition systems, Markov chains (possibly with weights in a cancellative monoid), deterministic automata, and to colour refinement for graphs (also called the 1-dimensional Weisfeiler-Lehman algorithm), where each of these instances matches the run-time of the best concrete algorithm known. In order to cover weighted systems with weights in a non-cancellative monoid, we generalize the complexity analysis of the main algorithm, relaxing the complexity requirements of the functor’s refinement interface. In this relaxed setting, we can handle weighted systems with weights in a (possibly non-cancellative) monoid M in O((m + n) ⋅ log n ⋅ log min(∣M ∣, m)). Since zippable functors are not closed under composition, we define a separate modularity construction to handle composites of such system types. This construction introduces explicit intermediate states, possibly affecting the run-time complexity. For example, Segala systems combine non-deterministic and probabilistic behaviour, and the generic algorithm minimizes them in mp ⋅ log ma where mp is the number of probabilistic edges and ma the number of non-deterministic edges. This instance matches the run- time of an explicit algorithm developed independently and at the same time [53] and improves the previously best-known algorithm for Segala systems [17]. With the modularity reduction, the generic framework also supports minimization of weighted tree automata under backwards bisimulation in O(m ⋅ log m) run-time, improving the previously best-known algorithm [62]. A comparison of all instances can be found in Table 6.1 on page 145. A case-study of an actual tool implementation called CoPaR shows that our generic category-based algorithm can be of use in practise and is capable of handling input coalgebras with millions of edges within a few minutes.
In Chapter 7 in Part II, we compare the two previously discussed aspects of minimality. We show that they are dual concepts by defining an abstract notion of minimality and minimization in a category. The instance of this general minimization in the category of pointed coalgebras is the reachability construction and its instance in the dual category is bisimilarity minimization. Thus, these two minimization methods have many properties in common – up to duality. Finally, we consider the minimization of F -coalgebras under both reachability and bisimilarity. If F preserves inverse images, we show that we obtain the same minimized coalgebra no matter in which order we solve the two minimization tasks.

Diese Arbeit enthält eine Übersicht von Ergebnissen zum Thema Origami und Geometrische Konstruktionen.
Zunächst wird der Körper der mit Origami faltbaren Zahlen konstruiert, anschließend werden diese Kentnisse auf klassische Konstruktionsproblem angewandt. Abschließend werden einige mögliche Erweiterungen des vorgestellten Axiomensystems dargestellt.

In this thesis we study the structure algebra Z of the stable moment graph (a moment graph that exhibits a certain periodicity property—namely, its edge labels are invariant under translation by an element of the finite coroot lattice) for the case of the affine root system A_1. For a field k and the symmetric algebra S over k associated with the coroot lattice, the structure algebra Z is an S-algebra and in particular, it is an S-module. We study its S-module structure and construct an S-basis. We actually construct two bases: one comes from the perspective of linear algebra, the other comes from the perspective of moment graph theory.
By “setting c equal to zero” in the structure algebra Z, where c denotes a central element of the affine Kac-Moody algebra sl_2, we obtain the S^fin-module Z_c=0, where S^fin denotes the symmetric algebra associated with the finite coroot lattice. This module is “locally finite”, i.e. it can be described in terms of the finite root system A_1 and we show that it is determined by a set of certain divisibility relations. These relations can be regarded as a generalization of ordinary moment graph relations that define sections of sheaves on moment graphs, and because of this we call them higher-order congruence relations.
Furthermore, the module Z_c=0 inherits the algebra structure from the structure algebra Z. We examine this algebra structure on Z_c=0 by computing the structure constants.
The obtained results apply to an arbitrary affine root system—the studied phenomena occur in all root directions. Within the scope of applications and generalizations of the subgeneric results, the same pattern as in Kato’s theorem appears in our setting of (sheaves on) moment graphs, which enables a categorification of Kato’s theorem.

We determine some particularly interesting momentum polytopes for multiplicity free quasi-Hamiltonian manifolds by using the methods developed in [Kno16]. This leads to lots of new examples of multiplicity free quasi-Hamiltonian manifolds or equivalently, Hamiltonian loop group actions.
Precisely, we determine all convex quasi-Hamiltonian G-manifolds for G simple and simply connected where the momentum polytope is of rank one for compact Hamiltonian and quasi-Hamiltonian manifolds and we classify all Hamiltonian and q-Hamiltonian manifolds with a surjective moment map.

In representation theory typical problems are decomposition problems, i.e. the question how a given representation decomposes into smallest possible parts. A subclass of that are branching problems, asking for the decomposition of a representation that is irreducible in terms of the whole algebraic structure, when restricted to a substructure. For real reductive Lie groups these problems have recently been studied in terms of symmetry breaking operators which are
intertwining operators between a restricted group representation and a subgroup representation, intertwining with respect to the subgroup. We will address this problem in the category of Harish–Chandra modules, which are both representations of the Lie algebra and of the maximal compact subgroup of a Lie group, realized on the spaces of K-finite vectors of smooth representations. This way we will give a full classification of intertwining operators between Harish–Chandra modules of generalized principal series representations of the groups (GL(n, R), GL(n−1, R)), intertwining with respect to the Lie algebra and the maximal compact subgroup of GL(n−1, R).

The classification of spherical G-varieties X of a connected, reductive, algebraic group G over an algebraically closed field of characteristic 0 can be expressed in a purely combinatorial language. The first goal of this thesis is to define to this combinatorial data an interpretation by means of a reductive group G_X , the dual group of a spherical variety. We show that this group can be embedded into the dual group G^∨ . It appears together with a homomorphism
G_X × SL_2 → G^v ,
where the mapping of the SL_2 -factor is also determined by data coming from the variety. This result should be understood as a contribution to the work of Sakellaridis-Venkatesh. They consider applications of spherical varieties in harmonic analysis, in the context of the Langlands program. For this work the existence of a homomorphism as above is essential.
Moreover, we give the definition of a group G_X^(ass) which is connected to the combinatorics of X and to the group G_X.
A further attempt of this thesis is the investigation of pairs of spherical roots in odd characteristic. We will in particular determine all rank 2 spherical varieties whose spherical roots do not exist in characteristic 0.
The combinatorics over fields of characteristic 2 turn out to be of different nature than over other fields. There we have the important structural property that the valuation cone of a spherical variety is the negative fundamental domain of a finite reflection group. This is in general false in characteristic 2. We will present a family of counterexamples.

Anfang der 1990er Jahre führten Andersen, Jantzen und Soergel ein kombinatorisches Modell ein, um gewisse Darstellungen der folgenden zwei Situationen zu beschreiben:
a) U_p ist die quantisierte einhüllende Algebra einer komplexen Lie-Algebra an einer p-ten Einheitswurzel, wobei p > 1 eine ungerade ganze Zahl ist (und prim zu 3 wenn das zugrundeliegende Wurzelsystem vom Typ G_2 ist),
b) Lie(G_k), wobei G_k eine zusammenhängende, einfach zusammenhängende halbeinfache algebraische Gruppe über einem algebraisch abgeschlossenen Körper k mit char k > h, wobei h die Coxeterzahl des zugrundeliegenden Wurzelsystems ist.
Der Zusammenhang zwischen diesen beiden Situationen ist grundlegend, um die Modulare Lusztig-Vermutung für char p>> 0 zu zeigen. Diese Vermutung stellt eine Charakterformel für Darstellungen zusammenhängender reduktiver algebraischer Gruppen über einem algebraisch abgeschlossenen Körper k mit char k = p > h auf. Mit dem Werk von Andersen, Jantzen und Soergel kann man sie aus ihrem char 0-Analogon herleiten, der Quantum-Vermutung von Lusztig.
Dieses Modell wird durch eine kombinatorische Kategorie K_k und einer vollen Unterkategorie der sogenannten speziellen Objekte M_k realisiert. Die Definition der speziellen Objekte ist sehr technisch. Ein besseres Verständnis oder eine intrinsische Beschreibung durch kategorielle Eigenschaften von M_k könnten beispielsweise zu einer Verbesserung einer oberen Schranke für Ausnahmeprimzahlen der Modularen Lusztig-Vermutung führen.
Diese Arbeit enthält eine detaillierte Untersuchung von M k . Ein Hauptresultat ist die Beschreibung des Verhaltens der Dualität, wobei eine wichtige Klasse der speziellen Objekte aus selbstdualen Objekten besteht. Ein weiteres wichtiges Resultat ist die Beschreibung des Zentrums von M_k.

In the present thesis we study the representation theory of a symmetrizable Kac-Moody algebra. We restrict ourselves to the BGG category O, in which the simple objects are highest weight modules. In determining the characters of simple objects, the so-called Verma modules play an important role in category O. We focus our attention on w-twisted Verma modules, where w denotes an element of the Weyl group: these are objects which have the same character as ordinary Verma modules, but exhibit a different module structure.
We construct projective covers in the full subcategory of modules with a w-twisted Verma flag. In particular, we show that the category of modules with a w-twisted Verma flag contains enough projectives. With the help of these projective objects, we can determine the center of a deformed block of the category of modules with a w-twisted Verma flag. We notice that it coincides with the center of a deformed block of the larger category O. Finally, we show that a deformed block of negative level of the category of modules with a w-twisted Verma flag is equivalent to the category of sheaves with a Verma flag on a moment graph with w-twisted order. This equivalence shows, that for arbitrary Weyl group elements w the respective categories of modules with a w-twisted Verma flag are equivalent to each other: in particular also equivalent to the category of modules with a Verma flag. Thereby we can relate the multiplicities of w-twisted Verma modules in w-twisted projective covers to multiplicities of simple highest weight modules in Verma modules. This phenomenon can be considered as a w-twisted version of the BGG reciprocity theorem.

The present thesis deals with the representation theory of a symmetrizable Kac-Moody algebra. We restrict ourselves to the highest weight modules whose structure is given by the BGG category O. In the case of an affine Kac-Moody algebra, one distinguishes between representations of positive, negative and critical level. An important role for the calculation of characters of simple highest weight modules is played by the Verma modules in positive and negative level. At the critical level, it is helpful to introduce the restricted category O, a certain subcategory of the usual category O. The usual Verma modules are then replaced by restricted Verma modules that appear as maximal restricted quotients of aforementioned Verma modules.
The Jantzen filtration provides a good tool for studying simple subquotients of a Verma module. In case of a Verma module in positive level, we show that the structure of subquotients of this filtration is given by the coefficients of certain Kazhdan-Lusztig polynomials, by associating it with the Andersen filtration in negative level.
At the critical level, we define an analogue of the Jantzen filtration for restricted Verma modules and prove an alternating sum formula for it. As a corollary from this we get the `Linkage Principle', which was already proven by Arakawa and Fiebig. A special case of the sum formula for subgeneric restricted Verma modules allows us to calculate the center of a deformed block of the restricted category O.

This thesis investigates duals in tricategories.
We develop different notions of duals in general tricategories, that are motivated from geometric applications. Furthermore we show that bimodule categories over fusion categories with bimodule traces yield a tricategory with duals. The notion of bimodule traces is related to certain Frobenius algebras in the fusion categories.