text:
\begin{document}

\begin{abstract}
We compute the representation theory of two families of noncrossing partition quantum groups connected to amalgamated free products and free wreath products. This illustrates the efficiency of the methods developed in our previous joint work with M. Weber.
\end{abstract}

\maketitle

\section{Introduction}

Easy quantum groups are a class of compact quantum groups introduced by T. Banica and R. Speicher in \cite{banica2009liberation}. They are built from sets of partitions through a Tannaka-Kreain duality argument. In a joint work with M. Weber \cite{freslon2013representation}, we developed a general machinery to compute the representation theory of an easy quantum group out of its defining combinatorial data. However, our techniques are only completely effective when the partitions involved are \emph{noncrossing}. It turns out that the representation theory of all easy quantum groups associated to noncrossing partitions had already been computed at that time so that we could only show that our method allowed for a uniform and simple way to derive all these results.

Later on, we introduced in \cite{freslon2014partition} a generalization of easy quantum groups called \emph{partition quantum groups} to which the aforementioned results adapt straightforwardly. This potentially yields many new examples for which the tools of \cite{freslon2013representation} could be useful in describing the representation theory. In \cite{freslon2017noncrossing} we classified a family of partition quantum groups all of whose elements had never been studied before. The present paper will be concerned with computing the representation theory of some of these examples.

Our main point is to illustrate how effective the techniques of \cite{freslon2013representation} are. In particular, our first family of examples comes from amalgamated free products of compact quantum groups, for which there is no general method to study representation theory (unlike the case of classical discrete groups). Here we can very easily describe all irreducible representations together with the fusion rules. The second family is a generalization of free wreath products and once again, our method quite easily yields the result, in contrast with the technicality of the treatment of free wreath products in \cite{lemeux2013fusion}.

The main results of this paper were stated in an early version of \cite{freslon2017noncrossing}, together with sketches of proofs. We later decided to remove them and give full details in this independent article.

\section{Preliminaries}

In order to keep this work short, we will not recall all the definitions and results of the theory of partition quantum groups. We refer the reader to \cite{freslon2014partition} and the references therein for a detailed account. Our basic objects are partitions of finite sets, which we represent by drawing the elements of the set on two parallel rows and connecting them by lines if they belong to the same component of the partition. This graphical interpretation enables to concatenate partitions horizontally and vertically (if the number of points match) and rotate points from one line to another. A \emph{category of partitions} is a collection of partitions $\CC(k, l)$ on $k+l$ points for all integers $k, l$ which is globally stable under the above operations. It is moreover said to be \emph{coloured} if to each point is attached an element of a colour set $\A$. When a point of a partition is rotated from one row to another, its colour is changed into its inverse, which is defined through an involutive map $a\mapsto a^{-1}$ fixed once and for all on $\A$. To each partition $p$ we associate the word $w$ formed by the colours of the upper row (from left to right) and the word $w'$ formed by the colours of its lower row (again from left to right). We then write $p\in \CC(w, w')$.

The framework of easy quantum groups \cite{banica2009liberation} generalizes to this setting. In particular, to any category of coloured partitions $\CC$ and any integer $N$ is associated a compact quantum group $\G_{N}(\CC)$. It is generated by unitary representations $(u^{a})_{a\in \A}$ indexed by the colours and any irreducible representation is a subrepresentation of a tensor product
\begin{equation*}
u^{\otimes w} = u^{w_{1}}\otimes\cdots\otimes u^{w_{n}}.
\end{equation*}

Together with M. Weber, we developped in \cite{freslon2013representation} a method to compute the representation theory of $\G_{N}(\CC)$ by using only the combinatorial properties of $\CC$. The main tool is the so-called projective partitions :

\begin{de}
A partition $p$ is said to be \emph{projective} if $pp = p = p^{*}$. Moreover,
\begin{itemize}
\item A projective partition $p$ is said to be \emph{dominated} by $q$ if $qp = p$. Then, $pq = p$ and we write $p\preceq q$.
\item Two projective partitions $p$ and $q$ are said to be \emph{equivalent} in a category of partitions $\CC$ if there exists $r\in \CC$ such that $r^{*}r = p$ and $rr^{*} = q$. We then write $p\sim q$ or $p\sim_{\CC} q$ if we want to keep track of the category of partitions.
\end{itemize}
Note that if $p\sim q$, then $t(p) = t(q)$.
\end{de}

If $p$ and $q$ are equivalent in $\CC$, then they in fact both belong to $\CC$. Moreover, the equivalence is implemented by a unique partition denoted by $r_{p}^{q}$. As explained in \cite[Def 4.1]{freslon2013representation}, one can associate to any projective partition $p\in \CC(w, w)$ a subrepresentation $u_{p}$ of $u^{\otimes w}$. The study of these representations can be very complicated in general but in the noncrossing case (i.e. when the lines can be drawn so as not to cross) things become more tractable thanks to \cite[Thm 4.18 and Prop 4.22]{freslon2013representation} :

\begin{thm}
Let $\CC$ be a category of noncrossing partitions and let $N\geqslant 4$ be an integer. Then,
\begin{itemize}
\item $u_{p}$ is a non-zero irreducible representation for any projective partition $p$,
\item $u_{p}\sim u_{q}$ if and only if $p\sim q$,
\item $u^{\otimes w} = \displaystyle\bigoplus_{p\in \Proj(w)} u_{p}$ as a direct sum of representations. In particular, any irreducible representation is equivalent to $u_{p}$ for some projective partition $p$.
\end{itemize}
\end{thm}

To complete the description of the representation theory, we have to know how tensor products of irreducible representations split into sums of irreducible representations. This is often called the \emph{fusion rules} of the quantum group. Once again, in the noncrossing case a complete description can be obtained by combinatorial means. To explain this, we first need to introduce some specific partitions : we denote by $h_{\square}^{k}$ the projective partition in $NC(2k, 2k)$ where the $i$-th point in each row is connected to the $(2k-i+1)$-th point in the same row (i.e. an increasing inclusion of $k$ blocks of size $2$). If moreover we connect the points $1$, $k$, $1'$ and $k'$, we obtain another projective partition in $NC(2k, 2k)$ denoted by $h_{\boxvert}^{k}$. From this, we define binary operations on projective partitions, using $\idpart$ to denote the identity partition and adding suitable colours :
\begin{eqnarray*}
p\square^{k} q & = & (p_{u}^{*}\otimes q_{u}^{*})\left(\idpart^{\otimes t(p)-k}\otimes h_{\square}^{k}\otimes \idpart^{\otimes t(q)-k}\right)(p_{u}\otimes q_{u}) \\
p\boxvert^{k} q & = & (p_{u}^{*}\otimes q_{u}^{*})\left(\idpart^{\otimes t(p)-k}\otimes h_{\boxvert}^{k}\otimes \idpart^{\otimes t(q)-k}\right)(p_{u}\otimes q_{u})
\end{eqnarray*}
where $p = p_{u}^{*}p_{u}$ and $q = q_{u}^{*}q_{u}$ (such decompositions exist and are essentially unique, see \cite[Prop 2.9]{freslon2013representation}). We refer the reader to \cite[Subsec 4.5]{freslon2013representation} for more details.

\begin{thm}\label{thm:fusionrules}
Let $\CC$ be a category of noncrossing partitions and let $N\geqslant 4$ be an integer. Then, for any projective partitions $p, q\in \CC$,
\begin{equation*}
u_{p}\otimes u_{q} = u_{p\otimes q} \oplus\bigoplus_{k=1}^{\min(t(p), t(q))}u_{p\square^{k} q}\oplus u_{p\boxvert^{k} q}
\end{equation*}
with the convention that $u_{p\square^{k} q} = 0$ (resp. $u_{p\boxvert^{k} q} = 0$) if $p\square^{k} q$ (resp. $p\boxvert^{k} q$) is not in $\CC$.
\end{thm}

We end with some notations. The unique one-block partitions (i.e. with all its points connected) in $P(w, w')$ will be denoted by $\pi(w, w')$. If we consider instead the two-block partition in $P(w, w')$ where all the upper points are connected and all the lower points are connected, then we will denote it by $\beta(w, w')$.

\section{Amalgamated free products of free orthogonal quantum groups}\label{sec:biorthogonal}

Our first family of examples is linked to the free orthogonal quantum groups introduced by S. Wang in \cite{wang1995free}. In this section, $\A$ will consist in two colours $x$ and $y$ which are their own inverse. Recall from \cite{banica2009liberation} that if we denote by $\CC_{O^{+}}$ the category of all noncrossing pair partitions coloured by $x$, then $\G_{N}(\CC_{O^{+}}) = O_{N}^{+}$. Moreover, it has a projective version $PO_{N}^{+}$ generated by all the coefficients of $u^{x}\otimes u^{x}$. Consider now two copies of $\CC_{O^{+}}$, one coloured by $x$ and the other one by $y$ and form their free product amalgamated over their projective versions (see \cite{wang1995free} for the definition of amalgamated free products). This can be described as a partition quantum group using the partition $D_{xy}\in NC(2, 0)$ which is $\sqcup$ coloured with $x$ and $y$, see \cite[Lem 4.2]{freslon2017noncrossing}. We can in fact define a whole family of compact quantum groups in that way.

\begin{de}
For $\ell\geqslant 0$, we define a category of partitions $\CC_{O^{++}(\ell)}$ by
\begin{equation*}
\CC_{O^{++}(\ell)} = \left\langle \CC_{O^{+}}\ast\CC_{O^{+}}, D_{xy}^{*}D_{xy}, D_{xy}^{\otimes \ell}\right\rangle,
\end{equation*}
where by convention $D_{xy}^{\otimes 0} = \emptyset$ and $\langle\cdot\rangle$ denotes the category of partitions generated by a given set of partitions. Moreover, we write $O_{N}^{++}(\ell)$ for $\G_{N}(\CC_{O^{++}(\ell)})$.
\end{de}

The partition $D_{xy}^{*}D_{xy}$ is projective and the corresponding one-dimensional representation was explicitly described in \cite[Lem 4.3]{freslon2017noncrossing}. Let us denote by $\Gr(\G)$ the group of one-dimensional representations of a compact quantum group $\G$.

\begin{lem}\label{lem:cyclic1d}
For $1\leqslant k\leqslant N$, set
\begin{equation*}
s = \sum_{m=1}^{N}u_{km}^{x}u_{km}^{y}\in C(O_{N}^{++}).
\end{equation*}
Then, $s$ is a group-like element which does not depend on $k$. Moreover, it generates the group of group-like elements $\mathcal{G}(O_{N}^{++}(\ell))$ (which is therefore cyclic).
\end{lem}

As already mentioned,
\begin{equation*}
O_{N}^{++}(0) = O_{N}^{+}\underset{PO_{N}^{+}}{\ast}O_{N}^{+}
\end{equation*}
and $O_{N}^{++}(\ell)$ is obtained by quotienting this amalgamated free product by the relation $s^{\ell} = 1$. S. Wang gave in \cite{wang1995free} a description of all irreducible representations of a free product of quantum groups. However, there is no analogous result for amalgamated free products. That is why our computation is interesting : taking advantage of the partition structure, we can explicitly compute the representation theory of the amalgamated free product and its quotients. To do this, it will prove convenient to have an alternate description of $\CC_{O^{++}(\ell)}$. Let us first remark that any word on $\A = \{x, y\}$ can be seen as an element of the free product $\Z_{2}\ast\Z_{2}$ by sending $x$ to the generator of the first copy of $\Z_{2}$ and $y$ to the generator of the second one and denote by $\varphi$ the map sending a word to its image in $\Z_{2}\ast\Z_{2}$.

\begin{de}
For an integer $\ell$, let $\Gamma_{\ell}$ be the subgroup of $\Z_{2}\ast\Z_{2}$ generated by $\varphi(xy)^{\ell}$. A partition $p\in NC(w, w')$ is said to be \emph{$\ell$-admissible} if $\varphi(w)\varphi(w')^{-1}\in \Gamma_{\ell}$. The set of all $\ell$-admissible \emph{pair} partitions is denoted by $\DD_{\ell}$.
\end{de}

The point of this definition is that $\DD_{\ell}$ is a category of partitions and $D_{xy}^{*}D_{xy}, D_{xy}^{\otimes \ell}\in \DD_{\ell}$, hence $\CC_{O^{++}(\ell)}\subset \DD_{\ell}$. With this in hand, we are now ready to compute the fusion rules of $O_{N}^{++}(\ell)$. For convenience, we define the abstract labelling separately. By convention, we set $\Z_{0} = \Z$.

\begin{de}
For an integer $\ell$, let $W_{\ell}$ be the free monoid $\N\ast\Z_{\ell}$ and denote by $X$ and $\theta$ the generators of $\N$ and $\Z_{\ell}$ respectively. We endow this monoid with the unique antimultiplicative involution $w\mapsto \overline{w}$ induced by $\overline{X} = X$ and $\overline{\theta} = \theta^{-1}$. Eventually, we denote by $M_{\ell}$ the quotient of $W_{\ell}$ by the relation $X\theta = \overline{\theta}X$
\end{de}

\begin{thm}\label{thm:biorthogonalfusionrules}
The irreducible representations of $O_{N}^{++}(\ell)$ can be labelled, up to unitary equivalence, by the elements of $M_{\ell}$. Moreover, the fusion rules are given by the formula
\begin{equation*}
\theta^{k}X^{n}\otimes X^{n'}\theta^{k'} = \theta^{k+k'} \oplus \bigoplus_{i=0}^{\min(n, n')} \theta^{k}X^{n+n' - 2i}\theta^{k'}.
\end{equation*}
\end{thm}

