All Topologies on a Finite Set

[Martin Baker]

Its taken me a long time to work it out but I have written spad code to
generate a list of all topologies on a given finite set.
I worked out an algorithm myself (I didn't try to reverse engineer the
lisp code mentioned in a previous thread which was mostly about
simplicial complexes).
I think the approach I worked out is correct but I don't know how to
check for sure. The results look correct and it produces the correct
number of topologies as you can see here:

(1) -> #allTopologiesOnSet [1,2,3]

(1) 29
Type:
PositiveInteger
(2) -> #allTopologiesOnSet [1,2,3,4]

(2) 355
Type:
PositiveInteger
(3) -> #allTopologiesOnSet [1,2,3,4,5]

(3) 6942
Type:
PositiveInteger
(4) -> #allTopologiesOnSet [1,2,3,4,5,6]
(in this case a thread ran 100% for 4 hours until I gave up and pressed ^C)

These results agree with the table at the bottom of the Wiki page here:
https://en.wikipedia.org/wiki/Finite_topological_space

My code is here:
https://github.com/martinbaker/fricasAlgTop/blob/topology/topology.spad

This Wiki page says "There is no known simple formula to compute T(n)
for arbitrary n" and forums like this:
https://mathoverflow.net/questions/8970/number-of-valid-topologies-on-a-finite-set-of-n-elements
seem to suggest that an efficient algorithm is an open problem.

So what am I missing here? Why do they say its so difficult?
The code seems to be efficient (Of course my spad code can be improved
but I cant see how the underlying algorithm could be made more
efficient). It doesn't generate a lattice of latices and then filter out
valid topologies, instead it recurses directly to the required topologies.
So if we had a lattice of latices (with the top and bottom elements
removed as they all have top and bottom elements) we would need to check
2^(2^n-2)-2
potential topologies.
But my code grades the power set and then takes the power set of each
grade separately (which is a lot less) and it does not recurse to the
next grade for cases where the required meets and joins don't exist so
it cuts out the invalid cases at an early stage.

Any ideas how I could check this out further?

Martin

[Kurt Pagani]

Hi Martin

The "simple" is puzzling. I know no formula at all that could tell T(n)
for arbitrary n. Do you?

> and forums like this:
> https://mathoverflow.net/questions/8970/number-of-valid-topologies-on-a-
> finite-set-of-n-elements
> seem to suggest that an efficient algorithm is an open problem.

What's the meaning of "efficient"?

https://codegolf.stackexchange.com/questions/2773/calculate-the-number-of-topologies-on-1-2-n

All these codes play out for n<=10, so one should identify the
time/space complexity of the algorithm:

O(1) - Excellent/Best
O(log n) - Good
O(n) - Fair
O(n log n) - Bad
O(n^2), O(2^n) and O(n!) - Horrible/Worst


Some quotations from the link above:
Python (147 chars): Quick for N<=6, slow for N=7, unlikely N>=8 will
ever complete.

Haskell (144 chars. )Extremely slow for n > 4.

>
> So what am I missing here? Why do they say its so difficult?

It seems to be difficult for n > 10 ...

> The code seems to be efficient (Of course my spad code can be improved
> but I cant see how the underlying algorithm could be made more
> efficient). It doesn't generate a lattice of latices and then filter out
> valid topologies, instead it recurses directly to the required topologies.
> So if we had a lattice of latices (with the top and bottom elements
> removed as they all have top and bottom elements) we would need to check
> 2^(2^n-2)-2
> potential topologies.
> But my code grades the power set and then takes the power set of each
> grade separately (which is a lot less) and it does not recurse to the
> next grade for cases where the required meets and joins don't exist so
> it cuts out the invalid cases at an early stage.
>
> Any ideas how I could check this out further?

Maybe studying current opinions ...
https://www.researchgate.net/post/Is-there-any-method-to-know-the-number-of-topologies-defined-on-a-set

https://arxiv.org/pdf/1503.08359

