20
$\begingroup$

In Possible number of open sets in a topology Shreya Jaganathan asked if there exists a finite topological space with exactly 100 open sets. It was quickly pointed out that for each positive integer $N$, $\{0,1,\dots,N-2\}$ is a set of size $N-1$ with the topology $\{\{0,1,\dots,n-1\}:0\leq n\leq N-1\}$ of size $N$.

It was then pointed out by bof that for $N=100$, there exists a topology with $N$ open sets on a set of size $8$, but M W showed there does not exist such a topology on a set of size $7$.

Let $\operatorname{Par}(N)$ be the topological par of each positive integer $N$, defined as the smallest cardinality of a topological space that has exactly $N$ open sets. Then $\operatorname{Par}(100)=8$ by bof and M W's results.

We can see that $\operatorname{Par}(2^N)=N$: every topology is a subset of the power set of size $2^N$, and the power set is itself the discrete topology.

This also shows that $\operatorname{Par}(N)\geq \lceil \log_2(N)\rceil$. Note that $\operatorname{Par}(100)=8>7=\lceil\log_2(100)\rceil$.

How might we compute the topological par for positive integers in general?

$\endgroup$
7
  • $\begingroup$ Every topology is a distributive lattice. The example given there is of the form $L_2^2\times L_5^2$ where $L_2$ is a distributive lattice of size $2$ and $L_5$ is a distributive lattice of size $5.$ The fundamental theorem of finite distributive lattices lets us get small topologies, and we get $P=P_2\sqcup P_2\sqcup P_5\sqcup P_5$ where $P_2$ and $P_5$ are partial orders of size $1$ and $3$ with , respectively, $2$ and $5$ order ideals. So it seems like the best way to go is prime factorizing $n,$ and answer the question for prime $n$ first. $\endgroup$ Nov 5, 2023 at 16:37
  • $\begingroup$ The prime factorization is definitely what is happening with $n$ a power of $2$ case. $\endgroup$ Nov 5, 2023 at 16:38
  • $\begingroup$ Specifically, you want a distributive lattice of $n$ elements with the least number of irreducible elements. An element $x\in L$ is irreducible if $x=a\cup b$ means $x=a$ or $x=b.$ The set of irreducible elements is the size smallest set that can be the size of a topology with that distributive lattice. $\endgroup$ Nov 5, 2023 at 16:44
  • $\begingroup$ For $n=7,$ we get a par of $4.$ That is the smallest case where the par is greater than $\lceil \log_2 n\rceil.$ $\endgroup$ Nov 5, 2023 at 17:12
  • $\begingroup$ It would be interesting to check $n=21.$ It seems possible we can get a par of $5$ rather than the $4+2=6$ gotten via the prime factorization. $\endgroup$ Nov 5, 2023 at 17:15

1 Answer 1

23
$\begingroup$

This is A137813 on the OEIS, and some references are given there. In particular:

$\endgroup$
2
  • $\begingroup$ Does this sequence have any interesting properties? Is there some smaller upper bound for Par(n)? $\endgroup$
    – MannerPots
    Nov 6, 2023 at 18:46
  • 3
    $\begingroup$ @MannerPots The paper by Ragnarsson and Tenner that I linked to contains a number of results about this sequence. In particular, they prove the upper bound $\mathrm{Par}(k) \leq \frac{4}{3}\lfloor \log_2(k)\rfloor + 2$. $\endgroup$ Nov 6, 2023 at 19:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .