{"id":"32f5427d-625d-4077-be80-831c59b1ef16","arxiv_id":"2411.13218","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For semi-algebraic sets in R^n, the coarsest adapted cylindrical algebraic decomposition always exists in dimensions 1 and 2, but fails to exist for some sets in dimension 3 and higher.","lead":"The paper studies when a mathematical description of a region of space can be simplified to its absolute minimum, by examining cylindrical algebraic decompositions, a standard tool in computer algebra. It proves that in one and two dimensions the simplest description always exists, but in three or more dimensions it sometimes does not, and gives a way to detect this with a reduction system.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: Theorem 4.1's gluing is justified; only minor presentational gaps remain.","rationale":"After checking the proof of Theorem 4.1 cell by cell, the non-emptiness and equality-of-restrictions requirements identified by the reader are met. Because C'_{2j-1} is open and contains xi_{2i}, it contains a neighbourhood of xi_{2i}; therefore its intersections with the left sector, the section point, and the right sector are nonempty. Corollary 3.5 applies to each of these three intersections and yields identical section counts and coincident section functions on the shared parts. This is exactly what makes the piecewise glued functions continuous and what makes each merged triple cell meet the corresponding cell of C', so the adaptedness of the merged CAD follows. The only real defect in the printed proof is the range in the display of eC_2, which fails to include the top-sector union; if that were taken literally the construction would not be a partition, but the proof's own sentence 'for all l in {1,...,2u'+1}' indicates the intended range. I also note Example 4.8 omits the construction for B and the U example's replacement of -x/2 by -x/y is sketched, but neither is needed for Proposition 4.4 and Corollary 4.6, since the trousers already provide counterexamples in every dimension n>=3. Hence I do not see a load-bearing correctness concern; the reader's conditional verdict can stand, though the archival version should fix the typo and supply the missing Example 4.8 details.","tokens_in":14639,"tokens_out":28069,"duration_ms":288609,"concrete_test":"Independently re-derive the construction in Theorem 4.1, writing eC_2 with merged unions for all l=1,...,2u'_{2j-1}+1, and check that the resulting eC is a CAD adapted to S and strictly coarser than C; this settles whether the flagged gluing (with the top-sector range corrected) actually goes through.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I find no load-bearing flaw in the central claims. The reader's weakest point, the gluing argument in Theorem 4.1, is justified: C'_{2j-1} is an open interval containing ξ_{2i}, so each of C_{2i-1}, C_{2i}, C_{2i+1} meets it in a nonempty set; Corollary 3.5 then gives equal section counts and equal section restrictions on those overlapping pieces. Consequently, for every level-l cell, the three cells C_{2i-1:l}, C_{2i:l}, C_{2i+1:l} meet C'_{2j-1:l}, which forces all four to lie on the same side of S. The glued functions are continuous because in the ambient cell C'_{2j-1} they coincide with the continuous sections of C'. The displayed definition of eC_2 in the proof of Theorem 4.1 lists merged unions only for l=1,...,2u' and omits the top-sector union l=2u'+1; taken literally this is not a partition, but the surrounding text shows the intended full range, so it is a typo rather than a correctness gap. Likewise, Example 4.8's set B is asserted without proof, but the n>=3 counterexample already rests on the trousers T, whose minimality is supported by the reduction analysis in Example 5.11. These are presentation issues, not a threat to the central theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the poset CAD(S) of cylindrical algebraic decompositions adapted to a semi-algebraic set S, ordered by refinement. It proves that every adapted CAD can be reduced to a minimal one (Proposition 3.1), that uniqueness of minimal elements is equivalent to existence of a minimum (Proposition 3.3), and that in a minimal CAD the last-level section functions over each base cell are exactly the boundary of the corresponding slice S_x (Proposition 3.4). The main structural result is Theorem 4.1: for n=1 and n=2 every semi-algebraic S admits a minimum adapted CAD, while for n≥3 there exist explicit semi-algebraic sets, such as the 'trousers' T and its higher-dimensional versions, whose poset has no minimum (Proposition 4.4 and Corollary 4.6). Section 5 introduces CAD-tree reductions, gives an algorithm for computing minimal CADs, and proves that CAD(S) has a minimum if and only if its reduction system is confluent (Theorem 5.15).","tokens_in":14912,"tokens_out":14720,"duration_ms":145554,"significance":"If correct, these are clean structural results about a natural combinatorial object attached to any semi-algebraic set. The dimension threshold 1,2 versus ≥3 is surprising and well illustrated by the explicit trousers example. The paper is purely deductive: it uses no fitted parameters, no data, and no reliance on the authors' prior results; the proofs rest on standard facts such as Collins' theorem and Newman's lemma, together with the authors' explicit constructions. The confluence characterization in Theorem 5.15 connects CADs to abstract reduction systems in an elegant way and gives a useful conceptual counterpart to the Gröbner-basis theory of confluence. The reduction-based algorithm also provides a plausible post-processing framework. I specifically checked the delicate gluing step in the proof of Theorem 4.1: Corollary 3.5, together with the fact that ξ_{2i} is an interior point of the sector C'_{2j-1}, supplies the needed equality of section counts and restrictions, so the uniqueness argument is valid.","major_comments":[],"minor_comments":[{"comment":"The defining display of e𝒞₂ lists merged unions only for l=1,...,2u'_{2j-1} and thereby omits the top-sector union corresponding to l=2u'_{2j-1}+1; taken literally, e𝒞₂ is not a partition. The surrounding text and the argument clearly intend the full range, so this is a typographical error, but it should be corrected.","section":"§4, proof of Theorem 4.1"},{"comment":"In the definition of T_n, the second line of the union is written as a subset of R^3; it should be a subset of R^n. This is a typo but could confuse readers.","section":"Corollary 4.6"},{"comment":"The claim that neither B nor U admits a minimum CAD is asserted without proof: for B the construction is explicitly omitted, and for U the authors only say that the trousers construction applies after replacing -x/2 by -x/y. Since the main n≥3 counterexample is already fully established by Proposition 4.4 and Corollary 4.6, this omission does not threaten the central claim, but the statements should be proved or the example should be removed.","section":"Example 4.8"},{"comment":"The sentence 'Similar considerations show that Ψ₃₂ does not lift to a CAD reduction for 𝒞′' is very terse. The argument for the first reduction rule is spelled out; the second case should be expanded so that the minimality proof for the second trousers CAD is self-contained.","section":"Example 5.11"},{"comment":"The notation 'the function x ↦ -x/2 χ(x,y)' is formally incorrect, since the domain of the section is a cell in R^2 and the variable is (x,y); it should read (x,y) ↦ -x/2 χ(x,y). The same issue appears in Example 4.8.","section":"Proof of Proposition 4.4"},{"comment":"The final sentence says 'We finally show by induction that 𝒟ₖ ⪯ 𝒞ₖ for k∈{p,...,n}', but the induction is not written out. A few sentences explaining the inductive step would make the proof complete.","section":"Proof of Theorem 5.9"}],"recommendation":"minor_revision","confidential_remarks":"This is a sound and well-scoped theoretical contribution. The auxiliary claims in Example 4.8 are not needed for the main dichotomy, so if space is tight the authors could safely drop them; otherwise they should provide proofs. None of the issues identified affects the central theorems, and I would be happy to see the paper accepted after the local revisions described above."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper settles a natural open problem in CAD theory: for every semi-algebraic set in R^1 or R^2, the poset of adapted CADs has a minimum (a coarsest one), while in R^3 and above there are sets with no minimum. The trousers example is explicit and convincing, and the reduction-system characterization of when a minimum exists is a nice unifying touch. This is genuinely new: the existence questions were left open in Locatelli's and Wilson's theses, and the proofs do not reduce to earlier results.\n\nWhat I liked: Proposition 3.4 (last-level sections of a minimal CAD are exactly the boundary of S) is clean and useful. The gluing argument in Theorem 4.1, which the reader flagged as delicate, is actually justified: Corollary 3.5 gives equal section counts and equal restrictions on the overlapping open cells, and continuity of the glued functions follows because they match a continuous function on a neighbourhood of each point. The confluence characterization in Theorem 5.15 is a nice analogy to Gröbner bases and is proven correctly via Newman's lemma. The reduction-based algorithm is a sensible post-processing tool and the tree formalism makes the minimality check in the trousers example much less painful than brute force.\n\nSoft spots are minor and presentational. Example 4.8 asserts that the set B has no minimum adapted CAD but omits the construction, saying only that it follows the same lines with suitable adaptations. For a paper whose main point is the dimension-3 counterexample, this is a bit unsatisfying, though the trousers alone already carry the weight. The definition of eC_2 in Theorem 4.1 displays only the merged unions for l=1,...,2u' and omits the top sector l=2u'+1; the surrounding text makes the intended range clear, so it is a typo, not a gap. The proof of Proposition 4.4 says \"careful inspection\" and defers minimality to Section 5, which is fine for an ISSAC paper but means the reader has to wait for the payoff.\n\nOverall, the mathematics looks correct. There is no fitting, no data, no circularity, and the citation pattern is honest. This paper is for CAD researchers and algorithm designers; the cell-count lower bounds are directly relevant to benchmarking. It deserves a serious referee and publication with minor revisions; I would carefully check the omitted set B example during review.","headline":"Solid structural results on minimal CADs: minima in dimensions 1 and 2, a sharp counterexample in dimension 3, and a confluence characterization; minor presentation gaps only.","tokens_in":15437,"tokens_out":1187,"would_cite":true,"duration_ms":15012,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["14P10","68W30"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every semi-algebraic set in the plane has a unique coarsest adapted cylindrical algebraic decomposition, while in dimensions three and above some sets do not.","keywords":["cylindrical algebraic decomposition","semi-algebraic set","minimal CAD","minimum element","refinement order","abstract reduction system","confluence","real algebraic geometry"],"falsifier":"Find two distinct minimal adapted CADs for a single semi-algebraic set in the plane, or show for the three-dimensional 'trousers' set that there exists an adapted CAD coarser than both of the two minimal CADs described in the paper; either observation would refute the corresponding theorem.","tokens_in":14448,"feed_emoji":"📐","tokens_out":6135,"duration_ms":53265,"temperature":0.7,"pith_summary":"The paper asks when a cylindrical algebraic decomposition (CAD) adapted to a semi-algebraic set can be simplified to a canonical coarsest one. It proves that every semi-algebraic set in $\\mathbb{R}$ or $\\mathbb{R}^2$ has a minimum adapted CAD, meaning all adapted decompositions share a single coarsest common refinement. In dimension three and above this fails: the authors exhibit explicit semi-algebraic sets, such as the 'trousers', with several distinct minimal adapted CADs and hence no minimum. They also show that the existence of a minimum is equivalent to confluence of a reduction system that merges redundant cells, and they use that system to give an algorithm that simplifies any adapted CAD to a minimal one.","feed_headline":"Planar semi-algebraic sets have one coarsest CAD","feed_subtitle":"From dimension three, some sets split into several equally simple decompositions with no unique minimum.","key_machinery":"The engine of the analysis is the poset $\\mathrm{CAD}(S)$ of adapted CADs under the refinement order, together with a tree representation of a CAD whose leaves are labelled by whether the cell lies in $S$ or in its complement. A reduction rule merges a section with its two neighbouring sectors when the three cells are all inside $S$ or all inside the complement, and when such a rule lifts geometrically it yields a coarser adapted CAD. The key structural tool is Corollary 3.5, which forces the section functions of two minimal CADs to agree on overlapping base cells, making gluing possible in dimensions one and two. Confluence of the resulting rewriting system is then shown to be equivalent to the existence of a minimum CAD.","core_discovery":"The central discovery is a sharp dimension cut-off for canonical CAD simplification. For every semi-algebraic set $S$ in $\\mathbb{R}$ and $\\mathbb{R}^2$, any two minimal CADs adapted to $S$ must coincide (Theorem 4.1), so their common refinement is a minimum; the proof glues sections above adjacent base cells using the fact that section functions agree on overlaps (Corollary 3.5). For $n \\geq 3$, the set $T = \\{(x,y,z)\\in\\mathbb{R}^3 : (x\\leq 0 \\lor y\\leq 0) \\land z=0\\} \\cup \\{(x,y,z)\\in\\mathbb{R}^3 : x>0,\\ y>0,\\ z=-x/2\\}$ has two distinct minimal adapted CADs and therefore no minimum (Proposition 4.4), with a direct extension to all higher dimensions (Corollary 4.6). The paper concludes with Theorem 5.15: the poset of adapted CADs for $S$ has a minimum if and only if the associated reduction system is confluent.","pith_inferences":["A practical implication the authors leave implicit is that for high-dimensional problems 'the' simplified CAD cannot be defined canonically, so CAD post-processing pipelines must either accept arbitrary minimal outputs or use additional user-chosen criteria to select among them.","The trousers construction suggests that failure of a minimum arises when a cell is a section in one CAD and part of a sector in another, forcing the glued function to become discontinuous; this may be a general mechanism for non-uniqueness.","One could test whether the confluence criterion is decidable for sets given by polynomial data, since the reduction system is terminating and admits only finitely many reduction rules at each stage.","The result mirrors the role of confluence in Gröbner basis theory, raising the question of whether a completion procedure could be developed for adapted CADs."],"forward_implications":["In dimensions 1 and 2, any CAD algorithm's output can be post-processed to a unique coarsest adapted CAD, independent of the algorithm's choices.","In dimension 3 and higher, no canonical simplification exists for some semi-algebraic sets, so any choice of minimal CAD is arbitrary without extra criteria.","Minimal adapted CADs provide tight lower bounds on the number of cells needed to represent a given set, which can serve as benchmarks for CAD algorithms.","The reduction system yields an algorithmic route to a minimal CAD by repeatedly applying liftable reduction rules, avoiding exhaustive search over all coarser partitions.","The confluence criterion connects the existence of a minimum to a terminating rewriting system, placing the problem in the standard framework of abstract reduction systems."],"supporting_citations":[{"why":"Collins' theorem guarantees that a CAD adapted to a semi-algebraic set exists; it is the foundational existence result on which the whole framework rests.","marker":"[9]"},{"why":"Baader and Nipkow supply the abstract reduction system terminology and Newman's lemma, which the paper uses to equate local and global confluence in Lemma 5.14.","marker":"[2]"},{"why":"Brown introduces the refinement/simplicity order on CADs and algorithms for simple CAD construction, the notion that the paper extends and analyses.","marker":"[6]"},{"why":"Locatelli's thesis is cited as prior work that raised the question of minimal or regular adapted CADs in this same framework.","marker":"[13]"},{"why":"Wilson's thesis is cited as another prior occurrence of the problem of simplifying CADs, motivating the study of minimal and minimum elements.","marker":"[16]"},{"why":"Basu, Pollack, and Roy provide the standard definition and basic properties of cylindrical algebraic decompositions used throughout the paper.","marker":"[3]"}],"fun_headline_variants":["A single coarsest CAD exists for planar sets only","CAD simplification hits a wall in dimension three","Unique minimal cell decompositions only up to 2D","From 3D up, some sets resist canonical CAD","Confluence decides when a unique minimal CAD exists"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that planar minimal decompositions coincide assumes that the cutting points and cutting curves of two minimal decompositions match wherever their regions overlap, and that the three neighbouring pieces around a cutting point always meet the corresponding region of the other decomposition; if that matching or those overlaps fail, the coarser decomposition used to force uniqueness cannot be built.","fun_headline_variants_meta":{"raw":{"variants":["A single coarsest CAD exists for planar sets only","CAD simplification hits a wall in dimension three","Unique minimal cell decompositions only up to 2D","From 3D up, some sets resist canonical CAD","Confluence decides when a unique minimal CAD exists"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000192,"raw_usage":{"total_tokens":1403,"prompt_tokens":1059,"completion_tokens":344,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":675,"completion_tokens_details":{"reasoning_tokens":268}},"tokens_in":675,"tokens_out":344,"duration_ms":3716,"temperature":1.0,"reasoning_tokens":268,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:42:16.279726+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find two distinct minimal adapted CADs for a single semi-algebraic set in the plane, or show for the three-dimensional 'trousers' set that there exists an adapted CAD coarser than both of the two minimal CADs described in the paper; either observation would refute the corresponding theorem.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Brown introduces the refinement/simplicity order on CADs and algorithms for simple CAD construction, the notion that the paper extends and analyses."},{"cited_title":"Locatelli","cited_arxiv_id":null,"evidence_quote":"Locatelli's thesis is cited as prior work that raised the question of minimal or regular adapted CADs in this same framework."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Wilson's thesis is cited as another prior occurrence of the problem of simplifying CADs, motivating the study of minimal and minimum elements."}],"review_version":1}