TITLE: Interchanging Derivative and Integral Example
QUESTION [6 upvotes]: In class the other day, my professor stated the following theorem:

Suppose $\frac{d}{dy}f(x,y)$ is continuous on $[0,1] \times [0,1]$, then $\frac{d}{dy} \int^1_0 f(x,y) \, dx = \int_0^1 \frac{d}{dy}f(x,y) \, dx$.

He then quickly corrected this to read:

Suppose $\frac{d}{dy}f(x,y)$ and f are continuous on $[0,1] \times [0,1]$, then $$\frac{d}{dy} \int^1_0 f(x,y) \, dx = \int_0^1 \frac{d}{dy}f(x,y) \, dx.$$

I was wondering if anyone could provide an example of $f$ which satisfies the conditions for the first statement written but not the subsequently added continuity condition from the second statement, and therefore fails the overall implication of the first statement.

REPLY [1 votes]: Implicit in the first statement is the existence of all integrals.
As long as $x \mapsto f(x,y)$ is integrable for each fixed $y$, then it is sufficient for $f_y$ to be continuous on $[0,1]^2$ to justify differentiating under the integral sign.
With
$$F(y) = \int_0^1 f(x,y) \, dx$$
and $y_0 \in [0,1]$, we have for $y \neq y_0$,
$$\left|\frac{F(y) - F(y_0)}{y - y_0} - \int_0^1 f_y(x,y_0) \, dx\right| = \left|\int_0^1 \left(\frac{f(x,y)- f(x,y_0)}{y - y_0} - f_y(x,y_0) \right) \, dx\right|.$$
Applying the mean value theorem there exists $\xi$ (which may depend on $x$) between $y$ and $y_0$ such that
$$\left|\frac{F(y) - F(y_0)}{y - y_0} - \int_0^1 f_y(x,y_0) \, dx\right| = \left|\int_0^1 \left(f_y(x, \xi) - f_y(x,y_0) \right) \, dx\right| \\ \leqslant \int_0^1 \left|f_y(x, \xi) - f_y(x,y_0) \right| \, dx.$$
By uniform continuity of $f_y$ on the compact set $[0,1]^2$ there exists for any $\epsilon > 0$ a $\delta > 0$ such that $|y - y_0| < \delta $ implies $|f_y(x, \xi) - f_y(x, y_0)| < \epsilon$ and
$$\left|\frac{F(y) - F(y_0)}{y - y_0} - \int_0^1 f_y(x,y_0) \, dx\right| < \epsilon,$$
proving that $F'(y_o) = \int_0^1 f_y(x,y_0) \, dx.$
There is no counterexample that you seek.
In fact, the switch is valid under much weaker conditions. Considering the Lebesgue integral, for example, if $x \mapsto f(x,y)$ is measurable for each $y$ and integrable for at least one $y$,$f_y(x,y_0)$ exists and there exists an integrable function $g$ such that for $x , y \in [0,1]$ and $y \neq y_0$
$$\left|\frac{f(x,y) - f(x,y_0)}{y - y_0}\right| \leqslant g(x)$$
Perhaps, a simple example might convey some intuition why continuity of $f$ itself is not needed.
Take
$$f(x,y) = \begin{cases} 1 + y, \,\,\, 0 \leqslant x \leqslant 1/2, \, 0 \leqslant y \leqslant 1 \\ 2 + y, \,\,\, 1/2 < x \leqslant 1, \, 0 \leqslant y \leqslant 1\end{cases}$$
Then $f_y(x,y) = 1$,
$$F(y) = \int_0^1 f(x,y) \, dx = \frac{3}{2} + y,$$
and
$$F'(y) = 1 = \int_0^1 f_y(x,y) \, dx$$


TITLE: Any suggestions on a rigorous stochastic differential equations book?
QUESTION [3 upvotes]: I have been looking through some books and they are not very rigorous. Any suggestions would be great.

REPLY [3 votes]: There are a lot of good books on the market, maybe you should describe more carefully what you want...
I think the following books don't lack rigor

C. Dellacherie and P.A. Meyer, Probabilités et Potentiel. Ch. I à IV. Hermann, Paris 1975, 290 pages
C. Dellacherie and P.A. Meyer, Probabilités et Potentiel. Ch. V à VIII, Hermann, Paris 1980, 476 pages
C. Dellacherie and P.A. Meyer, Probabilités et Potentiel. Ch IX à XI. Théorie discrète du potentiel. Hermann, Paris 1983, 229 pages
C. Dellacherie and P.A. Meyer, Probabilités et Potentiel. Ch. XII à XVI. Théorie du potentiel associée à une résolvante, théorie des processus de Markov Hermann, Paris 1987, 377 pages
C. Dellacherie, B. Maisonneuve and P.A. Meyer, Probabilités et Potentiel. Ch XVII à XXIV. Processus de Markov (fin). Compléments de calcul stochastique. Hermann, Paris 1992, 429 pages

see http://lmrs.univ-rouen.fr/Ouvrages/potentiel.html for details.
Or, if you want something more "modern", there are for example

D. Applebaum, Lévy Processes and Stochastic Calculus, Cambridge University Press, 2004
P. Protter. Stochastic integration and differential equations, volume 21 of
Stochastic Modelling and Applied Probability. Springer-Verlag, Berlin, 2005
N. Ikeda and S. Watanabe. Stochastic Differential Equations and Diffusion Processes. North-Holland, 1989
G. Di Nunno, B. Øksendal, and F. Proske. Malliavin Calculus for Levy Processes with Applications to Finance. Universitext. Springer-Verlag, Berlin, 2009.


text:
\begin{document}

\title{\large\bf On the cardinality of general $h$-fold sumsets
  \footnote{This work was supported by the National
Natural Science Foundation of China, Grant No. 11371195.}}
\date{}
\author{Quan-Hui Yang$^{1,2}$ and Yong-Gao Chen$^2$
\footnote{Emails:~yangquanhui01@163.com (Q.-H Yang), ygchen@njnu.edu.cn (Y.-G Chen).}\\
\small 1. School of Mathematics and Statistics, \\ \small Nanjing
University of Information Science and Technology,
\\ \small    Nanjing 210044, P. R. CHINA
\\ \small 2. School of Mathematical Sciences and Institute of
Mathematics,
\\ \small Nanjing Normal University,  Nanjing 210023, P. R. CHINA}
\maketitle
\vskip 3mm

\begin{abstract} Let $A=\{a_0,a_1,\ldots,a_{k-1}\}$ be a  set of $k$ integers. For any integer
$h\ge 1$ and any ordered $k$-tuple of positive integers
$\mathbf{r}=(r_0,r_1,\ldots,r_{k-1})$, we define a general
$h$-fold sumset, denoted by $h^{(\mathbf{r})}A$, which is the set
of all sums of $h$ elements of $A$, where $a_i$ appearing in the
sum can be repeated at most $r_i$ times for $i=0,1,\ldots,k-1$. In
this paper, we give the best lower bound for $|h^{(\mathbf{r})}A|$
in terms of $\mathbf{r}$ and $h$ and determine the structure of
the set $A$ when $|h^{(\mathbf{r})}A|$ is minimal. This
generalizes results of Nathanson, and recent results of Mistri and
Pandey and also solves a problem of Mistri and Pandey.

{\it 2010 Mathematics Subject Classification:} 11B13.

{\it Keywords and phrases:} $h$-fold sumsets, arithmetic progression, direct and inverse problems.

\end{abstract}

\section{Introduction}\label{b}
Let $\mathbb{N}$ denote the set of all nonnegative integers. For
any
 finite set of integers $A$ and any positive integer $h\ge
2$, define
$$hA=\{a_1+a_2+\cdots+a_h:a_i\in A (1\le i\le h)\}$$
and
$$h\text{\^{}}A=\{a_1+a_2+\cdots+a_h:a_i\in A (1\le i\le h), ~a_i\not=a_j~\text{for all }~i\not=j\}.$$
Sumsets are important in additive number theory (see \cite{Kapoor,lev1,lev2,Nathanson72,Nathanson89,Pan,chen,yang}).

Finding lower bounds for $|hA|$ and $|h\text{\^{}}A|$ in terms of
$h$ and $|A|$ and determining the structure of sets $A$ for which
$|hA|$ or $|h\text{\^{}}A|$ are minimal are important problems in
additive number theory.

 Nathanson \cite{Nathanson96} proved the following fundamental and important results.

\noindent{\bf  Theorem A.} (See \cite[Theorem 1.3]{Nathanson96})
{\em~ Let $h\ge 2$ be an integer and  $A$ a  finite set of
integers with $|A|=k$. Then
$$|hA|\ge hk-h+1.$$}

\noindent{\bf  Theorem B.} (See \cite[Theorem 1.6]{Nathanson96})
{\em~ Let $h\ge 2$ be an integer and  $A$ a  finite set of
integers with $|A|=k$. Then
$$|hA|= hk-h+1$$ if and only if $A$ is a $k$-term arithmetic progression.}

\noindent{\bf  Theorem C.} (See \cite[Theorem 1.9]{Nathanson96} or
\cite[Theorem 1]{Nathanson95}) {\em~ Let $A$ be a  finite set of
integers with $|A|=k$ and let $1\le h\le k$. Then
$$|h\text{\^{}}A|\ge hk-h^2+1.$$ This lower bound is best possible.}

\noindent{\bf  Theorem D.} (See \cite[Theorem 1.10]{Nathanson96} or \cite[Theorem 2]{Nathanson95})
{\em~ Let $k\ge 5$ and let $2\le h\le k-2$. If $A$ is a set of $k$ integers such that
$$|h\text{\^{}}A|= hk-h^2+1,$$ then $A$ is a $k$-term arithmetic progression.}

From now on, we assume that $A=\{ a_0, a_1, \dots , a_{k-1}\} $ is
a set of integers with $a_0<a_1<\cdots <a_{k-1}$. For two positive
integers $h$ and $r$, define
$$h^{(r)}A=\left\{\sum_{i=0}^{k-1}s_ia_i:0\le s_i\le r
~\text{for}~i=0,1,\ldots,k-1~\text{and}~\sum_{i=0}^{k-1}s_i=h\right\}.$$
Clearly, $h^{(1)}A=h\text{\^{}}A$ and $h^{(h)}A=hA$. Recently,
Mistri and Pandey generalized the above results.

\noindent{\bf  Theorem E.} (See \cite[Theorem 2.1]{Pandey}) {\em~
Let $A$ be a  set of $k$ integers, $r$ and $h$ be two integers
such that $1\le r\le h\le rk$.  Then
$$|h^{(r)}A|\ge mr(k-m)+(h-mr)(k-2m-1)+1,$$
where $m$ is the integer with $h/r-1<m\le h/r$. This lower bound
is best possible.}

\noindent{\bf  Theorem F.} (See \cite[Theorem 3.1, Theorem
3.2]{Pandey}) {\em~ Let $k\ge 3$, $r$ and $h$ be integers with
$1\le r\le h\le rk-2$ and $(k, h, r)\not= (4,2,1)$. If $A$ is a
set of $k$ integers such that
$$|h^{(r)}A|=mr(k-m)+(h-mr)(k-2m-1)+1,$$
where $m$ is the integer with $h/r-1<m\le h/r$, then $A$ is a
$k$-term arithmetic progression.}

For any ordered $k$-tuple of positive  integers
$\mathbf{r}=(r_0,r_1,\ldots,r_{k-1})$ and  any positive integer
$h$, define
$$h^{(\mathbf{r})}A=\left\{\sum_{i=0}^{k-1}s_ia_i:0\le s_i\le r_i
(0\le i\le k-1), ~\sum_{i=0}^{k-1}s_i=h\right\}.$$ Clearly, if
$\mathbf{r}=(r,r,\ldots,r)$ is an ordered $k$-tuple of positive
integers, then $h^{(\mathbf{r})}A=h^{(r)}A$.

Mistri and Pandey \cite[Concluding Remarks]{Pandey} said that it
is interesting to study the direct and inverse problems related to
sumset $h^{(\mathbf{r})}A$.

In this paper, we solve this problem.

For convenience, let $\sum\limits_{x=a}^{b}f(x)=0$ if $a>b$. Let
$I_{\mathbf{r}}(h)$ be the largest integer and $M_{\mathbf{r}}(h)$
be the least integer such that
\begin{eqnarray*}\sum_{j=0}^{I_{\mathbf{r}}(h)-1}r_j\le h,
\quad \sum_{j=M_{\mathbf{r}}(h)+1}^{k-1}r_j\le h,\end{eqnarray*}
and let
\begin{eqnarray*}\delta_{\mathbf{r}}(h)
=h-\sum_{j=0}^{I_{\mathbf{r}}(h)-1}r_j, \quad
\theta_{\mathbf{r}}(h)
=h-\sum_{j=M_{\mathbf{r}}(h)+1}^{k-1}r_j.\end{eqnarray*} Let
$$L(\mathbf{r}, h)=\sum_{j=M_{\mathbf{r}}(h)+1}^{k-1}j r_j
-\sum_{j=0}^{I_{\mathbf{r}}(h)-1}j r_j+M_{\mathbf{r}}(h)
\theta_{\mathbf{r}(h)}-I_{\mathbf{r}}(h)\delta_{\mathbf{r}(h)}+1.$$

In this paper, we prove the following theorems.
\begin{theorem}\label{thm1} Let $A=\{ a_0, a_1, \dots , a_{k-1}\} $ be
a set of integers with $a_0<a_1<\cdots <a_{k-1}$,
$\mathbf{r}=(r_0,r_1,\ldots,r_{k-1})$ be an ordered $k$-tuple of
positive integers and $h$ be an integer with $$2\le h\le
\sum_{j=0}^{k-1}r_j.$$ Then $$|h^{(\mathbf{r})}A|\ge L(\mathbf{r},
h).$$ This lower bound is best possible.
\end{theorem}

\begin{theorem}\label{thm2} Let $k\ge 5$  be an integer, $\mathbf{r}=(r_0,r_1,\ldots,r_{k-1})$
be an ordered $k$-tuple of positive integers and let $h$ be an
integer with $$2\le h\le \sum_{j=0}^{k-1}r_j-2.$$ If $A$ is a set
of $k$ integers, then
\begin{eqnarray*}|h^{(\mathbf{r})}A|=L(\mathbf{r}, h)
\end{eqnarray*}
if and only if  $A$ is a $k$-term arithmetic progression.
\end{theorem}

\begin{remark}For Theorem \ref{thm2} with $1\le k\le 4$,
we shall give  complete results in Section \ref{secx}. Since
$$L( (r, r, \dots , r), h)=mr(k-m)+(h-mr)(k-2m-1)+1,$$ Theorem F is
a corollary of Theorem \ref{thm2} and Theorems \ref{thm3} and
\ref{thm4} in Section \ref{secx}.
\end{remark}

 \begin{remark} If $h=1$, then $h^{(\mathbf{r})}A = A$. So
$|h^{(\mathbf{r})}A|=k$.

If $$h=\sum_{j=0}^{k-1}r_j-1,$$ then $$h^{(\mathbf{r})}A =\left\{
\sum_{j=0}^{k-1}r_j a_j - a_i : 0\le i\le k-1 \right\} .$$ So
$|h^{(\mathbf{r})}A|=k$.

If $$h=\sum_{j=0}^{k-1}r_j,$$ then
$$h^{(\mathbf{r})}A =\left\{ \sum_{j=0}^{k-1}r_j a_j \right\} .$$ So $|h^{(\mathbf{r})}A|=1$.
\end{remark}

\section{Proofs}

 For any $k$-tuple
$X=(x_0,x_1,\ldots,x_{k-1})\in \mathbb{N}^k$, define the function
$$\phi_A(X)=\sum_{j=0}^{k-1}{x_ja_j}.$$

For any ordered $k$-tuple of positive integers
$\mathbf{r}=(r_0,r_1,\ldots,r_{k-1})$ and any positive integer
$h$, let $R(\mathbf{r},h)$ be the set of all ordered $k$-tuple
 $(x_0,x_1,\ldots,x_{k-1})$ of $\mathbb{N}^k$ such that
