Greedy simplices in an ultrametric space (generalized Bhargava $p$-orderings)

Question

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:

• Darij Grinberg, Fedor Petrov, A greedoid and a matroid inspired by Bhargava's p-orderings, arXiv: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.

Answer 1

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.