\begin{proof}
Let $Z$ be the free monoid $\N\ast \N\ast \Z_{\ell}$ and denote by $X$, $Y$ and $\theta$ the generators. By noncrossingness, any projective partition in $\CC_{O^{++}(\ell)}$ is a tensor product of $\pi(x, x)$, $\pi(y, y)$ and projective partitions without through-blocks. The latter are, by Lemma \ref{lem:cyclic1d}, equivalent to tensor powers of $D_{xy}^{*}D_{xy}$ or of $D_{yx}^{*}D_{yx}$. Denoting by $X$ the equivalence class of $u_{\pi(x, x)}$, by $Y$ the equivalence class of $u_{\pi(y, y)}$ and by $\theta$ the one of $u_{D_{xy}^{*}D_{xy}}$, Lemma \ref{lem:cyclic1d} implies that the irreducible representations of $O_{N}^{++}(\ell)$ can be labelled (in a non-injective way) by $Z$. Moreover, rotating $D_{xy}^{*}D_{xy}$ yields the partition $\pi(x, y)\otimes D_{xy}$, which implements an equivalence between $\pi(x, x)\otimes (D_{xy}^{*}D_{xy})$ and $\pi(y, y)$. Hence, the relation $X\theta = Y$ holds and we do not need $Y$ to label the irreducible representations. Moreover
\begin{equation*}
\overline{\theta}X = \overline{Y} = Y = X\theta,
\end{equation*}
so that the irreducible representations of $O_{N}^{++}(\ell)$ can in fact be labelled by $M_{\ell}$. We now have a surjective map $M_{\ell}\rightarrow \Irr(O_{N}^{++}(\ell))$ and we claim that it is injective.

