This is related to trying to resolve the currently faulty second part of my answer to [this](https://mathoverflow.net/questions/229303/hyperimaginaries-and-continuous-logic/325027#325027) 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](https://core.ac.uk/download/pdf/33363438.pdf) 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](https://core.ac.uk/download/pdf/33363438.pdf) 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$



Uniformly Converging Metrization of Uniform Structure
$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).$


