Discussion on Lecture 09

Peer Kunstmann, 2023/01/12 10:15

Dear virtual lecturers,

some typos:

p. 106, l.-14: function
p. 108, l.3 of Remark 7.5: there exists a path
p. 110, l.4: set (as f and t are fixed)

Best, Peer

Christian Seifert, 2023/01/17 10:13

Dear Peer,

Many thanks!

Best, Christian

Peer Kunstmann, 2023/01/12 10:02, 2023/01/12 10:04

Dear virtual lecturers,

thank you very much for the lecture.

What is called a pseudometric on p. 105 is what I would call a semimetric (in analogy to seminorm, see the comment on $Q^{1 / 2}$ ) as $\infty$ is excluded as a value ( $ϱ$ has values in $[0, \infty)$ ).

On the other hand, I wonder if you really wanted to exclude $\infty$ as a value, since $d_{c o m b}$ in Remark 7.5 only has finite values if the graph is connected, which is not assumed there.

Another question: The inequality on p. 107, l.2 and in Remark 7.6 on p. 108 is also true with $\leq \frac{1}{2} m (K)$ instead of $\leq m (K)$ . Is there a reason for omitting the factor $\frac{1}{2}$ ? But without $\frac{1}{2}$ , the sentence ``A pseudometric is then intrinsic if its 1-Lipschitz functions satisfy this inequality.'' might be wrong.

Best regards, Peer

Christian Seifert, 2023/01/17 10:11

Dear Peer,

Many thanks. Concerning pseudometrics, there are different versions in the literature (including the value $\infty$ or not). For us, we can safely include the value $\infty$ here.

Concerning the factor $\frac{1}{2}$ , you are right. We have added the factor accordingly.

Best, Christian

Kai Jennissen, 2023/01/05 18:49, 2023/01/05 19:51

Dear virtual lecturers,

I think the second property of the function $f$ on bottom of page 114 does not hold for arbitrary (psuedo)metrics. $f |_{B_{2 r} ∖ B_{r}} = e^{β (r - ϱ_{B_{r} (o)} (\cdot))} - 1$ is true if and only if the exponent is greater or equal to zero. Since $β > 0$ this is the case if $ϱ_{B_{r} (o)} (y) \leq r$ for all $y \in B_{2 r} ∖ B_{r}$ . While this seems to holds intuitively I think it's only only true in case of a vector spaces with a metric induced by a norm and not for general metrics.

Let $X$ be a countable set then I think the following are counterexamples:

Let $ρ$ be the discrete metric, $r = 1 / 2$ and $o \in X$ . Then $B_{r} (o) = o$ , $B_{2 r} (o) = X$ and $ρ (o, x) = 1 > 1 / 2 = r$ for all $x \neq o$ .
Let $ρ := d_{c o m b}$ , $r = 3 / 2$ , $o \in X$ . Let $x \in B_{2 r} (o)$ such that the shortest path to $o$ has length $3$ , i.e. $o = x_{1} \sim x_{2} \sim x_{3} = x$ . Then $x_{1} \in B_{r} (o)$ and $ρ (x_{1}, x_{3}) = 2 > 3 / 2 = r$ . Furthermore by definition of $ρ$ there is no shorter path between $o$ and $x$ and therefore the shortest path between $x_{1}$ and $x_{3} = x$ has length 2, i.e. every $ρ (y, x_{3}) = 2 > 3 / 2 = r$ for all $y \in B_{r} (o)$

Or am I missing something?

