REVIEW 4 major objections 7 minor 12 references
Large Scale Geometries of Infinite Strings
T0 review · 4 major / 7 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The paper proves that for infinite strings over a finite alphabet, quasi-isometric embeddability is exactly componentwise reducibility, reducing large-scale geometry to a block-by-block colour-inclusion condition.
desk verdict A genuinely new framework for quasi-isometry of infinite strings, with a plausible central equivalence that is not yet proven as written. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing mechanism is the decomposition of any colour-preserving quasi-isometry $f:\alpha\to\beta$ into three quasi-isometric factors: a monotone injection, a monotone surjection, and a bijection, with the bijection further decomposed into finitely many atomic crossing maps. An atomic crossing map swaps two nearby positions of bounded distance and fixes everything else; it is the only source of non-monotonicity. Lemma III.10 shows such swaps preserve $\leqslant_{CR}$, and monotone quasi-isometries trivially yield witnessing partitions, so Theorem III.11 follows. The same loop-based and tree-based machinery drives the B\"uchi atlas classification and the complexity bound.
What would settle it
Examine the set $A=\{m>n \mid C(a_m)\notin C(w_{n+1}\cdots w_m)\}$ inside Lemma III.10 for an explicit quasi-isometry: find two distinct $m,m'\in A$ with $C(a_m)=C(a_{m'})$. If such a pair occurs and the claimed block inclusion $v_{n+1}\cdots v_{n+j}\sqsubseteq w_{n+1}\cdots w_{n+j}$ cannot then be closed, Theorem III.11 fails. A separate check is whether the ultrafilter set $X+i$ in the cone construction really forces colour $1$ at every power-of-two real, since the argument marks only endpoints as $1$ in the auxiliary string.
Extended reading notes
Core claim
On the paper's own terms, the discovery is Theorem III.11: for infinite strings $\alpha,\beta$ over a finite alphabet, $\alpha \leqslant_{QI}\beta$ if and only if $\alpha \leqslant_{CR}\beta$. Componentwise reducibility means that $\alpha=u_1u_2\cdots$ and $\beta=v_1v_2\cdots$ with all $|u_i|,|v_i|$ bounded by one constant and every colour appearing in $u_i$ appearing in $v_i$. The forward direction is easy; the substantive direction shows that any quasi-isometry can be massaged into this block form. The proof passes through a decomposition of an arbitrary quasi-isometry into a monotone injection, a monotone surjection, and finitely many atomic crossing maps, then shows that atomic crossing maps preserve componentwise reducibility. The same machinery supports the later claims: a short list of possible atlases for B\"uchi automata, linear-time equality of those atlases, and the $\Sigma_3^0$-completeness of the quasi-isometry problem for computable strings.
Load-bearing premise
The proof that atomic crossing maps preserve componentwise reducibility assumes that the finitely many later crossing positions it tracks all carry distinct colours; this distinctness is what bounds the search by the alphabet size. If two such positions share a colour, the bound and the transitivity argument for Theorem III.11 have no stated justification.
Editorial extensions
If this is right
- The partial order of large-scale geometries has a greatest element, uncountably many minimal elements, and both chains and antichains, so the classification of infinite strings by their global pattern is non-trivial.
- For eventually periodic strings, quasi-isometry reduces to inclusion of colour sets, giving a complete description of that part of the order.
- Every B\"uchi-recognisable language has an atlas from an explicit finite list, and equality of two such atlases is decidable in linear time.
- Quasi-isometry of computable strings is $\Sigma_3^0$-complete, while isometry is $\Pi_1^0$-complete, so the weaker geometric relation is strictly harder to detect.
- Asymptotic cones are quasi-isometry invariants, yet non-quasi-isometric strings can share a cone; under computable scaling, algorithmically random strings all have the same cone.
Reading between the lines
- If Theorem III.11 stands, the combinatorial block condition could replace metric arguments in future work: proving quasi-isometry would reduce to finding uniformly bounded block decompositions, and non-existence could be attacked through colour-set obstructions.
- The B\"uchi atlas list suggests a testable extension to richer automaton models: any formalism whose accepting runs eventually stay in a single strongly connected component should admit a similar finite case analysis.
- The cone examples indicate that, for coloured one-dimensional spaces, large-scale geometry is strictly finer than the asymptotic-cone invariant; one could test whether the two invariants coincide on the eventually periodic class, where the geometry is already fully classified.
- The cone collapse for algorithmically random strings invites a precision test: replacing the randomness notion by weaker ones under the same computable scaling would locate exactly where the cone-universality property breaks.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces colour-preserving quasi-isometries between infinite strings over a finite alphabet, viewed as coloured metric spaces on ω, and studies the induced partial order on quasi-isometry types. It claims a greatest large-scale geometry, infinite chains and antichains, and infinitely many minimal geometries. The central technical device is a combinatorial relation called componentwise reducibility (⩽_CR), and the paper asserts in Theorem III.11 that quasi-isometric embeddability (⩽_QI) is equivalent to ⩽_CR. This equivalence is then used to characterize the atlases of languages accepted by Büchi automata, yielding a linear-time decidability result for atlas equality, and to support a claimed Σ_3^0-completeness result for the quasi-isometry problem between computable strings. The final section constructs asymptotic cones for strings and studies their relation to quasi-isometry, including a Solovay-test argument that asymptotic cones of Martin-Löf random strings coincide for computable scaling factors.
Significance. The paper introduces a fresh and potentially influential framework connecting geometric group theory with formal language theory. The notion of large-scale geometry for strings, the atlas concept for languages, and the link to Büchi automata are attractive, and the claimed linear-time decidability of atlas equality contrasts sharply with the PSPACE-completeness of Büchi language equality. The results on minimal geometries, chains and antichains, and the use of Solovay tests for random strings are also interesting. However, the significance is conditional on the correctness of the central QI⇔CR bridge: several load-bearing proofs are sketched or contain gaps, and as written the main theorems are not fully certified. If the gaps are repaired, this would be a valuable contribution; in its current form the paper requires substantial revision.
major comments (4)
- [§III-A, Proposition III.8] The decomposition proof contains a type-inconsistency in the repair step. The pairs (n_i, m_i) are introduced as domain positions with f(m_i)-f(n_i)=D, but the proof then swaps colours at positions n_i and m_i in β. If n_i and m_i are positions in α, this operation is undefined on β; if they are intended to be the image positions f(n_i) and f(m_i), that notation is never introduced, and the distinctness of the swapped positions is not proved. The assertion that finitely many such swaps make g∘f monotone is also stated without proof. Since Theorem III.11 uses this decomposition as its first step, the proof of QI⇒CR is incomplete as written.
- [§III-B, Lemma III.10] The proof of Lemma III.10 assumes without justification that an atomic crossing f:β→γ can be normalized so that a_i∈u_i and b_i∈u_{i+1}; since atomic crossings act on β, these positions should lie in the v_i blocks, while u_i denote blocks of α. The proof also uses the hypothesis C(b_n)∈C(w_{n+i}) for i≥1, although under the stated crossing C(b_n) is placed in w_n, not in a later block. The bound |A|≤|Σ|-1 rests on the assertion that distinct m,m'∈A have C(a_m)≠C(a_{m'}), which is not proved and is not a consequence of the witnessing partitions or the crossing structure; colours of distinct positions can repeat. As Lemma III.10 is the transition step that makes ⩽_CR stable under atomic crossings, the proof of Theorem III.11 is not certified.
- [§V, Theorem V.2(2)] The Σ_3^0-completeness proof is explicitly informal. It says the construction can 'easily be achieved in two steps' and provides intuitive stagewise invariants, but it does not give a uniform effective construction of α_i and β_i from an index i, does not state the precise stagewise commitments that guarantee the (A_s,B_s)-quasi-isometry extensions can be continued, and does not fully prove the direction 'if W_i is infinite then α_i and β_i are not quasi-isometric'. For a completeness lower bound, a rigorous reduction is required, so this theorem is not established as written.
- [§VI, Theorem VI.4] The argument that Cone(β,F,s) has colour 1 at r=2^i conflates elements of X, which are indices n_k, with positions in β. β has a 1 only at the specific positions 2^{n_j}, not at all positions whose indices lie in X. The inclusion X+i∈F does not by itself imply that for F-many n the position round(r·2^n)=2^{n+i} is one of the 1-positions 2^{n_j}; an index shift is not a position shift. The final step choosing n_{k+1}=2n_k+2 to ensure α and β are not quasi-isometric is also merely asserted 'in the same manner as the proof of Theorem II.5' without the required calculation. This theorem therefore needs a corrected proof.
minor comments (7)
- [§I, Definition I.2] The definition of a quasi-isometry between coloured spaces is only implicit; it would help to state explicitly that the constants and the coarse surjectivity condition from Definition I.1 carry over unchanged.
- [§II-A, Lemma II.2] In the proof of Lemma II.2, the definitions of q and p are presented in the wrong order, with q referring to the not-yet-defined p; reordering the definitions would make the displayed inequalities easier to follow.
- [§II-B, Theorem II.6] The text 'the interval that corresponds to pa_n (p∈{0,1})' is a typo; it should presumably read 'the interval that corresponds to the block p^{a_n}'.
- [§III-A, Theorem III.3] In the proof of Theorem III.3, the constant A=max{|x|,|y|,|u|,|v|} can be 0 when a word is empty; since quasi-isometry constants are required to be at least 1, the proof should take A=max{1,|x|,|y|,|u|,|v|}.
- [§III-B, Lemma III.10] The proof of Lemma III.10 switches inconsistently between upper-case and lower-case notation for the colour function (C versus c); using one symbol throughout would remove ambiguity.
- [§IV, Lemma IV.4] The claim that the run can be decomposed into blocks of length at most |S| each containing a loop with both a 0 and a 1 is stated without proof; a short argument using the absence of monochromatic loops would make the lemma self-contained.
- [§VI, Definition VI.1] The colour function on the asymptotic cone is multi-valued, which is a deliberate relaxation, but the text should state explicitly that C is a relation from cone points to subsets of Σ rather than a function to Σ.
Circularity Check
No significant circularity: the QI/CR equivalence is derived from independent decompositions and does not assume its own conclusion.
full rationale
The paper's central bridge, Theorem III.11, states that α ≤_QI β implies α ≤_CR β. The proof does not use the target relation as an input: it first decomposes an arbitrary quasi-isometry via Proposition III.8 into a monotone injection, a monotone surjection, and a bijection built from atomic crossings, and then shows in Lemma III.10 that atomic crossings preserve componentwise reducibility. The converse direction, CR to QI, is an explicit construction, not a hidden restatement. No fitted parameters are renamed as predictions, no self-citation is load-bearing, and no uniqueness or structural property is imported from the authors' prior work; the cited external results (Jockusch-Soare, Rogers, Nies, Solovay tests, König's lemma) are used as standard tools and are not substitutes for the paper's own derivations. The temporary 'Postulate' in Section IV is explicitly an assumption introduced for state-space analysis and later removed via the SCC decomposition and equation (⋆), so it is a proof device rather than a circular premise. The reader-facing skepticism about Lemma III.10 and Proposition III.8 concerns unproved indexing and boundedness claims; even if those gaps are real, incompleteness or incorrectness of a proof step is not the same as circularity, because the step is not equivalent to its input by definition. The derivation chain is therefore self-contained with respect to the target claims, and no circular step can be exhibited with the required textual reduction.
Assumptions & free parameters
assumptions (5)
- standard math Non-principal ultrafilters on ω exist and contain all cofinite sets.
- standard math König's lemma: every infinite finitely branching tree has an infinite path computable from the tree via the halting set.
- standard math Martin-Löf randomness is equivalent to passing all Solovay tests.
- standard math The set Fin = {i | W_i finite} is Sigma_3^0-complete.
- domain assumption The alphabet Σ is finite with |Σ| ≥ 2, and strings are infinite words over Σ.
Cite this review
Pith. "Pith review of Large Scale Geometries of Infinite Strings." pith.science (2026). https://pith.science/paper/BCMW2EHQ
@misc{pith2026190803800,
author = {Pith},
title = {Pith review of: Large Scale Geometries of Infinite Strings},
year = {2026},
howpublished = {\url{https://pith.science/paper/BCMW2EHQ}},
note = {Machine review of arXiv:1908.03800}
}
abstract
We introduce geometric consideration into the theory of formal languages. We aim to shed light on our understanding of global patterns that occur on infinite strings. We utilise methods of geometric group theory. Our emphasis is on large scale geometries. Two infinite strings have the same large scale geometry if there are colour preserving bi-Lipschitz maps with distortions between the strings. Call these maps quasi-isometries. Introduction of large scale geometries poses several questions. The first question asks to study the partial order induced by quasi-isometries. This partial order compares large scale geometries; as such it presents an algebraic tool for classification of global patterns. We prove there is a greatest large scale geometry and infinitely many minimal large scale geometries. The second question is related to understanding the quasi-isometric maps on various classes of strings. The third question investigates the sets of large scale geometries of strings accepted by computational models, e.g. B\"uchi automata. We provide an algorithm that describes large scale geometries of strings accepted by B\"uchi automata. This links large scale geometries with automata theory. The fourth question studies the complexity of the quasi-isometry problem. We show the problem is $\Sigma_3^0$-complete thus providing a bridge with computability theory. Finally, the fifth question asks to 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. Partly, we study asymptotic cones of algorithmically random strings thus connecting the topic with algorithmic randomness.
Reference graph
Works this paper leans on
-
[1]
B. V elickovic and T. Simon. Asymptotic cones of finitely g ener- ated groups. Bulletin of the London Mathematical Society, v ol. 32, pp. 203-220 (2000)
work page 2000
-
[2]
A Dioubina, I. Polterovich, Explicit constructions of u niversal R-trees and asymptotic geometry of hyperbolic spaces, prep rint, math.DG/9904133
-
[3]
Polterovich, Structures at infinity of hyp erbolic spaces, (Russian) Uspekhi Mat
A Dioubina, I. Polterovich, Structures at infinity of hyp erbolic spaces, (Russian) Uspekhi Mat. Nauk 53 (1998), no. 5(323), 2 39- 240; translation in Russian Math. Surveys 53 (1998), no. 5, 1 093- 1094
work page 1998
-
[4]
L. V an Den Dries and A. Wilkie. On Gromov’s theorem concer n- ing groups of polynomial growth and elementary logic, Journ . of Algebra 89 (1984), 349-374
work page 1984
- [5]
-
[6]
M.Gromov, Groups of polynomial growth and expanding map s : Inst. Hautes Etudes Sci. Publ. Math. No. 53 (1981) 5375
work page 1981
-
[7]
M.Gromov, Hyperbolic groups : in Essays in Group The- ory(ed. S.M.Gersten) M.S.R.I. Publications No. 8, Springe r- V erlag (1987) 75263
work page 1987
-
[8]
M.Gromov, Asymptotic invariants of infinite groups: in G eomet- ric group theory, V ol. (eds. G.A.Niblo, M.A.Roller) LondonMath. Soc. Lecture Notes Series No. 182, Cambridge Univ. Press (19 93) 1295
Show all 12 references
-
[9]
de la Harpe, Topics in geometric group theory: Chicago Lectures in Mathematics, University of Chicago Press (2000 )
P . de la Harpe, Topics in geometric group theory: Chicago Lectures in Mathematics, University of Chicago Press (2000 )
2000
-
[10]
C. G. Jockusch and R. Soare. Π 0 1-classes and degrees of theories. Transactions of the American Mathematical Socie ty, 173, p. 3356, 1972
1972
-
[11]
A. Nies. Computability and Randomness. Oxford Univers ity Press, 2012
2012
-
[12]
H. Rogers. Theory of Recursive Functions and Effective Com- putability. MIT Press, 1987. 12
1987
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.