text:
\section{Stochastic Approaches}
Batch algorithms such as BCD and GN could have serious memory and computational issues, especially when the data tensor or matrix is large and dense.
Recall that the MTTKRP (i.e., $\H_n^\T\X_n$) costs ${\cal O}(R\prod_{n=1}^N I_n)$ operations, if no structure of the tensor can be exploited. This is quite expensive for large $I_n$ and high-order tensors.
For big data problems, stochastic optimization is a classic workaround for avoiding memory/operation explosion. In a nutshell, stochastic algorithms are particularly suitable for handling problems having the following form:
\begin{equation}\label{eq:emprical}
    \min_{\bm \theta}~\frac{1}{L}\sum_{\ell=1}^L f_\ell(\bm \theta) + h(\bm \theta),
\end{equation}
where the first term is often called the ``empirical risk'' function in the literature.
The classic stochastic proximal gradient descent (SPGD) updates the optimization variables via
\begin{equation}\label{eq:stopgd}
 \bm \theta^{(t+1)}\leftarrow {\sf Prox}_h\left(\bm \theta^{(t)} - \alpha^{(t)} \bm g(\bm \theta^{(t)}) \right),
\end{equation}
where $\bm g(\bm \theta^{(t)}) $ is a random vector (or, ``stochastic oracle'') evaluated at $\bm \theta^{(t)}$, constructed through a random variable (RV) $\xi^{(t)}$.
The idea is to use an easily computable stochastic oracle to approximate the computationally expensive full gradient $\nabla f(\bm \theta)=\frac{1}{L}\sum_{\ell=1}^L \nabla f(\bm \theta)$, so that \eqref{eq:stopgd} serves as an economical version of the PGD algorithm.
A popular choice is $\bm g(\bm \theta^{(t)}) =\nabla f_\ell(\bm \theta^{(t)})$, where $\ell\in\{1,\ldots,L\}$ is randomly selected following the probability mass function (PMF) ${\sf Pr}(\xi^{(t)}=\ell)=1/L$. This simple construction has a nice property: $\bm g(\bm \theta^{(t)}) $ is an unbiased estimator for the full gradient given the history of random sampling, i.e., $$\nabla f(\bm \theta^{(t)})=\frac{1}{L}\sum_{\ell=1}^L \nabla f_\ell(\bm \theta^{(t)})=\mathbb{E}_{\xi^{(r)}}\left[  \bm g(\bm \theta^{(t)}) | {\cal H}^{(t)} \right],$$
where ${\cal H}^{(t)}$ collects all the RVs appearing before iteration~$t$.
The unbiasedness is often instrumental in establishing convergence of stochastic algorithms\footnote{Biased stochastic oracle and its convergence properties are also discussed in the literature; see, e.g., \cite{xu2015block}. However, the analysis is more involved. In addition, some conditions (e.g., bounded bias) are not easy to verify.}.
Another very important aspect is the variance of $\bm g(\bm \theta^{(t)}) $. Assume that the variance is bounded, i.e.,  $\mathbb{V}\left[  \bm g(\bm \theta^{(t)}) | {\cal H}^{(t)} \right] \leq \tau.$
Naturally, one hopes $\tau$ to be small---so that the average deviation of $\bm g(\bm \theta^{(t)})$ from the full gradient is small---and thus the SPGD algorithm will behave more like the PGD algorithm.
Smaller $\tau$ can be obtained via using more samples to construct  $\bm g(\bm \theta^{(t)})$, e.g., using
$$
\bm g(\bm \theta^{(t)})=\frac{1}{|{\cal B}^{(t)}|}\sum_{\ell\in {\cal B}^{(t)} }\nabla f_\ell(\bm \theta^{(t)}),
$$
where ${\cal B}^{(t)}$ denotes the index set of the $f_\ell(\bm \theta^{(t)})$'s sampled at iteration $t$. This leads to the so-called ``mini-batch'' scheme. Note that if $|{\cal B}^{(t)}|=L$, then $\tau=0$ and SPGD becomes the PGD.
As we have mentioned, a smaller $\tau$ would make the convergence properties of SPGD more like the PGD, and thus is preferred.
However, a larger $|{\cal B}^{(t)}|$ leads to more operations for computing the stochastic oracle.
In practice, this is a tradeoff that oftentimes requires some tuning to balance.

The randomness of stochastic algorithms makes characterizing the convergence properties of any single instance not meaningful.
Instead, the ``expected convergence properties'' are often used. For example, when $h(\bm \theta)$ is absent,  a convergence criterion of interest is expressed as follows:
\begin{equation}\label{eq:totalexpect}
     \liminf_{t\rightarrow \infty}{\mathbb{E}\left[ \left\|\nabla f\left(\bm \theta^{(t)}\right)\right\|_2^2 \right]}= 0,