Note that thanks to the commutation relation $X\theta = \overline{\theta}X$, any element of $M_{\ell}$ can be written in the form $\theta^{k}X^{n}$ for $k\in \Z$ and $n\in \N$. Assume that there exist $n, n'\in \N$ and $k, k'\in \Z$ such that $\theta^{k}X^{n} = \theta^{k'}X^{n'}$ in $\Irr(O_{N}^{++}(\ell))$. This translates into the equivalence of projective partitions
\begin{equation*}
(D_{xy}^{*}D_{xy})^{\otimes k}\otimes \pi(x, x)^{\otimes n} \sim (D_{xy}^{*}D_{xy})^{\otimes k'}\otimes \pi(x, x)^{\otimes n'}.
\end{equation*}
By \cite[Lem 4.19]{freslon2013representation}, equivalent projective partitions have the same number of through-blocks. Since the number of through-blocks is the power of $\pi(x, x)$, we deduce that $n=n'$. But then, the equivalence reduces to $D_{xy}^{\otimes \vert k-k'\vert} = 1$. Because the image under $\varphi$ of this partition is $\varphi(xy)^{\vert k-k'\vert}$ and $\CC_{O^{++}(\ell)}\subset\DD_{\ell}$, it follows that $k = k' \mod \ell$, so that the two representations are already equivalent in $M_{\ell}$. We therefore conclude that $\Irr(O_{N}^{++}(\ell)) = M_{\ell}$.

For the tensor product, notice first that because of the commutation relations, any representation is equivalent to one as in the statement. Moreover,
\begin{equation*}
\pi(x, x)^{\otimes n}\square^{i}\pi(x, x)^{\otimes n'} \sim \pi(x, x)^{\otimes (n+n'-2i)}
\end{equation*}
while $\pi(x, x)^{\otimes n}\boxvert^{i}\pi(x, x)^{\otimes n'}\notin \CC_{O^{++}(\ell)}$.
\end{proof}

\begin{rem}\label{rem:amalgamateddecompositionorthogonal}
These fusion rules suggest that $O_{N}^{++}(\ell)$ may be decomposed as a product of $O_{N}^{+}$ and $\Z_{\ell}$ with some commutation relation. In fact, let $C(\G)$ be the quotient of the free product $C(O_{N}^{+})\ast C^{*}(\Z_{\ell})$ by the relations $t u_{ij} = u_{ij}t^{-1}$ for all $1\leqslant i, j\leqslant N$, where $t$ is the canonical generator of $C^{*}(\Z_{\ell})$ and $u$ is the fundamental representation of $O_{N}^{+}$. Then, the push-forward of the coproduct endows $\G$ with a compact quantum group structure which can be proven to be is isomorphic to $O_{N}^{++}$.
\end{rem}

A close look at the proof of Theorem \ref{thm:biorthogonalfusionrules} shows that it works for any category of partitions containing $\CC_{O^{++}(\ell)}$ and contained in $\DD_{\ell}$. The reason for that is, as one may guess, that these two categories are equal.

\begin{cor}
For any integer $\ell$, $\CC_{O^{++}(\ell)} = \DD_{\ell}$.
\end{cor}

\begin{proof}
By \cite[Thm 4.4]{freslon2017noncrossing}, the inclusion $\CC_{O^{++}(\ell)} \subset \DD_{\ell}$ implies that $\DD_{\ell} = \CC_{O^{++}(\ell')}$ for some integer $\ell'$. But then, it follows from the proof of Theorem \ref{thm:biorthogonalfusionrules} that
\begin{equation*}
\Z_{\ell} = \Gr(\G_{N}(\DD_{\ell})) = \Gr(O_{N}^{++}(\ell')) = \Z_{\ell'}
\end{equation*}
so that $\ell = \ell'$.
\end{proof}

\section{Free wreath products of pairs}

Our second family of examples is a generalization of the free wreath product construction of \cite{bichon2004free} called \emph{free wreath products of pairs} and introduced in \cite{freslon2017noncrossing}. Given a discrete group $\Gamma$ and an integer $N$, one can build a compact quantum group $\widehat{\Gamma}\wr_{\ast}S_{N}^{+}$ called the free wreath product of $\widehat{\Gamma}$ (this is the compact quantum group dual to $\Gamma$) by $S_{N}^{+}$. It was shown in \cite{lemeux2013fusion} that these objects are partition quantum groups. More precisely, let $S$ be a symmetric generating set of $\Gamma$ and consider a noncrossing partition coloured by $S$. We can associate to its upper and lower colouring elements of $\Gamma$ by simply multiplying the colours. Let us denote by $\varphi(w)$ the element thus obtained from a word $w$. If we denote by $\CC_{\Gamma, S}$ the set of all noncrossing partitions such that in each block with upper and lower colouring $w$ and $w'$ respectively, $\varphi(w) = \varphi(w')$, we get a category of partitions whose associated compact quantum group is by \cite[Thm 2.12]{lemeux2013fusion} exactly $\widehat{\Gamma}\wr_{\ast}S_{N}^{+}$. It turns out that this compact quantum group does not depend on $S$.

Let now $\Lambda\subset \Gamma$ be a fixed subgroup. Any element $\lambda\in \Lambda$ is by definition the image under $\varphi$ of a word $w_{\lambda}$ on $S$. Let us denote by $\CC_{\Gamma, \Lambda, S}$ the category of partitions generated by $\CC_{\Gamma, S}$ and $\beta(w_{\lambda}, w_{\lambda})$ for all $\lambda\in \Lambda$. The associated compact quantum group is denoted by $H_{N}^{++}(\Gamma, \Lambda)$ and called the \emph{free wreath product of the pair $(\Gamma, \Lambda)$ by $S_{N}^{+}$}. It is easily seen that this does not depend on $S$ or on the choice of the representatives $w_{\lambda}$. We will now compute the representation theory of this compact quantum group. To do this, it will be useful as in Section \ref{sec:biorthogonal} to embed $\CC_{\Gamma, \Lambda, S}$ into a category of partitions defined in a different way. This time however, the definition is subtler so that we first introduce some terminology :

\begin{de}
Let $p$ be a partition of $\{1, \cdots, k\}$. A subpartition $q$ (i.e.~a union of blocks of $p$) is said to be \emph{full} if it is a partition of $\{a, \cdots, a+b\}$ for some $1\leqslant a\leqslant a+b\leqslant k$.
\end{de}

For convenience, we give the definition of our auxiliary category of partitions as a Lemma.

\begin{lem}
Let $\DD_{\Gamma, \Lambda, S}$ be the set of all partitions $p\in NC^{S}(w, w')$ such that
\begin{itemize}
\item $\varphi(w) = \varphi(w')$,
\item For any full subpartition of $p$ with upper and lower colourings $v$ and $v'$ respectively, $\varphi(v)^{-1}\varphi(v')\in \Lambda$.
\end{itemize}
Then, this is a category of partitions and $\CC_{\Gamma, \Lambda, S}\subset \DD_{\Gamma, \Lambda, S}$.
\end{lem}

\begin{proof}
The first condition is clearly preserved under all category operations. As for the second one, only the stability under vertical concatenation is not obvious. So let $p, q\in \DD_{\Gamma, \Lambda, S}$ and consider a full subpartition $r$ of $qp$. If it lies on one line, it was already a full subpartition of $p$ or $q$ so that its colouring yields an element in $\Lambda$.

Otherwise, by definition $r$ consists in the first $a$ upper points of $p$ and the first $b$ lower points of $q$ or the last $a$ upper points of $p$ and the last $b$ lower points of $q$. Since the two cases are similar, we will only consider the first one. Let $r'$ be the smallest full subpartition of $p$ such that
\begin{itemize}
\item Its upper points are the first $a$ upper points of $p$,
\item It contains all the lower points of $p$ which are either connected to one of the first $a$ upper points of $p$ or correspond to upper points of $q$ which are connected to one of its first $b$ lower points.
\end{itemize}
Similarly, we consider the smallest subpartition $r''$ of $q$ such that
\begin{itemize}
\item Its lower points are the first $b$ lower points of $q$,
\item It contains all the upper points of $q$ which are either connected to one of the first $b$ lower points of $q$ or correspond to lower points of $p$ which are connected to one of its first $a$ upper points.
\end{itemize}
Let us denote by $a'$ (resp. $b'$) the number of lower (resp. upper) points of $r'$ (resp. $r''$). We claim that $a' = b'$. Indeed, assume that $a' > b'$ and consider the point $a'+1$ in $r''$. It does not correspond to an upper point of $q$ connected to one of the first $b$ lower points by definition, hence it is connected to one of the first $a$ upper points of $p$. But then the point $a'+1$ in the upper row of $q$ should be in $r''$, contradicting $a' > b'$. The impossibility of the other inequality follows in a similar way. Thus, the vertical concatenation $r''r'$ makes sense and must by definition equal $r$. Since both $r'$ and $r''$ satisfy the second condition in the statement, so does $r$.

As for the inclusion, simply notice that by definition $\CC_{\Gamma, S}\subset\DD_{\Gamma, \{e\}, S}\subset\DD_{\Gamma, \Lambda, S}$ and $\beta(w_{\lambda}, w_{\lambda})\in\DD_{\Gamma, \Lambda, S}$ for all $\lambda\in \Lambda$.
\end{proof}

With this characterization, we can start by finding all the one-dimensional representations of $H_{N}^{++}(\Gamma, \Lambda)$.

\begin{lem}\label{lem:onedwreath}
There is an isomorphism
\begin{equation*}
\Gr(H_{N}^{++}(\Gamma, \Lambda)) \simeq \Lambda.
\end{equation*}
\end{lem}

\begin{proof}
Let $p = q^{*}q$ be a non-through-block projective partition and let $w = g_{1}\cdots g_{n}$ be its upper colouring. Then,
\begin{equation*}
\beta(w, w) = \pi(w, w)p\pi(w, w)\in \CC_{\Gamma, \Lambda, S}
\end{equation*}
and since the upper points of $\beta(w, w)$ form a full subpartition, by the second defining condition of $\DD_{\Gamma, \Lambda, S}$ we have $\varphi(w) \in \Lambda$. Moreover, $\pi(w, w)p$ is an equivalence between $p$ and $\beta(w, w)$, hence the map
\begin{equation*}
\Phi :\Lambda\longrightarrow \Gr(H_{N}^{++}(\Gamma, \Lambda))
\end{equation*}
defined by $\Phi(\lambda) = \beta(w_{\lambda}, w_{\lambda})$ is a surjection. It is moreover compatible with the group multiplication and inverse, so that $\Gr(H_{N}^{++}(\Gamma, \Lambda))$ is a quotient of $\Lambda$.

Assume now that there exist $\lambda, \lambda'\in \Lambda$ such that $\beta_{\lambda} \sim \beta_{\lambda'}$. This equivalence can only be implemented by $\beta_{\lambda}\beta_{\lambda'}$ so that this partition must be in $\CC_{\Gamma, \Lambda, S}$. But by the first defining condition of $\DD_{\Gamma, \Lambda, S}$, this forces $\lambda = \lambda'$ and the result is proved.
\end{proof}

In order to describe higher-dimensional representations, let us introduce some notations : we denote by $F(\Gamma)$ the free monoid on $\Gamma$ and we consider the relation $\sim$ defined on it by
\begin{equation*}
w_{1}\dots (w_{i}.\lambda)w_{i+1}\dots w_{n}\sim w_{1}\dots w_{i}(\lambda.w_{i+1})\dots w_{n}
\end{equation*}
for any $1\leqslant i\leqslant n-1$ and $\lambda\in \Lambda$. The corresponding quotient will be denoted by $W(\Gamma, \Lambda)$.

\begin{thm}\label{thm:wreathfusionrules}
The one-dimensional representations of $H_{N}^{++}(\Gamma, \Lambda)$ can be labelled by $\Lambda$ and the other irreducible representations can be labelled by $W(\Gamma,  \Lambda)$.
\end{thm}

\begin{proof}
The result for one-dimensional representations was proved in Lemma \ref{lem:onedwreath}. For the other representations, we will split the proof into several steps.\\

\noindent\textbf{Step 1.} As a first step we claim that irreducible representations of $H_{N}^{++}(\Gamma, \Lambda)$ of dimension more than one can be labelled by $F(\Gamma)$. Consider a projective partition $p$ with at least one through-block. By noncrossingness it can be written as $p_{1}\otimes\cdots\otimes p_{n}$ where each $p_{i}$ is projective and $t(p_{i}) = 1$. If we denote by $w_{i}$ the upper colouring of $p_{i}$, then
\begin{equation*}
r = \left[\pi(w_{1}, w_{1})\otimes\cdots\otimes\pi(w_{n}, w_{n})\right]p
\end{equation*}
is an equivalence between $p$ and $\pi(w_{1}, w_{1})\otimes\cdots\otimes\pi(w_{n}, w_{n})$. This means that the map
\begin{equation*}
\Psi : \gamma_{1}\cdots\gamma_{n} \mapsto \pi(w_{\gamma_{1}}, w_{\gamma_{1}})\otimes\cdots\otimes\pi(w_{\gamma_{n}}, w_{\gamma_{n}})
\end{equation*}
induces a surjection from $F(\Gamma)$ onto the set of equivalence classes of irreducible representations of $H_{N}^{++}(\Gamma, \Lambda)$.\\

\noindent\textbf{Step 2.} The second step is to prove that they are in fact labelled by $W(\Gamma, \Lambda)$. Indeed, fix $\gamma, \gamma'\in\Gamma$ and $\lambda\in\Lambda$. Then,
\begin{align*}
r & = \left[\pi(w_{\gamma}.w_{\lambda}, w_{\gamma}.w_{\lambda})\otimes\pi(w_{\gamma'}, w_{\gamma'})\right]\left[\pi(w_{\gamma}, w_{\gamma})\otimes\beta(w_{\lambda}, w_{\lambda})\otimes\pi(w_{\gamma'}, w_{\gamma'})\right] \\
& \left[\pi(w_{\gamma}, w_{\gamma})\otimes\pi(w_{\lambda}.w_{\gamma'}, w_{\lambda}.w_{\gamma'})\right]
\end{align*}
yields an equivalence between the representations labelled by $(\gamma\lambda)\gamma'$ and $\gamma(\lambda\gamma')$, proving our claim. We will again denote by $\Psi$ the map obtained from $W(\Gamma, \Lambda)$ to the set of equivalence classes of higher-dimensional irreducible representations of $H_{N}^{++}(\Gamma, \Lambda)$.\\

\noindent\textbf{Step 3.} We now have to prove that there is no more relations, so let us consider $\gamma_{1}, \cdots, \gamma_{n}\in \Gamma$ and $\gamma'_{1}, \cdots, \gamma'_{k}\in \Gamma$ such that $\Psi(\gamma_{1}\cdots\gamma_{n}) = \Psi(\gamma'_{1}\cdots\gamma'_{k})$. By \cite[Thm 4.18 and Lem 4.19]{freslon2013representation}, if two projective partitions give equivalent representations, then they have the same number of through-blocks, so that the previous equality forces $k = n$. We will now prove by induction on $n$ that $\Psi(\gamma_{1}\cdots\gamma_{n}) = \Psi(\gamma_{1}'\cdots\gamma'_{n})$ implies that the two words are equal in $W(\Gamma, \Lambda)$. Let us start with the case $n = 2$. By assumption,
\begin{equation*}
r = \pi(w_{\gamma_{1}}, w_{\gamma'_{1}})\otimes\pi(w_{\gamma_{2}}, w_{\gamma'_{2}})\in \CC_{\Gamma, \Lambda, S}
\end{equation*}
and since $\pi(w_{\gamma_{1}}, w_{\gamma'_{1}})$ is a full subpartition of $r$, by the second defining condition of $\DD_{\Gamma, \Lambda, S}$ we have $\gamma_{1}^{-1}\gamma_{1}'\in \Lambda$. Let us denote by $\lambda$ this element. It follows that
\begin{align*}
[\pi(w_{\gamma'_{1}}, w_{\gamma'_{1}})\otimes\beta(w_{\lambda}, w_{\lambda})\otimes\pi(w_{\gamma'_{2}}, w_{\gamma'_{2}})]r & = \pi(w_{\gamma_{1}}, w_{\gamma_{1}})\otimes \beta(\emptyset, w_{\lambda})\otimes \pi(w_{\gamma_{2}}, w_{\gamma'_{2}}) \\
& \in \CC_{\Gamma, \Lambda, S}.
\end{align*}
Removing $\pi(w_{\gamma_{1}}, w_{\gamma_{1}})$ and capping yields $\pi(w_{\gamma_{2}}, w_{\lambda\gamma'_{2}})\in \CC_{\Gamma, \Lambda, S}$ so that by the first defining condition of $\DD_{\Gamma, \Lambda, S}$, $\gamma_{2} = \lambda\gamma'_{2}$. Summing up, $\gamma'_{1} = \gamma_{1}\lambda$ and $\gamma'_{2} = \lambda^{-1}\gamma_{2}$ and $\gamma_{1}\gamma_{2} = \gamma'_{1}\gamma'_{2}$ in $W(\Gamma, \Lambda)$.

Now for an arbitrary $n$, the reasoning is the same : we have
\begin{equation*}
r = \pi(w_{\gamma_{1}}, w_{\gamma_{1}'})\otimes\cdots\otimes \pi(w_{\gamma_{n}}, w_{\gamma'_{n}})\in \CC_{\Gamma, \Lambda, S}.
\end{equation*}
The second defining condition yields $\gamma_{1}^{-1}\gamma'_{1} \in \Lambda$ and by concatenating we get
\begin{equation*}
\pi(w_{\gamma_{2}}, w_{(\gamma_{1}^{-1}\gamma'_{1})\gamma_{2}'})\otimes\cdots\otimes \pi(w_{\gamma_{n}}, w_{\gamma'_{n}})\in \CC_{\Gamma, \Lambda, S},
\end{equation*}
from which we conclude by induction.\\
\end{proof}

As in Section \ref{sec:biorthogonal}, the larger category of partitions that we used in fact coincides with the original one.

\begin{cor}
For any inclusion $\Lambda\subset\Gamma$ and any finite symmetric generating set $S$, $\CC_{\Gamma, \Lambda, S} = \DD_{\Gamma, \Lambda, S}$.
\end{cor}

\begin{proof}
By \cite[Prop 3.16]{freslon2017noncrossing}, there exists a quotient map $\pi : \Gamma \to \Gamma'$ and a subgroup $\Lambda'\subset \Gamma'$ containing $\pi(\Lambda)$ such that $\DD_{\Gamma, \Lambda, S} = \CC_{\Gamma', \Lambda', S}$. By Lemma \ref{lem:onedwreath} and Theorem \ref{thm:wreathfusionrules}, $\Lambda = \Lambda'$ and $W(\Gamma, \Lambda) = W(\Gamma', \Lambda)$, yielding $\Gamma = \Gamma'$.
\end{proof}

We still have to describe the fusion rules of $H_{N}^{++}(\Gamma, \Lambda)$. For this purpose, we define two operations on $W(\Gamma, \Lambda)$. Given words $a = a_{1}\cdots a_{n}$, $b = b_{1}\cdots b_{n'}$ and $c$ such that $\varphi(c)\in \Lambda$, we set
\begin{align*}
a\underset{c}{\bullet}b & = a_{1}\cdots a_{n-1}(a_{n}.\varphi(c))b_{1}\cdots b_{n'} = a_{1}\cdots a_{n}(\varphi(c).b_{1})b_{2}\cdots b_{n'} \\
a\underset{c}{\ast}b & = a_{1}\cdots a_{n-1}(a_{n}.\varphi(c).b_{1})b_{2}\cdots b_{n'}.
\end{align*}
We can now compute the fusion rules.

\begin{prop}
The fusion rules of $H_{N}^{++}(\Gamma, \Lambda)$ are given by
\begin{align*}
(w_{1}\dots w_{n})\otimes (w_{1}'\dots w_{n'}') & = \sum_{w = az, w' = z'b, \varphi(zz')\in \Lambda} a\underset{zz'}{\bullet}b + a\underset{zz'}{\ast}b \\
\lambda\otimes (w_{1}\dots w_{n}) & = (\lambda.w_{1})w_{2}\dots w_{n}
\end{align*}
\end{prop}

\begin{proof}
The second equality follows directly from the definitions. As for the first one, let us note that for $k\leqslant \min(n, n')$, concatenating $w\square^{k}w'$ or $w\boxvert^{k}w'$ by
\begin{equation*}
\pi(w_{n-k+1}\cdots w_{n}w'_{1}\cdots w'_{k}, w_{n-k+1}\cdots w_{n}w'_{1}\cdots w'_{k})
\end{equation*}
in the middle we obtain the blocks of $\beta(w_{n-k+1}\cdots w_{n}w'_{1}\cdots w'_{k}, w_{n-k+1}\cdots w_{n}w'_{1}\cdots w'_{k})$. This means that the original partition is in $\CC_{\Gamma, \Lambda, S}$ only if the latter is, which in turn means that $\varphi(w_{n-k+1}\cdots w_{n}w'_{1}\cdots w'_{k})\in \Lambda$. In other words, the tensor product splits as a sum over all the decompositions $w = az$, $w' = z'b$ with $\varphi(zz')\in \Lambda$.

Considering now such a decomposition with $a$ of length $k$, then as explained in the previous paragraph $q\square^{k}w'$ is equivalent to $a\underset{zz'}{\ast b}$ while concatenating by
\begin{equation*}
\pi(w_{n-k}\cdots w_{n}w'_{1}\cdots, w'_{k+1}, w_{n-k}\cdots w_{n}w'_{1}\cdots, w'_{k+1})
\end{equation*}
shows that $w\boxvert^{k}w'$ is equivalent to $a\underset{zz'}{\bullet}b$.
\end{proof}

\bibliographystyle{amsplain}
\bibliography{../../../quantum}

\end{document}


text:
\begin{definition}[Definition:Mersenne Prime/Index]
The '''index''' of the '''[[Definition:Mersenne Prime|Mersenne prime]]''' $M_p = 2^p - 1$ is the [[Definition:Prime Number|(prime) number]] $p$.
\end{definition}

config: wiki


TITLE: Injection from $\mathbb{N} \to F$ an ordered field?
QUESTION [0 upvotes]: Let $F$ be an ordered field. Is it necessarily true that there is an injection $f:\mathbb{N} \to F$? If that is the case, then I suppose from there it can be concluded that $F$ must be an infinite set. Am I correct?

REPLY [1 votes]: Let $F$ be an ordered field. By recursion define $f: \mathbb{N} \to F$ by $f(0)=0$ and $f(n+1)= f(n)+1$, where the $+$ is taken in $\mathbb{N}$ for $n+1$ and as the $+$-operation in $F$ in $f(n)+1$ (if you want to be ultraprecise, distinguish them by notation, like $+_F$ etc.)
Then $f(1)=1$ and the axioms for an ordered field tell us that $0=f(0)<_F 1=f(1)$.
Also, if $f(m) < f(n)$ for all $m < n$ then for $m < n+1$ we have $m < n$ and $f(m) <_F f(n) <_F f(n)+1=f(n+1)$, or $m=n$ and then also $f(m)=f(n) <_F f(n)+1=f(n+1)$. So by induction we have shown that $m < n$ implies $f(m) <_F f(n)$ and so we have an order-preserving injection from $\mathbb{N}$ into $F$.
In particular, $F$ is infinite.


text:
\begin{document}

\title{A pattern search bound constrained optimization method with a nonmonotone line search strategy}

\author{Johanna A. Frau and Elvio A. Pilotta \thanks{Facultad de Matem\'atica, Astronom\'{\i}a y F\'{\i}sica, Universidad Nacional de C\'ordoba, CIEM (CONICET), Medina Allende s/n, Ciudad Universitaria (5000) C\'ordoba, Argentina. E-mail: \{jfrau, pilotta\}@famaf.unc.edu.ar}}

\maketitle

\begin{abstract}
A new pattern search method for bound constrained optimization is introduced. The proposed algorithm employs the coordinate directions, in a suitable way, with a nonmonotone line search for accepting the new iterate, without using derivatives of the objective function. The main global convergence results are strongly based on the relationship between the step length and a stationarity measure.
Several numerical experiments are performed using a well known set of test problems. Other line search strategies were tested and compared with the new algorithm.

\

{\bf Key words.} pattern search methods, bound constrained optimization, global convergence, numerical experiments.

\

{\bf AMS Subject classifications.} 90C30, 90C56, 65K05.

\end{abstract}
\hrulefill

\section{Introduction}\label{intro}

In this paper, we propose a new algorithm to solve bound constrained optimization problems where the derivatives of the objective function are not available. So, the problem of interest is

\begin{equation}\label{problem}
\begin{array}{lc }
\mbox{minimize} & f(x) \\
\mbox{subject to} & x \in \Omega
\end{array}
\end{equation}
where $f: \mathbbm{R}^n \rightarrow \mathbbm{R}$  and $\Omega = \{x \in \mathbbm{R}^n \, | \, l \leq x \leq u\}$ with $-\infty \leq l < u \leq \infty$. We assume that the objective function is continuosly differentiable on $\Omega$ but the derivative information is unrealiable or non-existent. This situation frequently appears in many real world applications where functional values $f(x)$ require complex simulations or the function contains noise. This kind of situations may arise in applications from molecular geometry \cite{ANRV04,MM94}, medical image registration \cite{OB07}, shape and design optimization \cite{BDFST98,DV04,MWDM04}. There are many problems where the functional values come from practical experiments, so  the explicit formulation of the objective function is not available and Quasi-Newton or finite difference methods are not applicable. Derivative-free optimization has received considerable attention from the optimization community during the last years, including the establishment of solid mathematical foundations for many of the methods considered in practice. Particularly, pattern search methods have succeeded where more elaborate approaches fail. These methods belong to the family of direct search methods, characterized by unsophisticated implementations, the abscence of the construction of a model of the objective function and the use of pattern matrices to explore directions around the current iterate. See \cite{AD03,CSV09,HJ61,KLT03,T97}.

\

Pattern search methods were initially introduced by Hooke and Jeeves \cite{HJ61} for unconstrained optimization problems and lately analized and formally presented by Torczon et. al.  \cite{KLT03,T97}. More recently, some strategies were adapted from derivative-based methods  and incorporated to pattern search methods. For instance, in \cite{DMR08} the authors introduced a global strategy, based in the ideas developed in {\cite{GLL86,LMR06,LF00,LS02}, that uses a nonmonotone line search scheme in a pattern search algorithm.

\

In \cite{LT99} Lewis and Torczon extended the pattern search method for the bound constrained case although they did not perform numerical experiments. This problem was also studied in \cite{AEP11} using polynomial interpolation and trust region strategies, which is a quite different approach to pattern search methods.

\

In this article, we propose a pattern search method that includes a nonmonotone line search as globalization strategy for a bound constrained optimization problem (\ref{problem}). The new algorithm is based on the ideas introduced in \cite{DMR08} for the unconstrained case, however the proofs of the main convergence results of our method use a completely different philosophy . To prove the global convergence, we use the stationarity measure $\chi(x)$ defined in \cite{KLT03}. This measure takes into account the degree to which the directions of the steepest descent point outward  with respect to the portion of the feasible region near $x$. In order to validate our algorithm, we perform several numerical experiments and comparisons with other well established algorithm. After that, we extend our benchmark study by incorporating other line search strategies \cite{A66,C09,KLNS15,NS13,ZH04}.

\

This paper is organized as follows: some definitions and preliminary results are given in Section 2. The new algorithm is introduced in Section 3. Convergence results are stated in Section 4. Numerical experiments are presented and analized in Section 5. Finally, some conclusions are given in Section 6.

\subsection*{Notation}
In this work, $e^{(i)}$ denotes the i-th canonical vector in $\mathbb{R}^{n}$ and
$\|\cdot\|$ will be the Euclidean norm. Also, $int(\Omega)$ denotes the largest open set contained in $\Omega$.

\

\section{Definitions and preliminary results}

In this section, we present some definitions and results which are necessary in order to guarantee  convergence of the method that we propose to solve problem (\ref{problem}).

\

The following two definitions are the basis of the theory of convergence and they are widely used in the context of optimization. The first definition refers to the cone $K$ generated by the set of all nonnegative linear combinations of vectors of a given set. The second definition includes those vectors that make an angle of 90$^\circ$ or more with each element of $K$, the polar cone ${K^\circ}$.

\begin{definition}
Let $\textit{D}= \lbrace v^{(1)}, v^{(2)}, \ldots, v^{(r)} \rbrace$ be a set of $\textit{r}$ vectors in $\mathbb{R}^{n}$. The set $\textit{D}$ generates the cone $K$ if
$$
K=\lbrace u | u= \sum_{i=1}^r c^{(i)} v^{(i)}, c^{(i)} \geq 0, \mbox{ for } i=1,2, \ldots, r \rbrace.
$$
\end{definition}

\begin{definition}
The polar cone of a cone $K$, denoted by $K^\circ$, is the cone defined by
$$
K^\circ=\lbrace w| w^Tu \leq 0, \mbox{ for all } u \in K \rbrace.
$$
\end{definition}

When we are minimizing a function in a feasible region, we are particularly interested in choosing search directions (descent directions at best) which  improve  the objective function and remain feasible at the same time. Given $x \in \Omega$, we define $K(x, \epsilon)$ as the cone generated by 0 and the outward pointing normals of the constraints within a distance $\epsilon$ of $x$, namely
$$
\lbrace e^{(i)} | u^{(i)}-x^{(i)} \leq \epsilon \rbrace \cup \lbrace -e^{(i)} | x^{(i)}-l^{(i)} \leq \epsilon \rbrace .
$$
In other words, $K(x, \epsilon)$ is generated by the normals to the faces of the feasible region within distance $\epsilon$ of $x$. Observe that if $K(x, \epsilon)=\lbrace 0 \rbrace$, as in the unconstrained case or when $x$ is well within the interior of the feasible region, $K^\circ(x,\epsilon)= \mathbb{R}^{n}$. The cone $K(x, \epsilon)$ is important because, for suitable choices of $\epsilon$, its polar  $K^\circ(x,\epsilon)$ approximates the feasible region near $x$. So, if  $K^\circ(x,\epsilon)\neq \lbrace 0 \rbrace$, the search can proceed from $x$ along all directions in $K^\circ(x,\epsilon)$ for at least a distance of $\epsilon$ and still remain inside the feasible region. See \cite{KLT03} for more details.

\

As in the theory of methods based explicitly on derivatives, in derivative free optimization, we need a measure that lets us know how close a point $x$ is to constrained stationarity. In this article, we adopted the following  measure of stationarity
$$
\chi(x)= \max_{\substack {x +\omega \in \Omega, \\ \| \omega\| \leq 1}} -\nabla f(x)^T \omega.
$$
Roughly speaking, $\chi(x)$ captures the degree to which the direction of steepest descent is outward pointing with respect to the portion of the feasible region near $x$. In \cite{CGT00}, the authors proved that if $\Omega$ is convex, the function $\chi$ has the following properties:
\begin{enumerate}
\item $\chi(x) \mbox{ is continuous. }$
\item $\chi(x)\geq 0$.
\item $\chi(x)=0 \mbox{ if and only if } x \mbox{ is a KKT point }$for the problem (\ref{problem}).
\end{enumerate}

Thus, showing that $\chi(x_k) \rightarrow 0$ as $k \rightarrow \infty$ establishes a global first-order convergence result, which will be one  of our primary goals on this work.

\
\section{The bound constrained nonmonotone pattern search algorithm \texttt{nmps}}

We begin this section by introducing the proposed algorithm.

\

Let $M$ be a positive integer, which indicates how many previous functional values will be considered on the nonmonotone line search. Let $\Delta_{tol}> 0$ be the tolerance for the convergence criterion. Let $D_{\bigoplus}$ be a finite set of $\mathbbm{R}^n$ given by the coordinate directions, that is,
$$
D_{\bigoplus}= \lbrace \pm e^ {{(i)}}| i=1,2,\ldots,n \rbrace.
$$

\

Assume that $\lbrace \eta_k \rbrace$ is a sequence chosen such that $\eta_k>0$, for all $k=0,1,2,\ldots,$ and $ \sum_{k=0}^{\infty}\eta_{k}=\eta < \infty$ is a convergent series.

\

Suppose that $x_0 \in \Omega$ is an initial approximation to the solution and let $\Delta_0 > 0$ be the initial value for the step length. Given $x_k \in \Omega$, $\Delta_k > \Delta_{tol}> 0$, the steps for computing $x_{k+1}$ are given by the following algorithm.

\begin{algorithm}[\texttt{nmps}]
\end{algorithm}

\subsubsection*{{\bf Step 1}:}
Compute $f(x_k)$ and define $f_{\max}(x_k)$ such that
$$
f_{\max}(x_k)=\max \lbrace f(x_k),\ldots,f(x_{k-{\min\lbrace k,M-1\rbrace}}) \rbrace = \max_{0 \leq j\leq m(k)} \lbrace f(x_{k-j}) \rbrace
$$
where $m(k)=\min \lbrace k,M-1 \rbrace$.

\subsubsection*{{\bf Step 2}: {\it Backtracking}}

\begin{itemize}
\item[2.1] Find (if possible) $d\in D_\oplus$ such that $(x_k + \Delta_k d) \in \Omega$ and the inequality
\begin{equation}\label{nmc}
f(x_k + \Delta_k d)\leq f_{\max}(x_k)+ \eta_k - \Delta_k^{2}
\end{equation}
holds. Set $\Delta_{k+1}\leftarrow 1$ and $x_{k+1}\leftarrow x_k+ \Delta_k d$.

\item[2.2] If there is no a direction $d\in D_\oplus$ such that $(x_k + \Delta_k d) \in \Omega$ and (\ref{nmc}) holds, then set

$\Delta_k \leftarrow \displaystyle \frac{\Delta_k}{2}$ and repeat Step 2.1 until
a new $x_{k+1}$ is found.

If $\Delta_{k+1}<\Delta_{tol}$ terminate the execution of the algorithm.
\end{itemize}

\section{Theoretical results and convergence analysis}

In order to prove our main convergence result we need to demonstrate some auxiliary results. The following proposition concerns the nonmonotonicity of $\{f(x_k)\}$. It is analogous to Lemma 2.3 in \cite{BMR03}.

\begin{proposition} \label{propaux}
If $l(k)$ is an integer such that
\begin{center}
$kM-m(kM)\leq l(k)\leq kM$,
\end{center}
with $m(kM)=\min\lbrace kM,M-1\rbrace$, and
$$
\begin{array}{rcl}
f(x_{l(k)})& = & \stackbin[0 \leq j\leq m(kM)]{}{\max} \lbrace f(x_{kM-j}) \rbrace \\[3mm]
& = & \max \lbrace f(x_{kM}),f(x_{kM-1}),\ldots,f(x_{kM-{\min\lbrace kM,M-1\rbrace}}) \rbrace
\end{array}
$$
then
\begin{equation}\label{proposicion1}
f(x_{l(k+1)} \leq f(x_{l(k)}) + \eta_{kM} + \ldots + \eta_{kM-M+1} - \Delta_{l(k+1)-1}^{2}
\end{equation}
\end{proposition}

\begin{proof}

From now on we are going to suppose that the iteration $k$ is such that $k \geq M $, therefore $m(kM)=\min \lbrace {kM,M-1} \rbrace= M-1$.

\

Then, by an inductive argument on $t=1,2, \ldots, M$ we will prove that
\begin{equation}\label{induccion}
f(x_{kM+t)} \leq f(x_{l(k)})+ \eta_{kM} + \ldots + \eta_{kM-M+1} - \Delta_{kM+t-1}^{2}
\end{equation}
holds for all iteration $k=1,2, \ldots$

\

In fact, from (\ref{nmc}), we have
$$
\begin{array}{rcl}
f(x_{kM+1}) & \leq & f_{\max}(x_{kM}) + \eta_{kM} - \Delta_{kM}^2 \\
& = & \stackbin[0 \leq j\leq M-1]{}{\max} \lbrace f(x_{kM-j}) \rbrace + \eta_{kM} - \Delta_{kM}^2 \\[2mm]
& = & f(x_{l(k)})+ \eta_{kM} - \Delta_{kM}^2 \\
& < & f(x_{l(k)})+ \eta_{kM},
\end{array}
$$
for all $k \in \mathbbm{N}$. Therefore, the inequality (\ref{induccion}) holds for $t=1$.

\

Now, by inductive hypothesis, we suppose that
$$
\begin{array}{rcl}
f(x_{kM+t^\prime)} & \leq & f(x_{l(k)})+ \eta_{kM} + \ldots + \eta_{kM+t^\prime-1} - \Delta_{kM+t^\prime-1}^{2} \\
& < & f(x_{l(k)}) + \eta_{kM} + \ldots + \eta_{kM+t^\prime-1}
\end{array}
$$
for all $t^\prime = 1,2,\ldots, t$.

\

We will prove that (\ref{induccion}) holds for $t+1$. Indeed,
$$
\begin{array}{rcl}
f(x_{kM+t+1)} & \leq & f_{\max}(x_{kM+t})+ \eta_{kM+t} - \Delta^{2}_{kM+t} \\
& = & \max\lbrace f(x_{kM+t}), f(x_{kM+t-1}), \ldots, f(x_{kM+t-M+1}) \rbrace + \eta_{kM+t} - \Delta^{2}_{kM+t} \\
& = & \max \lbrace \max \lbrace f(x_{kM}), \ldots, f(x_{kM+t-M+1}) \rbrace, f(x_{kM+1}), \ldots, f(x_{kM+t}) \rbrace + \\
&& \eta_{kM+t} - \Delta^{2}_{kM+t} \\
& = &  \max \lbrace f(x_{l(k)}), f(x_{kM+1}), \ldots, f(x_{kM+t}) \rbrace + \eta_{kM+t} - \Delta^{2}_{kM+t}
\end{array}
$$

Now by induction step,
$$
\max \lbrace f(x_{kM+1}), \ldots, f(x_{kM+t}) \rbrace < f(x_{l(k)}) + \eta_{kM} + \ldots + \eta_{kM+t+1}.
$$

Thus,

$$
f(x_{kM+t+1)} \leq f(x_{l(k)})+ \eta_{kM} + \ldots + \eta_{kM+t-1} + \eta_{kM+t} -\Delta^{2}_{kM+t},
$$
so the inequality (\ref{induccion}) holds for $t+1$.

\

Finally, since $(k+1)M-M+1\leq l(k+1) \leq kM+M,$ we have
$$
l(k+1)=kM+t \mbox{ for some } t \in \lbrace 1,2, \ldots, M \rbrace.
$$
\end{proof}

The next proposition is an important tool to prove global convergence of the \texttt{nmps} algorithm where  the inequality of Proposition \ref{propaux} is applied iteratively. This idea has also been  introduced by Birgin et. al in \cite{BMR03} and we adapted it for our case.

\begin{proposition}
If $\lbrace f(x_{k}) \rbrace _{k \in \mathbbm{N}}$ is bounded below then $\displaystyle \lim_{k \to \infty}\Delta^{2}_{l(k)-1}=0$

\end{proposition}

\begin{proof}
By applying the inequality (\ref{proposicion1}) we have
$$
f(x_{l(k+1)}) \leq f(x_0) + \displaystyle \sum_{k=0}^{\infty}\eta_{k} - \displaystyle \sum_{k=1}^{\infty} \Delta^2_{l(k)-1},
$$
equivalently
$$
\displaystyle \sum_{k=1}^{\infty} \Delta^2_{l(k)-1} \leq f(x_0) -f(x_{l(k+1)}) + \displaystyle \sum_{k=0}^{\infty}\eta_{k}.
$$
Now, since $f$ is bounded below we have $-f(x_k)\leq -C$ for all $k$, and due to summability of the sequence $\lbrace \eta_k \rbrace$, we obtain
$$
\displaystyle \sum_{k=1}^{\infty} \Delta^2_{l(k)-1}< +\infty,
$$
so $\displaystyle \lim_{k \to \infty}\Delta^{2}_{l(k)-1}=0$, as we want to prove.
\end{proof}

\

In consequence, we observe that
$$
\lim_{k \to \infty}\Delta_{l(k)-1} = 0,
$$
since the steps $\Delta_k$ are small enough and positives.

\

Now we define set of index
$$
U= \lbrace l(1)-1, l(2)-1, l(3)-1, \ldots \rbrace
$$
where $\lbrace l(k) \rbrace$ is the sequence of index defined in the Proposition \ref{propaux}.

\

The following two results have been demonstrated by Kolda, Lewis and Torczon in \cite{KLT03}.

\begin{proposition} \label{prop3}
Let $x \in \Omega$ and $\varepsilon \leq 0$, and let $K=K(x,\varepsilon)$ and $K^{\circ}=K^{\circ}(x,\varepsilon)$ for the bound constrained problem (\ref{problem}). Let $\textit{G}_{K^{\circ}}\subseteq D_{\bigoplus}$ the set of generators of $K^{\circ}$. Then, if $[-\nabla f(x)]_{K^{\circ}}\neq 0$, there is $d \in \textit{G}_{K^{\circ}}$ such that
$$
\frac{1}{\sqrt{n}} \| [-\nabla f(x)]_{K^{\circ}} \| \leq -\nabla f(x)^{T}d.
$$
\end{proposition}

\

\begin{proposition}\label{prop4}
Let $x \in \Omega$ and $\varepsilon \geq 0$, and let $K^{\circ}=K^{\circ}(x,\varepsilon)$ and $K=K(x,\varepsilon)$ for the bound constrained problem (\ref{problem}). Then
$$
\chi (x)\leq \| [-\nabla f(x)]_{K^{\circ}} \| + \sqrt{n} \| [-\nabla f(x)]_{K}
\|\varepsilon.
$$
\end{proposition}

\

Next, we present the main global convergence result of \texttt{nmps} algorithm.

\begin{theorem}
Let $f:\mathbbm{R}^n\rightarrow \mathbbm{R}$ be continuously differentiable, and suppose $\nabla f(x)$ is Lipschitz continuous with constante $L$, $\|\nabla f(x) \| \leq \gamma$, for all $x \in \Omega$ and $\lbrace f(x_{k}) \rbrace _{k \in \mathbbm{N}}$ is bounded below. If $\lbrace x_k \rbrace _{k \in U}$ is the sequence generated by the \texttt{nmps} algorithm then
$$
\chi (x_k) \leq \sqrt{n}(L+ \gamma)\Delta_k \, \mbox{ for all } \, k \in U.
$$
\end{theorem}

\begin{proof}
We will consider two cases.

\textit{Case 1.} If $x_k + \Delta_k d \notin int(\Omega)$ for all $d \in D_{\bigoplus}$, then $x_k + \Delta_k d$ is either on the boundary of or outside of $\Omega$ for all directions $d \in D_{\bigoplus}$.

\

In other words, if $l^{(i)}\leq x_k^{(i)} \leq u^{(i)}$ then $x_k^{(i)}-\Delta_k \leq l^{(i)}$ and $x_k^{(i)}+\Delta_k\geq u^{(i)}$ for all $i = 1, 2,\ldots, n$.

\

The last inequalities imply that if $x_k+\omega \in \Omega$, the vector $\omega$ cannot have their components greater than $\Delta_k$, that is, $\omega^{(i)}\leq \Delta_k$ for all $i$. Therefore, $\|\omega \|\leq \sqrt{n} \Delta_k$.

\

So,
$$
\begin{array}{rcl}
\chi(x_k) & = &\displaystyle \max_{\substack {x_k +\omega \in \Omega, \\ \| \omega\| \leq 1}} -\nabla f(x_k)^T \omega \\
& \leq & \displaystyle \max_{\substack {x_k +\omega \in \Omega, \\ \| \omega\| \leq 1}}\|\nabla f(x_k) \| \| \omega \| \\
& \leq &\|\nabla f(x_k) \| \sqrt{n} \Delta_k \\
& \leq & \sqrt{n} \gamma \Delta_k,
\end{array}
$$
which completes the proof for the Case 1.

\

\textit{Case 2.} Now we suppose that there is at least $d \in D_{\bigoplus}$ such that $x_k + \Delta_k d \in int(\Omega)$. Thus, the cone $K^{\circ}(x_k,\Delta_k)$ is generated by all the directions $d \in D_{\bigoplus}$ such that $x_k + \Delta_k d int(\Omega)$.

\

By the mean value theorem, we have that
\begin{equation}\label{valormedio}
f(x_k+\Delta_k d_k)-f(x_k)=\Delta_k \nabla f(x_k+\lambda_k \Delta_k d_k)^Td_k,
\end{equation}
for some $\lambda_k \in [0,1]$.

\

Since $k \in U$, this implies
$$
0 \leq f(x_k+ \Delta_k d_k)- f_{\max}(x_k)- \eta_k + \Delta_k^2.
$$

\

Taking into account that $-f_{\max}(x_k) \leq -f(x_k)$ and $\eta_k > 0$ for all $k$, we obtain
\begin{equation}\label{desigualdad}
0 \leq f(x_k+ \Delta_k d_k) -f(x_k) + \Delta_k^2.
\end{equation}

\

Then, we replace (\ref{valormedio}) in (\ref{desigualdad})
$$
0 \leq \Delta_k \nabla f(x_k+\lambda_k \Delta_k d_k)^Td_k + \Delta_k^2.
$$

\

Next, we divide the last inequality by $\Delta_k$ and adding $-\nabla f(x_k)^Td_k$, we get the following inequality
$$
-\nabla f(x_k)^Td_k \leq (\nabla f(x_k+ \lambda_k \Delta_k d_k)- \nabla f(x_k))^T d_k + \Delta_k.
$$

\

Using the Proposition \ref{prop3} we have
$$
\dfrac{1}{\sqrt{n}} \| [-\nabla f(x)]_{K^{\circ}} \| \leq (\nabla f(x_k+ \lambda_k \Delta_k d_k)- \nabla f(x_k))^T d_k + \Delta_k.
$$

Then by the Cauchy-Schwarz inequality, the fact that $\| d_k \|=1$ for all $k$ and the boundedness hypothesis of the gradient, we obtain
$$
\dfrac{1}{\sqrt{n}} \| [-\nabla f(x)]_{K^{\circ}} \| \leq \|(\nabla f(x_k+ \lambda_k \Delta_k d_k)- \nabla f(x_k)) \| + \Delta_k \leq L \Delta_k + \Delta_k.
$$

In consequence,
$$
\| [-\nabla f(x)]_{K^{\circ}} \| \leq \sqrt{n} L \Delta_k + \sqrt{n} \Delta_k \leq \sqrt{n} L \Delta_k.
$$

Finally, combining the Proposition \ref{prop4} with the above result
$$
\chi (x)\leq \| [-\nabla f(x)]_{K^{\circ}} \| + \sqrt{n} \| [-\nabla f(x)]_{K} \|\varepsilon \leq \| [-\nabla f(x)]_{K^{\circ}} \| + \sqrt{n} \gamma \Delta_k \leq \sqrt{n} L \Delta_k + \sqrt{n} \gamma \Delta_k
$$
consequently,
\begin{center}
$\chi (x)\leq \sqrt{n}(L+ \gamma)\Delta_k$,
\end{center}
and the proof is complete.

\end{proof}

\section{Numerical results}

In this section we show and analyse the numerical results obtained using our nonmonotone pattern search bound constrained optimization \texttt{nmps} algorithm. All the numerical experiments were executed on a computer with a 2.3 GHz Intel Core i5--6200u processor (8 GB RAM). We implemented the  \texttt{nmps} algorithm in \texttt{matlab R2016b 64-bit}.

\

To the purpose of carefully analyse the performance of our algorithm we decided to organize our study in two parts. First, we compare the \texttt{nmps} algorithm with the  \texttt{patternsearch} routine from \texttt{matlab}'s optimization toolbox, since both algorithms are based on pattern search methods. Then, we study the performance of \texttt{nmps} algorithm using different line search strategies \cite{C09,KLNS15,NS13,ZH04} and the classical Armijo's rule \cite{A66}.

\

We have selected a set of 63 bound constrained problems from Hock--Schittkowski collection \cite{HS81}. Since this collection has only 9 bound constrained problems, we have modified other 54 problems with general constraints, extracting the linear and nonlinear constraints from each one of them. The detailed list of these problems and their characteristics is provided in
Table~\ref{tab:infoproblemas}.

\

As it is usual in derivative-free optimization articles, we are interested in the number of functional values needed to satisfy the stopping criteria, which are: reaching a sufficiently small step length ($\Delta_k < \Delta_{\mbox{tol}}$), attaining the maximum number of function evaluations $MaxFE$ or attaining the maximum number of iterations $MaxIt$. We adopt the convergence test proposed in \cite{MW09} to measure the ability of an algorithm to improve an initial approximation and to declare that a problem has been solved if the following condition holds

\begin{equation} \label{test}
f(x_0)-f(x) \geq (1-\tau)(f(x_0)-f_{\mbox{L}}),
\end{equation}
where $x_0$ is the initial feasible approximation, $\tau > 0$ is the level of accuracy and $f_{\mbox{L}}$ is the smallest functional value obtained among the considered solvers. We use the performance profile graphs  \cite{DM02,MW09} to illustrate the results obtained with (\ref{test}).

\

\begin{table}
\begin{center}
\resizebox{8cm}{!} {
\begin{tabular}{|c|c|c|c|c|}
\hline
Prob. & N$^{\circ}$. HS & n & bound & objective \\
 & & & constraints & function \\
\hline
1 & 1 & 2 & 1 & Generalized polynomial \\ \hline
2 & 2 & 2 & 1 & Generalized polynomial\\ \hline
3 & 3 & 2 & 1 & Generalized polynomial\\ \hline
4 & 4 & 2 & 2 & Generalized polynomial\\ \hline
5 & 5 & 2 & 4 & General\\ \hline
6 & 25 & 3 & 6 & Sum of squares\\ \hline
7 & 38 & 4 & 8 & Generalized polynomial\\ \hline
8 & 45 & 5 & 10 & Constant\\ \hline
9 & 110 & 10 & 20 & General\\ \hline
10 & 13 & 2 & 2 & Quadratic\\ \hline
11 & 15 & 2 & 1 & Generalized polynomial\\ \hline
12 & 16 & 2 & 3 & Generalized polynomial\\ \hline
13 & 17 & 2 & 3 & Generalized polynomial\\ \hline
14 & 18 & 2 & 4 & Quadratic\\ \hline
15 & 19 & 2 & 4 & Generalized polynomial\\ \hline
16 & 20 & 2 & 2 &  Generalized polynomial\\ \hline
17 & 21 & 2 & 4 & Quadratic\\ \hline
18 & 23 & 2 & 4 & Quadratic\\ \hline
19 & 24 & 2 & 2 & Generalized polynomial\\ \hline
20 & 30 & 3 & 6 & Quadratic\\ \hline
21 & 31 & 3 & 6 & Quadratic\\ \hline
22 & 32 & 3 & 3 & Quadratic\\ \hline
23 & 33 & 3 & 4 & Generalized polynomial\\ \hline
24 & 34 & 3 & 6 & Linear\\ \hline
25 & 35 & 3 & 3 & Quadratic\\ \hline
26 & 36 & 3 & 6 & Generalized polynomial\\ \hline
27 & 37 & 3 & 6 & Generalized polynomial\\ \hline
28 & 41 & 4 & 8 & Generalized polynomial\\ \hline
29 & 42 & 4 & 2 & Quadratic\\ \hline
30 & 44 & 4 & 4 & Quadratic\\ \hline
31 & 53 & 5 & 10 & Quadratic\\ \hline
32 & 54 & 6 & 12 & General\\ \hline
33 & 55 & 6 & 8 & General\\ \hline
34 & 57 & 2 & 2 & Sum of squares\\ \hline
35 & 59 & 2 & 4 & General\\ \hline
36 & 60 & 3 & 6 & Generalized polynomial\\ \hline
37 & 62 & 3 & 6 & General\\ \hline
38 & 63 & 3 & 3 & Quadratic\\ \hline
39 & 64 & 3 & 3 & Generalized polynomial\\ \hline
40 & 65 & 3 & 6 & Quadratic\\ \hline
41 & 66 & 3 & 6 & Linear\\ \hline
42 & 68 & 4 & 8 & General\\ \hline
43 & 69 & 4 & 8 & General\\ \hline
44 & 71 & 4 & 8 & Generalized polynomial\\ \hline
45 & 72 & 4 & 8 & Linear\\ \hline
46 & 73 & 4 & 4 & Linear\\ \hline
47 & 74 & 4 & 8 & Generalized polynomial\\ \hline
48 & 75 & 4 & 8 & Generalized polynomial\\ \hline
49 & 76 & 4 & 4 & Quadratic\\ \hline
50 & 80 & 5 & 10 & General\\ \hline
51 & 81 & 5 & 10 & General\\ \hline
52 & 83 & 5 & 10 & Quadratic\\ \hline
53 & 84 & 5 & 10 & Quadratic\\ \hline
54 & 86 & 5 & 5 & Generalized polynomial\\ \hline
55 & 93 & 6 & 6 & Generalized polynomial\\ \hline
56 & 101 & 7 & 14 & Generalized polynomial\\ \hline
57 & 102 & 7 & 14 & Generalized polynomial\\ \hline
58 & 103 & 7 & 14 & Generalized polynomial\\ \hline
59 & 104 & 8 & 16 & Generalized polynomial\\ \hline
60 & 106 & 8 & 16 & Linear\\ \hline
61 & 108 & 9 & 2 & Quadratic\\ \hline
62 & 114 & 10 & 20 & Quadratic\\ \hline
63 & 119 & 16  & 32 & Generalized polynomial\\ \hline

\end{tabular}
}
\caption{Characteristics of test problems.}
\label{tab:infoproblemas}
\end{center}
\end{table}

Given $P$ the set of problems, $|P|$ denotes the cardinality of $P$ and $S$ the set of considered solvers. The performance profile of a solver $s \in S$ is defined as the fraction of problems where the performance ratio is at most $\alpha$, that is, $\rho_{s}(\alpha)=\frac{1}{|P|}\mbox \, \mbox{size} \, \lbrace p \in Pv: r_{p,s}\leq \alpha \rbrace$, where $r_{p,s}=\frac{t_{p,s}}{\lbrace  \min t_{p,s}: s \in S\rbrace}$, $t_{p,s}$ is the number of function evaluations required to satisfy the convergence test (\ref{test}).

\

We used the same initial approximation $x_0$ as indicated in \cite{HS81}, projecting onto the bound constraints if the initial approximation was not feasible. After some preliminary tests we adopted $\eta_k=1.1^{-k}$ for all $k$. Finally, the following algorithmic parameters were set: $\Delta_0 = 1.0$, as the initial step length, $M = 15$, $MaxFE = 2500$, $MaxIt = 5000$ and $\Delta_{tol} = TOL = 10^{-6}$.

\

It is worth mentioning three important implementation details of our algorithm. First, the function $f$ is evaluated in all possible coordinate directions and the accepted new approximation is such that produces the minimum functional value of $f(x_k + \Delta_k d)$. Second, the step length is updated using the following scheme $\Delta_{k+1}= \min \lbrace 1, 2\Delta_k \rbrace$. Third, the
accepted points are stored in a memory for the purpose to avoid revisiting older points without slow down the implementation. See \cite{LST07}.

\subsection{Comparison of performance profiles between \texttt{nmps} and \texttt{patternsearch} } \label{experimentos1}

We tested our algorithm \texttt{nmps} using the set of test problems and we compared it with the well established routine \texttt{patternsearch} from \texttt{matlab}. Since both codes are based on a pattern search scheme, we set the same algorithmic parameters. The numerical results are shown in Table~2.

\

In Figure \ref{f:performanceprofile63} we show the performance profile pictures using condition (\ref{test}) with three levels of accuracy: $\tau=10^{-1}$, $\tau=10^{-3}$ and $\tau=10^{-5}$, where a smaller value of $\tau$ means the satusfaction of condition (\ref{test}) is more strict. In a performance profile plot, the top curve represents the most efficient method within a factor $\tau$ of the best measure. When both methods match with the best result, then they are both counted as successful. This means that the sum of the successful percentages may exceed $100\%$.

\begin{figure} [H]
 \centering
  \subfloat[]{
   \label{f:tol1}
    \includegraphics[width=0.5\textwidth]{PP63problemas1e-1_010518_v1.jpg}}
  \subfloat[]{
   \label{f:tol2}
    \includegraphics[width=0.5\textwidth]{PP63problemas1e-3_010518_v1.jpg}}
    \\
    \subfloat[]{
    \label{f:tol3}
    \includegraphics[width=0.5\textwidth]{PP63problemas1e-5_010518_v1.jpg}}
 \caption{Performance profiles of \texttt{nmps} and \texttt{patternsearch}.}
 \label{f:performanceprofile63}
\end{figure}

\

In Figure \ref{f:tol1}, with $\tau=10^{-1}$, we observe that \texttt{nmps} algorithm is the best solver in the $82\%$ of the set problems while \texttt{patternsearch} does it in $71\%$. We also see, within a factor of $1.7$ of the best solver, both algorithms have a similar behaviour  and the performance profile shows these algorithms can solve a problem with a probability of $0.87$ with respect to the best solver. Finally, if the goal is to solve efficiently $95\%$ of the problems, the \texttt{nmps} algorithm accomplishes this by using $2.4$ times the minimum number of function evaluations while \texttt{patternsearch} needs a factor of $7.5$.

\

Now, when we increase the level of accuracy to $\tau=10^{-3}$ (Figure \ref{f:tol2}), we note that  \texttt{nmps} wins in the $79\%$ of the problems in comparison with the $68\%$ of \texttt{patternsearch}. Also, both solvers are equivalent if the solution is required within a factor of $1.7$ of the best solver, with a probability of $0.84$. Although both solvers can  reach the solution in, at most, $95\%$ of the problems, our algorithm was closer than the other since it solved $94\%$ of them, using $3.7$ times the minimum number of function evaluations.

\

Finally, we observe in Figure \ref{f:tol3} that the performance of both solvers deteriorate using
$\tau=10^{-5}$ as the level of accuracy. In any case, the algorithm \texttt{nmps} wins in $74\%$ of the problems meanwhile \texttt{patternsearch} wins in $62\%$. As before, \texttt{nmps} algorithm
performs better than \texttt{patternsearch} if you consider a solver that finds the solution using $1.7$ times the minimum number of function evaluations, with a probability of $0.8$. In such a case, we could expect at most that \texttt{nmps} algorithm solves $87\%$ of the problems  while \texttt{patternsearch}  solves $81\%$.

\

We conclude that, regardless the level of accuracy, our algorithm outperforms the  \texttt{patternsearch} routine with the set of test problems considered. In fact, our algorithm always has a probability $10\%$ greater than \texttt{patternsearch} to get the solution.

\

In the next subsection we will test our algorithm using other line search strategies in order to analyse and understand the advantages of employing different nonmonotone line search procedures.

\

\subsection{Comparison of performance profiles using other line search strategies} \label{otrasbusquedas}

Recently, some authors proposed different nonmonotone line search strategies for solving unconstrained minimization problems and nonlinear systems, with derivatives based and derivative-free methods \cite{C09,KLNS15,NS13,ZH04}. They show that such approaches are successful, therefore we have adopted them to our bound constrained derivative-free optimization problem (\ref{problem}).

\

The first approach, which is called {\it C-line search} and we have implemented in \texttt{Cpatternsearch} algorithm, is similar to the nonmonotone line search condition (\ref{nmc}), where $f_{\max}(x_k)$ is replaced by the sequence $\{C_k\}$ given by
\begin{equation} \label{C}
Q_{k+1}=r_k Q_k +1, \hspace{1cm} C_{k+1}=\dfrac{r_kQ_k(C_k+ \eta_k)+f_{k+1}}{Q_{k+1}}
\end{equation}
with $Q_0=1$, $C_0=f(x_0)$, $r_k \in [0,1]$ and $\lbrace \eta_k \rbrace$ satisfying	 $\sum_{k=0}^{\infty}\eta_{k}=\eta < \infty$ for all $k=0,1,2,\ldots$

\

The second strategy, which is called {\it $\lambda$-line search} and we have implemented in \texttt{$\lambda$patternsearch} algorithm, is also analogous to (\ref{nmc}) but in this case $f_{\max}(x_k)$ is defined by
\begin{equation} \label{lambda}
f_{\max}(x_k)=\max \lbrace f(x_k),\displaystyle \sum_{r=0}^{m(k)-1} \lambda_{k_r}f(x_{k-r}) \rbrace
\end{equation}
with $M \in \mathbbm{N}$, $m(k)=\min \lbrace k,M-1 \rbrace$, $\lambda_{k_r}\geqslant \lambda$ and $\sum_{r=0}^{m(k)-1}\lambda_{k_r}=1$ for all $k=0,1,2,\ldots$

\

Finally, we have adapted the classical Armijo's rule to our bound constrained problem (\ref{problem})
\begin{equation}\label{armijo}
f(x_k + \Delta_k d)\leq f(x_k)+ \eta_k - \Delta_k^{2}
\end{equation}
with $\lbrace \eta_k \rbrace$ y $\Delta_k$ defined as in the Algorithm 1. It was implemented in \texttt{armijo} algorithm.

\

Again, we chose $\eta_k=1.1^{-k}$ for all $k$, for the three new conditions. Also, we adopted $M=15$ and $\lambda_{k_r}=1/m(k)$ for all $r$ in \texttt{$\lambda$patternsearch} and $r_k=0.85$ for all $k$ in \texttt{Cpatternsearch}. Next, we show the performance profiles with convergence test (\ref{test}) for solving our set of test problems using \texttt{nmps}, \texttt{patternsearch}, \texttt{Cpatternsearch}, \texttt{$\lambda$patternsearch} and \texttt{armijo} algorithms. The numerical results are also presented in Table~2.

\

In Figure \ref{f:tol11}, for $\tau=10^{-1}$, we see that \texttt{$\lambda$patternsearch}
attains the best performance in $76\%$ of the problems, followed by \texttt{nmps} with $59\%$ and \texttt{Cpatternsearch} with  $57\%$, below  we find \texttt{patternsearch} and \texttt{armijo} with $56\%$ and $51\%$ respectively. We also observe, within a factor of $2.5$ of the best solver, \texttt{$\lambda$patternsearch} reaches the greater probability of solving a problem (around $0.92$) and \texttt{nmps} follows it with $0.9$. Furthermore, in this case, \texttt{patternsearch} is the solver with the lowest performance, with a probability of $0.76$. Moreover, with this level of accuracy, we note that \texttt{armijo} solves almost $97\%$ of the problems using a factor of $4.9$ times the minimum number of function evaluations, meanwhile \texttt{nmps} has the same behaviour requiring a factor of $5.75$.

\

Figure \ref{f:tol22} displays the performance profile for $\tau=10^{-3}$, increasing in this way the level of accuracy. Once more, \texttt{$\lambda$patternsearch} is the most successful solver with a probability of $0.63$, followed by \texttt{Cpatternsearch} and \texttt{nmps} with a probability of
$0.62$ and $0.6$, respectively. In the last positions, we find \texttt{armijo} and \texttt{patternsearch} with $0.52$ and $0.51$, respectively. Now, within a factor of $2.5$ of the best solver, \texttt{nmps} exhibits the best performance solving  $89\%$ of the problems. Later,
\texttt{Cpatternsearch} and \texttt{armijo} get $87\% $ and $85\%$ on the resolution of our set of problems. With this level of accuracy, the most we can expect is to solve $94\%$ of the problems within a factor of $3.8$ of the best solver. In the same sense, \texttt{Cpatternsearch} and \texttt{nmps} present a similar behaviour.

\

Finally, Figure \ref{f:tol33}  presents the performance profile for $\tau=10^{-5}$, requiring in this way a greater descent in the objective function. We observe that \texttt{Cpatternsearch}  wins in $65\%$ of the problems, followed by \texttt{nmps} and \texttt{$\lambda$patternsearch}
with $57\%$, \texttt{armijo} with  $49\%$ and \texttt{patternsearch} with $44\%$. We see, within a factor of $2.5$ of the best solver, \texttt{Cpatternsearch}  obtains the higher probability for solving a problem ($0.87$), followed by \texttt{nmps} ($0.84$). In this figure, as opposed to Figures \ref{f:tol11} and \ref{f:tol22}, we can see how the performance of the different methods are slightly separated from each other. Also, \texttt{Cpatternsearch} algorithm is always on top of all the remaining solvers. In this case, \texttt{Cpatternsearch} achieves the solution in $92\%$  of the problems within a factor of $2.79$ followed by  \texttt{nmps} that solves $87\%$ of the problems using $3.6$ times the minimum number of function evaluations. The other solvers can only solve at most $80\%$ of the problems employing greater factors.

\begin{table}
\begin{center}
\resizebox{16cm}{!} {
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
Prob. & \multicolumn{3}{c|}{\texttt{nmps}}& \multicolumn{3}{c|}{\texttt{patternsearch}} &\multicolumn{3}{c|}{\texttt{$\lambda$patternsearch}}&
\multicolumn{3}{c|}{\texttt{Cpatternsearch}}&\multicolumn{3}{c|}{\texttt{armijo}}\\
\cline{2-16}

& $It.$ & $FE.$ & $stop$
& $It.$ & $FE.$ & $stop$
& $It.$ & $FE.$ & $stop$
& $It.$ & $FE.$ & $stop$
& $It.$ & $FE.$ & $stop$\\
\hline

1  &  341 & 352  & TOL & 625 & 2500 & MaxFE& 339& 352 &TOL &  530& 352 & TOL& 1003 & 2500 & MaxFE\\ \hline
2  & 402 &  323 & TOL & 58 & 207 & TOL &5000 & 6&MaxIt &628 &281&TOL & 277 & 155 & TOL\\ \hline
3  & 277 & 83 & TOL & 39 &  119 & TOL &	1660& 2500& MaxFE&307 &83& TOL&1659 & 2500 &MaxFE\\ \hline
4  & 277 & 46 & TOL &34 & 84 & TOL &5000 & 14 &MaxIt &307 &46& TOL& 277 & 48& TOL\\ \hline
5  & 293 & 305 & TOL & 36 & 145 & TOL  &269 & 337&TOL & 305&314& TOL& 269& 336&TOL\\ \hline
6  & 700 & 2500 & MaxFE & 513 & 2500 & MaxFE &5000 & 1330&MaxIt &670 &2500& MaxFE& 552& 2500& MaxFE\\ \hline
7  & 1124 & 2500 & MaxFE & 176 & 1409 & TOL &5000 & 177&MaxIt &974 &2500& MaxFE& 455& 2500& MaXFE\\ \hline
8  & 278 & 219 & TOL & 50 & 290 & TOL &	5000& 134& MaxIt& 307&132& TOL& 278 & 248& TOL\\ \hline
9  & 262 & 2500 & MaxFE &129  & 2500 & TOL & 141& 2500& MaxFE&211 &2500&MaxFE & 141& 2500&MaxFE\\ \hline
10 & 278 &  64 & TOL & 26 & 77 & TOL &278 & 64&TOL &307 &64& TOL& 278 & 64 &TOL\\ \hline
11  & 277 & 158 & TOL & 625 & 2500 & MaxFE&5000 &106 &MaxIt &306 &156&TOL &277  &539 &TOL\\ \hline
12  & 278 & 150 & TOL & 93 & 343 & TOL & 5000&98&MaxIt &306 &139& TOL& 278& 143&TOL\\ \hline
13  & 278 & 150 & TOL & 93 & 343 & TOL & 5000&98&MaxIt & 306&139& TOL& 278& 143&TOL\\ \hline
14  & 278 & 45 & TOL & 37 & 92  & TOL &5000 &17 &MaxIt & 307&45&TOL & 278& 45&TOL\\ \hline
15  & 278 & 77 & TOL & 48 & 133 & TOL & 278&77&TOL & 5000&77&MaxIt & 278& 77&TOL\\ \hline
16  & 278 & 151 & TOL & 93 & 345 & TOL &5000 &99&MaxIt & 306&140& TOL& 278& 144&TOL\\ \hline
17  & 277 & 63 & TOL & 21 & 64 & TOL & 277&63&TOL & 307&63&TOL & 277 & 63&TOL\\ \hline
18  & 288 & 260 & TOL & 34 & 137 & TOL & 277&289&TOL & 305&314& TOL& 270 & 369& TOL\\ \hline
19  & 834 & 2500 & MaxFE & 627 & 2500 & MaxFE &834 &2500&MaxFE & 834&2500& MaxFE& 834& 2500&MaxFE\\ \hline
20  & 278 & 108 & TOL & 26 & 131 & TOL &5000 &23&MaxIt &307 &108& TOL& 278& 108&TOL\\ \hline
21  & 278 & 106 & TOL & 26 & 128 & TOL & 5000&21&MaxIt & 307&106&TOL & 278& 106&TOL\\ \hline
22  & 277 & 76 & TOL & 47 & 183 & TOL &277 &76& TOL& 306&76& TOL&277 & 82&TOL\\ \hline
23  & 277 & 712 & TOL & 37 & 129 & TOL & 277&708&TOL & 307&791&TOL & 277& 704&TOL\\ \hline
24  & 278 & 480 & TOL & 128  & 747 & TOL &278 &480& TOL& 307&480& TOL& 278& 480&TOL\\ \hline
25  &  289 & 480 & TOL & 130 & 774 & TOL &278 &508&TOL &305 &522& TOL&273 & 625&TOL\\ \hline
26  & 281 & 192 & TOL & 95 & 402 & TOL & 281&192&TOL &5000 &192& MaxIt& 281& 192&TOL\\ \hline
27  & 5000 & 443 & MaxIt & 34 & 86 & TOL & 5000 &443&TOL &5000 &437& MaxIt&5000 & 443&MaxIt\\ \hline
28  & 278 & 81 & TOL & 20 & 81 & TOL & 5000&13&MaxIt &307 &81& TOL&278 & 81&TOL\\ \hline
29  & 278 & 146 & TOL & 43 & 259 & TOL &5000 &44&MaxIt & 307&146&TOL & 278& 146&TOL\\ \hline
30  & 625 & 2500 & MaxFE & 418 & 2500 & MaxFE &625 &2500&MaxFe & 625&2500& MaxFE& 625& 2500&MaxFE\\ \hline
31  & 288 & 800 & TOL & 39 & 391 & TOL &277 &939&TOL & 306&965& TOL& 270& 1130&TOL\\ \hline
32  & 278 & 13 & TOL & 247 & 2500 & MaxFE &278 &13& TOL& 307&287&TOL & 278 & 13& TOL\\ \hline
33  & 277 & 1818 & TOL & 51 & 398 & TOL & 384&2500&MaxFE  & 306&2011& TOL&277 & 1810&TOL\\ \hline
34  & 280 & 140 & TOL & 61 & 191 & TOL &5000 &77&MaxIt & 307&120& TOL&278 & 134&TOL\\ \hline
35  & 278 & 326 & TOL & 119 & 410 &TOL &277 &320&TOL & 307&335& TOL& 277& 509&TOL\\ \hline
36  & 403 & 737 & TOL &  125 & 751 & TOL & 294&746& TOL& 322&755&TOL & 278& 744&TOL\\ \hline
37  & 285 & 287 & TOL & 48 & 210 & TOL &284 &122&TOL & 5000&275& TOL&284 & 122&TOL\\ \hline
38  & 500 & 2500 & MaxFE & 417  & 2500 & MaxFE &500 &2500&MaxFE &500 &2500&MaxFE & 500& 2500&MaxFE\\ \hline
39  & 392 & 1501 & TOL & 325 & 1945 & TOL &5000 &1135&MaxIt & 5000&1447& MaxIt& 634& 2500&TOL\\ \hline
40  & 278 & 106 & TOL & 70 & 297 & TOL &5000 &61&MaxIt & 306&106&TOL & 278& 106&TOL\\ \hline
41  & 278 & 592 & TOL &  140 & 782 & TOL &278 &750&TOL & 307&592&TOL &420 & 1842&TOL\\ \hline
42  & 277 & 1241 & TOL & 46 & 288 & TOL & 277&1234&TOL & 307&1377&TOL & 278& 1238&TOL\\ \hline
43  & 282 & 1373 & TOL & 48 & 299 & TOL &278 &1239&TOL &445 &2069&TOL & 278& 1226&TOL\\ \hline
44  & 278 & 110 & TOL & 53 & 252 & TOL & 5000&38&MaxIt & 307&110&TOL & 278& 110&TOL\\ \hline
45  & 278  & 107 & TOL & 76 & 431 & TOL & 5000&39&MaxIt & 306&107& TOL& 278& 107&TOL\\ \hline
46  & 278 & 100 & TOL & 66 & 352 & TOL & 278&100&TOL & 306&100&TOL & 278& 100&TOL\\ \hline
47  & 278 & 121 & TOL & 20 & 117 & TOL & 278&121&TOL & 307&107&TOL & 278& 121&TOL\\ \hline
48  & 278 & 106 & TOL & 20 & 113& TOL&278 &106& TOL& 307&104&TOL & 278& 106&TOL\\ \hline
49  & 278 & 195 & TOL & 60 & 426& TOL & 278&195&TOL & 306&195&TOL & 277& 177&TOL\\ \hline
50  & 278 & 457 & TOL & 74 & 484&TOL &278 &457&TOL & 307&181& TOL& 278& 457&TOL\\ \hline
51  & 287 & 538 & TOL & 46 & 396& TOL&364 &2500&MaxFE & 318&663&TOL &361 & 2500&MaxFE\\ \hline
52  & 284 & 1289 & TOL & 20 & 101& TOL& 284&1289&TOL & 5000&155&TOL & 284& 1289&TOL\\ \hline
53  & 405 & 2500 & MaxFE & 625 & 2500&MaxFE &405 &2500&MaxFE & 405&2500&MaxFE & 405& 2500&MaxFE\\ \hline
54  & 602 & 1443 & TOL & 85 & 826& TOL&249 &1016&TOL & 450&1275&TOL & 252& 1045&TOL\\ \hline
55  & 277 & 1856 & TOL & 106 & 824& TOL&278 &1861&TOL & 307&2055&TOL & 277& 1849&TOL\\ \hline
56  & 357 & 2500 & MaxFE & 233 & 2500&MaxFE &5000 &547&MaxIt & 361&2500&MaxFE & 247& 2500&MaxFE\\ \hline
57  & 376 & 2500 & MaxFE & 233 & 2500& MaxFE&5000 &547&MaxIt &347 &2500& MaxFE& 255& 2500&MaxFE\\ \hline
58  & 376 & 2500 & MaxFE  & 232 & 2500& MaxFE&5000 &964&MaxIt &345 &2500& MaxFE& 257& 2500&MaxFE\\ \hline
59  & 278 & 621 & TOL & 100 & 1294& TOL & 213&2500& MaxFE& 306&621& TOL& 215& 2500&MaxFE\\ \hline
60  & 167 & 2500 & MaxFE & 157 & 2500& MaxFE&167 &2500&MaxFE & 167&2500&MaxFE & 167& 2500&MaxFE\\ \hline
61  & 167 & 2500 & MaxFE & 157 & 2500& MaxFE&167 &2500& MaxFE&167 &2500& MaxFE& 167& 2500&MaxFE\\ \hline
62  & 149 & 2500 & MaxFE & 150 & 2500& MaxFE&149 &2500& MaxFE& 149&2500&MaxFE & 149& 2500&MaxFE\\ \hline
63  & 278 & 2446 & TOL & 104 & 2500& MaxFE& 5000&2142& MaxIt& 307&2446&TOL & 278& 2446&TOL\\ \hline

\end{tabular}
}
\caption{Results of numerical experiments}
\end{center}
\end{table}

\

\begin{figure}[H]
 \centering
  \subfloat[]{
   \label{f:tol11}
    \includegraphics[width=0.5\textwidth]{PP63problemas1e-1_010518.jpg}}
  \subfloat[]{
   \label{f:tol22}
    \includegraphics[width=0.5\textwidth]{PP63problemas1e-3_010518.jpg}}
    \\
    \subfloat[]{
    \label{f:tol33}
    \includegraphics[width=0.5\textwidth]{PP63problemas1e-5_010518.jpg}}
\caption{Performance profiles for the five strategies}

\label{f:performanceprofile63_2}
\end{figure}

From the analysis of the figures included in Figure \ref{f:performanceprofile63_2} we can obtain the following conclusions. First, in most cases the use of  a nonmonotone line search of the kind (\ref{nmc}), (\ref{C}) or (\ref{lambda}) turns into an advantage in the performance of the algorithms compared to the classical Armijo's rule (\ref{armijo}). In other words, a greater effort devoted to building $f_{\max}(x_k)$ or $C_k$ results in a decrease in the number of function evaluations carried out by the algorithm, which is one of the main goals in derivative-free methods. Second, although the strategies (\ref{nmc}) and (\ref{lambda}) have similar definitions, the above analysis shows, while  \texttt{$\lambda$patternsearch} reduces its performance as the level of accuracy increases, \texttt{nmps} remains stable for all values of  $\tau$. So, if we should choose between this two strategies, \texttt{nmps} would be  the most suitable. Third, the \texttt{Cpatternsearch} algorithm could be considered as the solver with the best performance because it is always above the other solvers as the level of accuracy increases. Our algorithm \texttt{nmps}, in its turn, seems to be a good competitor to \texttt{Cpatternsearch}, attaining a similar performance with respect to the latter in several cases. Also, \texttt{nmps} always obtains the second place regarding the probability to solve all the problems. At the end, to our surprise, we observe that the performance of \texttt{patternsearch} algorithm is in many cases below all remaining methods.

\

\section{Conclusions}

In this paper, we have proposed a new pattern search algorithm \texttt{nmps} to solve bound constrained optimization problems, which uses a nonmonotone line search strategy for accepting the new iterate. We have proved that, under mild assumptions, we can guarantee global convergence of our method to a KKT point. This result is strongly based on  the relationship between the step length and the stationarity measure (defined by Conn et al. in \cite{CGT00}), and it  was proved in Section~4.  Furthermore, we have performed several numerical experiments where we have compared the performance of our algorithm to other line search strategies that were implemented in  \texttt{patternsearch}, \texttt{$\lambda$patternsearch}, \texttt{Cpatternsearch} and \texttt{armijo} algorithms. The benchmark results were satisfactory, so we can conclude that the \texttt{nmps} algorithm is competitive, compared to the other solvers, as the numerical experiments reveal. We are currently working on an extension of the \texttt{nmps} algorithm to linearly constrained optimization problems, taking into account the directions generated by the linear constraints.

\

\section*{Disclosure statement}

No potential conflict of interest was reported by the authors.

\

\section*{Funding}

This work was partially supported by research project Consejo Nacional de Investigaciones Cient\'ificas y T\'ecnicas (CONICET) PIP 112--201101--00050, PUE 22920160100134CO and Secretar\'ia de Ciencia y Tecnolog\'ia (SECyT-UNC).

\
\bibliographystyle{plain}

config: arxiv


TITLE: Coefficient of $x$ in the expansion of $P(x) = (x+1)(x+3) \cdots (x+2^k-1)$
QUESTION [1 upvotes]: Prove that the coefficient of $x$ in the expansion of $P(x) = (x+1)(x+3) \cdots (x+2^k-1)$ is $$(1 \cdot 3 \cdots (2^k-1))\cdot \sum_{i=1}^{2^{k-1}} \dfrac{1}{2i-1}.$$

For any $x$ in any one of the factors we take, we can pick any other possible combinations of the constant terms in the other sets. How do we use that to derive the formula?

REPLY [2 votes]: As an alternative to @dxiv's excellent method:
Method 1: when expanding the product, a term of the form $ax$ is obtained by taking all constant coefficients of each factor, except one. Hence the $x$ coefficient of a polynomial $P(x)=(x+a_1)(x+a_2)\dots(x+a_n)$ is
$$
\sum_{j=1}^n\frac{\prod_{k=1}^na_k}{a_j}=P(0)\sum_{j=1}^n \frac{1}{a_j}
$$
(assuming no $a_j$'s is $0$).
Method 2: you can use induction and the special case of the Cauchy product formula $c_1(PQ)=c_0(P)c_1(Q)+c_1(P)c_0(Q)$ (where $c_j(P)$ denotes the coefficient of $x^j$ of a polynomial $P$).


TITLE: How to prove statement about $\mathcal{O}, \Theta$ and $\hbox{o}$?
QUESTION [0 upvotes]: For a given function g,
Prove that $\hbox{o}(g) \neq O(g) - Θ(g)$.
Thanks for the help in advance

REPLY [1 votes]: My comment apparently wasn't clear enough. The problem statement starts with let $f \in \mathcal{O}(g),~f \not\in \Theta(g)$ and $f \not\in \hbox{o}(g)$ so need to find $f$ or $g$ for this statement. We then quickly show that since $f \in \mathcal{O}(g),~f \not\in \Theta(g)$, we must have $f \in \mathcal{O}(g) - \Theta(g) = \{h\ |\ h \in \mathcal{O}(g) \mathrm{\ and\ } h \not\in \Theta(g)\}$. But we already know that $f \not\in \hbox{o}(g)$. Thus we have an element from the RHS which is not an element of the LHS so the two sides can not be equal as sets.

For two sets $A$ and $B$ to be equal, we must have that $A \subseteq B$ and $B \subseteq A$ where $\subseteq$ stands for subset. Formally, $A \subseteq B$ means that for any $x \in A$ we must have $x \in B$. So set equality basically says that pick anything from one set and we must be able to find it in the other set.
But in the problem above, we found a function $f$ that was part of one set but not part of the other set. Thus the two sets can not be equal.


TITLE: Definition of indefinite orthogonal group for 3 by 3 matricies, and how it it connected to special linear group for 2 by 2 matricies
QUESTION [2 upvotes]: I'm working on a project to show that $SL(2, \mathbb{R})$ is the same the identity component of $SO(1,2)=\{A\in M_{3x3}(\mathbb{R}):A^tI_{1,2}A=I_{1,2}, det(A)=1\}$ where $$I_{1,2} = \quad
\begin{pmatrix}
1 & 0 & 0 \\
0 & -1 & 0 \\
0 & 0 & -1\\
\end{pmatrix}$$ I have a homoeomorphism $$Ad:SL(2,\mathbb{R})\rightarrow GL(sl_2(\mathbb{R})), Ad(\sigma)(u)=\sigma u \sigma ^{-1} for \space \space\sigma \in SL(2, \mathbb{R}), u \in sl_2(\mathbb{R})$$  a quadratic form on $sl_2(\mathbb{R})$ given by $$Q(u,v) = - \frac{1}{2}Trace(uv)$$ and a basis of of $sl_2(\mathbb{R})$ $$E_1=
\quad
\begin{pmatrix}
0 & 1 \\
-1 & 0
\end{pmatrix}, \space E_2= \quad
\begin{pmatrix}
1 & 0 \\
0 & -1
\end{pmatrix}, \space E_3= \quad
\begin{pmatrix}
0 & 1 \\
1 & 0
\end{pmatrix}$$
By computing $Q(E_i,E_j)$, I have that the signature of $Q$ is $(1,2)$. I have shown that $Q(Ad(\sigma)(u),Ad(\sigma)(v))=Q(u,v)$.
In addition to the definition I gave before of $SO(1,2)$, I understand that it can also defined as matrices that preserve an inner product/bilinear/quadratic form of signature $(1,2)$. How is this the same as the definition I gave before? This looks like what I have for $Q$, but I don't see how to make the jump to 3 by 3 matricies. I have a 3 by 3 matrix representation of $Ad(\sigma)$ also.
From this point I'm supposed to conclude $Ad(SL2,\mathbb{R})\subset O(1,2)$, but I don't quite see the connection. I see the quadratic form I have has the same signature as $O(1,2)$. I have a feeling the answer is right in front of me but I can't connect the dots.

REPLY [1 votes]: From pages 123-124 in Noneuclidean Tesselations and Their Groups by Wilhelm  Magnus, every $A$ with $\det A = +1$ is given by real numbers $\alpha \delta - \beta \gamma = 1$ and
$$
A =
\left(
\begin{array}{ccc}
\frac{1}{2} \left( \alpha^2 + \beta^2 + \gamma^2 + \delta^2 \right) & \left( \alpha \beta + \gamma \delta \right) & \frac{1}{2} \left( \alpha^2 - \beta^2 + \gamma^2 - \delta^2 \right) \\
\left( \alpha \gamma + \beta \delta \right) & \left( \alpha \delta + \beta \gamma  \right) & \left( \alpha \gamma - \beta \delta \right) \\
\frac{1}{2} \left( \alpha^2 + \beta^2 - \gamma^2 - \delta^2 \right) & \left( \alpha \beta - \gamma \delta \right) & \frac{1}{2} \left( \alpha^2 - \beta^2 - \gamma^2 + \delta^2 \right) \\
\end{array}
\right)
$$
In turn, this goes back to pages 533-534 in the original German, Fricke and Klein (1897). There is a recent translation into English.


TITLE: Combinatorial proof of $ \sum\limits_{k=0}^n(-1)^k\frac{2^{n-k}\binom{n}{k}}{(m+k+1)\binom{m+k}{m}}=\sum\limits_{k=0}^n\frac{\binom{n}{k}}{m+k+1}$
QUESTION [3 upvotes]: While answering the following question : Solution to a definite integral as $\int_0^{1}(x^{m}\left(1+x)^{n}dx\right)$, I came accross a strange identity involving  binomials.
Using the binomial theorem, we can find our first expression to that integral : $ \int_{0}^{1}{x^{m}\left(1+x\right)^{n}\,\mathrm{d}x}=\sum\limits_{k=0}^{n}{\frac{\binom{n}{k}}{m+k+1}} $, while solving it the way I did leads to another expression : $ \int_{0}^{1}{x^{m}\left(1+x\right)^{n}\,\mathrm{d}x}=\sum\limits_{k=0}^{n}{\left(-1\right)^{k}\frac{2^{n-k}\binom{n}{k}}{\left(m+k+1\right)\binom{m+k}{m}}} $.

I was wondering if we could prove, using combinatorials, that for any $ n,m\in\mathbb{N} $ : $$ \sum\limits_{k=0}^{n}{\left(-1\right)^{k}\frac{2^{n-k}\binom{n}{k}}{\left(m+k+1\right)\binom{m+k}{m}}}=\sum\limits_{k=0}^{n}{\frac{\binom{n}{k}}{m+k+1}}$$

REPLY [1 votes]: Here is an algebraic proof by way of enrichment. We seek to verify that
$$\sum_{k=0}^n (-1)^k
\frac{2^{n-k} {n\choose k}}{(m+k+1) {m+k\choose k}}
= \sum_{k=0}^n \frac{{n\choose k}}{m+k+1}.$$
We can re-write this as
$$\frac{m! n!}{(n+m+1)!} 2^n
\sum_{k=0}^n (-1)^k 2^{-k} {n+m+1\choose n-k}
= \sum_{k=0}^n \frac{{n\choose k}}{m+k+1}$$
or
$$2^n \sum_{k=0}^n (-1)^k 2^{-k} {n+m+1\choose n-k}
= (m+1) {n+m+1\choose n}
\sum_{k=0}^n \frac{{n\choose k}}{m+k+1}.$$
We get for the LHS
$$2^n \sum_{k=0}^n (-1)^k 2^{-k} {n+m+1\choose m+k+1}
= 2^n \sum_{k=0}^n (-1)^k 2^{-k} [z^{n-k}]
\frac{1}{(1-z)^{m+k+2}}
\\ = 2^n [z^n] \frac{1}{(1-z)^{m+2}}
\sum_{k=0}^n (-1)^k 2^{-k} z^k \frac{1}{(1-z)^k}.$$
Here the coefficient extractor enforces the range
and we find
$$2^n [z^n] \frac{1}{(1-z)^{m+2}}
\sum_{k\ge 0} (-1)^k 2^{-k} z^k \frac{1}{(1-z)^k}
= 2^n [z^n] \frac{1}{(1-z)^{m+2}}
\frac{1}{1+z/(1-z)/2}
\\ = [z^n] \frac{1}{(1-2z)^{m+2}}
\frac{1}{1+z/(1-2z)}
= [z^n] \frac{1}{(1-2z)^{m+1}}\frac{1}{1-z}.$$
On the other hand we have
$${n+m+1\choose n} {n\choose k}
= \frac{(n+m+1)!}{(m+1)! \times k! \times (n-k)!}
= {n+m+1\choose n-k} {m+k+1\choose m+1}$$
which gives for  the RHS
$$\sum_{k=0}^n {n+m+1\choose n-k}
\frac{m+1}{m+k+1} {m+k+1\choose m+1}
= \sum_{k=0}^n {n+m+1\choose m+k+1} {m+k\choose m}
\\ = \sum_{k=0}^n {m+k\choose m}
[z^{n-k}] \frac{1}{(1-z)^{m+k+2}}
= [z^n] \sum_{k=0}^n {m+k\choose m}
\frac{1}{(1-z)^{m+k+2}} z^k.$$
We once more have the coefficient extractor enforcing the range
and we get
$$[z^n] \frac{1}{(1-z)^{m+2}} \sum_{k\ge 0} {m+k\choose m}
\frac{1}{(1-z)^k} z^k
\\ = [z^n] \frac{1}{(1-z)^{m+2}} \frac{1}{(1-z/(1-z))^{m+1}}
= [z^n] \frac{1}{1-z} \frac{1}{(1-2z)^{m+1}}.$$
The LHS is the same as the RHS which concludes the argument. The
coeffcient extractor evaluates to
$$\bbox[5px,border:2px solid #00A000]{
\sum_{k=0}^n {k+m\choose m} 2^k.}$$


TITLE: What does one do when Wolframalpha fails to solve an integral?
QUESTION [4 upvotes]: I'm looking for an analytic solution to this integral:
$$
\int\sqrt{\left(\frac{2 d}{(1 + 4 x ^ 2)^{\frac{3}{2}}} + 1\right) \frac{2}{\sqrt{1 + 4 x ^ 2}}}dx, d > -0.5
$$
Wolframalpha fails to find a solution to this, and using quadratures for evaluation is too slow for my use case since I need this for a real-time application.
What does one do in such cases? My intuition is to try to find a function that approximates the integral decently enough on a graphic calculator, but it's quite challenging to start from scratch.
The challenging part of this integral is the $+ 1$ in the first term. Without it, the solution is trivial.
Update:
The closest approximation I found is this:
$$
\frac{6 x \sqrt{\frac{2 d}{\sqrt{1 + 4 x ^ 2}} + 1}}{\sqrt[4]{9 ^ 2 x ^ 2 + 8 ^ 2} + 2}
$$
How could I improve the accuracy of this?

REPLY [7 votes]: First of all:
$$\sqrt{\frac{2d}{(4x^2+1)^\frac32}+1}=\sum_{n=0}^\infty\binom{\frac12}n\left(\frac{2d}{(4x^2+1)^\frac32}\right)^n= \sum_{n=0}^\infty\binom{\frac12}n(2d)^n(4x^2+1)^{-\frac{3n}2}$$
Therefore:
$$\int\sqrt{\left(\frac{2 d}{(1 + 4 x ^ 2)^{\frac{3}{2}}} + 1\right)} \frac{\sqrt2}{\sqrt[4]{1 + 4 x ^ 2}} dx= \sqrt2\sum_{n=0}^\infty\binom{\frac12}n(2d)^n\int\frac1{\sqrt[4]{4 x ^ 2+1}}(4x^2+1)^{-\frac{3n}2}dx$$
we integrate with the incomplete beta function $\text B_z(a,b)$:
$$\int\sqrt{\frac2{\sqrt{4x^2+1}}\left(\frac{2 d}{(1 + 4 x ^ 2)^{\frac{3}{2}}} + 1\right)}dx=-\frac{i\text{sgn}(x)}{2^\frac32}\sum_{n=0}^\infty\binom{\frac12}n (2d)^n \text B_{-4x^2}\left(\frac12,\frac34-\frac{3n}2\right)$$
which works when comparing both test links’ results, where the $5$th term in the example is on the order of $10^{-8}$ with potentially faster decaying terms as $n\to\infty$. It also works for the binomial series radius of convergence $2|d|<(4x^2+1)^\frac32\iff d\ge\frac12,x>\pm\frac12\sqrt{(2d)^\frac23-1}$:

Now you have an analytic solution as requested