Are the shortest-Hamiltonian-path, smallest-enclosing-ball, and entrywise $\ell_p$ matrix-norm functionals $g$-metrics of order $n\ge 3$ (for $\ell_p$, $n\ge 2$)?

The paper 'Structure for $g$-Metric Spaces and Related Fixed Point Theorems' (Choi, Kim, and Yang, 2018 preprint, arXiv:1804.03651; published 2022 under the title 'Generalized $G$-metric spaces' in Kyungpook Mathematical Journal 62(4) 773–785) axiomatizes a distance $d(x_0,\dots,x_n)$ of $n+1$ points — a $g$-metric of order $n$, where order 1 is an ordinary metric and order 2 is the Mustafa–Sims $G$-metric — and constructs examples from an ordinary pairwise metric $\delta$: the entrywise $\ell_\infty$ norm of the pairwise-distance matrix is a $g$-metric of every order, and the shortest-Hamiltonian-path construction is a $g$-metric of order 2. The paper explicitly leaves open: (a) whether the shortest-Hamiltonian-path (traveling-salesman-path) functional is a $g$-metric of any order $n\ge 3$ (Remark 2.15(2) of the preprint; the published version lists the construction as Example 2.9(5) with no claim or proof that it is one); (b) whether the diameter of the smallest enclosing ball of the points is a $g$-metric of any order $n\ge 3$ (Remark 2.15(3) of the preprint, Example 2.9(6) of the published version); and, as a companion 'natural question' (Remark 2.13 of the preprint, Remark 2.10(2) of the published version), (c) whether the entrywise $\ell_p$ norm of the pairwise-distance matrix is a $g$-metric for $1<p<\infty$ at any order $n\ge 2$. No resolution of any of these questions is known in the literature to date. The problem is whether each of the three functionals is a $g$-metric of the stated order in every metric space (for (b), every Euclidean datum).

Background

Several attempts have generalized the two-point metric to functions of more points. Gähler's 1963 2-metric line and the related $D$-metric turned out to have foundational defects, and Mustafa and Sims (2006) introduced the $G$-metric: a map $G:\Omega^3\to[0,\infty)$ measuring the 'size' of a triple, with $G(x,y,z)=0$ exactly when $x=y=z$, full permutation symmetry, monotonicity $G(x,x,y)\le G(x,y,z)$, and a triangle-type inequality $G(x,y,z)\le G(x,w,w)+G(y,z,w)$. Choi, Kim, and Yang generalized this to any number of arguments: a $g$-metric of order $n$ on a set $\Omega$ is a map $g:\Omega^{n+1}\to[0,\infty)$ satisfying (g1) positive definiteness, $g(x_0,\dots,x_n)=0$ if and only if $x_0=\cdots=x_n$; (g2) permutation invariance under any permutation of the $n+1$ arguments; (g3) monotonicity, $g(x_0,\dots,x_n)\le g(y_0,\dots,y_n)$ whenever the point set $\{x_i\}$ is a proper subset of $\{y_i\}$; and (g4) a generalized triangle inequality, $g(x_0,\dots,x_s,y_0,\dots,y_t)\le g(x_0,\dots,x_s,w,\dots,w)+g(y_0,\dots,y_t,w,\dots,w)$ for every decomposition $s+t+1=n$ and every $w\in\Omega$. Order 1 is exactly an ordinary metric and order 2 exactly a $G$-metric (Theorem 2.4(2) of the preprint), so the notion genuinely extends both. (The published journal version, which appeared under the title 'Generalized $G$-metric spaces', indexes the same objects by the number of arguments: its 'dimension $n$' takes $n$ arguments, dimension 2 being an ordinary metric, so its open-problem threshold $n\ge 4$ is the same as the preprint's order $n\ge 3$ used here.) The paper's examples start from an ordinary metric $\delta$ on $\Omega$ and build an $(n+1)$-ary functional out of the pairwise distances: the diameter $\max_{i,j}\delta(x_i,x_j)$, the entrywise $\ell_\infty$ norm of the distance matrix $M=[\delta(x_i,x_j)]_{0\le i,j\le n}$, is a $g$-metric of every order. Three further constructions are raised but not settled. (a) The shortest-Hamiltonian-path functional $d(x_0,\dots,x_n)=\min_{\pi}\sum_{i=0}^{n-1}\delta(x_{\pi(i)},x_{\pi(i+1)})$, minimized over all permutations $\pi$ of $\{0,\dots,n\}$: the length of the shortest path visiting each point exactly once, the path variant of the traveling salesman problem, a central problem of operations research and theoretical computer science. This is a $g$-metric of order 2 (the paper's Example 2.14), and Remark 2.15(2) states it is an open problem whether it is a $g$-metric for any $n\ge 3$ (the published version lists the same construction as Example 2.9(5), with no claim or proof that it is a $g$-metric). (b) The smallest-enclosing-ball diameter: for $\Omega\subseteq\mathbb{R}^m$ (ambient dimension $m$) viewed as a data set, $d(x_0,\dots,x_n)$ is the diameter of the smallest closed ball containing $\{x_0,\dots,x_n\}$ — the functional of Sylvester's 1857 smallest-enclosing-circle problem from computational geometry; Remark 2.15(3) states it is an open problem whether this is a $g$-metric for any $n\ge 3$ (Example 2.9(6) of the published version, stated there as an open problem for dimension $n\ge 4$). (c) The entrywise $\ell_p$ norms $\|M\|_p=(\sum_{i,j=0}^{n}\delta(x_i,x_j)^p)^{1/p}$ for $1<p<\infty$, posed in Remark 2.13 as a 'natural question' (Remark 2.10(2) of the published version) since the $p=\infty$ endpoint is settled. The shortest-Hamiltonian-path and smallest-enclosing-ball functionals are multiplicity-independent — their value depends only on the underlying set of distinct points, not on how often a point repeats among the arguments — so for them the decisive axiom (g4) reduces to the set inequality $d(A\cup B)\le d(A\cup\{w\})+d(B\cup\{w\})$ for point sets $A,B$ whose tuple sizes sum to $n+1$; the entrywise $\ell_p$ functional is not multiplicity-independent, since repeated arguments contribute repeated terms to the sum $\sum_{i,j}\delta(x_i,x_j)^p$, so for it axiom (g4) must be checked directly on tuples, including tuples with repeated points. The question is whether the relevant form of (g4), together with monotonicity (g3), survives beyond the settled cases. The common scientific objective is to determine which of the metric-induced $n$-ary 'spread' functionals proposed in the source paper actually satisfy the order-$n$ $g$-metric axioms.

