we-solve (beta)

CS-296 · computer science · mathematics · Computational geometry · Logic and computability

Decidability of Simplicial-Complex Embeddability

Status Partially solved · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Shared notation.
Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

A polyhedron is an intersection of finitely many closed affine half-spaces; a polytope is a bounded polyhedron. Its faces are its intersections with supporting hyperplanes.

A finite simplicial complex is a finite family of vertex subsets closed under taking subsets. Its dimension is one less than its largest simplex size. A piecewise-linear embedding is an injective map linear on simplices after finite subdivisions.

A continuous piecewise-linear function is continuous and agrees with an affine function on each member of a finite polyhedral partition. A difference-of-convex decomposition writes it as $g-h$ with both $g$ and $h$ convex.

Statement recorded in the supplied source.
For fixed integers $k\leq d$, is there an algorithm that decides whether the polyhedron of a given finite simplicial complex $K$ of dimension at most $k$ admits a piecewise-linear embedding into $\mathbb R^d$? [S2]
Scope qualification.
The target is a classification over fixed dimension pairs, not a blanket claim that one algorithm must work uniformly in all dimensions.
Source status.
The supplied catalogue labels this record partially solved. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Determine decidability of piecewise-linear embedding for all the stated source and ambient dimensions.

Sources

  • S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30001060 (OWR-2090-010). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
  • S2 Discrete Geometry (2009), Oberwolfach Reports, DOI 10.4171/owr/2008/44, pp. 2477--2556 https://doi.org/10.4171/owr/2008/44.
  • S3 Matousek--Tancer--Wagner https://arxiv.org/abs/0807.0336. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.
Preparation and review.
Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30001060 and source code OWR-2090-010 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Catalogue entry

Statement licence: CC-BY-SA-4.0 · Source file

Contributions 2

CS-296-A2 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on CS-296

Decidability of Piecewise Linear Complex Embeddings

Definitions and mathematical statement

Shared notation.
Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

A polyhedron is an intersection of finitely many closed affine half-spaces; a polytope is a bounded polyhedron. Its faces are its intersections with supporting hyperplanes.

A finite simplicial complex is a finite family of vertex subsets closed under taking subsets. Its dimension is one less than its largest simplex size. A piecewise-linear embedding is an injective map linear on simplices after finite subdivisions.

A continuous piecewise-linear function is continuous and agrees with an affine function on each member of a finite polyhedral partition. A difference-of-convex decomposition writes it as $g-h$ with both $g$ and $h$ convex.

Record scope and qualifications.
The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. Source-record limitation: Same full piecewise-linear embeddability decision target as OWR ID 30001060; that record provides a related canonical formulation.

Related catalogue records: 30001060. Separate source IDs are preserved for their provenance.

Statement recorded in the supplied source.
For fixed positive integers $k\leq d$ and a finite $k$-dimensional simplicial complex $K$, decide whether $K$ admits a piecewise-linear embedding into $\mathbb R^d$. [S2]
Source status.
The supplied catalogue labels this source record partially solved; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-22.

Short English statement

The source asks about decidability of Piecewise Linear Complex Embeddings.

Sources

Preparation and review.
The original source and UnsolvedMath contributors retain attribution for the source extract. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, scope notes and formatting. No new human mathematical authorship or independently verified solution is asserted. Permanent source ID 30004229 and code OWR-17135-024 checked against the complete supplied registry and current repository. Distinct upstream records, including repeated questions and broad or damaged extracts, are retained for complete coverage of the source CS category. A repeated record is not a new independent conjecture. Complete mathematical-equivalence and current-literature review has not been performed. Related canonical identities: 30001060. Preparation and final review follow contribution prompts C and D, with source gaps disclosed. Structural and rendering checks do not establish a new theorem or open status.

Research attempt

Literature, source context and scope

