Exact motion-planning complexity of real projective spaces
For an integer $n \ge 1$ let $\operatorname{TC}(\mathbb{RP}^n)$ be Farber's topological complexity of real projective space in the unreduced convention: the least $r$ for which $\mathbb{RP}^n \times \mathbb{RP}^n$ has an open cover $U_1, \dots, U_r$ with continuous maps $s_i : U_i \to C([0,1], \mathbb{RP}^n)$, the path space carrying the compact-open topology, such that $s_i(x, y)$ is a path from $x$ to $y$. Let $\operatorname{Imm}(\mathbb{RP}^n)$ be the least $m$ such that $\mathbb{RP}^n$ admits a smooth immersion into $\mathbb{R}^m$.
Farber, Tabachnikov and Yuzvinsky proved that $$\operatorname{TC}(\mathbb{RP}^n) = \operatorname{Imm}(\mathbb{RP}^n) + 1 \qquad (n \ne 1, 3, 7),$$ and that $\operatorname{TC}(\mathbb{RP}^n) = n + 1$ exactly when $n \in \{1, 3, 7\}$. They also proved $\operatorname{TC}(\mathbb{RP}^n) \le 2n$ for every $n$, with equality when $n$ is a power of $2$, and computed $\operatorname{TC}(\mathbb{RP}^n)$ for all $n \le 23$ from known immersion results. Davis's table of immersions of real projective spaces records, for example, that $\mathbb{RP}^{24}$ immerses in $\mathbb{R}^{39}$ but not in $\mathbb{R}^{37}$, so that $\operatorname{TC}(\mathbb{RP}^{24})$ is $39$ or $40$.
Problem. Determine $\operatorname{TC}(\mathbb{RP}^n)$ exactly for every $n \ge 1$: a complete numerical determination as a function of $n$, including the dimensions in which the known lower and upper bounds differ. For $n \ne 1, 3, 7$ this is the same as determining $\operatorname{Imm}(\mathbb{RP}^n)$; the identity above is a reformulation, not a numerical answer.
Source: Farber, Tabachnikov and Yuzvinsky (2003), who reduced it to the immersion problem for real projective spaces and computed the values for n ≤ 23 (arXiv 2002). Stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- AT — Algebraic Topology
- Secondary
- GT
- Keywords
- AIM Open Applied Problems, immersions, real projective spaces, topological complexity
References
@article{farber2003projective,
author = {Farber, Michael and Tabachnikov, Serge and Yuzvinsky, Sergey},
title = {Topological robotics: motion planning in projective spaces},
journal = {Int. Math. Res. Not.},
volume = {2003},
number = {34},
year = {2003},
pages = {1853--1870},
doi = {10.1155/S1073792803210035},
eprint = {math/0210018},
archivePrefix = {arXiv},
}
@misc{davis-immersion-table,
author = {Davis, Donald M.},
title = {Table of immersions and embeddings of real projective spaces},
howpublished = {\url{https://www.lehigh.edu/~dmd1/immtable}},
note = {Accessed 20 October 2026},
}
@misc{aim-projective-motion-planning,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Exact motion-planning complexity of real projective spaces}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/526-projective-motion-planning.md},
note = {Entry 526 at commit 24edaad, 2026-10-15},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00893, "Exact motion-planning complexity of real projective spaces", clopen.solutions.