{"id":"f784a291-7f5c-430d-b7d6-f195936f5a6e","arxiv_id":"1908.03773","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new graph-based algorithm approximates the Lagrange and Markov spectra on bounded intervals with Hausdorff error 1/Q in time O(Q^{3d}), where d is the Hausdorff dimension of a related continued fraction Cantor set.","lead":"The paper gives a polynomial-time algorithm that computes finite sets within 1/Q of the classical Lagrange and Markov spectra on any bounded interval. Because the error is controlled in Hausdorff distance and the cost is polynomial in Q, the method enables rigorous high-resolution pictures of these fractal spectra.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The advertised d_R exponents rely on an unproved (and in the introduction misstated) claim that the smallest value in L_{K+1}\\L_K equals L(K+1); if this fails, the chosen alphabet K is too small and the correctness and complexity bounds of Theorem 1 do not follow.","rationale":"The reader's weakest_assumption concerned the dimension estimates and distortion bound feeding into Theorem 13. Those indeed affect the numerical exponents but not the correctness of the approximation: if the dimension bound were off, the algorithm would still work with a larger exponent. The load-bearing gap I identify is more fundamental: it determines whether the graph on the small alphabet K actually approximates the true spectrum on the stated R-intervals. This is a separate premise, and the manuscript neither proves nor cites it. The introduction's erroneous bullet (identifying L(2,1) with √13) strengthens the concern that the authors may have conflated the maximum of L2 with the minimum of L3\\L2. I do not regard this as fatal: the underlying claim is plausibly true and standard, and the endpoint values R=√13 and R=2√5 can be handled by adjoining finitely many known points. But as written, the theorem's correctness on the full stated ranges is not fully established. I therefore keep the reader's CONDITIONAL verdict: the paper should add a proof or precise reference for the interval-containment lemma, and clarify the boundary-point handling. The concrete test above would settle whether the concern actually lands.","tokens_in":11802,"tokens_out":34933,"duration_ms":353183,"concrete_test":"Prove or supply a rigorous reference for the assertion that min(L_{K+1}\\L_K)=L(K+1) for K=2,3, and similarly for M_{K+1}\\M_K. A direct analytical check is to show that every bi-infinite sequence over {1,...,K+1} containing a K+1 has limsup λ0 ≥ L(K+1), with equality only for the constant sequence. Alternatively, run the algorithm for R=3.5 and large Q with both K=2 and K=3 and compare the resulting edge-weight sets on [0,3.5]: if the K=2 set is not 1/Q-close to the K=3 set on that interval, the interval-containment assumption fails and the advertised d_R bound is invalid.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 1's sharp complexity bounds require, for R≤√13, R≤2√5, and R≤√21, that L∩[0,R] (and M∩[0,R]) be contained in the spectra generated by digits 1..K for K=2,3,4 respectively, up to finitely many known boundary points. This reduction is justified only by the assertion in Section 2 that \"the smallest and largest values of LK\\L_{K-1} are respectively L(K) and L(1,K)\". No proof or citation is given for this claim, yet it is load-bearing: if some sequence using digit K+1 had Lagrange value below L(K+1), then the graph G_{K,Q} built on the smaller alphabet would not approximate the true spectrum on a whole interval, and the running time O(Q^{3d_R}) would be irrelevant. The risk is compounded by the introduction, which states \"L(2,1)=√13 is the maximum of L2\": in fact L(2,1)=2√3≈3.464 while √13≈3.606 equals L(3), the minimum of L3\\L2. This misstatement suggests the interval-containment property may have been confused in the writing. The same issue affects the Markov spectrum, since the algorithm treats L and M in parallel but the interval-containment claim is stated only for LK. This concern is independent of the dimension estimates in Theorem 13: even if those are correct, the algorithm would be solving the wrong approximation problem if the alphabet reduction is invalid.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents an algorithm that, for any R>0 and any precision parameter Q, outputs finite sets that are 1/Q-close in Hausdorff distance to the intersections of the Lagrange and Markov spectra with [0,R]. The algorithm encodes the one-sided subshift with digits 1..K as a finite weighted graph whose edges are 1/Q-cylinders for the Gauss map, then computes the discrete analogues of Lagrange and Markov values on the graph. The number of graph edges is bounded by |C_{K,Q}|^2, and |C_{K,Q}| is shown to grow like Q^{HD(E_K)} using Hausdorff dimension estimates for continued fraction Cantor sets. The paper also gives a comparison with approximation by periodic orbits and includes high-resolution figures generated by an implementation whose code is publicly available.","tokens_in":12087,"tokens_out":12611,"duration_ms":126295,"significance":"If the main theorem is correct, this is the first polynomial-time procedure with explicit complexity bounds for Hausdorff approximation of both spectra, and it connects the algorithmic complexity to the Hausdorff dimension of the Cantor sets E_K. The paper has several concrete strengths: the central approximation step is derived from the definitions with explicit constants; the dimension estimates quoted from Jenkinson--Pollicott are rigorous and the constants in Theorem 13 are explicit; the implementation is publicly available; and the figures provide falsifiable outputs of the method. These strengths make the paper potentially valuable for computational number theory and dynamical systems, provided the correctness gaps identified below are addressed.","major_comments":[{"comment":"The range R≤√13 is incompatible with the choice K=2 at the endpoint. The maximum of L2 is L(2,1)=2√3≈3.464, while L(3)=√13≈3.606 belongs to L; the difference is about 0.141. Thus L∩[0,√13] is not contained in L2, so the graph G_{2,Q} cannot produce a 1/Q-close approximation for large Q. The same endpoint problem occurs at R=2√5 with K=3, since L(4)=2√5 belongs to L and is not in L3 if the claim about the minimum of L4\\L3 is correct. The theorem should either state strict inequalities R<√13 and R<2√5, or the algorithm must explicitly adjoin the finitely many boundary values; the current wording is not correct.","section":"Section 2 and Theorem 1"},{"comment":"The assertion that 'the smallest and largest values of LK\\L_{K-1} are respectively L(K) and L(1,K)' is load-bearing for Theorem 1 but is stated without proof or reference. Moreover, the immediately following bullets contain numerical errors: 'L(2,1)=√13 is the maximum of L2' should read 'L(2,1)=2√3', and 'L(4)=2√5 is the maximum of L4\\L3' is inconsistent with Figure 1 unless 'minimum' is intended. Please provide a proof or a precise citation for the interval-containment property and correct these bullets.","section":"Section 2"},{"comment":"The proof of Theorem 9 is written only for the Markov spectrum, with the Lagrange case dismissed as 'similar'. Since the Lagrange statement of Theorem 1 depends on this result, a complete argument is needed. In particular, the proof for the Lagrange case should show that a limsup value in LK can be approximated by an edge that is maximal on a cycle, taking into account that weights on the approximating cycle may exceed the target value only finitely often.","section":"Section 5, Theorem 9"}],"minor_comments":[{"comment":"The title/abstract contains a typo: 'APPROXIMA TIONS' should be 'APPROXIMATIONS'.","section":"Abstract and title"},{"comment":"The shift edges are described in Section 3.2 as being in bijection with CK,Q×{1,...,K}×CK,Q, but Lemma 10 counts them as |CK,Q|^2. The missing factor K does not change the order of magnitude, but the counting statement should be made consistent.","section":"Section 3.2 and Lemma 10"},{"comment":"The statement that values R larger than √21 'do not make any sense' is too strong: L∩[0,R] is compact for every finite R and can be Hausdorff-approximated by finite sets. What the authors presumably mean is that the stated upper bounds on d_R do not apply, because one would need to include digits larger than 4.","section":"Remark 2"},{"comment":"In the Lagrange part of the proof, the text writes 'put t=L(a)∈L'; since a is restricted to ΣK, the statement is about LK, and the notation should reflect that.","section":"Section 7, Proposition 15"}],"recommendation":"major_revision","confidential_remarks":"The paper is a good fit for the journal and the core algorithmic idea is sound, but the errors in Section 2 are concentrated exactly where the hypotheses of Theorem 1 are determined. I recommend a major revision in which the authors re-derive the range-to-alphabet correspondence carefully, correct the numerical statements, and supply the missing Lagrange-case proof in Theorem 9."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: this paper delivers a real algorithm, not a heuristic. It builds a finite weighted graph whose Lagrange and Markov edge weights are provably 1/Q-close to the actual spectra on bounded intervals, and the graph size is polynomial in Q, with the exponent tied to the Hausdorff dimension of the continued-fraction Cantor sets E_K. That is a first, and the implementation is public. The main approximation theorem (Theorem 9) is convincing for the Markov case, and the graph encoding of cylinders plus the definition of Lagrange/Markov edges in a weighted digraph are clean ideas.\n\nThe complexity analysis is honest too. Theorem 13 gives explicit constants for the cylinder counts using rigorous dimension bounds from Jenkinson-Pollicott and a distortion bound from Moreira. That is reproducible work, and the figures in Section 8 demonstrate the algorithm in practice.\n\nWhere it gets soft:\n\n- The Lagrange half of Theorem 9 is not proved. 'The case is similar' is not a proof. The limsup argument may go through, but it needs to be written. This is the main mathematical gap.\n\n- Theorem 1 as stated has an endpoint problem. It claims R≤√13, R≤2√5, R≤√21, but at R equal to the lower endpoint of L_{K+1}\\L_K, the spectrum contains the isolated point L(K+1), which is not in the alphabet K. For example, 2√5 = L(4) is in L but not in L3, so the graph on {1,2,3} cannot see it. The theorem needs 'R<' or a separate treatment of boundary points. Not fatal, but as written it is technically false without a patch.\n\n- The alphabet reduction rests on the assertion that the smallest value in L_{K+1}\\L_K is L(K+1). The paper says 'it is easy to see' and gives no citation. I believe the assertion is true, but it should be proved or referenced. The introduction's bullet saying 'L(2,1)=√13 is the maximum of L2' is wrong (the value is 2√3). That typo does not affect the algorithm, but it signals that the interval-containment property deserves careful wording.\n\nWho this is for: anyone working on Lagrange/Markov spectra or computational dynamics. With the endpoint and Lagrange-case fixes, the theorem stands. It deserves a serious referee.","headline":"A genuine algorithmic result for the Lagrange and Markov spectra, with a clean graph construction and honest complexity bounds, but the Lagrange-case proof is unwritten and the theorem's closed-interval endpoint statements need patching.","tokens_in":12627,"tokens_out":10775,"would_cite":true,"duration_ms":98689,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["37C45","37B10","11J70","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every bounded interval, the Lagrange and Markov spectra can be approximated from both sides by finite sets at any prescribed precision, in time polynomial in the precision parameter.","keywords":["Lagrange spectrum","Markov spectrum","continued fractions","Gauss map","Hausdorff dimension","Diophantine approximation","polynomial-time algorithm","finite type shifts"],"falsifier":"Take $K=2$ and count the cylinders $C_{2,Q}$ for $Q=10^2,10^3,\\dots,10^8$; if $|C_{2,Q}|$ exceeds $4.98\\cdot Q^{0.5313}$ at any of these sizes, the $\\Theta(Q^{\\mathrm{HD}(E_2)})$ bound behind the advertised running time is refuted. Independently, for a fixed $Q$, check the Hausdorff distance between the algorithm's output and $\\mathcal{L}_2\\cap[0,\\sqrt{13}]$; any pair of points more than $1/Q$ apart would disprove the approximation claim.","tokens_in":11583,"feed_emoji":"🔢","tokens_out":11578,"duration_ms":106035,"temperature":0.7,"pith_summary":"The Lagrange spectrum records the best constants of Diophantine approximation of irrational numbers, and the Markov spectrum is its sibling defined by minima of indefinite binary quadratic forms; both are closed subsets of the positive reals with intricate fractal structure. This paper proves that, for any bounded interval [0,R], each spectrum can be bracketed by finite sets whose Hausdorff distance to the spectrum is at most 1/Q, and that those finite sets can be produced in time polynomial in Q. The proof is constructive: it encodes the dynamics of the Gauss map on digit-restricted continued fractions as a finite weighted graph, reads off spectral values as weights of special edges, and bounds the graph size by the Hausdorff dimension of the underlying Cantor sets. A reader should care because the result turns an apparently transcendental limit-supremum object into a finite, certifiable computation, and it connects the computational cost to a natural fractal invariant.","feed_headline":"Algorithm approximates Lagrange and Markov spectra at any precision","feed_subtitle":"Finite point sets land within 1/Q of both spectra in time O(Q^{3d}), with d under 0.53 up to √13.","key_machinery":"For $K\\le4$, the load-bearing object is the weighted directed graph $G_{K,Q}$. Its vertices and edges encode the collection $C_{K,Q}$ of shortest cylinders of the Gauss map whose interval diameter is at most $1/Q$; a shift edge $(p,a_0,s)$ carries the weight $a_0+\\mathrm{mid}_K(p)+\\mathrm{mid}_K(s)$, the midpoint of the height function $\\lambda_0$ over that cylinder, and the paper proves each such weight is within $1/Q$ of the true value of $\\lambda_0$ on the cylinder. The spectral approximation is carried by Lagrange edges, meaning edges that are maximal on some directed cycle, and Markov edges, meaning edges maximal on a path running from one cycle into another. The graph size estimate $|G_{K,Q}|=\\Theta(|C_{K,Q}|^2)=\\Theta(Q^{2\\mathrm{HD}(E_K)})$ follows from a diameter comparison, a lower bound on cylinder diameters, the uniform distortion bound for Gauss-map iterates, and a standard dimension-counting argument for cylinder covers; the total $O(Q^{3d_R})$ running time then comes from an $O(m^{3/2})$ step that extracts the spectral edge weights from a graph with $m$ edges.","core_discovery":"At the center of the paper is Theorem 1: for every $R>0$ there is an algorithm which, given $Q$, outputs finite sets that are $1/Q$-close in Hausdorff distance to both $\\mathcal{L}\\cap[0,R]$ and $\\mathcal{M}\\cap[0,R]$, and runs in time $O(Q^{3d_R})$. The exponents are explicit: $d_R<0.532$ when $R\\le\\sqrt{13}$, $d_R<0.706$ when $R\\le2\\sqrt{5}$, and $d_R<0.789$ when $R\\le\\sqrt{21}$, where $d_R$ is the Hausdorff dimension of the set $E_K$ of real numbers whose continued-fraction expansion uses only the digits $1,\\dots,K$. The proof works by reducing the spectra to a finite combinatorial problem: the weights of Lagrange and Markov edges in a weighted directed graph $G_{K,Q}$ built from $(1/Q)$-cylinders of the Gauss map are shown to form a $1/Q$-Hausdorff approximation to the true spectra. The graph size is controlled by $|C_{K,Q}|=\\Theta(Q^{\\mathrm{HD}(E_K)})$, which follows from bounded distortion of Gauss-map iterates and the standard connection between cylinder counts and Hausdorff dimension.","pith_inferences":["Inference: the same weighted-graph construction should transfer to any expanding one-dimensional map with bounded distortion and a digit-restricted alphabet, giving polynomial-time approximation of the associated spectra.","Inference: since the approximation guarantee is uniform in $Q$ but the exponent comes from Hausdorff dimension, tighter rigorous dimension bounds for $E_2,E_3,E_4$ would directly improve the running time without changing the algorithm.","Inference: the contrast with periodic-orbit approximation suggests that finite-type graph models, rather than periodic points, are the natural combinatorial skeleton for the fine structure of the Lagrange and Markov spectra.","Inference: one could use this algorithm as a numerical probe for the local fractal structure of the spectra by measuring how the density of output points scales with $Q$ on small intervals, yielding empirical estimates of local Hausdorff dimension."],"forward_implications":["For each $R\\le\\sqrt{21}$, certified finite approximations of both spectra on $[0,R]$ exist at resolution $1/Q$ with running time polynomial in $Q$.","Because the approximation is in Hausdorff distance, the output sets give both a lower and an upper bracket for every spectral point up to tolerance $1/Q$, so gaps and intervals in the spectra can be certified algorithmically.","The exponent $d_R$ is a concrete, dimension-dependent number, so the same graph construction applies for any finite digit alphabet once the corresponding Cantor set dimension is known.","The paper's implementation draws high-resolution pictures of $\\mathcal{L}_2$ and $\\mathcal{L}_3$ at precisions $1/150000$ and $1/3000$, showing the worst-case bounds are not merely asymptotic.","The method also highlights why approximating the spectra by periodic orbits is far worse: the periodic-orbit route requires exponentially many periods, whereas the graph route stays polynomial."],"supporting_citations":[{"why":"Supplies the continued-fraction formula that turns the Lagrange value of an irrational into a limsup of a height function on the bi-infinite shift, which is the starting point the whole construction approximates.","marker":"[Per21]"},{"why":"Provides the characterization of the spectra via periodic and ultimately periodic sequences, and the diameter-decay lemma used to control the number of prolongation edges in the graph.","marker":"[CF89]"},{"why":"Gives the uniform distortion bound of at most 4 for iterates of the Gauss map, which is needed for the $\\Theta(Q^{\\mathrm{HD}(E_K)})$ cylinder count.","marker":"[Mor18]"},{"why":"Supplies the rigorous bound $0.5312<\\mathrm{HD}(E_2)<0.5313$ used for the $R\\le\\sqrt{13}$ exponent.","marker":"[Je04]"},{"why":"Provides rigorous dimension estimates for the continued-fraction Cantor sets appearing in the complexity bounds.","marker":"[JePo01]"},{"why":"Adds rigorous effective bounds for $\\mathrm{HD}(E_2)$ that enter the explicit numerical values of $d_R$.","marker":"[JePo18]"},{"why":"The dimension-counting argument from this book is used in the proof of the cylinder-count estimate $|C_{K,Q}|=\\Theta(Q^{\\mathrm{HD}(E_K)})$.","marker":"[PaTa]"},{"why":"Provides the incremental cycle-detection and strongly-connected-component maintenance that yields the $O(m^{3/2})$ step for extracting Lagrange and Markov edge weights from the graph.","marker":"[HKMST12]"}],"fun_headline_variants":["New algorithm approximates both spectra in polynomial time","Polynomial-time method yields 1/Q-close approximations to spectra","Fast algorithm homes in on Lagrange and Markov spectra","Explicit bounds for approximating spectra via graph construction"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The advertised running time depends on two quoted numerical ingredients, rigorous bounds on the Hausdorff dimensions of the Cantor sets $E_2,E_3,E_4$ and a distortion bound of at most 4 for Gauss-map iterates, and if either of those failed the algorithm would still approximate correctly but could run slower than promised.","fun_headline_variants_meta":{"raw":{"variants":["New algorithm approximates both spectra in polynomial time","Polynomial-time method yields 1/Q-close approximations to spectra","Fast algorithm homes in on Lagrange and Markov spectra","Explicit bounds for approximating spectra via graph construction"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000297,"raw_usage":{"total_tokens":1679,"prompt_tokens":862,"completion_tokens":817,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":478,"completion_tokens_details":{"reasoning_tokens":753}},"tokens_in":478,"tokens_out":817,"duration_ms":9251,"temperature":1.0,"reasoning_tokens":753,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:05:51.000109+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $K=2$ and count the cylinders $C_{2,Q}$ for $Q=10^2,10^3,\\dots,10^8$; if $|C_{2,Q}|$ exceeds $4.98\\cdot Q^{0.5313}$ at any of these sizes, the $\\Theta(Q^{\\mathrm{HD}(E_2)})$ bound behind the advertised running time is refuted. Independently, for a fixed $Q$, check the Hausdorff distance between the algorithm's output and $\\mathcal{L}_2\\cap[0,\\sqrt{13}]$; any pair of points more than $1/Q$ apart would disprove the approximation claim.","supporting_citations":[],"review_version":1}