How far a lattice is from distributive/Boolean

59 Views Asked by At

Is there a standard quantification of how far a lattice is from being distributive? And Boolean? Or anyway how non-exact the representation is?

In other words, is there an object (or number) which is trivial (or zero) when the lattice has the desired property?

2

There are 2 best solutions below

2
On

If your lattice is a group, the following captures my intuition of how "far" it is from being distributed: $$\sum_{x, y, z} | x\wedge (y\vee z) - (x\wedge y)\vee (y\wedge z) | $$ where $| x | = x\vee x ^ {-1} $. It has the property that the sum is zero if and only if the lattice is distributive.

Sadly, any lattice ordered group is distributive, so this sum will always be 0 where it is defined. You could do something simple like count the set of triplets $x, y, z$ which are not distributive, but given the above problem with l-groups I doubt you can do much more.

Edit: you asked about a "norm" for lattices. I'm not aware of any standard definitions, but based on the little I know about your problem it seems like you might want to know how many "steps" it takes to get from $x$ to $y$ when you view the lattice as a graph. Here's one way to operationalize that.

I'm going to suppose you have some measure $\mu$ on the underlying set of elements from your lattice (this can be as simple as $\mu(S) = | S |$). Define the lower distance between $x$ and $y$ as $$d_l(x, y) =\mu(\{z: x\wedge y < z < x\}) +\mu(\{z: x\wedge y < z < y\})$$ and similarly the upper distance $$d_u (x, y) =\mu(\{z: x\vee y> z > x\}) +\mu(\{z: x\vee y > z > y\})$$ You can then define the distance as $$d(x, y) =\min(d_l, d_u)$$ If your lattice is discrete you could go even further and just specify that the distance between $x$ and $y$ is the shortest path when the lattice is viewed as a graph, possibly with some modifications depending on how you want to count incomparable elements.

For example, in this simple lattice:

enter image description here

  • $d(2, 2) = 0$
  • $d(2, 3) = 2$
  • $d(2, 5) = 1$
0
On

I know this is an old question and you might not be interested in this anymore, and it's also likely that there doesn't exist the ultimate correct answer to this kind of question, but here's another take.

Consider representations of the lattices. Boolean algebras have been represented by Stone spaces (topological representation), and these were generalized to bounded distributive lattices by Priestley (and I think also by Stone, before her; the importance of Priestley's contribution was mostly that she added representation of homomorphisms, but these are probably of no importance here). Later, Urquhart generalized this further to representations of bounded lattices (not necessarily distributive).

We may ignore the topology in all of these cases. In the finite case, the topology is discrete anyway; in the infinite case, if we ignore the topology, we obtain a structure from which we may then construct a lattice into which the original lattice can be embedded (we would use the topology to get an isomorphic lattice).

So here, the representation of a Boolean algebra is the poset (which is an anti-chain) of its ultrafilters. It is an anti-chain because ultrafilters are maximal filters, and as such, one cannot be strictly contained in other.
So ultrafilters are the same thing as maximal filters; another concept which is equivalent in the case of Boolean algebras is the one of prime filters.

Now enter bounded distributive lattices. These are represented by the poset of their prime filters. But these no longer make an anti-chain: there can be prime filters $F$ and $G$ with $F \subset G$ (and this is always the case if the lattice is not Boolean).
So you can quantify how far a distributive lattice is from a Boolean algebra by how far the poset of its prime filters is from an anti-chain. This could be, perhaps, the number of coverings in that poset (it won't work well in the case there are infinitely many; maybe a better measure could be defined).

Now for bounded lattices in general, the representation is a generalization of the previous one but in a way which I think there's no point in describing here.
These lattices are represented by a doubly ordered set $(X,\leq_1,\leq_2)$ (where each $\leq_i$ is a pre-order or quasi-order relation) as I described in this answer.
What is important to know about this (in the context of this post) is that, if the lattice happens to be distributive, the representation by the doubly ordered set above is such that $\leq_i$ is a partial order relation and moreover, $u\leq_1 v$ iff $v\leq_2 u$. So they are the converse of one another, and dropping one, we have the usual representation of a distributive lattice (again, modulo topology).
So you can measure how non-distributive the lattice is by checking how far is the doubly ordered set is from reducing to a poset. And this could perhaps be done by checking for how many pairs $(u,v)$ we have $u\leq_1 v$ but $v\nleq_2 u$ or vice-versa.
Again, if there are infinitely such pairs then maybe an improved way of measuring the difference could be defined.