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

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 $$$$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) .$$$$ 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:

• both claims are true for 2 or 3 vertices (checked by hands with few cases) Oct 30, 2018 at 6:39
• 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$. Oct 30, 2018 at 7:06

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, where the last inequality follows from the greedy procedure.

• This is beautiful! And the exchange lemma reminds me even more of matroids (or greedoids, for $n$-simplices are not just subsets). Oct 30, 2018 at 16:15
• For me too, also I do not know what are greedoids:) Oct 30, 2018 at 16:20
• 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? Oct 30, 2018 at 16:23
• Also, probably a non-equivalent questions: Do the greedy $m$-simplices regarded as sets form the bases of a matroid? Oct 30, 2018 at 16:28
• Maximum perimeter sets of given size are bases of a matroid, this follows from the exchange lemma, does not it? Oct 30, 2018 at 17:13