{"id":"a7c3e877-22b5-43fb-a8fe-dc4804a7088c","arxiv_id":"2411.18131","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors derive bivariate generating functions for the distribution of 22 length-2 mesh patterns on king permutations.","lead":"King permutations are orderings where neighboring entries never differ by exactly 1. This paper derives exact formulas for how often 22 small mesh patterns appear in such permutations, extending a line of work by Kitaev and Zhang.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.6's 'only violation is A ends with b+1' classification is unproved and carries the (t+t^2) factor; an exhaustive test of the decomposition would settle it.","rationale":"The reader's weakest-assumption analysis identified Theorem 4.6's replacement operation as the critical step; I agree that this is the most load-bearing point. My concern also extends to the equally hand-wavy classification of all non-king prefixes as having a single specified violation, and to the matching construction in Theorem 4.7. The formulas are internally consistent and pass the small-n checks, but those checks are too weak to validate the bijection. Since no actual counterexample has been found, the appropriate verdict remains CONDITIONAL: the central claim is plausible and likely correct, but it should not be used as a black box until the almost-king decomposition is either proved carefully or verified by exhaustive computation through n=10. The missing diagrams are a separate expositional defect that also prevents full independent confirmation of the pattern numbering.","tokens_in":14878,"tokens_out":17729,"duration_ms":165531,"concrete_test":"Implement an independent checker for pattern Nr.55 as drawn in [10,15]: generate all king permutations up to n=10, compute the bivariate series E(t,u), and compare every coefficient with Theorem 4.6. Then test the claimed decomposition directly: for each king permutation containing p, choose the occurrence with highest possible a, inspect the induced C and AbB, and verify that either red(AbB) is a p-avoiding king permutation or the only adjacent-value violation is that A ends with b+1, with no occurrence of p created by the insertion. Repeat the analogous 'replace 1 by 21' construction for Theorem 4.7. A single unclassified prefix or a newly created occurrence at n=9 or n=10 refutes the formula.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing step is in Theorem 4.6's equation (23), with the parallel construction in Theorem 4.7. The proof separates every containing permutation into a nonempty part C and a p-avoiding prefix AbB, then asserts that the only non-king prefixes that arise are exactly those whose unique violation is that A ends with b+1, and that inserting a removes this violation without introducing any new occurrence of p. This assertion is not proved; it is precisely what produces the (t+t^2) factor and hence the full formula for P(t). If the true set of possible non-king prefixes is larger, or if the insertion creates an occurrence of p inside AbB, then equations (23)/(24) and (25)/(26) fail, even though all displayed coefficients through t^8 can still match because such failures may first appear at larger n. The u=1, u=0 consistency checks and the small-n expansions do not test this bijection. The missing mesh-pattern diagrams make the claim harder to audit, but the bijection itself is the point that needs independent checking.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper initiates a systematic study of distributions of short mesh patterns on king permutations. It derives bivariate generating functions E(t,u) and avoidance generating functions P(t) for 22 length-2 mesh patterns indexed by the numbering of Kitaev and Zhang, after first obtaining auxiliary series for the strong-fixed-point statistic on king permutations and two restricted classes (Theorem 2.2). Results are divided into 'trivial' cases (Section 3) and further cases (Section 4); Section 5 lists 11 patterns left open. The proofs are bijective and use decompositions of king permutations around a chosen occurrence of a pattern.","tokens_in":15036,"tokens_out":14315,"duration_ms":121847,"significance":"If the formulas are correct, this is a useful and fairly systematic extension of the Kitaev-Zhang census to king permutations, with explicit parameter-free generating functions. The formulas pass basic internal consistency checks: for each pattern, setting u=1 recovers A(t) and setting u=0 recovers the paper's own avoidance series P(t), and the displayed expansions agree with the small coefficients. These checks are encouraging but do not by themselves validate the bijective decompositions used to obtain the formulas.","major_comments":[{"comment":"The proof of the avoidance formula is incomplete. The paper asserts that when an occurrence ab with a chosen as high as possible is removed, every non-king prefix AbB that can appear has as its only violation that A ends with b+1, and that inserting a into that prefix removes the violation without creating a new occurrence of p. This classification is exactly what produces the factor (t+t^2) in Eq. (23); if other non-king prefixes occur, or if the insertion creates an occurrence of p inside AbB, the formula for P(t) is wrong. Please provide a proof of this classification and of the 'no new occurrence' part.","section":"Theorem 4.6, Eq. (23)"},{"comment":"The derivation of the distribution formula uses the relation E*(t,u)=E(t,u)-tE*(t,u), where E*(t,u) is defined as the generating function for king permutations not beginning with the largest element. As written this relation is not correct: it would imply E(t,u)=(1+t)E*(t,u), but prefixing the largest element n to a king (n-1)-permutation that starts with n-1 does not produce a king permutation (for instance, 5 2 4 1 3 with n=6 gives 6 5 2 4 1 3). Since this relation is used to go from Eq. (24) to the closed form for E(t,u), the proof of the distribution formula needs repair; if the printed formula is a typo, the intended relation should be stated and proved.","section":"Theorem 4.6, after Eq. (24)"},{"comment":"The 'almost king permutation' case in the proof of Theorem 4.7 is another unproved load-bearing assertion. The paper claims that replacing the minimum element 1 by 21 in a non-empty p-avoiding king permutation yields a p-avoiding almost king permutation and that this introduces no new occurrence of p; this is what explains the factor t(P(t)-1) and hence the (1+t) factor in Eq. (25). Please provide a proof for this bijection, since an occurrence of p in the resulting AbB would change the avoidance formula.","section":"Theorem 4.7, Eq. (25)"},{"comment":"The manuscript as provided does not display the mesh-pattern diagrams: pattern entries such as 'Nr. 55 =' in Theorem 4.6 are followed by blank space, and Figures 1-11 are absent. Because each theorem is about a specific mesh pattern and the proofs refer to these figures, the paper is not auditable without them. Please include all pattern diagrams, or equivalent coordinate/shading descriptions, in the final version.","section":"All sections (missing figures)"}],"minor_comments":[{"comment":"In the proof of Theorem 4.4, the phrase 'counted by C(t)-1 given by Theorem 3.4' is a cross-reference error; C(t) is introduced in Lemma 2.1, while Theorem 3.4 concerns a different pattern.","section":"Theorem 4.4"},{"comment":"The expression E*(t,u)-1 in equation (24) would benefit from an explicit specification of the constant term of E* and of how the empty permutation is treated in the decomposition.","section":"Theorem 4.6, around Eq. (24)"}],"recommendation":"major_revision","confidential_remarks":"The paper's main mathematical gap is in the unproved bijections behind Theorems 4.6 and 4.7; the consistency checks u=1 and u=0 do not test those bijections. If the authors supply the missing proofs and restore the missing diagrams, the paper is likely to be a solid contribution to the distribution theory of mesh patterns on restricted permutation classes."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this is a genuinely useful paper, not a routine relabeling. King permutations have a different decomposition structure than unrestricted permutations (the leftmost strong fixed point splits into blocks in K^l and K^s), so turning Kitaev-Zhang's machinery onto them takes real work. The authors deliver explicit generating functions for 22 mesh patterns of length 2, with the known king-permutation generating function A(t) as the only external input. No fitted parameters, no circularity: the derivations come from first-principles decompositions, and the consistency checks hold — set u=1 and you get A(t), set u=0 and you get the paper's own avoidance series, and the small coefficients match. That is a solid package.\n\nThe soft spot is exactly where the stress-test note points: the 'almost king' bijection in Theorem 4.6 (and its sister in 4.7) carries the (t+t^2) factor in equation (23). The proof asserts that the only non-king prefix that can arise is one whose sole violation is that A ends with b+1, and that inserting a removes that violation without creating new occurrences of the pattern. That is load-bearing, and it is asserted rather than proved. The small-n expansions do not test it, because a failure of that classification could first appear at larger n. I don't think the formulas are wrong — the same trick appears in both theorems and the stated coefficients line up — but if I were refereeing, I would ask for a proof of that classification, or at least an independent coefficient check up to n=10 or so.\n\nMinor issue: the mesh-pattern diagrams are omitted, so you cannot audit the correspondence between pattern numbers and the schematic figures. That is an editorial shortcoming, not a mathematical one, but it makes the paper harder to check than it should be.\n\nThe six 'impossible' patterns are a trivial observation, but the authors are upfront about that, and the remaining sixteen are substantive. The paper is well-organized, the writing is clear, and the citations are appropriate. It is a modest but honest advance in a specific subfield — the kind of paper that belongs in a good combinatorics journal.\n\nMy recommendation: send it to a serious referee. The central claims look right, and the one genuinely fragile step is local and fixable. I would cite this if I worked on mesh patterns or restricted permutations, and I'd probably assign it in a reading group for graduate students learning generating function techniques. Accept with the request to tighten the almost-king argument.","headline":"Solid, workmanlike enumeration paper extending mesh-pattern distributions to king permutations; the formulas pass consistency checks, but the load-bearing 'almost king' bijection in Theorems 4.6–4.7 needs a real proof before you trust the answers.","tokens_in":15598,"tokens_out":1620,"would_cite":true,"duration_ms":17066,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05A05","05A15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper derives exact distributions for 22 mesh patterns on king permutations.","keywords":["mesh pattern","king permutation","distribution","avoidance","generating function","permutation patterns"],"falsifier":"Enumerate all king permutations of length $n$ for $n=5,6,\\dots,10$ by brute force, compute the total number of occurrences of each of the 22 patterns, and compare the resulting polynomial in $u$ with the coefficient of $t^n$ in the stated $E(t,u)$ from the corresponding theorem. The paper's own initial expansions agree at least through $n=7$ or $8$ for most patterns, so a first mismatch beyond that range would identify a specific formula to correct.","tokens_in":14624,"feed_emoji":"🧮","tokens_out":11203,"duration_ms":78544,"temperature":0.7,"pith_summary":"King permutations are permutations in which consecutive entries never differ by exactly 1. This paper extends the program of enumerating mesh-pattern occurrences to this restricted class, obtaining, for each of 22 short mesh patterns, an explicit bivariate generating function in which the first variable tracks length and the second tracks the number of occurrences. The same formulas yield the avoidance generating function for each pattern as the special case $u=0$. A sympathetic reader would care because such formulas convert a complicated combinatorial statistic into a rational expression in the known generating function of king permutations, making avoidance counts and distribution moments computable in closed form.","feed_headline":"Exact counts for 22 mesh patterns on king permutations","feed_subtitle":"Each formula gives both avoidance and occurrence counts for a short mesh pattern on king permutations.","key_machinery":"The engine of the paper is a decomposition method: identify an extremal occurrence of the target pattern, split the permutation into the blocks left and right of that occurrence, and express the generating function of the whole class as a product or sum of generating functions for smaller, already-understood subclasses of king permutations, namely $A(t)$, $B(t)$ (king permutations not beginning with the smallest element), and $C(t)$ (those not beginning with the smallest element nor ending with the largest). Reverse and complement symmetries reduce the 22 patterns to a smaller number of cases. The resulting functional equations are solved to produce explicit rational formulas in $A(t)$, where $A(t)=\\sum_{n\\ge0} n!t^n(1-t)^n/(1+t)^n$ is the known generating function for king permutations.","core_discovery":"On the paper's own terms, the central discovery is that for 22 mesh patterns of length 2 the distribution generating function $E(t,u) = \\sum_{n\\ge0} t^n \\sum_{\\sigma\\in K_n} u^{p(\\sigma)}$ is a rational expression in the known generating function $A(t)$ of king permutations, and the avoidance generating function $P(t) = E(t,0)$ is likewise rational in $A(t)$. For six of these patterns no king permutation can contain an occurrence, so $E(t,u)=A(t)$; for several others a permutation can contain the pattern at most once, and the generating functions simplify accordingly. The remaining cases are resolved by decomposing a king permutation at the leftmost (or otherwise extremal) occurrence of the pattern and setting up functional equations whose solutions yield the stated formulas.","pith_inferences":["We infer that the leftmost-occurrence decomposition developed here should apply to longer mesh patterns as well, since the block generating functions $A(t)$, $B(t)$, and $C(t)$ recur in every formula and no step seems to depend on the pattern having length exactly 2.","Because $A(t)$ is known explicitly, one could use these formulas to derive asymptotic estimates for the mean and variance of occurrence counts in random king permutations, a direction the paper does not pursue.","The insertion bijection used for patterns Nr. 55 and Nr. 63, replacing the minimum element $1$ by $21$ to repair a single adjacency violation, looks like a general repair operation that might be transplantable to other restricted permutation classes with a similar consecutive-difference condition."],"forward_implications":["For each of the 22 patterns, the coefficient of $t^n$ in the stated $P(t)$ gives the number of king $n$-permutations avoiding that pattern, so avoidance counts can be computed for every $n$ at once.","The bivariate generating functions $E(t,u)$ determine the full distribution of the occurrence statistic, including the probability that a uniformly random king $n$-permutation contains exactly $k$ occurrences.","Six of the patterns are impossible in king permutations, and several others can occur at most once, so their distributions collapse to simple expressions in $A(t)$.","Apart from the six impossible patterns, the 22 distributions are pairwise different, showing that on king permutations no further coincidental equidistributions among these short patterns exist.","The paper explicitly lists ten additional short patterns whose distribution on king permutations remains open, so the enumeration program is not yet complete."],"supporting_citations":[{"why":"Introduces mesh patterns, the object whose distributions are studied here.","marker":"[6]"},{"why":"Supplies the generating function $A(t)$ for king permutations that all later formulas are built from.","marker":"[8]"},{"why":"Provides the numbering of the 22 short patterns and the earlier avoidance classification that this paper extends.","marker":"[10]"},{"why":"Gives the previous distribution results for these patterns on all permutations, the baseline this paper moves to king permutations.","marker":"[15]"},{"why":"Contributes further distribution and avoidance formulas for mesh patterns, including the one additional pattern that remains open for king permutations.","marker":"[16]"},{"why":"Gives the recurrence for the number of king permutations used in the preliminaries.","marker":"[17]"},{"why":"Gives an alternative explicit formula for the king-permutation counts used in the paper.","marker":"[7]"}],"fun_headline_variants":["Exact rational formulas for 22 mesh patterns on kings","King permutations: rational generating functions for 22 patterns","22 mesh patterns on kings: avoidance and occurrence counts","Mesh patterns on kings: 22 exact distribution formulas","Rational generating functions for 22 mesh pattern distributions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For patterns Nr. 55 and Nr. 63 the proofs assume that a non-king prefix whose only violation is that its left part ends with the value one less than the next element can be turned into a king permutation by replacing the minimum element $1$ with $21$, and that this operation neither destroys nor creates any occurrence of the pattern; the formulas for those two patterns stand or fall on that correspondence.","fun_headline_variants_meta":{"raw":{"variants":["Exact rational formulas for 22 mesh patterns on kings","King permutations: rational generating functions for 22 patterns","22 mesh patterns on kings: avoidance and occurrence counts","Mesh patterns on kings: 22 exact distribution formulas","Rational generating functions for 22 mesh pattern distributions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001288,"raw_usage":{"total_tokens":5239,"prompt_tokens":901,"completion_tokens":4338,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":517,"completion_tokens_details":{"reasoning_tokens":4262}},"tokens_in":517,"tokens_out":4338,"duration_ms":25729,"temperature":1.0,"reasoning_tokens":4262,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:30:48.722631+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all king permutations of length $n$ for $n=5,6,\\dots,10$ by brute force, compute the total number of occurrences of each of the 22 patterns, and compare the resulting polynomial in $u$ with the coefficient of $t^n$ in the stated $E(t,u)$ from the corresponding theorem. The paper's own initial expansions agree at least through $n=7$ or $8$ for most patterns, so a first mismatch beyond that range would identify a specific formula to correct.","supporting_citations":[{"cited_title":"Br¨ and´ en and A","cited_arxiv_id":null,"evidence_quote":"Introduces mesh patterns, the object whose distributions are studied here."},{"cited_title":"Flajolet and R","cited_arxiv_id":null,"evidence_quote":"Supplies the generating function $A(t)$ for king permutations that all later formulas are built from."},{"cited_title":"Hilmarsson, I","cited_arxiv_id":null,"evidence_quote":"Provides the numbering of the 22 short patterns and the earlier avoidance classification that this paper extends."},{"cited_title":"Kitaev and P","cited_arxiv_id":null,"evidence_quote":"Gives the previous distribution results for these patterns on all permutations, the baseline this paper moves to king permutations."},{"cited_title":"Kitaev, P","cited_arxiv_id":null,"evidence_quote":"Contributes further distribution and avoidance formulas for mesh patterns, including the one additional pattern that remains open for king permutations."},{"cited_title":"Riordan, A recurrence for permutations without rising or fa lling suc- cessions, Ann","cited_arxiv_id":null,"evidence_quote":"Gives the recurrence for the number of king permutations used in the preliminaries."},{"cited_title":"Claesson, From Hertzsprung’s problem to pattern-rewriting systems, Algebr","cited_arxiv_id":null,"evidence_quote":"Gives an alternative explicit formula for the king-permutation counts used in the paper."}],"review_version":1}