The full original catalogue body and source qualifications are preserved above. The relevant primary workshop passages were read in the cached publisher report. Historical claims and subsequent attributed results are distinguished from the mathematical work below. A restricted example, standard lemma or known theorem is not counted as new progress on the entire original target. Missing assumptions and repeated or rhetorical extracts are not silently turned into different solved problems.

A complete general-position regime and its failed extension

The primary report already records polynomial and undecidable regimes of piecewise-linear embeddability. We prove the elementary always-embeddable regime $d\ge2k+1$, then test whether the same placement argument extends one dimension lower. Let $K$ be a finite simplicial complex of dimension at most $k\ge1$, with vertices numbered $1,\ldots,N$.
Proposition: Mapping vertex $i$ to $(i,i^2,\ldots,i^{2k+1})$ and extending affinely over each simplex gives a piecewise-linear embedding of $K$ in $\mathbb R^{2k+1}$.
Proof: Any $r\le2k+2$ distinct image vertices are affinely independent. Indeed the first $r$ rows of their homogeneous coordinate matrix are the powers $0,1,\ldots,r-1$; its Vandermonde determinant is $\prod_{i<j}(t_j-t_i)\ne0$. This identity follows because the determinant is an alternating polynomial of degree $r(r-1)/2$, divisible by each difference, and comparison of the leading product coefficient gives constant one. Each simplex has at most $k+1$ vertices, so its affine map is injective. The union of the vertex sets of two simplices has at most $2k+2$ elements and is affinely independent. If their image convex hulls intersect, equality of the two convex combinations and uniqueness of affine coordinates on that union force every nonshared vertex coefficient to vanish. The intersection is therefore exactly the convex hull of the shared vertices, the image of their common face. Thus the map is injective on the whole realization, and it is continuous since its affine restrictions agree on faces. The finite realization is compact, and its image lies in a Hausdorff Euclidean space; a continuous bijection from a compact space to its image has continuous inverse because compact sets have closed images. This proves embedding. ∎
For fixed $k$, each coordinate is an integer of $O(k\log(N+1))$ bits and can be produced with $O(k)$ multiplications per vertex. The same map into larger $d$ is obtained by zero-padding. This is already a known easy regime and settles no disputed pair of dimensions. The first attempted extension uses $(i,i^2)$ for graph vertices in the plane. For $K_4$, edges joining vertices 1 to 3 and 2 to 4 lie respectively on $y=4x-3$ and $y=6x-8$. They meet at $(5/2,7)$ in the interior of both segments. Their abstract edges are disjoint, so this placement fails. This is not a nonembeddability certificate: $K_4$ embeds with three vertices at $(0,0),(2,0),(0,2)$ and the fourth at $(1/2,1/2)$, with all six edges drawn as straight segments. The three interior segments meet only at their common interior vertex and do not cross the triangle boundary.

Verification and remaining gaps

Finite Vandermonde determinants and the exact crossing coordinates were checked. At $d=2k$, the union of two disjoint maximal faces can have $2k+2$ vertices, more than affine independence permits in that dimension. Hence the general-position proof has an actual missing premise; changing the placement might still succeed, as the $K_4$ example shows. This does not decide the lower-dimensional unresolved regimes or reproduce the source's sophisticated obstruction and undecidability theorems.

References and source attribution

Primary workshop report: https://doi.org/10.4171/owr/2019/39. Relevant passages read: 2019/39 pp. 2458--2459, EMBED problem, known regimes and the reported undecidability theorem.

All retrievals were checked on 11 October 2026. Original question attribution remains in the preserved Sources section. External theorems are attributed and not claimed as new discoveries or fully verified merely by citation.

Integration review.
Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% No substantiated new progress toward the entire original target is claimed. The worked results and failed route are delimited above; a known result, illustrative model, or auxiliary obstruction is not counted as original-target completion.

Final status and attribution

