text:
In this section we derive the learning rates for the tail-averaged SGD recursion in Hilbert scales. As usual, the error bounds rely on
a suitable error decomposition. Here, we follow the approach in \cite{pillaud2018statistical, mucke2019beating} and consider
\begin{equation}
\label{eq:decompfinalSGD}
\bar f_T - f_\cH = \underbrace{(\bar f_T - \bar g_T)}_{SGD \;\; variance} + \underbrace{(\bar g_T - f_\cH)}_{Section \;\; \ref{app-error-analysis-smoothness-promoting}} \;,
\end{equation}
where $\bar g_T$ is the tail-averaged GD recursion, defined in \eqref{eq:barGD}.
Recall that the GD recursion defined in \eqref{eq:barGD0} can be rewritten as
\begin{align*}
   g_{t} &= L^{-s} h^{GD}_{t}\,, \quad h^{GD}_{t+1} = h^{GD}_{t} - \gamma(\cT_{\bx, s}h^{GD}_{t}  - \cB^*_{\bx, s}\by ) \;.
\end{align*}

Denoting $(\bx_t, \by_t):=(x_{j_i}, y_{j_i})_{i=b(t-1)+1, ..., bt} \in (\cX \times \cY)^b$ the sample drawn at iteration $t$ , $t=1,...,T$ and
\[ \cB_{t,s} :=\cS_{\bx_t, s}L^{-s}: \cH \to \mbr^b  \;, \;\;\; \cT_{t,s}:= \cB^*_{t,s}\cB_{t,s} : \cH \to \cH \;,\]
a short calculation shows that the SGD recursion in \eqref{eq:SGD-recursion} can similarly be rewritten as
\[ f_{t+1} = L^{-s}h^{SGD}_{t} \,, \quad h^{SGD}_{t+1} = h^{SGD}_{t} - \gamma(\cT_{t+1, s}h^{SGD}_{t}  - \cB^*_{t+1, s}\by_{t+1} ) \;. \]

Thus, the difference
$$\mu_t:=f_t - g_t=L^{-s}\tilde \mu_t$$
with $\tilde \mu_t = h^{SGD}_{t}-h^{GD}_{t}$ follows the recursion
\begin{align*}
\tilde \mu_{t+1} &= (1-\gamma \cT_{t+1,s})\tilde \mu_t + \gamma   \xi_{t+1, s}   \;,
\end{align*}
where $ \xi_{t+1, s}=\xi^{(1)}_{t+1, s} + \xi^{(2)}_{t+1, s} $ and with
\begin{align*}
\xi^{(1)}_{t+1, s} &=(\cT_{\bx,s} - \cT_{t+1,s} ) h^{GD}_{t} \; \\
\xi^{(2)}_{t+1, s} &=  \cS^*_{t+1,s} \by_{t+1} -  \cS^*_{\bx ,s} \by \;,
\end{align*}
see \cite[Appendix E]{mucke2019beating}. We finally set $\bar \mu_T = L^{-s} \overline{\tilde \mu}_T$, with
$\overline{\tilde \mu}_T = \frac{2}{T}\sum_{t=\floor{T/2}+1}^T \tilde \mu_t$.

\subsection{Bounding SGD Variance}

\begin{proposition}
\label{prop.new}
Suppose Assumptions \ref{ass:bounded} and \ref{ass:link-condition3} are satisfied.
Let $s \geq 0$, $\nu \in [0, 1]$, $\gamma \kappa_s^2 < \frac{1}{4}$, $\beta=\frac{a-s}{2(a+s)}$ and $f_\cH \in \cD(L^s)$.
Define
\begin{equation}
\label{eq:def-SigmaT}
  \Sigma_T^2 (R)= \tilde M^2+||L^s f_\cH ||^2_\cH + \sigma^2_T (R)