https://cs.uwaterloo.ca/journals/JIS/VOL9/Benoumhani/benoumhani11.pdf

One of your links mentions the "Union-Closed Sets Conjecture".
https://dwest.web.illinois.edu/openp/unionclos.html
Although I have no idea how it's connected with this problem, the
associated ideas may be helpful.


BTW, your code works, however, n=6 also hot-smoked my laptop ...
(14) -> l5:=allTopologiesOnSet [1,2,3,4,5] ;



Type: List(TopologyFinite)


Time:
1.90 (EV) + 0.02 (GC) = 1.92 sec

(15) -> #l5

(15) 6942

so we are far from O(n*log n) ...

>
> Martin
>

[Kurt Pagani]

Forgot to mention

https://www.ams.org/journals/proc/1970-025-02/S0002-9939-1970-0253944-9/home.html

"""
The logarithm (base 2) of the number of distinct topologies on a set of
elements is shown to be asymptotic to (n^2)/4 as n goes to infinity.
"""

and especially: https://oeis.org/A000798

https://en.wikipedia.org/wiki/On-Line_Encyclopedia_of_Integer_Sequences

On 29/04/2025 18:25, Martin Baker wrote:

[Waldek Hebisch]

On Sat, May 03, 2025 at 01:17:34PM +0200, Kurt Pagani wrote:
> Hi Martin
>
> On 29/04/2025 18:25, Martin Baker wrote:
> >
> > This Wiki page says "There is no known simple formula to compute T(n)
> > for arbitrary n"
>
> The "simple" is puzzling. I know no formula at all that could tell T(n) for
> arbitrary n. Do you?

"Cardinality of set of topologies on [1,...,n]" is a simple formula,
but somewhat inconvenitent one. There is also relatively simple
formula in terms of number of T_0 topologies.

> > and forums like this:
> > https://mathoverflow.net/questions/8970/number-of-valid-topologies-on-a-
> > finite-set-of-n-elements
> > seem to suggest that an efficient algorithm is an open problem.
>
> What's the meaning of "efficient"?
>
> https://codegolf.stackexchange.com/questions/2773/calculate-the-number-of-topologies-on-1-2-n
>
> All these codes play out for n<=10, so one should identify the time/space
> complexity of the algorithm:
>
> O(1) - Excellent/Best

Impossible, O(1) algorithm can only give fixed number of answers.

> O(log n) - Good

Very unlikely to be useful, would need some funky compression scheme
for answers. Of corses, writing "T(n)" (with explicit n) attains
this complexity, but is useless.

> O(n) - Fair
> O(n log n) - Bad
> O(n^2),

That is the best possible with binary encoding of the result.

> O(2^n) and O(n!) - Horrible/Worst

Probably much better than any known method...

--
Waldek Hebisch

[Waldek Hebisch]

Number of topologies grows very fast with n, any method which tries
to generate all topologies and count them is going to be inpractical
even for moderately large n.

> The code seems to be efficient (Of course my spad code can be improved but I
> cant see how the underlying algorithm could be made more efficient). It
> doesn't generate a lattice of latices and then filter out valid topologies,
> instead it recurses directly to the required topologies.
> So if we had a lattice of latices (with the top and bottom elements removed
> as they all have top and bottom elements) we would need to check
> 2^(2^n-2)-2
> potential topologies.
> But my code grades the power set and then takes the power set of each grade
> separately (which is a lot less) and it does not recurse to the next grade
> for cases where the required meets and joins don't exist so it cuts out the
> invalid cases at an early stage.
>
> Any ideas how I could check this out further?

1) Use more compact representation of topology than list of sets.
2) Count only T_0 topologies, count only representatives of
homomorphism classes

Wikipedia page that you cited gives formula to compute number of
topologies knowing number of T_0 topologies. T_0 topologies
are in 1 to 1 correspondence with partial orders, so can be represented
in reasonably compact way. If you generate partial orders in
specific way, for example minimal elements first, maximal last
you can limit number of times that you generate the same
isomorphism class of partial order. You can count partial
orders using formula

