we-solve (beta)

CS-448 · computer science · mathematics · Artificial intelligence and machine learning · Computational complexity

Hidden-Layer Depth Complexity of Piecewise-Linear Functions

Status Open · 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.

ReLU is $\sigma(t)=\max\{0,t\}$. Hidden layers are the intermediate affine-plus-activation stages, excluding the final affine output; a continuous piecewise-linear function has finitely many affine regions with continuous agreement across boundaries.

A feed-forward neural network composes affine maps and specified nonlinear activations. ReLU is $\sigma(t)=\max\{0,t\}$. Empirical risk averages a loss on training samples; population risk is its expectation on the target distribution, and generalization compares these risks.

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.
What is the exact minimum hidden-layer depth required for a ReLU network to represent the function $(x_1,\ldots,x_d)\mapsto\max\{x_1,\ldots,x_d\}$? More generally, does there exist a continuous piecewise-linear function that cannot be represented by any ReLU network with at most two hidden layers? [S2]
Scope qualification.
Width, weight field, and layer-count convention are those of the source. The two questions are both retained, without equating a maximum-specific lower bound with a general depth separation.
Source status.
The supplied catalogue labels this record open. 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 the exact depth needed to represent maximum and determine whether any piecewise-linear function needs more than two hidden layers.

Sources

  • S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30006671 (OWR-14299916-009). 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 Modern and Emerging Phenomena in Machine Learning (2026), Oberwolfach Reports, DOI 10.4171/owr/2026/11, pp. 683--736 https://doi.org/10.4171/owr/2026/11.
  • S3 Ruess et al., Shallower ReLU Network Representations https://arxiv.org/abs/2607.21651.
  • S4 Bakaev et al., Better Neural Network Expressivity https://arxiv.org/abs/2505.14338. 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 30006671 and source code OWR-14299916-009 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 1

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

gpt 6 astra ultra attempt on CS-448

Hidden-Layer Depth Complexity of Piecewise-Linear 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.

ReLU is $\sigma(t)=\max\{0,t\}$. Hidden layers are the intermediate affine-plus-activation stages, excluding the final affine output; a continuous piecewise-linear function has finitely many affine regions with continuous agreement across boundaries.

A feed-forward neural network composes affine maps and specified nonlinear activations. ReLU is $\sigma(t)=\max\{0,t\}$. Empirical risk averages a loss on training samples; population risk is its expectation on the target distribution, and generalization compares these risks.

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.
What is the exact minimum hidden-layer depth required for a ReLU network to represent the function $(x_1,\ldots,x_d)\mapsto\max\{x_1,\ldots,x_d\}$? More generally, does there exist a continuous piecewise-linear function that cannot be represented by any ReLU network with at most two hidden layers? [S2]
Scope qualification.
Width, weight field, and layer-count convention are those of the source. The two questions are both retained, without equating a maximum-specific lower bound with a general depth separation.
Source status.
The supplied catalogue labels this record open. 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 the exact depth needed to represent maximum and determine whether any piecewise-linear function needs more than two hidden layers.

Sources

  • S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30006671 (OWR-14299916-009). 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 Modern and Emerging Phenomena in Machine Learning $2026$, Oberwolfach Reports, DOI 10.4171/owr/2026/11, pp. 683--736 https://doi.org/10.4171/owr/2026/11.
  • S3 Ruess et al., Shallower ReLU Network Representations https://arxiv.org/abs/2607.21651.
  • S4 Bakaev et al., Better Neural Network Expressivity https://arxiv.org/abs/2505.14338. 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 30006671 and source code OWR-14299916-009 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 catalogue body, including qualifications and historical source status, is preserved above. The original workshop report was inspected in the locally cached publisher PDF text. This attempt distinguishes the source question from any explicitly restricted model introduced below. Repeated records retain their own source IDs and do not become independent conjectures. Elementary results and attributed literature results are not claimed as new original-target progress.

Literature qualification and attempted hyperplane-jump lower bound