\end{equation}
and
\[  \sigma_T (R) = d_s(R) + R(\gamma T)^{-\beta} + \tilde \sigma + M + \frac{||L^sf_\cH ||_\cH}{\gamma T} + (\gamma T)^{-1} (d_s(R)+ R(\gamma T)^{-\beta} )  \;.\]
Assume further that
\[ n \geq \gamma T \max\{ 1, \cN_{\cT_s}(1/\gamma T) \} \;.\]
The SGD variance satisfies
\[ \mbe\left[ || \sqrt{\cT_s }\overline{\tilde \mu}_T ||^2_\cH \right] \leq  c_s Tr[\cT_s^{\nu}]  \; \frac{\Sigma^2_T (R)}{b}
            \gamma^{\nu}T^{\nu - 1}
     +   c_s' \gamma^2 T^5 \delta_n    \;, \]
for some $c_s < \infty$, $c'_s < \infty$ and with
\begin{equation}
\label{eq:delta}
  \delta_n = 2\exp\left( -a \sqrt{\frac{n}{\gamma T \cN_{\cT_s}(1/\gamma T)}} \right) \;,
\end{equation}
for some $a \in \mbr_+$.

The same bound holds if $-a/2 \leq s \leq 0$ under Assumption \ref{ass:link-condition2} instead of Assumption \ref{ass:link-condition3}  and with $\beta=\frac{r-s}{2(a+s)}$,
provided Assumption \ref{ass:SC-pre} is satisfied.
\end{proposition}

\begin{proof}[Proof of Proposition \ref{prop.new}]
The proof is along the lines of the proof of \cite[Proposition 6, Section D.1]{mucke2019beating} with slight modifications adapted to our setting.
Note that Assumption \ref{ass:moment} is satisfied if $\cY \subseteq [-M,M]$, for some $M>0$, with $\sigma = M$. The main new ingredient in the proof is a new
uniform bound  for the GD updates $||h^{GD}_{t}||_\cH = ||L^s g_t||_\cH = ||g_t||_s$  based on our Theorem \ref{theo:GDI}. This is straightforward by
following the arguments as in \cite[Lemma 8, Section D.1]{mucke2019beating}.
\end{proof}

\subsection{Final Bounds smoothness promoting SGD}
\label{app-proofs-SGD}

\begin{theorem}[Excess Risk]

Suppose Assumptions \ref{ass:bounded} and \ref{ass:link-condition3} are satisfied.
Let $\nu \in (0,1]$, $\beta=\frac{a-s}{2(a+s)}$ and $\gamma \kappa_s^2 < \frac{1}{4}$. Assume further that $ Tr[\cT_s^{ \nu}] <\infty$ and that
\[   n \geq \gamma T \max\{ 1, \cN_{\cT_s}(1/\gamma T) \}  \;.   \]
If $f_\cH \in \cD(L^s)$,  the excess risk satisfies
\begin{align*}
 \mbe\left[ ||\cS( \bar f_T - f_\cH )||^2_{L^2} \right] &\leq c_{a,s,\kappa_s, \nu} (\gamma T)^{-1 } \left(\; d^2_{s}(R)   + R^2(\gamma T)^{-2\beta}
      + \tilde \sigma^2  \frac{\gamma T \cN_{\cT_s}(1/(\gamma T)) }{n}     \;\right)  \no \\
   & \quad   +  \frac{\Sigma^2_T (R)}{bT}  (\gamma T)^{\nu}    + \Omega^2_n(\gamma T)  \;,
\end{align*}
where the remainder $\Omega_n(\cdot)$ is of lower order and given by
\begin{align*}

 \Omega_n(\gamma T)
 &= \frac{ || L^s\tilde g_T ||_\cH }{\gamma T} +   \sqrt{\frac{\gamma T}{n}}(d_s(R) + R^2(\gamma T)^{-\beta}) +  \gamma^2 T^5 \delta_n
\end{align*}
and where $\Sigma^2_T(R)$ is defined in \eqref{eq:def-SigmaT} and $\delta_n$ is given by \eqref{eq:delta}.
\end{theorem}

\[\]

\begin{proof}[Proof of Theorem \ref{prop:newSGD}]
The proof follows by combining \eqref{eq:decompfinalSGD} with Proposition \ref{prop.new} and Theorem \ref{theo:GDI} with $\alpha = 1/2$.
Moreover,
Lemma \ref{lem:approxbounds} gives
\begin{equation}
\label{eq:SGD1}
  ||L^s\tilde g_T||_\cH \leq  c_{a,s}(d_s(R) + R(\gamma T)^{-\beta}) +||L^s f_\cH||_\cH  \;,
\end{equation}
for some $c_{a,s} < \infty$. Thus,
\begin{align}
\label{eq:SGD2}
 \tilde M_T &= 2\kappa_s (M + \kappa_s ||L^s f_\cH||_\cH ) \no \\
  &\leq c_{a,\kappa_s} (M+  d_s(R) + R(\gamma T)^{-\beta} + ||L^s f_\cH||_\cH ) \;,
\end{align}
for some $c_{a,\kappa_s} < \infty$.
In addition, applying Lemma \ref{lem:approxbounds} once more leads to
\begin{align}
\label{eq:SGD3}
\tilde \tau_T  &= 2\kappa_s ||\cS \tilde g_T - f_\cH||_{L^2} \no \\
&\leq 4 \kappa_s (\gamma T)^{-1/2}(d_s(R) + R(\gamma T)^{-\beta}) \;.
\end{align}
Combining  Theorem \ref{theo:GDI} and Proposition \ref{prop.new}  with \eqref{eq:SGD1}, \eqref{eq:SGD2}, and \eqref{eq:SGD3} leads to
\begin{align*}
 & \mbe\left[ ||\cS \bar f_T - f_\cH ||^2_{L^2} \right] \leq c_{a,s,\kappa_s} (\gamma T)^{-\frac{1}{2}} \left(\; d_{s}(R)   + R(\gamma T)^{-\beta} +
\frac{ || L^s\tilde g_T ||_\cH }{\gamma T}  +  \right.  \no\\
&  \left. +  \tilde M_T \frac{\gamma T}{n} + \tilde \sigma  \sqrt{\frac{\gamma T \cN_{\cT_s}(1/(\gamma T)) }{n}} + \tilde \tau_T \frac{\gamma T}{\sqrt n}  \;  \right) \\
  & + c'_{\kappa_s} \left(   Tr[\cT_s^{ \nu}]  \; \frac{\Sigma^2_T (R)}{b}
            \gamma^{\nu}T^{\nu - 1}       +   c_s' \gamma^2 T^5 \delta_n  \right)   \\
 &\leq c_{a,s,\kappa_s, \nu} (\gamma T)^{-\frac{1}{2}} \left(\; d_{s}(R)   + R(\gamma T)^{-\beta}
      + \tilde \sigma  \sqrt{\frac{\gamma T \cN_{\cT_s}(1/(\gamma T)) }{n}}       +  \right.  \no \\
   & \left. +  \frac{\Sigma^2_T (R)}{bT}  (\gamma T)^{\nu}    + \Omega_n(\gamma T)  \;  \right)\;.
\end{align*}
\end{proof}

\begin{proof}[Proof of Corollary \ref{cor:ratesSGD}]
The proof of the  learning rate is now a standard calculation. A straightforward calculation shows that all choices of $\gamma, T, b$ balance the
leading order terms in Theorem \ref{prop:newSGD} and that $\Omega_n(\cdot)$ is of lower order.
\end{proof}

\begin{proof}[Proof of Corollary \ref{cor:ratesSGD2}]
The proof of the  learning rate is now a standard calculation. A straightforward calculation shows that all choices of $\gamma, T, b$ balance the
leading order terms in Theorem \ref{prop:newSGD} and that $\Omega_n(\cdot)$ is of lower order. Moreover, $d_s(R)\leq R_*$ and $R(\gamma T)\asymp R_*(\gamma T)^\beta $,
for some $R_*>0$.
\end{proof}

\subsection{Final Bounds Preconditioning  SGD }

\begin{theorem}[Excess Risk]
\label{prop:newSGDPre}
Suppose Assumptions \ref{ass:bounded}, \ref{ass:link-condition2}, and  \ref{ass:SC-pre} are satisfied.
Let $\nu \in (0,1]$, $\beta=\frac{r-s}{2(a+s)}$ and $\gamma \kappa_s^2 < \frac{1}{4}$. Assume further that $ Tr[\cT_s^{ \nu}] <\infty$ and that
\[   n \geq \gamma T \max\{ 1, \cN_{\cT_s}(1/\gamma T) \}  \;.   \]
If $f_\cH \in \cD(L^s)$,  the excess risk satisfies
\begin{align*}
 \mbe\left[ ||\cS( \bar f_T - f_\cH )||^2_{L^2} \right] &\leq c_{a,s,\kappa_s, \nu} (\gamma T)^{-1}
  \left(\; R (\gamma T)^{-\frac{r-s}{2(a+s)}} + \frac{||L^s \tilde g_T||_\cH}{\gamma T}  \right. \\
 & +  \left.      \tilde M_T \frac{\gamma T}{n} + \tilde \sigma  \sqrt{\frac{\gamma T \cN_{\cT_s}(1/(\gamma T)) }{n}} + \tilde \tau_T \frac{\gamma T}{\sqrt n}   \;  \right) \no \\

   & \quad  +  \frac{\Sigma^2_T }{bT}  (\gamma T)^{\nu}    + \Omega^2_n(\gamma T)  \;,
\end{align*}
where the remainder $\Omega_n(\cdot)$ is of lower order and given by
\begin{align*}
 \Omega_n(\gamma T)
 &= \frac{ || L^s\tilde g_T ||_\cH }{\gamma T} +   \sqrt{\frac{\gamma T}{n}}R (\gamma T)^{-\frac{r-s}{2(a+s)}} +  \gamma^2 T^5 \delta_n
\end{align*}
and where $\Sigma^2_T(R)$ is given by
\[ \Sigma^2_T = \tilde M^2 + ||L^sf_\cH ||^2_\cH + \tilde \sigma^2  + M^2 + \sigma_T^2 \;, \]
with
\[ \sigma_T =    R(\gamma T)^{- \frac{r-s}{2(a+s)}} + \frac{||L^s f_\cH ||}{\gamma T}\;. \]
\end{theorem}

\begin{proof}[Proof of Theorem \ref{prop:newSGDPre}]
The proof follows by combining \eqref{eq:decompfinalSGD} with Proposition \ref{prop.new}, Proposition \ref{prop:preII} and Theorem \ref{theo:GDIPre} with $\alpha = 1/2$.
\end{proof}

config: arxiv


TITLE: A possible defining characteristic of primitive roots.
QUESTION [2 upvotes]: If $n$ is a primitive root $\bmod p$ ($p$ is an odd prime ) does there always exist a least residue $t$ such that $n^t \equiv t \pmod p$ ?

REPLY [2 votes]: Recall that $n^{p-1}\equiv 1\pmod p$.
For any $r\in\{0,\ldots,p-1\}$, find $a$ with $n^a\equiv r\pmod p$. By the Chinese Remainder Theorem, there exists $t\in\mathbb N_0$ with $t\equiv a\pmod{p-1}$ and $t\equiv r\pmod p$. For such $t$, we have $n^t\equiv t\pmod p$. As is the case for any nonempty set of $\mathbb N_0$, there certainly is a minimal such $t$.


TITLE: Interval of convergance $\sum_0^\infty \frac{x^n}{(n!)^2}$
QUESTION [0 upvotes]: $$\sum_0^\infty \frac{x^n}{(n!)^2}$$
With what I now know the ratio test should give me
$$x * 1$$
So basically x. So that means my internal is (1,1) but this is wrong. Why?

REPLY [3 votes]: This time, the ratio limit is going to give you
$$ \lim_{n \rightarrow \infty} \ \left| \ x \ \cdot \frac{n! \cdot n!}{(n+1)! \cdot (n+1)!} \ \right| = \ \lim_{n \rightarrow \infty} \ \left| \ x \ \cdot \frac{1}{(n+1) \cdot (n+1)} \ \right| \ = \ 0 \ < 1 \ . $$
When you have a result which is always less than one, the radius of convergence is infinite.

REPLY [2 votes]: The ratio test:    $\ \ \ \left| \dfrac{a_{n+1}}{a_{n}} \right| = \left|  \dfrac{\dfrac{x^{n+1}}{((n+1)!)^2}}{\dfrac{x^n}{(n!)^2}}\right| =\left| \dfrac{x}{(n+1)^2} \right| $
for wich values of $x$ is the expression smaller  then $1$ as $n \to \infty$?

REPLY [2 votes]: $$
\sum_{n=0}^N \frac{|x|^n}{(n!)^2} \leq \sum_{n=0}^N \frac{|x|^n}{n!} < e^{|x|},
$$
so send $N \to \infty$ to see that that landlubbin' sequence converges absolutely for any $x$.

REPLY [1 votes]: For a series $\sum_n a_nx^n$ the radius of convergence is given by $$1/R=\limsup |a_n|^{1/n},$$
which in your case gives $1/R=0$ or $R=\infty$.


TITLE: Seeking a derangement $S: \{0,1\}^4 \to \{0,1\}^4$ for which changing one bit in the input always changes at least two bits in the output
QUESTION [0 upvotes]: Kindly asking for any hints about the following question:
Define a function $ S : \{0,1\}^4 \to \{0,1\}^4$ with this conditions:
1- For any $x$, $\ S(x) \neq x $
2- for any $x \neq y$, $\ S(x) \neq S(y).$
3- Changed one bit in the input always changing at least two bits in the output.

REPLY [1 votes]: After not getting systematically, I looked for solutions (there seem tobe gazillions) by backtracking
Try this
$$ 0000\mapsto 0001\\
0001\mapsto0010\\
0010\mapsto0100\\
0011\mapsto0111\\
0100\mapsto0110\\
0101\mapsto1000\\
0110\mapsto0011\\
0111\mapsto1101\\
1000\mapsto1010\\
1001\mapsto0101\\
1010\mapsto1111\\
1011\mapsto1100\\
1100\mapsto1001\\
1101\mapsto1110\\
1110\mapsto0000\\
1111\mapsto1011$$


TITLE: Minimal normal subgroups of a finite supersolvable groups
QUESTION [0 upvotes]: Let $G$ be a finite supersolvable group. Then a minimal normal subgroup of $G$ is has prime order. Is it true in general that $G$ has a minimal normal subgroup for each prime divisor of $G$?

REPLY [1 votes]: No.  For example, the supersolvable group $S_3$ has only one minimal normal subgroup, of order 3.  A similar situation occurs in the nonabelian group of order $pq$, where $p$ and $q$ are any primes with $p | q-1$.
All you can guarantee is that $G$ has a normal subgroup of order $p$, where $p$ is the largest prime dividing $|G|$.  Reason:  $G$ has a normal Sylow $p$-subgroup (the bottom of a Sylow tower), and this subgroup necessarily contains a minimal normal subgroup.


text:
\section{Conclusions}
This work proposes \fedac, a principled acceleration of \fedavg, which provably improves convergence speed and communication efficiency.
Our theory and experiments suggest that \fedac saves runtime and reduces communication overhead, especially in the setting of abundant workers and infrequent communication.
We establish stronger guarantees when the objectives are third-order smooth.
As a by-product, we also study the stability property of accelerated gradient descent, which may be of broader interest.
We expect \fedac could be generalized to broader settings, \eg, non-convex objective and/or heterogenous workers.


TITLE: Basis for Tensor Product of Infinite Dimensional Vector Spaces
QUESTION [11 upvotes]: If V and W are vector spaces over a common field with bases $V_B = ${$v_i : i \in I$} and $W_B = ${$w_j : j \in J$}, then is {$v_i \otimes w_j: i \in I, j \in J$} a basis for $V \otimes W$ ?
I have several references for the finite dimensional case but they seem to involve either a dimensional argument or reference to dual spaces, neither of which would seem to be appropriate in the infinite dimensional case.
The references that I can find for infinite dimensional spaces focus on "orthonormal bases" (usually in the context of Hilbert Spaces).
So, I'd appreciate any help answering

is this actually true if {$v_i : i \in I$} and {$w_j : j \in J$} are the Hamel (algebraic) bases of infinite dimensional spaces and what is the proof ?
Does it make any difference if only one space is infinite dimensional ?
Is there any difference between countable and larger infinities ?

Addendum 15 March 2015:
Why not simply define the tensor product as $F(V_B \times W_B)$, i.e. the free vector space generated by the set of ordered pairs of basis vectors ? There seems to be a bilinear mapping from $V \times W$ and it appears to satisfy the universal property.
Have I missed something here ?

REPLY [7 votes]: I give a "conceptual" answer.
Let $k$ be a field, and $V, W$ vector spaces over $k$. Recall that $k$-vector space $V\otimes_k W$ has the following universal property : if we note $\pi : V\times W\to V\otimes_k W$ the canonical $k$-bilinear map $(v,w)\mapsto v\otimes w$ and $\textrm{Bil}_k (V,W;P)$ the set of $k$-bilinear applications $V\times W\to P$ for a $k$-vector space $P$, then we have : for each $k$-vector space $P$ the map $\textrm{Hom}_k (V\otimes_k W,P)\to \textrm{Bil}_k (V,W;P)$ definied by $f\mapsto f\circ\pi$ is a bijection.
As I think that any answer to your question should emphasize what is true in general, what is proper to the situation (vector spaces = modules over a field) and what things are independent. I will prove the following three general lemmas, with the following hypothesis : from now on, $k$ is not a field but a commutative ring with unit, and $V,W$ are modules over $k$.
Lemma 0. The elements of the form $v\otimes w$ for $v\in V$ and $w\in W$, called elementary tensors (or also simple tensors), generate $V\otimes_k W$ over $k$.
Proof. I give a proof of this lemma using only the universal property of $V\otimes_k W$ and not any of its constructions (as quotient of $A^{(W\times V)}$ for instance). Note $Q$ the sub-$k$-module of $V\otimes_k W$ generated by elementary tensors. Note $\pi' : V\times W\to Q$ the map defined by $(v,w)\mapsto v\otimes w \in Q$. I pretend that $Q$ and $\pi'$ satisfies the same universal property that $V\otimes_k W$ and $\pi$ do. Let $P$ be a $k$-module. The map $\textrm{Hom}_k (Q,P)\to \textrm{Bil}_k (V,W;P)$ defined by $f\mapsto f\circ\pi'$ is a injective. Indeed : if $f\circ \pi' = g\circ \pi'$ for $f,g\in \textrm{Hom}_k (Q,P)$ then it means that $f$ and $g$ are equal on elementary tensors, and as elementary tensor generate $Q$ by definition of $Q$, we have $f=g$. Now, let's show that this map is surjective, so take $b\in \textrm{Bil}_k (V,W;P)$. By the universal property of $V\otimes_k W$ we can find $f\in \textrm{Hom}_k (V\otimes_k W,P)$ such that $b = f\circ\pi$, which obviously imply that $b = f' \circ \pi'$, where the $k$-linear map $f' : Q\to P$ is the restriction of $f$ to the submodule $Q$ of $V\otimes_k W$, that is, the $k$-linear map $f' : Q\to P$ defined by $q\mapsto f(q)$ for $q\in Q$. This shows the surjectivity of the map $\textrm{Hom}_k (Q,P)\to \textrm{Bil}_k (V,W;P)$, which is finally injective and surjective, that is, bijective. This shows that $Q$ and $\pi'$ satisfies the same universal property that $V\otimes_k W$ and $\pi$ do. Thanks to this, we will now show that $Q = V\otimes_k W$. Note $i : Q \to V\otimes_k W$ the canonical injection : it is the map sending an element of $Q$ to the same element but viewed as element of $V\times_k W$. Rephrased, what we want to show is that $i$ is surjective. Now $\pi' : V\times W \to Q$ is a $k$-bilinear map, so that by the universal property of $V\otimes_k W$ and $\pi$, there exists a unique $k$-linear map $\varphi : V\otimes_k W \to $ such that $\varphi\circ \pi = \pi'$. But then $(i\circ\varphi)\circ\pi = i\circ(\varphi\circ\pi) = i\circ\pi' = \pi = \textrm{Id}_{V\otimes_k W}\circ\pi$, and by the universal property $i\circ\varphi = \textrm{Id}_{V\otimes_k W}$, showing that $i$ has a right inverse, and is therefore surjective. $\square$
Lemma 1. If $(v_i)_{i\in I}$ (resp. $(w_j)_{j\in J}$) is a familly of generating elements of $V$ (resp. of $W$) over $k$, then the familly $(v_i\otimes w_j)_{(i,j)\in I\times J}$ is a familly of of generating elements of $V\otimes_k W$ over $k$.
Proof. As $\pi$ is $k$-bilinear, it is clear that any elementary tensor will be linear combination of $v_i\otimes w_j$'s over $k$, and by the previous lemma, the elementary tensors generate $V\otimes_k W$, showing thereby that the elements $v_i\otimes w_j$'s generate V\otimes_k W$
From now on we suppose that $k$ is a field.
Lemma 2. If $(v_i)_{i\in I}$ (resp. $(w_j)_{j\in J}$) is a familly of independant elements of $V$ (resp. of $W$) over $k$, then the familly $(v_i\otimes w_j)_{(i,j)\in I\times J}$ is a familly of independant vector of $V\otimes_k W$ over $k$. $\square$
Proof. Suppose we have a dependance relation $$\sum_{(i,j)\in I\times J} c_{i,j} v_i\otimes w_j = 0$$ where $(c_{i,j})_{(i,j)\in I\times J}$ is a familly a elements in $k$ such that $c_{i,j}\not=0$ only for finitely many indexes $(i,j)$'s. Complete $(v_i)_{i\in I}$ (resp. $(w_j)_{j\in J}$) in a basis $(v_i)_{i\in \overline{I}}$ (resp. $(w_j)_{j\in \overline{J}}$) of $V$ resp. (of $W$) over $k$. Take $(i_0,j_0)\in I\times J$ and let's show that $c_{i_0,j_0} = 0$. For this, consider the bilinear function $V\times W\to k$ sending $(v,w)=\left( \sum_{i\in \overline{I}} \lambda_i v_i, \sum_{j\in \overline{J}} \mu_j w_j \right)$ to $\lambda_{i_0} \mu_{j_0}$. Take by the universal property $f : V\otimes_k W \to k$ to be the linear map associated to this bilinear form. Applying the linear function to the above dependance equation gives $c_{i_0,j_0} = 0$. $\square$
Lemma 2 and 3 applied to the case of a field do answer your question.
Remark. No cardinality hypothesis were made.


TITLE: How to find subbase and base for $X\times Y$?
QUESTION [1 upvotes]: Let $\tau :=\{X,\emptyset,\{a\},\{b,c\}\} $ on $X=\{a,b,c\}$ and
$\tau^*:=\{Y,\emptyset,\{u\}\}$  on $Y:=\{u,v\}$
i) Find a subbase for the product topology on $X\times Y$
ii) Find a base for the product topology on $X\times Y$

