Abstract: The aim of these talks is to discuss the algorithms and data structures used to examine finite permutation groups, and to question where parallel processing can be a benefit. In the first talk, we'll aim to answer the following questions: How are permutations stored and multiplied on a computer? How are permutation groups stored, and how do we determine invariants such as group order? How are stabilizer subgroups computed?

Abstract: A function clone on a set D is a set of finitary operations on D which is closed under composition and which contains the projections. Every function clone carries a natural algebraic structure given by the equations that hold in the clone, as well as a natural topological structure given by pointwise convergence.
Let P be the function clone consisting of all projections on a two-element set. Given any function clone C on a countably infinite set, we compare the following questions:
1) Is there a homomorphism from C to P?
2) Is there a continuous homomorphism from C to P?
These questions have applications in constraint satisfaction. More context will be provided in the subsequent talk in the logic seminar.

Abstract: A chip-firing game on a graph G begins with a configuration (the number of 'chips' on each vertex). When a vertex 'fires', it sends a chip to each adjacent vertex, so the only rule of the game is that a vertex may 'fire' if and only if it has at least deg(v) chips. We discuss a variant of the chip-firing game, called the dollar game, in which one vertex is required to always be in debt. Using the dollar game, we form an abelian group structure K(G), called the critical group of G. We compute the order of K(G), and look at how the dollar game may be used as a tool for analyzing the structure of the group.

Abstract: There is a lot happening on the boundary between universal algebra and computer science. It is not very surprising that algebraists want to have fast algorithms. However, the connection runs in the other direction as well: It turns out that universal algebra is a very good tool for describing the complexity of the Constraint Satisfaction Problem (CSP).

An instance of the CSP asks us to decide if we can assign values to variables in such a way that a list of constraints is satisfied (examples: graph coloring, logical formula satisfiability, Sudoku). If we restrict the sort of constraints to be used, the complexity of solving the CSP can vary from polynomial to NP-complete. We will talk about how to use universal algebra to classify the complexity of many such restricted CSPs.

Abstract: Whitehead's problem is a question about abelian groups that was motivated by complex analysis via homology and eventually resolved by set theory. I use the word "resolved" rather than "solved" because it was shown that Whitehead's problem is undecidable using ordinary mathematics (ZFC). I want to discuss Whitehead's problem as an example of how Jensen's diamond principle from set theory can be applied in algebra. This week I will state Whitehead's problem and give the solution for countable groups.

Abstract: Universal Co-Algebra is a general theory of state based systems, encompassing familiar structures, such as automata, Kripke Structures, dynamical systems, stochastic automata, even topological spaces considered as doubly nondeterministic transition systems. In order to capture and generalize systems with such diverse behaviours, the mathematical language to deal with universal coalgebra is Category theory.
   The results obtained this way are very concrete: homomorphism theorems, Birkhoff style theorems, classification theorems, and they can be very elegantly derived, using only elementary categorical notions and tools.
   Universal Co-Algebra is in many ways dual to Universal Algebra, and when translating co-algebraic proofs, one even obtains elegant proofs of universal algebraic results, albeit in a more general setting than that of classical universal algebra.

Abstract: We say a finite group G is realized as a Galois group over a field K if there is a finite Galois extension L/K such that G is isomorphic to Gal(L/K). We will develop a method of checking whether a given group is realized over a given field. In particular, we will show that A_n is realized over Q.

Abstract: Supercharacters and superclasses are coarser versions of the irreducible characters and conjugacy classes of finite groups. I will discuss a supercharacter theory of the group of unipotent upper triangular matrices over a finite field. Classifying the conjugacy classes of this group is a provably 'wild' problem. By considering the orbits of a group action, conjugacy classes and characters can be clumped in a compatible manner such that the resulting superclasses and supercharacters are easily indexed. I will present this construction, as well as an analogous one for the unipotent orthogonal, symplectic and unitary groups.

Abstract: In 1979 Harold Ward introduced the so-called combinatorial degree of operations on abelian groups as a generalization of the degree of polynomials on rings. We extend his notion further to arbitrary groups. This allows us to characterize p-groups as those finite groups on which all operations have finite degree. I will prove that result using some basic facts from representation theory. As an application we obtain efficient algorithms for several computational problems (membership, size, ...) on subalgebras of powers of finite p-groups with additional operations.

Abstract: A synchronizing automaton is a finite automaton for which there is a word whose action "resets" the automaton, that is, leaves it in one particular state, no matter where it started. Such words are called reset words for the automaton. In 1968 Czerny conjectured that the maximum length of shortest reset words for synchronizing automata with n states is (n-1)^2. In this talk, I will mention some recent progress on this problem, and then describe how the problem can be viewed from a general algebra perspective, where a finite automaton is simply a unary algebra A. From this perspective, finding reset words amounts to finding constant terms in the term algebra of A, which are special elements of the one-generated free algebra over A. We will see how this observation and the Universal Algebra Calculator can be used to verify the Czerny conjecture for certain classes of automata.

Abstract: Convex subsets of affine spaces over the field R of real numbers may be described as so-called barycentric algebras. We will discuss possible extensions of the geometric and algebraic definitions of convex sets to the case of convex subsets of affine spaces over more general rings, in particular over principal ideal subdomains of R. We will discuss some of the consequences of the new definitions.

Abstract: The twentieth century saw a remarkable development and consolidation of the theory of groups and their representations. Now the theory is being extended in a number of different directions. The seminar will touch briefly on two of these, namely algebraic combinatorics and Hopf algebras, before delving more deeply into a third direction, the theory of quasigroups.

Abstract: Let R be a ring. Then R is called an E-ring provided every additive endomorphism of R is given by multiplication by a scalar (that is, if for every endomorphism f of (R, +), there exists r in R such that f(x) = rx for all x in R). Thus, in a sense, the E-rings are the rings for which all additive endomorphisms are "canonical". Such rings are well-studied in the literature. In this talk, we consider the multiplicative analog of this notion. To wit, let R be a commutative ring with identity, and let n be a positive integer. Then the power function f(x) := xⁿ is easily seen to be 0-preserving multiplicative monoid endomorphism of R. Say that a commutative ring R with identity is a P-ring provided every 0-preserving multiplicative monoid endomorphism (as above) is equal to a power function (i.e. every such endomorphism is "canonical"). We determine the P-rings up to isomorphism.

Abstract: We emphasize the old fact that -- motivated by the uniqueness of prime factorization in the integers -- divisibility, ideal and valuation theory are three faces of the same topic in the study of classical commutative rings. We also underline the importance of Gauss' Lemma in representation theory, i.e., in the construction of commutative rings with pre-described divisibility theory.

Abstract: We will consider the question of whether an infinite Boolean algebra has the maximum number of subalgebras. The general question turns out to be independent of the usual axioms of set theory. A special combinatorial assumption yields an example of a Boolean algebra with a small number of subalgebras. Large-cardinal hypotheses yield a situation where every Boolean algebra has many subalgebras. We will also consider the implications of the latter model for general algebras with countably many functions. Advance experience with Boolean algebras will not be assumed. Knowledge of forcing and advanced set-theory will not be assumed, and the talk will avoid as much as possible technical details.

Abstract: The Inverse Problem of Galois Theory is the question: Which finite groups occur as Galois groups of a Galois extension K/Q? The problem is still open. Hilbert was the first to study this problem, and proved that the symmetric and the alternating groups are Galois groups over Q. We will discuss the methods needed for proving Hilbert's results.

Abstract: We will continue the construction from last week.

Abstract: Last week we discussed that the Jacobson radical of polynomials over a ring R is equal to polynomials over a nil ideal of R. The statement that this nil ideal is the upper nil radical of R is equivalent to the Koethe conjecture. Amitsur conjectured that polynomial rings over nil rings are nil, which is a sufficient condition for the truth of the above statement. This week we will begin the construction of Agata Smuktunowicz's counter example to Amitsur's conjecture.

Abstract: The Koethe Conjecture is the statement that the sum of any two left nil ideals of a ring R is nil. I will present a result of Agata Smoktunowizc which is related to Koethe's conjecture.

Abstract: I will discuss what is known about the structure of division rings (and fields) that are stable in the model theoretic sense.

Abstract: In 1981, Brendan McKay implemented a partition backtrack approach for testing graph isomorphisms in his software program Nauty (no automorphisms yet). Ten years later, Jeffrey Leon published a series of papers documenting how partition backtrack can be used to solve permutation group problems for which no known polynomial-time solution exists. In this talk, I'll discuss an implementation of partition backtrack for permutation group problems that is scalable from serial to parallel to massively parallel systems. Examples will be given using machines in the 2.5 Gflops (commodity single core) to 175 Tflops (top 50 supercomputer) range.

Abstract: We describe a method by which each Turing machine, T, is encoded in a finite algebra, A(T). The algebra A(T) will be such that A(T) possesses certain properties if and only if T halts, thus showing that these properties are undecidable in general. Background information on Turing machines can be found in the slides from last week or on Wikipedia.

Abstract: This is the first talk in a series. The goal of the series is to address certain undecidable problems in algebra by associating to each Turing machine an algebraic structure. This talk will cover the requisite background information on Turing machines, computability, and the halting problem. No prior knowledge of computability theory will be assumed.

Abstract: In 1902, Burnside asked whether a finitely generated torsion group must be finite. Following years of positive partial results, the question was finally answered negatively by Golod and Shaferevich in 1964. Improved counterexamples have been discovered by many authors. I'll speak about the 2010 counterexample due to Jan-Christoph Schlage-Puchta.

Abstract: The basic idea behind computing a composition series for a permutation group is easy: One recursively finds normal subgroups and their corresponding quotient groups until a chain of subnormal subgroups yielding simple quotients is found. In practice, we need a structured approach to locate permutation actions that behave well and yield normal subgroups as their kernels. The O'Nan-Scott Theorem, together with reduction to the transitive and then primitive case, provides such structure. That structure, and how it may be used to create a composition series, is the subject of this talk.