Title: Genericity and randomness with ITTMs

by Benoit Monin (LACL/Créteil University) as part of Computability theory and applications

Abstract

We will talk about constructibility through the study of Infinite-Time Turing machines. The study of Infinite-Time Turing machines, ITTMs for short, goes back to a paper by Hamkins and Lewis. Informally these machines work like regular Turing machines, with in addition that the time of computation can be any ordinal. Special rules are then defined to specify what happens at a limit step of computation.

This simple computational model yields several new non-trivial classes of objects, the first one being the class of objects which are computable using some ITTM. These classes have been later well understood and characterized by Welch. ITTMs are not the first attempt of extending computability notions. This was done previously for instance with alpha-recursion theory, an extension of recursion theory to Sigma_1-definability of subsets of ordinals, within initial segments of the Godel constructible hierarchy. Even though alpha-recursion theory is defined in a rather abstract way, the specialists have a good intuition of what “compute” means in this setting, and this intuition relies on the rough idea of “some” informal machine carrying computation times through the ordinal. ITTMs appeared all the more interesting, as they consist of a precise machine model that corresponds to part of alpha-recursion theory.

Recently Carl and Schlicht used the ITTM model to extend algorithmic randomness and effective genericity notions in this setting. Genericity and randomness are two different approaches to study typical objects, that is, objects having “all the typical properties” for some notion of typicality. For randomness, a property is typical if the class of reals sharing it is of measure 1, whereas for genericity, a property is typical if the class of reals sharing it is co-meager.

We will present a general framework to study randomness and genericity within Godel’s constructible hierarchy. Using this framework, we will present various theorems about randomness and genericity with respect to ITTMs. We will then end with a few exciting open questions for which we believe Beller Jensen and Welch’s forcing technique of their book “coding the universe” should be useful.

Title: Totally disconnected locally compact groups and the scale

by George Willis (University of Newcastle) as part of Topological Groups

Lecture held in Elysium.

Abstract

The scale is a positive, integer-valued function defined on any totally disconnected, locally compact (t.d.l.c.) group that reflects the structure of the group. Following a brief overview of the main directions of current research on t.d.l.c. groups, the talk will introduce the scale and describe aspects of group structure that it reveals. In particular, the notions of tidy subgroup, contraction subgroup and flat subgroup of a t.d.l.c. will be explained and illustrated with examples.

Title: Computing descending sequences in linear orderings

by Jun Le Goh (University of Wisconsin) as part of Computability theory and applications

Abstract

Let DS be the problem of computing a descending sequence in a given ill-founded linear ordering. We investigate the uniform computational content of DS from the point of view of Weihrauch reducibility, in particular its relationship with the analogous problem of computing a path in a given ill-founded tree (known as choice on Baire space).

First, we show that DS is strictly Weihrauch reducible to choice on Baire space. Our techniques characterize the problems which have codomain N and are Weihrauch reducible to DS, thereby identifying the so-called first-order part of DS.

Second, we use the technique of inseparable $Pi^1_1$ sets (first used by Angles d’Auriac, Kihara in this context) to study the strengthening of DS whose inputs are $Sigma^1_1$-codes for ill-founded linear orderings. We prove that this strengthening is still strictly Weihrauch reducible to choice on Baire space.

This is joint work with Arno Pauly and Manlio Valenti.

Title: Locally Compact Contraction Groups

by Helge Glöckner (Universität Paderborn) as part of Topological Groups

Lecture held in Elysium.

Abstract

Consider a locally compact group $G$, together with an automorphism $alpha$ which is $contractive$ in the sense that $alpha^nrightarrow{rm id}_G$ pointwise as $ntoinfty$. Siebert showed that $G$ is the direct product of its connected component $G_e$ and an $alpha$-stable, totally disconnected closed subgroup;

moreover, $G_e$ is a simply connected, nilpotent real Lie group.

I’ll report on research concerning the totally disconnected part, obtained jointly with G. A. Willis.

For each totally disconnected contraction group $(G,alpha)$, the set ${rm tor} G$ of torsion elements is a closed subgroup of $G$. Moreover, $G$ is a direct product

$$G=G_{p_1}times cdotstimes G_{p_n}times {rm tor} G$$ of $alpha$-stable $p$-adic Lie groups $G_p$ for certain primes $p_1,ldots, p_n$ and the torsion subgroup. The structure of $p$-adic contraction groups is known from the work of J. S. P. Wang; notably, they are nilpotent. As shown with Willis, ${rm tor} G$ admits a composition series and there are countably many possible composition factors, parametrized by the finite simple groups. More recent research showed that there are uncountably many non-isomorphic torsion contraction groups, but only countably many abelian ones. If a torsion contraction group $G$ has a compact open subgroup which is a pro-$p$-group, then $G$ is nilpotent. Likewise if $G$ is locally pro-nilpotent.

Title: Group dualities: G-barrelled groups

by Elena Martín-Peinador (University of Madrid) as part of Topological Groups

Lecture held in Elysium.

Abstract

A natural notion in the framework of abelian groups are the group dualities. The most efficient definition of a group duality is simply a pair $(G, H)$, where $G$ denotes an abstract abelian group and $H$ a subgroup of characters of $G$, that is $H leq {rm Hom}(G, mathbb T)$. Two group topologies for $G$ and $H$ appear from scratch in a group duality $(G, H)$: the weak topologies $sigma(G, H)$ and $sigma (H, G)$ respectively. Are there more group topologies either in $G$ or $H$ that can be strictly related with the duality $(G, H)$? In this sense we shall define the term “compatible topology” and loosely speaking we consider the compatible topologies as members of the duality.

The locally quasi-convex topologies defined by Vilenkin in the 50′s form a significant class for the construction of a duality theory for groups. The fact that a locally convex topological vector space is in particular a locally quasi-convex group serves as a nexus to emulate well-known results of Functional Analysis for the class of topological groups.

In this talk we shall

deal with questions of the sort:

Under which conditions is there a locally compact topology in a fixed duality?

The same question for a metrizable, or a $k$-group topology.

We shall also introduce the $g$-barrelled groups, a class for which the Mackey-Arens Theorem admits an optimal counterpart. We study also the existence of $g$-barrelled topologies in a group duality $(G, H)$.

Title: Redundancy of information: lowering effective dimension

by Joe Miller (University of Wisconsin) as part of Computability theory and applications

Abstract

A natural way to measure the similarity between two infinite

binary sequences X and Y is to take the (upper) density of their

symmetric difference. This is the Besicovitch distance on Cantor

space. If d(X,Y) = 0, then we say that X and Y are coarsely

equivalent. Greenberg, M., Shen, and Westrick (2018) proved that a

binary sequence has effective (Hausdorff) dimension 1 if and only if

it is coarsely equivalent to a Martin-Löf random sequence. They went

on to determine the best and worst cases for the distance from a

dimension t sequence to the nearest dimension s>t sequence. Thus, the

difficulty of increasing dimension is understood.

Greenberg, et al. also determined the distance from a dimension 1

sequence to the nearest dimension t sequence. But they left open the

general problem of reducing dimension, which is made difficult by the

fact that the information in a dimension s sequence can be coded (at

least somewhat) redundantly. Goh, M., Soskova, and Westrick recently

gave a complete solution.

I will talk about both the results in the 2018 paper and the more

recent work. In particular, I will discuss some of the coding theory

behind these results. No previous knowledge of coding theory is

assumed.