In a previous blog post, I discussed the recent result of Guth and Katz obtaining a near-optimal bound on the Erdos distance problem. One of the tools used in the proof (building upon the earlier work of Elekes and Sharir) was the observation that the incidence geometry of the Euclidean group of rigid motions of the plane was almost identical to that of lines in the Euclidean space :

Proposition 1One can identify a (Zariski-)dense portion of with , in such a way that for any two points in the plane , the set of rigid motions mapping to forms a line in .

*Proof:* A rigid motion is either a translation or a rotation, with the latter forming a Zariski-dense subset of . Identify a rotation in by an angle with around a point with the element in . (Note that such rotations also form a Zariski-dense subset of .) Elementary trigonometry then reveals that if maps to , then lies on the perpendicular bisector of , and depends in a linear fashion on (for fixed ). The claim follows.

As seen from the proof, this proposition is an easy (though *ad hoc*) application of elementary trigonometry, but it was still puzzling to me why such a simple parameterisation of the incidence structure of was possible. Certainly it was clear from general algebraic geometry considerations that *some* bounded-degree algebraic description was available, but why would the be expressible as lines and not as, say, quadratic or cubic curves?

In this post I would like to record some observations arising from discussions with Jordan Ellenberg, Jozsef Solymosi, and Josh Zahl which give a more conceptual (but less elementary) derivation of the above proposition that avoids the use of *ad hoc* coordinate transformations such as . The starting point is to view the Euclidean plane as the scaling limit of the sphere (a fact which is familiar to all of us through the geometry of the Earth), which makes the Euclidean group a scaling limit of the rotation group . The latter can then be lifted to a double cover, namely the spin group . This group has a natural interpretation as the unit quaternions, which is isometric to the unit sphere . The analogue of the lines in this setting become great circles on this sphere; applying a projective transformation, one can map to (or more precisely to the projective space ), at whichi point the great circles become lines. This gives a proof of Proposition 1.

Details of the correspondence are provided below the fold. One by-product of this analysis, incidentally, is the observation that the Guth-Katz bound for the Erdos distance problem in the plane , immediately extends with almost no modification to the sphere as well (i.e. any points in determine distances), as well as to the hyperbolic plane .

** — 1. Euclidean geometry as the scaling limit of spherical geometry — **

Euclidean geometry and spherical geometry are examples of Kleinian geometries: the geometry of a space with a group of symmetries acting transitively on it. In the case of Euclidean plane geometry, the space is the plane and the symmetry group is the special Euclidean group ; in the case of spherical geometry, the space is the unit sphere and the symmetry group is the special orthogonal group . According to the Kleinian way of thinking (as formalised by the Erlangen program), explicit coordinates on should be avoided if possible, with a preference instead for only using concepts (e.g. congruence, distance, angle) that are invariant with respect to the group of symmetries .

As we all know from the geometry of the Earth (and the Greek root *geometria* literally means “Earth measurement”), the geometry of the sphere resembles the geometry of the plane at scales that are small compared to the radius of the sphere. There are at least two ways to make this intuitive fact more precise. One is to make the radius of the sphere go to infinity, and perform a suitable limit (e.g. a Gromov-Hausdorff limit). A dual approach is to keep the radius of the sphere fixed (e.g. considering only the unit sphere), but making the scale being considered on the sphere shrink to zero. The two approaches are of course equivalent, but we will consider the latter.

Thus, we view as the unit sphere in . With an eye to using the quaternionic number system later on, we will denote the standard basis of as , thus in particular is a point on the sphere which we will view as an “origin” for this sphere. The tangent plane to at this point is then

This plane is tangent to the sphere to second order. In particular, if , and is a small parameter (which we think of as going to zero eventually), then we can find a point on of the form . (If one wishes, one can enforce the error to lie in the direction, in order to make the identification uniquely well-defined, although this is not strictly necessary for the discussion below.) Thus, we can view the -neighbourhood of the origin as being approximately identifiable with a bounded neighbourhood of the origin in the plane via the identification

With this identification, one can see various structures in spherical geometry correspond (up to errors of ) to analogous structures in planar geometry. For instance, a great circle in is of the form