Problem Statement

Let $(\Omega,\delta)$ be a metric space and let $n\ge 3$ be an integer (for part (c), $n\ge 2$; the case $n=1$ is trivial). Consider the three functionals $d:\Omega^{n+1}\to[0,\infty)$ induced by $\delta$ and the tuple $(x_0,\dots,x_n)$: (a) the shortest-Hamiltonian-path functional

$$d(x_0,\dots,x_n)=\min_{\pi}\sum_{i=0}^{n-1}\delta(x_{\pi(i)},x_{\pi(i+1)}),$$

where the minimum runs over all permutations $\pi$ of $\{0,\dots,n\}$; (b) the smallest-enclosing-ball diameter, for $\Omega\subseteq\mathbb{R}^m$ with the Euclidean metric ($m\ge 1$ arbitrary): $d(x_0,\dots,x_n)$ is the diameter of the smallest closed ball containing $\{x_0,\dots,x_n\}$; and (c) the entrywise matrix norm

$$d(x_0,\dots,x_n)=\|M\|_p=\Big(\sum_{i,j=0}^{n}\delta(x_i,x_j)^p\Big)^{1/p},\quad 1<p<\infty,$$

where $M=[\delta(x_i,x_j)]_{0\le i,j\le n}$. For each of the three functionals and each order, determine whether $d$ is a $g$-metric of order $n$ in the sense of Definition 2.1 of Choi–Kim–Yang, i.e. whether it satisfies: (g1) $d(x_0,\dots,x_n)=0$ if and only if $x_0=\cdots=x_n$; (g2) $d(x_{\sigma(0)},\dots,x_{\sigma(n)})=d(x_0,\dots,x_n)$ for every permutation $\sigma$ of $\{0,\dots,n\}$; (g3) $d(x_0,\dots,x_n)\le d(y_0,\dots,y_n)$ whenever the point set $\{x_i:i=0,\dots,n\}$ is a proper subset of $\{y_i:i=0,\dots,n\}$; and (g4) $d(x_0,\dots,x_s,y_0,\dots,y_t)\le d(x_0,\dots,x_s,w,\dots,w)+d(y_0,\dots,y_t,w,\dots,w)$ for all $s,t\ge 0$ with $s+t+1=n$ and all $w\in\Omega$, where in each term on the right-hand side the point $w$ is repeated so that the term has $n+1$ arguments in total. The quantifier is: the axioms must hold for all choices of the points in every metric space $(\Omega,\delta)$ (for (b), every $\Omega\subseteq\mathbb{R}^m$ with the Euclidean metric). The common objective uniting the three parts is to decide which of the source paper's proposed metric-induced $n$-ary functionals satisfy the order-$n$ $g$-metric axioms beyond the settled cases (order 2 for (a); all orders for the $p=\infty$ norm (the diameter) in the norm family).

References

1. Hayoung Choi, Sejong Kim, Seung Yeop Yang, 'Generalized $G$-metric spaces', Kyungpook Mathematical Journal 62(4) (2022) 773–785, DOI: 10.5666/KMJ.2022.62.4.773, https://doi.org/10.5666/KMJ.2022.62.4.773
2. Hayoung Choi, Sejong Kim, Seung Yeop Yang, 'Structure for $g$-Metric Spaces and Related Fixed Point Theorems' (2018 preprint; contains the fixed-point material not included in the journal version), arXiv:1804.03651, https://arxiv.org/abs/1804.03651
3. Rasoul Abazari, 'Statistical convergence in g-metric spaces' (2021), arXiv:2103.05527, https://arxiv.org/abs/2103.05527
4. Saime Kolancı, Mehmet Gürdal, 'On Ideal Convergence in Generalized Metric Spaces', Dera Natung Government College Research Journal 8 (2023) 81–96, DOI: 10.56405/dngcrj.2023.08.01.06, https://doi.org/10.56405/dngcrj.2023.08.01.06
5. Mohamed Jleli, Cristina Maria Pacurar, Bessem Samet, 'New directions in fixed point theory in $G$-metric spaces and applications to mappings contracting perimeters of triangles' (2024), arXiv:2405.11648, https://arxiv.org/abs/2405.11648
6. Kamran Alam Khan, 'Generalized $n$-metric spaces and fixed point theorems' (2018), arXiv:1809.08997, https://arxiv.org/abs/1809.08997
7. Kamran Alam Khan, 'Banach and Suzuki-type fixed point theorems in Generalized $n$-metric spaces with an application' (2021), arXiv:2108.05194, https://arxiv.org/abs/2108.05194
8. Zead Mustafa, Brailey Sims, 'A new approach to generalized metric spaces', Journal of Nonlinear and Convex Analysis 7(2) (2006) 289–297, zbMATH Zbl 1111.54025, https://zbmath.org/?q=an%3A1111.54025
9. J. J. Sylvester, 'A question in the geometry of situation', Quarterly Journal of Pure and Applied Mathematics 1 (1857) 79