TITLE: Gradient fields with holes and the fundamental theorem of line integrals
QUESTION [0 upvotes]: I'm learning vector calculus for the GRE, so this is my first time encountering these concepts. To my knowledge, a gradient field $\mathbf{F}(x,y) : D\to \mathbb{R}^2$ is one where there exists a scalar function $f(x,y) : D\to \mathbb{R}$ such that $$ \mathbf{F}=\nabla f $$
Here, I'm not specifying $D$ to be simply-connected, or even open. I believe this is a valid definition for any subset $D\subset \mathbb{R}^2$.
The fundamental theorem for line integral states that if $\mathbf{F}$ is a gradient field, i.e. $\mathbf{F}=\nabla f$ for some $f$, then along any path $C$ given by the parameterization $\mathbf{r}(t)$ for $a\leq t \leq b$
$$ \int_C \mathbf{F}\cdot d\mathbf{r}= f(\mathbf{r}(b))- f(\mathbf{r}(a)) $$
This might be a dumb question, but what if the domain has holes?
For example, take the scalar function $$f(x,y) = \frac{xy}{x^2+y^2}$$ then the corresponding gradient field is $\mathbf{F}(x,y) = \left( \frac{y(y^2-x^2)}{(x^2+y^2)^2}, \frac{x(x^2-y^2)}{(x^2+y^2)^2} \right)$.
I tried to take the line integral over the upper half circle, and the lower half circle, and it turns out they are both zero. Could I have applied the fundamental theorem of line integrals to this vector field $\mathbf{F}$?