I found the product topology as $\tau^1=\{X\times Y,\emptyset,X\times \{u\},\{a\}\times Y,\{a\}\times \{u\},\{b,c\}\times Y,\{b,c\}\times \{u\}\}$
Is this correct? How can I continue?

REPLY [2 votes]: Unless I'm overlooking something here, what you have there is a base (and hence a subbase) for the product topology, but not a topology in itself.
Remember: the product topology for $X\times Y$ is defined as the topology generated by the base $\{U\times V \mid U\in \tau, V\in \tau^*\}$. In general, this base is not a topology, as is the case here.
Note that the union of two open sets should be open. In the $\tau^1$ you provided, $(\{a\}\times \{u\})\cup (\{b\}\times Y)=\{(a,u), (b,u), (b,v)\}$ is nowhere to be found.


TITLE: How to calculate distance of shortest path when there is a flow in the river?
QUESTION [2 upvotes]: I am trying to solve this question:

I have figured out a solution involving calculus, however there seems to be a much simpler solution that was provided with the question, as follows:

However, I can't for the life of me understand this solution? Can someone explain what is happening in this solution?
It appears that a distance diagram is being used: the top of the triangle represents the distance traveled by the flow of the river in time t (the velocity of the river is 4 m/s); the left side of the triangle represents the distance traveled by the boat in time t (the velocity of the boat is 1 m/s).
This makes sense, however I can't understand the right side of the triangle, which represents the distance of the shortest path. How does this third side of the triangle represent the shortest distance? This is the part that is confusing me. If I can understand that, the rest of the solution is fairly straightforward.

