{"id":"1f3ea188-d0d3-41f5-a32c-3f8ba91b5760","arxiv_id":"1908.03800","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Introduces quasi-isometry types of infinite strings as a classification tool and characterizes the atlases of Buchi-recognizable languages.","lead":"This paper applies geometric group theory, specifically quasi-isometry, to classify infinite strings by their large-scale patterns. It proves structural results about the resulting partial order and links the classification to automata theory, computability, and algorithmic randomness.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The QI=CR bridge is not yet proven: Lemma III.10's Claim and its |A| bound are asserted rather than derived, and Proposition III.8 contains a type-inconsistent repair step.","rationale":"The reader correctly identified Lemma III.10 as the load-bearing point, but the specific step singled out — the bound |A| ≤ |Σ| − 1 — is actually fixable: if m < m′ and C(a_m) = C(a_{m′}), then the colour C(a_m) is placed by the atomic crossing into w_{m+1}, hence into w_{n+1}...w_{m′}, contradicting m′ ∈ A; similarly C(a_m) ≠ C(a_n) for m ∈ A. So the distinctness assertion can be supplied from the definitions. The deeper problem is that the Claim itself is written with an apparent index shift: under the stated normalization, C(b_n) appears in w_n, not in w_{n+i} for i ≥ 1, while C(a_n) appears in w_{n+1}. This makes the iterative step, and hence the transitivity argument for ⩽_CR under atomic crossings, not presently verifiable. Proposition III.8 has a related notational inconsistency in the swap construction, so the decomposition into monotone and atomic factors is also not yet fully rigorous. Because Theorem III.11 is the bridge to the Büchi atlas characterization and the linear-time decidability claim, the manuscript's main contributions remain conditional on a completed proof. I therefore do not see a demonstrated counterexample, but I also do not see a complete proof; keeping the reader's CONDITIONAL verdict is appropriate. A secondary concern in Theorem VI.4, where membership in the filter set X is used as though it marked a 1 in β, reinforces the need for a careful rewrite, but the primary issue is the unverified QI=CR equivalence.","tokens_in":22635,"tokens_out":12162,"duration_ms":133410,"concrete_test":"Re-derive Lemma III.10 from Definitions III.6 and III.7 with consistent notation, and prove the Claim in the exact form needed for Theorem III.11. In parallel, run a finite exhaustive check: for alphabet size 2, take all finite strings β and γ of length at most 12 with γ obtained from β by one atomic crossing, and all α ⩽_CR β witnessed by partitions with block length at most 3, then test whether α ⩽_CR γ. A violation would refute the lemma; a clean pass would localize the gap to the infinite-block induction and allow the proof to be completed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central structural result, Theorem III.11 (α ⩽_QI β ⇒ α ⩽_CR β), is a corollary of Proposition III.8 and Lemma III.10, and both links are underproved. In Proposition III.8 the pairs (n_i, m_i) are introduced as domain positions with f(m_i) − f(n_i) = D, but the repair step then swaps colours at positions n_i, m_i in β; if n_i, m_i are in α, this is type-incoherent, and if they are meant to be image positions the notation has not been introduced. The claim that finitely many such swaps make g ∘ f monotone is not proved. Lemma III.10 then assumes without proof that an atomic crossing can be normalized to a_i ∈ v_i and b_i ∈ v_{i+1} (the text writes u_i, conflating the α- and β-partitions), and its central Claim uses 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 analogous statement for C(a_n) would hold, but then the pigeonhole step and the assertion |A| ≤ |Σ| − 1, which depends on distinct m, m′ ∈ A having distinct C(a_m), would need to be re-checked with corrected indexing. As written, the equivalence on which the Büchi atlas characterization and the decidability result rest is therefore not certified. This is an incompleteness in the proof, not a demonstrated falsehood.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":22908,"tokens_out":10421,"duration_ms":99854,"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":[{"comment":"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.","section":"§III-A, Proposition III.8"},{"comment":"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.","section":"§III-B, Lemma III.10"},{"comment":"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.","section":"§V, Theorem V.2(2)"},{"comment":"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.","section":"§VI, Theorem VI.4"}],"minor_comments":[{"comment":"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.","section":"§I, Definition I.2"},{"comment":"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.","section":"§II-A, Lemma II.2"},{"comment":"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}'.","section":"§II-B, Theorem II.6"},{"comment":"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|}.","section":"§III-A, Theorem III.3"},{"comment":"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.","section":"§III-B, Lemma III.10"},{"comment":"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.","section":"§IV, Lemma IV.4"},{"comment":"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 Σ.","section":"§VI, Definition VI.1"}],"recommendation":"major_revision","confidential_remarks":"The paper is broad and ambitious, and the main ideas are promising. The central problem is rigor: the QI⇔CR equivalence, on which the Büchi atlas characterization and the decidability result depend, is not proved as written. I recommend asking the authors to repair the decomposition in Proposition III.8 and the proof of Lemma III.10, and to provide a rigorous reduction in Theorem V.2(2). If the QI⇔CR bridge cannot be repaired, the claims in Section IV and Corollary IV.8 would need to be restructured or withdrawn."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper brings quasi-isometry from geometric group theory to infinite strings over a finite alphabet. Strings are colored metric spaces, and the relation ⩽_QI between quasi-isometry types gives a partial order on \"large scale geometries.\" I don't know of prior work in this direction, so the conceptual setup is genuinely new. The structural results in Section II — greatest element, minimal elements, chains, anti-chains — are solid and give the framework substance. The Büchi atlas idea is also nice: Theorem IV.7 claims a full classification of atlases of Büchi-recognizable languages, with a linear-time decision procedure for atlas equality, which would be a striking contrast to PSPACE-completeness for language equality. The asymptotic-cone material, connecting to algorithmic randomness, is imaginative.\n\nBut the proof of the bridge theorem, III.11 (QI ⇒ CR), is not in acceptable shape. It relies on Proposition III.8 and Lemma III.10. In III.8, the proposition swaps colors at positions n_i, m_i in β, but those positions are defined as domain elements in α; if they are meant to be f(n_i), f(m_i), the notation hasn't been introduced. And the claim that finitely many such swaps make the map monotone is not proved. In Lemma III.10, the central claim asserts that distinct elements of A have distinct colors, with no justification, and the proof conflates the α-partition u_i with the β-partition v_i. These look like fixable errors, but they are load-bearing: without III.11, the Büchi characterization and the decidability algorithm lack their foundation.\n\nFurther soft spots: V.2(2) gives only an informal reduction for Σ_3^0-completeness; VI.4's ultrafilter argument appears to treat the index set X as if it marked 1s in β, though the 1s sit at 2^{n_i}; VI.7 is stated without proof. None of these are shown false — they are incomplete proofs in important places.\n\nWho will get value: people working at the interface of geometric group theory, formal languages, and symbolic dynamics. The framework is worth discussing, but as written I would not rely on the central equivalence.\n\nRecommendation: send to referees, but expect major revision. The paper deserves serious referee time because the ideas are new and the conjectured structure is plausible.\n\nBest,","headline":"A genuinely new framework for quasi-isometry of infinite strings, with a plausible central equivalence that is not yet proven as written.","tokens_in":23468,"tokens_out":5564,"would_cite":true,"duration_ms":54929,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["20F65","68Q45","03D55"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["quasi-isometry","large scale geometry","infinite strings","componentwise reducibility","Büchi automata","asymptotic cones","arithmetical hierarchy","algorithmic randomness"],"falsifier":"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.","tokens_in":22399,"feed_emoji":"📏","tokens_out":10657,"duration_ms":103534,"temperature":0.7,"pith_summary":"The paper brings geometric group theory's notion of quasi-isometry to infinite strings, treating the alphabet as colours on the positions of $\\omega$. Its central claim is that $\\alpha \\leqslant_{QI}\\beta$ holds exactly when $\\alpha$ and $\\beta$ admit uniformly bounded block partitions with the colour set of each block of $\\alpha$ contained in the colour set of the matching block of $\\beta$. This bridge turns a geometric question about distorted colour-preserving maps into a combinatorial one about block inclusions. From it, the paper derives a finite classification of the large-scale geometries of B\\\"uchi-recognisable languages, a $\\Sigma_3^0$-completeness result for the quasi-isometry problem, and asymptotic-cone invariants that connect the area to algorithmic randomness.","feed_headline":"Quasi-isometry equals blockwise inclusion for infinite strings","feed_subtitle":"The equivalence unlocks linear-time checks of Büchi automaton atlases and a complete complexity bound.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Formalises asymptotic cones as ultra-products, the construction Section VI adapts to coloured strings.","marker":"[4]"},{"why":"Establishes quasi-isometry invariants and the geometric-group-theory viewpoint the paper transfers to strings.","marker":"[6]"},{"why":"Defines asymptotic invariants of infinite groups, motivating the cones and large-scale classification.","marker":"[8]"},{"why":"Yields an infinite path through a finitely branching tree computable in the halting set, proving computability of a quasi-isometry.","marker":"[10]"},{"why":"Provides Solovay tests and algorithmic randomness facts used to show random strings have universal cones.","marker":"[11]"},{"why":"Supplies the $\\Sigma_3^0$-complete set Fin used to prove quasi-isometry is $\\Sigma_3^0$-complete.","marker":"[12]"}],"fun_headline_variants":["Quasi-isometry equivalence collapses to blockwise inclusion","Infinite strings: QI iff blockwise reducibility","String geometry: quasi-isometry equals componentwise inclusion","New theorem links QI to componentwise reducibility","Büchi automaton atlases from blockwise string geometry"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Quasi-isometry equivalence collapses to blockwise inclusion","Infinite strings: QI iff blockwise reducibility","String geometry: quasi-isometry equals componentwise inclusion","New theorem links QI to componentwise reducibility","Büchi automaton atlases from blockwise string geometry"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000237,"raw_usage":{"total_tokens":1559,"prompt_tokens":1050,"completion_tokens":509,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":666,"completion_tokens_details":{"reasoning_tokens":427}},"tokens_in":666,"tokens_out":509,"duration_ms":5607,"temperature":1.0,"reasoning_tokens":427,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:03:43.615921+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"V an Den Dries and A","cited_arxiv_id":null,"evidence_quote":"Formalises asymptotic cones as ultra-products, the construction Section VI adapts to coloured strings."},{"cited_title":"Hautes Etudes Sci","cited_arxiv_id":null,"evidence_quote":"Establishes quasi-isometry invariants and the geometric-group-theory viewpoint the paper transfers to strings."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines asymptotic invariants of infinite groups, motivating the cones and large-scale classification."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Yields an infinite path through a finitely branching tree computable in the halting set, proving computability of a quasi-isometry."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides Solovay tests and algorithmic randomness facts used to show random strings have universal cones."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the $\\Sigma_3^0$-complete set Fin used to prove quasi-isometry is $\\Sigma_3^0$-complete."}],"review_version":1}