REVIEW 3 major objections 5 minor 9 references
Permutation Matrices, Their Discrete Derivatives and Extremal Properties
T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The paper characterizes which integer vectors are discrete derivatives of permutations and determines extremal variation for permutations with distinct derivatives.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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).
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Section 3, Theorem 3.8] 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 3, Theorem 3.2] 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 4, Theorem 4.1] 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.
minor comments (5)
- [Section 2, Proposition 2.5] 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 2, Theorem 2.8] 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 3, Example 3.4] 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 4, Theorem 4.5] 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.
- [General] There are several typographical issues throughout, including 'Golumb' for Golomb and 'than' for 'then'; a careful proofreading pass is needed.
Circularity Check
No circularity: the main claims are established by direct proofs and explicit constructions, not by importing their own conclusions.
full rationale
The paper's central derivation chain is self-contained. Proposition 2.5 is proved directly: if z is a discrete derivative, the partial sums are exactly the entries of the permutation shifted by -π_1, giving n consecutive integers containing 0; conversely, the paper explicitly constructs a permutation from any such set of consecutive integers. Theorem 2.8 gives an explicit cyclic modular construction realizing every relatively prime pair (a,-b), and its proof verifies injectivity and derivative values directly. Theorem 3.7 derives the even-n extremal value by an independent coefficient/sign-pattern bounding argument, with equality characterized by the structure of local extrema, not by restating the definition of the maximum. No fitted parameter is renamed as a prediction, and no load-bearing premise is imported from prior work by the authors. The only external result quoted, Proposition 1.1 from Jedwab and Wodlinger, concerns structural properties of Costas arrays and is a side observation, not the basis of the paper's extremal or characterization theorems. The manuscript does omit the proof of the odd-n case, Theorem 3.8, saying only that it 'may be shown using the same type of arguments as in the proof of Theorem 3.7'; that is a completeness gap and a correctness risk, but an omitted proof is not circularity, since the announced method refers to an already established independent argument rather than to the theorem's own conclusion. No circular step can be quoted or exhibited, so the circularity score is 0.
Assumptions & free parameters
assumptions (2)
- standard math Standard arithmetic and combinatorial counting, including telescoping sums and induction, are used throughout.
- standard math The equivalence between adjacent derivative bounds and the L-Lipschitz condition (Equation 18) is used in Section 5.
Cite this review
Pith. "Pith review of Permutation Matrices, Their Discrete Derivatives and Extremal Properties." pith.science (2026). https://pith.science/paper/YDQ2JSIZ
@misc{pith2026190803739,
author = {Pith},
title = {Pith review of: Permutation Matrices, Their Discrete Derivatives and Extremal Properties},
year = {2026},
howpublished = {\url{https://pith.science/paper/YDQ2JSIZ}},
note = {Machine review of arXiv:1908.03739}
}
abstract
For a permutation $\pi$, and the corresponding permutation matrix, we introduce the notion of {\em discrete derivative}, obtained by taking differences of successive entries in $\pi$. We characterize the possible derivatives of permutations, and consider questions for permutations with certain properties satisfied by the derivative. For instance, we consider permutations with distinct derivatives, and the relationship to so-called Costas arrays.
Figures
Reference graph
Works this paper leans on
-
[1]
B´ ona,Combinatorics of Permutations , CRC Press, Inc
M. B´ ona,Combinatorics of Permutations , CRC Press, Inc. Boca Raton, 2004
work page 2004
-
[2]
R.A. Brualdi, H.J. Ryser, Combinatorial Matrix Theory , Cambridge University Press, Cambridge, 1991
work page 1991
-
[3]
Drakakis, A review of Costas arrays, J
K. Drakakis, A review of Costas arrays, J. Appl. Math. , 2006, Mar. 2006, Art. no. 26385. 26
work page 2006
-
[4]
K. Drakakis, An introduction to Costas arrays: http://www1.spms.ntu.edu.sg/∼ccrg/documents/basicTalkSingapore.pdf
-
[5]
S.W. Golomb and H. Taylor, Constructions and properties of Cost as arrays, Proceedings of the IEEE , 72 (9) (1984), 1143–1163
work page 1984
-
[6]
J. Jedwab and J. Wodlinger, Structural properties of Costas a rrays, Adv. Math. Commun., 8 (2014), 241-256
work page 2014
-
[7]
J. Jedwab and J. Wodlinger, The deficiency of Costas arrays, IEEE Trans. Inform. Theory , 60 (2014), no. 12, 7947-7954
work page 2014
-
[8]
J. Jedwab and L. Yen, Costas cubes, IEEE Trans. Inform. Theory , 64 (2018), no. 4, part 2, 3144-3149
work page 2018
Show all 9 references
-
[9]
Swanson, B
C.N. Swanson, B. Correll Jr, and R.W. Ho, Enumeration of parallelo grams in permutation matrices for improved bounds on the density of Cost as arrays, Electron. J. Combin , 23 (2016), no. 1, 1.44, 14 pp. 27
2016
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.