#P_n = \sum #c_i

#c_i = n!/#S_i

where #c_i is cardinality of isomorphism class i and #S_i is
cardinality of stabilizer of a representative of class i.
Most topologies are likely to have small stabilizers, so the
formulas above are likely to require much less work than
generating all topologies.

--
Waldek Hebisch

[Kurt Pagani]

On 03/05/2025 14:00, Waldek Hebisch wrote:
> On Sat, May 03, 2025 at 01:17:34PM +0200, Kurt Pagani wrote:
>> Hi Martin
>>
>> On 29/04/2025 18:25, Martin Baker wrote:
>>>
>>> This Wiki page says "There is no known simple formula to compute T(n)
>>> for arbitrary n"
>>
>> The "simple" is puzzling. I know no formula at all that could tell T(n) for
>> arbitrary n. Do you?
>
> "Cardinality of set of topologies on [1,...,n]" is a simple formula,
> but somewhat inconvenitent one. There is also relatively simple
> formula in terms of number of T_0 topologies.

I meant a practical one, T(100)=?, not reducing to other "uncomputable"
figures. To my knowledge the statement in the quotation below still holds?

--- https://oeis.org/A000798
Although no general formula is known for a(n), by considering the number
of topologies with a fixed number of open sets, it is possible to
explicitly represent the sequence in terms of Stirling numbers of the
second kind.
For example: a(n,3) = 2*S(n,2), a(n,4) = S(n,2) + 6*S(n,3), a(n,5) =
6*S(n,3) + 24*S(n,4).
Lower and upper bounds are known: 2^n <= a(n) <= 2^(n*(n-1)), n > 1.
This follows from the fact that there are 2^(n*(n-1)) reflexive
relations on a set with n elements.
Furthermore: a(n+1) <= a(n)*(3a(n)+1).
---

[Martin Baker]

Hi Waldek,

On 03/05/2025 13:17, Waldek Hebisch wrote:
> Number of topologies grows very fast with n, any method which tries
> to generate all topologies and count them is going to be inpractical
> even for moderately large n.

I could easily create a version of the code that does not generate a
list (either just outputting a count or print to a stream or something
like that). That would save a lot of memory but the recursive code would
still store a representation of a big part of the lattice structure in
memory at any one time. There might be a way to generate subsets and
then put them all together.

I probably don't want to spend much time optimising the SPAD code, I'm
more interested in the underlying algorithm. If the algorithm is correct
perhaps one day computers will improve enough to run it with bigger sets.

>> Any ideas how I could check this out further?
>
> 1) Use more compact representation of topology than list of sets.
> 2) Count only T_0 topologies, count only representatives of
> homomorphism classes

I have started to think about how the homomorphism classes could be
generated by decomposing unlabeled sets instead of the current code
which decomposes labeled sets.
I have put my initial thoughts here:

https://www.euclideanspace.com/maths/topology/topologicalSpace/finite/inequivalent/index.htm

This is leading me toward the idea of representing as a partial order
which links to what you said.

> Most topologies are likely to have small stabilizers, so the
> formulas above are likely to require much less work than
> generating all topologies.

Yes, I have an intuition there is some parallel here to the way that
permutation groups are represented in FriCAS/Axiom/Scratchpad. Also I
haven't fully thought through how this links to homotopy groups.

Thanks,

Martin

[Martin Baker]

googlegroups seems to be behaving strangely today.
I have just sent two replies to Kurt and Waldek's posts but only one has
appeared on the list. I will resend the other one later if it does not
appear.

Martin

[Kurt Pagani]

Hi Kurt,

On 03/05/2025 12:17, Kurt Pagani wrote:
> Hi Martin
>
> On 29/04/2025 18:25, Martin Baker wrote:
>> This Wiki page says "There is no known simple formula to compute
T(n) for arbitrary n"
>
> The "simple" is puzzling. I know no formula at all that could tell
T(n) for arbitrary n. Do you?