for some , where is the usual dot product. In order for this great circle to intersect the neighbourhood of the origin , one must have , and so we have

for some bounded quantity and some angle . If one then restricts the great circle to points , the constraint then becomes

which is within of the equation of a typical line in ,

This formalises the geometrically intuitive fact that great circles resemble lines at small scales.

Remark 1One can also adopt a more “intrinsic” Riemannian geometry viewpoint to see as the limit of rescaled versions of . Indeed, for each real number , there is a unique (up to isometry) simply connected Riemannian surface of constant scalar curvature . For , this is the unit sphere (rescaled by ); for , this is the Euclidean plane ; and for , it is the hyperbolic plane (rescaled by ). Sending to zero, we thus see the sphere (or hyperbolic plane) converging to the Euclidean plane.

We now apply a similar analysis to a rotation matrix acting on the unit sphere . In order for this rotation matrix to map an neighbourhood of the origin to another such neighbourhood, the rotation matrix must be of the form , where is a rotation that fixes , thus

for some angle , and is an infinitesimal rotation (i.e. an element of the Lie algebra ), thus for some reals . We then have

so in coordinates, becomes the map

which is within of the Euclidean rigid motion

Thus we see the Euclidean rigid motion group emerging as a scaling limit of the orthogonal rotation group (or alternatively, as the normal bundle of the stabiliser of the origin, which is a copy of ).

Remark 2One can also analyse the situation from a Lie algebra perspective. As is well known, one can equip the three-dimensional Lie algebra with a basis obeying the commutation relationscorresponding to infinitesimal rotations around the axes respectively. If we then rescale (which morally corresponds to looking at rotation matrices that almost fix , as above), the commutation relations rescale to

Sending , the Lie algebra degenerates to the solvable Lie algebra

which is the Lie algebra of the Euclidean group .

There is an exact analogue of this phenomenon for the isometry group of the hyperbolic plane (which one can think of as one sheet of the unit sphere in Minkowski space , just as is the unit sphere in ). The Lie algebra here can be equipped with a basis (which one can interpret as infinitesimal rotations and Lorentz boosts in Minkowski space) with the relations

and the same scaling argument as before gives as a scaling limit of .

** — 2. Lifting to the quaternions — **

The quaternions are a number system, defined formally as the set of numbers of the form

with . This a four-dimensional vector space; it can be turned into an algebra (and into a division ring) by enforcing Hamilton’s relations

The quaternions also come equipped with a conjugation operation

and a norm

thus

The conjugation operation is an anti-automorphism, and the norm is multiplicative: . The quaternions also have a trace

(in particular, and ), giving rise to a dot product

which (together with the norm) gives a Hilbert space structure on the quaternions.

The unit sphere of the quaternions forms a group, which is a model for the spin group (thus giving rise to an interpretation of the quaternions , which are of course acted upon by by left-multiplication, as spinors for this group). This group acts on itself isometrically by conjugation, with an element mapping to . As , this action preserves the quaternionic identity , and thus preserves the orthogonal complement of that identity in , which we can of course identify with . Thus acts on isometrically by conjugation, thus providing a map from to . One can verify that this map is surjective (indeed, conjugation by the quaternion corresponds to a rotation around the -axis by , and similarly for rotations around other axes) and is a double cover (since the center of is ), with the pre-image of any rotation in being a pair of diametrically opposed points in . Thus we see that can be identified (in either the topological or Riemannian geometrical senses) with the projective sphere . As acts transitively on , we see that does also.

The stabiliser of a point is easily seen to be a great circle in (being the intersection of with the center of , which is a plane). For instance, the stabiliser of the origin is the circle . (This, incidentally, gives an explicit geometric manifestation of the Hopf fibration.) By transitivity (and the isometric nature of the action), we conclude that the sets are also great circles in for any pair of points . Conversely, as all great circles are isometric to each other, we see that all great circles are of the form . One also sees that two great circles coincide only when have the same stabiliser, and when have the same stabiliser, which forces to either equal , or .

