<p>I think this is open. Note that if instead of testing equivalence under rotations you ask for equivalence under the general linear group, then already testing equivalence of degree <em>three</em> polynomials is GI-hard (<a href="https://doi.org/10.1007/11672142_8" rel="noreferrer">Agrawal-Saxena STACS '06</a>, <a href="https://www.cse.iitk.ac.in/users/nitin/papers/stacs06.pdf" rel="noreferrer">author's freely available version</a>), and in fact is at least as hard as testing isomorphism of algebras. Now, GI-hardness is not evidence that your problem is not in $\mathsf{P}$, as indeed, your whole questions is essentially whether we can put GI into $\mathsf{P}$ by the approach you suggest. However, the fact that cubic form equivalence already seems significantly harder than GI (e.g. we still do not know if algebra isomorphism is in quasi-poly time, unlike GI) suggests that (a) people have thought of this approach and (b) it is still open.</p>

<p>While I don't know for sure if similar results hold for the orthogonal group, I would be surprised if they didn't hold (esp. if you move from degree 3 to degree 6).</p>

CC BY-SA 3.0
2018-02-23T20:54:47.733Z
Thank you, I see I have a lot to read. Does testing differing by rotation of polynomials also became tough for degree three? The number of coefficients is O(dim^degree), rotation has dim(dim-1)/2 coefficients, so complete description modulo rotation should be given by O(dim^degree) independent rotation invariants. I know how to construct rotation invariants ( https://arxiv.org/pdf/1801.01058 ), the independence condition seems tough to prove, but high dependence seem unlikely (?)
Jarek Duda
CC BY-SA 3.0
2018-02-24T02:30:51.873Z
@JarekDuda: The same argument you make in your comment would apply to general linear equivalence, except instead of $\binom{dim}{2}$ coefficients you'd have $dim^2$, but those are both $\Theta(dim^2)$... Dependence between invariants is often a very deep question. Also, it's not just a question of how many independent invariants you need, but (a) can you compute which invariants you need in poly-time, and (b) can you even compute the value of each such invariant in poly-time?
Joshua Grochow
CC BY-SA 3.0
2018-02-24T05:54:20.827Z
Sure, if only being able to construct large number of invariants - while I don't know if it is true for other equivalence types(?), for rotation invariants there is construction where every graph gives one invariant, and there are systematic constructions of large numbers e.g. in analogy to length k cycle graphs for Tr(A^k) invariant for degree 2 polynomial x^T Ax. For fixed degree polynomial, we can produce sufficient number (or much more) of invariants in poly-time - the remaining problem is to ensure sufficient number of independent ones among them.
Jarek Duda
CC BY-SA 3.0
2018-02-23T19:35:30.730Z
2018-02-23T19:35:30.730Z
Joshua Grochow
<p>Imagine we have two size $m$ sets of points $X,Y\subset \mathbb{R}^n$. <strong>What is (time) complexity of testing if they differ only by rotation?</strong>: there exists rotation matrix $OO^T=O^TO=I$ such that $X=OY$?</p>

<p>There is an issue of representing real values here - for simplicity assume that there is (a short) algebraic formula for each coordinate, such that cost of basic arithmetic operations can be assumed as O(1). </p>

<p><strong>The basic question is if this problem is in P?</strong></p>

<hr>

<p>While at first view this problem might seem simple - usually it is sufficient to test norms of the points and local relations like angles, <strong>there are nasty examples where it is e.g. equivalent to graph isomorphism problem</strong>.</p>

<p>Specifically, looking at eigenspaces of adjacency matrix of <a href="https://en.wikipedia.org/wiki/Strongly_regular_graph" rel="nofollow noreferrer">strongly regular graphs</a> (SRG), <a href="https://encode.ru/threads/2739-Cryptographic-attacks-as-minimization-of-degree-4-polynomial-(through-3-SAT-problem)?p=55127&amp;viewfull=1#post55127" rel="nofollow noreferrer">we can give it geometrical interpretation</a>. Below is the simplest example - two 16 vertex SRGs, which locally look identical, but are not isomorphic:</p>

<p><a href="https://i.sstatic.net/IDZth.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/IDZth.png" alt="enter image description here"></a></p>

<p>Adjacency matrix of SRGs has always only three eigenvalues (of known formulas) - looking at eigenspace for eigenvalue 2 above (kernel of $A-2I$), it has dimension 6 - of basis written above. Orthonormalizing it (Gram-Schmidt), we get large space of possible orthonormal bases - differing by $O(6)$ rotation, which rotates "vertical vectors": 16 of length 6. Define such set of vectors as $X\subset \mathbb{R}^6$, $|X|=16$ here, and $Y$ correspondingly for the second graph - converting graph isomorphism question into question if $X$ and $Y$ differ only by rotation.</p>

<p>The difficulty is that all these points are in a sphere and recreate original relations: all neighbors (6 here) are in fixed angle &lt;90 degrees, all non-neighbors (9 here) in another fixed angle >90 degrees, like in the schematic picture above. </p>

<p>So testing based on norm and <strong>local</strong> angles takes as back to graph isomorphism problem ... but  geometric interpretation allows to work on <strong>global</strong> properties like rotation invariants.</p>

<hr>

<p>Generally, a natural "global" approach is trying to <strong>describe both sets "modulo rotation"</strong> (which contains $n(n-1)/2$ degrees of freedom), and then just check if both descriptions are identical. </p>

<p>We can usually define <strong>rotation invariants</strong> - the question is constructing a complete set of rotation invaraints: completely determining a set modulo rotation.</p>

<p>While I couldn't find a way for practical rotation invariants directly working on points (?), it can be done for polynomials (<a href="https://math.stackexchange.com/questions/2576766/rotation-invariants-for-higher-degree-homogeneous-polynomials-like-trpm-fo">stack</a>). For degree 2 polynomial $x^T A x$, a complete basis of rotation invariants is e.g. $Tr(A^k)$ for $k=1,\ldots,n$. Diagrammatically they can be represented as length $k$ cycle, and we can analogously construct <a href="https://arxiv.org/pdf/1801.01058" rel="nofollow noreferrer">rotation invariants for higher order polynomials</a> (the remaining question is their independence), e.g. <strong>each graph below corresponds to a single rotation invariant of degree 1,2,3,4 polynomial</strong>:</p>

<p><a href="https://i.sstatic.net/CsxND.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/CsxND.png" alt="enter image description here"></a></p>

<p>The question is how to describe a set of points with a polynomial - generally we need high degree polynomials, e.g. $p(z)=\prod_{x\in X} (x\cdot (z-x))$, but sets for SRGs are quite regular - can be described with just degree 6 polynomial:</p>

<p>$$p(z)=\sum_{x\in X} (x\cdot z -a)^2 (x\cdot z -b)^2 (x\cdot z -c)^2 $$
where $a,b,c$ describe norm and angles in sets obtained for given SRG (are known).</p>

<p><strong>So can we test if two degree 6 polynomials differ only by rotation in polynomial time?</strong> If so, graph isomorphism for SRGs is in P.</p>

<p><strong>Are there tougher examples (for testing if two sets differ only by rotation) than from SRGs?</strong> I doubt it, allowing for quasi-polynomial upper bound thanks to Babai (?)</p>

<hr>

<p><strong>Update</strong>: <a href="https://redd.it/7zffdo" rel="nofollow noreferrer">I was pointed</a> similarity with (solved) <a href="https://en.wikipedia.org/wiki/Orthogonal_Procrustes_problem" rel="nofollow noreferrer">orthogonal Procrustes problem</a>:</p>

<p>$$\min_{O:O^TO=I} \|OA-B\|_F \quad\textrm{achieved for}\quad O=UV^T,\quad\textrm{  where}\quad BA^T=UDV^T$$</p>

<p>from singular value decomposition. We could construct these matrices from our points, however, it would require knowing the order - which we don't know and there are $m!$ possibilities.</p>

<p>We could try e.g. Monte-Carlo or genetic algorithm: switching some points and testing distance improvement using above formula, however, I suspect that such heuristic algorithm might have exponential number of local minima (?)</p>

CC BY-SA 3.0
2018-02-22T21:24:11.097Z
Well, the killer examples for practical graph isomorphism algorithms are not necessarily SRGs. There are two papers by Daniel Neuen and Pascal Schweitzer that [I discussed here](https://chat.stackexchange.com/transcript/56634/2017/8/3), which give the currently toughest examples. My discussion claims that "the multipede construction ... is basically the normal CFI construction applied to an undirected multi-edge hypergraph". This construction is further modified to make it rigid, which removes all the automorphisms. It was no SRG before, but after it will definitely be not an SRG.
Thomas Klimpel
CC BY-SA 3.0
2018-02-22T22:12:52.717Z
I think finding principal components of the point sets and checking them would help since PCA transformation has some pretty nice properties.
FazeL
CC BY-SA 3.0
2018-02-23T07:55:54.040Z
ThomasKlimpel, could you say something about eigenspaces of these other tough examples? @FazeL, eigenvalues of correlation matrix from PCA are examples of rotation invariants - necessary conditions for differing only by rotation (trivial for SRGs). The problem is to get a sufficient condition, e.g. through a complete basis of rotation invariants - completely determining set (or polynomial) modulo rotation. Here is a general construction for polynomials: https://arxiv.org/pdf/1801.01058 , the question is how to choose sufficient number (known) of independent invariants?
Jarek Duda
CC BY-SA 3.0
2018-02-23T09:45:43.900Z
Those graphs are already colored, For fixed $k$, there are colors for which $2^{k-1}$ nodes have that color, and colors for which 2 nodes have that color. In terms of eigenspaces, this means you get many eigenspaces of dimension $2^{k-1}$, and even more eigenspaces of dimension $2$. At least that is what happens if the CFI construction is applied to a k-regular undirected graph. (But don't worry, isomorphism of SRG is an open problem too.)
Thomas Klimpel
CC BY-SA 3.0
2018-02-23T10:06:07.233Z
The eigenspaces of dimension $2^{k-1}$ might actually separate into even smaller eigenspaces, since even for SRG, we have more than 1 eigenspace, but the logic above would suggest that there is just a single eigenspace. Take a look at figure 4.2 in the shorter (more theoretical) paper, so see/understand how those graphs look like.
Thomas Klimpel
CC BY-SA 3.0
2018-02-23T16:17:58.877Z
@ThomasKlimpel, small eigenspaces are simpler to use for GI, e.g. dimension 1 with eigenvector of all different coordinates (e.g. I see in "tough example" of size 25 from https://cstheory.stackexchange.com/questions/5956/ ) emphasize two orders among vertices (ascending/descending) - it is sufficient just to test two permutations to confirm or exclude isomorphism. The difficulty comes with large eigenspaces here, especially if angles just recreate the graph - not bringing any additional information - SRGs provide this worst possible scenario, but seem tamable using degree 6 polynomial  ...
Jarek Duda
CC BY-SA 3.0
2018-02-23T19:40:41.810Z
I assume you're aware of the complete characterization if we only want invariants of the *ordered* list of vectors, rather than the (unordered) set? E.g. Prop F.14 (IIRC) in Fulton-Harris. The invariant ring is generated by the dot products of the vectors, together with the following determinants: if you have $m$ vectors in $\mathbb{R}^n$, then all $\binom{n}{m}$ determinants of $m \times m$ square sub-matrices of the natural $n \times m$ matrix.
Joshua Grochow
CC BY-SA 3.0
2018-02-24T02:28:03.833Z
Wait a minute, I'm also missing something. Even for SRG, what exactly is the reduction you are proposing from SRGI to equivalence of point sets under rotations? One direction is clear (if the graphs are isomorphic, then there is a rotation), but I don't immediately see the other direction...
Joshua Grochow
CC BY-SA 3.0
2018-02-24T05:36:49.893Z
@JoshuaGrochow, once again the construction is: take a degenerated eigenvalue (known formulas for SRGs, lambda = 2 here, can be also used -2 instead), orthonormalize its eigenvectors - getting here size 6 orthonormal basis of eigenspace. There is large freedom of choosing such basis: we could multiply this 6x16 matrix by any O(6), which rotates vertical size 6 vectors: one per original vertex. Take set of such 16 length 6 vectors - neglecting their order, question if two sets differ by rotation is about choosing the same orthonormal basis (page 10 of https://arxiv.org/pdf/1703.04456 ).
Jarek Duda
CC BY-SA 3.0
2018-02-24T06:02:10.673Z
@JarekDuda: Ah, okay. (For the record, I already understood everything in your comment, the key thing I was missing was the equations on p. 10 of your thing, that the dot products between the "vertical" vectors completely determine the adjacency matrix for SRGs.)
Joshua Grochow
<cc.complexity-theory><complexity-classes><graph-isomorphism><computational-geometry><high-dimensional-geometry>
Complexity of testing if two sets of $m$ points in $\mathbb{R}^n$ differ only by rotation?
Jarek Duda
# Complexity of testing if two sets of $m$ points in $\mathbb{R}^n$ differ only by rotation?

(Asked by: username_0 on 2018-02-22)

Imagine we have two size $m$ sets of points $X,Y\subset \mathbb{R}^n$. **What is (time) complexity of testing if they differ only by rotation?**: there exists rotation matrix $OO^T=O^TO=I$ such that $X=OY$?

There is an issue of representing real values here - for simplicity assume that there is (a short) algebraic formula for each coordinate, such that cost of basic arithmetic operations can be assumed as O(1).

**The basic question is if this problem is in P?**

---

While at first view this problem might seem simple - usually it is sufficient to test norms of the points and local relations like angles, **there are nasty examples where it is e.g. equivalent to graph isomorphism problem**.

Specifically, looking at eigenspaces of adjacency matrix of [strongly regular graphs](https://en.wikipedia.org/wiki/Strongly_regular_graph) (SRG), [we can give it geometrical interpretation](https://encode.ru/threads/2739-Cryptographic-attacks-as-minimization-of-degree-4-polynomial-(through-3-SAT-problem)?p=55127&viewfull=1#post55127). Below is the simplest example - two 16 vertex SRGs, which locally look identical, but are not isomorphic:

[![enter image description here](https://i.sstatic.net/IDZth.png)](https://i.sstatic.net/IDZth.png)

Adjacency matrix of SRGs has always only three eigenvalues (of known formulas) - looking at eigenspace for eigenvalue 2 above (kernel of $A-2I$), it has dimension 6 - of basis written above. Orthonormalizing it (Gram-Schmidt), we get large space of possible orthonormal bases - differing by $O(6)$ rotation, which rotates "vertical vectors": 16 of length 6. Define such set of vectors as $X\subset \mathbb{R}^6$, $|X|=16$ here, and $Y$ correspondingly for the second graph - converting graph isomorphism question into question if $X$ and $Y$ differ only by rotation.

The difficulty is that all these points are in a sphere and recreate original relations: all neighbors (6 here) are in fixed angle <90 degrees, all non-neighbors (9 here) in another fixed angle >90 degrees, like in the schematic picture above.

So testing based on norm and **local** angles takes as back to graph isomorphism problem ... but geometric interpretation allows to work on **global** properties like rotation invariants.

---

Generally, a natural "global" approach is trying to **describe both sets "modulo rotation"** (which contains $n(n-1)/2$ degrees of freedom), and then just check if both descriptions are identical.

We can usually define **rotation invariants** - the question is constructing a complete set of rotation invaraints: completely determining a set modulo rotation.

While I couldn't find a way for practical rotation invariants directly working on points (?), it can be done for polynomials ([stack](https://math.stackexchange.com/questions/2576766/rotation-invariants-for-higher-degree-homogeneous-polynomials-like-trpm-fo)). For degree 2 polynomial $x^T A x$, a complete basis of rotation invariants is e.g. $Tr(A^k)$ for $k=1,\ldots,n$. Diagrammatically they can be represented as length $k$ cycle, and we can analogously construct [rotation invariants for higher order polynomials](https://arxiv.org/pdf/1801.01058) (the remaining question is their independence), e.g. **each graph below corresponds to a single rotation invariant of degree 1,2,3,4 polynomial**:

[![enter image description here](https://i.sstatic.net/CsxND.png)](https://i.sstatic.net/CsxND.png)

The question is how to describe a set of points with a polynomial - generally we need high degree polynomials, e.g. $p(z)=\prod\_{x\in X} (x\cdot (z-x))$, but sets for SRGs are quite regular - can be described with just degree 6 polynomial:

$$p(z)=\sum\_{x\in X} (x\cdot z -a)^2 (x\cdot z -b)^2 (x\cdot z -c)^2 $$
where $a,b,c$ describe norm and angles in sets obtained for given SRG (are known).

**So can we test if two degree 6 polynomials differ only by rotation in polynomial time?** If so, graph isomorphism for SRGs is in P.

**Are there tougher examples (for testing if two sets differ only by rotation) than from SRGs?** I doubt it, allowing for quasi-polynomial upper bound thanks to Babai (?)

---

**Update**: [I was pointed](https://redd.it/7zffdo) similarity with (solved) [orthogonal Procrustes problem](https://en.wikipedia.org/wiki/Orthogonal_Procrustes_problem):

$$\min\_{O:O^TO=I} \|OA-B\|\_F \quad\textrm{achieved for}\quad O=UV^T,\quad\textrm{ where}\quad BA^T=UDV^T$$

from singular value decomposition. We could construct these matrices from our points, however, it would require knowing the order - which we don't know and there are $m!$ possibilities.

We could try e.g. Monte-Carlo or genetic algorithm: switching some points and testing distance improvement using above formula, however, I suspect that such heuristic algorithm might have exponential number of local minima (?)

**Tags:** cc.complexity-theory, complexity-classes, graph-isomorphism, computational-geometry, high-dimensional-geometry
> **Comments:**
> **username_1**: Well, the killer examples for practical graph isomorphism algorithms are not necessarily SRGs. There are two papers by Daniel Neuen and Pascal Schweitzer that [I discussed here](https://chat.stackexchange.com/transcript/56634/2017/8/3), which give the currently toughest examples. My discussion claims that "the multipede construction ... is basically the normal CFI construction applied to an undirected multi-edge hypergraph". This construction is further modified to make it rigid, which removes all the automorphisms. It was no SRG before, but after it will definitely be not an SRG.  
> **username_2**: I think finding principal components of the point sets and checking them would help since PCA transformation has some pretty nice properties.  
> **username_0**: ThomasKlimpel, could you say something about eigenspaces of these other tough examples? @FazeL, eigenvalues of correlation matrix from PCA are examples of rotation invariants - necessary conditions for differing only by rotation (trivial for SRGs). The problem is to get a sufficient condition, e.g. through a complete basis of rotation invariants - completely determining set (or polynomial) modulo rotation. Here is a general construction for polynomials: https://arxiv.org/pdf/1801.01058 , the question is how to choose sufficient number (known) of independent invariants?  
> **username_1**: Those graphs are already colored, For fixed $k$, there are colors for which $2^{k-1}$ nodes have that color, and colors for which 2 nodes have that color. In terms of eigenspaces, this means you get many eigenspaces of dimension $2^{k-1}$, and even more eigenspaces of dimension $2$. At least that is what happens if the CFI construction is applied to a k-regular undirected graph. (But don't worry, isomorphism of SRG is an open problem too.)  
> **username_1**: The eigenspaces of dimension $2^{k-1}$ might actually separate into even smaller eigenspaces, since even for SRG, we have more than 1 eigenspace, but the logic above would suggest that there is just a single eigenspace. Take a look at figure 4.2 in the shorter (more theoretical) paper, so see/understand how those graphs look like.  
> **username_0**: @ThomasKlimpel, small eigenspaces are simpler to use for GI, e.g. dimension 1 with eigenvector of all different coordinates (e.g. I see in "tough example" of size 25 from https://cstheory.stackexchange.com/questions/5956/ ) emphasize two orders among vertices (ascending/descending) - it is sufficient just to test two permutations to confirm or exclude isomorphism. The difficulty comes with large eigenspaces here, especially if angles just recreate the graph - not bringing any additional information - SRGs provide this worst possible scenario, but seem tamable using degree 6 polynomial  ...  
> **username_3**: I assume you're aware of the complete characterization if we only want invariants of the *ordered* list of vectors, rather than the (unordered) set? E.g. Prop F.14 (IIRC) in Fulton-Harris. The invariant ring is generated by the dot products of the vectors, together with the following determinants: if you have $m$ vectors in $\mathbb{R}^n$, then all $\binom{n}{m}$ determinants of $m \times m$ square sub-matrices of the natural $n \times m$ matrix.  
> **username_3**: Wait a minute, I'm also missing something. Even for SRG, what exactly is the reduction you are proposing from SRGI to equivalence of point sets under rotations? One direction is clear (if the graphs are isomorphic, then there is a rotation), but I don't immediately see the other direction...  
> **username_0**: @JoshuaGrochow, once again the construction is: take a degenerated eigenvalue (known formulas for SRGs, lambda = 2 here, can be also used -2 instead), orthonormalize its eigenvectors - getting here size 6 orthonormal basis of eigenspace. There is large freedom of choosing such basis: we could multiply this 6x16 matrix by any O(6), which rotates vertical size 6 vectors: one per original vertex. Take set of such 16 length 6 vectors - neglecting their order, question if two sets differ by rotation is about choosing the same orthonormal basis (page 10 of https://arxiv.org/pdf/1703.04456 ).  
> **username_3**: @JarekDuda: Ah, okay. (For the record, I already understood everything in your comment, the key thing I was missing was the equations on p. 10 of your thing, that the dot products between the "vertical" vectors completely determine the adjacency matrix for SRGs.)  

---

## 1 answers

### Answer by username_3 on 2018-02-23. Score: 5

I think this is open. Note that if instead of testing equivalence under rotations you ask for equivalence under the general linear group, then already testing equivalence of degree *three* polynomials is GI-hard ([Agrawal-Saxena STACS '06](https://doi.org/10.1007/11672142_8), [author's freely available version](https://www.cse.iitk.ac.in/users/nitin/papers/stacs06.pdf)), and in fact is at least as hard as testing isomorphism of algebras. Now, GI-hardness is not evidence that your problem is not in $\mathsf{P}$, as indeed, your whole questions is essentially whether we can put GI into $\mathsf{P}$ by the approach you suggest. However, the fact that cubic form equivalence already seems significantly harder than GI (e.g. we still do not know if algebra isomorphism is in quasi-poly time, unlike GI) suggests that (a) people have thought of this approach and (b) it is still open.

While I don't know for sure if similar results hold for the orthogonal group, I would be surprised if they didn't hold (esp. if you move from degree 3 to degree 6).

> **Comments:**
> **username_0**: Thank you, I see I have a lot to read. Does testing differing by rotation of polynomials also became tough for degree three? The number of coefficients is O(dim^degree), rotation has dim(dim-1)/2 coefficients, so complete description modulo rotation should be given by O(dim^degree) independent rotation invariants. I know how to construct rotation invariants ( https://arxiv.org/pdf/1801.01058 ), the independence condition seems tough to prove, but high dependence seem unlikely (?)  
> **username_3**: @JarekDuda: The same argument you make in your comment would apply to general linear equivalence, except instead of $\binom{dim}{2}$ coefficients you'd have $dim^2$, but those are both $\Theta(dim^2)$... Dependence between invariants is often a very deep question. Also, it's not just a question of how many independent invariants you need, but (a) can you compute which invariants you need in poly-time, and (b) can you even compute the value of each such invariant in poly-time?  
> **username_0**: Sure, if only being able to construct large number of invariants - while I don't know if it is true for other equivalence types(?), for rotation invariants there is construction where every graph gives one invariant, and there are systematic constructions of large numbers e.g. in analogy to length k cycle graphs for Tr(A^k) invariant for degree 2 polynomial x^T Ax. For fixed degree polynomial, we can produce sufficient number (or much more) of invariants in poly-time - the remaining problem is to ensure sufficient number of independent ones among them.  

---

