nextLatticePermutation in SymmetricGroupCombinatoricFunctions

[Martin Baker]

I think I am making progress with my finite topology code but I would
like to check to see if any of you know if there is any existing code in
the FriCAS library that would help me minimise the code I need to write.

I have been looking at the library code and I thought there is a
possibility that nextLatticePermutation in
SymmetricGroupCombinatoricFunctions might possibly do the sort of thing
I want. Is there tutorial information for this combinator code and do
you think it would help with the following?

I now have two domains that can represent topology. In the first one
each representation is a topology like this:

-- A topology on a finite set.
-- Defined by a list of open sets.
-- Elements are labelled by a NNI number.
Rep := Record(basis:Boolean,topology:List (Set NNI))

In the second one each representation is a topology isomorphism class
like this:

-- A representation of a topology isomorphism class consisting of:
-- unlabeledOpenSets: the cardinality of each set
-- substructure: subset lattice structure represented as a poset
-- Only immediate subsets are listed (like Hasse diagram).
-- Top and bottom are assumed so don't have to be explicitly listed.
Rep := Record(unlabeledOpenSets:List NNI,
substructure:List Record(superset:NNI,subset:NNI))

These two domains have very similar functions but they represent
different things.

I want to be able to convert between these representations. For
instance, given a topology isomorphism class, I want a function that
will list all topologies for that class and also a function to construct
one representative topology. Also I would like a function to go in the
reverse direction.

Do you think the combinator code in the library would help? Also this
subject seems to be related to Galois theory, is there any code in the
library that helps with that?

My code is here:
https://github.com/martinbaker/fricasAlgTop/blob/topology/topology.spad
Although this is still at the stage where I am trying to get the overall
design right and to find out how it relates to existing FriCAS code.

Any ideas appreciated, thanks,

Martin

[Waldek Hebisch]

AFAICS _both_ can represent either topologies or isomorphism classes.
In both cases to get isomorphism classes you need to to some
filtering to choose a representaitve or form abstracition classes
(classes of equvalent topologies).

Typicaly is is easier to work with partial pre-orders, as there is only
one pre-order corresponding to a given topology, while you can
take many different bases.

> I want to be able to convert between these representations.

Given a topology and a point p consider minimal open set contaning
p, call it U(p). Such a set exist, you can get it as intersection
of all open sets contaning p (since topology is finite this is a
finite family of open sets, so its intersection is open). You
can compute U(p) taking intersection of all elements of a basis
containing p. Once you know U(p) you know pre-order: q <= p
and only if q \in U(p). Conversly, when you know pre-order
you can get U(p) as {q : q <= p }. U(p) give you a basis of
topology (in fact a minimal basis, every other basis must
contain all U(p)).

> For instance,
> given a topology isomorphism class, I want a function that will list all
> topologies for that class and also a function to construct one
> representative topology. Also I would like a function to go in the reverse
> direction.

You need to decide how you represent isomorphism class. If you
represent class using a representative, then going for topology
to class is trivial, any topology may serve as a representative.
But then you need code to compute equivalence, and you need to
deal with conseqences of fact that such representation is
noncanonical. You man try to put order on topologies, as say
take smallest topology in a class as a representative, then
you will need some work to compute representative, but equality
of classes will be easy.

> Do you think the combinator code in the library would help? Also this
> subject seems to be related to Galois theory, is there any code in the
> library that helps with that?

Equvalence of classes can be done via graph isomorphism, but we
have no code to do this. Enumerating equvalence class is a
special case for enumerationg isomorphic graphs on the same
set of vertices.

I do not think that existing code will help much, because it
seem to solve different problems. Rather, you should look
at structure of topologies.

--
Waldek Hebisch

[Martin Baker]

Hi Waldek,
Thank you for your helpful reply, lots of issues here:

On 26/05/2025 14:56, Waldek Hebisch wrote:
> AFAICS _both_ can represent either topologies or isomorphism classes.
> In both cases to get isomorphism classes you need to to some
> filtering to choose a representaitve or form abstracition classes
> (classes of equvalent topologies).

The idea here is that:
* topologies are sets of _labeled_ sets
* isomorphism classes are sets of _unlabeled_ sets
(both with the usual meet,join top and bottom axioms)

