# Uniformly Converging Metrization of Uniform Structure

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.

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

Find $$m maximal such that $$\sum_{i. (It may be the case that $$m=0$$.) Note that since $$m$$ is chosen maximally, it must also be the case that $$\sum_{m. 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 and $$f(z_{m+1},z_k) \leq \beta f_{k-m-1}(z_{m+1},z_k) \leq \beta \sum_{m

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$$

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

• This is excellent. Thank you very much. One thing though is that I needed $\beta \leq 2$ to prove the inequality $f(x,y) \leq \beta d(x,y)$, which you use in the third and second to last paragraphs. (I'll edit my question to include the proof.) I don't need the case $2 < \beta < 3$, but I'm worried that $3$ might not be optimal. – James Hanson Mar 11 '19 at 15:19
• @JamesHanson: and thank you for the interesting question and for spotting my hasty assumption. I've changed my claims accordingly and moved all remarks about the $\beta>2$ case to the end. – Dap Mar 12 '19 at 0:10