10
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Maybe I'm missing something, but for a fixed $n$ your relation looks like the product of two smooth relations (by Hjorth's comment), which is smooth as witnessed by the product of the two reductions to identity. Varying $n$ is a disjoint union of countably many smooth things, which is again smooth $\endgroup$ Sep 23, 2022 at 11:45
  • 9
    $\begingroup$ @AlessandroCodenotti this is not the product of the relations because the conjugating matrix has to be the same for both matrices. $\endgroup$
    – YCor
    Sep 23, 2022 at 12:07
  • 2
    $\begingroup$ @BenjaminSteinberg Borel complexity subsumes arithmetic complexity and far more---it is Delta^1_1---and so there aren't generally results along the lines you suggest. This is a step up from computability. Practitioners identify the Borel realm with "explicit" mathematics. $\endgroup$ Sep 23, 2022 at 18:18
  • 2
    $\begingroup$ Ah that's a good point, I didn't notice you want the same $g$. So to show nonsmoothness we are looking for a Borel way to associate to every $x\in 2^\Bbb N$ a triple $f(x)=(n,A,B)$ such that $f(x)\sim f(y)\iff$ the two sequences agree on a tail. Maybe there is some clever construction where the length of the segment on which $x,y$ agree determines $n$? $\endgroup$ Sep 23, 2022 at 19:41
  • 1
    $\begingroup$ @AlessandroCodenotti If the equivalence relation in the question is nonsmooth then it must be nonsmooth when restricted to some fixed $n$. So I don't think the role of $n$ should matter much as long as it is large enough. $\endgroup$ Sep 23, 2022 at 21:53

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ For the real action, orbits are also locally closed (they are quantifier-free definable with polynomial inequalities). $\endgroup$
    – YCor
    Sep 23, 2022 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.