Page de maths de Thierry Monteil


  contact ::
  thèmes de recherche ::
  papiers ::
  thèse ::
  séminaires (photos) ::
  m2 ::
  admin ::
  blog ::
  liens ::
  english

Blog -- About the complexity of infinite permutations

Introduction

A $\mathbb{N}-$ permutation is a total order $\prec$ on $\mathbb{N}$ . We can also define $\mathbb{Z}-$ permutations.

Equivalently, a $\mathbb{N}-$ permutation is an injective map $\alpha$ from $\mathbb{N}$ to $\mathbb{R}$ , where two maps $\alpha$ and $\beta$ are identified if

$(\forall (i,j)\in\mathbb{N}^2 )(\alpha(i)<\alpha(j) \Leftrightarrow \beta(i)<\beta(j)).$

Indeed, any infinite countable total order is isomorphic to a subset of $(\mathbb{R},<)$ and $\alpha$ allows to pull it back as a total order $\prec$ on $\mathbb{N}$ .

In the paper [1], Dmitri Fon-Der-Flaass and Anna Frid introduced a notion of complexity for infinite permutations, this is a verbatim transposition of the notion of complexity that exists for infinite words:

Let $\prec$ be a $\mathbb{N}-$ permutation. For each couple $(k,n)$ of integers, we can consider the linear ordering induced by $\prec$ on the set $\{k,k+1,\dots,k+n-1\}$ : it can be interpreted as an element $\sigma_{\prec}(k,n)$ of the symmetric group $S_n$ (the $\sigma$ that satisfies $\sigma(0)+k \prec \sigma(1)+k \prec \dots \prec \sigma(n-1)+k$ ). The complexity of $\prec$ is the function that maps each positive $n$ to the number $p_{\prec}(n) = card \{\sigma_{\prec}(k,n) | k \in \mathbb{N} \}$ .

In particular, they prove that:

A $\mathbb{N}-$ permutation $\prec$ has a bounded complexity iff it is ultimately T-periodic for some T>0 :

$(\exists N\in\mathbb{N}) (\forall i,j \geq N) (i \prec j \Leftrightarrow i+T \prec j+T )$

There exists non ultimately periodic $\mathbb{N}-$ permutations whose complexity grows arbitrary slow to infinity.
A non-periodic $\mathbb{Z}-$ permutation has at least a linear complexity.

The complexity of infinite words is a widely used notion, in symbolic dynamics for example, it allows to define the topological entropy of a subshift and a linear complexity leads to some explicit bounds of the number of ergodic invariant measures of a subshift as well as an insurance for the lack of strong mixing (assuming unique ergodicity).

Note that in the definition of the complexity, there are in fact two orders in game, the canonical order $<$ on $\mathbb{N}$ that will be called the domain order, and $\prec$ that will be called the range order (because of the second definition involving $\alpha$ ).

A question

A question that seems natural is the following : "what does the complexity of an infinite permutation tell us about the order type of $\prec$ " (i.e. when we forget the labelling with $\mathbb{N}$ ). Other formulation : "if $\sigma$ is a bijection of $\mathbb{N}$ , what is the connection between the complexity of the infinite permutation $\alpha$ and the one of $\alpha\circ\sigma$ ?"

A first simple remark is the following : any countable total order admits a labelling whose complexity is $n!$ (the maximal complexity where any finite permutation appear). Such an increase of complexity can be viewed as an artifact due to the noisy labelling, and we want to look at the intrinsic complexity of the order type of $\prec$ .

So let's have a look to the other side: given a countable order type, what is the smallest complexity that we can reach among all labellings?

Let us describe the Hausdorff derivation on the (countable) total orders (see for example [2]): if $(E,<)$ is a total order, we can define an equivalence relation on $E$ by setting $x\sim y$ if and only if the segment $<a href=$ x,y" alt="x,y" align="absmiddle"> is finite. The order $<$ on $E$ induces a natural order on $\partial(E)=E/\sim$ so you can iterate the process and define the nth derivative $\partial^n(E)$ for any integer $n$ . There is also a limit process: we can identify two elements of $E$ if there exists an integer $n$ such that they belong to the same "nth iterated class" in $\partial^n(E)$ : this allows us to define $\partial^{\omega}(E)$ . Iterating again, we can define $\partial^o(E)$ for any (countable) ordinal $o$ . If there exists a ordinal $o$ such that $\partial^o(E)$ is a singleton we will say that $E$ is scattered and the smallest such $o$ will be called the rank of $E$ . Scattered orders are exactly those in which the order type of the rationals does not embed. The rank behaves well with the embedding notion and any countable total order embeds in the rationals, in this sense, we can say that the set of rational numbers with its natural order is the most complex countable total order.

The total orders that admit a bounded complexity (i.e. that arise as the range order of some ultimately periodic infinite permutation) are more or less the orders of rank less than or equal to 2: not bad (to be more precise, the total orders that admit a bounded complexity are the orders $(E,<)$ such that $\partial(E)$ is finite, but it is easy to define the f-rank as being the smallest ordinal $o$ such that $\partial^o(E)$ is finite, so the rank and the f-rank differ by at most 1). Does complexity allow us to grasp scattered orders?

