REVIEW 3 major objections 4 minor 10 references
Permutations with few inversions are locally uniform
T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read A random permutation with few inversions is locally uniform at small scales, even though globally it hugs the main diagonal.
desk verdict The abstract admits the core proofs are flawed, so the stated theorems are unproven; the conjectured thresholds are new and plausible, and the paper is honest and well-written. 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 argument runs through inversion sequences: write each permutation as $(e_j)$ with $0 \le e_j < j$, where $e_j$ counts inversions ending at position $j$; this turns permutations into a balls-in-boxes model with $m$ balls and capacities $0,1,\dots,n-1$. A position-independence operation $\Psi$ (remove the last value, add a new first value, preserving the inversion count) shifts consecutive patterns rightward, so all positions behave like position 1. The load-bearing approximation is Corollary 10, which says that in a suffix of length $t$ with $s$ balls, when $t \ll s \ll t^2/\log t$ and the per-box cap $r$ exceeds $(1+\varepsilon)(s/t)\log t$, the number of restricted suffixes $|I_{t,s,r}|$ is asymptotic to the unrestricted weak-composition count $\binom{s+t-1}{s}$. This lets the author replace the constrained suffix by an unconstrained composition in the counts $N^{k,\ell}_{n,m}$, and a tripartition of the inversion sequence into a first block $A$ (the patterned part), a middle buffer $B$, and a long suffix $C$ converts that approximation into the threshold formulas in Propositions 11, 14 and 16.
What would settle it
For $n$ up to roughly 40, enumerate all $n$-permutations with $m$ inversions for several $m$ in the range $n \ll m \ll n^2/\log^2 n$, and compare the exact ratio $N^{k,\ell}_{n,m}/N^{k,0}_{n,m}$ with the values predicted by Proposition 14 ($1$, $e^{-\beta}$, or $0$ depending on whether $\ell \ll m/n$, $\ell \sim \beta m/n$, or $\ell \gg m/n$). A sequence where the ratio deviates from these limits while the hypotheses hold refutes the enumeration core, and a direct check of Corollary 10 against exact counts of restricted inversion-sequence suffixes would locate the failure.
Extended reading notes
Core claim
The central object of study is $\sigma_{n,m}$, the uniform random $n$-permutation with exactly $m$ inversions, for $m$ superlinear and subquadratic in $n$. The paper's intended discovery is that local and global structure separate cleanly: for $k = o(\sqrt{m/n})$, the restriction of $\sigma_{n,m}$ to any interval of length $k$ is asymptotically uniform over $\mathcal{S}_k$, meaning each of the $k!$ relative orders occurs with probability $1/k! + o(1)$; this uniformity fails once $k \gg \sqrt{m/n}$, with the probability of a pattern of inversion density $\rho$ in the critical window $k \sim \alpha\sqrt{m/n}$ equal to $e^{(1-2\rho)\alpha^2/4}/k!$ up to a $1+o(1)$ factor. For inversions between two positions at distance $k$, the probability of a descent is $1/2$ for $k \ll m/n$, is $0$ for $k \gg m/n$, and in the window $k \sim \alpha m/n$ equals $(e^\alpha(\alpha-1)+1)/(e^\alpha-1)^2$, always below $1/2$. The write-up also records that a referee found flaws in the proofs, so the author's own abstract concludes that these results have not been established; the core textual claim remains the dichotomy itself.
Load-bearing premise
Everything rests on replacing the constrained tail of a random inversion sequence by an unconstrained list of nonnegative integers with the correct sum at the scale $r = \lceil 2(m/n)\log n \rceil$; if that approximation fails, the enumeration behind all five theorems collapses.
Editorial extensions
If this is right
- If the theorems are correct, the local statistics of $\sigma_{n,m}$ are asymptotically those of a uniformly random permutation at every scale $k = o(\sqrt{m/n})$, so no local sample can reveal that the permutation is nearly sorted.
- The threshold for consecutive-pattern uniformity is exactly $k = \Theta(\sqrt{m/n})$: in the critical window $k \sim \alpha\sqrt{m/n}$, patterns with inversion density $\rho$ appear with probability $e^{(1-2\rho)\alpha^2/4}/k!$ asymptotically, so the local distribution is biased toward increasing patterns.
- The inversion threshold for pairs at distance $k$ is the larger scale $k = \Theta(m/n)$: the probability of a descent is asymptotically $1/2$ below it and $0$ above it, with a critical-window value strictly below $1/2$ that decreases in $\alpha$.
- Together the thresholds imply a clean local–global separation: a permutation in this range is globally very close to the identity in displacement, yet a finite window cannot distinguish it from a uniformly random permutation.
Reading between the lines
- Beyond the paper, the same weak-composition tripartition should control other local statistics (descent counts, increasing runs, pattern densities) at the same thresholds, since the method only uses the total inversion count of the patterned block.
- Beyond the paper, the failure of the approximation at $m = \Omega(n^2/\log^2 n)$ suggests that an extension to larger $m$ will need a different treatment of the suffix cap; the critical-window formulas are local enough that they may survive with modified prefactors.
- Beyond the paper, exact enumeration for $n$ up to roughly 40 could test whether the ratio $N^{k,\ell}_{n,m}/N^{k,0}_{n,m}$ follows the predicted $1$, $e^{-\beta}$, or $0$ trichotomy at the proposed scales, which would locate the proof flaw quickly.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies a uniformly random n-permutation with exactly m inversions, for n << m << n^2/log^2 n, and claims a local-global dichotomy. It asserts that local windows of length k << sqrt(m/n) are asymptotically uniform over S_k (Theorem 1); that in the critical window k ~ alpha sqrt(m/n) the probability of a given pattern tau is ~ exp((1-2 rho) alpha^2/4)/k!, where rho is the inversion density of tau (Theorem 2); that patterns with sufficient inversion density vanish when k >> sqrt(m/n) (Theorem 3); that a pair at distance k is as likely as not to be inverted when k << m/n and almost never inverted when k >> m/n (Theorem 4); and that in the critical window k ~ alpha m/n the inversion probability tends to (e^alpha(alpha-1)+1)/(e^alpha-1)^2 (Theorem 5). The abstract itself states that a referee found flaws in the proofs on pages 9 and 15 that do not seem easily rectifiable, and that the stated results have not been established.
Significance. If the theorems were valid, they would give a clean and interesting local-global dichotomy for sparse permutations, with explicit thresholds and critical-window constants, and would extend the sparse-model analogy initiated by Acan and Pittel. The position-independence bijection in Proposition 8 is elegant, and the idea of approximating inversion-sequence suffixes by unrestricted weak compositions is natural. However, the manuscript's own abstract concedes that the central proofs are invalid and the results are not established. Since the consequences for local uniformity and inversion thresholds all depend on the enumeration machinery in Propositions 11, 14, and 16, the paper cannot in its current form be considered a proof of these claims. The candor of the self-assessment is commendable, but it does not replace a correct argument.
major comments (3)
- [Abstract and Sections 3–4] The abstract contains the statement: 'As pointed out by a referee, there are flaws in the proofs that do not seem easily rectifiable (see comments on pages 9 and 15). So the results stated above have not been established.' This is an explicit admission, within the manuscript itself, that the central derivations are invalid. Because the claimed thresholds and critical-window formulas all rest on the same enumeration scheme, this admission is decisive for the paper's current status as a proof. The manuscript should not be accepted or sent for minor revision while its own text disclaims the validity of its main theorems.
- [Section 2.3 and Theorem 3] The tripartition setup requires r > k (Section 2.3, 'Given some k>0 and r>k'), and Proposition 11 defines B = (r choose 2) - (k choose 2) and b_i = |I_{r-k,i,k}|, quantities that are only meaningful when r > k. Proposition 14, whose proof invokes Proposition 11 with r = ceil(2m/n log n), therefore also inherits the r > k restriction. Theorem 3, however, permits any k >> sqrt(m/n) with no upper bound on k. For instance, with m = n^{3/2} and k = n^{0.6}, one has k >> sqrt(m/n) = n^{0.25} and r ~ 2 n^{0.5} log n < k for large n, so the quantities B and b_i are not defined and the enumeration underlying N_{k,ell}^{n,m} is not available. Thus the claimed threshold behavior covers a range for which the proof does not apply.
- [Page 15, Theorem 5 proof] The proof of Theorem 5 derives the critical-window inversion probability from closed forms for S_uparrow and S_downarrow and then passes to the ratio of the two sums over i. The algebraic identities are asserted without derivation, and the asymptotic step applies pointwise asymptotic equivalences S_uparrow ~ f(y) C_1 and S_downarrow ~ f(y) C_2 to sums over i = 0,...,A, where A ~ r^2/2 can grow; no uniformity in i is supplied. In addition, the abstract specifically flags page 15 as containing a flaw that is not easily rectifiable. Consequently, the critical-window formula in Theorem 5 is not established by the presented argument.
minor comments (4)
- [Theorem 2 proof] The notation 'sum_{phi in [0,1]}' over inversion densities is imprecise; for a given k the sum is over the finite set {j/(k choose 2) : 0 <= j <= (k choose 2)}, and the limiting statement 'where we take limits over those n for which phi (k choose 2) in N' is awkward. A clearer notation would be 'sum over attainable densities phi_k'.
- [Section 2.3, equation (1)] The definition 'N_{k,ell}^{n,m} = |I_{n-k,m-ell,k}|' is followed by the partition in equation (1) that sums over part B; the text should explicitly state that the first expression is only a schematic suffix count and that (1) is the operative formula. This would prevent the reader from thinking the two expressions are identical.
- [Section 4, Figure 6] The nonstandard inversion sequence for the first k+1 points is described informally; the capacity constraints for the special boxes k and k+1 should be stated explicitly, since Proposition 16 depends on the admissible ranges for those entries.
- [General presentation] The manuscript would benefit from a statement at the end of the abstract clarifying its status as a preprint with disclaimed proofs, or alternatively from removing the referee comment from the abstract and discussing the issue in a separate note, so that readers are not confronted with a self-refutation in the abstract itself.
Circularity Check
No circularity: the inversion-sequence enumeration is self-contained, and the referee-noted proof flaws are correctness risks, not circular reasoning.
full rationale
The derivation chain is self-contained and does not reduce to its own inputs. Position independence (Proposition 8) is proved by an explicit inversion-preserving bijection. The enumeration of semi-sparse permutations rests on representing permutations by inversion sequences and approximating large suffix counts by unrestricted weak compositions (Corollary 10); this approximation generalizes an external result of Acan and Pittel [1] with the proof included, so it is not a self-citation. The tripartition counts (Propositions 11 and 14) express N^{k,ell}_{n,m} as exact sums of suffix counts, then approximate those suffixes; no fitted parameter is renamed as a prediction. The normalization in Theorem 2 uses the identity that pattern probabilities sum to 1 together with tail bounds on the inversion density of a uniformly random permutation; this is a standard probabilistic self-normalization, not circular. The abstract explicitly states that a referee found flaws on pages 9 and 15 and that the stated results have not been established; the specific gap noted by the skeptic—Proposition 14 implicitly requires r>k while Theorem 3 permits k>r—is a proof-coverage defect, not a reduction of the conclusion to an assumption. No load-bearing claim is justified solely by a citation to the author's prior work; the only self-citations are for background notation. Hence the circularity score is 0.
Assumptions & free parameters
assumptions (4)
- domain assumption The map Psi in Proposition 8 is a bijection on S_{n,m} that preserves the inversion count and shifts consecutive patterns one position to the right.
- domain assumption For t << s << t^2/log t, the number of restricted inversion-sequence suffixes I_{t,s,r} is asymptotic to the number of unrestricted weak compositions C_{t,s} whenever r > (1+epsilon) s/t log t (Corollary 10).
- domain assumption The closed-form summation identities for S^+ and S^- in the proof of Theorem 5 are correct, and their asymptotic evaluation by Proposition 12 is valid for every alpha > 0.
- standard math Hoeffding's inequality yields the tail bound P[|rho_inv(sigma_n) - 1/2| > theta] < 2 exp(-theta^2 n) (Proposition 15).
Cite this review
Pith. "Pith review of Permutations with few inversions are locally uniform." pith.science (2026). https://pith.science/paper/ZHPN6JOO
@misc{pith2026190807277,
author = {Pith},
title = {Pith review of: Permutations with few inversions are locally uniform},
year = {2026},
howpublished = {\url{https://pith.science/paper/ZHPN6JOO}},
note = {Machine review of arXiv:1908.07277}
}
abstract
We prove that permutations with few inversions exhibit a local-global dichotomy in the following sense. Suppose ${\boldsymbol\sigma}$ is a permutation chosen uniformly at random from the set of all permutations of $[n]$ with exactly $m=m(n)\ll n^2$ inversions. If $i<j$ are chosen uniformly at random from $[n]$, then ${\boldsymbol\sigma}(i)<{\boldsymbol\sigma}(j)$ asymptotically almost surely. However, if $i$ and $j$ are chosen so that $j-i\ll m/n$, and $m \ll n^2/\log^2 n$, then $\lim_{n\to\infty}\mathbb{P}\big[{\boldsymbol\sigma}(i)<{\boldsymbol\sigma}(j)\big]=\frac{1}{2}$. Moreover, if $k=k(n)\ll \sqrt{m/n}$, then the restriction of ${\boldsymbol\sigma}$ to a random $k$-point interval is asymptotically uniformly distributed over $\mathcal{S}_k$. Thus, knowledge of the local structure of ${\boldsymbol\sigma}$ reveals nothing about its global form. We establish that $\sqrt{m/n}$ is the threshold for local uniformity and $m/n$ the threshold for inversions, and determine the behaviour in the critical windows. As pointed out by a referee, there are flaws in the proofs that do not seem easily rectifiable (see comments on pages 9 and 15). So the results stated above have not been established.
Figures
Figures from the paper (4 more)
Reference graph
Works this paper leans on
-
[1]
On the connected components of a random permutation graph with a given number of edges
H ¨useyin Acan and Boris Pittel. On the connected components of a random permutation graph with a given number of edges. J. Combin. Theory Ser. A, 120(8):1947–1975, 2013
work page 1947
-
[2]
Permutation patterns: basic definitions and notation
David Bevan. Permutation patterns: basic definitions and notation. arXiv:1506.06673, 2015
arXiv 2015
-
[3]
Mikl ´os B´ona. Combinatorics of Permutations. CRC Press, second edition, 2012
work page 2012
-
[4]
Persi Diaconis and R. L. Graham. Spearman’s footrule as a measure of disarray. J. Royal Statist. Soc. Ser. B , 39:262–268, 1977
work page 1977
-
[5]
P . Erd˝os and A. R ´enyi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutat´ o Int. K˝ ozl., 5:17–61, 1960
work page 1960
-
[6]
Permutations with fixed pattern densities
Richard Kenyon, Daniel Kr ´al’, Charles Radin, and Peter Winkler. Permutations with fixed pattern densities. Random Structures & Algorithms, 2019
work page 2019
-
[7]
Patterns in Permutations and Words
Sergey Kitaev. Patterns in Permutations and Words. Springer, 2011
work page 2011
-
[8]
Donald E. Knuth. The Art of Computer Programming. Vol. 3: Sorting and Searching. Addison-Wesley, 1973
work page 1973
Show all 10 references
-
[9]
Permutation classes
Vincent Vatter. Permutation classes. In Mikl ´os B ´ona, editor, The Handbook of Enumerative Combinatorics . CRC Press, 2015
2015
-
[10]
Mathematica
Wolfram Research, Inc. Mathematica. wolfram.com/mathematica. 17
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.