text:
\begin{document}

\title[Graded identities with involution for the algebra of upper triangular matrices]{Graded identities with involution for the algebra of upper triangular matrices}

\thanks{Corresponding Author: D. Diniz}

\author[D. Diniz]{Diogo Diniz}
\address{Unidade Acadêmica de Matemática, Universidade Federal de Campina Grande, Campina Grande, PB, 58429-970, Brazil}
\email{diogo@mat.ufcg.edu.br}
\thanks{D. Diniz was partially supported by CNPq grants No.~303822/2016-3, No.~406401/2016-0 and No.~421129/2018-2.}

\author[A. Ramos]{Alex Ramos}
\address{Universidade de Pernambuco, Caruaru, PE, 55294-902, Brazil}
\email{alex.borges@upe.br}
\thanks{A. Ramos was partially supported by CNPq grant No.~406401/2016-0}

\keywords{Graded involutions; polynomial identities; algebra of upper block-triangular matrices; }

\subjclass[2010]{16R10, 16W50}

\begin{abstract}
	Let $F$ be a field of characteristic zero. We prove that if a group grading on $UT_m(F)$ admits a graded involution then this grading is a coarsening of a $\mathbb{Z}^{\lfloor\frac{m}{2}\rfloor}$-grading on $UT_m(F)$ and the graded involution is equivalent to the reflection or symplectic involution on $UT_m(F)$. A finite basis for the $(\mathbb{Z}^{\lfloor\frac{m}{2}\rfloor},\ast)$-identities is exhibited for the reflection and symplectic involutions and the asymptotic growth of the $(\mathbb{Z}^{\lfloor\frac{m}{2}\rfloor},\ast)$-codimensions is determined. As a consequence we prove that for any $G$-grading on $UT_m(F)$ and any graded involution the $(G,\ast)$-exponent is $m$ if $m$ is even and either $m$ or $m+1$ if $m$ is odd. For the algebra $UT_3(F)$ there are, up to equivalence, two non-trivial gradings that admit a graded involution: the canonical $\mathbb{Z}$-grading  and the $\mathbb{Z}_2$-grading induced by $(0,1,0)$. We determine a basis for the $(\mathbb{Z}_2,\ast)$-identities and prove that the exponent is $3$. Hence we conclude that the ordinary $\ast$-exponent for $UT_3(F)$ is $3$.
\end{abstract}
\maketitle

\section{Introduction}
Let $F$ be a field and let $m$ be a positive integer. The algebra $UT_m(F)$ of $m\times m$ upper triangular matrices with entries in $F$ plays an important role in the theory of algebras with polynomial identities. A grading by a group $G$ (or a $G$-grading) on an algebra $A$ is a vector space decomposition $A=\oplus_{g\in G}A_g$ such that $A_gA_h\subseteq A_{gh}$, for every $g,h\in G$. The subspace $A_g$ is called the homogeneous component of degree $g$. If $a$ is a non-zero element of $A_g$ we say that $a$ is homogeneous of degree $g$. The support of the grading is the set $\{g\in G \mid A_g\neq 0\}$.

Let ${\bf g}=(g_1,\dots, g_m)$ be an $m$-tuple of elements of the group $G$. Then $UT_m(F)$ admits a grading for which the elementary matrix $e_{ij}$ with $1$ in the $(i,j)$-th entry and $0$ in the remaining entries is homogeneous of degree $g_ig_j^{-1}$. We say that this is the elementary grading on $UT_m(F)$ induced by ${\bf g}$.
The group gradings on $UT_m(F)$ were classified by A. Valenti and M. Zaicev.
\begin{theorem}\cite[Theorem 7]{VZ}\label{elgr}
Let $G$ be an arbitrary group and $F$ a field. Suppose that the algebra $UT_m(F)=A=\oplus_{g\in G}A_g$ of $m\times m$ upper triangular matrices over the field $F$ is $G$-graded. Then $A$, as a $G$-graded algebra, is isomorphic to $UT_m(F)$ with an elementary $G$-grading.
\end{theorem}
An involution $\ast$ on the algebra $A$ is a linear map $a\mapsto a^{\ast}$ such that $(a^{\ast})^{\ast}=a$ and $(ab)^{\ast}=b^{\ast}a^{\ast}$, for every $a,b\in A$. If $A$ has a $G$-grading $A=\oplus_{g\in G}A_g$ then $\ast$ is a graded involution if $A_g^{\ast}\subseteq A_g$, for every $g\in G$. We say that $A$ is a $G$-graded algebra with graded involution or simply that $A$ is a $(G,\ast)$-algebra. If $B$ is a $(G,\ast)$-algebra with involution $\circ$ then a homomorphism of algebras $\varphi:A\rightarrow B$ is a homomorphism of $(G,\ast)$-algebras if $\varphi(A_g)\subseteq B_g$ for every $g\in G$ and $\varphi(a^{\ast})=\varphi(a)^{\circ}$, for every $a\in A$. If $\varphi$ is an isomorphism of algebras then we say that $A$ and $B$ are isomorphic as $(G,\ast)$-algebras and that $\ast$ and $\circ$ are equivalent. The $H$-grading $A^{\prime}=\oplus_{h\in H}A_{h}^{\prime}$ on the algebra $A$ is a coarsening of the $G$-grading
\begin{align}\label{ggrading}
A=\oplus_{g\in G}A_{g}
\end{align}
if for every $g\in G$ there exists $h\in H$ such that $A_g\subseteq A_h^{\prime}$. Let $\alpha:G\rightarrow H$ be a homomorphism of groups. Then we construct an $H$-grading from the $G$-grading (\ref{ggrading}) with homogeneous components $A_h^{\prime}=\oplus_{g\in \alpha^{-1}(h)}A_g$, $h$ in $H$. We refer to this $H$-grading as the coarsening of the $G$-grading (\ref{ggrading}) induced by $\alpha$.

A basis for the (ordinary) polynomial identities for $UT_m(F)$ is well known (see, for example, \cite{GZ}). The linear transformation $\ast$ such that $e_{ij}^\ast=e_{m+1-j,m+1-i}$ is an involution on $UT_m(F)$ called the reflection involution. If $m=2r$ let
\begin{align}\label{D}
D=\left(\begin{array}{cc}
I_r & 0\\
0& -I_r
\end{array}\right),
\end{align}
the involution $s$ on $UT_{m}(F)$ given by $A^s=DA^{\ast}D^{-1}$, for $A\in UT_m(F)$, is called the symplectic involution. O. M. Di Vincenzo, P. Koshlukov and R. La Scala proved in \cite[Proposition 2.5]{VKS} that every involution on $UT_m(F)$ is equivalent to the reflection involution or to the symplectic involution. The polynomial identities with involution for $UT_m(F)$ were also studied in \cite{VKS}, a finite basis for the identities with involution, and other numerical invariants, were determined for $m=2,3$. The graded involutions on $UT_m(F)$, for an algebraically closed field $F$ with $\mathrm{char}\, F\neq 2$ were classified in \cite{FGDY}. The classification is given in the next result.
\begin{corollary}\cite[Corollary 34]{FGDY}\label{classf}
	Let $F$ be an algebraically closed field, $\mathrm{char}\,F\neq 2$ and let $G$ be a group. Let $\mathcal{U}^{\prime}$ be a $G$-grading on $UT_m(F)$ such that $\mathrm{supp}\ \mathcal{U}^{\prime}$ generates $G$. If $\mathcal{U}^{\prime}$ admits an antiautomorphism then $G$ is an abelian group. Let $\varphi^{\prime}$ be an involution on the graded algebra $\mathcal{U}^{\prime}$. Then $(\mathcal{U}^{\prime},\varphi^{\prime})$ is isomorphic to $(\mathcal{U},\varphi)$, where $\mathcal{U}$ is the elementary grading on $UT_m(F)$ induced by a tuple $(g_1,\dots,g_m)$ of elements of $G$ such that $g_1g_m=g_2g_{m-1}=\cdots=g_mg_1$ and $\varphi$ is either $\ast$ or $s$.
\end{corollary}
Let $X_{g}=\{x_{i,g}, x_{i,g}^{\ast} \mid i\in \mathbb{N}\}$, $g\in G$, be a family of countable pairwise disjoint sets. The free algebra $F\langle X^{\prime} \rangle$, freely generated by $X^{\prime}=\cup_{g\in G}X_g$, admits an involution, also denoted by $\ast$, such that $(x_{i,g})^{\ast}=x_{i,g}^{\ast}$ and $(x_{i,g}^{\ast})^{\ast}=x_{i,g}$. The algebra $F\langle X^{\prime} \rangle$ also admits a grading by $G$ such that the indeterminates in $X_g$ are homogeneous of degree $g$. Then $\ast$ is a graded involution on $F\langle X^{\prime} \rangle$. Note that $F\langle X^{\prime} \rangle$ is generated, as an algebra with involution, by the set $X_G=\{x_{i,g}\mid i\in \mathbb{N}, g\in G\}$. Henceforth we denote by $F_{G,\ast}\langle X_G \rangle$ the algebra $F\langle X^{\prime} \rangle$, we may omit the group $G$ in $X_G$ and write $F_{G,\ast}\langle X \rangle$.  If $A$ is an algebra with a $G$-grading and graded involution $\ast$ then for every map $X\rightarrow A$ there exists a unique homomorphism (of $(G,\ast)$-algebras) $\varphi:F_{G,\ast}\langle X \rangle\rightarrow A$ that extends the map $X\rightarrow A$. The polynomial $f(x_{i_1,g_1},\dots, x_{i_n,g_n})$ is a $(G,\ast)$-identity for $A$ if $f(a_1,\dots, a_n)=0$ whenever $a_1\in A_{g_1},\dots, a_n\in A_{g_n}$. Henceforth a substitution $S$ for $f(x_{i_1,g_1},\dots, x_{i_n,g_n})$ is a tuple $(a_1,\dots, a_n)\in A^{n}$ such that $a_i\in A_{g_i}$, $i=1,\dots, n$. The set of $(G,\ast)$-identities for $A$ is denoted by $T_{G\,\ast}(A)$. We remark that $T_{G\,\ast}(A)$ is a $T(G,\ast)$-ideal of $F_{G,\ast}\langle X \rangle$, i.e., it is invariant under the involution $\ast$ and the endomorphisms of $F_{G,\ast}\langle X \rangle$ as a $(G,\ast)$-algebra. Such ideals of $F_{G,\ast}\langle X \rangle$ are called $T_{G,\ast}$-ideals. If $P$ is a subset of $F_{G,\ast}\langle X \rangle$ such that the intersection of the $T(G,\ast)$-ideals of $F_{G,\ast}\langle X \rangle$ that contain $P$ is $T_{G\,\ast}(A)$ then  we say that $P$ is a basis for $T_{G\,\ast}(A)$. If $G=\{e\}$ we recover the definition of $\ast$-polynomial identity for algebras with involution. In this case we denote by $T_{\ast}(A)$ the set of $\ast$-identities for the algebra with involution $A$.

The graded polynomial identities for $M_m(F)$ with the transpose involutions were studied in \cite{HN} for a crossed product grading and $\mathrm{char}\, F=0$ and in \cite{GC} for an elementary grading with commutative neutral component and an infinite field $F$. In \cite[Theorem 2.3]{DKV} the authors provided basis for the graded polynomial identities for $UT_{m}(F)$ with an arbitrary grading, as a consequence they proved that two gradings are isomorphic if and only if they satisfy the same graded polynomial identities. In the next proposition we prove that the analogous result holds for $(G,\ast)$-identities.
\begin{remark}\label{rem}
	The graded identities of an algebra determine the ordinary identities, see \cite[Proposition 1]{BD}. The analogous result holds for $\ast$-graded identities and the proof is similar. More precisely, if $A=\oplus_{g\in G}A_g$, $B=\oplus_{g\in G}B_g$ are $G$-graded algebras with graded involutions $\circ$, $\diamond$, respectively, such that $T_{G,\ast}(A)=T_{G,\ast}(B)$ then $T_{\ast}(A)=T_{\ast}(B)$.
\end{remark}

The subalgebra $F\langle X \rangle$ of $F_{G,\ast}\langle X \rangle$ (viewed as an algebra, without involution) generate by $X$ is the free $G$-graded algebra. If $A$ is a $G$-graded algebra with graded involution then $T_{G,\ast}(A)\cap F\langle X \rangle$ is the set of $G$-graded identities for $A$ (as a graded algebra, without involution), this set is denoted by $T_G(A)$.
\begin{remark}\label{idisom}
	Let $A$, $B$ be $G$-gradings on algebras of upper triangular matrices. Then $T_G(A)=T_G(B)$ if and only if $A$ and $B$ are isomorphic as $G$-graded algebras. Moreover if $A$ and $B$ are elementary gradings then $A=B$, see \cite{DKV},\cite{DS}.
\end{remark}
\begin{proposition}
	Let $F$ be an algebraically closed field, $\mathrm{char}\, F\neq 2$. Let $\mathcal{U}$ and $\mathcal{U}^{\prime}$ be $G$-gradings on algebras of upper triangular matrices and let $\circ$, $\diamond$ be graded involutions on $\mathcal{U}$, $\mathcal{U}^{\prime}$, respectively. Then $(\mathcal{U},\circ)$ is isomorphic to $(\mathcal{U}^{\prime},\diamond)$ if and only if $T_{G,\ast}(\mathcal{U})=T_{G,\ast}(\mathcal{U}^{\prime})$.
\end{proposition}
\begin{proof}
	We assume that $T_{G,\ast}(\mathcal{U})=T_{G,\ast}(\mathcal{U}^{\prime})$ and that $(\mathcal{U},\circ)$, $(\mathcal{U}^{\prime},\diamond)$ are as in Corollary \ref{classf} with elementary gradings. Note that $T_G(\mathcal{U})=T_G(\mathcal{U}^{\prime})$, therefore Remark \ref{idisom} implies that $\mathcal{U}=\mathcal{U}^{\prime}$. Remark \ref{rem} implies that $(\mathcal{U},\circ)$, $(\mathcal{U}^{\prime},\diamond)$ satisfy the same $\ast$-identities. Let $m$ be the positive integer such that $\mathcal{U}$ is a grading on $UT_m(F)$.  If $m$ is odd then $\circ$ and $\diamond$ coincide with the reflection involution, thus $\circ=\diamond$ and we are done. Now assume that $m$ is even. Note that in the relatively free algebra determined by $(UT_m,\circ)$ the element $[x_1,x_2]\cdots[x_{2m-3},x_{2m-2}]$ is symmetric if $\circ$ is the reflection involution and skew-symmetric if $\circ$ is the symplectic involution. Since $(UT_m,\circ)$ and $(UT_m,\diamond)$ satisfy the same identities with involution we conclude that $\circ=\diamond$.
\end{proof}

Henceforth for $\delta\in \{\emptyset, \ast\}$ the symbol $x_{i,g}^{\delta}$ represents the indeterminate $x_{i,g}$ if $\delta=\emptyset$ and it represents the indeterminate $x_{i,g}^{\ast}$ if $\delta=\ast$. We denote by $P_{n}^{G,\ast}$ the subspace
\begin{align*}
\mathrm{span}\{x_{\sigma(1),g_1}^{\delta_1}\cdots x_{\sigma(n),g_n}^{\delta_n} \mid \sigma \in S_n, g_1,\dots, g_n \in G, \delta_i=\emptyset\mbox{ or }\delta_i=\ast, i=1,\dots,n\}.
\end{align*}
The $n$-th $(G,\ast)$-codimension of the algebra $A$ with a $G$-grading and graded involution $\ast$ is the dimension $c_n^{G,\ast}(A)$ of the vector space $P_n^{G,\ast}(A):=P_n^{G,\ast}/(P_n^{G,\ast}\cap T_{G,\ast}(A))$. If the limit
\begin{align*}
\lim\limits{n\to \infty}\sqrt[n]{c_n^{(G,\ast)}(A)},
\end{align*}
exists then it is called the $(G,\ast)$-exponent of $A$ and is denoted by $\mathrm{exp}^{G,\ast}(A)$.

