{"id":"6708b658-af24-4821-ab0f-6fd6ebf515a1","arxiv_id":"2411.12718","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"The least k such that every permutation of length n is determined by its multiset of k-subsequence patterns is between exp(Omega(sqrt(ln n))) and O(sqrt(n ln n)).","lead":"This paper proves new upper and lower bounds for how many subsequence fragments are needed to uniquely identify a permutation, improving earlier results from quadratic to roughly the square root of n times log n. This sharpens a well-studied reconstruction parameter and brings permutation reconstruction in line with binary string reconstruction.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Upper bound depends on an unverified Hahn-polynomial estimate; as printed, Eq. (3.2) already fails for n=4, so the F_k lower bound must be checked before Theorem 3.2 is accepted.","rationale":"The central claim is the upper bound; the lower bound follows from the known binary-sequence lower bound via Theorem 2.1, so the explicit Mathematica constant in Theorem 2.2 is not load-bearing. The computer-assisted Lemma 4.3 affects only small n and the exact table, not the asymptotic claims. Theorem 4.1's additive constant has a small gap (the inequality 2√((n−2)ln(n−3)) < n−d−4 is not justified by the displayed condition), but the O(√(d ln d)) bound survives with a larger constant, so it is not the central risk. The decisive step is Theorem 3.2, where a single unproved, likely mis-normalized lower bound on F_k converts the polynomial technique into k-reconstructibility. Because the printed T_i does not satisfy the orthogonality used to derive F_k, the proof as written is incomplete. This does not prove the theorem false; it means the central upper bound is conditional on a precise, verifiable normalization. That matches the reader's CONDITIONAL verdict.","tokens_in":12046,"tokens_out":25797,"duration_ms":231324,"concrete_test":"Use a CAS to evaluate Eq. (3.2) for the printed definition at n=4, i=1, j=0 (or n=5, k=1). If nonzero, try the two natural corrections: T_i with 1/\\binom{n}{j}, or Eq. (3.2) with weight \\binom{n}{x}; for whichever matches [11], recompute F_k at n=7, k=⌈√(8 ln 7)⌉ and n=1000, k=⌈√(1001 ln 1000)⌉ and compare with e^{(k+1)k/(n+1)}−1+1/(n+1). If the inequality fails in the regime used in Theorem 3.2, the upper bound collapses; if it holds under the corrected normalization, the gap is a repairable typo.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The upper bound s(n) ≤ 2⌈√((n−2)ln(n−3))⌉+2 (Theorem 3.2) rests entirely on the estimate F_k > e^{(k+1)k/(n+1)}−1+1/(n+1) imported from [11, Sec. 3.2.1]. With the definitions printed in the paper this cannot be checked, because the claimed orthogonality (3.2) is false: for n=4, T_1(x)=1−8x and ∑_{x=0}^4 T_1(x)=−75≠0, while (3.2) with i=1,j=0 requires 0. Thus either the displayed T_i is missing a combinatorial factor (e.g. a denominator \\binom{n}{j}) or the orthogonality sum is missing a weight \\binom{n}{x}; in both cases Eq. (3.3) does not follow, and the subsequent conclusion F_k>n+1 has no proof in the text. This is the single load-bearing step for the upper bound; if the normalization from [11] does not match Theorem 3.1's unweighted polynomial sums, the O(√(n ln n)) bound is unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the permutation reconstruction problem from k-minors, defining s(n) as the smallest k such that every permutation in S_n is reconstructible from its k-deck. It claims lower and upper bounds s(n) >= 30.811*sqrt(log_3(n+1)) for n >= 16 and s(n) <= 2*ceil(sqrt((n-2)ln(n-3))) + 2 for n >= 7, giving exp(Omega(sqrt(ln n))) <= s(n) <= O(sqrt(n ln n)) asymptotically. It then translates these bounds into improved bounds on N_d, the smallest number such that any permutation of length n >= N_d is (n-d)-reconstructible, obtaining d + exp(Omega(sqrt(ln d))) < N_d < d + O(sqrt(d ln d)). The paper also provides an algorithm and exact or small-interval values of s(n) for n <= 10.","tokens_in":12352,"tokens_out":11097,"duration_ms":100092,"significance":"The claimed improvement over the previous bounds N_d > d + log_2 d and N_d < d^2/4 + 2d + 4 is significant if correct. The reduction of permutation reconstruction to binary-sequence reconstruction (Theorem 2.1), the bivariate polynomial basis lemma (Lemma 3.2), and the sufficient condition in Theorem 3.1 are clean and mostly rigorous. However, the proof of the upper bound relies on an orthogonality statement that is false as printed, so the central upper-bound result is currently unsupported. If the Hahn-polynomial normalization is corrected and the external estimate from [11] is properly matched, the approach may be salvageable.","major_comments":[{"comment":"The claimed orthogonality of the polynomials T_i on [0,n] is false as stated. For n=4, i=1, the displayed formula gives T_1(x)=1-8x, and the sum over x=0..4 of T_1(x) equals -75, which is nonzero and therefore contradicts Eq. (3.2) for j=0. Consequently, the derivation of Eq. (3.3) - in particular the identity (n+1)*sum_x p_k(x)^2 = (n+1)F_k - is invalid, and the subsequent conclusion 'F_k > n+1' in Theorem 3.2 has no proof. The authors must correct the definition of T_i (for example by supplying the missing weight or the correct Hahn-polynomial normalization) or replace the Hahn-polynomial argument entirely.","section":"Eq. (3.2)"},{"comment":"The upper bound depends entirely on the imported estimate F_k > e^{(k+1)k/(n+1)} - 1 + 1/(n+1) from [11, Section 3.2.1], which is not proved in the paper. Because the definition of F_k here uses the T_i and d_i whose orthogonality fails, it is not established that the quantity bounded in [11] coincides with the F_k used in this paper. The authors need to state the exact external theorem with matching notation and either prove the estimate in their setting or give a precise reference that supports the inequality for the specific F_k defined in Section 3.","section":"Theorem 3.2"},{"comment":"The proof of the lower bound relies on the unstated Mathematica assertion that f(30.811*sqrt(log_3(n+1))) <= n for all n >= 16, where f is defined in the proof. This computer check is load-bearing for the specific constant 30.811, and no code, certificate, or rigorous argument is provided. In addition, k is used as a real number in the expression s'(n) >= k+1, although k must be an integer; the statement and proof should use floor or ceiling of the real expression. The authors should either provide the verification or replace the assertion with an analytic argument, and handle the integrality of k throughout.","section":"Theorem 2.2"}],"minor_comments":[{"comment":"The exponent in the displayed inequalities is sometimes written as sqrt(ln n)/(n+1) and sometimes as sqrt(ln n/(n+1)); these are different quantities, and the inequalities should be re-checked and made consistent.","section":"Proof of Theorem 3.2"},{"comment":"The statement that the matrices S and P are 'exactly the same' for the reverse characteristic vectors is not self-evident; the relationship between the row index i, the values ar{S}_j, and the forward characteristic vectors should be spelled out more explicitly.","section":"Algorithm 1, Step 3"},{"comment":"Theorem 2.2 is stated as s(n) >= 30.811 * sqrt(log_3(n+1)), but s(n) is an integer; the statement should use a floor or ceiling of the real expression to be formally correct.","section":"Section 2"},{"comment":"There are minor typos and formatting issues, such as 'parame ter' in the abstract, 'assistant of computers' in Section 4, and inconsistent spacing around 'For' in Example 2.1; these do not affect the mathematics.","section":"Throughout"},{"comment":"The bounds for s(n) in Table II for n=11..14 are derived from the previous N_d results of Raykova; it would improve clarity to explicitly indicate which bound comes from which source.","section":"Table II"}],"recommendation":"major_revision","confidential_remarks":"The paper's lower-bound reduction and the polynomial-basis lemmas are sound and interesting, but the upper-bound proof is invalid as printed because the stated orthogonality (3.2) is false. Since the upper bound is a central contribution, the paper cannot be accepted without a substantial correction to the Hahn-polynomial construction and a careful verification of the imported estimate from [11]. The lower-bound proof also needs a rigorization of the Mathematica assertion. The scope of these fixes is within what a major revision can address, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the lower bound is probably correct and the bivariate basis lemma is a nice piece of work, but the headline upper bound does not follow from the arguments as written. Eq. (3.2) is false: for n=4, T_1(x)=1-8x, and the unweighted sum over x=0..4 is -75, not 0. The orthogonality claim is missing the binomial weight (or the normalization is off), and Eq. (3.3) collapses with it. Since F_k > n+1 is the whole engine behind Theorem 3.2, the O(sqrt(n log n)) upper bound is unsupported in this draft.\n\nWhat is genuinely new and good: the threshold s(n), the clean embedding proof of s(n) >= s'(n), and the bivariate basis lemma (Lemma 3.2) with the resulting sufficient condition in Theorem 3.1. That theorem is a useful reduction. The lower bound s(n) >= 30.811 log_3^{1/2}(n+1) follows from Dudik-Schulman and is fine. The small-n algorithm (Algorithm 1) is a reasonable heuristic, but Lemma 4.3 has no code or certificate, so the exact values s(9)=s(10)=5 should be treated as computational claims.\n\nThe other soft spots are minor by comparison: the Mathematica verification in Theorem 2.2 is not reproducible, and the 'left grows faster' step in Theorem 4.1 could use a few lines of proof. None of these are fatal on their own.\n\nWhere does this leave us? The paper deserves a serious referee because the framework and the lower bound are worth engaging with, and the upper bound may be repairable with a corrected Hahn-polynomial argument. But as submitted, the central asymptotic upper bound should not be accepted. I would send it to review with the expectation of major revision: fix the orthogonality/normalization and re-derive (3.3), or find another polynomial that satisfies Theorem 3.1. If that cannot be done, Theorem 3.2 should be removed or scaled back.","headline":"The lower bound and the bivariate basis lemma are solid, but the upper bound rests on a false orthogonality claim and needs a major fix before it can be trusted.","tokens_in":12869,"tokens_out":6365,"would_cite":false,"duration_ms":55804,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05A05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that the minimum deck size for reconstructing any permutation of length $n$ is between $\\exp(\\Omega(\\sqrt{\\ln n}))$ and $O(\\sqrt{n\\ln n})$, and improves the bounds on $N_d$ from quadratic to $d+O(\\sqrt{d\\ln d})$.","keywords":["permutation reconstruction","k-minors","k-deck","Hahn polynomials","sequence reconstruction","reconstruction from minors","asymptotic bounds"],"falsifier":"Compute $F_k=\\sum_{i=0}^k T_i(-1)^2/d_i$ exactly for the Hahn polynomials used in the paper, with $k=\\lceil\\sqrt{(n+1)\\ln n}\\rceil$ for increasing $n$, and check whether $F_k>n+1$; a single $n$ where the inequality $F_k>e^{(k+1)k/(n+1)}-1+1/(n+1)$ or $F_k>n+1$ fails would break the upper-bound proof. Independently, a brute-force search could falsify the stated $s(n)$ upper bound by finding two distinct permutations of length $n$ with the same $k$-deck for $k=2\\lceil\\sqrt{(n-2)\\ln(n-3)}\\rceil+2$; for $n=11$ this is already within the paper's own algorithmic range.","tokens_in":11804,"feed_emoji":"🧩","tokens_out":19115,"duration_ms":143623,"temperature":0.7,"pith_summary":"The paper asks how many order-preserving subsequences ($k$-minors) of a permutation must be collected before the whole permutation is uniquely determined. It proves that this minimum $k$, written $s(n)$, is at least $\\exp(\\Omega(\\sqrt{\\ln n}))$ and at most $2\\lceil\\sqrt{(n-2)\\ln(n-3)}\\rceil+2$, so the reconstruction threshold is sublinear in $n$. The same result transfers to the older parameter $N_d$, the length beyond which every permutation is determined by its $(n-d)$-minors: the new bounds $d+\\exp(\\Omega(\\sqrt{\\ln d}))<N_d<d+O(\\sqrt{d\\ln d})$ replace the previous $d+\\log_2 d<N_d<d^2/4+2d+4$. A sympathetic reader would care because the upper bound drops from quadratic in $d$ to nearly linear, showing that much less data is needed to identify a permutation than earlier arguments suggested.","feed_headline":"A deck of O(sqrt(n log n)) minors identifies any permutation","feed_subtitle":"New bounds also cut the reconstruction window N_d from d^2 to d + O(sqrt(d log d)).","key_machinery":"The load-bearing machinery is a polynomial basis for reconstruction. For a permutation $z\\in S_k$, the indicator $z_{ij}$ records whether entry $i$ is less than entry $j$; summing these indicators over all minors gives linear statistics $S_{ij}(x)$ of the $k$-deck. The paper proves that the bivariate polynomials $f_{ij}(x,y)=\\binom{x-1}{i-1}\\binom{y-x-1}{j-i-1}\\binom{n-y}{k-j}$, for $1\\le i<j\\le k$, form a basis of all bivariate polynomials of degree at most $k-2$, and that two permutations with equal $k$-decks force $\\sum_{x<y}\\delta_{xy}\\phi(x,y)=0$ for every such polynomial $\\phi$, where $\\delta_{xy}$ compares the two permutations' inversion patterns. This is converted into a univariate certificate: if some polynomial $\\phi$ of degree at most $k-2$ satisfies $\\phi(-1)>(n-2)\\sum_{x=0}^{n-3}|\\phi(x)|$, then every permutation is $k$-reconstructible. The paper constructs $\\phi=p_k^2$ using Hahn polynomials $T_i$ orthogonal on $\\{0,\\ldots,n\\}$, with $p_k=\\sum T_i(-1)/d_i\\,T_i(x)$, and computes $\\Delta(p_k^2)=(n+1-F_k)F_k$, where $F_k=\\sum T_i(-1)^2/d_i$. The imported estimate $F_k>e^{(k+1)k/(n+1)}-1+1/(n+1)$ then yields $F_k>n+1$ when $k\\ge\\sqrt{(n+1)\\ln n}$, making $\\Delta$ negative and completing the certificate.","core_discovery":"The paper's central claim is that the least $k$ for which every permutation of length $n$ has a distinct $k$-deck satisfies $s(n)=\\exp(\\Omega(\\sqrt{\\ln n}))$ and $s(n)=O(\\sqrt{n\\ln n})$. For large $n$ the explicit inequalities are $s(n)\\ge 30.811\\,\\log_3^{1/2}(n+1)$ and $s(n)\\le 2\\lceil\\sqrt{(n-2)\\ln(n-3)}\\rceil+2$. The proof of the lower bound embeds binary sequences into permutations, so a pair of sequences with the same $k$-deck produces a pair of permutations with the same $k$-deck; the lower bound for binary sequence reconstruction then transfers verbatim. The proof of the upper bound shows that equal $k$-decks force all low-degree bivariate polynomial sums over the order-comparison array to vanish, and then exhibits a squared Hahn polynomial whose value at $-1$ dominates its total mass elsewhere; this certifies $k$-reconstructibility once $k\\ge\\sqrt{(n+1)\\ln n}$. From $s(n)$ the paper derives $N_d<d+3\\sqrt{d\\ln d}$ for large $d$, and $N_d>d+\\exp(\\Omega(\\sqrt{\\ln d}))$, which together improve both sides of the previous bounds.","pith_inferences":["The gap between $\\exp(\\Omega(\\sqrt{\\ln n}))$ and $O(\\sqrt{n\\ln n})$ is very wide; if the true $s(n)$ is closer to the lower bound, then $N_d-d$ would be subpolynomial in $d$, which is a testable conjecture by improving the $F_k$ estimate.","The same Hahn-polynomial certificate might transfer to matrix or hypermatrix reconstruction, where the analogue of the $k$-deck is a multiset of submatrices; the condition $F_k>n+1$ gives a concrete sufficient bound one could check numerically in those settings.","The characteristic-vector algorithm implies that certifying non-reconstructibility for larger $n$ can be done without enumerating all $n!$ permutations; applying it to $n=11$ is a feasible next step that would decide whether $s(11)$ is 5, 6, 7, or 8."],"forward_implications":["For large $n$, a deck of about $2\\sqrt{n\\ln n}$ minors is enough to reconstruct every permutation of length $n$, a sublinear amount of data.","For any fixed deficiency $d$, all permutations of length at least $d+O(\\sqrt{d\\ln d})$ are determined by their $(n-d)$-minors, improving the earlier quadratic upper bound on $N_d$.","No universal reconstruction guarantee can hold with decks of size below $\\exp(\\Omega(\\sqrt{\\ln n}))$, so the threshold cannot be pushed to a fixed fractional power of $n$ by this type of argument.","The exact small values are now $s(5)=s(6)=s(7)=4$ and $s(8)=s(9)=s(10)=5$, with $s(11)$ the first undetermined case, lying between 5 and 8."],"supporting_citations":[{"why":"Supplies the estimate $F_k>e^{(k+1)k/(n+1)}-1+1/(n+1)$ that makes the upper-bound certificate $F_k>n+1$ work.","marker":"[11]"},{"why":"Provides the lower bound for binary sequence reconstruction that transfers to permutations via the embedding in Theorem 2.1, and the dual parameter $S(k)$ used in Theorem 2.2.","marker":"[12]"},{"why":"Establishes the previous bounds $d+\\log_2 d<N_d<d^2/4+2d+4$ and supplies small values of $N_d$ used to pin down $s(n)$ for $n\\le 10$.","marker":"[9]"},{"why":"Introduces $N_d$ and proves $N_1=5$, $N_2=6$, $N_3\\le 13$, the base cases for the small-$n$ table.","marker":"[8]"},{"why":"Supplies the polynomial-reconstruction idea for subsequences that the upper-bound argument adapts to permutations.","marker":"[23]"},{"why":"Defines the Hahn polynomials whose orthogonality on $\\{0,\\ldots,n\\}$ is used to compute $\\Delta(p_k^2)$.","marker":"[24]"}],"fun_headline_variants":["Tiny deck of O(sqrt(n log n)) minors identifies every permutation","All permutations identified by O(sqrt(n log n))-minors","Permutation decks need only O(sqrt(n log n)) minors","Improved bounds: reconstruction from O(sqrt(n log n)) minors","Shrinks permutation reconstruction to O(sqrt(n log n)) minors"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the unproved lower bound $F_k>e^{(k+1)k/(n+1)}-1+1/(n+1)$ on a quantity $F_k$ built from orthogonal polynomials; if that estimate fails at the deck sizes considered, the paper gives no other way to certify reconstructibility.","fun_headline_variants_meta":{"raw":{"variants":["Tiny deck of O(sqrt(n log n)) minors identifies every permutation","All permutations identified by O(sqrt(n log n))-minors","Permutation decks need only O(sqrt(n log n)) minors","Improved bounds: reconstruction from O(sqrt(n log n)) minors","Shrinks permutation reconstruction to O(sqrt(n log n)) minors"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000933,"raw_usage":{"total_tokens":4021,"prompt_tokens":1004,"completion_tokens":3017,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":620,"completion_tokens_details":{"reasoning_tokens":2936}},"tokens_in":620,"tokens_out":3017,"duration_ms":22895,"temperature":1.0,"reasoning_tokens":2936,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T17:15:33.294896+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute $F_k=\\sum_{i=0}^k T_i(-1)^2/d_i$ exactly for the Hahn polynomials used in the paper, with $k=\\lceil\\sqrt{(n+1)\\ln n}\\rceil$ for increasing $n$, and check whether $F_k>n+1$; a single $n$ where the inequality $F_k>e^{(k+1)k/(n+1)}-1+1/(n+1)$ or $F_k>n+1$ fails would break the upper-bound proof. Independently, a brute-force search could falsify the stated $s(n)$ upper bound by finding two distinct permutations of length $n$ with the same $k$-deck for $k=2\\lceil\\sqrt{(n-2)\\ln(n-3)}\\rceil+2$; for $n=11$ this is already within the paper's own algorithmic range.","supporting_citations":[{"cited_title":"An improvement of a Borwein– Erd´ elyi–K´ os result,","cited_arxiv_id":null,"evidence_quote":"Supplies the estimate $F_k>e^{(k+1)k/(n+1)}-1+1/(n+1)$ that makes the upper-bound certificate $F_k>n+1$ work."},{"cited_title":"Reconstruction from subse quences,","cited_arxiv_id":null,"evidence_quote":"Provides the lower bound for binary sequence reconstruction that transfers to permutations via the embedding in Theorem 2.1, and the dual parameter $S(k)$ used in Theorem 2.2."},{"cited_title":"Permutation reconstruction from minors,","cited_arxiv_id":null,"evidence_quote":"Establishes the previous bounds $d+\\log_2 d<N_d<d^2/4+2d+4$ and supplies small values of $N_d$ used to pin down $s(n)$ for $n\\le 10$."},{"cited_title":"Permutation reconstruction,","cited_arxiv_id":null,"evidence_quote":"Introduces $N_d$ and proves $N_1=5$, $N_2=6$, $N_3\\le 13$, the base cases for the small-$n$ table."},{"cited_title":"On a reconstruction proble m for sequences,","cited_arxiv_id":null,"evidence_quote":"Supplies the polynomial-reconstruction idea for subsequences that the upper-bound argument adapts to permutations."},{"cited_title":"The hahn polynomials, formulas and an appli cation,","cited_arxiv_id":null,"evidence_quote":"Defines the Hahn polynomials whose orthogonality on $\\{0,\\ldots,n\\}$ is used to compute $\\Delta(p_k^2)$."}],"review_version":1}