20

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?

Karl
  • 11,446
Steven Clontz
  • 5,719
  • 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. – Thomas Andrews Nov 05 '23 at 16:37
  • The prime factorization is definitely what is happening with $n$ a power of $2$ case. – Thomas Andrews Nov 05 '23 at 16:38
  • 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. – Thomas Andrews Nov 05 '23 at 16:44
  • 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.$ – Thomas Andrews Nov 05 '23 at 17:12
  • 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. – Thomas Andrews Nov 05 '23 at 17:15
  • If $p(n)$ is par for $n,$ we get, for $0\leq m<2^k$ you can show $k\leq p(2^k+m)\leq k+p(m+1).$ – Thomas Andrews Nov 05 '23 at 17:27
  • In general, we can get $p(2^n+1)=n+1,$ so another counterexample of my prime factorization approach might be $7=p(65).$ The prime factorization approach fails if $p(13)\neq 4.$ – Thomas Andrews Nov 05 '23 at 17:38

1 Answers1

23

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

Alex Kruckman
  • 76,357
  • Does this sequence have any interesting properties? Is there some smaller upper bound for Par(n)? – MannerPots Nov 06 '23 at 18:46
  • 3
    @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$. – Alex Kruckman Nov 06 '23 at 19:41