text:
\chapter{Comparing two distributions}
\label{chap:comparing-two-distributions}

\section{A simple coupling based argument}
For $i=1,2$, let $(\Omega_i,\mathcal{F}_i,\Prob_i)$ be probability spaces, and let $\tau_i\colon\Z^d \times A \times \W \to \R$ be two edge-weight functions. Assume that
\begin{equation*}
  \begin{split}
    0 <~& a_i = \essinf_{x,\alpha,\w} \tau_i(x,\alpha,\w), \\
    & b_i = \esssup_{x,\alpha,\w} \tau_i(x,\alpha,\w) < \infty.
  \end{split}
\end{equation*}

We wish to compare $m_1(x)$ and $m_2(x)$, the corresponding time-constants. There is an elementary argument to obtain a very basic estimate between the two time-constants\footnote{told to me by M. Damron}. We will reproduce it using the variational formula to highlight the duality in the problem.

It will be easier to compare the two \FPP~problems if they're both on the space $(\R^{d})^{\Z^d}$, and we first show that we can always assume this. Consider the map $M\colon\W \to (\R^{d})^{\Z^d}$ defined as
\begin{equation}
  M(\w) = (\tau(V_z \w))_{z \in \Z^d}.
  \label{eq:map-M-of-omega-into-R-infinity}
\end{equation}
Let
\begin{equation}
  \mathcal{C} = \sigma(M) \subset \mathcal{F}
  \label{eq:sigma-algebra-C-generated-by-M}
\end{equation}
be the sigma-algebra generated by $M$. We next show that it's enough to consider functions $f \in S$ that are measurable with respect to $\mathcal{C}$.
\begin{prop}
  Assume that every $f \in S$ (defined in~\Corref{cor:discrete-set-S-for-variational-formula-with-lipschitz-constraint}) also satisfies the additional condition that $f(x,\w)$ is $\mathcal{C}$ measurable for each $x \in \Z^d$. Then, the variational formula in~\Eqref{eq:variational-formula-at-origin} is unchanged.
  \label{prop:functions-measurable-wrt-sigma-tau}
\end{prop}
The proof is a simple consequence of convexity and can be found in~\Secref{sec:some-proofs-from-comparing-two-distros}.

With~\Propref{prop:functions-measurable-wrt-sigma-tau}, it's easy to show that pushing the problem forward to the space $(\R^{2d})^{\Z^d}$ does not change the first-passage percolation problem. Let $\textrm{Im}(M) \subset (\R^{2d})^{\Z^d}$ be the image of $\W$ under the map $M$. Let $\Prob_M$ be the push-forward measure of $\Prob$ under $M$. It is enough to show that for each $f \in S$, there is a $g\colon(\R^{2d})^{\Z^d} \to \R$ such that
\[
  g(M(\w)) = f(\w) \quad \almostsurely .
\]
By~\Propref{prop:functions-measurable-wrt-sigma-tau}, we can assume that $f$ is $\sigma(M)$ measurable and hence by an elementary measurability lemma (see, for example~\citet{williams_probability_1991}) there is a function $g$ as required above.

Therefore, we will henceforth assume that $\W = (\R^{d})^{\Z^d}$, $\mathcal{F}$ is the infinite product $\sigma$-algebra, $\Prob_1 \AND \Prob_2$ are the probability measures, the group of translations are just shift maps, and
\[
  t_i(\w) := (\tau_i(0,\alpha,\w_i))_{\alpha \in A},
\]
is the first coordinate of $\w$.

A coupling of two measures $\Prob_1$ and $\Prob_2$ is a probability measure on the product space $\W \times \W$ with product sigma-algebra $\mathcal{F} \times \mathcal{F}$ and $\Prob_1 \AND \Prob_2$ as marginals. Let $\Pi(\W \times \W)$ be the space of all couplings on $\W \times \W$.
\begin{define}[a type of $W^{\infty}$ Wasserstein distance]
  \[
    d(\Prob_1,\Prob_2) = \inf_{\pi \in \Pi(\W \times \W)} \esssup_{(\w_1,\w_2) \in \W \times \W} \sup_{\alpha \in A} |t(\w_1) - t(\w_2)|.
  \]
  \label{define:l-infinity-coupling-distance}
\end{define}

The primal version of the comparison result is easily proved:
\begin{prop}
  For all $x \in \R^d$,
  \begin{equation*}
    | m_1(x) - m_2(x) | \leq \max\left( \frac{b_1}{a_1}, \frac{b_2}{a_2} \right) d(\Prob_1,\Prob_2) |x|_1 .
  \end{equation*}
  \label{prop:distance-estimate-between-time-constants-primal-argument}
\end{prop}
\begin{proof}
  Let $\gamma$ be a path connecting the origin to $[nx]$, let $\pi$ be a coupling, and let $d(\gamma)$ be the $l^1$ length of the path. Then,
  \[
    \sum_{i=1}^{d(\gamma)} | \tau_1(\gamma_i,\gamma_{i+1} - \gamma_i,\w_1) - \tau_2(\gamma_i,\gamma_{i+1} - \gamma_i,\w_2) | \leq d(\gamma) \esssup_{\w_1,\w_2} |t(\w_1) - t(\w_2)|_{\infty}.
  \]
  Since we can always take a shortest $l^1$ distance path between $0$ and $[nx]$, its enough to consider paths from $0$ to $[nx]$ that satisfy
  \[
    d(\gamma) \leq \max\left( \frac{b_1}{a_1}, \frac{b_2}{a_2} \right) |[nx]|_1.
  \]
  Take an inf over all such paths to get
  \[
    |T_1([nx]) - T_2([nx])| \leq  \max\left( \frac{b_1}{a_1}, \frac{b_2}{a_2} \right) \esssup_{\w_1,\w_2} |t(\w_1) - t(\w_2)|_{\infty} |[nx]|_1
  \]
  Divide by $n$ and take a limit as $n \to \infty$. Taking an infimum over couplings $\pi$, we get the result.
\end{proof}

We can prove a similar version of~\Propref{prop:distance-estimate-between-time-constants-primal-argument} using just the variational formula.
\begin{prop}
  For all $x \in \R^d$,
  \begin{equation*}
    | m_1(x) - m_2(x) | \leq \max\left(\frac{b_1}{a_1},\frac{b_2}{a_2}\right) \frac{b_1 b_2}{a_1 a_2} d(\Prob_1,\Prob_2) |x|_1
  \end{equation*}
  \label{prop:distance-estimate-between-time-constants-dual-argument}
\end{prop}
With the following lemma, the proof of~\Propref{prop:distance-estimate-between-time-constants-dual-argument} is easy.
\begin{lemma}
  Let $H_1$ and $H_2$ be the corresponding limiting Hamiltonians. Then,
  \[
    |\overline{H}_1(p) - \overline{H}_2(p)| \leq \max\left(\frac{b_1}{a_1},\frac{b_2}{a_2}\right) |p|_{\infty}\frac{1}{a_1 a_2} d(\Prob_1,\Prob_2)
  \]
    \label{lem:distance-estimate-between-Hamiltonians}
\end{lemma}

