pith. sign in

arxiv: 2604.28116 · v1 · submitted 2026-04-30 · 🧮 math.CO · math.NT· math.PR

The proportion of permutations fixing a k-set

Ben Green , Mehtaab Sawhney This is my paper

Pith reviewed 2026-05-07 05:41 UTC · model grok-4.3

classification 🧮 math.CO math.NTmath.PR
keywords permutationsinvariant setsasymptoticsanalytic combinatoricsmultiplication tableperiodic functionprobability limitsfixed sets
0
0 comments X

The pith

The limiting probability that a random permutation has a k-element invariant set is asymptotically f({log_{2} k}) k^{-δ} (log k)^{-3/2} with δ ≈ 0.086 and f a nearly constant smooth periodic function.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper defines p(k) as the limiting probability, as the set size n grows, that a random permutation of n elements leaves some k-element subset invariant. It derives a precise asymptotic expression for p(k) involving a power-law decay with exponent δ slightly less than 1, a logarithmic factor, and a small periodic modulation depending on the fractional part of log base 2 of k. The result is positioned as a model problem whose solution techniques will yield an asymptotic formula for the number of distinct entries in the n-by-n integer multiplication table. A reader should care because it quantifies how rare it is for random permutations to preserve subsets of a given size and links permutation statistics to classical questions in multiplicative combinatorics.

Core claim

Denote by p(k) the limit as n approaches infinity of the probability that a random permutation on [n] has an invariant set of size k. Then p(k) is asymptotically f({log_{2} k}) k^{-δ} (log k)^{-3/2}, where δ equals 1 minus (1 plus log log 2) over log 2, approximately 0.086, and f is a smooth positive function on the reals modulo 1 that the authors describe explicitly. The ratio of the maximum to the minimum of f is less than 1 plus 2 times 10 to the minus 7, although the authors conjecture that f is not constant.

What carries the argument

Analytic combinatorics applied to the generating function for permutations with specified invariant sets, whose singularity analysis produces the power δ and the periodic component f.

Load-bearing premise

The analysis presupposes that the limiting probability p(k) exists for each k and that the generating-function approach yields a valid asymptotic expansion with the stated exponent and periodic function without uncontrolled error terms.

What would settle it

Numerical computation of the exact proportion of permutations in S_n for n much larger than k (for example n = 10^5 and k = 2^{10}) that possess an invariant k-set, then comparison against the predicted value using the explicit form of f, the exponent δ, and the logarithmic factor.

read the original abstract

Denote by $p(k)$ the limit, as $n \rightarrow \infty$, of the probability that a random permutation on a set of size $n$ has an invariant set of size $k$. We give an asymptotic formula for $p(k)$, showing that it is asymptotically $f(\{\log_2 k\}) k^{-\delta} (\log k)^{-3/2}$ where $\delta = 1 - \frac{1 + \log \log 2}{\log 2} \approx 0.086$ and $f$ is a smooth, positive, function on $\mathbb{R}/\mathbb{Z}$, which we will describe explicitly. The function $f$ satisfies $\frac{\max f}{\min f} < 1 + 2 \times 10^{-7}$ and we conjecture that it is not constant. Estimating $p(k)$ is a model for the more well-known question which asks for an estimation of $M(n)$, the number of distinct elements in the $n$-by-$n$ multiplication table. By elaborating on the techniques in this paper, we will give an asymptotic for $M(n)$ in forthcoming work.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper defines p(k) as the limiting probability (n→∞) that a random permutation of [n] admits at least one invariant k-set. It derives the asymptotic p(k) ∼ f({log₂ k}) k^{-δ} (log k)^{-3/2} where δ = 1 − (1 + log log 2)/log 2 ≈ 0.086, f is a smooth positive periodic function on R/Z described explicitly via the singularity analysis, max f/min f < 1 + 2×10^{-7}, and conjectures that f is non-constant. The result is presented as a model problem whose techniques extend to the asymptotic for the size M(n) of the n×n multiplication table.

