3
$\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.

$\endgroup$
  • 2
    $\begingroup$ both claims are true for 2 or 3 vertices (checked by hands with few cases) $\endgroup$ – Fedor Petrov Oct 30 '18 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$ – Fedor Petrov Oct 30 '18 at 7:06
1
$\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$
  • $\begingroup$ This is beautiful! And the exchange lemma reminds me even more of matroids (or greedoids, for $n$-simplices are not just subsets). $\endgroup$ – darij grinberg Oct 30 '18 at 16:15
  • $\begingroup$ For me too, also I do not know what are greedoids:) $\endgroup$ – Fedor Petrov Oct 30 '18 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$ – darij grinberg Oct 30 '18 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$ – darij grinberg Oct 30 '18 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$ – Fedor Petrov Oct 30 '18 at 17:13

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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