{"id":"634700c0-43fe-499e-80ee-6563f166144f","arxiv_id":"2412.04170","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every tree with ℓ leaves, the d-dimensional discrepancy of its subtrees is asymptotically ℓ/(d B(d/2,1/2)), confirming two conjectures.","lead":"This paper proves that for any tree with a large number of leaves, the d-dimensional discrepancy of its subtrees is asymptotically ℓ/(d B(d/2,1/2)), settling a conjecture from Krishna et al. The proof uses random vectors on the sphere and a leaf-pruning reduction, and it also resolves a second conjecture about oriented discrepancy.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The reader's conditional verdict is defensible because the paper has several proof gaps and omitted justifications, especially in Theorem 1.4. However, the specific strongest claim about a numerator/denominator typo does not match the supplied full text, where the displayed formula has B in the denominator. The central upper-bound construction in Theorem 1.2 is a standard probabilistic argument with the correct constant, and the lower bound is a straightforward import from [15] whose value is corroborated by the paper's own star computation. Claim 2.3 has a missing case, but the missing case is trivially handled, so it is not load-bearing. The secondary oriented-discrepancy proof is under-specified, which supports keeping a conditional verdict, but I do not see a fatal flaw in the main theorem. Therefore the verdict should remain unchanged from the reader's conditional assessment.","tokens_in":7274,"tokens_out":44064,"duration_ms":461227,"concrete_test":"Re-derive the expectation in Claim 2.2 for x uniform on S^d using the surface-area formula stated on page 4, and confirm it equals 2/(d B(d/2,1/2)). Then independently verify Theorem 7 of [15] for the star S_ell by averaging over directions a in S^d and choosing the half of edges with positive projection; this should give the lower bound ell/(d B(d/2,1/2)). If both checks pass, the asymptotic constant in Theorem 1.2 is internally and externally supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No load-bearing flaw found in the central argument. In the supplied full text, Theorem 1.2 has B(d/2,1/2) in the denominator, consistent with the proof's expectation computation, so the reader's numerator/denominator typo concern does not reproduce. Lemma 2.1 correctly samples antipodal pairs on S^d and controls max_a Σ|<x_i,a>|; the expectation 2/(d B(d/2,1/2)) yields the stated constant. The asymptotic equality does rely on the imported lower bound [15, Thm 7], but that is a cited theorem, and the paper's own star computation independently matches the constant. The proof gaps noted by the reader are localized and repairable: in Claim 2.3, when a subtree is exactly {xy}, the imbalance is f(xy) = -f(yz), which is realized by the subtree {yz} of T', so equality still holds. Claim 2.4 and Theorem 1.4 are sketchy, but they concern the secondary result and do not undermine Theorem 1.2.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the d-dimensional discrepancy of subtrees of a tree T, denoted D_d(T), and the oriented counterpart D⃗(T). Its main result, Theorem 1.2, states that for every tree with ℓ leaves, D_d(T) = (1+o(1)) ℓ/(d B(d/2,1/2)), confirming a conjecture of Krishna, Michaeli, Sarantis, Wang and Wang. The second result, Theorem 1.4, states that D⃗(T) = (1/2+o(1))ℓ, confirming a related conjecture. The upper bound is obtained by a random construction on stars (with an ε-net and concentration arguments), a decomposition of the tree into a star forest and a remainder tree, and an induction on the number of leaves; the lower bound is imported from Theorem 7 of [15].","tokens_in":7481,"tokens_out":30287,"duration_ms":263982,"significance":"The result is a natural tight asymptotic in discrepancy theory for trees and confirms two conjectures from [15]. The random construction is elegant, the constant matches the star case, and the lower bound from [15] is correctly invoked. The paper does not include machine-checked proofs or code, but the probabilistic estimates are standard and the main ideas are sound. However, the proof as printed contains a false inequality in the main decomposition in §2, Eq. (7), and a local gap in Claim 2.3; both are repairable. The proof of the secondary theorem, Theorem 1.4, is only sketched and needs to be written out.","major_comments":[{"comment":"The inequality ∑_{i=1}^r D_d(F_i) ≤ max_{a∈S^d} R_a ≤ φ(ℓ_F) is false in general. For example, take a path v_1...v_m and attach two leaves to each v_i; after the reduction in Claim 2.3, each F_i is a star with two leaves (or one leaf at the endpoints), and for each such small star D_d(F_i)=1. Hence the left-hand side equals Θ(m), while φ(ℓ_F) ∼ ℓ_F/(dB(d/2,1/2)) = (1+o(1))m/2 for d=2, and more generally the leading constant 1/(dB) is < 1. This makes the derivation of (8) invalid as printed. The intended argument can be repaired by proving directly that, with a single random coloring of all edges of F as in Lemma 2.1, the contribution of F to any subtree of T has norm at most φ(ℓ_F), yielding D_d(T) ≤ D_d(R)+φ(ℓ_F). The current (6)–(7) transition should be rewritten accordingly.","section":"§2, Eq. (7)"},{"comment":"The proof of (5) does not cover subtrees \\hat T that contain the edge xy but not yz. The only such connected subtree is {xy}, and the displayed equality would read f(xy)=0, which is generally false. The claim is still true because |f(xy)|=|f(yz)| and the imbalance of {xy} is realized by the subtree {yz} of T', but this exceptional case must be handled explicitly. Since Claim 2.3 is used repeatedly in the induction for Theorem 1.2, this is a load-bearing gap.","section":"§2, Claim 2.3"},{"comment":"The proof of Theorem 1.4 is only sketched. The construction of \\hat T' from \\hat T in Claim 2.4 is described in prose ('cutting terminal paths', 'similarly to the previous case') without a precise invariant that the two sums differ by at most one, and the case where the root r lies outside T' is not fully justified. The 'analogue of Lemma 2.1 for oriented discrepancy' is never stated or proved. Since Theorem 1.4 is one of the two main results, these arguments should be written out in full.","section":"§2, Claim 2.4 and proof of Theorem 1.4"}],"minor_comments":[{"comment":"The phrase 'for x sampled uniformly at random in S^{d-1}' should read 'in S^d': the density computation that follows (with measure sin^{d-1}θ dθ) is for S^d, and the formula E[|⟨x,a⟩|] = 2/(d B(d/2,1/2)) is correct for x ∈ S^d.","section":"§2, Claim 2.2"},{"comment":"The expression '⃗D(S_d)' should be '⃗D(S_ℓ)': S_d denotes the d-sphere, while the star with ℓ leaves is S_ℓ.","section":"§2, proof of Theorem 1.4"},{"comment":"The notation ⟨x_i · a⟩ is unusual; please use ⟨x_i, a⟩ consistently.","section":"§2, Lemma 2.1"},{"comment":"The first inequality in (4), D_d(S_ℓ) ≤ max_{ε_i ∈ {−1,1}} ‖∑ ε_i x_i‖, is true but merits a sentence: subtrees of the star correspond to 0/1 choices of elements of K, and any such choice is dominated in norm by some ±1 choice over the pairs.","section":"§2, Eq. (4)"}],"recommendation":"major_revision","confidential_remarks":"The central result is very likely correct and the paper is worth publishing after a careful revision. The main issue is the false inequality in Eq. (7); without rewriting the (6)–(7) transition, the proof of Theorem 1.2 is invalid as printed. I would ask the authors to replace that transition with the direct random-coloring argument, to patch the exceptional case in Claim 2.3, and to expand the proof of Theorem 1.4 so that Claim 2.4 is fully justified."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this note proves the expected tight asymptotic for subtree discrepancy, ℓ/(d B(d/2,1/2)), and settles the oriented version at ℓ/2. The main ideas—random antipodal pairs, epsilon-nets, leaf-pruning decomposition—are right, and the paper is worth engaging with, but the write-up has a few genuine rough spots. What's new: Theorem 1.2 confirms the conjecture from Krishna et al. for every d, not just d=1; Theorem 1.4 confirms the oriented conjecture. The star lemma is clean: sample ℓ/2 antipodal pairs, union-bound over an epsilon-net, and get the constant from E|<x,a>| = 2/(d B(d/2,1/2)). The reduction of a general tree to a star forest plus a residual tree with geometrically decaying leaf count is the right structural argument. Soft spots, in proportion. The reader flagged a numerator/denominator typo in the constant, but that does not reproduce in the version I read: Theorem 1.2 has B in the denominator, consistent with the proof. That concern is a false positive. The real issues are smaller. Claim 2.3's proof of equality (5) is not literally correct: for the subtree consisting only of the pendant edge xy, the sum is −f(yz), not what their subtraction of both xy and yz gives. The equality of maxima still holds because {yz} in T' has the same norm, so the claim survives with a sentence added. Claim 2.4 is sketchy—phrases like \"one can ensure\" and \"similarly\" carry real weight, and the final induction for Theorem 1.4 is compressed. None of this threatens Theorem 1.2, but a referee should ask for a cleaned version, especially since the paper sells itself as a note. The lower bound is imported from [15, Thm 7]. That is legitimate—it is a published theorem—but the asymptotic tightness is only as solid as that external result. The paper's own star computation independently matches the constant, which is reassuring. Who for: anyone working in combinatorial discrepancy or geometric discrepancy on graphs. It is a note, so do not expect broad impact, but it resolves two open conjectures cleanly. I would send it to a serious referee; with the proof details fixed, it should be publishable.","headline":"A short, correct-looking proof of the conjectured tight discrepancy for subtrees, with a few localized write-up gaps that a referee should ask to be fixed before publication.","tokens_in":669,"tokens_out":682,"would_cite":true,"duration_ms":30518,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C05","05C15","11K38"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the discrepancy of any tree's subtrees is asymptotically $\\ell/(d\\,B(d/2,1/2))$, confirming the earlier conjecture on tightness.","keywords":["discrepancy theory","tree discrepancy","subtrees","sphere colorings","oriented discrepancy","epsilon-nets","asymptotic tightness","Beta function"],"falsifier":"For $d=2$, the theorem predicts that a star with $\\ell$ leaves has discrepancy $(1+o(1))\\ell/4$, since $B(1,1/2)=2$. A numerical or exact computation of $\\min_f \\max_{S'\\subseteq S_\\ell}\\|\\sum_{e\\in S'} f(e)\\|$ for a large $\\ell$ that falls below $\\ell/4$ by a constant fraction would refute the lower bound, while a value above $\\ell/4+O(\\ell^{3/4})$ would refute the upper bound.","tokens_in":7105,"feed_emoji":"🌳","tokens_out":11504,"duration_ms":102796,"temperature":0.7,"pith_summary":"For every fixed dimension $d$, the paper proves that any tree with $\\ell$ leaves has $d$-dimensional subtree discrepancy $\\frac{\\ell}{d\\,B(d/2,1/2)}(1+o(1))$, where $B$ is the Beta function. This matches a lower bound proved in the earlier paper [15], confirming the conjecture that the lower bound is asymptotically tight. The proof constructs a coloring for stars by random antipodal pairs of vectors on the sphere and then reduces an arbitrary tree to a star forest by pruning leaves whose neighbor has degree two. The same construction settles the oriented version: the oriented discrepancy of subtrees is $(1/2+o(1))\\ell$. The constant matters because it gives the exact asymptotic cost of balancing all connected subtrees of a tree simultaneously, and it links vector discrepancy to ordinary color discrepancy through the regular simplex identity.","feed_headline":"Leaf-count formula settles subtree discrepancy conjecture","feed_subtitle":"A random antipodal sphere coloring balances every subtree at the lower-bound constant; oriented discrepancy is half the leaves.","key_machinery":"Three objects carry the proof. First, the random antipodal star coloring: choose $\\lceil \\ell/2\\rceil$ points $x_i$ uniformly on $\\mathbb{S}^d$ and color each leaf by either $x_i$ or $-x_i$; the maximum imbalance of a subtree is controlled by $R_a=\\sum_i|\\langle x_i,a\\rangle|$, whose expectation per pair is $2/(d\\,B(d/2,1/2))$, and an $\\varepsilon$-net on the sphere turns the supremum over directions $a$ into a finite union bound. Second, Claim 2.3: if a leaf's neighbor has degree two, deleting that leaf edge does not change $D_d$, so every tree can be pruned into a skeleton with no degree-two parents of leaves. Third, the star-forest decomposition: split the pruned tree into a star forest $F$ and a residual tree $R$ whose leaf counts shrink geometrically, apply the star bound to each component, and sum via the triangle inequality.","core_discovery":"The central discovery is that the lower bound $D_d(T)\\ge \\ell/(d\\,B(d/2,1/2))$ is tight up to a factor $1+o(1)$ for every fixed $d$, so the leaf count is the only asymptotic parameter that controls subtree discrepancy. The paper proves this by establishing the matching upper bound: for stars, $\\ell/2$ random antipodal pairs on $\\mathbb{S}^d$ make the worst subtree sum at most $\\ell/(d\\,B(d/2,1/2)) + O(\\ell^{3/4})$ with positive probability; for general trees, repeated application of a pruning claim reduces the tree to a star forest with geometrically decaying leaf counts, and summing the star bounds yields the main theorem. The same decomposition, with an oriented pruning claim that loses at most one unit per step, gives $\\vec D(T)=(1/2+o(1))\\ell$ and settles the second conjecture.","pith_inferences":["Extrapolating from the method, the star proof actually yields a quantitative error term $O(\\ell^{3/4})$; tracking the constants in the $\\varepsilon$-net and Chernoff steps could turn the main $o(1)$ statement into an explicit finite-$\\ell$ bound.","The pruning decomposition depends only on the degree-two parent structure, so a similar leaf-count-driven constant may hold for forests, or for trees with weighted edges, by summing over components.","If the imported lower bound could be proved directly, the same upper-bound machinery would upgrade the identity from asymptotic to exact at the level of the leading constant; the remaining gap is the black-box lower bound, not the construction.","A natural next target is the second-order term, which the proof suggests should be $O(\\ell^{3/4})$ for stars but may depend on the tree's diameter for general trees."],"forward_implications":["The exact constant $\\ell/(d\\,B(d/2,1/2))$ determines the asymptotic discrepancy for every fixed dimension $d$, so dimension enters only through the Beta factor $B(d/2,1/2)$ and the leaf count is the sole structural parameter.","Because the same pruning works for all trees, the result shows that the asymptotic discrepancy is universal across trees with the same number of leaves; topology beyond leaf count only affects lower-order terms.","Through the regular-simplex identity, the vector bound transfers to $(d+1)$-colourings, giving matching-order bounds on the combinatorial discrepancy of subtrees.","The oriented discrepancy statement $\\vec D(T)=(1/2+o(1))\\ell$ confirms the second conjecture and shows that an optimal orientation can balance rooted oriented subtrees only up to half the leaf count."],"supporting_citations":[{"why":"Supplies the lower bound $D_d(T)\\ge \\ell/(d\\,B(d/2,1/2))$ that Theorem 1.2 must match; the upper-bound proof imports it as a black box.","marker":"Theorem 7 in [15]"},{"why":"Supplies the lower bound $\\vec D(T)\\ge \\lceil \\ell/2\\rceil+1$ that Theorem 1.4 asymptotically matches.","marker":"Theorem 4 in [15]"},{"why":"Guarantees the existence and size of an $\\varepsilon$-net on $\\mathbb{S}^d$, which is used to discretize the maximum projection in the star case.","marker":"Lemma 5.2 in [17]"}],"fun_headline_variants":["Leaf count settles subtree discrepancy","Tight leaf-count bound for tree discrepancy","Subtree discrepancy: leaf count is asymptotic","Conjecture on subtree discrepancy resolved"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The tightness claim rests on two steps taken as given: the imported lower bound $D_d(T)\\ge \\ell/(d\\,B(d/2,1/2))$, and the pruning equality that deleting a leaf edge from a degree-two neighbor leaves the discrepancy unchanged; the written proof of the pruning step skips the single-edge case.","fun_headline_variants_meta":{"raw":{"variants":["Leaf count settles subtree discrepancy","Tight leaf-count bound for tree discrepancy","Subtree discrepancy: leaf count is asymptotic","Conjecture on subtree discrepancy resolved"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000354,"raw_usage":{"total_tokens":1872,"prompt_tokens":837,"completion_tokens":1035,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":453,"completion_tokens_details":{"reasoning_tokens":984}},"tokens_in":453,"tokens_out":1035,"duration_ms":9699,"temperature":1.0,"reasoning_tokens":984,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T21:43:15.330409+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $d=2$, the theorem predicts that a star with $\\ell$ leaves has discrepancy $(1+o(1))\\ell/4$, since $B(1,1/2)=2$. A numerical or exact computation of $\\min_f \\max_{S'\\subseteq S_\\ell}\\|\\sum_{e\\in S'} f(e)\\|$ for a large $\\ell$ that falls below $\\ell/4$ by a constant fraction would refute the lower bound, while a value above $\\ell/4+O(\\ell^{3/4})$ would refute the upper bound.","supporting_citations":[],"review_version":1}