5
$\begingroup$

Let $\left(U, d\right)$ be a finite ultrametric space -- that is, $U$ is a finite set, and $d : U \times U \to \mathbb{R}_{\geq 0}$ is a metric on $U$ such that every $x, y, z \in U$ satisfy $d\left(x, z\right) \leq \max\left\{d\left(x,y\right), d\left(y,z\right)\right\}$ (in words: in any triangle, the longest two sides have the same length).

Fix $n \in \mathbb{N}$. An $n$-simplex shall mean an $\left(n+1\right)$-tuple $\left(u_0, u_1, \ldots, u_n\right)$ of elements of $U$. The sum-sequence of an $n$-simplex $\left(u_0, u_1, \ldots, u_n\right)$ shall mean the $n$-tuple $\left(s_1, s_2, \ldots, s_n\right) \in \mathbb{R}^n$, where $s_i = d\left(u_0, u_i\right) + d\left(u_1, u_i\right) + \cdots + d\left(u_{i-1}, u_i\right)$ for each $i\in \left\{1,2,\ldots,n\right\}$.

An $n$-simplex $\left(u_0, u_1, \ldots, u_n\right)$ is said to be greedy if and only if every $i \in \left\{1,2,\ldots,n\right\}$ and $v \in U$ satisfy \begin{equation} d\left(u_0, u_i\right) + d\left(u_1, u_i\right) + \cdots + d\left(u_{i-1}, u_i\right) \geq d\left(u_0, v\right) + d\left(u_1, v\right) + \cdots + d\left(u_{i-1}, v\right) . \end{equation} Intuitively speaking, a greedy $n$-simplex is what you get if you try to construct an $n$-simplex with the lexicographically largest possible sum-sequence by first picking any $u_0 \in U$, then picking any $u_1 \in U$ maximizing $d\left(u_0, u_1\right)$ (with $u_0$ already fixed), then picking any $u_2 \in U$ maximizing $d\left(u_0, u_2\right) + d\left(u_1, u_2\right)$, etc.. Note that there are many choices in this construction. Nevertheless, I suspect the following:

Conjecture 1. Any two greedy $n$-simplices have the same sum-sequence.

This would generalize Theorem 5 in Manjul Bhargava, The Factorial Function and Generalizations, The American Mathematical Monthly, Vol. 107, 2000, pp.783-799. Indeed, the set $S$ in that paper can be regarded as an ultrametric space (with the metric defined by $d\left(s, t\right) = p^{- v_p\left(s-t\right)}$, as usual), and then the $p$-orderings would be exactly the greedy $\infty$-simplices. (For the pedants: Of course, $S$ is not finite, and $\infty \notin \mathbb{N}$; but it is easy to reduce the claims to the case of finite $U$ and finite $n$.)

If Conjecture 1 holds, then the sum-sequence of any $n$-simplex is lexicographically $\leq$ to the sum-sequence of any greedy $n$-simplex. This makes me wonder if we can say something stronger:

Conjecture 2. Let $\left(t_1, t_2, \ldots, t_n\right)$ be the sum-sequence of any $n$-simplex, and let $\left(s_1, s_2, \ldots, s_n\right)$ be the sum-sequence of any greedy $n$-simplex. Then, $t_1 + t_2 + \cdots + t_i \leq s_1 + s_2 + \cdots + s_i$ for any $i \in \left\{0,1,\ldots,n\right\}$.

Note that proving this for $i = n$ is enough, because the first $i+1$ entries of a greedy $n$-simplex always form a greedy $i$-simplex. So Conjecture 2 is tantamount to saying that the perimeter of a greedy $n$-simplex (i.e., the sum of its edge-lengths) is $\geq$ to the perimeter of any $n$-simplex. In other words, the greedy algorithm succeeds in maximizing the perimeter.

I regret to say I have not thought much about this, as I am currently completely swamped between teaching, job hunting and some risible pretense of research. But the most obvious things don't work: Bhargava's proof for his Theorem 5 is number-theoretical and doesn't generalize. I know that we can define an equivalence relation $\sim$ on $U$ by letting $x \sim y$ if $x = y$ or $d\left(x, y\right)$ is the smallest nonzero value of $d$, and I know that any permutation of $U$ that preserves $\sim$ is an automorphism of the metric space $\left(U, d\right)$. I thought of replacing $U$ by $U / \sim$, but so far I don't really see how to translate things to the quotient. I am tagging this "matroid-theory" just in case, but I don't myself see how to reduce the above greedy algorithm to that of a matroid.

I wouldn't be surprised if this has practical applications: An ultrametric space $\left(U, d\right)$ can be viewed as a nested sequence of set partitions of $U$ (i.e., a set partition, then another that refines it, then another that refines it further, and so on), so some sort of classification at several levels of fine-grainedness. An $n$-simplex of maximum perimeter would then be a way to sample $n$ data points that are "as representative as possible of the whole population", in the sense of not being closer to each other than necessary.

