Articles

Algorithms via geometry

Configuration spaces and their geometry

For a fixed natural number n and manifold X, the configuration space \mathrm{Conf}^n X is space of all tuples of n distinct points in X, i.e. we may think of it as the open manifold X^n - \Delta, where here $\latex \Delta$ denotes the extended diagonal consisting of all n-tuples where the values of at least two coordinates coincide.

Configuration spaces arise naturally in the consideration of certain problems in physics, and more recently and more concretely in robotics: here, for instance, the manifold X may be taken to be the space our n robots are moving around, and then \mathrm{Conf}^n X represents all the possible combinations (“configurations”) of positions which the robots can occupy at any point in time. A path in $latex \mathrm{Conf}^n X$ then represents a set of possible simultaneous trajectories, and so the study of the configuration space and its properties becomes useful to motion planning.

More broadly, we may consider more general configuration spaces which represent the possible positions, or more general states, of a given robotic (or other) system, and think of paths in these configuration spaces as ways for the system to move from one position / state to another.

Sometimes the configuration spaces can be CAT(0), or even cubulated (i.e., in this context, made homeomorphic or maybe even bi-Lipschitz to a CAT(0) cube complex), and that can be convenient for developing algorithms to solve corresponding problems in robotics.This is the case, for instance, for a model robotic arm operating in a tunnel.

A slightly different application in which non-positively curved configuration spaces have also made an appearance is to phylogenetic trees.

Comparisons in image spaces

Suppose we have a collection of images of comparable two-dimensional surfaces, say neural images of the exterior surface of the human brain, or shapes of various animal bones, and we wish to compare them in some way, or perhaps obtain some “best match” mapping between a given neural image and some standard structural template/s.

This sounds very much like the question asked and addressed by Teichmüller theory: what are the natural maps between two different geometries on the same topological surface? In the case of higher-genus surfaces, the answer that Teichmüller theory gives is “extermal quasiconformal maps”, and more generally, and indeed something which forms an important part of the backdrop for Teichmüller theory in the first place, uniformization tells us that any compact surface is conformally equivalent to a sphere, torus, or hyperbolic surface.

Hence conformal maps and their geometry become natural tools in this sort of shape analysis, and quasiconformal maps (and possibly Teichmüller theory) can come into the picture when either discrete approximations or higher-genus surfaces are involved. Notions of distance between shapes, based on some notion of deformation energy, or on quasiconformal constants, can be useful in making quantitative statements such as “this shape is closer to model shape A than to model shape B.”

Cryptography from geometric group theory

Non-commutative cryptography uses cryptographic primitives, methods and systems based on non-commutative algebraic structure, as opposed to most familiar cryptographic systems, which are based on the commutative algebra underlying number theory.

Many of the protocols are very similar or analogous to those in more familiar (“commutative”) cryptographic systems, the main difference being that the hard (or, in many cases, presumed-to-be-hard based on existing evidence—rigorous cryptanalysis is still in many cases an open problem) problems underlying the security of the proposed primitives and/or systems come from group theory, or the theory of other non-commutative algebraic structures.

For instance, here is a general protocol for encryption / decryption: let G be a group, and let and B be commuting subgroups—i.e. ab = ba for all a \in A, b \in B, or in other words A \subset N_G(B), B \subset N_G(A), and fix x \in G (to be made public.) Alice and Bob choose secret keys a and b from A and publish y = x^a, z = x^b as public keys.

To send an encrypted message m, Alice picks a random r \in B and sends (x^r, H(z^r) \oplus m), where is some hash function and \oplus denotes XOR.

To recover the plaintext, Bob computes z^r = (x^b)^r = x^{br} = (x^r)^b and then m = H(z^r) \oplus m \oplus H(Z^r).

In the commutative setting, where we interpret G as (some finite quotient of) a integer ring and x^r as exponentiation, the security of this protocol would depend on the difficulty of finding discrete logarithms.

In the non-commutative setting, in a somewhat egregious abuse of notation, we interpret x^r as conjugation, and then the security of the protocol would depend on the difficulty of the conjugacy search problem (i.e. given z, t \in G, find r \in G s.t. t = rzr^{-1}.)

The difficulty of the conjugacy search problem in a given group, as well as other desirable properties (from either a security or an implementation standpoint), such as efficiently solvable word problem, computable normal forms, and super-polynomial growth function, is something that is often most (or at least more) easily studied using geometric methods.

Hence some of the groups which have been suggested in the context of this application: braid groups, Grigorchuk’s group, Thompson’s group/s, Artin groups, free groups, etc.

Other (apparently, or provably) difficult problems arising in geometric group theory may also be used, e.g. subgroup isomorphism in RAAGs (although this may potentially be less tenable in light of Babai’s recent breakthrough in graph isomorphism) or subgroup distortion in hyperbolic groups.

