{"id":"83fd3e34-8584-4c63-91da-48b00f378fb2","arxiv_id":"2411.18782","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"The set of spanning tree numbers of connected planar simple graphs on n vertices has size at least c^n for some c>1, for all large n.","lead":"Mathematicians proved that the number of distinct spanning tree counts among n-vertex planar graphs grows exponentially with n, settling a 1969 question. The proof links graph structure to continued fractions and to deep results on Diophantine approximation, and gives explicit planar graphs with prescribed spanning tree counts.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The Main Dimension Theorem depends on an uncertified pointwise inequality; a rigorous interval-arithmetic check would settle whether the proof is complete.","rationale":"The graph-theoretic reduction (Theorem 1.9) is explicit and convincing: the Υ operations preserve simplicity and planarity, and the vertex count is exact. The Diophantine reduction to Γ_A and the admissibility Lemma 3.3 are standard. The paper's most delicate point is the numerical inequality in §4.1, which is exactly the reader's weakest assumption. I agree with the conditional verdict: this is not an internal contradiction, and the margin suggests the inequality is likely true, but the proof as written does not contain the required certificate. The proposed interval-arithmetic check would settle it. If it passes, I would regard the paper as acceptable modulo the external BK/Kan technology; if it fails, the positive-proportion theorem is unsupported. Since the reader already marked the paper conditional, no verdict change is needed.","tokens_in":19274,"tokens_out":17512,"duration_ms":159311,"concrete_test":"Use interval arithmetic to check the §4.1 inequalities rigorously. Take s=31/40, A=110, and the polynomial fs in (4.4) with its decimal coefficients interpreted as exact rationals; partition [0,1] adaptively so that validated enclosures of fs and of L_s f_s - f_s on every subinterval are obtained, and require the lower enclosure of L_s f_s - f_s to be >0 (and fs>0.3). If this succeeds, Theorem 1.19 is proved as stated; if some subinterval cannot be separated from 0, the claimed certificate is invalid and the authors must supply a different polynomial or a sharper verified bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The decisive numerical step is the proof of Theorem 1.19 in §4.1. Lemma 4.1 requires a strict pointwise inequality (4.3) on the whole interval [0,1]. The only evidence supplied is the assertion that for s=0.775, A=110, and the polynomial fs in (4.4), one has fs(x)>0.3 and L_s f_s(x)-f_s(x)>7e-5 for every x in [0,1], accompanied by a plot and the phrase \"it can be verified.\" No interval-arithmetic certificate, exact rational enclosure, or reproducible code is given. Since L_s involves s=31/40 powers of 1/(1+b+x) summed up to b=110, the difference is a transcendental expression; a plot does not exclude a small negative dip, and the 7e-5 margin is not by itself a proof. If this fails, the conclusion ϑ_A>0.775 is unsupported, so Theorem 1.17 cannot be applied and the stronger positive-proportion Theorem 1.3 loses its only quantitative input. (Theorem 1.1 has an independent route in §3.2, so the headline exponential-growth claim is less directly at risk.) The later note in §5.9 citing Pollicott's 20-digit computation does not repair the gap, since that external preprint is also cited without a certificate here.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies T(n), the set of spanning-tree counts of connected simple planar graphs on n vertices. It proves Theorem 1.1, that |T(n)| > c^n for some c > 1, answering Sedláček's 1969 question, and Theorem 1.3, that a positive proportion of {1, ..., c^n} is realized as spanning-tree counts. The proof combines four ingredients: a Main Graph Theorem (Theorem 1.9) constructing simple planar graphs from continued fractions, a dualization to the function α(t), a use of Bourgain–Kontorovich-type thin-orbit technology to prove a positive-proportion form of Zaremba's conjecture (Theorems 1.12, 1.16), and a numerical Hausdorff-dimension lower bound (Theorem 1.19). The paper also gives an independent route to Theorem 1.1 in §3.2 that does not need the full positive-proportion result.","tokens_in":19508,"tokens_out":22828,"duration_ms":223367,"significance":"If the numerical step is made rigorous, this is a substantial advance: it settles a problem open since 1969 and proves a quantitatively stronger positive-proportion theorem. The graph-theoretic core (Theorem 1.9 and Lemmas 2.1–2.3) is elementary, explicit, and convincing, and the paper is transparent about its dependence on the deep external results of Bourgain–Kontorovich and Kan. The paper also includes concrete constants, a follow-up comparison in [ABG25], and useful discussion of related conjectures. The main obstacle is the uncertified numerical inequality in §4.1. This is a load-bearing step for Theorems 1.12, 1.7, and 1.3, and currently the proof is not complete as written. The issue is local and appears fixable with a rigorous interval-arithmetic certificate or exact rational enclosure.","major_comments":[{"comment":"The proof of Theorem 1.19 is incomplete as written. The paper asserts that for s = 0.775, A = 110, and the polynomial f_s in (4.4), one has f_s(x) > 0.3 and (L_s f_s − f_s)(x) > 7×10^{-5} for every x in [0,1], citing Figure 4.1. Since L_s is a sum of 110 terms involving the exponent s = 31/40, the displayed 7-decimal coefficients and a plot do not constitute a proof of a strict pointwise inequality on a continuum. The margin 7×10^{-5} is small relative to what is needed to rule out rounding error without an enclosure. Because Theorem 1.17 requires ϑ_A > 0.775, Theorems 1.12, 1.7, and 1.3 all depend on this uncertified check. The later citation in §5.9 of Pollicott's 20-digit computation does not repair the gap, since that computation is also not certified in this paper. Please provide a rigorous interval-arithmetic or exact rational certificate, with code or data sufficient to verify (4.3).","section":"Section 4.1, inequalities following Eq. (4.4)"},{"comment":"The passage from the counting estimate |B_N| = N^{2ϑ_A+o(1)} to the claimed lower bound |N_A ∩ [1,N]| ≫ N^{ϑ_A−o(1)} is not justified in the text. The argument that R_A also contains (t+u)/(t+2u) shows that each fraction t/u produces a new numerator t+u, but the sentence 't+u and t together determine the pair (t,u)' is a statement about ordered pairs and does not bound the number of old fractions that can have the same new numerator. As written, the multiplicity of a fixed n = t+u could in principle be large. Please either supply the multiplicity bound or cite the standard dimension/projection result behind this step. The same comment applies to the claim in Remark 4.2 that ϑ_A > 1/2 already for A = 4; if Theorem 1.1 is to be independent of the A = 110 certificate, a rigorous lower bound for ϑ_4 must be provided.","section":"Section 3.2, Eq. (3.4)"},{"comment":"The adaptation of the Bourgain–Kontorovich theorem to the semigroup Γ_A needs to be made explicit. The paper quotes Theorem 3.2 as a general black box but does not state its full hypotheses, and Lemma 3.3 verifies only the congruence property Γ_A mod q = SL(2,Z/qZ). To apply the theorem to Γ_A, the authors should identify precisely which theorem from [BK14] is being used, confirm that Γ_A satisfies its hypotheses, and explain why the Hausdorff dimension of the semigroup's limit set is the quantity ϑ_A defined through C_A. I do not doubt that these checks can be done, but as written the route from [BK14, Theorem 1.8] and [Kan21] to Theorem 1.16 is a sketch rather than a verification.","section":"Section 3.3, Theorem 3.2 and Lemma 3.3"}],"minor_comments":[{"comment":"The name 'Zarembra' is a typo for 'Zaremba'.","section":"Statement of Theorem 1.14"},{"comment":"The reference entry for [ABG25] contains a stray duplicated line 'Random Structures in Algorithms, 1 (1990), 175–181.' from the entry for [Alo90].","section":"References"},{"comment":"The phrase 'Cauchy–Schwartz' should be 'Cauchy–Schwarz'.","section":"Section 3.4"},{"comment":"The captions should state how the plotted values were computed and should not be used as evidence for the pointwise inequalities; the relevant inequalities need the rigorous certificate requested in the first major comment.","section":"Figures 4.1 and 4.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely correct in its overall architecture, but the uncertified numerical inequality in §4.1 is a real gap in the proof of the positive-proportion Theorem 1.3. I recommend major revision rather than rejection, because the gap is local and appears fixable with a rigorous interval-arithmetic verification. The authors should also tighten the exposition around §3.2 and §3.3 so that the dependence on external theorems is fully checkable. If a rigorous certificate is supplied and the requested details are added, I would support acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The headline result is real: Theorem 1.1 gives exponential growth of |T(n)| for the first time, and the proof is elementary and convincing. The graph-to-fraction construction in Theorem 1.9 is a genuinely new mechanism, and Section 3.2 alone already settles Sedlacek's 1969 question with an explicit constant c≈1.1103. The paper is well-written and honest about what is open; the historical survey and the connections to Zaremba's conjecture are genuinely useful. The citation pattern is healthy: prior bounds by Sedlacek, Azarija, and Stong are correctly described, and the use of Bourgain–Kontorovich and Kan is properly credited.\n\nThe soft spot is the numerical verification in Section 4.1. The proof of Theorem 1.19 depends on the strict inequality L_s f_s - f_s > 0 on [0,1], asserted from a plot and a decimal polynomial with margin 7e-5. That is load-bearing for Theorem 1.3 (positive proportion), and as written it is not a rigorous proof: no interval arithmetic, code, or exact rational certificate is supplied. If that inequality fails, Theorem 1.3 loses its quantitative input. The later note in §5.9 citing Pollicott's 20-digit computation does not repair the gap, since that preprint is also uncertified here. This is not fatal to Theorem 1.1, which has an independent route in §3.2 needing only ϑ_A > 1/2, but it means the stronger theorem is conditional on an uncertified numeric claim.\n\nThe adaptation of the Bourgain–Kontorovich machinery to the semigroup Γ_A is sketched rather than proved; a reader who wants to check all details must go to the original papers. That is acceptable for a research paper, but it is worth flagging.\n\nWho this is for: enumerative combinatorists and people working on Zaremba-type Diophantine problems. It deserves a serious referee; the main theorem is solid, and the numeric gap is fixable. I would send it to a good combinatorics journal after the authors provide a rigorous certificate for the numerical inequality or make the code available. The core exponential-growth result should be published.","headline":"Settles the 55-year-old exponential growth question with an elegant continued-fraction reduction; the stronger positive-proportion theorem rests on an uncertified numeric inequality that should be fixed.","tokens_in":20060,"tokens_out":3152,"would_cite":true,"duration_ms":27165,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C30","11A55","11K55","28A80"],"pacs":[],"model":"deepseek-v4-flash","headline":"The set of possible numbers of spanning trees of connected simple planar graphs on n vertices grows exponentially with n, answering a 1969 question of Sedláček.","keywords":["spanning trees","planar graphs","continued fractions","Zaremba's conjecture","thin orbits","Hausdorff dimension","transfer operator","exponential growth"],"falsifier":"Run the Section 4.1 verification with rigorous interval arithmetic or a certified eigenvalue computation for the $5\\times 5$ transfer matrix at $s=0.775$, $A=110$; if any $x\\in[0,1]$ has $L_s f_s(x)-f_s(x)\\le 0$, or if the computed top eigenvalue is at most $1$, then the dimension theorem is false.","tokens_in":19062,"feed_emoji":"🌳","tokens_out":14495,"duration_ms":184463,"temperature":0.7,"pith_summary":"This paper proves that the set of possible numbers of spanning trees of connected simple planar graphs on $n$ vertices grows exponentially with $n$, settling a question raised by Sedláček in 1969. The proof connects graph theory to Diophantine approximation: certain continued fraction expansions are shown to produce graphs with prescribed spanning-tree counts, and a positive proportion of integers admit such expansions with bounded partial quotients. That Diophantine statement is proved using techniques developed for Zaremba's conjecture, and the decisive numerical ingredient is a rigorous computer-assisted estimate that a certain Cantor-like fractal has Hausdorff dimension above $0.775$. The argument reduces the former open problem to two explicit inequalities involving a single polynomial and a transfer operator, which the paper verifies directly.","feed_headline":"Exponential growth proved for planar spanning-tree counts","feed_subtitle":"A 1969 question of Sedláček is settled via continued fractions, Zaremba's conjecture, and a dimension check.","key_machinery":"The machinery is a bridge from graphs to continued fractions and back. On the graph side, two operations on a marked planar graph, subdividing an edge ($\\Phi_k$) and adding parallel edges ($\\Psi_k$), multiply the spanning-tree vector $(\\tau(G-e),\\tau(G/e))$ by the shear matrices $\\begin{pmatrix}1&k\\\\0&1\\end{pmatrix}$ and $\\begin{pmatrix}1&0\\\\k&1\\end{pmatrix}$; composing these in alternating order produces exactly the matrix $\\begin{pmatrix}*&*\\\\t&u\\end{pmatrix}$ attached to the continued fraction $t/u=[b_1,1,b_2,1,\\ldots,b_m,1]$. This yields the Main Graph Theorem: such a fraction gives a simple planar graph with $\\tau(G)=t$ and $|V|=b_2+\\cdots+b_m+2$. On the Diophantine side, the set $R_A$ of such fractions with $1\\le b_i\\le A$ is captured by the semigroup $\\Gamma_A$ generated by the products $\\begin{pmatrix}0&1\\\\1&1\\end{pmatrix}\\begin{pmatrix}0&1\\\\1&b\\end{pmatrix}$, and its orbit under a fixed vector produces the numerators $t$. The orbital circle method, refined to threshold $\\delta_0=0.775$, says that if the limit set of $\\Gamma_A$ has Hausdorff dimension $\\vartheta_A>\\delta_0$, then a positive proportion of admissible integers occur as numerators. Finally, $\\vartheta_A$ is controlled by the pressure zero of the transfer operator $L_s f(x)=\\sum_{b=1}^A |T_b'(x)|^s f(T_b(x))$ with $T_b(x)=\\frac{b+x}{1+b+x}$; a positive polynomial $f$ with $L_s f>f$ on $[0,1]$ proves $\\vartheta_A>s$, and such an $f$ is exhibited for $s=0.775$ and $A=110$.","core_discovery":"This paper claims that the number of distinct spanning-tree counts of connected simple planar graphs on $n$ vertices grows at least exponentially in $n$, and that a positive proportion of the integers up to that exponential scale are realized as such counts. The proof has four interlocking pieces. First, for a marked planar graph the spanning-tree vector $(\\tau(G-e),\\tau(G/e))$ is transformed by two operations, subdividing an edge and adding parallel edges, so that successive applications multiply the vector by shear matrices; reading the coordinates as numerator and denominator, the construction realizes exactly those rationals whose continued fraction expansion alternates $1$'s with positive digits, i.e. $t/u=[b_1,1,b_2,1,\\ldots,b_m,1]$. Second, a Diophantine conjecture asserting that every integer $t$ admits such a fraction $t/u$ with digits bounded by $A$ is shown to hold for a positive proportion of $t$, conditional on a Hausdorff dimension threshold $\\delta_0<1$. Third, that threshold is supplied by the orbital circle method refined to $\\delta_0=0.775$. Fourth, the dimension condition is verified: for $A=110$, the fractal of these alternating continued fractions has Hausdorff dimension strictly above $0.775$, as witnessed by an explicit polynomial satisfying a transfer-operator inequality. Taken together, these steps yield the exponential growth theorems.","pith_inferences":["The transfer-operator certificate could be turned into a fully machine-checkable proof by running the same inequality test under interval arithmetic; the paper's margin of $7\\times 10^{-5}$ is small but the method is systematic, so this is a computational rather than a conceptual gap.","If the density-one variant described in Remark 1.18 is carried out, the conclusion would strengthen to almost every integer up to $c^n$ being a spanning-tree count, implying a density-one version of the bound $\\alpha(t)=O(\\log t)$.","The graph–continued fraction correspondence hints that similar encodings could attack Sedláček-type problems for other graph families, such as regular graphs, wherever a Zaremba-type Diophantine statement can be proved for the relevant set of fractions.","The connection to spectra of Laplace operators mentioned in the final remarks suggests the exponential growth result may be interpretable as a statement about limit points of the spanning-tree spectral invariant $s(G)=\\log \\tau(G)/|G|$."],"forward_implications":["The cardinality $|T(n)|$ of the set of spanning-tree counts of connected simple planar graphs on $n$ vertices is at least $c^n$ for some $c>1$ and all large $n$, settling Sedláček's 1969 lower-bound question.","A positive proportion of the integers $1,\\ldots,c^n$ occur as spanning-tree counts of such graphs; the paper conjectures in Remark 1.18 that this can be improved from positive proportion to density one.","The dual function $\\alpha(t)$, the minimum number of vertices needed to realize $t$ spanning trees, satisfies $\\alpha(t)=O(\\log t)$ for a positive proportion of $t$.","The same exponential lower bound holds for the larger family of all simple graphs, the first such bound for that family.","Under the paper's own method the base constant $c$ can be taken as $1.1103$, and no constant above the golden ratio $\\varphi\\approx 1.618$ can be obtained by this approach."],"supporting_citations":[{"why":"Introduced the lower-bound question for |T(n)| and proved the first quadratic lower bound; the problem the paper resolves.","marker":"[Sed69]"},{"why":"Supplies the orbital circle method and the local-global principle for thin orbits that the paper adapts to numerators of alternating continued fractions.","marker":"[BK14]"},{"why":"Provides the improved threshold δ0=0.775 used as the target for the dimension verification.","marker":"[Kan21]"},{"why":"Supplies the rigorous transfer-operator and test-function procedure used to prove the dimension lower bound in Section 4.","marker":"[PV22]"},{"why":"The graph construction with elementary matrix operations is a variation of this work's construction, giving the Main Graph Theorem.","marker":"[CP24c]"},{"why":"Gives the previous best bound on α(t), the yardstick the new theorems improve.","marker":"[Sto22]"},{"why":"Gives the prior estimate 0.732<¯ϑ<0.819 for the associated fractal, motivating the need for the sharper dimension computation.","marker":"[HT23]"}],"fun_headline_variants":["Exponential growth of planar spanning-tree counts settled","1969 Sedláček question answered: exponential tree counts","Spanning trees: exponential growth for planar graphs proven","Planar graphs: exponential variety of spanning-tree numbers","Exponential spanning-tree counts in planar graphs established"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire theorem rests on the claim, supported in Section 4.1 only by decimal values and a plot, that the polynomial $f_s(x)=0.0121844x^4-0.0513245x^3+0.116313x^2-0.225988x+0.526229$ satisfies $L_s f_s(x)-f_s(x)>7\\times 10^{-5}$ on $[0,1]$ at $s=0.775$ and $A=110$; if that inequality fails, the dimension bound and the positive-proportion theorem collapse.","fun_headline_variants_meta":{"raw":{"variants":["Exponential growth of planar spanning-tree counts settled","1969 Sedláček question answered: exponential tree counts","Spanning trees: exponential growth for planar graphs proven","Planar graphs: exponential variety of spanning-tree numbers","Exponential spanning-tree counts in planar graphs established"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000188,"raw_usage":{"total_tokens":1292,"prompt_tokens":868,"completion_tokens":424,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":484,"completion_tokens_details":{"reasoning_tokens":349}},"tokens_in":484,"tokens_out":424,"duration_ms":4519,"temperature":1.0,"reasoning_tokens":349,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T10:52:51.843516+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the Section 4.1 verification with rigorous interval arithmetic or a certified eigenvalue computation for the $5\\times 5$ transfer matrix at $s=0.775$, $A=110$; if any $x\\in[0,1]$ has $L_s f_s(x)-f_s(x)\\le 0$, or if the computed top eigenvalue is at most $1$, then the dimension theorem is false.","supporting_citations":[],"review_version":1}