Large scale geometries of infinite strings

We aim to shed light on our understanding of large-scale properties of infinite strings. Say that an infinite string X has weaker large-scale geometry than that of Y if there is color preserving bi-Lipschitz map from X to Y with small distortion. This defines a partially ordered set of large-scale geometries on infinite strings. This partial order presents an algebraic tool for classification of global patterns. We prove that this partial order has a greatest element and has infinite chains and anti-chains. We study the sets of large-scale geometries of strings accepted by finite state machines. We provide an algorithm that describes large scale geometries of strings accepted by $\omega$- automata. This connects the work with the complexity theory. We prove that the quasi-isometry problem is $\Sigma_2^0$-complete, thus providing a bridge with computability theory. We build algebraic structures that are invariants of large-scale geometries. We invoke asymptotic cones, a key concept in geometric group theory, defined via model-theoretic notion of ultra-product. We study asymptotic cones of algorithmically random strings, thus connecting the topic with algorithmic randomness.