By defining $f$ as: $f (x) = {(m i n {e^{β r}, e^{β (r - ϱ (o, x)}} - 1)}_{+}$ we get a function with the required properties.

Kind Regards,

Kai

Matthias Keller, 2023/01/17 12:56

Dear Kai,

Thank you very much for this keen observation. You are right, in metric spaces one only has $B_{r} (B_{r} (o)) \subseteq B_{2 r} (o)$ but not necessarily equality.

The argument in the lecture notes can be fixed by doing the case distinctions for the properties of $f$ and $g$ and in Lemma 7.15 (a) with respect to $B_{r} (B_{r} (o))$ instead of $B_{2 r} (o)$ . (For the properties of $g$ one gets an additional case on the set $B_{2 r} (o) ∖ B_{r} (B_{r} (o))$ but this does not matter in the proof.)

These changes will be included in the final version of the lecture notes.

Best and thanks again

Matthias

Anna Muranova, 2023/01/01 17:43, 2023/01/01 17:44

Dear all,

shouldn't there be additional assumptions in Exercise 1?

If we consider the tree with just two vertices $v_{1}, v_{2}$ from the $r o o t$ , then using the function $f (r o o t) = 1$ , $f (v_{1}) = 1$ , $f (v_{2}) = 0$ , we have $f \in A_{1}$ and, therefore, $σ (r o o t, v_{2}) \geq 1 > 1 / \sqrt{2}$ , while $d_{c o m b} (r o o t, v_{2}) = 1$ . Moreover, we can add infinite amount of vertices, whose precessor would be $v_{1}$ with $f = 1$ and the same with $v_{2}$ and $f = 0$ .

What am I doing wrong here?

Best, Anna

Tim Schmatzler, 2023/01/11 23:39, 2023/01/12 12:58

Dear Anna,

I think you are right, and that the equality $σ (x, y) = d_{comb} (x, y) / \sqrt{2}$ holds only when the distance is even. For $d (x, y) = 3$ , I believe I have shown that $σ (x, y) = \sqrt{5} > 3 / \sqrt{2}$ and for $d (x, y) = 5$ , I suspect it is $σ (x, y) = \sqrt{13}$ . But I might be mistaken and will need to check my work tomorrow; also, I think the method generalizes to give a formula for general $d (x, y)$ odd.

Best regards,

Tim

Marcel Schmidt, 2023/01/17 11:33

Dear Anna and Tim,

One has to assume connectedness of the graph, which seems to be missing in the exercise. The constant $1 / \sqrt{2}$ is wrong, we have $σ (x, y) = d_{c o m b} (x, y)$ on trees with standard weights and counting measure.

The upper bound (which Tim disputed) can be seen as follows: Let $f$ be function with $| \nabla f |^{2} \leq 1$ . For $x \sim y$ this implies

$| f (x) - f (y) | = {(| f (x) - f (y) |^{2})}^{1 / 2} \leq {(\sum_{z \sim x} | f (x) - f (z) |^{2})}^{1 / 2} = | \nabla f | (x) \leq 1.$

Now take a path $(x_{0}, \dots, x_{n})$ from $x$ to $y$ . Using the previous inequality yields

$| f (x) - f (y) | \leq \sum_{i = 0}^{n - 1} | f (x_{i}) - f (x_{i + 1}) | \leq n .$

Since the path was arbitrary, this implies $| f (x) - f (y) | \leq d_{c o m b} (x, y)$ . So far we have not used the tree structure at all, it is used for establishing the opposite inequality (which we still leave as an exercise).

Our mistake comes from different conventions in the literature and putting the constant on the wrong side of the equation. Sometimes

$\sum_{y \sim x} | f (x) - f (y) |^{2}$

and sometimes

$\frac{1}{2} \sum_{y \sim x} | f (x) - f (y) |^{2}$

is denoted as $| \nabla f |^{2} (x)$ . The first convention is the one used in our lecture notes and leads to $σ = d_{c o m b}$ on trees.

With the latter convention one obtains $σ = \sqrt{2} d_{c o m b}$ on trees (which is still not the identity claimed in the exercise, we put the constant on the wrong side ;)).

Best, Marcel

Patrizio Bifulco, 2023/01/17 18:57, 2023/01/17 19:02

Dear Anna, dear Marcel and dear Tim