REPLY [0 votes]: The Triangle Law of Vector Addition states that when two vectors are represented by two sides of a triangle in the same order then the third side of that triangle represents the resultant of the vectors. Note that the two vctors to be added must be placed head to tail.
Let  $ \vec a $  denote the velocity of the boat in still water and   $ \vec b $  denote the velocity of the water. If  $ \vec v $ denotes the actual velocity of the boat, then $\vec v= \vec a+ \vec b$.
Suppose that the boat crosses the river by the shortest path in a time $t$. After a time $t$, let $ \vec x$ denote the displacement of the boat in still water and $ \vec y$ denote the displacement of the water. At this time, let  $ \vec r$ denote the actual displacement of the boat due to the combined effect of the effort of the rower and the current in the river. Then
$$\vec r=\vec x+ \vec y$$.
By the Triangle Law, $ \vec x,\ \vec y\  and\  \vec  r $ may be represented by the sides of a triangle.
$\vec y$ is easy to draw as it has magnitude $4t$ and is parallel to the bank.
Assuming that the river is flowing left to right, $\vec x$ must be in some random direction up the river but is of magnitude $1t$. By the Triangle Law, $\vec x$ and $\vec y$ must be drawn head to tail. The resultant displacement  $\vec r$ must now be drawn from the starting point to the head of $\vec y$ and is of magnitude d, the actual distance travelled by the boat.
As the questioner has pointed out, the problem is straightforward after the triangle is correctly drawn and labelled.
As $d =\frac{60}{sin\phi}$, d is a minimum when $sin \phi$ is a maximum. Then $sin \phi = \frac{sin \beta}{4}$ yields $( sin \phi) _{max} = \frac{1}{4}$.
So $\frac {60}{d_{min}}= \frac{1}{4}$ gives $d_{min}= 240m$.
When applying the Triangle Law, note that if the two vectors to be added are cyclic, then the resultant must be anti-cyclic.


text:
\chapter{Explicit algorithm to produce a minimizer}
\label{chap:explicit-algorithm-to-produce-a-minimizer}

Let  $\{ V_{e_1}, \ldots, V_{e_d} \}$ be commuting, invertible, measure-preserving ergodic transformations on $\W$. They generate the group of translation operators in~\Eqref{eq:translation-group-of-operators} under composition. Suppose we have \FPP~on the undirected graph on $\Z^d$, i.e.,
\begin{equation}
  \tau(x,\alpha,\w) = \tau(x + \alpha, - \alpha,\w).
  \label{eq:edge-FPP-assumption}
