Wild classification problems and Borel reducibility

Question

My question is whether the archetype of 'wild' problems in algebra, namely classifying pairs of square matrices up to similarity, is 'non-smooth' in the sense of Borel reducibility.

This was implicitly raised by Joel David Hamkins in his answer to the question When is a classification problem "wild"?, but I'd like to make it explicit here. Let me explain.

Wikipedia rather loosely defines a classification problem in algebra to be wild if it "contains" the problem of classifying pairs of square matrices up to similarity: that is, classifying equivalence classes of pairs $A,B \colon \mathbb{C}^n \to \mathbb{C}^n$ where $(A,B) \sim (A',B')$ iff $A' = gAg^{-1}$ and $B' = gBg^{-1}$ for some invertible $g \colon \mathbb{C}^n \to \mathbb{C}^n$. The looseness lies in the word "contains" and also how to deal with the fact that $n$ is a variable. I hope it's been made precise somewhere but I haven't seen it done.

Meanwhile, there's an extensive theory of Borel reducibility that could serve to make this word "contains" more precise.

Briefly, a standard Borel space is a set $X$ equipped with a sigma-algebra of subsets that are the Borel sets for some separable complete metric on $X$; I'll call these Borel subsets of $X$. A function between standard Borel spaces is Borel if the inverse image of any Borel subset is a Borel subset. A Borel equivalence relation on a standard Borel space is an equivalence relation on $X$ that's a Borel subset of $X \times X$. Getting to the point, we say a Borel equivalence relation $R \subseteq X \times X$ is Borel reducible to a Borel equivalence relation $S \subseteq Y \times Y$ if there's a Borel function $f \colon X \to Y$ such that

$$ x R y \iff f(x) S f(y) $$

Finally, we say a Borel equivalence relation is smooth if it's Borel reducible to the relation of equality on $\mathbb{R}$.

'Tractable' classification problems tend to involve classifying things up to some smooth equivalence relation, while 'intractable' problems tend to be nonsmooth. For a good overview see:

• Greg Hjorth, Borel equivalence relations, Handbook of Set Theory, eds. Matthew Foreman and Akihiro Kanamori, 2009, pp. 297-332.

For a shorter intro see Joel David Hamkins' answer.

So, we may ask if the problem of classifying pairs of square matrices up to similarity is non-smooth. To formalize this, I guess we should form a Borel space of triples $(n,A,B)$ where $n \in \mathbb{N}$ and $A,B \colon \mathbb{C}^n \to \mathbb{C}^n$ are linear maps: there is a straightforward way to do this. Then we can form a Borel equivalence relation where $(n,A,B) \sim (n',A',B')$ iff $n = n'$, $A' = gAg^{-1}$ and $B' = gBg^{-1}$ for some invertible $g \colon \mathbb{C}^n \to \mathbb{C}^n$. Then we can ask if this equivalence relation is non-smooth. That's my question!

As a bit of tantalizing evidence, in Hjorth's article, when he's listing examples of smooth equivalence relations, he writes:

Another example is the equivalence relation of matrices over $\mathbb{C}$ considered up to similarity. As remarked in [29], this equivalence relation is smooth, since we can assign to a matrix its canonical Jordan form as a complete invariant.

However, I don't see him coming out and saying the equivalence relation for pairs of matrices is non-smooth.

Answer 1

Maybe surprisingly, the classification appears to be smooth. I need to combine two results neither of which I understand, which is predictably fraught with danger, but here goes. The following appears as Proposition 2.1.12 in Zimmer's Ergodic Theory and Semisimple Groups:

Proposition 1: Suppose a locally compact second countable (Hausdorff, I assume) group $G$ acts continuously on a separable metrizable space $X$. If every $G$-orbit is locally closed, then the action is smooth (in the Borel sense).

Zimmer uses a different definition of smoothness but since I found this book referenced by a paper of Kechris using your definition of smoothness I will blithely assume that they are equivalent. Now we need a second result I don't understand:

Proposition 2: An algebraic action of an algebraic group on a variety over $\mathbb{C}$ has locally closed orbits (in the Zariski topology, hence in the Euclidean topology).

This is supposed to follow from Chevalley's theorem.

Corollary: For every $n$, the action of $GL_n(\mathbb{C})$ on $M_n(\mathbb{C})^2$ by simultaneous conjugacy is smooth (in the Borel sense).

Interestingly enough the result over $\mathbb{R}$ doesn't immediately follow because Chevalley's theorem doesn't hold. There's an MO question about locally closed orbits for algebraic actions over $\mathbb{R}$ but I don't understand that one either. And of course I may have misunderstood the statements or the hypotheses of one or the other of these results...

(Also, as a comment, you can find a precise definition of wildness in Wild Hypersurfaces by Leuschke, in the context of stating Drozd's trichotomy theorem.)

Edit: It would be interesting to more explicitly write down a Borel invariant which separates orbits here. The only invariants I can see are the following: given a word $w$ in the free monoid the Jordan normal form of $w(A, B)$ is a conjugacy invariant of the pair $(A, B)$. Based on the answers to this old MO question of mine these are likely not to be complete conjugacy invariants, but I can't think of any others, personally.