\begin{eqnarray*}
\sum_{j=0}^{k-1}x_j=h,\quad  0\le x_i\le r_i, \quad
i=0,1,\ldots,k-1.
\end{eqnarray*}
Then
 $$h^{(\mathbf{r})}A=\{\phi_A(X):X\in R(\mathbf{r},h)\}.$$
For any positive integer $k$ and any $k$-tuple
$X=(x_0,x_1,\ldots,x_{k-1})\in \mathbb{N}^k$, define
 the weighted
sum $$S(X)=\sum_{j=0}^{k-1} {j x_j}.$$ For two $k$-tuples
$U=(u_0,u_1,\ldots,u_{k-1}),W=(w_0,w_1,\ldots,w_{k-1})\in
\mathbb{N}^k$,

we call $U\rightarrow W$ a {\em step} if there exists an index
$j\ge 0$ such that $w_j=u_j-1$, $w_{j+1}=u_{j+1}+1$ and $w_i=u_i$
for all integers $i\not=j,j+1$. We call $X_1\rightarrow
X_2\rightarrow \cdots \rightarrow X_t$ a {\em $(\mathbf{r},
h)$-path} of length $t$, if $X_i\in R(\mathbf{r},h) (1\le i\le t)$
and $X_{i+1}\rightarrow X_{i} (1\le i\le t-1)$ are steps. It is
clear that if $X_1\rightarrow X_2\rightarrow \cdots \rightarrow
X_t$ is a $(\mathbf{r}, h)$-path of length $t$, then
$$S(X_{i+1})-S(X_{i})= 1 (1\le i\le t-1).$$
Thus $S(X_t)-S(X_1)=t-1$.

Let
$$V=(r_0,r_1,\ldots,r_{I_{\mathbf{r}}(h)-1},\delta_{\mathbf{r}(h)},0,\ldots,0)$$
and
$$V'=(0,\ldots,0,\theta_{\mathbf{r}(h)},r_{M_{\mathbf{r}}(h)+1},\ldots,r_{k-1}),$$
where
$I_{\mathbf{r}}(h),\delta_{\mathbf{r}(h)},\theta_{\mathbf{r}(h)},M_{\mathbf{r}}(h)$
are defined as in Section \ref{b}. Then $V, V'\in
R(\mathbf{r},h)$.