Remark 3Using a projective transformation, one can identify (a hemisphere of) with , with (most) great circles becoming lines in . Thus, we see that the incidence geometry of the in is essentially equivalent to the incidence geometry of lines in . Because of this, the Guth-Katz argument to establish the bound for the number of distances determined by points in the plane , also extends to points in the sphere . Indeed, as in the Guth-Katz paper, it suffices to show that the number of congruent line segments in these points is . For each such pair of line segments, there is a unique element of (and thus two antipodal elements of ) that maps to ; these two antipodal points are also the intersection of with . Applying the projective transformation, one arrives at exactly the same incidence problem between points and lines considered by Guth-Katz (and in particular, one can apply Theorems 2.4, 2.5 from their paper as a black box, after verifying that at most lines of the form project into a plane or regulus, which is proven in the case in much the same way as it is in the case). We omit the details.A similar argument (changing the signatures in various metrics, and in the Clifford algebra underlying the quaternions) also allows one to establish the same results in the hyperbolic plane ; again, we omit the details.

If we restrict attention to an -neighbourhood of the origin in the sphere , and similarly restrict to an -neighbourhood of the stabiliser of in the spin group , we can use the correspondences from the previous section to convert into in the limit, and in the limit into a double cover of the rotation group (which ends up just being isomorphic to again). The great circles in then, in the limit, become the analogous sets in , and the above correspondences can then be used to map (most of) to , and (most) to lines, giving Proposition 1.

## 19 comments

Comments feed for this article

6 March, 2011 at 12:30 pm

Kristal CantwellWhat is the set of points in 7 dimensions that corresponds to rotations in 3 space that send one point to another? Has anyone looked at this before? It looks to me that 7 coordinates are needed. 3 for the center of rotation, 3 for the axis of rotation and one for the magnitude of rotation. If the result in 2 dimensions could be generalized perhaps this set of points would be something relatively simple.

6 March, 2011 at 1:12 pm

Terence TaoActually, the space SE(3) of rigid motions in R^3 is six-dimensional rather than seven (one only needs two coordinates, rather than three, to describe the axis of rotation). As in the above post, one can view SE(3) as a scaling limit of SO(4), which has a double cover of Spin(4), but the topology of these spaces is more complicated (there is no analogue of the quaternions to help out in this case). The set of rotations $l_{A \to B}$ then becomes a double coset of the stabiliser of a single point, which is the three-dimensional space SO(3), which is essentially a 3-sphere (or more precisely, it has a 3-sphere as a double cover, as discussed above).

6 March, 2011 at 1:03 pm

Kristal CantwellI have been looking at this and if the center of rotation is restricted to a plane in space then I think the two dimensional result goes through and the result is a line with some other fixed coordinates maybe this idea can be used to get at the set of points in 7 dimensional space.

6 March, 2011 at 3:17 pm

Willie WongTerry: in the last paragraph you say that the correspondence can be used to map “most of” SE(2) to R^3, can you say a few words about what are the elements that are left out?

6 March, 2011 at 3:27 pm

Terence TaoIt’s the translations which are left out. (One can think of a translation in R^2 as an infinitesimal rotation around an origin on the (projective) line at infinity.)

6 March, 2011 at 4:29 pm

Willie WongActually, I was hoping you could say a few words about upstairs. Each translation corresponds to an unique element in l_{AB}: is there an easy way to see that this element should necessarily be discarded in the construction you gave?

7 March, 2011 at 3:51 am

Willie WongAh, nevermind. I think I see. Originally I was under the mis-impression that the elements of SE(2) corresponds to only elements of l_{AB} that lies in the epsilon-ball around i. But in fact it corresponds to any element of an l_{AB} with the property that l_{AB} has one intersection with S^2 that is O(epsilon) of i. (In other words, I didn’t understand what you meant by “epsilon neighborhood of stabiliser of i”.) So in effect you are blowing up two dimensions (corresponding to S^2) using the rescaling and maping the remaining direction (a S^1) to R using projection. Neat.

6 March, 2011 at 8:22 pm

Fred LunnonThis is all completely obvious in the appropriate Geometric Algebra setting

