{"id":"c2b3e84e-960d-4192-ba8d-e8fdb9994754","arxiv_id":"2502.07000","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For the new multimodal linear search problem with p modes, the exact optimal competitive ratio is 2p+3+√(8(p+1)) when p is odd, and a specific polynomial root with matching bounds when p is even.","lead":"A single searcher must find a hidden target on a line using one of p possible detection modes, without knowing the target's distance, direction, or the correct mode. This paper finds the exact fastest-possible worst-case search time, expressed as a formula that depends on p and on whether p is odd or even.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Even-p lower bound rests on a false algebraic identity in the k-selection step of Theorem 4; the argument is likely repairable but must be corrected.","rationale":"The reader's verdict is CONDITIONAL, and the most serious defect I find is in the proof of Theorem 4, not in Lemma 3. The reader's flagged 'bare minimum' in Lemma 3 is actually easy to justify: after reaching x_i and eventually returning to the origin, the searcher must have traversed a path from the origin through x_0, x_1, ..., x_i and back, whose length is at least 2Σ|x_j|, so the travel-time lower bound is valid. The false algebraic identity 'w/(w−1)+c−1 = 2c' in the k-selection step is a concrete, checkable error. It does not by itself invalidate the theorem, because the required threshold can be replaced by a different constant and Lemma 3 still supplies exponentially growing lower bounds, so a repair is plausible. However, since the proof as written asks the reader to accept an incorrect equality at a pivotal point, the paper should not be accepted without a correction. This agrees with the reader's CONDITIONAL verdict, so no verdict change is proposed. I set agreement_with_reader to 'partial' because the reader emphasized the travel-time bound in Lemma 3 as the weakest assumption, whereas the more load-bearing issue is the algebraic error in the subsequent k-selection argument, which the reader also noted but did not center.","tokens_in":18075,"tokens_out":27661,"duration_ms":227969,"concrete_test":"Independently re-derive the 'It would suffice' line in the proof of Theorem 4, §3.3. Substitute w=(c+1)/(c−1) into the displayed inequality preceding it, compute the minimal value of |x_k|/w^k needed for the inequality to hold for all sufficiently large i, and compare with the asserted value 2c. Then verify whether Lemma 3 still yields such a k with the corrected threshold, and whether the subsequent recurrence for z_i and the appeal to Lemma 2 go through unchanged. If the corrected threshold still allows k to be chosen, the concern is non-fatal; if not, the even-p lower bound is unproven.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of the even-p lower bound (Theorem 4, §3.3) selects an index k such that |x_k|/w^k is large enough to control the negative constant in inequality (3.5). The text asserts: 'It would suffice to simply have |x_k|/w^k ≥ w/(w−1)+c−1 = 2c.' This equality is false: with w=(c+1)/(c−1), one obtains w/(w−1)+c−1 = (c+1)/2 + c−1 = (3c−1)/2, not 2c. The subsequent bound k ≥ 2ln(c)/ln(1+2/(c^2−c−2)) is derived from this incorrect constant. The step is load-bearing because the splitting of the sums in (3.5) and the later application of Lemma 2 both depend on the chosen k. A corrected constant still appears sufficient: tracing the preceding displayed inequality shows a condition of the form |x_k|/w^k ≥ constant suffices, and Lemma 3 gives exponential growth, so the proof can likely be repaired. Nevertheless, as written the proof has an uncorrected algebraic error at exactly the point where Lemma 3 is used.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a new 'multimodal' variant of linear search in which a searcher moving at speed 1 on the real line must find a stationary target at unknown distance d >= 1, in an unknown direction, and detectable only in one of p initially unknown search modes. The main results are exact competitive ratios: for odd p the optimal ratio is 2p+3+sqrt(8(p+1)), achieved by Algorithm 4; for even p it is the unique root c* of D_p(c) = (c-1)^4 - 4p(c+1)^2(c-p-1) in [2p+1+sqrt(8p), infinity), achieved by Algorithm 5, with explicit bounds 2p+3+sqrt(8(p-1)) <= c* <= 2p+3+sqrt(8p). The upper-bound proofs are explicit, and the lower bounds are based on a period decomposition of any algorithm, on Lemma 2 which rules out certain positive recurrences, and, for even p, on the exponential exploration bound of Lemma 3. A practical variant replaces infinitesimal motion by a finite cell decomposition and achieves competitive ratio c*+epsilon with O(log(p/epsilon)) cell searches per round.","tokens_in":18261,"tokens_out":17565,"duration_ms":139932,"significance":"If the even-p lower bound is repaired as indicated below, the paper gives a clean, tight characterization of a natural generalization of classical linear search, with a genuine parity phenomenon: the optimal ratio has a closed form for odd p but only an implicit polynomial characterization for even p. The constants are parameter-free and falsifiable, and the p=1 special case recovers the classical ratio 9. The upper and lower bounds are derived from first principles rather than fitted to the answer, and the proposed finite-motion epsilon-approximation is an explicit, implementable construction. These are substantial strengths. The paper should be of interest to the search-theory and online-algorithms communities if the technical issues in the even-p lower-bound proof are resolved.","major_comments":[{"comment":"The assertion 'It would suffice to simply have |x_k|/w^k >= w/(w-1)+c-1 = 2c' is arithmetically false. With w=(c+1)/(c-1), one has w/(w-1)=(c+1)/2, so w/(w-1)+c-1 = (3c-1)/2, not 2c. The subsequent sufficient condition and the displayed bound k >= 2 ln(c) / ln(1 + 2/(c^2-c-2)) are computed with the incorrect constant. This step is load-bearing because it is the mechanism by which Lemma 3's exponential growth is injected into inequality (3.5). The error is repairable: any fixed positive constant suffices, since (2/c)(c/(w(c-2)))^k grows without bound, but the proof as written contains an uncorrected algebraic error at exactly the point where Lemma 3 is used. Please correct the constant and re-derive the corresponding k bound.","section":"Section 3.3, proof of Theorem 4 (around inequality (3.5))"},{"comment":"Lemma 3 is essential for the even-p lower bound, yet its proof consists of two unproved assertions: that after reaching x_i and returning to the origin the searcher has spent at least 2*sum_{j=0}^i |x_j| time, and that this forces |x_i| >= (2/c)*sum_{j=0}^i |x_j| under competitive ratio c. Both assertions are true -- the first follows by summing the lengths of the alternating excursions, and the second follows because any coordinate y with |y| < T/c must have been explored by the return time T to avoid exceeding ratio c -- but they are not immediate and should be proved in the text. Since the lemma supplies the exponential lower bound used in Theorem 4, this missing support is load-bearing and should be addressed in the revision.","section":"Section 3.3, Lemma 3"}],"minor_comments":[{"comment":"The argument about positive concave-down sequences and slopes is informal. A concise formal proof of the contradiction, for example by iterating the second-difference inequality or by a standard discrete concavity argument, would improve the rigor of both lower-bound theorems.","section":"Section 3.1, proof of Lemma 2"},{"comment":"The displayed upper bound on the number of cell searches per round is garbled in places, with expressions such as 'p + p + 3(p + 1) + epsilon', 'p + p + 3p + p + epsilon', and '(4 + 18p)/epsilon'. These should be typeset correctly and the derivation of the bound on (c+epsilon-p)(a^2-1) should be shown explicitly.","section":"Section 4, proof of Theorem 6"},{"comment":"The exact sign evaluations of D_p at the two endpoints are delegated to an anonymous Mathematica link. Since these are finite polynomial identities, including the algebra in the paper or in an appendix would make the proof self-contained and archival.","section":"Section 3.3, Theorem 5"},{"comment":"The rendered notation 'c*sqrt(p)+1' is ambiguous and should be typeset clearly as c/sqrt(p+1) or c*sqrt(p+1) as appropriate, to avoid confusion with c*sqrt(p)+1.","section":"Section 3.2 and 3.3, notation"}],"recommendation":"major_revision","confidential_remarks":"The paper is well within the journal's scope and the main claims are likely correct. The algebraic error in Theorem 4 appears to be a genuine typo rather than a conceptual flaw, and the same proof structure should go through with (3c-1)/2 in place of 2c. I would like to see the corrected proof, an expanded Lemma 3, and the self-contained endpoint evaluations before acceptance. The use of an anonymous Mathematica link for central sign checks should be replaced by written algebra."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The paper introduces multimodal linear search, where a searcher has p modes and the target is detectable only in one. That's a natural generalization of Beck-Newman, and the parity distinction is a real insight: odd p, the searcher ends a cell on the opposite side; even p, on the same side. The main result is tight competitive ratios for both cases, with explicit formulas and a clean quartic for even p. The upper bounds are constructive, the lower bounds use the standard period/island machinery, and the c+ε approximation with finite direction changes is a nice practical touch. Table 1 is consistent with the formulas.\n\nThe soft spot is in the proof of Theorem 4. The text asserts w/(w−1)+c−1 = 2c. That's false: w=(c+1)/(c−1), so w/(w−1) = (c+1)/2, and adding c−1 gives (3c−1)/2. The wrong constant is used to select the index k that splits the sums in inequality (3.5), so the even-p lower bound is not rigorously established as written. This is a real flaw, but it looks repairable: Lemma 3 gives exponential growth of the |x_i|, so any constant threshold can be met with a larger k; the k bound changes from 2 ln c / ln(1+2/(c^2−c−2)) to something similar. I'd want the authors to fix this before relying on the lower bound.\n\nThe reader also flagged Lemma 3's 'bare minimum' travel time. I checked it and think it's fine: the shortest path that visits the alternating extremes x_0,...,x_i and returns to the origin has length exactly 2 Σ |x_j|. It deserves a sentence of justification, but it's not a gap.\n\nOverall: the problem is well-motivated, the results are probably correct, and the exposition is clear. The paper is for people in search theory and online algorithms; the parity effect may be worth a reading-group discussion. I'd cite it after the proof patch. For peer review, it should go to a referee rather than be desk-rejected; the error is localized, and fixing it is a matter of careful algebra.","headline":"Solid new variant of linear search with a genuine parity effect; the even-p lower bound has a localized arithmetic error that is repairable but should be corrected.","tokens_in":18827,"tokens_out":6548,"would_cite":true,"duration_ms":50703,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","90B40"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves tight worst-case competitive ratios for multimodal linear search: $2p+3+\\sqrt{8(p+1)}$ for odd $p$ and the root of a quartic for even $p$.","keywords":["autonomous agent","competitive ratio","linear search","multimodal search","search modes","oblivious mobile target","lower bounds","parity"],"falsifier":"Construct a valid $p=2$ search schedule whose period endpoints satisfy $|x_i| < \\frac{2}{c}\\left(\\frac{c}{c-2}\\right)^i$ for $c=10.27303$, the claimed optimal ratio; concretely, return to the origin after reaching period endpoints $1$ and $-2$ in less than $6$ time units while still exploring all coordinates in both modes. Showing such a schedule exists would refute Lemma 3, and exhibiting any $p=2$ algorithm with worst-case competitive ratio below $10.27303$ would refute Theorem 4.","tokens_in":17844,"feed_emoji":"🔍","tokens_out":10649,"duration_ms":94215,"temperature":0.7,"pith_summary":"The paper introduces multimodal linear search, in which a searcher on a line must find a stationary target at an unknown distance and direction, and the target is only detectable when the searcher is using the one correct mode among $p$. It proves the exact worst-case competitive ratio for every $p$, settling the problem. For odd $p$ the optimum is the closed form $2p+3+\\sqrt{8(p+1)}$; for even $p$ it is the unique root of a quartic polynomial, bracketed between $2p+3+\\sqrt{8(p-1)}$ and $2p+3+\\sqrt{8p}$. The parity split is structural: with odd $p$ a cell search ends on the opposite side from where it started, while with even $p$ it ends where it started. The optimal strategies require infinitely fine back-and-forth motion, and the paper also supplies a finite-precision variant with competitive ratio $c+\\varepsilon$ that makes the result implementable.","feed_headline":"Exact optimum found for p-mode line search, odd and even split","feed_subtitle":"For p=1 this recovers the classic ratio 9; for larger p it gives exact algorithms plus a near-optimal practical version.","key_machinery":"The load-bearing object is the 'central island' of explored coordinates and the sequence of period endpoints $(x_i,t_i)$ extracted from any algorithm: period $i$ is the time interval during which the island is extended in direction $(-1)^i$, ending at signed coordinate $x_i$. The argument's engine is a recurrence lemma, generalizing a lemma of Beck and Newman, stating that no positive infinite sequence can satisfy $y_{i+2} \\le a y_{i+1} - b y_i$ when $a^2-4b<0$. For odd $p$ the period accounting yields exactly such a bad recurrence unless the ratio is at least $2p+3+\\sqrt{8(p+1)}$; for even $p$, an exponential-growth lemma $|x_i| \\ge \\frac{2}{c}\\left(\\frac{c}{c-2}\\right)^i$ feeds the same recurrence and forces the ratio to the quartic root. The quartic $D_p(c)$ is the sign-determining quantity whose root separates attainable from unattainable ratios.","core_discovery":"On the paper's own terms, the central discovery is that the multimodal linear search problem has a well-defined optimal competitive ratio that depends on the parity of $p$ and on nothing else about the mode structure. The paper constructs an algorithm for odd $p$, alternating exponentially growing intervals searched simultaneously in all modes, and proves its ratio is $2p+3+\\sqrt{8(p+1)}$; for even $p$ it constructs an algorithm that balances a thorough-search phase against a single-cell phase and proves its ratio is the unique root $c$ of $(c-1)^4-4p(c+1)^2(c-p-1)=0$ in $[2p+1+\\sqrt{8p},\\infty)$. Matching lower bounds, built on a period-based decomposition of any searcher's motion and an impossibility lemma for positive sequences, show no algorithm can do better. Thus the problem is exactly solved, with $p=1$ collapsing to the classical ratio $9$.","pith_inferences":["The parity split likely extends to search on any space where the searcher must return to a central point between excursions, such as stars or trees, where the cost of returning depends on whether the last cell search ends at the near or far edge; testing that would clarify whether the quartic root is a line-specific artifact.","The finite-precision $c+\\varepsilon$ algorithm makes turn-cost variants tractable: with a cost per direction change, the exponentially growing cell sizes of the practical procedure can be re-optimized, and the paper's explicit cell-count bound gives a starting point for such an analysis.","Because the even-$p$ ratio lies between the odd-$p$ values for $p$ and $p-1$, the true ratio as a function of $p$ is interleaved by parity, with the even-$p$ value squeezed between adjacent odd-$p$ closed forms.","For a stationary target, the mode structure enters only through the number of modes, not which mode is correct; this suggests the same tight ratios would hold if the correct mode were chosen adversarially online, and a randomized searcher might beat them in expectation, an open direction the paper notes."],"forward_implications":["For $p=1$ the formula gives $9$, recovering the optimal competitive ratio of the classical linear search problem and confirming the generalization.","For odd $p$, a searcher can achieve the exact optimum with an explicit exponential growth factor $1+\\sqrt{2/(p+1)}$; the worst case is a target arbitrarily close to the start of a round.","For even $p$, the optimal ratio is algebraic and can be computed to any precision as the root of a quartic, with explicit bounds in terms of radicals given.","For any $\\varepsilon>0$ there is a strategy whose competitive ratio is within $\\varepsilon$ of optimal and that uses only finitely many direction changes in any finite time interval, with $O(\\log(p/\\varepsilon))$ cell searches per round.","The lower bounds apply to all algorithms, including those with infinitely precise movement, so these ratios are genuinely unbeatable, not merely optimal within the proposed family."],"supporting_citations":[{"why":"Introduces the classical linear search problem with optimal ratio 9; the paper's $p=1$ case must match it, and Lemma 2 generalizes a lemma from this paper.","marker":"[5]"},{"why":"One of the two foundational formulations of linear search that the multimodal problem extends.","marker":"[4]"},{"why":"The other foundational formulation of linear search, establishing the problem lineage and the baseline competitive-analysis setting.","marker":"[6]"}],"fun_headline_variants":["Exact optimal ratio for p-mode line search, odd and even split","Parity rules: optimal ratios for multimodal line search","Multimodal line search solved: tight odd/even ratios","Optimal search with p modes: exact competitive ratios","Odd vs even p: exact ratios for multimodal search"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is a piece of bookkeeping in Lemma 3: once the searcher has reached its furthest explored point in period $i$ and later returns to the origin, it must have travelled at least twice the sum of all period-endpoint distances, and therefore every coordinate within distance $(2/c)$ times that sum must already be explored if the competitive ratio is at most $c$. If some valid search path can return to the origin more cheaply, the exponential lower bound and the even-$p$ optimal ratio fall apart.","fun_headline_variants_meta":{"raw":{"variants":["Exact optimal ratio for p-mode line search, odd and even split","Parity rules: optimal ratios for multimodal line search","Multimodal line search solved: tight odd/even ratios","Optimal search with p modes: exact competitive ratios","Odd vs even p: exact ratios for multimodal search"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000235,"raw_usage":{"total_tokens":1551,"prompt_tokens":1050,"completion_tokens":501,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":666,"completion_tokens_details":{"reasoning_tokens":419}},"tokens_in":666,"tokens_out":501,"duration_ms":5206,"temperature":1.0,"reasoning_tokens":419,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T14:08:54.678399+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a valid $p=2$ search schedule whose period endpoints satisfy $|x_i| < \\frac{2}{c}\\left(\\frac{c}{c-2}\\right)^i$ for $c=10.27303$, the claimed optimal ratio; concretely, return to the origin after reaching period endpoints $1$ and $-2$ in less than $6$ time units while still exploring all coordinates in both modes. Showing such a schedule exists would refute Lemma 3, and exhibiting any $p=2$ algorithm with worst-case competitive ratio below $10.27303$ would refute Theorem 4.","supporting_citations":[{"cited_title":"Beck and D","cited_arxiv_id":null,"evidence_quote":"Introduces the classical linear search problem with optimal ratio 9; the paper's $p=1$ case must match it, and Lemma 2 generalizes a lemma from this paper."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"One of the two foundational formulations of linear search that the multimodal problem extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The other foundational formulation of linear search, establishing the problem lineage and the baseline competitive-analysis setting."}],"review_version":1}