Tag - Semigroup theory

Quoos Luciane: Semigroups and algebraic geometry codes

6th November, 2023

A linear code is a vector subspace of 𝔽qn, where 𝔽q is a finite field with q elements. The family of linear error-correcting codes are specially important when one is attempting to transmit messages across a noisy communication channel. Data can be corrupted in transmission or storage by a variety of undesirable phenomenon, such as radio interference, electrical noise, scratch, etc.. It is useful to have a way to detect and correct such data corruption. An error-correcting code can correct more errors larger is its minimum distance. This course aims to introduce a family of error-correcting codes, the Algebraic Geometry Codes, and show how to use the theory of semigroups to improve the minimum distance of the code. This construction of codes make use of a function field in one variable over a finite field. We will show how the local information in one or two rational places, the knowledge of the semigroup in these places, can be used to improve the minimum distance of the code.

Patricia Commins: Left regular bands with symmetry

27th October, 2023

rich connection to poset topology developed by Margolis, Saliola, and Steinberg. Many of the LRBs appearing in the literature are naturally equipped with group actions. In this talk, we will explore LRB semigroup algebras under these group actions, focusing on the structure of the invariant subalgebra and more generally, the semigroup algebra as a simultaneous representation of the group and the invariant subalgebra.  

Our primary example will be the face monoid of the braid arrangement which is acted upon by the symmetric group. Bidigare proved the invariant subalgebra of the face semigroup algebra is (anti-)isomorphic to Solomon's descent algebra. We will explore the structure of the entire semigroup algebra as a simultaneous representation of the descent algebra and the symmetric group. If time permits, we may explore how this example extends to a more general class of LRBs.

No prior knowledge of LRBs or hyperplane arrangements will be assumed!

Robert Gray: Subgroups of inverse monoids via the geometry of their Cayley graphs

4th May, 2023

In the 1960s Higman was able to characterize the finitely generated subgroups of finitely presented groups, that is, groups defined using a finite set of generators and finite set of defining relations. His result, which is called the Higman Embedding Theorem, is a key result in combinatorial group theory which makes precise the connection between group presentations and logic. In this talk I will present a result of a similar flavour, proved in recent joint work with Mark Kambites (Manchester), in which we characterise the groups of units of inverse monoids defined by presentation where all the defining relators are of the form w=1. I will explain what an inverse monoid is, the motivation for studying this class of inverse monoids, and also outline some of the geometric ideas that we developed in order to prove our results.

Marzia Mazzotta: Classification of set-theoretical solutions to the pentagon equation

17th April, 2023

The pentagon equation classically originates from the field of Mathematical Physics. Our attention is placed on the study of set-theoretical solutions of this equation, namely, maps s: X×X → X×X given by s(x, y)=(xy, θx(y)), where X is a semigroup and θx: X → X is a map satisfying two laws. In this talk, we give some recent descriptions of some classes of solutions achieved starting from particular semigroups. Into the specific, we provide a characterization of idempotent-invariant solutions on a Clifford semigroup X, that are those for which θa remains invariant on the set of idempotents E(X). In addition, we will focus on the classes of involutive and idempotent solutions, which are solutions fulfilling s2=idX×X and s2=s, respectively.

Volker Diekert: Decidability of membership problems for 2×2 matrices over ℚ

7th October, 2022

We consider membership problems in matrix semigroups. Using symbolic algorithms on words and finite automata, we prove various new decidability results for 2×2 matrices over ℚ. For that, we introduce the concept of flat rational sets: if M is a monoid and N is a submonoid, then flat rational sets of M over N are finite unions of the form L0g1L1⋯gtLt where all Li are rational subsets of N and gi ∈ M. We give quite general sufficient conditions under which flat rational sets form an effective relative Boolean algebra. As a corollary, we obtain that the emptiness problem for Boolean combinations of flat rational subsets of GL2(ℚ) over GL2(ℤ) is decidable (in singly exponential time). It is possible that such a strong decidability result cannot be pushed any further for groups sitting between GL2(ℤ) and GL2(ℚ).

We also show a dichotomy for non-trivial group extension of GL2(ℤ) in GL2(ℚ): if G is a f.g. group such that GL2(ℤ) < G ≤ GL2(ℚ), then either G ≅ GL2(ℤ) × ℤk, for some k ≥ 1, or G contains an extension of the Baumslag-Solitar group BS(1,q), with q ≥ 2, of infinite index. In the first case of the dichotomy the membership problem for G is decidable but the equality problem for rational subsets of G is undecidable. In the second case, decidability of the membership problem for rational subsets in G is open.

Our result improves various natural decidability results for 2×2 matrices with rational entries, and it also supports them with concrete complexity bounds for the first time.

Laura Ciobanu: Free group homomorphisms and the Post Correspondence Problem

19th April, 2021

The Post Correspondence Problem (PCP) is a classical problem in computer science that can be stated as: is it decidable whether, given two morphisms g and h between two free semigroups A and B, there is any non-trivial x in A such that g(x)=h(x)? This question can be phrased in terms of equalizers, asked in the context of free groups, and expanded: if the 'equalizer' of g and h is defined to be the subgroup consisting of all x where g(x)=h(x), it is natural to wonder not only whether the equalizer is trivial, but what its rank or basis might be. While the PCP for semigroups is famously insoluble and acts as a source of undecidability in many areas of computer science, the PCP for free groups is open, as are the related questions about rank, basis, or further generalizations. However, in this talk we will show that there are links and surprising equivalences between these problems in free groups, and classes of maps for which we can give complete answers.

Vladimir Shpilrain: What, if anything, can be done in sublinear time?

4th February, 2021

In his talk on September 10, 2020, Yuri Gurevich discussed some algorithms that run in linear time (in the "length" of an input). We are going to take it up a notch and discuss what can be done in sublinear time; in particular, without reading the whole input but only a small part thereof. One well-known example is deciding divisibility of a decimal integer by 2, 5, or 10: this is done by reading just the last digit. We will discuss some less obvious examples from (semi)group theory.

James East: Transformation representations of semigroups

10th December, 2020

The degree of a finite semigroup S is the minimum n such that S can be faithfully represented by transformations of an n-set. This talk will discuss some recent work calculating degrees of various classes of semigroups, including null semigroups, nilpotent semigroups, rectangular bands and sandwich semigroups. Some interesting combinatorial objects play an important role, including integer compositions and hypergraph colourings.

Viacheslav Artamonov: Polynomially complete quasigroups and their application

13th August, 2020

Polynomial completeness of a universal algebra A means that any operation on A is a composition of basic operations with a specialization of some variables. In the talk we consider algebraic properties of finite polynomially complete quasigroups, the problem of recognition of its completeness in terms of its Latin square. Basing on this approach we can construct polynomially complete quasigroups of any order greater than 32 which is a power of 2. As an application we consider cryptosystems based on quasigroups.