Uniformly Converging Metrization of Uniform Structure

Question

This is related to trying to resolve the currently faulty second part of my answer to this question, but is by itself a purely real analysis question.

Let $X$ be a set with a uniform structure presented by a function $f:X^2 \rightarrow [0,1]$ satisfying the following conditions:

• $f(x,x) = 0$
• $f(x,y) = f(y,x)$
• For some fixed parameter $1 < \beta \leq 2$, $f(x_0,x_3)\leq \beta \max(f(x_0 ,x_1 ),f(x_1 ,x_2),f(x_2,x_3))$.

It's clear that the sets $\{(x,y)\in X^2 : f(x,y) < \varepsilon\}$ generate a (pseudo-)uniformity on the set $X$. (I say 'pseudo-' because we haven't guaranteed that points are separated by $f$ but it's not really important for this question.)

Let $f_1(x,y) = f(x,y)$ and for $k>1$, let

$$f_k(x,y) = \inf_{z_1,\dots,z_{k-1}} f(x,z_1)+f(z_1,z_2) + \dots + f(z_{k-1},y) .$$

It's clear that $f_k(x,x)=0$, $f_k(x,y)=f_k(y,x)$, and $0\leq f_{k+1}(x,y)\leq f_k(x,y) \leq f(x,y) \leq 1$. This last one implies that the sequence $f_k(x,y)$ is monotonically decreasing and bounded from below and so converges for any $x,y$. Let $d(x,y)=\lim_{k\rightarrow \infty}f_k(x,y)$. It's clear that $d(x,x)=0$, $d(x,y)=d(y,x)$, and $0 \leq d(x,y) \leq f_k(x,y) \leq 1)$. It's also fairly clear that $d(x,y)$ obeys the triangle inequality so in particular it is a pseudo-metric.

You can show with an argument similar to the one around page 16 of this document (page 18 according to the pdf) that $\beta^{-1} f(x,y) \leq d(x,y) \leq f(x,y)$, so $d(x,y)$ induces the same (pseudo-)uniform structure on $X$ as $f$ does. (In the document $\beta = 2$.)

What would allow me to resolve the other question is the sequence $f_k$ converging uniformly. I've gone back and forth on how I feel it's going to turn out for a while now but I can neither prove it nor provide a counterexample. So the question is

Under what conditions does the sequence $f_k$ converge uniformly?

The best I've been able to do is under the assumption that $\beta < \sqrt{2}$ which ends up implying that the chains witnessing the values of $f_k(x,y)$ are very 'clumpy' in that there's a single $f(z_i,z_{i+1})$ which accounts for 'most' of the value of $f_k(x,y)$, but the bound on $f_{k+1}$ in terms of $f_k$ I can compute from this seems to be too marginal to get uniform convergence.

---

EDIT: This is adapted from this document.

Lemma. If $1 < \beta \leq 2$ then $f(x,y) \leq \beta d(x,y)$.

Proof. We will show that $f(x,y) \leq \beta f_k(x,y)$ for every $k$.

Clearly this is true for $f_1(x,y)=f(x,y)$, since $\beta >1$. Assume that we have shown this result for all $\ell<k$.

Let $z_1,\dots,z_{k-1}$ be some chain and let $z_0 = x$ and $z_k = y$. Let $r=\sum_{i<k} f(z_i,z_{i+1})$.

Find $m<k$ maximal such that $\sum_{i<m} f(z_i,z_{i+1}) \leq \frac{r}{2}$. (It may be the case that $m=0$.) Note that since $m$ is chosen maximally, it must also be the case that $\sum_{m<i<k} f(z_i,z_{i+1})\leq \frac{r}{2}$. Also it's certainly the case that $f(z_m,z_{m+1})\leq r$. By the induction hypothesis $$f(z_0,z_m)\leq \beta f_m(z_0,z_m) \leq \beta \sum_{i<m} f(z_i,z_{i+1})\leq \beta \frac{r}{2}$$ and $$ f(z_{m+1},z_k) \leq \beta f_{k-m-1}(z_{m+1},z_k) \leq \beta \sum_{m<i<k} f(z_i,z_{i+1}) \leq \beta \frac{r}{2}.$$

So now we can apply the assumed inequality to get $$f(z_0,z_k)\leq \beta \max(f(z_0,z_m),f(z_m,z_{m+1}),f(z_{m+1},z_k)) \leq \beta \max(\beta \frac{r}{2},r).$$

Since $\beta\leq 2$, $\beta\frac{r}{2}\leq r$, so we get $f(x,y)=f(z_0,z_k)\leq \beta r$. Since this is true for any such chain we get $f(x,y)\leq \beta f_k(x,y)$, as required. So by induction this is true for all $k$ and we get $f(x,y) \leq \beta d(x,y)$. $\Box$

Answer 1

$f_k$ converges uniformly for $1\leq\beta\leq 2.$