Unfortunately, we can construct an infinite permutation whose range order is the chain of rationals and whose complexity is at most linear: Let $\varphi$ be a sequence of positive integers that grows very fast. We define a $\mathbb{N}-$ permutation $\alpha:\mathbb{N}\to\mathbb{Q}$ as follows: $\alpha$ sends the $\varphi(0)$ first integers increasingly into the positive rationals, then it sends the next $\varphi(0)$ integers increasingly into the non-positive rationals, then it sends the next $\varphi(1)$ increasingly into the positive rationals, it sends the next $\varphi(1)$ integers increasingly into the non-positive rationals, and so on... You can do this in such a way that the map $\alpha$ is a bijection. Now, let $n$ be a positive integer. If $k$ is greater than $2\sum_{i=0}^{l-1}\varphi(i)$ , for some $l$ satisfying $\varphi(l)\geq n$ , then the associated element $\sigma(k,n)$ of $S_n$ is just one of the cycle $x\mapsto x+t \mbox{ mod } n$ ):

Hence, we are controlling all but the first $2\sum_{i=0}^{l-1}\varphi(i)$ $k$ 's, so $p_{\alpha}(n)\leq n + 2\sum_{i=0}^{l-1}\varphi(i)$ , that is linear provided $\varphi$ has exponential grow (we chose the smallest admissible $l$ ).

This is due to the fact that, even if $\alpha$ has to knit a lot to cover $\mathbb{Q}$ , we have been able to slow down the complexity by spacing the problems ( $\varphi$ acts as a delay). For example, since $\mathbb{Q}$ is a dense total order, there must be $k_1<k_2<k_3<k_4$ in $\mathbb{N}$ such that $\alpha(k_1)<\alpha(k_3)<\alpha(k_2)<\alpha(k_4)$ in $\mathbb{Q}$ but the permutation 1324 will not appear as a $\sigma(k,4)$ since the $k_i$ can not be consecutive. Hence, the complexity is not able to grasp long distance knitting: to become aware of the relation that exists between $\alpha(1)$ , $\alpha(100)$ , $\alpha(1000)$ and $\alpha(10000)$ , we have to wait until $p_{\prec}(10000)$ even if it concerns the relation between 4 elements only.

To solve this problem, we can introduce another notion of complexity that assigns to any integer $n$ the total number of permutations $\sigma_{\prec}(k_1,k_2,\dots,k_n)\in S_n$ induced by $\prec$ on the subsets $\{k_1<k_2<\dots<k_n\}$ of $\mathbb{N}$ . With such a definition of complexity, any permutation whose range order is non-scattered has complexity $n!$ . Also, this complexity is very explosive, for example any $\mathbb{N}-$ permutation whose range order has no maximum and no minimum has complexity at least $2^{n-1}$ , this bound is reached with the permutation given by $\alpha(2n)=n+1$ and $\alpha(2n+1)=-n-1$ .

It is tautological to say that a $\mathbb{N}-$ permutation is a couple $(<,\prec)$ of total orders on $\mathbb{N}$ such that $<$ is the canonical order, but such a definition gives more symmetry between the two orders in game. With such a point of view, the complexity we just introduced is the profile of the relational structure $(\mathbb{N},<,\prec)$ (see [3] for a survey about the profile of relations).

A more general question in that direction suggested by Maurice Pouzet can be to describe the possible profiles of the bichains (i.e. the triples $(V,<_1,<_2)$ such that $<_1$ and $<_2$ are total orders on the set $V$ ).

An example

Let us consider the Sharkovsky ordering:

 3 < 5 < 7 < 9 < 11 ... 2.3 < 2.5 < 2.7 < 2.9 ... < 2^2.3 < 2^2.5 < 2^2.7 ...  .... ... 2^4 < 2^3 < 2^2 < 2 < 1

It is a simple labelling on the chain $\omega.\omega+\omega^*$ whose rank is 3 (the f-rank is 2), whose complexity is linear (it is non-decreasing and satisfies $p(2n) = 2 p(n)$ ), and whose profile is $n!$ . In fact any labelling of $\omega.\omega+\omega^*$ will lead to a profile equal to $n!$ , we can interpret this by saying that $\omega$ and $\omega.\omega+\omega^*$ are not correlated.

Is it true that any bichain whose order type $(<_1,<_2)$ is such that $<_1$ and $<_2$ do not have the same f-rank should have a profile equal to $n!$ ?

References

Dmitri G. Fon-Der-Flaass and Anna E. Frid (2005), On infinite permutations, in 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), Stefan Felsner (ed.), Discrete Mathematics and Theoretical Computer Science Proceedings AE, pp. 267-272
Antonio Montalbán, On the equimorphism types of linear orderings, to appear in the Bulletin of Symbolic Logic.
Maurice Pouzet, The Profile of relations, Global Journal of Pure and Applied Mathematics, Volume 2 Number 3 (2006).


    Page web propulsée par nilcms. Pour une validation stricte, débrouillez-vous.


[ Wiki ::
	WildSurfaces -
	BwataBaire -
	Substitutions -
	CellularAutomata -
	LMA -
	Ecool
]