I am wondering whether the constant $\frac{1}{\sqrt{2}}$ is wrong for even combinatorial distances (as Tim already suggested).

Indeed, if $x, y \in X$ and $x = x_{0}, \dots, x_{n} = y$ is some path from $x$ to $y$ . Then for $f \in A_{1} (X)$ one can estimate using Cauchy-Schwarz:

$\begin{aligned} (f (x) - f (y))^{2} & = (\sum_{k = 0}^{n - 1} f (x_{k}) - f (x_{k + 1}))^{2} \\ \leq n \sum_{k = 0}^{n - 1} (f (x_{k}) - f (x_{k + 1}))^{2} \\ = n \sum_{k = 0}^{\frac{n}{2} - 1} \underset{\leq | \nabla f |^{2} (x_{2 k + 1}) \leq 1}{\underset{⏟}{(f (x_{2 k}) - f (x_{2 k + 1}))^{2} + (f (x_{2 k + 1}) - f (x_{2 (k + 1)}))^{2}}} \\ \leq n \cdot \frac{n}{2} = \frac{n^{2}}{2}, \end{aligned}$ so we reach at $f (x) - f (y) \leq \frac{n}{\sqrt{2}}$ .

For odd combinatorial distances I would guess (as Tim also already did) that $σ (x, y) = \sqrt{\frac{d_{c o m b} (x, y)^{2} + 1}{2}}$ but I did not check it myself yet.

Overall, it seems that the upper bound $n$ may be not sharp enough. What do you think, maybe I am getting wrong somewhere?

Best wishes, Patrizio

Maximilian Weinberg, 2023/01/19 12:29, 2023/01/19 12:37

Dear all,

I could confirm Tim's and Patrizio's guess that $σ = \sqrt{\frac{n^{2} + 1}{2}}$ in the case where $n$ is odd.

To see this, one can show that, if $f$ maximizes the difference $f (x_{n}) - f (x_{0})$ , we must have $| \nabla f | (x_{k}) = 1$ for $1 \leq k \leq n - 1$ . This implies that the differences $d_{k} = f (x_{k + 1}) - f (x_{k})$ have to alternate between two values.

One can then use Lagrange multipliers to find a maximizing pair $(d_{0}, d_{1})$ . This gives the above result for odd $n$ . When $n$ is even, the value given in the original exercise is confirmed.

Kind regards,

Max

Marcel Schmidt, 2023/01/25 10:48

Dear all,

sorry for my late reply. You are indeed correct, one has to distinguish between even and odd combinatorial distances.

When I wrote my last comment I believed our exercise was stated correctly with possibly a wrong constant. Hence, I just looked for the constant and did not see true mistake.

Best Marcel

Patrizio Bifulco, 2022/12/24 01:00, 2022/12/24 01:08

Dear virtual lecturers,

thank you very much for another very interesting lecture. Here are some minor remarks/typos:

On page 106 right after Definition 7.1 it should probably read 'we note that differentiable functions […]' (without 'a').
On page 107 in the proof of Lemma 7.2 (iii) $⟹$ (i) in the first displayed formula, I think it should be $| \nabla ϱ (o, \cdot) | (o)^{2}$ instead of $| \nabla ϱ (o, \cdot) | (x)^{2}$ .
In Example 7.3 there is a bracket missing after $x_{i - 1}$ and one to much after $x_{i}$ in the definition of $ρ (x, y)$ .
On page 111 where you recall the Cauchy-Schwarz inequality, there should be a $G$ (instead of $F$ ) in the second term of the right-hand side.
At the bottom of page 114, in the second property of $f$ , shouldn't it read $f |_{B_{2 r} ∖ B_{r}} = e^{β (r - ϱ_{B_{r} (o)} (\cdot))} - 1$ (instead of $f |_{B_{2 r} ∖ B_{r}} = e^{β (r - ϱ (B_{r} (o), \cdot))} - 1$ )?
Right after, in the first property of $g$ , I think there is a $+ 1$ missing on the right-hand side.
A last very minor (and therefore hardly worth mentioning) “typo”: In Case 3 of the proof for Lemma 7.15(a) right before part (b), you used a different $ϱ$ (namely $ρ$ ) than before.

