On the Non-Locality of Solvability and Nilpotency in Cayley Graphs

This paper investigates whether solvability and nilpotency are local properties of Cayley graphs, that is, whether they can be determined from neighborhoods of fixed finite radius. Using the residual p-finiteness of free groups, we construct a sequence of finite nilpotent groups that converges, in the space of marked groups, to the free group on two generators. We then use a large-girth theorem for symmetric groups to obtain a sequence of finite groups that are neither solvable nor nilpotent and that converge to the same limit. Since both sequences converge to the same free group, it follows that for every fixed radius R, sufficiently large groups from the two sequences have identical radius-R neighborhoods around the identity in their Cayley graphs. Consequently, solvability and nilpotency cannot be determined from neighborhoods of any fixed finite radius. In particular, these properties are not local properties of Cayley graphs. As a consequence, any method that relies solely on bounded-radius neighborhood information cannot perfectly determine solvability or nilpotency from Cayley graphs. This yields a fundamental limitation of bounded-depth message-passing Graph Neural Networks (GNNs) for algebraic property prediction.