\end{equation}
Let $A_+ = \{e_1, \ldots, e_d\}$. Let $t\colon A_+ \times \W \to \R$ be a function representing the edge-weight at the origin. For example, it could consist of $d$ i.i.d.~edge-weights, one for each direction. Let $x=(x_1,\ldots,x_d) \in \Z^d$. Then, the edge-weight function is given by
\[
  \tau(x,\alpha,\w) = t\left(\alpha,V_{e_1}^{x_1}\cdots V_{e_d}^{x_d}\w \right).
\]
In this section, we will assume the following symmetry on the medium:
\begin{equation}
  V_{e_1} = \cdots = V_{e_d} = V .
  \label{eq:symmetry-assumption-on-medium}
\end{equation}
\
This means that for each $\w$ the function $\tau(\cdot,\cdot,\w)$ is constant along the hyperplanes $\{ x \in \Z^d : \sum_{i=1}^d x_i = z \}$ for each $z \in \Z$. Despite this symmetry, the medium is still quite random, and it's not so obvious ---although one ought to be able to calculate it--- what the time-constant is. However, the set $S$ in~\Eqref{eq:discrete-set-S-for-variationalf-formula} is tremendously simplified.
\begin{prop}
  If $\phi \in S$ and~\Eqref{eq:symmetry-assumption-on-medium} holds,
  the derivative points in the $\sum_i e_i$ direction; i.e.,
  \[
    \mathcal{D}\phi(x,\alpha,\w) = \mathcal{D}\phi(0,e_1,\w) \quad \forall \alpha \in A \AND ~\forall x \in \Z^d ~\almostsurely.
  \]
  \label{prop:simplifying-the-set-of-functions-S}
\end{prop}
\begin{proof}
  The derivative of $\phi$ sums to $0$ over any discrete loop in $\Z^d$. In particular, for any $i \neq j \in \{1,\ldots,d\}$
  \begin{multline}
    \mathcal{D}\phi(x,e_i,\w) + \mathcal{D}\phi(x+e_i,e_j,\w) + \\  + \mathcal{D}\phi(x+e_i+e_j,-e_i,\w) + \mathcal{D}\phi(x+e_j,-e_j,\w)
    = 0.
  \end{multline}
 Since the derivative is stationary and $\mathcal{D}\phi(x,\alpha,\w) = -\mathcal{D}\phi(x+\alpha,-\alpha)$, we have
  \[
    \begin{split}
      \mathcal{D}\phi(x,e_i,\w)  - \mathcal{D}\phi(x,e_j,\w) & = \mathcal{D}\phi(x,e_i,V_{e_j}\w) - \mathcal{D}\phi(x,e_j,V_{e_i}\w), \\
      & = \mathcal{D}\phi(x,e_i,V\w) - \mathcal{D}\phi(x,e_j,V\w).
    \end{split}
  \]
  Hence, $\mathcal{D}\phi(0,e_i,\w) - \mathcal{D}\phi(0,e_j,\w)$ is invariant under $V$. Since it also has zero mean, it follows from ergodicity that
  \[
    \mathcal{D}\phi(x,\alpha,\w) = \mathcal{D}\phi(x,e_1,\w) \quad \forall \alpha \in A ~\almostsurely.
  \]

\end{proof}

Next, we simplify the variational formula under the symmetry assumption~\Eqref{eq:symmetry-assumption-on-medium}. Redefine the discrete Hamiltonian for $t \in \R$, $p \in \R^d$ to be
\begin{equation}
  \mathcal{H}_{sym}(t,p,\w) := \sup_{\alpha \in A^+} \frac{|t + p\cdot\alpha|}{\tau(0,\alpha,\w)} .
  \label{eq:discrete-hamiltonian-2}
\end{equation}

\begin{prop}
  If we assume~\Eqref{eq:symmetry-assumption-on-medium} and~\Eqref{eq:edge-FPP-assumption}, the variational formula becomes
  \begin{equation}
    \overline{H}(p) = \inf_{f \in F} \esssup_w \mathcal{H}_{sym}(f(\w),p,\w),
  \end{equation}
  where
  \begin{equation}
    F := \left\{ f:\W \to \R ,~ E[f] = 0,~ \sup_{\alpha \in A^+} \left|f + p\cdot\alpha \right| \leq (b/a)|p|_{\infty} \right\}.
    \label{eq:set-S-under-symmetry-assumption}
  \end{equation}
  \label{prop:variational-formula-in-symmetric-situation}
\end{prop}
\begin{proof}
  For each $\phi \in S$, let $f(\w) = D\phi(0,e_1,\w)$. The proof is easy using the assumption~\Eqref{eq:edge-FPP-assumption} on the edge-weights and~\Propref{prop:simplifying-the-set-of-functions-S}. To wit,
\[
  \begin{split}
    \esssup_{\w} \sup_x \mathcal{H}(\phi,p,x,\w)
    & = \esssup_{\w} \sup_x \sup_{\alpha \in A} \left\{ \frac{-\mathcal{D}\phi(x,\alpha,\w) - p\cdot \alpha}{\tau(x,\alpha,\w)} \right\}, \\
    & = \esssup_{\w} \sup_{\alpha \in A^+} \left\{ \frac{|\mathcal{D}\phi(0,e_1,\w) + p\cdot \alpha|}{\tau(0,\alpha,\w)} \right\}, \\
    & = \esssup_{\w} \mathcal{H}_{sym}(f(\w),p,\w).
  \end{split}
\]

\end{proof}
In the following, we will write $\mathcal{H}_{sym}(f,\w)$ and drop reference to $p$ since it's irrelevant to our arguments. We present an algorithm that produces a minimizer for the variational problem under the symmetry assumption. The idea behind the algorithm is simple. At each iteration, we try to reduce the essential supremum over $\w$ by modifying $f(\w)$, while simultaneously keeping it inside the set $F$. If it fails to reduce the sup, we must be at a minimizer. We explain what we're trying to do in each step in the proof of convergence of the algorithm. So we suggest skimming the definition of the algorithm first, and returning to the definition of each step when reading the proof.\newline