An adaptation of the proof of \cite[Theorem 10]{FP} yields the following result.
\begin{proposition}\label{coars}
	Let $A$ be an algebra with a $G$-grading with finite support and let $\ast$ be a graded involution on $A$. If the $H$-grading  $A^{\prime}$ is a coarsening of the $G$-grading on $A$ induced by a surjective homomorphism then
	\begin{align*}
	c_n^{\ast}(A)\leq c_n^{H,\ast}(A^{\prime})\leq c_n^{G,\ast}(A),
	\end{align*}
	where $c_n^{\ast}(A)$ is the ordinary $n$-th codimension of $A$.
\end{proposition}
\begin{proof}
Let $\psi:G\rightarrow H$ be a surjective homomorphism. For each $h\in H$ choose $g_h\in\psi^{-1}(h)$. Let $S=\{g\in G\mid A_g\neq 0\}$ be the support of the $G$-grading on $A$ and set
\begin{align*}
y_{i,h}= \left\{\begin{array}{c}
\sum_{l\in S\cap \psi^{-1}(h)}x_{i,l},\mbox{ if }S\cap \psi^{-1}(h) \neq \emptyset,\\ x_{i,g_h},\mbox{ if }S\cap \psi^{-1}(h) = \emptyset
\end{array}\right..
\end{align*}
Let $R$ be the subalgebra (with involution) of $F_{G,\ast}\langle X_G \rangle $ generated by the set $\{y_{i,g_h}\mid i\in \mathbb{N}, h\in H\}$. The algebra $R$ admits an $H$-grading such that $y_{i,h}$ is homogeneous of degree $h$ and its involutin $R$ is a graded involution. The homomorphism from $F_{H,\ast}\langle X_H \rangle$ to $R$ such that $x_{i,h}\mapsto y_{i,h}$ is an isomorphism of $H$-graded algebras with involution. We identify $F_{H,\ast}\langle X_H \rangle$ with $R$, with this identification $T_{H,\ast}(A)= T_{G,\ast}(A)\cap R$ and $P_n^{H,\ast}\subseteq P_n^{G,\ast}$. Hence the kernel of the linear map
\begin{align}\label{linmap}
P_n^{H,\ast}\hookrightarrow P_n^{G,\ast}\rightarrow P_n^{G,\ast}(A),
\end{align}
where the first map is the inclusion and the second map is the canonical quotient map, is $P_n^{H,\ast}\cap T_{G,\ast}(A)$. Note that $P_n^{H,\ast}\cap T_{G,\ast}(A)=P_n^{H,\ast}\cap T_{H,\ast}(A^{\prime})$, hence (\ref{linmap}) induces an injective linear transformation $P_n^{H,\ast}(A^{\prime})\rightarrow P_n^{G,\ast}(A)$. Clearly this implies that $c_n^{H,\ast}(A^{\prime})\leq c_n^{G,\ast}(A)$. The other inequality is a consequence of this applied to the trivial group and the homomorphism $H\rightarrow \{e\}$.
\end{proof}

The paper is organized in the following way, in Section \ref{s2} we prove that every grading on $UT_m(F)$ that admits an involution is a coarsening of a suitable $\mathbb{Z}^{\lfloor\frac{m}{2}\rfloor}$-grading for which the reflection and symplectic (if $m$ is even) involutions are graded involutions. A basis for the $(G,\ast)$-identities for this algebra with the reflection and symplectic involutions is exhibited in Theorem \ref{mainfine}. We determine the growth of the $(\mathbb{Z}^{\lfloor\frac{m}{2}\rfloor}, \ast)$-codimensions and compute the $(\mathbb{Z}^{\lfloor\frac{m}{2}\rfloor}, \ast)$-exponent for $UT_m(F)$ in Theorem \ref{expo}. As a consequence we conclude that for any $G$-grading and any graded involution on $UT_m(F)$ the $(G,\ast)$-exponent is $m$ if $m$ is even and $m$ or $m+1$ if $m$ is odd. This is the analogous for the $(G,\ast)$-identities of the results in \cite{FP} for the graded exponent of $UT_m(F)$. In the graded case the exponent with an arbitrary grading coincides with the ordinary one (for $UT_m(F)$ as an associative, Lie or Jordan algebra). In Section \ref{s3} we prove that $UT_3$ has, up to equivalence two non-trivial gradings that admit graded involution, the canonical $\mathbb{Z}$-grading studied in Section \ref{s2} and the elementary $\mathbb{Z}_2$-grading induced by the triple $(0,1,0)$. In this case every involution is equivalent to the reflection involution. We exhibit a basis for the $(\mathbb{Z}_2,\ast)$-identities in Theorem \ref{basis}. We also prove that the $(\mathbb{Z}_2,\ast)$-exponent for $UT_3(F)$ in this case is $3$, hence Proposition \ref{coars} implies that the ordinary $\ast$-exponent for $UT_3(F)$ is $3$. We remark this is a direct consequence of the results in \cite{VKS} on the ordintary $\ast$-identities for $UT_3(F)$.

\section{Graded Identities with Involution for $UT_m(F)$}\label{s2}

In this section we construct a grading on $UT_m(F)$ that is the finest among the elementary gradings that admit graded involution. For this grading we determine a basis and compute the $\ast$-graded exponent for the reflection and the symplectic involutions.

\begin{definition}
	Let $m$ be a positive integer. The elementary $\mathbb{Z}^{\lfloor \frac{m}{2} \rfloor}$-grading on $UT_m(F)$ induced by
	\begin{enumerate}
	\item[] $(e_1,\dots, e_{r},0,e_{r}-e_{r-1},\dots, e_r-e_1)$ if $m=2r$,
	\item[] $(e_1,\dots, e_r,0, -e_{r},\dots, -e_{1})$ if $m=2r+1$,
\end{enumerate}
where $e_i$ is the tuple in $\mathbb{Z}^{\lfloor \frac{m}{2} \rfloor}$ with $i$-th entry equal to $1$ and remaining entries equal to $0$, is called the finest grading on $UT_m(F)$.
\end{definition}

Next we prove that any grading on $UT_m(F)$ that admits a graded involution is isomorphic to a coarsening of the finest grading on this algebra.

\begin{proposition}\label{coarsening}
	Let $A$ be a grading by a group $G$ on $UT_m(F)$. If $A$ admits a graded involution $\circ$ then there exists a homomorphism of groups $\alpha:\mathbb{Z}^{\lfloor \frac{m}{2} \rfloor}\rightarrow G$ such that $(A,\circ)$ is isomorphic to the grading induced by $\alpha$ from the finest grading on $UT_m(F)$ with the reflection or symplectic involution.
\end{proposition}
\begin{proof}
Theorem \ref{elgr} implies that there exists a tuple ${\bf g}=(g_1,\dots, g_m)$ such that $A$ is isomorphic to the elementary grading on $UT_m(F)$ induced by ${\bf g}$. Hence we may assume without loss of generality that $A$ has the elementary $G$-grading induced by ${\bf g}$. For every $g\in G$ the tuple $(g_1g,\dots, g_mg)$ induces the same the elementary grading, hence we may assume without loss of generality that $g_{r+1}=e$, where $r=\lfloor \frac{m}{2} \rfloor$. Let $\overline{F}$ be the algebraic closure of $F$. The extension of $\circ$ to $UT_m(\overline{F})$ is a graded involution on this algebra with the elementary grading induced by ${\bf g}$. Corollary \ref{classf} implies that $g_1g_m=g_2g_{m-1}=\cdots=g_mg_1$. Hence the reflection involution $\ast$ is a graded involution on $A$. The map $a\mapsto (a^{\ast})^{\circ}$ is an automorphism of $A$ as a graded algebra. Then there exists a homogeneous invertible matrix $u\in A$ such that $(a^{\ast})^{\circ}=uau^{-1}$ (see \cite[Lemma 24]{FGDY}). Since $u$ is invertible the entries in the diagonal of $u$ are non-zero, hence $u$ is homogeneous of degree $e$. We have $a^{\circ}=ua^{\ast}u^{-1}$, since $\circ$ is an involution it follows that $u^{\ast}=\pm u$. Let $D$ be the matrix in (\ref{D}). \cite[Lemma 24]{DKV} implies that there exists a matrix $c\in UT_m(F)$ such that $u=cc^{\ast}$ if $u^{\ast}=u$ and $u^{\prime}=cc^{s}$, where $u^{\prime}=uD$, if $u^{\ast}=-u$. Since $u$ is homogeneous of degree $e$ it follows from the proof of \cite[Lemma 24]{DKV} that $c$ is homogeneous of degree $e$. The map $\psi(a)=c^{-1}a c$ is an isomorphism of $(G,\ast)$-algebras from $(A,\circ)$ to $(A,\ast)$ if $u^{\ast}=u$ and from $(A,\circ)$ to $(A,s)$ if $u^{\ast}=-u$.

Since $g_{r+1}=e$ the elements $g_1,\dots, g_m$ lie in the support of the grading. Therefore Corollary \ref{classf} implies that the subgroup generated by $g_1,\dots, g_m$ is abelian. Let $\alpha:\mathbb{Z}^{\lfloor \frac{m}{2} \rfloor}\rightarrow G$ be the map such that $\alpha(e_i)=g_i$ for $i=1,\dots, r$. The grading induced by $\alpha$ on the finest grading on $UT_m(F)$ is the elementary grading determined by ${\bf g}$.
\end{proof}

\begin{lemma}\label{l2}
	Let $G=\mathbb{Z}^{\lfloor \frac{m}{2} \rfloor}$. If $UT_m(F)$ has the finest grading then $\mathrm{deg}_G\, e_{i,j}=\mathrm{deg}_G\, e_{k,l}\neq e$ if and only if $e_{i,j}=e_{k,l}$ or $e_{i,j}^{\ast}=e_{k,l}$.
\end{lemma}
\begin{proof}
	Let us assume that
	\begin{align}\label{eqdeg}
	\mathrm{deg}_G\, e_{i,j}=\mathrm{deg}_G\, e_{k,l}\neq e.
	\end{align}
	We prove the result for $\mathcal{U}=UT_{2r}$, the proof for $UT_{2r+1}$ is analogous. We consider the following sets of elementary matrices: $E_I=\{e_{uv}\mid u,v\leq r\}$; $E_{II}=\{e_{uv}\mid u\leq r, v>r\}$; $E_{III}=\{e_{uv}\mid u,v>r\}$. Note that
	\begin{enumerate}
		\item If $e_{i,j}\in E_{I}$ then $\mathrm{deg}\, e_{i,j}=e_{i}-e_j$;
		\item If $e_{i,j}\in E_{II}$ then $\mathrm{deg}\, e_{i,j}=e_i+e_{2r+1-j}-e_{r}$;
		\item If $e_{i,j}\in E_{III}$ then $\mathrm{deg}\, e_{i,j}=e_{2r+1-j}-e_{2r+1-i}$.
	\end{enumerate}
	If $e_{i,j}\in E_{I}$ then (\ref{eqdeg}) implies that $e_{k,l}\in E_{I}\cup E_{III}$. If $e_{k,l}\in E_{I}$ then (\ref{eqdeg}) implies that $e_i-e_j=e_k-e_l$, therefore $e_{i,j}=e_{k,l}$. If $e_{k,l}\in E_{III}$ then $e_{i}-e_j=e_{2r+1-l}-e_{2r+1-k}$, hence $i=2r+1-l$ and $j=2r+1-k$. In this case $e_{k,l}=e_{i,j}^{\ast}$. Analogously if $e_{ij}\in E_{III}$ we conclude that $e_{kl}=e_{ij}$ or $e_{kl}=e_{ij}^{\ast}$. Now assume that $e_{i,j}\in E_{II}$, then $e_{k,l}\in E_{II}$. Hence (\ref{eqdeg}) implies that $e_i+e_{2r+1-j}-e_{r}=e_{k}+e_{2r+1-l}-e_{r}$. We have two possibilities: $i=k$ and $2r+1-j=2r+1-l$ or $i=2r+1-l$ and $2r+1-j=k$. In the first case $e_{i,j}=e_{k,l}$ and in the second case $e_{k,l}=e_{i,j}^{\ast}$.
\end{proof}

Now assume that $UT_m(F)$ has the finest grading. The neutral component is the subspace of the diagonal matrices, hence
\begin{align}\label{i1}
[x_{1,\epsilon},x_{2,\epsilon}],
\end{align}
is a $(\mathbb{Z}^{\lfloor \frac{m}{2} \rfloor},\ast)$-identity for $UT_m(F)$. We consider the following polynomials
\begin{align}\label{i2}
x_{1,g}^{\ast}-x_{1,g}, \mbox{ where } \mathrm{dim}\, (UT_m(F))_g=1,
\end{align}
and for $m=2r+1$ the polynomials
\begin{align}\label{i3}
x_{1,g}x_{2,e}x_{3,h}-x_{1,g}x_{2,e}^{\ast}x_{3,h},\mbox{ where }g=e_i, h=e_{2r+2-j}, i<r+1<j
\end{align}
and
\begin{align}\label{i4}
	x_{1,\epsilon}x_{2,g}x_{3,\epsilon}-x_{1,\epsilon}^{\ast}x_{2,g}x_{3,\epsilon}-	x_{1,\epsilon}x_{2,g}x_{3,\epsilon}^{\ast}+	x_{1,\epsilon}^{\ast}x_{2,g}x_{3,\epsilon}^{\ast},\mbox{ where }g=e_i, 1\leq i \leq r.
\end{align}
\begin{proposition}\label{id}
	The polynomials (\ref{i1}), (\ref{i2}), (\ref{i3}) and (\ref{i4}) are $(\mathbb{Z}^{\lfloor \frac{m}{2} \rfloor},\ast)$-identities for $UT_m(F)$ with the finest grading and the reflection involution.
\end{proposition}
\begin{proof}
The proof is an easy verification that the result of every elementary substitution is zero, so we omit it.
\end{proof}

\begin{lemma}\label{one}
	If $M=x_{u_1,g_1}^{\delta_1}\cdots x_{u_n,g_n}^{\delta_{n}}$, where $g_i\neq e$ for $i=1,\dots,n$, is not a $(G,\ast)$-identity for $UT_m(F)$ and $n>1$ then there exists only one elementary substitution $S$ such that $M_S\neq 0$.
\end{lemma}
\begin{proof}
	Let $S=(e_{i_1,j_1},\dots, e_{i_n,j_n})$ be an elementary substitution for $x_{u_1,g_1}\cdots x_{u_n,g_n}$. Note that $$(x_{u_1,g_1}\cdots x_{u_n,g_n})_S=M_{S^{\prime}},$$ where $S^{\prime}=(e_{i_1,j_1}^{\delta_1},\dots, e_{i_n,j_n}^{\delta_n})$. Hence we may assume without loss of generality that $M=x_{u_1,g_1}\cdots x_{u_n,g_n}$. Let $S_1,S_2$ be elementary substitutions such that $(x_1\cdots x_n)_{S_i}\neq 0$, $i=1,2$ and $S_1\neq S_2$. Let $t$ be the smallest index such that $e_{i,j}:=(x_{u_t,g_t})_{S_1}\neq (x_{u_t,g_t})_{S_2}:=e_{r,s}$. Lemma \ref{l2} implies that $e_{r,s}=e_{i,j}^{\ast}$. If $t>1$ then $M_{S_1}\neq 0$ implies that $(x_{u_{t-1},g_{t-1}})_{S_1}=e_{ui}$ for some index $u$. Moreover since $t$ is minimal we conclude that $(x_{u_{t-1},g_{t-1}})_{S_2}=e_{ui}$. Hence $M_{S_2}\neq 0$ implies that $e_{ui}e_{ij}^{\ast}\neq 0$. Therefore $m+1-j=i$, in this case $e_{rs}=e_{ij}^{\ast}=e_{ij}$, which is a contradiction since $e_{i,j}\neq e_{r,s}$. Now assume that $t=1$. If $(x_{u_2,g_2})_{S_1}=(x_{u_2,g_2})_{S_2}$ then an analogous argument to the one above implies that $e_{rs}=e_{ij}^{\ast}=e_{ij}$, which is a contradiction. Otherwise let $e_{ju}=(x_{u_2,g_2})_{S_1}$. Lemma \ref{l2} implies that $(x_{u_2,g_2})_{S_2}=e_{ju}^{\ast}$. Since $M_{S_2}\neq 0$ we conclude that
	\begin{align*}
	e_{ij}^{\ast}e_{ju}^{\ast}\neq 0.
	\end{align*}
	Therefore $m+1-i=m+1-u$, which implies that $i=u$. This is a contradiction since $i<j<u$.
\end{proof}

\begin{definition}\label{defgood}
Let $G=\mathbb{Z}^{\lfloor \frac{m}{2} \rfloor}$ and let $\mathcal{U}$ be the algebra $UT_m(F)$ with the finest grading. Let
\begin{align}\label{good}
M=M_1x_{u_1,g_1}^{\delta_1}M_2x_{u_2,g_2}^{\delta_2}\cdots M_kx_{u_k,g_k}^{\delta_k}M_{k+1},
\end{align}
be a monomial in $P_n^{G,\ast}$, where $g_1,\dots,g_k\neq e$ and
\begin{align*}
M_i=x_{k_{i,1},e}^{\delta_{i,1}}\cdots x_{k_{i,s_i},e}^{\delta_{i,s_i}}.
\end{align*}
We say that $M$ is good if it lies in $P_n^{G,\ast}$, $M$ is not a $(G,\ast)$-identity for $\mathcal{U}$ and moreover,
\begin{enumerate}
	\item[I] $k_{i,1}<\cdots < k_{i,s_i}$;
	\item[II] If $\mathrm{dim}\, \mathcal{U}_{g_i}=1$ then $\delta_i=\emptyset$ and $M_i=1$;
	\item[III]  If $\mathrm{dim}\, \mathcal{U}_g=1$ for $g=g_ig_{i+1}\cdots g_j$ for $i< j$ then $M_i=1$ and $u_i<u_j$;
	\item[IV] If $m=2r+1$, $g_i=e_p, g_{i+1}=e_{2r+2-q}, p<r+1<q$ then ${\delta_{i+1,1}}=\dots={\delta_{i+1,s_{i+1}}}=\emptyset$;
	\item[V] If $m=2r+1$, $k=1$ and $g_1=e_i$, for some $i\in \{1,\dots, r\}$ then $\delta_{1,1}=\dots = \delta_{1,s_1}=\emptyset$ or 	$\delta_{2,1}=\dots = \delta_{2,s_2}=\emptyset$.
\end{enumerate}
\end{definition}

\begin{lemma}\label{genpn}
	Let $G=\mathbb{Z}^{\lfloor \frac{m}{2} \rfloor}$. The set of good monomials of degree $n$ generates the vector space $P_n^{G,\ast}$ modulo the $T_{G,\ast}$-ideal generated by the identities (\ref{i1}), (\ref{i2}), (\ref{i3}) and (\ref{i4}) and the monomials in $T_{G,\ast}(UT_m(F))$.
\end{lemma}
\begin{proof}
	Let $J$ be the $T_{G,\ast}$-ideal generated by the identities (\ref{i1})-(\ref{i4}) together with the monomials in $T_{G,\ast}(UT_m(F))$ and let $M$ be a monomial in $P_n^{G,\ast}\setminus T_{G,\ast}(UT_m)$. A monomial $M$ in $P_n^{G,\ast}$ may be written as in (\ref{good}). We use (\ref{i1}) to write $M$ modulo $J$ as a monomial that satisfies (I). If $\mathrm{dim}\, \mathcal{U}_{g_i}=1$ then $x_{u_i,g_i}^{\ast}- x_{u_i,g_i}$ is an identity for $UT_m(F)$ then we replace $x_{u_i,g_i}^{\ast}$ by $x_{u_i,g_i}$, if necessary, and obtain a monomial that is congruent modulo $J$ to $M$, and that satisfies (I) and (II). Now assume that $\mathrm{dim}\, \mathcal{U}_g=1$ for $g=g_ig_{i+1}\cdots g_j$ for $i< j$, in this case $x_{1,g}^{\ast}-x_{1,g}\in T_{G,\ast}(UT_m(F))$. Then
	\begin{align*}
	M_ix_{u_i,g_i}^{\delta_i}\cdots M_jx_{u_j,g_j}^{\delta_j}\equiv_J(x_{u_j,g_j}^{\delta_j})^{\ast}M_j^{\ast}\cdots (x_{u_i,g_i}^{\delta_i})^{\ast}M_i^{\ast}\equiv_Jx_{u_i,g_i}^{\delta_i}\cdots M_jx_{u_j,g_j}^{\delta_j}M_{i}^{\ast},
	\end{align*}
	therefore $M$ is congruent modulo $J$ to a monomial that satisfies $(I)-(III)$. Now assume that $m=2r+1$, $g_i=e_p, g_{i+1}=e_{2r+2-q}, p<r+1<q$. Then the polynomial
	\begin{align*}
	x_{1,g_i}x_{2,e}x_{3,g_{i+1}}-x_{1,g_i}x_{2,e}^{\ast}x_{3,g_{i+1}}
	\end{align*}
	is a $(G,\ast)$-identity for $UT_m(F)$ in (\ref{i3}). Hence if $\delta_{i,l}=\ast$ we have
	\begin{align*}
	x_{u_i,g_i}^{\delta_i}x_{k_{i,1},\epsilon}^{\delta_{i,1}}\cdots x_{k_{i,l},\epsilon}^{\ast}\cdots x_{k_{i,s_i},\epsilon}^{\delta_{i,s_i}} x_{u_{i+1},g_{i+1}}^{\delta_{i+1}}\equiv_J x_{u_i,g_i}^{\delta_i}x_{k_{i,1},\epsilon}^{\delta_{i,1}}\cdots x_{k_{i,l},\epsilon}\cdots x_{k_{i,s_i},\epsilon}^{\delta_{i,s_i}} x_{u_{i+1},g_{i+1}}^{\delta_{i+1}},
	\end{align*}
	hence $x_{u_i,g_i}^{\delta_i}M_i x_{u_{i+1},g_{i+1}}^{\delta_{i+1}}\equiv_J x_{u_i,g_i}^{\delta_i}x_{k_{i,1},\epsilon}\cdots x_{k_{i,s_i},\epsilon} x_{u_{i+1},g_{i+1}}^{\delta_{i+1}}$. Therefore $M$ is congruent modulo $J$ to a monomial that satisfies $(I)-(IV)$. This monomial is good unless $m=2r+1$, $k=1$ and $g_1=e_i$, for some $i\in \{1,\dots, r\}$. Now assume that this is the case, it follows from identities (\ref{i1}) and (\ref{i4}) that $M$ is congruent modulo $J$ to a monomial that satisfies $(I)-(V)$, i.e., $M$ is congruent modulo $J$ to a linear combination of good monomials.
\end{proof}

\begin{remark}\label{k}
	Note that if $g_1,\dots, g_m\in G\setminus\{e\}$ then the result of a substitution in $N=x_{1,g_1}^{\delta_1}\cdots x_{m,g_m}^{\delta_m}$ is the product of $m$ strictly upper triangular matrices and equals zero. Therefore the monomial $N$ is an identity for $UT_m(F)$ with the finest grading. Hence we conclude that if $N\notin T_{G,\ast}(UT_m(F))$ then $k\leq m-1$.
\end{remark}

\begin{theorem}\label{mainfine}
	Let $G=\mathbb{Z}^{\lfloor \frac{m}{2} \rfloor}$. The polynomials (\ref{i1}), (\ref{i2}), (\ref{i3}) and (\ref{i4}) together with a finite number of monomial identities form a basis for the $(G,\ast)$-identities for $UT_m(F)$ with the finest grading and refletion involuton. Moreover the images of the good monomials of degree $n$, under the canonical quotient map, form a basis for $P_n^{G,\ast}/P_n^{G,\ast}\cap T_{G,\ast}(UT_m)$.
\end{theorem}
\begin{proof}
	Let $J$ be the $T_{G,\ast}$-ideal generated by the identities (\ref{i1}), (\ref{i2}), (\ref{i3}) and (\ref{i4}) and the monomials
	\begin{align}\label{monj}
	x_{1,g_1}\cdots x_{k,g_k},
	\end{align}
	in $T_{G,\ast}(UT_m)$ with $g_i\neq e$ for $i=1,\dots,k$ and $k\leq m$. Proposition \ref{id} implies that $J\subseteq T_{G,\ast}(UT_m(F))$. Remark \ref{k} implies that every monomial in $T_G(UT_m(F))$ lies in $J$. It remains to prove the reverse inclusion. We prove that the good monomials are linearly independent modulo $T_{G,\ast}(UT_m(F))$.	Let $T=\{x_{1,h_1},\dots, x_{n,h_n}\mid h_1,\dots, h_n\in G\}$ be a set of indeterminates. Let $\mathcal{M}(T)$ be the set of good monomials in the inteterminates in $T$.  We prove that $\mathcal{M}(T)$ is linearly independent modulo $T_{G,\ast}(UT_m(F))$, this implies that the good monomials are independent modulo $T_{G,\ast}(UT_m(F))$. Let $k$ be the number of indices $i$ such that $h_i\neq e$. Let $M,M^{\prime}\in \mathcal{M}(T)$. If $k>1$ then Lemma \ref{one} and the conditions $(I)-(IV)$ in Definition \ref{defgood} imply that if $S$ is an elementary substitution such that $(M)_S=(M^{\prime})_S\neq 0$ then $M=M^{\prime}$, hence the  $\mathcal{M}(T)$ is linearly independent modulo $T_{G,\ast}(UT_m)$ in this case. Now assume that $k=1$. If $m=2r$ or $m=2r+1$ and $\mathrm{deg}_G\, M, \mathrm{deg}_G\, M^{\prime}\notin\{e_j\mid j=1,\dots, r\}$ then $(M)_S=(M^{\prime})_S\neq 0$, for an elementary substitution $S$, also implies that $M=M^{\prime}$. Now assume that  $m=2r+1$ and $\mathrm{deg}_G\, M, \mathrm{deg}_G\, M^{\prime}\in\{e_j\mid j=1,\dots, r\}$. Let
	\begin{align*}
	M=x_{k_{1,1},\epsilon}^{\delta_{1,1}}\cdots x_{k_{1,s_1},\epsilon}^{\delta_{1,s_1}}x_{u_1,g_1}^{\delta_1}x_{k_{2,1},\epsilon}^{\delta_{2,1}}\cdots x_{k_{2,s_2},\epsilon}^{\delta_{2,s_2}}.
	\end{align*}
	Note that if $\delta_{i,j}=\ast$ for some $i,j$ then there exists an elementary substitution $S$ such that $(M)_S\neq 0$ and $(M)_S=(M^{\prime})_S$ implies that $M=M^{\prime}$. Indeed, assume first that $i=1$. We have $g_1=\mathrm{deg}_G\, M=e_{i}$ for some $i\in \{1,\dots,r\}$. Since $m=2r+1$ the degree of $e_{i,r+1}$ is $e_i$. We consider the substitution $S$ such that
	\begin{align*}
	&(x_{u_1,g_1}^{\delta_1})_S=e_{i,r+1},\\ &(x_{k_{1,j},\epsilon}^{\delta_{1,j}})_S=e_{ii}\mbox{ for }j=1,\dots s_1,\\ &(x_{k_{2,j^{\prime}},\epsilon}^{\delta_{2,j^{\prime}}})_S=e_{r+1,r+1}\mbox{ for }j^{\prime}=1,\dots s_2.
	\end{align*}
	Conditions $(I)$ and $(V)$ from Definition \ref{defgood} imply that if $M^{\prime}$ is a good monomial in $\mathcal{M}(T)$ and $(M)_S=(M^{\prime})_S$ then $M=M^{\prime}$. The proof for $i=2$ is analogous. As a consequence $\mathcal{M}(T)$ is linearly independent modulo $T_{G,\ast}(UT_m)$ in this case.
	Now let $f$ be a multilinear polynomial in $P_n^{G,\ast}\cap T_{G,\ast}(UT_m(F))$. We may write $f$ modulo $J$ to a linear combination
	\begin{align*}
	\sum_{i=1}^{t} \lambda_i M_i,
	\end{align*}
	of good monomials $M_1,\dots, M_t$ in $\mathcal{M}(T)$ for some set of indeterminates $T$. Since $\mathcal{M}(T)$ is linearly independent modulo $T_{G,\ast}(UT_m(F))$ we conclude that $\lambda_1=\dots=\lambda_l=0$. Therefore $f\in J$. Since the field is of characteristic zero this implies that $T_{G,\ast}(UT_m(F))\subseteq J$.
\end{proof}

\begin{remark}
	Let $G=\mathbb{Z}^{r}$ and let $\mathcal{U}$ be the finest $G$-grading on $UT_{2r}(F)$. If $\mathrm{dim}\, \mathcal{U}_g=1$ then there exist $1\leq i,j\leq 2r$ with $i+j=m+1$ such that $\mathcal{U}_g=\mathrm{span}\, \{e_{i,j}\}$. Note that in this case $i\leq r<j$, hence $e_{i,j}^{s}=-e_{i,j}$. Therefore $x_{1,g}^{\ast}+x_{1,g}$ is a $(G,\ast)$-identity for $\mathcal{U}$ with the symplectic involution.
\end{remark}

An adaptation of the argument above proves the following result.

\begin{theorem}
Let $G=\mathbb{Z}^{r}$ and let $\mathcal{U}$ be the finest $G$-grading on $UT_{2r}(F)$. The $(G,\ast)$-identities of the algebra $UT_{2r}(F)$ with the finest grading and symplectic involution follow from the identities
\begin{align}
&[x_{1,e},x_{2,e}],\\
&x_{1,g}^{\ast}+x_{1,g},\,  \mathrm{dim}\, \mathcal{U}_g=1,
\end{align}
and a finite number of monomial identities. Moreover the the images of the good monomials of degree $n$, under the canonical quotient map, form a basis for $P_n^{G,\ast}/P_n^{G,\ast}\cap T_{G,\ast}(UT_m)$.
\end{theorem}

We now determine the asymtotic growth for the $(G,\ast)$-codimensions of $UT_m(F)$ with the finest grading and reflection involution.

\begin{lemma}\label{parttuple}
	Let $S$ be a set with $n$ elements and let $t$ be a positive integer. The number of tuples $(S_1,\dots, S_t)$ such that $S_i\subseteq S$ for $i=1,\dots, t$, $S_i\cap S_j=\emptyset$ whenever $i\neq j$ and $\cup_{i=1}^t S_i=S$ is $t^n$.
\end{lemma}
\begin{proof}
For a tuple $T=(S_1,\dots, S_t)$ as above let $f_T:S\rightarrow \{1,\cdots,t\}$ be the map such that $S_i=f_T^{-1}(i)$, for $i=1,\dots, t$. Note that $T\mapsto f_T$ is a bijection from the set of tuples to the set of maps from $S$ to $\{1,\dots, t\}$. The number of maps from $S$ to $\{1,\dots, t\}$ is $t^n$, therefore the number of tuples is $t^n$.
\end{proof}

\begin{theorem}\label{expo}
	For $UT_m(F)$, $m>1$, with the finest grading and reflection involution $\ast$ there exists a constant $C$ such that we have
	\begin{align*}
	c_n^{G,\ast}(UT_m(F))\sim\left\{ \begin{array}{l}
	 Cn^{m-1}(m+1)^n , \mbox{ if }m\mbox{ is odd},\\
	 Cn^{m-1}m^n , \mbox{ if }m\mbox{ is even}.
	\end{array}\right.
	\end{align*}
	In particular,
	\begin{align*}
	\mathrm{exp}^{G,\ast}(UT_m(F))= \left\{ \begin{array}{l}
	m+1, \mbox{ if } m \mbox{ is odd }\\
	m, \mbox{ if } m \mbox{ is even }.
	\end{array}\right.
	\end{align*}
\end{theorem}
\begin{proof}
Theorem \ref{mainfine} implies that $c_n^{G,\ast}(UT_m(F))$ is the number of good monomials in $P_n^{G,\ast}$. Let $N_k(n)$ be the number of good monomials in $P_n^{G,\ast}$ in $k$ indeterminates of degree different form $e$, then
\begin{align*}
c_n^{G,\ast}(UT_m(F))=N_0(n)+\cdots+N_{m-1}(n)
\end{align*}
We prove first that if $k<m-1$ then $N_k(n)=o(n^{m-1}(m+1)^n)$ for odd $m$ and $N_k(n)=o(n^{m-1}m^n)$ for even $m$.
Let
\begin{align}\label{goodnk}
M_1x_{u_1,g_1}^{\delta_1}M_2x_{u_2,g_2}^{\delta_2}\cdots M_kx_{u_k,g_k}^{\delta_k}M_{k+1},
\end{align}
be a good monomial in $P_n^{G,\ast}$, here $g_1,\dots,g_k\neq e$ and
\begin{align*}
M_i=x_{k_{i,1},e}^{\delta_{i,1}}\cdots x_{k_{i,s_i},e}^{\delta_{i,s_i}}.
\end{align*}
Note that the number of elements in the support of the grading is $<\mathrm{dim}\, UT_m(F)=\frac{m^2+m}{2}$. Hence the number of choices for the indices $g_1,\dots, g_k$ is at most $\left(\frac{m^2+m}{2}\right)^k$. The number of choices for the indices $u_1,\dots, u_k$ is at most $k!{n\choose k}$. Lemma \ref{one} implies that there exists a unique elementary substitution $S$ such that
\begin{align}\label{subss}
0\neq \left(x_{u_1,g_1}^{\delta_1}x_{u_2,g_2}^{\delta_2}\cdots x_{u_k,g_k}^{\delta_k}\right)_S=e_{i_1,i_2}e_{i_2i_3}\cdots e_{i_k,i_{k+1}}.
\end{align}
Let $t$ be the number of pairs $a<b$ such that $i_a+i_b=m+1$. Conditions (II) and (III) imply that if $a<b$ is a pair such that such that $i_a+i_b=m+1$ then $M_{a}=1$, hence there exists $t$ indices $l$ such that $M_l=1$. Let $j_1,\dots, j_{k+1-t}$ be the remaining indices. Lemma \ref{parttuple} implies that the number of choices for the indices $k_{i,j}$ of the indeterminates in the monomials $M_{j_1},\dots, M_{j_{k+1-t}}$ is $(k+1-t)^{n-k}$, moreover the number of choices for the $,\delta_j,\delta_{j_l,1}$ is at most $2^{n}$, therefore
\begin{align}\label{desig}
N_k(n)\leq \left(\frac{m^2+m}{2}\right)^kk!{n \choose k}(k+1-t)^{n-k}2^n.
\end{align}
We claim that $k+1-t\leq \frac{m+1}{2}$ if $m$ is odd and $k+1-t\leq \frac{m}{2}$ if $m$ is even. Let ${\bf i}$ be the sequence $1\leq i_1<\cdots<i_{k+1}\leq m$ and let $w({\bf i}):=k+1-t$ be the weight of ${\bf i}$. Note that if ${\bf i}^{\prime}$ is a sequence obtained from ${\bf i}$ by adding one entry then $w({\bf i})\leq w({\bf i}^{\prime})$, hence the greatest value of the weight coresponds to the sequence $1<2<\cdots<m$, this proves the claim. Note that $k!{n\choose k}<n^k$, then for odd $m$ as a consequence of (\ref{desig}) we have
\begin{align*}
N_k(n)< \left(\frac{m^2+m}{2}\right)^kn^{k}\left(m+1\right)^n.
\end{align*}
Since $k<m-1$ we have
\begin{align*}
\lim_{n\to\infty}\frac{N_k(n)}{n^{m-1}(m+1)^n}=0,
\end{align*}
i.e. $N_k(n)=o(n^{m-1}(m+1)^n)$ for odd $m$.
We prove analogously that $N_m(n)=o(n^{m-1}m^n)$ for even $m$.

Now we determine $N_{m-1}(n)$. Note that for $k=m-1$ it follows from (\ref{subss}) that $i_l=l$ for $l=1,\dots, m-1$. Hence $g_i$ is the degree of $e_{i,i+1}$. If $m=2r+1$ then $M_1=\cdots=M_r=1$ and the indeterminates in $M_{r+1}$ have no $\ast$. The total number of good monomials in this case is
\begin{align*}
&(m-1)!{n\choose m-1}2^{m-1}(r+1)^{n-m+1}\left(\sum_{s_{r+1}=0}^{n-m+1}2^{n-m+1-s_{r+1}}\right)=\\&(m-1)!{n\choose m-1}2^{m-1}(r+1)^{n-m+1}\left(2^{n-m+2}-1\right)\sim 2\left(\frac{m+1}{2}\right)^{-m+1}n^{m-1}(m+1)^n.
\end{align*}
If $m=2r$ then $M_1=\cdots=M_r=1$, $\delta_r=\emptyset$, hence the total number in this case is
\begin{align*}
(m-1)!{n\choose m-1}2^{m-2}r^{n-m+1}2^{n-m+1}\sim 2^{-1}r^{-m+1}n^{m-1}m^{n}.
\end{align*}
Hence we conclude that there
\begin{align*}
c_n^{G,\ast}(UT_m(F))\sim\left\{ \begin{array}{l}
Cn^{m-1}(m+1)^n , \mbox{ if }m\mbox{ is odd},\\
Cn^{m-1}m^n , \mbox{ if }m\mbox{ is even},
\end{array}\right.
\end{align*}
where $C=2\left(\frac{m+1}{2}\right)^{-m+1}$ if $m$ is odd and $C=2^{-1}r^{-m+1}$ if $m=2r$.

The conclusion about the $(G,\ast)$-exponent of $UT_m(F)$ is a direct consequence the above.
\end{proof}

An adaptation of the proof of the theorem aboves yields the following result.

\begin{theorem}\label{expo1}
	For $UT_{2r}(F)$, with the finest grading and symplectic involution $s$ we have
	\begin{align*}
	c_n^{G,\ast}(UT_{2r}(F))\sim Cn^{2r-1}(2r)^n
	\end{align*}
	In particular,
	\begin{align*}
	\mathrm{exp}^{G,\ast}(UT_{2r}(F))= 2r
	\end{align*}
\end{theorem}

As a consequence of Proposition \ref{coars}, Theorem \ref{expo} and Theorem \ref{expo1} we obtain the following result.

\begin{corollary}
	For an arbitrary $G$-grading on $UT_m(F)$ and graded involution $\ast$ we have $\mathrm{exp}^{G,\ast}(UT_m)=m$ if $m$ is even and $\mathrm{exp}^{G,\ast}(UT_m)=m+1$ or $\mathrm{exp}^{G,\ast}(UT_m)=m$ if $m$ is odd.
\end{corollary}

\section{Graded Identities with Involution for $UT_3(F)$}\label{s3}
In this section we describe the gradings on $UT_3(F)$ that admit graded involution. If the group $G$ does not have elements of order $2$ then the only two possible gradings (up to equivalence) are the trivial grading and the grading in the previous section. If $G$ has elements of order $2$ then it admits $G$-gradings equivalent to the $\mathbb{Z}_2$-grading on $UT_3(F)$ induced by $(0,1,0)$. Such gradings admit as a graded involution, up to equivalence, the reflection involution. We describe the $\mathbb{Z}_2$-graded identities with involution in this case.

Let $Y^{+}=\{y_1^{+},y_2^{+},\dots\}$, $Y^{-}=\{y_1^{-},y_2^{-},\dots\}$, $Z^{+}=\{z_1^{+},z_2^{+},\dots\}$ and $Z^{-}=\{z_1^{-},z_2^{-},\dots\}$ be four infinite countable and pairwise disjoint sets and let $Y=Y^{+}\cup Y^{-}$, $Z=Z^{+}\cup Z^{-}$. Let $F\langle Y\cup Z, \ast \rangle$ be the free algebra freely
generated by $Y\cup Z$ with the $\mathbb{Z}_2$-grading such  that the indeterminates in $Y$ have degree $0$ and the indeterminates in $Z$ have degree $1$ and involution $\ast$ such that the indeterminates in $Y^{+}, Z^{+}$ are symmetric and the indeterminates in $Y^{-},Z^{-}$ are skew-symmetric. Then $F\langle Y\cup Z, \ast \rangle$ is the free $\mathbb{Z}_2$-graded algebra with graded involution $\ast$.

Henceforth the commutators of higher order are left-normed, i.e., if $a_1,\dots, a_n$ are elements of an associative algebra then $[a_1,\dots, a_n]:=[[a_1,\dots, a_{n-1}], a_n]$ for $n\geq 3$.  A polynomial in $F\langle Y\cup Z, \ast \rangle$ is $Y^{+}$-proper if it is a linear combination of polynomials of the form
\begin{align*}
(y_1^{-})^{q_1}\cdots (y_b^{-})^{q_b}(z_1^{+})^{r_1}\cdots (z_c^{+})^{r_c}(z_1^{-})^{s_1}\cdots (z_d^{-})^{s_d}u_1^{t_1}\cdots u_e^{t_e},
\end{align*}
where $q_i,r_i,s_i,t_i$ are non-negative integers and $u_1,\dots, u_n$ are left-normed commutators (of degree $\geq 2$) of indeterminates in $Y\cup Z$. Let $\Gamma$ be the subspace of $F\langle Y\cup Z, \ast \rangle$ of $Y^{+}$-proper polynomials. As in the case of (ungraded) algebras with involution, since $\mathrm{char}\, F=0$, any $T_{\mathbb{Z}_2,\ast}$-ideal is generated by its $Y^{+}$-proper multilinear polynomials, the proof follows closely the one for algebras with involution (see \cite[Lemma 2.1]{DG}) so we omit it.
We recall that $P_n^{\mathbb{Z}_2,\ast}$ is the subspace of $F\langle Y\cup Z\rangle$ of the multilinear polynomials of degree $n$ in the indeterminates in $Y\cup Z$ such that in each monomial the index $i$ appears once for $i=1,\dots,n$, we also define $\Gamma_n=\Gamma \cap P_n^{\mathbb{Z}_2,\ast}$.
 Let $A$ be a $\mathbb{Z}_2$-graded algebra with graded involution. We define $\Gamma_n(A)=\Gamma_n/\Gamma_n\cap T_{\mathbb{Z}_2,\ast}(A)$, the $n$-th $Y^{+}$-proper codimension of $A$ is $\mathrm{dim}\, \Gamma_n(A)$ and is denoted by $\gamma_n^{\mathbb{Z}_2,\ast}(A)$. In the next result we provide a relation between the proper and ordinary codimensions of $A$. The proof follows closely the one in the case of (ungraded) algebras with involution (see \cite[Theorem 2.3]{DG}) so we omit it.

\begin{proposition}\label{codim}
	Let $A$ be a $\mathbb{Z}_2$-graded algebra with graded involution $\ast$. The codimension sequence $c_n^{\mathbb{Z}_2,\ast}(A)$ and the proper codimension sequence $\gamma_n^{\mathbb{Z}_2,\ast}(A)$ are related by the following equalities
	\begin{align*}
	c_n^{\mathbb{Z}_2,\ast}(A)=\sum_{i=0}^{n}{n\choose i}\gamma_n^{\mathbb{Z}_2,\ast}(A).
	\end{align*}
\end{proposition}

In this section we consider $\mathcal{U}=UT_3(F)$ with the $\mathbb{Z}_2$-grading induced by $(0,1,0)$ and the reflection involution. Then
\begin{align*}
&\mathcal{U}_0^{+}=\langle e_{11}+e_{33}, e_{22}, e_{13}\rangle,\ \ \mathcal{U}_0^{-}=\langle e_{11}-e_{33} \rangle\\
&\mathcal{U}_1^{+}=\langle e_{12}+e_{23}\rangle,\ \ \mathcal{U}_1^{-}=\langle e_{12}-e_{23}\rangle.
\end{align*}

\begin{lemma}\label{ids}
	The polynomials
	\begin{align}
	&x_1x_2x_3-x_3x_2x_1, x_1,x_3 \in Y^{-}, Z^{+}, Z^{-}\label{1}\\
	&z_1z_2z_3\label{2}\\
	 &[x_1,x_2],x_1,x_2\in Y^{+},Y^{-}, Z^{+}, Z^{-}\label{3}\\
	 &[y_1^{+},y_2^{-}][x_3,x_4]\label{4}\\

	 &[y_1^{+},z_1z_2]\label{6}\\
	 &[y_1^+,y_2^-]z_3, z_3[y_1^+,y_2^-]\label{7}\\%\\

	 & [y_1^{+},y_2^{-}]y_3^{-}+y_3^{-}[y_1^{+},y_2^{-}]\label{9}\\
	 & y_1^{-}z_1y_2^{-}\label{10}\\
	 & z_1y_1^{-}z_2\label{11}\\
	 & z_1^{+}z_2^{-}+z_{2}^{-}z_1^{+}\label{12}\\
	 & z_1z_2y_1^{-}+y_1^{-}z_1z_2\label{13}\\
	 & [z_1,y_1^{+}]z_2+ z_1[z_2,y_1^{+}], \label{14}
	\end{align}
	are graded identities with involution for $UT_3(F)$.
\end{lemma}
\begin{proof}
The proof is an easy verification that the result of every elementary substitution is zero, so we omit it.
\end{proof}

\begin{theorem}\label{basis}
	The polynomials (\ref{1})-(\ref{14}) form a basis for the $(\mathbb{Z}_2,\ast)$-identities with for $\mathcal{U}=UT_3(F)$ with the elementary $\mathbb{Z}_2$-grading induced by $(0,1,0)$ and the reflection involution.

\end{theorem}
\begin{proof}
Let $I$ be the $T_{(\mathbb{Z}_2,\ast)}$-ideal generated by the polynomials (\ref{1})-(\ref{14}). Lemma \ref{ids} implies that $I\subseteq T_{\mathbb{Z}_2,\ast}(\mathcal{U})$. Since the field is of characteristic zero to prove that $I= T_{\mathbb{Z}_2,\ast}(\mathcal{U})$ it is sufficient to prove that $\Gamma_n\cap T_{\mathbb{Z}_2,\ast}(\mathcal{U})\subseteq I$. Let $f$ be a polynomial in $\Gamma_n\cap T_{\mathbb{Z}_2,\ast}(\mathcal{U})$. If the number of indeterminates in $f$ of odd degree is $>2$ then $f$ is a consequence of (\ref{2}), hence $f$ lies in $I$.  The rest of the proof is divided in three cases.

\vspace{0,3cm}

{\bf Case 1:} $f$ is a polynomial in even indeterminates only.

Note that if every indeterminate in $f$ is skew-symmetric then $f$ is congruent modulo $I$ to a scalar multiple of
\begin{align}\label{y-}
y_1^{-}\cdots y_n^{-}.
\end{align}
Let $\alpha$ be the scalar such that $f\equiv_I\alpha y_1^{-}\cdots y_n^{-}$. Since $f\in T_{\mathbb{Z}_2,\ast}(\mathcal{U})$ and $I\subseteq  T_{\mathbb{Z}_2,\ast}(\mathcal{U})$ we conclude that $\alpha y_1^{-}\cdots y_n^{-} \in T_{\mathbb{Z}_2,\ast}(\mathcal{U})$. The monomial (\ref{y-}) is not an identity for $\mathcal{U}$, hence we conclude that $\alpha=0$. Therefore $f\in I$.

Now we assume that $f$ has symmetric indeterminates. Since $f$ is proper, if it is a polynomial in symmmetric even indeterminates only then it is a consequence of (\ref{3}), therefore it lies in $I$. Hence we assume that $f$ has symmetric and skew-symmetric indeterminates. Let $y_{i_1}^{-},\dots, y_{i_a}^{-}, y_{j_1}^{+},\dots, y_{j_b}^{+}$, $a,b>0$, be the indeterminates in $f$. Recall that $f$ is a linear combination of polynomials of the form
\begin{align}\label{poly}
y_{k_1}^{-}\cdots y_{k_r}^{-}u_1\cdots u_s,
\end{align}
where $u_1,\dots, u_s$ are commutators. Note that if in a commutator $u_i$ the first two indeterminates are both symmetric or both skew-symmetric then $u_i$ is a consequence of (\ref{3}). Hence in this case the polynomial (\ref{poly}) lies in $I$. Otherwise we may use the anti-commutativity of in the first two indeterminates of the left-normed commutator to write $f$ as a linear combination of polynomials in (\ref{poly}) such that the first indeterminate in $u_i$ is symmetric for $i=1,\dots,s$. If $s>1$ then the polynomial (\ref{poly}) is a consequence of (\ref{4}), hence $f$ is congruent modulo $I$ to a linear combination of polynomials the form (\ref{poly}) with $s=1$ and first indeterminate symmetric in the commutator. Note that $[y_{i_1}^{+},y_{i_2}^{-},\dots, y_{i_k}^{-}]$ is a symmetric polynomial of degree $0$,  hence (\ref{3}) implies that $[y_{i_1}^{+},y_{i_2}^{-},\dots, y_{i_k}^{-},y_{i_{k+1}}^{+}]$ lies in $I$. Therefore $f$ is congruent modulo $I$ to a linear combination of polynomials of the form
\begin{align}\label{pol}
y_{k_1}^{-}\cdots y_{k_r}^{-}[y_{j_1}^{+},y_{t_{1}}^{-},\dots, y_{t_s}^{-}].
\end{align}
We use the polynomial in (\ref{9}) to conclude that $$[y_{j_1}^{+},y_{t_{1}}^{-},\dots, y_{t_s}^{-}]\equiv_I(-2)^{s-1}y_{t_s}^{-}\cdots y_{t_2}^{-}[y_{j_1}^{+},y_{t_1}^{-}].$$
Now note that in the polynomial above the skew-symmetric indeterminates may be reordered modulo $I$ due to (\ref{1}). Hence every polynomial in $\Gamma_n$ is congruent modulo $I$ to a linear combination of polynomials of the form
\begin{align}\label{basiseven}
p_{j}=y_{i_1}^{-}\cdots y_{i_{n-2}}^{-}[y_{j}^{+},y_{i_{n-1}}^{-}],
\end{align}
where $i_1<\cdots < i_{n-1}, \{i_1,\dots, i_{n-1},j\}=\{1,\dots,n\}$.
We claim that the polynomials $p_1,\dots, p_n$ are linearly independent modulo $T_{\mathbb{Z}_2,\ast}(\mathcal{U})$. Indeed let $\alpha_1,\dots, \alpha_n$ be scalars such that
\begin{align*}
\alpha_1p_1+\cdots+\alpha_np_n\in T_{\mathbb{Z}_2,\ast}(\mathcal{U}).
\end{align*}
Since different sets of indeterminats appear in different polynomials in (\ref{basiseven}) we conclude that $\alpha_ip_i\in T_{\mathbb{Z}_2,\ast}(\mathcal{U})$. Note that $p_i\notin T_{\mathbb{Z}_2,\ast}(\mathcal{U})$, $i=1,\dots, n$, therefore we conclude that $\alpha_1,\dots, \alpha_n=0$. Now let $\alpha_1^{\prime},\dots, \alpha_n^{\prime}$ be scalars such that
\begin{align*}
f\equiv_I \alpha_1^{\prime}p_1+\cdots + \alpha_n^{\prime}p_n,
\end{align*}
Then $\alpha_1^{\prime}p_1+\cdots + \alpha_n^{\prime}p_n$ is a $(\mathbb{Z}_2,\ast)$-identity for $\mathcal{U}$, as a consequence $\alpha_1^{\prime}=\dots = \alpha_n^{\prime}=0$. Therefore $f\in I$.

\vspace{0,3cm}

{\bf Case 2:} $f$ is a polynomial in one odd indeterminate.

As a consequence of (\ref{4}), (\ref{7}) the polynomial $f$ is congruent modulo $I$ a linear combination of polynomials of the form
\begin{align}\label{polyzbas1}
y_{i_1}^{-}\cdots y_{i_{n-1}}^{-}z_j,
\end{align}
where $i_1<\cdots< i_{n-1}$, $\{i_1,\dots, i_{n-1},j\}=\{1,\dots, n\}$ and of polynomials in $\Gamma_n$ of the form
\begin{align}\label{polyz2}
g=y_{i_1}^{-}\cdots y_{i_k}^{-}[z_j,y_{j_1},\cdots, y_{j_{n-k}}].
\end{align}
It follows from the identities (\ref{3}) and (\ref{7}) that we may reorder, modulo $I$, the even indeterminates in the commutator in $g$ and assume that the symmetric ones appear before the skew-symmetric ones. We rewrite (\ref{10}) as $y_1^{-}y_2^{-}z_1-y_1^{-}[y_2^{-},z_1]$, therefore modulo $I$ we may assume that, if $k\geq 1$, the even skew-symmetric indeterminates of $g$ are outside of the commutator. As a consequence $g$ is congruent, modulo $I$, to
\begin{align}\label{polyzbas2}
y_{i_1}^{-}\cdots y_{i_a}^{-}[z_j,y_{k_1}^{+},\cdots, y_{k_b}^{+}],
\end{align}
where $b>0$, $i_1<\cdots<i_a$, $k_1<\cdots<k_b$, $\{i_1,\dots, i_a,j,k_1,\dots,k_b\}=\{1,\dots, n\}$
or
\begin{align}\label{polyzbas3}
[z_j,y_{k_1}^{+},\cdots, y_{k_b}^{+},y_{i_1}^{-},\cdots, y_{i_a}^{-}],
\end{align}
where $i_1<\cdots<i_a$, $k_1<\cdots<k_b$, $\{i_1,\dots, i_a,j,k_1,\dots,k_b\}=\{1,\dots, n\}$.

Hence $f$ is congruent modulo $I$ to a linear combination of the polynomials in (\ref{polyzbas1}), (\ref{polyzbas2}) and (\ref{polyzbas3}). It is easy to verify that these polynomials are linearly independent modulo $T_{\mathbb{Z}_2,\ast}(\mathcal{U})$. Hence we conclude, as in the previous case, that $f\in I$.

\vspace{0,3cm}

{\bf Case 3:} $f$ is a polynomial in two odd indeterminates.

Note that if no symmetric even indeterminate appears in $f$ then it follows from identities (\ref{3}), (\ref{11}), (\ref{12}) and (\ref{13}) that $f$ is congruent modulo $I$ to a linear combination of the polynomials
\begin{align}\label{basis31}
y_{i_1}^{-}\cdots y_{i_{n-2}}^{-}z_{j_1}z_{j_2},
\end{align}
where $i_1<\cdots< i_{n-2}$, $j_1<j_2$ and $\{i_1,\dots, i_{n-2},j_1,j_2\}=\{1,\dots,n\}$.

Now assume that $f$ has even symmetric indetermintates. Let $u=[z_{j_1},y_{t_1},\cdots, y_{t_r},z_{j_2}, y_{s_1},\cdots, y_{s_{r^{\prime}}}]$, $r,r^{\prime}\geq 0$, be a commutator involving both odd indeterminates. We claim that, if at least one even indeterminate is symmetric, then $u$ is a linear combination of proper polynomials in which the two odd indeterminates do not appear in the same commutator. Indeed, if one of the indeterminates $y_{s_i}$, $1\leq i \leq r^{\prime}$ is symmetric then it follows from (\ref{6}) that $u\in I$. Now assume that these indeterminates are skew-symmetric. In this case it follows from (\ref{13}) that $u$ is congruent modulo $I$ to a scalar multiple of
\begin{align*}
y_{s_{r^{\prime}}}\cdots y_{s_1} u^{\prime},
\end{align*}
where $u^{\prime}=[z_{j_1},y_{t_1},\cdots, y_{t_r},z_{j_2}]$.  We use identities (\ref{11}) and (\ref{13}) to conclude that $u^{\prime}$ is congruent, modulo $I$, to a scalar multiple of a polynomial of the form
\begin{align*}
y_{i_1}^{-}\cdots y_{i_a}^{-}[z_{j_1},y_{k_1}^{+},\dots, y_{k_b}^{+},z_{j_2}].
\end{align*}
Identity (\ref{6}) implies that $$z_1[y_1^{+},z_2]+z_2[y_1^{+},z_1]-[z_1,y_1^{+},z_2]\in I.$$ If $b>0$ we use  we use this identity to write the commutator $[z_{j_1},y_{1}^{+},\dots, y_{b}^{+},z_{j_2}]$, modulo $I$, as a linear combination of the desired form. This proves the claim.

Therefore $f$ is congruent modulo $I$ to a linear combination of proper polynomials of the form
\begin{align}\label{polyy}
y_{i_1}^{-}\cdots y_{i_a}^{-}[z_{j_1},y_{k_1}^{+},\dots, y_{k_b}^{+}][z_{j_2},y_{t_1}^{+},\dots, y_{t_c}^{+}].
\end{align}

We use identity (\ref{14}) to conclude that (\ref{polyy}) is congruent modulo $I$ to a scalar multiple of a polynomial of the form
\begin{align}\label{polyyy}
y_{i_1}^{-}\cdots y_{i_a}^{-}z_{j_1}[z_{j_2},y_{s_1}^{+},\dots, y_{s_r}^{+}].
\end{align}
Moreover if $z_1,z_2$ are both symmetric or skew-symmetric then $z_1[z_2,y_1^{+}]-z_2[z_1,y_1^{+}]$ follows from (\ref{1}), if one is symmetric and the other skew-symmetric then $z_1[y_1^{+},z_2]+z_2[y_1^{+},z_1]$ follows from (\ref{3}) and (\ref{6}). Now we use these identities to order the indices of the odd indeterminates, the identities (\ref{3}) to order the indices in the symmetric/skew-symmetric even indeterminates and conclude $f$ is congruent modulo $I$ to a linear combination of the polynomials in (\ref{basis31}) and (\ref{polyyy}), where the indices of the polynomial in (\ref{polyyy}) satisfy the following conditions: $r>0$ $i_1<\cdots<i_a$, $j_1<j_2$, $s_1<\cdots<s_r$ and $\{i_1,\dots, i_a,j_1,j_2,s_1,\dots, s_r\}=\{1,\dots, n\}$. These polynomials are linearly independent modulo $T_{\mathbb{Z}_2,\ast}(\mathcal{U})$. Therefore we conclude that $f\in I$.
\end{proof}

\begin{corollary}\label{codim3}
	For $\mathcal{U}=UT_3(F)$ with the elementary $\mathbb{Z}_2$-grading induced by $(0,1,0)$ and the reflection involution $\ast$ we have $$\mathrm{exp}^{\mathbb{Z}_2,\ast}(\mathcal{U})=3.$$
\end{corollary}
\begin{proof}
It follows from the proof of Theorem \ref{basis} that the images of the polynomials (\ref{y-}), (\ref{basiseven}), (\ref{polyzbas1}), (\ref{polyzbas2}), (\ref{polyzbas3}), (\ref{basis31}) and (\ref{polyyy}) form a basis for $\Gamma_n(\mathcal{U})$. Therefore
\begin{align*}
\gamma_n^{\mathbb{Z}_2,\ast}(\mathcal{U})=1+n+n+n(2^{n-1}-1)+n2^{n-1}+{n\choose 2}+{n\choose 2}\left(2^{n-2}-1\right)=1+n+n2^n+{n\choose 2}2^{n-2}.
\end{align*}
Proposition \ref{codim} implies that
\begin{align*}
c_n^{\mathbb{Z}_2,\ast}(\mathcal{U})=\sum_{i=0}^{n}{n\choose i}\gamma_i^{\mathbb{Z}_2,\ast}(\mathcal{U}),
\end{align*}
Note that for $1\leq i \leq n$ we have
\begin{align*}
2^{i}\leq \gamma_i^{\mathbb{Z}_2,\ast}(\mathcal{U})\leq \left(n+1+\frac{1}{4}{n\choose 2}\right)2^i.
\end{align*}
Hence
\begin{align*}
3^n=\sum_{i=0}^{n}{n\choose i}2^i\leq c_n^{\mathbb{Z}_2,\ast}(\mathcal{U})\leq \left(n+1+\frac{1}{4}{n\choose 2}\right) \sum_{i=0}^{n}{n\choose i}2^i=\left(n+1+\frac{1}{4}{n\choose 2}\right)3^n.
\end{align*}
Therefore we conclude that $\mathrm{exp}^{\mathbb{Z}_2,\ast}(\mathcal{U})=3$.
\end{proof}

We remark that as a consequence of the corollary above and of Proposition \ref{coars} the $\ast$-exponent of $UT_3(F)$ is $3$. This also follows from the computations in \cite{VKS}.


TITLE: Given a family of probability distributions that are "close to each other" and have expected values 1, 2, 3..., find a lower bound on their variance
QUESTION [3 upvotes]: Let $\left(\mathcal{D}_{n}\right)_{n\in\mathbb{N}}$ be a family of probability distributions such as:

$\forall n\in\mathbb{N}$, $\mathbb{E}\left[\mathcal{D}_{n}\right]=n$: the average value of the n-th distribution is n.
$\forall n\in\mathbb{N}$, $\delta\left(\mathcal{D}_{n},\mathcal{D}_{n+1}\right)<\varepsilon$
for some small $\varepsilon>0$, where $\delta$ is the total variation
distance:
two consecutive distributions are "close to each other".

I want to find a lower bound on $\text{Var}\left(\mathcal{D}_{n}\right)=\mathbb{E}\left[\left(\mathcal{D}_{n}-n\right)^{2}\right]$.
[Edit: I originally conjectured that the bound was something like $\frac{\left(1-\varepsilon\right)}{\varepsilon}\cdot n$, at least asymptotically, but Ross' answer below shows that this is wrong and you can get a family for which each variance is proportional to $1/\varepsilon^2$. I'm looking for any lower bound that is proportional to $1/\varepsilon$ for small values of $\varepsilon$.]

REPLY [3 votes]: You can have the variance independent of $n$.  Let each $\mathcal{D}_{n}$ be a triangular distribution that starts at $n-k$ with value $\varepsilon$, rises in steps of $\varepsilon$ up to $(k+1)\varepsilon$ at $n$, then drops back down to $\varepsilon$ at $n+k$.  This set of distributions satisfies the distance requirement.  To get total probability of $1$ we need $k+1=\frac 1{\sqrt {\varepsilon}}$.  The variance is $$2\sum_{j=1}^k(k-j)\epsilon j^2\approx \frac 1{6\varepsilon}$$ I haven't proved this is the minimum


TITLE: From $(p\lor q)\to r, s\to\neg p, s\land\neg q$, prove $\neg r$
QUESTION [0 upvotes]: Need help with this:
$$\frac{p\lor q\to r;s\to\neg p;s\land\neg q}{\therefore\neg r}$$
How do I prove that $\neg r$ is in fact true?

REPLY [1 votes]: The only premise you have involving $r$ is the first one, which has the form $XYZ\to r$.  No matter how much you know or can prove about $XYZ$, you will never be able to conclude $\lnot r$ from this; it only tells you a condition under which you can conclude $r$.
Compare: “If you steal, you will be arrested.”  Could you ever be certain that you won't be arrested?  No, of course not.  Whether or not you steal, you might be arrested for tax fraud or for wearing the wrong shirt on Wednesday.


text:
\section{The full recovery transition}\label{sec:app_perfect_recovery}

In this section, we assume a Gaussian standard prior $P_0 = \mathcal{N}_\beta(0,1)$ and a noiseless phase retrieval channel,
and we show that information-theoretic full recovery is achieved exactly at $\alpha = \alpha_{\FR,\IT} \equiv \beta(1-\nu(\{0\}))$.
We can assume without loss of generality that $\langle \lambda \rangle_\nu = \alpha$, as this amounts to a simple rescaling of $\bPhi$, irrelevant under the noiseless channel.
This implies in particular that $Q_z = \hat{Q}_z = 1$.

\subsection{The state evolution equations}

Since we assumed a Gaussian prior, we have, with $P_\mathrm{out}(y|z) = \delta(y-|z|^2)$:
\begin{subnumcases}{\label{eq:se_pr_gaussian_prior}}
\label{eq:se_pr_gaussian_prior_qz}
    q_z = \frac{1}{1 + \hat{q}_z} \Big[\hat{q}_z + \int \mathrm{d}y\int_\bbK \mathcal{D}_\beta \xi \frac{\Big|\int_\bbK \mathcal{D}_\beta z \ z \  P_\mathrm{out}\Big(y\Big|\frac{z}{\sqrt{1 + \hat{q}_z}} + \sqrt{\frac{\hat{q}_z}{1 + \hat{q}_z}}\xi\Big)\Big|^2}{\int_\bbK \mathcal{D}_\beta z P_\mathrm{out}\Big(y\Big|\frac{z}{\sqrt{1 + \hat{q}_z}} + \sqrt{\frac{\hat{q}_z}{1 + \hat{q}_z}}\xi\Big)}\Big],& \\
\label{eq:se_pr_gaussian_prior_qhx}
    \hat{q}_x = \frac{q_x}{1-q_x},& \\
\label{eq:se_pr_gaussian_prior_qhz}
    \hat{q}_z = \frac{q_z}{1-q_z} - \gamma_z, &\\
\label{eq:se_pr_gaussian_prior_qx}
    q_x = \alpha \gamma_z (1-q_z), & \\
\label{eq:se_pr_gaussian_prior_gammaz}
    \alpha(1-q_z) = \Big\langle \frac{\lambda}{1 + \lambda \gamma_z}\Big\rangle_\nu.&
\end{subnumcases}
Comparing these equations to Conjecture~\ref{conjecture:replicas_general},
one can see that we imposed $\gamma_x = 0$, a straightforward consequence of the Gaussian prior (see Section~\ref{sec:app_equivalence_replicas} where this calculation is detailed for a different purpose).

\subsection{Noisy phase retrieval with small variance}

We wish to show that the free entropy of the full recovery solution is the global maximum of the free entropy potential
for $\alpha > \alpha_\mathrm{IT}$, while it is never the case for $\alpha < \alpha_\mathrm{IT}$.
However, under a noiseless channel, the free entropy potential might diverge in this point, which
indicates towards a regularization procedure.
Therefore we consider a noisy Gaussian channel with noise $\Delta > 0$:
\begin{align}
    P_\mathrm{out}(y|z) = \frac{1}{\sqrt{2 \pi \Delta}} \exp \Big\{-\frac{1}{2\Delta}(y-|z|^2)^2\Big\}.
\end{align}
We will compute the limit, as $\Delta \downarrow 0$, of the free entropy of the ``almost perfect'' recovery fixed point.
We look for a solution close to the point which corresponds to the best possible recovery:
\begin{subnumcases}{}
    q_x = 1 - \nu(\{0\}), &\\
    q_z = 1.&
\end{subnumcases}
Indeed it is easy to see that $q_x \leq 1 -\nu(\{0\})$ since $\mathrm{rk}[\bPhi^\dagger \bPhi] \sim n (1-\nu(\{0\}))$.
We are thus looking for a fixed point of the state evolution equations~\eqref{eq:se_pr_gaussian_prior}
 that satisfies:
 \begin{subnumcases}{}
    q_x = 1 - \nu(\{0\}) + \smallO_\Delta(1), & \\
    q_z = 1 + \smallO_\Delta(1), & \\
    \hat{q}_x^{-1} = \nu(\{0\}) / (1-\nu(\{0\})) + \smallO_\Delta(1), &\\
    \hat{q}_z^{-1} = \smallO_\Delta(1).&
 \end{subnumcases}
 Let us now precise the asymptotics of these quantities as $\Delta \downarrow 0$.
By eq.~\eqref{eq:se_pr_gaussian_prior_qx}, we find easily:
\begin{align}
    \gamma_z \sim \frac{1-\nu(\{0\})}{\alpha(1-q_z)}.
\end{align}
Then from eq.~\eqref{eq:se_pr_gaussian_prior_qhz}, we also have:
\begin{align}\label{eq:qhz_scaling}
    \hat{q}_z \sim \frac{\alpha-1+\nu(\{0\})}{\alpha(1-q_z)}.
\end{align}
Note that if $\alpha \leq 1$, then necessarily $\nu(\{0\}) \geq 1-\alpha$, so that the quantity in the numerator is always positive.
We now turn to eq.~\eqref{eq:se_pr_gaussian_prior_qz}.
We assume the scaling $\hat{q}_z^{-1} = c \Delta + \smallO_\Delta(\Delta)$.
We have by Gaussian integration by parts and using the specific form of $P_\mathrm{out}$:
\begin{align*}
     \int \mathrm{d}y \mathcal{D}_\beta \xi & \frac{\Big|\int \mathcal{D}_\beta z \ z \  P_\mathrm{out}\Big(y\Big|\frac{z}{\sqrt{1 + \hat{q}_z}} + \sqrt{\frac{\hat{q}_z}{1 + \hat{q}_z}}\xi\Big)\Big|^2}{\int \mathcal{D}_\beta z P_\mathrm{out}\Big(y\Big|\frac{z}{\sqrt{1 + \hat{q}_z}} + \sqrt{\frac{\hat{q}_z}{1 + \hat{q}_z}}\xi\Big)} \\
     &= \frac{1}{(1+\hat{q}_z)} \int \mathrm{d}y \mathcal{D}_\beta \xi \frac{\Big|\int \mathcal{D}_\beta z \  P_\mathrm{out}'\Big(y\Big|\frac{z}{\sqrt{1 + \hat{q}_z}} + \sqrt{\frac{\hat{q}_z}{1 + \hat{q}_z}}\xi\Big)\Big|^2}{\int \mathcal{D}_\beta z P_\mathrm{out}\Big(y\Big|\frac{z}{\sqrt{1 + \hat{q}_z}} + \sqrt{\frac{\hat{q}_z}{1 + \hat{q}_z}}\xi\Big)} \sim \frac{4}{\Delta(1+\hat{q}_z)} \sim 4c.
\end{align*}
Gaussian integration by parts and our conventions for derivatives of real functions of complex variables are summarized in Section~\ref{subsec:app_derivatives}.
This yields that $1-q_z = \Delta c(1-4c) + \smallO_\Delta(1)$.
Combining this result with eq.~\eqref{eq:qhz_scaling}, we have
\begin{align*}
    c (1-4c)&= c \Big[\frac{\alpha-1+\nu(\{0\})}{\alpha}\Big].
\end{align*}
This implies $c = (1-\nu(\{0\}))/(4 \alpha)$, and we finally obtain the leading order asymptotics of $q_z,\hat{q_z},\gamma_z$ as $\Delta \to 0$:
\begin{subnumcases}{\label{eq:final_asymptotics}}
   \hat{q}_z = \frac{4 \alpha}{(1-\nu(\{0\}))\Delta} + \smallO_\Delta\(\Delta^{-1}\), & \\
   1- q_z = \frac{(1-\nu(\{0\})(\alpha -1 + \nu(\{0\}))}{4 \alpha ^2} \Delta + \smallO_\Delta(\Delta), & \\
   \gamma_z = \frac{4 \alpha}{\Delta(\alpha-1+\nu(\{0\}))}+ \smallO_\Delta(\Delta^{-1}) . &
\end{subnumcases}
Let us now compute the asymptotics of the three auxiliary functions $I_0,I_\mathrm{out}$ and $I_\mathrm{int}$ of Conjecture~\ref{conjecture:replicas_general}:
\begin{align*}
    I_0(q_x) &= \frac{\beta}{2} [q_x + \ln(1-q_x)], \\
    I_\mathrm{out}(q_z) &= -\frac{\beta\hat{q}_z q_z}{2} - \frac{\beta}{2} \ln (1 + \hat{q}_z) + \frac{\beta \hat{q}_z}{2} + \int \mathrm{d}y \mathcal{D}\xi \ J(\hat{q}_z,y,\xi) \ln J(\hat{q}_z,y,\xi), \\
    J(\hat{q}_z,y,\xi) &\equiv \int \mathcal{D}z P_\mathrm{out}\Big(y\Big|\frac{z}{\sqrt{1 + \hat{q}_z}} + \sqrt{\frac{\hat{q}_z}{1 + \hat{q}_z}}\xi\Big), \nonumber \\
    I_\mathrm{int}(q_x,q_z) &= \frac{\beta}{2}[\alpha (1 - q_z) \gamma_z - \langle \ln (1 + \lambda \gamma_z) \rangle_\nu - \ln(1-q_x) - q_x - \alpha \ln(1 - q_z) - \alpha q_z ].
\end{align*}
Using eq.~\eqref{eq:final_asymptotics} and the specific form of the channel, we reach:
\begin{align*}
    I_0(q_x) + I_\mathrm{int}(q_x,q_z) &\sim - \frac{\beta(\alpha-1+\nu(\{0\}))}{2} \ln \Delta, \\
    I_\mathrm{out}(q_z) &\sim \frac{(\beta-1)}{2} \ln \Delta.
\end{align*}
Therefore when considering the total free entropy we have
\begin{align*}
    I_0(q_x) + I_\mathrm{int}(q_x,q_z) + \alpha I_\mathrm{out}(q_z) &\sim \frac{\alpha(\beta-1) - \beta(\alpha-1+\nu(\{0\}))}{2} \ln \Delta , \\
    & \sim \frac{\beta(1-\nu(\{0\}))-\alpha}{2} \ln \Delta.
\end{align*}
This implies that the full recovery point has a free entropy of $- \infty$ for $\alpha < \alpha_{\FR,\IT} \equiv \beta(1-\nu(\{0\}))$, and $+ \infty$ for $\alpha > \alpha_{\FR,\IT}$.
Thus this point is always the global maximum of the free entropy for $\alpha > \alpha_{\FR,\IT}$, while it
is never the case for $\alpha < \alpha_{\FR,\IT}$, which ends our argument.

config: arxiv


text:
\section{Appendix}
\subsection{General kernel derivatives of stationary kernels}

\emph{Stationary kernels} can be written as a function of the distance, i.e.,
$k(t,t') = \tilde{k}(|t-t'|)$. In many cases, it is helpful to define the
distance in terms of the squared distance and in units of the step length $h$.
\begin{align}
r(t,t') &= \frac{(t-t')^2}{h^2}\\
k(t,t') &= (\tilde{k} \circ r)(t,t')
\end{align}

In the following, there is a list of necessary kernel derivatives in order to
compute partial kernel derivatives needed in Sec.~\ref{sec:2nd-order-methods}.
We will write $k(r)$ for $\tilde{k}(r(t,t'))$ for easier parsing.

\begin{align}
\kd  &= \dkdr \frac{\de r}{\de t'}\\
\label{eq:kd-stat}
     &= \dkdr \left(-2\frac{(t-t')}{h^2}\right)\\
\dkd &= \frac{\de \kd}{\de t}\\
     &= \left(\dtkdrt \frac{\de r}{\de t} \frac{\de r}{\de t'}\right)
      + \left(\dkdr \frac{\de^2 r}{\de t \de t'}\right)\\
\label{eq:dkd-stat}
     &= -4 \frac{(t-t')^2}{h^4} \dtkdrt - \frac{2}{h^2} \dkdr
\end{align}

With Eqs.~\eqref{eq:kd-stat} and \eqref{eq:dkd-stat}, this gives rise to the
following substitutions:
\begin{align}
k(t_n + h\alpha, t_n + h\alpha) &= k(0)\\
\kd(t_n + h\alpha, t_n) &= -2\frac{\alpha}{h} \evalat{\dkdr}{\alpha^2}\\
\kd(t_n + h, t_n) &= -\frac{2}{h} \evalat{\dkdr}{1}\\
\kd(t_n + h, t_n + h\alpha) &= -2 \frac{(1-\alpha)}{h} \evalat{\dkdr}{(1-\alpha)^2}\\
\dkd(t_n + h\alpha, t_n + h\alpha) &= - \frac{2}{h^2} \evalat{\dkdr}{0}\\
\dkd(t_n, t_n) &= - \frac{2}{h^2} \evalat{\dkdr}{0}\\
\dkd(t_n + h\alpha, t_n) &= -4 \frac{\alpha^2}{h^2} \evalat{\dtkdrt}{\alpha^2}
                             - \frac{2}{h^2}\evalat{\dkdr}{\alpha^2}
\end{align}

Furthermore, we observe that there are two special cases, $\alpha = \frac{1}{2}$
and $\alpha = 1$, which need to be treated seperately.

\subsection{The Integrated Wiener Process}
It was assumed that the Integrated Wiener Process (IW) will lead to a connection with
Runge-Kutta methods. This section details the derivation of
higher-order IW kernels, derivatives and other needed relationships.

The \emph{Wiener Process kernel} is given by:
\begin{align}
k_{WP}(t,t') &= c (\min(t,t') - b)
\end{align}
In order to arrive at higher-order IW kernels, one must integrate
$k_{WP}$ with respect to both $t$ and $t'$ which gives:
\begin{align}
k^1_{WP}(t,t') &= \int_b^t du \int_b^{t'} dv (c \min(u,v) - b)\\
&= c \int_b^t du \int_b^{t'} dv \min(u,v) - c b (t-b) (t'-b)\\
&\stackrel{t>t'}{=} c \left(\int_{t'}^t du \int_b^{t'} dv\; v
                      + 2 \int_b^{t'} du \int_b^{u} dv\; v\right)
                 - c b (t-b) (t'-b)\\
&= c \left( \int_{t'}^t du\; \frac{1}{2}(t'^2 - b^2)
          + 2 \int_b^{t'} du\; \frac{1}{2} (u^2 - b^2) \right) - c b
          (t-b) (t'-b)\\
&= c \left( \frac{1}{2}(t-t')(t'^2 - b^2) - b^2 (t'-b) +
          \frac{1}{3}(t'^3 - b^3) \right) - c b (t-b)(t'-b)\\

&= c \left[ \abs{t - t'} \frac{\min\nolimits^2(t,t')}{2} +
            \frac{\min\nolimits^3(t,t')}{3} + \frac{1}{2} b^2(t+t') -
            \frac{1}{3}b^3 - btt'\right]
\end{align}

Its derivatives are given by:
\begin{align}
\kd^1(t,t') &=
  c \left[
    \begin{cases}
      t < t': & \frac{t^2}{2} + \frac{b^2}{2} - bt\\
      t > t': & tt' - \frac{t'^2}{2} + \frac{b^2}{2} - bt
    \end{cases}
    \right]
\end{align}
and
\begin{align}
\dkd^1(t,t') &= c (\min(t,t') - b)
\end{align}
which is exactly what we expected it to be.

Iterating this process leads to the \emph{Twice Integrated Wiener
  Process}. For simplicity, we'll assume $b=0$  which leads to:
\begin{align}
k^2_{WP}(t,t') &= c \left[ \int_0^t du \int_0^{t'} dv\; \abs{u-v}
  \frac{\min\nolimits^2(u,v)}{2} +
  \frac{\min\nolimits^3(u,v)}{3}\right]\\
  &\stackrel{t>t'}{=} c \left[
     \left( \int_{t'}^t du \int_0^{t'} dv\; (u-v)
     \frac{v^2}{2} + \frac{v^3}{3} \right) +
     \left( \int_0^{t'} du \int_0^u dv\; (u-v) \frac{v^2}{2} +
     \frac{v^3}{3} \right)  +
     \left( \int_0^v du \int_0^{t'} dv\; (v-u) \frac{u^2}{2} +
     \frac{u^3}{3} \right) \right]
\end{align}

\section{Basic derivatives}
The following derivatives are needed in computing some of the
derivatives of the \emph{Integrated Wiener Process}:
\begin{align}
\frac{\de}{\de t'} \abs{t - t'} &= \frac{\de}{\de t'} \sqrt{(t-t')^2}\\
&= \frac{1}{2 \sqrt{(t-t')^2}} 2 (t-t')(-1)\\
&= -\frac{(t-t')}{\sqrt{(t-t')^2}}\\
&= -\frac{(t-t')}{\abs{t-t'}}
\end{align}
Furthermore, we have:
\begin{align}
\frac{\de}{\de t'} \min(t, t') &= \frac{\de}{\de t'} \frac{1}{2} (t + t' - \abs{t - t'})\\
\label{eq:min-derivative}
&= \frac{1}{2}\left(1 + \frac{(t-t')}{\abs{t-t'}}\right)\\
&= \ind{[t > t']}
\end{align}

\section{Higher order integrated Wiener Process as solutions to
  Stochastic Differential Equations}

Consider a $d$-dimensional stochastic process
$\vec{X}(t) = (X_1(t), \dots, X_d(t))$ which satisfies the following
stochastic differential equations:
\begin{align}
d\vec{X}(t) &= \mat{F}\vec{X}(t) + \vec{L}d\vec{W}(t)
\end{align}
where $\vec{W}(t)$ denotes Brownian motion and $\mat{F}$ and $\vec{L}$
are mixing weights given in matrix and vector form. If $\mat{F}$ and
$\vec{L}$ are of the form
\begin{align}
\mat{F} &= \begin{bmatrix} 0 & 1 & 0 & \hdots & 0\\
                           0 & 0 & 1 & \hdots & 0\\
                           \vdots & \vdots & \ddots & \ddots & 0\\
                           0 & \hdots & \hdots & 0 & 1\\
                           0 & \hdots & \hdots & \hdots & 0
           \end{bmatrix}
&
\vec{L} &= \begin{bmatrix} 0\\ 0\\ \vdots\\ 0\\ 1 \end{bmatrix}
\end{align}
then it is clear that $X_d(t)$ is distributed according to a Brownian
motion but is also the $d^{\text{th}}$ derivative of $X_1(t)$ and,
therefore, $X_1(t)$ is a $d$-times integrated Brownian motion. This is
can be used to compute the covariance function of the $d$-times
integrated Wiener Process in closed form easily.


TITLE: Does the limit $\,\lim_{x\to\infty}f(x)\,$ exist?
QUESTION [3 upvotes]: Let $ \,f :[0,\infty) \to R$ be the function  such that for any positive  $a$, the sequence  $\left\lbrace \,f(an)\right\rbrace$ converges to $0$.
  Does  the limit $\ \lim_{x\to\infty}f(x)\,$ exist?

My  answer : yes, take  $\;f_n(x) = e^{{-nax}^2}$.

REPLY [2 votes]: I will give you few hints.

Try with something discontinuous  (maybe something that is zero except for some points)
Look at the points considered by the problem. They are all of the form $an$ for some $a>0$ fixed. This means that you are only looking at integer multiples of $a$. What happens if your function is defined $1$ on $b^n$, where $b$ is some noninteger number larger than $1$ (to be choosen)?


TITLE: Get the minimum number which can be divided by 63 and modulus 40 equals 1
QUESTION [1 upvotes]: I have got a puzzle to find out the smallest n (natural number) that:
n modulus 2 is 1.
n modulus 3 is 0.
n modulus 4 is 1.
n modulus 5 is 1.
n modulus 6 is 3.
n modulus 7 is 0.
n modulus 8 is 1.
n modulus 9 is 0.
It is not hard to find out that n % 63 == 0 and n % 40 == 1. Then I wrote a small program to find out the smallest n is 441.
But my question is, is there any mathematical way in finding out the smallest number in the last part, rather than using a program to traverse? Or is traverse the only approach in this situation?

REPLY [2 votes]: One way to solve this problem is by using the Euclidean Algorithm. You know $n=63k$ and $n=40j+1$ for some $j,k\in\mathbb{N}$. Setting these equal to each other, you find $63k-40j=1$. If you continually divide and keep track of remainders using the Euclidean Algorithm, you find:
\begin{align*}
63&=1\cdot40&+23\\
40&=1\cdot23&+17\\
23&=1\cdot17&+6\\
17&=2\cdot6&+5\\
6&=1\cdot5&+1\\
\end{align*}
With this system of equations, you can now start from the bottom and work your way to the top to express $1$ as a linear combination of $63$ and $40$:
\begin{align*}
1&=6-1\cdot5\\
&=6-1\cdot(17-2\cdot6)\\
&=3\cdot6-1\cdot17\\
&\dots\\
&=7\cdot63-11\cdot40\\
\end{align*}
Since $7$ and $11$ are relatively prime, there is no smaller multiple of $63$ than $7\cdot63=441$ which satisfies the original problem.


text:
\vspace{-.5 cm}
\section{Numerical Experiments}\label{sec:simulation}

In this section, we evaluate the performance of the proposed QDGD Algorithm on decentralized quadratic minimization and ridge regression problems and demonstrate the effect of various parameters on the relative expected error rate.  We carry out the simulations on artificial and real data sets corresponding to quadratic minimization  and ridge regression problems, respectively. In both cases, the graph of agents is a connected Erd\H{o}s-R\'enyi with edge probability $p_c$. We set the edge weight matrix to be $W = I - \frac{2}{3 \lambda_{\text{max}}(\mathbf{L})} \mathbf{L}$ where $\mathbf{L}$ is the Laplacian with $\lambda_{\text{max}}(\mathbf{L})$ as its largest eigenvalue.

\subsection{Decentralized quadratic minimization}

In this section, we evaluate the performance of the proposed QDGD Algorithm on minimizing a distributed quadratic objective. We pictorially demonstrate the effect of quantization noise and graph topology on the relative expected error rate.

Consider the quadratic optimization problem

\begin{equation} \label{eq:quadratic}
    \min_{ \bx \in \mathbb{R}^p} \ f(\bx) = \sum_{i=1}^{n} \frac{1}{2} \bx^\top \bA_i \bx +  \bb_i^\top \bx,
\end{equation}

where $f_i(\bx) = \frac{1}{2} \bx^\top \bA_i \bx +  \bb_i^\top \bx$ denotes the local objective function of node $i\in [n]$. The unique solution to (\ref{eq:quadratic}) is therefore $\widetilde{\bx}^* = -\left( \sum_{i=1}^{n} \bA_i\right)^{-1}\left(\sum_{i=1}^{n}\bb_i\right)$. We pick diagonal matrices $\bA_i$ such that $p/2$ of the diagonal entries of each $\bA_i$ are drawn from the set $\{1,2,2^2\}$ and the other $p/2$ diagonal entries are drawn from the set $\{1,2^{-1},2^{-2}\}$, all uniformly at random. Entries of vectors $\bb_i$ are randomly picked from the interval $(0,1)$. In our simulations, we let an additive noise model the quantization error, i.e. $Q(\bx)=\bx+ {\eta}$ where $\eta \sim \mathcal{N}(0,\frac{\sigma^2}{p} I_p)$.

We first consider  a connected Erd\H{o}s-R\'enyi graph of $n=50$ nodes and connectivity probability of $p_c=0.35$ and dimension $p=20$. Fig.~\ref{sigma_plot} shows the convergence rate corresponding to three values of quantization noise $\sigma^2 \in \{2,20,200\}$ and $\delta=3/8$, compared to {{the theoretical upper bound derived in Theorem \ref{thm1} in the logarithmic scale.}} For each plot, stepsizes are  pick as $\eps={c_1}/{T^{3\delta/2}}$ and $\al = {c_2}/{T^{\delta/2}}$ where the constants $c_1,c_2$ are finely tuned. As expected, Fig.~\ref{sigma_plot} shows that the error rate linearly scales with the quantization noise; however, it does not saturate around a non-vanishing residual, regardless the variance. Moreover, Fig.~\ref{sigma_plot} demonstrates that the convergence rate closely follows the upper bound derived in  Theorem \ref{thm1}. For instance, for the plot corresponding to $\sigma^2=200$, the relative errors are evaluated as ${e_{T_1}}/{e_0}=0.1108$ and  ${e_{T_2}}/{e_0}=0.0634$ for $T_1=800$ and $T_2=3200$, respectively. Therefore, ${e_{T_2}}/{e_{T_1}} \approx 0.57$ which is upper bounded by $(\frac{T_1}{T_2})^{\delta} \approx 0.59$.

To observe the effect of graph topology, quantization noise variance is fixed to $\sigma^2=200$ and we varied the connectivity ratio by picking three different values, i.e. $p_c \in \{0.35,0.5,1\}$ where $p_c=1$ corresponds to the complete graph case.  We also fix the parameter $\delta=3/8$ and accordingly  pick the stepsizes $\eps={c_1}/{T^{3\delta/2}}$ and $\al = {c_2}/{T^{\delta/2}}$ where the constants $c_1,c_2$ are finely tuned. As Fig. \ref{graph_plot} depicts, for the same number of iterations, deviation from the optimal solution tends to increase as the graph is gets sparse. In other words, even noisy information of the neighbor nodes improves the gradient estimate for local nodes. It also highlights the fact that regardless of the sparsity of the graph, the proposed QDGD algorithm guarantees the consensus to the optimal solution for each local node, as long as the graph is connected.\\

\begin{figure}[h]
\vspace{-.5cm}
\includegraphics[width=.5\textwidth ]{quantized_consensus_quadratic_c1_c2_2_delta_025_sigma2_01-1-10_n_50_p_20_pc_035.pdf}
\centering
\vspace{-.5cm}
\caption{Relative optimal squared error for three values of quantization noise variance: $\sigma^2 \in \{2,20,200\}$, compared with the order of upper bound.}
\label{sigma_plot}
\end{figure}

\begin{figure}[h]
\vspace{-.5cm}
\includegraphics[width=.5\textwidth ]{quantized_consensus_quadratic_c1_c2_2_delta_025_sigma2_10_n_50_p_20_different_graphs.pdf}
\centering
\vspace{-.5cm}
\caption{Relative optimal squared error for three vales of graph connectivity ratio: $p_c \in \{0.35,0.5,1\}$, compared with the order of upper bound.}
\label{graph_plot}
\end{figure}

\subsection{Decentralized ridge regression}

Consider the ridge regression problem:

\begin{equation} \label{eq:ridgereg}
    \min_{\bx \in \mathbb{R}^p} f(\bx) = \sum_{j=1}^{D} \norm{\mathbf{a}_j \bx - b_j}^2 + \frac{\lambda}{2} \norm{\bx}_2^2,
\end{equation}

over the data set $\mathcal{D} = \{ (\mathbf{a}_j , b_j): j=1,\cdots,D\}$ where each pair $(\mathbf{a}_j , b_j)$ denotes the predictors-response variables corresponding to data point $j\in[D]$ where $\mathbf{a}_j \in \mathbb{R}^{1 \times p}, b_j \in \mathbb{R}$ and $\lambda > 0$ is the regularization parameter. To make this problem decentralized, we pick $n$ agents and uniformly divide the data set $\mathcal{D}$ among the $n$ agents, i.e., each agent is assigned with $d = D/n$ data points. Therefore, (\ref{eq:ridgereg}) can be decomposed as follows:

\begin{equation} \label{eq:ridgereg2}
    \min_{\bx \in \mathbb{R}^p} f(\bx) = \sum_{i=1}^{n} f_i(\bx),
\end{equation}

where the local function corresponding to agent $i \in [n]$ is

\begin{equation} \label{eq:ridgereg3}
    f_i(\bx) = \norm{\bA_i \bx - \bb_i}^2 + \frac{\lambda}{2n} \norm{\bx}^2,
\end{equation}

and

\begin{align} \label{eq:ridgereg3}
    \bA_i &= [\mathbf{a}_{(i-1)d+1};\cdots;\mathbf{a}_{id}] \in \mathbb{R}^{d \times p},\\
    \bb_i &= [b_{(i-1)d+1};\cdots;b_{id}] \in \mathbb{R}^{d}.
\end{align}

The unique solution to (\ref{eq:ridgereg2}) is

\begin{equation} \label{eq:ridgereg4}
    \widetilde{\bx}^* = \left(\sum_{i=1}^{n} \bA^{\top}_i\bA_i + \lambda {I}\right)^{-1}\left(\sum_{i=1}^{n} \bA^{\top}_i\bb_i\right).
\end{equation}

To simulate  the decentralized ridge regression (\ref{eq:ridgereg2}), we pick ``Pen-Based Recognition of Handwritten Digits Data Set" \cite{Dua:2017} and use $D=5000$ training samples with $p=16$ features and $10$ possible labels corresponding to digits $\{\textrm`0\textrm', \textrm`1\textrm', \cdots, \textrm`9\textrm'\}$. We pick $\lambda=2$ and consider a connected Erd\H{o}s-R\'enyi graph with $n=50$ agents and edge probability $p_c$, i.e. each assigned with $d=100$ data points.  The decision variables are quantized according to the low-precision quantizer with quantization level $s$, as described in Example \ref{ex:lp}.

Firstly, we fix $p_c=0.25$ and $s=1$ and vary the tuning parameter $\delta$. Fig. \ref{sigma_plot_ridge} depicts the convergence trend corresponding to two values $\delta \in \{0.175,0.275\}$. For each pick of $\delta$, the stepsizes are set to $\eps={c_1}/{T^{3\delta/2}}$ and $\al = {c_2}/{T^{\delta/2}}$ with finely tuned constants $c_1,c_2$.

Secondly, to observe the effect of graph density, we let the quantization level be $s=1$ and vary the graph configuration. For $\delta=0.275$, Fig. \ref{graph_plot_ridge} shows the resulting convergence rates for Erd\H{o}s-R\'enyi random graphs with two vales of graph connectivity ratio $p_c \in \{0.25,0.45\}$, complete graph and cycle graph.

\begin{figure}[t]
\includegraphics[width=.5\textwidth ]{delta_045_065_c1_162e-5_5e-4_n_50_pc_025_s_1_QSGD_for_paper.pdf}
\centering
\vspace{-.5cm}
\caption{Relative optimal squared error for two vales of $\delta$: $\delta \in \{0.175,0.275\}$.}
\label{sigma_plot_ridge}
\end{figure}

\begin{figure}[t]
\includegraphics[width=.5\textwidth ]{delta_045_c1_162e-5_n_50_combined_graphs_s_1_QSGD_for_paper.pdf}
\centering
\vspace{-.5cm}
\caption{Relative optimal squared error for Erd\H{o}s-R\'enyi random graphs with two vales of graph connectivity ratio: $p_c \in \{0.25,0.45\}$, complete graph and cycle graph.}
\label{graph_plot_ridge}
\end{figure}

\iffalse
We first consider the least squares optimization problem defined in \eqref{eq:leasetsqr} where $f_i(\bx) = \frac{1}{2} \norm{\bA_i \bx - \bb_i}^2$ denotes the local objective function of node $i\in [n]$. We consider the linear model with $\bb_i = \bA_i \tilde{\bx} + \boldsymbol\eta_i$ where the entries of $\bA_i \in \mathbb{R}^{p\times p}$ and $\tilde{\bx} \in \mathbb{R}^{p}$ are drawn randomly from standard normal distribution and $\boldsymbol\eta_i \in \mathbb{R}^{p}$ is additive white Gaussian noise.  The unique solution to (\ref{eq:leasetsqr}) is therefore

\begin{equation} \label{}
    \widetilde{\bx}^* = \left(\sum_{i=1}^{n} \bA^{\top}_i\bA_i \right)^{-1} \left(\sum_{i=1}^{n} \bA^{\top}_i\bb_i\right).
\end{equation}

We consider a connected Erd\"{o}s-R\'enyi graph of $n=100$ nodes and connectivity probability of $p_c=0.1$ and dimension $p=20$. Figure~\ref{sigma_plot} shows the convergence rate corresponding to three values of quantization noise $\sigma^2 \in \{0.1,1,10\}$, compared to {{the theoretical upper bound derived in Theorem \ref{thm1} in the logarithmic scale}} for $\delta=0.3$. As expected, Figure~\ref{sigma_plot} shows that the error rate linearly scales with the quantization noise; however, it does not saturate around a non-vanishing residual, regardless the variance. Moreover, Figure~\ref{sigma_plot} demonstrates that the convergence rate closely follows the upper bound derived in  Theorem \ref{thm1}.

{\color{red}{what quantization do you use here? How can you modify $\sigma$?}}

To observe the effect of graph topology, quantization noise variance is fixed to $\sigma^2=0.1$ and $\delta=0.3$ and we varied the connectivity ratio by picking three different values, i.e. $p_c \in \{0.1,0.5,1\}$ where $p_c=1$ corresponds to the complete graph case. As Figure \ref{graph_plot} depicts, for the same number of iterations, deviation from the optimal solution tends to increase as the graph is gets sparse. In other words, even noisy information of the neighbor nodes improves the gradient estimate for local nodes. It also highlights the fact that regardless of the sparsity of the graph, the proposed QDGD algorithm guarantees the consensus to the optimal solution for each local node, as long as the graph is connected.\\

\begin{figure}[t]
\includegraphics[width=.5\textwidth ]{arxiv1-28}
\centering
\vspace{-.5cm}
\caption{Relative optimal squared error for three vales of quantization error: $\sigma^2 \in \{0.1,1,10\}$, compared with the order of upper bound.}
\label{sigma_plot}
\end{figure}

\begin{figure}[t]
\includegraphics[width=.5\textwidth ]{arxiv2-28}
\centering
\vspace{-.5cm}
\caption{Relative optimal squared error for three vales of graph connectivity ratio: $p_c \in \{0.1,0.5,1\}$, compared with the order of upper bound.}
\label{graph_plot}
\end{figure}

\fi

\subsection{Logistic regression}
To further evaluate the proposed method with other benchmarks, in this section we consider the logistic regression where the goal is to learn a classifier $\bx$ to predict the labels $b_{j} \in \{+1,-1\}$. More specifically, consider the regularized logistic regression problem as follows:

\begin{equation} \label{eq:logisticreg}
    \min_{\bx \in \mathbb{R}^p} f(\bx) =
    \frac{1}{n} \sum_{j=1}^{D} \log \left( 1 + \exp \left(- b_j \mathbf{a}_{j} \bx \right) \right)
    +
    \frac{\lambda}{2} \norm{\bx}_2^2,
\end{equation}

where $b_j \in \{+1,-1\}$ denotes the label of the $j$th data-point corresponding to the feature vector $\mathbf{a}_{j} \in \mathbb{R}^{1 \times p}$. The total $D$ data-points are distributed among the $n$ nodes such that each node is assigned with $d=D/n$ samples. The underlying network is an Erd\"{o}s-R\'enyi graph with $n=50$ nodes and connectivity probability $p_c=0.45$. We generate a data-set of $D=5000$ samples as follows. Each sample with label $+1$ is associated with a feature vector of $p=4$ random gaussian entries with mean $\mu$ and variance $\gamma^2$. Similarly, samples with labels $-1$ are associated with a feature vector of random gaussian entries with mean $-\mu$ and variance $\gamma^2$. We let $\mu=3$ and $\gamma^2=1$.

In the implementation of the QDGD method, we pick the parameter $\delta=0.45$ and accordingly  pick the stepsizes $\eps={c_1}/{T^{3\delta/2}}$ and $\al = {c_2}/{T^{\delta/2}}$ where the constants $c_1,c_2$ are finely tuned.

As a benchmark, we compare our proposed QDGD method with the naive DGD algorithm \cite{yuan2016convergence} in which we let the nodes exchange quantized decision variables. That is, the update rule at node $i$ and iteration $t$ in this benchmark is

\begin{equation}\label{eq:DGDwQ}
    \bx_{i,t+1} =   w_{ii} \bx_{i,t} + \sum_{ j \in  \mathcal{N}_i } w_{ij} \bz_{j,t} - \al \gr f_i(\bx_{i,t}),
\end{equation}

where we pick the stepsize $\al = c/T$ with finely tuned constant $c$.

In both methods, we use the low-precision quantizer in \eqref{eq:low_per_def} with $s$ levels of quantization. Note that unlike the proposed QDGD, the update rule in this benchmark employs only one step-size $\al$. In addition to this comparison, we illustrate the effect of the quantization level $s$ on the convergence of the two methods. Fig. \ref{logistic_plot} demonstrates the loss values resulting from the two methods for five picks of $T \in \{750,1000,1250,1500,1750\}$. As we mentioned earlier, the proposed QDGD is an exact method, i.e. the local models converge to the global optimal model with any desired optimality gap. However, a naive generalization of the existing methods (e.g. DGD) with quantization (e.g. in \eqref{eq:DGDwQ}) will result in a convergence to a neighborhood of the global optimal.

Fig. \ref{logistic_plot} also shows that for less noisy quantizers (larger $s$), nodes receive more accurate models from the neighbors and hence they achieve a smaller loss within a fixed number of iterations.

\begin{figure}[t]
\includegraphics[width=.5\textwidth ]{logistic.pdf}
\centering
\caption{Comparing the proposed QDGD method and the naive DGD with quantization (see \eqref{eq:DGDwQ}); and varying the quantizations levels $s \in \{1,20\}$.}
\label{logistic_plot}
\end{figure}


TITLE: Help proving $I^2$ is a principal ideal and $I$ isn't with $I=(x,y-1)$ in the ring $R := \mathbb{R}[x,y]/(x^2+y^2-1)$
QUESTION [2 upvotes]: So we have this ring $R := \mathbb{R}[x,y]/(x^2+y^2-1)$ with an ideal $I=(x,y-1)$ generated by the elements $x$ and $y-1$. I'm having trouble proving that $I^2=(x^2,x(y-1),(y-1)^2)$ is a principal ideal, because the gcd of those elements is 1. But the ideal $I^2=(1)$ is just $R$, so I dont know if that's a principal ideal. I'm also having trouble proving that $I$ is not a principal ideal, because their gcd is also $1$. So if I say that it isn't a principal ideal because their gcd is $1$ then i'm contradicting my first "proof". Is there any chance my ideal $I^2$ is wrong, from what I understood the square of an ideal generated by 2 elements $a,b$ is (a^2,ab,b^2), but I may be wrong. Does anybody have any tips?

REPLY [3 votes]: Actually $I^2 \neq (1)$ (indeed the gcd of $x$ and $y-1$ is $1$ so if your argument were correct we'd have $I = R$, which is not the case because $R/I \cong \mathbb{R} \neq 0$.). This idea only works in Euclidean domains, where you can use the division algorithm to prove that $(a,b) = (\gcd(a,b))$. There is no division algorithm in $R$, so that doesn't hold here!
To clarify a couple points from your post:

$R$ certainly is a principal ideal of $R$. Remember that a principal ideal is just any ideal of the form $(r) = \{rx : x \in R\}$ for some $r \in R$. Since $R = (1)$, this is principal.

You're correct that $(a,b)^2 = (a^2, ab, b^2)$. Indeed, generally we have that $(x_1, \dots, x_n)^2$ is the ideal generated by all products $x_i x_j$ where $i,j \in \{1, \dots, n\}$. You should try to prove this! Hint: show both sets are subsets of one another.

Anyway, to show that $I^2$ is principal, you should try to find some element $p \in R$ such that the image of $I$ is $0$ under the quotient $R \to R/(p)$ – this will tell you that $I^2 \subseteq (p)$, and you will only need to prove $p \in I^2$ to conclude that $I^2 = (p)$. To show that $I$ is not principal, you could try to argue by contradiction: e.g. it's possible to prove that $R/(p) \not\cong \mathbb{R} \cong R/I$ for any $p \in R$ (first of all, if $R/(p) \cong \mathbb{R}$ then $(p)$ is maximal...).
If you know anything about algebraic geometry, you can gain a lot of intuition here by noting that $R$ is the coordinate ring of the circle.


TITLE: Determinants order of operations
QUESTION [1 upvotes]: When computing determinants using their properties, what is the order in which the determinant gets evaluated?
Ie.   \begin{vmatrix}
        2AA^t \\
        \end{vmatrix}
Do we start with $2A$ or $A^t$?
similarly for this one:
\begin{vmatrix}
        2A^t(A^{-1})^2 \\
        \end{vmatrix}
Do we start with $2A^t$ or $(A^{-1})^2$?

REPLY [1 votes]: Let $n$ be the size (number of rows or of columns) of matrix $A$.
For the first question, I would use this before any calculation:
$$|2AA^\top|=2^n|A|\cdot |A^\top|$$
$$=2^n|A|\cdot |A|$$
$$=2^n|A|^2$$
For the second question, I would use this before any calculations:
$$|2A^\top(A^{-1})^2|=2^n|A^\top|\cdot|A^{-1}|^2$$
$$=2^n|A|\cdot|A|^{-2}$$
$$=2^n|A|^{-1}$$
Then I would do the calculations. These work due to the identities
$$|AB|=|A|\cdot |B|$$
$$|A^{-1}|=|A|^{-1}$$
$$|A^\top|=|A|$$
$$|cA|=c^n|A|$$


TITLE: integer matrices with non-real spectra
QUESTION [5 upvotes]: I am interested in infinite order elements $A\in SL(3, {\mathbb Z})$ whose spectra are not contained in ${\mathbb R}$ (i.e. such $A$ has two distinct complex-conjugate eigenvalues which are not roots of unity); I will refer to them as NRS matrices.
Question. Is there a pair of commuting NRS matrices $A, B\in SL(3,  {\mathbb Z})$ whose product is again an NRS matrix, such that $A, B$ generate a non-cyclic subgroup of $SL(3, {\mathbb Z})$?
As the last resort, one can look for such matrices by computer-search, but I would prefer to avoid doing this.

REPLY [8 votes]: There are no such pairs.
Let $\lambda_1$, $\lambda_2$, $\lambda_3$ be the eigenvalues of $A$, and $\mu_1,\mu_2,\mu_3$ be those of $B$ (with $\lambda_1,\mu_1\in\mathbb R$). Since the eigenvalues are distinct, $A$ and $B$ are diagonalizable; since they commute, they are simultaneously diagonalizable, i.e., an eigenbasis for $A$ is also that for $B$. We assume that in a common eigenbasis, $\lambda_i$ corresponds to $\mu_i$ (clearly, $\lambda_1$ corresponds to $\mu_1$ --- because only these eigenvectors may be chosen real).
Now let $e_2$ be an eigenvector for $A$ corresponding to $\lambda_2$. The linear system  defining it has coefficients in $K=\mathbb Q[\lambda_2]$, so we may assume that the elements of $e_2$ are also in $K$. Writing down the condition that $e_2$ is an eigenvector of $B$ (with eigenvalue $\mu_2$) we get that $\mu_2\in K$. Thus $\mathbb Q[\mu_2]=K=\mathbb Q[\lambda_2]$. Moreover, $\lambda_2$ and $\mu_2$ belong to the units group of $K$ --- which, as is known, is cyclic.
Thus $\lambda_2^k=\mu_2^\ell$ for some $k$ and $\ell$, which yields also $\lambda_i^k=\mu_i^\ell$, and hence $A^k=B^\ell$. Thus the subgroup generated by $A$ and $B$ is cyclic.


TITLE: The effect of A/C and global warming
QUESTION [5 upvotes]: I had been thinking about the way an air conditioning system moves heat from one place to another. The unit runs and drops the temp. in the building and raises the temp. outside. Also there is mechanical energy that converts to heat (the compressor and fan motors) and is also put outside. If this is the case, is there an effect caused by A/C systems running on the outside temp.?
Can the total amount of heat being moved from inside to outside contribute to global warming? Consider how many systems there.
As more and more A/C systems are installed and more and more buildings built, can't this lead to (if it hasn't started already) a higher temp outside?
I am not a scientist; if this question is wrong, I would like to know why.

REPLY [14 votes]: The heat energy being moved does not contribute to any global warming.  The A/C is simply moving energy from inside to outside;  the heat just turns around and flows back into the room, and the total stays the same.  It's like someone trying to keep a leaky boat from sinking; you dump some water over the side, and it (or some just like it) leaks back in. A certain capacity pump can keep the water level in the boat low enough for the boat to survive. The A/C does the same for our houses.
But...
The energy used to drive the A/C is a different matter.  Depending on the source of this electrical energy, there could be a minor contribution to global warming.
If the electricity came from fossil fuels, then the energy is stored solar energy from whenever the fossil fuel was first formed from atmospheric carbon dioxide by plants using sunlight.  You could say that the energy absorbed by plants through photosynthesis kept the earth somewhat cooler than it otherwise would have been, and now we're "correcting" this by burning the fossil fuel back to carbon dioxide.
Here in Ontario, much of our electricity historically came from hydro-electric plants, like Niagara Falls.  Does this contribute to global warming?  Not really...  Sunlight (energy) falls on the ocean.  Some of this energy warms the water.  The rest evaporates some water, lifts it kilometers into the air, and lets it fall as rain on elevated land.  As this water flows back to the ocean, it converts its potential energy into kinetic energy, and then into heat.  The water flowing away from Niagara Falls is slightly warmer than the water at the top.  But, if the water goes through a generator on its way down, electrical energy is extracted, and the water is cooler than it otherwise would be.  So, the heat produced in Toronto by using electricity is exactly balanced by the slightly cooler Niagara River.  Eventually all the water makes it back to the ocean, and all the original solar energy is converted to heat...
As commented by @AlanSE, the negative effect of the carbon dioxide in the atmosphere greatly outweighs these energy transfer effects...


TITLE: Adiabatic free expansion (Joule expansion) needing a small explanation
QUESTION [0 upvotes]: My professor tries to demonstrate that adiabatic free expansion is an irreversible process:

for and adiabatic $Q=0$;

because the gas is expanding through vacuum W=0;

therefore $\Delta U=Q-W=0$
now I can put back the gas doing work on it: $W=p\Delta V$,
because $\Delta V$ is negative $W$ is negative too, so $\Delta U=-W$ we have an increment of the internal energy.
$U=U(T)$, $\Delta U=\frac32nR\Delta T$ so if the ΔU is positive $\Delta T$ is positive too,
now arrive the thing that I haven't understood, my professor said:
a) We can extract $Q=W$
b) $Q\rightarrow W$ isn't possible for the second law of thermodynamics, therefore, a free adiabatic expansion is not reversible.
I understand the second law of thermodynamics, I don't understand the passage from point a) to point b).

REPLY [1 votes]: Your professor is saying that step b returns the gas to its original state that existed before the expansion and reversible recompression.  So, overall, you have carried out a cycle (on the system), the net result of which is to take heat from a single source and produce an equal amount of work.  (Incidentally, in the reversible expansion, you are supposed to be using a constant temperature reservoir, such that the internal energy doesn't change during the expansion, and the change in U is zero throughout the expansion.).
According to the second law, with a cyclic process, receiving heat from a single source at a constant temperature and converting it to work is not allowed.
EDIT ADDED TO INCORPORATE VALUABLE COMMENTS of @BobD BELOW
In the case of the present cycle, the gas receives work from the surroundings (does negative work) and rejects heat to the surroundings.  This is not prohibited by the 2nd law of thermodynamics.  The 2nd law only prohibits receiving heat from a single source at constant temperature and doing an equal amount of work in a cycle.  So the professor's analysis says nothing about the reversibility of the expansion.