{"id":"0961deac-38bb-4bd3-a90d-1c2a8d19b0b9","arxiv_id":"1908.05246","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For Mallows permutations, the longest common subsequence of two independent copies satisfies a central limit theorem for fixed parameters and an L^p law of large numbers with constant sqrt(6)/3 when the parameters approach 1 with n(1-q) -> infinity.","lead":"This paper proves two limit theorems for the longest common subsequence (LCS) of two random permutations drawn from the Mallows distribution, a probability model that weights permutations by their number of inversions. The first says the LCS is asymptotically Gaussian when both parameters are fixed below 1; the second gives an explicit growth constant when the parameters drift slowly to 1.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Load-bearing gap: Lemma 2.12, quoted from [12] and unproved here, carries the LCS-to-LIS reduction (6) and the E_i bound in Lemma 2.13; Theorem 1 depends on it.","rationale":"The reader's CONDITIONAL verdict is appropriate. The weakest point is Lemma 2.12: Theorem 1's L^p claim requires uniform integrability, obtained only through (6), and the E_i bounds in Lemma 2.13, both via this quoted coupling. If the lemma were false, the proof would not go through even if the statement happens to be true. The other flagged issues are real but less central: the abstract's two-parameter WLLN is not proved by Theorem 1, which assumes identical q_n; and the normalization in (29)-(36) has a √β inconsistency that is reconcilable, since the final constant √6/3 arises from 2\\bar J(β)/√β and the displayed algebra is a scaling slip rather than a fatal error. Lemma 2.14's proof also omits induction details, but Lemma 2.12 is used at more fundamental points. I do not recommend rejection: the quoted lemma is published in [12], and the rest of the paper is structurally coherent. The correct next step is to verify the key lemma independently; hence the verdict stays CONDITIONAL and unchanged from the reader's assessment.","tokens_in":48,"tokens_out":13674,"duration_ms":736600,"concrete_test":"Run an exact exhaustive check of Lemma 2.12 for n≤6: enumerate all index sets a⊂[n], all q∈{0.2,0.5,0.8}, and all y∈S_k (point-mass ν), and verify the stochastic dominance P(LIS(X_a,y)≥t)≤P(LIS(Z_a)≥t) for every threshold t, where X,Z∼μ_{n,q}. A single violation refutes the lemma as stated; if all cases pass, the lemma's use in (6) and Lemma 2.13 is supported in the small-n regime, and the remaining risk is the unproved general proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"At the center of Theorem 1 is Lemma 2.12, a coupling statement quoted from the author's earlier paper [12] and not proved in this manuscript. For any increasing index set a of size k, any 0<q≤1, and any distribution ν on S_k, the lemma asserts the existence of (X,Y,Z) with X∼μ_{n,q}, Y∼ν, Z∼μ_{n,q}, X⊥Y, and LIS(X_a,Y) ≤ LIS(Z_a). This is not a minor technicality: it produces (6), the stochastic bound LIS(π_n,τ_n) ≤ LIS(Z_n) that transfers uniform integrability of |LIS(Z_n)/(n√(1-q))|^p from [3] to the LCS; it is also the step used inside Lemma 2.13 to control the E_i terms. Without Lemma 2.12, the proof of Theorem 1 has no route from LCS to LIS tails, and the block argument in §2.5 loses both the uniform-integrability control and the E_i bound. The lemma is stronger than needed (arbitrary ν rather than only ν=μ_{n,q}), and its proof lives in a separate paper, so it should be singled out for independent verification. The concern is not that the result is implausible—the final constant √6/3 is consistent with the β-regime limit—but that this quoted coupling might fail in the form used here.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the longest common subsequence (LCS) of two independent Mallows-distributed random permutations. Theorem 1 states that if q_n in (0,1), q_n -> 1, and n(1-q_n) -> infinity, then for two independent Mallows(n,q_n) permutations, LCS/(n sqrt(1-q_n)) converges to sqrt(6)/3 in L^p for every p>0. Theorem 2 states that for fixed 0<q,q'<1, there exist constants a=a(q,q')>0 and sigma=sigma(q,q')>0 such that (LCS - a n)/(sigma sqrt(n)) converges in distribution to N(0,1). The proof of Theorem 1 reduces LCS to LIS through a coupling lemma (Lemma 2.12) quoted from the authors' earlier paper [12], then uses a block decomposition and a beta-regime weak law for LCS; the proof of Theorem 2 builds a regenerative process from two independent infinite Mallows permutations and applies a renewal central limit theorem.","tokens_in":22268,"tokens_out":22494,"duration_ms":209865,"significance":"If the results hold, they form a substantial advance: they provide the first weak law and CLT for the LCS of two non-uniform random permutations, with an explicit constant sqrt(6)/3 that is consistent with the beta-regime limit in [12] and with the LIS results of [2,3]. The regenerative CLT is conceptually clean and uses only finite second moments, and the constants are defined explicitly from the stationary distribution rather than fitted. The main risks are the heavy reliance on the external coupling lemma and internal normalization errors in the displayed derivation of the weak-law constant; both appear addressable in revision, so the central claims are plausible but not yet fully supported by the manuscript as written.","major_comments":[{"comment":"Lemma 2.12 is load-bearing but is quoted from [12] and not proved in this manuscript. It produces inequality (6), which is the only route transferring uniform integrability of |LIS(Z_n)/(n sqrt(1-q))|^p from [3] to the LCS, and it is invoked again in Lemma 2.13 for the E_i, F_i, and residual-block terms. If Lemma 2.12 fails in any of these applications, the block argument in Section 2.5 collapses. The lemma is stronger than the paper's own needs, since every application here takes nu to be a Mallows distribution; the authors should either reproduce a proof in an appendix or state and prove a Mallows-only version with nu = mu_{k,q}, and verify explicitly that (6), Lemma 2.13, and the uniform-integrability claim (30) are all covered.","section":"Section 2.3, Lemma 2.12 and its uses"},{"comment":"The abstract claims a weak law in the two-parameter regime n(1-q) -> infinity and n(1-q') -> infinity, but Theorem 1 is stated only for a single sequence q_n used for both permutations. The proof in Sections 2.4 and 2.5 uses one parameter q throughout, and no reduction for q_n different from q'_n is supplied. Either Theorem 1 must be extended to independent Mallows(n,q_n) and Mallows(n,q'_n) with n(1-q_n) -> infinity and n(1-q'_n) -> infinity, or the abstract and introduction must be amended to state the single-parameter result that is actually proved.","section":"Theorem 1 versus the abstract"},{"comment":"As printed, the displayed normalization is internally inconsistent. The beta-regime result Theorem 3 gives X_1 / sqrt(beta(q)/(1-q)) -> 2 Jbar(beta), that is, sqrt((1-q)/beta(q)) X_1 -> 2 Jbar(beta). If Eqs. (29) and (31) are read with sqrt(1-q)/beta as displayed, then Eqs. (34)-(36) do not yield the stated factor 2 Jbar(beta)/sqrt(beta); if they are read with the intended sqrt((1-q)/beta), then Eq. (34) must display the 1/sqrt(beta) factor explicitly. The final constant sqrt(6)/3 is consistent with the intended normalization, but the displayed chain of equations leading to (32) must be corrected before the proof is verifiable.","section":"Section 2.5, Eqs. (29)-(36)"}],"minor_comments":[{"comment":"The displayed inequality 1 - 4 floor(a/(1-q)) >= 1 - 5a/(1-q) > q cannot hold as printed for q close to 1, because the right-hand side is negative. It should presumably be 1 - 4/floor(a/(1-q)) > q, which is the type of condition needed to apply Theorem 1.3 of [3]; please correct the expression.","section":"Section 2.5, proof of Lemma 2.13"},{"comment":"The notation beta is used both for the limiting constant, as in beta(q) -> beta, and for the value in the factor m beta/(n(1-q)) in Eqs. (34) and (35). Since the limit in (35) uses beta(q), the distinction should be made explicit to avoid the appearance of an extra factor.","section":"Section 2.4, Eqs. (11), (34), (35)"},{"comment":"Lemma 2.14 should state explicitly that all three processes are q-Mallows processes with the same parameter q and should specify the law of p'_n; as written, the lemma only asserts independence of {bar p_i} and {p'_i}, not the marginal distributions.","section":"Section 2.6, Lemma 2.14"},{"comment":"The abstract contains grammatical errors ('The Mallows measure is measure on permutations', 'introduce d') and would benefit from a careful editorial pass before resubmission.","section":"Abstract and introduction"}],"recommendation":"major_revision","confidential_remarks":"The manuscript leans heavily on the second author's previous work [12], especially Lemma 2.12 and Theorem 3. The editor may wish to check that the novel contribution, particularly the regenerative CLT in Theorem 2 and the coupling construction in Lemma 2.14, is sufficiently distinct and substantial relative to [11,12]. The normalization typos in Section 2.5 are fixable but must be corrected, since they currently obscure the derivation of the weak-law constant."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know before getting into the details. First, the paper genuinely delivers what the title promises: an L^p law of large numbers for the LCS of two independent Mallows permutations in the heavy-drift regime, with the explicit constant sqrt(6)/3, and a CLT for fixed q,q'. Second, the abstract says more than the theorems prove: Theorem 1 is only stated and proved for identical parameters q_n = q'_n, not the two-parameter regime the abstract advertises. There's also a normalization error in the displayed derivation around equations (29)-(36) that needs sorting out.\n\nWhat's new: Basu-Bhatnagar and Bhatnagar-Peled had the LIS versions; this paper supplies the LCS counterparts. The block-decomposition skeleton is from [3], and the regenerative CLT skeleton from [2], but the reduction from LCS to LIS via the coupling in Lemma 2.12 and the combinatorial exchange lemma 2.14 are the real work. The final constant sqrt(6)/3 is consistent with the beta-regime limit from the second author's earlier paper, which is a good sign the calculation is right.\n\nWhere I'd push back: the abstract overclaim is real. The cross-parameter weak law is never stated or proved; the proof assumes equal parameters from the start. That should be fixed by either proving the general case or rewriting the abstract. The normalization issue: (29) and (31) as printed scale by sqrt(1-q)/beta, but the algebra leading to the final constant requires scaling by sqrt(1-q)/sqrt(beta). As written, the limit would diverge; the final constant shows the intended scaling. A referee should ask for the corrected equations. Finally, Lemma 2.12 is load-bearing and quoted from [12] without proof. That's a published result, so relying on it is legitimate, but since the whole LCS-to-LIS transfer rests on it, a careful referee should check the citation. The proof of Claim 2.15 also omits some induction cases; those look routine.\n\nOverall: the central claims are defensible and the flaws are presentation- and citation-hygiene issues, not load-bearing holes in the mathematics. The paper deserves a serious referee. I'd recommend conditional acceptance after the abstract is corrected, the normalization typo fixed, and the dependence on [12] made explicit.","headline":"Proves the natural LCS analogues of the LIS limit theorems for Mallows permutations; the main results look right, but the abstract overclaims and there's a normalization slip to fix.","tokens_in":22937,"tokens_out":6442,"would_cite":true,"duration_ms":55966,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60F05","60C05","60J10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Two independent Mallows permutations have an LCS obeying an L^p law near q=1 and a Gaussian law at fixed q.","keywords":["longest common subsequence","Mallows permutation","longest increasing subsequence","central limit theorem","law of large numbers","regenerative process","coupling","q-Mallows process"],"falsifier":"Search small cases exhaustively, e.g., $n=4$ or $5$, $0<q<1$, all increasing index sets $a$, and all distributions $\\nu$ on $S_k$ by linear programming, for a violation of the inequality $\\mathrm{LIS}(X_a,Y)\\le\\mathrm{LIS}(Z_a)$; a single violation would invalidate Lemma 2.12 and the proof of Theorem 1. Alternatively, simulate two independent Mallows permutations with $q_n=1-n^{-\\alpha}$ for $\\alpha\\in(0,1)$, compute $\\mathrm{LCS}(\\pi_n,\\tau_n)/(n\\sqrt{1-q_n})$, and check whether the ratio approaches $\\sqrt{6}/3$ as $n$ grows; a persistent downward trend would contradict Theorem 1.","tokens_in":21768,"feed_emoji":"🎲","tokens_out":7844,"duration_ms":77772,"temperature":0.7,"pith_summary":"This paper proves two limit theorems for the length of the longest common subsequence (LCS) of two independent random permutations drawn from the Mallows measure, which weights a permutation by $q$ raised to its inversion count. In the near-uniform regime, $q_n \\to 1$ with $n(1-q_n) \\to \\infty$, it shows that $\\mathrm{LCS}(\\pi_n,\\tau_n)/(n\\sqrt{1-q_n})$ converges in $L^p$ for every $0<p<\\infty$ to $\\sqrt{6}/3$, extending the known weak law for the longest increasing subsequence to the common-subsequence problem. In the fixed-parameter regime $0<q,q'<1$, it shows the LCS is asymptotically Gaussian after affine scaling by a linear term and a $\\sqrt{n}$ term. A sympathetic reader would care because these are distributional limits for the LCS of non-uniform random permutations, with an explicit universal constant where earlier work on random strings gave only bounds.","feed_headline":"Common subsequence length hits sqrt(6)/3 limit","feed_subtitle":"For Mallows permutations, LCS scales deterministically as q nears 1 and turns Gaussian at fixed q.","key_machinery":"The load-bearing object is Lemma 2.12, a domination coupling stated from the earlier paper [12]: for any increasing index set $a$ and any distribution $\\nu$ on $S_k$, there are independent $X\\sim\\mu_{n,q}$, $Y\\sim\\nu$ and $Z\\sim\\mu_{n,q}$ with $\\mathrm{LIS}(X_a,Y)\\le \\mathrm{LIS}(Z_a)$. This inequality converts every LIS upper bound for one Mallows permutation into an LCS upper bound for two permutations, yielding the uniform-integrability step and controlling the error sets in the block decomposition. The remaining machinery is the block decomposition into strips of length $\\beta/(1-q)$ and, for Theorem 2, the regenerative process generated by two independent infinite Mallows insertion processes whose regeneration times are the first return times of the product chain $M_n=\\max\\{M_{n-1},Z_n\\}-1$.","core_discovery":"The central discovery is that the LCS of two independent Mallows permutations can be treated as a longest increasing subsequence (LIS) problem on a point set, and that LIS bounds for a single Mallows permutation can be transferred to the two-permutation setting. The key identity is $\\mathrm{LCS}(\\pi,\\tau)=\\mathrm{LIS}(\\pi^{-1},\\tau^{-1})$, after which Theorem 1 partitions $[n]$ into blocks of size $\\beta/(1-q)$, proves the blockwise LIS contributions are close to i.i.d., and uses a domination coupling to control error terms; uniform integrability upgrades $L^1$ convergence to $L^p$ with the constant $\\sqrt{6}/3$. Theorem 2 builds an infinite Mallows insertion process, defines regeneration times when both permutations have filled $[j]$, bounds the LCS between partial sums of i.i.d. block LCS variables, and derives finiteness of the first two moments of the inter-renewal times through a product Markov chain and Kac's formula; Anscombe's theorem then gives the Gaussian limit.","pith_inferences":["The paper's abstract advertises two parameters $q,q'$ in the near-uniform regime, but Theorem 1 as stated requires $q_n=q'_n$; a genuine two-parameter $L^p$ law would need a two-parameter analogue of Lemma 2.12, which is not supplied here.","If Lemma 2.12 were false, Theorem 1 might still be true, but the proof's uniform-integrability step and the $E_i,F_i,E'_i,F'_i$ bounds would need a different mechanism; the theorem and the lemma should not be conflated.","The regenerative-CLT machinery suggests a testable extension: replacing the geometric insertion variables by other light-tailed discrete distributions should preserve Gaussian LCS fluctuations whenever the product chain has finite second moments.","The constant $\\sqrt{6}/3$ equals $2\\bar{J}(\\infty)/\\sqrt{\\infty}$, suggesting that $\\bar{J}(\\beta)$ may serve as a universal interpolation between the finite-$\\beta$ and near-uniform regimes; one could conjecture that finite-$\\beta$ corrections to the near-uniform law are governed by derivatives of $\\bar{J}$."],"forward_implications":["In the near-uniform regime, the random length $\\mathrm{LCS}(\\pi_n,\\tau_n)$ is concentrated around $0.8165\\, n\\sqrt{1-q_n}$, with convergence in $L^p$ for every finite $p$, not merely in probability.","At fixed $q,q'$, the LCS has Gaussian fluctuations with asymptotic mean $a(q,q')\\,n$ and standard deviation $\\sigma(q,q')\\,\\sqrt{n}$, where $a=\\nu_{0,0}\\,\\mathbb{E}(Y_1)$ and $\\sigma^2=\\nu_{0,0}\\operatorname{Var}(Y_1-aX_1)$.","The regenerative representation makes the constants $a$ and $\\sigma^2$ computable in principle from the stationary distribution of a simple one-dimensional product Markov chain.","Sending $\\beta\\to\\infty$ in the finite-$\\beta$ weak law of [12] recovers the constant $\\sqrt{6}/3$, since $2\\bar{J}(\\beta)/\\sqrt{\\beta}\\to 1/\\sqrt{6}$.","The block argument implies that the block LCS variables are asymptotically i.i.d., so the LCS inherits the concentration behavior of the LIS rather than the slower fluctuations of i.i.d. random strings."],"supporting_citations":[{"why":"Supplies the block-decomposition method, the strip weak law, uniform integrability of the LIS, and the q-Mallows process lemmas used in Theorem 1.","marker":"[3]"},{"why":"Provides Lemma 2.12, the domination coupling, and the finite-\\beta weak law for the LCS used to evaluate block means.","marker":"[12]"},{"why":"Supplies the regenerative-process and product-Markov-chain approach, the infinite Mallows construction, and the CLT for the LIS that Theorem 2 adapts.","marker":"[2]"},{"why":"Gives the limiting LIS constant in the finite $n(1-q)\\to\\beta$ regime used inside each strip.","marker":"[15]"},{"why":"Provides the infinite Mallows$(q)$ insertion process used to build the regenerative coupling.","marker":"[10]"},{"why":"Supplies Kac's formula used to derive finiteness of the second moment of the return time.","marker":"[1]"}],"fun_headline_variants":["Gaussian limit for LCS of Mallows permutations","Mallows permutations: LCS limit is Gaussian","LCS of Mallows approaches Gaussian distribution","Common subsequence of Mallows: Gaussian limit"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The block argument of Theorem 1 rests on Lemma 2.12, imported from the earlier paper [12] and not proved here: for every increasing index set $a$ and every distribution $\\nu$ on $S_k$, the LIS of a Mallows permutation against $\\nu$ is dominated by the LIS of a single Mallows permutation on those indices. If that domination fails for some $\\nu$, the uniform-integrability step and the $E_i,F_i$, and residual-block bounds collapse.","fun_headline_variants_meta":{"raw":{"variants":["Gaussian limit for LCS of Mallows permutations","Mallows permutations: LCS limit is Gaussian","LCS of Mallows approaches Gaussian distribution","Common subsequence of Mallows: Gaussian limit"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000473,"raw_usage":{"total_tokens":2362,"prompt_tokens":967,"completion_tokens":1395,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":583,"completion_tokens_details":{"reasoning_tokens":1335}},"tokens_in":583,"tokens_out":1395,"duration_ms":14626,"temperature":1.0,"reasoning_tokens":1335,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:24:02.074292+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search small cases exhaustively, e.g., $n=4$ or $5$, $0<q<1$, all increasing index sets $a$, and all distributions $\\nu$ on $S_k$ by linear programming, for a violation of the inequality $\\mathrm{LIS}(X_a,Y)\\le\\mathrm{LIS}(Z_a)$; a single violation would invalidate Lemma 2.12 and the proof of Theorem 1. Alternatively, simulate two independent Mallows permutations with $q_n=1-n^{-\\alpha}$ for $\\alpha\\in(0,1)$, compute $\\mathrm{LCS}(\\pi_n,\\tau_n)/(n\\sqrt{1-q_n})$, and check whether the ratio approaches $\\sqrt{6}/3$ as $n$ grows; a persistent downward trend would contradict Theorem 1.","supporting_citations":[{"cited_title":"3-4, 719–780","cited_arxiv_id":null,"evidence_quote":"Supplies the block-decomposition method, the strip weak law, uniform integrability of the LIS, and the q-Mallows process lemmas used in Theorem 1."},{"cited_title":"3, 1311–1355","cited_arxiv_id":null,"evidence_quote":"Provides Lemma 2.12, the domination coupling, and the finite-\\beta weak law for the LCS used to evaluate block means."},{"cited_title":"4, 1934–1951","cited_arxiv_id":null,"evidence_quote":"Supplies the regenerative-process and product-Markov-chain approach, the infinite Mallows construction, and the CLT for the LIS that Theorem 2 adapts."},{"cited_title":"2, 514–540","cited_arxiv_id":null,"evidence_quote":"Gives the limiting LIS constant in the finite $n(1-q)\\to\\beta$ regime used inside each strip."},{"cited_title":"5, 615–639","cited_arxiv_id":null,"evidence_quote":"Provides the infinite Mallows$(q)$ insertion process used to build the regenerative coupling."},{"cited_title":"28 NAYA BANERJEE† AND KE JIN ‡","cited_arxiv_id":null,"evidence_quote":"Supplies Kac's formula used to derive finiteness of the second moment of the return time."}],"review_version":1}