Optimal evaluation of symmetry-adapted n-correlations via recursive contraction of sparse symmetric tensors

We present a comprehensive analysis of an algorithm for evaluating high-dimensional polynomials that are invariant (or equi-variant) under permutations and rotations. This task arises in the evaluation linear models as well as equivariant neural network models of many-particle systems. The theoretical bottleneck is the contraction of a high-dimensional symmetric and sparse tensor with a specific sparsity pattern that is directly related to the symmetries imposed on the polynomial. The sparsity of this tensor makes it challenging to construct a highly efficient evaluation scheme. The references [10, 11] introduced a recursive evaluation strategy that relied on a number of heuristics, but performed well in tests. In the present work, we propose an explicit construction of such a recursive evaluation strategy and show that it is in fact optimal in the limit of infinite polynomial degree.