Random Permutations Fixing k-Sets

Permutations Preserving a Small Subset

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

For a uniform random $\pi\in S_n$, preserving a $k$-set means $\pi(S)=S$ for some $S\subseteq[n]$ with $|S|=k$; its elements need not be fixed individually. First let $n\to\infty$ with $k$ fixed to define $p(k)$, then let $k\to\infty$. The exponent in the cited formulation is $\alpha=1-(1+\log\log2)/\log2$. [S1] [S2]

Statement recorded in the supplied source.

Let $p(k)$ be the limit as $n \to \infty$ of the probability that a random permutation on $[n]$ preserves some set of size $k$. 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$? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Establish nonconstancy/constancy of f and resolve monotonicity. [S1]

Short English statement

As the size of a preserved subset increases, does its limiting probability always decrease, and does its known scale have a single limiting multiplier?

Research attempt

Provenance and scope.

This individual attempt was generated by GPT-6 Astra Ultra on 1 October 2026. The method was to derive explicit partial results and test the first proposed extension adversarially. The original statement and sources below are retained. No claim of mathematical novelty or complete solution is made.

Formal target and updated literature.

An invariant $k$-set is a union of cycles, not necessarily a set of fixed points. First take the permutation size to infinity for fixed $k$, defining $p(k)$, then let $k$ grow. Green and Sawhney's inspected 2026 manuscript gives an asymptotic with a positive smooth periodic factor $f(\{\log_2k\})$, and conjectures that this factor is nonconstant. Accordingly the remaining constant-factor question is whether that explicitly described factor is constant; the general asymptotic is not treated as unknown here. We derive an exact finite computation for each fixed $k$ and test whether the natural coupling can prove monotonicity.

The limiting cycle model.

For fixed $k$, the numbers $Z_1,\ldots,Z_k$ of cycles of lengths one through $k$ converge jointly to independent Poisson variables of means $1,1/2,\ldots,1/k$. This standard permutation fact can be checked from factorial moments: choosing ordered disjoint cycles of the requested lengths gives expectation $\prod j^{-a_j}$ whenever their total length fits in the permutation. These are precisely the mixed factorial moments of the independent Poisson vector. Consequently \[ p(k)=\Pr\left(k\in\left\{\sum_{j=1}^k j b_j:0\leq b_j\leq Z_j\right\}\right). \] No cycles longer than $k$ can participate in a $k$-set, so the finite vector suffices.

An exact finite-state recursion.

For each $j\leq k$, replace $Z_j$ by $C_j=\min(Z_j,\lfloor k/j\rfloor)$. This does not change attainability of any total at most $k$: extra copies of a cycle length beyond that cap cannot be used. Starting with the attainable-sum set $S_0=\{0\}$, update \[ S_j=\bigcup_{b=0}^{C_j}(S_{j-1}+jb)\cap\{0,\ldots,k\}. \] The probabilities of $C_j=c$ are the Poisson probabilities for $c<\lfloor k/j\rfloor$ and the remaining tail probability at the cap. Thus the recursion has finitely many states, with exact probabilities expressible through exponentials and rational numbers. A bitmask implementation makes each update a union of shifted masks. This is an exact formula, though not an efficient asymptotic method when $k$ is large.

For example, \[ p(1)=1-e^{-1},\qquad p(2)=1-2e^{-3/2}. \] For $k=3$, failure requires $Z_3=0$ and either $Z_1=0$, or $Z_1\in\{1,2\}$ together with $Z_2=0$. Therefore \[ p(3)=1-e^{-4/3}-\tfrac32e^{-11/6}. \] The formulas distinguish a two-cycle from two fixed points and include all multiplicities.

Why the natural samplewise monotonicity argument fails.

Couple every $p(k)$ using one independent infinite family $(Z_j)_{j\geq1}$. The event that $k+1$ is an attainable cycle sum does not imply that $k$ is attainable. For example, if $Z_{k+1}\geq1$ while $Z_1=\cdots=Z_k=0$, then $k+1$ is attainable and $k$ is not. This event has positive probability. Conversely, if $Z_1=k$ and $Z_2=\cdots=Z_{k+1}=0$, then $k$ is attainable and $k+1$ is not. Thus the events are not nested in either direction. Monotonicity of their probabilities, if true, needs an averaging or transport argument rather than the obvious inclusion coupling.

Finite checks and their precision limit.

The companion script evaluates the recursion in floating-point arithmetic for $k\leq12$. It obtains $p(1)\approx0.63212$, $p(2)\approx0.55374$, $p(3)\approx0.49658$, and $p(12)\approx0.36119$, with decreases at each tested step. These numerical values are explicitly not interval-certified proofs of all twelve comparisons; the first three have the exact expressions above. More importantly, a finite initial segment cannot establish monotonicity for every $k$, and it cannot resolve a very small oscillation in an asymptotic periodic factor.

The periodic-factor theorem also does not immediately settle monotonicity. A smoothly varying factor can coexist with a decaying power, and an asymptotic error that is merely $o(1)$ can exceed the relative difference between consecutive values. To infer $p(k+1)\leq p(k)$ from an asymptotic formula requires error control on the scale of consecutive differences, or an independent inequality.

Final gap.

The checked output is the exact Poisson subset-sum formula, a finite-state computation, and explicit positive-probability obstructions to event inclusion. The unresolved tasks are a probability inequality valid for all adjacent $k$, and a proof of constancy or nonconstancy of the periodic factor from the current primary theorem. Neither is asserted on the basis of the finite computation.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 141 (GREEN-053), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 Ben Green, 100 Open Problems (author’s maintained problem list). https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf. The author-hosted document was inspected on 27 September 2026; the archive’s local code is not a problem-number locator in this paper.

• S3 B. Green and M. Sawhney, The proportion of permutations fixing a k-set, arXiv:2604.28116 $2026$. https://arxiv.org/abs/2604.28116. Bibliographic information from the supplied record.

• S4 S. Eberhard, K. Ford, B. Green, Permutations fixing a k-set, arXiv:1507.04465 $2015$. https://arxiv.org/abs/1507.04465. Bibliographic information from the supplied record.

• E1 B. Green and M. Sawhney, The proportion of permutations fixing a $k$-set, 2026. https://arxiv.org/abs/2604.28116. Inspected 1 October 2026.