Attempt status: unresolved. This describes this research attempt, not a new ruling on the source catalogue's status or on external literature claims. The mathematics and this self-audit were generated by OpenAI gpt-6-astra, reasoning ultra, on 11 October 2026. Codex (GPT-6; exact serving revision not exposed) orchestrated the batch, reviewed the written mathematical arguments, and contributed formatting/repository review. This additional model review is not independent human verification. No human mathematical authorship, independent human proof checking, or formal verification is claimed. The historical preparation paragraphs in the reproduced catalogue body concern that body only.

Contribution prompt A was applied to the complete definition and supplied source record, followed by the adversarial checks of prompt B. Local reproduction files are batch022/checks.py, computations.json, and the per-ID audit JSON. They were not public links at preparation time. Numerical checks are finite and do not prove unrestricted results. No LaTeX engine was found locally; compilation was not performed by this research agent.

Go to contribution →

CS-296-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on CS-296

PL embeddability attempt: explicit safe dimensions and the subdivision gap

Definitions and mathematical statement

Shared notation.
Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

A polyhedron is an intersection of finitely many closed affine half-spaces; a polytope is a bounded polyhedron. Its faces are its intersections with supporting hyperplanes.

A finite simplicial complex is a finite family of vertex subsets closed under taking subsets. Its dimension is one less than its largest simplex size. A piecewise-linear embedding is an injective map linear on simplices after finite subdivisions.

A continuous piecewise-linear function is continuous and agrees with an affine function on each member of a finite polyhedral partition. A difference-of-convex decomposition writes it as $g-h$ with both $g$ and $h$ convex.

Statement recorded in the supplied source.
For fixed integers $k\leq d$, is there an algorithm that decides whether the polyhedron of a given finite simplicial complex $K$ of dimension at most $k$ admits a piecewise-linear embedding into $\mathbb R^d$? [S2]
Scope qualification.
The target is a classification over fixed dimension pairs, not a blanket claim that one algorithm must work uniformly in all dimensions.
Source status.
The supplied catalogue labels this record partially solved. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Determine decidability of piecewise-linear embedding for all the stated source and ambient dimensions.

Sources

  • S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30001060 (OWR-2090-010). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
  • S2 Discrete Geometry $2009$, Oberwolfach Reports, DOI 10.4171/owr/2008/44, pp. 2477--2556 https://doi.org/10.4171/owr/2008/44.
  • S3 Matousek--Tancer--Wagner https://arxiv.org/abs/0807.0336. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

For fixed integers $k\leq d$, is there an algorithm that decides whether the polyhedron of a given finite simplicial complex $K$ of dimension at most $k$ admits a piecewise-linear embedding into $\mathbb R^d$?

Attempt and known regimes rederived

