{"id":"da92b1a8-ce6b-4438-9e12-549553845915","arxiv_id":"2412.13372","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"SOS programs can certify MTW non-negativity for rational costs, but the inverse-region theorem is mathematically flawed.","lead":"This paper proposes using sum-of-squares optimization to certify, by computer, that a transportation cost satisfies the Ma-Trudinger-Wang curvature condition, which guarantees the optimal transport map is continuous. The forward certificates are sound in principle, but the inverse procedure for locating regions of regularity has a mathematical gap.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 7's V− branch relies on the false claim that nonpositive principal minors imply negative semidefiniteness, so the advertised NNCC inverse inner-approximation is unproved.","rationale":"The reader's weakest-assumption diagnosis is exactly the load-bearing flaw: the V− branch of Theorem 7 assumes that nonpositive principal minors characterize negative semidefiniteness, which is false in dimension two and higher. This is not a peripheral technicality; the inverse problem is one of the two headline contributions in the abstract and Section 1. The forward theorems 5 and 6 are sound sufficient conditions, and the numerical experiments are suggestive, but the reported residuals (1e-7 to 1e-11) also do not support the phrase 'provably correct' without an exact rounding or rational-certificate step. Still, the decisive issue is the invalid inverse theorem. Since the paper's central claim is a general, provably correct framework for both certification and inner approximation, and the inner-approximation half is not established, the REJECT verdict stands. I do not propose changing the reader's verdict; I only sharpen the concrete counterexample that confirms it.","tokens_in":26580,"tokens_out":10938,"duration_ms":109995,"concrete_test":"Re-derive the V− branch of Theorem 7 using the correct negative-semidefiniteness criterion: all principal minors of -A nonnegative. Then run the explicit instance with A = [[-1, 2], [2, -1]], F_D = -1, Λ = X × Y = closed unit disk, V = 0, m_1 = x^2 + y^2 - 1, r_1 = 1, and all other SOS multipliers zero. All V− constraints are SOS, so Theorem 7 would certify NNCC on Λ; however F = F_N/F_D = [[1, -2], [-2, 1]] has eigenvalues 3 and -1, so NNCC fails at e.g. (x,y) = (0,0).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central advertised capability includes computing semialgebraic inner approximations for the NNCC/MTW conditions. In the proof of Theorem 7 (Section 3.2), the V− branch imposes that every principal minor f_j of F_N satisfies f_j ≤ 0 on the sublevel set {V ≤ 0}, and then concludes that F_N is negative semidefinite, so that F = F_N/F_D is positive semidefinite when F_D < 0. That implication is false for n ≥ 2. For example, A = [[-1, 2], [2, -1]] has all principal minors nonpositive (-1, -1, and det = -3) but has eigenvalues 1 and -3, so it is indefinite. Consequently F_N/F_D need not be positive semidefinite. The V− branch of Theorem 7 therefore does not certify NNCC on the claimed union of sublevel sets, and the inverse NNCC problem—one of the two main advertised contributions—is left without a valid proof. Theorem 8 has a separate gap: it returns a subset of the extended variables (x, y, ξ, η), not a subset U × V of X × Y as promised, so it also does not deliver the advertised region. The forward SOS theorems 5 and 6 are sound sufficient conditions, but they do not repair the inverse problem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a sum-of-squares (SOS) programming framework for two tasks in optimal transport regularity: (i) certifying non-negativity of the Ma-Trudinger-Wang (MTW) tensor / non-negative cost curvature (NNCC) for a given rational ground cost over a semialgebraic domain, and (ii) computing semialgebraic inner approximations of the region where these conditions hold. The forward method is stated in Theorems 5 and 6, the inverse NNCC method in Theorem 7, and the inverse MTW method in Theorem 8. Numerical examples treat a perturbed Euclidean cost, a log-partition cost for the isotropic multivariate normal, and a squared-distance cost for a positively curved surface, using SOSTOOLS/YALMIP.","tokens_in":26776,"tokens_out":18294,"duration_ms":167252,"significance":"If the proposed theorems were correct, the paper would contribute a broadly applicable computational tool to a problem—verifying MTW/NNCC conditions—that has previously been handled only by hand-crafted analytic arguments for specific costs. The forward SOS certificates are attractive because they reduce a hard nonnegativity question to an SDP, and the inverse certificates would give a constructive way to localize regularity regions. The numerical experiments are concrete, and the paper honestly reports residuals and timings. However, the advertised 'provably correct' claim is compromised by several load-bearing gaps: the forward theorems omit a sign condition on the denominator, the inverse NNCC theorem relies on a false matrix-semidefiniteness criterion, and the inverse MTW theorem returns a subset of the extended (x,y,xi,eta) space rather than a subset of X×Y. These issues need substantial repair before the central claims are supported.","major_comments":[{"comment":"The proof of Theorem 5 infers from the certificate (13) that F_N(x,y)+F_N^T(x,y) is positive semidefinite only under the additional condition F_D(x,y) >= 0. When F_D < 0 on a subset of X×Y, the certificate imposes no useful lower bound on F_N; indeed, for the scalar rational matrix F = -1 represented as F_N = 1, F_D = -1, the choice s0 = 0 satisfies (13) with no constraints, yet NNCC fails. Thus Theorem 5 is not a sound sufficient condition as stated. Theorem 6 has the same sign deficiency: for F_D < 0, inequality (14) implies an upper bound on the quadratic form of F_N after division by a negative denominator, which is the opposite of the MTW lower bound. The statements should either explicitly assume F_D > 0 on X×Y or split into the two sign cases handled later in Theorem 7.","section":"Section 3.1, Theorem 5 (and Theorem 6)"},{"comment":"In the V− branch, the SOS constraints together with V(x,y) <= 0 imply that all principal minors f_j of F_N satisfy f_j <= 0. The proof then concludes that F_N is negative semidefinite, so that F_N/F_D is positive semidefinite when F_D < 0. This implication is false for n >= 2: the matrix A = [[-1, 2], [2, -1]] has all principal minors non-positive but is indefinite (eigenvalues 1 and -3). Consequently the claimed inner approximation {(x,y) ∈ Λ | V−(x,y) <= 0} is not certified to be a region where NNCC holds. The correct condition for negative semidefiniteness requires all principal minors of -F_N to be nonnegative, i.e., the principal minors of F_N of size k must have sign (-1)^k; non-positive principal minors alone are insufficient.","section":"Section 3.2, Theorem 7, V− branch"},{"comment":"The inverse problem (16) asks for a subset U×V of X×Y on which the MTW(κ) condition holds, but Theorem 8 returns a subset of the extended variable space: {(x,y,ξ,η) ∈ Λ | V±(x,y,ξ,η) <= 0, η(ξ)=0}. This is not a subset of X×Y, and even if a base point (x,y) belongs to the projection, the theorem only certifies the inequality for those (ξ,η) that lie in the sublevel set, not for all orthogonal pairs (ξ,η) as required by MTW(κ). Therefore the regions plotted in Examples 3 and 4 (Figures 1 and 2) are not established as regions of MTW regularity in the sense of the advertised inverse problem. The theorem needs to be reformulated so that V is independent of (ξ,η) (or otherwise quantified over all admissible pairs) and the returned object is a genuine base-space region.","section":"Section 3.2, Theorem 8"},{"comment":"The paper repeatedly states that the framework can 'certify or falsify' non-negativity of the MTW tensor (Abstract and Contributions), and Section 3.2 says infeasibility of the forward problem 'falsifies' the condition. However, the numerical pipeline solves SOS tightenings, which are only sufficient conditions; infeasibility of the SOS program at a given relaxation degree does not imply that the original polynomial inequalities are violated. The bisection estimates in Section 4.1 therefore do not rigorously establish the reported thresholds εmax as exact bounds. The language should be softened to 'certify' only, or the falsification claim should be justified with a convergent hierarchy or an explicit separating point.","section":"Introduction and Section 3.2"}],"minor_comments":[{"comment":"The notation U×V is used for an arbitrary sublevel set {(x,y) ∈ X×Y | V(x,y) <= 0}, which is not necessarily a Cartesian product of a subset U of X and a subset V of Y. This is misleading; consider using a different symbol such as W or R for the candidate region.","section":"Section 3.2, Eq. (15)-(19)"},{"comment":"The use of '±' in the constraints is terse: the plus and minus signs correspond to two separate SOS systems for V+ and V−, respectively. The statement would be clearer if the two systems were written out explicitly.","section":"Theorems 7 and 8 statements"},{"comment":"The definition of the residual as 'the largest coefficient in the polynomial S − s^T s' is unclear: S and s are not precisely defined in the table caption, and it is not evident that the quantity is nonnegative or that it measures feasibility error. Please spell out the residual computation.","section":"Table 2 and Table 3"},{"comment":"The reported SOS decomposition for the n=3 log-partition example presents s as a matrix of coefficients multiplied by a monomial vector, but the surrounding text writes s(x,ξ,η)^T s(x,ξ,η). Please clarify whether s is a vector or a matrix and whether the displayed object is the Gram-matrix factor.","section":"Appendix D"},{"comment":"The sentence 'For n = 1, there are no pairs ξ, η such that η(ξ) = 0 with η and ξ both non-zero' is correct, but it implies that MTW(0) is vacuous in 1D; the example appears to be verifying NNCC instead. The text should state this explicitly to avoid confusion.","section":"Section 4.1, Example 1"},{"comment":"There are numerous typographical artifacts in the rendering: for example, 'Y ALMIP' appears with an internal space, 'Positivstellansatz' is misspelled, and 'X Y' is sometimes printed without a product symbol. A careful proofreading pass is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The reader's take recommends rejection, and I agree that the current version does not support the advertised claims because of the Theorem 7 principal-minor error and the Theorem 8 mismatch. However, I see a viable repair path: adding a sign assumption (F_D > 0) to Theorems 5-6, replacing the false principal-minor test in Theorem 7 with the correct alternating-sign condition for negative semidefiniteness, and reformulating Theorem 8 so that the output is a genuine X×Y region quantified over all directions. These are substantial but in-scope technical corrections. If the authors can repair the theorems and rerun the examples under the corrected certificates, the paper could be publishable; the present form, though, is not. A rejection is also defensible if the authors are unable to deliver the corrected inverse theorems."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know first: the forward half of this paper is a genuine, useful contribution. Theorems 5 and 6 give sound sufficient conditions for certifying NNCC and MTW(kappa) via SOS programming, and the log-partition cost example with an explicit SOS decomposition for n=3 is a real computational result. The bisection match with the known n=1 threshold (2/3) is reassuring. That part deserves credit.\n\nThe inverse half does not hold up. Theorem 7's V-minus branch concludes that F_N/F_D is positive semidefinite on the sublevel set {V <= 0} because all principal minors of F_N are nonpositive there. That implication is false in dimension two and higher: the symmetric matrix [[-1,2],[2,-1]] has all principal minors nonpositive but is indefinite. So the advertised union of sublevel sets is not certified to satisfy NNCC. This is not a minor typo; it is the load-bearing step for one of the two main contributions. Theorem 8 has a separate structural gap: it returns a subset of (x,y,xi,eta) satisfying eta(xi)=0, not a product set U times V subset of X times Y as the inverse problem promises. The \"provably correct\" language is also stronger than the numerics support: residuals around 1e-7 are approximate certificates, and without exact rounding or rational reconstruction they are not proofs.\n\nThe forward part is a solid start. The inverse formulation might be repairable, for example by enforcing -F_N PSD directly rather than via principal minors, and by handling the product-set issue explicitly. But as submitted, the central claim of a general, provably correct framework that handles both forward and inverse problems is not supported. I would not accept this version, but I would send it to peer review: the topic matters, the forward results are worth refereeing, and the flaws are specific enough for a reviewer to point to and for the authors to fix. My own verdict is skeptical on the current version, not dismissive of the approach.","headline":"The forward SOS certification of MTW/NNCC is new and usable; the inverse problem is invalid as stated because Theorem 7 relies on a false principal-minor criterion and Theorem 8 returns the wrong kind of set.","tokens_in":27352,"tokens_out":3652,"would_cite":true,"duration_ms":33869,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["49Q22","90C22","14P10"],"pacs":[],"model":"deepseek-v4-flash","headline":"SOS certificates now prove where optimal transport maps stay regular","keywords":["optimal transport","Ma-Trudinger-Wang tensor","MTW condition","Monge map regularity","sum-of-squares programming","semidefinite programming","non-negative cost curvature","semialgebraic geometry"],"falsifier":"Apply the $V_-$ argument to $F_N=\\begin{pmatrix}-1&2\\\\2&-1\\end{pmatrix}$ with $F_D=-1$: every principal minor of $F_N$ is non-positive, so the proof's premise is satisfied, yet $F_N$ has a positive eigenvalue and $-F_N$ is not positive semidefinite; a feasible $V_-$ SOS certificate would therefore certify NNCC where it does not hold.","tokens_in":26296,"feed_emoji":"📐","tokens_out":10745,"duration_ms":93546,"temperature":0.7,"pith_summary":"The paper sets out to make the Ma–Trudinger–Wang (MTW) condition algorithmically checkable: for a given ground cost, it wants to certify or falsify non-negativity of the fourth-order MTW tensor, and to compute the region in which that non-negativity holds. The proposed route is sum-of-squares (SOS) programming. Whenever the MTW tensor matrix is rational over a semialgebraic domain, the certification problem becomes an SOS feasibility problem, hence a semidefinite program, via Theorems 5 and 6. The inverse problem is solved by parameterizing the unknown region as the zero sublevel set of a polynomial and minimizing its volume under SOS constraints, yielding inner approximations claimed by Theorems 7 and 8. Numerical examples recover a known analytical threshold for a perturbed Euclidean cost, certify a log-partition cost in dimensions three through six, and localize regularity for a positive-curvature squared-distance cost.","feed_headline":"SOS certificates prove where optimal transport stays regular","feed_subtitle":"The MTW curvature condition becomes a semidefinite program and the regular region is computed explicitly.","key_machinery":"The central object is the MTW tensor matrix $F(x,y)\\in\\mathbb{R}^{n^2\\times n^2}$ built from partial derivatives of the ground cost $c$ and from the inverse mixed Hessian $H=((\\nabla_x\\otimes\\nabla_y)c)^{-1}$; the MTW quadratic form is $(\\xi\\otimes\\eta)^\\top F(\\xi\\otimes\\eta)$. The carrying mechanism is the Positivstellensatz in its SOS form: a polynomial that is non-negative on an Archimedean semialgebraic set can be written as a sum of squares plus multipliers of the set-defining inequalities. The forward theorems substitute that representation into the MTW inequality, turning it into a semidefinite program; the inverse theorems use the same representation with the region-defining polynomial $V$ as the decision variable, so the zero sublevel sets of $V_+$ and $V_-$ give the inner approximation of the regular region.","core_discovery":"On the paper's own terms, the central discovery is that optimal-transport regularity verification reduces to linear algebra: the MTW tensor is written as $S(x,y)(\\xi,\\eta)=(\\xi\\otimes\\eta)^\\top F(x,y)(\\xi\\otimes\\eta)$, and when the entries of $F$ are rational functions, the condition $S\\ge 0$ on a semialgebraic set is equivalent to an SOS feasibility problem. The same reduction handles the strong MTW($\\kappa$) condition, with the orthogonality constraint $\\eta(\\xi)=0$ absorbed by a polynomial multiplier in the SOS identity. For the inverse problem, the paper claims that an inner approximation of the regular region can be computed by minimizing the volume of a polynomial sublevel set subject to SOS constraints, with two certificates $V_+$ and $V_-$ covering the cases where the denominator of $F$ is positive or negative. The paper therefore claims the first provably correct computational framework for certifying, falsifying, and localizing MTW and non-negative cost curvature (NNCC) regularity for a broad class of ground costs, including costs that are not themselves rational as long as $F$ is rational.","pith_inferences":["Inference: the forward certificate could be used as a design constraint on a parameterized family of costs, letting one search over costs that are guaranteed MTW-regular rather than merely checking a fixed cost.","Inference: the paper notes that MTW and NNCC imply connected $c$-subdifferentials and faster $c$-conjugation; a testable extension is to use the computed regions as domain decompositions inside numerical OT solvers, where continuity of the map is known a priori.","Inference: for non-rational costs such as $-\\log\\|x-y\\|$, rational approximation of the cost would make the same pipeline applicable to reflector-antenna and lens-design problems; the paper lists these as motivating examples but does not run them.","Inference: bisection in $\\kappa$ over the forward MTW($\\kappa$) certificate would yield the largest strong-MTW constant, turning the binary certificate into a quantitative regularity margin."],"forward_implications":["For rational ground costs, MTW(0) and MTW($\\kappa$) verification becomes a semidefinite program; feasibility is a certificate of regularity on the entire semialgebraic domain.","Infeasibility of the forward SOS program is a computational falsification of MTW or NNCC on that domain, giving a concrete breakdown point for continuity of the Monge map.","The inverse program outputs an explicit polynomial $V$ whose zero sublevel set is a provable inner approximation of the regular region, so the user knows exactly where the map is guaranteed to be continuous.","The method reproduces analytically known results, such as the $\\varepsilon_{\\max}=2/3$ threshold for the one-dimensional perturbed Euclidean cost, and extends to log-partition costs whose MTW tensor is rational even though the cost itself is not.","Because the certificates are SOS identities, the outputs are machine-checkable and can be handed to existing semidefinite-programming solvers."],"supporting_citations":[{"why":"defines the MTW tensor and the biquadratic inequality that the paper certifies.","marker":"Ma et al. (2005)"},{"why":"proves that the MTW condition is sufficient for continuity of the Monge map, motivating the certification problem.","marker":"Trudinger & Wang (2009)"},{"why":"establishes (for smooth costs) the necessity of the MTW condition via connected $c$-subdifferentials and connects it to reflector-antenna costs.","marker":"Loeper (2009)"},{"why":"supplies the SOS-to-SDP parameterization that turns polynomial non-negativity constraints into semidefinite programs.","marker":"Parrilo (2003)"},{"why":"provides the Positivstellensatz representation of strictly positive polynomials on Archimedean semialgebraic sets used in the certificates.","marker":"Putinar (1993)"},{"why":"gives the log-partition cost example and the analytic MTW(0) result that the SOS certificate in Example 2 reproduces.","marker":"Khan & Zhang (2020)"},{"why":"supplies the analytic MTW(0) benchmark for the perturbed Euclidean cost used in Example 1.","marker":"Lee & Li (2009)"},{"why":"provides analytic MTW examples for hyperbolic and related costs, including the positive-curvature metric in Example 4.","marker":"Lee & Li (2012)"},{"why":"is the source of the sublevel-set volume-minimization heuristic that the inverse problem's objective is modeled on.","marker":"Jones (2024)"}],"fun_headline_variants":["SOS certificates verify MTW regularity for transport maps","MTW positivity checked by sum-of-squares programming","Certifying MTW regularity becomes a semidefinite program","SOS proof of MTW non-negativity for transport costs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of the inverse theorem's negative-denominator branch assumes that a symmetric matrix whose principal minors are all non-positive must be negative semidefinite, an implication that is false in dimension two and higher.","fun_headline_variants_meta":{"raw":{"variants":["SOS certificates verify MTW regularity for transport maps","MTW positivity checked by sum-of-squares programming","Certifying MTW regularity becomes a semidefinite program","SOS proof of MTW non-negativity for transport costs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000794,"raw_usage":{"total_tokens":3506,"prompt_tokens":964,"completion_tokens":2542,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":580,"completion_tokens_details":{"reasoning_tokens":2476}},"tokens_in":580,"tokens_out":2542,"duration_ms":17859,"temperature":1.0,"reasoning_tokens":2476,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T13:12:28.154383+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Apply the $V_-$ argument to $F_N=\\begin{pmatrix}-1&2\\\\2&-1\\end{pmatrix}$ with $F_D=-1$: every principal minor of $F_N$ is non-positive, so the proof's premise is satisfied, yet $F_N$ has a positive eigenvalue and $-F_N$ is not positive semidefinite; a feasible $V_-$ SOS certificate would therefore certify NNCC where it does not hold.","supporting_citations":[{"cited_title":"On the regularity of solutions of optimal transportation problems","cited_arxiv_id":null,"evidence_quote":"establishes (for smooth costs) the necessity of the MTW condition via connected $c$-subdifferentials and connects it to reflector-antenna costs."},{"cited_title":"Positive polynomials on compact semi-algebraic sets","cited_arxiv_id":null,"evidence_quote":"provides the Positivstellensatz representation of strictly positive polynomials on Archimedean semialgebraic sets used in the certificates."},{"cited_title":"The K \\\"a hler geometry of certain optimal transport problems","cited_arxiv_id":null,"evidence_quote":"gives the log-partition cost example and the analytic MTW(0) result that the SOS certificate in Example 2 reproduces."},{"cited_title":"Sublevel set approximation in the H ausdorff and volume metric with application to path planning and obstacle avoidance","cited_arxiv_id":null,"evidence_quote":"is the source of the sublevel-set volume-minimization heuristic that the inverse problem's objective is modeled on."}],"review_version":1}