Minimal Convex Difference Decompositions of CPWL Functions

Duplicate Minimal Convex-Difference Decomposition Problem

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.

For continuous piecewise-linear $f$, each affine region carries a linear formula. A convex-difference representation is $f=g-h$ with convex piecewise-linear $g,h$; minimizing pieces requires counting the regions according to the source's convention.

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. The supplied registry flags this extraction as unrecoverable. It is displayed as a literal source fragment; the definitions provide context rather than a replacement formal statement.

Source-record limitation: Source flags the statement as unrecoverable: The official report confirms that this overlapping extraction repeats the minimal convex-difference decomposition problem represented canonically by OWR-14299089-005. No separate clean statement is promoted; the original record remains publicly visible and retained for provenance.

Related catalogue records: 30006217. Separate source IDs are preserved for their provenance. The source text below is rendered literally where necessary; damaged formulas and composite extracts are not silently repaired into a new mathematical claim. The supplied catalogue marks this record as unrecoverable. Its extract and terminology are documented, but a complete original problem has not been reconstructed.

Statement recorded in the supplied source.

It remains an open question to construct a minimal decomposition in general dimensions, or to describe a finite procedure to compute it. CWPL function f : Rn

\textbackslash{}

to R can be written as the difference f = g − h of two convex CPWL functions [2, 4]. Consequently, a natural idea to circumvent the challenges induced by nonconvexity is to use such a decomposition f = g − h and solve the desired problem separately for g and h. However, the crucial question arising from this strategy is: how much more complex are g and h compared to f ? A well-established measure for the complexity of a CPWL function is the number of its linear pieces. Therefore, the main question we study is the following. Problem 1. How to decompose a CPWL function f into a difference f = g − h of two convex CPWL functions with as few pieces as possible? There exist many ways in the literature to obtain such a decomposition, but none of them guarantees minimality or at least a useful bound on the number of pieces of g and h depending on those of f . In fact, no finite procedure is known that guarantees to find a minimal decomposition, with the exception of a recent solution for special cases in dimension 2 [3]. We propose a novel perspective on Problem 1 making use of polyhedral geome- try. Instead of aiming for a globally optimal decomposition, we restrict to Mini-Workshop: Alcoved Polytopes in Physics and Optimization 553 [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 supplied fragment concerns duplicate Minimal Convex-Difference Decomposition Problem. Its complete mathematical target is not recovered.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30006218 (OWR-14299089-006). Catalogue curation and metadata: CC BY 4.0. The source extract is retained; definitions, English summaries and qualifications are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Mini-Workshop: Alcoved Polytopes in Physics and Optimization $2025$, Oberwolfach Reports, DOI 10.4171/owr/2025/12, pp. 531--558 https://doi.org/10.4171/owr/2025/12.
• S3 Brandenburg--Grillo--Hertrich, Decomposition Polyhedra https://arxiv.org/abs/2410.04907.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

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 30006218 and code OWR-14299089-006 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: 30006217. 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. Codex (GPT-6; exact serving revision not exposed) supplied the auxiliary proof route used here. OpenAI gpt-6-astra, reasoning ultra, independently worked through its mathematical steps, wrote this exposition, and performed the finite checks. This is model collaboration, not independent human verification.

This record is expressly a duplicate extract of the convex-difference question associated with record 30006217; it is retained separately for provenance, not counted as an independent conjecture. The primary and September 2026 published discussion distinguish fixed-complex minimality from unrestricted global minimality. Here the attempted simplification is to remove common convex bending from a univariate pair; the root supplied the slope-splitting route used in the analysis.

Exact cancellation of common bending in one dimension

Let $G,H$ be convex CPWL functions on $\mathbb R$ with finitely many breakpoints. At each position in the union of their breakpoint sets let $\alpha_t,\beta_t\ge0$ be their respective slope jumps, zero if absent. Define \[ C(x)=\sum_t\min(\alpha_t,\beta_t)(x-t)_+. \] Then $G-C$ and $H-C$ remain convex: their jumps are respectively $\max(\alpha_t-\beta_t,0)$ and $\max(\beta_t-\alpha_t,0)$, and their affine left tails are unchanged. Their difference is still $f=G-H$. This proof follows by integrating the stepwise derivatives, or by the hinge representation obtained by matching the affine left tail and every jump.

Writing $p=\#\{t:\alpha_t>\beta_t\}$ and $q=\#\{t:\alpha_t<\beta_t\}$, the resulting counts are $(p+1,q+1)$. These are globally minimal over every convex pair representing $f$: at a positive jump of $f$, any such pair must have a strictly positive jump in its first member; at a negative jump it must have one in the second, because convex jumps are nonnegative and their difference equals the jump of $f$. This gives independent lower bounds of $p+1$ and $q+1$, even if other positions are allowed. Thus removing common bending achieves both lower bounds in this restricted dimension.

An explicit obstruction to reading complexity from an arbitrary pair

For the affine function $f(x)=x$, the pair $(g,h)=(x,0)$ has one piece in each member. For any distinct $t_1,\ldots,t_r$ and positive coefficients $a_j$, adding $C(x)=\sum_{j=1}^ra_j(x-t_j)_+$ to both gives the same $f$ but $r+1$ pieces in each member. Therefore a raw convex-difference representation can be arbitrarily more complex than the minimum. Common-bend cancellation removes all these artificial pieces. Affine functions do not affect convexity, so the example is valid on the whole line.

Verification and remaining gaps

Exact signed-jump tests check cancellation and the affine example with four common bends. In higher dimensions, a local prescription of bends may fail compatibility around faces; this one-dimensional cancellation proof does not establish a global convex function that removes them. Neither the original general-dimensional question nor an independent new problem for this duplicate is solved.

References and source attribution

Primary workshop report: https://doi.org/10.4171/owr/2025/12. Relevant passages read: OWR 2025/12, printed pages551--553; duplicate of the same Problem1.

https://link.springer.com/article/10.1007/s00454-026-00875-1. Read published introduction distinguishing global and fixed-complex problems; not full theorem-proof verification.

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, read and reviewed the written mathematical arguments, independently reran the finite checks, and contributed formatting/repository review. 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 batch026/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.

Minimal Convex Difference Decompositions of CPWL Functions

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.

For continuous piecewise-linear $f$, each affine region carries a linear formula. A convex-difference representation is $f=g-h$ with convex piecewise-linear $g,h$; minimizing pieces requires counting the regions according to the source's convention.

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.

Given a continuous piecewise-linear function $f$, decompose it as $f=g-h$ with $g$ and $h$ convex continuous piecewise-linear functions having as few linear pieces as possible. Construct a finite procedure that finds a globally minimal decomposition in arbitrary dimension. [S2]

Scope qualification.

The objective counting $g$ and $h$ pieces, encoding, and treatment of compatible subdivisions are not specified. The target is global across decompositions, not optimality on one fixed complex.

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-22.

Short English statement

Find a finite globally optimal procedure for decomposing a piecewise-linear function as a difference of two convex ones.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30006217 (OWR-14299089-005). 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 Mini-Workshop: Alcoved Polytopes in Physics and Optimization $2025$, Oberwolfach Reports, DOI 10.4171/owr/2025/12, pp. 531--558 https://doi.org/10.4171/owr/2025/12.
• S3 Decomposition polyhedra of CPWL functions https://openreview.net/forum?id=vVCHWVBsLH. 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 30006217 and source code OWR-14299089-005 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.

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. Codex (GPT-6; exact serving revision not exposed) supplied the auxiliary proof route used here. OpenAI gpt-6-astra, reasoning ultra, independently worked through its mathematical steps, wrote this exposition, and performed the finite checks. This is model collaboration, not independent human verification.

The workshop asks for globally minimal convex-difference decompositions, beyond those compatible with a fixed complex. The September 2026 publisher version retains that distinction in Problem 1.1 and Section 1.1. This attempt gives a complete one-dimensional auxiliary calculation. It is a classical slope decomposition, not new progress in general dimension. The root supplied the same auxiliary route; it was independently checked here.

Global piece minima on the real line

Let $f:\mathbb R\to\mathbb R$ be continuous piecewise affine with finitely many actual breakpoints $t_1<\cdots<t_m$, nonzero slope jumps $\Delta_j$, and affine formula $ax+b$ to the left of all breakpoints. Let $p$ count positive jumps and $q$ negative jumps, so $p+q=m$. Count pieces as maximal intervals on which a convex CPWL function is affine; an affine function has one piece. For example $f(x)=x_+-2(x-1)_++(x-2)_+$ has minimal counts $(3,2)$. For rational sorted breakpoint/slope data the construction uses $O(m)$ arithmetic operations; sorting unsorted distinct positions costs $O(m\log m)$ comparisons. This is an arithmetic count, not a claim that bit lengths are constant.

Verification and remaining gaps

Exact checks compare the hinge formulas interval by interval and count the jump signs, including the affine case $m=0$. In higher dimensions, independently repairing jumps across faces need not yield globally compatible convex functions. This proof supplies neither an enumeration bound for unknown complexes nor a global minimum algorithm in arbitrary dimension.

References and source attribution

Primary workshop report: https://doi.org/10.4171/owr/2025/12. Relevant passages read: OWR 2025/12, printed pages 551--553, Brandenburg Problem1 and fixed-complex theorem.

https://link.springer.com/article/10.1007/s00454-026-00875-1. Read published September2026 abstract, Problem1.1 and Sections1.1.1/1.1.6: fixed-complex versus global distinction remains explicit; full paper not audited.

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, read and reviewed the written mathematical arguments, independently reran the finite checks, and contributed formatting/repository review. 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 batch026/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.