On Sat, 30 Jul 2016, John Cremona wrote:
Can we keep certify() for functions that return True/False, or possibly
return None if ok and raise an error otherwise (as in an assert statement
); and only use certificate() for functions that return some sort of
certificate? There are primality certificates, for example.
Ouh. Sounds very hard to remember two almost same keyword.
What kind of certificates we have:
- Dimension of poset and breadth of lattice are integers. There are always
certificate that can we attach to those: for dimension it is realizers,
i.e. a set of n linear orders, that actually show that the dimension is at
most n; for breadth it is set of n elements showing that the breadth is at
least n.
- For planarity of grahp we can get "no"-certificate: a Kuratowski minor.
Mathematically there exists also "yes"-certificate, i.e. the drawing on a
plane.
- If a lattice is dismantlable or not, there are both "yes" and "no"
certificates: the dismantling order or a crown subposet.
- If a lattice is relatively complemented or not, there is
"no"-certificate: elements a,b,c so that b is the only element covering
only a and covered by only c. There is no meaningful "yes"-certificate.
- And for example is_prime can have only "yes"-certificate, i.e. two
integers.
- If a finite lattice is not modular, we could have either by-definition
"no"-certificate, i.e. elements not obeying modular law, or
lattice-theoretic "no"-certificate, i.e. a pentangon sublattice.
So, this can be a little complicated.
--
Jori Mäntysalo