I am very looking forward to next year's lectures!

Kind regards, Patrizio

Christian Seifert, 2023/01/02 10:40

Dear Patrizio,

Many thanks. We will correct the mistakes/typos.

Best, Christian

Kai Jennissen, 2022/12/19 11:01

Dear virtual lecturers,

thank you very much for the lecture.

In the proof of Th. 7.8 it is shown that $\frac{h^{2}}{2} \leq \frac{Q (φ)}{| | φ | |^{2}}$ for all $φ \in C_{C} (X)$ . I do not see how this result is extended to $D (Q)$ which is used in the variational characterization of $λ_{0} (L)$ ?

Kind regards, Kai

Marcel Schmidt, 2022/12/21 12:15

Dear Kai,

in the Theorem $Q$ is the form $Q_{b, 0, m}^{(D)}$ , whose domain is defined as the closure of $C_{c} (X)$ with respect to the norm $f \mapsto \sqrt{Q (f) + ‖ f ‖^{2}}$ . Thus, for each $f \in D (Q)$ there exists a sequence $(φ_{n})$ in $C_{c} (X)$ such that $| Q (φ_{n})^{1 / 2} - Q (f)^{1 / 2} | \leq Q (φ_{n} - f)^{1 / 2} \to 0$ and $φ_{n} \to f$ in $ℓ^{2} (X, m)$ . Hence, it suffices to show the estimate on $C_c(X).

Best, Marcel

Kai Jennissen, 2022/12/21 18:17, 2022/12/22 14:59

Thanks. Since the inequality holds for every element of the sequence $Q (φ_{n})$ it also holds for $Q (f)$ since $Q (φ_{n} \to Q (f)$ , which complets the proof of Th. 7.8.

Am I right that $| Q (φ_{n})^{\frac{1}{2}} - Q (f)^{\frac{1}{2}} | \leq Q (φ_{n} - f)^{\frac{1}{2}}$ follows since

$\begin{aligned} 0 \leq {(Q (φ_{n})^{\frac{1}{2}} - Q (f)^{\frac{1}{2}})}^{2} & = Q (φ_{n}) - 2 Q (φ_{n})^{\frac{1}{2}} Q (f)^{\frac{1}{2}} + Q (f) \\ \leq Q (φ_{n}) - 2 Q (φ_{n}, f) + Q (f) = Q (φ_{n} - f) \end{aligned}$ where I've used $\begin{aligned} Q (f, g) = ⟨ f, L g ⟩ & = ⟨ L^{\frac{1}{2}} f, L^{\frac{1}{2}} g ⟩ \\ \leq | | L^{\frac{1}{2}} f | | | | L^{\frac{1}{2}} g | | \\ = ⟨ L^{\frac{1}{2}} f, L^{\frac{1}{2}} f ⟩^{\frac{1}{2}} ⟨ L^{\frac{1}{2}} g, L^{\frac{1}{2}} g ⟩^{\frac{1}{2}} \\ = ⟨ f, L f ⟩^{\frac{1}{2}} ⟨ g, L g ⟩^{\frac{1}{2}} \\ = Q (f)^{\frac{1}{2}} Q (g)^{\frac{1}{2}} \end{aligned}$

Kind Regards, Kai

Marcel Schmidt, 2023/01/04 10:19

Dear Kai,

the inequality follows from $Q^{1 / 2}$ being a seminorm, which is a consequence of $(f, g) \mapsto Q (f, g)$ being a semi-scalar product.

Best, Marcel

Kai Jennissen, 2023/01/07 11:12

Thanks. I didn't notice that but it makes thinks easier.

Best, Kai

ISem26

Sidebar

Discussion on Lecture 09

Discussion on Lecture 09