\begin{lemma}\label{lem0}We have $S(V')-S(V)+1=L(\mathbf{r}, h)$. In particular, any $(\mathbf{r}, h)$-path from $V$
to $V'$ has length $L(\mathbf{r}, h)$.\end{lemma}

\begin{proof} Noting that
$$S(V)=\sum_{j=0}^{I_{\mathbf{r}}(h)-1}j r_j+I_{\mathbf{r}}(h)\delta_{\mathbf{r}(h)},\quad
S(V')=\sum_{j=M_{\mathbf{r}}(h)+1}^{k-1}j
r_j+M_{\mathbf{r}}(h)\theta_{\mathbf{r}(h)},$$ we have
\begin{eqnarray*}S(V')-S(V)&=&\sum_{j=M_{\mathbf{r}}(h)+1}^{k-1}j r_j
-\sum_{j=0}^{I_{\mathbf{r}}(h)-1}j
r_j+M_{\mathbf{r}}(h)\theta_{\mathbf{r}(h)}-I_{\mathbf{r}}(h)\delta_{\mathbf{r}(h)}\\
&=&L(\mathbf{r}, h)-1.\end{eqnarray*} Since a $(\mathbf{r},
h)$-path from $V$ to $V'$ has length $S(V')-S(V)+1$, it follows
that any $(\mathbf{r}, h)$-path from $V$ to $V'$ has length
$L(\mathbf{r}, h)$.
\end{proof}

\begin{lemma}\label{lem1} Let
$X=(x_0,x_1,\ldots,x_{k-1})\in R(\mathbf{r},h)$ and $
Y=(y_0,y_1,\ldots,y_{k-1})\in R(\mathbf{r},h)$ with $X\not=Y$. If
$$\sum_{j=i}^{k-1}x_j\le \sum_{j=i}^{k-1}y_j, \quad
i=1,2,\ldots,k-1,$$ then there exists a $(\mathbf{r}, h)$-path
from $X$ to $Y$.
\end{lemma}

\begin{proof} Let $X_0=X\rightarrow X_1\rightarrow \cdots\rightarrow X_g$ be a
 $(\mathbf{r}, h)$-path of the maximal length such that
\begin{eqnarray}\label{condition}\sum_{j=t}^{k-1}x_{i,j}\le \sum_{j=t}^{k-1}y_j,
\quad ~1\le t\le k-1, 1\le i\le g,\end{eqnarray} where
$X_i=(x_{i,0},x_{i,1},\ldots,x_{i,k-1})~(0\le i\le g)$. Now we
prove that $X_g=Y$. Suppose that $X_g\not=Y$. Let $s$ be the
maximal index with $x_{g,s}\not=y_s$. Noting that $X, Y\in
R(\mathbf{r},h)$, we have
$$\sum_{j=0}^{k-1}x_{g,j}=h=\sum_{j=0}^{k-1}y_j.$$
Hence $s\ge 1$. Since
$$\sum_{j=s}^{k-1}x_{g,j}\le \sum_{j=s}^{k-1}y_j,$$ it follows
from the definition of $s$ that  $x_{g,s}<y_s$. If $x_{g,s-1}>0$,
let
$$X_{g+1}=(x_{g,0},\ldots,x_{g,s-1}-1,x_{g,s}+1,x_{g,s+1},\ldots,x_{g,k-1}),$$
then $X_g\rightarrow X_{g+1}$ is a $(\mathbf{r}, h)$-path and
$X_{g+1}$ also satisfies \eqref{condition}. This is a
contradiction with the maximality of $g$. Hence $x_{g,s-1}=0$. If
$x_{g,j}=0$ for all $0\le j\le s-1$, then
\begin{eqnarray*}\sum_{j=0}^{k-1}x_{g,j}&=&x_{g,s}+\sum_{j=s+1}^{k-1}x_{g,j}\\
&=&x_{g,s}+\sum_{j=s+1}^{k-1}y_j\\
&<&y_s+\sum_{j=s+1}^{k-1}y_j\\
&\le &\sum_{j=0}^{k-1}y_j=h,\end{eqnarray*} a contradiction with
$X_g\in R(\mathbf{r},h)$ (see the definition of $(\mathbf{r},
h)$-path). Thus there exists an index $j$ with $0\le j< s-1$ such
that $x_{g,j}>0$. We assume that $j$ is the largest such index.
Let
$$X_{g+1}=(x_{g,0},\ldots,x_{g,j}-1,x_{g,j+1}+1,0, \dots , 0, x_{g,s},\ldots,x_{g,k-1}).$$
Then $X_g\rightarrow X_{g+1}$ is a $(\mathbf{r}, h)$-path. Since
$X_{g}$  satisfies \eqref{condition}, it follows that $X_{g+1}$
also satisfies \eqref{condition}. This is a contradiction with the
maximality of $g$. Therefore, $X_g=Y$.
\end{proof}

\begin{lemma}\label{lem2}  Let $X_1\rightarrow
X_2\rightarrow \cdots\rightarrow X_{t-1}\rightarrow X_t$ and
$X_1\rightarrow X_2'\rightarrow \cdots\rightarrow
X_{t-1}'\rightarrow X_t$ be two different $(\mathbf{r}, h)$-paths
from $X_1$ to $X_t$. If $A$ is a set of $k$ integers such that
$|h^{(\mathbf{r})}A|=L(\mathbf{r}, h)$, then
$\phi_A(X_i)=\phi_A(X_i')$ for $i=2,3,\ldots,t-1$.
\end{lemma}

\begin{proof}  By Lemma \ref{lem1}, there exists a
$(\mathbf{r}, h)$-path from $V$ to $X_1$ and another $(\mathbf{r},
h)$-path from $X_t$ to $V'$. Thus we have the following
$(\mathbf{r}, h)$-path from $V$ to $V'$:
\begin{eqnarray}\label{path}V\rightarrow \cdots\rightarrow X_1\rightarrow X_2\rightarrow \cdots\rightarrow X_{t-1}
\rightarrow X_t\rightarrow \cdots \rightarrow V'.\end{eqnarray} By
Lemma \ref{lem0}, the length of
 the $(\mathbf{r}, h)$-path \eqref{path} is
$L(\mathbf{r}, h)=|h^{(\mathbf{r})}A|$. Clearly,
$$\phi_A(V)<\cdots<\phi_A(X_1)<\phi_A(X_2)<\cdots<\phi_A(X_{t-1})<\phi_A(X_{t})<\cdots<\phi_A(V').$$
Since
$$\{\phi_A(X):X ~\text{is on the $(\mathbf{r}, h)$-path \eqref{path}}\}\subseteq h^{(\mathbf{r})}A$$
and
$$|\{\phi_A(X):X ~\text{is on the $(\mathbf{r}, h)$-path \eqref{path}}\}|= |h^{(\mathbf{r})}A|,$$
it follows that $$h^{(\mathbf{r})}A=\{\phi_A(X):X ~\text{is on the
$(\mathbf{r}, h)$-path \eqref{path}}\}.$$ Noting that
$$\{\phi_A(X_2'),\phi_A(X_3'),\ldots,\phi_A(X_{t-1}')\}\subseteq h^{(\mathbf{r})}A$$
and
$$\phi_A(X_1)<\phi_A(X_2')<\cdots<\phi_A(X_{t-1}')<\phi_A(X_{t}),$$
we have $\phi_A(X_i)=\phi_A(X_i')$ for $i=2,3,\ldots,t-1$.
\end{proof}

\begin{lemma}\label{lem3} Let $c_i$ and $d_i (0\le i\le k-1)$ be integers with $c_i\le d_i(0\le i\le k-1)$.
If $h$ is an integer with $$\sum_{i=0}^{k-1} c_i \le h\le
\sum_{i=0}^{k-1} d_i,$$ then there exist integers $x_i (0\le i\le
k-1)$  with $c_i\le x_i\le  d_i(0\le i\le k-1)$ such that
$$h=x_0+x_1+\cdots +x_{k-1}.$$
\end{lemma}

Proof is left to the reader.

\begin{proof}[Proof of Theorem \ref{thm1}]

 By Lemma
\ref{lem1}, there exists a $(\mathbf{r}, h)$-path
$V=V_0\rightarrow V_1\rightarrow \cdots \rightarrow V_{\ell}=V'$.

By Lemma \ref{lem0}, we have $\ell +1=L(\mathbf{r}, h)$. Since
$\phi_A(V_i)\in h^{(\mathbf{r})}A (0\le i\le \ell )$ and
$\phi_A(V_{i+1})>\phi_A(V_i) (0\le i\le \ell -1 )$, we have
\begin{equation}\label{w}|h^{(\mathbf{r})}A|\ge \ell+1=L(\mathbf{r},
h).\end{equation}

Next we show that this lower bound is optimal. Let $A=\{0,1,\ldots,k-1\}$.
Then the smallest integer in $h^{(\mathbf{r})}A$ is
\begin{eqnarray*}&&\underbrace{0+\cdots+0}_{r_0~\text{copies}}+\underbrace{1+\cdots+1}_{r_1~\text{copies}}
+\cdots+\underbrace{(I_{\mathbf{r}}(h)-1)+\cdots+(I_{\mathbf{r}}(h)-1)}_{r_{I_{\mathbf{r}}(h)-1}~\text{copies}}\\
&&+\underbrace{I_{\mathbf{r}}(h)+\cdots+I_{\mathbf{r}}(h)}_{\delta_{\mathbf{r}(h)}~\text{copies}}\\
&=& S(V)
\end{eqnarray*}
and the largest integer in $h^{(\mathbf{r})}A$ is
\begin{eqnarray*}&&\underbrace{M_{\mathbf{r}}(h)+\cdots+M_{\mathbf{r}}(h)}_{\theta_{\mathbf{r}}(h)~\text{copies}}
+\underbrace{(M_{\mathbf{r}}(h)+1)+\cdots+(M_{\mathbf{r}}(h)+1)}_{r_{M_{\mathbf{r}}(h)+1}~\text{copies}}\\
&&+\cdots+\underbrace{(k-2)+\cdots+(k-2)}_{r_{k-2}~\text{copies}}
+\underbrace{(k-1)+\cdots+(k-1)}_{r_{k-1}~\text{copies}}\\
&=& S(V').
\end{eqnarray*}
It follows that
$$h^{(\mathbf{r})}A\subseteq [S(V),
S(V')].$$ Thus, by Lemma \ref{lem0}, we have
\begin{equation}\label{s}|h^{(\mathbf{r})}A|\le  S(V')-S(V)+1=L(\mathbf{r}, h).\end{equation} By
\eqref{w} and \eqref{s}, we have
$$|h^{(\mathbf{r})}A|=L(\mathbf{r}, h).$$
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm2}]

Suppose that $|h^{(\mathbf{r})}A|=L(\mathbf{r}, h)$. For any
integer $j$ with $0\le j\le k-4$, by $$2\le h\le
\sum_{i=0}^{k-1}r_i-2$$ and Lemma \ref{lem3}, there exists
$$X=(x_0,
x_1, \dots, x_j, x_{j+1}, x_{j+2}, x_{j+3}, \dots , x_{k-1}) \in
R(\mathbf{r},h)$$ such that
$$1\le x_j\le r_j, \quad 0\le x_{j+1}\le r_{j+1}-1,\quad 1\le x_{j+2}\le
r_{j+2},\quad 0\le x_{j+3}\le r_{j+3}-1.$$ Then
\begin{eqnarray*}&&(\dots, x_j, x_{j+1}, x_{j+2}, x_{j+3}, \dots
)\\
&\rightarrow& (\dots, x_j-1, x_{j+1}+1, x_{j+2}, x_{j+3}, \dots
)\\
&\rightarrow& (\dots, x_j-1, x_{j+1}+1, x_{j+2}-1, x_{j+3}+1,
\dots ) \end{eqnarray*} and
\begin{eqnarray*}&&(\dots, x_j, x_{j+1}, x_{j+2}, x_{j+3}, \dots   )\\
&\rightarrow & (\dots, x_j, x_{j+1}, x_{j+2}-1, x_{j+3}+1, \dots
)\\
& \rightarrow& (\dots, x_j-1, x_{j+1}+1, x_{j+2}-1, x_{j+3}+1,
\dots )\end{eqnarray*} are two different $(\mathbf{r}, h)$-paths.
By Lemma \ref{lem2}, we have
$$\phi_A ((\dots, x_j-1, x_{j+1}+1, x_{j+2}, x_{j+3}, \dots
)) = \phi_A ((\dots, x_j, x_{j+1}, x_{j+2}-1, x_{j+3}+1, \dots
)).$$ This implies that $a_{j+1}-a_j=a_{j+3}-a_{j+2}$. Therefore,

$$a_{1}-a_0=a_{3}-a_{2}=a_{5}-a_{4}=\cdots , \quad a_{2}-a_{1}=a_{4}-a_{3}=a_6-a_5=\cdots.$$
In order to prove that $A$ is a $k$-term arithmetic progression,
it suffices to prove $a_4-a_3=a_1-a_0$.

By $$2\le h\le \sum_{i=0}^{k-1}r_i-2$$ and Lemma \ref{lem3}, there
exists
$$Y=(y_0,
y_1, y_2, y_3, y_4, \dots, y_{k-1}) \in R(\mathbf{r},h)$$ such
that
$$1\le y_0\le r_0, \quad 0\le y_1\le r_1-1,
\quad 1\le y_3\le r_3, \quad 0\le y_4\le r_4-1.$$ Then
\begin{eqnarray*}&& (y_0,
y_1, y_2, y_3, y_4, \dots, y_{k-1}) \\
&\rightarrow & (y_0-1,
y_1+1, y_2, y_3, y_4, \dots, y_{k-1}) \\
&\rightarrow &(y_0-1, y_1+1, y_2, y_3-1, y_4+1, \dots, y_{k-1})
\end{eqnarray*}
and
\begin{eqnarray*}&& (y_0,
y_1, y_2, y_3, y_4, \dots, y_{k-1}) \\
&\rightarrow & (y_0,
y_1, y_2, y_3-1, y_4+1, \dots, y_{k-1}) \\
&\rightarrow &(y_0-1, y_1+1, y_2, y_3-1, y_4+1, \dots, y_{k-1})
\end{eqnarray*}
are two different $(\mathbf{r}, h)$-paths. By Lemma \ref{lem2}, we
have
$$\phi_A ((y_0-1,
y_1+1, y_2, y_3, y_4, \dots, y_{k-1})) = \phi_A ((y_0, y_1, y_2,
y_3-1, y_4+1, \dots, y_{k-1})).$$ This implies that
$a_1-a_0=a_4-a_3$.

Therefore, $A$ is a $k$-term arithmetic progression.

Conversely, if $A$ is a $k$-term arithmetic progression, without
loss of generality, we may assume that $A=\{0,1,\dots , k-1\}$. By
the proof of Theorem \ref{thm1}, we have
$|h^{(\mathbf{r})}A|=L(\mathbf{r}, h)$.
\end{proof}

\section{Cases $1\le k\le 4$} \label{secx}

For $k=1$ and $1\le h\le r_0$, it is easy to see that
$h^{(\mathbf{r})}A = \{ h a_0 \}$. So $|h^{(\mathbf{r})}A|=1$.

For $k=2$ and $1\le h\le r_0+r_1$, we have
$$h^{(\mathbf{r})}A =\{ x_0 a_0 +x_1 a_1 : 0\le x_0\le r_0, 0\le
x_1\le r_1, x_0+x_1=h, x_0,x_1\in \mathbb{N}\} .$$ So
$$|h^{(\mathbf{r})}A|= |\{ (x_0, x_1): 0\le x_0\le r_0, 0\le
x_1\le r_1, x_0+x_1=h, x_0,x_1\in \mathbb{N}\} |.$$

Now we deal with the cases $k=3$ and $k=4$.

\begin{theorem}\label{thm3} Let $A=\{ a_0<a_1<a_2\}$ be a set of integers and
$\mathbf{r}= (r_0,r_1,r_2)$ be an ordered $3$-tuple of positive
integers. Suppose that $h$ is an integer with $2\le h\le
r_0+r_1+r_2 -2$. Then

(i) for $r_1=1$, we have $|h^{(\mathbf{r})}A|=L(\mathbf{r}, h)$;

(ii) for $r_1\ge 2$, we have $|h^{(\mathbf{r})}A|=L(\mathbf{r},
h)$ if and only if $A$ is a $3$-term arithmetic progression.
\end{theorem}

\begin{proof} We first prove (i). Suppose that $r_1=1$.
By Lemma \ref{lem1}, there exists a $(\mathbf{r}, h)$-path from
$V$ to $V'$: \begin{equation}\label{xyz} V=V_0\rightarrow
V_1\rightarrow \cdots\rightarrow V_t=V'.\end{equation} Let
$X=(x_0, x_1, x_2)\rightarrow Y$ be a $(\mathbf{r}, h)$-path. If
$x_1=0$, then $Y=(x_0-1,1,x_2)$. If $x_1=1$, then
$Y=(x_0,0,x_2+1)$. That is, $Y$ is uniquely determined by $X$.
Hence,  the $(\mathbf{r}, h)$-path \eqref{xyz} is uniquely
determined by $V$ and $V'$. For any $W\in R(\mathbf{r},h)$, by
Lemma \ref{lem1}, there exists a $(\mathbf{r}, h)$-path from $V$
to $W$ and a $(\mathbf{r}, h)$-path $W$ to $V'$. Since \eqref{xyz}
is unique, we have $W\in \{V_0,V_1,\ldots,V_t\}$. Thus, by the
definition of $h^{(\mathbf{r})}A$, $\phi_A (V_i) <\phi_A (V_{i+1})
(0\le i\le t-1)$ and Lemma \ref{lem0}, we have
\begin{eqnarray*}
|h^{(\mathbf{r})}A|&=&|\{ \phi_A (X) : X\in R(\mathbf{r},h)\} |\\
&=&|\{ \phi_A (V_i) : i=0,\dots , t\} |\\
&=& t+1=S(V')-S(V)+1=L(\mathbf{r}, h).\end{eqnarray*}

Next we shall prove (ii). If $A$ is a $3$-term arithmetic
progression, without loss of generality, we may assume that
$A=\{0,1,2\}$. By the proof of Theorem \ref{thm1}, we have
$|h^{(\mathbf{r})}A|=L(\mathbf{r}, h)$.

Conversely, suppose that $r_1\ge 2$ and
$|h^{(\mathbf{r})}A|=L(\mathbf{r}, h)$.

Since $2\le h\le r_0+r_1+r_2 -2$, there exists $ (x_0, x_1,
x_2)\in R(\mathbf{r},h)$ such that
$$1\le x_0\le r_0,\quad 1\le x_1\le r_1-1,\quad 0\le x_2\le r_2-1.$$
Then
$$ (x_0, x_1, x_2)\rightarrow (x_0-1, x_1+1, x_2)\rightarrow (x_0-1, x_1,
x_2+1)$$ and
$$ (x_0, x_1, x_2)\rightarrow (x_0, x_1-1, x_2+1)\rightarrow (x_0-1, x_1,
x_2+1)$$ are two different $(\mathbf{r}, h)$-paths. By Lemma
\ref{lem2}, we have
$$\phi_A ((x_0-1, x_1+1, x_2)) = \phi_A ((x_0, x_1-1, x_2+1)).$$ This implies that
$a_1-a_0=a_2-a_1$. Therefore, $A$ is a $3$-term arithmetic
progression.\end{proof}

\begin{theorem}\label{thm4} Let $A=\{ a_0<a_1<a_2<a_3\} $ be a set of integers
and $\mathbf{r}= (r_0,r_1,r_2,r_3)$ be an ordered $4$-tuple of
positive integers. Suppose that $h$ is an integer with $2\le h\le
r_0+r_1+r_2+r_3 -2$. Then

(i) for $r_1=r_2=1$, we have $|h^{(\mathbf{r})}A|=L(\mathbf{r},
h)$ if and only if $a_1-a_0=a_3-a_2$;

(ii) for $r_1\ge 2$ or $r_2\ge 2$, we have
$|h^{(\mathbf{r})}A|=L(\mathbf{r}, h)$ if and only if $A$ is a
$4$-term arithmetic progression.
\end{theorem}

\begin{proof}  Suppose that $|h^{(\mathbf{r})}A|=L(\mathbf{r}, h)$.

 Since $2\le h\le r_0+r_1+r_2+r_3 -2$, there exists $ (x_0, x_1,
x_2, x_3)\in R(\mathbf{r},h)$ such that
$$1\le x_0\le r_0,\quad  0\le x_1\le r_1-1,\quad 1\le x_2\le r_2, \quad 0\le x_3\le r_3-1.$$
Then
$$ (x_0, x_1, x_2,x_3)\rightarrow (x_0-1, x_1+1, x_2, x_3)\rightarrow (x_0-1, x_1+1,
x_2-1, x_3+1)$$ and
$$ (x_0, x_1, x_2, x_3)\rightarrow (x_0, x_1, x_2-1, x_3+1)\rightarrow (x_0-1, x_1+1,
x_2-1, x_3+1)$$ are two different $(\mathbf{r}, h)$-paths. By
Lemma \ref{lem2}, we have
$$\phi_A ((x_0-1, x_1+1, x_2, x_3)) = \phi_A ((x_0, x_1, x_2-1, x_3+1)).$$ This implies that
\begin{equation}\label{v} a_1-a_0=a_3-a_2.\end{equation}

We first prove (i).

It is enough to prove that if $r_1=r_2=1$ and $a_1-a_0=a_3-a_2$,
then $|h^{(\mathbf{r})}A|=L(\mathbf{r}, h)$.

 By Lemma \ref{lem1}, there exists a
$(\mathbf{r}, h)$-path from $V$ to $V'$
\begin{equation}\label{xys} V=V_0\rightarrow V_1\rightarrow
\cdots\rightarrow V_s=V'.\end{equation}  Suppose that
\begin{equation}\label{xyt} V=W_0\rightarrow W_1\rightarrow
\cdots\rightarrow W_t=V'\end{equation} is also a $(\mathbf{r},
h)$-path from $V$ to $V'$. By Lemma \ref{lem0}, we have $s=t$. Now
we prove that $\phi_A (V_i)=\phi_A (W_i) (0\le i\le s)$. In order
to prove this, we prove the following stronger result: for $0\le
i<s$, if $V_i=W_i$, then either $V_{i+1}=W_{i+1}$ or $V_{i+2}=
W_{i+2}$ and $\phi_A (V_{i+1})= \phi_A (W_{i+1})$.

Suppose that $0\le i<s$ and $V_i=W_i= (v_{i,0}, v_{i,1}, v_{i,2},
v_{i,3})$.

{\bf Case 1:} $v_{i,1}=v_{i,2}=0$. Then, by the definition of
step, we have
$$V_{i+1}=(v_{i,0}-1, v_{i,1}+1, v_{i,2},
v_{i,3}) =W_{i+1}.$$

{\bf Case 2:} $v_{i,1}=v_{i,2}=1$. Then, by the definition of
step and $r_1=r_2=1$, we have
$$V_{i+1}=(v_{i,0}, v_{i,1}, v_{i,2}-1,
v_{i,3}+1) =W_{i+1}.$$

{\bf Case 3:} $v_{i,1}=1, v_{i,2}=0$. Then, by the definition of
 step and $r_1=r_2=1$, we have
$$V_{i+1}=(v_{i,0}, v_{i,1}-1, v_{i,2}+1,
v_{i,3}+1) =W_{i+1}.$$

{\bf Case 4:} $v_{i,1}=0, v_{i,2}=1$. Then, by the definition of
 step and $r_1=r_2=1$, we have \begin{equation}\label{u}\{
V_{i+1},W_{i+1} \} \subseteq \{ (v_{i,0}-1, v_{i,1}+1, v_{i,2},
v_{i,3}), (v_{i,0}, v_{i,1}, v_{i,2}-1, v_{i,3}+1) \} .
\end{equation} Since
\begin{eqnarray*}&&\phi_A ((v_{i,0}-1, v_{i,1}+1, v_{i,2},
v_{i,3}))-\phi_A (V_i)\\
& =& a_1-a_0=a_3-a_2\\
& =& \phi_A ((v_{i,0}, v_{i,1}, v_{i,2}-1, v_{i,3}+1))-\phi_A
(V_i) ,\end{eqnarray*} we have $\phi_A (V_{i+1})= \phi_A
(W_{i+1})$.
 By \eqref{u}, the definition of
adjacency and $r_1=r_2=1$, we have
$$V_{i+2}=(v_{i,0}-1, v_{i,1}+1, v_{i,2}-1,
v_{i,3}+1)=W_{i+2}.$$

Thus, we have proved that for $0\le i<s$, if $V_i=W_i$, then
either $V_{i+1}=W_{i+1}$ or  $V_{i+2}= W_{i+2}$ and $\phi_A
(V_{i+1})= \phi_A (W_{i+1})$. It follows from $V_0=W_0$ and
$V_s=W_s$ that $\phi_A (V_i)=\phi_A (W_i) (0\le i\le s)$.

For any $W\in R(\mathbf{r},h)$, by Lemma \ref{lem1}, there exists
a $(\mathbf{r}, h)$-path from $V$ to $W$ and a $(\mathbf{r},
h)$-path $W$ to $V'$. By the above arguments, we have
$$\phi_A (W)\in \{ \phi_A (V_i) : 0\le i\le s\} .$$
Hence
$$h^{(\mathbf{r})}A = \{ \phi_A (X) : X\in R(\mathbf{r},h) \}
 =\{ \phi_A (V_i) : 0\le i\le s\} .$$
Therefore, by Lemma \ref{lem0},
$$|h^{(\mathbf{r})}A|=s+1=S(V')-S(V)+1=L(\mathbf{r}, h).$$

Now we prove (ii).

If $A$ is a $4$-term arithmetic progression, without loss of
generality, we may assume that $A=\{0,1,2,3\}$. By the proof of
Theorem \ref{thm1}, we have $|h^{(\mathbf{r})}A|=L(\mathbf{r},h)$.

Conversely, we suppose that $|h^{(\mathbf{r})}A|=L(\mathbf{r},h)$
and $r_1\ge 2$ or $r_2\ge 2$. By \eqref{v}, it is enough to prove
that $a_2-a_1=a_1-a_0$ or $a_2-a_1=a_3-a_2$.

{\bf Case 1:}  $r_1\ge 2$. Since $2\le h\le r_0+r_1+r_2+r_3 -2$,
there exists $Y=(y_0, y_1, y_2, y_3)\in R(\mathbf{r},h)$ such that
$$1\le y_0\le r_0,\quad  1\le y_1\le r_1-1,\quad 0\le y_2\le r_2-1, \quad 0\le y_3\le r_3.$$
Then
$$ (y_0, y_1, y_2,y_3)\rightarrow (y_0-1, y_1+1, y_2, y_3)\rightarrow (y_0-1, y_1,
y_2+1, y_3)$$ and
$$ (y_0, y_1, y_2, y_3)\rightarrow (y_0, y_1-1, y_2+1, y_3)\rightarrow (y_0-1, y_1,
y_2+1, y_3)$$ are two different $(\mathbf{r}, h)$-paths. By Lemma
\ref{lem2}, we have
$$\phi_A ((y_0-1, y_1+1, y_2, y_3)) = \phi_A ((y_0, y_1-1, y_2+1, y_3)).$$ This implies that
$a_1-a_0=a_2-a_1$.

{\bf Case 2:}  $r_2\ge 2$. Since $2\le h\le r_0+r_1+r_2+r_3 -2$,
there exists $Z=(z_0, z_1, z_2, z_3)\in R(\mathbf{r},h)$ such that
$$0\le z_0\le r_0,\quad  1\le z_1\le r_1,\quad 1\le z_2\le r_2-1, \quad 0\le z_3\le r_3-1.$$
Then
$$ (z_0, z_1, z_2,z_3)\rightarrow (z_0, z_1-1, z_2+1, z_3)\rightarrow (z_0, z_1-1,
z_2, z_3+1)$$ and
$$ (z_0, z_1, z_2, z_3)\rightarrow (z_0, z_1, z_2-1, z_3+1)\rightarrow (z_0, z_1-1,
z_2, z_3+1)$$ are two different $(\mathbf{r}, h)$-paths. By Lemma
\ref{lem2}, we have
$$\phi_A ((z_0, z_1-1, z_2+1, z_3)) = \phi_A ((z_0, z_1, z_2-1, z_3+1)).$$ This implies that
$a_2-a_1=a_3-a_2$.

Therefore, $A$ is a $4$-term arithmetic progression.
\end{proof}

config: arxiv


text:
\subsection{Related work}
The analysis of \fedavg (a.k.a. Local SGD) is an active area of research.
Early research on \fedavg mostly focused on the particular case of $R = 1$, also known as ``one-shot averaging'', where the iterates are only averaged once at the end of procedure \citep{Mcdonald.Mohri.ea-NIPS09,Zinkevich.Weimer.ea-NIPS10,Zhang.Duchi.ea-13,Shamir.Srebro-Allerton14,Rosenblatt.Nadler-16}.
The first convergence result on \fedavg with general (more than one) synchronization for convex objectives was established by \citet{Stich-ICLR19} under the assumption of uniformly bounded gradients.
\citet{Stich.Karimireddy-arXiv19,Haddadpour.Kamani.ea-NeurIPS19,Dieuleveut.Patel-NeurIPS19,Khaled.Mishchenko.ea-AISTATS20} relaxed this requirement and studied \fedavg under assumptions similar to our \cref{asm1}.
These works also attained better rates than \citep{Stich-ICLR19} through an improved stability analysis of SGD.
However, recent work \citep{Woodworth.Patel.ea-ICML20} showed that all the above bounds on \fedavg are strictly dominated by minibatch SGD \citep{Dekel.Gilad-Bachrach.ea-JMLR12} baseline.
\citet{Woodworth.Patel.ea-ICML20} provided the first bound for \fedavg that can improve over minibatch SGD for certain cases.
This is to our knowledge the state-of-the-art bound for \fedavg and its variants.
Our \fedac uniformly dominates this bound on \fedavg.

The specialty of quadratic objectives for better communication efficiency has been studied in an array of contexts \citep{Zhang.Duchi.ea-JMLR15,Jain.Kakade.ea-18}. \citet{Woodworth.Patel.ea-ICML20} studied an acceleration of \fedavg but was limited to quadratic objectives.
More generally, \citet{Dieuleveut.Patel-NeurIPS19} studied the convergence of \fedavg under bounded \nth{3}-derivative, but the bounds are still dominated by minibatch SGD baseline \citep{Woodworth.Patel.ea-ICML20}.
Recent work by \citet{Godichon-Baggioni.Saadane-20} studied one-shot averaging under similar assumptions.
Our analysis on \fedavg (\cref{fedavg:a2}) allows for general $R$ and reduces to a comparable bound if $R = 1$, which is further improved by our analysis on \fedac (\cref{fedacii:a2}).

\fedavg has also been studied in other more general settings. A series of recent papers (\eg, \citep{Zhou.Cong-IJCAI18,Haddadpour.Kamani.ea-ICML19,Wang.Joshi-19,Yu.Jin-ICML19,Yu.Jin.ea-ICML19,Yu.Yang.ea-AAAI19}) studied the convergence of \fedavg for non-convex objectives.
We conjecture that \fedac can be generalized to non-convex objectives to attain better efficiency by combining our result with recent non-convex acceleration algorithms (\emph{e.g.}, \citep{Carmon.Duchi.ea-SIOPT18}).
Numerous recent papers \citep{
    Khaled.Mishchenko.ea-AISTATS20,Li.Huang.ea-ICLR20,Haddadpour.Mahdavi-arXiv19,Koloskova.Loizou.ea-ICML20} studied \fedavg in heterogeneous settings, where each worker has access to stochastic gradient oracles from different distributions.
Other variants of \fedavg have been proposed in the face of heterogeneity \citep{Pathak.Wainwright-NeurIPS20,Li.Sahu.ea-MLSys20,Karimireddy.Kale.ea-ICML20,Wang.Tantia.ea-ICLR20}.
We defer the analysis of \fedac for heterogeneous settings for future work.
Other techniques, such as quantization, can also reduce communication cost \citep{Alistarh.Grubic.ea-NIPS17,Wen.Xu.ea-NIPS17,Stich.Cordonnier.ea-NeurIPS18,Basu.Data.ea-NeurIPS19,Mishchenko.Gorbunov.ea-arXiv19,Reisizadeh.Mokhtari.ea-AISTATS20}.
We refer readers to \citep{Kairouz.McMahan.ea-arXiv19} for a more comprehensive survey of the recent development of algorithms in Federated Learning.

Stability is one of the major topics in machine learning and has been studied for a variety of purposes \citep{Yu.Kumbier-20}. For example, \citet{Bousquet.Elisseeff-JMLR02,Hardt.Recht.ea-ICML16} showed that algorithmic stability can be used to establish generalization bounds.
\citet{Chen.Jin.ea-arXiv18} provided the stability bound of standard Accelerated Gradient Descent (AGD) for \emph{quadratic objectives}.
To the best of our knowledge, there is no existing (positive or negative) result on the stability of AGD for general convex or strongly convex objectives.
This work provides the first (negative) result on the stability of standard deterministic AGD, which suggests that standard AGD may not be initial-value stable even for strongly convex and smooth objectives (\cref{instability:sketch}).\footnote{
We construct the counterexample for initial-value stability for simplicity and clarity.
We conjecture that our counterexample also extends to other algorithmic stability notions (\eg, uniform stability \citep{Bousquet.Elisseeff-JMLR02}) since initial-value stability is usually milder than the others.
} This result may be of broader interest.
The tradeoff technique of \fedac also provides a possible remedy to mitigate the instability issue, which may be applied to derive better generalization bounds for momentum-based methods.

The stochastic optimization problem $\min_{w \in \reals^d} F(w) :=  \expt_{\xi \sim \mathcal{D}} f(w; \xi)$ we consider in this paper is commonly referred to as the \emph{stochastic approximation} (SA) problem in the literature \citep{Kushner.Yin.ea-03}. Another related question is the \emph{sample average approximation} (SAA), also known as \emph{empirical risk minimization} (ERM) problem \citep{Vapnik-98}. The ERM problem is defined as $\min_{w \in \reals^d} F(w) :=  \frac{1}{N} \sum_{i=1}^N f(w; \xi^{(i)})$, where the sum of a fixed finite set of objectives is to be optimized.
For strongly-convex ERM, it is possible to leverage variance reduction techniques \citep{Johnson.Zhang-13} to attain linear convergence. For example,  the Distributed Accelerated SVRG (DA-SVRG) \citep{Lee.Lin.ea-JMLR17} can attain expected $\varepsilon$-optimality within $\tilde{\mathcal{O}}(\frac{N}{M} \log(1/\varepsilon) )$ parallel runtime and $\tilde{\mathcal{O}}( \log(1/\varepsilon))$ rounds of communication.
If we were to apply \fedac for ERM, it can attain expected $\varepsilon$-optimality with
$\tilde{\mathcal{O}}(\frac{1}{M \varepsilon})$ parallel runtime and $\tilde{\mathcal{O}}(M^{\frac{1}{3}})$ rounds of communication (assuming \cref{asm1} is satisfied).
Therefore one can obtain low accuracy solution with \fedac in a short parallel runtime, whereas DA-SVRG may be preferred if high accuracy is required and $N$ is relatively small.
It is worth mentioning that \fedac is not designed or proved for the distributed ERM setting, and we include this rough comparison for completeness.
We conjecture that \fedac can be incorporated with appropriate variance reduction techniques to attain better performance in distributed ERM setting.


text:
\begin{document}

\title{Topological Conformal Dimension}

\author{Claudio A. DiMarco}
\address{215 Carnegie, Mathematics Department, Syracuse University,
Syracuse, NY 13244-1150}
\email{cdimarco@syr.edu}

\subjclass[2010]{Primary 28A80, 30L10; Secondary 28A78, 54F45}

\keywords{metric space, conformal dimension, topological dimension, quasisymmetric map, Cantor sets}

\date{\today}

\begin{abstract}
We investigate a quasisymmetrically invariant counterpart of the topological Hausdorff dimension of a metric space.  This invariant, called the \textit{topological conformal dimension}, gives a lower bound on the topological Hausdorff dimension of quasisymmetric images of the space.  We obtain results concerning the behavior of this quantity under products and unions, and compute it for some classical fractals.  The range of possible values of the topological conformal dimension is also considered, and we show that this quantity can be fractional.
\end{abstract}

\maketitle

\section{Introduction}

For a metric space $(X,d),$ the topological dimension can be defined inductively as
\begin{align*}
\dim_t X=\inf\{c: X\text{ has a basis }\mathcal{U}\text{ such that } \dim_t\partial U\leq c-1~\text{for all}~ U\in\mathcal{U}\},
\end{align*}
where $\dim_t\varnothing=-1.$  Since topological dimension is bounded above by Hausdorff dimension, we write $\dim_t X\leq\dim_H X$  and say that $X$ is \textit{fractal} if $\dim_t X<\dim_H X$~\cite{BM}.

Topological dimension is invariant under homeomorphisms, while Hausdorff dimension is bi-Lipschitz invariant.  An intermediate interesting class of maps between the first two is quasisymmetric maps~\cites{JH,TV}.  In order to classify spaces up to quasisymmetric equivalence, it is useful to have a concept of dimension that is quasisymmetrically invariant.  One such example is conformal dimension~\cite{MT}, which we denote $\dim_C X.$

Conformal dimension is modeled after Hausdorff dimension, which measures the size of a metric space.  Recently, Balka, Buczolich and Elekes~\cite{BBE2} introduced the \textit{topological Hausdorff dimension}, which is a bi-Lipschitz invariant sensitive to connectivity.  Unlike conformal dimension, this dimension is not quasisymmetrically invariant (Theorem~\ref{dimth theorem}).  Indeed, it can be arbitrarily increased by quasisymmetric maps (Fact \ref{effect of snowflake on tH}).  At present, there are no nontrivial lower bounds on topological Hausdorff dimension of quasisymmetric images, unlike for Hausdorff dimension.

In this paper, we introduce a quasisymmetric invariant that delivers such a bound: the \textit{topological conformal dimension}, denoted $\dim_{tC}X.$  Writing $\dim_{tH}X$ for the topological Hausdorff dimension,
\begin{equation*}
\dim_{tH}f(X)\geq \dim_{tC}X
\end{equation*}
for every quasisymmetric mapping $f$ of $X.$  Our investigation uncovers a parallel between conformal dimension and topological conformal dimension.  The former detects rich families of curves, while the latter detects rich families of surfaces.  By definition,
\begin{equation*}
\dim_{tC}X=\inf\{c:X \text{ has a basis } \mathcal{U} \text{ such that } \dim_C \partial U\leq c-1 \text{ for all } U\in\mathcal{U}\}.
\end{equation*}

We obtain results concerning the behavior of this new quantity under products and unions, along with the range of its possible values.  The topological conformal dimension is computed for some classical fractals, often via comparison to the Hausdorff dimension.  The following theorem, proven in section 4, gives a two-sided estimate for the topological conformal dimension of a space that contains a  ``diffuse" family of surfaces.  This result is similar to that of Pansu; lower bounds for conformal dimension are based on the presence of a diffuse family of curves.  The Assouad dimension of $X$ is denoted $\dim_A X$~\cite{JH}.
\newtheorem*{ftc2}{Theorem \ref{ftc2}}
\begin{ftc2}
Let $(X,d,\mu)$ be a compact, doubling metric measure space with $\dim_A X=D<\infty.$  Suppose that there exists a family $\mathcal{Q}$ of surfaces with the following properties:
\begin{enumerate}[(i)]
\item[\textnormal{(i)}] there is a family $\{f_{\alpha}:\alpha\in J\}$ of $L-$bi-Lipschitz maps such that $Q_{\alpha}=f_{\alpha}([0,1]^2)$ for each $Q_{\alpha}\in\mathcal{Q}.$
\item[\textnormal{(ii)}] there exists a measure $\nu_0$ on $\mathcal{Q}$, a constant $C_0,$ and $r_0>0$ so that
\begin{equation*}\label{eqE}
0<\nu_0\{Q_{\alpha}\in\mathcal{Q}:Q_{\alpha}\cap B(x,r)\neq\emptyset\}\leq C_0 r^d
\end{equation*}
\noindent for all $x\in X$ and for all $r\leq r_0.$
\item[\textnormal{(iii)}] The union of edges $\bigcup_{\alpha\in J}f_{\alpha}\left(\partial([0,1]^2)\right)$ is not dense in $X.$
\end{enumerate}
Then $1+\frac{D}{D-d}\leq\dim_{tC} X\leq D .$
\end{ftc2}
Such spaces are shown to exist for every $0<d<1$ with $D=2+d.$  Since $2+\nicefrac{d}{2}\leq \dim_{tC}\leq 2+d$, it follows that the topological conformal dimension attains infinitely many fractional values even though they are not explicitly determined.  In particular, if $0<d<1$ and $D=2+d$, then $2<\dim_{tC}X<3$, which furnishes a collection of compact metric spaces with fractional topological conformal dimension.

A key difference between topological conformal dimension and topological Hausdorff dimension is that conformal dimension may increase under Lipschitz maps.  This makes it difficult to give a lower bound on topological conformal dimension, such as that in Theorem~\ref{ftc2}.

\section{Preliminaries and Basic Properties}

The subscripts of dim indicate the type of dimension.  By convention, every dimension of the empty set is $-1.$  For any set $A,~|A|$ means the cardinality of $A.$  We write $B(x,\eps)$ for the open ball centered at $x$ of radius $\eps.$  We will often refer to a basis of $X,$ by which we mean a basis for the topology on $X$ induced by the metric on $X.$  Our definition of topological conformal dimension is similar to that of the classical topological dimension and the topological Hausdorff dimension.  The \textit{topological Hausdorff dimension} is defined in~\cite{BBE2} as
\begin{align*}
\dim_{tH}X=\inf\{c:X\text{ has a basis }\mathcal{U}\text{ such that }\dim_H\partial U\leq c-1~\forall U\in\mathcal{U}\}.
\end{align*}
An embedding $f:X\rightarrow Y$ is \textit{quasisymmetric} if there is a homeomorphism $\eta:[0,\infty)\rightarrow [0,\infty)$ so that
\begin{align*}
d_X(x,a)\leq td_X(x,b)~\text{ implies }~d_Y(f(x),f(a))\leq\eta(t)d_Y(f(x),f(b))
\end{align*}
for all triples $a,b,x$ of points in $X,$ and for all $t>0$ ~\cite{JH}.  The conformal dimension is defined via the Hausdorff dimension.  For the latter, recall that the \textit{p-dimensional Hausdorff measure} of $X$ is
\begin{align*}
\mathcal{H}^p(X)=\lim_{\delta\rightarrow 0}\inf\left\{\sum (\diam E_j)^p: X\subset \bigcup E_j\text{ and }\diam E_j\leq\delta~\forall j\right\}.
\end{align*}
The \textit{Hausdorff dimension} of $X$ is $\dim_H X=\inf\{p:\mathcal{H}^p(X)=0\},$ and the \textit{conformal dimension} of $X$ is
\begin{align*}
\dim_C X=\inf\left\{\dim_H f(X):f\text{ is quasisymmetric}\right\}.
\end{align*}

\begin{definition}
The \textit{topological conformal dimension} of a metric space $(X,d)$ is
\begin{equation}\label{defc}
\dim_{tC}X=\inf\{c:X \text{ has a basis } \mathcal{U} \text{ such that } \dim_C \partial U\leq c-1 \text{ for all } U\in\mathcal{U}\}
\end{equation}
\end{definition}

We will have occasion to use the following two facts.
\begin{align}
\dim_t X\leq \dim_C X\leq \dim_H X \label{f2}\\
\dim_t X\leq\dim_{tC}X\leq\dim_{tH}X\leq\dim_H X \label{f1}
\end{align}

\begin{proof}
Inequality \eqref{f2} is well known~\cite{MT}.  For the first inequality in \eqref{f1}, let $\mathcal{U}$ be a basis of $X$ and $U\in\mathcal{U}.$  By \eqref{f2} we have $\dim_t\partial U\leq\dim_C\partial U,$ so if $\dim_C\partial U\leq c-1$ then $\dim_t\partial U\leq c-1.$  It follows that $\dim_t X\leq\dim_{tC}X.$  Using \eqref{f2}, the same argument gives $\dim_{tC}X\leq\dim_{tH}X.$  The inequality $\dim_{tH}X\leq\dim_H X$ is Theorem~4.4~in~\cite{BBE2}.
\end{proof}
By Fact~4.1~in~\cite{BBE2} we have $\dim_{tH}X=0\Leftrightarrow \dim_t X=0,$ so \eqref{f2} yields
\begin{equation}
\dim_t X=0\Leftrightarrow \dim_{tC}X=0\Leftrightarrow \dim_{tH} X=0.\label{00}
\end{equation}

\begin{proposition}
If $X$ is a metric space, then $\dim_t X\leq \dim_{tC} X\leq \dim_C X.$
\end{proposition}

\begin{proof}
 The first inequality is \eqref{f1}.  For the second, let $ \eps>0.$  By definition of $\dim_C X$ there is a quasisymmetric map $f$ with $\dim_H f(X) \leq \dim_C X+\eps.$  Since the topological conformal dimension is a quasisymmetric invariant, we have
\begin{equation}
\dim_{tC}X=\dim_{tC}f(X)\leq\dim_{tH}f(X)\leq\dim_H f(X)\leq\dim_C X+\eps. \qedhere
\end{equation}
\end{proof}

\begin{proposition}
The topological conformal dimension of a countable set is zero, and for open subsets of $\mathbb{R}^d$ and for smooth $d-$dimensional manifolds, the topological conformal dimension is $d.$
\end{proposition}
\begin{proof}
This follows immediately from \eqref{f1}.
\end{proof}

It is clear from the definition that the topological conformal dimension is invariant under quasisymmetric maps.  In particular, it is invariant under bi-Lipschitz maps.  The following examples are along the lines of those in ~\cite{BBE2}.  The next example shows that the topological conformal dimension can increase under Lipschitz maps in general, and Example~4.12~in~\cite{BBE2} gives an example with an injective Lipschitz map.

\begin{example}\label{lip example}
 Let $K\subset [0,1]$ be a Cantor set of positive Lebesgue measure.  Lemma~4.10~in~\cite{BBE2} gives a surjective Lipschitz map $f:K\rightarrow [0,1],~\text{namely}~f(x)=\frac{m((-\infty,x)\cap K)}{m(K)},$ where $m$ is Lebesgue measure.  Since $K$ has a basis of clopen sets, we have $\dim_t K=\dim_{tC}K=0.$  Also $1=\dim_{tC}[0,1]=\dim_{tC}f(K),$ so $\dim_{tC}K<\dim_{tC}f(K).$
\end{example}

\section{Behavior Under Inclusions, Unions, and Products}

As with other types of dimension, tC-dimension is monotone under inclusion.
\begin{proposition} \textnormal{(Monotonicity under inclusion)}
If $X$ is a subset of a metric space $Y$, then $\dim_{tC}X\leq\dim_{tC}Y.$
\end{proposition}
\begin{proof}
If $\mathcal{U}$ is a basis of $Y$ then $\{U\cap X:U\in\mathcal{U}\}$ is a basis in $X$ and $\partial_X(U\cap X)\subset\partial_Y U$ holds for all $U\in\mathcal{U}.$  Note that monotonicity of conformal dimension follows from monotonicity of Hausdorff dimension.  Thus $\dim_C \partial_X(U\cap X)\leq\dim_C\partial_Y U,$ so the result follows.
\end{proof}

Conformal dimension is stable under finite disjoint unions of compact sets (\cite{MT}, Proposition~5.2.3).  The same is true of the topological conformal dimension.

\begin{fact}\label{th1}
 If $S_1$ and $S_2$ are disjoint compact subsets of a metric space and if $S=S_1\cup S_2,$ then $\dim_{tC}S=\max\{\dim_{tC}S_1,\dim_{tC}S_2\}.$
\end{fact}

\begin{proof}
 Let $\eps>0.$  We find a basis $\mathcal{U}$ of $S$ and $d\geq 0$ such that $\dim_C \partial U\leq d-1$ for all  $U\in\mathcal{U},$ and such that $d\leq \max\{\dim_{tC}S_1,\dim_{tC}S_2\}+\eps.$
By definition of the topological conformal dimension, for $i=1,2$ there exist $\mathcal{U}_i,d_i$ such that $\mathcal{U}_i$ is a basis for $S_i,~\dim_C \partial U_i\leq d_i-1$ for all $U_i\in\mathcal{U}_i,$ and $d_i\leq \dim_{tC}S_i+\eps.$

Consider the basis $\mathcal{U}=\mathcal{U}_1\cup\mathcal{U}_2$ of $S$ and let  $d=\max\{d_1,d_2\}.$  For each $U=U_1\cup U_2\in\mathcal{U},~\partial U_1$ and $\partial U_2$ are disjoint compact sets, so $\partial U=\partial U_1\cup \partial U_2$ and Proposition~5.2.3~in~\cite{MT} implies
\begin{equation}
\begin{split}
\dim_C \partial U=&\max\{\dim_C \partial U_1,\dim_C \partial U_2\}\\ \label{x}
\leq & \max\{d_1-1,d_2-1\}\\
\leq & \max\{\dim_{tC}S_1,\dim_{tC}S_2\}+\eps-1.
\end{split}
\end{equation}
Inequality (\ref{x}) yields $\dim_{tC}S\leq \max\{\dim_{tC}S_1,\dim_{tC}S_2\}$ and  monotonicity gives the opposite inequality.
\end{proof}

\begin{corollary}\label{cor12}
 If $\{X_1,\dots,X_n\}$ is a disjoint family of compact subsets of a metric space, then $\dim_{tC}\bigcup_{i=1}^n X_i=\max\{\dim_{tC} X_i|i=1,\dots,n\}.$
\end{corollary}

Unlike the Hausdorff dimension, the next example shows that finite stability does not hold for non-closed sets.

\begin{example}
Each of $\mathbb{Q}$ and $\mathbb{R}\setminus\mathbb{Q}$ has a basis of clopen sets, so their topological dimensions are zero.  Then \eqref{00} gives $\dim_{tC}\mathbb{Q}=\dim_{tC}(\mathbb{R}\setminus\mathbb{Q})=0.$  By \eqref{f1} we have $\dim_{tC}\mathbb{R}=1$ so that
\begin{align*}
\dim_{tC}\mathbb{R}=1>0=\max\{\dim_{tC}\mathbb{Q},\dim_{tC}(\mathbb{R}\setminus\mathbb{Q})\}.
\end{align*}
\end{example}

\subsection{Dimension of Products}
For two metric spaces $X$ and $Y$ we consider the product space $Z=X\times Y$ with metric
\begin{equation*}
d_Z((x_1,y_1),(x_2,y_2))=\max (d_X(x_1,x_2),d_Y(y_1,y_2)).
\end{equation*}
Under certain favorable conditions, Hausdorff dimension is additive under products~\cite{PM}.  This is not the case for conformal dimension~\cite{MT}.  In section 4 we will see that topological conformal dimension is also not additive under products (Corollary \ref{tc not additive}).  In this section we provide an upper bound on the tC-dimension of the product of two Jordan arcs.  This requires a lemma pertaining to the conformal dimension of the union of two \textit{proper}, \textit{uniformly perfect} subsets of a metric space.

\begin{lemma}\label{arcthm}
Let $(X,d)$ be a metric space with  proper uniformly perfect subsets $A$ and $B$ such that $A\cup B=X.$  Then $\dim_C X=\max\{\dim_C A,\dim_C B\}.$
\end{lemma}

The proof of Lemma \ref{arcthm} relies heavily on Theorem~1~in~\cite{PH} several times, so it is included below.  A metric space $X$ is called \textit{proper} if closed and bounded subsets are compact.  It is called \textit{uniformly perfect} if there is a constant $C\geq 1$ so that for each $x\in X$ and for each $r>0$ the set $B(x,r)\setminus B(x,\frac{r}{C})$ is nonempty whenever the set $X\setminus B(x,r)$ is nonempty~\cite{JH}.

\begin{theorem}\textnormal{(Haissinsky)}\label{haissinsky}
Let $(X,d_X)$ be a proper metric space containing at least two points and $(Y,d_Y)$ a proper uniformly perfect space.  Suppose there is a quasisymmetric embedding $f:Y\rightarrow X.$  Then there is a metric $\hat{d}$ on $X$ such that
\begin{enumerate}[(i)]
\item[\textnormal{(i)}] $\id:(X,d_X)\rightarrow (X,\hat{d})$ is quasisymmetric;
\item[\textnormal{(ii)}] $\id:(X\setminus f(Y),d_X)\rightarrow (X\setminus f(Y),\hat{d})$ is locally bi-Lipschitz;
\item[\textnormal{(iii)}] $f:(Y,d_Y)\rightarrow (X,\hat{d})$ is bi-Lipschitz onto its image.
\end{enumerate}
\end{theorem}

\begin{proof}[Proof of Lemma \ref{arcthm}]
Put $c=\dim_C(A,d)$ and $c'=\dim_C(B,d).$  Let $\eps>0.$  By definition of conformal dimension there is a quasisymmetric map $g$ with $\dim_H g(A,d)\leq c+\eps.$  Then $f=g^{-1}:g(A,d)\rightarrow X$ is a quasisymmetric embedding.  Since $A$ and $B$ are proper, it follows that $X$ is also proper.  Indeed, let $E\subset X$ be closed and bounded.  Then $E=(E\cap A)\cup (E\cap B)$ and since $E$ is closed in $X,~E\cap A$ and $E\cap B$ are closed in $A$ and $B,$ respectively.  Since $E$ is bounded, $E\cap A$ and $E\cap B$ are also bounded.  Therefore $E\cap A$ and $E\cap B$ are compact since $A$ and $B$ are proper.  Then $E$ is a union of two compact sets and hence is compact, so $X$ is proper.  By Theorem~\ref{haissinsky} there is a metric $d_1$ on $X$ such that
\begin{align}
\id\colon&(X,d)\rightarrow (X,d_1)~\text{is quasisymmetric} \label{1}\\
\id\colon&(X\setminus A,d)\rightarrow (X\setminus A,d_1)~\text{is locally bi-Lipschitz}\label{2}\\
f\colon&g(A,d)\rightarrow (A,d_1)~\text{is bi-Lipschitz}\label{3}
\end{align}

Since the restriction of a quasisymmetric map is again quasisymmetric, \eqref{1} implies $\dim_C(B,d_1)=\dim_C(B,d)=c'.$  Therefore there is a quasisymmetric map $r$ such that $\dim_H r(B,d_1)\leq c'+\eps.$  Then $h=r^{-1}:r(B,d_1)\rightarrow (X,d_1)$ is a quasisymmetric embedding with image $(B,d_1).$  Since $r$ is a homeomorphism,  $r(B,d_1)$ is proper and uniformly perfect.  Another application of Theorem~\ref{haissinsky} gives a metric $d_2$ on $X$ such that
\begin{align}
\id:~&(X,d_1)\rightarrow (X,d_2)~\text{is quasisymmetric}\label{4}\\
\id:~&(X\setminus B,d_1)\rightarrow (X\setminus B,d_2)~\text{is locally bi-Lipschitz}\label{5}\\
h:~&r(B,d_1)\rightarrow (B,d_2)~\text{is bi-Lipschitz}\label{6}
\end{align}

Locally bi-Lipschitz maps preserve Hausdorff dimension, so \eqref{5} and \eqref{3} yield
\begin{equation}\label{6'}
\begin{split}
\dim_H(X\setminus B,d_2)&=\dim_H(X\setminus B,d_1)\\
&\leq\dim_H(A,d_1)\\
&=\dim_H g(A,d).
\end{split}
\end{equation}
Also \eqref{6} shows that $\dim_H(B,d_2)=\dim_H r(B,d_1),$ so by \eqref{6'} we have
\begin{equation}
\begin{split}
\dim_H(X,d_2)=&\max\{\dim_H(X\setminus B,d_2),\dim_H(B,d_2)\}\label{7}\\
\leq& \max\{\dim_H g(A,d),\dim_H r(B,d_1)\}\\
\leq& \max\{c+\eps,c'+\eps\}\\
=&\max\{c,c'\}+\eps.
\end{split}
\end{equation}

Finally \eqref{4}, \eqref{7} and monotonicity give $\dim_C (X,d_1)=\max\{c,c'\}$ so that (\ref{1}) implies $\dim_C (X,d)=\max\{c,c'\}.$
\end{proof}

\begin{theorem}
If $\Gamma$ and $\Lambda$ are Jordan arcs then
\[
2\leq\dim_{tC}(\Gamma\times\Lambda)\leq \max\{\dim_C\Gamma,\dim_C\Lambda\}+1.
\]
\end{theorem}

\begin{proof}
The first inequality is due to the fact that $2=\dim_t (\Gamma\times \Lambda)\leq \dim_{tC}(\Gamma\times\Lambda).$  For the second inequality, let $\mathcal{U}=\{\gamma((c,d))\times \lambda((a,b)):a,b,c,d\in[0,1]\}$ where $\gamma,~\lambda$ are the homeomorphisms parametrizing $\Gamma,~\Lambda$ respectively.  Let $A\times B\in\mathcal{U}$ where $A=\gamma(c,d),~B=\lambda(c,d).$ Since $A$ and $B$ are open, the interior of $A\times B$ is again $A\times B,$ so we may write $\partial (A\times B)$ as
\begin{align}
\partial(A\times B)=&\overline{A\times B}\setminus (A\times B) \notag \\
=&(\partial A\times B)\cup (A\times\partial B)\cup (\partial A\times\partial B)  \label{8} \\
=&\left((\overline{A}\times\{\lambda(c)\})\cup (\{\gamma(b)\}\times \overline{B})\right)\cup\left( \overline{A}\times\{\lambda(d)\})\cup (\{\gamma(a)\}\times\overline{B})\right). \notag
\end{align}

Let $S=(\overline{A}\times\{\lambda(c)\})\cup (\{\gamma(b)\}\times \overline{B})$ and $T=(\overline{A}\times\{\lambda(d)\})\cup (\{\gamma(a)\}\times\overline{B}).$  Since each of $S$ and $T$ is a union of two connected sets, Lemma \ref{arcthm} gives
\begin{equation}
\begin{split}
\dim_C S=&\max\{\dim_C (\overline{A}\times\{\lambda(c)\}),\dim_C  (\{\gamma(b)\}\times \overline{B})\} \\ =& \max\{\dim_C \overline{A},\dim_C \overline{B}\}\label{9}\\
\dim_C T=&\max\{\dim_C (\overline{A}\times\{\lambda(d)\}),\dim_C (\{\gamma(a)\}\times\overline{B})\} \\ = &\max\{\dim_C \overline{A},\dim_C \overline{B}\}
\end{split}
\end{equation}
Since $S$ and $T$ are connected, Lemma \ref{arcthm}, \eqref{8} and \eqref{9} yield
\begin{align*}
\dim_C \partial(A\times B)=&\max\{\dim_C S,\dim_C T\}\\
=&\max\{\dim_C \overline{A},\dim_C \overline{B}\}\\
\leq&\max\{\dim_C \Gamma,\dim_C \Lambda\}.
\end{align*}
The conclusion now follows from the definition of the topological conformal dimension.
\end{proof}

We conclude this section with a simple observation that classifies product spaces consisting of two factors; one factor is the unit interval, the other has conformal dimension zero.

\begin{fact}\label{easy product proposition}
If $\dim_C X=0$ then $\dim_{tC}(X\times [0,1])=1.$
\end{fact}

\begin{proof}
Since $X\times [0,1]$ contains a line segment, $\dim_{tC} (X\times [0,1])\geq 1.$  On the other hand, $X$ has a basis $\mathcal{U}$ of clopen sets since $\dim_t X\leq\dim_C X=0.$  Then for every $U\in\mathcal{U}$ and $0\leq a\leq b\leq 1$ we have
\begin{align*}
\dim_C \partial(U\times (a,b))&=\dim_C (U\times \partial(a,b))\\
&=\dim_C (U\times\{a,b\})\\
&=\dim_C U\\
&\leq\dim_C X=0.\qedhere
\end{align*}
\end{proof}

\section{Range of Dimension}

Taking products of Cantor sets, one sees that the Hausdorff dimension attains all values in $[0,\infty]$.  Topological Hausdorff dimension attains all values in $[1,\infty]$ by Theorem~4.24~in~\cite{BBE2}.  It was shown in ~\cite{JT} that conformal dimension attains all values in $[1,\infty],$ and later in \cite{LK} that it does not attain any value in $(0,1)$.  Possible values of the topological conformal dimension are restricted to $\{-1,0,1\}\cup[2,\infty].$

\begin{fact}
The topological conformal dimension cannot take any value in $(1,2).$
\end{fact}
\begin{proof}
If $X=\varnothing$ then $\dim_{tC}X =-1.$  Let $X$ be a nonempty metric space with $\dim_{tC}X=c$ and suppose $1<c<2.$  By definition of the topological conformal dimension there is a number $d$ and a basis $\mathcal{U}$ for $X$ such that $1<c<d<2$ and $\dim_C\partial U\leq d-1$ for all $U\in\mathcal{U}.$  Then \cite{LK} implies $\dim_C \partial U=0$ for all $U\in\mathcal{U}$ so that $\dim_{tC}X\leq 1,$ a contradiction.
\end{proof}

For tC-dimension, all integer values in $[2,\infty]$ are realized by Euclidean spaces.  It is more involved to obtain examples that attain non-integer values.  Theorem~\ref{ftc2} gives one method for accomplishing this task.  In particular, it shows that there are compact subsets of $\mathbb[0,1]^3$ with fractional topological conformal dimension.

\begin{definition}A metric space $X$ is \textit{Ahlfors $d$-regular} if it admits a Borel regular measure $\mu$ such that
\begin{equation}
\frac{1}{K}r^d\leq\mu\left(\overline{B}(x,r)\right)\leq Kr^d
\end{equation}
for some constant $K\geq 1$ for all balls ${B}(x,r)$ of radius $0<r<2\diam X.$
\end{definition}

The primary tool we use to prove Theorem~\ref{ftc2} is Proposition~4.1.3~in~\cite{MT}, so it is included here for sake of completeness.

\begin{proposition}\label{MT prop}\textnormal{(Pansu)}
Let $(Z,d,\mu)$ be a compact, doubling metric measure space, and let $1<p<\infty$ and $p'=\frac{p}{p-1}.$ Suppose that there exists a family $\mathcal{E}$ of connected sets in $Z$ and a probability measure $\nu$ on $\mathcal{E}$ with the following properties:
\begin{enumerate}[(i)]
\item[\textnormal{(i)}] there exists $c>0$ so that $\diam E\geq c$ for all $E\in\mathcal{E},$ and
\item[\textnormal{(ii)}] there exists $C$ and $r_0>0$ so that
\begin{equation}\label{eq10}
\nu\{E\in\mathcal{E}:E\cap B(x,r)\neq\varnothing\}\leq C\mu(B(x,r))^{\nicefrac{1}{p'}}
\end{equation}
for all balls $x\in Z$ and for all $r\leq r_0.$
\end{enumerate}
Then $\dim_C Z\geq p.$
\end{proposition}

\begin{lemma}\label{fractaltclemma}
If $A\subset \mathbb{C}$ is open, connected, and bounded, then there is a connected set $E\subset\partial A$ such that $\diam E=\diam A.$
\end{lemma}

\begin{proof}
Let $\{S_{\alpha}|\alpha\in J\}$ be the set of connected components of $\overline{A}^c$ and let $\beta\in J$ be such that $S_{\beta}$ is unbounded.  We will show that $E=\partial S_{\beta}$ satisfies the conclusion of the lemma.

The Phragm\'en-Brouwer theorem (Theorem VI.2.1~in~\cite{GW}) shows that $\partial S_{\beta}$ is connected.  Note that $\partial S_{\beta}\subset \partial A.$  Indeed, if $w\in \partial S_{\beta}\setminus \partial A$ then either $w\in A$ or $w\in \overline{A}^c.$  If $w\in \overline{A}^c$ then $w\in S_{\gamma}$ for some $\gamma\neq \beta.$  Since $\overline{S_{\beta}}$ is connected and $\partial S_{\beta}\subset \overline{S_{\beta}},$ we have $S_{\beta}\subset S_{\gamma},$ a contradiction.  If $w\in A$ then $S_{\beta}\subset\overline{S_{\beta}}\subset A$, a contradiction.

For $z\in\mathbb{C}$ let $\text{Arg}(z)$ be the principal argument of $z.$  Without loss of generality, let $0\in A$ and choose an argument $-\pi<\phi\leq\pi$ and a point $z\in\mathbb{C}$ with $|z|>\diam\overline{A}$ and $\text{Arg}(z)=\phi.$  Connect $0$ to $z$ by a line segment; call it $L.$  The function $w\mapsto |w|$ is continuous on the compact set $L\cap\overline A,$ so it attains a maximum on $L\cap\overline{A},$ say at $z_{\phi}.$

Put $F=\{z_{\phi}:-\pi<\phi\leq\pi\}.$  We claim that $\diam F\geq\diam A$.  To see this, choose $a,b\in\partial A$ such that $|a-b|=\diam A.$  We will show that $a,b\in F.$  Since $0\in A$ we have $|a-b|>|a|$ and $|a-b|>|b|.$  Note that the function $f(t)=|ta-b|$ is strictly convex on $[0,\infty)$ and $f(0)=|b|<|a-b|=f(1).$  Then $f$ is strictly increasing on $[1,\infty)$ so that $ta\notin A$ for all $t>1.$  It follows that $a\in F$ and similarly $b\in F.$  Clearly  $F\subset(\partial A)\cap(\partial S_{\beta})$.  Therefore $\diam \partial S_{\beta}\geq \diam F\geq\diam A.$  Since $\partial S_{\beta}\subset \overline{A}$ we see that $\diam \partial S_{\beta}\leq\diam\overline{A}=\diam A,$ so $\diam E=\diam A$ with $E=\partial S_{\beta}.$
\end{proof}

The following theorem is the main result of this section.  Recall that $f:X\rightarrow Y$ is $L-$bi-Lipschitz if both $f$ and $f^{-1}$ are $L-$Lipschitz.  We write $\dim_A X$ for the Assouad dimension of $X,$ see \cite{JH},\cite{MT}.
\begin{theorem}\label{ftc2}
Let $(X,d,\mu)$ be a compact, doubling metric measure space with $\dim_A X=D<\infty.$  Suppose that there exists a family $\mathcal{Q}$ of surfaces with the following properties:
\begin{enumerate}[(i)]
\item[\textnormal{(i)}] There is a family $\{f_{\alpha}:\alpha\in J\}$ of $L-$bi-Lipschitz maps such that $Q_{\alpha}=f_{\alpha}([0,1]^2)$ for each $Q_{\alpha}\in\mathcal{Q}.$
\item[\textnormal{(ii)}] There exists a measure $\nu_0$ on $\mathcal{Q}$, a constant $C_0,$ and $r_0>0$ so that
\begin{equation}\label{eqE}
0<\nu_0\{Q_{\alpha}\in\mathcal{Q}:Q_{\alpha}\cap B(x,r)\neq\emptyset\}\leq C_0 r^d
\end{equation}
\noindent for all $x\in X$ and for all $r\leq r_0.$
\item[\textnormal{(iii)}] The union of edges $\bigcup_{\alpha\in J}f_{\alpha}\left(\partial([0,1]^2)\right)$ is not dense in $X.$
\end{enumerate}
Then $\dim_{tC} X\geq 1+\frac{D}{D-d}.$
\end{theorem}

\begin{corollary}\label{ftc3}
Let $(C,\nu_C)$ be a compact Ahlfors $d-$regular metric measure space.  If $X=C\times[0,1]^2$ then $2+\nicefrac{d}{2}\leq\dim_{tC}X\leq 2+d.$
\end{corollary}

\begin{proof}[Proof of Theorem \ref{ftc2}]
Let $\mathcal{U}$ be a basis for $X$.  For each $\alpha$, call $f_{\alpha}(\partial_{\mathbb{C}}([0,1]^2))$ the \textit{edge} of $Q_{\alpha}.$  In this proof, $\partial G$ means the boundary of $G$ in $Q_{\alpha}.$  Boundaries in other spaces are indicated by subscripts.  Assumption (iii) shows that there is an open set $U'\subset X$ that does not meet the edge of $Q_{\alpha}$ for any $\alpha.$  Choose a nonempty $U\in\mathcal{U}$ such that $\overline U\subset U'.$  We will show that $\dim_C \partial_X U\geq \frac{D}{D-d}$ using Proposition \ref{MT prop}.

Choose a compact set $K\subset U$ with nonempty interior, and for each $\alpha$ with $K\cap Q_{\alpha}\neq\varnothing$ choose $z_{\alpha}\in K\cap Q_{\alpha}.$  Put $J_K=\{\alpha\in J:K\cap Q_{\alpha}\neq\varnothing\}.$  Let $B_{\alpha}$ be the connected component of $U\cap Q_{\alpha}$ containing $z_{\alpha}.$  Consider $A_{\alpha}=f_{\alpha}^{-1}(B_{\alpha})$.  Note that $A_{\alpha}$ is open, connected, and does not intersect $\partial_{\mathbb{C}}([0,1]^2),$ so Corollary \ref{fractaltclemma} gives a connected set $E_{\alpha}\subset\partial_{\mathbb{C}} A_{\alpha}$ with $\diam E_{\alpha}=\diam A_{\alpha}.$  Since $f_{\alpha}$ is a homeomorphism, $f_{\alpha}(E_{\alpha})$ is connected.

To satisfy the first part of condition (i) of Proposition \ref{MT prop}, define  $\mathcal{E}=\{f_{\alpha}(E_{\alpha}):\alpha\in J_K\}.$  We need to show that $f_{\alpha}(E_{\alpha})\subset\partial_X U.$  Since $B_{\alpha}$ is a component of $U\cap Q_{\alpha}$ we have $\partial B_{\alpha}\subset \partial(U\cap Q_{\alpha}).$  Then
\begin{equation}
\begin{split}
f_{\alpha}(E_{\alpha})\subset f_{\alpha}(\partial_{\mathbb{C}} A_{\alpha})&=\partial f_{\alpha}(A_{\alpha})=\partial B_{\alpha}\subset \partial(U\cap Q_{\alpha})\subset\partial_X U.
\end{split}
\end{equation}

To satisfy \eqref{eq10} we must show that there is $c>0$ such that $\diam f_{\alpha}(E_{\alpha})\geq c$ for all $\alpha\in J_K$.  We have
\begin{equation}
\begin{split}\label{eq13}
\diam f_{\alpha}(E_{\alpha})&\geq \frac{1}{L}\diam E_{\alpha}\\
&=\frac{1}{L}\diam A_{\alpha}\\
&\geq \frac{1}{L^2}\diam B_{\alpha}\\
\end{split}
\end{equation}
for all $\alpha\in J_K,$ so it suffices to show that there is $c'>0$ with $\diam(B_{\alpha})\geq c'$ for all $\alpha\in J_K.$  Since $\overline{B_{\alpha}}$ is connected and meets both $K$ and $\partial_X U,$ we see that $\diam B_{\alpha}\geq\dist(K,\partial_XU)=c'>0$.  Then \eqref{eq13} yields
\begin{equation}
\begin{split}\label{eq14}
\diam f_{\alpha}(E_{\alpha})\geq \frac{1}{L^2}\diam (B_\alpha)\geq \frac{c'}{L^2}
\end{split}
\end{equation}
for all $\alpha\in J_K,$ so condition (i) of Proposition \ref{MT prop} is satisfied with $c=\nicefrac{c'}{L^2}$.

To establish \eqref{eq10} we let $s>D$ and show that \eqref{eq10} holds with $p=\frac{s}{s-d}$ and $p'=\frac{s}{d}.$  Put $r_0=\diam\partial_X U.$  We need to use an existence theorem for doubling measures proved by Vol'berg and Konyagin, and extended by Luukainen and Saksman~\cite{LS}.  Since $s>D=\dim_A X\geq\dim_A\partial_X U,$ the Corollary to Theorem 1 in \cite{LS} together with Theorem 13.5 in \cite{JH} show that $\partial_X U$ carries a $(t_0,s)-$homogeneous measure for some $t_0.$  So there is a doubling measure $\mu_0$ on $\partial_X U$ satisfying
\begin{equation}\label{eq15}
\mu_0(B(x,\lambda r))\leq t_0\lambda^s\mu_0(B(x,r))
\end{equation}
for all $x\in \partial_X U,~r>0,$ and $\lambda\geq 1.$  Fix such a ball $B(x,r).$  With $\lambda=\frac{\diam\partial_X U}{r},$ inequality \eqref{eq15} gives
\begin{equation}\label{eq16}
\mu_0(B(x,r))\geq\frac{\mu_0(\partial_X U)}{t_0(\diam\partial_X U)^s}r^s=Mr^s
\end{equation}
so that
\begin{equation}\label{eq17}
\mu_0(B(x,r))^{\nicefrac{1}{p'}}\geq M^{\nicefrac{1}{p'}}r^d.
\end{equation}

To finish establishing \eqref{eq10} we need to define a measure $\nu$ on $\mathcal{E}.$  Let $F_{\alpha}=f_{\alpha}(E_{\alpha}),$ and for $F\subset \mathcal{E}$ define
\begin{equation}\label{eq18}
\nu(F)=K_0\nu_0\{Q_{\alpha}:F_{\alpha}\in F\},
\end{equation}
where $K_0$ is such that $\nu(\mathcal{E})=1.$  Note that $F_{\alpha}\cap B(x,r)\neq\varnothing$ implies $Q_{\alpha}\cap B(x,r)\neq\varnothing.$  Coupled with \eqref{eq18} and \eqref{eqE}, this yields
\begin{equation}\label{eq19}
\begin{split}
\nu\{F_{\alpha}:F_{\alpha}\cap B(x,r)\neq\varnothing\}&\leq\nu\{F_{\alpha}:Q_{\alpha}\cap B(x,r)\neq\varnothing\}\\
&=K_0\nu_0\{Q_{\alpha}:Q_{\alpha}\cap B(x,r)\neq\varnothing\}\\
&\leq K_0 C_0 r^d.
\end{split}
\end{equation}
Now \eqref{eq19} and \eqref{eq17} give
\begin{equation}\label{eq20}
\begin{split}
\nu\{F_{\alpha}:F_{\alpha}\cap B(x,r)\neq\varnothing\}&\leq K_0 C_0 r^d\\
&\leq \frac{K_0 C_0}{M^{\nicefrac{1}{p'}}}\mu_0(B(x,r))^{\nicefrac{1}{p'}}\\
&=C\mu_0(B(x,r))^{\nicefrac{1}{p'}}.
\end{split}
\end{equation}

Since the choice of $B(x,r)$ was arbitrary, \eqref{eq20} holds for all such balls, so we have \eqref{eq10}.  Therefore $\dim_C \partial_X U\geq p=\frac{s}{s-d}$ for all $s>D.$  Letting $s\rightarrow D$ gives $\dim_C \partial_X U\geq \frac{D}{D-d}$ and hence $\dim_{tC}X\geq 1+\frac{D}{D-d}.$
\end{proof}

\begin{proof}[Proof of Corollary \ref{ftc3}]
The family of surfaces $\mathcal{Q}=\{\{x\}\times [0,1]^2: x\in C\}$ satifies conditions (i) and (iii) of Theorem \ref{ftc2}.  It remains to show that condition (ii) holds.

Let $d=\dim_H C$ and let $\pi_1:X\rightarrow C$ be the projection of $X$ onto $C.$  For $F\subset \mathcal{Q}$ define
\begin{equation}\label{eq21}
\nu_0(F)=\nu_C\left(\bigcup_{Q\in F} \pi_1(Q)\right).
\end{equation}
By Ahlfors regularity, there is a constant $N$ such that $\nu_C(\pi_1(B(x,r)))\leq Nr^d$ for all $z\in X$ and $0<r\leq\diam X.$  It now follows from \eqref{eq21} that
\begin{equation}\label{eq22}
\begin{split}
\nu_0\{Q\in\mathcal{Q}: Q\cap B(z,r)\neq\varnothing\}&=\nu_C\left(\bigcup_{E\cap B(z,r)\neq\varnothing}\pi_1(Q)\right)\\
&\leq \nu_C(\pi_1(B(z,r)))\\
&\leq Nr^d,
\end{split}
\end{equation}
which is condition (ii).  Since $X$ is Ahlfors $D-$regular with $D=2+d$ we have
\begin{equation}\label{eq23}
\dim_A(C\times [0,1]^2)=\dim_H (C\times [0,1]^2)=2+d=D.
\end{equation}
Equation \eqref{eq23} and Theorem \ref{ftc2} yield
\begin{equation*}
2+\nicefrac{d}{2}\leq\dim_{tC}X\leq 2+d. \qedhere
\end{equation*}
\end{proof}

\begin{corollary}\label{tc not additive}
Topological conformal dimension is not additive under products.  Moreover, this quantity can be fractional.
\end{corollary}
\begin{proof}
Letting $C$ be the middle-thirds Cantor set, the hypotheses of Corollary \ref{ftc3} are satisfied with $d=\frac{\ln(2)}{\ln(3)}$.  Since $C$ is totally disconnected, $\dim_{tC}C=0,$ so
\begin{equation}\label{eq24}
\dim_{tC} C+\dim_{tC} ([0,1]^2)=2< 2+\nicefrac{d}{2}\leq\dim_{tC}(C\times [0,1]^2).
\end{equation}
Also $\dim_{tC} (C\times [0,1]^2)\leq 2+d<3,$ so \eqref{eq24} shows that  $\dim_{tC}(C\times [0,1]^2)$ is not an integer.
\end{proof}

Theorem \ref{ftc2} provides hope for an affirmative answer to the following conjecture.

\begin{conjecture}
For every $d\in[2,\infty]$ there is a metric space $X$ with $\dim_{tC}X=d.$
\end{conjecture}

\section{Comparison with Other Dimensions}

In this section, examples are given to demonstrate that topological conformal dimension is different from topological dimension, conformal dimension, topological Hausdorff dimension, and Hausdorff dimension.  It is also shown that conformal dimension and tH-dimension are not comparable.  We compute the tC-dimensions of some classical fractals.  In particular, this type of dimension classifies the Sierpinski carpet as dimension 1, unlike the Hausdorff, topological Hausdorff, and conformal dimensions.

Due to the additivity of Hausdorff dimension under products and to the fact that  topological dimension only assumes integer values, the following fact is readily seen by considering Corollary \ref{tc not additive}.

\begin{fact}
Topological conformal dimension is different from topological dimension and Hausdorff dimension.
\end{fact}

Write $SG$ for the Sierpinski gasket and $SC$ for the Sierpinski carpet.  Laakso proved that $\dim_C SG=1$~\cite{TW}, while the value $\dim_C SC$ remains unknown~\cite{MT}.

\begin{example}\label{tc of carpet}
$\dim_{tC}SG=\dim_{tC}SC=1.$
\end{example}
\begin{proof}
Since $SG$ contains a line segment, $\dim_{tC}SG\geq 1,$ and we have $\dim_{tC}SG\leq\dim_H SG=\frac{\ln(3)}{\ln(2)}<2.$  Since $\dim_{tC}SG\notin (1,2),$ it follows that $\dim_{tC}SG=1.$

Similarly, since $SC$ contains a line segment, $\dim_{tC}SC\geq 1$.  On the other hand, $\dim_{tC}SC\leq\dim_H SC=\frac{\ln(8)}{\ln(3)}<2$ so that $\dim_{tC}SC=1.$
\end{proof}

In light of Example \ref{tc of carpet}, we observe the following fact.

\begin{fact}
Topological conformal dimension is different from conformal dimension and topological Hausdorff dimension.
\end{fact}
\begin{proof}
If $C$ is the middle-thirds Cantor set, monotonicity of conformal dimension implies $\dim_C SC\geq \dim_C (C\times [0,1]).$  By Proposition 4.1.11 in \cite{MT},  $\dim_C (C\times [0,1])=1+\frac{\ln(2)}{\ln(3)}$, so $\dim_C SC\geq 1+\frac{\ln(2)}{\ln(3)}.$  By Theorem~5.4~in~\cite{BBE2}, $\dim_{tH}SC=1+\frac{\ln(2)}{\ln(3)}.$
\end{proof}

\begin{fact}
Conformal dimension and topological Hausdorff dimension are not comparable.
\end{fact}
\begin{proof}
We produce spaces $X$ and $Y$ such that $\dim_C X<\dim_{tH}X$ and $\dim_C Y>\dim_{tH}Y.$  Let $0<\alpha<1$ and let $\left([0,1]^n\right)^{\alpha}$ be the metric space that results from snowflaking $[0,1]^n$, as in Fact~\ref{effect of snowflake on tH} below.  By Fact~\ref{effect of snowflake on tH},
\begin{equation*}
\dim_{tH}\left(([0,1]^n)^{\alpha}\right)=\frac{n-1}{\alpha}+1>n=\dim_C\left(([0,1]^n)^{\alpha}\right).
\end{equation*}
On the other hand, if $K\subset\mathbb{R}$ is a uniformly perfect Cantor set with $\dim_HK=1,$ then $\dim_CK=1>\dim_{tH}K=0$ by Corollary 3.3 in \cite{H}.
\end{proof}

\begin{proposition}\label{arcprop}
 If $K$ is homeomorphic to $[0,1],$ then $\dim_{tC}K=1.$
\end{proposition}
\begin{remark}In particular, the topological conformal dimension of the von Koch snowflake is $1.$
\end{remark}
\begin{proof}[Proof of Proposition \ref{arcprop}]
Inequality (\ref{f2}) implies $\dim_{tC}K\geq 1.$  On the other hand, if $K$ is homeomorphic to $[0,1]$ then the usual basis of $[0,1]$ gives a basis $\mathcal{U}$ for $K$ such that $|\partial U|= 2$ for all $U\in\mathcal{U}.$  Then $\dim_C \partial U=0$ for all $U\in\mathcal{U}$ and hence $\dim_{tC}K\leq 1.$
\end{proof}

There are some well known fractals for which the tC-dimension remains unknown, such as Rickman's rug (defined in~\cite{MT}) and the Heisenberg group.  We can, however, compute both the tC and tH-dimensions of the Menger sponge (defined in \cite{MT}, section 3.5).  The following theorem is useful for computing the tH-dimension of the sponge.

\begin{theorem}\label{dimth product}
If $X$ is nonempty, locally compact, Ahlfors $d$-regular, and totally disconnected, and if  $Y$ is any separable metric space with $\dim_{tH}Y\geq 1$, then $\dim_{tH}(X\times Y)=\dim_H X+\dim_{tH}Y.$
\end{theorem}

\begin{proof}
If $\dim_{tH}Y=\infty$ then the statement is trivial, so assume $\dim_{tH}Y<\infty.$  We will first show
\begin{equation}\label{tH1}
\dim_{tH}(X\times Y)\leq \dim_H X+\dim_{tH}Y.
\end{equation}
Since $X$ is locally compact, $\dim_t X=0$ by Theorem~29.7~in~\cite{SW}, so X has a basis $\mathcal{U}$ consisting of clopen sets.  Let $\eps>0$ and choose a basis $\mathcal{V}$ of $Y$ such that $\dim_H\partial V\leq\dim_{tH}V-1+\eps$ for all $V\in\mathcal{V}.$  For $U\times V\in \mathcal{U}\times\mathcal{V}$ we have $\partial (U\times V)=U\times\partial V.$ Since $X$ is Ahlfors regular, Theorem~5.7~in~\cite{PM} implies that its upper Minkowski dimension $\overline{\dim}_M X$ is equal to $\dim_H X$. Corollary~8.10~in~\cite{PM} gives
\begin{equation}
\begin{split}
\dim_H(U\times\partial V)\leq \dim_H(X\times\partial V)&=\dim_H X+\dim_H\partial V\\
&\leq \dim_H X+\dim_{tH}Y-1+\eps. \label{10}
\end{split}
\end{equation}
Since $\eps>0$ was arbitrary \eqref{10} implies \eqref{tH1}.

For the reverse inequality, we show that for any $S\subset (X\times Y)$ where $(X\times Y)\setminus S$ is totally disconnected,
\begin{equation}
\dim_H S\geq \dim_H X+\dim_{tH}Y-1.\label{13}
\end{equation}
Once \eqref{13} is established for all such $S$, Theorem 3.6 in \cite{BBE2} will give the result.  For example, if $X$ is the middle-thirds Cantor set and if $Y=[0,1]^2$, one such subset is $S=X\times (Y\setminus (C\times C)).$  To this end, suppose there is $S$ such that (\ref{13}) fails.  Choose $\beta$ such that
\begin{equation}
\dim_{H}(S)<\beta<\dim_H X+\dim_{tH} Y-1  \label{11}
\end{equation}

Note that $X$ is proper since it is complete and Ahlfors regular.  Put $\dim_H X=d.$  By virtue of the coarea inequality (Theorem~2.10.25~in~\cite{HF})
\begin{equation}\label{coarea}
\int_X^* \mathcal{H}^{\beta-d}(S\cap(\{x\}\times Y))~d\mathcal{H}^d(x)\leq C \mathcal{H}^{\beta}(S).
\end{equation}
Then $\mathcal{H}^d(S)=0$ since $\beta>\dim_H S,$ so there exists $x\in X$ such that
\begin{equation}\label{12}
\dim_H (S\cap (\{x\}\times Y))\leq \beta-\dim_H X.
\end{equation}
On the other hand, since $Y$ is separable,
\begin{equation}\label{14}
\dim_H(S\cap(\{x\}\times Y))\geq\dim_{tH}Y-1
\end{equation}
by Theorem 3.6 in \cite{BBE2}.  Inequalities \eqref{12} and \eqref{14} yield
\begin{align*}
\dim_{tH}Y-1\leq\beta-\dim_H X,
\end{align*}
which contradicts \eqref{11}.
\end{proof}

Let $M$ denote the Menger sponge.  We compute $\dim_{tH}M$ followed by $\dim_{tC}M.$

\begin{example}\label{th of sponge}
$\dim_{tH}M=1+\frac{\ln(4)}{\ln(3)}.$
\end{example}
\begin{proof}
Consider the sets of intervals
\begin{align*}
W'&=\{[0,b):0<b<1;~b~\text{is a dyadic rational}\},\\
W''&=\{(a,1]:0<a<1;~a~\text{is a dyadic rational}\},\\
W'''&=\{(a,b):0< a<b<1;~a~\text{and}~b~\text{are dyadic rationals}\}.
\end{align*}
Put $W=W'\cup W''\cup W'''$ and let $\mathcal{U}=M\cap(W\times W\times W).$  Note that $\mathcal{U}$ is a basis of $M$ such that for all $U\in \mathcal{U},~ \partial U$ is a union of at most six sides of a cube in $M.$  Each side of $\partial U$ is a finite union of sets geometrically similar to $C\times C,$ where $C$ is the middle-thirds Cantor set.  Then $\dim_H\partial U=\frac{\ln(4)}{\ln(3)}$ so that $\dim_{tH}M\leq 1+\frac{\ln(4)}{\ln(3)}.$

On the other hand, $M$ contains $C\times SC$, so $\dim_{tH}M\geq\dim_{tH}(C\times SC)$ by monotonicity of the topological Hausdorff dimension.  Note that Theorem~5.4~in~\cite{BBE2} gives $\dim_{tH}SC=1+\frac{\ln(2)}{\ln(3)}$.  Since $C\times SC$ satisfies the hypotheses of Theorem~\ref{dimth product},
\begin{align*}
\dim_{tH}(C\times SC)=\dim_H C+\dim_{tH}SC=1+\frac{\ln(4)}{\ln(3)}.
\end{align*}
Thus $\dim_{tH}M\geq 1+\frac{\ln(4)}{\ln(3)}.$
\end{proof}

\begin{example}
$\dim_{tC}M=1.$
\end{example}
\begin{proof}
Let $\mathcal{U}$ be as in Example \ref{th of sponge}.  A similar argument shows that $\dim_{tC}M\leq 1+\dim_C (C\times C).$  Since $C\times C$ is uniformly disconnected, $\dim_C (C\times C)=0$~(\cite{MT}, section 1.3], so $\dim_{tC}M\leq 1.$  By monotonicity $\dim_{tC}M\geq 1.$
\end{proof}

\section{Quasisymmetric Distortion of Topological Hausdorff Dimension}

Topological Hausdorff dimension is not quasisymmetrically invariant.  For example, it increases under the snowflake transformation:
\begin{fact}\label{effect of snowflake on tH}
Let $(X,d)$ be a metric space and let $0<\alpha<1.$  If $X^{\alpha}=(X,d^{\alpha})$ is the snowflaked metric space defined by the transformation $d(x,y)\mapsto d(x,y)^{\alpha}$, then $\dim_{tH} (X^{\alpha})=\frac{1}{\alpha}(\dim_{tH}X-1)+1.$
\end{fact}
\begin{proof}
For any metric space $Z,$ snowflaking has the following effect on Hasdorff dimension: $\dim_H (Z^{\alpha})=\frac{1}{\alpha}\dim_H Z$ (\cite{MT}, Corollary 1.4.18).  Applying this fact to open subsets of $X^{\alpha}$ gives
\begin{equation}
\begin{split}
\dim_{tH}X^{\alpha}&=\inf\{c: X^{\alpha}~\text{has basis}~\mathcal{U}^{\alpha},~\dim_H (\partial U^{\alpha})\leq c-1~\forall U^{\alpha}\in\mathcal{U}^{\alpha}\}\\
&=\inf\{c: X~\text{has basis}~\mathcal{U},~\frac{1}{\alpha}\dim_H \partial U\leq c-1~\forall U\in\mathcal{U}\}\\
&=\inf\{c: X~\text{has basis}~\mathcal{U},~\dim_H \partial U\leq (\alpha c-\alpha +1)-1~\forall U\in\mathcal{U}\}\\
\end{split}
\end{equation}
The desired equality now follows from the definition of tH-dimension.
\end{proof}

More interestingly, there exist spaces which are minimal for conformal dimension, yet their topological Hausdorff dimension can be lowered by quasisymmetric maps.  This is the content of Theorem~\ref{dimth theorem}.  Note that if $C$ is a compact Ahlfors regular  metric space, then $C\times [0,1]$ is minimal for conformal dimension~\cite{JT}, i.e. $\dim_C (C\times[0,1])=\dim_H(C\times[0,1]).$

\begin{theorem}\label{dimth theorem}
Let $C$ be an Ahlfors $d-$regular metric measure space with $0<d<1,$ and let $X=C\times [0,1].$  For every $\eps>0$ there is a metric space $Y$ and a quasisymmetric map $f:X\rightarrow Y$ such that $\dim_{tH}Y\leq1+\eps.$

As a consequence, $\dim_{tC}X=1.$
\end{theorem}

\begin{remark} If $C$ is the middle thirds Cantor set, under the assumptions of Theorem~\ref{dimth theorem} we have $\dim_{tH}X=1+d$ by Lemma~4.21~in~\cite{BBE2}, and $\dim_C X=1+d$ by~\cite{JT} and Corollary~8.11~in~\cite{PM}.
\end{remark}

\begin{proof}
Let $D=\{\frac{a}{2^i}:a,i\in\mathbb{N},a\leq 2^i\}$ and write $D=\{y_1,y_2,\dots\}.$  For each $n$ let $\mu_n$ be the restriction of $\mathcal{H}^d$ to $C\times\{y_n\}.$
We define a measure $\nu$ on $X$ by
\begin{align*}
\nu(E)=\sum_{n=1}^{\infty}\frac{\mu_n(E)}{2^n}
\end{align*}

Let $\alpha>0.$  By Theorem 4.1 in ~\cite{LK} there is a quasisymmetric map $f:X\rightarrow Y$ such that for all $z=(x,y)\in X$ and for all $r>0$
\begin{equation}
\begin{split}
f(B(z,r))\subset B(f(z),R),~~\text{where}~R=\min\{C(\alpha)r^{\nicefrac{1}{\alpha}}\nu(B(z,r))^{\nicefrac{-1}{\alpha}},r\}.\label{20}
\end{split}
\end{equation}
Since $C$ is Ahlfors $d-$regular, there is a constant $K$ such that for every $x\in C$ and for $0<r\leq\diam C$
\begin{equation}
\begin{split}
\nu(B((x,y_j),r))&=\sum_{n=1}^{\infty}\frac{\mu_n(B((x,y_j),r)}{2^n}\\
&\geq \frac{\mu_j(B((x,y_j),r)}{2^j}\\
&\geq K2^{-j} r^d\\
&=K_j r^d.\label{21}\\
\end{split}
\end{equation}
Let $x_1,x_2\in C$ and put $z_1=(x_1,y_j),~z_2=(x_2,y_j),~r=|x_1-x_2|=d_X(z_1,z_2)=|z_1-z_2|.$ By \eqref{21}
\begin{equation}
\begin{split}\label{22}
R&\leq \frac{C(\alpha)r^{\nicefrac{1}{\alpha}}}{\nu(B(z_1,r))^{\nicefrac{1}{\alpha}}}\\
&\leq \frac{C(\alpha)r^{\nicefrac{1}{\alpha}}}{K_j^{\nicefrac{1}{\alpha}}\left(r^d\right)^{\nicefrac{1}{\alpha}}}\\
&=C(j,\alpha)r^{\frac{1-d}{\alpha}}\\
&=C(j,\alpha)|z_1-z_2|^{\frac{1-d}{\alpha}}
\end{split}
\end{equation}
where $C(j,\alpha)$ is a constant that depends only on $j$ and $\alpha.$  Continuity of $f$ and \eqref{20} imply $f(\overline{B}(z_1,r))\subset\overline{B}(f(z_1),R).$ Then $|f(z_1)-f(z_2)|\leq R$, so by \eqref{22}
\begin{equation}\label{23}
|f(z_1)-f(z_2)|\leq R\leq C(j,\alpha)|z_1-z_2|^{\frac{1-d}{\alpha}}.
\end{equation}
By \eqref{23} we see that for all $j$
\begin{align*}
\dim_H f(C\times\{y_j\})\leq \frac{\alpha}{1-d}\dim_H (C\times\{y_j\})=\frac{\alpha d}{1-d}.
\end{align*}
Since $\alpha$ was arbitrary, for every $\eps>0$ there is a quasisymmetric map $f_{\eps}:X\rightarrow Y$ such that $\dim_H f_{\eps}(C\times\{y_j\})\leq \eps$ for all $j.$  Notice that since $f_{\eps}$ is a homeomorphism, $f_{\eps}(X)\setminus f_{\eps}(C\times D)$ is totally disconnected.  Also $\dim_H f_{\eps}(C\times D)=\sup_j\dim_H f_{\eps}(C\times \{y_j\})\leq \eps$ so that Theorem 3.7~in~\cite{BBE2} gives $\dim_{tH} f_{\eps}(X)\leq 1+\eps.$

To see that $\dim_{tC}X=1,$ first note that $\dim_{tC}X\geq 1$ by montonicity.  Quasisymmetric invariance of the tC-dimension coupled with \eqref{f1} shows that for every $\eps>0,$
\begin{equation*}
\dim_{tC}X=\dim_{tC}f(X)\leq\dim_{tH}f(X)\leq 1+\eps.  \qedhere
\end{equation*}
\end{proof}

As stated in the introduction, topological conformal dimension gives a lower bound on the topological Hausdorff dimensions of quasisymmetric images of a given metric space.
\begin{equation}\label{24}
\dim_{tC}X\leq\inf\{\dim_{tH}f(X):f\text{ is quasisymmetric}\}.
\end{equation}

\begin{question}
Does equality hold in \eqref{24} for every metric space?
\end{question}

\subsection*{Acknowledgement} This paper is based on a part of a PhD thesis written by the author under the supervision of Leonid Kovalev.  The author thanks the anonymous referee for many useful suggestions in revising this paper.

\end{document}


TITLE: Action of the fundamental group
QUESTION [2 upvotes]: Suppose that $M$ is a smooth manifold. Is it true that the fundamental group $\pi_1(M)$ always acts on $M$? If so, how this action is defined?
EDIT: Of course I want my action to be nontrivial, say faithful. Moreover, I expect this action to have a geometric flavour.
I never saw such a statement but I wonder if it is this true. Very often in geometry one is interested in equivariant versions of some homology theories, so it seems that some manifolds are investigated together with some group action. Of course this is rather vaque motivation but reasons for asking questions may be very broad.

REPLY [3 votes]: You might want to look at a simple case like $S^1 = [0, 1] / 0 \sim 1$, whose fundamental group is $\mathbb Z$. It's true that you can define a faithful action of $\mathbb Z$ on $S^1$: send $1$ to the map $\theta \mapsto \theta + a$, where $a$ is some irrational number. (Alternatively and equivalently: define $n\cdot p$ to be $p + na \bmod 1$, where $a$ is some fixed irrational).
But this faithful action doesn't seem to capture much of the relationship between the fundamental group and the circle itself.
On the other hand, any action of $\mathbb Z$ on $S^1$ has to look something like this, for the orbit of a point $p$ under the action will generally be some infinite sequence of points of $S^1$, and this sequence should probably not have a limit, so they end up 'scattered' like the points $\{p + na \mid n \in \mathbb Z \}$ in the example above.
In short: looking at this simple example leads me to think that there's probably not a generally nice action of $\pi_1(M)$ on $M$.


TITLE: How do I calculate what the exact difference in the x-values are in these two linear plots?
QUESTION [0 upvotes]: I'm at work and I'm kind of drawing a blank right now since it is a Monday morning. So we have these two plots and there's some variation in temperature (the x-values) going on here. How can I calculate the value? The pink plot is our ideal and good data, while the green plot is the part of the tool not performing as well and running at higher than expected temperature. I am trying to see the difference in (x-values) temperatures between the two plots when they have the y-value or Rs.I know I can horizontally take my cursor and make a rough estimate on the temperature and I can see they're off by 12 degrees. But how can I show this mathematically?
Rs vs. Temp for two susceptors

REPLY [0 votes]: if I understand your problem right, you have the linear equation y=ax+b and y=cx+d, just modify for x=(y-b)/a and x=(y-d)/c and calculate the difference for equal y.


TITLE: Is there any curriculum based on recreational mathematics?
QUESTION [10 upvotes]: I'm a high school physics teacher. Next year, I'll be teaching mathematics for middle school students so I was wondering if there's a curriculum based on recreational mathematics  which not only present a sequence of puzzles and games but which also should have definite objectives. I hope there's such curricula because if not I'll have to make such one and it will take a really long time to author and test.

REPLY [2 votes]: Actually there is a number of such books, though I wouldn't call it a "curriculum".  I suggest you try the recent books by Ian Stewart, particularly Professor Stewart's Cabinet of Mathematical Curiosities (2008)
and Professor Stewart's Hoard of Mathematical Treasures: Another Drawer from the Cabinet of Curiosities (2009).


TITLE: About the order of a meromorphic function
QUESTION [5 upvotes]: In Gunning's book, lectures on Riemann surfaces, the order of a meromorphic function is defined as the order of the first non-zero coefficient in Laurent series of the function.
About this assertion, "the order of a meromorphic function f is non-zero only at a discrete set of points ", I don't understand the meaning, as we all know, locally a meromorphic function f is a quotient  of two holomorphic functions, say f=g/h, so ord(f)=Z(h) where Z(h) is the zero set of h, Z(h) is non-zero only at a discrete set of points? There must be some wrong of my understanding. So where is the wrong ? Any help will be greatly appreciated. Thanks

REPLY [3 votes]: By definition of a Riemann surface $X$ and a meromorphic function on $X$,
if $p \in X$ then there is a neighborhood $U $ of $p$ such that there is a local biholomorphism $\phi : U \to V \subset \mathbb{C}$, and $f$ is meromorphic at $p$ iff $f \circ \phi^{-1}$ is meromorphic at $\phi(p)$.
The order of the zero/pole of $f$ at $p$ is defined to be the order of $f \circ \phi^{-1}$ at $\phi(p)$ (this is consistent since the order of a zero or pole doesn't change under biholomorphic maps).
Yes, the zeros and poles of a meromorphic function on $X$ are isolated (be careful with the definition of isolated :  $0$ and $\infty  \not \in\mathbb{C}^* $, that's why the zeros of $\sin(1/z)\sin(z)$ which is meromorphic  on $\mathbb{C}^*$ can accumulate at $0$ and $\infty$).
That's why compact Riemann surfaces are much more restrictive : on those Riemann surfaces, there are no such "points" where the zero/poles can accumulate.
On Riemann surfaces, you can't say anymore that a meromorphic function is  globally the quotient of two holomorphic functions (on a compact Riemann surface, there are no non-constant holomorphic functions).


TITLE: multiplicity free chain of Lie subgroups gives a completely integrable system on symplectic manifold
QUESTION [5 upvotes]: Assume we have a symplectic manifold $N$ and a Hamiltonian action of a Lie group $G$, such that the algebra of all $G$-invariant functions on $N$ is commutative under Poisson bracket.
Furthermore, assume we have a ascending chain $ \{1\} =G_l\subset G_{l-1} \subset \dots \subset G_1 = G$ of Lie subgroups, such that the coadjoint-actions of $G_{i+1} $ on the coadjoint orbits of $G_i$ acting on $\mathfrak{g}_i^*$ is multiplicity-free. That means, that the algebra of all $G_{i+1}$-invariant functions on the $G_i$-orbits of $\mathfrak{g}_i^*$is commutative under the induced Poisson bracket.
Then we get that the Moment map of the $G_{i+1}$ action is just the projection of $\mathfrak{g_i^*}$ to $\mathfrak{g_{i+1}^*}$ restricted to the $G_i$-orbit on $\mathfrak{g_i^*}$.
Guillemin and Sternberg prove in their paper "On collective complete integrability according to the method of Thimm" that under these assumptions, $N$ is completely integrable. But I don't understand, how this assumptions already imply, that we find enough first Integrals, that are functionally independent on an open and dense subset on $N$.
I checked their book "symplectic techniques in physics" and their paper mentioned before, but couldn't find any answer to this problem.
They are just saying, if we take the trivial Lagrangian foliation on ${0}=\mathfrak{g}_l^*$ and pullback this foliation step by step to a foliation on $\mathfrak{g^*}$ we are done.
But then: How does this follow, or why are we done?
I hope someone can help me to understand this problem.

REPLY [1 votes]: I believe that in the paper "On collective complete integrability according to the method of Thimm" Guillemin and Sternberg showed the necessary conditions on G in order to get integrability in a system composed by collective motion, but they are not sufficient. If you have an integrable system composed by functions obtained from a chain of subgroups, i.e. collective, all the conditions that you have mentioned must be satisfied, but they are not enough to ensure integrability. In the case of coadjoint orbits of compact Lie groups SO(N) and U(N) the conditions are sufficient. The constraint is encoded in the algebra of invariant functions.


TITLE: How to construct three mutually orthogonal circles in stereographic projection?
QUESTION [10 upvotes]: I'm new to spherical geometry and I enjoy doing ruler-and-compass constructions, so I'm trying to teach myself to do them in stereographic projection. I'm finding it challenging, to put it mildly.
The following picture shows three mutually orthogonal great circles projected onto the plane (On the sphere it would look like this.):

The grey circle with the shading is the intersection of the sphere with the plane. The two purple circles are orthogonal and divide the sphere into four equal biangles (segments -- like so). The dotted circle is what I want but I made it by eye and can't figure out how to construct it properly. It's orthogonal to both purple circles, as the green tangent lines show (sort of -- I'm aware it's not terribly accurate).
So I have two questions:

How can I construct the dotted circle with ruler and compass? If the answer is, in fact, staring me in the face then a gentle hint would do!
Is there a good source, online or in a book, of practical instructions / guidance for doing this kind of thing by hand?

Any pointers would be very gratefully accepted.
[EDIT: Late last night it occurred to me that I had everything I needed to solve the problem except the following technique: given an arbitrary point in the plane, construct the projection of the great circle of which that point is a "centre" (i.e., the equator for which the given point is the North or South pole).
This would enable me to bisect (on the sphere!) one of the circle arcs that the required circle must cross; by symmetry it must clearly cross there (halfway), so this constructs a point on the circle. Then either do this three times and construct the circle on these three points or, more elegantly, construct the tangent to the purple circle at that point and the centre of the required circle will be where the tangent crosses the line pointed out by Will Jagy.]

OK, thanks to both Will Jagy and Willemien for coming up with solutions to this. I'm illustrating both for clarity here. They are closely-related but different. Although my intuition isn't all the way there yet, I'm convinced that these are both correct constructions. Certainly GeoGebra measures the circles to be identical, orthogonal to the two given circles and to cross the primitive at diametrically-opposed points.
First Willemein's solution:

Second, Will Jagy's (I actually did this first, and had to walk myself through it a bit more, so it's more annotated):

REPLY [1 votes]: In case anyone ever again looks at this... in my diagram giving the simple final construction, i claim that, given the "primitive" which is the  Equator, and the sterographic projection of a great circle from the North Pole, the projected circle must meet the Equator in a diameter of the Equator, also it is easy to find the projections of the two endpoint of the rotational "axis" of the given great circle. So, below I give two views. The top is edge on, along the sphere diameter that is the intersection of the plane of the Equator and the plane of the (blue) great circle. The rotational axis of the blue circle is in green, and the projections $\alpha_1, \alpha_2$ given. The other view is from above the plane of the equator, showing the Equator and the stereographic projection of the blue circle. Note that the blue circle does meet the Equator in a diameter of the Equator. Given that diagram, just two circles, it is quite easy to find the projections of $\alpha_1, \alpha_2,$ with the same arrangement of line segments as the diagram above. If we have a second and third great circle on the sphere, orthogonal to the blue one, then $\alpha_1, \alpha_2$ must lie on both circles, therefore on both projected circles.


TITLE: How to show that two statements are logically equivalent using different laws?
QUESTION [0 upvotes]: I have to show that
$(\backsim(P\vee Q))\vee(\backsim P\wedge Q)\cong \backsim P.$
I tried like this but do not know how to get the desired result using different laws
L.H.S$=(\backsim(P\vee Q))\vee(\backsim P\wedge Q)$
$=(\backsim(P\vee Q))\vee\backsim(\backsim((\backsim P\wedge Q))$
$=(\backsim(P\vee Q))\vee\backsim(\backsim\backsim P\vee\backsim Q))$ by De-Morgan' law
$=\backsim[(P\vee Q))\wedge( P\vee\backsim Q))]$ because $\backsim\backsim P=P$
I do not know  how to proceed further to get the desired result $\backsim P.$
I can prove this using truth table but do not know how to prove using different laws.
I need in detail answer.
Thank You!

REPLY [1 votes]: $\neg [(P∨Q))∧(P∨\neg Q)]$ is equivalent to $\neg [P\wedge (Q\vee\neg Q)]$ by distributivity. But $Q\vee \neg Q$ is logically true and so the formula is equivalent to $\neg [P\wedge true]$ which is $\neg P$ as required.


TITLE: Axiom of Choice and Ascending Chain Condition
QUESTION [4 upvotes]: Matsumura, in his "Commutative Ring Theory" p. 14 proves that "A partially ordered set $\Gamma$ satisfies the ascending chain condition $\Leftrightarrow$ every nonempty subset of $\Gamma$ has a maximal element."
In proving the $\Rightarrow$ direction, he uses the following argument: Consider a nonempty subset $\Gamma'$ of $\Gamma$. Suppose that $\Gamma'$ has no maximal element. Then "by the axiom of choice" for any $\gamma \in \Gamma'$ we can select an element $\phi(\gamma')$ such that $\phi(\gamma')> \gamma'$. In that way we obtain a nonterminating ascending chain $\gamma' < \phi(\gamma')<\phi^2 (\gamma') <\cdots$, contradiction."
My question is: why is the axiom of choice necessary here?
Don't we already have by hypothesis (no maximal element exists) a rule $\phi : \Gamma' \rightarrow \Gamma'$ to assign to each $\gamma'$ the element $\phi(\gamma')$?

REPLY [5 votes]: The Axiom of Choice is the mechanism that allows you to construct this rule/function.  Even though you know that to each $\gamma \in \Gamma^\prime$ there is some $\gamma^\prime \in \Gamma^\prime$ greater than it, this only means that for each $\gamma$ the collection $$A_\gamma = \{ \gamma^\prime \in \Gamma^\prime : \gamma^\prime > \gamma \}$$ is nonempty. It does not provide you a means for constructing a rule to say for each $\gamma$ this is the element of $A_\gamma$ I want!  The whole point of the Axiom of Choice is to be able to choose particular elements from possibly infinitely many different nonempty sets where there is no rule to uniformly select a unique element from each.
Note, also, that in this instance, since you are only concerned with generating an increasing sequence of elements of $\Gamma^\prime$, you could get away with using only the Axiom of Dependent Choice), which is quite a bit weaker.

REPLY [2 votes]: No, "no maximal element" doesn't give you a choice function. A choice function is a function $\phi: \mathcal P(\Gamma')\setminus \{\varnothing\} \to \Gamma'$ such that $\phi(x) \in x \subset \Gamma'$ for all subsets $x$ of $\Gamma'$.
If $\Gamma'$ has no maximal element then for every $\gamma \in \Gamma'$ you can find $\gamma'$ such that $\gamma < \gamma'$. Then to construct your infinite ascending chain you use that together with a choice function as follows: start with an element $\gamma$ and consider the set of all elements that are bigger than it (which is non-empty since $\Gamma'$ has no maximal element). You use the choice function to pick an element from this set. To construct the infinite chain you need to make infinitely many choices which is the reason why you need a choice function. If you only made finitely many choices there would not be a need for a choice function.
Whenever you need to make infinitely many choices for  which you cannot write down an explicit rule you need the axiom of choice. In this case, you have infinitely many sets from which you need to choose: the set of elements that are bigger than the ones you have already chosen.