So when we go from labeled sets to unlabeled sets all we have left is
the number of elements (cardinality) which looses the information about
meets and joins so we have to put that explicitly back into the
representation as a subset structure.

Representing isomorphism classes in this way does not involve choosing a
representative. Also I hope there should be a canonical way to represent
the subset structure so that I can implement: equality(=) is isomorphic
to isomorphism. (a bit like Voevodsky’s Univalence Axiom).

I take your point that we can represent either with both representations
but it seems a lot more efficient this way round.
For instance, representing isomorphism classes with a labeled set and
then using only representative members seems like creating arbitrary
information that is not used (would the nice property that meets are
intersections and joins are unions still be valid in this case?).

Or, this other way round, the following two topologies would have the
same shape lattice, so how do you distinguish them from the substructure
only?
[{}, {3}, {1, 2}, {1, 2, 3}]
[{}, {1}, {2, 3}, {1, 2, 3}]

> Typicaly is is easier to work with partial pre-orders, as there is only
> one pre-order corresponding to a given topology, while you can
> take many different bases.

I think that may be what I meant by 'subset structure'. I was thinking
of implementing it as a list of (subset,superset) pairs. Since subset
and superset are NNI indexes I was hoping there would be a way to force
them in a canonical order.

>> I want to be able to convert between these representations.
>
> Given a topology and a point p consider minimal open set contaning
> p, call it U(p). Such a set exist, you can get it as intersection
> of all open sets contaning p (since topology is finite this is a
> finite family of open sets, so its intersection is open). You
> can compute U(p) taking intersection of all elements of a basis
> containing p. Once you know U(p) you know pre-order: q <= p
> and only if q \in U(p). Conversly, when you know pre-order
> you can get U(p) as {q : q <= p }. U(p) give you a basis of
> topology (in fact a minimal basis, every other basis must
> contain all U(p)).

Yes, I have been experimenting with some code for converting topologies
to/from basis. I need to do some more work on this.

>> For instance,
>> given a topology isomorphism class, I want a function that will list all
>> topologies for that class and also a function to construct one
>> representative topology. Also I would like a function to go in the reverse
>> direction.
>
> You need to decide how you represent isomorphism class. If you
> represent class using a representative, then going for topology
> to class is trivial, any topology may serve as a representative.
> But then you need code to compute equivalence, and you need to
> deal with conseqences of fact that such representation is
> noncanonical. You man try to put order on topologies, as say
> take smallest topology in a class as a representative, then
> you will need some work to compute representative, but equality
> of classes will be easy.

If you think what I said above is valid then I think I can represent an
isomorphism class without using a representative.

>> Do you think the combinator code in the library would help? Also this
>> subject seems to be related to Galois theory, is there any code in the
>> library that helps with that?
>
> Equvalence of classes can be done via graph isomorphism, but we
> have no code to do this. Enumerating equvalence class is a
> special case for enumerationg isomorphic graphs on the same
> set of vertices.

It seems like we have a sequence of structures each one more specific
than the last:

graph -> partial pre-order -> lattice

It would be good if these things could be implemented in the most
general way and then inherited by more specific structures.

> I do not think that existing code will help much, because it
> seem to solve different problems. Rather, you should look
> at structure of topologies.

OK, thank you for checking this.

I have been thinking for some time now that the most efficient way to
represent a topology would be to build it up from sub-topologies but I
could not work out how to do this. However, I have just realised how to
do it: build a big topology from smaller _discrete_ topologies.

