{"id":"9062b807-e3f8-47cc-b8a1-7021c5e076ac","arxiv_id":"2507.07779","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For every depth d below the exact depth of the n-simplex, every depth-d polytope misses the simplex by an empty-corner distance of exactly n+1-2^d.","lead":"This paper proves that a simplex cannot be approximated by polytopes built from sums and convex hulls unless the construction is already deep enough to contain the simplex exactly. The bound, n+1-2^d, is the first sharp inapproximability result for this depth model and transfers to lower bounds on ReLU network depth.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the central additivity assumption (Claim 15) re-derives cleanly and the induction in Theorem 5 is sound.","rationale":"The Reader identified Claim 15 as the weakest assumption, and I agree that this is the most load-bearing step for Theorem 5. However, a careful re-derivation in barycentric coordinates confirms the additivity: the affine constants in the barycentric coordinates cancel in the Minkowski sum, so the empty-corner sizes add exactly. I also checked the induction chain of Theorem 5, including the upper-bound construction via a 2^d-vertex face, the use of Theorem 2 and Theorem 3, and the handling of point operands in the union operation. The proof of the central claim appears internally consistent. The remaining caveats, such as the terseness of geometric arguments in Theorem 8 and the reliance on the external Kadets-type theorem in Lemma 7, do not affect the central claim of Theorem 5. I therefore recommend keeping the Reader's ACCEPT verdict unchanged.","tokens_in":13915,"tokens_out":41562,"duration_ms":479215,"concrete_test":"Verify Claim 15 independently in the standard 2-simplex: choose two convex bodies L1, L2 with different orientations, e.g. small triangles near two different vertices. For each body compute a_j = min alpha_j, M_j = max alpha_j, lambda = 1 - sum a_j, and Ev_j = a_j + lambda - M_j for each vertex j. Then compute the same quantities for L = L1 + L2 and check Ev_j(L) = Ev_j(L1) + Ev_j(L2) for all three j, using the affine barycentric functions alpha_1 = 1-x-y, alpha_2 = x, alpha_3 = y. If this equality fails for any j, the lower bound in Theorem 5 is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. The most load-bearing step in the central claim is Claim 15, which asserts exact additivity of empty-corner sizes under Minkowski sums: Ev(L1+L2, Delta_o(L1+L2)) = Ev(L1, Delta_o(L1)) + Ev(L2, Delta_o(L2)). I re-derived this in barycentric coordinates. Writing the simplex via affine barycentric functions alpha_j with sum alpha_j = 1, the minimal outer homothet has lower bounds a_j = min_L alpha_j and coefficient lambda = 1 - sum a_j. For L = L1 + L2, the affine offsets cancel: a_j^L = a_j^1 + a_j^2 - c_j, M_j^L = M_j^1 + M_j^2 - c_j, and lambda^L = lambda^1 + lambda^2, giving Ev_j(L) = Ev_j(L1) + Ev_j(L2) exactly. The subsequent induction in Theorem 5 is then valid: Theorem 2 gives co-De(P) <= max_j co-De(Q_j), Theorem 3 gives co-De(Q_j) <= co-De(K_j)+co-De(L_j) <= 2^d, and the upper bound is attained by a 2^d-vertex face of Delta_n. The treatment of degenerate point operands, by replacing a singleton with a segment to a point of the other operand, preserves the convex hull and keeps both operands in the induction class. I found no step in the central proof of Theorem 5 that fails.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the approximation of polytopes by polytopes of bounded \"depth\" in a model where depth is measured by the number of alternating layers of Minkowski sums and convex hulls of unions. The main result, Theorem 5, gives an exact formula for the minimum empty-corner distance from the n-dimensional simplex to any depth-d polytope for 0<d<ceil(log2(n+1)), namely n+1-2^d. This implies that simplices cannot be approximated by polytopes of insufficient depth. A secondary result, Theorem 8, characterizes simplices as the only \"outer additive\" convex bodies. The proofs use support functions, barycentric coordinates, and additivity properties of empty-corner sizes under Minkowski sums.","tokens_in":14191,"tokens_out":28380,"duration_ms":285745,"significance":"The main theorem is a sharp, parameter-free inapproximability result with a clean and surprising formula. It strengthens Valerdi's depth-complexity lower bound for simplices and transfers to a lower bound on the expected L1 deviation of support functions, which is relevant to the expressivity of rectified linear unit networks. The proof is elementary and self-contained, and the key additivity lemma (Claim 15) is a nice observation. The characterization of simplices as the only outer additive convex bodies is also attractive and independent of the main line. The paper is clearly written and the central claims are well supported.","major_comments":[],"minor_comments":[{"comment":"The equality Ev(L;H)=min{Ev(L1;H), Ev(L2;H)} is stated without proof; the subsequent argument only uses the trivial inequality direction, so the equality should either be proven or, if not needed, removed to avoid confusion.","section":"Section 4.2, proof of Theorem 3"},{"comment":"The step \"It follows that F is a supporting hyperplane of K\" needs justification; the fact that conv(Bu∪{x}) lies on ∂K implies that the affine hull of that set, and hence any hyperplane containing it, is a supporting hyperplane of K, but this should be spelled out for the reader.","section":"Section 2.2, Claim 12"},{"comment":"The reduction for point terms (when Kj or Lj lies in Pn,0) does not explicitly address the case when both Kj and Lj are singletons; a sentence explaining that such terms can be dropped because translations do not affect the empty-corner distance would complete the induction argument.","section":"Section 4.2, proof of Theorem 5"},{"comment":"The phrase \"By translation if needed, we can assume without loss of generality that H' = k∆o(L)\" is correct but may confuse readers because H' and ∆o(L) are not necessarily concentric; a brief remark that the origin is moved to the center of the homothety mapping one to the other would help.","section":"Section 5.2, proof of Lemma 16"},{"comment":"The title contains a spurious space in \"APPROXIMA TION\"; the paper should be proofread for similar typographical errors.","section":"Title and typographical issues"}],"recommendation":"minor_revision","confidential_remarks":"The central result is sound and the paper is a solid contribution. The proof of Claim 12 in Theorem 8 is terse and would benefit from a more explicit argument, but it does not affect the main inapproximability theorem. The remaining issues are presentation-level and can be addressed locally."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, two things about arXiv:2507.07779. The main result (Theorem 5) is a sharp quantitative inapproximability bound for simplices in the depth model. It strengthens Valerdi's lower bound by showing even approximation fails below the exact depth, and it identifies the precise empty-corner distance n+1-2^d. Along the way, Theorem 8 gives a clean characterization: a convex body is outer additive iff it is a simplex. Both are new.\n\nThe paper earns its keep. The empty-corner distance is a useful tool. The additivity over Minkowski sums, Claim 15, is the load-bearing step, and it re-derives cleanly in barycentric coordinates; I checked it. The induction in Theorem 5 is then straightforward via Theorems 2 and 3. The proof is self-contained except for one external Kadets-type theorem by Akopyan and Karasev, which is properly stated and credited.\n\nSoft spots are proportionately small. The proof of Theorem 8 is terse, especially Claim 12 and the verification that the covering in Claim 21 is inductive. A referee will need to fill in those geometric details. Section 5 is dense; Lemma 19 and Claim 18 assume the reader can keep up, and the application of the Kadets-type result deserves a bit more hand-holding. These are presentation issues, not correctness flaws. No circularity; the lower bound doesn't assume Valerdi's theorem, and self-citations are motivational.\n\nWho should read this: people working on ReLU network depth, monotone networks, and Minkowski decomposability of polytopes. The result yields a concrete epsilon gap for low-depth approximation of the simplex. I'd take it to reading group, and I'd cite it.\n\nMy call: it deserves a serious referee. Send it out. With minor revisions to expand a few arguments it is solid.","headline":"A sharp inapproximability result for simplices in the depth model, with a clean main proof and a few terse corners that a referee can fix.","tokens_in":14725,"tokens_out":3039,"would_cite":true,"duration_ms":30097,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["52A20","52B11","52B12"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that, for every depth $d$ below $\\lceil \\log_2(n+1)\\rceil$, every polytope of depth $d$ misses the $n$-simplex by empty-corner distance at least $n+1-2^d$, and that simplices are the only convex bodies whose outer…","keywords":["approximation depth","convex polytopes","Minkowski sum","simplex","empty-corner distance","depth complexity","outer additive","zonotopes"],"falsifier":"The theorem would be refuted by exhibiting a single polytope $P \\in P_{n,d}$ with $d < \\lceil \\log_2(n+1)\\rceil$ and $D_e(P;\\Delta_n) < n+1-2^d$; the smallest nontrivial case is $n=3, d=1$, where the formula says every centrally symmetric body, i.e. every zonotope, has $D_e = 2$, so a zonotope with $D_e < 2$ would be a direct counterexample.","tokens_in":13698,"feed_emoji":"🔺","tokens_out":11876,"duration_ms":115461,"temperature":0.7,"pith_summary":"The paper studies how well a target polytope can be approximated by polytopes of limited \"depth,\" where depth counts the number of alternating rounds of Minkowski sums and convex hulls of unions used to build the polytope, the same hierarchy that describes convex functions computed by ReLU networks with a given number of hidden layers. Its central result is that simplices are essentially inapproximable at insufficient depth: for every $d < \\lceil \\log_2(n+1)\\rceil$, the best possible empty-corner distance from the $n$-dimensional simplex to any depth-$d$ polytope is exactly $n+1-2^d$. Consequently, no sequence of depth-$d$ polytopes can converge to the simplex in the Hausdorff metric until $d$ reaches the simplex's exact depth complexity. Along the way the paper proves that simplices are the only convex bodies for which the outer homothety coefficient is additive under Minkowski sums, and this additivity is what makes the distance computation exact. The result matters because the simplex is the universal generator for piecewise-linear convex functions, so the distance lower bound transfers to a positive approximation error for shallow networks, measured against uniform directions on the sphere.","feed_headline":"Depth-d polytopes miss the simplex by exactly n+1-2^d","feed_subtitle":"Below depth log2(n+1) the gap is forced, so shallow polytope networks cannot touch the basic simplex.","key_machinery":"The central object is the empty-corner distance $D_e(L;\\Delta_n)$. For the smallest homothet $\\Delta_o(L)$ of the simplex containing $L$, each vertex $v$ of $\\Delta_o(L)$ has an empty corner of size $E_v(L;\\Delta_o(L))$ measuring the largest homothet of $\\Delta_n$ inside $\\Delta_o(L)$ with vertex $v$ that avoids $L$; the distance is the sum of these sizes divided by the size of $\\Delta_o(L)$. The co-distance $\\operatorname{co-}D_e = n+1-D_e$ is the quantity that behaves well. The key identity is Claim 15: for a Minkowski sum $L = L_1 + L_2$, the empty-corner sizes add termwise, $E_v(L,\\Delta_o(L)) = E_v(L_1,\\Delta_o(L_1)) + E_v(L_2,\\Delta_o(L_2))$, which implies $D_e(L)$ lies between $D_e(L_1)$ and $D_e(L_2)$. Theorem 3 gives the conjugate inequality for $K * L = \\operatorname{conv}(K \\cup L)$: $\\operatorname{co-}D_e(K * L) \\le \\operatorname{co-}D_e(K) + \\operatorname{co-}D_e(L)$. Running these two inequalities over the inductive definition of $P_{n,d}$ is what forces the value $n+1-2^d$.","core_discovery":"For the simplex $\\Delta_n$, the depth hierarchy has an exact approximation profile. Theorem 5 states that for $0 < d < \\lceil \\log_2(n+1)\\rceil$ the minimum empty-corner distance from $\\Delta_n$ to a non-point depth-$d$ polytope is $n+1-2^d$, and the minimum is attained. Thus the previously known lower bound on the depth complexity of the simplex is stable: before depth $\\lceil \\log_2(n+1)\\rceil$, approximation is not merely impossible to make exact, it is bounded away from zero by a forced discrete gap. The proof rests on two structural facts: Minkowski sums cannot reduce the distance (Theorem 2 gives $\\operatorname{co-}D_e(L) \\le \\max_j \\operatorname{co-}D_e(L_j)$), and the convex hull of a union can at most add the two co-distances (Theorem 3 gives $\\operatorname{co-}D_e(L_1 * L_2) \\le \\operatorname{co-}D_e(L_1) + \\operatorname{co-}D_e(L_2)$). Together with the value $\\operatorname{co-}D_e = n-1$ for centrally symmetric bodies (Lemma 4, which gives the depth-one base case), the induction forces the exact formula. The paper also proves Theorem 8: a convex body is outer additive if and only if it is a simplex, and Lemmas 6 and 7 relate the empty-corner distance to the in-out distance, transferring the obstruction to the functional and network setting.","pith_inferences":["Editorial: because the exact gap $n+1-2^d$ is attained by a simple construction, the theorem yields a computable certificate: any proposed depth-$d$ approximation can be checked against the empty-corner profile, giving a direct lower-bound test for network depth.","Editorial: since the proof of outer additivity needs only interval summands, the characterization of simplices suggests a practical finite test for recognizing simplex-shaped convex bodies: test additivity against pairs of intervals in sufficiently many directions.","Editorial: a natural testable extension is to replace the simplex by another simplex-faced indecomposable polytope and ask whether an analogous exact corner-distance formula holds; the proof here is simplex-specific, so such an extension would require a new additive quantity."],"forward_implications":["If Theorem 5 is correct, then for every $d < \\lceil \\log_2(n+1)\\rceil$ no sequence of depth-$d$ polytopes converges to $\\Delta_n$; the distance is bounded below by $n+1-2^d$, and the bound is sharp by an explicit construction.","The depth-one case is exactly Lemma 4: every centrally symmetric body, in particular every zonotope, sits at distance $n-1$ from the simplex, so no amount of Minkowski summing improves on the formula at $d=1$.","On the function side, the lower bound translates to a uniform positive gap: for fixed $n$ and any depth-$d$ network with $d < \\lceil \\log_2(n+1)\\rceil$, the expected absolute difference between its support function and that of the simplex, over uniform directions on the sphere, is at least some $\\varepsilon_0(n) > 0$.","The characterization of outer additivity shows the trivial-approximation phenomenon is not an accident of the chosen distance: simplices are the only convex bodies for which the outer coefficient is exactly additive under Minkowski sums.","Because the exact gap $n+1-2^d$ is attained, the theorem gives a sharp non-asymptotic tradeoff between depth and approximation quality rather than only an asymptotic inapproximability statement."],"supporting_citations":[{"why":"Proves the depth-complexity lower bound $\\lceil \\log_2(n+1)\\rceil$ for the simplex, which Theorem 5 strengthens from exact computation to approximation stability.","marker":"[21]"},{"why":"Establishes the classical result that indecomposable targets can only be approximated by homothets, the asymptotic analogue this paper makes quantitative for simplices.","marker":"[16]"},{"why":"Supplies indecomposability of simplices and the decomposition theory of polytopes used to frame the main theorems.","marker":"[17]"},{"why":"Provides the Kadets-type theorem used in the proof of Lemma 7 to compare empty-corner distance with in-out distance.","marker":"[1]"},{"why":"Contains the containment and inscribed-simplex techniques used in Lemma 19 to select supporting half-spaces while preserving the inner simplex coefficient.","marker":"[12]"},{"why":"Motivates the depth hierarchy through monotone ReLU networks and input convex neural networks and supplies adjacent expressivity results for the same model.","marker":"[3]"},{"why":"Used to state that the simplex's depth complexity governs the depth needed to compute all piecewise-linear convex functions, the target of the functional implications.","marker":"[2]"},{"why":"Used alongside [2] for hinging-hyperplane representations of piecewise-linear functions and their depth requirements.","marker":"[22]"}],"fun_headline_variants":["Simplex gap: n+1-2^d before depth log2(n+1)","Depth-d polytopes can't touch simplex: exact gap","Forced gap: simplex needs depth > log2(n+1)","Exact empty-corner distance: n+1-2^d for simplex","Shallow polytopes miss simplex by n+1-2^d"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument that forces the exact value $n+1-2^d$ depends on Claim 15: for Minkowski sums, the empty-corner sizes add exactly, a property proved only for simplices, so if that additivity failed for some summands in the depth hierarchy the induction would no longer force the gap.","fun_headline_variants_meta":{"raw":{"variants":["Simplex gap: n+1-2^d before depth log2(n+1)","Depth-d polytopes can't touch simplex: exact gap","Forced gap: simplex needs depth > log2(n+1)","Exact empty-corner distance: n+1-2^d for simplex","Shallow polytopes miss simplex by n+1-2^d"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000187,"raw_usage":{"total_tokens":1330,"prompt_tokens":945,"completion_tokens":385,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":561,"completion_tokens_details":{"reasoning_tokens":285}},"tokens_in":561,"tokens_out":385,"duration_ms":4494,"temperature":1.0,"reasoning_tokens":285,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T18:34:33.261038+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The theorem would be refuted by exhibiting a single polytope $P \\in P_{n,d}$ with $d < \\lceil \\log_2(n+1)\\rceil$ and $D_e(P;\\Delta_n) < n+1-2^d$; the smallest nontrivial case is $n=3, d=1$, where the formula says every centrally symmetric body, i.e. every zonotope, has $D_e = 2$, so a zonotope with $D_e < 2$ would be a direct counterexample.","supporting_citations":[{"cited_title":"Valerdi, On minimal depth in neural networks , arXiv:2402.15315 (2024)","cited_arxiv_id":null,"evidence_quote":"Proves the depth-complexity lower bound $\\lceil \\log_2(n+1)\\rceil$ for the simplex, which Theorem 5 strengthens from exact computation to approximation stability."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the classical result that indecomposable targets can only be approximated by homothets, the asymptotic analogue this paper makes quantitative for simplices."},{"cited_title":"Shephard, Decomposable convex polyhedra, Mathematika 10 (1963), no","cited_arxiv_id":null,"evidence_quote":"Supplies indecomposability of simplices and the decomposition theory of polytopes used to frame the main theorems."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Kadets-type theorem used in the proof of Lemma 7 to compare empty-corner distance with in-out distance."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Contains the containment and inscribed-simplex techniques used in Lemma 19 to select supporting half-spaces while preserving the inner simplex coefficient."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Used to state that the simplex's depth complexity governs the depth needed to compute all piecewise-linear convex functions, the target of the functional implications."},{"cited_title":"12, 4425–4431","cited_arxiv_id":null,"evidence_quote":"Used alongside [2] for hinging-hyperplane representations of piecewise-linear functions and their depth requirements."}],"review_version":1}