Statures and dimensions of spaces of trees, of infinite words

In a previous open question, I asked whether one could compute the ordinal rank of the sobrification SX of a Noetherian space X, and the ordinal rank of the lattice HX of closed subsets of X, for various kinds of Noetherian spaces X. This was solved by Bastien Laboureix and me [5]. We now call the rank of SX the dimension dim X of X, because it somehow generalizes the notion of Krull dimension of a Noetherian commutative ring; and we call the ordinal rank of HX (minus 1) the stature ||X|| of X, generalizing the notion of the same name in the theory of well-partial-orderings [1].

The main theme of this research is: given a construction X≝C(X1,…,Xn) of a Noetherian space from Noetherian spaces X1,…,Xn, determine the dimension and stature of X as a function of those of X1,…,Xn, if that is possible, and give optimal lower and upper bounds otherwise.

For example, given any Noetherian space X, we can form the construction X* of all finite words on X, with the word topology (Definition 9.7.26 in the book). Then, and assuming X non-empty, ||X*||=ωω||X||’, where the notation α’ denotes α–1 if α is a finite ordinal, α+1 if α is a critical ordinal plus a natural number, and α otherwise; while dim X*=ωdim Xo, where the notation αo denotes α+1 if α is a critical ordinal plus a natural number, and α otherwise. The formula for ||X*|| confirms and extends a formula obtained by Schmidt [4], closing research by de Jongh and Parikh [3], on well-partial-orderings.

Among the constructions that have been left unexplored yet, we find:

  1. The space T(X) of finite trees, with the tree topology (Definition 9.7.39 in the book). This promises to be much harder than the case of words [5, Section 12], because the tree regular expressions representing the irreducible closed subsets of T(X) are pretty complex [2, Section 11]. This also promises to be hard because of the complexity of the ordinal notation system that would be required. There is a pretty simple one, the θ notation of Rathjen and Weiermann, but it is limited to countable ordinals; I am afraid that one would have to follow Schmidt [4] and use Schütte’s Klammersymbole (of which the best explanation I know of can be found here).
  2. The space of finite and infinite words over X [6]. I expect this case to be a grueling adaptation of [5, Section 12], without much invention, but requiring a lot of work.
  3. The space of what I call transfinite words over X. The infinite words I alluded to above are words of length ω. I reserve the terme “transfinite” to denote words of arbitrary ordinal length. The space of transfinite words over X (of length bounded by an arbitrarily high ordinal) is also Noetherian (unpublished work with Simon Halfon and Aliaume Lopez), and this is obtained by giving an explicit upper bound on its stature. One may wonder whether that upper bound is optimal.
  4. Then, there are many other variants on the theme of trees. With T(X), each vertex has a finite word of arguments. We may consider trees where arguments are arranged as finite multisets instead, namely whose order does not matter. We may consider trees whose arguments are arranged as… trees; let me call those new trees 2-trees. Then there are 3-trees, which are tree-like structures where arguments are arranged as 2-trees, and so on. Aliaume Lopez has a general theorem that says that, given a Noetherian-preserving construction X ↦ C(X) that satisfies a form of uniformity, the space of trees with arguments organized as a C(.) of subtrees is Noetherian. Similar, but less general constructions already exist on well-quasi-orders [7], and the question of statures of trees parameterized by a construction C(.) for arguments has already been investigated in the case of countable well-partial-orders [8].

Those questions are difficult. Most of them are reserved to excellent PhD students, to the exception of question 2 (infinite words), which can be addressed by a gifted M2 (masters, second year) student.

None of these questions have direct applications, either in computer science or in mathematics, for now (as of 2021). If you are interested in any of those questions, you should keep that in mind; if you wish to obtain a position after your PhD, you should prefer research topics which have applications, and which the research community is interested in.

  1. Andreas Blass, Yuri Gurevich. Program Termination and Well Partial Orderings. ACM Transactions on Computational Logic 9(3) Art.18, 2008.
  2. Alain Finkel and Jean Goubault-Larrecq. Forward analysis for WSTS, part I: Completions. Mathematical Structures in Computer Science, 30(7):752–832, 2020.
  3. Dick Herman Jacobus de Jongh and Rohit Parikh. Well-partial orderings and hierarchies. Nederl. Akad. Wetensch. Proc. Ser. A 80=Indag. Math., 39(3):195–207, 1977.
  4. Diana Schmidt. Well-partial orderings and their maximal order types. Habilitation, University of Heidelberg, Heidelberg, 1979.
  5. Jean Goubault-Larrecq and Bastien Laboureix. Statures and dimensions of Noetherian spaces. arXiv report 2112.06828, 2021.
  6. Jean Goubault-Larrecq. Infinitary Noetherian constructions I. Infinite words. Colloquium Mathematicum, 2021, in press.
  7. Ryu Hasegawa. Two applications of analytic functors. Theoretical Computer Science 272(1-2):113–175, 2002.
  8. Andreas Weiermann. A computation of the maximal order type of the term ordering on finite multisets. CiE ’09: Proceedings of the 5th Conference on Computability in Europe: Mathematical Theory and Computational Practice, pages 488–498, 2009.
jgl-2011

— Jean Goubault-Larrecq (December 20th, 2021)