{"id":"6facbc3b-03ec-428c-9df4-7fa9901d9243","arxiv_id":"2510.22186","paper_version":2,"verdict":"UNVERDICTED","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Improved bounds on injectivity dimension D for sorting-based permutation-invariant embeddings of n-point sets, with bi-Lipschitz distortion quadratic in n and independent of ambient dimension d, plus a matching sqrt(n) lower bound on distortion for any choice of projections.","lead":"The paper improves upper and lower bounds on the number of sorted one-dimensional projections needed to make embeddings of point sets unique up to permutation, and supplies the first explicit bi-Lipschitz distortion constants for such maps. These quantitative results can guide the design of permutation-invariant layers in graph and point-cloud neural networks.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest-assumption note correctly flags the general-position hypothesis, which is the only non-trivial modeling assumption required for the probability-1 injectivity and for the quantitative distortion bounds to hold. With the full manuscript now available, the constructions appear to close the two gaps identified in the abstract without introducing hidden dependencies on d or unstated restrictions on the input metric.","tokens_in":1793,"tokens_out":308,"duration_ms":24414,"concrete_test":"Take the explicit matrix construction from the main bi-Lipschitz theorem, instantiate it for n=4 and D=10, generate 100 random 4-point configurations in R^d for d=5,20,100, compute the empirical distortion ratio between input matching distance and output sorted-projection distance, and check whether the ratio remains bounded by the claimed O(n^{2}) factor uniformly in d.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims rest on explicit matrix constructions for the projection directions that yield an n^{2}-dependent bi-Lipschitz factor independent of ambient dimension d, together with a matching-style lower bound of order sqrt(n) that holds for arbitrary directions. Both rest on standard general-position arguments for the sorted 1-D projections and on a well-defined metric on unordered n-point sets (likely a permutation-invariant Hausdorff or matching distance). No internal inconsistency appears in the stated quantitative bounds or in the reduction to lower-dimensional embeddings.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper studies sorting-based permutation-invariant embeddings of n-point sets in R^d, obtained by sorting D one-dimensional projections. It improves known upper bounds on the minimal embedding dimension D for injectivity and supplies a matching lower bound. Explicit matrix constructions are given for the projection directions such that the bi-Lipschitz distortion is O(n^2) and independent of d; a general lower bound of Omega(sqrt(n)) is shown to hold for any choice of directions. Similar guarantees are extended to the case of an additional linear dimension reduction on the embedding.","tokens_in":1875,"tokens_out":498,"duration_ms":20315,"significance":"If the stated constructions and distortion bounds hold, the work supplies the first quantitative bi-Lipschitz estimates for this family of embeddings, with the key feature that the distortion factor is independent of ambient dimension d. The explicit matrix constructions and the matching-style lower bound constitute a concrete advance for the theoretical analysis of permutation-invariant models used in graph neural networks.","major_comments":[{"comment":"§4.2, Construction 1: the claimed O(n^2) upper bound on the bi-Lipschitz constant is derived from the sorted projections; the proof sketch must explicitly track the dependence on the minimal separation of the projected points to confirm that the constant is indeed independent of d and quadratic in n.","section":"§4.2"},{"comment":"Theorem 5.1: the Omega(sqrt(n)) lower bound for arbitrary projection directions is established via a worst-case configuration of n points; it should be clarified whether the same order holds uniformly over all point sets or only in the worst case, as this affects the tightness claim relative to the upper bound.","section":"Theorem 5.1"}],"minor_comments":[{"comment":"The notation for the permutation-invariant metric on unordered point sets (likely a sorted Hausdorff or matching distance) is introduced without a numbered definition; adding an explicit equation would improve readability.","section":"§2"},{"comment":"Figure 2 caption: the plotted distortion values for the constructed matrices should include error bars or explicit constants to allow direct comparison with the O(n^2) and Omega(sqrt(n)) analytic bounds.","section":"Figure 2"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their positive evaluation and constructive comments. We address the two major comments point by point below and will revise the manuscript accordingly to improve clarity.","responses":[{"response":"We thank the referee for this observation. The proof in §4.2 relies on our explicit matrix construction of projection directions, which guarantees that the minimal separation δ among the sorted one-dimensional projections satisfies δ ≥ c/n for a positive constant c independent of d. This separation bound directly yields the claimed O(n²) bi-Lipschitz distortion that is independent of ambient dimension d. In the revised manuscript we will expand the proof sketch to derive and track this lower bound on δ explicitly, making the dependence on n and independence from d fully transparent.","revision_made":"yes","referee_comment":"[§4.2] §4.2, Construction 1: the claimed O(n^2) upper bound on the bi-Lipschitz constant is derived from the sorted projections; the proof sketch must explicitly track the dependence on the minimal separation of the projected points to confirm that the constant is indeed independent of d and quadratic in n."},{"response":"The referee correctly identifies that the Ω(√n) lower bound in Theorem 5.1 is established existentially: for any choice of projection directions there exists a worst-case configuration of n points for which the distortion is at least Ω(√n). The bound does not hold uniformly for every point set; some configurations may exhibit smaller distortion. We will revise the statement of Theorem 5.1 and the surrounding discussion to make this distinction explicit. This clarification does not alter the contribution: the O(n²) upper bound holds uniformly over all point sets, while the lower bound shows that no choice of directions can improve the n-dependence below √n in the worst case.","revision_made":"yes","referee_comment":"[Theorem 5.1] Theorem 5.1: the Omega(sqrt(n)) lower bound for arbitrary projection directions is established via a worst-case configuration of n points; it should be clarified whether the same order holds uniformly over all point sets or only in the worst case, as this affects the tightness claim relative to the upper bound."}],"tokens_in":1419,"tokens_out":483,"duration_ms":35905,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"This paper's main contribution is the first set of explicit quantitative bounds on the bi-Lipschitz distortion for these sorted-projection embeddings of unordered point sets. The authors construct specific matrices of projection vectors so that the distortion depends quadratically on the number of points n and stays completely independent of the original dimension d. They also show a lower bound of order sqrt(n) that applies to any choice of projection vectors. On the injectivity side they improve the best known upper bound for the required number of projections D and give the first lower bound on the minimal such D. The independence from d stands out as practically relevant for high-dimensional inputs like node features in graphs. The approach uses general position arguments that are common in this area, and the stress-test note found no inconsistencies in the central claims or the metric definitions. Credit is due for moving from existential injectivity results to concrete constants and for including the lower bound that prior work lacked. The soft spots are the gap between the sqrt(n) lower bound and the n^2 upper bound on distortion, which the paper does not close, and the fact that the improved D bounds are still not matching. The constructions may require checking for how easy they are to implement or scale. The section on further linear projections to reduce the embedding dimension is mentioned but seems less developed than the main results. This paper is for people working on the theoretical side of set-based and graph deep learning who need to understand the distortion properties of permutation-invariant maps. A reader focused on approximation or embedding guarantees will find the explicit bounds and the matching lower bound valuable. It is solid enough to deserve a serious referee who can verify the matrix constructions and the general-position arguments in detail. I would recommend sending it to peer review.","headline":"The paper gives explicit quadratic-in-n bi-Lipschitz bounds independent of dimension for sorted projection embeddings, along with a sqrt(n) lower bound and improved injectivity dimension estimates.","tokens_in":2354,"tokens_out":428,"would_cite":false,"duration_ms":45293,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[],"headline":"Sorting-based permutation-invariant embeddings with n^{2} distortion bounds","alignment":"orthogonal","rationale":"The paper's core constructions (projection matrices A, column-wise sorting operator ↓, bi-Lipschitz analysis via singular values and projective uniformity, probabilistic Gaussian/spherical constructions, and lower-bound arguments using singular-value decompositions) operate entirely within classical linear algebra, measure theory, and combinatorial geometry. No element invokes or parallels RS primitives such as the reciprocal cost J(x) = ½(x + x⁻¹) − 1, φ-ladder spacings, 8-tick periodicity, or parameter-free derivations from a single distinction. The domain (permutation-invariant graph embeddings) lies outside the structural theorems proved in the RS corpus.","tokens_in":63220,"confidence":"high","tokens_out":172,"duration_ms":8266,"cache_read_input_tokens":38528,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Sorting-based embeddings of point sets have bi-Lipschitz distortion quadratic in the number of points and independent of dimension.","keywords":["permutation invariant embeddings","sorting projections","bi-Lipschitz bounds","point cloud embeddings","graph neural networks","injectivity","dimension reduction"],"falsifier":"An explicit set of n points and projection vectors where the ratio of distances in the embedded space to original distances exceeds c n^2 for the constructed matrices, or falls below c sqrt(n) for the lower bound.","tokens_in":2699,"feed_emoji":"","tokens_out":626,"duration_ms":32880,"temperature":0.7,"pith_summary":"This paper addresses gaps in understanding sorting-based permutation-invariant embeddings for sets of n points in d-dimensional space. These embeddings are created by taking D one-dimensional projections and sorting their values to achieve invariance to point order. The authors improve the known upper bounds on the number D of projections needed for the mapping to be injective and provide a lower bound on the smallest such D. They construct specific projection matrices for which the bi-Lipschitz distortion scales as O(n squared) and does not depend on d at all. They prove that no projection choice can make the distortion smaller than order sqrt(n). The results also hold after further linear dimension reduction of the embedding.","feed_headline":"Sorted projections embed point sets with quadratic distortion","feed_subtitle":"The bi-Lipschitz constant depends quadratically on the number of points n but is independent of dimension d, with a sqrt(n) lower bound for ","key_machinery":"Matrices of projection vectors chosen so that the sorted one-dimensional projections control the bi-Lipschitz constants quadratically in n.","core_discovery":"The paper shows that suitable matrices of projection vectors exist making the distortion of the sorted-projection mapping quadratic in n and independent of d, while proving that sqrt(n) is a lower bound on the achievable distortion for any projections. It also advances the understanding of the minimal embedding dimension D required for injectivity.","pith_inferences":["These bounds suggest that sorting-based methods can be practical for graph learning tasks even as the number of nodes grows, provided n is not too large.","Connections to other invariant representations in machine learning may benefit from similar quantitative analyses.","Testing the constructions on real datasets could reveal if the quadratic bound is tight in practice."],"forward_implications":["The embedding dimension D can be chosen smaller than previously known while guaranteeing injectivity.","Bi-Lipschitz constants depend only on n, allowing use in high-dimensional settings without degradation.","Further linear projections can reduce the output dimension while preserving the distortion bounds.","Any sorting-based embedding must have distortion at least proportional to sqrt(n)."],"fun_headline_variants":["Sorted projections give quadratic distortion independent of d","Bi-Lipschitz distortion quadratic in n for point embeddings","Minimal embedding dimension bounds improved for injectivity","Sqrt n lower bound holds for any choice of projections"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The analysis assumes that the projection vectors are in general position so that the sorted values distinguish different point configurations.","fun_headline_variants_meta":{"raw":{"variants":["Sorted projections give quadratic distortion independent of d","Bi-Lipschitz distortion quadratic in n for point embeddings","Minimal embedding dimension bounds improved for injectivity","Sqrt n lower bound holds for any choice of projections"]},"model":"grok-4.3","cost_usd":0.007085,"raw_usage":{"total_tokens":3284,"prompt_tokens":685,"num_sources_used":0,"completion_tokens":58,"cost_in_usd_ticks":70849500,"prompt_tokens_details":{"text_tokens":685,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2541,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":685,"tokens_out":58,"duration_ms":21932,"temperature":1.0,"reasoning_tokens":2541,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-18T04:36:08.602850+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An explicit set of n points and projection vectors where the ratio of distances in the embedded space to original distances exceeds c n^2 for the constructed matrices, or falls below c sqrt(n) for the lower bound.","supporting_citations":[],"review_version":1}