\end{equation}
where the expectation is taken over all the random variables that were used for constructing the stochastic oracles for all the iterations (i.e., the ``total expectation").
Equation~\eqref{eq:totalexpect} means that every limit point of $\{ \bm \theta^{(t)} \}$ is a stationary point {\it in expectation}. When $h(\bm \theta)$ is present, similar ideas are utilized. Recall that $\bm 0\in \partial F(\bm \theta^{(t)})$ is the necessary condition for attaining a stationary point [cf.\ Eq.~\eqref{eq:convergence}].
In \cite{xu2015block}, the expected counterpart of \eqref{eq:convergence}, i.e.,
\begin{equation}\label{eq:constrainedexpct}
\liminf_{t\rightarrow \infty}\mathbb{E}[{\rm dist}(\bm 0, \partial F(\bm \theta^{(t)}) ) ]=0
\end{equation}
is employed for establishing the notion of stationary-point convergence for nonconvex nonsmooth problems under the stochastic settings.
For both \eqref{eq:totalexpect} and \eqref{eq:constrainedexpct}, when some more assumptions hold (e.g., the solution sequence is bounded), the ``$\inf$'' notation can be removed, meaning that the whole sequence converges to a stationary point on average.

\subsection{Entry Sampling}
Many SLRD problems can be re-expressed in a similar form as that in \eqref{eq:emprical}.
One can rewrite the constrained CPD problem under the least squares fitting loss as follows:
\begin{equation}\label{eq:cpd_entry}
\begin{aligned}
\min_{\{\A_{n}\}_{n=1}^N}&~\frac{1}{L}\sum_{i_1=1}^{I_1}\ldots \sum_{i_N=1}^{I_N}{f_{i_1,\ldots,i_N}(\bm \theta)}+{h(\bm \theta)}

\end{aligned}
\end{equation}
where $L=\prod_{n=1}^N I_n$, $h(\bm \theta)={\sum_{n=1}^Nh_n(\A_n)}$ and $f_{i_1,\ldots,i_N}={( {\cal T}(i_1,\ldots,i_N)-\sum_{r=1}^R \prod_{n=1}^N \A_n(i_n,r))^2}$.
Assume ${\cal B}^{(t)}$ is a set of indices of the tensor entries that are randomly sampled [see Fig.~\ref{fig:sampling-strategies} (left)].
The corresponding SPGD update is as follows: $\bm \theta^{(t+1)}$ is given by
\begin{align}\label{eq:spgd}
   {\sf Prox}_h\bigg(\bm \theta^{(t)} -\frac{\alpha^{(t)}}{|{\cal B}^{(t)}|} \sum_{(i_1,\ldots,i_N)\in{\cal B}^{(t)}} \nabla f_{i_1,\ldots,i_N}\big(\bm \theta^{(t)}\big) \bigg).
\end{align}
It is not difficult to see that many entries of $\nabla f_{i_1,\ldots,i_N}(\bm \theta^{(t)})$ are zero, since $\nabla f_{i_1,\ldots,i_N}(\bm \theta^{(t)})$ only contains the information of $\A_{n}(i_n,:)$; we have

$\left[\nabla f_{i_1,\ldots,i_N}(\bm \theta^{(t)})\right]_g = 0$ for all $\theta_g \notin \{ \A_n(i_n,r)~|~(i_1,\ldots,i_N)\in{\cal B}^{(t)}\}$.

The derivative w.r.t. $\A_n(i_n,:)$ for the sampled indices is easy to compute; see \cite{sidiropoulos2017tensor}.
This is essentially the idea in \cite{beutel2014flexifact} for coupled tensor and matrix decompositions. This kind of sampling strategy ensures that the constructed stochastic oracle is an unbiased estimation for the full gradient, and features very lightweight updates. Computing the term $\sum_{{\cal B}^{(t)}}\nabla f_{i_1,\ldots,i_N}(\bm \theta^{(t)})$ requires only ${\cal O}(R|{\cal B}^{(t)}|)$ operations, instead of ${\cal O}(R\prod_{n=1}^N I_n )$ operations for computing the full gradient.

\definecolor{basecolor}{RGB}{0,85,165}

\begin{figure}[htp]
	\centering
	\begin{tikzpicture}[
	all tensors/.append style={tensor scale=0.13, 2d, anchor=A},
	elm/.style={tensor, dim={1,1,1},fill=basecolor!60!white,draw=basecolor},
	pil/.style={ <-, shorten <=2pt,  shorten >=4pt,}]

	\node [tensor, dim={10,15,7}, only back faces, dashed back lines,draw=basecolor] (T1) {};
	\node at (T1.3 15 3) [elm] {};
	\node at (T1.1 5 6) [elm] (t11){};
	\node at (T1.3 9 2) [elm] {};
	\node at (T1.9 2 7) [elm] {};
	\node at (T1.9 12 4) [elm] {};
	\node at (T1.A) [tensor, dim={10,15,7}, anchor=A, fill opacity=0.2,
	fill=basecolor, draw=basecolor] (T1) {};

	\draw [pil,shorten >=1pt] ($(t11.A)!0.5!(t11.G)$) to [pil,bend left] ++(0.3,0.3) node
	[font=\footnotesize,anchor=west, inner sep=0pt] {$t_{ijk}$};

	\node at (T1.C) [tensor, dim={10,15,7}, only back faces, dashed back
	lines,draw=basecolor, anchor=A, xshift=1cm] (T2) {};
	\node at (T2.7 5 4) [elm] {};
	\node at (T2.7 6 4) [elm] {};
	\node at (T2.4 5 4) [elm] (t21) {};
	\node at (T2.4 6 4) [elm] {};
	\node at (T2.4 5 3) [elm] {};
	\node at (T2.4 6 3) [elm] {};
	\node at (T2.7 5 3) [elm] {};
	\node at (T2.7 6 3) [elm] {};
	\node at (T2.A) [tensor, dim={10,15,7}, anchor=A, fill opacity=0.2,
	fill=basecolor, draw=basecolor] (T2) {};

	\draw [pil,shorten >=1pt] ($(t21.A)!0.5!(t21.G)$) to [pil,bend left] ++(0.3,0.8) node
	[font=\footnotesize,anchor=west, inner sep=0pt] {$\ten{T}_{\text{sub}}$};

	\node at (T2.C) [tensor, dim={10,15,7}, only back faces, dashed back
	lines,draw=basecolor, anchor=A, xshift=1cm] (T3) {};
	\node at (T3.1 12 4) [elm,dim={10,1,1}] (t31) {};
	\node at (T3.2 3 1) [elm,dim={1,15,1}] (t32) {};
	\node at (T3.9 5 1) [elm,dim={1,1,7}] (t33) {};
	\node at (T3.A) [tensor, dim={10,15,7}, anchor=A, fill opacity=0.2,
	fill=basecolor, draw=basecolor] (T3) {};

	\draw [pil,shorten >=1pt] ($(t31.A)!0.5!(t31.G)$) to [pil,bend left] ++(0.3,0.4) node
	[font=\footnotesize,anchor=south west, inner sep=0pt] {mode 1};

	\draw [pil,shorten <=3pt,shorten >=1pt] (t32) to [pil,bend right] ++(-0.3,0.7) node
	[font=\footnotesize,anchor=south east,inner sep=0pt] {mode 2};

	\draw [pil,shorten <=1pt, shorten >=1pt] (t33.D) to [pil,bend right] ++(0.3,-0.35) node
	[font=\footnotesize,anchor=west,inner sep=0pt] {mode 3};

	\node at (T1) [yshift=-1.4cm,font=\footnotesize] {entry};
	\node at (T2) [yshift=-1.4cm,font=\footnotesize] {subtensor};
	\node at (T3) [yshift=-1.4cm,font=\footnotesize] {fiber};

	\end{tikzpicture}
	\vspace{-5mm}
	\caption{Various sampling strategies used in stochastic optimization
		algorithms.}
	\label{fig:sampling-strategies}
	\vspace{-.5cm}
\end{figure}

\subsection{Subtensor Sampling}
Entry-sampling based approaches are direct applications of the conventional PSGD for tensor decomposition. However, these methods do not leverage existing tensor decomposition tools.
One way to take advantage of existing tensor decomposition algorithms is sampling subtensors, instead of entries.
The {\em randomized block sampling} (RBS) algorithm \cite{vervliet2016randomized} considers the unconstrained CPD problem. The algorithm samples a subtensor
$$
{\cal T}_{\rm sub}^{(t)}={\cal T}({\cal S}_1,\ldots,{\cal S}_N) \approx \sum_{r=1}^R \A_1({\cal S}_1,r)\circ \ldots \circ \A_N({\cal S}_N,r)
$$
at every iteration $t$ and updates the latent variables by computing \emph{one} optimization step using:
\begin{equation}\label{eq:RBS}
\begin{aligned}
\bm \theta_{\rm sub}^{(t+1)} &\leftarrow \arg\min_{\bm \theta_{\rm sub}} \left\|{\cal T}_{\rm sub}^{(t)}-\llbracket \A_1^{\rm sub}, \ldots, \A_N^{\rm sub}\rrbracket\right\|^2_{\rm F},\\
\bm \theta_{\rm -sub}^{(t+1)}& \leftarrow \bm \theta_{\rm -sub}^{(t)},
\end{aligned}
\end{equation}
where all variables affected by ${\cal T}_{\rm sub}^{(t)}$ are collected in $\bm \theta_{\rm sub}=[{\rm vec}(\A_1^{\rm sub});\ldots,{\rm vec}(\A_N^{\rm sub})]$, $\A_n^{\rm sub}=\A_n({\cal S}_n,:)$, and $\bm \theta_{\rm -sub}$ contains all the other optimization variables. As each update in \eqref{eq:RBS} involves one step in a common tensor decomposition problem, many off-the-shelf algorithms, such as ALS or GN, can be leveraged \cite{vervliet2016randomized}.

The above algorithm works well, especially when the tensor rank is low and the sampled subtensors already have identifiable latent factors---under such cases, the estimated $\A_n^{\rm sub}$ from subtensors can serve as a good estimate for the corresponding part of $\A_n$ after one or two updates.
In practice, one needs not to exactly solve the subproblems in \eqref{eq:RBS}. Combining with some trust region considerations, the work in \cite{vervliet2016randomized} suggested using a one-step GN or one-step regularized ALS to update $\bm \theta_{\rm sub}$.
Note the sampled subtensors

are typically not independent under this framework, since one wishes to update every unknown parameter in an equally frequent way; see~\cite{vervliet2016randomized}. This is quite different from established conventions in stochastic optimization, which makes convergence analysis for RBS more challenging than the entry sampling based methods.

\subsection{Fiber Sampling}

In principle, the entry sampling and SPGD idea in \eqref{eq:spgd} can handle any $h(\cdot)$ that admits simple proximal operators.
In addition, the RBS algorithm can be applied together any constraint compatible with the GN framework as well.
However, such sampling strategies are no longer viable when it comes to constraints/regularizers that are imposed on the columns of the latent factors, e.g.,
the probability simplex constraint that is often used in statistical learning $(\bm 1^\T\A_n =\bm 1^\T,~\bm A_n\geq \bm 0)$, the constraint
$\|\A_n\|_{2,1}=\sum_{i_n=1}^{I_N}\|\A_n(i_n,:)\|_2$ used for promoting row-sparsity, or the total variation/smoothness regularization terms on the columns of $\A_n$.
The reason is that ${\cal T}_{\rm sub}$ only contains information of $\A_n({\cal S}_n,:)$---which means that enforcing column constraints on $\bm A_n$ is not possible if updates in \eqref{eq:spgd} or \eqref{eq:RBS} are employed.

Recently, the works in \cite{battaglino2018practical,fu2019block} advocate to sample a (set of) mode-$n$ ``fibers'' for updating $\A_n$. A mode-$n$ fiber of the tensor ${\cal T}$ is an $I_n$-dimensional vector that is obtained by varying the mode-$n$ index while fixing others of ${\cal T}$ [see Fig.~\ref{fig:sampling-strategies} (right)]. The interesting connection here is that
\begin{align*}
\underbrace{{\cal T}(i_1,\ldots,i_{n-1},:,i_{n+1},\ldots,i_N)}_{\text{a mode-$n$ fiber}}
=\X_n(j_n,:),
\end{align*}
where $j_n=1+\sum_{\ell=1,\ell\neq n}(i_\ell-1)J_\ell$ and $J_\ell=\prod_{m=1,m\neq n}^{\ell-1}I_m$. Under this sampling strategy, the whole $\A_n$ can be updated in one iteration. Specifically, in iteration $t$, the work in \cite{battaglino2018practical} updates $\A_n$ for $n=1,\ldots,N$ sequentially, as in the BCD case. To update $\A_n$, it samples a set of mode-$n$ fibers, indexed by ${\cal Q}_n^{(t)}$ and solve a `sketched least squares' problem:
\begin{equation}
\min_{\A_n}~\left\| \X_n({\cal Q}_n^{(t)},:) - \H_n^{(t)}({\cal Q}_n^{(t)},:)\A_n^\T \right\|_{\rm F}^2,
\end{equation}
whose solution is $$ \A_n^{(t+1)} \leftarrow ( \H_n^{(t)}({\cal Q}_n^{(t)},:)^{\dagger}\X_n({\cal Q}_n^{(t)},:))^\T. $$
This simple sampling strategy makes sure that every entry of $\A_n$ can be updated in iteration $t$.
The rationale behind is also reasonable: If the tensor is low-rank, then one does not need to use all the data to solve the least squares subproblems---using randomly sketched data is enough, if the system of linear equations $\X_n = \H^{(t)}({\cal Q}_n^{(t)},:)\A_n^\T$ is over-determined, it returns the same solution as solving $\X_n = \H^{(t)}\A_n^\T$.

The work in \cite{battaglino2018practical} did not explicitly consider structural information on $\A_n$'s, and the convergence properties of the approach are unclear.
To incorporate structural information and to establish convergence, the recent work in \cite{fu2019block} offered a remedy. There, a block-randomized sampling strategy was proposed to help establish unbiasedness of the gradient estimation. Then, PGD is combined with fiber sampling for handling structural constraints.
The procedure consists of two sampling stages: first, randomly sample a mode $n\in\{1,\ldots,N\}$ with random seed $\zeta^{(t)}$ such that ${\sf Pr}(\zeta^{(t)} = n)=1/N$. Then, sample a set of mode-$n$ fibers indexed by ${\cal Q}_n$ uniformly at random (with another random seed $\xi^{(t)}$).  Using the sampled data, construct
\begin{equation}\label{eq:Gn}
 \G^{(t)} =[\G^{(t)}_1;\ldots;\G^{(t)}_N],
\end{equation}
where $\G_n^{(t)} =  \A_n\B^\T\B-\X_n({\cal Q}_n,:)^\T\B$ with
$\B = \H^{(t)}({\cal Q}_n^{(t)},:)$, and $\G_k^{(t)}=\bm 0$ for $k\neq n$.
This block-randomization technique entails the following equality:
\begin{equation}\label{eq:brascpd_g}
{\rm vec}\left(\mathbb{E}_{\xi^{(t)}}\left[ \G^{(t)}|{\cal H}^{(t)},\zeta^{(t)} \right]\right)=c\nabla f(\bm \theta^{(t)}),
\end{equation}
where $c>0$ is a constant; i.e., the constructed stochastic vector is an unbiased estimation (up to a constant scaling factor) for the full gradient, conditioned on the filtration. Then, the algorithm updates the latent factors via
\begin{equation}\label{eq:brascpd}
\A_n^{(t+1)} \leftarrow {\sf Prox}_{h_n}\left( \A_n^{(t)} -\alpha^{(t)} \G_n^{(t)} \right).
\end{equation}
Because of \eqref{eq:brascpd_g}, the above is almost identical to single block SPGD, and thus enjoys similar convergence guarantees \cite{fu2019block}.

Fiber sampling approaches as in \cite{battaglino2018practical} and \cite{fu2019block} are economical, since they never need to instantiate the large matrix $\H_n$ or to compute the full MTTKRP.
{ A remark is that fiber sampling is also of interest in partially observed tensor recovery \cite{kanatsoulis2019regular,zhang2020spectrum}; in Section \ref{sec:tractable} it will actually be argued that under mild conditions exact completion of a fiber-sampled tensor is possible via a matrix eigenvalue decomposition \cite{sorensen2015fibersampling}.}

\subsection{Adaptive Step-size Scheduling}

Implementing stochastic algorithms oftentimes requires somewhat intensive hands-on tuning for selecting hyperparameters, in particular, the step size $\alpha^{(t)}$. Generic SGD and SPGD analyses suggest to set the step size sequence following the Robbins and Monro's rule, i.e.,

$\sum_{t=0}^\infty \alpha^{(t)} =\infty,~\sum_{t=0}^\infty (\alpha^{(t)})^2<\infty.$

The common practice is to set $\alpha^{(t)} =\alpha/t^\beta$ with $\beta>1$, but the ``best'' $\alpha$ and $\beta$ for different problem instances can be quite different.

To resolve this issue, adaptive step-size strategies that can automatically determine $\alpha^{(r)}$ are considered in the literature. The RBS method in \cite{vervliet2016randomized} and the fiber sampling method in \cite{fu2019block} both consider adaptive step-size selection for tensor decomposition.
In particular, the latter combines the insight of \texttt{adagrad} that has been popular in deep neural network training together with block-randomized tensor decomposition to come up with an adaptive step-size scheme (see ``{\bf Adagrad for Stochastic SLRD}").

\begin{mdframed}[backgroundcolor=blue!10,topline=false,
	rightline=false,
	leftline=false,
	bottomline=false]

\noindent
{\bf Adagrad for Stochastic SLRD}
In \cite{fu2019block}, the following term is updated for each block $n$ under the block-randomized fiber sampling framework:
\begin{align*}
[\bm \eta^{(t)}_{n}]_{i,r} &\leftarrow \frac{1}{\left(b + \sum_{q=1}^{t}[{\bm G}_{(n)}^{(q)}]_{i,r}^2\right)^{1/2+\epsilon}},\label{eq:etaada}
\end{align*}
where $b$ and $\epsilon$ are inconsequential small positive quantities for regularization purpose.
Then, the selected block is updated via
\begin{equation}\label{eq:adas=cpd}
\A_n^{(t+1)} \leftarrow {\sf Prox}_{h_n}\left( \A_n^{(t)} -\bm \eta^{(t)}_n \circledast \G_n^{(t)} \right).
\end{equation}
The above can be understood as a data-adaptive pre-conditioning for the stochastic oracle $\G_n^{(t)}$. Implementing \texttt{adagrad} based stochastic CPD (AdaCPD) is fairly easy, but in practice it often saves a lot of effort for fine-tuning $\alpha^{(t)}$ while attaining competitive convergence speed; see Fig.~\ref{fig:fig1}.
This also shows the potential of adapting the well-developed stochastic optimization tools in deep neural network training to serve the purpose of SLRD.

It is shown in \cite{fu2019block} that, using the \texttt{adagrad} version of the fiber sampling algorithm, every limit point of $\{\bm \theta^{(t)}\}$ is a stationary point in expectation, if $h(\bm \theta)$ is absent. However, convergence in the presence of nonsmooth $h(\bm \theta)$ is still an open challenge.
\end{mdframed}

\begin{figure}
	\centering

	\setlength{\figurewidth}{6cm}
    \setlength{\figureheight}{3cm}
    \input{img/stochastic.tikz}
	\caption{Stochastic algorithms [BrasCPD (manually fine-tuned step size) and AdaCPD (adaptive step size)] use significantly fewer operations to reach a good estimation accuracy for the latent factors, compared to batch algorithms. The MSE for estimating the $\A_{n}$'s against the number of full MTTKRP used. The CP rank is 10 and $I_n=100$ for all $n=1,2,3$. Figure reproduced from \cite{fu2019block}. Permission will be sought upon publication.}
	\label{fig:fig1}
	\vspace{-,5cm}
\end{figure}

\smallskip
\begin{comment}
To conclude this section, we have the following remarks:

\noindent
$\bullet$ Stochastic tensor decomposition algorithms can have many different sampling strategies, but some strategies may make adding certain types of structural constraints hard. This makes designing sampling strategies for different tensor models an interesting problem---which needs to balance between complexity, convergence properties, and the flexibility for incorporating constraints/regularization terms of interest.

\noindent
$\bullet$ Convergence analysis for stochastic tensor decomposition algorithms is not always obvious, since generic stochastic optimization tools may not cover specific sampling patterns. Many theoretical aspects need to be addressed from the optimization side to explain the effectiveness of some algorithms, e.g., CPRAND and RBS.

\noindent
$\bullet$ Adaptive step-size rules are particularly important for software engineering---as well as for stable and fast convergence in practice. There remains a lot to understand about adaptive step-size rules in structured tensor decomposition. Existing convergence results only characterize the smooth optimization case (unconstrained tensor/matrix decomposition in our context).
Establishing convergence under the nonconvex nonsmooth case may require more advanced analytical tools, or even modifications of the update rules.
\end{comment}

In Fig.~\ref{fig:fig1}, we show the MSE on the estimated $\A_{n}$'s obtained by different algorithms after using a certain number of full MTTKRP (which serves as a unified complexity measure). Here, the tensor has size $100\times 100 \times 100$ and its CP rank is $R=10$. One can see that stochastic algorithms (BrasCPD and AdaCPD) work remarkably well in this simulation. In particular, the adaptive step size algorithm exhibits promising performance without tuning step-size parameters. We also would like to mention that the stochastic algorithms naturally work with incomplete data (e.g., data with missing entries or fibers), since the updates only rely on partial data.

\bigskip

{
Table~\ref{tab:handbook} presents an incomplete summary of structural constraints/regularization terms (together with the Euclidean data fitting-based CPD cost function) that can be handled by the introduced nonconvex optimization frameworks. One can see that different frameworks may be specialized for different types of structural constraints and regularization terms.
In terms of accommodating structural requirements, the AO-ADMM algorithm \cite{huang2016flexible} and the GN framework offered in Tensorlab \cite{vervliet2016tensorlab3} may be the most flexible ones, since they can handle multiple structural constraints simultaneously.

}

\begin{table*}[htbp]
 \centering
   \begin{threeparttable}[b]

  \caption{An incomplete summary of structural constraints that can be handled by some representative algorithms.}  \label{tab:handbook}

				\centering

    \begin{tabular}{lcccc}
    \toprule
    Structural constraint or regularization & $\begin{subarray}{c} \text{AO-ADMM~\cite{huang2016flexible}} \\ \text{(exact BCD)}\end{subarray}$  & $\begin{subarray}{c} \text{APG~\cite{xu2013block}} \\ \text{(inexac BCD)}\end{subarray}$ &  $\begin{subarray}{c} \text{Tensorlab~\cite{vervliet2016tensorlab3}} \\ \text{(GN)}\end{subarray}$  & $\begin{subarray}{c} \text{AdaCPD~\cite{fu2019block}} \\ \text{(stochastic)}\end{subarray}$ \\
    \midrule
    Nonnegativity ($\A_n\geq \bm 0$) & \CheckmarkBold     & \CheckmarkBold     & \CheckmarkBold      & \CheckmarkBold  \\
    Sparsity ($\|\A_n\|_1=\sum_{i=1}^{I_n}\sum_{r=1}^R |\A_n(i,r)|$)    & \CheckmarkBold     & \CheckmarkBold      & \CheckmarkBold\tnote{+}      & \CheckmarkBold  \\
    Column group  sparsity ($\|\A_n\|_{2,1}=\sum_{r=1}^R\|\A_n(:,r)\|_2$)    & \CheckmarkBold     & \CheckmarkBold      & \CheckmarkBold\tnote{+}      & \CheckmarkBold  \\
    Row group  sparsity ($\|\A_n^\T\|_{2,1}=\sum_{i=1}^{I_n}\|\A_n(i,:)\|_2$)    & \CheckmarkBold     & \CheckmarkBold      & \CheckmarkBold\tnote{+}      & \CheckmarkBold  \\
    Total variation ($\|\bm T_1\bm A_n\|_1$)\tnote{*} & \CheckmarkBold      & \CheckmarkBold      & \CheckmarkBold\tnote{+}      & \CheckmarkBold  \\
    Row prob. simplex ($\A_n\bm 1=\bm 1,~\A_n\geq \bm 0$) & \CheckmarkBold      & \CheckmarkBold      & \CheckmarkBold      & \CheckmarkBold  \\
    Column prob. simplex ($\bm 1^\T\A_n=\bm 1^\T,~\A_n\geq \bm 0$) & \CheckmarkBold      & \CheckmarkBold      & \CheckmarkBold      & \CheckmarkBold \\
    Tikhonov smoothness ($\|\bm T_2\A_n\|_{\rm F}^2$)\tnote{*} & \CheckmarkBold     & \CheckmarkBold      & \CheckmarkBold      & \CheckmarkBold  \\
    Decomposition symmetry ($\A_n=\A_m$)&       &       & \CheckmarkBold      &  \\
    Boundedness ($a\leq \A_n(i,r)\leq b$) & \CheckmarkBold      & \CheckmarkBold     & \CheckmarkBold      & \CheckmarkBold  \\
    Coupled factorization (see \cite{ibrahim2019crowdsourcing,ibrahim2019stochastic,sorensen2015coupledcanonicalpart1,kanatsoulis2019regular}) & \CheckmarkBold      & \CheckmarkBold     & \CheckmarkBold      & \CheckmarkBold  \\
    Multiple structures combined (e.g., $\|\bm T_2\A_n\|_1 + \|\A_n\|_{2,1}$) & \CheckmarkBold      &       &  \CheckmarkBold       &  \\
    \bottomrule
    \end{tabular}

      \begin{tablenotes}
     \item[*] The operators $\bm T_1$ and $\bm T_2$ are sparse circulant matrices whose expressions can be found in the literature, e.g., \cite{CVX2004}.
     \item[+] GN-based methods (except for ProxGN in \cite{huang2019globalsip}) work with differentiable functions. In Tensorlab, the $\ell_1$ norm-related non-differentiable terms are handled using function-smoothing techniques as approximations; see details in \cite{vervliet2018numericaloptimization}.
   \end{tablenotes}
  \end{threeparttable}

\end{table*}

\begin{comment}

\begin{table}[htbp]

		\begin{mdframed}[backgroundcolor=blue!10,topline=false,
			rightline=false,
			leftline=false,
			bottomline=false]
				\centering
	\caption{Exact BCD algorithms for SLRDs.}
		\begin{tabular}{ccc}

		\toprule
		\textbf{Algorithm} & \textbf{Model} (dist loss) & \textbf{Subproblem Solver} \\
		\midrule
		AO-ADMM \cite{huang2016flexible} & CPD (LS)  & ADMM \\
		AO-Nesterov \cite{liavas2017nesterov} & CPD (LS)   & Accelerated PGD \\
			   alsgrad \cite{lin2007projected} & NMF (LS)   & PGD \\
		NeNMF \cite{guan2012nenmf} & NMF (LS)   & Accelerated PGD \\
	ANLS \cite{kim2008nonnegative}  & NMF (LS)   & Active Set  \\
	AO-Mirror \cite{kargas2019learning} &  Coupled CPD (KL) & Mirror Descent \\
		\bottomrule
	\end{tabular}

	\label{tab:exactbcd}
	\end{mdframed}
\end{table}

\end{comment}

config: arxiv


TITLE: Set equivalence - Zorich's real analysis
QUESTION [2 upvotes]: I am doing my BS Mathematics second year through an open university IGNOU.
I am taking a first course in real analysis. I am using the text by Bartle and Shebert and the one by Zorich to supplement it. I would like to have my proof on elementary set equivalence verified. This is a naive attempt.

Verify the relation
$$(A \subset C)\wedge(B \subset C)\iff((A \cup B) \subset C)$$

Proof.
(1) Consider arbitrary elements $x_{1}\in A,x_{2} \in B$.
We are given $(A \subset C) \wedge (B \subset C)$. It follows -
$x_{1} \in A \implies x_{1} \in C$.
$x_{2} \in B \implies x_{2} \in C$.
$x_{1},x_{2} \in (A \cup B) \implies x_{1},x_{2} \in C$
Consequently, $(A \cup B) \subset C$.
$(A \subset C) \wedge (B \subset C) \implies (A \cup B) \subset C$.
(2) In the other direction, consider arbitary elements $x_{1},x_{2} \in (A \cup B)$. Given $(A \cup B) \subset C$, we must have $x_{1},x_{2} \in C$.
But, $x_{1},x_{2} \in (A \cup B)$ implies
(a) $x_{1} \in A, x_{2} \in B$ or
(b) $x_{1},x_{2} \in (A \cap B)$ or
(c) $x_{1},x_{2} \in A, B = \phi$ or
(d) $A = \phi, x_{1},x_{2} \in B$
Each of these implies the left hand side $(A \subset C)\wedge(B \subset C)$ holds.
$((A \cup B) \subset C) \implies (A \subset C)\wedge(B \subset C)$
From (1) and (2) we have :
$((A \cup B) \subset C) \iff (A \subset C)\wedge(B \subset C)$

REPLY [1 votes]: You don't need two elements, just one arbitary one will do to show an inclusion.
So suppose $(A \subset C) \land (B \subset C)$ holds.
This implies that $A \subset C$ and $B \subset C$ both hold.
We want to show that $(A \cup B) \subset C$, so let $x \in A \cup B$ be arbitary.
This means that $x \in A$ or $x \in B$. If the first is the case, then from  $A \subset C$ we conclude that $x \in C$. If the second is the case, from $B \subset C$ we see that $x \in C$. So $x \in C$ holds. This shows that $(A \cup B) \subset C$.
Now suppose that $(A \cup B) \subset C$ holds, and we want to show that $(A \subset C) \land (B \subset C)$ is then true.
So take $x \in A$ arbitrarily. Then $x \in A \cup B$ and so $x \in C$ by the assumed inclusion. So $A \subset C$.
Take $x \in B$ arbitarily. Then $x \in A \cup B$ and so $x \in C$ by the assumed inclusion. So $B \subset C$. As both hold, so does $(A \subset C) \land (B \subset C)$.
We have shown two implications, hence the equivalence.

REPLY [1 votes]: The $x_1, x_2$ stuff is just confusion.
Proof of left to right.  Assume the premise.
If x in A $\cup$ B, then x in A or x in B.
In either case, by the premise, x in C.
Proof of right to left is simple.  All it takes is knowing
A subset A $\cup$ B and B subset A $\cup$ B,


text:
\begin{document}
	\title{Complemented Lattices of Subracks}
	\author[A. Saki]{A. Saki}
\address{Amir Saki, Department of Pure Mathematics, Faculty of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Polytechnic), 424, Hafez Ave., Tehran 15914, Iran.}
\email{amir.saki.math@gmail.com}
\author[D. Kiani]{D. Kiani\,*}
\thanks{* Corresponding author}
\address{Dariush Kiani, Department of Pure Mathematics, Faculty of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Polytechnic), 424, Hafez Ave., Tehran 15914, Iran, and School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran.}
\email{dkiani@aut.ac.ir,  dkiani7@gmail.com}
\begin{abstract}
In this paper, a question due to Heckenberger, Shareshian and Welker on racks in \cite{Wel} is positively answered. A rack is a set together with a self-distributive bijective binary operation. We show that the lattice of subracks of every finite rack is complemented. Moreover, we characterize finite  modular lattices of subracks in terms of complements of subracks.  Also, we introduce a certain class of racks including all finite groups with the conjugation operation, called $G$-racks, and we study some of their properties. In particular, we show that a finite $G$-rack has the homotopy type of a sphere. Further, we show that the lattice of subracks of an infinite rack is not necessarily complemented which gives an affirmative answer to the aformentioned question. Indeed, we show that the lattice of subracks of the set of rational numbers, as a dihedral rack, is not complemented.  Finally, we show that being a Boolean algebra, pseudocomplemented and  uniquely complemented as well as distributivity are equivalent for the lattice of subracks of a rack.

\smallskip
\vspace{5pt}
\noindent \textsc{Keywords.} Rack,  lattice of subracks, complemented lattice, modular lattice.
\end{abstract}
\maketitle

\section{Introduction}
Nowadays, racks  are used in several fields of pure and applied sciences  by knot theory, for example in  encoding the strands of knot diagrams. The study of an algebraic structure like a rack was started by M. Takasaki in \cite{Tak} where he studied reflections in  finite geometry. Indeed, he used a certain algebraic structure known as key or involutory quandle. Since then, racks, quandles and similar self-distributive systems were used in many papers for studying braids and knots (see \cite{Bri}, \cite{Fen}, \cite{Joy} and \cite{Mat}).  See also \cite{And}, for some  results about racks and their applications in Hopf algebras.

A \textit{rack} is a set together with a self-distributive and bijective operation. A \textit{subrack} of a rack $(R,\tg)$  is a subset $Q$ of $R$ where $(Q,\tg)$ is a rack. The set of all subracks of  a rack $R$  together with the inclusion order is a lattice. More precisely, the meet and the join of two subracks are the intersection of them and the subrack generated by them, respectively. The lattice of subracks of a rack was introduced by I. Heckenberger et al. in \cite{Wel} where the authors started the study of racks  from the combined perspective of both combinatorics and group theory, and they also posed some interesting questions about the lattice of subracks. In \cite{SK1},  a positive answer was given to one of those questions. Indeed, it was shown that the lattice of subracks of any rack is atomic. Moreover in \cite{SK1}, the atoms of the lattice of subracks were shown to be exactly all subracks generated by a singleton of $R$.

In this paper, we  answer  the following question for finite racks, due to I. Heckenberger et al. in \cite{Wel}:
\begin{Question} \label{Que}
Is there a rack $R$ whose lattice of subracks  is not complemented?
\end{Question}

Indeed, the above question is the first part of Question 5.2 in \cite{Wel}. In this paper, we give a positive answer to Question \ref{Que} by providing an example among infinite racks. However, we show that the lattice of subracks of any finite rack is complemented.

Concerning  other properties of lattices of subracks one can mention \cite[Example~2.3]{Wel} where it was shown that the rack of all transpositions in the permutation group $S_n$ together with the conjugation operation is isomorphic to the lattice of all partitions of a set with $n$ elements. It was also shown in \cite[Corollary 2.11]{Wel}  that the topology of  the lattice of subracks of a rack, in the sense of its order complex, could be complicated.

This paper is organized as follows. In Section \ref{sec}, we provide some preliminaries which we use throughout the paper.  Section \ref{sec1} is devoted to Question \ref{Que} in the case of finite racks and some related problems arising from this question. Indeed, we show that the lattice of subracks of any finite rack is complemented.  Moreover, we show  how  modularity and  complements of subracks in the lattice of subracks of a finite rack are related. In Section \ref{G}, we  introduce a certain class of racks including all finite groups with the conjugation operation, called  $G$-racks, and we study some  of their properties such as their homotopy types. In Section \ref{S}, we eventually give a positive answer to Question \ref{Que} using infinite racks. Actually, we show that the abelian group $\mathbb{Q}$, as a dihedral rack, is not complemented. At the end of this section, we show that being a Boolean algebra, pseudocomplemented, uniquely complemented and distributivity are equivalent for the lattice of subracks of a rack.

\section{Preliminaries}\label{sec}
A lattice is a  partially ordered set  in which every two elements have a unique least upper bound (supremum) and a unique greatest lower bound (infimum). Let $L$ be a lattice. We call the supremum and the infimum of the two elements $a,b\in L$, the \textit{join} and the \textit{meet} of $a$ and $b$, respectively, and denote them by $a\vee b$ and $a\wedge b$, respectively. If $L$ has the greatest (resp. least) element, then this element is denoted by $\hat{1}$ (resp. $\hat{0}$). A lattice including $\hat{0}$ and $\hat{1}$ is called \textit{bounded}. The lattice $L$ is called \textit{distributive} if $a\wedge(b\vee c)=(a\wedge b)\vee(a\wedge c)$, for all $a,b,c\in L$. Modularity  is a simple generalization of  distributivity. Indeed, the lattice $L$ is called \textit{modular} if $a\wedge(c\vee b)=(a\wedge c)\vee b$, for all $a,b,c\in L$ with $b\le a$. The lattice $L$ including $\hat{0}$ and $\hat{1}$ is called \textit{complemented} if for every $a\in L$ there exists an element $b\in L$, called the complement of $a$, such that $a\wedge b=\hat{0}$ and $a\vee b=\hat{1}$. If in a complemented lattice every element has a unique complement, then the lattice is called \textit{uniquely complemented}. A complemented distributive lattice is called a \textit{Boolean algebra}. We denote  the lattice obtained by removing $\hat{0}$ and $\hat{1}$ (if  exist) by $\overline{L}$. An \textit{atom} of $L$  is an element $a\in L$ such that $b\le a$ implies  $b=a$, for every $b\in\overline{L}$. A lattice whose any of elements is the join of some atoms is called \textit{atomic}. A \textit{relatively atomic} lattice is a lattice in which every interval is atomic. Similarly, a \textit{relatively complemented} lattice is a lattice in which every closed bounded interval $[x,y]$  is complemented. It is obvious that every bounded relatively atomic lattice (resp. bounded relatively complemented lattice) is atomic (resp. complemented). The lattice $L$ including $\hat{0}$ is called \textit{pseudocomplemented} if for every $x\in L$ there exists a greatest element $x^*$ with  $x\wedge x^*=\hat{0}$ (here $x^*$ is unique).

A (finite abstract) \textit{simplicial complex} is a collection $\Delta$ of sets  such that for each $\sigma\in\Delta$ and $\tau\subseteq\sigma$, one has $\tau\in\Delta$. Let $\Delta$ be a simplicial complex. The elements of $\Delta$ are called \textit{faces} or \textit{simplices} of $\Delta$.  Maximal faces of $\Delta$ are called  \textit{facets}. The dimension of a face of $\Delta$ is defined to be the cardinality of the face minus one. The dimension of $\Delta$ is the maximum of the dimensions of its faces. A subcomplex of $\Delta$ is a subset $\Gamma$ of $\Delta$ which is a simplicial complex.

A  rack  is a set $R$ together with a binary operation $\tg$ such that the following conditions are satisfied: for all $a,b,c\in R$, we have $a\tg(b\tg c)=(a\tg b)\tg(a\tg c)$, and there exists a unique $x\in R$ with $a\tg x=b$. A \textit{quandle} is a rack $Q$ with the additional condition $x\tg x=x$, for all $x\in Q$.

Let $(R,\tg)$ be a rack. A  subrack  of $R$ is a subset $Q$ of $R$ where $(Q,\tg)$ is a rack as well. The set of all subracks of $R$ with the inclusion order is a lattice called the\textit{ lattice of subracks} of $R$, and denoted by $\mathcal{R}(R)$. For a subset $S$ of $R$, the \textit{subrack generated} by $S$ in $R$, denoted by $\ll S\gg$, is the intersection of all subracks of $R$ including $S$. It follows from the definition that  for every $a\in R$, the map $f_a:R\to R$ with $f_a(b)=a\tg b$ is a bijection. An automorphism of $R$ is a function $\phi:R\to R$ such that for all $a,b\in R$, we have $\phi(a\tg b)=\phi(a)\tg\phi(b)$. The \textit{inner group} of $R$, denoted by $\mathrm{Inn}(R)$, is the subgroup generated by $\{f_a:a\in R\}$ in the automorphism group of $R$. Note that $f_a$ is an automorphism of $R$, for every $a\in R$. The inner group of $R$ acts on $R$ by the natural action $\phi*x=\phi(x)$, for all $\phi\in\mathrm{Inn}(R)$ and $x\in R$. The orbits of this action are subracks of $R$. In other words, the orbit including $x\in R$ is the set $\{\phi(x): \phi\in\mathrm{Inn}(R)\}$. Note that when we refer to a group as a rack, we mean that the operation is conjugation.

\section{Complementedness of The Lattice of Subracks of Finite Racks} \label{sec1}

In this section, we discuss Question \ref{Que} for finite racks. Indeed, we show that $\mathcal{R}(R)$ is complemented for every finite rack $R$. We also determine some other structural properties of $\mathcal{R}(R)$. In particular, we give a characterization of finite modular lattices of subracks in terms of complements of the elements  of the underlying racks. The study of Question \ref{Que} in the case of infinite racks is postponed to Section \ref{S} where a positive answer to this question is provided.

\medskip
The following theorem is one of the most important results of this paper which immediately concludes that the lattice of subracks of a finite rack is complemented.

\begin{Theorem} \label{Thm1}
Let $R$ be a finite rack. Then the following statements hold:
\begin{enumerate}
\item
The intersection of all maximal subracks of $R$ is empty.
\item
For any two subracks $Q_1$ and $Q_2$ of $R$ with $T=\ll Q_1, Q_2\gg$, the subrack $Q_1$ has a complement in $\mathcal{R}(T)$ which is a subset of $Q_2$.
\end{enumerate}
\end{Theorem}

\begin{proof}
(1) If $R=\emptyset$, then the result is clear. Now, we  assume that $R\neq\emptyset$. Suppose that $\{M_i\}_{i=1}^n$ is the set of all maximal subracks of $R$ and $X=\bigcap_{i=1}^nM_i$. Let $\phi$ be an  automorphism of $R$. It is easily seen  that the map $M_i\mapsto \phi(M_i)$ is a permutation on the set of all maximal subracks of $R$. Therefore, we have
\[ \phi(X)=\phi\left(\bigcap_{i=1}^nM_i\right)=\bigcap_{i=1}^n\phi(M_i)=\bigcap_{i=1}^nM_i=X,\]
which implies that $X$ is the union of a set of orbits of $R$. Note that $R\backslash X$ is the union of the other orbits, and hence it is a subrack. If $X\neq\emptyset$, then there is a maximal subrack $M$ containing $R\backslash X$. We also have $X\subseteq M$ and hence $M=R$ which is a contradiction.

(2) Let
\[ \mathcal{C}\coloneqq\{|Q_1\cap Q|: \text{$Q$ is a subrack of $Q_2$ and $T=\ll Q_1, Q\gg$}\}.\]
Obviously, $|Q_1\cap Q_2|$ belongs to $\mathcal{C}$, so that $\mathcal{C}$ is nonempty. Assume that $|Q_1\cap Q_3|$ is the minimum element of $\mathcal{C}$ for a subrack $Q_3$ of $Q_2$. We show that $Q_3$ is a complement of $Q_1$ in $\mathcal{R}(T)$. To do this, it is enough to show that  $Q_1\cap Q_3=\emptyset$. Suppose on contrast that  $x\in Q_1\cap Q_3$. By the part (1) the intersection of all maximal subracks of $Q_3$ is  empty, so there exists a maximal subrack $Q_4$ of $Q_3$ which does not contain $x$. Thus by Theorem 2.3 of \cite{SK1}, $Q_4$ is a complement of $\ll x\gg$ in $\mathcal{R}(Q_3)$. Now, we have $|Q_1\cap Q_4|<|Q_1\cap Q_3|$, while
\[\ll Q_1, Q_4\gg= \ll Q_1, x, Q_4\gg=\ll Q_1, \ll x, Q_4\gg\gg=\ll Q_1, Q_3\gg= T.\]
But this is  a contradiction, since $|Q_1\cap Q_3|$ is the minimum of $\mathcal{C}$.
\end{proof}
\begin{Corollary}
The lattice of subracks of every finite rack is complemented.
\end{Corollary}

\begin{proof}
Let $R$ be a rack and $Q$ be a subrack of $R$. Then we have $\ll Q, R\gg=R$, and hence by the part (2) of Theorem \ref{Thm1}, the result follows.
\end{proof}

There is an important relationship between the lattices of subracks of racks and quandles. The \textit{corresponding quandle} of $R$, denoted by $(\bar{R},*)$, is the set of all atoms of $R$ together with the following operation: for any two atoms $A$ and $B$ of $R$ with $a\in A$ and $b\in B$, we have $A*B=C$ where $C$ is the atom which includes $a\tg b$. We may sometimes consider  quandles instead of racks, because the lattice of subracks of a rack and its corresponding quandle are isomorphic, by  \cite[Corollary~2.7]{SK1}.

Note that the lattice of subracks of a rack is not necessarily relatively complemented. For  example, let $Q$ be the quandle $S_3$.   Since every subrack of $Q$ including a 2-cycle and a 3-cycle includes all other 2-cycles and 3-cycles, it follows that the interval $\left[(1\quad 2), Q\right]$ is not complemented (see Figure \ref{S3}).

Similarly, the lattice of subracks of a rack is not necessarily relatively atomic. For  example, let $Q$ be the dihedral quandle  $\mathbb{Z}_{8}$ (i.e. $x\tg y=2x-y$ for all $x,y\in\mathbb{Z}_8$). In this quandle, the interval $\left[\{0\}, Q\right]$ is not atomic. Indeed, this interval has only the atom $\{0,4\}$, and hence the subrack $\{0,2,4,6\}$ is not the join of some atoms of this interval. Furthermore, this interval  is not complemented, because every subrack of $Q$ which includes an odd number and an even number must generate  $Q$ (see Figure \ref{Z8}).

\begin{figure}[h]
\centering
\subfloat[The lattice~$\mathcal{R}(S_3\backslash\{id\})$, and a non-complemented atomic interval of it (shown in red).\label{S3}]{
\definecolor{ffqqqq}{rgb}{1.,0.,0.}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\clip(4.9,-2.2998147694362574) rectangle (9.438965103515084,2.257682708337581);
\draw [line width=0.4pt] (7.,-2.)-- (5.,-0.8);
\draw [line width=0.4pt] (7.,-2.)-- (6.,-0.8);
\draw [line width=0.4pt] (7.,-2.)-- (7.,-0.8);
\draw [line width=0.4pt] (7.,-2.)-- (8.,-0.8);
\draw [line width=0.4pt] (7.,-2.)-- (9.004851665309076,-0.8040825942618293);
\draw [line width=0.4pt] (7.,-0.8)-- (5.50419,0.7);
\draw [line width=0.4pt] (6.,-0.8)-- (5.50419,0.7);
\draw [line width=0.8pt,color=ffqqqq] (5.,-0.8)-- (5.50419,0.7);
\draw [line width=0.4pt] (8.,-0.8)-- (8.5,0.7);
\draw [line width=0.4pt] (9.004851665309076,-0.8040825942618293)-- (8.5,0.7);
\draw [line width=0.8pt,color=ffqqqq] (5.50419,0.7)-- (7.,2.);
\draw [line width=0.4pt] (8.5,0.7)-- (7.,2.);
\draw [line width=0.4pt] (13.55718533921923,-2.0012363055269073)-- (10.,-1.);
\draw [line width=0.4pt] (11.,-1.)-- (13.55718533921923,-2.0012363055269073);
\draw [line width=0.4pt] (13.55718533921923,-2.0012363055269073)-- (12.,-1.);
\draw [line width=0.4pt] (13.,-1.)-- (13.55718533921923,-2.0012363055269073);
\draw [line width=0.4pt] (13.55718533921923,-2.0012363055269073)-- (14.,-1.);
\draw [line width=0.4pt] (13.55718533921923,-2.0012363055269073)-- (15.,-1.);
\draw [line width=0.4pt] (13.55718533921923,-2.0012363055269073)-- (16.,-1.);
\draw [line width=0.4pt] (13.55718533921923,-2.0012363055269073)-- (17.,-1.);
\draw [line width=0.8pt,color=ffqqqq] (10.,-1.)-- (10.461236731966114,-0.031087191820382755);
\draw [line width=0.4pt] (11.,-1.)-- (10.461236731966114,-0.031087191820382755);
\draw [line width=0.4pt] (12.,-1.)-- (12.495351725987788,-0.005500839694323996);
\draw [line width=0.4pt] (12.495351725987788,-0.005500839694323996)-- (13.,-1.);
\draw [line width=0.4pt] (14.,-1.)-- (14.491087191820375,-0.018294015757353375);
\draw [line width=0.4pt] (14.491087191820375,-0.018294015757353375)-- (15.,-1.);
\draw [line width=0.4pt] (16.,-1.)-- (16.397270425211754,-0.005500839694323996);
\draw [line width=0.4pt] (16.397270425211754,-0.005500839694323996)-- (17.,-1.);
\draw [line width=0.8pt,color=ffqqqq] (10.461236731966114,-0.031087191820382755)-- (11.459104464882406,0.9795737171589383);
\draw [line width=0.4pt] (11.459104464882406,0.9795737171589383)-- (12.495351725987788,-0.005500839694323996);
\draw [line width=0.4pt] (14.491087191820375,-0.018294015757353375)-- (15.48895492473667,0.9667805410959089);
\draw [line width=0.4pt] (15.48895492473667,0.9667805410959089)-- (16.397270425211754,-0.005500839694323996);
\draw [line width=0.8pt,color=ffqqqq] (11.459104464882406,0.9795737171589383)-- (13.518805811030141,1.9646482740122007);
\draw [line width=0.4pt] (15.48895492473667,0.9667805410959089)-- (13.518805811030141,1.9646482740122007);
\begin{scriptsize}
\draw [fill=black] (7.,-2.) circle (2.5pt);
\draw [fill=black] (7.,-0.8) circle (2.5pt);
\draw [fill=black] (6.,-0.8) circle (2.5pt);
\draw [fill=black] (5.,-0.8) circle (2.5pt);
\draw [fill=black] (8.,-0.8) circle (2.5pt);
\draw [fill=black] (9.004851665309076,-0.8040825942618293) circle (2.5pt);
\draw [fill=black] (5.50419,0.7) circle (2.5pt);
\draw [fill=black] (8.5,0.7) circle (2.5pt);
\draw [fill=black] (7.,2.) circle (2.5pt);
\draw [fill=black] (10.,-1.) circle (2.5pt);
\draw [fill=black] (11.,-1.) circle (2.5pt);
\draw [fill=black] (12.,-1.) circle (2.5pt);
\draw [fill=black] (13.,-1.) circle (2.5pt);
\draw [fill=black] (14.,-1.) circle (2.5pt);
\draw [fill=black] (15.,-1.) circle (2.5pt);
\draw [fill=black] (16.,-1.) circle (2.5pt);
\draw [fill=black] (17.,-1.) circle (2.5pt);
\draw [fill=black] (13.55718533921923,-2.0012363055269073) circle (2.5pt);
\draw [fill=black] (10.461236731966114,-0.031087191820382755) circle (2.5pt);
\draw [fill=black] (12.495351725987788,-0.005500839694323996) circle (2.5pt);
\draw [fill=black] (14.491087191820375,-0.018294015757353375) circle (2.5pt);
\draw [fill=black] (16.397270425211754,-0.005500839694323996) circle (2.5pt);
\draw [fill=black] (11.459104464882406,0.9795737171589383) circle (2.5pt);
\draw [fill=black] (15.48895492473667,0.9667805410959089) circle (2.5pt);
\draw [fill=black] (13.518805811030141,1.9646482740122007) circle (2.5pt);
\end{scriptsize}
\end{tikzpicture}
}
\qquad
\subfloat[The lattice of subracks of $\mathbb{Z}_8$ as a dihedral rack, and an interval of it (shown in red) which is neither complemented nor atomic.\label{Z8}]{
\definecolor{ffqqqq}{rgb}{1.,0.,0.}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\clip(9.747996143653158,-2.2707398253994224) rectangle (17.456380921672192,2.2867576523744155);
\draw [line width=0.4pt] (7.,-2.)-- (5.,-0.8);
\draw [line width=0.4pt] (7.,-2.)-- (6.,-0.8);
\draw [line width=0.4pt] (7.,-2.)-- (7.,-0.8);
\draw [line width=0.4pt] (7.,-2.)-- (8.,-0.8);
\draw [line width=0.4pt] (7.,-2.)-- (9.004851665309076,-0.8040825942618293);
\draw [line width=0.4pt] (7.,-0.8)-- (5.50419,0.7);
\draw [line width=0.8pt,color=ffqqqq] (6.,-0.8)-- (5.50419,0.7);
\draw [line width=0.4pt] (5.,-0.8)-- (5.50419,0.7);
\draw [line width=0.4pt] (8.,-0.8)-- (8.5,0.7);
\draw [line width=0.4pt] (9.004851665309076,-0.8040825942618293)-- (8.5,0.7);
\draw [line width=0.8pt,color=ffqqqq] (5.50419,0.7)-- (7.,2.);
\draw [line width=0.4pt] (8.5,0.7)-- (7.,2.);
\draw [line width=0.4pt] (13.55718533921923,-2.0012363055269073)-- (10.,-1.);
\draw [line width=0.4pt] (11.,-1.)-- (13.55718533921923,-2.0012363055269073);
\draw [line width=0.4pt] (13.55718533921923,-2.0012363055269073)-- (12.,-1.);
\draw [line width=0.4pt] (13.,-1.)-- (13.55718533921923,-2.0012363055269073);
\draw [line width=0.4pt] (13.55718533921923,-2.0012363055269073)-- (14.,-1.);
\draw [line width=0.4pt] (13.55718533921923,-2.0012363055269073)-- (15.,-1.);
\draw [line width=0.4pt] (13.55718533921923,-2.0012363055269073)-- (16.,-1.);
\draw [line width=0.4pt] (13.55718533921923,-2.0012363055269073)-- (17.,-1.);
\draw [line width=0.8pt,color=ffqqqq] (10.,-1.)-- (10.461236731966114,-0.031087191820382755);
\draw [line width=0.4pt] (11.,-1.)-- (10.461236731966114,-0.031087191820382755);
\draw [line width=0.4pt] (12.,-1.)-- (12.495351725987788,-0.005500839694323996);
\draw [line width=0.4pt] (12.495351725987788,-0.005500839694323996)-- (13.,-1.);
\draw [line width=0.4pt] (14.,-1.)-- (14.491087191820375,-0.018294015757353375);
\draw [line width=0.4pt] (14.491087191820375,-0.018294015757353375)-- (15.,-1.);
\draw [line width=0.4pt] (16.,-1.)-- (16.397270425211754,-0.005500839694323996);
\draw [line width=0.4pt] (16.397270425211754,-0.005500839694323996)-- (17.,-1.);
\draw [line width=0.8pt,color=ffqqqq] (10.461236731966114,-0.031087191820382755)-- (11.459104464882406,0.9795737171589383);
\draw [line width=0.4pt] (11.459104464882406,0.9795737171589383)-- (12.495351725987788,-0.005500839694323996);
\draw [line width=0.4pt] (14.491087191820375,-0.018294015757353375)-- (15.48895492473667,0.9667805410959089);
\draw [line width=0.4pt] (15.48895492473667,0.9667805410959089)-- (16.397270425211754,-0.005500839694323996);
\draw [line width=0.8pt,color=ffqqqq] (11.459104464882406,0.9795737171589383)-- (13.518805811030141,1.9646482740122007);
\draw [line width=0.4pt] (15.48895492473667,0.9667805410959089)-- (13.518805811030141,1.9646482740122007);
\begin{scriptsize}
\draw [fill=black] (7.,-2.) circle (2.5pt);
\draw [fill=black] (7.,-0.8) circle (2.5pt);
\draw [fill=black] (6.,-0.8) circle (2.5pt);
\draw [fill=black] (5.,-0.8) circle (2.5pt);
\draw [fill=black] (8.,-0.8) circle (2.5pt);
\draw [fill=black] (9.004851665309076,-0.8040825942618293) circle (2.5pt);
\draw [fill=black] (5.50419,0.7) circle (2.5pt);
\draw [fill=black] (8.5,0.7) circle (2.5pt);
\draw [fill=black] (7.,2.) circle (2.5pt);
\draw [fill=black] (10.,-1.) circle (2.5pt);
\draw [fill=black] (11.,-1.) circle (2.5pt);
\draw [fill=black] (12.,-1.) circle (2.5pt);
\draw [fill=black] (13.,-1.) circle (2.5pt);
\draw [fill=black] (14.,-1.) circle (2.5pt);
\draw [fill=black] (15.,-1.) circle (2.5pt);
\draw [fill=black] (16.,-1.) circle (2.5pt);
\draw [fill=black] (17.,-1.) circle (2.5pt);
\draw [fill=black] (13.55718533921923,-2.0012363055269073) circle (2.5pt);
\draw [fill=black] (10.461236731966114,-0.031087191820382755) circle (2.5pt);
\draw [fill=black] (12.495351725987788,-0.005500839694323996) circle (2.5pt);
\draw [fill=black] (14.491087191820375,-0.018294015757353375) circle (2.5pt);
\draw [fill=black] (16.397270425211754,-0.005500839694323996) circle (2.5pt);
\draw [fill=black] (11.459104464882406,0.9795737171589383) circle (2.5pt);
\draw [fill=black] (15.48895492473667,0.9667805410959089) circle (2.5pt);
\draw [fill=black] (13.518805811030141,1.9646482740122007) circle (2.5pt);
\end{scriptsize}
\end{tikzpicture}
}
\caption{The lattice of subracks of a rack is not necessarily  relatively complemented or relatively atomic.}
\end{figure}

It is well-known that every complemented modular lattice is relatively complemented. To see this, let $L$ be a complemented modular lattice and $[a,b]$ be an interval in $L$. For an element $c\in[a,b]$, if $c'$ is a complement of $c$ in $L$, then $a\vee(c'\wedge b)$ is a complement of $c$ in $[a,b]$, because by modularity we have $c\wedge\left(a\vee(c'\wedge b)\right)=\left(c\wedge(c'\wedge b)\right)\vee a=a$, and we also have $c\vee\left(a\vee(c'\wedge b)\right)=c\vee(c'\wedge b)=b\wedge(c\vee c')=b$.

A \textit{sublattice} $S$ of $L$ is a subset of $L$ such that the join and the meet of every two elements of $S$ in $L$ belong to $S$. Note that it is a well-known fact that a lattice $L$ is modular if and only if it does not have any sublattice isomorphic to  the lattice in Figure \ref{f1} (see \cite[Theorem 2 of Section 7]{Gra}). As some well-known examples of modular lattices, we refer to the lattice of submodules of a module over a ring, and the lattice of normal subgroups of a group. Since the lattice of subracks is atomic, modular lattice of subracks are geometric lattices. The following theorem provides a relationship between modularity and reducing complements in the lattice of subracks of a finite rack.

\begin{figure}
\definecolor{ududff}{rgb}{0.30196078431372547,0.30196078431372547,1.}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\clip(0,-2.1747111242953716) rectangle (7.837052219488011,2.22048237520128);
\draw [line width=0.4pt] (4.,-2.)-- (2.,-1.);
\draw [line width=0.4pt] (4.,-2.)-- (6.,-1.);
\draw [line width=0.4pt] (2.,-1.)-- (2.,1.);
\draw [line width=0.4pt] (2.,1.)-- (5.,2.);
\draw [line width=0.4pt] (6.,-1.)-- (5.,2.);
\begin{scriptsize}
\draw [fill=black] (4.,-2.) circle (2.5pt);
\draw [fill=black] (2.,-1.) circle (2.5pt);
\draw [fill=black] (6.,-1.) circle (2.5pt);
\draw [fill=black] (2.,1.) circle (2.5pt);
\draw [fill=ududff] (5.,2.) circle (2.5pt);
\draw [fill=black] (5.,2.) circle (2.5pt);
\end{scriptsize}
\end{tikzpicture}
\caption{The lattice $N_5$ as  the smallest lattice which is not modular.\label{f1}}
\end{figure}

Let $R$ be a finite rack and let $Q$, $R_1$ and $R_2$ be subracks of $R$ with $Q\subseteq R_1\subseteq R_2$. Then we say that a complement $Q'$ of $Q$ in $\mathcal{R}(R_2)$ can be reduced to a complement of $Q$ in $\mathcal{R}(R_1)$, if $Q'\cap R_1$ is a complement of $Q$ in $\mathcal{R}(R_1)$.
\begin{Theorem}\label{Thm2}
Let $R$ be a finite rack. Then $\mathcal{R}(R)$ is modular if and only if for all subracks $Q,R_1$ and $R_2$ of $R$ with $Q\subseteq R_1\subseteq R_2$  every complement of $Q$ in $\mathcal{R}(R_2)$ can be reduced to a complement of $Q$ in $\mathcal{R}(R_1)$.
\end{Theorem}

\begin{proof}
First, suppose that $\mathcal{R}(R)$ is modular, and $Q,R_1$ and $R_2$ are subracks of $R$ with $Q\subseteq R_1\subseteq R_2$. Let $Q'$ be a complement of $Q$ in $\mathcal{R}(R_2)$. By modularity, we have $R_1\cap\ll Q',Q\gg=\ll R_1\cap Q',Q\gg$. It follows that $R_1=\ll R_1\cap Q',Q\gg$, and hence $R_1\cap Q'$ is a complement of $Q$ in $\mathcal{R}(R_1)$.

Conversely, suppose that we can reduce every complement of $Q$ in $\mathcal{R}(R_2)$ to a complement of $Q$ in $\mathcal{R}(R_1)$ for every subrack $Q$ of $R_2$. If $\mathcal{R}(R)$ is not modular, then $\mathcal{R}(R)$ has  a  sublattice   as shown in  Figure \ref{NM}.
\begin{figure}
\centering
\subfloat[The lattice $N_5$ in a non-modular lattice of subracks.\label{NM}]{
\definecolor{ududff}{rgb}{0.30196078431372547,0.30196078431372547,1.}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\clip(1.3,-2.55) rectangle (7,3);
\draw [line width=0.4pt] (4.,-2.)-- (2.,-1.);
\draw [line width=0.4pt] (4.,-2.)-- (6.,-1.);
\draw [line width=0.4pt] (2.,-1.)-- (2.,1.);
\draw [line width=0.4pt] (2.,1.)-- (5.,2.);
\draw [line width=0.4pt] (6.,-1.)-- (5.,2.);
\draw (3.15,-2.0354248486414646) node[anchor=north west] {$Q_1\cap Q_2$};
\draw (1.2,-0.6) node[anchor=north west] {$Q_1$};
\draw (6.126431693679114,-0.6) node[anchor=north west] {$Q_2$};
\draw (1.2,1.5) node[anchor=north west] {$Q_3$};
\draw (3.75,2.8) node[anchor=north west] {$\ll Q_1, Q_2\gg$};
\begin{scriptsize}
\draw [fill=black] (4.,-2.) circle (2.5pt);
\draw [fill=black] (2.,-1.) circle (2.5pt);
\draw [fill=black] (6.,-1.) circle (2.5pt);
\draw [fill=black] (2.,1.) circle (2.5pt);
\draw [fill=ududff] (5.,2.) circle (2.5pt);
\draw [fill=black] (5.,2.) circle (2.5pt);
\end{scriptsize}
\end{tikzpicture}
}
\qquad
\subfloat[The lattice $N_5$  which has an empty bottom element.\label{NM1}]{
\definecolor{ududff}{rgb}{0.30196078431372547,0.30196078431372547,1.}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\clip(1.37,-2.55) rectangle (7,3);
\draw [line width=0.4pt] (4.,-2.)-- (2.,-1.);
\draw [line width=0.4pt] (4.,-2.)-- (6.,-1.);
\draw [line width=0.4pt] (2.,-1.)-- (2.,1.);
\draw [line width=0.4pt] (2.,1.)-- (5.,2.);
\draw [line width=0.4pt] (6.,-1.)-- (5.,2.);
\draw (3.76,-2.0354248486414646) node[anchor=north west] {$\emptyset$};
\draw (1.2,-0.6) node[anchor=north west] {$Q_1$};
\draw (6.126431693679114,-0.6) node[anchor=north west] {$Q_2'$};
\draw (1.2,1.5) node[anchor=north west] {$Q_3$};
\draw (3.75,2.8) node[anchor=north west] {$\ll Q_1, Q_2'\gg$};
\begin{scriptsize}
\draw [fill=black] (4.,-2.) circle (2.5pt);
\draw [fill=black] (2.,-1.) circle (2.5pt);
\draw [fill=black] (6.,-1.) circle (2.5pt);
\draw [fill=black] (2.,1.) circle (2.5pt);
\draw [fill=ududff] (5.,2.) circle (2.5pt);
\draw [fill=black] (5.,2.) circle (2.5pt);
\end{scriptsize}
\end{tikzpicture}
}
\caption{One can construct the right  sublattice from the left one.}
\end{figure}
It follows from the part (2) of Theorem \ref{Thm1} that there exists a subrack $Q'_2$ of $Q_2$ which is a complement of $Q_1$ in $\mathcal{R}(T)$ with $T=\ll Q_1,Q_2\gg$, and hence $Q'_2\cap Q_1=\emptyset$ and $T=\ll Q_1, Q'_2\gg$. We have $Q'_2\cap Q_3\subseteq Q_2\cap Q_3=Q_2\cap Q_1$, and hence $Q'_2\cap Q_3=\emptyset$ because the intersection of $Q_1$ and $Q'_2$ is empty. We therefore obtain the  sublattice of $\mathcal{R}(R)$ shown in Figure~\ref{NM1}. By our assumption, we can reduce $Q'_2$ to  a complement of $Q_1$ in $\mathcal{R}(Q_3)$, namely $Q'_2\cap Q_3$ is a complement of $Q_1$ in $\mathcal{R}(Q_3)$. But this is impossible because $Q'_2\cap Q_3$ is  empty, a contradiction. Therefore $\mathcal{R}(R)$ is a modular lattice.
\end{proof}

\section{$G$-Racks}\label{G}

In this section, we introduce a certain class of racks called  \textit{$G$-racks}, (here "$G$" stands for  "Group", motivated by the fact that this class of racks includes all finite groups). We say that a rack $R$ is a $G$-rack if $R$ is the only subrack of $R$ which has a nonempty intersection with every orbit of $R$. By  \cite[Lemma 2.8]{Wel}, all finite groups are $G$-racks. Note that the orbits of a group  are its conjugacy classes. An example of a rack whose lattice of subracks is not distributive was introduced in \cite{SK1}. We call such a rack a \textit{$P$-rack}, and then  we show that $\mathrm{Inn}(R)$ is an abelian group if and only if $R$ is a $P$-rack for all racks $R$. Next, we give an example of an infinite group which is not a $G$-rack. Finally, we provide some equivalent properties to being a Boolean algebra for $G$-racks.

\medskip
Now, we introduce $P$-racks. Let $R$ be a set, and  $\{R_i\}_{i\in I}$  be a partition of $R$. Assume that $\{f_i\}_{i\in I}$ is a family of permutations on $R$ such that $f_i(R_j)=R_j$ and $f_if_j=f_jf_i$ for all $i,j\in I$. If $x\tg y=f_i(y)$  for all $x,y\in R$ where $x\in R_i$, then $(R,\tg)$ is a rack  which we call a $P$-rack (here "P" comes from "Partition"). This rack is a quandle if and only if for each $i\in I$ the restriction of $f_i$ to $R_i$ is the identity. We denote such a $P$-rack by $\left(R,\{R_i\}_{i\in I},\{f_i\}_{i\in I}\right)$. See also \cite[Example 2.9]{SK1}.

In the next proposition, we show that any $P$-rack is a  $G$-rack.

\begin{Proposition}
All $P$-racks are $G$-racks.
\end{Proposition}

\begin{proof}
Let $\left(R,\{R_i\}_{i\in I},\{f_i\}_{i\in I}\right)$ be a $P$-rack. Suppose that $\mathcal{O}$ is the collection of all orbits of $R$, and $Q$ is a subrack of $R$ such that $Q\cap X\neq\emptyset$ for every $X\in\mathcal{O}$. Note that for each orbit $X$ of $R$, there is a unique $i\in I$ for which $X\subseteq R_i$.  For an  element $x\in R$, let $X$ be the orbit including $x$. Let $X\subseteq R_i$ for some $i\in I$, and $y\in Q\cap X$. There is an element $\phi=f_{a_1}\cdots f_{a_l}$ in $\mathrm{Inn}(R)$ for which $\phi(y)=x$. Note that for each $j\in I$, the elements of $R_j$ have the same action on the other elements of $R$. Therefore by the assumptions, we have $\phi\in\mathrm{Inn}(Q)$, and hence $x\in Q$. It follows that $R$ is a $G$-rack.
\end{proof}

In the next theorem, we characterize all racks with  abelian inner groups. Indeed, we show that such racks are exactly the same as the $P$-racks.
\begin{Theorem}
Let $R$ be a rack. Then $\mathrm{Inn}(R)$ is an abelian group if and only if $R$ is a $P$-rack.
\end{Theorem}

\begin{proof}
By definition of a $P$-rack, it is obvious that the inner group of a $P$-rack is abelian. Conversely, assume that $R$ is a rack with  abelian inner group. We define the equivalence relation $\sim$ on $R$ as the following: for all $x,y\in R$, we have $x\sim y$ if and only if $f_x=f_y$. Now, we show that the partition given by these equivalence classes is a desired partition as in the definition of a $P$-rack. It is enough to show that for each $x,y\in R$, the elements $f_x(y)$, $f_x^{-1}(y)$ and $y$ belong to a same class, namely $f_{f_x(y)}=f_{f_x^{-1}(y)}=f_y$. The latter equalities hold, since we have $f_{f_x(y)}=f_xf_yf_x^{-1}=f_y$ and $f_{f_x^{-1}(y)}=f_x^{-1}f_yf_x=f_y$ by \cite[Lemma 2.1]{SK1}, and  $\mathrm{Inn}(R)$ is abelian by our assumption.
\end{proof}

The following lemma plays an important role in the sequel.
\begin{Lemma}\label{Lemma}
Any rack is a $G$-rack if and only if its corresponding quandle is a $G$-rack.
\end{Lemma}

\begin{proof}
Let $(R,\tg)$ be a rack, and let $\overline{x}$ be the atom including $x$ for any $x\in R$.  For any subrack $Q$ of $R$, let $\overline{Q}=\{\overline{x}:x\in Q\}$. Then by \cite[Corollary 2.7]{SK1}, the map $Q\mapsto\overline{Q}$ defines a lattice isomorphism from $\mathcal{R}(R)$ to $\mathcal{R}(\overline{R})$ mapping the orbits of $R$ to the orbits of $\overline{R}$.

Now, let $R$ be a $G$-rack, and let $\{X_i\}_{i\in I}$ be the set of all orbits of $R$. Then $\{\overline{X_i}\}_{i\in I}$ is the set of all orbits of $\overline{R}$. We show that $\overline{R}$ is a $G$-rack. Let $\overline{Q}$ be a subrack of $\overline{R}$ such that $\overline{Q}\cap \overline{X_i}\neq\emptyset$ for any $i\in I$. Then $Q\cap X_i\neq\emptyset$ for any $i\in I$, since the map is one-to-one and $\overline{\emptyset}=\emptyset$. It follows that $Q=R$, since $R$ is a $G$-rack, and hence $\overline{Q}=\overline{R}$. Thus $\overline{R}$ is a $G$-rack as well. The converse follows similarly.
\end{proof}

An \textit{orthocomplemented} lattice  is a complemented lattice $L$ equipped with a function $\phi:L\to L$ such that $\phi^2=id$, $\phi(x)$ is a complement of $x$ in $L$, and $\phi(y)\le\phi(x)$ for all $x,y\in L$ with $x\le y$.

 In the next theorem, we characterize modular, relatively complemented and orthocomplemented  $G$-racks.

 \begin{Theorem}\label{Prop}
 Let $R$ be a $G$-rack. Then the following statements are equivalent:
 \begin{enumerate}
 \item
 $\mathcal{R}(R)$ is a Boolean algebra.
 \item
 $\mathcal{R}(R)$ is modular.
 \item
 $\mathcal{R}(R)$ is relatively complemented.
 \item
 $\mathcal{R}(R)$ is orthocomplemented.
 \end{enumerate}
 \end{Theorem}

\begin{proof}
It is a well-known fact that (1) implies the other statements (see \cite[Section~6]{Gra}), and hence it is enough to show that each of  (2), (3) and (4) implies (1). By Lemma \ref{Lemma}, without loss of generality, we may assume that $R$ is a quandle. To see that $\mathcal{R}(R)$ is a Boolean algebra, it is enough to show that every orbit of $R$ is a singleton.  Let  $X$ be  an orbit of $R$ and $x\in X$. We can assume that $R$ has some orbits other than $X$, since otherwise, by definition of a $G$-rack, it follows that $R=\{x\}=X$, and hence there is nothing to prove. Note that if for a subrack $Q$ of $R$, we have $\ll X,Q\gg=R$, then $Q$ has a nonempty intersection with every orbit $Y\neq X$. Indeed, if  there is an orbit $Y\neq X$ with $Y\cap Q=\emptyset$, then $\ll X, Q\gg\subseteq R\backslash Y$, a contradiction. In particular, each complement of $X$ in $\mathcal{R}(R)$ has a nonempty intersection with every orbit of $R$ except $X$.  Now we consider the following cases:

First, suppose that $\mathcal{R}(R)$ is modular. If $X\neq\{x\}$, then $\mathcal{R}(R)$ has the sublattice $N_5$ shown in Figure \ref{f3}. Hence $\mathcal{R}(R)$ is not modular which is a contradiction.

\begin{figure}
\definecolor{ududff}{rgb}{0.30196078431372547,0.30196078431372547,1.}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\clip(0,-2.55) rectangle (8,3);
\draw [line width=0.4pt] (4.,-2.)-- (2.,-1.);
\draw [line width=0.4pt] (4.,-2.)-- (6.,-1.);
\draw [line width=0.4pt] (2.,-1.)-- (2.,1.);
\draw [line width=0.4pt] (2.,1.)-- (5.,2.);
\draw [line width=0.4pt] (6.,-1.)-- (5.,2.);
\draw (3.76,-2.0354248486414646) node[anchor=north west] {$\emptyset$};
\draw (1,-0.6) node[anchor=north west] {$\{x\}$};
\draw (6.126431693679114,-0.6) node[anchor=north west] {$R\backslash X$};
\draw (1.2,1.33) node[anchor=north west] {$X$};
\draw (4.7,2.7) node[anchor=north west] {$R$};
\begin{scriptsize}
\draw [fill=black] (4.,-2.) circle (2.5pt);
\draw [fill=black] (2.,-1.) circle (2.5pt);
\draw [fill=black] (6.,-1.) circle (2.5pt);
\draw [fill=black] (2.,1.) circle (2.5pt);
\draw [fill=ududff] (5.,2.) circle (2.5pt);
\draw [fill=black] (5.,2.) circle (2.5pt);
\end{scriptsize}
\end{tikzpicture}
\caption{Nontrivial $G$-racks do not have the sublattice $N_5$. \label{f3}}
\end{figure}

Next, suppose that $\mathcal{R}(R)$ is relatively complemented. Consider the interval $[\{x\},R]$. Suppose that $T$ is  a complement of $X$ in the interval $[\{x\},R]$, and hence $T\cap X=\{x\}$ and $T$ has a nonempty intersection with every orbit of $R$. This implies that $T=R$, since $R$ is a $G$-rack. Now, it follows from $T\cap X=\{x\}$ that $X=\{x\}$.

Finally, suppose that $\mathcal{R}(R)$ is orthocomplemented. Let $\phi:\mathcal{R}(R)\to\mathcal{R}(R)$ be a desired function as in the definition. Note that $\phi(X)$ has a nonempty intersection with every orbit of $R$ except $X$, since $\phi(X)$ is a complement of $X$ in $R$. We have $\phi(X)\subseteq\phi(\{x\})$, and hence $\phi(\{x\})$ has a nonempty intersection with every orbit of $R$ except $X$, as well. If $\phi(\{x\})\nsubseteq R\backslash X$, then $\phi(\{x\})$ has a nonempty intersection with every orbit of $R$, and hence $\phi(\{x\})=R$, since $R$ is a $G$-rack. But this is a contradiction, since  $\phi(\{x\})$ is a complement of $\{x\}$ in $\mathcal{R}(R)$. Therefore, we have $\phi(\{x\})\subseteq R\backslash X$, and hence $\phi(R\backslash X)\subseteq \phi^2(\{x\})=\{x\}$. This implies that $\phi(R\backslash X)=\{x\}$. Repeating the above arguments, for any $y\in X$, shows that $\phi(R\backslash X)=\{y\}=\{x\}$. Thus $X=\{x\}$.
 \end{proof}

 \begin{figure}[h]
\centering
\subfloat[The lattice $N_5$ in $\mathcal{R}(S_3)$.\label{NMM}]{
\definecolor{ududff}{rgb}{0.30196078431372547,0.30196078431372547,1.}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\clip(1.3,-2.55) rectangle (7,3);
\draw [line width=0.4pt] (4.,-2.)-- (2.,-1.);
\draw [line width=0.4pt] (4.,-2.)-- (6.,-1.);
\draw [line width=0.4pt] (2.,-1.)-- (2.,1.);
\draw [line width=0.4pt] (2.,1.)-- (5.,2.);
\draw [line width=0.4pt] (6.,-1.)-- (5.,2.);
\draw (3.75,-2.0354248486414646) node[anchor=north west] {$\emptyset$};
\draw (1.9,-0.5) node[anchor=north west] {\small{$\{(1\quad 2\quad 3)\}$}};
\draw (4.3,-0.5) node[anchor=north west] {\small{$\{(1\quad 2)\}$}};
\draw (1.2,1.5) node[anchor=north west] {$A_3$};
\draw (4.7,2.8) node[anchor=north west] {$S_3$};
\begin{scriptsize}
\draw [fill=black] (4.,-2.) circle (2.5pt);
\draw [fill=black] (2.,-1.) circle (2.5pt);
\draw [fill=black] (6.,-1.) circle (2.5pt);
\draw [fill=black] (2.,1.) circle (2.5pt);
\draw [fill=ududff] (5.,2.) circle (2.5pt);
\draw [fill=black] (5.,2.) circle (2.5pt);
\end{scriptsize}
\end{tikzpicture}
}
\qquad
\subfloat[The lattice $N_5$  in $\mathcal{R}(Q_8)$.\label{NMM1}]{
\definecolor{ududff}{rgb}{0.30196078431372547,0.30196078431372547,1.}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\clip(1.37,-2.55) rectangle (7,3);
\draw [line width=0.4pt] (4.,-2.)-- (2.,-1.);
\draw [line width=0.4pt] (4.,-2.)-- (6.,-1.);
\draw [line width=0.4pt] (2.,-1.)-- (2.,1.);
\draw [line width=0.4pt] (2.,1.)-- (5.,2.);
\draw [line width=0.4pt] (6.,-1.)-- (5.,2.);
\draw (3.76,-2.0354248486414646) node[anchor=north west] {$\emptyset$};
\draw (1.185,-0.6) node[anchor=north west] {$\{i\}$};
\draw (6.,-0.6) node[anchor=north west] {$\{j\}$};
\draw (1.195,1.75) node[anchor=north west] {$\{\pm i\}$};
\draw (4.1,2.8) node[anchor=north west] {$\{\pm i,\pm j\}$};
\begin{scriptsize}
\draw [fill=black] (4.,-2.) circle (2.5pt);
\draw [fill=black] (2.,-1.) circle (2.5pt);
\draw [fill=black] (6.,-1.) circle (2.5pt);
\draw [fill=black] (2.,1.) circle (2.5pt);
\draw [fill=ududff] (5.,2.) circle (2.5pt);
\draw [fill=black] (5.,2.) circle (2.5pt);
\end{scriptsize}
\end{tikzpicture}
}
\qquad
\subfloat[The lattice $N_5$  in $\mathcal{R}(D_8)$.\label{NMMM1}]{
\definecolor{ududff}{rgb}{0.30196078431372547,0.30196078431372547,1.}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\clip(1.25,-2.55) rectangle (7,3);
\draw [line width=0.4pt] (4.,-2.)-- (2.,-1.);
\draw [line width=0.4pt] (4.,-2.)-- (6.,-1.);
\draw [line width=0.4pt] (2.,-1.)-- (2.,1.);
\draw [line width=0.4pt] (2.,1.)-- (5.,2.);
\draw [line width=0.4pt] (6.,-1.)-- (5.,2.);
\draw (3.76,-2.0354248486414646) node[anchor=north west] {$\emptyset$};
\draw (1.05,-0.6) node[anchor=north west] {$\{\sigma\}$};
\draw (6.,-0.6) node[anchor=north west] {$\{\tau\}$};
\draw (1.195,1.84) node[anchor=north west] {$\{\sigma,\sigma^3\}$};
\draw (3.75,2.8) node[anchor=north west] {$\{\sigma,\tau,\sigma^3,\sigma^2\tau\}$};
\begin{scriptsize}
\draw [fill=black] (4.,-2.) circle (2.5pt);
\draw [fill=black] (2.,-1.) circle (2.5pt);
\draw [fill=black] (6.,-1.) circle (2.5pt);
\draw [fill=black] (2.,1.) circle (2.5pt);
\draw [fill=ududff] (5.,2.) circle (2.5pt);
\draw [fill=black] (5.,2.) circle (2.5pt);
\end{scriptsize}
\end{tikzpicture}
}
\caption{The lattices of subracks of $S_3$, $Q_8$ and $D_8$ are not modular.\label{f2}}
\end{figure}
 As an immediate consequence of Theorem \ref{Prop}, the lattice of subracks of a finite group $G$ is modular, relatively complemented or orthocomplemented if and only if $\{x,y\}$  is a subrack of $G$ for all $x,y\in G$. Therefore, these equivalent conditions imply that  each two elements of $G$ commute with each other. Let $Q_8=\{\pm1, \pm i,\pm j,\pm k\}$ and $D_8=\left<\sigma,\tau:\sigma^4=1,\tau^2=1, \tau\sigma=\sigma^3\tau\right>$ be the quaternion group and dihedral group, respectively. In \cite{Wel},  all finite groups whose lattice of subracks is graded (i.e. all maximal chains of the lattice have the same length) were characterized.  Indeed, it was shown that the lattice of subracks of a finite group is graded if and only if the group is abelian, $S_3$, $D_8$ or $Q_8$. See Figure \ref{f2} to observe why $S_3$, $Q_8$ and $D_8$ have non-modular lattice of subracks. We would also like to remark that in  Theorem~\ref{Prop}, we  directly determined the groups (including infinite groups) with the modular lattice of subracks  without using the fact that modular lattices are graded.

The \textit{order complex} of a poset $P$, denoted by $\Delta(P)$, is the set of all chains of $P$. Here, by the homotopy type of a poset $P$, we mean  the homotopy type of the order complex of $\overline{P}=P\backslash\{\hat{0},\hat{1}\}$. In the following, we determine the homotopy type of the lattice of subracks of a finite $G$-rack as a generalization of  \cite[Proposition~1.1]{Wel} for the lattice of subracks of a finite group. For this purpose, we need the well known nerve lemma (see \cite[Theorem~10.7]{Bjo}). The \textit{nerve} of a family $\mathcal{A}=\{A_i\}_{i\in I}$ of sets, denoted by $\mathcal{N}(\mathcal{A})$,  is a simplicial complex whose faces are the subsets $J$ of $I$ for which $\bigcap_{j\in J}A_j$ is nonempty. A \textit{covering} for a simplicial complex $\Delta$ is a collection $\{\Delta_i\}_{i\in I}$ of subcomplexes of $\Delta$ such that $\Delta=\bigcup_{i\in I}\Delta_i$.

\begin{Lemma}{(Nerve Lemma) }\label{Nerve}
Let $\Delta$ be a finite simplicial complex, and let $\mathcal{A}=\{\Delta_i\}_{i=1}^n$ be  a covering for $\Delta$. If for every $J\subseteq\{1,\ldots,n\}$, the intersection $\bigcap_{j\in J}\Delta_j$ is  $\{\emptyset\}$ or contractible, then $\mathcal{N}(\mathcal{A})$ and $\Delta$ have the same homotopy type.
\end{Lemma}

Now, we are ready to prove the following theorem.

\begin{Theorem}
Let $R$ be a finite $G$-rack which has $c$ orbits. Then $\mathcal{R}(R)$ has the homotopy type of  the $(c-2)$-dimensional sphere, $S^{c-2}$.
\end{Theorem}

\begin{proof}
For every subrack $Q$ of $R$, let
\[\Delta_Q=\left\{\{\sigma_0,\ldots,\sigma_t\}\in\Delta(\overline{\mathcal{R}(R)}): \emptyset\subsetneq\sigma_0\subsetneq\cdots\subsetneq \sigma_t\subseteq Q\right\}.\]
In particular, $\Delta_{\emptyset}=\{\emptyset\}$. We have that $\mathcal{A}=\left\{\Delta_M: \text{$M$ is a maximal subrack of $R$}\right\}$ is a covering for $\Delta(\overline{\mathcal{R}(R)})$. Let $\{X_1,\ldots,X_c\}$ be the set of all orbits of $R$. Then $M$ is a maximal subrack of $R$ if and only if $M=R\backslash X_i$ for some $i=1,\ldots,c$, since $R$ is a $G$-rack. Let $M_i=R\backslash X_i$ for all $i=1,\ldots,c$, and let $I\subseteq\{1,\ldots,c\}$. Then it follows that $\bigcap_{i\in I}\Delta_{M_i}=\{\emptyset\}$ if and only if $I=\{1,\ldots,c\}$. This implies that the facets of $\mathcal{N}(\mathcal{A})$ are exactly the subsets of $\{1,\ldots,c\}$ with $c-1$ elements. Thus $\mathcal{N}(\mathcal{A})$ has the homotopy type of $S^{c-2}$. It is clear that for any nonempty  subrack $Q\neq R$,  the simplicial complex $\Delta_Q$ is a cone over $Q$, so that $\Delta_Q$ is contractible. On the other hand, for any $I\subseteq\{1,\cdots c\}$ we have $\bigcap_{i\in I}\Delta_{M_i}=\Delta_{\bigcap_{i\in I}M_i}$ which is $\{\emptyset\}$ or a cone over $\bigcap_{i\in I}M_i$, and hence it is $\{\emptyset\}$ or contractible. Now, it follows from Lemma \ref{Nerve} that the homotopy types of $\Delta(\overline{\mathcal{R}(R)})$ and $\mathcal{N}(\mathcal{A})$ are the same, and hence  $\Delta(\overline{\mathcal{R}(R)})$ has the homotopy type of $S^{c-2}$.
\end{proof}

Despite all finite groups are $G$-racks, in the next example we show that there are some infinite groups which are not $G$-racks.

\begin{Example}
Let $H$ be the subgroup of all permutations on $\mathbb{N}$ fixing all elements  except a finite number of elements. One could consider $H$ as $\bigcup_{n\in\mathbb{N}}S_n$ where $S_n$ and its natural embedding in $S_{\mathbb{N}}$ are identified for all $n\in\mathbb{N}$. The orbits of $H$ are exactly its conjugacy classes. Hence any orbit of $H$ including an element $x$ also contains all elements of $H$ which have the same cycle structure as $x$. We show that $H$ is not a $G$-rack. Note that the set of all orbits of $H$ is countable. Let $\{C_i\}_{i\in\mathbb{N}}$ be the set of all orbits of $H$. Then we can choose inductively pairwise disjoint permutations $g_i\in C_i$. Let $Q=\{g_i\}_{i\in I}$. Then any  two elements of $Q$ commute with each other, and hence $Q$ is a subrack of $H$. Therefore $Q$ is a proper subrack of $H$ including an element of every orbit of $H$ which implies that $H$ is not a $G$-rack.
\end{Example}

\section{Complementedness of The Lattices of Subracks of Infinite Racks}\label{S}
In this section, we show that the lattice of subracks of an infinite rack is not necessarily complemented which answers  Question~\ref{Que}. To do this, we show that the lattice of subracks of $\mathbb{Q}$, as a dihedral rack, is not complemented. This example also shows that a rack may not have a maximal subrack. Indeed in Section~\ref{sec1} to prove that the lattice of subracks of every finite rack is complemented, we  used the fact that every subrack is contained in a maximal subrack. We also provide examples of infinite racks whose lattices of subracks are complemented. Although all trivial racks have  complemented lattices of subracks, there are some non-trivial infinite racks whose lattices of subracks are complemented.

\medskip
First, in the following lemma, we characterize all subracks of $\mathbb{Q}$ as a dihedral rack. We use this characterization to show that the dihedral rack $\mathbb{Q}$ is not complemented.

\begin{Lemma}\label{Lemma1}
The nonempty subracks of $\mathbb{Q}$ (as a dihedral rack) are exactly the cosets of the subgroups of $\mathbb{Q}$.
\end{Lemma}

\begin{proof}
Let $Q$ be a nonempty subrack of $\mathbb{Q}$. First, assume that $0\in Q$. Then for any integer $s$ and any $z\in Q$, one has $sz\in Q$. Indeed, if $s\ge 0$, then $sz\in Q$ and $-sz\in Q$ by induction on $s$, since $(sz)\tg\left((s-1)z\right)=(s+1)z$ and $0\in Q$. Now, we show that $Q$ is a subgroup of $\mathbb{Q}$. Let $x,y\in Q$ where $x=a/b$ and $y=c/d$  for some integers $a,b,c,d$. If $x=0$ or $y=0$, then obviously $x-y\in Q$. Let $e=\mathrm{gcd}(ad,bc)$. Then either $e=\mathrm{gcd}(2ad,bc)$ or $e=\mathrm{gcd}(ad,2bc)$. Without loss of generality, assume that $e=\mathrm{gcd}(2ad,bc)$. Thus, there are integers $s,t$ for which $2sad-tbc=e$. So, it follows from $(sx)\tg(ty)\in Q$ that $e/bd\in Q$, and hence $x-y$, which is a multiple of $e/bd$, belongs to $Q$.\\
Next, assume that $Q$ is an arbitrary nonempty subrack of $\mathbb{Q}$ and $x\in Q$. One could observe that $Q-x$ is a subrack of $\mathbb{Q}$ including $0$, and hence by the above argument $Q-x$ is a subgroup of $\mathbb{Q}$. Therefore, $Q$ is a coset of a subgroup of $\mathbb{Q}$.
\end{proof}

Now, we are ready to show that there are infinite racks whose lattices of subracks are not complemented.

\begin{Theorem}
The lattice of subracks of $\mathbb{Q}$ (as a dihedral rack) is not complemented.
\end{Theorem}

\begin{proof}
Suppose that $Q$ is a nonempty subrack of $\mathbb{Q}$. Then $Q=H+x$ where $H$ is a subgroup of $\mathbb{Q}$ and $x\in Q$ by Lemma \ref{Lemma1}. Now let $L=\ll Q,0\gg$ which is a subgroup of $\mathbb{Q}$ by Lemma \ref{Lemma1}. We show that $L=H+\left<x\right>$. Since $H+\left<x\right>$ contains $Q\cup\{0\}$, we have $L\subseteq H+\left<x\right>$. On the other hand,  for any $h\in H$ and any integer $s$, we have $h+sx=(h+x)+(s-1)x\in L$, since $L$ is a subgroup of $\mathbb{Q}$. Therefore $H+\left<x\right>\subseteq L$.

Now, we show that the subrack $\{0\}$ does not have any complement in $\mathcal{R}(\mathbb{Q})$. On contrast, assume that $Q=H+x$ is a complement of $\{0\}$ in $\mathcal{R}(\mathbb{Q})$, where $H$ is a subgroup of $\mathbb{Q}$ and $x\in Q$. It follows that $H+\left<x\right>=\mathbb{Q}$, and hence $\mathbb{Q}/H$ and $\left<x\right>/\left(\left<x\right>\cap H\right)$ are isomorphic groups. Since $0\notin Q$ it follows that  $x\neq 0$. Let $x=r/s$.  Then $\{0\}\neq\left<r\right>\subseteq\left<x\right>$. Moreover, $H\neq\{0\}$ implies that there exists a nonzero element $y=t/u\in H$, and hence $\{0\}\neq\left<t\right>\subseteq H$. Therefore,  $\left<rt\right>\subseteq H\cap\left<x\right>$, and hence $\left<x\right>/\left(\left<x\right>\cap H\right)$ is a finite cyclic group. This implies that $H$ is a proper subgroup of $\mathbb{Q}$ with finite index which is a contradiction.
\end{proof}

In the following example, we show that the lattice of subracks of every $G$-rack is complemented.

\begin{Example}
Let $R$ be a $G$-rack, and let $Q$ be a subrack of $R$. Assume that $L$ is the union of all orbits of $R$ whose intersections with $Q$ are all empty. Then $L$ and $Q$ are disjoint and $\ll Q, L\gg$ has a nonempty intersection with any orbit of $R$, and hence $\ll Q, L\gg=R$. It follows that $L$ is a complement of $Q$ in $\mathcal{R}(R)$. As a consequence, the lattice of subracks of every $P$-rack is complemented as well.
\end{Example}

In the next example, we provide an infinite quandle whose lattice of subracks is complemented.

\begin{Example}
Let $R$ be the quandle of all transpositions in $S_{\mathbb{N}}$ equipped with the conjugation operation. We show that $\mathcal{R}(R)$ is complemented. Note that for any subrack $Q$ of $R$ and any transposition $(a\;\;b)$ of $R$, we have
\[ \ll Q, (a \;\; b)\gg=Q\cup\{(a\;\; x): \exists x\in\mathbb{N}\;(x\;\;b)\in Q\}\cup\{(b\;\; x): \exists x\in\mathbb{N}\;(x\;\;a)\in Q\},\]
by \cite[Lemma 2.2]{SK1}.
Now, let $Q$ be a subrack of $R$ and $\Gamma$ be the set of all subracks $T$ of $R$ with $T\cap Q=\emptyset$. One could easily observe that $\Gamma$ is nonempty and any chain in $\Gamma$ has an upper bound in $\Gamma$. Thus $\Gamma$ has a maximal element $Q'$ by Zorn's Lemma. We show that $Q'$ is a complement of $Q$ in $\mathcal{R}(R)$. Suppose on contrast that $\ll Q,Q'\gg\neq R$, and hence there exists a transposition $(a\;\; b)\in R\backslash\ll Q,Q'\gg$. By maximality of $Q'$ in $\Gamma$, there exists an element $(x\;\;y)\in\;\ll Q', (a\;\;b)\gg\cap\;Q$. Since $(x\;\;y)\notin Q'$ and $(x\;\;y)\in\;\ll Q', (a\;\;b)\gg$, we have $\{x,y\}\cap\{a,b\}\neq\emptyset$. Hence  we may consider $(x\;\;y)=(a\;\;z)$ and $(b\;\;z)\in Q'$ for some $z\in\{x,y\}$. This implies that $(a\;\;b)=(a\;\;z)(b\;\;z)(a\;\;z)\in\;\ll Q,Q'\gg$, a contradiction. Therefore, $Q'$ is a complement of $Q$ in $\mathcal{R}(R)$.
\end{Example}

For any rack $R$, by considering $\mathrm{Inn}(R)$ with the conjugation operation, we have the homomorphism of racks  $\phi:R\to\mathrm{Inn}(R)$ defined by $\phi(r)=f_r$ for any $r\in R$. Indeed, we have $\phi(r\tg s)=f_{r\tg s}=f_{f_r(s)}=f_rf_sf_r^{-1}=f_r\tg f_s$. Now, by considering the dihedral rack $\mathbb{Q}$, the homomorphism $\phi$ is injective, and hence $\phi(\mathbb{Q})$ is a subrack of $\mathrm{Inn}(Q)$ which is isomorphic to the rack $\mathbb{Q}$. This implies that infinite groups might have some subracks which are not complemented and do not have any maximal subracks.

In the next theorem, we provide some equivalent statements concerning the structure of the lattice of subracks of a rack.

\begin{Theorem} \label{equi}
Let $R$ be a rack. Then the following statements are equivalent:
\begin{enumerate}
\item
$\mathcal{R}(R)$ is a Boolean algebra.
\item
$\mathcal{R}(R)$ is distributive.
\item
$\mathcal{R}(R)$ is pseudocomplemented.
\item
$\mathcal{R}(R)$ is uniquely complemented.
\end{enumerate}
\end{Theorem}

\begin{proof}
It was shown in \cite[Theorem 2.8]{SK1} that the statements (1) and (2) are equivalent. Now, we show that the other statements are equivalent to the statement (1). By \cite[Corollary 2.7]{SK1}, we have that  the lattice of subracks of every rack is isomorphic to the one for its corresponding quandle, and hence here it is enough to consider quandles.

First, assume that $\mathcal{R}(R)$ is pseudocomplemented. It is enough to show that $f_x(y)=y$ for all $x,y\in R$. Assume on contrast  that there exist $x,y\in R$ with $f_x(y)\neq y$.  For every $z\in R\backslash\{y\}$, it follows from $\{y\}\wedge\{z\}=\hat{0}$ that $z\in\{y\}^*$, and hence $\{y\}^*=R\backslash\{y\}$. Since $f_x(y)\neq y$, we have $f_x(y)\in \{y\}^*$. Hence $y=f_x^{-1}(f_x(y))\in \{y\}^*$, because $x\in \{y\}^*$, which is a contradiction. Therefore $\mathcal{R}(R)$ is a Boolean algebra. Conversely, it is well-known that every Boolean algebra is pseudocomplemented.

Next, suppose that $\mathcal{R}(R)$ is uniquely complemented.  Assume on contrast that $f_x(y)\neq y$ for some $x,y\in R$. Consider $Q$ as the unique complement of $\{y\}$ in $\mathcal{R}(R)$, and hence $\ll y,Q\gg=R$ and $y\notin Q$. One could observe that
\[\ll Q, f_q(y)\gg=\ll f_y(Q),y\gg=\ll y,Q\gg=R,\]
for any $q\in Q$. It follows from $y\notin Q$ that  $y\notin f_y(Q)$ and $f_q(y)\notin Q$ for any $q\in Q$. Therefore, by uniquely complementedness of $\mathcal{R}(R)$, we have $f_y(Q)=Q$ and $f_q(y)=y$ for any $q\in Q$. This implies that $R=\ll y,Q\gg=Q\cup\{y\}$, and hence $Q=R\backslash\{y\}$. Then, similar to the proof of equivalency of (1) and (3), we get a contradiction, and hence $\mathcal{R}(R)$ is a Boolean algebra (see also \cite[Theorems 1,2]{Bir}). The converse  follows from the well-known fact that every Boolean algebra is a uniquely complemented lattice.
\end{proof}
\section*{Acknowledgements}
The authors would like to thank Sara Saeedi Madani for her useful comments. The authors would also like to thank the institute for research in fundamental sciences (IPM) for financial support. The research of the second author was in part supported by a grant from IPM (No. 96050212).


TITLE: Divisor Function Proofs
QUESTION [1 upvotes]: I am trying to decipher the proofs to the following statements:
Let $d$ be the divisor function, then;

show that $d(n)$ is odd if and only if $n$ is a square
Show that for a given $n\geq 2$, there are infinitely many positive integers $x$ such
that $d(x) = n$.

I am trying to go through them, but I keep getting stuck along the way. Help answering the question would be appreciated

REPLY [1 votes]: Hint for the first : If $n=p_1^{a_1}...p_k^{a_k}$, then $d(n)=(a_1+1)...(a_k+1)$
Note that all factors have to be odd, if $d(n)$ is odd.
Hint for the second : Use $N=p^{n-1}$ , $p$ any prime.


TITLE: How do I solve this problem on successive percentages?
QUESTION [0 upvotes]: Question:
" The population of a city in 2017 increased by 12.5 % from 2016 and in 2018 it decreased by 8 % with respect to previous year and in 2019 it again increased by 15 % with respect to previous year. If in 2019, the population of the city is 1190250,then what was the population of city in 2016?"
My doubt is exactly whether the increased population is after 2019 or in 2019. Eitherways how do I calculate the value from there. A detailed guidance into the same will be most welcome. Infact the calculation behind the process will be very helpful for me. What is the thinking process behind successive percentage? Some amount of help will be most welcome.

REPLY [0 votes]: I think this is a classic type of exercise, to stress the fact that applying percentages to a number in different orders leads to different results.
The way I would approach this is by writing one equation per statement, using the population in various years as variables. For example, supposing the population at year $y$ is called $P_y$, from the data in the text:
$$ P_{17} = 1.125 P_{16} $$
$$ P_{18} = 0.92 P_{17} $$
$$ P_{19} = \ldots P_{18}$$
and I'll leave the coefficient in the last equation to you.
Then, since the text gives you the value of $P_{19}$, you can work your way bak one year at a time to find $P_{16}$.
My interpretation is that $1190250$ is the population at the end of $2019$.


TITLE: contour integration of log.
QUESTION [2 upvotes]: I am looking at a contour integration of the following function:
$f(z)=\frac{z\log(z)}{1-z^2}$ for $z\ne 1$ and $-\frac{1}{2}$ for $z=1$.
I should find the real part of the integral of $f$ in the first quadrant, namely that $z=e^{i\theta}$ for $\theta\in [0,\pi/2]$.
I first found the poles, which are $z=\pm 1$, since $z=-1$ is not in the above area, I only concerned myself my $z=1$, by applying L'Hospital rule, I found that the residual of $f(z)$ is $\frac{-1}{2}$.
Therefore I found the contour integral to be:
$I_c=2\pi\cdot i\cdot (-1/2)=-\pi\cdot i$. Which then has a zero real part.
I think this is wrong, does anybody how what I did wrong?
Thank you.

REPLY [0 votes]: We can parameterize:
$$\begin{align*}
&\text{Re}\!\int_C \frac{z\log(z)}{1-z^2}dz \\
&= -\text{Re}\!\int_0^{\pi/2} \frac{te^{2it}}{1-e^{2it}}dt&\text{(parameterize)}\\
&= -\frac{1}{4}\text{Re}\!\int_{C'}\frac{\log(z)}{1-z}dz&\text{(let } u=e^{2it}\text{)} \\
&=-\frac{1}{4}\text{Re}\!\sum_{k=0}^\infty\int_{1}^{-1}\log(z)z^kdz&\text{(geometric series)}\\
&=-\frac{1}{4}\text{Re}\!\sum_{k=0}^\infty \left(-i\pi\frac{(-1)^n}{n+1}+\frac{(-1)^n}{(n+1)^2}+\frac{1}{(n+1)^2}\right)dz&\log(z)\to-t\\
&=-\frac{1}{4}\text{Re}\!\left(-i\pi\log(2)+\frac{\pi^2}{12}+\frac{\pi^2}{6}\right)&\text{(basel problem)}\\
&=-\frac{\pi^2}{16}\\
\end{align*}$$


TITLE: Proving a quotient group is not Abelian without calculating actual cosets
QUESTION [1 upvotes]: Given the normal subgroup of S4: N={(1),(12)(34),(13)(24),(14)(23)}, show that S4/N is not Abelian.
What I did was to calculate two random cosets of N in S4,like in the picture I attached, and show they do not commute. This was kind of tedious, is there a more clever way to show it?

REPLY [5 votes]: Here is an entirely different argument:
First observe that $|S_4/N|=6$. The only groups of order 6 are $S_3$ and $C_6$. Since $S_4$ contains no element of order 6, it follows that $S_4/N$ contains no element of order 6 and therefore $S_4/N\equiv S_3$ which is non-abelian.


TITLE: what's wrong with the prove about "$f \in L_\mathrm{loc}^1(\Bbb{R}^d)$ implies a.e. point belongs to the Lebesgue set of $f$ "
QUESTION [1 upvotes]: Some definitions:
If a measurable function on $\Bbb{R}^d$ is locally integrable, if for every ball $B$ the function $f(x)\chi_B(x)$ is integrable. We shall denote by $L_\mathrm{loc}^1(\Bbb{R}^d)$ the space of all locally integrable functions.
If $f$ is locally integrable on $\Bbb{R}^d$, the Lebesgue set of $f$ consists of all points $\bar{x} \in \Bbb{R}^d$ for which $f(\bar{x})$ is finite and $$\lim_{m(B)\rightarrow 0}_{\bar{x}\in B}\frac{1}{m(B)}\int_B|f(y)-f(\bar{x})| \, \text{d}y=0$$

Theorem:
If $f \in L_\mathrm{loc}^1(\Bbb{R}^d)$,then for a.e. $x$$$\lim_{m(B)\rightarrow 0}_{x\in B}\frac{1}{m(B)}\int_Bf(y) \, \text{d}y=f(x)$$

Problem:
If $f \in L_\mathrm{loc}^1(\Bbb{R}^d)$, then almost every point belongs to the Lebesgue set of $f$.

My approach to this problem:
By definition, for a fixed $\bar{x}$, $|f(y)-f(\bar{x})| \in L_\mathrm{loc}^1(\Bbb{R}^d)$ as a function of $y$. Then I use the above theorem to this function. I get
$$\lim_{m(B)\rightarrow 0}_{\bar{x}\in B}\frac{1}{m(B)}\int_B|f(y)-f(\bar{x})| \, \text{d}y=|f(\bar{x})-f(\bar{x})|=0,$$,
then almost every point belongs to the Lebesgue set of $f$. what's wrong with my prove? thanks very much.

REPLY [1 votes]: It's possible that for a given $\bar{x}$, $\bar{x}$ is one of the few points for which the limit is not zero. Since you are defining different functions for each $\bar{x}$, conceivably this could happen for each $\bar{x}$, in which case no points would be in the Lebesgue set of $f$.


TITLE: If $g$ and $g\circ f$ are graded homomorphisms, must $f$ be graded?
QUESTION [4 upvotes]: Question

Let $A$ be a graded ring (always commutative with identity) and $M,N$ and $P$ be graded $A$-modules. Let $f:M \longrightarrow N$ and $g:N \longrightarrow P$ be $A$-module homomorphisms with $g$ being graded such that $g\circ f$ is graded. Is $f$ graded?

My thinking:
$\forall$ $m_k \in M_k$ with degree $k$. Therefore, $g\circ f(m_k) \in P_k$ since $g\circ f$ is graded. Suppose $f(m_k) = n_1 + \dots + n_r$ with $deg(n_i) = i$.
Therefore, $g\circ f(m_k) = g(n_1) + \dots + g(n_r)$. Because $g$ is graded, $deg(g(n_i)) = i$ for each $i$. We have $g(n_i) = 0$ if $i \neq k$.
That is, if $n_i \neq 0$ for some $i \neq k$ ,then $g(n_i) \neq 0$ (I think this statement has trouble...)

REPLY [7 votes]: The answer is negative: take $f$ arbitrary and $g=0$.


TITLE: Discrete Mathematics (Sets) - Simplify a set
QUESTION [0 upvotes]: The maths book give the example question:

Simplify $(A \cap B \cap C) \cup (A \cap B \cap C') \cup (A \cap B\,' \cap C)$.

($C'$ is the complement of $C$.)
The first few steps they give I understand, they simplify it to:
$$(A \cap B \cap C) \cup (A \cap C \cap B\,') \cup (A \cap B \cap C')$$
using commutative laws.
However the next step I don't understand (I know it uses distributive laws, but that's it). It goes from the above to:
$$((A \cap C) \cap (B \cup B\,')) \cup (A \cap B \cap C')$$
I understand they only touched the first 2 brackets, but I can't figure out what they've done to get there :/
The 2 Distributive laws they've given me are:
$$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$$
$$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$$
I know I'm missing something really simple, but I just can't figure it out:/ any help will be much appreciated.

REPLY [1 votes]: We can apply commutativity again to get:
$A \cap B \cap C = A \cap C \cap B$ (technically we're applying associativity and commutativity, but I hope this "short-cut" is clear).
Let's replace $A \cap C$ with the letter $X$. Then your "first two brackets" (as you call them) are:
$(X \cap B) \cup (X \cap B')$, so using the second of your distributive laws, we have:
$(X \cap B) \cup (X \cap B') = X\cap (B \cup B')$
Replacing $X$ with $A \cap C$, this becomes:
$(A \cap C) \cap (B \cup B')$, which is the part you say you didn't understand.


TITLE: Solve a Sturm-Liouville Boundary Value Problem
QUESTION [1 upvotes]: Solve the Wave Equation
I've been trying to solve the above wave equation
where $u = u(x, t)$ and $c ∈ \mathbb{R}$ is a constant, subject to
$$
u(x, 0) = 0,\;\; 0 < x < 1, \\
u_t(x, 0) = U_0x,\;\; 0 < x < 1, \\
u(0, t) = 0, \;\; t > 0, \\
u(1, t) = 0, \;\; t > 0.
$$
I know that a Sturm-Liouville Boundary Value Problem for a function $y(x)$ on some interval $a ≤ x ≤ b$ is a two-point boundary value problem which satisfies the ODE but am unsure of how to use the information given to me to solve this wave equation as a Sturm-Liouville BVP.

REPLY [1 votes]: After separation of variables, and enforcing homogeneous conditions,
$$
    u(x,t) = \sum_{n=1}^{\infty}A_n \sin(n\pi c t)\sin(n\pi x).
$$
The condition $u_t(x,0)=U_0 x$ determines the constants $A_n$:
$$
     U_0 x = \sum_{n=1}^{\infty}A_nn\pi c\sin(n\pi x)
$$
The coefficients are determined by orthogonality of the functions $\sin(n\pi x)$:
$$
     U_0\int_{0}^{\pi}x\sin(n\pi x)dx = A_n n\pi c\int_{0}^{\pi}\sin^2(n\pi x)dx \\
       A_n = \frac{U_0}{n\pi c}\cdot \frac{\int_{0}^{\pi}x\sin(n\pi x)dx}{\int_0^{\pi}\sin^2(n\pi x)dx}.
$$


TITLE: Why the area of a square is $side^2$
QUESTION [1 upvotes]: I recently stumbled upon Edwin Moise's proof of the area of a square, but there is something that is bothering me in his proof - he claims that since the inequalities $(1)$ and $(5)$ are true, then $a =\sqrt{S_a}$. but why? why $(1)$ and $(5)$ imply that there is an equality between $a$ and $\sqrt{S_a}$?
I would be grateful if you could explain his proof, especially the latter part.
Thank you!

REPLY [1 votes]: Here's another mathematical proof of the given fact. This is not really radically different from the last one, but it's more geometric in the sense that it makes the picture much more clear.
We will use $b=\sqrt{\alpha S_a}$ in this argument.
If possible let $a\neq b$ and $|b-a|=d$.
Now, because of the structure of the reals, for any $r\in \mathbb R$, we can find a sequence of rationals $\{q_n\}_{n=1}^\infty$ which converges to $r$. So, take a sequence $\{a_n\}_{n=1}^\infty$ which converges to $a$. Put $\epsilon=\frac d 2$. Because of convergence, for this choice of $\epsilon$, there is an $n\in \mathbb N$ such that $|a-a_n|<\epsilon=\frac d 2$. This gives us a contradiction.
Another way to see it is to construct the sequence and argue that since we have
$$\lim_{n\to \infty} |a_n-a|=0$$
that is the distance between $a$ and a rational $a_n$ can be made arbitrarily small, $a$ and $b$ must coincide.
I hope this makes the geometry clear.