Degree Bounds for Separating Polynomial and Neural Invariants for Point Clouds
Abstract
Neural networks that respect the symmetries of point clouds commonly compute high-order representations of the rotation group to improve their expressivity. Such models are known to be universal, and thus able to separate any pair of point clouds, when using representations of sufficiently high order, yet no precise bound on this order, as a function of the number of points, was previously known. We establish the first quadratic lower and upper degree bounds for polynomials that separate point clouds of n points up to rotations and permutations. By showing Tensor Field Networks and MACE can express all invariant polynomials of a given degree with sufficient representation order, we additionally derive the first explicit, quadratic bound on the representation order sufficient for these architectures to be complete, replacing previous existence results with concrete guarantees. We further show that, under local regularity assumptions, point cloud separation can be achieved with a message-passing-based model using invariants whose degree depends only on the size of a local neighborhood, rather than on the size of the full point cloud. Finally, we provide counterexamples showing MACE must compute high order irreducible representations to separate locally regular point clouds.
Related
- Separating components of real algebraic varieties by cohomological invariants
- Non-existence of separating morphisms of low degree
- On elements of degree g in the separating semigroup of a real curve of genus g
- Polynomial Invariants of Pseudo-Anosov Maps (Addendum)
- Welschinger invariants and the Conway polynomial
BibTeX
@misc{hordan2026degree,
title = {{Degree Bounds for Separating Polynomial and Neural Invariants for Point Clouds}},
author = {Snir Hordan and Harm Derksen and Mircea Petrache and Nadav Dym},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26612},
eprint = {2610.26612},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26612},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Degree Bounds for Separating Polynomial and Neural Invariants for Point Clouds
AU - Snir Hordan
AU - Harm Derksen
AU - Mircea Petrache
AU - Nadav Dym
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.26612
UR - https://arxiv.org/abs/2610.26612
AB - Neural networks that respect the symmetries of point clouds commonly compute high-order representations of the rotation group to improve their expressivity. Such models are known to be universal, and thus able to separate any pair of point clouds, when using representations of sufficiently high order, yet no precise bound on this order, as a function of the number of points, was previously known. We establish the first quadratic lower and upper degree bounds for polynomials that separate point clouds of n points up to rotations and permutations. By showing Tensor Field Networks and MACE can express all invariant polynomials of a given degree with sufficient representation order, we additionally derive the first explicit, quadratic bound on the representation order sufficient for these architectures to be complete, replacing previous existence results with concrete guarantees. We further show that, under local regularity assumptions, point cloud separation can be achieved with a message-passing-based model using invariants whose degree depends only on the size of a local neighborhood, rather than on the size of the full point cloud. Finally, we provide counterexamples showing MACE must compute high order irreducible representations to separate locally regular point clouds.
ER -