Permutations fixing a set of size k
Let $p(k)$ be the limiting probability, as $n \to \infty$, that a uniformly random permutation of $[n]$ has an invariant set of size $k$, and let $\alpha = 1 - \frac{1 + \log\log 2}{\log 2}$. Eberhard, Ford and Green showed that $p(k)$ lies between constant multiples of $k^{-\alpha}(\log k)^{-3/2}$. The second question below is a model for counting the distinct entries of the $N \times N$ multiplication table.
Problem. Is $p(k)$ a decreasing function of $k$? Is $p(k) = (C + o(1)) k^{-\alpha} (\log k)^{-3/2}$ for some absolute constant $C$?
Source: From a paper of J. R. Britnell and M. Wildon; see S. Eberhard, K. Ford and B. Green, Permutations fixing a k-set (2016). Listed as Problem 87 in B. Green, 100 open problems (version of January 2026).
Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.
Classification
- Primary
- CO — Combinatorics
- Secondary
- NT, PR
- Keywords
- asymptotic enumeration, invariant sets, multiplication table problem, random permutations
References
@article{eberhard2016kset,
author = {Eberhard, Sean and Ford, Kevin and Green, Ben},
title = {Permutations fixing a $k$-set},
journal = {International Mathematics Research Notices},
volume = {2016},
number = {21},
pages = {6713--6731},
year = {2016},
doi = {10.1093/imrn/rnv371}
}
@misc{green2026sawhney,
author = {Green, Ben and Sawhney, Mehtaab},
title = {The proportion of permutations fixing a $k$-set},
year = {2026},
eprint = {2604.28116},
archivePrefix = {arXiv}
}
@misc{green100open,
author = {Green, Ben},
title = {100 open problems},
howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
note = {Problem 87; version of January 2026, most recent update December 2025},
year = {2026}
}
Resolution claims
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^{-δ} (\log k)^{-3/2}$ where $δ= 1 - \frac{1 + \log \log 2}{\log 2} \approx 0.086$ and $f$ …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-29 | Open → Partially resolved | The registry's curators | The proportion of permutations fixing a $k$-set v1 recorded from arXiv:2604.28116v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01044, "Permutations fixing a set of size k", clopen.solutions.