{"id":"c75b31ce-7ea6-4a1c-a267-5ccc02487904","arxiv_id":"1908.03739","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Discrete derivatives of permutations are characterized by consecutive partial-sum sets, and two-valued derivatives are exactly coprime pairs (a,-b), with explicit cyclic constructions.","lead":"This paper introduces the discrete derivative of a permutation, the list of differences between consecutive entries, and characterizes which difference lists can occur. It also solves extremal problems such as the largest possible total variation and the smallest possible maximum step, with explicit constructions.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.8 is false as stated: for n=5, the permutation (3,5,1,4,2) has global variation 11, exceeding the claimed maximum of 8.","rationale":"The reader correctly identifies Theorem 3.8 as the weak point, but the actual defect is stronger than an omitted proof: an explicit n=5 counterexample shows the asserted formula and characterization are false. Since this is a headline extremal result of Section 3, the current manuscript cannot be accepted. Other contributions, including Proposition 2.5, Theorem 2.8, and the even-n Theorem 3.7, appear essentially correct, though Theorem 2.8's quantification is sloppy and Theorem 4.1's odd-n construction contains a fixable typo. The existence of a concrete counterexample to a central theorem outweighs these secondary issues and warrants rejection of the version under review.","tokens_in":18844,"tokens_out":15341,"duration_ms":160165,"concrete_test":"Compute Δ(π) for π=(3,5,1,4,2) ∈ S_5 as |5−3| + |1−5| + |4−1| + |2−4| = 11 and compare it with Theorem 3.8's claimed Δ*_5 = 8. The value 11 exceeds the claimed maximum, so the theorem is refuted as stated without further computation.","verdict_should_be":"REJECT","load_bearing_attack":"The most load-bearing problem is not just that the proof of Theorem 3.8 is omitted; the theorem's statement is false. For n=5 the claimed maximum is Δ*_5 = (3·25 − 6·5 − 13)/4 = 8. But π=(3,5,1,4,2) ∈ S_5 gives Δ(π) = |5−3| + |1−5| + |4−1| + |2−4| = 2+4+3+2 = 11, exceeding 8. This π is also mid-alternating in the sense of the theorem (with k=2, adjacent entries alternate across the middle value 3) and satisfies {π1,π5} = {2,3}, so the claimed equality characterization is violated as well. The error is not a small boundary case: the standard coefficient/sign-pattern bound gives the odd-n maximum floor(n^2/2)−1 = (n^2−3)/2, which agrees with the theorem's formula only at n=7. Already for n=9 the theorem predicts 44 while the correct upper bound is 39. Thus the central odd-n extremal result in Section 3 is not merely unproved; it is incorrect as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the discrete derivative D(π) of a permutation as the vector of successive differences, characterizes which integer vectors arise as derivatives (Prop. 2.5), and characterizes two-valued derivatives as coprime opposite-sign pairs (Lemma 2.7, Thm. 2.8). It then studies extremal problems: the minimum possible maximum derivative among 1-Costas permutations (Thm. 3.2), the maximum sum of absolute derivatives (Thms. 3.7 and 3.8), the maximum of the minimum absolute derivative (Thm. 4.1), and a classification of convex permutation matrices (Thm. 4.5). The paper also discusses Costas arrays, Lipschitz permutations, and centrosymmetric variants.","tokens_in":19065,"tokens_out":22862,"duration_ms":216067,"significance":"If the results held, the paper would provide clean extremal characterizations for a natural notion of derivative of a permutation. The characterization in Proposition 2.5 and Theorem 2.8 are elegant and appear correct, as does the even-n global-variation theorem (Thm. 3.7). The paper also gives explicit constructions, which are valuable. However, the odd-n global-variation theorem (Thm. 3.8) is false as stated, and the odd-n minimum-Delta formula in Theorem 3.2 is inconsistent with the paper's own displayed derivative. These are load-bearing errors in the extremal claims of Section 3, and Theorem 4.1 also contains a misprinted construction. The paper is therefore not publishable in its current form, but the errors appear correctable within the manuscript's scope.","major_comments":[{"comment":"Theorem 3.8 is false as stated. For n=5 the formula gives Δ*_5=(3·25−6·5−13)/4=8, but π=(3,5,1,4,2)∈S_5 has Δ(π)=|5−3|+|1−5|+|4−1|+|2−4|=2+4+3+2=11. This π is also mid-alternating with k=2 and {π_1,π_5}={2,3}, so the claimed equality characterization fails as well. The proof is moreover omitted, with only the sentence 'may be shown using the same type of arguments as in the proof of Theorem 3.7, so we therefore omit the proof.' The usual coefficient/sign bound gives the odd-n maximum floor(n²/2)−1=(n²−3)/2, which agrees with the printed formula only at n=7. The theorem must be corrected and proved.","section":"Section 3, Theorem 3.8"},{"comment":"The claimed minimum value of Δ(π) among 1-Costas permutations for odd n is incorrect. In the odd case n=2k+1, the derivative displayed in the proof is (k, −(k−1), …, −1, −(k+1), 1, −2, …, k−1), whose ℓ1-norm is k+(k−1)+⋯+1+(k+1)+1+2+⋯+(k−1)=k²+k+1=(n²+3)/4, not (n−1)²/4+1. For n=5 the printed value is 5, which is already impossible because four distinct nonzero derivative values have absolute sum at least 6. The numerical claim in the theorem must be corrected, and the proof adjusted accordingly.","section":"Section 3, Theorem 3.2"},{"comment":"The odd-n construction in the proof of Theorem 4.1 is not a permutation as printed. With n=2k+1, the displayed sequence π(n)=(1,k+1,2,k+2,3,k+3,…,k−1,n−1,k+1) repeats k+1 and omits n; for n=7 it gives (1,4,2,5,3,6,4), which is not in S_7. The displayed derivative (k+1,k,k+1,k,…,k,k+1) is inconsistent with that sequence. The proof of the lower bound for odd n needs a corrected explicit construction, such as alternating the two halves with a single shift.","section":"Section 4, Theorem 4.1"}],"minor_comments":[{"comment":"In the converse part, the construction π=(s+1,1,2,3,…,s,s+2,…,n) is not a permutation when s=0; the case s=0 should be handled separately.","section":"Section 2, Proposition 2.5"},{"comment":"The statement of Theorem 2.8 is logically tangled: it assumes '1≤a<b≤n−1' and then concludes 'there exists an integer n'. The theorem should state that for every relatively prime a,b with 1≤a<b there exists a permutation of order n=a+b realizing (a,−b).","section":"Section 2, Theorem 2.8"},{"comment":"The derivative list in Example 3.4 contains the value 3 twice; according to the formula in Theorem 3.2 it should be (6,−5,4,−3,2,−1,−7,1,−2,3,−4,5).","section":"Section 3, Example 3.4"},{"comment":"The proof of Theorem 4.5 is very compressed, especially Cases 4 and 5, where phrases such as 'by checking the possible derivatives' and 'one derives' stand in for a detailed case analysis. Please expand these arguments so that the classification is verifiable.","section":"Section 4, Theorem 4.5"},{"comment":"There are several typographical issues throughout, including 'Golumb' for Golomb and 'than' for 'then'; a careful proofreading pass is needed.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"For the editor: I considered rejection because Theorem 3.8 is false as stated, but the correct odd-n maximum is the standard floor(n²/2)−1 and the remaining sections contain sound contributions, so the errors appear correctable within the manuscript's scope. I therefore recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague—\n\nThe headline is that the main odd-n extremal claim is false. Theorem 3.8 states that for odd n the maximum global variation is (3n^2−6n−13)/4 and characterizes equality via mid-alternating permutations with specified endpoints. For n=5 the claimed maximum is 8, but π=(3,5,1,4,2) has variation 11, and it satisfies the stated equality conditions. This is not a boundary typo: at n=9 the theorem claims 44 while the standard coefficient bound gives 39. Section 3's odd case is unsupported and, as written, wrong.\n\nThere is real value here, though. The discrete-derivative framing is natural, and Proposition 2.5—a vector z is a derivative of a permutation iff the partial sums plus 0 form n consecutive integers containing 0—is clean and correct. Theorem 2.8's D-pair characterization (realizing (a,−b) for coprime a<b by a simple cyclic construction) is explicit, checkable, and new to me. The even-n extremal theorem (3.7) looks right; its bounding argument is transparent. The 1-Costas constructions in Theorem 3.2 are explicit and their derivatives are displayed. These are useful pieces.\n\nThe soft spots are more than cosmetic. Theorem 3.8 is not merely unproved—the authors say it follows by the same arguments as even n—it is wrong, so the proof transfer fails. Theorem 4.1's odd-n construction, as printed, is not a permutation (the sequence repeats entries), so the claimed lower bound is not established; it is probably a typo and a correct construction exists, but as written it does not work. Theorem 4.5's case analysis is compressed; the classification of convex permutations may be true, but I would not rely on it without a full expansion.\n\nNet: the paper is a draft that needs a rigorous rework of Section 3 and a careful fix of Theorem 4.1. The good results warrant a referee's time, though the referee will need to verify more than usual. I would not cite it in its present form. If the authors correct the odd-n theorem and tighten the proofs, the remaining parts stand.\n\nRecommendation: send to peer review, with the flag on Theorem 3.8 for the referee to check first.","headline":"Theorem 3.8's claimed odd-n maximum is false — the permutation (3,5,1,4,2) already beats it — but the derivative characterization and D-pair construction are solid, novel pieces worth preserving.","tokens_in":19622,"tokens_out":4002,"would_cite":false,"duration_ms":39265,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05B20","15B48"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper characterizes which integer vectors are discrete derivatives of permutations and determines extremal variation for permutations with distinct derivatives.","keywords":["discrete derivative","permutation matrix","Costas array","1-Costas permutation","D-pair","global variation","local variation","convex permutation"],"falsifier":"Enumerate all $n!$ permutations for a small odd order such as $n=7$ or $n=9$, compute $\\Delta(\\pi)=\\sum_{i=1}^{n-1}|\\pi_{i+1}-\\pi_i|$, and compare the maximum with $(3n^2-6n-13)/4$; a permutation exceeding this value, or attaining it without being mid-alternating and having one of the two allowed endpoint pairs, would refute Theorem 3.8. The $n=7$ case is small enough for direct enumeration.","tokens_in":18615,"feed_emoji":"🧮","tokens_out":12747,"duration_ms":112154,"temperature":0.7,"pith_summary":"The paper introduces the discrete derivative of a permutation, the vector of differences between consecutive entries, and asks which integer vectors can arise. Its central characterization is that $z=(z_1,\\ldots,z_{n-1})$ is a derivative exactly when the set $S_z=\\{0\\}\\cup\\{\\sum_{k=1}^i z_k:1\\le i\\le n-1\\}$ is a set of $n$ consecutive integers containing $0$; since $\\pi$ is uniquely rebuilt from its derivative, this describes the image completely. For two-valued derivatives, the paper proves that, up to reversal and sign change, the only possible pairs are $(a,-b)$ with $1\\le a<b$ and $\\gcd(a,b)=1$, and it exhibits an explicit cyclic construction of order $a+b$ realizing each such pair. It then settles several extremal questions: the smallest possible maximum step among permutations with all distinct derivatives is $\\lceil n/2\\rceil$; the largest possible total variation is $(n^2-2)/2$ for even $n$, with the odd-order analogue $(3n^2-6n-13)/4$ stated; and the convex permutation matrices are exactly four explicit shapes together with their reversals.","feed_headline":"One rule identifies every possible permutation derivative","feed_subtitle":"The derivative determines the permutation; two-valued derivatives are coprime pairs, and extremal variation is pinned down.","key_machinery":"The load-bearing object is the partial-sum set $S_z$ of a candidate derivative; the characterization works because the partial sums of $D(\\pi)$ are exactly $\\pi_2-\\pi_1,\\ldots,\\pi_n-\\pi_1$, so they are the entries of the permutation translated by $-\\pi_1$. The two-valued construction uses cyclic column stepping modulo $a+b$: from a 1 in the first row, move $a$ columns to the right and reduce modulo $a+b$, so each derivative is either $a$ or $a-(a+b)=-b$. The extremal-variation argument rewrites $\\Delta(\\pi)=\\sum_{i=1}^{n-1}|\\pi_{i+1}-\\pi_i|$ as $2\\sum_{i\\in V_+}\\pi_i-2\\sum_{i\\in V_-}\\pi_i$ plus endpoint terms, where $V_+$ are interior peaks and $V_-$ interior valleys; bounding $|V_+|$ and $|V_-|$ by $n/2-1$ yields the even formula and the mid-alternating equality condition. For convexity, Algorithm 1 builds a permutation matrix column by column, maintaining that the rows occupied by the first $k$ columns form an interval, which leads to the four-matrix classification.","core_discovery":"The paper's discovery is a complete description of the discrete-derivative image. For an integer vector $z$, define $S_z=\\{0\\}\\cup\\{\\sum_{k=1}^i z_k:1\\le i\\le n-1\\}$; then $z=D(\\pi)$ for some permutation $\\pi\\in S_n$ if and only if $S_z$ consists of $n$ consecutive integers containing $0$. The reverse direction is witnessed by an explicit permutation built from $S_z$, and the derivative determines $\\pi$ uniquely. The paper calls $(p,q)$ a D-pair when some permutation has derivative values exactly $p$ and $q$, and proves that up to reversal and sign change a D-pair must be $(a,-b)$ with $1\\le a<b$ and $\\gcd(a,b)=1$; the construction places a 1 in the first row and then steps $a$ columns cyclically modulo $a+b$, generalizing the cyclic shift permutation. On the extremal side, it proves that the even-order maximum total variation is $(n^2-2)/2$, with equality if and only if the permutation is mid-alternating (each consecutive pair straddles the median) and its first and last entries are $n/2$ and $n/2+1$; it states the odd-order version with maximum $(3n^2-6n-13)/4$ and the analogous mid-alternating characterization. It also proves $\\max_\\pi \\min_i |D(\\pi)_i|=\\lfloor n/2\\rfloor$ and classifies convex permutations (those whose derivative entries are increasing).","pith_inferences":["The partial-sum criterion reframes the search for Costas permutations as a search over integer vectors rather than over permutations: one can enumerate vectors whose partial sums are consecutive and then test whether every consecutive-block sum is distinct.","The cyclic D-pair construction realizes every coprime pair $(a,-b)$, but the derivatives it produces are only two-valued; testing whether these permutations are $k$-Costas for larger $k$ could provide a structured family for probing the Costas existence conjecture.","If the omitted odd-$n$ proof can be completed along the even-case lines, the even and odd formulas may be expressible as a single parity-dependent expression, and the endpoint conditions hint at a recursive alternating structure around the median."],"forward_implications":["Every integer vector whose partial sums form $n$ consecutive integers containing $0$ is realized by a unique permutation, giving a complete translation between derivative vectors and permutations.","A two-valued derivative $(a,-b)$ exists exactly when $a$ and $b$ are coprime, and the cyclic construction realizes it in order $a+b$; no non-coprime two-valued derivative is possible.","A permutation with all distinct derivatives must have some step of size at least $\\lceil n/2\\rceil$, and the paper's explicit matrices attain this bound for every $n$.","For even $n$, the maximum total variation is $(n^2-2)/2$, attained exactly by mid-alternating permutations whose first and last entries are $n/2$ and $n/2+1$.","If the stated odd formula is correct, the maximum total variation for odd $n$ is $(3n^2-6n-13)/4$, and the extremal permutations are mid-alternating with one of two endpoint pairs."],"supporting_citations":[{"why":"Supplies the standard treatment of permutations and descents that motivates defining the discrete derivative.","marker":"[1]"},{"why":"Supplies the treatment of permutation matrices as (0,1)-matrices on which the paper's matrix viewpoint rests.","marker":"[2]"},{"why":"Defines Costas arrays, the object whose relaxed derivative conditions motivate 1-Costas permutations.","marker":"[5]"},{"why":"Provides structural properties of Costas arrays, including Proposition 1.1 quoted in the introduction.","marker":"[6]"},{"why":"Provides enumeration data for Costas permutations that the paper's 1-Costas counts and open questions extend.","marker":"[9]"}],"fun_headline_variants":["Permutation derivatives: full characterization and extremal bounds","Two-valued derivatives are exactly coprime pairs","Mid-alternating permutations achieve max total variation","Derivative determines the permutation uniquely"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The odd-order maximum-variation theorem is stated without proof; the load-bearing premise is that the even-order bounding argument transfers to odd $n$ without new difficulties, particularly for the middle entry and the endpoint pair $\\{\\pi_1,\\pi_n\\}$. If that transfer fails, the formula $(3n^2-6n-13)/4$ and its characterization are unsupported.","fun_headline_variants_meta":{"raw":{"variants":["Permutation derivatives: full characterization and extremal bounds","Two-valued derivatives are exactly coprime pairs","Mid-alternating permutations achieve max total variation","Derivative determines the permutation uniquely"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000176,"raw_usage":{"total_tokens":1279,"prompt_tokens":921,"completion_tokens":358,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":537,"completion_tokens_details":{"reasoning_tokens":303}},"tokens_in":537,"tokens_out":358,"duration_ms":4322,"temperature":1.0,"reasoning_tokens":303,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:02:58.664492+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all $n!$ permutations for a small odd order such as $n=7$ or $n=9$, compute $\\Delta(\\pi)=\\sum_{i=1}^{n-1}|\\pi_{i+1}-\\pi_i|$, and compare the maximum with $(3n^2-6n-13)/4$; a permutation exceeding this value, or attaining it without being mid-alternating and having one of the two allowed endpoint pairs, would refute Theorem 3.8. The $n=7$ case is small enough for direct enumeration.","supporting_citations":[{"cited_title":"B´ ona,Combinatorics of Permutations , CRC Press, Inc","cited_arxiv_id":null,"evidence_quote":"Supplies the standard treatment of permutations and descents that motivates defining the discrete derivative."},{"cited_title":"Brualdi, H.J","cited_arxiv_id":null,"evidence_quote":"Supplies the treatment of permutation matrices as (0,1)-matrices on which the paper's matrix viewpoint rests."},{"cited_title":"Golomb and H","cited_arxiv_id":null,"evidence_quote":"Defines Costas arrays, the object whose relaxed derivative conditions motivate 1-Costas permutations."},{"cited_title":"Jedwab and J","cited_arxiv_id":null,"evidence_quote":"Provides structural properties of Costas arrays, including Proposition 1.1 quoted in the introduction."},{"cited_title":"Swanson, B","cited_arxiv_id":null,"evidence_quote":"Provides enumeration data for Costas permutations that the paper's 1-Costas counts and open questions extend."}],"review_version":1}