PoPMiNE 2004: talks and abstracts

June 25, 2004

1 Invited talk

Dr Ian McIntosh – University of York Geometry and computer vision

The talk will introduce one of the central problems of computer vision and consider one approach to solving it using the sort of mathematics which geometers have found successful in the past, namely, the calculus of variations and heat flow. Since the emphasis is on computable solutions, I will explain what the discrete version of heat flow is.

2 Contributed talks

Robert Bailey – Queen Mary, University of London Codes from permutation groups

Traditional error-correcting codes are vector spaces over finite fields. We replace these with permutation groups, where the transmitted codewords are group elements written in “passive form”, i.e. the images of 1, …, n written in order. A particular class of permutation groups, which we call base transitive, is particularly useful.

These in turn require a different decoding algorithm, which introduces the concept of an uncovering-by-bases. Depending on the structure of the group, this may take one of various quite different forms, but each makes use of particular combinatorial objects, such as covering designs, Hadamard matrices, and even some error-correcting codes.

Alan Cain – University of St. Andrews Malcev presentations A Malcev presentation is a special type of presentation for a semigroup that embeds in a group. Malcev presentations were introduced by J.-C. Spehner in 1977, but are related to earlier work by A.I. Malcev on the embeddability of semigroups into groups. This talk will give an introduction to Malcev presentations and then discuss recent developments in the area. These developments include:

• the discovery of groups whose finitely generated subsemigroups all have finite Malcev presentations;

• confirmation that finitely generated subsemigroups of coherent groups need not admit finite Malcev presentations;

• links with the theory of automatic semigroups.

Yemon Choi – University of Newcastle upon Tyne Perturbations and normed cohomology

We give an overview of some topics that fall into the broad class of “perturbation of normed algebraic structures”. Our motivating example is the problem of “stability of multiplication” on a Banach algebra, for which partial results have been obtained using a suitable version of Hochschild cohomology (Raeburn and Taylor, 1977; B.E. Johnson 1977).

If time permits we will briefly discuss problems with a similar flavour, such as quasicharacters on discrete groups, almost multiplicative functionals on commutative Banach algebras, and an old result of Kalton and Roberts on “approximately additive set functions”. No previous knowledge of cohomology or Banach algebras will be assumed; our aim is to present several telling examples rather than an all-encompassing theory.

Matt Daws – University of Leeds Nonstandard analysis

Nonstandard Analysis is a logically consistent way of introducing “infinitesimals”. Once we have infinitesimals, we can develop calculus in an intuitive manner; for example, a function is continuous if and only if it takes infinitesimal perturbations to infinitesimal perturbations.

We will give an introduction to Nonstandard Analysis, presenting a concrete approach using ultrafilters. No knowledge of “higher-order languages” will be needed, and this should allow anyone with a basic background in analysis to follow the talk. The aim is to give a proof of the Intermediate Value Theorem.

Robert Gray – University of St. Andrews Generating sets of ideals in endomorphism monoids

For any mathematical structure M, the set of endomorphisms, End(M) is closed under composition and forms a monoid (a semigroup with identity). When M is simply a finite set of size n, then End(M) ≅ T_{n} the full transformation semigroup. It is known that the proper two-sided ideals of T_{n}, namely the semigroups K(n, r) = {α ∈ T_{n} : |Im(α)| ≤ r : 1 ≤ r < n}, are generated by idempotents (elements that satisfy α^{2} = α). In 1990 Howie and McFadden proved that the smallest number of idempotents required to generate this semigroup, its idempotent rank, is S(n, r) (the Stirling number of the second kind).

A number of other structures M are known to have the property that the proper two-sided ideals of End(M) are idempotent generated. In particular it was proven that End(M) has this property when M is a finite dimensional vector space (Erdos, 1967, and Dawlings, 1981), when M is a finite dimensional independence algebra, a concept which generalizes sets and vector spaces (Fountain and Lewin, 1990) and when M is a finite chain (Gurba, 1990). In this talk I will describe how we can prove new results in this area by considering ranks and idempotent ranks of arbitrary 0-Rees matrix semigroups. In particular we prove the corresponding result to that of Howie and McFadden in the case where M is a finite vector space.

James Grime – University of York Irreducible representations of S_{n} and the fusion procedure

I will begin by describing how Young symmetrizers and left ideals of the group algebra can give the irreducible representations of the symmetric group. I will then present my description of the diagonal matrix element from which we may obtain such ideals.

Elizabeth Kimber – University of St. Andrews Generalized cyclic presentations

Every finite abelian group has a generalized cyclic presentation (GCP), so a natural question to ask is when does G × H have a GCP if G is abelian and H is non-abelian? This talk will include some example based partial anwers to this question. A further question is when does a finite abelian group have a GCP on a minimum generating set? A classification for finite abelian groups of ranks two, three, and four will be given. This uses a result by Miklós Abért on symmetric presentations of finite abelian groups.

Luda Markus – Bar-Ilan University, Israel Automata and algorithms for subgroups of amalgamated free products

In the 1980’s Stallings showed that every finitely generated subgroup of a free group is canonically represented by a finite minimal immersion of a bouquet of circles. In terms of the theory of automata, this is a minimal finite inverse automaton. This allows for the deep algorithmic theory of finite automata and finite inverse monoids to be used to answer questions about finitely generated subgroups of free groups.

In the first part of the talk, we review the theory for the free group and discuss a number of algorithmic problems solved by these methods, including the membership problem and the finite index problem.

In the second part, we look at applying the same methods to other classes of groups. A fundamental new problem is that the Stallings folding algorithm must be modified to allow for “sewing” on relations of nonfree groups. We look at the class of groups that are amalgams of finite groups or amalgams of free groups over a maximal cyclic subgroup: since these groups are locally quasiconvex, all finitely generated subgroups are represented by finite automata. We give an algorithm to compute such a finite automaton and use it to solve various algorithmic problems.

Joachim M. Mouanda – University of Newcastle upon Tyne The Fejér-Riesz theorem: factorising trigonometric polynomials

The factorization of nonnegative functions has a long and illustrious history. In 1915, Fejér and Riesz proved that every positive trigonometric polynomial defined on the dual group of Z with complex coefficients can be factored in terms of analytic trigonometric polynomials. In 1968, Marvin Rosenblum proved the operator version and in 2000 Michael Dritschel provided a new proof of the operator version.

Lizzie Wharton – St, Hugh’s College, Oxford University Quasivarieties and universal closures

We define universal theory and quasi-identities and give examples of the classes of groups these define. We discuss some groups for which explicit descriptions of quasi-identities and universal sentences can be given. We also describe the groups that are contained in the universal closures of, and in the quasivarieties generated by, these groups.