EDIT: Note: Some of what I wrote in this post is false. The metric on the set $S$ in Bhargava's paper has to be defined by $d\left(s,t\right) = -v_p\left(s,t\right)$ (not by $d\left(s,t\right) = p^{-v_p\left(s,t\right)}$) in order for the $p$-orderings to be the greedy $\infty$-simplices. This requires slightly generalizing the definition of a metric: Instead of being a map to $\mathbb{R}_{\geq 0}$, it now has to be a map to $\mathbb{R} \cup \left\{-\infty\right\}$ which takes the value $-\infty$ only at pairs of the form $\left(a,a\right)$. This is no longer a metric in the proper sense of this word, but just a symmetric map on $U \times U$ that satisfies $d\left(x, z\right) \leq \max\left\{d\left(x,y\right), d\left(y,z\right)\right\}$. Soon, a preprint by Fedor Petrov and myself will come out which discusses these issues in greater detail.

EDIT2: The preprint is out:

It incorporates both Fedor's answer to this question and the conversation we had in the chat afterwards, and more. A followup paper is in the process of being written:

$\endgroup$
2
  • 2
    $\begingroup$ both claims are true for 2 or 3 vertices (checked by hands with few cases) $\endgroup$ Oct 30, 2018 at 6:39
  • $\begingroup$ Well, without cases and possibly generalizable: it suffices to prove that the greedy simplex $(u_0,u_1)$ or $(u_0,u_1,u_2)$ maximizes the sum of mutual distances. If $d_1=d(u_0,u_1)$, then the whole $U$ is covered by a ball of radius $d_1$ centered in $u_0$, thus have diameter at most $d_1$. Next, if we denote $d_2=\min(d(u_2,u_0),d(u_2,u_1)))$ (of course $\max(d(u_2,u_0),d(u_2,u_1)))=d_1$), the whole $U$ is covered by two balls of radius $d_2$ centered in $u_0,u_1$, thus by pigeonhole principle any triangle has a side of length at most $d_2$, and two others are at most $d_1$. $\endgroup$ Oct 30, 2018 at 7:06

1 Answer 1

2
$\begingroup$

It looks that both claims are true.

For $V\subset U$ denote by $f(V)$ the sum of mutual distances between elements of $V$.

Exchange lemma. Let $V\subset U$ and $v\in U$, and let $w$ be a projection of $v$ on $V$ (that is, a point in $V$ that is closest to $v$). Then, $f(V\cup v\setminus w)\geqslant f(V)$ and $d(v,x)\geqslant d(w,x)$ for any $x\in V$.

Proof. If the latter inequality fails for some $x\in V$, we have $d(w,x)>d(v,x)\geqslant d(v,w)$, a contradiction to the ultra-triangle inequality for $\triangle vxw$. Summing up $d(v,x)\geqslant d(w,x)$ by $x\in V\setminus w$ we get $f(V\cup v\setminus w)\geqslant f(V)$.

Not we prove that for a greedy simplex $S=\{v_0,\dots,v_m\}$ we have $$f(S)\geqslant f(T)\,\,\,\,(\star)$$ for any $T\subset V$, $|T|=m+1$. This implies both of your conjectures.

We do this by choosing consecutively elements $u_0,u_1,\dots\in T$ such that $u_i$ is a projection of $v_i$ on $T\setminus \{u_0,\dots,u_{i-1}\}$. Then by the exchange lemma we have $d(v_i,u_j)\geqslant d(u_i,u_j)$ whenever $j>i$ (since $u_j \in T\setminus \{u_0,\dots,u_{i-1}\}$). Summing this by all pairs $j>i$ we get $f(T)\leqslant \sum_{i<j} d(v_i,u_j)=\sum_j \sum_{i<j} d(v_i,u_j)\leqslant \sum_j \sum_{i<j} d(v_i,v_j)=f(S)$, where the last inequality follows from the greedy procedure.

$\endgroup$
13
  • $\begingroup$ This is beautiful! And the exchange lemma reminds me even more of matroids (or greedoids, for $n$-simplices are not just subsets). $\endgroup$ Oct 30, 2018 at 16:15
  • $\begingroup$ For me too, also I do not know what are greedoids:) $\endgroup$ Oct 30, 2018 at 16:20
  • 1
    $\begingroup$ Greedoids, at least defined as in Section 1 of A. Bjorner, L. Lovasz, P. W. Shor, Chip-firing games on graphs, are something like a noncommutative analogue of matroids (in the sense that independent sets have become independent tuples). Anyway, forget about greedoids for now: The greedy simplices don't form a greedoid (it's not locally free). But maybe the $m$-element subsets with maximum perimeter are the bases of a matroid? $\endgroup$ Oct 30, 2018 at 16:23
  • 1
    $\begingroup$ Also, probably a non-equivalent questions: Do the greedy $m$-simplices regarded as sets form the bases of a matroid? $\endgroup$ Oct 30, 2018 at 16:28
  • $\begingroup$ Maximum perimeter sets of given size are bases of a matroid, this follows from the exchange lemma, does not it? $\endgroup$ Oct 30, 2018 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.