So this:
[{1, 2, 3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {1, 2},
{1, 3}, {2, 3}, {1, 4}, {1}, {2}, {3}, {}]
could be coded like this:
P{1, 2, 3}+{1, 4}+{1, 2, 4}+{1, 3, 4}+{1, 2, 3, 4}

Where P means powerset.

This is the same way that simplicial complexes are coded. A 'discrete'
topology corresponds to a 'face' and simplicial complexes are built up
from faces.

I am not saying that simplicial complexes are the same as these
topologies (we know they are not). I am just thinking they might be
represented in a similar way.

I have not thought through all of this yet, one thing I would like to
implement is simplicial sets (simplicial complexes with degenerate
faces) Is there any way degenerate faces could be brought into this theory.

Do you think that, if a lattice model domain was implemented in the
FriCAS library then both simplicial complexes and finite topology
domains could be built from it?

Martin

[Waldek Hebisch]

On Mon, May 26, 2025 at 06:48:39PM +0100, Martin Baker wrote:
> Hi Waldek,
> Thank you for your helpful reply, lots of issues here:
>
> On 26/05/2025 14:56, Waldek Hebisch wrote:
> > AFAICS _both_ can represent either topologies or isomorphism classes.
> > In both cases to get isomorphism classes you need to to some
> > filtering to choose a representaitve or form abstracition classes
> > (classes of equvalent topologies).
>
> The idea here is that:
> * topologies are sets of _labeled_ sets

OK.

> * isomorphism classes are sets of _unlabeled_ sets
> (both with the usual meet,join top and bottom axioms)

I do not think this will work well (at least not in a simple
way). In isomorphism class you allow arbitrary relabeling, so
at "absolute" level labels do not matter. But they
matter in relative sense. You need to know when two elements
are in fact one element (that is they are equal), you need
to know if for given p and q there is an open set containing
q but such that p is not in this set. Easiest way to
keep this information is to use labels. You could try to
encode elements of the set by their properties, but to
do this you need to know which combination of properties
are possible.

What you wrote above looks more like you would like to represent
lattice of open sets as an abstract lattice. AFAICS you still
would have to decide when two abstrace lattices are isomorphic
and it is not clear if isomorphism class of lattices gives you
isomorphism class of topologial spaces. Mathematical version of
Murphy principle says that if there is no reason for some property
to be true, then it is false. And ATM I see no reason to
have nice correspondence there (of course I may be missing
something).

> So when we go from labeled sets to unlabeled sets all we have left is the
> number of elements (cardinality) which looses the information about meets
> and joins so we have to put that explicitly back into the representation as
> a subset structure.
>
> Representing isomorphism classes in this way does not involve choosing a
> representative. Also I hope there should be a canonical way to represent the
> subset structure so that I can implement: equality(=) is isomorphic to
> isomorphism. (a bit like Voevodsky’s Univalence Axiom).
>
> I take your point that we can represent either with both representations but
> it seems a lot more efficient this way round.
> For instance, representing isomorphism classes with a labeled set and then
> using only representative members seems like creating arbitrary information
> that is not used (would the nice property that meets are intersections and
> joins are unions still be valid in this case?).

Well, sometimes discarding information is not easy. Concerning meets
and joins, correspondence that I have in mind is 1-1 correspondence
between topologies and pre-orders. Any pre-order has corresponding
topology, so there is no requrement for nice meets and joins.

> Or, this other way round, the following two topologies would have the same
> shape lattice, so how do you distinguish them from the substructure only?
> [{}, {3}, {1, 2}, {1, 2, 3}]
> [{}, {1}, {2, 3}, {1, 2, 3}]

First, minimal basis(es) are respectively
[{3}, {1, 2}]
[{1}, {2, 3}]

Denoting by <=_1 and <=_2 corresponding preoders we have 1 <=_1 2 and
2 <=_1 1. OTOH 1 <=_2 2 is false. So pre-orders are different.

> > Typicaly is is easier to work with partial pre-orders, as there is only
> > one pre-order corresponding to a given topology, while you can
> > take many different bases.
>
> I think that may be what I meant by 'subset structure'. I was thinking of
> implementing it as a list of (subset,superset) pairs. Since subset and
> superset are NNI indexes I was hoping there would be a way to force them in
> a canonical order.

You are thinking subsets, which potentially is quite bulky, there may
be (and probably typically is) exponentially many open subsets, while
pre-order needs matrix of size N^2 (where N is number of elements in
the base set).

It is not clear to me what _exactly_ you want to do, but it looks
tricky to make it work without using a representative of
something. Of course, in extreme case you could use set of
topologies isomorphic to a given topology, but done in a
simple way this is double exponential. You could try to prune
this, but usually taking a representative is a most efficient
way to get rid of bulk.

<snip>

> I have been thinking for some time now that the most efficient way to
> represent a topology would be to build it up from sub-topologies but I could
> not work out how to do this. However, I have just realised how to do it:
> build a big topology from smaller _discrete_ topologies.
>
> So this:
> [{1, 2, 3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {1, 2},
> {1, 3}, {2, 3}, {1, 4}, {1}, {2}, {3}, {}]
> could be coded like this:
> P{1, 2, 3}+{1, 4}+{1, 2, 4}+{1, 3, 4}+{1, 2, 3, 4}
>
> Where P means powerset.

Well, there is easy thing to do: each finite topological space
is a disjoint sum of connected componests. I the case above
one connected component is {1, 4} (with topology [{}, {1}, {1, 4}]),
there two other components: {2} and {3}. You can view {1, 4}
with the topology above as an extention of {1} by {4}, but in
general added part ({4} here) is "glued" to previous part in
a non trivial way. I think it is much clearer when you look
at corresponding pre-orders. Pre-order on {1, 4} is just
normal linear order, but it should be clear that you may have
much more "interesting" pre-orders. Let X be a topological
space. The set of minimal elements of X, call it M is just a
discrete space. X - M gives you smaller topology. But whole
topology is only determined once you now order relations between
elements of M and X - M.

--
Waldek Hebisch

[Ralf Hemmecke]

On 5/26/25 22:31, Waldek Hebisch wrote:
> On Mon, May 26, 2025 at 06:48:39PM +0100, Martin Baker wrote:
>> The idea here is that:
>> * topologies are sets of _labeled_ sets

>> * isomorphism classes are sets of _unlabeled_ sets
>> (both with the usual meet,join top and bottom axioms)

Strange, suddenly that reminds me of something I did in Aldor-Combinat
together with Martin Rubey (CC to him). Maybe Martin R. is still more
into the subject and can say something with respect to Combinatorial
Species and how topologies are modelled by them.

Ralf

[Martin Baker]

On 26/05/2025 21:31, Waldek Hebisch wrote:
>> * isomorphism classes are sets of _unlabeled_ sets
>> (both with the usual meet,join top and bottom axioms)
>
> I do not think this will work well (at least not in a simple
> way). In isomorphism class you allow arbitrary relabeling, so
> at "absolute" level labels do not matter. But they
> matter in relative sense. You need to know when two elements
> are in fact one element (that is they are equal), you need
> to know if for given p and q there is an open set containing
> q but such that p is not in this set. Easiest way to
> keep this information is to use labels. You could try to
> encode elements of the set by their properties, but to
> do this you need to know which combination of properties
> are possible.
>
> What you wrote above looks more like you would like to represent
> lattice of open sets as an abstract lattice. AFAICS you still
> would have to decide when two abstrace lattices are isomorphic
> and it is not clear if isomorphism class of lattices gives you
> isomorphism class of topologial spaces. Mathematical version of
> Murphy principle says that if there is no reason for some property
> to be true, then it is false. And ATM I see no reason to
> have nice correspondence there (of course I may be missing
> something).

Perhaps if I use an example:
A topology might be represented like this:

[{}, {3}, {1, 2}, {1, 2, 3}]

But for a isomorphism class we want a representation that includes
multiple topologies such as:

[{}, {3}, {1, 2}, {1, 2, 3}]
[{}, {1}, {2, 3}, {1, 2, 3}]

and so on

We could choose one to represent the whole class:

[{}, {3}, {1, 2}, {1, 2, 3}]

Alternatively we could represent it as a partial order:
[ _|_<a , _|_ < b , a<T, b<T]
Or we could represent it as a lattice:
[ a/\b=_|_ , a\/b=T]

It seems to me that all 3 of these represent the same structure (upto
isomorphism).
I have used labels for the partial order and lattice cases but these
labels represent elements of the topology not elements of the open sets.
(So, in this case _|_={} a={3} b={1, 2} T={1, 2, 3})
So I think the partial order seems more compact and involves less
arbitrary choices.

> Well, sometimes discarding information is not easy. Concerning meets
> and joins, correspondence that I have in mind is 1-1 correspondence
> between topologies and pre-orders. Any pre-order has corresponding
> topology, so there is no requrement for nice meets and joins.

I don't quite see what you are saying here? Cant we define it either way
and convert between them:
[ _|_<a , _|_ < b , a<T, b<T] = [ a/\b=_|_ , a\/b=T]

I seem to remember that things get a bit more complicated for infinite
topologies but is what you say true for finite topologies?

> It is not clear to me what _exactly_ you want to do, but it looks
> tricky to make it work without using a representative of
> something.

I would like to implement two domains, one for the topology case and
another one for the iso class case.
For the iso class case I cant see why the alternative codings I
suggested above would not work? They don't seem to require an arbitrary
representative.

>> I have been thinking for some time now that the most efficient way to
>> represent a topology would be to build it up from sub-topologies but I could
>> not work out how to do this. However, I have just realised how to do it:
>> build a big topology from smaller _discrete_ topologies.
>>
>> So this:
>> [{1, 2, 3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {1, 2},
>> {1, 3}, {2, 3}, {1, 4}, {1}, {2}, {3}, {}]
>> could be coded like this:
>> P{1, 2, 3}+{1, 4}+{1, 2, 4}+{1, 3, 4}+{1, 2, 3, 4}
>>
>> Where P means powerset.
>
> Well, there is easy thing to do: each finite topological space
> is a disjoint sum of connected componests. I the case above
> one connected component is {1, 4} (with topology [{}, {1}, {1, 4}]),
> there two other components: {2} and {3}. You can view {1, 4}
> with the topology above as an extention of {1} by {4}, but in
> general added part ({4} here) is "glued" to previous part in
> a non trivial way. I think it is much clearer when you look
> at corresponding pre-orders. Pre-order on {1, 4} is just
> normal linear order, but it should be clear that you may have
> much more "interesting" pre-orders. Let X be a topological
> space. The set of minimal elements of X, call it M is just a
> discrete space. X - M gives you smaller topology. But whole
> topology is only determined once you now order relations between
> elements of M and X - M.

This seems to me potentially a very efficient encoding for the topology
case. I will think about this more.

Martin

[Waldek Hebisch]

So, it seems that you want to represent topology via its lattice
of open sets. There is a trivial difficulty here: two point
space with discrete topology: [{}, {1}, {2}, {1, 2}] has
isomorphic lattice of open sets, so there are multiple
non-isomorphic topologies with "the same" lattice of open
sets. This is trivial difficulty and vanishes if you require
your space to be T_0. However, IMO your example is misleading
(like computing 2^0 and 2^1 and concuding that exponential is
quite small). Consider sligtly bigger topology with basis

[{1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 2, 3, 4, 5, 6}]

The topology has 19 open sets, so lattice of open sets is
significantly bigger than the basis above. Consider labeling
of part of the lattice of open sets corresponding to the
basis above:

a = {1}, b = {1, 2}, c = {1, 3}, d = {1, 4}, e = {1, 5},
f = {1, 2, 3, 4, 5, 6}

If you look at this you will notice that each set above
introduces exactly one new element (new in the sense that
it did not appear in earlier sets). So, in effect labeling
of open sets gives you labeling of elements of the space.
But since lattice of open sets is much bigger than the
basis you have a lot of irrelevant labels.

--
Waldek Hebisch

[Martin Baker]

On 27/05/2025 16:31, Waldek Hebisch wrote:
> So, it seems that you want to represent topology via its lattice
> of open sets.

Well, I'm keeping an open mind about open sets but my initial instinct
was to use:
* labeled open sets for topologies.
* set size + lattice for iso classes.

The reason for the second is that, to use labeled open sets for iso
classes, the constructor algorithm would have to:
* choose a representative for each iso class (this seems very arbitrary
and I don't know how to do it)
* choose a basis.
* make sure these choices are closed under union and intersection.

(I think I should re-read your earlier messages in case you have
explained these things already)

By the way, in you earlier email you mentioned using pre-order to code
this, this prompted me to read this page:
https://en.wikipedia.org/wiki/Specialization_(pre)order
So I am starting to understand what you meant. However it suggests that
Specialization pre order only works for T0 separation. At first I
thought this would not matter (why bother about points that can't be
distinguished by the lattice). Then I had the thought these points must
be the degenerate points. Things I've read suggest that degenerate
points are very useful (for example in calculating products of
topologies and other nice properties) so perhaps I do need T0. I am
thinking that I would need to base it on a weak pre-order? Do you know
if this speculation, on my part, is valid?

> There is a trivial difficulty here: two point
> space with discrete topology: [{}, {1}, {2}, {1, 2}] has
> isomorphic lattice of open sets, so there are multiple
> non-isomorphic topologies with "the same" lattice of open
> sets. This is trivial difficulty and vanishes if you require
> your space to be T_0. However, IMO your example is misleading
> (like computing 2^0 and 2^1 and concuding that exponential is
> quite small). Consider sligtly bigger topology with basis
>
> [{1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 2, 3, 4, 5, 6}]
>
> The topology has 19 open sets, so lattice of open sets is
> significantly bigger than the basis above. Consider labeling
> of part of the lattice of open sets corresponding to the
> basis above:
>
> a = {1}, b = {1, 2}, c = {1, 3}, d = {1, 4}, e = {1, 5},
> f = {1, 2, 3, 4, 5, 6}
>
> If you look at this you will notice that each set above
> introduces exactly one new element (new in the sense that
> it did not appear in earlier sets). So, in effect labeling
> of open sets gives you labeling of elements of the space.
> But since lattice of open sets is much bigger than the
> basis you have a lot of irrelevant labels.

OK, I will have to work through this. It just seems counter-intuitive
because there are a lot less iso classes than topologies so we should be
able to code them with less data?

Thanks,

Martin

[Waldek Hebisch]

On Tue, May 27, 2025 at 06:55:38PM +0100, Martin Baker wrote:
> On 27/05/2025 16:31, Waldek Hebisch wrote:
> > So, it seems that you want to represent topology via its lattice
> > of open sets.
>
> Well, I'm keeping an open mind about open sets but my initial instinct was
> to use:
> * labeled open sets for topologies.
> * set size + lattice for iso classes.
>
> The reason for the second is that, to use labeled open sets for iso classes,
> the constructor algorithm would have to:
> * choose a representative for each iso class (this seems very arbitrary and
> I don't know how to do it)
> * choose a basis.
> * make sure these choices are closed under union and intersection.

There is no need to have basis closed under set union. Actually,
it makes sense to have basis which is as small as possible, and
on set of cardinality N it is possible to take basis which has
at most N elements. Similarly, intersection of two members of
basis does not need to be in basis, all what is needed is that
intersection is an open set, that is can be written as sum of
elements of basis.

> (I think I should re-read your earlier messages in case you have explained
> these things already)
>
> By the way, in you earlier email you mentioned using pre-order to code this,
> this prompted me to read this page:
> https://en.wikipedia.org/wiki/Specialization_(pre)order
> So I am starting to understand what you meant. However it suggests that
> Specialization pre order only works for T0 separation.

No, pre-order works for arbitrary finite topological spaces.
T_0 means that you get _partial order_.

> At first I thought
> this would not matter (why bother about points that can't be distinguished
> by the lattice). Then I had the thought these points must be the degenerate
> points. Things I've read suggest that degenerate points are very useful (for
> example in calculating products of topologies and other nice properties) so
> perhaps I do need T0.

When looking at structure of topological spaces, spaces that are
not T_0 are mostly a distraction, one can easily get properties
of arbitrary topological spaces knowing structue of T_0 spaces.
But since in arbitrary spaces two different points may be
indistinguishable by topological properties alone it is less
convenient to speak about such spaces.

> I am thinking that I would need to base it on a weak
> pre-order? Do you know if this speculation, on my part, is valid?

I affraid that we use different terminology here. In the Wikipedia
article (and I use the same definition) pre-order means that
there may be two different points x and y such that x <= y and
y <= x. That allows handling arbitrary topological spaces.
Partial order means that when x <= y and y <= x, then x = y,
which implies that spaces corresponding to partial orders are
T_0.

<snip example>

> OK, I will have to work through this. It just seems counter-intuitive
> because there are a lot less iso classes than topologies so we should be
> able to code them with less data?

Well, discarding information is not so easy. You need to invent
some clever encoding, clearly lattice of open sets does not give
you such an encoding.

--
Waldek Hebisch