# Constructing a metric over a lattice

Consider a lattice $({\cal L}, \wedge, \vee)$ with an antimonotonic function $f: {\cal L} \rightarrow {\mathbb R}$ defined on it (i.e $x \preceq y \implies f(x) \ge f(y)$).

$f$ is said to be submodular if for all $x,y \in {\cal L}$, $$f(x) + f(y) \ge f(x \wedge y) + f(x \vee y)$$ and supermodular if the inequality is flipped (again for all $x,y$).

It's generally known (there's an easy proof), that a submodular $f$ induces a metric on ${\cal L}$ via the defn $$d_s(x,y) = 2f(x \wedge y) - f(x) - f(y)$$. If $f$ is supermodular, then the construction $$d^s(x,y) = f(x) + f(y) - 2f(x \vee y)$$ yields a metric.

Question I'm dealing with an $f$ that is nether sub- nor supermodular. I can define the "distance" $$d(x,y) = \min ( d^s(x,y), d_s(x,y))$$

Conjecture: $d(x,y)$ is a metric.

I have very little sound mathematical intuition for why this conjecture should be true, and bucketloads of empirical evidence (from a lattice I'm actually working with). This seems like the kind of thing that if true, would be reasonably well known to experts, and if false, might have a clear counterexample. So this is a plea for help.

Since it might make a difference, I should mention that the lattice I'm working with is nondistributive in general, but it has distributive sublattices where I'm still unable to prove the conjecture.

-
Suresh, it will be very helpful if you explain in your question what your notations $L,\wedge,\vee$ mean. L stands for lattice, but what are $\wedge$ and $\vee$? I guess $x \wedge y$ does not mean wedge product of x and y ? – Dmitri –  Dmitri Feb 21 '10 at 11:04
In a lattice $x \vee y$ denotes the greatest lower bound of $\{x,y\}$ and $x \wedge y$ the least upper bound. –  Gerald Edgar Feb 21 '10 at 11:31
Ok, I think I got, it, here by lattice we mean this: en.wikipedia.org/wiki/Partially_ordered_set , but not this: en.wikipedia.org/wiki/Lattice_(group) I was not awear of the first definition of Lattice, wiki is helpful here en.wikipedia.org/wiki/Lattice_(mathematics) –  Dmitri Feb 21 '10 at 12:47
By the way, I seem to have reversed $\wedge, \vee$ in my comment. –  Gerald Edgar Feb 21 '10 at 13:28
@Dmitri: Look at the tag "lattice" ... it is interesting that there are posts on both types of lattice that use the label. –  Gerald Edgar Feb 21 '10 at 17:45
show 1 more comment

First failed attempt (this poset is not a lattice)

triangle inequality fails for the three .5 nodes in the middle

Second attempt Our lattice consists of sets, with intersection and union. I show them by Venn diagrams here... The same three middle sets fail the triangle inequality for the same reasons as before. But now it is surely a lattice, right?

-
So I originally had a comment saying that this was a good example (and I also accepted the answer), but now I'm not so sure. In your example, let's label the three .5 elements A, B, C from left to right. Consider the "middle" .5 element B, and the .4 element "above" it in the drawing. These two elements have two meets in the lattice (the .9 and the .6). That violates the unique meet (and join) property of a lattice. I'm not certain there's an easy way to fix this. –  Suresh Venkat Feb 21 '10 at 17:37
Edited to add a second attempt. –  Gerald Edgar Feb 21 '10 at 18:53
I think this example works, but I'm going to let it stew in my head for a few hours before I accept it :). Thanks ! –  Suresh Venkat Feb 21 '10 at 20:23
Don't you need some strict inequality somewhere in your definitions? For example, a constant function meets your definitions of antimonotonic, submodular, and supermodular, but does not induce a metric (assuming your lattice has more than one element) since $d^s$ and $d_s$ would then always evaluate to zero.
For this I think "antimonotonic" should be: $x < y \Longrightarrow f(x) > f(y)$. –  Gerald Edgar Feb 22 '10 at 13:02
Probably to define a distance starting with a general antimonotonic $f$ we should do this: if $a\lt b$ then $d(a,b) = d(b,a) = f(a)-f(b)$, and for general $a,b$ let $d(a,b)$ be $$\inf \sum_{n=1}^n d(x_i,x_{i-1}),$$ where the infimum is over all sequences $a=x_0, x_1, \dots, x_n=b$ such that adjacent terms are comparable (call such sequences paths from $a$ to $b$). In your original proposal we used only two-step paths from $a$ to $b$, but to get the triangle inequality we need to allow longer paths as well. Presumably submodular implies that a certain two-step path is shortest, and supermodular that a different two-step path is shortest. Plus, this will apply to a poset that is not a lattice.