Significance. If the derivation holds, the explicit form of δ, the (log k)^{-3/2} factor, and the near-constant periodic function f constitute a sharp and novel application of analytic combinatorics to permutation statistics. The connection to the multiplication-table problem and the conjecture on f add value; the small oscillation bound is a striking quantitative feature that would be of independent interest if rigorously established.

major comments (3)
  1. [§3] §3 (Bivariate GF for E[N²]): The passage from the exact EGF exp(∑_{m≥1} (x^m + y^m + (xy)^m)/m) to the rational approximation 1/((1-x)(1-y)(1-xy)) for extracting the diagonal coefficients up to size k requires explicit control of the truncation error for m > k and the tail contribution. The manuscript must supply bounds showing that these errors are o( of the main term ) so that the second-moment method yields a sharp asymptotic for Prob(N > 0) rather than merely a lower bound.
  2. [§4] §4 (Singularity analysis): The exponent δ and the factor (log k)^{-3/2} are extracted from the saddle-point or singularity analysis of the approximated generating function near its dominant manifold. The paper must specify the contours, justify the negligible contribution of non-dominant singularities, and provide rigorous error-term estimates (including dependence on the fractional part {log₂ k}) to confirm that the stated asymptotic is valid uniformly in k.
  3. [§5] §5 (Computation of f): The numerical claim max f / min f < 1 + 2×10^{-7} is extremely tight and sensitive to any O(1/log k) remainder. The manuscript should describe the method (Fourier coefficients, numerical quadrature, etc.) used to evaluate f and supply a priori error bounds demonstrating that the reported ratio is not inflated by approximation artifacts.
minor comments (2)
  1. [§1] The fractional-part notation {log₂ k} and the precise definition of the Poissonized model should be introduced with a short paragraph in §1 for readers unfamiliar with analytic combinatorics of permutations.
  2. A brief comparison with earlier results on the probability of fixed-point-free permutations or small invariant sets would help situate the new asymptotic.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the detailed and insightful comments on our manuscript. We appreciate the opportunity to clarify the technical details and strengthen the rigor of our proofs. We will revise the manuscript to address all the points raised, providing the necessary error bounds and justifications. Our responses to the major comments are as follows.

read point-by-point responses

  1. Referee: [§3] §3 (Bivariate GF for E[N²]): The passage from the exact EGF exp(∑_{m≥1} (x^m + y^m + (xy)^m)/m) to the rational approximation 1/((1-x)(1-y)(1-xy)) for extracting the diagonal coefficients up to size k requires explicit control of the truncation error for m > k and the tail contribution. The manuscript must supply bounds showing that these errors are o( of the main term ) so that the second-moment method yields a sharp asymptotic for Prob(N > 0) rather than merely a lower bound.

    Authors: We acknowledge that the manuscript would benefit from a more explicit treatment of the error terms in the approximation of the bivariate generating function. In the revised version, we will add a dedicated subsection in §3 detailing the truncation error. We bound the tail sum_{m>k} (x^m + y^m + (xy)^m)/m by integrating the geometric series and show that its contribution to the diagonal coefficients is O(k^{-1} (log k)^{-1}) times the main term, which is sufficiently small to not affect the leading asymptotic in the second-moment calculation. This ensures that the variance is asymptotically equivalent to the square of the mean, yielding the sharp probability. revision: yes

  2. Referee: [§4] §4 (Singularity analysis): The exponent δ and the factor (log k)^{-3/2} are extracted from the saddle-point or singularity analysis of the approximated generating function near its dominant manifold. The paper must specify the contours, justify the negligible contribution of non-dominant singularities, and provide rigorous error-term estimates (including dependence on the fractional part {log₂ k}) to confirm that the stated asymptotic is valid uniformly in k.

    Authors: We agree that the singularity analysis section requires more precise specification of the integration contours and error estimates. In the revision, we will describe the contours as small circles or Hankel-like paths around the dominant singularities on the manifold determined by the saddle-point equations. Non-dominant singularities will be shown to contribute an error of O(k^{-δ - ε}) for some ε > 0 by contour shifting and standard estimates on the integrand. The error term will be made uniform in the fractional part {log₂ k} by isolating the periodic component f and bounding the remainder independently of the phase, confirming the asymptotic holds uniformly for all positive integers k. revision: yes

  3. Referee: [§5] §5 (Computation of f): The numerical claim max f / min f < 1 + 2×10^{-7} is extremely tight and sensitive to any O(1/log k) remainder. The manuscript should describe the method (Fourier coefficients, numerical quadrature, etc.) used to evaluate f and supply a priori error bounds demonstrating that the reported ratio is not inflated by approximation artifacts.

    Authors: The function f is derived explicitly from the singularity analysis as a Fourier series. We evaluate it by truncating the series after sufficiently many terms (approximately 200) and using numerical quadrature for the coefficients with high-precision floating point arithmetic. In the revised manuscript, we will describe this computational method in detail and provide a priori error bounds: the Fourier coefficients decay exponentially, allowing us to bound the truncation error by 10^{-10}, and the quadrature error is controlled to 10^{-12}. These bounds ensure that the reported ratio max f / min f < 1 + 2×10^{-7} is accurate and not affected by numerical artifacts. We maintain our conjecture that f is non-constant based on the presence of non-vanishing higher harmonics in the explicit expression. revision: yes

