Permutation groups

Definitions and mathematical statement

Let $G_n$ be the intended family of permutation groups, with a random walk generated by allowed transpositions, transition law $m_x$ from $x$, and metric $d_n$. For example, on $S_n$ one can use the word metric in all transpositions, but the source does not explicitly choose this group, metric, or step distribution. Laziness, the choice of transpositions, and discrete versus continuous time also have to be specified.

Given these data, one-step coarse Ricci curvature would be \[ \kappa_n(x,y)=1-\frac{W_1(m_x,m_y)}{d_n(x,y)}\qquad(x\ne y), \] where $W_1$ is the coupling transport distance with cost $d_n$. If $\mu_n$ is the relevant stationary probability, a corresponding concentration profile can be written \[ \alpha_n(r)=\sup_{\mu_n(A)\ge1/2} \left(1-\mu_n(A_r)\right),\qquad A_r=\{x:\inf_{a\in A}d_n(x,a)\le r\}. \] These definitions identify the kinds of data needed to compare curvature predictions with actual concentration; the source supplies neither a precise profile nor quantitative predicted and optimal orders.

Ollivier's Problem U states that positive coarse Ricci curvature for the transposition walk yields concentration of the wrong order, and asks for an explanation. Specifically, can hyperbolic-like properties of permutation groups, or a mixture of positive and negative curvature behavior, account for that discrepancy? The source supplies no definition of "hyperbolic-like," no second curvature notion or sign decomposition, and no quantified implication connecting those properties to concentration. Accordingly this is retained as an explanatory research problem, rather than replaced by an invented theorem.

The assertion of positive curvature also depends on the walk convention. In particular, a discrete walk taking exactly one transposition each step has a parity constraint, so positivity should not be transferred to that convention without checking the kernel and metric. The record does not resolve that choice.

Short English statement

Explain why the concentration predicted from coarse Ricci curvature for permutation transposition walks has a different order from the actual optimal concentration. The suggested explanations involve hyperbolic-like geometry or interacting positive and negative curvature effects, but the source gives no precise conjectural mechanism.

The supplied research summary calls this discrepancy unresolved and says no verified resolution was located. Its OPEN-TRIAGE label is a supplied assessment, and provenance records no later authoritative resolution check. Neither the exact orders nor the relevant walk normalization are provided.

Sources

• Local UnsolvedMath registry, permanent ID 4000021, source code catalogue entry, "Permutation groups," proposed by Yann Ollivier, 2008. Dataset curation and metadata: Ulam AI and UnsolvedMath Contributors, CC BY 4.0.
• Yann Ollivier, Discrete Ricci curvature: Open problems (2008), Problem U, https://www.yann-ollivier.org/rech/publs/problems_curvmarkov.pdf; pdf-text extraction, accessed 2026-07-29.
• The supplied research summary gives no separate primary reference for the asserted optimal concentration, the curvature prediction, or a proposed geometric explanation.
• Source provenance marks status evidence NEEDS_REVIEW and rights NEEDS_REVIEW: the source presents the item as open, no later authoritative resolution check is recorded, and redistribution permission was not established despite verified public access. This qualification is separate from the dataset licence.