Non-commutative cryptography is still in many ways a nascent field; there are few concrete manifestations—the Algebraic Eraser is a rare example of one—and its security is presumed but yet to be fully tested—as demonstrated by the ongoing debate over the security of the Algebraic Eraser. Perhaps partly due to the relative lack of real-world applications, and partly due to the novelty of the field, cryptanalysis and work to establish the security of proposed protocols has been relatively slow in coming, although such work does exist.

Advertisements
Standard
Examples

CAT(0) not a quasi-isometry invariant of groups

It is easy enough to produce examples of pairs of spaces which are quasi-isometric, but only one of which is CAT(0): the CAT(k) inequality applies at every scale, but quasi-isometries do not allow any control over what happens at small scales. For instance, we could quasi-isometrically map Euclidean space into a space with regions of (arbitrarily large) positive curvature concentrated inside bounded balls, in which small triangles will fail to satisfy the CAT(0) condition.

It is a little trickier to produce examples of pairs of groups which are quasi-isometric, but only one of which is CAT(0), since now the CAT(0) condition applies not directly to the group, but refers to (the existence of) a CAT(0) space on which the group acts geometrically and cocompactly (and hence a fortiori by semisimple isometries), and we have, at first blush, great freedom to choose what that space might be, depending on what the group is.

Here are two constructions that work, both of which are pointed out in Remark 1 of this paper of Piggott-Ruane-Walsh (although one of them—the second example below—somewhat badly).

Fundamental groups of graph manifolds

One example follows from the work of Kapovich-Leeb on fundamental groups of graph manifolds. Kapovich-Leeb proved (Theorem 1.1) that whenever M is a Haken (i.e. contains an essential properly embedded surface) Riemmanian 3-manifold with \chi(M) = 0, \pi(M) is quasi-isometric to a fundamental group of a compact non-positively curved 3-manifold; groups of the latter description are always CAT(0).

On the other hand, Leeb showed (Example 4.2) that there exist Haken 3-manifolds with \chi(M) = 0—more specifically, closed graph manifolds with no atoroidal components  (i.e. all of whose geometric components are Seifert-fibred) and empty boundary—which do not admit metrics of nonpositive curvature; decomposing the manifold we see that there exist spherical regions in M, and then it follows that the fundamental groups \pi_1(M) of such manifolds M cannot be CAT(0).

Mapping class groups (and unit tangent bundles)

A different example can be found by messing around with mapping class groups; the following is taken from p. 258 of Bridson and Haefliger’s Metric Spaces of Nonpositive Curvature (the top half of the page, not the bottom half.)

Let K be the central extension 1 \to \langle T_c \rangle \to K \to \pi_1(\Sigma_2) \to 1 defined as the kernel of the natural homomorphisms \mathrm{Mod}(\Sigma_2^b) \to \mathrm{Mod}(\Sigma_2^p) \to \mathrm{Mod}(\Sigma_2), where \Sigma_2 is the closed genus-2 surface, \Sigma_2^b denotes the genus-2 surface with a single boundary component c \cong S^1 (and T_c denotes the Dehn twist about c), and \Sigma_2^p denotes the genus-2 surface with a single puncture.

By an unpublished observation of Geoffrey Mess (looking at the geometry of the mapping classes), K is the fundamental group of the unit tangent bundle S\Sigma_2 of \Sigma_2, and hence a cocompact lattice in \widetilde{\mathrm{PSL}_2\mathbb{R}}, but this last does not contain the fundamental group of any closed hyperbolic surface. But, on the other hand, any finite-index subgroup of \pi_1(\Sigma_2) is, by covering space theory, the fundamental group of a closed hyperbolic surface; and now we may conclude that our central extension cannot be split, even after passing to a finite-index subgroup of \pi_1(\Sigma_2).

Now we have the following general result on isometries of CAT(0) spaces: any group of isometries of a CAT(0) space which contains a central A \cong \mathbb{Z}^n subgroup contains a finite-index subgroup which has A as a direct factor.

Hence we conclude that our K cannot be (isomorphic to) a group of semisimple isometries of any CAT(0) space, i.e. K is not a CAT(0) group.

On the other hand, Epstein, Gersten (and Mess? So claims Misha Kapovich) independently proved that \pi_1(S\Sigma_2) is quasi-isometric to \pi_1(\Sigma_2) \times \mathbb{Z}, which is certainly CAT(0), e.g. being the product of two CAT(0) groups. This—that two of the Thurston model geometries, \widetilde{\mathrm{PSL}_2\mathbb{R}} and \mathbb{H}^2 \times \mathbb{R}, are quasi-isometric to each other—is apparently also a [multiply] unpublished observation—trying to track down a reference was annoyingly tricky. Gromov’s Metric Structures for Riemannian and Non-Riemannian Spaces contains an account.

Standard