\noindent\textbf{Start algorithm}
\vspace{-1em}
\begin{enumerate}
  \item \label{step:find-distance-between-sup-and-mean} Start with any $f_0 \in F$, for example, $f_0 = 0$. Let $\mu_0 = E[\mathcal{H}_{sym}(f_0,\w)]$, and let
    \[
    d = \esssup_{\w \in \W} \mathcal{H}_{sym}(f_0,\w) - \mu_0.
    \]
    If $d = 0$, stop.
  \item \label{step:define-min-set-S-and-I} Define the sets
    \begin{align}
      MIN_0 & :=  \{ \w : \mathcal{H}_{sym}(f_0,\w) = \min_x \mathcal{H}_{sym}(x,\w)  \},\\
      S & :=  \{ \w : \mathcal{H}_{sym}(f_0,\w) > \mu_0 \},\\
      I & :=  \{ \w : \mathcal{H}_{sym}(f_0,\w) < \mu_0 \}.
      \label{eq:definition-of-the-sets-MIN-S-I}
    \end{align}
    If
    \[ \esssup_{\w \in MIN_0} \mathcal{H}_{sym}(f_0,\w) = \esssup_{\w \in \W} \mathcal{H}_{sym}(f_0,\W), \]
    stop.
  \item \label{step:construct-delta-f} Let $\Delta f^*(\w)$ be such that
    \[ \mathcal{H}_{sym}(f_0 + \Delta f^*(\w),\w) = \min_x \mathcal{H}_{sym}(x,\w). \]
    Define the sets
    \begin{align*}
      S_+ & :=  \{ \w \in S \setminus MIN_0 : D_+ \mathcal{H}_{sym} \subset (-\infty,0) \},\\
      S_- & :=  \{ \w \in S \setminus MIN_0 : D_- \mathcal{H}_{sym} \subset (0,\infty) \},
    \end{align*}

    where $D_+ \AND D_-$ are the left and right derivatives of the convex function $\mathcal{H}_{sym}(\cdot,\w)$. Let
    \[
      \Delta f(\w) = \left\{ \begin{array}{cc}
        \max\left(- a (\mathcal{H}_{sym}(f_0,\w) - \mu_0),~\Delta f^*(\w) \right)
        & \w \in S_+ \\
        \min\left( a (\mathcal{H}_{sym}(f_0,\w) - \mu_0),~\Delta f^*(\w) \right)
        & \w \in S_-  \\
        a \xi (\mu_0 - \mathcal{H}_{sym}(f_0,\w) ) & \w \in I \\
        0   & \text{elsewhere}
      \end{array} \right. ,
    \]
    where
    \[
    \xi = - \frac{ \int_{S_+ \cup S_-} \Delta f(\w)~\Prob(d\w)}{ \int_I  a (\mu_0 - \mathcal{H}_{sym}(f_0,\w) )~\Prob(d\w)}.
    \]
    Let $f_1 = f_0 + \Delta f(\w)$. Return to step $1$.

\end{enumerate}
\noindent\textbf{End algorithm}

\begin{theorem}
  There are three possibilities for the algorithm:
  \begin{enumerate}
    \item If it terminates in a finite number of steps with $d = 0$, we have a minimizer that's a corrector.
    \item If it terminates in a finite number of steps with $d > 0$, we have a minimizer that's not a corrector
    \item If it does not terminate, we produce a corrector in the limit.
  \end{enumerate}
  \label{thm:algorithm-convergence}
\end{theorem}
We need the following lemma to prove~\Thmref{thm:algorithm-convergence}.

\begin{lemma} \mbox\newline
  The function $\mathcal{H}_{sym}(x,\w)$ has the following properties:
  \begin{enumerate}
    \item For each $\w$, it is convex in $x$.
    \item It has a unique measurable minimum $x^*(\w)$.
    \item Its left and right derivatives satisfy $D_{-} \mathcal{H}_{sym}(x,\w) \in [b^{-1},a^{-1}]$ or $D_+ \mathcal{H}_{sym} \in [-a^{-1},-b^{-1}]$ a.s. $\w$.
  \end{enumerate}
  \label{lem:H-sym-is-convex-and-its-min-is-measurable}
\end{lemma}
We will prove~\Lemref{lem:H-sym-is-convex-and-its-min-is-measurable} after proving~\Thmref{thm:algorithm-convergence}.

  \begin{figure}
    \centering
    \includegraphics[height=0.4\textheight]{Figure_for_sets_in_algorithm.png}
    \caption{Sketch of sets in algorithm. The outermost square represents the probability space $\W$. $S$ is the upper triangle in the inner square, and $I$ is the lower triangle in the inner square. $\W \setminus S \setminus I$ is the annular region between the two squares.}
    \label{fig:sets-in-algorithm}
  \end{figure}

\begin{proof}[Proof of~\Thmref{thm:algorithm-convergence}]

\mbox{}\newline
\noindent $1$. In the first step, we compute $d$, the distance between the mean and supremum of $\mathcal{H}_{sym}(f,\w)$. If $d = 0$, $f$ must be a corrector and from~\Corref{cor:inf-sup-inequality-for-limiting-Hamiltonian}, it must be a minimizer. Therefore, we stop the algorithm.

\noindent $2$. $MIN_0$ is the set on which $\mathcal{H}(f_0,\w)$ cannot be lowered further. $S$ and $I$ are the sets on which $\mathcal{H}_{sym}(f_0,\w)$ is bigger and lower than its mean $\mu_0$. $f$ will be modified on these two sets in step 3.

Lemma~\ref{lem:uniform-in-n-delta-estimate} says that $\mathcal{H}_{sym}(\cdot,\w)$ is convex and has a minimum. So there is the possibility of the algorithm getting ``stuck'' at a minimum of $\mathcal{H}_{sym}$. That is, $f_0$ might be such that $\mathcal{H}_{sym}(f_0,\w) = \mathcal{H}_{sym}(x^*(\w),\w)$ on a set of positive measure, and also
    \[
      \esssup_{\w \in MIN_0} \mathcal{H}_{sym}(f_0,\w) = \esssup_{\w \in \W} \mathcal{H}_{sym}(f_0,\W).
    \]
    For any other $g \in F$, we clearly have $\mathcal{H}_{sym}(g(\w),\w) \geq \mathcal{H}_{sym}(f_0(\w),\w)$ on $MIN_0$. Hence $f_0$ must be a minimizer, and we stop the algorithm.

  \noindent $3$. $\Delta f$ is first defined on the sets $S_+$ and $S_-$ so that the supremum falls. Then, $\Delta f$ is defined on $I$ so that it satisfies
    \[

        E[\Delta f] = 0.

    \]
    We need to make sure that $\xi$ is not infinite. Notice that $E[(\mu_0 - \mathcal{H}_{sym}(f_0,\w) ), I] > 0$; for if not, $\essinf_{\w \in I} \mathcal{H}_{sym}(\w) = \mu_0$. Hence $\Delta f$ is well-defined on $I$. We derive a useful estimate on $\xi$ next. Since
  \begin{equation*}
    \left|E[ \left( \mathcal{H}_{sym}(f_0,\w) - \mu_0 \right) , S \setminus MIN_0 ] \right| \leq
    E[ \left( \mu_0 - \mathcal{H}_{sym}(f_0,\w) \right) , I ] ,
  \end{equation*}
  we have
  \[
    \begin{split}
      E[\Delta f, S_+ \cup S_-]

      & \leq a E[(\mathcal{H}_{sym}(f_0,\w) - \mu_0),S_+ \cup S_-],  \\

      & \leq a E[\mu_0 - \mathcal{H}_{sym}(f_0,\w), I] .
    \end{split}
  \]
  Therefore,
  \begin{equation}
   -1 < \xi  < 1  .
    \label{eq:algorithm-xi-is-bounded}
  \end{equation}

  Finally, we prove that if the algorithm does not terminate in either step~\ref{step:find-distance-between-sup-and-mean} or~\ref{step:define-min-set-S-and-I}, we produce a corrector in the limit. We claim that if at the end of step $3$ of the algorithm, $\esssup \mathcal{H}(f_1)$ does not fall enough, the algorithm will terminate at the next step.
  \begin{claim}
    If
    \begin{equation}
      \esssup_{\w \in \W} \mathcal{H}_{sym}(f_1,\w) > \esssup_{\w \in \W} \mathcal{H}_{sym}(f_0,\w) - \frac{da}{b},
      \label{eq:suppose-that-H-f1-does-not-fall-enough}
    \end{equation}
  the algorithm will terminate when it goes to step $2$ in the following iteration. That is,
  \[
    \esssup_{\w \in \W} \mathcal{H}_{sym}(f_1,\w) = \esssup_{MIN_1}\mathcal{H}_{sym}(f_1,\w),
  \]
  where $MIN_1$ is defined in~\Eqref{eq:definition-of-the-sets-MIN-S-I} with $f_0$ replaced by $f_1$.
  \label{claim:intermediate-termination-possibility-if-sup-does-not-fall-enough}
  \end{claim}

  Now suppose that the algorithm does not terminate, and let $f_n$ be the $n$\textsuperscript{th} iterate. Claim~\ref{claim:intermediate-termination-possibility-if-sup-does-not-fall-enough} gives us the estimate
  \[
    \esssup_{\w \in \W} \mathcal{H}_{sym}(f_n,\w) \leq \esssup_{\w \in \W} \mathcal{H}_{sym}(f_{n-1},\w) - d_n \frac{a}{b}.
  \]
  Since $\mathcal{H}_{sym} \geq 0$, we must have $d_n \to 0$. Since for all $n$, we have
  \[
    \esssup_{\w \in \W} \mathcal{H}_{sym}(f_n,\w) < \esssup_{\w \in \W} \mathcal{H}_{sym}(f_0,\w),
  \]
  the coercivity of $\mathcal{H}_{sym}$ implies that $f_n$ must be bounded uniformly in $n$. By our construction, $\{f_n\}$ is a bounded martingale with respect to the filtration $\mathcal{F}_n = \sigma(f_1,\ldots,f_{n})$. Hence by the martingale convergence theorem, $f_{\infty}(\w) = \lim_n f_n(\w)$ exists a.s., and further the convergence is uniform in every $L^p$ norm. Then, by the continuity of the $\mathcal{H}$, its nonnegativity, and its uniform boundedness on compact sets, we get for any $p \in \R$,
  \[
    \begin{split}
      0 = & \lim_n d_n \\
      = & \lim_{n \to \infty} \esssup \mathcal{H}_{sym}(f_n(\w),\w) - \int \mathcal{H}_{sym}(f_n(\w),\w),\\
      \geq & \Norm{\mathcal{H}_{sym}(f_{\infty},\w)}{p} - \int \mathcal{H}_{sym}(f_{\infty},\w).\\
    \end{split}
  \]
  Taking $p \to \infty$ proves that $f_{\infty}$ is a corrector. This completes the proof except for~\Claimref{claim:intermediate-termination-possibility-if-sup-does-not-fall-enough}. We prove this next.

\end{proof}

\begin{proof}[Proof of~\Claimref{claim:intermediate-termination-possibility-if-sup-does-not-fall-enough}]
  Let
  \[
    R := \{ \w \in S \setminus MIN_0 : a~|\mathcal{H}_{sym}(f_0,\w) - \mu_0)| < \Delta f^*(\w) \},
  \]
  be the set on which we can modify $f_0$ without hitting the minimum of $\mathcal{H}(f_0,\w)$; i.e., $\mathcal{H}_{sym}(f_1,\w) > \mathcal{H}_{sym}(x^*(\w),\w)$. By the definition of $\Delta f$ and the bound on the derivatives of $\mathcal{H}(\cdot,\w)$ in~\Propref{lem:H-sym-is-convex-and-its-min-is-measurable}, we have
  \begin{multline*}
    \mathcal{H}(f_0,\w)  - \frac{1}{a}a(\mathcal{H}_{sym}(f_0,\w) - \mu_0) \leq \mathcal{H}(f_1,\w) \\ \leq  \mathcal{H}(f_0,\w) - \frac{1}{b} a (\mathcal{H}_{sym}(f_0,\w) - \mu_0)
    \qquad \w \in R ~\almostsurely.
  \end{multline*}
  Therefore,
  \begin{equation}
    \mu_0 \leq  \esssup_{\w \in R} \mathcal{H}(f_1,\w) \leq  \esssup_{\w \in R}  \mathcal{H}(f_0,\w) - \frac{da}{b}.
    \label{eq:bound-on-H-f1-on-set-R}
  \end{equation}

  Similarly for $\w \in I$, we use the bound on $\xi$ in~\Eqref{eq:algorithm-xi-is-bounded} to get
  \begin{equation}
    \mathcal{H}_{sym}(f_1,\w) \leq \mathcal{H}_{sym}(f_0,\w) + \xi (\mu_0 - \mathcal{H}_{sym}(f_0,\w)) \leq \mu_0 \quad \w \in I ~\almostsurely .
    \label{eq:bound-on-H-f1-on-set-I}
  \end{equation}
  From the definition of $R$, it follows that $S \setminus R \subset MIN_1$. Since $\Delta f = 0$ on $S \cap MIN_0$, we must have $S \cap MIN_0 \subset MIN_1$.

  Consider the condition in~\Eqref{eq:suppose-that-H-f1-does-not-fall-enough} again. Equations~\eqref{eq:bound-on-H-f1-on-set-R} and~\eqref{eq:bound-on-H-f1-on-set-I} imply that we can ignore the sets $R$ and $I$ when taking a sup over $\W$. It's clear that we can ignore $\W \setminus S \setminus I$ too, since $\mathcal{H}(f_0,\w) = \mu_0$ on this set. Summarizing, we get
  \[
    \begin{split}
      \esssup_{\W} \mathcal{H}_{sym}(f_1,\w) & = \esssup_{S \setminus R ~\cup~ MIN_0 \cap S} \mathcal{H}_{sym}(f_1,\w) = \esssup_{MIN_1} \mathcal{H}(f_1,\w).
    \end{split}
  \]
  Hence, the algorithm terminates at step $2$ in the next iteration.