— for 2-space Euclidean geometry, the spinors of Cl(2,0,1).

Denoting generators by x, y, o, each rotation thru angle t is represented by

an even grade-2 versor of the form

1 + tan(t/2) (a ox + b oy + p yx)

mapping immediately to a point on the line joining the origin (0,0,0) to the

point (a,b,1) in 3-space, setting p = 1. Notice that this mapping sends a

half-turn to the plane at infinity. Translation thru distance tan(t/2) can

also be accommodated, simply by setting p = 0.

For rotation in 3-space, the algebra is Cl(3,0,1), the spinor

1 + tan(t/2) (a ox + b oy + c oz + p yx + q xz + r zy)

mapping to a point on a line thru the origin in 6-space.

Here p yx + q xz + r zy is constrained by p^2 + q^2 + r^2 = 1 ,

representing a unit imaginary quaternion; the entire vector represents a

classical screw. For translation the quaternion part is zero.

An analogous result holds for rotation / translation with coline axis in

Euclidean n-space, mapping (rotor) to point on line in dimension (n+1)n/2.

Once outside 2-space however, a general kinematic isometry is a nontrivial

composition of rotations and translation, requiring a higher-grade spinor

(motor) for its representation.

Another way to look at all this is that it’s about the Lie algebra of the

Euclidean isometry group E(n).

Fred Lunnon

7 March, 2011 at 11:54 am

Fred LunnonA little clarification of my rather terse previous post —

Translations require the normalising constraint

a^2 + b^2 + c^2 … = 1 ;

the distance travelled (correction) is then 2 tan(t/2) in direction

perpendicular to copoint (hyperplane) with Cartesian equation

a X^2 + b Y^2 + c Z^2 + … = 0 .

Generators x, y, z, … represent (reflections in) copoints perpendicular

to Cartesian coordinate axes X, Y, Z, … ; o represents an isotropic

(non-invertible) “black hole” at infinity.

3-space rotations & reflections map to a quadric cone in 6-space, defined by

the Grassmann constraint

a p + b q + c r = 0 ;

3-space kinematic isometries maps bijectively to points in Euclidean

(strictly, projective) 6-space.

When n >= 4, the analogous correspondence between n-space isometry and

(n+1)n/2-space point is also bijective, with the exception of a set of

measure zero comprising isometries whose factorisation into orthogonal

rotations incorporates more than one half-turn.

[In Lie-algebra terminology, their differential vanishes at the identity.]

These includes pure-grade “blades” representing (reflection in) subspaces of

(even) codimension > 2.

There is a brief exposition of the 3-space algebra (DCQ) at

https://docs.google.com/leaf?id=0B6QR93hqu1AhMTFjOWFjMGQtM2YwMy00MGIzLWE4NzAtOGYxZGQ4ZGUwNTU3&hl=en

also accounts by

Jon.~M.~Selig

Geometric Fundamentals of Robotics

Springer (2005)

and by

Charles Gunn

On the Homogeneous Model Of Euclidean Geometry

AGCSE (2011)

https://arxiv.org/abs/1101.4542

Fred Lunnon

10 March, 2011 at 3:35 am

Three Dimensional Algebraic Curves | Gaurav Happy Tiwari[…] Lines in the Euclidean group SE(2) (terrytao.wordpress.com) […]

11 March, 2011 at 12:07 pm

Exceptional isogenies between the classical Lie groups « What’s new[…] A slightly different interpretation of this correspondence, using quaternions, was discussed in this recent blog post. […]

17 March, 2011 at 8:00 am

An incidence theorem in higher dimensions « What’s new[…] this paper we use the polynomial Ham Sandwich method of Guth and Katz (as discussed previously on this blog) to establish higher-dimensional versions of the Szemerédi-Trotter theorem, albeit at the […]

18 March, 2011 at 8:54 am

Tim JonesDear Professor Tao,

In your Remark 3, is it obvious that a log factor is required for the distances problem on the sphere? For example, must the lattice grid example for R^2 carry over to S^2? Or might it be possible to remove the log and obtain N distances?