Circularity Check

0 steps flagged

Derivation self-contained via generating functions and singularity analysis

full rationale

The paper assumes the existence of the limit defining p(k) and extracts the stated asymptotic from the bivariate exponential generating function exp(∑ (x^m + y^m + (xy)^m)/m) via standard singularity analysis and saddle-point methods on the dominant singularity manifold. The explicit formula for δ in terms of log 2 and log log 2, the periodic function f on R/Z, and the (log k)^{-3/2} factor all arise directly from the local expansion and contour integration without any reduction to fitted parameters, self-referential definitions, or load-bearing self-citations. The forthcoming-work remark on M(n) is not used in the argument for p(k). No step in the derivation chain collapses to a tautology or to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The derivation relies on standard axioms of combinatorics (existence of the symmetric group, uniform measure on permutations) and analytic combinatorics (generating functions, singularity analysis). No free parameters are fitted to data; δ is computed from universal constants. No new entities are postulated.

axioms (2)
  • domain assumption The limit p(k) exists for each fixed positive integer k.
    The paper defines p(k) as this limit and proceeds to give its asymptotic; existence is presupposed before the asymptotic is derived.
  • standard math Standard tools of analytic combinatorics (generating functions and singularity analysis) apply to the enumeration of permutations with restricted cycle or set structure.
    The form of the asymptotic (power, log, periodic oscillation) is characteristic of such methods.

