Information Coded in Mathematical Structures

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

Mathematical logic uses mathematical tools in an introspective way to study mathematics itself. This project will use the tools of mathematical logic (and computability theory in particular) to study the way that information can be coded into mathematical structures of the types that arise in all areas of mathematics. The general paradigm is that information is encoded into a mathematical structure if it can always be recovered in an intrinsic way from the structure, without artifacts from the way that the structure is presented. For the simplest kinds of information, like a string of 0's and 1's, the situation is well-understood. But for more complex kinds of information, the situation is much less well-understood and there are many interesting phenomena to explore. Understanding the coding of information will help us understand both the nature of information and the ability of structures of various kinds to code information. This, in turn, informs and guides the mathematical practice of other mathematicians. This project includes the training of undergraduate and graduate students and outreach to high schools. More formally, we say that a piece of information A is coded in a structure B if from every copy of the structure, we can recover in a computable way a copy of the information A. For example if B is a countably infinite group then a copy of B is a Cayley table for the group, noting that for an infinite group there are many different Cayley tables obtained by listing the elements of the group in different orders. By a piece of information we mean, in order of increasing complexity, a binary string (or subset of the natural numbers), an infinite family of binary strings, an infinite tree, or some other structure. For the first case of a binary string, there is a good structural characterisation of when a structure codes a binary string; one can interpret this as saying that there is always a good reason for a binary string to be coded by a structure. This is not the case for any more of the more complicated types of information; it seems that there are structures which happen to code information, but there is no good structural reason as to why. This project aims to explore these phenomena and push them to their limit with one aim being to give new tools to attack difficult open problems on degree spectra which have been resistant to current techniques. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.