18 March, 2011 at 3:11 pm

Terence TaoGood question! I don’t see how the grid example in R^2 extends easily to the S^2 case, so in principle one might be able to do better. On the other hand, I cannot think of a technique which would give better results in the S^2 setting than the R^2 case; typically in mathematics, the flat case is easier than the curved case, so the results tend to be stronger in the former. If the sharp lower bound for R^2 is ever established rigorously, this may shed more light on what is going on at S^2.

22 March, 2011 at 10:16 am

The First Xamuel.com Irregular Linkfest[…] Terence Tao: Lines in the Euclidean group SE(2) […]

25 March, 2011 at 2:17 am

Charles GunnA historical note: as far as I can tell, the discovery of this parametrization of SE(2) is due to Eduard Study described in his 1891 paper “Von den bewegungen und umlegungen”, Mathematische Annalen, 39:441–566, 1891. There he develops the theory first for SE(3) (resulting in the so-called dual quaternions, an 8-dimensional algebra, which has found widespread applications in robotics, computer vision, and other applied fields). He then specializes this group to S0(3) (rotations fixing the origin), and carries out a limiting process similar to that described above, to arrive at the euclidean group of the plane. The resulting 4D algebra is sometimes called the planar quaternions (see J. Michael McCarthy. “An Introduction to Theoretical Kinematics”, MIT Press, Cambridge, MA, 1990.) Another thorough treatment of the same can be found in Wilhelm Blaschke, “Ebene Kinematik”, Tuebner, Leibzig, 1938, which includes some very nice geometric motivations of these results. He also (following Study) shows how the planes of the resulting parameter space give rise to a representation of the indirection isometries of the euclidean plane (reflections and glide reflections). Blaschke called this parameter space quasi-elliptic space since it arises from the limit of S3 (as the unit quaternions) in this fashion, when two of the generators become nilpotent (j^2=k^2=0). The points in the “plane at infinity” of the parameter space represent translations; the planes perpendicular to the embedded R2 represent pure reflections.

All this can be perhaps best understood in a modern context via the Clifford algebra which I write as P(Cl(2,0,1))*: that is, the Clifford algebra with degenerate metric (2,0,1), projectivized (so it acts on projective space P2 and not vector space R3). The ‘*’ means that 1-vectors represent lines, not points (dual construction). The even subalgebra of this Clifford algebra (when normalized called the Spin group) is then isomorphic to the planar quaternions described above, just like the even subalgebra of the nondegenerate (“elliptic”) Clifford algebra P(Cl(3,0))* gives the ordinary quaternions. The indirect isometries are also present (in both cases, naturally) via the so-called Pin group, generated by “sandwiches” gxg~ with a 1-vector g (lines).

More about P(Cl(2,0,1))* and similar results for 3D can be found in the above-quoted paper:

Charles Gunn

On the Homogeneous Model Of Euclidean Geometry

AGACSE (2011)

https://arxiv.org/abs/1101.4542

2 April, 2011 at 12:02 pm

iosevichI have a possibly naive question about the Erdos exponent on the sphere. The only way I see to construct an example of points on the sphere that determine only distances is by placing points uniformly around a great circle. What if one assumes that not all points lie on the same circle. Is it reasonable to conjecture that the exponent increases? Less ambitiously, suppose that the set of points is well-distributed. The best example I am aware of yields distinct distances. More generally, I wonder if the sharp Erdos exponent of a manifold depends on the degree to which ${\Bbb Z}^d$ acts transitively on the space in question.

12 May, 2013 at 8:50 am

Distinct Distances: Open Problems and Current Bounds #2 | The Plane Truth[…] number of distinct distances that any set of points on a hypersphere in must always determine. Tao showed that the bound of Guth and Katz remains valid when the point set is on a sphere in (or on a hyperbolic […]

23 June, 2013 at 2:56 pm

Subsets with no repeated distances | Some Plane Truths[…] an extension of Guth and Katz’s distinct distances result to points on a sphere, as derived by Tao. Let be the set of vertices of a regular -gon in . It can be easily verified that the points of […]