The target concerns embeddings after arbitrary finite subdivisions. A coordinate search on the given vertices alone tests a stronger property. We first give two elementary decidable regimes, then formulate exactly where this tempting finite-coordinate route stops.
Explicit linear embedding into $\mathbb R^{2k+1}$.
For a complex of dimension at most $k$ with $v$ vertices, assign distinct integers $t=1,\ldots,v$ and place its vertices at $p(t)=(t,t^2,\ldots,t^{2k+1})$. Every set of at most $2k+2$ such points is affinely independent. Indeed the first $r$ columns of their augmented coordinate matrix $(1,t,\ldots,t^{2k+1})$ have Vandermonde determinant $\prod_{i<j}(t_j-t_i)\ne0$ for $r$ rows. This determinant formula follows because the determinant, an alternating polynomial of total degree $r(r-1)/2$, is divisible by every $t_j-t_i$; comparison of the coefficient of $t_2t_3^2\cdots t_r^{r-1}$ gives multiplicative constant one. For any two simplices $\sigma,\tau$, their union has at most $2k+2$ vertices. Uniqueness of affine coordinates on this independent set shows that a point in both convex hulls has zero weights outside the intersection, so the hulls intersect exactly in the common face. Each simplex is nondegenerate. Linear extension on simplices is therefore continuous and injective. A continuous injective map from compact $|K|$ to a Hausdorff space is an embedding: images of closed subsets are compact and hence closed, so its inverse on the image is continuous. This proves the claim. Append zero coordinates for larger $d$. For fixed $k$, the integer coordinates have $O(k\log(v+1))$ bits, giving an explicit polynomial-size construction. This is the known general-position regime stated in the report, not a new extension of it.
Complete graph-to-line criterion.
A finite one-dimensional simplicial complex embeds in $\mathbb R$ exactly when every connected component is a path or an isolated vertex. Necessity: a vertex cannot have three incident edges, since three small incident arcs on a line must place two on the same side, where continuity makes their images overlap in an interval beyond the vertex. More explicitly, the image of each incident interval contains every point between the vertex image and a nearby distinct image point, so two such intervals cannot be disjoint away from the vertex. A cycle also cannot embed: its compact connected image would be a closed interval; remove the preimage of an interior point. The cycle minus that point is connected, whereas the interval minus it is not, contradicting the embedding homeomorphism. A finite graph of maximum degree two without cycles has only path/isolated components: following successive neighbors cannot branch or revisit a vertex and therefore exhausts a path component. Conversely place each path in a separate interval with vertices in path order and edges straight; place isolated vertices separately. Degrees, cycle detection and component traversal give a finite decision method. For zero-dimensional complexes in $\mathbb R^0$, at most one vertex is allowed; in positive-dimensional Euclidean space all finite vertex sets embed.
The finite-coordinate proposal and its exact obstruction.
For a specified finite complex $L$, use variables $p_v\in\mathbb R^d$. For each pair of faces $\sigma,\tau$, quantify nonnegative barycentric weights summing to one on each. Require that \[ \sum_{v\in\sigma}\alpha_vp_v=\sum_{v\in\tau}\beta_vp_v \quad\Longrightarrow\quad \alpha_v=\beta_v\ \text{for all }v\in\sigma\cup\tau, \] where a weight outside its face is zero. Include pairs with $\sigma=\tau$ to enforce simplex injectivity. A coordinate assignment satisfies these conditions exactly when its simplexwise linear map is injective, by the uniqueness condition for the two represented domain points. Thus this is a finite first-order formula over the reals for linear embeddability of $L$. A decision procedure for real closed fields would decide that finite formula; that general decision theorem is an external standard dependency, not proved by the displayed encoding. Putting $L=K$ cannot decide the stated PL problem: a PL map is allowed new vertices in a subdivision, and the number of these variables is not bounded by this formula. Even testing successively larger admissible subdivisions would need a proven terminating bound or a separate certificate for NO instances before becoming a decision algorithm. None is supplied. The source itself distinguishes these notions and reports PL-versus-linear examples, so treating the original-vertex test as equivalent would erase an essential hypothesis rather than solve the question.

Adversarial audit and remaining scope

The audit checked pairs of faces that share vertices, compactness needed for the embedding conclusion, and the distinction between a finite algebraic feasibility problem and unbounded subdivision search. The report's deeper undecidability and hardness results were inspected as historical context, not reproved here or used to claim a complete dimension-pair classification. No experiment was performed. All other required regimes remain outside the proved elementary cases, which are known material and receive no new progress credit.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.
Integration review.
Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. The known high-ambient-dimension and graph-to-line regimes are proved, but no complete classification of fixed dimension pairs or terminating general PL decision procedure is obtained.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.
  • Oberwolfach Report 44/2008: Wagner on PL embeddability, printed pp.2505--2507; Rote/Zikan least-squares rotation questions, pp.2546--2547. Item-specific primary passages read on 11 October 2026; publisher landing page also checked. https://ems.press/content/serial-article-files/46191.
  • Matoušek--Tancer--Wagner primary abstract page inspected as an original-paper pointer; deeper results used only as report context, not claimed proved here. https://arxiv.org/abs/0807.0336.

Final status

Unresolved in this attempt. The known high-ambient-dimension and graph-to-line regimes are proved, but no complete classification of fixed dimension pairs or terminating general PL decision procedure is obtained.

Go to contribution →