\begin{proof}[Proof of~\Propref{prop:distance-estimate-between-time-constants-dual-argument}]

  We established the elementary inequality
    \[
      \overline{H}_i(p) \geq \frac{|p|_{\infty}}{b_i}
    \]
    in the proof of Proposition~$3.9$ in part I. Hence for each $x,p \in \R^d$,
    \[
      \begin{split}
        \left| \frac{p\cdot x}{\overline{H}_1(p)} - \frac{p\cdot x}{\overline{H}_2(p)} \right|
        & = \left| p\cdot x \left( \frac{\overline{H}_1(p) - \overline{H}_2(p)}{\overline{H}_1(p) H_2(p)} \right) \right| \\

        & \leq \max\left(\frac{b_1}{a_1},\frac{b_2}{a_2}\right) \frac{1}{a_1 a_2} |x|_1 d(\Prob_1,\Prob_2).
      \end{split}
    \]
    We've used the H\"older inequality and~\Lemref{lem:distance-estimate-between-Hamiltonians} in the above computation. Since $m_i$ are the dual norms of $\overline{H}_i$, the proof is complete.
\end{proof}
\begin{proof}[Proof of~\Lemref{lem:distance-estimate-between-Hamiltonians}]
  First, fix $f \in S$, where $S$ is defined in~\Eqref{eq:discrete-set-S-for-variational-formula-with-lipschitz-constraint}. For each measure $\Prob_1 \AND \Prob_2$, the constraint on $S$ is different:
  \[
    \sup_{\alpha \in A} \left( - \mathcal{D}f(x,\alpha) - p \cdot \alpha \right) \leq \frac{b_1}{a_1}|p|_{\infty} \qquad \forall x \in \Z^d.
  \]
  Hence, we might as well assume that
  \[
    \sup_{\alpha \in A} \left| \mathcal{D}f(x,\alpha) + p \cdot \alpha \right| \leq \max\left(  \frac{b_1}{a_1}, \frac{b_2}{a_2}\right) \qquad \forall x \in \Z^d.
  \]

  Then, for a fixed coupling $\pi \in \Pi(\W \times \W)$,
    \begin{align*}

      \left|
      \vphantom{\frac{\mathcal{D}f(0,\alpha,\w_1) + p\cdot\alpha}{\tau_1(0,\alpha,\w_1)} - \frac{\mathcal{D}f(0,\alpha,\w_2) + p\cdot\alpha}{\tau_2(0,\alpha,\w_2)}}
      \frac{\mathcal{D}f(0,\alpha,\w_1) + p\cdot\alpha}{\tau_1(0,\alpha,\w_1)} -
      \right. & \left.
      \vphantom{\frac{\mathcal{D}f(0,\alpha,\w_1) + p\cdot\alpha}{\tau_1(0,\alpha,\w_1)} - \frac{\mathcal{D}f(0,\alpha,\w_2) + p\cdot\alpha}{\tau_2(0,\alpha,\w_2)}}
      \frac{\mathcal{D}f(0,\alpha,\w_2) + p\cdot\alpha}{\tau_2(0,\alpha,\w_2)} \right| \\
      & \leq \max\left( \frac{b_1}{a_1},\frac{b_2}{a_2} \right) |p|_{\infty} \frac{|\tau_1(0,\alpha,\w_1) - \tau_2(0,\alpha,\w_2)|}{\tau_1(0,\alpha,\w_1)\tau_2(0,\alpha,\w_2)} \\
      & \leq \max\left(  \frac{b_1}{a_1}, \frac{b_2}{a_2}\right) |p|_{\infty}\frac{1}{a_1 a_2} \esssup_{\w_1,\w_2} |t(\w_1) - t(\w_2)|_{\infty},
    \end{align*}
  using~\Corref{cor:discrete-set-S-for-variational-formula-with-lipschitz-constraint}. Since this is true for all functions in $S$, and all couplings in $\Pi(\W \times \W)$, we can take supremums and infimums as appropriate to get the result.
\end{proof}

\begin{remark}
  The estimate through the variational formula in~\Propref{prop:distance-estimate-between-time-constants-dual-argument} is worse than the estimate in~\Propref{prop:distance-estimate-between-time-constants-primal-argument}. However, the estimates used ---the lower bound for $\overline{H}(p)$ and the bound for $\nu_{\e}$ from~\Eqref{eq:2-lipschitz-conditions-nu-epsilon-upper-bound}--- were quite crude, and these are easily improved.
\end{remark}
\begin{remark}
  The basic step in the primal argument was to take the worst case path in the $x$ direction, and the corresponding step in the dual argument was to take the worst case function $f$ in the $p$ direction. This seems to indicate some (nonlinear) duality between paths on the lattice and functions in $S$. Is there a structural theory of this duality?
\end{remark}

\section{A more convenient coupling distance}
The coupling distance in~\Defref{define:l-infinity-coupling-distance} is not very useful in general. However, when the medium is i.i.d, it's easy to get an upper bound for it in terms of a more familiar distance on the marginal distribution of the edge-weight $\tau(0,\alpha,\w)$. When $\Prob = \mu^{\otimes \Z^d}$, where $\mu$ is a measure on $\R^{d}$, couplings on $\R^d \times \R^d$ can be turned into a coupling on $\W \times \W$ by taking a product. Suppose further that the marginal measure $\mu$ on $\R^d$ is also an i.i.d.~product measure, and let $F_i$ be the cumulative distribution function of $\tau_i(0,\alpha,\w)$ for $i=1,~2$. Then, for example, we can write $d(\Prob_1,\Prob_2)$ in terms of the Kolmogorov-Smirnov distance between $F_1 \AND F_2$, assuming $F_1 \AND F_2$ are nice enough.

Let $F_i$ have density $\rho_i$, and assume
\[
\begin{split}
  \min(\text{supp}(F_i)) = & [a_i,b_i] \subset (0,\infty), \\
  \rho^* = & \min_i \min_{a_i \leq x \leq b_i} \rho_i(x) > 0,
\end{split}
\]
where supp denotes the support of the distribution. Let
\[
    d_{Kol}(F_1,F_2) = \sup_x |F_1(x) - F_2(x)|
\]
be the Kolmogorov-Smirnov distance between the two distributions.

We will use the standard Skorokhod representation to define random variables $Y_i(x)$ on $([0,1],\mathcal{F},\Leb)$ with distributions $F_i$. Since $\rho^{\ast} > 0$, $F_i$ is strictly monotone, and hence we define

\begin{define}[Skorokhod representation of edge-weights]
  \[
    Y_i(x) = F^{-1}_i(x).
  \]
  \label{def:skorokhod-representation-of-tau}
\end{define}

It's clear that $\Leb(Y_i(x) \leq c) = \Leb(F^{-1}_i(x) \leq c) = F(c)$.
\begin{prop}
  \[
  |Y_1(x) - Y_2(x)| \leq \frac{d_{Kol}(F_1,F_2)}{\rho^*}
  \]
  \label{prop:distance-between-embedded-tau1-and-tau2}
\end{prop}
\begin{proof}
  Fix $s \in [0,1]$, let $x = F_1^{-1}(s)$, and use $d = d_{Kol}(F_1,F_2)$ as shorthand.

  From the definition of the Kolmogorov-Smirnov distance,
  \[
  F_2(x)  \geq F_1(x) - d = s - d.
  \]
  If $r \geq d/\rho^* + x$, we have
  \[

    F_2(r) \geq (s-d) + \rho^* (r - x) = s.

  \]
  It follows that
  \[
    F^{-1}_2(s) \leq \frac{d}{\rho^*} + F_1^{-1}(s) .
  \]
  Repeating the argument for $x = F_2^{-1}(s)$, we get the result.