REPLY [0 votes]: No, unfortunately you cannot apply FTLI if the gradient field has holes. I believe the (almost) gradient field
$$\vec{F} (x, y) = \left(\frac{-y}{x^2 + y^2}, \frac{x}{x^2 + y^2}\right)$$
which is (almost) the gradient of $f = \arctan(y/x)$ (except that $f$ is not defined at $(0, 0)$). It has the property that
$$\int_C \vec{F} \cdot \vec{dr} = 2 \pi$$
for any closed curve $C$ which surrounds the origin. What you can do for such problematic vector fields, however, is to notice that $\vec{F}$ is a gradient field away from its discontinuities, so you can always evaluate the above integral by deforming $C$ into any nice closed loop you like (and here, a particularly nice one is the unit circle). In other words,
$$\int_C \vec{F} \cdot \vec{dr} = \int_{C'} \vec{F} \cdot \vec{dr}$$
for any $C'$ also containing the origin (which is the only problematic point) and preserving orientation. The reason that such a deformation is possible is due to Stokes' Theorem, which notes that
$$\int_{\partial A} \vec{F} \cdot \vec{dr} = \iint_{A} (\vec{\nabla} \times \vec{F}) \cdot \vec{dA}$$
for any $A$, as long as the function is $\mathcal{C}^2$ over $A$. Choosing $A$ to be $C \setminus C'$, we can see that
$$\int_{\partial A} \vec{F} \cdot \vec{dr} = \int_C \vec{F} \cdot \vec{dr} - \int_{C'} \vec{F} \cdot \vec{dr} = \iint_{A} (\vec{\nabla} \times \vec{F}) \cdot \vec{dA} = 0$$


TITLE: What's the reason behind $e^{tx} \leq \frac{b-x}{b-a}e^{ta}+\frac{x-a}{b-a}e^{tb}$?
QUESTION [0 upvotes]: $e^{tx}$ is a convex function of $x$
Then, $\forall x\in [a,b]$
$e^{tx} \leq \frac{b-x}{b-a}e^{ta}+\frac{x-a}{b-a}e^{tb}$ holds.
Which is not same as convex definition $f(tx_1+(1-t)x_2)\leq tf(x_1)+(1-t)f(x_2)$.
An explanation of my inequality would be appreciated. Thank you very much in advance.

REPLY [1 votes]: You are using the letter $t$ twice for two different things. Instead use $$f(\lambda x_1 + (1-\lambda)x_2) \le \lambda f(x_1) + (1-\lambda) f(x_2).$$
Let $x_1 = a$, $x_2 = b$, and $\lambda = \dfrac{b-x}{b-a}$.

REPLY [1 votes]: Note that for a convex function
$$f(\lambda x + (1-\lambda) y)\le \lambda f(x) + (1-\lambda) f(y) $$
and in this case

$x=at$
$y=bt$
$\lambda= \frac{b-x}{b-a}$


TITLE: Silly optimization question
QUESTION [0 upvotes]: If I have a function i have to optimize subject to one constraint, are all feasible points automatically regular points since theres only one constraint?

REPLY [1 votes]: No. Given $m$ constraints $g_1,g_2,\ldots,g_m:\mathbb R^n\to\mathbb R$, a point $x\in\mathbb R^n$ is called regular if the set of vectors $\{\nabla g_1(x),\nabla g_2(x),\ldots,\nabla g_m(x)\}$ is linearly independent. If there is only one constraint, the set is a singleton $\{\nabla g_1(x)\}$, but it may still not be linearly independent if $\nabla g_1(x)=0$.


text:
\section{Proofs of Section~\ref{sec:appli}}
\label{proof:appli}

The appendix contains the proofs of the results stated in Section~\ref{sec:appli}, regarding the application of the proposed analysis to the case of one-dimensional and two-dimensional Fourier-Haar setting.

\subsection{Proof of Corollary \ref{corol:mri_iso_lambda}}
\label{proof:mri_setup_iso}

Let $A_0 = \mathcal{F}H^* = \replacemath{(a_1 | a_2 | \hdots |a_n )^*}{(d_1 | d_2 | \hdots |d_n )^*} \in \Cbb^{n \times n}$ with $n = 2^{J+1}$ be the Fourier-Haar transform and consider wavelet and frequency subbands $(\Omega_j)_{0 \leq j \leq J}$ and $(W_j)_{0 \leq j \leq J}$ as illustrated in Section~\ref{sec:applications_mri_iso}.

Recalling the local coherence estimate \eqref{eq:localcoherenceFH} from \cite[Lemma 1]{adcock2016note}, one has for $k \in \{1,\hdots , n \}$
\begin{align*}
\| \replacemath{a}{d}_{k,{S}} \|_2^2 = \sum_{j=0}^J \| P_S P_{\Omega_{j}} \replacemath{a}{d}_{k} \|_2^2 \leq \sum_{j=0}^J {s}_j \|  P_{\Omega_{j}} \replacemath{a}{d}_{k} \|_\infty^2 \leq C \cdot 2^{-j(k)} \sum_{j=0}^J {s}_j  2^{-|j(k)-j|},
\end{align*}
where $j(k)$ is the frequency level corresponding to index $k$ and where $C>0$ is a universal constant. Consequently, an estimate for $\Lambda({S},\pi)$ is
$$
\Lambda({S},\pi) := \max_{1\leq k \leq n} \frac{C \cdot 2^{-j(k)} \sum_{j=0}^J  {s}_j  2^{-|j(k)-j|}}{ \pi_k }.
$$
Recalling Lemma~\ref{lem:max_over_simplex}, the probability \replace{}{distribution} $\pi^\Lambda$ minimizing the previous bound is such that for all $k \in \{1 ,\hdots , n \}$
\begin{align*}
\pi_k^\Lambda = \frac{2^{-j(k)} \sum_{j=0}^J  {s}_j  2^{-|j(k)-j|}}{ \sum_{p=1}^n 2^{-j(p)}   \sum_{j=0}^J  {s}_j  2^{-|j(p)-j|} }.
\end{align*}
Since the size of the frequency subbands is $|W_j| = 2^{\max(j,1)}$, one can rewrite,
for all $k \in \{1 ,\hdots , n \}$
\begin{align*}
\pi_k^\Lambda &= \frac{2^{-j(k)} \sum_{j=0}^J  {s}_j  2^{-|j(k)-j|}}{ \sum_{j'=0}^J  2^{\max(j',1)-j'}  \sum_{j=0}^J  {s}_j   2^{-|j'-j|} } .
\end{align*}
Therefore, since $2^{j} \leq 2^{\max(j,1)} \leq 2^{j+1}$, we have
\begin{align*}
\Lambda({S},\pi^\Lambda)
= \sum_{j'= 0}^J 2^{\max(j',1)-j'}\sum_{j = 0}^J s_j 2^{-|j'-j|}
= D \cdot
\sum_{j=0}^J  \left( s_j + \sum_{\substack{j'=0\\ {j' \neq j}}}^J  {s}_{j'}  2^{-|j-j'|} \right),
\end{align*}
with $1 \leq D \leq 2$.
With such a choice of probability \replace{}{distribution} $\pi^\Lambda$, an estimate for $\Gamma$ can be derived as follows:
\begin{align*}
\Gamma(\pi^\Lambda)
&:= \max_{1\leq k \leq n} \frac{{C\, \cdot \,}2^{-j(k)}}{\pi^{\replacemath{}{\Lambda}}_k}
= \max_{1\leq k \leq n}  \frac{{C \,\cdot \,}2^{-j(k)} \Lambda(S,\pi^\Lambda) }{ 2^{-j(k)} \sum_{j'=0}^J  {s}_{j'}  2^{-|j(k)-j'|}   }
= \frac{{C \,\cdot \,}\Lambda(S,\pi^\Lambda)}{\displaystyle\min_{1\leq k \leq n} \sum_{j'=0}^J  {s}_{j'}  2^{-|j(k)-j'|} } ,
\end{align*}
where we used that $\|\replacemath{a}{d}_k\|_\infty^2 \leq C \cdot 2^{-j(k)}$ thanks to \eqref{eq:localcoherenceFH}. Therefore Condition \eqref{cond:killthethetalog} is satisfied if
$$
\min_{1\leq k \leq n} s_{j(k)}  + \sum_{j'\neq j(k)}  {s}_{j'}  2^{-|j(k)-j'|} \gtrsim \ln(3n/\varepsilon),
$$
which, in turn, is equivalent to
$$
\min_{0\leq j \leq J} s_{j}  + \sum_{j'\neq j}  {s}_{j'}  2^{-|j-j'|} \gtrsim \ln(3n/\varepsilon).
$$
Theorem \ref{thm:killthetalog} can be now applied, ensuring stable and robust recovery with probability $1-\varepsilon$ with a required number of measurements

\begin{align*}
m& \gtrsim   \sum_{j=0}^J  \left( s_j + \sum_{j'=0\atop j' \neq j}^J  {s}_j'  2^{-|j-j'|} \right) \cdot  \ln({3}n/\varepsilon).
\end{align*}
This concludes the proof of the corollary.

\subsection{Proof of Corollary \ref{corol:linesHaarMRI}}
\label{proof:corollinesHaarMRI}

The proof of Corollary~\ref{corol:linesHaarMRI} relies on the estimate of $\Theta(S,\pi)$ and on the choice of the corresponding optimal measure $\pi^\Theta$ on the space of vertical lines. With a slight abuse of notation, here $S$ can be interpreted as a subset of $\{1,\ldots,\sqrt{n}\}^2$ or as a subset of $\{1,\ldots,n\}$, depending on whether vectorization is used or not. In order to estimate $\Theta(S,\pi)$, we consider the term
$$
\|D_k^* D_{k,S}\|_{\infty \to \infty}
=
\max_{1 \leq i \leq n} \|e_i^* D_k^* D_{k,S}\|_1.
$$
Recalling that $D_{k} = \phi_{k,:} \otimes \phi$ and that $\phi$ is an isometry, we obtain
\begin{align*}
D_k^*D_{k,S}
= (\phi_{k,:}\otimes \phi)^*(\phi_{k,:}\otimes \phi)P_S^*
= ((\phi_{k,:})^* \phi_{k,:} \otimes \phi^* \phi)P_S^*
= ((\phi_{k,:})^* \phi_{k,:} \otimes I)P_S^*.
\end{align*}
Let us explicitly write
$$
(\phi_{k,:})^* \phi_{k,:} \otimes I
=
\begin{pmatrix}
\overline{\phi_{k,1}} \phi_{k,1} I & \cdots & \overline{\phi_{k,1}} \phi_{k,\sqrt{n}} I\\
\vdots & \ddots & \vdots \\
\overline{\phi_{k,\sqrt{n}}} \phi_{k,1} I & \cdots & \overline{\phi_{k,\sqrt{n}}} \phi_{k,\sqrt{n}} I
\end{pmatrix}.
$$
Then, we have
\begin{align*}
\max_{1 \leq i \leq n} \|e_i^* D_k^* D_{k,S}\|_1
& = \max_{1 \leq q \leq \sqrt{n}} \max_{1 \leq t \leq \sqrt{n}} \|e_t^* \begin{pmatrix}\overline{\phi_{k,q}} \phi_{k,1} I | \cdots | \overline{\phi_{k,q}} \phi_{k,\sqrt{n}} I\end{pmatrix}P_S^*\|_1\\
& = \max_{1 \leq q \leq \sqrt{n}} |\phi_{k,q}|\max_{1 \leq t \leq \sqrt{n}} \|e_t^* \begin{pmatrix} \phi_{k,1} I | \cdots |  \phi_{k,\sqrt{n}} I\end{pmatrix}P_S^*\|_1.
\end{align*}
The local coherence bound \eqref{eq:localcoherenceFH} yields $\displaystyle\max_{1 \leq q \leq \sqrt{n}} |\phi_{k,q}| \lesssim 2^{-j(k)/2}$. We estimate
\begin{align*}
\max_{1 \leq t \leq \sqrt{n}} \|e_t^* \begin{pmatrix} \phi_{k,1} I | \cdots |  \phi_{k,\sqrt{n}} I\end{pmatrix}P_S^*\|_1
& = \max_{1 \leq t \leq \sqrt{n}}  \left\|\begin{pmatrix} \phi_{k,1} (P_{S \cap C_1})_{t,:} | \cdots |  \phi_{k,\sqrt{n}} (P_{S \cap C_{\sqrt{n}}})_{t,:}\end{pmatrix}\right\|_1\\
& = \max_{1 \leq t \leq \sqrt{n}}  \sum_{q = 1}^{\sqrt{n}}|\phi_{k,q}|\left\|(P_{S \cap C_q})_{t,:} \right\|_1,
\end{align*}
where $C_q = \{1,\ldots,\sqrt{n}\}\times \{q\}$ is the $q$-th vertical line of $\{1,\ldots,n\}^2$. Now, we observe that
$$
\left\|(P_{S \cap C_q})_{t,:} \right\|_1
= \mathbbm{1}_{S \cap C_q}(t) :=
\begin{cases}
1 & \text{if } t \in S \cap C_q\\
0 & \text{otherwise}.
\end{cases}
$$
Finally, using the above relation, the decomposition of $\{1,\ldots,n\}^2$ into subbands $(\Omega_{\ell,j})_{0\leq \ell,j \leq J}$, and resorting again to \eqref{eq:localcoherenceFH}, we see that
\begin{align*}
\max_{1 \leq t \leq \sqrt{n}}  \sum_{q = 1}^{\sqrt{n}}|\phi_{k,q}|\left\|(P_{S \cap C_q})_{t,:} \right\|_1
& = \max_{1 \leq t \leq \sqrt{n}}  \sum_{q = 1}^{\sqrt{n}}|\phi_{k,q}|\mathbbm{1}_{S \cap C_q}(t)
 = \max_{0 \leq \ell \leq J} \max_{t \in \Omega_\ell}
\sum_{j = 0}^J \sum_{q \in \Omega_j} |\phi_{k,q}|\mathbbm{1}_{S \cap C_q}(t)\\
& \leq \max_{0 \leq \ell \leq J} \max_{t \in \Omega_\ell}
\sum_{j = 0}^J \max_{q \in \Omega_j} |\phi_{k,q}| \sum_{q \in \Omega_j} \mathbbm{1}_{S \cap C_q}(t)\\
& = \max_{0 \leq \ell \leq J} \max_{t \in \Omega_\ell}
\sum_{j = 0}^J \max_{q \in \Omega_j} |\phi_{k,q}| |S \cap \Omega_{\ell,j} \cap R_t|\\

& \lesssim \sum_{j = 0}^J 2^{-j(k)/2} 2^{-|j(k)-j|/2} s_j^r.
\end{align*}
This leads to the desired estimate of $\Theta(S,\pi)$. Using Lemma~\ref{lem:max_over_simplex} we can then derive the corresponding optimal measure $\pi^\Theta$ and conclude the proof.

\subsection{Proof of Corollary \ref{corol:linesHaarMRI_lambda}}
\label{proof:corollinesHaarMRI_lambda}

{We divide the proof of Corollary~\ref{corol:linesHaarMRI_lambda} into two steps. First, we find the optimal sampling measure $\pi^\Lambda$ that minimizes $\Lambda(S,\pi)$ and compute the corresponding $\Lambda(S,\pi^\Lambda)$. In the second step, we estimate $\Gamma(\pi^\Lambda)$ and derive the extra condition on the structured sparsity of the signal.

\paragraph{Step 1: Estimate of $\Lambda$ and derivation of $\pi^\Lambda$}

As in the previous section, here $S$ can be interpreted as a subset of $\{1,\ldots,\sqrt{n}\}^2$ or as a subset of $\{1,\ldots,n\}$, depending on whether vectorization is used or not.  Let us fix a frequency $k \in W_j$. Our first goal is to estimate the quantity $\|D_{k,S}^* D_{k,S}\|_{2 \to 2}$. This will lead us to the optimal choice of $\pi = \pi^{\Lambda}$.

First, we observe that $\|D_{k,S}^* D_{k,S}\|_{2 \to 2} = \|D_{k,S}\|_{2 \to 2}^2$. Now, let $v \in \mathbb{C}^n$ and $V \in \Cbb^{\sqrt{n} \times \sqrt{n}}$ be such that $v = \vect (V)$ (recall that the vectorization operator $\vect(\cdot)$ stacks the columns of a matrix on top of each other). Taking into account the structure of $D_{k,S}$ and $v$, and recalling that $\phi$ is an isometry,  we have
\begin{align*}
\|D_{k,S} v \|_{2}^2
& = \Bigg\|\sum_{i = 1}^{\sqrt{n}}\phi_{k,i} \phi (V_S)_{:,i} \Bigg\|_2^2
= \Bigg\|\phi \sum_{i = 1}^{\sqrt{n}}\phi_{k,i} (V_S)_{:,i} \Bigg\|_2^2
= \Bigg\|\sum_{i = 1}^{\sqrt{n}}\phi_{k,i} (V_S)_{:,i} \Bigg\|_2^2
= \sum_{q = 1}^{\sqrt{n}} \Bigg| \sum_{i = 1}^{\sqrt{n}}\phi_{k,i} (V_S)_{q,i}\Bigg|^2.
\end{align*}

Taking advantage of the decomposition of the wavelet multi-index space into tensor product subbands $(\Omega_{\ell,j})_{0 \leq \ell, j \leq J}$ and recalling \eqref{eq:localcoherenceFH}, we extend the previous chain of equalities as follows:
\begin{align*}
\|D_{k,S}v\|_2^2
& = \sum_{\ell = 0}^J \sum_{q \in \Omega_\ell} \Bigg| \sum_{j = 0}^{J} \sum_{i \in \Omega_{j}} \phi_{k,i} (V_S)_{q,i} \Bigg|^2
 \leq \sum_{\ell= 0}^J \sum_{q \in \Omega_\ell} \Bigg( \sum_{j = 0}^{J} \max_{i \in \Omega_{j}}|\phi_{k,i}|\sum_{i \in \Omega_{j}}  |(V_S)_{q,i}| \Bigg)^2\\
& = \sum_{\ell= 0}^J \sum_{q \in \Omega_\ell} \Bigg( \sum_{j = 0}^{J} \sqrt{\mu_{j(k),j}} \|V_{S\cap\Omega_{\ell,j}\cap R_q}\|_1 \Bigg)^2,
\end{align*}
where $j(k)$ is such that $k \in W_{j(k)}$ and $\mu_{\ell,j}$ is the local coherence of the Fourier-Haar transform defined in \eqref{eq:localcoherenceFH}. Using the Cauchy-Schwarz inequality, rearranging the summation, and recalling Definition~\ref{def:sparsity_in_levels_2D}, we see that
\begin{align*}
\|D_{k,S}v\|_2^2
& \leq
\sum_{\ell= 0}^J \sum_{q \in \Omega_\ell} \Bigg( \sum_{j = 0}^{J} \sqrt{\mu_{j(k),j}} \sqrt{s_{j}^r} \|V_{S\cap\Omega_{\ell,j}\cap R_q}\|_2 \Bigg)^2
 \leq
J  \sum_{\ell= 0}^J \sum_{q \in \Omega_\ell}  \sum_{j = 0}^{J} \mu_{j(k),j} s_{j}^r \|V_{S\cap\Omega_{\ell,j}\cap R_q}\|_2^2 \\
& =
J   \Bigg(\sum_{j = 0}^{J} \mu_{j(k),j} s_{j}^r \Bigg)\sum_{j = 0}^{J}\sum_{\ell= 0}^J \sum_{q \in \Omega_\ell}\|V_{S\cap\Omega_{\ell,j}\cap R_q}\|_2^2
 =
J \Bigg(\sum_{\ell = 0}^{J} \mu_{j(k),j} s_{j}^r \Bigg) \|v\|_2^2.
\end{align*}
Combining the above relations an using again \eqref{eq:localcoherenceFH} yields
$$
\|D_{k,S}^* D_{k,S}\|_{2 \to 2}
\leq J \sum_{j = 0}^{J} \mu_{j(k),j} s_{j}^r
\leq C \cdot J 2^{-j(k)} \sum_{j = 0}^{J} 2^{-|j(k)-j|} s_{j}^r,
$$
where $C>0$ is the universal constant in \eqref{eq:localcoherenceFH}. Using Lemma~\ref{lem:max_over_simplex} and recalling that $|W_j| = 2^{\max(1,j)}$, the optimal probability $\pi^\Lambda$ is, for all $k = 1,\ldots,\sqrt{n}$,
$$
\pi^\Lambda_{k}
= \frac{ 2^{-j(k)} \sum_{j = 0}^{J} 2^{-|j(k)-j|} s_{j}^r}{\sum_{t = 0}^{\sqrt{n}} 2^{-j(t)} \sum_{j = 0}^{J} 2^{-|j(t)-j|} s_{j}^r}
= \frac{ 2^{-j(k)} \sum_{j = 0}^{J} 2^{-|j(k)-j|} s_{j}^r}{\sum_{\ell = 0}^J 2^{\max(1,\ell)-\ell} \sum_{j = 0}^{J} 2^{-|\ell-j|} s_{j}^r}.
$$
This leads to
\begin{align*}
\max_{0 \leq k \leq \sqrt{n}} \frac{\|D_{k,S}^* D_{k,S}\|_{2 \to 2}}{\pi_k^{\Lambda}}
\leq C J \cdot \sum_{\ell = 0}^J 2^{\max(1,\ell)-\ell} \sum_{j = 0}^{J} 2^{-|j-\ell|} s_{j}^r
=: \Lambda(S,\pi^{\Lambda}).
\end{align*}

\paragraph{Step 2: Estimate of $\Gamma$ and conclusion}

Employing \eqref{eq:localcoherenceFH} and recalling that $\phi$ is an isometry, we have
$$
\|D_k\|_{1 \to 2}^2
=
\max_{1 \leq i \leq \sqrt{n}} \max_{1 \leq q \leq \sqrt{n}} \|\phi_{k,i} \phi_{:,q}\|_2^2
=
\max_{1 \leq i \leq \sqrt{n}} \max_{1 \leq q \leq \sqrt{n}} |\phi_{k,i}|^2 \underbrace{\|\phi_{:,q}\|_2^2}_{=1}
\leq C \cdot 2^{-j(k)}.
$$
Therefore, we estimate
\begin{align*}
\max_{1 \leq k \leq \sqrt{n}} \frac{\|D_k\|_{1 \to 2}}{\pi_k^\Lambda}
& \leq
\max_{1 \leq k \leq \sqrt{n}}\frac{C \cdot 2^{-j(k)}}{
2^{-j(k)} \sum_{j = 0}^{J} 2^{-|j-j(k)|} s_{j}^r} \Big(\sum_{\ell = 0}^J 2^{\max(1,\ell)-\ell} \sum_{j = 0}^{J} 2^{-|j-\ell|} s_{j}^r\Big)\\
& = \frac{\Lambda(S,\pi^\Lambda)}{
\displaystyle J \cdot \min_{0 \leq \ell \leq J}\sum_{j = 0}^{J} 2^{-|j-\ell|} s_{j}^r}=: \Gamma(\pi^\Lambda).
\end{align*}
As a consequence, the condition \eqref{cond:killthethetalog}  of Theorem~\ref{thm:killthetalog} reads
$$
J \cdot \min_{0 \leq \ell \leq J}\sum_{j = 0}^{J} 2^{-|j-\ell|} s_{j}^r \gtrsim \ln(3n/\varepsilon)
$$
and the minimum sampling complexity is
$$
m \gtrsim \Lambda(S,\pi^{\Lambda})\ln(3n/\varepsilon),
$$
which, in turn,  is implied by
$$
m\gtrsim \Bigg(\sum_{j = 0}^J s_j^r + \sum_{\substack{\ell = 0\\ \ell \neq j}}^{J} 2^{-|\ell-j|} s_{\ell}^r \Bigg)\log_2(\sqrt{n})\ln(3n / \varepsilon).
$$
This concludes the proof.

config: arxiv


TITLE: Generalised Coordinates in 3D Rotation
QUESTION [3 upvotes]: If you have N particles on a surface of a rigid body and the rigid body is rotating about some axis, we say there are six generalised coordinates for the system (N particles on the surface) and set up the lagrangian.
The constraints we know are

The distance between any two particles is invariant
The angles between the line joining any particles is invariant as well
and that's it.

We also know a formula for finding the number of genralised coordinates
i.e difference between number of degrees of freedom (3N) and number of constraints (which is N(N-1)/2).
Clearly using this formula doesn't give 6 generalised coordinates.
Where's the mistake and how to count the number of generalised coordinates?
Note : Even I know the argument as to if you know 3 points on surface, you can determine the position of any other particle on the surface. But my question is about counting the generalised coordinates using the above formula.

REPLY [2 votes]: Your mistake is to assume that the number of constraints is $N(N-1)/2$. This number is only true for $N\leq 4$.
Let us label the particles by $1,2,\ldots,N$ and say that $\bar{ij}$ denotes the constraint between particles $i$ and $j$. For one particle there is no constraint. For two particles there is one constraint (see the diagrams bellow). If $N=3$ we have three constraints: $\bar{12},\bar{13},\bar{23}$. Add a fourth particle and we gain three others constraints: $\bar{14}$ and $\bar{24}$ fix the distance from particle $4$ to particles $1$ and $2$ and $\bar{34}$ which forbids the fourth particle to rotate about the axis joining $1$ and $2$. This fixes the distance from $4$ to $3$. This gives a total of six constraints. Finally consider adding one more particle. Now things get different. The new constraints $\bar{15},\bar{25}$ fix the distance to $1$ and $2$. The only freedom the sixth particle still have is to rotate about the line joining $1$ and $2$. Therefore just one more constraint, say $\bar{13}$, is enough to rigidly fix the sixth particle. The total number of constraints in this case is six.

As you can see in this construction, the first particle added zero constraints, the second one added one constraint, the third one added two constraints and the nth ($n\geq 4$) one added three constraints. The total number of constraints for $N\geq 5$ particles is therefore $1+2+3(N-3)=3(N-2)$. Hence there are $3N-3(N-2)=6$ degrees of freedom.


TITLE: What are the benefits or losses of learning real analysis through a constructivist approach instead of a standard apporach?
QUESTION [3 upvotes]: Recently I've found some courses on real analysis that use the constructivist approach and I got curious on some aspects:

What are the benefits of learning through this approach?
Is it ok to learn through a constructivist approach instead of a standard approach?
How different the teaching on these approaches would be?

Here I'm presuming a student who haven't taken real analysis
lectures.
I'm presuming that constructivist approaches to real analysis are not a standard practice in analysis courses but I'm not sure about that.

REPLY [3 votes]: The main benefit I can see (apart from possible personal preferences in favor of constructive mathematics) is that people who learn "classical" methods first can find it challenging to learn to work constructively later. So, if someone is planning to do constructive math later, learning it constructively from the outset might be a benefit. On the other hand, if one is planning to do classical mathematics later, it may make more sense to learn it classically in the first place.
Teaching constructive math has the same variations as teaching classical math - some professors will use a detailed lecture-style approach, while some will use an inquiry-based approach where the student discovers more on her own.  Books on constructive mathematics read basically the same as books on classical mathematics.


TITLE: Why is $A - A^T$ unimodular for any Seifert-matrix $A$ of some knot $K$?
QUESTION [3 upvotes]: I am studying Seifert matrices. Right now I am working with those matrices from a linear algebra perspective, but I will need to understand the knot theory behind it as well. I am using the fact that $A-A^T$ is unimodular for some Seifert-matrix $A$ and I would really appreciate any help on understanding why.
Here is some context:
Let $K$ be some knot in $S^3$, and let $F$ be some Seifert-Surface of $K$. Then as $F$ is orientable we can choose a bicollar $[-1,1]\times F$. The Seifert-Matrix of $K$ according to that Seifert-Surface then is the matrix representing the map
$$f:H_1(F)\times H_1(F)\rightarrow \mathbb{Z}$$
given by
$$f([x],[y])=lk(x,y^+)$$
where lk is the linking form and $y^+$ is the pushoff of $y\times\{0\}$ in the bicollar to $y\times\{1\}$. Now one probable needs to write down a basis (classification of surfaces) and do some calculations, but I am unsure on how to see that the generated matrix has the above property in general.
I am new to knot theory, but rather familiar with a lot of basic algebraic topology. Any help would be greatly appreciated!
Edit: I have already proven that any two generated Seifert-matrices are S-equivalent. Thus it would suffice to show that one generated matrix has the desired property (maybe one of the non-singular ones of minimal size? But that may be nonsense) and then that the property is preserved under S-equivalency. For congruency it is true obviously. I will look into right/left enlargements resp. reductions later. ( This has to be true , else the statement was false)

REPLY [3 votes]: Consider a genus $g$ oriented surface $S$, with $m$ punctures embedded in $S^3$:

We have a basis for $H_1(S)$ given by the $g$ blue cycles indicated, the $g$ red cycles and the $m$ green cycles.  The intersection form takes a pair of cycles to the number of intersections, counted with sign coming from the orientation of the ordered directions of the cycles, at the point they cross.
From the diagram we see that with respect to the given basis (red, blue green), the intersection form is represented by $Q$: the diagonal composition of $g$ matrices of the form: $$\left(\begin{array}{cc}0&1\\-1&0\end{array}\right),$$
and $m$ $0$'s.
If we quotient by the null space of the form, then we get a unimodular form $\beta\colon\mathbb{Z}^{2g}\times\mathbb{Z}^{2g}\to\mathbb{Z}$.  That is $\beta$ induces an isomorphism: $$\hat{\beta}\colon \mathbb{Z}^{2g}\stackrel{\tiny\sim}\to {\rm Hom}_\mathbb{Z}(\mathbb{Z}^{2g},\mathbb{Z})$$
A matrix $M$ representing $\beta$ (with respect to some basis) also represents the induced map $\hat{\beta}$ (with respect to the dual basis on ${\rm Hom}_\mathbb{Z}(\mathbb{Z}^{2g},\mathbb{Z}))$.
As $\hat{\beta}$ is an isomorphism, with respect to any basis, the matrix representing $\hat{\beta}$ has determinant $\pm 1$.  Thus $M$ has determinant $\pm1$.
It remains to show that $Q=A-A^T$, where $A$ is the Seifert matrix computed with respect to the red\green\blue basis.  Then they will represent the same form, and we know that any matrix representing this form has determinant $\pm1$.
Let $x_i,y_i$ represent the $i$'th red and blue cycles respectively. Thicken the surface $S$, so that $x_i^+,y_i^+$ are the cycles $x_i,y_i$ pushed to the outer surface of $S$.
Then lk$(y_i,x_i^+)-$lk$(x_i,y_i^+)=1$:

The cycles here are not linked about the intersection point.
On the other hand:

The cycles here are linked one degree higher than in the previous diagram, because of the additional link about the intersection point.
If $u,v\in H_1(S)$ do not intersect, then:
$\qquad\qquad\qquad$lk$(u,v^+)=\,$lk$(u,v)=\,$lk$(v,u)=\,$lk$(v,u^+)$.
Thus $A$ is some symmetric matrix plus the diagonal composition of $g$ copies of: $$\left(\begin{array}{cc}0&1\\0&0\end{array}\right),$$
and $m$ $0$'s.
We conclude $Q=A-A^T$ as required.


TITLE: Show that $a^{61} \equiv a\pmod{1001}$ for every $a \in \mathbb{N}$
QUESTION [7 upvotes]: I'm asked to show that $a^{61} \equiv a\pmod{1001}$ for every $a \in \mathbb{N}$. I've tried to tackle this using Fermat's Little Theorem and Euler's Theorem, but I can't even get started. My main problem seems to be the "for every $a \in \mathbb{N}$" part, because if it restricted $\gcd(a, 1001) = 1$ I would be able to factor out 1001 and try to show that it's factors divide $a^{61} - a$. I'm kinda lost here. Any help is appreciated.

REPLY [1 votes]: HINT.-$$\begin{cases}a^{61}=(a^7)^8\cdot a^5\equiv a^8\cdot a^5\equiv a^7\equiv a\mod7\\a^{61}=(a^{11})^5\cdot a^6\equiv a^ {11}\equiv a\mod 11\\a^{61}=(a^{13})^4\cdot a^9\equiv a^{13}\equiv a\mod13\end{cases}$$
Thus $$a^{61}-a=7m_1=11m_2=13m_3\Rightarrow?$$


TITLE: Prove that $S$ is countably infinite
QUESTION [2 upvotes]: Suppose we have the set $S\subset\mathbb{ N \times N}$ where $\mathbb N$ is the set of positive integers $\{1, 2,\ldots\}$ with the property: $S = \{\langle m, n \rangle\mid m \leq n\}$. Suppose $f\colon S \to N$ is defined as:
$$f(\langle m, n \rangle) = \frac{{n(n - 1)}}{2} + m.$$ Prove that $S$ is countably infinite.
Proof sketch: In order to prove $S$ is countably infinite I have to prove $f$ is a bijection, that is, it is both an injection and a surjection. However I don't even know how to get started on the injection part, say, suppose $f(\langle m_{1}, n_{1}\rangle)=f(\langle m_{2}, n_{2}\rangle)$ then $\langle m_{1}, n_{1} \rangle=\langle m_{2}, n_{2}\rangle$.
Hope someone could help me with this, thanks!

REPLY [2 votes]: To prove that $S$ is countably infinite is enough to prove that is infinite (since $S\subset \mathbb{N} \times \mathbb{N}$ and $\mathbb{N} \times \mathbb{N}$ is countable). Since $(1,n) \in S, \ \forall n \in \mathbb{N}$ you are done.


TITLE: A difficulty with Fourier sine transform
QUESTION [0 upvotes]: I'm trying to work through an exercise on Fourier sine transform. The function given is
$$ f(x) = \frac{\sin(\omega x)}{x^2 + 1}\quad \omega > 0 $$
with Fourier sine transform pair defined as
$$ f_s(x) = \sqrt{2}f(x),$$
$$\hat{F}_s(k) = \int_{0}^{\infty}f_s(x) \sin(kx)\mathrm{d}x.$$
I'm told I need to consider two cases: $\omega > k$ and $\omega < k$ and I'm not sure why, I think it is something to do with Jordan's lemma when performing the contour integration.

REPLY [1 votes]: You have
$$
\hat{F}_s(k)
= \int_{0}^{\infty}f_s(x) \sin(kx)\mathrm{d}x
= \int_{0}^{\infty} \sqrt{2} f(x) \sin(kx)\mathrm{d}x
= \sqrt{2} \int_{0}^{\infty} \frac{\sin(\omega x)}{x^2+1} \sin(kx)\mathrm{d}x
\\
= \sqrt{2} \frac{1}{2} \int_{-\infty}^{\infty} \frac{\sin(\omega x)}{x^2+1} \sin(kx)\mathrm{d}x
= \sqrt{2} \frac{1}{4} \int_{-\infty}^{\infty} \frac{\cos(\omega x-k x) - \cos(\omega x+k x)}{x^2+1} \mathrm{d}x
\\
= \operatorname{Re} \sqrt{2} \frac{1}{4} \int_{-\infty}^{\infty} \frac{e^{i(\omega-k)x} - e^{i(\omega+k)}}{x^2+1} \mathrm{d}x
$$
Now calculate
$$
I_\pm := \int_{-\infty}^{\infty} \frac{e^{i(\omega\pm k)x}}{x^2+1} \mathrm{d}x
$$
by a standard contour integration along $[-R,R]$ on the real axis and a semicircle. Be careful with whether the semicircle should be in the upper or lower half-plane to make the integral over it vanish when $R\to\infty.$ For that you will have to look at the sign of $\omega\pm k.$


TITLE: Quadratic algebras and Koszul algebras
QUESTION [4 upvotes]: Let $A$ be a quadratic algebra and $B$ the Ext-algebra of $A$.
In case $A$ is a Koszul algebra, we should have that the global dimension of $A$ plus one is equal to the Loewy length of $B$ (is there a reference for this?).
Namely we should have $gldim(A)= \sup \{ i \geq 0 | Ext_A^i(A_0,A_0) \neq 0 \} = LL(B)-1$, where LL stands for Loewy length and $A_0$ is the degree zero part of the graded algebra $A$.
Im not sure in general about the first equality here (it should at least hold for $A$ finite dimensional), but the second equality should be correct since $B$ is generated in degree 0 and 1.
Thus $gldim(A)+1=LL(B)$.

Question 1: Is $gldim(A)= \sup \{ i \geq 0 | Ext_A^i(A_0,A_0) \neq 0 \} $ true in general or under some restrictions? Is there a reference?
Question 2: Is a quadratic algebra Koszul iff $gldim(A)+1=LL(B)$ holds?

Maybe on needs to assume further restrictions for question 1, but I think in some form it will be true.
One should be able to apply this in two nice examples:
a) $A=K[x_1,...,x_n]$ the polynomial ring in $n$ variables. Here $B$ is the Grassmann algebra in $n$ variables which has Loewy length $n+1$ and this shows that $A$ has global dimension $n$.
b)$A=kQ$ the quiver algebra of an arbitrary quiver with finitely many points and at least one arrow (that may be infinite dimensional). Then $B$ is the algebra with the same quiver and radical square zero and thus Loewy length 2. Thus the formula would give here that $A$ has global dimension one and I think the proof of this is actually quite complicated without those tools.

REPLY [3 votes]: A useful reference for answering your questions at least partially is Theorem 1.7 (especially part (5) of it) in the notes  http://inmabb.criba.edu.ar/revuma/pdf/v48n2/v48n2a05.pdf .


TITLE: Derivation of formula for angle of rotation to eliminate xy term in rotated conic
QUESTION [0 upvotes]: Is there a derivation for the formula $ tan2θ = \frac{B}{A-C} $ relationship used to find an angle of rotation at which the coordinate axes for a conic containing an xy term can be rotated to eliminate the xy term? I only see sources that directly show the formula and say that it is derived by setting $ x'y' = 0 $ but I want to see the actual derivation.

REPLY [1 votes]: A useful way to proceed is to derive the equation of a conic in general position.

Consider a conic with eccentricity $e>0$ (no circles), semi-latus rectum $s$, focus $(f_x, f_y)$, and major radius direction vector $(\cos\theta,\sin\theta)$. The focus-directrix definition of the (non-circle) conic
$$\text{distance to focus} = \text{eccentricity}\cdot(\text{distance to directrix})
\tag0$$
tells us that the distance from the endpoints of the latus rectum (and thus also the focus) to the directrix is $s/e$. Therefore, we can write the equation of the directrix, whose normal vector is $(\cos\theta,\sin\theta)$, as
$$
(x-f_x)\cos\theta+(y-f_y)\sin\theta-\frac{s}{e} = 0
\tag1$$
Since $\sin^2\theta+\cos^2\theta=1$, the (signed) distance from $(x,y)$ to the directrix is the left-hand side of $(1)$. Substituting into the square of $(0)$ and lightly simplifying, we have this equation for a conic (that happens to work for circles):
$$(x-f_x)^2+(y-f_y)^2 \;=\; \left(\; (x-f_x)e\cos\theta+(y-f_y)e\sin\theta-s \;\right)^2
\tag{2}$$
Expanding $(2)$, gathering terms, and allowing for having multiplied-through by an arbitrary constant $k\neq 0$, gives us the representation $K(x,y)=0$, with polynomial $K$ given by
\begin{equation}
K(x,y) := k_{20}x^2+2k_{11}x y+k_{02}y^2+2k_{10}x+2k_{01}y+k_{00}
\end{equation}
whose coefficients are the following expressions in the conic's parameters (and $k$):
$$\begin{align}
k_{20} &:= \phantom{-}k (1 - e^2 \cos^2\theta)\\[0.25em]
k_{02} &:= \phantom{-}k (1 - e^2 \sin^2\theta)\\[0.25em]
k_{11} &:= -k e^2 \cos\theta\sin\theta \\[1em]
k_{10} &:= \phantom{-}k e s \cos\theta - k_{20}f_x - k_{11}f_y  \\[0.25em]
k_{01} &:= \phantom{-}k e s \sin\theta - k_{11}f_x - k_{02}f_y  \\[0.25em]
k_{00} &:= -k s^2 - k_{20}f_x^2 - k_{02}f_y^2 - 2 k_{11}f_x f_y - 2 k_{10}f_x - 2 k_{01}f_y
\end{align} \tag3$$
From here, we see that the $xy$ term vanishes when $e=0$ (the circle case we're ignoring) or when $\theta$ is a multiple of a right angle (ie, when the conic's axes are aligned with the coordinate axes). And we see that we can retrieve that angle via
$$\frac{2k_{11}}{k_{20}-k_{02}}=\frac{-e^2\cdot 2\sin\theta\cos\theta}{-e^2(\cos^2\theta-\sin^2\theta)}=\frac{\sin2\theta}{\cos2\theta}=\tan2\theta \tag4$$
This is the desired relation. It may help to use a form that avoids problematic zero denominators:
$$\sin2\theta : \cos2\theta \;=\; 2k_{11}:k_{20}-k_{02}\tag{4'}$$

Note that having the coefficients expressed in terms of the conic's parameters readily confirms another helpful fact. The discriminant of $K$ reduces to
$$k_{20}k_{02}-k_{11}^2=k^2(1-e^2) \tag5$$
so that the type of conic (ellipse, parabola, hyperbola) is "obviously" determined by the discriminant's sign (positive, zero, negative).
Of course, since $K$ encodes a conic, it must be possible to retrieve all parameters of that conic from the coefficients, solving the system $(3)$ for those parameters. (There are ambiguities. $K$ can't distinguish between the foci, for instance.) Doing so leads to some complicated formulas, as shown in, say, this answer, so deriving them can be tricky. Nevertheless, system $(3)$ provides some insight into the formulas and, as with $(4)$ and $(5)$, can make confirming them relatively straightforward.


TITLE: $2+3+5+9+8+15+11+21+14+27+17+\dots$
QUESTION [0 upvotes]: I need to find the sum of the series upto $2n+1$ term
$2+3+5+9+8+15+11+21+14+27+17+\dots$
so $2,5,8,11,14,17\dots$ is one AP and $3,9,15\dots$ is another AP
I just want to know From which AP I should take $n$ terms and $n+1$ terms to find the final sum?

REPLY [2 votes]: $(2n+1)$ is odd, so the last term in given series should be the term in the series $2,5,8,..$.
So you take:$(n+1)$ terms from $2,5,8,11,...$ and $n$ terms from $3,9,15,...$


TITLE: For a stopping time does $E[(\tau \wedge t)1_A]=E[(\tau \wedge s)1_A] $ for $s \le t $ and any $A \in \mathcal F_{\tau \wedge s }$?
QUESTION [3 upvotes]: I have the following question as stated in the title:

For a stopping time $\tau $ does $E[(\tau \wedge t)1_A]=E[(\tau \wedge s)1_A] $ for $s \le t $ and any $A \in \mathcal F_{\tau \wedge s }$?

Here $\mathcal F_{\tau \wedge s } $ is the $\sigma $-algebra of $\tau \wedge s $-past.

The context is that I'm trying to show that $(B^2_{\tau \wedge t } - \tau \wedge t,\mathcal F_{\tau \wedge t })$ is a martingale and the question is here is a second step in showing that $E[\tau \wedge t|\mathcal F_{\tau \wedge s} ]=\tau \wedge s$.
Thanks in advance!

REPLY [2 votes]: We have
\begin{alignat*}{2}
\mathbb{E}[(\tau \wedge t)\mathbf{1}_A] & = \mathbb{E}\Big[\mathbb{E}\left[(\tau \wedge t)\mathbf{1}_A\;|\;\mathcal F_{\tau \wedge s }\right]\Big]\quad\text{by the tower property}\\
& = \mathbb{E}\Big[\mathbb{E}\left[(\tau \wedge t)\;|\;\mathcal F_{\tau \wedge s }\right]\mathbf{1}_A\Big]\quad\text{by measurability}\\
& \neq \mathbb{E}\Big[\mathbb{E}\left[(\tau \wedge s)\;|\;\mathcal F_{\tau \wedge s }\right]\mathbf{1}_A\Big]\\
& = \mathbb{E}\left[(\tau \wedge s)\mathbf{1}_A\right],
\end{alignat*}
so answer seems no. Counterexample: $\tau=\infty$ almost surely.

If $B$ is a standard Brownian motion, then $\mathbb E\left[ B^2_{t}\right] = {t}$ and $\mathbb E\left[ B^2_{t}\;\;|\;\; \mathcal{F}_s\right] = B_s^2 + {t-s}$.
What you need to show seems
$$
\mathbb E\left[ B_{\tau\wedge t}^2 - {\tau\wedge t} \;\;|\;\; \mathcal{F}_{\tau\wedge s}\right] = B_{\tau\wedge s}^2 - {\tau\wedge s}
$$
for which you need $(B_t-B_s)\amalg\mathcal F_s$ and $(B_t-B_s)\sim B_{t-s}$.


TITLE: Ordering problem from combinatorics
QUESTION [0 upvotes]: So the question is as follows.
We will have an ordered parade of the flags of 15 countries through a street. In how
many ways can we order the flags in the parade if the flags of country X and Y cannot be next to each other.
I know this is a problem from ordered selection without repetiton but I cannot see how to tackle this problem.
Thank you in advance for the help.

REPLY [2 votes]: We can count the number of combinations taking into account all the possible sequences and removing those containing $XY$ and $YX$.

Total combinations: $15!$
Combinations with $XY$: this block can be placed in $14$ different spots (depending on where $X$ lies), and the rest of the
flags can be ordered in $13!$ ways, so $14*13! = 14!$. Similarly you can think to $XY$ as a single letter and so you can order the $14$ letters in $14!$ ways.
Combinations with $YX$: same as before, $14!$

So the possible combinations are $15!-2*14! = 14!*13$.
Different Solution
This nice result made me think to a different approach:
you can remove $Y$ and shuffle the remaining $14$ flags in $14!$ ways.
Now, where can you put $Y$ back in? You have $15$ spots but you can't place it next to $X$, so you need to remove 2 spots, so only $13$ are viable: $14!*13$.


TITLE: Showing existence in proof of Division Algorithm using induction
QUESTION [1 upvotes]: Division Algorithm: Let $a$, $b$ $\in \mathbb{Z}$ be any integers and $b \neq 0$. Then, $\exists$ unique integers $q$, $r$ such that
$a = bq + r$ and $0 \leq r < |b|$.
I am trying to show existence by induction on a, and I need assistance.
This is what I've done so far:
$a=1$: Suppose $a=1$. Then, we can write $1 = b\cdot 0 + 1$. This would be the case when $b>a$, so $0\leq r<|b|$ is satisfied.
Assume true for $a=k$: Suppose that for $k \in \mathbb{Z}$, $b \neq 0$, $\exists q_{k}$, $r_{k}$ s.t. $k = b\cdot q_{k}+r_{k}$ where $0\leq r_{k} < |b|$.
Show true for $a=k+1$: Supposing the case for $a=k$:
$k=b\cdot q_{k}+r_{k}$, where $0\leq r_{k} < |b|$.
Then, $k+1=b\cdot q_{k}+r_{k}+1 \to$
$k+1 = b\cdot q_{k}+(r_{k}+1)$.
If $r_{k}+1 < |b|$, then let $q_{k}=q_{k+1}$, $r_{k+1}=r_{k}+1$, and we're done.
If $r_{k}+1 \geq |b|$, then let $q_{k+1}=q_{k}+1$, until $r_{k+1}<|b|$, and we achieve our desired result.
I was wondering if this proof was correct, and if not, what do I need to do to fix it? Also, do I also need to prove that I can do this:
"If $r_{k}+1 \geq |b|$, then let $q_{k+1}=q_{k}+1$, until $r_{k+1}<|b|$, and we achieve our desired result."
and if so, how do I do that?
Thank you.

REPLY [1 votes]: You can improve your proof by noting that since $r_k$ is at most $|b| - 1$, that $r_k + 1$ is at most $|b|$ (remember, these are integers we're dealing with, which go up "in increments of $1$").
Thus your second case is just:
$r_k + 1 = |b|$, in which case:
$k+1 = b\cdot q_k + |b|$.
If $b < 0$ take $q_{k+1} = q_k - 1$, if $b > 0$ take $q_{k+1} = q_k + 1$, which shows existence.
This highlights a flaw in your approach: suppose $b = -5$, and $k = 24$.
Now $24 = (-5)(-4) + 4$, so $q_k = -4$ and $r_k = 4$ will work.
However, $k+1 = 25 = (-5)(-4) + 5$, and increasing $q_k$ by $1$ will never work out:
$(-5)(-3)$ INCREASES $r_{k+1}$ to $10$, and it only gets worse as you increase $q_k$:
$(-5)(-2)$ demands an $r_{k+1}$ of $15$
$(-5)(-1)$ requires an $r_{k+1}$ of $20$
$(-5)(0)$ leads to an $r_{k+1}$ of $25$
$(-5)(1)$ leads to a remainder of $30$, and so on.


TITLE: Is there a "common" name for this type of combinatorial optimization problem?
QUESTION [4 upvotes]: I'm trying to find papers that discuss approaches (in particular, any Deep Learning or Deep Reinforcement Learning techniques) that could be used used to solve the problem described in the next paragraph. My question is whether such problem has a an equivalent problem with a "famous" name (similarly to what happens with problems like the Knapsack problem or the Job Shop Scheduling problem), since that would make my search much easier.
The problem in question is: given n tasks T1, T2, ..., Tn of varying cost $c_{i}$, and m nodes N1, ..., Nm with varying capacity $r_{i}$, what is the task allocation that minimizes the number of used nodes as priority 1, and the total quantity of free resources in the used nodes as priority 2.
So for example, if I have tasks {T1, T2} with costs {3, 7}, and nodes {N1, N2, N3} with capacity {5, 11, 12}. The optimal alocation would be assigning T1 and T2 to N2, since it would require only one node, and the number of free resources is $11 - 7 - 3 = 1$.
Any tips on what sort of terminology I could use on my search are also welcome! Same applies to suggestions on similar "famous" problems that, even if not equivalent, could be interesting to look at (as per my comments above, I am already familiar with the Knapsack and the JSS problems).
Thank you very much!

REPLY [3 votes]: This is the cutting stock problem with multiple stock lengths.


TITLE: Exercise 12:9.3. Bruckner's Real Analysis
QUESTION [1 upvotes]: The following is from Bruckner's Real Analysis :

In Exercise 12:9.3. :
Part (a) : If we want to make sure that $F(f)$ be common only on the value $1- \ln 2$ and because the lower bound of integration starts at $ \ln 2$ wouldn't that the minimum value for $a$ be $1$, no less?
Part (b) : If to consider $g=t - b$ then $a$ perhaps can be chosen less than $1$ but how the rigorous connection happens, I don't know?

REPLY [0 votes]: Let $X=\mathcal{C}[0,1]$. Let $h(t)=ae^t$ where $a\geq 0$.
Recall that $A=\{f \in X : \|f\|\leq 1\}$ and $B=\{f \in X : \|f-h\|\leq 1\}$.
Item a. Note that for all $f\in A$, we have $F(f)\leq 1 - \ln 2$. We also have that the constant function $1$ belongs to $A$ and $F(1)=1 - \ln 2$. So, $\sup \{F(f): f\in A\}= 1- \ln 2$.
So, in order that $F$ separates $A$ and $B$, we must have, for all $f \in B$, $F(f) \geq 1- \ln 2$. It is easy to see that this is true if and only if
$F(ae^t-1) \geq 1- \ln 2$. So,
\begin{align*}
 F(ae^t-1) & = \int_0^1(ae^t-1) dg =  \int_{\ln 2}^1(ae^t-1) dg = \\
 & =[ae^t-1]_{\ln 2}^1= (e-2)a-(1 -\ln 2) \geq 1- \ln 2
\end{align*}
So,
$$ a \geq \frac{2(1 -\ln 2)}{e-2}$$
So $F$ separates $A$ and $B$ if and only if $ a \geq \frac{2(1 -\ln 2)}{e-2}$. So, the smallest value of $a$ for which $F$ separates $A$ and $B$ is $ a = \frac{2(1 -\ln 2)}{e-2}$.
item b: It is easy to see that
\begin{align*} a > \frac{2}{e}  & \implies ae-1 >1 \implies \|ae^t-1\| >1 \implies \\
& \implies \text{ there is a functional that separates $A$ and $B$. }
\end{align*}
In fact, if $a > \frac{2}{e}$, we have $(\ln2 -\ln a) <1$. Define $g_a$ by $g_a(t)= 0$, if $0 \leq t \leq (\ln2 -\ln a)$  and   $g_a(t)= t-(\ln 2 - \ln a) $, if $ (\ln2 -\ln a) \leq t \leq 1$.  As in example 12.45, we define, for all $f \in X$,
$$ F_a(f)=\int_0^1 f dg_a$$
So, we have for all $f \in A$,
$$ F_a(f) \leq  \int_0^1 1 dg_a= \int_{\ln2 -\ln a}^1 1 dg_a = 1 -(\ln2 -\ln a)$$
Now, if $a > \frac{2}{e}$, we have $(\ln2 -\ln a) <1$ and we also have $ae^t-1 \geq 1$, for $(\ln2 -\ln a) \leq t \leq 1$. So, for all $f \in B$.
\begin{align*} F_a(f) & \geq  \int_0^1 (ae^t-1)dg_a=\int_{\ln2 -\ln a}^1 (ae^t-1) dg_a \geq \\
& \geq\int_{\ln2 -\ln a}^1 1 dg_a = 1 -(\ln2 -\ln a)
\end{align*}
Now note that is $a \leq \frac{2}{e}$, then $ae^t - 1 <1$ for all $t\in [0,1)$ and $ae^t - 1 \leq 1$ for $t=1$.
So,
$$A \cap B= \{f \in X : \forall  t, (ae^t - 1) \leq f(t) \leq 1 \} \ne \emptyset $$
Any functional $F$ that would separate $A$ and $B$ must assign the same value all $f \in A \cap B$. But any functional $F$ is of the form
$$ F(f)=\int_0^1 f dg$$
for some $g \in \text{NBV}[0,1]$.
So, since $ae^t - 1 <1$ for all $t\in [0,1)$ and $F$ must assign the same value all $f \in A \cap B$, we can easily conclude that $g(t)=0$ for all $t\in [0,1)$ (see Remark below). So $F$ is identically null and does not separate $A$ and $B$.
So we have shown that:

If $a > \frac{2}{e}$, there is a functional that separates $A$ and $B$.

If $a \leq \frac{2}{e}$, there is no functional that separates $A$ and $B$.

So, there is no smallest value of $a$ for which some linear functional separates $A$ and $B$. The infimum of the $a$ for which there are such linear functional is $\frac{2}{e}$.
Item c. If the question were asked for open balls, the answer for item b would not change.
In fact, if the question were asked for open balls, we would have
$A_1=\{f \in X : \|f\|<1\}$ and $B_1=\{f \in X : \|f-h\|< 1\}$. It is easy to see that a linear functional $F$ separates open balls $A_1$ and $B_1$ if and only if it separates the corresponding closed balls $A$ and $B$ (the closure of the open balls). So  the answer for item b would not change.
It is interesting to consider what happens for  $a=\frac{2}{e}$. In this case, $A_1 \cap B_1 =\emptyset$ (because if $f\in A_1$, then $f(1) <1$ and if $f\in B_1$, $f(1)> ae-1= 2-1=1$ ). We could then think that there is a functional that separates $A_1$ and $B_1$. However, there is no such functional, because, as said above, a linear functional $F$ separates open balls $A_1$ and $B_1$ if and only if it separates the corresponding closed balls $A$ and $B$ (the closure of the open balls).
$\square$
Remark: Let us prove in detail that if $F$ must assign the same value all $f \in A \cap B$, then $g(t)=0$ for all $t\in [0,1)$.
Note that, by Riesz Representation Theorem, $g \in \text{NBV}[0,1]$, so $g$ is a bounded variation function, $g$ is right continuous and $g(0)=0$.
Now, for a contradiction, suppose there is a $t_0 \in (0,1)]$ such that $g(t_0) \ne 0$. Without loss of generality, suppose  $g(t_0) > 0$. Since  $g$ is right continuous, there is $t_1 >t_0$ such that $g(t)>0$ for $t \in (t_0,t_1)$. Let $\varepsilon <\frac{t_1-t_0}{2}$ and let
$f_0 \in \mathcal{C}[0,1]$ such that

$f_0(t) \in [0, 2-ae^{t_1} ]$, for all $t\in [0,1]$

$f_0(t) = 0$ for $t \in [0,t_0] \cup [t_1, 1]$

$f_0(t)=2-ae^{t_1}$ for $t\in [t_0+\varepsilon , t_1-\varepsilon]$

Clearly
$$F(f_0)= \int_0^1 f_0(t)dg > 0$$
But, it is easy to see that, for all $t \in [0, 1]$, $(ae^t - 1) \leq 1- f_0(t) \leq 1$. So, $1- f_0 \in A \cap B$. Since the constant function $1$ is also in $A\cap B$, we have
$F( 1- f_0(t))= F(1)$.
So,
$$ F(f_0)= F(1 - (1- f_0(t))) = F(1) - F( 1- f_0(t)) =0$$
Contradiction. So we have $g(t)=0$ for all $t\in [0,1)$.


TITLE: Methods of solving linear system of equations, how to select the appropriate method
QUESTION [3 upvotes]: A linear system of equations Ax=b can be solved using various methods, namely, inverse method, Gauss/Gauss-Jordan elimination, LU factorization, EVD (Eigenvalue Decomposition), and SVD (Singular Value Decomposition).
I know that there are several disadvantages of using inverse method; for example, with ill conditioned matrix A the solution can not be computed with inverse method. Moreover, I know that with changing vector b LU factorization has advantage over Gauss/Gauss-Jordan elimination.  How to decide between LU, SVD, and EVD? Is there any scenario where Gauss/Gauss-Jordan elimination has advantage over LU, SVD, and EVD?

REPLY [2 votes]: If you want to see what a group of experts did, Matlab has a flowchart for their mldivide (aka "backslash") : https://www.mathworks.com/help/matlab/ref/mldivide.html
The punchline appears to be that unless the matrix has structure, use LU for square and QR for non-square.
See also: https://scicomp.stackexchange.com/questions/1001/how-does-the-matlab-backslash-operator-solve-ax-b-for-square-matrices for


TITLE: Closure on topological vector space
QUESTION [1 upvotes]: I came across a problem on topological vector spaces that seems to be simple yet it bothers me:
Let $A,B$ be non empty subsets of the t.v.s $X$  with $\overline{A}$ compact. Then show that $$\overline{A+B}=\overline{A}+\overline{B}$$
Ok using that $f$ (let $f$ for addition $f:X\times X\to X$) is continuous on a t.v.s we get $$\overline{A}+\overline{B}=f(\overline{A}\times \overline{B})=f(\overline{A\times B})\subseteq \overline{f(A\times B)}=\overline{A+B}.$$
For the other inclusion can't i use that if $z\in \overline{A+B}$ then it belongs to every closed set containing $A+B$ . More specifically it belongs to the intersection of the family $$\overline{A}+ M$$ where $M$ closed, $B\subseteq M$.
I guess something is wrong as i didn't use the compactness assumption...
Any hints would be great.

REPLY [0 votes]: (1). If $c\in Cl(A+B)$ there is a sequence $(c_n)_n$ in $A+B$ converging to $c.$ Let $c_n=a_n+b_n$ with  $a_n\in A$ and $b_n\in B.$ Since $Cl(A)$ is compact and $(a_n)_n$ is a sequence in $Cl(A),$ there is a sub-sequence $(a_{n_j})_j$ converging to some $a\in Cl(A),$  so $(b_{n_j})_j =(c_{n_j}-a_{n_j})_j$ converges to $c-a.$ Obviously if $(b_{n_j})_j$ converges, then it converges to some to some $b\in Cl(B).$ So $c=a+b\in Cl(A)+Cl(B).$
(2). If $d\in Cl(A)+Cl(B)$ there exist $a\in Cl(A)$ and $b\in Cl(B)$ with $d=a+b. $ There are sequences $(a_n)_n, (b_n)_n$ in $A,B$ respectively, converging to $a,b$ respectively. The sequence $(a_n+b_n)_n$ in $A+B$ converges to $a+b= d.$ So $d\in Cl(A+B).$


TITLE: Radius of a circumference having two chords
QUESTION [1 upvotes]: In the image, the lenghts of the chords are $6$ and $8$, and the gap between the chords is $1$. Then the radius of the circumference is?

I drew the perpendicular diameters to the chords and tried to apply power of a point, but i didn't find anything. I need some hints.

REPLY [0 votes]: By Pythagoras,
$$\sqrt{r^2-3^2}-\sqrt{r^2-4^2}=1$$
then
$$(r^2-3^2)-2\sqrt{r^2-3^2}\sqrt{r^2-4^2}+(r^2-4^2)=1,$$
$$(2r^2-26)^2=4(r^2-9)(r^2-16),$$
$$4r^2-100=0.$$


text:
\begin{document}

\section{Problem Setup} \label{sec:setup}
We are interested in studying the following differential system
\begin{equation}
\label{eq:ode}
\frac{d}{dt} \x (t, \aalpha)=\f(\x, \aalpha,g(t)), \quad \x(t_0)=\x_0,
\end{equation}
where $\x=(x_1, \ldots, x_d)\in \R^d$ are state variables, $\aalpha=(\alpha_1,,\ldots, \alpha_l)\in \R^l$ denote measurable quantities which effect the evolution of the state variables, $g(t)$ are time dependent inputs, and $t_0$ is the initial time.

This dynamical system defines a mapping from the initial condition $t=t_0$ to the solution at $t=s$ as below
\begin{equation*}
\x(s; \x_0, \aalpha, g(t))=\PPhi_{s-t_0}(\x_0; \aalpha, g(t)), \quad s>t_0.
\end{equation*}
We call this mapping the \textit{flow map} for the ODE \eqref{eq:ode}.

Now assume that we can represent the time dependent inputs via
$$g(t)=\sum_{i=1}^n g_i\phi_i(t)$$
The we can represent the flow map via
$$
\x(s; \x_0, \aalpha,\V{g}, t_0)=\PPhi_{s-t_0}(\x_0; \aalpha, \V{g}, t_0), \quad s>t_0.
$$
where $\V{g}=(g_1,\ldots,g_n)\in\R^n$. This expansion allows the specification of a large class of time dependent inputs. For example the expansion may be the truncation of a stochastic process such as a Weiner process which describes brownian motion.

\begin{remark}Consider the recovery of the numerical solution of a discretized ODE. Let $x(t;,\x, \aalpha, g(t))$ be the output of the ODE solver at time $t=t_0+\Delta$ produced using $k$ timesteps. The flow map above will be exact for any forcing $g$ if we set $n=k$ and the basis function $\phi$ to be piecewise polynomial basis functions centered at each of the $k$ timesteps in the interval $\Delta$. For example if using explicit forward Euler the $\phi$ will be piecewise linar.
 \end{remark}

In this paper, we assume the form of the governing equations $\f(t,\x, \aalpha, g(t)):\R^d\rightarrow\R^d$ is unknown. Our goal is to create an accurate model for the governing equation using data of the solution trajectories $\x$ and the measurable quantities $\aalpha$. To approximate the governing equations we collect data int the form of pairs, each of which corresponds to the solution states along one trajectory at two different time instances with time lag $\Delta$. That is we consider the data pairs
\begin{equation*}
\z^{(1)}_j=\left(\x_j+\epsilon_j^{(1)},\aalpha_j, \V{g}, t_0\right), \quad \z^{(2)}_j=\PPhi_{\Delta_j}(\x_j; \aalpha_j, \V{g}_j, t_{0,j})+\epsilon_j^{(2)}, \quad j=1,\ldots,J
\end{equation*}
where $J$ is the total number of data pairs, and $\epsilon_j^{(1)}$ and $\epsilon_j^{(2)}$ are measurement/simulation errors. For notational convenience, we assume $\Delta_j=\Delta$ to be a constant for all $j$ throughout this paper. Consequently, the data set becomes input-output measurements of the $\Delta$-lag flow map,
\eq{\x\rightarrow\Phi_\Delta(\x,\aalpha,\V{g}, t_0).}

\section{Analysis}
Now we consider the consequences of not being able to approximate the input $g$ with a finite number of terms $n$, i.e. we have
$$\lVert g(t)-\sum_{i=1}^n g_i\phi_i(t)\rVert\le\epsilon,\forall t$$

\section{Numerical Examples}
\subsection*{Example 1: Linear Scalar ODE}
Let us first consider the following linear ODE with a single random parameter
\begin{equation}
	\label{eq:example_1}
		\frac{dx}{dt}=-\alpha\, x + g_1\sin(t)+g_2\cos\left(\frac{t}{2}\right), \quad x(t_0)=x_0,
\end{equation}
where $\alpha$ is a random coefficient. We will consider two cases when $\V{g}$ is fixed for all time and when $\V{g}$ can take a set of permissible values. The former case simulates laboratory conditions when forcing can be controlled, and the later case when the exact nature of the forcing is unknown. In both examples we take $I_\alpha=[0,1]$.

\subsubsection*{Case 1: Known forcing}
Set $I_x=[-0.2,1]$, $g_1=0.05$ and $g_2=0.0$ and make prediction with initial condition $x_0$ randomly chosen for uniform distribution on $I_x$. For case plotted $x_0=0.30042641$.  Build approximation using sparse grid.
\onefig{../poly_learning/non-autonomous-example-case-I}{Linear Scalar ODE Case I}
\subsubsection*{Case 1: Unknown forcing}
Set $I_x=[-0.2,1]$, $g_1\in[-0.05,0.05]$ and $g_2\in[-0.05,0.05]$ and make prediction with initial condition $x_0$ randomly chosen for uniform distribution on $I_x$. For case plotted $x_0=0.32319388$. Build approximation using sparse grid.
\onefig{../poly_learning/non-autonomous-example-case-II}{Linear Scalar ODE Case II}

\end{document}


TITLE: From a.e. convergence to pointwise convergence
QUESTION [0 upvotes]: I have a question about a.e. convergence.
Let $K$ be a compact subset of $\mathbb{R}^d$ and $\{f_{n}\}$ be a sequence of continous functions on $K$. We assume that $f_n(x) \to 0$ a.e. $x \in K$
Question
Can we show that $f_{n}(x)\to 0$ for every $x \in K$ ?
My idea
Set
\begin{align*}
A&=\left\{ x \in K : \lim_{n \to \infty}f_{n}(x) \neq 0 \right\} , \\
B&=\left\{ x \in K : \lim_{n \to \infty}f_{n}(x)= 0 \right\}.
\end{align*}
If $A \neq \emptyset$, there exists $y \in K$, $\epsilon_{0}>0$ and subsequence $\{n_{k}\}$ such that
\begin{align*}
\text{ for every }k \ge 1, |f_{n_{k}}(y)| \ge \epsilon_0 .
\end{align*}
Since $B$ is a dense subset of $K$, we can find $x_k \in A$ such that
\begin{align*}
\text{ for every }k \ge 1, |f_{n_{k}}(y)-f_{n_{k}}(x_k)| < \epsilon_0/2.
\end{align*}
Accordingly, for all $k \ge 1$,
\begin{align*}
|f_{n_k}(y)| <|f_{n_{k}}(x_k)|+\epsilon_0/2
\end{align*}
But for large $k$ enough, say $K$, $|f_{n_K}(x_K)|<\epsilon_0/2$ holds because $x_K \in B$. Therefore,
\begin{align*}
|f_{n_K}(y)|<|f_{n_K}(x_K)|+\epsilon_0/2<\epsilon_0
\end{align*}
This is contradiction.
Is this correct?

REPLY [1 votes]: Take $d=1$, $K=[0,1]$ and $f_n(x)=x^n$.
Then your initial conditions are met:

$f_n(x)\to 0$ for all $x$ in $[0,1)$, which means
  $$f_n(x)\to 0 \text{ a.e.}$$
  is true

However, it is not true that $\forall x: f_n(x)\to 0$, because, $f_n(1)=1$ for every $n$.

Furthermore, you can extend the counterexample to any dimension, by defining
$$f(x_1,x_2,\dots, x_d) = x_1^n$$
and taking $K=[0,1]^d$:

Clearly, $f_n(x)\to 0$ for almost all $x\in K$. The set on which this is not true is $A=\{(1,x_2,\dots, x_d)| x_i\in[0,1]\}$ which has measure $0$ (it is a $d-1$-dimensional set!)
$\forall x\in A\forall n\in\mathbb N: f_n(x)=1$.

OK, so clearly your proof must be wrong, but where did you go wrong? Well, for one thing, you claim that $B$ is dense, which may not be the case.
But in my example, $B$ is dense, but still this is not enough to conclude that $f_n(x)\to 0$ everywhere. So you must have made another error.
Your error is in saying

But for large $k$ enough, say $K$, $|f_{n_K}(x_K)|<\epsilon_0/2$ holds because $x_K \in B$

This is not true, because as you move $K$, you are changing both $f_{n_K}$ as well as $x_K$. There exists a sequence $x_k$ such that:

For all $k$, $x_k\in B$
For all $k$ $f_k(x_k) > \frac12$

Which proves that your claim is wrong.

Your claim would be correct if you had a fixed value of $x\in B$, and you would the claim

There exists some $K$ such that $|f_K(x)|<\epsilon$.

But what you claimed was a stronger (and false) claim.


text:
\begin{document}
\begin{abstract}
  For any equivalence relation \(\equiv\) on positive integers such that \(nk \equiv mk\) if and
  only if \(n \equiv m\), there is an abelian group \(G\) such that the
  endomorphism ring of \(G^n\) and \(G^m\) are isomorphic if and only if \(n \equiv
  m\).  However, \(G^n\) and \(G^m\) are not isomorphic if \(n \neq m\).
\end{abstract}

\maketitle{}

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

We construct partially ordered abelian groups such that the orbit of a
distinguished element under the automorphism group is prescribed; the precise
statement is Theorem~\ref{th:2} in Subsection~\ref{sec:dimension-groups}.  The
prescribed orbit controls the \emph{matrix type} of a ring, i.e., which matrix
algebras over the ring are isomorphic, hence we can characterize the matrix
types of ultramatricial algebras over any principal ideal domain, see
Theorem~\ref{th:1} in Subsection~\ref{sec:ultr-algebr}.  If the ground ring is
\(\setZ\) then these algebras are realizable as endomorphism rings of torsion-free
abelian groups, which groups therefore have the property stated in the
abstract, see Corollary~\ref{cor:1}.

We are indebted to P\'eter V\'amos who draw our attention to this wonderful problem.

\subsection{Dimension groups}
\label{sec:dimension-groups}

An \emph{order unit} in a partially ordered abelian group is a positive
element \(u\) such that for every element \(x\) there is a positive integer
\(n\) such that \(nu \geq x\). A \emph{dimension group} \((D, \leq, u)\) is a
countable partially ordered abelian group \((D, \leq)\) with order unit \(u\)
such that every finite subset of \(D\) is contained in a subgroup, which is
isomorphic to a direct product of finitely many copies of \((\setZ, \leq)\) as a
partially ordered abelian group.

Our main result, which will be proven from Section~\ref{sec:overv-constr} on, is:
\begin{theorem}
  \label{th:2}
  Let \(H \leq \setQ_+^\times\) be a subgroup of the multiplicative group of the positive
  rational numbers. Then there is a dimension group \((D, \leq, u)\) whose group
  of order-preserving automorphisms is isomorphic to \(H\). Furthermore, under
  this isomorphism every element of \(H\) acts on \(u\) by multiplication by
  itself as a rational number.
\end{theorem}

In the special case when \(H\) is generated by a set \(S\) of prime numbers,
one may choose \(D\) to be the ring \(\setZ[S^{-1}]\) and \(u=1\), see
\cite[Proposition~4.2]{MR99f:16008}.

\subsection{Ultramatricial algebras}
\label{sec:ultr-algebr}

An \emph{ultramatricial algebra} over a field or principal ideal domain \(F\)
is an \(F\)-algebra which is a union of an upward directed countable set of
\(F\)-subalgebras, which are direct products of finitely many matrix algebras
over \(F\).

\subsubsection{Matrix types of rings}
\label{sec:matrix-types-rings}

Let \(M_n(R)\) denote the ring of \(n \times n\) matrices over the ring \(R\).
Obviously, \(M_n(R)\) is ultramatricial if \(R\) is ultramatricial.  The
\emph{matrix type} of a ring \(R\) is the equivalence on positive integers
describing which matrix algebras over \(R\) are isomorphic:
\begin{equation}
  \label{eq:1}
  \mt(R) := \{ (n,m) \mid M_n(R) \cong M_m(R) \}.
\end{equation}
Clearly, if \((n,m) \in \mt(R)\) then \((mk,nk) \in \mt(R)\) for all positive
integers \(m\), \(n\), \(k\).  The converse also holds for ultramatricial
algebras but probably not for all rings.

The next theorem states that all such equivalences indeed arise as matrix
types of ultramatricial algebras:
\begin{theorem}
  \label{th:1}
  Let \(F\) be a field or principal ideal domain and \(\equiv\) be an equivalence
  relation on the set of positive integers. Then the following are equivalent:
  \begin{enumerate}[label=(\roman*)]
  \item For all positive integers \(n\), \(m\) and \(k\)
    \begin{equation}
      \label{eq:2}
      n \equiv m \iff nk \equiv mk.
    \end{equation}
  \item There is a (unique) subgroup \(H\) of the multiplicative group
    \(\setQ_+^\times\) of positive rational numbers such that for all positive integers
    \(n\) and \(m\):
    \begin{equation}
      \label{eq:29}
      n \equiv m \iff \frac{n}{m} \in H.
    \end{equation}
  \item There exists an ultramatricial \(F\)-algebra with matrix type \(\equiv\).
  \end{enumerate}
\end{theorem}

The second statement is clearly a reformulation of the first one, which is
useful for explicit construction of equivalences, as pointed out by the
referee.

The equivalence of the second and third statements is a simple consequence of
our main result, Theorem~\ref{th:2}, as we will explain in the
\hyperref[sec:equiv-dimens-groups]{next section}.

\subsubsection{Basis types of rings}
\label{sec:basis-types-rings}

In a similar vein, the \emph{basis type} of a ring \(R\) characterizes which
finite rank free modules are isomorphic:
\begin{equation}
  \label{eq:30}
  \operatorname{bt}(R) := \{ (n,m) | R^n \cong R^m \}.
\end{equation}
The analogue of Theorem~\ref{th:1} for basis types is Theorem~1 of
\cite{MR0238903}: every equivalence relation with the property \(n \equiv m\) if
and only if \(n+k \equiv m+k\) is the basis type of a ring of infinite matrices.

Clearly, if \(R^n \cong R^m\) then \(R^{n+k} \cong R^{m+k}\).  All equivalence
relation with this property arise as basis type of a ring: see
\cite{MR0132764}.

The basis type is obviously smaller than the matrix type.  It seems plausible
that this is the only relation between the two types.  For example,
ultramatricial algebras have trivial basis type i.e., free modules of
different finite rank are not isomorphic.

Every ultramatricial algebra \(R\) over \(F=\setZ\) is a countable reduced
torsion-free ring, and hence is the endomorphism ring of a torsion-free
abelian group \(G\) by \cite[Theorem~A]{MR27:3704}.  Then \(M_n(R)\) is the
endomorphism ring of \(G^n\).  Obviously \(G^n\) and \(G^m\) are not
isomorphic if \(n \neq m\) since there is no invertible \(n \times m\) matrix over
\(R\).  Hence we have the statement in the abstract as an immediate corollary
to the last theorem:
\begin{corollary}\label{cor:1}
  Let \(\equiv\) be an equivalence relation on positive integers with the property
  that \(n \equiv m\) if and only if \(nk \equiv mk\) for all positive integers \(n\), \(m\)
  and \(k\).  Then there is a torsion-free abelian group \(G\) such that the
  endomorphism ring of \(G^n\) and \(G^m\) are isomorphic if and only if
  \(n \equiv m\).  Moreover, \(G^n\) and \(G^m\) are isomorphic if and only if
  \(n=m\).
\end{corollary}

\section{Equivalence of dimension groups and ultramatricial algebras}
\label{sec:equiv-dimens-groups}

Dimension groups and ultramatricial algebras over a fixed field or principal
ideal domain are essentially the same.  In this section, we recall this
equivalence, which shows that Theorem~\ref{th:1} follows from
Theorem~\ref{th:2}.  For more details and proofs see
\cite[Proposition~4.1]{MR99f:16008} or \cite[Chapter~15, Lemma~15.23,
Theorems~15.24 and 15.25]{MR93m:16006}, which assume that the ground ring is a
field, but the arguments also work when it is a principal ideal domain.

First we define the functor \(K_0\) from the category of rings to the category
of preordered abelian groups with a distinguished order unit.  The isomorphism
classes of finitely generated projective left modules over a ring \(R\) form a
commutative monoid where the binary operation is the direct sum.  The quotient
group of the monoid is denoted by \(K_0(R)\).  Declaring the isomorphism
classes of projective modules to be nonnegative, \(K_0(R)\) becomes a
preordered group.  The isomorphism class \(u\) of \(R\), the free module of
rank \(1\), is an order unit of \(K_0(R)\).

If \(f\colon R \to S\) is a ring homomorphism then let \(K_0(f)\) map the isomorphism
class of a projective module \(P\) to that of \(S \otimes_R P\).  So \(K_0(f)\) is a
homomorphism preserving both the order and the order unit.

If \(R\) is an ultramatricial algebra then \(K_0(R)\) is a dimension group.
Conversely, every dimension group is isomorphic to the \(K_0\) of an
ultramatricial algebra.  If \(R\) and \(S\) are ultramatricial algebras then
every morphism between \(K_0(R)\) and \(K_0(S)\) is of the form \(K_0(f)\) for
some algebra homomorphism \(f\colon R \to S\).  However, \(f\) is not unique in
general.  Nevertheless, every isomorphism between \(K_0(R)\) and \(K_0(S)\)
comes from an isomorphism between \(R\) and \(S\).

Thus, by restriction, \(K_0\) is essentially an equivalence between the category of
ultramatricial algebras over a given field and the category of dimension
groups with morphisms the group homomorphisms preserving both the order and
the order unit.

Now we examine how the matrix type of an ultramatricial algebra can be
recovered from its dimension group.  The standard Morita equivalence between
\(R\) and \(M_n(R)\) induces an isomorphism between the \(K_0\) groups.
However, this isomorphism does not preserve the order unit, in fact
\(K_0(M_n(R))\) is \((K_0(R), \leq, nu)\) where \(u\) is the order unit of
\(K_0(R)\).

So if \(R\) is an ultramatricial algebra, then the dimension groups
\(K_0(M_n(R))\) and \(K_0(M_m(R))\) (and hence the algebras \(M_n(R)\) and
\(M_m(R)\)) are isomorphic if and only if there is an order-preserving
automorphism of \(K_0(R)\) sending \(nu\) to \(mu\).  Obviously, for any
dimension group \((D, \leq, u)\) whether an order-preserving automorphism maps
\(nu\) to \(mu\), depends only on the factor \(m/n\).  Such factors \(m/n\)
form a subgroup of the multiplicative group \(\setQ_+^\times\) of the positive
rationals.

So the classification of matrix types of ultramatricial algebras is equivalent
to the classification of subgroups of \(\setQ_+^\times\) which arise from dimension
groups in the above construction. Theorem~\ref{th:2} states that all subgroups
arise, and Theorem~\ref{th:1} is just the translation of it to the language of
matrix types of ultramatricial algebras.

\section{Overview of the construction}
\label{sec:overv-constr}

In the rest of the paper we prove Theorem~\ref{th:2}.  In this section we
outline the main ideas of the proof and leave the details for the following
sections.  The \hyperref[sec:notation]{next section} fixes notations used frequently in the rest of the
paper.  Section~\ref{sec:abelian-groups-endo} recalls a construction of
abelian groups.  The actual proof is contained in the rest of the sections,
which are organized so that they can be read independently.  At the beginning
of every section, we shall refer to its main proposition, which will be the
only statement used in other sections.  The same is true for subsections.

To prove Theorem~\ref{th:2}, we fix a subgroup \(H\) of the positive rationals
and construct a dimension group \(D\) for it.  We search for \(D\) (as an abelian
group without any order) in the form \(D := \setQ u \oplus G\) where \(H\) acts on the
direct sum componentwise.  We let \(H\) act on \(\setQ u\) by multiplication as
required to act on the order unit.  A key observation
(Proposition~\ref{prop:2}) is that if the only automorphisms of \(G\) are the
elements of \(H\) and their negatives, then for any partial order \(\leq\) on
\(D\), which is preserved by \(H\) and makes \((D, \leq, u)\) a dimension group,
the order-preserving automorphism group of \(D\) is only \(H\).  So \((D, \leq,
u)\) satisfies the \hyperref[th:2]{theorem}.

Therefore, all we have to do is to find such a \(G\) and \(\leq\).  Actually,
\(G\) is already constructed by A.~L.~S.~Corner in~\cite{MR27:3704}.  Since we
shall use the structure of \(G\) to define the partial order \(\leq\), we recall
a special case of the construction in Section~\ref{sec:abelian-groups-endo},
which is enough for our purposes.  See also \cite{GT} for the general
statement.

Finally, we define a partial order \(\leq\) on \(D\) making it a dimension group
in Subsection~\ref{sec:partial-order}.  The basic idea is to explicitly make
some subgroups of \(D\) order-isomorphic to \(\setZ^n\) and show that these
partial orders on the subgroups are compatible.  This will be based on a
description of \(G\) (Proposition~\ref{prop:3}): we define elements of \(G\),
which will be bases of order-subgroups \(\setZ^n\) of \(D\) and state relations
between them implying the compatibility of partial orders.

\section{Notation}
\label{sec:notation}

This section is just for fixing notation used throughout the paper.

Let \(x_h\) denote the element of the group ring \(\setZ H\) corresponding to \(h
\in H\). This is to distinguish \(x_ha\) the value of \(x_h\) at \(a\) from
\(ha\) the element \(a\) multiplied by the rational number \(h\).

If the automorphism group of an abelian group is the direct product of a group
\(H\) and the two element group generated by \(-1\) then we say that the
automorphism group is \(\pm H\).

\section{Abelian groups with prescribed endomorphisms}
\label{sec:abelian-groups-endo}

In this section we revise a special case of A.~L.~S.~Corner's construction of
abelian groups with prescribed endomorphism rings.  I am grateful to R\"udiger
G\"obel and his group for teaching me this method.

Let \(\completion{M}\) denote the \(\setZ\)-adic completion of the abelian group \(M\).
The following result is is a special case of Theorem~1.1 from
\cite{0178.02303} by taking \(A=R\) and \(N_k=0\):

\begin{proposition}
  \label{prop:1}
  Let \(R\) be a ring with free additive group. Let \(B\) be a free
  \(R\)-module of rank at least \(2\) and \(\{w_b : b \in B \setminus \{0\}\}\) a collection
  of elements of \(\completion{\setZ}\) algebraically independent over \(\setZ\). Let the
  \(R\)-module \(G\) be
  \begin{equation}
    \label{eq:3}
    G := \langle B, Rbw_b : b \in B \setminus \{0\} \rangle_* \subseteq \completion{B}.
  \end{equation}

  Then \(G\) is a reduced abelian group with endomorphism ring \(R\).
\end{proposition}
Here \(*\) means purification: i.e., we add all the elements \(x\) of
\(\completion{B}\) to \(E := B \oplus_{b \in B \setminus \{0\}} Rbw_b\) for which \(nx \in E\)
for some nonzero integer \(n\).  The usual down-to-earth description of \(G\)
is the following, which we shall use in
Subsection~\ref{sec:abelian-group-under}: we select positive integers \(m_n\)
such that every integer divides \(m_1 \dotsm m_n\) for \(n\) large enough.  We
choose elements \(w_b^{(n)}\) of \(\completion{\setZ}\) for all nonzero elements
\(b\) of \(B\) and natural numbers \(n\) such that \(w_b^{(0)} = w_b\) and
\(w_b^{(n)} - m_n w_b^{(n+1)}\) is an integer.  Then \(G\) is generated by the
submodules \(B\) and \(Rbw_b^{(n)}\).  Obviously, \(G_n := B \oplus_{b \in B \setminus \{0\}}
Rbw_b^{(n)}\) is a submodule of \(G\) and these modules \(G_n\) form an
increasing chain whose union is the whole \(G\).  It is important to note that
\(G\) does \emph{not} depend on the choice of the \(m_n\) and \(w_b^{(n)}\).
However, the submodules \(G_n\) \emph{does} depend on them.

\begin{remark}
  \label{remark:Corner}
  Note that the automorphism group of \(G\) is the group of units of \(R\),
  which is just \(\pm H\) if \(R = \setZ H\) and \(H\) is an orderable group.  (It
  is a famous conjecture that the group of units of \(\setZ H\) is \(\pm H\) for all
  torsion-free groups \(H\).)

  We will be interested in the case when \(H \leq \setQ_+^\times\) and \(R = \setZ H\) is a
  group ring.  The free module \(B\) will have countable rank.  Recall that
  there are continuum many elements of \(\completion{\setZ}\) algebraically independent
  over \(\setZ\), so the construction works in this case, and we will get a reduced
  abelian group \(G\) with automorphism group \(\pm H\).
\end{remark}

\section{Construction of the dimension group}
\label{sec:constr-dimens-group}

We now construct our dimension group \(D = \setQ u \oplus G\) starting from a subgroup
\(H \leq \setQ_+^\times\) of the positive rationals.  The main result of the section is
Proposition~\ref{prop:4}.

The \hyperref[prop:3]{proposition} in Subsection~\ref{sec:abelian-group-under}
defines \(G\) and summarizes the (technical) properties of \(G\) used in
Subsection~\ref{sec:partial-order} to put the partial order on \(D\).

Let \(\nSeq\) denote the set of sequences of length \(n\) whose elements are
\(0\) or \(1\). If \(y\) is a finite sequence of \(0\) and \(1\) then let
\(y0\) denote the sequence obtained from \(y\) by adding an additional element
\(0\) to the end. Similarly, we can define \(y1\).  These sequences will be
identified with elements of \(G\).

\subsection{The abelian group under the dimension group}
\label{sec:abelian-group-under}

In this subsection we construct an abelian group \(G\) satisfying the
following properties. Essentially, \(G\) will be the underlying abelian group
of our dimension group.

\begin{proposition}\label{prop:3}
  Let \(H \leq \setQ_+^\times\) be a subgroup of the multiplicative group of the positive
  rational numbers. Let \(R:=\setZ H\) denote its group ring. Then there exist:
  \begin{itemize}
  \item an \(R\)-module \(G\), which is also a reduced abelian group,
  \item a finite subset \(F_n \subseteq H\) for all positive integer \(n\),
  \item positive integers \(s_n\), \(t_n\), \(k_n\) and \(l_n\) for \(n \geq 0\)
  \end{itemize}
  subject to the following conditions:
  \begin{enumerate}[label=(\roman*)]
  \item \label{item:1} \(\Aut G = \pm H\).
  \item \label{item:11} Structure of \(G\):
    \begin{enumerate}[label=(\alph*), ref=\theenumi.(\alph*)]
    \item \label{item:2} \(G\) is a union of an increasing sequence of free
      submodules \(G_n\).
    \item \label{item:3} \(G_n\) has base \(\nSeq \cup \{ c_i^{(n)} : i = 1, \dotsc,
      n \}\).
    \end{enumerate}
  \item \label{item:12} Relations describing the inclusion \(G_n \subseteq G_{n+1}\):
    \begin{enumerate}[label=(\alph*), ref=\theenumi.(\alph*)]
    \item \label{item:4} \(y = y0 + s_n^2 \cdot y1\) \quad for all \(y \in \nSeq\).
    \item \label{item:5} There are integers \(n_{h,y}^{(i)}\) for all \(i \leq
      n\), \(h \in H\) and \(y \in \nSeq\) such that
      \begin{equation}\label{eq:12}
        c_i^{(n)} - s_nt_n c_i^{(n+1)} = \sum_{\substack{h \in F_i \\ y \in \nSeq}}
        n_{h,y}^{(i)} x_h \cdot y0, \quad 0 \leq n_{h,y}^{(i)} < s_nt_n.
      \end{equation}
    \end{enumerate}
  \item \label{item:10} Properties of \(s_n\), \(t_n\), \(k_n\) and \(l_n\):
    \begin{enumerate}[label=(\alph*), ref=\theenumi.(\alph*)]
    \item \label{item:7}
      \begin{align*}
        k_0 &= 1, & k_{n+1} &= s_n k_n,\\
        l_0 &= 1, & l_{n+1} &= t_n l_n.
      \end{align*}
    \item \label{item:8} Every positive integer divides \(k_n\) and \(l_n\) for
      \(n\) large enough.
    \item \label{item:9} \(k_n (s_n^2-1) \geq l_n s_n t_n \sum_{i=1}^n \sum_{h \in F_i} h\).
    \end{enumerate}
  \end{enumerate}
\end{proposition}

\begin{proof}
The construction of the items is easy.  One has to care about defining
them in the correct order.

Let \(B\) be a countable-rank free module over the group ring \(R:=\setZ H\) i.e.,
\(B = \setZ H \otimes A\) where \(A\) is a free abelian group of countably infinite
rank.  Using this group we define \(G\) by Equation~\eqref{eq:3} as in
Proposition~\ref{prop:1}.  (The \(\setZ\)-adic integers \(w_b\) can be chosen
arbitrarily.)  The \hyperref[prop:1]{proposition} tells us that \(G\) is a
reduced abelian group and \(\Aut G = \pm H\) so \ref{item:1} is satisfied.

We identify a base of \(A\) with the finite sequences of \(0\) and \(1\) not ending with \(0\)
(so with the sequences ending with \(1\) and the empty sequence). In this
base, the sequences of length at most \(n\) is a basis of a free subgroup
\(A_n\) of \(A\) and the free \(R\)-module \(B_n = R \otimes A_n\).

Let us enumerate the elements of \(B \setminus \{0\}\) into a sequence \(b_1, b_2,
\dotsc\) such that \(b_n \in B_n\). Every element of \(B\) can be written uniquely
as \(\sum_{h \in H} x_h b_h\) where \(b_h \in A\) and only finitely many of the
\(b_h\) are nonzero. We define the \emph{support} of an element of \(B\) as the
finite set
\begin{equation}
  \label{eq:14}
  \left[ \sum_{h \in H} x_h b_h \right] := \{ h \in H \mid b_h \neq 0 \} \quad (b_h \in A).
\end{equation}
Let \(F_i := [b_i]\) be the support of \(b_i\).

Now we are ready to define our positive integers \(s_n\), \(t_n\), \(k_n\) and
\(l_n\). Let us impose the following additional condition on them:
\begin{trivlist}
\item[\hypertarget{item:divisible}{(*)}] \(t_n\) is divisible by \(n\), and \(t_n\) divides \(s_n\).
\end{trivlist}
Now the integers can be defined recursively such that \ref{item:7}, \ref{item:9}
and~\hyperlink{item:divisible}{(*)} hold. These automatically imply the truth of \ref{item:8}.

Now we identify the sequences of \(0\) and \(1\) with elements of \(A\).  We
have already done this for the sequences not ending with zero: they form a
basis of \(A\).  As dictated by~\ref{item:4}, we set
\begin{equation}
  \label{eq:15}
  y0 := y - s_n^2 \cdot y1 \quad (y \in \nSeq).
\end{equation}
(This is in fact a recursive definition on the length of \(y\) since \(y\) may
also end with zero.) Thus the sequences of finite length are identified with
elements of \(A\) such that \ref{item:4} holds and the sequences of length
exactly \(n\) form a basis of \(A_n\) as can be easily seen by induction on
\(n\).

We turn to the definition of the \(G_n\). Let us choose \(\setZ\)-adic integers
\(w_i^{(n)}\) for \(1 \leq i \leq n\) such that
\begin{equation}
  \label{eq:16}
  w_i^{(0)} := w_{b_i}, \quad w_i^{(n)} - s_n t_n w_i^{(n+1)} \in \setZ, \quad
  w_i^{(n)} \in \completion{\setZ}.
\end{equation}
We let \(G_n\) be the free submodule
\begin{equation}
  \label{eq:17}
  G_n := B_n \oplus \bigoplus_{i=1}^n R b_i w_i^{(n)}.
\end{equation}
It follows from the definition of \(G\) (Equation~\eqref{eq:3}) that the groups
\(G_n\) form an increasing sequence of submodules whose union is \(G\).

The only missing entities are the elements \(c_i^{(n)}\).  We could set \(c_i^{(n)}=b_i
w_i^{(n)}\) to satisfy \ref{item:3} but this may not be appropriate
for~\ref{item:5}.  Therefore we shall set
\begin{equation}
  \label{eq:18}
  c_i^{(n)} := b_i w_i^{(n)} + b_i^{(n)} \quad (b_i^{(n)} \in B_n, i \leq n)
\end{equation}
for some \(b_i^{(n)}\).  This ensures \ref{item:3}.  For \(i\) fixed, we are
going to define the \(b_i^{(n)}\) recursively for \(n \geq i\) subject to:
\begin{enumerate}[label=(\Alph*)]
\item \label{item:13} \(b_i^{(n)} \in B_n\).
\item \label{item:14} \([b_i^{(n)}] \subseteq [b_i] = F_i\).
\item \label{item:15} For suitable integers \(n_{h,y}^{(i)}\):
  \begin{equation}
    \label{eq:19}
    b_i \left(w_i^{(n)} - s_n t_n w_i^{(n+1)} \right) + b_i^{(n)} =
    s_n t_n b_i^{(n+1)} + \sum_{h \in F, y \in \nSeq} n_{h,y}^{(i)} x_h \cdot y0, \quad 0 \leq n_{h,y}^{(i)} < s_nt_n.
  \end{equation}
\end{enumerate}
Note that the last equation is just a reformulation of~\ref{item:5} in terms of
the \(b_i^{(n)}\).

Now we carry out the recursive definition. We can start with
\(b_i^{(i)}:=0\). Observe that \ref{item:15} determines how to define
\(b_i^{(n+1)}\): the left-hand side is an element of \(B_{n+1}\), a free
abelian group with basis \(x_h y\) for \(h \in H\) and \(y\) a sequence of \(0\)
and \(1\) of length \(n+1\). We divide the coefficient of every \(x_h y\) by
\(s_n t_n\). The quotient gives the coefficient of \(x_h y\) in
\(b_i^{(n+1)}\) and the remainder is a coefficient of the big sum on the
right. Since the support of the left-hand side is contained in \(F_i\) by
induction, the same is true for \(b_i^{(n+1)}\) and the sum on the right-hand
side.  The left-hand side is actually contained in \(B_n\) not only
\(B_{n+1}\). This means that the coefficients of sequences of length \(n+1\)
ending with \(1\) are divisible by \(s_n^2\) by~\ref{item:4} and hence by
\(s_n t_n\) since \(t_n\) divides \(s_n\). So in the sum on the right-hand
side, the coefficient of sequences ending with \(1\) is zero. Thus we have
defined \(b_i^{(n+1)}\) according to the requirements.
\end{proof}

\subsection{The partial order}
\label{sec:partial-order}

In this subsection we define a partial order on \(D\) which will make it a
dimension group.

\begin{proposition}\label{prop:4}
  Let \(H \leq \setQ_+^\times\) be a subgroup of the multiplicative group of the positive
  rational numbers acting on \(\setQ u\) by multiplication. Suppose \(G\) is a
  group satisfying the conditions of Proposition~\ref{prop:3}. Let \(H\) act
  on \(D := \setQ u \oplus G\) componentwise. Then there is a partial order \(\leq\) on
  \(D\) such that \((D, \leq, u)\) is a dimension group on which \(H\) acts by
  order-preserving automorphisms.
\end{proposition}

The dimension group \(D\) in the \hyperref[prop:4]{proposition} satisfies all
requirements of Theorem~\ref{th:2}.  We shall see in the
\hyperref[sec:autom-dimens-groups]{next section} that the group of
order-preserving automorphisms of \(D\) is exactly \(H\). The other
requirements are obviously satisfied.

\begin{proof}
We define the partial order on a larger group, the divisible hull \(\setQ D\) of
\(D\).  For all natural number \(n\) and finite subset \(F\) of \(H\) we
define a subgroup of \(D\):
\begin{equation}
  \label{eq:5}
  D_{n,F} := \setZ \frac{u}{k_n} \oplus \bigoplus_{\substack{h \in F \\ y \in \nSeq}} \setZ x_hy \oplus
  \bigoplus_{\substack{i=1 \\ h \in F}}^n \setZ x_hc_i^{(n)}.
\end{equation}
We define the partial order on \(\setQ D_{n,F}\) as the product order
\begin{equation}
  \label{eq:6}
  (\setQ D_{n,F}, \leq) := (\setQ v_{n,F}, \leq) \times \prod_{\substack{h \in F \\ y \in \nSeq}} (\setQ x_hy, \leq) \times
  \prod_{\substack{i=1 \\ h \in F}}^n (\setQ x_hc_i^{(n)}, \leq)
\end{equation}
where
\begin{equation}
  \label{eq:7}
  v_{n,F} := \frac{u}{k_n} - \sum_{h \in F} h^{-1} x_h
  \left(
    k_n \sum_{y \in \nSeq} y +
    l_n \sum_{i=1}^n c_i^{(n)}
  \right).
\end{equation}
Note that this makes \(u\) an order unit of \(\setQ D_{n,F}\).

The subgroups \(D_{n,F}\) form a directed system whose union is the whole
\(D\). It follows that the subgroups \(\setQ D_{n,F}\) form a directed system
whose union is \(\setQ D\).

We are in a position now to reduce the proof to two lemmas stated below.  The
\hyperref[lem:3]{first one} states that the inclusions between the \(\setQ
D_{n,F}\) are order-embeddings.  The \hyperref[lem:4]{second one} claims that
a cofinal set of the \(D_{n,F}\) is order-isomorphic to a direct product of
finitely many copies of \((\setZ, \leq)\).

It follows that \(\setQ D\) has a unique partial order which extends the partial
order of all the \(\setQ D_{n,F}\).  Under this partial order \(u\) is clearly an
order-unit.  The \(D_{n,F}\) provide enough order-subgroups isomorphic to a
finite direct power of \((\setZ, \leq)\), hence \((D, \leq, u)\) is a dimension group.

The partial order is preserved by \(H\) since any \(h \in H\) maps \(\setQ D_{n,F}\)
bijectively onto \(\setQ D_{n,hF}\) and this bijection is an order-isomorphism of
the two subgroups. (Note that \(x_hv_{n,F} = h v_{n,hF}\).)

Thus \((D, \leq, u)\) have all the properties claimed.

All in all, the proposition is proved modulo the following two lemmas.
\end{proof}

\begin{lemma}
  \label{lem:3}
  The inclusions between the subgroups \(\setQ D_{n,F}\) are order-embeddings.
\end{lemma}

\begin{lemma}
  \label{lem:4}
  A cofinal set of the groups \(D_{n,F}\) is order-isomorphic to a finite direct
  power of \((\setZ, \leq)\).
\end{lemma}

We consider first the inclusions.

\begin{proof}[Proof of Lemma~\ref{lem:3}]
First we prove the claim that \(\setQ D_{n,F}\) is an order-subgroup of \(\setQ
D_{n+1,F'}\) if \(F'\) contains \(F\) and \(FF_i\) for all \(i \leq n\).
For this, it is good to have the following general example of an
order-embedding of \((\setQ, \leq)^m\) into \((\setQ, \leq)^{m+k}\) given by a matrix:
\begin{equation}
  \label{eq:28}
  \begin{pmatrix}
        >0 & 0  & \ldots & 0               & \geq0 & \ldots & \geq0\\
    0  & >0 & 0  & \vdots               & \geq0 & \ldots & \geq0\\
    \vdots  &    & \ddots  & \vdots               & \vdots  &  \vdots  & \vdots \\
    0  & \ldots & 0  & >0              & \geq0 & \ldots & \geq0\\
  \end{pmatrix}.
\end{equation}
On the first \(m\) coordinates this is an order-isomorphism: every coordinate
is multiplied by a positive number. On the last \(k\) coordinates the map is
an arbitrary order-preserving map. By permutating the coordinates, we may
complicate the map.

All in all, a homomorphism \((\setQ, \leq)^m \to (\setQ, \leq)^M\) is an order-embedding if
the canonical basis elements of the domain have only nonnegative coordinates
in the codomain and every basis element has a positive coordinate, which
coordinate is zero for the other basis elements.

We show that the inclusion of \(\setQ D_{n,F}\) into \(\setQ D_{n+1,F'}\) is an
order-embedding of the above type using the direct product
decomposition~\eqref{eq:6}.  To this end, we express the generators of \(\setQ
D_{n,F}\) as linear combination of the generators of \(\setQ D_{n+1,F'}\) (which
in particular shows that \(\setQ D_{n,F}\) is really a subgroup of \(\setQ
D_{n+1,F'}\)):
\begin{align}
  \label{eq:8}
  x_h y &= x_h \cdot y0 + s_n^2 x_h \cdot y1 & y \in \nSeq,\, &h \in F\\
  \label{eq:9}
  x_h c_i^{(n)} &= s_n t_n x_h c_i^{(n+1)} + \sum_{\substack{t \in F_i \\ y \in
      \nSeq}} n_{t,y}^{(i)} x_{ht} \cdot y0 & i \leq n,\, &h \in F\\
  \label{eq:10}
  v_{n,F} &=
  \begin{aligned}[t]
    s_n v_{n+1,F'} &+ \sum_{h \in F'} s_n l_{n+1} h^{-1} x_h c_{n+1}^{(n+1)}\\
    &+ \sum_{\substack{h \in F' \setminus F \\ i \leq n}} s_n l_{n+1} h^{-1} x_h c_i^{(n+1)}\\
    &+ \sum_{\substack{h \in F \\ y \in \nSeq}} k_n (s_n^2 - 1) h^{-1} x_h \cdot y0\\
    &+ \sum_{\substack{h \in F' \setminus F \\ y \in \nSeq[n+1]}} k_n s_n^2 h^{-1} x_h y\\
    &- \sum_{\substack{h \in F, i \leq n \\t \in F_i, y \in \nSeq}} l_n n_{t,y}^{(i)}
    h^{-1} x_{ht} \cdot y0
  \end{aligned}
\end{align}
These are easy consequences of the formulas under~\ref{item:12} of
Proposition~\ref{prop:3} and the definition~\eqref{eq:7} of \(v_{n,F}\).  All
the coordinates of the above generators are obviously nonnegative except for
the coefficient of \(x_h y0\) of \(v_{n,F}\) for \(y \in \nSeq\) and \(h \in F'\).
So let us consider the coefficient of \(h^{-1} x_h y0\) in
Equation~\eqref{eq:10}: from the third or forth row comes \(k_n (s_n^2-1)\)
or \(k_n s_n^2\) depending on whether \(h\) is contained in \(F\).  From the
last row \(- l_n n_{t,y}^{(i)} t\) comes for all \(t \in F_i\) and \(i \leq n\) for
which \(h t^{-1}\) lies in \(F\).  All in all, the coefficient is at least
\begin{equation}
  \label{eq:13}
  k_n (s_n^2 - 1) - \sum_{t \in F_i, i \leq n} l_n n_{t,y}^{(i)} t \geq k_n (s_n^2 -
  1) - \sum_{t \in F_i, i \leq n} l_n s_n t_n t \geq 0
\end{equation}
by \ref{item:9} from Proposition~\ref{prop:3}.

Now we check that each of the above generators of \(\setQ D_{n,F}\) has a positive
coordinate in \(\setQ D_{n+1,F'}\) which coordinate is zero for the other
generators. This coordinate is \(x_h y1\) for \(x_h y\) where \(h \in F\) and
\(y \in \nSeq\); it is \(x_h c_i^{(n+1)}\) for \(x_h c_i^{(n)}\) where \(h \in F\)
and \(i \leq n\); finally, it is \(v_{n+1,F'}\) for \(v_{n,F}\).

So far we have proved that \(\setQ D_{n,F}\) is an order-subgroup of \(\setQ
D_{n+1,F'}\) if \(F'\) contains \(F\) and \(FF_i\) for \(i \leq n\).  It follows
by induction on \(m-n\) that for every \(n\) and \(F\) and \(m>n\) there is a
finite subset \(S\) of \(H\) such that \(\setQ D_{n,F}\) is an order-subgroup of
\(\setQ D_{m,F'}\) if \(F'\) contains \(S\).  Hence, if \(\setQ D_{n,F}\) is a
subgroup of \(\setQ D_{k,C}\) then both are order-subgroups of \(\setQ D_{m,F'}\) for
suitable \(m\) and \(F'\), hence \(\setQ D_{n,F}\) must be an order-subgroup of
\(\setQ D_{k,C}\).  This shows that the inclusions between the \(\setQ D_{n,F}\) are
order-embeddings.
\end{proof}

Now we return to our second lemma, namely that a cofinal subset of the
\(D_{n,F}\) are order-isomorphic to a finite power of \(\setZ\).
\begin{proof}[Proof of Lemma~\ref{lem:4}]
If \(n\) is a natural number and \(F\) is a finite subset of \(H\) such that
for all \(h \in H\) the rational numbers \(k_n h^{-1}\) and \(l_n h^{-1}\) are
actually integers then the coefficients of the \(x_h y\) in~\eqref{eq:7} are
integers and hence
\begin{equation}
  \label{eq:11}
  (D_{n,F}, \leq) := (\setZ v_{n,F}, \leq) \times \prod_{\substack{h \in F \\ y \in \nSeq}} (\setZ x_hy, \leq) \times
  \prod_{\substack{i=1 \\ h \in F}}^n (\setZ x_hc_i^{(n)}, \leq).
\end{equation}
We show that such \(D_{n,F}\) form a cofinal system i.e., every \(D_{n,F}\) is
contained in a \(D_{m,F'}\) which has the above property. This is easy once we
know that \(D_{n,F}\) is contained in \(D_{m,F'}\) if \(m \geq n\) and \(F'\)
contains \(F\) and \(FF_i\) for \(i \leq n\). This last statement follows form
the fact that \(x_hc_i^{(n)}\) is contained in \(D_{m,F'}\) if \(m \geq n\) and
\(h\) and \(hF_i\) are contained in \(F'\).  This fact can be proved by
induction on \(m-n\): the case \(m=n\) is obvious because \(h \in F'\).  If \(m >
n\) then \(x_h c_i^{(n+1)}\) is contained in \(D_{m,F'}\) by induction and
\(x_h (c_i^{(n)} - s_n t_n c_i^{(n+1)})\) is also contained in \(D_{m,F'}\) by
Equation~\eqref{eq:12} since \(hF_i\) is contained in \(F'\).
\end{proof}

\section{Automorphisms of dimension groups}
\label{sec:autom-dimens-groups}

In this section we prove that \(H\) is the full group of order-preserving
automorphisms of \(D\) constructed in Proposition~\ref{prop:4}, which finishes
the proof of our \hyperref[th:2]{main theorem}.  This is a special case of the following
proposition, which we are going to prove in this section.
Note that \(D / \setQ u = G\) has the required automorphism group.

\begin{proposition}
  \label{prop:2}
  Let \((D, \leq, u)\) be a dimension group of rank at least \(3\) on which a
  group \(H\) acts by order-preserving automorphisms (the order unit need not
  be preserved).  Let us suppose that the maximal divisible subgroup of \(D\)
  is \(\setQ u\). Furthermore, let us assume that
  \begin{equation}
    \label{eq:4}
    \Aut D / \setQ u = \pm H = \setZ/2\setZ (-1) \times H
  \end{equation}
  i.e., the automorphisms of \(D / \setQ u\) are those induced by \(H\) and their
  negatives. Then \(\Aut (D, \leq) = H\). In other words, all the order-preserving
  automorphisms of \(D\) are those coming from \(H\).
\end{proposition}

We base our proof on the comparison of multiples of \(u\) with elements of
\(D\). This can be described by some rational numbers:
\begin{definition}
  \label{def:1}
  Let \((D, \leq, u)\) be a dimension group. Then for every element \(d\) of
  \(D\) we denote by \(r(d)\) the least rational number \(q\) such that \(q u
  \geq d\). Similarly, let \(l(d)\) denote the greatest rational number \(q\)
  with the property \(q u \leq d\). In other words, for all rational numbers
  \(q\):
  \begin{align}
    \label{eq:20}
    q u \geq d &\iff q \geq r(d),\\
    \label{eq:21}
    q u \leq d &\iff q \leq l(d).
  \end{align}
\end{definition}

We collect the main (and mostly obvious) properties of the functions \(r\) and
\(l\) in the following lemma:
\begin{lemma}
  \label{lem:1}
  Let \((D, \leq, u)\) be a dimension group and \(d\) and element of it. Then the
  following hold:
  \begin{enumerate}[label=(\alph*)]
  \item \label{item:16} The numbers \(r(d)\) and \(l(d)\) exist.
  \item \label{item:17} We have \(l(d)=r(d)=0\) if and only if \(d=0\).
  \item \label{item:19} \(r(-d) = - l(d)\) and \(l(-d)=-r(d)\).
  \item \label{item:22} For all rational numbers \(s\):
    \begin{align}
      r(d+su) &= r(d) + s,\\
      l(d+su) &= l(d) + s.
    \end{align}
  \item \label{item:18} If \(\Phi\) is an order-preserving automorphism of \(D\)
    and \(\Phi(u) = q u\) then
    \begin{align}
      \label{eq:22}
      l(\Phi(d)) &= q l(d),\\
      \label{eq:23}
      r(\Phi(d)) &= q r(d).
    \end{align}
  \item \label{item:20} If \(D\) has rank at least \(3\), the function \(d \mapsto
    l(d) + r(d)\) from \(D\) to the additive group of rational numbers is not
    additive. (It is additive if the rank of \(D\) is at most \(2\).)
  \end{enumerate}
\end{lemma}

\begin{proof}
To prove the existence of \(l(d)\) and \(r(d)\), we may restrict ourselves to
an order-subgroup \((\setZ, \leq)^k\) containing \(d\) and \(u\). Such a subgroup
exists by the definition of dimension group. Clearly, \(u=(n_1,\dotsc,n_k)\)
remains an order unit in the subgroup i.e., its coordinates \(n_i\) are
positive. For every element \((m_1,\dotsc,m_k)\) of \((\setZ, \leq)^k\) the functions
\(r\) and \(l\) are clearly well-defined and have the values
\begin{align}
  \label{eq:24}
  r(m_1,\dotsc,m_k) &= \max_{1 \leq i \leq k} \frac{m_i}{n_i},\\
  \label{eq:25}
  l(m_1,\dotsc,m_k) &= \min_{1 \leq i \leq k} \frac{m_i}{n_i}.
\end{align}
These formulas also show that \(r(d)=l(d)=0\) if and only if \(d=0\). If \(D\)
has rank at least \(3\) then there is an order-subgroup  \((\setZ,
\leq)^k\) of \(D\) containing \(u\) with \(k \geq 3\). We can deduce from the above
formulas that \(r+l\) is not additive even when restricted to such a subgroup.
For example, for the elements \(e_i\) whose \(i\)th coordinate is \(1\) and
all the other coordinates \(0\), we have \(r(e_1)=r(e_2)=r(e_1+e_2)=1\) and
\(l(e_1)=l(e_2)=l(e_1+e_2)=0\), and so \(r(e_1+e_2)+l(e_1+e_2) \neq r(e_1) +
l(e_1) + r(e_2) + l(e_2)\).

The remaining items~\ref{item:19}, \ref{item:22} and \ref{item:18} are obvious.
\end{proof}

Now we start proving the proposition. First we split the order-preserving
automorphism group of \(D\).
\begin{lemma}
  \label{lem:2}
  With the hypothesis and notation of Proposition~\ref{prop:2}, let us denote
  by \(\Gamma\colon \Aut (D, \leq) \to \Aut D / \setQ u\) the canonical map, i.e., \(\Gamma(f)\) is
  the automorphism induced by \(f\) on the quotient. Then there is a
  semidirect product decomposition
  \begin{equation}
    \label{eq:26}
    \Aut (D, \leq) = \Gamma^{-1}(\setZ/2\setZ) \rtimes H,
  \end{equation}
where \(\setZ/2\setZ\) is generated by \(-1\).
\end{lemma}

\begin{proof}
Note that \(\setQ u\) is invariant under automorphisms since it is the largest
divisible subgroup, so \(\Gamma\) is well-defined. Note that the composition
\begin{equation}
  \label{eq:27}
  H \longrightarrow \Aut (D, \leq) \xrightarrow{\Gamma} \Aut (D / \setQ u) = \setZ/2\setZ \times H \longrightarrow H
\end{equation}
is the identity, which implies the claimed decomposition as a semidirect
product. Here the first arrow is the inclusion of \(H\) given by the
\(H\)-action on \(D\) and the last arrow is projection onto the second
coordinate.
\end{proof}

Now we show that the first term of the semidirect product is trivial, which
finishes the proof.

To this end, we choose an order-preserving automorphism \(\Phi \in \Gamma^{-1}(\setZ/2\setZ)\)
and show that it is the identity. By the choice of \(\Phi\), there is a number
\(\varepsilon=\pm1\) such that the image of \(\Phi-\varepsilon\) is contained in \(\setQ u\). Moreover,
since \(\setQ u\) is invariant, there is a positive rational number \(q\) such that
\(\Phi(u)=qu\).

Our first task is to show that \(q=1\). Therefore we select a nonzero element
\(d\) in the kernel of \(\Phi - \varepsilon\). Since \(\Phi - \varepsilon\) maps to a \(1\)-rank group
\(\setQ u\) and the rank of \(D\) is greater than \(1\), such an element \(d\)
exists.  Now we use Lemma~\ref{lem:1}~\ref{item:18}.  If \(\varepsilon=1\), we obtain
\(r(d)=qr(d)\) and \(l(d)=ql(d)\) and thus \(q=1\) since \(r(d)\) and \(l(d)\)
are not both zero.  If \(\varepsilon=-1\) then \(r(d)=-ql(d)\) and \(l(d)=-qr(d)\).
Again, since at least one of \(r(d)\) and \(l(d)\) is not zero and \(q\) is
positive, \(q\) must be \(1\).

So far we know that \(\Phi(u)=u\). Let \(d\) be an arbitrary element of
\(D\). Then there is a rational number \(s\) depending on \(d\) such that
\(\Phi(d)=\varepsilon d + su\). Our next task is to determine \(s\).

We apply Lemma~\ref{lem:1} again, but this time item \ref{item:22} of it.  If
\(\varepsilon=1\) then \(r(d) = r(d) + s\) and \(l(d) = l(d) + s\).  We conclude that
\(s=0\) for all \(d\).  In other words, \(\Phi\) is the identity.  If \(\varepsilon=-1\)
then we have \(r(d) = s - l(d)\) and \(l(d) = s - r(d)\).  Thus \(s = r(d) +
l(d)\) for all \(d\), which means that \(\Phi(d) = d - (r(d) + l(d)) u\).  So
\(r+l\) is an additive function contradicting Lemma~\ref{lem:1}~\ref{item:20}.

Hence we have proved that \(\Phi=1\) and this finishes the proof.
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
\providecommand{\MRhref}[2]{\href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}


TITLE: Variance and expected values by dices, how does addition work?
QUESTION [3 upvotes]: I have read through some stuff and I am confused now.
If we have a fair die and we just roll once, the expected value is going to be 3,5 and the variance is 2,916.
Well, it is easy to count by one die, but if we have 8 dice (6 sides) and we are interested in the sum of the roll, then the calculation can get really messy if we start to write up the chances of every possible outcome.
Luckily, the expected value is easy to count, it stays in the middle, so in this case, it's 28.
But the variance seems to be more difficult, it seems to me because the chances of the outcomes may vary who knows how.
Is there a formula you know about to count the variance in this situation, or do I have to write up all possibilities and count the probabilities?
Thanks

REPLY [1 votes]: Let the dice be labelled $1,2,3,\dots,8$. Let random variable $X_i$ be the number showing on die $i$. Then our sum $Y$ is equal to $X_1+\cdots+X_8$.
The variance of a sum of independent random variables is the sum of the variances. Thus $Y$ has variance $\text{Var}(X_1)+\cdots +\text{Var}(X_8)$. The variances of the $X_i$ are all equal, and you know them, so you know the variance of $Y$.
Remark: The distribution of $Y$ can be found, but it is a quite messy and lengthy business. In principle we could find this distribution, and use it to compute the variance of $Y$. Luckily, there is a much easier way to do it!