\end{proof}

To finish, we complete the proof of~\Lemref{lem:H-sym-is-convex-and-its-min-is-measurable}.
\begin{proof}[Proof of~\Lemref{lem:H-sym-is-convex-and-its-min-is-measurable}]

  Since
  \begin{equation*}
    \mathcal{H}_{sym}(t,p,\w) = \sup_{\alpha \in A^+} \frac{|t + p\cdot\alpha|}{\tau(0,\alpha,\w)},
  \end{equation*}
  Clearly $\mathcal{H}_{sym}$ is convex. Its minimum is unique since $\tau(0,\alpha,\w) \geq a$, and therefore, it cannot have a ``flat spot'' parallel to the $t$-axis.

  Now, $\mathcal{H}_{sym}$ can only take its minimum at a minimum of $|t + p\cdot\alpha|/\tau(0,\alpha,\w)$ or when $t$ is such that $|t + p\cdot\alpha|/\tau(0,\alpha_1,\w) = |t + p\cdot\alpha|/\tau(0,\alpha_2,\w)$ for any $\alpha_1,\alpha_2 \in A_+$. There are only a finite number of such possibilities, we can compute all of them, and hence its easy to see that $x^*(\w)$ is measurable.

  The fact that $D_{-} \mathcal{H}_{sym}(t,\w) \in [b^{-1},a^{-1}]$ or $D_+ \mathcal{H}_{sym}(t,\w) \in [-a^{-1},-b^{-1}]$ for all $t$, follows easily from the form of $\mathcal{H}_{sym}$.
\end{proof}

Suppose the vector $\vec{t}(\w) = (t(e_1,\w), \ldots, t(e_d,\w))$ takes at most a finite number of different values $\{\vec{t}_0,\ldots,\vec{t}_{n-1}\} =: \W_0$. Let our probability space be $\W = (\R^d)^{\Z}$, let $\tau(z,\cdot,\w) = \w_{z_1}$ ($z_1$ is the first coordinate of $z$), and let the marginal of $\Prob$ on any coordinate of $\W$ be supported on $\W_0$.

