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: