Optimal Complexity of Definable Cylindrical Decompositions

Definitions and mathematical statement

A semialgebraic subset of ${\mathbb{R}}^n$ is a finite Boolean combination of sets defined by polynomial equalities and strict polynomial inequalities with real coefficients. More generally, definability is relative to a specified first-order structure and a convention concerning permitted parameters. The source does not specify that structure or parameter convention; its workshop context concerns o-minimality.

For a specified structure on ${\mathbb{R}}$, a finite partition $\mathcal D$ of ${\mathbb{R}}^n$ into definable cells is cylindrical, with respect to a fixed coordinate order, if for every $1\leq k<n$ and every $C,D\in\mathcal D$, \[ \pi_k(C)=\pi_k(D)\quad\text{or}\quad \pi_k(C)\cap\pi_k(D)=\varnothing, \] where $\pi_k(x_1,\ldots,x_n)=(x_1,\ldots,x_k)$. Here cells are understood in the usual recursive sense: in dimension one they are points or open intervals, and in higher dimensions they are graphs of continuous definable functions over cells or regions between continuous definable boundary functions, allowing unbounded regions. A partition is compatible with a set if that set is a union of its parts. These definitions describe a conventional real setting; the supplied record does not determine whether precisely this setting, compatibility condition, or coordinate convention is intended. It supplies no definition of a semi-cylindrical decomposition.

Source question. Can the quantitative bounds for semi-cylindrical or cylindrical decompositions of definable, even semialgebraic, sets be improved to optimal bounds in higher dimensions?

Unresolved formulation. The record does not specify the input class and its complexity parameters, the quantity to be bounded, the admissible decompositions, the dimensions covered by "higher dimensions," or the meaning of optimality. In particular, it does not distinguish bounds on the number of cells, the complexity of their descriptions, or the computational resources needed to construct them. Consequently, no particular inequality, quantified asymptotic bound, or matching lower-bound requirement can be extracted without additional hypotheses. The question is retained as a research target, including its semialgebraic special case, rather than asserted as a fully specified conjecture.

Short English statement

Determine optimal quantitative bounds for semi-cylindrical or cylindrical decompositions in higher dimensions, including for semialgebraic sets. The supplied question leaves the complexity measure, input parameters, admissible decompositions, and meaning of optimality unspecified, so a precise quantified conjecture requires further source clarification.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30003502$, title Optimal Complexity of Definable Cylindrical Decompositions, source problem code catalogue entry, collection Oberwolfach Reports Open Problems. No individual proposer is identified; the supplied proposed year is $2017$.
• Supplied report citation: O-Minimality and its Applications to Number Theory and Analysis (2018), Oberwolfach Reports, pp. 1349--1420, DOI 10.4171/owr/2017/22. Supplied source URL and literature-source link, labeled "Oberwolfach Reports 2018": https://doi.org/10.4171/owr/2017/22. The background describes these reports as records of mathematical workshops and their open-problem discussions. No precise location within the report is supplied for this question.
• Literature assessment checked at 2026-08-21: the supplied curation labels the problem open, states that the report identifies nonoptimal higher-dimensional quantitative bounds as a major open problem, and states that no later general optimal bound was located. This is supplied dated curation, not an independently verified literature assessment. Its stated checked source is the report linked above; the record requests independent verification of time-sensitive status and cited claims.
• The supplied record labels its statement "exact" and describes it as clear, self-contained, publication-ready, and retained byte-for-byte. Those are supplied editorial assessments; they do not resolve the formulation gaps identified here.