We show that even if $\Prob$ is a product measure, under the symmetry assumption, the structure of the problem is nearly equivalent to a periodic medium. Define the sets
\[
  A_i := \{ \w \in \W : \tau(0,\cdot,\w) = \vec{t}_i \}, \quad i=1,\ldots,n-1.
\]
 The set $F$ of functions in~\Eqref{eq:set-S-under-symmetry-assumption} can be restricted to
 \begin{equation}
   F := \left\{ f(\w) : f(\w) = \sum_{i=0}^{n-1} f_i 1_{A_i}(\w),~f_i \in \R,~E[f] = 0 \right\},
   \label{eq:set-of-functions-F-in-variational-formula}
 \end{equation}
 and the algorithm continues to produce a minimizer. Now suppose we have a periodic medium with equal periods in both directions; i.e., the translations satisfy
 \[
    \tau(0,\cdot,V^n \w) = \tau(0,\cdot,V \w) ~\almostsurely.
 \]
 in addition to~\Eqref{eq:symmetry-assumption-on-medium}. Periodicity only forces the additional constraint $\Prob(A_i) = 1/n$, and except for this, the problem is nearly unchanged. Periodic homogenization has been well-studied and there are many algorithms to produce the effective Hamiltonian; see for example,~\citet{gomes_computing_2004} or~\citet{oberman_homogenization_2009}.

 Our algorithm works even if $\tau(0,\cdot,\w)$ takes an uncountable number of values; i.e., the period is infinite. Notice that what we have here is an $n$-dimensional deterministic convex minimization problem with linear constraints (see~\Propref{prop:variational-formula-in-symmetric-situation} and~\Eqref{eq:set-of-functions-F-in-variational-formula}). It's worth stating (without proof, of course) that our algorithm is computationally much faster than conjugate gradient and other standard constrained optimization methods.

 \begin{remark}
   The symmetry assumption is a massive simplification, and removing this is a real challenge. If the translations $V_i$ are rationally related, we ought to be able to generalize the algorithm with a little work. However, taking this route ---solving the loop/cocycle condition--- in general is probably hopeless. It appears that working on an instance $\w \in \W$ of the probability space would be the most convenient way to proceed, since we can work directly with a function $f\colon\Z^d \to \R$ (instead of its derivative) and forget the cocycle condition.
 \end{remark}


TITLE: Covering maps from the torus to the torus of degree any positive integer
QUESTION [1 upvotes]: I'm trying to get my head around covering maps.
I've seen a question that asks to show there are covering maps $p$ from the torus $T$ onto $T$ with degree equal to any positive integer.
I'm not sure how to show this. I know there are covering maps from $S^1$ to $S^1$ with degree equal to any positive integer $n$ (by taking the $n$th power map), so I was wondering about mapping both the $x$ and $y$ coordinate of the torus to their $n$th power. However, I'm not sure if this has degree $n$ or degree $n^2$, and I'm not sure how to prove this is a covering map.
Any help much appreciated! Thank you.

REPLY [1 votes]: First, do you know that the product of two covering maps $E\to B, F\to C$ (so $E\times F\to B\times C$) is also a covering map ?
If you don't already know this, you should definitely try and prove it, it's a good exercise !
With this in mind, it follows that for any $n,m\geq 1$, the map $p_{n,m} : S^1\times S^1\to S^1\times S^1$ given by $(z,w)\mapsto (z^n,w^m)$ is a covering map.
ADDED : Below, I used a notion of degree that is not the one you meant (they coincide for covering maps of manifolds).
For the notion you meant (the number of sheets of the covering, that is, the cardinality of each fiber), there is an easy proof which was essentially given by Paul Frost in the comments : $p_{n,m}^{-1}(x,y) = p_n^{-1}(x)\times p_m^{-1}(y)$ has cardinality $nm$.
Below was the old argument for the degree (using homological degree) :
Now, about its degree : since $n,m$ can be different, you see that your first guess (that the degree of $p_{n,n}$ be $n$) isn't quite reasonable. Your second guess, however, that it be $n^2$ (and more generally, that the degree of $p_{n,m}$ be $nm$) is way more reasonable, and in fact is what happens. And then you can clearly see how to get degree $n$ (for instance with $m=1$).
How to prove this ? Well it sort of depends on what you know. If you know the Künneth formula, then this will follow from it + the remark that $z\mapsto z^n, S^1\to S^1$ has degree $n$. Can you see why ?
If you don't know the Künneth formula, but do know about cohomology (or like it better), then you can do it using that as well : indeed by the universal coefficients theorem, the degree of the map can also be detected cohomologically, so looking at $H^2(\mathbb T)\to H^2(\mathbb T)$. But then $H^*(\mathbb T) = \mathbb Z[x,y]/(x^2,y^2)$ with $x,y$ in degree $1$ and anticommuting, so $H^2(\mathbb T) = \mathbb Z \cdot xy$, so you can get the degree from looking at where $x,y$ are sent. But for those you can look at $\pi_1$, and then it's clear.
If you don't know the Künneth formula, and don't know about the cohomology ring, there's probably other ways to do it, but probably with some trick. For instance use that $p_{n,m}$ is actually the composite of $p_{n,1}$ and $p_{1,m}$, so you can restrict yourself to either of those, and by symmetry to, say, $p_{n,1}$, and then you can probably use the local degree formula (but you'd have to know that).


TITLE: matrix with variable and their rank
QUESTION [0 upvotes]: $M = \pmatrix{1 + p& 0& 0& p\\p& 2p& 1 + 3p& p\\2p& 0& 0& 0\\0& 4p& 0& 2p\\p& 2p& 3p& p}$
has rank $4$ for for a variable $p\in\mathbb{C} \text{ or }\mathbb{R}$, does this mean: for any complex number $p$ the columns are linearly independent set of vectors in $\mathbb{C}^5 \text { or }\mathbb{R}^5$?
And, regarding the assurance of its rank $4$, I put it in Matlab and asked rank($M$), and it gives result $4$

REPLY [1 votes]: For $p=0$, the last column is equal to zero, so in this case rank is clearly at most $3$.
Let us have a look on the case $p\ne0$. A rather standard method to find matrix rank is to use elementary row operations and/or elementary column operations. Notice that since we assume that $p\ne0$, we are allowed to divide by $p$.
$\begin{pmatrix}
1+p& 0 & 0  & p\\
 p &2p &1+3p& p\\
2p & 0 & 0  & 0\\
 0 &4p & 0  &2p\\
 p &2p &3p  & p
\end{pmatrix}\sim
\begin{pmatrix}
1+p& 0 & 0  & p\\
 p &2p &1+3p& p\\
 2 & 0 & 0  & 0\\
 0 & 4 & 0  & 2\\
 1 & 2 & 3  & 1
\end{pmatrix}\sim
\begin{pmatrix}
 1 & 0 & 0  & 0\\
1+p& 0 & 0  & p\\
 p &2p &1+3p& p\\
 0 & 4 & 0  & 2\\
 1 & 2 & 3  & 1
\end{pmatrix}\sim
\begin{pmatrix}
 1 & 0 & 0  & 0\\
 0 & 0 & 0  & p\\
 0 &2p &1+3p& p\\
 0 & 2 & 0  & 1\\
 0 & 2 & 3  & 1
\end{pmatrix}\sim
\begin{pmatrix}
 1 & 0 & 0  & 0\\
 0 & 0 & 0  & 1\\
 0 & 0 &1+3p& 0\\
 0 & 2 & 0  & 1\\
 0 & 0 & 3  & 0
\end{pmatrix}\sim
\begin{pmatrix}
 1 & 0 & 0  & 0\\
 0 & 2 & 0  & 1\\
 0 & 0 & 3  & 0\\
 0 & 0 & 0  & 1\\
 0 & 0 &1+3p& 0
\end{pmatrix}\sim
\begin{pmatrix}
 1 & 0 & 0  & 0\\
 0 & 2 & 0  & 0\\
 0 & 0 & 1  & 0\\
 0 & 0 & 0  & 1\\
 0 & 0 &1+3p& 0
\end{pmatrix}\sim
\begin{pmatrix}
 1 & 0 & 0  & 0\\
 0 & 1 & 0  & 0\\
 0 & 0 & 1  & 0\\
 0 & 0 & 0  & 1\\
 0 & 0 & 0& 0
\end{pmatrix}$
We see that the rank (in the case $p\ne0$) is indeed equal to $4$.
And to answer your additional question: Yes, this means that for $p\ne0$ the columns are linearly independent.