Let $(X,d)$ be a metric space and let $x,y \in X$ be points. We will define the metric segment between the points $x,y$ as the following set:

$\left [ x,y \right ]=\left \{ z \in X : d(x,z)+d(z,y)=d(x,y) \right \}$

Also, we will say that a set $C \subseteq X$ is convex if for all $x,y \in C$ it holds true that $\left [ x,y \right ] \subseteq C$.

It can be easily seen that $\emptyset$ and $X$ are convex and that the intersection of any two convex sets is a convex set.

We will call a family $\mathcal{F} \subseteq \mathcal{P} (X)$ 'special' if the following is satisfied:

  • $\emptyset, X \in \mathcal{F}$
  • $\forall U, V \in \mathcal{F} : U \cap V \in \mathcal{F}$

Furthermore, we will call such a family $\mathcal{F}$ metrizable if there exists a metric $d: X \times X \rightarrow \mathbb{R}$ such that the set of all convex sets in $(X,d)$ is equal to $\mathcal{F}$.

Denote by $a(n)$ the overall number of metrizable special families that can be defined on a set of $n$ elements.

My question is how can we write a code to enumerate the sequence $a(n)$?

How would we even go about checking whether a function $d: X \times X \rightarrow \mathbb{R}$ on a finite set $X$ is a metric?

Note: The number of special families on $n$ is given in OEIS as A102894. As an example, the special family $\left \{\emptyset, \left \{ 1 \right \}, \left \{2 \right \}, \left \{3 \right \}, \left \{ 1,2 \right \}, \left \{2,3 \right \}, \left \{1,2,3 \right \} \right \}$ is metrizable because it precisely agrees with the set of all convex sets in the metric space $(\left \{1,2,3 \right \}, d)$ where $d$ is the standard Euclidean metric on $\mathbb{R}$. Also, as I understand, there is this rather simple code to evaluate the number of (non-necessarily metrizable) special families on a set of $n$ elements:

b[n_] := 
   And[MemberQ[#, {}], MemberQ[#, Range[n]], 
     SubsetQ[#, Intersection @@@ Tuples[#, 2]]] &]]

We would just need to incorporate the metrizability condition, but I am clueless on how to go about this.

  • 2
    $\begingroup$ This seems to be a query that should go to math.stackexchange.com and not mathematica.statckexchange.com. The former is for mathematics whereas the latter is for Wolfram Research's software Mathematica. $\endgroup$
    – murray
    Aug 14, 2022 at 21:28
  • 1
    $\begingroup$ Well I am interested in the Mathematica code to enumerate $a(n)$. I wouldn’t agree that is suitable for math.stackexchange.com. $\endgroup$
    – user227351
    Aug 14, 2022 at 21:33
  • 1
    $\begingroup$ I agree that this is suited for Mathematica stackexchange; it may involve some mathematical content, but it is explicitly asking for efficient Mathematica code to count certain mathematical structures. However, I will say that it seems quite difficult, given that there is so far not any code to do so. But it is interesting! I'd suggest breaking it down into smaller questions to attract more attention, but to be honest, I'm not totally sure how one would do that. It might just be a hard problem, period. $\endgroup$
    – thorimur
    Aug 17, 2022 at 3:53
  • $\begingroup$ Agreed. It certainly is quite a hard problem. $\endgroup$
    – user227351
    Aug 17, 2022 at 11:58
  • 1
    $\begingroup$ Mathematica has functionality for determining whether there exist solutions to certain equations and inequalities; asking for the existence of a metric is equivalent to asking for a solution to a system of equations and inequalities in $n(n-1)/2$ variables (one for each nonzero distance value), in the worst case. I imagine "brute forcing" this means taking advantage of those symbolic functionalities. $\endgroup$
    – thorimur
    Aug 19, 2022 at 17:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.