pith-pipeline@v0.9.0 · 5508 in / 1612 out tokens · 39660 ms · 2026-05-07T05:41:16.749042+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages

  1. [1]

    ca/louigi/papers/ballot.pdf

    Louigi Addario-Berry and Bruce Reed,Ballot theorems for random walks with finite variance, https://problab. ca/louigi/papers/ballot.pdf. 33, 102, 103

    work page

  2. [2]

    Louigi Addario-Berry and Bruce Reed,Ballot theorems, old and new, Horizons of combinatorics, Bolyai Soc. Math. Stud., vol. 17, Springer, Berlin, 2008, pp. 9–35. 33

    work page 2008

  3. [3]

    Probab.42 (2014), 959–993

    Elie Aidekon and Zhan Shi,The Seneta-Heyde scaling for the branching random walk, Ann. Probab.42 (2014), 959–993. 100

    work page 2014

  4. [4]

    Noga Alon and Joel Spencer,The probabilistic method, third ed., Wiley-Interscience Series in Discrete Mathe- matics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2008, With an appendix on the life and work of Paul Erdős. 95, 114

    work page 2008

  5. [5]

    Probab.20 (1992), 1567–

    Richard Arratia and Simon Tavaré,The cycle structure of random permutations, Ann. Probab.20 (1992), 1567–

    work page 1992

  6. [6]

    Number Theory40 (1992), 146–164

    MichelBalazard, Jean-LouisNicolas, CarlPomerance, andGéraldTenenbaum, Grandes déviations pour certaines fonctions arithmétiques, J. Number Theory40 (1992), 146–164. 3

    work page 1992

  7. [7]

    application au problème de l’attente à un guichet, Comptes Rendus de l’Académie des Sciences214 (1942), 452–456

    Émile Borel,Sur l’emploi du théorème de Bernoulli pour faciliter le calcul d’un infinité de coefficients. application au problème de l’attente à un guichet, Comptes Rendus de l’Académie des Sciences214 (1942), 452–456. 101

    work page 1942

  8. [8]

    Stéphane Boucheron, Gábor Lugosi, and Pascal Massart,Concentration inequalities: A nonasymptotic theory of independence, Oxford University Press, 2013. 114

    work page 2013

  9. [9]

    Richard Brent, Carl Pomerance, David Purdum, and Jonathan Webster,Algorithms for the multiplication table problem, Integers 21 (2021), Paper No. A92, 19. 3

    work page 2021

  10. [10]

    Theory Related Fields 133 (2005), 508–530

    Francesco Caravenna, A local limit theorem for random walks conditioned to stay positive, Probab. Theory Related Fields 133 (2005), 508–530. 35

    work page 2005

  11. [11]

    10, 16, 35, 104, 105, 107

    Denis Denisov, Alexander Tarasov, and Vitali Wachtel,Asymptotic expansions for normal deviations of random walks conditioned to stay positive, arXiv:2412.09145. 10, 16, 35, 104, 105, 107

    work page arXiv

  12. [12]

    107, 108

    Denis Denisov, Alexander Tarasov, and Vitali Wachtel,Berry-Esseén inequality for random walks conditioned to stay positive, arXiv:2412.08502. 107, 108

    work page arXiv

  13. [13]

    Denis Denisov, Alexander Tarasov, and Vitali Wachtel,Expansions for random walks conditioned to stay positive, arXiv:2401.09929. 35, 107

    work page arXiv

  14. [14]

    Algebraic Combin.28 (2008), 189–218

    Persi Diaconis, Jason Fulman, and Robert Guralnick,On fixed points of permutations, J. Algebraic Combin.28 (2008), 189–218. 2

    work page 2008

  15. [15]

    Sean Eberhard, Kevin Ford, and Ben Green,Permutations fixing a k-set, Int. Math. Res. Not. IMRN (2016), 6713–6731. 2, 3, 7, 79

    work page 2016

  16. [16]

    Paul Erdős,Some remarks on number theory (Hebrew with English summary), https://users.renyi.hu/~p_ erdos/1955-13.pdf. 2

    work page 1955

  17. [17]

    Univ.15 (1960), 41–49

    Paul Erdős,An asymptotic inequality in the theory of numbers (Russian), Vestnik Leningrad. Univ.15 (1960), 41–49. 2, 7

    work page 1960

  18. [18]

    William Feller,An introduction to probability theory and its applications. Vol. II, second ed., John Wiley & Sons, Inc., New York-London-Sydney, 1971. 100 115

    work page 1971

  19. [19]

    Philippe Flajolet and Robert Sedgewick,Analytic combinatorics, Cambridge University Press, Cambridge, 2009. 3

    work page 2009

  20. [20]

    Kevin Ford,The distribution of integers with a divisor in a given interval, Ann. of Math. (2)168 (2008), 367–433. 3, 8, 9, 86

    work page 2008

  21. [21]

    Theory Related Fields 145 (2009), 269–283

    Kevin Ford, Sharp probability estimates for random walks with barriers, Probab. Theory Related Fields 145 (2009), 269–283. 34

    work page 2009

  22. [22]

    Math.232 (2023), 1027–1160

    Kevin Ford, Ben Green, and Dimitris Koukoulopoulos,Equal sums in random sets and the concentration of divisors, Invent. Math.232 (2023), 1027–1160. 44

    work page 2023

  23. [23]

    Aleksandr Osipovich Gel’fond,An estimate for the remainder term in a limit theorem for recurrent events, Theory of Probability & Its Applications9 (1964), 299–303. 101

    work page 1964

  24. [24]

    249, Springer, New York, 2008

    Loukas Grafakos, Classical Fourier analysis, second ed., Graduate Texts in Mathematics, vol. 249, Springer, New York, 2008. 45

    work page 2008

  25. [25]

    Ion Grama and Hui Xiao,Local limit theorems for conditioned random walks by the heat kernel approximation, https://arxiv.org/abs/2509.14009. 35

    work page arXiv

  26. [26]

    Andrew Granville, Alisa Sedunova, and Cihan Sabuncu, The multiplication table constant and sums of two squares, Acta Arith.214 (2024), 499–522. 3, 5

    work page 2024

  27. [27]

    Ben Green and Mehtaab Sawhney,The multiplication table problem, forthcoming. 2

    work page

  28. [28]

    G. H. Hardy,Ramanujan. Twelve lectures on subjects suggested by his life and work, Cambridge University Press, Cambridge; The Macmillan Company, New York, 1940. 3

    work page 1940

  29. [29]

    Svante Janson, Tomasz Łuczak, and Andrzej Rucinski,Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. 114

    work page 2000

  30. [30]

    M. V. Kozlov, The asymptotic behavior of the probability of non-extinction of critical branching processes in a random environment, Teor. Verojatnost. i Primenen.21 (1976), 813–825, (English translation in Theory of Probability and Its Applications21 (1976), 791–804.). 102

    work page 1976

  31. [31]

    Tomasz Łuczak and László Pyber,On random generation of the symmetric group, Combin. Probab. Comput.2 (1993), 505–512. 2

    work page 1993

  32. [32]

    Probab.23 (1995), 105–140

    Robin Pemantle and Yuval Peres,Critical random walk in random environment on trees, Ann. Probab.23 (1995), 105–140. 102

    work page 1995

  33. [33]

    Band 82, Springer-Verlag, New York-Heidelberg, 1975, Translated from the Russian by A

    Valentin Vladimirovich Petrov,Sums of independent random variables, Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas], vol. Band 82, Springer-Verlag, New York-Heidelberg, 1975, Translated from the Russian by A. A. Brown. 107

    work page 1975

  34. [34]

    Probab.9 (1981), 699–704

    Grant Ritter,Growth of random walks conditioned to stay positive, Ann. Probab.9 (1981), 699–704. 38

    work page 1981

  35. [35]

    Jeremy Schlitt,Multiplication tables for integers with restricted prime factors, https://arxiv.org/abs/2603. 19212. 11

    work page

  36. [36]

    Soundararajan,Ramanujan and the anatomy of integers, in Srinivasa Ramanujan: Going Strong at 125, Part II, Notices AMS 60 (2013), no

    K. Soundararajan,Ramanujan and the anatomy of integers, in Srinivasa Ramanujan: Going Strong at 125, Part II, Notices AMS 60 (2013), no. 1, 10–22. 3

    work page 2013

  37. [37]

    II, Math

    Erik Sparre Andersen,On the fluctuations of sums of random variables. II, Math. Scand.2 (1954), 195–223. 100

    work page 1954

  38. [38]

    Frank Spitzer, A combinatorial lemma and its application to probability theory, Trans. Amer. Math. Soc. 82 (1956), 323–339. 100

    work page 1956

  39. [39]

    Frank Spitzer, A Tauberian theorem and its probability interpretation, Trans. Amer. Math. Soc. 94 (1960), 150–169. 100

    work page 1960

  40. [40]

    Vladimir Vatutin and Vitaly Wachtel,Local probabilities for random walks conditioned to stay positive, Proba- bility Theory and Related Fields143 (2009), 177–217. 33

    work page 2009

  41. [41]

    Yu Zhang, A power law for connectedness of some random graphs at the critical point, Random Structures Algorithms 2 (1991), 101–119. 102 Mathematical Institute, Andrew Wiles Building, Radcliffe Obser v atory Quarter, Woodstock Rd, Oxford OX2 6QW, UK Email address: ben.green@maths.ox.ac.uk Department of Mathematics, Columbia University and OpenAI Email add...

    work page 1991