The Wiki page talks about a "simple formula" and some stackexchange
posts talk about a "simple algorithm". I don't know if they are making a
real distinction between "formula" and "algorithm" or if its just choice
of words. I guess there are some numerical algorithms that can't be
expressed as formulas? Can recursion be put in a formula?

>> and forums like this:
>>
https://mathoverflow.net/questions/8970/number-of-valid-topologies-on-a-finite-set-of-n-elements

>> seem to suggest that an efficient algorithm is an open problem.
>
> What's the meaning of "efficient"?
>
>
https://codegolf.stackexchange.com/questions/2773/calculate-the-number-of-topologies-on-1-2-n

As far as I can tell these example all use what I call a brute-force
method, that is, powerset of powerset and filter out valid topologies (I
can't be sure because the aim seems to be to make the code as small as
possible rather than understandable).

What I would like is a way to define "efficient" which depends only on
the algorithm and not the low level details of the language. For
instance I think it should penalise algorithms which generate invalid
results and then have to filter them out.

> All these codes play out for n<=10, so one should identify the time/
space complexity of the algorithm:
>
> O(1) - Excellent/Best

> O(log n) - Good

> O(n) - Fair
> O(n log n) - Bad

> O(n^2), O(2^n) and O(n!) - Horrible/Worst

I will look at the references you gave. At first sight this looks like
the theory around the 'P versus NP problem'. I think one of the classic
problems is factoring multiplication of numbers whereas this problem is
about factoring union/join of sets. So they are both about factoring so
it would not surprise me if they had the same level of complexity.

>> So what am I missing here? Why do they say its so difficult?

> It seems to be difficult for n > 10 ...

Do you know what the issue with n > 10 is? Is it just because the
numbers are so large, or does something change such as a breakdown in
symmetries?

Thank you very much for all these ideas, I will followup on the links
and let you know how I get on.

Martin

[Kurt Pagani]

Hi martin

forwarding apparently worked ...

On Sunday, 4 May 2025 at 11:30:59 UTC+2 Kurt Pagani wrote:

Hi Kurt,

On 03/05/2025 12:17, Kurt Pagani wrote:
> Hi Martin
>
> On 29/04/2025 18:25, Martin Baker wrote:
>> This Wiki page says "There is no known simple formula to compute
T(n) for arbitrary n"
>
> The "simple" is puzzling. I know no formula at all that could tell
T(n) for arbitrary n. Do you?

The Wiki page talks about a "simple formula" and some stackexchange
posts talk about a "simple algorithm". I don't know if they are making a
real distinction between "formula" and "algorithm" or if its just choice
of words. I guess there are some numerical algorithms that can't be
expressed as formulas? Can recursion be put in a formula?

It's not so simple to define "simple" :-) I don't pay too much attention to this informal use of language,

The semantics of 'formula' is manifold, e.g. in formal systems (à la Smullyan) you may describe things which you wouldn't call a formula in the ordinary sense, wheras what's "ordinary sense"?

 

>> and forums like this:
>>
https://mathoverflow.net/questions/8970/number-of-valid-topologies-on-a-finite-set-of-n-elements

>> seem to suggest that an efficient algorithm is an open problem.
>
> What's the meaning of "efficient"?
>
>
https://codegolf.stackexchange.com/questions/2773/calculate-the-number-of-topologies-on-1-2-n

As far as I can tell these example all use what I call a brute-force
method, that is, powerset of powerset and filter out valid topologies (I
can't be sure because the aim seems to be to make the code as small as
possible rather than understandable).

That's true, however, I didn't find any other on the fly.

 

What I would like is a way to define "efficient" which depends only on
the algorithm and not the low level details of the language. For
instance I think it should penalise algorithms which generate invalid
results and then have to filter them out.