I will argue that for any $\epsilon>0$ and any path $z_0,z_1,\dots,z_{k-1},z_k,$ there is a sub-path $z_0,z_{i_1},\dots,z_{i_{m-1}},z_k$ such that either $$f(z_0,z_{i_1})+\dots+f(z_{i_{m-1}},z_k)\leq (1+\epsilon)(f(z_0,z_1)+\dots+f(z_{k-1},z_k))\tag{1}$$ and $m$ is bounded by a function of $\epsilon$ and $\beta,$ or $$f(z_0,z_{i_1})+\dots+f(z_{i_{m-1}},z_k)\leq f(z_0,z_1)+\dots+f(z_{k-1},z_k)\tag{2}$$ and $m<k.$ So by induction on $k,$ any path can always be shrunk to satisfy (1) with $m$ bounded.

The following argument helps to analyse the paths.

Lemma. For all $\delta>0$ and all integers $K\geq 3$ there exists $n$ such that for any $r>0$ and any set $A\subseteq [0,r]$ either:

• $A$ can be covered by at most $n$ intervals of total length at most $r\delta,$ or
• $A$ contains a sequence $a_1<\dots<a_K$ such that the maximum step $\max(a_{i+1}-a_i)$ is at most $2(a_K-a_1)/(K-2).$

Proof. By Szemerédi's theorem, for large $N$ the set $A'=\{\lfloor aN/r\rfloor\mid a\in A\}\subseteq\{0,1,\dots,N\}$ has cardinality less than $\delta N/2$ unless $A'$ contains an arithmetic progression $t_1<\dots<t_K.$ In the first case we can cover $A$ by at most $n=\lceil \delta N/2\rceil$ intervals $[rt/N,r(t+1)/N]$ for $t\in A',$ of total length at most $r\delta.$ In the second case we can pick $a_i\in A$ such that $\lfloor a_iN/r\rfloor=t_i.$ Let $d$ be the step size of $\{t_i\}.$ Then $(a_{i+1}-a_i)/(a_K-a_1)\leq (d+1)/((K-2)d)\leq 2/(K-2).$ $\Box$

Take $$r=\sum_{i=0}^{k} f(z_i,z_{i+1})$$ $$A=\{0\}\cup\{\sum_{i=0}^{j} f(z_i,z_{i+1})\mid j\in\{0,1,\dots,k\}\}$$ $$\delta=\epsilon/10$$ and $K=3^d+1$ where $d$ is an integer large enough that $2\beta^{d+1}<3^d-1$ - this uses $\beta<3.$

Let $n$ be the number given by the lemma. Note $n$ is bounded in terms of $\epsilon$ and $\beta.$

The first case to consider is that $A$ can be covered by at most $n$ intervals of total length at most $r\delta.$ We can modify these intervals so they are disjoint and their endpoints lie in $A.$ Form a subpath by removing all the $z_i$ lying in the interior of these intervals. This increases the total by at most $r\beta\epsilon/10$: each interval corresponds to some $z_i,\dots,z_j,$ and we can use the inequality $f(z_i,z_j)\leq \beta d(z_i,z_j)\leq \beta (f(z_i,z_{i+1})+\dots+f(z_{j-1},z_j)).$ This small relative error ensures (1) holds. Since each interval has two endpoints, $m\leq 2n+1.$

The second case is that $A$ contains $a_1<\dots<a_K$ with $\max(a_{i+1}-a_i)\leq 2(a_K-a_1)/(K-2).$ These elements of $A$ correspond to some $z_{j_1},\dots,z_{j_K}$ which must satisfy $f(z_{j_{i+1}},z_{j_i})\leq 2\beta(a_K-a_1)/(K-2)$ (by the inequality used in the previous paragraph). By induction on $D$ for $0\leq D\leq d$ we have $f(z_{j_{i+3^D}},z_{j_i})\leq 2\beta^{D+1}(a_K-a_1)/(K-2).$ Hence $f(z_{j_K},z_{j_1})\leq a_K-a_1.$ This means that removing all the $z_i$ for $j_1<i<j_K$ gives a sub-path satisfying (2).

This gives a uniform bound $f_k(x,y)\leq (1+\epsilon)d(x,y)$ where $k$ depends only on $\epsilon$ and $\beta.$

---

Remarks about the case $\beta>2$:

The argument goes through for $2<\beta<3$ under the extra assumption $f(x,y)\leq \beta d(x,y).$ For $\beta=3$ we can get arbitrarily slow convergence on $X=\mathbb N\times\mathbb Z$ by taking

$$f((n,x),(n',y))=\begin{cases} 0&\text{ if $n=n'$ and $\{x,y\}=\{2k,2k+1\}$ for some $k\in\mathbb Z$}\\ 1&\text{ if $n\neq n'$}\\ \min(1,|x-y|/n)&\text{ otherwise.} \end{cases}.$$ For even $n$ this gives $f_k((n,0),(n,n/2))\geq (n-k)/2$ but $d((n,0),(n,n/2))=1/2.$

I don't know if the convergence is uniform for $2<\beta<3$ without the assumption $f(x,y)\leq \beta d(x,y).$