The current primary Rueß et al. preprint, version 2, gives two-hidden-layer representations of $\max_n$ for $n\le12$; this is attributed work, not a result of this attempt. The catalogue's older summary mentioned a smaller range. We test a direct geometric lower-bound route and locate exactly where it stops.
Proposition: The function $f(x_1,x_2,x_3)=\max\{x_1,x_2,x_3\}$ cannot be represented by a finite-width ReLU network with one hidden layer and real weights, but can be represented with two hidden layers.
Proof: A one-hidden-layer representation, even allowing an additional affine term, has the form $\ell(x)+\sum_{j=1}^r a_j\sigma(w_j^Tx+b_j)$. Zero normals contribute constants and can be absorbed into $\ell$. The only potential gradient jumps are on the finitely many hyperplanes $H_j=\{w_j^Tx+b_j=0\}$. Let $H=\{x_1=x_2\}$. On its open part $U=\{x_1=x_2>x_3\}$ the target has a nonzero gradient jump $e_1-e_2$ when crossing from $x_1<x_2$ to $x_1>x_2$. A finite union of intersections of other hyperplanes with $H$ cannot cover the two-dimensional open set $U$: each distinct intersection is a line or empty. Thus some neurons must have hyperplane exactly $H$. Their combined gradient jump across $H$ is a fixed vector, independent of the crossing point, since each is a scalar ReLU of a multiple of $x_1-x_2$. At points of $H$ away from all other $H_j$, all remaining terms are affine in a neighborhood, and contribute zero jump. The fixed jump therefore must equal $e_1-e_2$ on $U$. But the open part $V=\{x_1=x_2<x_3\}$ also contains points avoiding all other hyperplanes. Near any such point the target is simply $x_3$ and has zero jump across $H$. The same fixed vector would have to be zero, a contradiction. For an explicit two-hidden-layer construction, the first layer produces \[ h=\sigma(x_1-x_2),\quad u_2=\sigma(x_2),\ v_2=\sigma(-x_2),\quad u_3=\sigma(x_3),\ v_3=\sigma(-x_3). \] The second layer produces $q=\sigma(h+u_2-v_2-u_3+v_3)$ and copies the nonnegative $u_3,v_3$ through ReLU units. The affine output is $q+u_3-v_3$. Since $u_i-v_i=x_i$, this equals $\sigma(\max(x_1,x_2)-x_3)+x_3=f$. ∎
Restricting the additional coordinates to $x_3$ yields the same one-hidden-layer obstruction for every $\max_d$ with $d\ge3$. The attempted next induction fails: in a second hidden layer a preactivation is piecewise affine, so its zero set need not be a whole hyperplane with a spatially constant jump. Our own two-layer construction already localizes such jumps. The proof therefore cannot be repeated to show a function needs more than two hidden layers.

Verification and remaining gaps

The explicit network was evaluated exactly on all 125 triples in $\{-2,-1,0,1,2\}^3$. The hyperplane argument is a standard elementary lower bound, not novel progress. The exact unrestricted depth for all dimensions and the existence of any function requiring more than two hidden layers are not resolved here.

References and source attribution

The primary Oberwolfach workshop report, https://doi.org/10.4171/owr/2026/11, was inspected on 11 October 2026. Relevant source passages: 2026/11 pp. 725--726, exact ReLU depth question. Catalogue and contributor attribution remain in the original Sources section. Mathematical arguments labeled as this attempt are proved above; cited external results remain attributed to their authors and are not independently reproved or claimed as our discoveries.

https://arxiv.org/html/2607.21651v2. Rueß and coauthors, Shallower ReLU Network Representations via Exact Linear Algebra, version 2. Opened full primary HTML; Theorem 1.1 states exact depth two for arities 3 through 12, and the introduction distinguishes unrestricted from weight-restricted lower bounds. This reported theorem is not independently reproved here.

https://arxiv.org/abs/2505.14338. Bakaev and coauthors, Better Neural Network Expressivity: Subdividing the Simplex. Primary abstract checked for the earlier five-input construction and its distinction from restrictions on the weight field.

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 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 batch011/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 →