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$


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

  • $\begingroup$ 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. $\endgroup$ Mar 11, 2019 at 15:19
  • $\begingroup$ @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. $\endgroup$
    – Dap
    Mar 12, 2019 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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