Sententia cdsmithus

June 15, 2009

Thoughts on an Associative Metric for the Non-Negative Reals

Filed under: math — cdsmith @ 12:00 pm

A recent reddit post posed the question of whether there exists an associative metric on the non-negative reals.  I didn’t see it until after most people moved on, so I’m posting my thoughts on the subject here.  It is likely that none of this is new, but perhaps some people will find it interesting to have it collected in one place.

As a brief review just to collect the relevant definitions in one place… a function d : X^2 \to \mathbb{R}_{\geq 0} is a metric if:

  1. d(x,y) = 0 when x = y, and d(x,y) > 0 when x \neq y.  This is called definiteness.
  2. d(x,y) = d(y,x).  This is called symmetry.
  3. d(x,y) \leq d(x,z) + d(z,y).  This is the triangle inequality.

In particular, if X = \mathbb{R}_{\geq 0}, then d is a binary operation.  One may then ask whether it is associative.  That is, if d(x, d(y,z)) = d(d(x,y),z).  The problem is whether there exists a metric d on the non-negative reals that is in fact associative.

A Key Observation

To get started, let’s just play some games with manipulating the axioms above.  Let’s consider any non-negative real number x, and let k = d(0,x).  That is, k is the distance of x from the origin.  Then something interesting happens.  By the associative property we’ve just discussed, we have:

d(0, d(x,k)) = d(d(0,x), k)

But remember, d(0,x) on the right-hand side of that equation is the same as k, and by the definiteness property of a metric, d(k,k) = 0.  So we really have:

d(0, d(x,k)) = d(k,k) = 0

Now, applying definiteness again in the other direction, we can conclude that 0 = d(x,k), and then applying it yet a third time, that x = k.  In other words, we have:

Proposition 1: Suppose d is an associative metric on the non-negative reals.  Then for all non-negative reals x, d(0,x) = x.

This is not an unusual property of a metric on the reals.  For example, the standard metric d(x,y) = |x-y| has this property for all non-negative numbers.  However, it’s not true of all metric (not the discrete metric, for example.)  Note that so far, we have used only associativity and definiteness.  The really interesting property of metric, though, is the triangle inequality.  So let’s apply that to try to get some bounds on the possible choices of d, by decomposing distances into distances from the origin.  Suppose we choose x and y as arbitrary non-negative reals.  Then we have:

  1. d(0,x) \leq d(0,y) + d(y,x)
  2. d(0,y) \leq d(0,x) + d(x,y)
  3. d(x,y) \leq d(x,0) + d(0,y)

Now, just using symmetry and proposition 1 to simplify those expressions, we get:

Proposition 2: Suppose d is an associative metric on the non-negative reals.  Then for all non-negative reals x and y,|x-y| \leq d(x,y) \leq x + y.

These are not very tight bounds on the possible values of d, really.  But they do tell us something interesting: namely, that a metric that works for us will necessarily have something to do with the magnitudes of the numbers involved.  This was not necessarily a given — one can imagine metrics on many sets of numbers that are entirely unrelated to the magnitudes of the numbers involved.  It turns out that in our case, our willingness to interchange the value of the metric with its inputs via the associative property somehow forces the metric to give significance to the magnitude of the numbers.

Group Structure

The original post to Reddit made the casual observation that it can be shown that if this is true, then \mathbb{R}_{\geq 0} is a group under this operation.  To review another basical definition, a group is any set together with a binary operation (which I’ll call \bullet), which satisfies:

  1. Associativity: that is, x \bullet (y \bullet z) = (x \bullet y) \bullet z.
  2. Identity: that is, there exists e such that for all x, e \bullet x = x \bullet e = x.
  3. Inverses: that is, for any x, there is a x^{-1} such that x \bullet x^{-1} = x^{-1} \bullet x = e.

As a quick change of notation (so that we’re more consistent with the infix notation normally used for groups), we define x \bullet y = d(x,y).  Of course, the associativity of \bullet was something we assumed from the very beginning.  Proposition 1, together with the symmetry property, give us the identity, which is zero.  Definiteness gives us inverses: for any x, we know d(x,x) = 0, so that x is its own inverse.  Therefore, \langle \mathbb{R}_{\geq 0}, \bullet\rangle is a group.

A good bit could be said about the structure of this group.  In fact, that every element is its own inverse gives us very specific information about what this group looks like (it’s built from copies of \mathbb{Z}_2, for example.)  But even just knowing that it’s a group gives us some interesting ways to think about the problem.  The bounds we found in the previous section were actually compatible with the standard metric on the real numbers.  But seen as a group operation, our associative metric starts to develop some interesting properties that are somewhat different from the standard metric.

For example: suppose you give me a non-negative real x, and ask me what other non-negative reals are a distance y away from it.  Because distance is a group operation, there is precisely one answer to this question: if x \bullet z = y, then z = x^{-1} \bullet y (and in this case, since every number is its own inverse, that’s the same as x \bullet y).  In other words the function d_x(y) = d(x,y) is necessarily one-to-one, for any x.

That’s a pretty significant statement!  In fact, it’s fairly simple now to show that for x \neq 0, d_x therefore cannot be a continuous function in the topology induced by the standard metric |x-y|.  We might previously have hoped that perhaps the metric that worked would look something like the standard metric, though perhaps stretched or distorted in some way.  In fact, the earlier proposition gave us extra hope, by limiting the amount by which our metric can differ from the standard metric.  It’s now clear, though, that an associative metric will be quite  different from the standard metric.

(As an aside, it’s worth noting that d_x above is continuous in the topology induced by the metric d.  This is basically equivalent to requiring that for any \epsilon > 0, there exists \delta > 0 such that whenever y \bullet y_0 < \delta, we also have d_x(y) \bullet d_x(y_0) < \epsilon.  But d_x(y) \bullet d_x(y_0) = x \bullet y \bullet x \bullet y_0 = y \bullet y_0, so choosing \delta = \epsilon always works.)

Where Next?

Who knows.  We have two conclusions now that seem rather at odds with each other: first, then an associative metric would need to overestimate the standard metric by a bounded (though, admittedly, very loosely bounded) amount.  Second, we have that in terms of topological properties, our metric differs significantly.  Resolving these tensions — or showing that they can’t be resolved — would perhaps be an important next step in addressing the problem.

Blog at WordPress.com.