Let $\left(U, d\right)$ be a finite [ultrametric space](https://en.wikipedia.org/wiki/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](https://www.maa.org/sites/default/files/pdf/upload_library/22/Hasse/00029890.di021346.02p0064l.pdf). 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:


* [Darij Grinberg, Fedor Petrov, *A greedoid and a matroid inspired by Bhargava's p-orderings*, arXiv:1909.01965v3](https://arxiv.org/abs/1909.01965v3).


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:


* [Darij Grinberg, *The Bhargava greedoid as a Gaussian elimination greedoid*](https://darijgrinberg.gitlab.io/algebra/greedrepv2.pdf).



Greedy simplices in an ultrametric space (generalized Bhargava $p$-orderings)
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. 


