{"id":"3d084437-d4c3-46dc-803b-a917816669c2","arxiv_id":"1908.01382","paper_version":6,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For Mallows(q) permutations, the probability of avoiding pattern 123 decays as q^(n^2/4); avoiding 132 or 213 decays as (1-q)^n; avoiding 312 or 231 has a rate characterized by a functional equation.","lead":"This paper derives precise asymptotic probabilities that a random permutation drawn from a Mallows distribution avoids a length-three pattern. It finds dramatically different decay rates for different patterns, from q^(n^2/4) for 123 to (1-q)^n for 132 and 213.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's explicit LB/UB for 312/231 rely on an unproved assertion that the chosen c is the smallest of the candidate thresholds; the ordering is never demonstrated.","rationale":"After reviewing the proofs of Theorems 1 and 2, I find them essentially correct. The lower bound in (6.1) is justified by (6.10) together with the fact that the product of (1-q^{i_j}) is at most 1; the upper bound follows similarly. The sub-additivity argument in Proposition 3 is valid. In Theorem 2, the union bound over choices of the set {i_1,...,i_m} is suppressed, but the number of such sets is exp(o(n)) because m lies within O(n^alpha) of n with alpha<1, so the missing subexponential factor does not affect the n-th root; thus the exact exponential rate 1-q stands. The only substantive gap is in Theorem 4: the proof selects c as the minimum of candidate thresholds but never proves the required ordering. This is a simple algebraic comparison and likely true numerically, but it is load-bearing because a false ordering would invalidate the explicit UB(q)/LB(q). The reader's weakest assumption identifies exactly this issue. A conditional verdict is appropriate, pending the missing verification; no change to the reader's verdict is needed.","tokens_in":13616,"tokens_out":38239,"duration_ms":322191,"concrete_test":"Verify the four inequalities A3(q) <= A1(q), A3(q) <= A2(q), A4(q) <= A1(q), and A4(q) <= A2(q) for all q in (0,1), where A1 = 1/(1+q), A2 = (1+q+q^2 - sqrt((1+q+q^2)^2 - 4q^2))/(2q^2), A3 = (1 - sqrt(1 - 4q^2(1-q)(1+q^2)))/(2q^2(1+q^2)), and A4 = ((1-q^4) - sqrt((1-q^4)^2 - 4q^2(1-q)(1-q^3)))/(2q^2(1-q^3)). This can be settled by symbolic manipulation (squaring after confirming nonnegativity) or by rigorous interval arithmetic on q in (0,1). If all four hold, the proof of Theorem 4 is completed by adding a short lemma; if any fails, the explicit bounds in (1.21) need revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the proof of Theorem 4 (Section 5), the explicit lower bound LB(q) is obtained by asserting that the right-hand side of (5.4) is the smallest of the three candidate thresholds in (5.1), (5.2), and (5.4), and the explicit upper bound UB(q) is obtained by asserting that the right-hand side of (5.6) is the smallest of (5.1), (5.2), and (5.6). These ordering statements are stated without proof ('It turns out...', 'One can show...'). The derivation of each bound requires the chosen c to satisfy the intermediate inequalities used to reach the later criterion; for the lower bound c must be less than the thresholds in (5.1) and (5.2), and for the upper bound c must likewise be less than those thresholds. If either ordering fails for some q in (0,1), the corresponding bound in Theorem 4 would not follow from the preceding argument. This gap does not affect the qualitative Theorem 3 or the exact results in Theorems 1 and 2, but it leaves the paper's 'rather precise' explicit bounds for tau = 312 and 231 unjustified as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the probability that a random permutation of size n drawn from the Mallows(q) distribution avoids a fixed pattern τ ∈ S3, with q ∈ (0,1). Using the online construction of Mallows permutations, subadditivity, and a generating-function analysis, the author proves that the probability of avoiding 123 decays like q^{n^2/4} in the n^2-exponential scale (Theorem 1), that the probabilities for 132 and 213 decay with exponential rate exactly 1−q (Theorem 2), and obtains a functional equation for the generating function relevant to 312/231 (Proposition 5). Theorem 3 translates finite nested inequalities into lower and upper bounds on the exponential rate, and Theorem 4 gives explicit closed-form lower and upper bounds LB(q) and UB(q) for the 312/231 rate. A duality argument extends the results to q>1 for patterns other than 123.","tokens_in":13866,"tokens_out":16651,"duration_ms":155947,"significance":"The results are substantial and novel. The exact n^2-exponential rate for 123-avoidance under Mallows(q) is a striking super-exponential decay, and Theorems 1 and 2 complement the Stanley–Wilf picture for non-uniform random permutations. The derivations are self-contained, rely on standard tools (online construction, subadditivity, generating functions), and involve no fitted parameters; the numerical 'true values' in the table are computed from the derived functional equations. The main gap concerns the proof of Theorem 4's explicit bounds, which is local and fixable.","major_comments":[{"comment":"The upper-bound derivation requires c to be simultaneously smaller than the right-hand sides of (5.1), (5.2), and (5.6), because the case analysis reaches (5.5) only when c < (5.1) and c < (5.2). The paper states without proof that 'One can show that the right hand side of (5.6) is the smallest of the three.' If this ordering fails for some q ∈ (0,1), then choosing c equal to the right-hand side of (5.6) does not satisfy the hypotheses, and the claimed upper bound UB(q) in (1.21) does not follow from the preceding argument. The same section also asserts, without proof, that the right-hand side of (5.4) is the smallest threshold for the lower bound; that particular ordering claim is not needed for the validity of the lower bound (since c satisfying any one of (5.1), (5.2), or (5.4) suffices), but it should be justified or removed. Please supply the missing ordering proof by elementary algebra, or adjust the statement of Theorem 4 to use a c whose validity is demonstrated.","section":"Section 5, proof of Theorem 4"}],"minor_comments":[{"comment":"The assertion that P^q_{n−⌊n^α⌋}(σ'_1=i_1,...,σ'_m=i_m) is maximized over 1≤i_1<...<i_m≤n−⌊n^α⌋ at {i_1,...,i_m}={1,...,m} is stated as 'readily' without proof. A short argument using the inversion count (the set {1,...,m} minimizes the number of inversions with the complement) would make the proof self-contained.","section":"Section 7, around (7.1)"},{"comment":"The notation B^c_{n,ε} in (7.2) appears to be a typo for B^c_{n,α}, since the event B_{n,α} was defined just above.","section":"Section 7, equation (7.2)"},{"comment":"The 'true value' row in the table contains only four entries (presumably for q=0.1, 0.2, 0.3, 0.4), while the table has columns up to q=0.9. Please clarify which values the 'true value' row refers to and why it is omitted for larger q.","section":"Table after Theorem 4"}],"recommendation":"major_revision","confidential_remarks":"I see no indication of circularity or parameter fitting; the main results are likely correct. The only substantive obstacle is the missing ordering verification in Section 5, which is needed for the upper-bound claim of Theorem 4. If the author can supply that proof or suitably modify the statement, the paper should be acceptable. The paper fits the journal's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper gives the first precise asymptotic rates for length-three pattern avoidance under Mallows distributions, and the main results hold up. Theorem 1's q^{n^2/4} decay for 123 and Theorem 2's 1-q exponential rate for 132/213 are genuinely new. The functional-equation approach for 312/231 is natural and produces explicit bounds.\n\nThe proofs are mostly rigorous. The online construction is used cleanly, and the sub-additivity argument for existence of the n-th root limit is standard. I checked the main steps of Theorems 1 and 2; those proofs are detailed and convincing. The recursion in Proposition 4 gives an elegant route to the generating function.\n\nThe soft spot is Theorem 4. The explicit lower and upper bounds depend on unstated comparisons among the candidate thresholds (5.1)-(5.4) and (5.1), (5.2), (5.6). The paper says 'It turns out' and 'One can show' without providing the verification. It may be a routine algebraic check, but for the claimed explicit formulas to be proved, those orderings need to be demonstrated. This does not affect the qualitative Theorem 3 or the exact Theorems 1 and 2, so it is a gap, not a crash.\n\nTwo smaller things: in Section 7 the monotonicity assertion that the maximum occurs at {1,...,m} is stated as 'readily'; it is plausible but unproved. And Remark 2 cites 'private correspondence' for Panzo's bound; that is not a citable source for a published proof, though the argument is included in the remark, so it is less of an issue.\n\nThe citation pattern looks reasonable. The paper is self-contained from standard Mallows properties. The numerical 'true values' are computed from the derived equations, which is disclosed; they are not used to fit anything.\n\nFor whom: researchers in random permutations and permutation patterns will want this. It deserves a serious referee; with the ordering lemma added, I would accept without reservation. As is, it should be conditionally accepted, with the author asked to fill the algebraic gaps.\n\nRecommendation: send to peer review.","headline":"New, correct asymptotics for Mallows pattern avoidance; Theorem 4's explicit bounds need a small proof patch.","tokens_in":14326,"tokens_out":2871,"would_cite":true,"duration_ms":26600,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60C05","05A05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that avoiding 123 under Mallows(q<1) has probability q^{n^2/4+o(n^2)} and that 132 and 213 decay exponentially at rate 1-q.","keywords":["pattern-avoiding permutation","Mallows distribution","random permutation","inversions","length-three pattern","generating function","subadditive sequences","super-exponential decay"],"falsifier":"Fix $q=1/2$ and compute the weighted count of $123$-avoiding permutations exactly by dynamic programming over inversion counts for $n$ up to a few hundred; Theorem 1 predicts $(1/n^2)\\log P^q_n(S_n(123))\\to \\frac14\\log q\\approx -0.1733$. Drift away from that value would falsify the theorem. The companion check for $132$ is $(1/n)\\log P^q_n(S_n(132))\\to \\log(1-q)\\approx -0.6931$.","tokens_in":13441,"feed_emoji":"📉","tokens_out":12014,"duration_ms":107836,"temperature":0.7,"pith_summary":"This paper studies how likely a random permutation drawn from Mallows($q$)—weights proportional to $q^{\\mathrm{inv}(\\sigma)}$, with $q<1$ favoring nearly sorted permutations—is to avoid a fixed three-letter pattern. For the increasing pattern $123$, it proves the avoidance probability decays like $q^{n^2/4}$: super-exponential decay with sharp constant $1/4$. For $132$ and $213$, it proves the exponential decay rate is exactly $1-q$. For $312$ and $231$, it identifies the rate as the reciprocal of the radius of convergence of a generating function and supplies explicit numerical bounds. The results show that switching from the uniform distribution to a Mallows model changes three-letter pattern avoidance from an exponential rarity to either exponential or super-exponential rarity depending on the pattern.","feed_headline":"Avoiding pattern 123 under Mallows(q) costs q^{n^2/4}","feed_subtitle":"For q<1, the increasing pattern is super-exponentially rare, while 132 and 213 decay at rate 1-q.","key_machinery":"The engine is the online construction of a Mallows permutation: at step $j$, place $j$ with $X_j$ geometric($1-q$) truncated to $\\{0,\\dots,j-1\\}$ numbers to its right. This converts the inversion weight into an independent product, and pattern avoidance is read off from inequalities among the $X_j$; for $123$, avoidance forces the non-maximal $X_j$ values to form a strictly increasing sequence. For $312$ and $231$, the avoidance probabilities satisfy a convolution recursion that, after multiplying by $w_n=\\prod_{l=1}^n(1-q^l)$, gives a generating function $G_q$ obeying the $q$-difference equation $G_q(t)=1/(1-(1-q)tG_q(qt))$; its radius of convergence yields the exponential rate. A subadditivity argument, using that the induced blocks of a Mallows permutation are independent Mallows permutations, guarantees the exponential rate exists for every length-three pattern.","core_discovery":"The central claim is that under Mallows($q$) with $q\\in(0,1)$, the asymptotic avoidance probability splits sharply by pattern. Theorem 1 gives $\\lim_{n\\to\\infty}(P^q_n(S_n(123)))^{1/n^2}=q^{1/4}$, so $P^q_n(S_n(123))=q^{n^2/4+o(n^2)}$: a $123$-avoider is super-exponentially rare. Theorem 2 gives $\\lim_{n\\to\\infty}(P^q_n(S_n(132)))^{1/n}=\\lim_{n\\to\\infty}(P^q_n(S_n(213)))^{1/n}=1-q$, the slowest possible exponential decay since the identity permutation alone contributes a $(1-q)^n$ lower bound. For $312$ and $231$, the paper proves the rate is $1/r(q)$, where $r(q)$ is the radius of convergence of the generating function $G_q(t)=\\sum_n w_n P^q_n(S_n(312))t^n$ satisfying $G_q(t)=1/(1-(1-q)tG_q(qt))$, and Theorem 4 bounds this rate explicitly. It also proves $P^q_n(S_n(312))=P^q_n(S_n(231))>P^q_n(S_n(213))=P^q_n(S_n(132))$ for all $n\\ge3$, and the duality $q\\leftrightarrow 1/q$ transfers the results to $q>1$ with $123$ as the exceptional pattern.","pith_inferences":["The $q^{1/4}$ constant for $123$ is probably the first member of a family: avoiding $12\\cdots k$ under Mallows($q$) should decay like $q^{c_k n^2}$ with $c_3=1/4$; a transfer-matrix computation for $k=4,5$ could test this.","Theorem 1 leaves the subexponential prefactor open; extracting it would tie the proof to known large-deviation results for geometric order statistics and the longest increasing subsequence in Mallows permutations.","The unproved ordering claim behind Theorem 4 can be checked by directly comparing the closed forms in (5.1), (5.2), and (5.6) for all $q$; if it fails, the characterization by $1/r(q)$ would survive but the explicit bounds would need replacement.","The table's 'true values' are numerical, not proven; a worthwhile target is a proof that the $312/231$ rate is monotone or has a closed form."],"forward_implications":["For $q<1$, the expected number of $123$-avoiders among $n$ independent Mallows($q$) permutations is asymptotic to $q^{n^2/4}$; one needs roughly $q^{-n^2/4}$ samples to see one.","For $132$ and $213$, the rate $1-q$ is the minimal possible, so these patterns are only exponentially rare, markedly more common than $123$-avoiders.","For $312$ and $231$, the rate is computable numerically by iterating the functional equation; the explicit bounds in Theorem 4 differ by less than $0.01$ for $q\\le0.5$.","By parameter duality, for $q>1$ the results carry over to every pattern except $123$."],"supporting_citations":[{"why":"Supplies the restriction property that induced blocks of a Mallows permutation are independent Mallows permutations; this is the load-bearing step for subadditivity and the existence of exponential rates.","marker":"[1]"},{"why":"Gives the exact count of length-three avoiding permutations under the uniform measure; this sets the uniform baseline and enters the ratio argument for the $4(1-q)$ upper bound.","marker":"[2]"},{"why":"Provides the product formula for the normalising constant $Z_n(q)$, which underlies the Mallows weights and the estimates in Theorem 1.","marker":"[8]"}],"fun_headline_variants":["Mallows(q) makes pattern 123 super-rare: probability q^{n^2/4}","Pattern 123 avoidance under Mallows(q) decays super-exponentially","Sharp split in Mallows(q): 123 tiny, 132/213 at rate 1-q","Mallows(q) avoidance: 123 costs q^{n^2/4}, others exponential","Duality q↔1/q flips which pattern is exceptional in Mallows"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The explicit upper and lower bounds for the $312/231$ decay rate are valid only if the threshold coming from inequality (5.6) is the smallest of the three candidate thresholds (5.1), (5.2), and (5.6); the paper states this ordering without proof.","fun_headline_variants_meta":{"raw":{"variants":["Mallows(q) makes pattern 123 super-rare: probability q^{n^2/4}","Pattern 123 avoidance under Mallows(q) decays super-exponentially","Sharp split in Mallows(q): 123 tiny, 132/213 at rate 1-q","Mallows(q) avoidance: 123 costs q^{n^2/4}, others exponential","Duality q↔1/q flips which pattern is exceptional in Mallows"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00035,"raw_usage":{"total_tokens":1924,"prompt_tokens":974,"completion_tokens":950,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":590,"completion_tokens_details":{"reasoning_tokens":832}},"tokens_in":590,"tokens_out":950,"duration_ms":8921,"temperature":1.0,"reasoning_tokens":832,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:13:51.433497+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix $q=1/2$ and compute the weighted count of $123$-avoiding permutations exactly by dynamic programming over inversion counts for $n$ up to a few hundred; Theorem 1 predicts $(1/n^2)\\log P^q_n(S_n(123))\\to \\frac14\\log q\\approx -0.1733$. Drift away from that value would falsify the theorem. The companion check for $132$ is $(1/n)\\log P^q_n(S_n(132))\\to \\log(1-q)\\approx -0.6931$.","supporting_citations":[{"cited_title":"and Peled, R., Lengths of monotone subsequences in a Mallows per- mutation, Probab","cited_arxiv_id":null,"evidence_quote":"Supplies the restriction property that induced blocks of a Mallows permutation are independent Mallows permutations; this is the load-bearing step for subadditivity and the existence of exponential rates."},{"cited_title":"Combinatorics of Permutations , Chapman & Hall/CRC, Boca Raton, FL, (2004)","cited_arxiv_id":null,"evidence_quote":"Gives the exact count of length-three avoiding permutations under the uniform measure; this sets the uniform baseline and enters the ratio argument for the $4(1-q)$ upper bound."},{"cited_title":"P., Enumerative Combinatorics","cited_arxiv_id":null,"evidence_quote":"Provides the product formula for the normalising constant $Z_n(q)$, which underlies the Mallows weights and the estimates in Theorem 1."}],"review_version":1}