**The biggest axiom in the world**

In math the rules of a game are called

**axioms**. What's the longest axiom that people have ever thought about?

I'm not sure, but I have a candidate. A

**lattice**is a set with two operations called ∨ and ∧, obeying the 6 equations listed below. But a while back people wondered: can you give an equivalent definition of a lattice using just

*one*equation? It's a pointless puzzle, as far as I can tell, but some people enjoy such challenges.

And in 1970 someone solved it:

*yes, you can!*But the equation they found was incredibly long.

Before I go into details, I should say a bit about lattices. The concept of a lattice is far from pointless - there are lattices all over the place!

For example, suppose you take integers, or real numbers. Let x ∨ y be the

*maximum*of x and y: the bigger one. Let x ∧ y be the

*minimum*of x and y: the smaller one. Then it's easy to check that the 6 axioms listed here hold.

Or, suppose you take statements. Let p ∨ q be the statement "p or q", and let p ∧ q be the statement "p and q". Then the 6 axioms here hold!

For example, consider the axiom p ∧ (p ∨ q) = p. If you say "it's raining, and it's also raining or snowing", that means the same thing as "it's raining" - which is why people don't usually say this.

The two examples I just gave obey other axioms, too. They're both

**distributive**lattices, meaning they obey this rule:

p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r)

and the rule with ∧ and ∨ switched:

p ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ r)

But nondistributive lattices are also important. For example, in quantum logic, "or" and "and" don't obey these distributive laws!

Anyway, back to the main story. In 1970, Ralph McKenzie proved that you can write down a single equation that is equivalent to the 6 lattice axioms. But it was an equation containing 34 variables and roughly 300,000 symbols! It was too long for him to actually bother writing it down. Instead, he proved that you

*could*, if you wanted to.

Later this work was improved. In 1977, Ranganathan Padmanabhan found an equation in 7 variables with 243 symbols that did the job. In 1996 he teamed up with William McCune and found an equation with the same number of variables and only 79 symbols that defined lattices. And so on...

The best result I know is by McCune, Padmanbhan and Robert Veroff. In 2003 they discovered that this equation does the job:

(((y∨x)∧x)∨(((z∧(x∨x))∨(u∧x))∧v))∧(w∨((s∨x)∧(x∨t))) = x

They also found another equation, equally long, that also works.

**Puzzle:**what's the easiest way to get another equation, equally long, that also defines lattices?

That is

*not*the one they found - that would be too easy!

How did they find these equations? They checked about a half a trillion possible axioms using a computer, and ruled out all but 100,000 candidates by showing that certain non-lattices obey those axioms. Then they used a computer program called OTTER to go through the remaining candidates and search for proofs that they are equivalent to the usual axioms of a lattice.

Not all these proof searches ended in success or failure... some took too long. So, there could still exist a single equation, shorter than the ones they found, that defines the concept of lattice.

Here is their paper:

• William McCune, Ranganathan Padmanabhan, Robert Veroff, Yet another single law for lattices, http://arxiv.org/abs/math/0307284.

By the way:

When I said "it's a pointless puzzle, as far as I can tell", that's not supposed to be an insult. I simply mean that I don't see how to connect this puzzle - "is there a single equation that does the job?" - to themes in mathematics that I consider important. It's always possible to learn more and change ones mind about these things.

The puzzle becomes a bit more interesting when you learn that you can't find a single equation that defines

*distributive*lattices: you need 2. And it's even more interesting when you learn that among "varieties of lattices",

*none*can be defined with just a single equation

*except*plain old lattices and the one-element lattices (which are defined by the equation x = y).

By contrast, "varieties of semigroups where every element is idempotent" can always be defined using just a single equation. This was rather shocking to me.

However, I still don't see any point to reducing the number of equations to the bare minimum! In practice, it's better to have a larger number of

*comprehensible*axioms rather than a single complicated one. So, this whole subject feels like a "sport" to me: a game of "can you do it?"

#spnetwork arXiv:math/0307284 #lattice #variety

#bigness

View 36 previous comments

- +Pol Nasam - The lattice of partitions of an n-element set is full of interesting puzzles. In any lattice an
**antichain**is a subset S such that any pair x,y in S is**incomparable**: neither x ≤ y nor y ≤ x. What's the largest number of elements possible for an antichain in the lattice of partitions of an n-element set? This problem, raised by Gian-Carlo Rota, has led to quite a few surprises.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.8959Jun 10, 2015 - +Pol Nasam - maybe you know this, but:

A**lattice**can be alternatively defined as a partially ordered set where every pair of elements has a least upper bound and a greatest lower bound. A lattice is**complete**if*every*subset has a least upper bound and a greatest lower bound. It's easy to see that any finite lattice is complete. The lattice of partitions of a finite set is finite, so it's automatically complete.Jun 10, 2015 - +John Baez Didn't know about that problem. I'll check that later-my phone's browser doesn't render that abstract properly. Meanwhile, you have any
*spoilers*on those surprises you mention?

Wrt. complete, I took the*shortcut*complete=bound & closed, but I don't remember now if that is true here. That was a distracting point, I see now.Jun 10, 2015 - This game might be interpretable in a meaningful way. Suppose that you know how to define something like the homology of a Lawvere theory. Maybe the fact that you have a presentation with one relation could be interpreted as the corresponding homology group of the theory of lattices being of rank at most one. At least Squier has shown similar results concerning presentations of monoids. Just wild guessing here...Jun 10, 2015
- +John Baez I didn't know about those Sperner Posets either. Interestingly enough, any non-negative function Z on the partition lattice \Pi of a set, that satisfies Z(P) + a <= Z(Q) whenever P<Q defines an antichain {P \in \Pi ; d-1/2<Z(P)<d+1/2} for some given d. The paper states a=1, but I maybe that can be relaxed by rescaling Z. I wonder if that can somehow be expressed as a ball of a certain radius in \Pi.

For any partition P, one can define H(P) = - \Sum_i p_i log p_i

where p_i = n_i/N, and n_i is the size of block i of P and N the total number of elements. I'm just guessing here, but, adequately rescaled, -H(P) could satisfy above condition.

The interesting thing is that for any two partitions P, Q,

d(P,Q) = 2 H(P^Q) - H(P) - H(Q)

defines a metric in the partition lattice. The first I've seen mentioning this distance was Zurek in PRA 1989, I think, and the first one I know of applying it to partitions is Maria Meila Proc. 16th Ann. Conf. Computational

Learning Theory (2003), pp. 173–187.Jun 10, 2015 - +Samuel Mimram - that would be incredibly nice. I recently discovered there's a surprisingly large amount of work taking varieties (roughly Lawvere theories with a
*specified set*of generating morphisms) and finding the least number of relations required for a presentation. But I don't know any homological interpretation. Please try to find one!

There's a good introduction here:

• Walter Taylor, Equational logic, http://www.math.uh.edu/~hjm/hjmathsurvey_1979.pdf

A theory where only n relations are needed is called an**n-based theory**.Jun 12, 2015

Add a comment...