\end{proof}
Let $\pi$ be the coupling on $\R \times \R$ defined as the pushforward measure of $\Leb([0,1] \times [0,1]$ under the map $(x_1,x_2) \mapsto (Y_1(x_1),Y_2(x_2))$. We can take a product of $\pi$ to get a coupling on $\W \times \W$. Thus, we have proved that
\[
  d(\Prob_1,\Prob_2) \leq d_{Kol}(F_1,F_2).
\]

config: arxiv


TITLE: proving that some spaces are homeomorphic
QUESTION [3 upvotes]: I was doing some problems , but I don´t know how to prove 2 of them Dx  , that are about homeomorphism.
I have to prove that
$$
R^{n + 1}  - \left\{ 0 \right\} \cong S^n \times\,R
$$
where R denotes the real numbers all of this with the usual topology of $R^n$
For every $c>0$  $
\left\{ {\left( {x,y,z} \right) \in R^3 :x^2  + y^2  - z^2  = c} \right\} \cong S^1 \,\times\,R
$ I think that it will be useful to use the last problem  :/

REPLY [5 votes]: Define a map from $\mathbb R^{n+1}\setminus\{0\}$ to $S^n\times\mathbb R^+$ as follows:
$$\vec{x}\mapsto (\vec{x}/||\vec{x}||,||\vec{x}||).$$
Now verify that this is a homeomorphism, and use that $\mathbb R^+\cong \mathbb R$.


TITLE: Canonical Form of $x^2+x-y=p$
QUESTION [0 upvotes]: Can anyone please help me to put the following equation into canonical form, with the $p$ at the end being a constant:
$$x^2+x-y^2=p$$
Or even just explain what canonical form is?

REPLY [0 votes]: Are you learning conics? $x^2+x -y^2 = p \implies \left(x+\dfrac{1}{2}\right)^2 - y^2 = p+\dfrac{1}{4}$. But if your original equation is: $x^2+x -y = p \implies y = \left(x+\dfrac{1}{2}\right)^2 - p - \dfrac{1}{4}$


TITLE: How to recover multiplication of group elements from category of groups?
QUESTION [8 upvotes]: Motivating question: If we know everything about $\mathbf{Grp}$, do we know everything about groups?
Background: Consider the category $\mathbf{Grp}$ abstractly, rather than as a concrete category.  The elements of a group $G$ may be recovered as follows: first, identify the group $\mathcal{Z}$ as the unique minimal generator (MO/7793), i.e. a generator such that no proper quotient is also a generator.    Then Hom($\mathbb{Z}$,-) represents the forgetful functor $\mathbf{Grp} \to \mathbf{Set}$ and recovers the elements of group.
Question:

How can you also recover the group operation on elements?

Here is an unfinished attempt (that someone else mentioned): define the free group on two generators by the coproduct $F_2 = \mathbb{Z} \amalg \mathbb{Z}$.  Then for two group elements $g_1, g_2 : \mathbb{Z} \to G$, these maps will define a map $f :  F_2 \to G$ (because $F_2$ is a colimit).  Finally, suppose we could categorically specify the map $m : \mathbb{Z} \to F_2, 1 \mapsto xy$, where $x,y$ are the generators of $F_2$.  Then the group multiplication of the elements $g_1, g_2$ would yield the element $g_1 g_2 = f \cdot m : \mathbb{Z} \to G$.
In the above approach, the only remaining task is to somehow specify the map $m : \mathbb{Z} \to F_2, 1 \mapsto xy$ categorically.
Edit (in response to comment):
I should mention that we will not be able to distinguish $m : \mathbb{Z} \to F_2, 1 \mapsto xy$ from $m' : 1 \mapsto yx$.  The best we can hope for is to specify both $m$ and $m'$ without singling either of them out.  In other words, when we attempt to recover group multiplication, we can provide a choice of either the original group multiplication or multiplication in the opposite group, but we cannot privilege either choice.  The reason is that the functor sending a group to its opposite group is an auto-equivalence of $\mathbf{Grp}$.

REPLY [2 votes]: Once you have $\mathbb{Z}$, you have the Lawvere theory of groups (which can be recovered as the opposite category on the full subcategory on the finite coproducts of $\mathbb{Z}$), which is a way of axiomatizing what a group is that doesn't depend on a choice of "generators." What I mean by this is that multiplication, inversion, and unit can be composed to get a lot of other operations, such as
$$(x, y, z) \mapsto x^{-3} y z^4 y^3$$
which satisfy some relations, and the Lawvere theory of groups packages up all of this information (the above operation is, after all, the same thing as a particular element of $F_3$) without privileging a particular choice of generating operations, in the same way that you can specify a group itself in a way that doesn't privilege a particular presentation. See, for example, this blog post and this blog post for some details.


TITLE: Group of Order $p^2$ Isomorphic to $\mathbb{Z}_{p^2}$ or $\mathbb{Z}_{p}$ $\times$ $\mathbb{Z}_{p}$
QUESTION [2 upvotes]: I'm a bit lost on this problem:

Show that a group of order $p^2$ is isomorphic to $\mathbb{Z}_{p^2}$ or $\mathbb{Z}_{p}$ $\times$ $\mathbb{Z}_{p}$.

The only thing I can think of that may relate to this problem is Lagrange's Theorem, where the order of a subgroup divides the order of a group. But I'm not sure if I can even use that for this problem... Any help would be tremendously helpful. Thank you!

REPLY [0 votes]: (Note $|G|=p^2\implies G$ is abelian, but I'd leave that out as a separate proof.)
Let $a\in G$.  By Lagrange's Theorem $\operatorname{ord}(a) = 1, p$ or $p^2$ .

$\operatorname{ord}(a) = 1\implies a = e.$
$\operatorname{ord}(a) = p$.  Let $H = \langle a\rangle$, which is a subgroup of $G$.
$(G:H) = p^2/p = p\implies G/H = \langle Hb\rangle$ for $b\in G$ and $b\not\in H$.
In other words,\begin{align*}
    G = & \, \{e, \\
    &\,\, a, a^2, \cdots, a^{p-1}, \\
    & \,\,b, b^2, \cdots, b^{p-1}, \\
    & \,\,ab, ab^2, \cdots, ab^{p-1}, a^2b,\cdots, a^{p-1}b^{p-1} \}
  \end{align*}
Let $f: G\rightarrow \mathbb{Z}_p\times\mathbb{Z}_p$ such that $f(a^xb^y) = (x, y)$ for $(x, y)\in\mathbb{Z}_p\times\mathbb{Z}_p$.
(a) $f$ is invertible, as $f^{-1}(x,y) = a^xb^y \implies f$ is a bijection.
(b) $f(a^xb^y) = (x,y) = (x,0) + (0,y) = f(a^x) + f(b^y)\implies f$ is a homomorphism.
Hence $\operatorname{ord}(a) = p\implies G\cong\mathbb{Z}_p\times\mathbb{Z}_p$.
$\operatorname{ord}(a) = p^2\implies G = \{e, a, a^2, \cdots, a^{p^2-1}\}$.
Let $f: G\rightarrow \mathbb{Z}_{p^2}$ such that $f(a^x) = x$ for $x\in \mathbb{Z}_{p^2}$.
(a) $f$ is invertible, as $f^{-1}(x) = a^x \implies f$ is a bijection.
(b) $f(a^xa^y) = f(a^{x+y}) = x+y = f(a^x) + f(a^y)\implies f$ is a homomorphism.
Hence $\operatorname{ord}(a) = p^2\implies G\cong\mathbb{Z}_{p^2}$.

$\Box$


TITLE: The solution of the classical Yang-Baxter equation induces a Lie bialgebra
QUESTION [1 upvotes]: We know that the classical Yang-Baxter equation is
$$[r_{12}, r_{13}]+[r_{12}, r_{23}]+[r_{13}, r_{23}]=0,\quad(*)$$
and we have the following Theorem.
Theorem: Let $\mathcal{G}$ be a Lie algebra and $r\in \mathcal{G}\otimes \mathcal{G}.$ Then the map $\delta: \mathcal{G}\rightarrow
\mathcal{G}\otimes \mathcal{G}$ defined by Eq. $\delta(X)=X.r$ induces a Lie bialgebra structure on $\mathcal{G}$ if and only if the following two conditions are satisfied (for any $x\in \mathcal{G}$).

$(\mathrm{ad}(x)\otimes \mathrm{id} +\mathrm{id}\otimes \mathrm{ad}(x))(r+r^{21})=0;$
$(\mathrm{ad}(x)\otimes \mathrm{id} \otimes \mathrm{id} +\mathrm{id} \otimes \mathrm{ad}(x)\otimes \mathrm{id}+\mathrm{id} \otimes \mathrm{id} \otimes \mathrm{ad}(x))([r_{12}, r_{13}]+[r_{12}, r_{23}]+[r_{13}, r_{23}])=0.$

The theorem shows that when $r\in \mathcal{G}\otimes \mathcal{G},$ induces a Lie bialgebra structure if and only if satisfying two conditions.
My question is that how to induce the lie bialgebra when $r\in \mathcal{G}\otimes \mathcal{G}$ is the solution of the equation (*), can you give me some references? Thank you very much.

REPLY [1 votes]: Simply take $\delta(x)=ad_x(r)$.
First condition says that the image of $\delta$ is contained in the subspace of anti-symmetric tensor.
The cocycle condition is trivial because $\delta$ is a coboundary.
Condition 2 translates into co-Jacobi. This requires some pacient, but no trick. Write $r=r_1+r_2$ with $r_1$ Anti symmetric and $r_2$ symmetric. Condition 2 is equivalent to the fact that $ [r_1,r_1]\in \Lambda^3g$ is an invariant tensor. When $\delta(x)=ad_x(r)$ (this is equal to $ad_x(r_1)$ because $r_2$ is ad invariant), the invariance of this element is tautologically co-Jacobi condition.


TITLE: What was the heuristics behind Gauss's guess on the asymptotic distribution of k-almost primes?
QUESTION [2 upvotes]: My question refers to Gauss's conjecture on the number $\pi_{k}(n)$ of k-almost primes less then a given number $n$. Gauss conjectured that:
$$\pi_{k}(n) \sim \biggl(\frac {{n}}{{\log (n)}}\biggr)\frac {{(\log (\log (n)))^{k - 1}}}{{(k - 1)!}}\,.$$
To be more precise historically, in Gauss's writing appear only the cases $k=1$ (the prime number theorem), $k = 2$ and $k = 3$, but the general form of the conjecture can be understood from these cases as well.
I found it very difficult to understand how Gauss came up with this. In contrast to the prime number theorem, where he might have conjectured it on the basis of empirical numeric tables, the complicated form of the conjecture in the cases $k= 2$ and $k = 3$ is much more difficult to guess empirically. So I think he might have had a kind of heuristic method to come up with this conjecture.
Something is not clear historically about Gauss's asymptotic laws in number theory. So if anybody has a clue, or even an example of an heuristic that leads to this conjecture, I'll be glad to hear.

REPLY [3 votes]: Once you know or have (correctly) guessed that $\pi(x) \sim \frac{x}{\log x}$, you don't need heuristics or guesses to come up with the asymptotic behaviour of the $k$-almost primes. You can compute that from the asymptotic behaviour of $\pi$.
Let's look at the semiprimes first - unsurprisingly, the simplest case. If $n \leqslant x$ is a semiprime, then (at least) one prime factor of $n$ must be $\leqslant \sqrt{x}$. Hence
$$\sum_{p \leqslant \sqrt{x}} \pi\biggl(\frac{x}{p}\biggr) \tag{$\ast$}$$
counts the semiprimes not exceeding $x$. Not exactly, since semiprimes both of whose prime factors are $\leqslant \sqrt{x}$ are counted twice. Subtract the count of those. That's $\frac{1}{2} \pi(\sqrt{x})\bigl(\pi(\sqrt{x} \pm 1\bigr)$, the sign depending on whether $\pi_2(x)$ shall count only squarefree semiprimes or also the squares of primes. The difference is obviously asymptotically negligible. The overcounting is $O(\pi(\sqrt{x})^2) = O\bigl(\frac{x}{(\log x)^2}\bigr)$, so just from looking at the even semiprimes we can conclude that it's asymptotically irrelevant.
Hence it suffices to compute $(\ast)$ using $\pi(x) \sim \frac{x}{\log x}$. Since the arguments of $\pi$ in $(\ast)$ are all $\geqslant \sqrt{x}$, it's easy to see that
$$\sum_{p \leqslant \sqrt{x}} \pi\biggl(\frac{x}{p}\biggr) \sim \sum_{p \leqslant \sqrt{x}} \frac{x}{p\log \frac{x}{p}} = \frac{x}{\log x} \sum_{p \leqslant \sqrt{x}} \frac{1}{p\bigl(1 - \frac{\log p}{\log x}\bigr)}\,.$$
From the (assumed or proven) asymptotics of $\pi(x)$, via summation by parts one obtains the relations
$$\sum_{p \leqslant y} \frac{\log p}{p} \sim \log y \qquad\text{and}\qquad \sum_{p \leqslant y} \frac{1}{p} \sim \log \log y,$$
and together with
$$1 < \frac{1}{1-y} \leqslant 1 + 2y$$
for $0 < y \leqslant \frac{1}{2}$ we find
$$\sum_{p \leqslant \sqrt{x}} \frac{1}{p} < \sum_{p \leqslant \sqrt{x}} \frac{1}{p\bigl(1-\frac{\log p}{\log x}\bigr)} \leqslant \sum_{p \leqslant \sqrt{x}} \frac{1}{p} + \frac{2}{\log x}\sum_{p \leqslant \sqrt{x}} \frac{\log p}{p}\,.$$
Hence
$$\sum_{p \leqslant \sqrt{x}} \frac{1}{p}\Biggl(\frac{1}{1-\frac{\log p}{\log x}} - 1\Biggr)$$
remains bounded, and
$$\pi_2(x) \sim \sum_{p \leqslant \sqrt{x}} \pi\biggl(\frac{x}{p}\biggr) \sim \frac{x}{\log x} \log \log \sqrt{x} \sim \frac{x}{\log x}\log \log x\,.$$
For $3$-almost primes, we count similarly.
$$\sum_{p \leqslant \sqrt[3]{x}} \pi_2\biggl(\frac{x}{p}\biggr)$$
counts the products $\leqslant x$ of three primes having a prime factor $\leqslant \sqrt[3]{x}$. Of course these are all $3$-almost primes not exceeding $x$. But the $3$-almost primes having two prime factors $\leqslant \sqrt[3]{x}$ are counted twice, so we must subtract their count, and arrive at
$$\sum_{p \leqslant \sqrt[3]{x}} \pi_2\biggl(\frac{x}{p}\biggr) - \sum_{p \leqslant q \leqslant \sqrt[3]{x}} \pi\biggl(\frac{x}{pq}\biggr)\,.$$
But those with all three factors $\leqslant \sqrt[3]{x}$ now have been added thrice and subtracted thrice, so that count has to be re-added. But their count is $O(\pi(\sqrt[3]{x})^3) = O\bigl(\frac{x}{(\log x)^3}\bigr)$, hence asymptotically insignificant. (The "thrice added and thrice subtracted" isn't correct for numbers with a repeated prime factor, but looking at those shows their number is negligible.) Using the obtained asymptotics for $\pi_2$, we calculate
$$\sum_{p \leqslant \sqrt[3]{x}} \pi_2\biggl(\frac{x}{p}\biggr) \sim \frac{x(\log \log x)^2}{\log x}$$
in a similar way as above (the $\log \log \frac{x}{p} = \log \log x + \log \bigl(1 - \frac{\log p}{\log x}\bigr)$ factor causes a bit of extra work but no difficulty), and - omitting some details to justify ignoring some asymptotically negligible terms - we obtain
\begin{align}
\sum_{p\leqslant q \leqslant \sqrt[3]{x}} \pi\biggl(\frac{x}{pq}\biggr)
&\sim \frac{x}{\log x}\sum_{p,q} \frac{1}{pq} \\
&= \frac{x}{\log x} \sum_{q \leqslant \sqrt[3]{x}} \frac{1}{q}\sum_{p \leqslant q} \frac{1}{p} \\
&\sim \frac{x}{\log x} \sum_{q\leqslant \sqrt[3]{x}} \frac{\log \log q}{q} \\
&\sim \frac{x}{\log x}\cdot \frac{(\log \log \sqrt[3]{x})^2}{2} \\
&\sim \frac{x(\log \log x)^2}{2\log x}\,,
\end{align}
using
$$\sum_{p \leqslant y} \frac{(\log \log p)^k}{p} \sim \frac{(\log \log y)^{k+1}}{k+1}$$
which also follows from $\pi(x) \sim \frac{x}{\log x}$. Subtraction yields $\pi_3(x) \sim \frac{x(\log \log x)^2}{2\log x}$.
Generally, the inclusion-exclusion principle gives us
$$\pi_k(x) = \sum_{r = 1}^{k-1} (-1)^{r-1} \sum_{p_1 \leqslant \dotsc \leqslant p_r \leqslant \sqrt[k]{x}} \pi_{k-r}\biggl(\frac{x}{p_1\cdot \dotsc\cdot p_r}\biggr) + O\biggl(\frac{x}{(\log x)^k}\biggr)\,,$$
and one finds
\begin{align}
\sum_{p_1 \leqslant \dotsc \leqslant p_r \leqslant \sqrt[k]{x}} \pi_{k-r}\biggl(\frac{x}{p_1\cdot \dotsc\cdot p_r}\biggr) &\sim \frac{x(\log \log x)^{k-r-1}}{(k-r-1)!\,\log x}\sum_{p_1 \leqslant \dotsc \leqslant p_r \leqslant \sqrt[k]{x}} \frac{1}{p_1\cdot\dotsc\cdot p_r} \\
&\sim \binom{k-1}{r}\frac{x(\log \log x)^{k-1}}{(k-1)!\,\log x}\,.
\end{align}
Since $\sum_{r = 1}^{k-1} (-1)^{r-1}\binom{k-1}{r} = 1$, we find
$$\pi_k(x) \sim \frac{x(\log \log x)^{k-1}}{(k-1)!\,\log x}$$
for all $k \geqslant 1$.
The omitted steps showing that all other terms in the expansions are negligible are tedious, but pose no technical challenge.
It may be worth pointing out that due to the slow growth of $\log \log x$,  the lower order terms can overshadow the dominant term for a long time.  Except for small $k$, the asymptotics are useless  in ranges where the $k$-almost primes can be explicitly counted.


TITLE: Is Universal set undefined?
QUESTION [0 upvotes]: Is there any formal definition for Universal set other than informal definitions that are used generally?

REPLY [4 votes]: The universal set is "the set of all objects of interest". Assuming modern set theory is in play (read: Zermelo–Fraenkel), the objects of interests are themselves sets, and under certain (and arguably reasonable) assumptions, there is no set of all sets.
Other approaches to formalizing set theory do allow for a universal set (e.g. Quine's New Foundations, or Positive set theory), and they deter the Russell paradox in other ways.

When you are not interested in set theory, then your universal set is just some "large enough set to include all the meaningful information". This could be the real numbers, and a bunch of functions, or about of other objects.
For example, if you are working in a topological space $X$, then treating $X$ as the universal set is useful. Because $\bigcap\varnothing$ is defined to be "everything", or the universal set, if such set exists.
This makes it slightly cleaner to think about "finite intersection of open sets is open", because $\varnothing$ is itself a finite collection of open sets, so $\bigcap\varnothing$ is supposed to be open. But if we evaluate $\bigcap\varnothing$ in the full set theoretic universe, this is not a set.


TITLE: Construct a second order linear differential equation
QUESTION [2 upvotes]: I'm wondering if somebody can help me with this question.

Construct a second-order linear differential equation that has this following general solution:

$$x(t)=a(t^2-1)+be^{t^2+t}$$ for a,b two constant.

I tried to compute : $\frac{d^2}{dt^2}x(t)$ and $\frac{d}{dt}x(t)$ and after put it in this following equation:
$$\frac{d^2}{dt^2}x(t)+ a_1(t)\frac{d}{dt}x(t) + a_2(t)x(t) = u(t)$$
And then find $a_1(t),a_2(t)$ and $u(t)$ such that is it true. Hence we obtain :
$$a(2+a_1(t)2t + a_2(t)(t^2-1))+b(2e^{t^2+t} + (2t +1)e^{t^2+t} + a_1(t)(2t+1)e^{t^2+t} + a_2(t)e^{t^2+t}) = u(t)$$ Since I don't want a particular equation but one which is true, I consider that the parenthesis of b is equal to zero, and so I found :
$$\frac{d^2}{dt^2}x(t) - (2t + 1)\frac{d}{dt}x(t) -2 x(t) = -a(6t^2-2t-3).$$
But I think it's not true, because there is always our constant a.

REPLY [1 votes]: Given two linearly independent solutions $\phi_1$ and $\phi_2$ there is always a corresponding homogenous differential equation
$$
W(\phi_1,\phi_2, x) = W(\phi_1,\phi_2) x'' - W'(\phi_1,\phi_2) x' + W(\phi_1',\phi_2') x =0,
$$
where $W$ denotes the Wronski determinant. More information can be found in Section 3.5 on my book on Ordinary Differential Equations.


TITLE: Using chain rule to find the derivative of $(4x^2-2)^3$
QUESTION [3 upvotes]: I just took a quiz and one of the problems was to get the derivative of $f(x) = (4x^2-2)^3$.
I used the chain rule and got $f'(x) = 24x(4x^2-2)^2$.
However, plugging it into the derivative function in a TI-89 returns
$f(x) = 96x(2x^2-1)^2$. Which is right? Me or the calculator?

REPLY [4 votes]: $$y' = 24x(4x^2-2)^2$$
$$y'=24x[2(2x^2-1)]^2$$
$$y'=24x[2^2(2x^2-1)^2]$$
$$y'=96x(2x^2-1)^2$$
both are right


TITLE: Helly theorem application
QUESTION [0 upvotes]: Let $X$ be a normed space, $dim(X)=d$, let $r>0, A$ and $\subset X$ . Show that if every $d+1$ points of $A$ are contained in a closed ball of radius $r$, then $A$ is contained in a closed ball of radius $r$.
After immerging $X$ in $R^d$,my idea is using Helly theorem, I have to show that the family of balls is a $d+1$ centered family, it seems simple but i can't. Then the sets are convex, their intersection is non empty, so I'm done i think!
Any suggestion? Thanks.

REPLY [1 votes]: For each $x\in X$ let $C_x$ be the closed ball of radius $r$ centred at $x$; note that $x\in C_y$ if and only if $\|x-y\|\le r$ if and only if $y\in C_x$.
If $x_1,\ldots,x_{d+1}\in A$, there is an $x\in X$ such that $\{x_1,\ldots,x_{d+1}\}\subseteq C_x$, and it follows from the observation in the first paragraph that $x\in\bigcap_{k=1}^{d+1}C_{x_k}\ne\varnothing$.
(You were already using the observation in the first paragraph to go from $\bigcap_{x\in A}C_x\ne\varnothing$ to the existence of an $x\in X$ such that $A\subseteq C_x$!)


TITLE: Ways to arrange $8$ people in $8$ chairs in a row if person $A$ can't sit next to $B$ or $C$.
QUESTION [3 upvotes]: In how many ways can I arrange $8$ persons in a row if person $A$
  can't sit next to person $B$ and person $C$.

I have made the case that $5$  persons ($A,B,C$ are not included) are already in place and I can have such a configuration in $5!$ ways. Now, $A$ can take place between each person and also before and after the first and last person, thus $A$ can be placed in $\dbinom {6}{1}$ and $B, C$ can take place in $5\cdot4$ ways.
So I have $5!\cdot 6 \cdot 5 \cdot 4 =1440$ ways to do that.
However I don't know if this result is correct since the solution is not available online (this problem comes from Mu Alpha Theta 1991).
Also what are other ways to look at the problem?

REPLY [2 votes]: Use the inclusion/exclusion principle:

Include the total number of permutations, which is $8!=40320$
Exclude the number of permutations containing $AB$ or $BA$, which is $2\cdot7!=10080$
Exclude the number of permutations containing $AC$ or $CA$, which is $2\cdot7!=10080$
Include the number of permutations containing $BAC$ or $CAB$, which is $2\cdot6!=1440$

Hence the number of legal permutations is:
$$40320-10080-10080+1440=21600$$


TITLE: Braiding matrix in Chern-Simons theories$.$
QUESTION [2 upvotes]: Consider a Chern-Simons system with gauge group $G$ and level $k$. Such a system can be used to model anyons, where the latter are identified with the integrable representations of $G$.
One of the most important properties of anyons is that they provide a non-trivial representation of the braiding group. This braiding is encoded in the so-called braiding matrix $B$. For the particular case of $G=\mathrm{SU}(2)$, ref.1 gives the expression for the $B$ matrix:
$$
B=q^{T^a_j\otimes T^a_j},\qquad q\equiv \mathrm e^{\frac{4\pi i}{k+2}}\tag{7.74}
$$
I have two questions:

First, one of notation. I don't really know what the author means by $T^a_j\otimes T^a_j$, and I'd be glad if someone could translate this into a more precise mathematical language. In particular, given two highest-weight representations of $G_k$, $\hat\mu,\hat\nu$, what is their brading $B_{\hat\mu\hat\nu}\in\mathbb C$?
Second, I'd like to know how the formula above is generalised to an arbitrary group $G$. I think the correct answer is that $q\to\exp\frac{4\pi i}{k+g}$, where $g$ is the dual Coxeter number of $G$, but I haven't been able to find this formula anywhere.

References.

Pachos, J.K. - Introduction To Topological Quantum Computation.

REPLY [2 votes]: The configuration space $\mathcal {M}$ of $N$ non-Abelian anyons on the $2-$ sphere $S^2$ consists of $N$ copies of $S^2$ excluding the collision points and in addition $N$ irreducible representations of a non-Abelian Lie group $G$ corresponding to the highest weight vectors $j_k$, $k= 1, .,.,.,N$.
The corresponding (physical) Hilbert space is given by:
$$H = \mathrm{inv}\left(\bigotimes_{k=1}^{N} H^{(j_k)}\right)$$
Where, $H^{(j_k)}$ is the Hilbert space of the $k-$th anyon carrying a representation $j_k$ of a non-Abelian Lie group $G$. ($j_k$ is the highest weight vector of the representation).
The physical Hilbert space includes only the scalar representations in the tensor product .
The braiding matrix is a non-Abelian holonomy $B$ of a flat connection (which will be described below) on the trivial bundle $\mathcal {P} = \mathcal {M} \otimes G$, corresponding to a closed path in the configuration space in which one anyon say the $m-$th one encircles a single other anyon say the $n-$th. (The exact trajectory is immaterial since the connection is flat). In this case the braiding matrix $B = q^t$ is given by: (Here I am writing explicitly the short hand notation of Pachos):
$$t = \sum_{a=1}^{\dim(G)} I_1 \otimes . . . \otimes T^a_{j_m}\otimes  . . . \otimes T^a_{j_n}\otimes  ... \otimes I_k$$
The sum in the braiding matrix is over an orthonormal basis of the Lie algebra $\mathfrak{g}$ of $G$. $I_k$ are unit matrices, so the braiding matrix acts only on the tensor product of the local Hilbert spaces corresponding to the anyons $m$ and $n$.
Please notice that due to fact that $t$ is invariant under $G$, the braiding works within the physical Hilbert space of invariants.
The braiding matrix can be obtained from a quantum mechanical model of the Anyon system. I am following here Oh and Verlinde . A system of particles in $2+1$ dimensions acquires anyon statistics when it is coupled to a Chern-Simons term. In the case of non-Abelian Anyons, the particles need to  have internal structure and to be coupled to a non-Abelian Chern Simons term. Oh works with the following theory of non-relativistic Anyons whose action (for $SU(2)$ anyons is given by:
$$ I = \int dt \sum_{k=1}^N \left( \frac{m_k}{2} \dot{q_k}^2 - Q_k^a (\theta_k, \phi_k)\left(A_i^a (q_k, t)\dot{ q_k }^i  - A_0^a(q_k, t)\right) +j_k\cos(\theta_k)\dot{\phi_k}\right )  + \quad k \int dt d^2x \epsilon^{\mu \nu \lambda} (A_{\mu }\partial_{\nu} A_{\lambda } + \frac{2}{3} A_{\mu }A_{\nu} A_{\lambda } )$$
This is equation (2) in the article with a slight change of notation. $j_k$ is the spin of the $k-$th anyon; the second term in the action is the non-Abelian Lorentz term interaction. The third term is the symplectic potential of the two-spheres consisting of the classical phase spaces of the spin degrees of freedom. $ Q_k^a$ are the classical non-Abelian charges, which due to the fact that the group is $SU(2)$ are given by the components of the angular momentum (The Poisson algebra of the sphere):
$$(Q_k^1, Q_k^2, Q_k^3) = j_k \left(\cos(\phi_k) \sin(\theta_k), \sin(\phi_k) \sin(\theta_k), \cos(\theta_k) \right)$$
The Gauss' law (equations of motion of $A_0^a$) takes the form:
$$k F_{12}^a = \sum_{k=1}^N Q_k^a \delta^2(x-x_k)$$
Except at the particle points the gauge field is flat, and the  flat connection solving the Gauss Law is given in the holomorphic gauge ($z = x^1+ix^2$)
$$A_{z}^a = \sum_{k=1}^N Q_k^a \frac{1}{z-z_k}$$
The charges $ Q_k^a $ quantize into the representation matrices $T_k^a$ of the $\mathfrak{su}(2)$ algebra.  The holonomy of the connection becomes:
$$B = Pe^{\frac{1}{2 \pi k}\int_{\Gamma} \sum_k dz^k \sum_{l\ne k} dz^l T_k^a \otimes T_l^a  \frac{1}{z_k-z_l}}$$
In the two-body case the exponent becomes self commuting over time and the path ordering becomes unnecessary and we get the final result:
$$B = e^{\frac{i}{2k}  T_1^a \otimes T_2^a}$$


TITLE: Convergence in probability of a function of random variable
QUESTION [0 upvotes]: Can somebody give me hint to solve the following problem:
Let $Y1,Y2,Y3, \ldots$ be a sequence of positive i.i.d. random variables with $0 < E[\ln Y_i]=\gamma<\infty$. Define the sequence ${X_n,n=1,2,3,...}$ as\begin{equation}
         X_n=(Y_1 Y_2 Y_3 \cdots Y_{n-1}Y_n)^{\frac{1}{n}}, \qquad \textrm{ for }n=1,2,3,\cdots.
      \end{equation}show that
$X_n \xrightarrow{p} e^{\gamma}$.
My attempt:
By continuous mapping theorem,  $X_n \xrightarrow{p} e^{\gamma} \implies Z_n = \ln X_n \xrightarrow{p} \gamma$. Now,
$P(|Z_n-\gamma|) \geq \epsilon ) \leq \frac{Var(Z_n)}{\epsilon^2}$, by Chebyshev's ineqality. The question is: How to bound the variance?

REPLY [0 votes]: The weak law of large numbers implies $\frac{1}{n} \sum_{i=1}^n \ln Y_i \overset{p}{\to} \gamma$. The continuous mapping theorem then implies $X_n = e^{\frac{1}{n} \sum_{i=1}^n \ln Y_i} \overset{p}{\to} e^\gamma$. The weak law of large numbers does not require that the variance of $\ln Y_i$ is finite.


TITLE: Show that if $A$ is a symmetric positive definite matrix, then $A^{-1}$ is a symmetric positive definite matrix
QUESTION [1 upvotes]: We know that matrix $A$ that fulfills those conditions has to be nonsingular, thus there exists an inverse matrix.

REPLY [0 votes]: For symmetry of the inverse consider,
$$ A^{-1}A = I = I^T = (AA^{-1})^T = (A^{-1})^T A^T = (A^{-1})^T A ,  $$
from this we can conclude that,
$$ A^{-1} = (A^{-1})^T \qquad \text{(The inverse is symmetric)}.$$

Recall that a matrix is positive definite if $\langle Av,v \rangle > 0 $ for all $v$ in our vector space. Since $A$ is nonsingular we know that it represents a linear automorphism on our vector space; which means for every vector $v$ there is a unique nonzero $b$ such that $Ab = v$. This allows us to write,
$$ \langle A^{-1} v,v \rangle = \langle A^{-1} A b, Ab \rangle = \langle b,Ab\rangle = \langle Ab,b\rangle > 0 \qquad \text{(The inverse is positive definite)}.$$


TITLE: Tricky algebra for minimization
QUESTION [1 upvotes]: Find the local minimum for $f(x, y) = 2x^4 + y^2 - 4xy + 5y,\:x,y \in \mathbb{R}$ find the local minimum.
Okay this seems easy enough, the necessary condition dictates that candidates are of the form $\nabla f(x_0,y_0)=(0,0)$ but $\nabla f(x,y)=(8x^3-4y,2y-4x+5)$, so we end up with $4x^3-4x+5=0$. How this one solve this? Wolfram gives an estimate of -1.38 but is it possible to direstly find the root?
Thanks

REPLY [2 votes]: The explicit expression for the unique real root of $4x^3 - 4x+5 = 0$ is not very elegant, so I do not think there is a nice way to obtain it, besides of just applying Cardano's formula


TITLE: How would I prove $10^x> 1$ for $x>0$ without using logarithms?
QUESTION [2 upvotes]: I was asked this question and got completely stumped. The person who asked this has instructed me specifically not to use logarithms. I know there is a more sophisticated way to explain exponentiation using limits of sequences (which would work here), but unfortunately limits are outside the reach in this particular context. So I was wondering, is there a simple way to explain why $0<x<1$ can only be expressed as negative powers of $10$ (or any other number greater than $1$, for that matter) using only high-school algebra? I suppose the proof doesn't have to be entirely rigorous, as long as it's sufficiently convincing.

REPLY [5 votes]: If $x$ is a positive rational number $p/q$ (where $p$ and $q$ have no common factors), then we can define $10^x$ as
$$
\left(\sqrt[q]{10}\right)^p=\underbrace{\sqrt[q]{10} \cdot \sqrt[q]{10} \cdot \sqrt[q]{10} \cdot \ldots \cdot \sqrt[q]{10}}_{\text{$p$ times}} \, .
$$
For any positive integer $q$, the $q$-th root of $10$ is greater than $1$. This means that $10^x$ is greater than $1$ because the product of $p$ numbers that are greater than $1$ is greater than $1$.
There are no hiccups caused when $x$ is irrational, because in that case $10^x$ is defined in such a way that it is strictly increasing.


TITLE: I want to study $\sqrt[n]{n}$ and its behavior.
QUESTION [5 upvotes]: As I was studying some limit problems, I came across
$$\sqrt[n]{n}$$
and astoundingly found out that the graph of this has a maximum when $n = e$.
I thought there is no way that this is not a famous fact and I am very interested in it. I looked up some words such as "nth roots" or "rational exponents" but I haven't found this fact right away.
Can someone guide me to a link or tell me at least what this expression goes by in order to do a little bit of researching ?

REPLY [6 votes]: Simply derive to find the maximum, but first note that
$$\sqrt[n]{n} =n^{1/n}=\exp(\log(n^{1/n}))$$
This should explain the connection with $e$. In more detail:
$$\frac{dn^{1/n}}{dn}=n^{1/n}\frac{1-\log n}{n^2}$$
So the derivative is only zero when $\log n = 1 \to \ n=e$.


text:
\section{Introduction}\label{introduction}

Consider the generic finite-sum optimization problem
\begin{equation}\label{eq: objective function}
    \min_{\ww \in \bbR^{d}} \bigg\{ f(\ww) \triangleq \frac{1}{m} \sum_{i = 1}^{m} f_{i}(\ww) \bigg\},
\end{equation}
in a centralized distributed computing environment comprised of one central driver machine communicating to $m$ worker machines, where each worker $i$ only has access to $f_i$.
A common application of this problem is where each worker $i$ has access to a portion of $n$ data points $\{\xx_1,\ldots,\xx_n\}$, indexed by a set $S_i\subseteq\{1,\ldots,n\}$, with
\begin{equation}\label{eq: objective function 2}
    f_i(\ww) = \frac{|S_i|}{n}\sum_{j\in S_i}\ell_j(\ww;\xx_j),
\end{equation}
where $\ell_i$ is a loss function corresponding to $\xx_i$ and parameterized by $\ww$.
For example, such settings are popular in industry in the form of federated learning when data is collected and processed locally, which increases computing resources and facilitates data privacy \cite{agarwal2018cpsgd}.
Another example is in big data regimes, where it is more practical, or even necessary, to partition and store large datasets on separate machines \cite{DiSCO}.
Distributing machine learning model parameters is also becoming a necessity as some highly successful models now contain billions of parameters, such as GPT-2 \cite{radford2019language, lee2014model}.

The need for distributed computing has motivated the development of many frameworks.
For example, the popular machine learning packages PyTorch \cite{PyTorch} and Tensorflow \cite{TensorFlow} contain comprehensive functionality for distributed training of machine learning models.
Despite many benefits to distributed computing, there are significant computational bottlenecks, such as those introduced through bandwidth and latency \cite{shamir2014distributed, li2014communication, wangni2018gradient}.
Frequent transmission of data is expensive in terms of time and physical resources \cite{DiSCO}.
For example, even transferring data on a local machine can be the main contributor to energy consumption \cite{shalf}.

With the bottleneck of communication, there has recently been significant focus on developing communication-efficient distributed optimization algorithms.
This is particularly apparent in regards to popular first-order methods, such as stochastic gradient descent (SGD) \cite{haddadpour2019trading, ivkin2019communication, vogels2019powersgd, basu2019qsparse, teng2019leader, zheng2019communication}.
As first-order methods solely rely on gradient information, which can often be computed easily in parallel, they are usually straightforward to implement in a distributed setting.
However, their typical inherent nature of performing many computationally inexpensive iterations, which is suitable and desirable on a single machine, leads to significant data transmission costs and ineffective utilization of increased computing resources in a distributed computing environment \cite{GIANT}.

\subsection*{Related Work}
In contrast to first-order methods, second-order methods perform more computation per iteration and, as a result, often require far fewer iterations to achieve similar results.
In distributed settings, these properties directly translate to more efficient utilization of the increased computing resources and far fewer communications over the network.
Motivated by this potential, several distributed Newton-type algorithms have recently been developed, most notably DANE \cite{DANE}, DiSCO \cite{DiSCO}, InexactDANE and AIDE \cite{AIDE}, GIANT \cite{GIANT}, and DINGO \cite{crane2019dingo}.

While each of these second-order distributed methods have notable benefits, they all come with disadvantages that limit their applicability.
DiSCO and GIANT are simple to implement, as they involve sub-problems in the form of linear systems.
Whereas, the sub-problems of InexactDANE and AIDE involve non-linear optimization problems and their hyper-parameters are difficult and time consuming to tune.
DiSCO and GIANT rely on strong-convexity assumptions, and GIANT theoretically requires particular function form and data distribution over the network in \eqref{eq: objective function 2}.
In contrast, InexactDANE and AIDE are applicable to non-convex objectives.
DINGO’s motivation is to not require strong-convexity assumptions, i.e., it converges for invex problems \cite{mishra2008invexity}, and still be easy to use in practice, i.e., simple to tune hyper-parameters and linear-least squares sub-problems.
DINGO achieves this by optimizing the norm of the gradient as a surrogate function.
Thus, it may converge to a local maximum or saddle point in non-invex problems.
Moreover, the theoretical analysis of DINGO is limited to exact update.

\input{tables/table1.tex}

\subsection*{Contributions}
We present a novel communication-efficient distributed second-order optimization algorithm that combines many of the above-mentioned desirable properties.
Our algorithm is named DINO, for ``\textbf{DI}stributed \textbf{N}ewton-type \textbf{O}ptimization method".
Our method is inspired by the novel approach of DINGO, which allowed it to circumvent various theoretical and practical issues of other methods.
However, unlike DINGO, we minimize \eqref{eq: objective function} directly and our analysis involves less assumptions and is under inexact update; see Tables \ref{table: 1} and \ref{table: 2} for high-level algorithm properties.

A summary of our contributions is as follows.

\begin{enumerate}
    \item The analysis of DINO is simple, intuitive, requires very minimal assumptions and can be applied to arbitrary non-convex functions.
    Namely, by requiring only Lipschitz continuous gradients $\grad f_i$, we show global sub-linear convergence for general non-convex \eqref{eq: objective function}.
    Recall that additional assumptions are typically required for the analysis of second-order methods.
    Such common assumptions include strong convexity, e.g., in \cite{roosta2019sub}, and Lipschitz continuous Hessian, e.g., in \cite{xu2017newton}, which are both required for GIANT.
    Although the theory of DINGO does not require these, it still assumes additional unconventional properties of the Hessian and, in addition, is restricted to invex problems, as a strict sub-class of general non-convex models.
    Furthermore, in our analysis, we don't assume specific function form or data distribution for applications of the form \eqref{eq: objective function 2}. For example, this is in contrast to GIANT, which is restricted to loss functions involving linear predictor models and specific data distributions.

    \item DINO is practically parameter free, in that it will converge regardless of the selected hyper-parameters.
    This is in sharp contrast to many first-order methods.
    The hyper-parameters of InexactDANE and AIDE require meticulous fine-tuning and these are sensitive to the given application.
    DINO is simple to tune and performs well across a variety of problems without modification of the hyper-parameters.

    \item The sub-problems of DINO are simple.
    Like DINGO, the sub-problems of our method are simple linear least-squares problems for which efficient and robust direct and iterative solvers exists.
    In contrast, non-linear optimization sub-problems, such as those arising in InexactDANE and AIDE, can be difficult to solve and often involve additional hard to tune hyper-parameters.
\end{enumerate}

\subsection*{Notation and Definitions}

Throughout the paper, vectors and matrices are denoted by bold lower-case and bold upper-case letters, respectively, e.g., $ \vv $ and $ \VV $.
We use regular lower-case and upper-case letters to denote scalar constants, e.g., $ d $  or $ L $.
The common \textit{Euclidean inner product} is denoted by $\langle \xx,\yy \rangle = \xx^T\yy$ for $\xx,\yy\in\bbR^d$.
Given a vector $\vv$ and matrix $\AA$, we denote their vector $\ell_2$ norm and matrix \textit{spectral} norm as
$\|\vv\|$ and $\|\AA\|$, respectively.
The \textit{Moore--Penrose inverse} of $\AA$ is denoted by $\AA^\dagger$.
We let $\ww_t\in\mathbb{R}^{d}$ denote the point at iteration $t$.
For notational convenience, we denote
$\bgg_{t,i} \defeq \grad f_i(\ww_t)$,
$\bgg_{t} \defeq \grad f(\ww_t)$,
$\HH_{t,i} \defeq \grad^2 f_i(\ww_t)$ and
$\HH_{t} \defeq \grad^2 f(\ww_t)$.
We also let
\begin{align}
\label{eq: H tilde and g tilde}
    \tilde{\HH}_{t,i} \defeq \begin{bmatrix} \HH_{t,i} \\ \phi\eye \end{bmatrix} \in\bbR^{2d\times d}
    \quad\text{and}\quad
    \tilde{\bgg}_t \defeq \begin{pmatrix} \bgg_t \\ \zero \end{pmatrix} \in\bbR^{2d},
\end{align}
where $\phi>0$, $\eye$ is the identity matrix, and $\zero$ is the zero vector.
We say that a \textit{communication round} is performed when the driver uses a \textit{broadcast} or \textit{reduce} operation to send or receive information to or from the workers in parallel, respectively.
For example, computing the gradient $\bgg_t$ requires two communication rounds, i.e., the driver broadcasts $\ww_t$ and then, using a reduce operation, receives $\bgg_{t,i}$ from all workers to then form $\bgg_t=\sum_{i=1}^{m}\bgg_{t,i}/m$.