{"id":4549,"date":"2021-12-20T09:46:46","date_gmt":"2021-12-20T08:46:46","guid":{"rendered":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=4549"},"modified":"2022-11-19T14:56:36","modified_gmt":"2022-11-19T13:56:36","slug":"statures-and-dimensions-of-spaces-of-trees-of-infinite-words","status":"publish","type":"page","link":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=4549","title":{"rendered":"Statures and dimensions of spaces of trees, of infinite words"},"content":{"rendered":"\n

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

The main theme of this research is: given a construction X<\/em>\u225dC<\/em>(X<\/em>1<\/sub>,…,Xn<\/sub><\/em>) of a Noetherian space from Noetherian spaces X<\/em>1<\/sub>,…,Xn<\/sub><\/em>, determine the dimension and stature of X<\/em> as a function of those of X<\/em>1<\/sub>,…,Xn<\/sub><\/em>, if that is possible, and give optimal lower and upper bounds otherwise.<\/p>\n\n\n\n

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

Among the constructions that have been left unexplored yet, we find:<\/p>\n\n\n\n

    \n
  1. The space T<\/strong>(X<\/em>) of finite trees, with the tree topology (Definition 9.7.39 in the book<\/a>). 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<\/strong>(X<\/em>) 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 \u03b8<\/em> 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\u00fctte’s Klammersymbole (of which the best explanation I know of can be found here<\/a>).<\/li>\n\n\n\n
  2. The space of finite and infinite<\/em> words over X<\/em> [6]. I expect this case to be a grueling adaptation of [5, Section 12], without much invention, but requiring a lot of work.<\/li>\n\n\n\n
  3. The space of what I call transfinite<\/em> words over X<\/em>. The infinite words I alluded to above are words of length \u03c9. I reserve the terme “transfinite” to denote words of arbitrary ordinal length. The space of transfinite words over X<\/em> (of length bounded by an arbitrarily high ordinal) is also Noetherian (unpublished work with Simon Halfon<\/a> and Aliaume Lopez<\/a>), and this is obtained by giving an explicit upper bound on its stature. One may wonder whether that upper bound is optimal.<\/li>\n\n\n\n
  4. Then, there are many other variants on the theme of trees. With T<\/strong>(X<\/em>), each vertex has a finite word<\/em> 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<\/em>. Then there are 3-trees, which are tree-like structures where arguments are arranged as 2-trees, and so on. Aliaume Lopez<\/a> has a general theorem that says that, given a Noetherian-preserving construction X<\/em> \u21a6 C<\/em>(X<\/em>) that satisfies a form of uniformity, the space of trees with arguments organized as a C<\/em>(.<\/em>) 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<\/em>(.) for arguments has already been investigated in the case of countable well-partial-orders [8].<\/li>\n<\/ol>\n\n\n\n

    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.<\/p>\n\n\n\n

    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.<\/p>\n\n\n\n

      \n
    1. Andreas Blass, Yuri Gurevich. Program Termination and Well Partial Orderings<\/a>. ACM Transactions on Computational Logic 9(3) Art.18, 2008.<\/li>\n\n\n\n
    2. Alain Finkel and Jean Goubault-Larrecq. Forward analysis for WSTS, part I: Completions<\/a>. Mathematical Structures in Computer Science, 30(7):752\u2013832, 2020.<\/li>\n\n\n\n
    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\u2013207, 1977.<\/li>\n\n\n\n
    4. Diana Schmidt. Well-partial orderings and their maximal order types. Habilitation, University of Heidelberg, Heidelberg, 1979.<\/li>\n\n\n\n
    5. Jean Goubault-Larrecq and Bastien Laboureix. Statures and dimensions of Noetherian spaces. arXiv report 2112.06828<\/a>, 2021.<\/li>\n\n\n\n
    6. Jean Goubault-Larrecq. Infinitary Noetherian constructions I. Infinite words<\/a>. Colloquium Mathematicum, 2021, in press.<\/li>\n\n\n\n
    7. Ryu Hasegawa. Two applications of analytic functors<\/a>. Theoretical Computer Science<\/a> 272(1-2)<\/a>:113\u2013175, 2002.<\/li>\n\n\n\n
    8. Andreas Weiermann. A computation of the maximal order type of the term ordering on finite multisets<\/a>. CiE ’09: Proceedings of the 5th Conference on Computability in Europe: Mathematical Theory and Computational Practice<\/a>, pages 488\u2013498, 2009.<\/li>\n<\/ol>\n\n\n
      \n
      \"jgl-2011\"<\/figure>\n<\/div>\n\n\n

      \u2014 Jean Goubault-Larrecq<\/a> (December 20th, 2021)<\/p>\n","protected":false},"excerpt":{"rendered":"

      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 … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_crdt_document":"","footnotes":""},"class_list":["post-4549","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/4549","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4549"}],"version-history":[{"count":7,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/4549\/revisions"}],"predecessor-version":[{"id":5882,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/4549\/revisions\/5882"}],"wp:attachment":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4549"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}