> All these codes play out for n<=10, so one should identify the time/
space complexity of the algorithm:
>
> O(1) - Excellent/Best
> O(log n) - Good
> O(n) - Fair
> O(n log n) - Bad
> O(n^2), O(2^n) and O(n!) - Horrible/Worst

I just see that I forgot providing the ref for the above:

https://www.bigocheatsheet.com/ or

https://www.freecodecamp.org/news/big-o-cheat-sheet-time-complexity-chart/

I have no clear idea what O(?) we could expect at best. I was rather surprised that the step from n=5 to n=6 in  your code

has such an impact. The asymptotics, however,  log_2(T(n)) ~ n^2/4  doesn't bode well, IMO.

I will look at the references you gave. At first sight this looks like
the theory around the 'P versus NP problem'. I think one of the classic
problems is factoring multiplication of numbers whereas this problem is
about factoring union/join of sets. So they are both about factoring so
it would not surprise me if they had the same level of complexity.

Very true!

 

>> So what am I missing here? Why do they say its so difficult?
> It seems to be difficult for n > 10 ...

Do you know what the issue with n > 10 is? Is it just because the
numbers are so large, or does something change such as a breakdown in
symmetries?

I have no clue, however, if the bounds 2^n <= T(n) <= 2^(n*(n-1)) are correct (I guess so), then, according to the asymptotics mentioned above, the numbers get very large indeed.

[Martin Baker]

On 04/05/2025 11:33, Kurt Pagani wrote:
>
> Hi martin
> forwarding apparently worked

Yes, thank you for that, I tried several times to post to the list and
it never appeared.

I guess it must be some issue with my google account, very strange, I
suspect AI is involved somewhere.

Martin

[Grégory Vanuxem]

Strange 

--
You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/60127fed-2d0c-4054-a42b-982cf79b6346%40martinb.com.

[Martin Baker]

Hi Kurt,

On 03/05/2025 12:17, Kurt Pagani wrote:

> Hi Martin
>
> On 29/04/2025 18:25, Martin Baker wrote:
>> This Wiki page says "There is no known simple formula to compute T(n)
>> for arbitrary n"
>
> The "simple" is puzzling. I know no formula at all that could tell T(n)
> for arbitrary n. Do you?

The Wiki page talks about a "simple formula" and some stackexchange
posts talk about a "simple algorithm". I don't know if they are making a
real distinction between "formula" and "algorithm" or if its just choice
of words. I guess there are some numerical algorithms that can't be
expressed as formulas? Can recursion be put in a formula?

>> and forums like this:
>> https://mathoverflow.net/questions/8970/number-of-valid-topologies-on-
>> a- finite-set-of-n-elements
>> seem to suggest that an efficient algorithm is an open problem.
>
> What's the meaning of "efficient"?
>
> https://codegolf.stackexchange.com/questions/2773/calculate-the-number-
> of-topologies-on-1-2-n
>
> All these codes play out for n<=10, so one should identify the time/
> space complexity of the algorithm:
>
>   O(1) - Excellent/Best
>   O(log n) - Good
>   O(n) - Fair
>   O(n log n) - Bad
>   O(n^2), O(2^n) and O(n!) - Horrible/Worst

I will look at the references you gave. At first sight this looks like
the theory around the 'P versus NP problem'. I think one of the classic
problems is factoring multiplication of numbers whereas this problem is
about factoring union/join of sets. So they are both about factoring so
it would not surprise me if they had the same level of complexity.

[Qian Yun]

On 5/4/25 8:28 PM, Martin Baker wrote:
> On 04/05/2025 11:33, Kurt Pagani wrote:
>>
>> Hi martin
>> forwarding apparently worked
>
> Yes, thank you for that, I tried several times to post to the list and
> it never appeared.

I received "Moderator's spam report" only 4 hours ago with 5 of
your emails from 3 days ago. I released one of the email.

I think it might be a glitch in the google system, or your email
account is marked as spammer incorrectly.

- Qian