text:
\section{Preliminaries}\label{sec:preliminaries}
First we recall the well-known definition of the Bregman distance, the primal-dual formulation for \eqref{eq:separable_convex}, and a variational inequality characterization for the optimality condition of \eqref{eq:separable_convex}, which will be used in the sequel.

\subsection{Basic notation}\label{subsec:basic_notation}
Given a proper, closed and convex function $f$, we denote $\dom{f} := \set{\xb\in\R^n~|~f(\xb) <+\infty}$ the domain of $f$, $\partial{f}(\xb) := \{\vb\in\R^n ~|~ f(\tilde{\xb}) - f(\xb) \geq \vb^T(\tilde{\xb} - \xb), ~\forall \tilde{\xb}\in\dom{f}\}$ the subdifferential of $f$ at $\xb$. If $f$ is differentiable, $\nabla{f}(\xb)$ denotes the gradient of $f$ at $\xb$.
For given vector $\xb\in\R^n$, we define $\norm{\xb}_2$ the Euclidean norm of $\xb$.
We use a superscripted notation $L^f > 0$ to denote the corresponding Lipschitz constant of a differentiable function $f$. Similarly,  we use a subscripted notation $\sigma_g > 0$ to denote the corresponding strong convexity constant of a convex function $g$.

\subsection{Proximity functions and Bregman distances}\label{subsec:prox_bregman}
Given a nonempty, closed convex set $\Xc$, a nonnegative, continuous and $\sigma_b$-strongly convex function $b$ is called a \textit{proximity} function (or prox-function) of $\Xc$ if $\Xc\subseteq \dom{b}$.
For example, the simplest prox-function is $b_{\Xc}(\xb) := (\sigma_b/2)\norm{\xb - \xb_c}^2_2$ for any $\sigma_b > 0$ and $\xb_c\in\Xc$.
Whenever unspecified, we use this specific prox-function with $\sigma_b = 1$.

Given a smooth prox-function $b$ of $\Xc$ with the parameter $\sigma_b > 0$. We define
\begin{equation}\label{eq:bregman_distance}
d_b(\xb, \yb) := b(\xb) - b(\yb) - \nabla{b}(\yb)^T(\xb - \yb), ~~\forall \xb, \yb\in\dom{b},
\end{equation}
the Bregman distance between $\xb$ and $\yb$ with respect to $b$.
Given a matrix $\Sb$, we also define the projected prox-diameter of a given set $\Xc$ with respect to $d_b$ as
\begin{equation}\label{eq:bregman_diameter}
D^{\Sb}_{\Xc} := \sup_{\xb, \xb_c\in\Xc} d_b(\Sb\xb, \Sb\xb_c).
\end{equation}
Here, we project the set $\Xc$ onto the range space of matrix $\Sb$. If $\Xc$ is bounded, then $0 \leq D^{\Sb}_{\Xc} < +\infty$.
For $b(\xb) := (\sigma_b/2)\norm{\xb - \xb_c}^2_2$, we have $d_b(\xb, \yb) = (\sigma_b/2)\norm{\xb-\yb}_2^2$, which is indeed the Euclidean distance.

\subsection{Primal-dual formulation}\label{subsec:primal_dual_formulation}
We write the min-max formulation of \eqref{eq:separable_convex} based on the Lagrange dualization as follows:
\begin{equation}\label{eq:min_max}
\max_{\yb\in\R^m}\min_{\xb\in\Xc}\Lc(\xb, \yb) \equiv \max_{\yb\in\R^m}\min_{\xb\in\Xc} \{ f(\xb) + \yb^T(\Ab\xb - \bb) \},
\end{equation}
where $\Lc$ is the Lagrange function and $\yb$ is the dual variable. We write the dual function $g(\yb)$ as
\begin{equation}\label{eq:dual_func}
g(\yb) := \min_{\xb\in\Xc}\{  f(\xb) + \yb^T(\Ab\xb - \bb) \},
\end{equation}
which leads to the following definition of the so-called dual problem
\begin{equation}\label{eq:dual_prob}
g^{\star} := \max_{\yb\in\R^m} g(\yb).
\end{equation}

Let $\xb^{\star}(\yb)$ be a solution of \eqref{eq:dual_func} at a given $\yb\in\R^m$.  Corresponding to $\xb^{\star}(\yb)$, we also define the domain of $g$ as
\begin{equation}\label{eq:dom_g}
\dom{g} := \set{ \yb\in\R^m ~|~ \xb^{\star}(\yb) ~\textrm{exists}}.
\end{equation}
If $f$ is continuous on $\Xc$ and if $\Xc$ is compact, then $\xb^{\star}(\yb)$ exists for any $\yb\in\R^m$.
Unfortunately, the dual function $g$ is typically nonsmooth, and hence the numerical solutions of \eqref{eq:dual_prob} are usually difficult \cite{Nesterov2004}.
In general, we have $g(\yb) \leq f(\xb)$, which is known as weak-duality in convex optimization. In order to guarantee strong duality, i.e., $f^{\star} = g^{\star}$ for \eqref{eq:separable_convex} and \eqref{eq:dual_prob}, we require the following assumption:

\begin{assumption}\label{as:A1}
The constraint set  $\mathcal{X}$ and the solution set $\mathcal{X}^{\star}$  of \eqref{eq:separable_convex} are nonempty.
The function $f$ is proper, closed and convex.
In addition, either $\mathcal{X}$ is a polytope or the following Slater condition holds:
\begin{equation}\label{eq:slater_cond}
\set{\xb \in\mathbb{R}^n ~|~ \Ab\xb = \bb} \cap \mathrm{relint}(\Xc) \neq \emptyset,
\end{equation}
where $\mathrm{relint}(\mathcal{X})$ is the relative interior of $\mathcal{X}$.
\end{assumption}

Under Assumption \ref{as:A1}, the solution set $\Yc^{\star}$ of the dual problem \eqref{eq:dual_prob} is also nonempty and bounded. Moreover, the strong duality holds, i.e., $f^{\star} = g^{\star}$. Any point $(\xb^{\star}, \yb^{\star})\in\Xc^{\star}\times\Yc^{\star}$ is a primal-dual solution to \eqref{eq:separable_convex} and \eqref{eq:dual_prob}, and is also a saddle point of the Lagrange function $\Lc$, i.e., $\Lc(\xb^{\star},\yb) \leq \Lc(\xb^{\star}, \yb^{\star}) \leq \Lc(\xb, \yb^{\star})$ for all $\xb\in \Xc$ and $\yb\in\R^m$.
These inequalities lead to the following estimate
\begin{equation}\label{eq:pd_lower_bound}
f(\xb) - g(\yb) \geq f(\xb) -  f^{\star}  \geq -\norm{\yb^{\star}}_2\norm{\Ab\xb - \bb}_2, ~~\forall \xb\in\Xc, ~\yb\in\R^m.
\end{equation}
Our goal in this paper is to solve the primal constrained problem  \eqref{eq:separable_convex}, while numerical algorithms only give an approximate solution up to a certain accuracy.
Hence, we  need to specify the concept of an approximate solution for \eqref{eq:separable_convex}.
\begin{definition}\label{de:approx_sol}
Given a target accuracy $\varepsilon \geq 0$, a point $\tilde{\xb}^{\star}\in\Xc$ is said to be an $\varepsilon$-solution of \eqref{eq:separable_convex} if $ \abs{f(\tilde{\xb}^{\star}) - f^{\star}} \leq \varepsilon$ and $\Vert\Ab\tilde{\xb}^{\star} - \bb\Vert_2 \leq \varepsilon$.
\end{definition}
Here, we assume in Definition \ref{de:approx_sol} that $\tilde{\xb}^{\star}\in\Xc$, i.e., $\tilde{\xb}^{\star}$ is exactly feasible to $\Xc$. This requirement is reasonable in practice since $\Xc$ is usually a ``simple'' set where the projection onto $\Xc$ can be computed exactly.
Moreover, we can use different accuracy levels for the absolute value of the primal objective residual $\abs{f(\tilde{\xb}^{\star}) - f^{\star}}$ and the primal feasibility gap $\Vert\Ab\tilde{\xb}^{\star} - \bb\Vert_2$ in Definition \ref{de:approx_sol}.

\subsection{Mixed-variational inequality formulation and gap function}
Let $\wb := (\xb, \yb) \equiv (\xb^T, \yb^T)^T \in\R^n\times \R^m$ be the primal-dual variable and $F(\wb) := \begin{pmatrix}\Ab^T\yb\\ \bb - \Ab\xb\end{pmatrix}$ be a partial Karush-Kuhn-Tucker  mapping.
Then, the optimality condition of \eqref{eq:separable_convex} becomes
\begin{equation}\label{eq:VIP}
f(\xb) - f(\xb^{\star}) + F(\wb^{\star})^T(\wb - \wb^{\star}) \geq 0, ~~ \forall \wb \in\Xc\times \R^m,
\end{equation}
which is known as a \textit{mixed-variational inequality} \cite{Facchinei2003}.
If we define
\begin{equation}\label{eq:gap_func}
G(\wb^{\star}) := \max_{\wb\in\Wc :=\Xc\times \R^m}\set{f(\xb^{\star}) - f(\xb) + F(\wb^{\star})^T(\wb^{\star} - \wb)},
\end{equation}
then $G$ is known as the Auslender gap function of \eqref{eq:VIP} \cite{Auslender1976}.

Let $\Wc := \Xc \times \R^m$. Then, by the definition of $F$, we can see that
\begin{equation*}
G(\wb^{\star}) = \displaystyle\max_{(\xb, \yb)\in\Wc}\set{f(\xb^{\star})  + \yb^T(\Ab\xb^{\star} - \bb) - f(\xb) - (\Ab\xb - \bb)^T\yb^{\star}} = f(\xb^{\star}) - g(\yb^{\star}) \geq 0.
\end{equation*}
It is clear that $G(\wb^{\star}) = 0$ if and only if $\wb^{\star} := (\xb^{\star}, \yb^{\star}) \in \Wc^{\star} := \Xc^{\star}\times\Yc^{\star}$, which is indeed the \textit{strong duality} property.

config: arxiv


TITLE: Dirac delta and test functions
QUESTION [1 upvotes]: By the use of the test functions prove that:
$$f(t) \delta '(t) = f(0) \delta '(t) - f'(0) \delta(t)$$
Attempt:
I want to use some test function $\phi (t)$. So starting from
$$\langle f \delta' , \ \phi \rangle = \int^\infty_{-\infty} f(t)\delta'(t) \phi(t) \ dt$$
Using integration by parts:
$$= \Big[ f'(t) \delta (t) \phi (t) \Big]^\infty_{-\infty} - \int^\infty_{-\infty} f'(t) \delta (t) \phi'(t) \ dt$$
I'm stuck here. The aim is to arrive at $\langle f(0) \delta' - f'(0) \delta, \ \phi \rangle$.
I am not sure how to proceed. I think I will need to use the $\langle \delta, \phi \rangle = \phi(0)$ property at some point.
What do I need to do?
Any help is greatly appreciated.

REPLY [1 votes]: I guess you are using physicist's notations, however the dirac distribution is not associated to a locally-integrable function.
Actually using the definitions, we get quickly the answer. Let $\varphi$ be a test function, one has : $$\langle f\delta', \varphi \rangle=\langle \delta', f\varphi \rangle = -\langle \delta, (f\varphi)' \rangle = -\langle \delta, f'\varphi \rangle-\langle \delta, f\varphi' \rangle= -f'(0)\varphi(0)-f(0)\varphi'(0).$$ But $$f'(0)\varphi(0)=f'(0)\langle\delta,\varphi \rangle$$ and $$f(0)\varphi'(0)=-f(0)\langle \delta',\varphi \rangle,$$ hence $$f\delta' =f(0)\delta'-f'(0)\delta.$$


TITLE: Finding $u_0(x,y)$ for Laplace's Equation
QUESTION [1 upvotes]: I looked at this resource to help me solve the below problem, but I still have questions on some parts.
Problem

My Questions
To solve Laplace's equation, I assumed $u(x,y) = X(x)Y(y)$.
For $\lambda = 0$, when solving $X'' = 0$, I get $X(x)=c_2$. However, for λ = 0, the solutions says $X = 1$- how?
For $\lambda = 0$, $Y(y)= k_1y + k_2$, but the solution says $u_0(x,y) = y$. What happened to $k_2$?

REPLY [2 votes]: To provide some context, the resource quoted uses separation of variables. Using an ansatz of the form $u(x,t) = X(x)Y(y)$, one obtains a pair of ODEs,
$$ X''(x) + \lambda X(x) = 0, \ \ \ \ \ \ Y''(y) - \lambda Y(y) = 0.$$
These ODEs have solutions for various values of $\lambda$, and the full solution to the PDE is a linear superposition of $X_\lambda (x)Y_\lambda (y)$ for the various values of $\lambda$. The OP's questions seek clarification specifically about the contribution with $\lambda = 0$.
First, let's deal with the $Y(y)$ equation. It is true that the general solution to $Y''(y)  = 0$ is $Y(y) = k_1  y + k_2$. However, since $u(x,y)$ satisfies the boundary condition $u(x,0) = 0$, we want $Y(y)$ correspondingly to satisfy the boundary condition $Y(0) = 0$. This implies that $k_2 = 0$. So we have $Y(y) = k_1 y$.
Next, the solution to the $X(x)$ equation satisfying the appropriate boundary conditions is indeed $X(x) = c_2$. So the full $\lambda = 0$ solution is
$ u_{\lambda = 0}(x,t) = c_2 k_1 y.$
However, since both $c_2$ and $k_1$ are constants, we may as well redefine them, setting
$ c_{2, {\rm \ new}} = 1$ and $k_{1, {\rm \ new }} = c_{2, {\rm \ old }} \times k_{1,{\rm \ old}}$. This redefinition makes no difference to the solution.
For completeness, the full solution, including contributions from other values of $\lambda$, looks like
$$ u(x,y) = a_0 y + \sum_{n = 1}^\infty a_n \cos \frac{n \pi x }{a} \sinh \frac{n \pi y}{b},$$
(so $a_0$ is the same thing as $c_{2, {\rm \ old}} \times k_{1, {\rm \ old}}$), and the coefficients $a_n$ and $b_n$ are to be determined by comparison with the Fourier expansion of the $g(x)$ function appearing in the boundary condition at $y = b$.


TITLE: What's the measure of the angle that forms the straight Euler line and the circle that passes through B?
QUESTION [2 upvotes]: For reference(exact copy of the question): In a triangle with acute angle $ABC$. the straight line of Euler determines with its sides an inscribed quadrilateral. Find the measure of the angle that forms the straight Euler line and the circumradius that passes through B.(answer: $90^o$)
My progress::
I confess that I didn't understand the question well... I made the drawing below but only in function of the answer and I'm not sure if that's what the elucidate is asking... But I can't imagine how to solve it from a generic drawing.

Resolution figure by MathLover:

REPLY [3 votes]: The question says $AMNC$ is an inscribed quadrilateral, so $\angle AMN = 180^\circ - \angle C$.
$\implies \angle BMO = \angle C$
Also as $O$ is the circumcenter of $\triangle ABC$, $\angle AOB = 2 \angle C$ and as $\triangle AOB$ is isosceles,
$\angle MBO = \angle BAO = \frac{180^\circ - 2 \angle C}{2} = 90^\circ - \angle C$
That leads to $\triangle BOM$ being a right triangle and $\angle BOM = 90^\circ$.
Also note that this is possible when $\angle ABC$ is acute and the Euler line passes through the sides of $\angle ABC$ such that $AMNC$ is cyclic. In other words, $A$ and $C$ should be the vertices of the quadrilateral and not $B$.


TITLE: Circuit with three capacitors and a switch
QUESTION [2 upvotes]: I have a homework problem where I have a battery connected to a capacitor and a switch that connects the capacitor to 2 others in series/disconnects the circuit from the battery.
The question is:

S is initially closed to the left until c1 is completely charged. Once charged, it closes to the right and remains closed there until it reaches equilibrium. Calculate the difference in potential of c1.

I'm stumped because I don't know how the charges distribute between the three capacitors once the circuit is closed, and so I'm not able to calculate the final voltage. I probably didn't do too good of a job translating the text so if you don't understand ask. Thank you.

REPLY [2 votes]: Remember: Capacitors in parallel all have the same voltage across their plates, but can have different charges.
So, when the switch is closed to the left, C1 is has a certain charge and voltage. Then, when the switch is closed to the right, that charge in C1 distributes in such a way so that the voltage across all three capacitors is equal.
You can intuitively justify it this way—imagine if one of the three capacitors had a lower voltage. We know that electrons will move from higher potential to lower potential (like a ball rolling from the top of a hill to the bottom); so if one of the three capacitors had a different voltage, charge would just redistribute itself (since all of the lower plates are connected to one another) until none of the capacitors had a lower voltage; that is, until they all had the same voltage.
You should be able to solve the problem using this, and the various rules for capacitors connected to one another.

REPLY [1 votes]: The total charge on $C_1$ ends up distributed across the three capacitors, so that the final voltage on the three of them will be the same.
Now you know that $Q=CV$. When the switch is thrown, the total charge $Q$ is the same, but the capacitance $C$ becomes 5 times greater (10+20+20).


text:
\begin{document}

\title{Stable characters from permutation patterns}
\author{Christian Gaetz}
\thanks{C.G. is supported by a National Science Foundation Graduate Research Fellowship under Grant No. 1122374.}
\address{Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA.}
\email{\href{mailto:gaetz@mit.edu}{gaetz@mit.edu}}

\author{Christopher Ryba}
\email{\href{mailto:ryba@mit.edu}{ryba@mit.edu}}
\date{\today}

\begin{abstract}
For a fixed permutation $\sigma \in S_k$, let $N_{\sigma}$ denote the function which counts occurrences of $\sigma$ as a pattern in permutations from $S_n$.  We study the expected value (and $d$-th moments) of $N_{\sigma}$ on conjugacy classes of $S_n$ and prove that the irreducible character support of these class functions stabilizes as $n$ grows.  This says that there is a single polynomial in the variables $n, m_1, \ldots, m_{dk}$ which computes these moments on any conjugacy class (of cycle type $1^{m_1}2^{m_2}\cdots$) of any symmetric group.  This result generalizes results of Hultman \cite{Hultman2014} and of Gill \cite{Gill2013}, who proved the cases $(d,k)=(1,2)$ and $(1,3)$ using ad hoc methods.  Our proof is, to our knowledge, the first application of partition algebras to the study of permutation patterns.
\end{abstract}

\maketitle

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

A permutation $\pi=\pi_1 \cdots \pi_n$ in the symmetric group $S_n$ is said to \emph{contain the pattern} $\sigma=\sigma_1 \cdots \sigma_k \in S_k$ if there exist indices $1 \leq i_1 < \cdots < i_k \leq n$ such that $\pi_{i_a}<\pi_{i_b}$ if and only if $\sigma_a < \sigma_b$;
in this case we say $(i_1,\ldots,i_k)$ is an \emph{occurrence} of $\sigma$.  If $\pi$ does not contain any occurrences of $\sigma$, then it is said to \emph{avoid} $\sigma$.

One of the earliest prominent results in the theory of permutation patterns was Knuth's \cite{Knuth} characterization of ``stack-sortable" permutations as those avoiding the pattern $\sigma=231$.  Since then, permutation patterns have been found to play an important role in many settings where algebraic or geometric objects are indexed by permutations, being ubiquitous in the study of Schubert varieties, Bruhat order, and Kazhdan--Lusztig polynomials \cite{Abe-Billey}.  The study of permutation patterns has grown into a very active field in its own right.

We write $N_{\sigma}(\pi)$ for the number of occurrences of $\sigma$ in $\pi$, and view
\[
N_{\sigma}: \coprod_{n \geq 1} S_n \to \N
\]
as a function on all symmetric groups at once.  These pattern counting functions are very well studied (see, e.g. \cite{Bona-textbook}).  In particular, it was shown by Janson, Nakamura, and Zeilberger \cite{Janson-Nakamura-Zeilberger} that the distribution of $N_{\sigma}$ on a uniformly random permutation from $S_n$ is asymptotically normal, and by Zeilberger that the moments of this distribution are given by polynomials in $n$ \cite{Zeilberger}.  Theorem~\ref{thm:main} refines this polynomiality result by showing that there is a polynomial which computes these moments for all conjugacy classes of all symmetric groups; Corollary~\ref{cor:recover-zeilberger} recovers Zeilberger's result.

One area of recent interest is the, as yet poorly understood, interaction between permutation patterns and the group structure of symmetric groups, which has proven quite difficult to understand.  For example, Richard Stanley asked in 2007 for an enumeration of cyclic permutations in $S_n$ avoiding a given pattern from $S_3$; despite the fact that the total number of avoiders for each of these patterns is well-known to be given by the Catalan numbers, only partial progress has been made on Stanley's question \cite{Archer-Elizalde, Bona-Cory} with none of the cases completely resolved.  Other examples include the study of permutation patterns in involutions \cite{invol2, invol1} and in powers of a given permutation \cite{Bona-Smith}.

Hultman \cite{Hultman2014} observed how turning permutation statistics (such as $N_{\sigma}$) into virtual $S_n$-characters allows for computation of their expected values on random permutations drawn from various distributions.  Computing these characters directly requires understanding occurrences of $\sigma$ in every conjugacy class, a problem which is considered difficult by experts.  Hultman and later Gill \cite{Gill2013} were able to compute these characters for $\sigma \in S_2$ and $\sigma \in S_3$, respectively, via some case work, but this direct enumeration is clearly infeasible for longer patterns $\sigma$ and for higher moments $N^d_{\sigma}$ of the pattern counting functions.  Theorem~\ref{thm:main} and its proof using partition algebras give a uniform framework for understanding these characters for all $\sigma$ and for all $d$.  In particular we give a conceptual explanation for the curious fact, noted by Hultman and Gill, that the irreducible character supports in the cases they computed are surprisingly small, and stabilize as $n$ grows.

\subsection{Permutation pattern polynomials}
\label{sec:intro-ppp}

For a fixed permutation $\sigma \in S_k$, and positive integers $d,n$, we define a class function $M_{\sigma, d, n}: S_n \to \N$ by
\begin{equation}
\label{eq:M-def}
M_{\sigma,d,n}(\pi)=\frac{1}{|C_{\pi}|} \sum_{\pi' \in C_{\pi}} N_{\sigma}^d(\pi'),
\end{equation}
where $C_{\pi}$ denotes the conjugacy class of $\pi \in S_n$.  That is, $M_{\sigma,d,n}(\pi)$ is the (raw) $d$-th moment of the random variable $N_{\sigma}$ when permutations are chosen uniformly at random from $C_{\pi}$.  In the case $d=1$ and $k=2,3$ this function has previously been studied by Hultman \cite{Hultman2014} and by Gill \cite{Gill2013}.  Conjugacy classes in the symmetric group are determined by the cycle types of permutations; for $i=1,2,\ldots$ we write $m_i$ for the function on $\coprod_{n \geq 1} S_n$ taking $\pi$ to the number of $i$-cycles in its cycle decomposition.

By definition $M_{\sigma, d, n}$ is a class function on $S_n$, and thus it may be uniquely written as a linear combination of the irreducible characters of $S_n$.  These irreducible characters $\chi^{\lambda}$ are well-known to be indexed by integer partitions $\lambda=(\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_{\ell} \geq 0)$ with $|\lambda|:=\sum_i \lambda_i=n$.  We write $\Y$ for \emph{Young's lattice}, the set of partitions of all positive integers, and $\Y_n$ for the set of partitions of $n$.  Whenever $n-|\lambda|\geq \lambda_1$, we write $\lambda[n]$ for the partition $(n-|\lambda|, \lambda_1, \cdots, \lambda_{\ell})$ of $n$.

Our main result is Theorem~\ref{thm:main}, which shows that---although the functions $M_{\sigma, d, n}$ are not obviously related to one another as $n$ grows---in fact they ``stabilize" in a well-defined sense.  In particular, the values of $M_{\sigma,d,n}$ for all conjugacy classes in all symmetric groups $S_n$ may be determined knowing only the values in small symmetric groups.  The proof takes advantage of new techniques for understanding permutation patterns in conjugacy classes using partition algebras.

Partition algebras are well known to play a role in ``representation stability phenomena'', for example, they are endomorphism algebras in the Deligne category $\underline{\mathrm{Rep}}(S_t)$ (see \cite{ComesOstrik}). The Deligne category is a category depending on a parameter $t$ which ``interpolates'' the representation categories of symmetric groups $S_n$, and results about $\underline{\mathrm{Rep}}(S_t)$ imply results for all symmetric groups. Given that the partition algebras play a key role in the proof of our main result (Theorem \ref{thm:main}), it would be interesting to see whether there are other connections between permutation patterns and the active area of representation stability (see \cite{SamSnowden} for a survey of other aspects of representation stability).

As we will see, the family $M_{\sigma, d, n}$ behaves nicely as $n$ varies.  It will therefore sometimes be convenient to think of the family as defining a single function
\[
M_{\sigma,d}: \coprod_{n} S_n \to \N.
\]

\begin{theorem}
\label{thm:main}
Let $\sigma \in S_k$, and $d \geq 1$, then:
\begin{enumerate}[label=(\alph*)]
    \item \label{part:polynomial} $M_{\sigma, d}(\pi)$ is a polynomial in the variables $n, m_1(\pi), m_2(\pi), \ldots, m_{dk}(\pi)$ of degree at most $dk$, where $n$ has degree $1$ and $m_i$ has degree $i$.
    \item \label{part:stable} For all $n \geq 2dk$ we have an equality of class functions
\[
M_{\sigma, d, n} = \sum_{\substack{\lambda \in \Y \\ |\lambda|\leq dk}} a^{\lambda}_{\sigma,d}(n) \chi^{\lambda[n]}
\]
for some family of polynomials $a^{\lambda}_{\sigma, d} \in \Q[n]$ of degree at most $dk-|\lambda|$.
\end{enumerate}
\end{theorem}

\begin{remark}
Theorem~\ref{thm:main} is far from obvious from the definitions; indeed it is not even clear a priori that $M_{\sigma, d}(\pi)$ should be determined by $n,m_1(\pi),\ldots,m_{dk}(\pi)$ alone.
\end{remark}

As a very special case of Theorem~\ref{thm:main}, we also recover a result of Zeilberger.

\begin{cor}[Zeilberger \cite{Zeilberger}]
\label{cor:recover-zeilberger}
The $d$-th moment of $N_{\sigma}$ on all of $S_n$ (rather than refined by conjugacy class, as in $M_{\sigma, d, n}$) is given by a polynomial in $n$, provided $n \geq 2dk$.
\end{cor}
\begin{proof}
By definition the desired moment is
\begin{align*}
    \frac{1}{n!}\sum_{\pi \in S_n} N_{\sigma}^d(\pi)&=\frac{1}{n!}\sum_{\substack{C \\ \text{conjugacy class}}} \sum_{\pi \in C} N_{\sigma}^d(\pi) \\
    &=\frac{1}{n!}\sum_{\pi \in S_n} M_{\sigma, d, n}(\pi) \\
    &=\langle M_{\sigma, d, n} , \mathbbm{1}_{S_n} \rangle, \\
    &= \sum_{\substack{\lambda \in \Y \\ |\lambda|\leq dk}} a_{\sigma, d}^\lambda(n) \langle \chi^{\lambda[n]} , \mathbbm{1}_{S_n} \rangle,
\end{align*}
where $\langle, \rangle$ denotes the inner product of class functions. For $n \geq 2dk$, this is just $a_{\sigma, d}^\varnothing(n)$. By Theorem~\ref{thm:main} this is a polynomial.
\end{proof}

Theorem~\ref{thm:main} also allows for the computation of moments of $N_{\sigma}$ on non-uniformly random permutations, such as products of random transpositions; as observed by Hultman \cite{Hultman2014}, this reduces to computing the character inner product of $M_{\sigma, d, n}$ and another character.  Since part \ref{part:stable} of the theorem implies that the support of $M_{\sigma, d, n}$ stabilizes, such inner products become tractable finite sums, whereas the analogous sums for permutation statistics other than $N_{\sigma}$ may gain more terms as $n$ increases.
\\

The remainder of the paper is organized as follows: Section~\ref{sec:partition algebras} contains background material on partition algebras.  Section~\ref{sec:proof-of-main} contains the proof of Theorem~\ref{thm:main}, which connects partition algebras to permutation patterns.

\subsection{Acknowledgements}

We are grateful to Axel Hultman for his help with important references and to Pavel Etingof for his helpful comments.

\section{Partition algebras}
\label{sec:partition algebras}

Partition algebras were first introduced by Martin \cite{Martin} and, independently, Jones \cite{Jones} in connection with statistical mechanics. The partition algebras satisfy a Schur--Weyl-type duality with the symmetric group, which has made the partition algebra an object relevant to the study of representations of symmetric groups (for example, see \cite{Deligne}, \cite{BHH} and \cite{BDO}). An excellent introduction to partition algebras can be found in \cite{ComesOstrik}; every result in this section is explained there, apart from Theorem~\ref{bicharacter_theorem}.

\begin{defin}
A \emph{set partition} $\{U_i\}$ of a set $X$ is a family of subsets $U_i$ of $X$ such that $X$ is the disjoint union of the $U_i$. We say that the $U_i$ are the \emph{parts} of the set partition $\{U_i\}$. We call a set partition of the set $\{1,\ldots, k, 1^\prime, \ldots, k^\prime\}$ a \emph{$(k,k)$-set partition}.
\end{defin}

It is standard to depict set partitions diagrammatically, as this allows for a concise definition of the partition algebras. Given a set partition $\{U_i\}$ of a set $X$, we may consider a graph whose vertices are given by elements of $X$, and whose connected components are precisely the parts $U_i$. Although there are many choices of edges yielding the same connected components, they will be equivalent for our purposes. We will not distinguish between a set partition and a graph representing it, so we will refer to the elements of $U_i$ as ``vertices''.

\begin{defin}
The \emph{partition algebra} $\Par_k(t)$ (where $k \in \mathbb{Z}_{\geq 0}$ and $t \in \mathbb{C}$), as a complex vector space, has a basis consisting of all $(k,k)$-set partitions. The product $P_1 P_2$ of two partitions is computed as follows: Relabel $P_2$ by adding a prime to each element of the underlying set (so it is a set partition of $\{1^\prime, \ldots, k^\prime, 1^{\prime\prime}, \ldots, k^{\prime\prime}\}$). Consider the graph $G(P_1,P_2)$ with vertex set
\[
\{1,\ldots,k,1^\prime, \ldots, k^\prime, 1^{\prime\prime}, \ldots, k^{\prime\prime}\},
\]
which is obtained by identifying each vertex in $\{1^\prime,  \ldots, k^\prime\}$ in $P_1$ with the vertex in $P_2$ bearing the same label (and retaining the edges in both $P_1$ and $P_2$).  Let $c(P_1, P_2)$ be the number of connected components of $G(P_1, P_2)$ consisting only of vertices from $\{1^\prime, \ldots, k^\prime \}$. Then
\[
P_1 P_2 = t^{c(P_1,P_2)} P_3,
\]
where $P_3$ is obtained by removing the elements $\{1^\prime, \ldots, k^\prime\}$ from the set partition corresponding to $G(P_1,P_2)$, and then relabelling all elements with double primes to have single primes.
\end{defin}

\begin{ex}
Suppose we take the $(3,3)$-set partitions $P_1 = \{\{1,1^\prime\},\{2^\prime\},\{2,3,3^\prime\}\}$ and $P_2 = \{\{1\},\{1^\prime\},\{2\},\{2^\prime,3\},\{3^\prime\}\}$ depicted below:
\[
P_1=
\begin{tikzcd}
1\arrow[d, dash, thick]& 2\arrow[r, dash, thick] & 3\arrow[d, dash, thick]\\
1^\prime & 2^\prime & 3^\prime
\end{tikzcd}, \hspace{0.5in}
P_2=
\begin{tikzcd} 1& 2 & 3\arrow[ld,dash, thick]\\
1^\prime & 2^\prime & 3^\prime
\end{tikzcd}.
\]
Then the graph $G(P_1, P_2)$ is
\[
\begin{tikzcd}
1\arrow[d, dash, thick]& 2\arrow[r, dash, thick] & 3\arrow[d, dash, thick]\\
1^\prime & 2^\prime & 3^\prime\arrow[ld, dash, thick] \\
1^{\prime\prime} & 2^{\prime\prime} & 3^{\prime\prime}
\end{tikzcd},
\]
from which we read off the set partition $\{\{1,1^\prime\},\{1^{\prime\prime}\},\{2,3,3^\prime,2^{\prime\prime}\},\{2^\prime\},\{3^{\prime\prime}\}\}$.  Exactly one part consists only of primed vertices, namely $\{2^\prime\}$. Thus $c(P_1,P_2) = 1$. Taking the induced set partition on the top and bottom rows, we get
\[
P_3 =
\begin{tikzcd}
1& 2\arrow[d, dash, thick]\arrow[r, dash, thick] & 3\\
1^\prime & 2^\prime & 3^\prime
\end{tikzcd},
\]
so we conclude $P_1 P_2 = t P_3$.
\end{ex}

\begin{remark}
The partition algebras arise as endomorphism algebras in the Deligne category $\underline{\mathrm{Rep}}(S_t)$, introduced in \cite{Deligne}. These categories ``interpolate'' the representation categories of all of the symmetric groups $S_n$ in a certain sense. We direct the interested reader to \cite{ComesOstrik}.
\end{remark}

The symmetric group $S_n$ tautologically acts on the set $[n] = \{1,2,\ldots, n\}$. We let $V$ be the associated permutation representation, although to avoid confusion we write $v_i$ for the basis vector corresponding to $i \in [n]$. We consider $V^{\otimes k}$, which is simply the permutation representation on the set $[n]^k$. It therefore has a basis consisting of words of length $k$ in the alphabet $[n]$. Given such a word $I = i_1 i_2 \cdots i_k$, we write $v_I = v_{i_1} \otimes v_{i_2} \otimes \cdots \otimes v_{i_k}$.

In analogy with the Schur--Weyl duality map $\mathbb{C}S_k \to \End_{GL(V)}(V^{\otimes k})$, there is a map
\[
\Phi_{k,n}: \Par_k(n) \to \End_{S_n}(V^{\otimes k}).
\]
Fix a set partition $P$ of the set $\{1, \ldots k, 1^\prime, \ldots, k^\prime\}$, and let $I \in [n]^k$. Then
\[
\Phi_{k,n}(P) \cdot v_I =
\sum_{J \in [n]^k} C_{P}(J,I) v_{J},
\]
where $C_P(J,I)$ is either zero or one according the following rule: Give each unprimed vertex $r$ of $P$ the label $j_r$, and give each primed vertex $r^\prime$ of $P$ the label $i_r$; if each part of $P$ is monochromatic (i.e. if all edges have endpoints with the same label), then $C_P(J,I) = 1$, if not, $C_P(J,I)=0$. The action of $S_n$ on $V^{\otimes k}$ is by permuting the label set, and therefore respects monochromatic labellings. Thus, the action of $P$ commutes with the action of $S_n$.  One can check that $\Phi_{k,n}$ is an algebra map. The key point is that the calculation of ${P_1}{P_2}$ leads to considering monochromatic labellings of $G(P_1, P_2)$, and each of the $c(P_1, P_2)$ components that are removed in the calculation may be assigned an arbitrary label in $[n]$. This is how the scalar multiple $n^{c(P_1,P_2)}$ arises (note that we have set the parameter $t$ to equal $n$).

Let $P_1$, $P_2$ be set partitions of a set $X$. We say that $P_1$ is a \emph{coarsening} of $P_2$ if whenever $x_1, x_2 \in X$ are in the same part of $P_2$, they are also in the same part of $P_1$. This makes set partitions of $X$ into a poset.

\begin{defin}
For a $(k,k)$-set partition $P$, let $x_P \in \Par_k(t)$ be defined by the recursion
\[
P=\sum_{\mbox{$P^\prime$ is a coarsening of $P$}} x_{P^\prime}.
\]
\end{defin}
It is immediate that the $x_P$ are a basis of $\Par_k(t)$ by an upper-unitriangularity argument. Moreover, the $x_P$ are linear combinations of the ${P^\prime}$ whose coefficients do not depend on $t$, as we have made no reference to the multiplicative structure.  An easy inclusion-exclusion argument determines $\Phi_{k,n}(x_P)$.

\begin{prop}
We have that
\[
\Phi_{k,n}(x_P) \cdot v_I = \sum_{J \in [n]^k} C_{P}^\prime(J,I) v_{J},
\]
where $C_{P}^\prime(J,I)$ is computed similarly to $C_{P}(J,I)$, except that it is only nonzero if in addition to being monochromatic, distinct parts of $P$ have distinct labels.
\end{prop}

The $x_P$ are useful because they control the kernel of $\Phi_{k,n}$:

\begin{theorem} \label{duality_hom_theorem}
The map $\Phi_{k,n}$ is always surjective. The kernel is spanned by $x_P$ where $P$ has strictly more than $n$ parts. In particular, $\Phi_{k,n}$ is injective whenever $n \geq 2k$.
\end{theorem}

We now perform a character calculation similar to that in Theorem 3.2.2 of \cite{Halverson}.

\begin{theorem} \label{bicharacter_theorem}
Let $P$ be a $(k,k)$-set partition (and hence an element of $\Par_k(n)$). Fix an element $g \in S_n$ of cycle type $(1^{m_1}2^{m_2}\cdots)$. Then, viewing $V^{\otimes k}$ as module for $\mathbb{C}S_n \otimes \Par_k(n)$,
\[
\tr_{V^{\otimes k}}(g \otimes P)
\]
is a polynomial in $n, m_1, m_2, \ldots, m_k$. If we let $n$ have degree 1, and $m_i$ have degree $i$, then this polynomial has degree at most $k$.
\end{theorem}

\begin{proof}
Let us consider the action of $g \otimes P$ on $v_I$ for $I \in [n]^k$:
\[
g \otimes P \cdot v_I = \sum_{J} C_P(J,I) v_{g(J)}.
\]
The coefficient of $v_I$ in this sum is equal to $C_P(g^{-1}(I),I)$, so
\[
\tr_{V^{\otimes k}}(g \otimes P) = \sum_{I} C_P(g^{-1}(I),I).
\]
We now count the $I \in [n]^k$ such that $C_P(g^{-1}(I),I) = 1$. Because of the monochromatic condition, it suffices to instead consider labellings of the parts of $P$, rather than the individual vertices. Consider the directed graph $G$ whose vertices are parts of $P$, having a directed edge from $U_i$ to $U_j$ if there is $r \in [n]$ such that $r \in U_i$ and $r^\prime \in U_j$ (note that this graph may have loops). In order to have $C_P(g^{-1}(I),I) = 1$, it is necessary and sufficient that whenever there is an edge from $U_i$ to $U_j$, the label of $U_j$ must be obtained by applying $g$ to the label of $U_i$. Note that because the action of $g$ on labels is invertible, the label of $U_j$ also determines the label of $U_i$.

We now count the labellings.  For each connected component in $G$, choosing the label of any vertex determines the labels for all vertices in that component. This may be done algorithmically by depth-first search; however, if we encounter an edge connecting two vertices that have already been visited, we still require the labellings to be related by $g$. This happens precisely when there is a cycle in the graph. If such a cycle has $l_+$ edges directed forwards and $l_-$ edges directed backwards, we require that $g^{l_+-l_-}$ must fix the label of every vertex in the cycle, and hence the label of every vertex in the component. Let $l_{tot}$ be the greatest common divisor of $l_+ - l_-$ among all undirected cycles in the connected component in $G$, where $l_{tot}=0$ if there are no cycles. The the label of a vertex must be fixed by $g^{l_{tot}}$ and the number of labels satisfying this condition is
\[
Q_{l_{tot}} = \sum_{d \mid l_{tot}} d m_d,
\]
which is equal to $n$ if $l_{tot} = 0$. So the total number of $I \in [n]^k$ is equal to the product of $Q_{l_{tot}}$ across all connected components of the graph $G$.

It remains to show that $m_i$ with $i > k$ cannot appear, and to analyse the degree of the polynomial obtained in this way. Each element $r \in [n]$ contributes an edge to $G$ (unless an edge was already present). This means that $G$ has at most $n$ edges, so any component with a cycle must have a cycle of length at most $n$, meaning that $l_{tot} \leq n$. This shows that only the claimed variables appear. It also shows that a component of $G$ with $r$ edges contributes a multiplicative factor of degree at most $r$. Note that $r=0$ cannot happen: every part contains either a primed or unprimed vertex, and therefore has an incoming or outgoing edge in $G$ (even if it connects back to the same part).
\end{proof}

\section{Proof of the stability theorem}
\label{sec:proof-of-main}

We begin by constructing an algebraic method for counting permutation patterns. In this section, $V$ is the permutation representation of $S_n$ corresponding to the natural action on $[n]$, and $v_I$ is the pure tensor in $V^{\otimes k}$ corresponding to the word $I \in [n]^k$.  We extend the notion of pattern containment from permutations to more general functions and tuples as follows: Let $\sigma$ be any function from the set $\{1,\ldots,k\}$ to itself (not necessarily a permutation), then we say that the tuple $(i_1, \ldots, i_k)$ is \emph{$\sigma$-sorted} if $i_a < i_b$ if and only if $\sigma(a) < \sigma(b)$.

\begin{defin}
For a function $\sigma :[k] \to [k]$, let $E_\sigma: \mathbb{C} \to V^{\otimes k}$ be the linear map defined by
\[
E_\sigma(1) = \sum_{\substack{I \in [n]^k \\I \mbox{ is $\sigma$-sorted}}} v_I.
\]
Similarly, we define the transpose map $E_\sigma^T: V^{\otimes k} \to \mathbb{C}$ by
\[
E_\sigma^T(v_I) =
\begin{cases}
1 & \mbox{$I$ is $\sigma$-sorted} \\
0 & \mbox{otherwise}
\end{cases}.
\]
\end{defin}

\begin{lemma}
For $g \in S_n$,  we have $N_\sigma(g) = \tr_\mathbb{C}(E_{\sigma}^T g E_{\Id})$.

\end{lemma}

\begin{proof}
We compute the value of $E_{\sigma}^T g E_{\Id}$ at $1 \in \mathbb{C}$. Note that $E_{\Id}(1)$ is the sum of pure tensors $v_I$ such that the word $I$ is strictly increasing. Let us consider a single such term $v_{i_1} \otimes v_{i_2} \otimes \cdots \otimes v_{i_k}$. Applying $g$ gives $v_{g(i_1)} \otimes v_{g(i_2)} \otimes \cdots \otimes v_{g(i_k)}$. Finally, applying $E_\sigma^T$ yields one if $(g(i_1), g(i_2), \ldots, g(i_k))$ is $\sigma$-sorted, which is to say that $I$ is an occurrence of $\sigma$ in $g$, and zero otherwise.
\end{proof}

\begin{lemma} \label{shuffle_lemma}
Given $\alpha: [k_1] \to [k_1]$ and $\beta: [k_2] \to [k_2]$, we have
\[
E_\alpha \otimes E_\beta = \sum_{\gamma} E_\gamma,
\]
where the sum is over $\gamma: [k_1 + k_2] \to [k_1 + k_2]$ such that $\gamma$ restricted to $\{1, \ldots, k_1\}$ is $\alpha$-sorted, $\gamma$ restricted to $\{k_1+1, \ldots, k_1+k_2\}$ is $\beta$-sorted, and the image of $\gamma$ is of the form $\{1,\ldots, r\}$ for some $r$.
\end{lemma}
\begin{proof}
By definition, $E_\alpha \otimes E_\beta$ sends $1 \in \mathbb{C}$ to the sum of all $v_I \otimes v_J$ such that $I$ is $\alpha$-sorted and $J$ is $\beta$-sorted. So, we obtain precisely the $v_{K}$ with the first $k_1$ elements $\alpha$-sorted, and final $k_2$ elements $\beta$-sorted (each with multiplicity 1). The stipulation on the image of $\gamma$ is to avoid overcounting (for example, a $(1,1)$-pattern is the same thing as a $(2,2)$-pattern, so $E_{(1,1)} = E_{(2,2)}$). Note that $E_{\gamma} = E_{\gamma^\prime}$ if and only if $\gamma$ is $\gamma^\prime$-sorted and vice-versa. If $r$ is the size of the image of $\gamma$, there is a unique $\gamma$-sorted element of $[r]$. This completes the proof.
\end{proof}

\begin{theorem}\label{averaging_theorem}
Given $\alpha, \beta$ functions $[k] \to [k]$, the linear map $T_{\alpha, \beta} : V^{\otimes k} \to V^{\otimes k}$ given by
\[
\frac{1}{n!}\sum_{x \in S_n} x^{-1} E_{\alpha} E_\beta^T x
\]
may be expressed in the form
\[
\Phi_{k,n}\left(\sum_{P} a_{P} {P}\right),
\]
where $P$ are $(k,k)$-set partitions, and the $a_P \in \mathbb{C}$ are independent of $n$.
\end{theorem}

\begin{proof}
Because $T_{\alpha, \beta}$ is defined by averaging over $S_n$, it commutes with the action of $S_n$ on $V^{\otimes k}$. It therefore lies in the image of $\Phi_{k,n}$, and so for each $n$, we have
\[
T_{\alpha, \beta} = \Phi_{k,n}\left(\sum_{P} a_P(n) P \right).
\]
We must show that $a_P(n)$ may be taken to be independent of $n$. It is equivalent to show that
\[
T_{\alpha, \beta} = \Phi_{k,n}\left(\sum_{P} b_P(n) x_P \right),
\]
with $b_P(n)$ independent of $n$. This is easier to check, because of the property that for any $I, J \in [n]^k$ there is a unique $(k,k)$-set partition $P$ such that $v_J$ appears with nonzero coefficient in $\Phi_{k,n}(x_P) v_I$. This $P$ is obtained by labelling the unprimed vertices in $\{1,\ldots, k, 1^\prime, \ldots, k^\prime\}$ with $J$, and labelling the primed vertices with $I$, then taking the parts of $P$ to be the maximal monochromatic subsets of the vertices. One can easily reverse this construction to find such $I$ and $J$ given $P$, provided the number of labels available (i.e. $n$) is at least the number of parts of $P$.

Let us choose $P$ with at most $n$ parts, and then select $I$ and $J$ as such that $v_J$ appears in $\Phi_{k,n}(x_P) v_I$. Let $L$ be the set of labels appearing in at least one of $I$ and $J$. Note that $|L|$ is precisely the number of parts of $P$.

The coefficient of $v_J$ in
\[
\frac{1}{n!}\sum_{x \in S_n} x^{-1} E_{\alpha} E_\beta^T x v_I
\]
is
\[
\frac{1}{n!} |\{x \in S_n \mid x(I)\mbox{ is $\beta$-sorted and } x(J) \mbox{ is $\alpha$-sorted} \}|.
\]
The sorting condition on $x$ is determined by how it reorders the elements of $L$. If $S_L$ is the subgroup of $S_n$ permuting the subset $L$ of $[n]$, each coset of $S_L$ yields each possible relative ordering of the elements of $L$ exactly once. Hence each coset has the same number of elements satisfying the sorting condition. Thus the coefficient becomes
\begin{eqnarray*}
& &
\frac{1}{n!} |S_n/S_L||\{x \in S_L \mid x(I)\mbox{ is $\beta$-sorted and } x(J) \mbox{ is $\alpha$-sorted} \}|\\
&=&
\frac{1}{|L|!}
|\{x \in S_L \mid x(I)\mbox{ is $\beta$-sorted and } x(J) \mbox{ is $\alpha$-sorted} \}|.
\end{eqnarray*}
This coefficient is independent of $n$. We note that if $|L| > n$ (so that it would be impossible to choose suitable $I$ and $J$), $\Phi_{k,n}(x_P) = 0$, so we may take $b_P$ to have the computed value even for small $n$.
\end{proof}

We are now ready to prove the main theorem.

\begin{proof}[Proof of Theorem~\ref{thm:main}]
We first prove part \ref{part:polynomial}.  We compute:
\begin{eqnarray*}
M_{\sigma, d, n}(\pi) &=&
\frac{1}{|C_{\pi}|} \sum_{\pi' \in C_{\pi}} N_{\sigma}^d(\pi') \\
&=&
\frac{1}{n!} \sum_{x \in S_n} \tr_{\mathbb{C}}(E_\sigma^T x\pi x^{-1} E_{\Id} )^d \\
&=&
\frac{1}{n!} \sum_{x \in S_n} \tr_{V^{\otimes k}}(x^{-1} E_{\Id} E_\sigma^T x\pi  )^d \\
&=&
\frac{1}{n!} \sum_{x \in S_n} \tr_{(V^{\otimes k})^{\otimes d}}(x^{-1} (E_{\Id})^{\otimes d} (E_\sigma^T)^{\otimes d} x \pi ).
\end{eqnarray*}
Now we note that $E_{\Id}^{\otimes d}$ is a linear combination of $E_{\alpha}$ for some patterns $\alpha$ by Lemma~\ref{shuffle_lemma}, and similarly $(E_{\sigma}^{T})^{\otimes d}$ is a linear combination of $E_{\beta}^T$ for some patterns $\beta$. So our expression becomes a linear combination of
\begin{eqnarray*}
\frac{1}{n!} \sum_{x \in S_n} \tr_{(V^{\otimes dk})}(x^{-1} (E_{\alpha}) E_\beta^T xg ) &=&
\tr_{(V^{\otimes dk})}\left(\frac{1}{n!} \sum_{x \in S_n} x^{-1} (E_{\alpha}) E_\beta^T x \pi \right) \\
&=&
\tr_{(V^{\otimes dk})}\left(\Phi_{dk, n}\left(\sum_{P}{a_P} D \right)\otimes \pi \right).
\end{eqnarray*}
Here we have used Theorem~\ref{averaging_theorem}. Finally, Theorem~\ref{bicharacter_theorem} guarantees that the result is a polynomial of the claimed form; this establishes part \ref{part:polynomial}.

For $\mu \in \Y_r$ it is well known (see Chapter 1, Section 7, Example 14 of Macdonald's book \cite{Macdonald}) that the function $\chi^{\mu[n]}$ on $\coprod_{n \geq 2r} S_n$ agrees with a polynomial $P_{\mu}(m_1,\ldots,m_r)$ of degree $r$, where $m_i$ has degree $i$ for each $i=1,\ldots,r$.  As in Section~\ref{sec:intro}, we evaluate these \emph{character polynomials} on a permutation $\pi$ by specifying the $m_i$ so that $1^{m_1}2^{m_2} \cdots$ is the cycle type of $\pi$.  Since the space of polynomials of degree at most $r$ (under this grading) has dimension $\sum_{n=0}^r |\Y_n|$, and since the character polynomials must be linearly independent by the orthogonality relation for characters, the character polynomials $\{P_{\mu}$ for $\mu \in \Y_n, n \leq r\}$ must form a basis of this space.

Now, by part \ref{part:polynomial}, we have that $M_{\sigma, d}$ is a polynomial in the variables $n,m_1,\ldots,m_{dk}$ of degree at most $dk$, where $\sigma \in S_k$ and $n$ has degree 1.  Decomposing $M_{\sigma, d}$ by applying the spanning property of character polynomials from the previous paragraph implies \ref{part:stable}.
\end{proof}

\bibliographystyle{plain}
\bibliography{paper.bib}
\end{document}


TITLE: Can we determine structure the automorphism group of all infinite abelian groups?
QUESTION [2 upvotes]: Let $G$ be a infinite abelian group .
We know that we can determine structure the automorphisms group of  all finite  abelian groups.
Can we determine structuer the automorphisms group of  all infinite  abelian groups?
Thank you

REPLY [1 votes]: We don't even know what all the infinite abelian groups are, much less do we have a description of their automorphism groups.  This question has some information about that.
Finitely generated abelian groups we have a better knowledge of, in particular of tame automorphisms, but these are not completely classified either.  In fact, even the automorphism groups of finite abelian groups are hard to describe in general.


text:
\begin{document}

\title{3-Divisibility of 9- and 27-Regular Partitions}
\author{S. Abinash}

\keywords{$l$-Regular Partitions; Hecke Eigenforms}
\subjclass[2010]{11P83}

\address{Indian Institute of Science Education and Research Thiruvananthapuram, Maruthamala P.O., Vithura, Thiruvananthapuram-695551, Kerala, India.}
\email{sarmaabinash15@iisertvm.ac.in}

\begin{abstract}
A partition of $n$ is $l$-regular if none of its parts is divisible by $l$. Let $b_l(n)$ denote the number of $l$-regular partitions of $n$. In this paper, using the theory of Hecke eigenforms explored by J.-P. Serre, we establish exact criteria for the $3$-divisibility of $b_9(n)$ and $b_{27}(n)$.
\end{abstract}

\maketitle

\section{\Large{\textbf{Introduction}}}

A partition of a positive integer $n$ is a non-increasing sequence of positive integers whose sum is $n$. The members of the sequence are called parts. For an integer $l\geq2$, a partition of $n$ is said to be $l$-regular if none of its parts is divisible by $l$. Let $b_l(n)$ denote the number of $l$-regular partitions of $n$. By convention, we assume that $b_l(0)=1$. The generating function for $b_l(n)$ is given by
\begin{align}
\sum_{n=0}^\infty b_l(n)q^n=\prod_{m=1}^\infty\frac{\left(1-q^{lm}\right)}{\left(1-q^m\right)}.\label{eq:1}
\end{align}
We also state the definition of Dedekind's eta-function,
\begin{align}
    \eta(z):=q^{1/24}\prod_{m=1}^\infty(1-q^m),\label{eq:30}
\end{align}
where $q=e^{2\pi iz}$.

In recent years, a few works have been done with regard to divisibility of $l$-regular partitions. For instance, Gordon and Ono \cite{4} showed that $b_l(n)$ is almost always divisible by $l^i$ for any prime $l$ and any positive integer $i$. Lovejoy and Penniston \cite{5} proved some results on $3$-divisibility of $b_3(n)$. For $l\in\{5,7,11 \}$, Dandurand and Penniston \cite{1} gave exact criteria for the $l$-divisibility of $b_l(n)$. In \cite{2}, Penniston established a precise description of the behaviour of $b_{11}(n)$ modulo $5$ when $5\nmid n$.

In this paper, we establish precise criteria for $3$-divisibility of $b_9(n)$ and $b_{27}(n)$. For any positive integer $n$ and prime $p$, let $ord_p(n)$ denote the highest power of $p$ that divides $n$. The following is the first main result of this paper.

\begin{theorem}
Let $n$ be a nonnegative integer. We have that $b_9(n)$ is divisible by $3$ if and only if one of the following conditions holds.
\begin{itemize}
    \item $\#\{p:p\equiv2\pmod3, \text{ } ord_p(3n+1) \text{ is odd}\}\neq0$.
    \item $\#\{p:p\equiv1\pmod3, \text{ } ord_p(3n+1)\equiv2\pmod3\}\neq0$.
\end{itemize}
\end{theorem}

Note that for an odd prime $p$, we can write $p=x^2+y^2$ for $x,y\in\mathbb Z$ if and only if $p\equiv1\pmod 4$. Furthermore, if $p\equiv5\pmod{12}$ then we may assume, without loss of generality, that $x\equiv1\equiv-y\pmod3$ as $x^2+y^2\equiv2\pmod3$; and if $p\equiv1\pmod{12}$ then we may assume, without loss of generality, that $x\not\equiv0\pmod3$ and $y\equiv0\pmod3$ as $x^2+y^2\equiv1\pmod3$.

Suppose $p_1,\cdots,p_s$ are primes such that $p_j\equiv5\pmod{12}$ with $3\mid\mid(x_j+y_j)$ and $\alpha_j=ord_{p_j}(12n+13)$ is even. Let's denote
\begin{align}
    k&:=(-1)^{s+1}\left(\prod_{j=1}^s(-1)^{\alpha_j/2-1}p_j^{6\alpha_j-12}\right)\left(\sum_{j=1}^s\frac{\alpha_j(\alpha_j+2)}{8}\left(\prod_{i\neq j}p_i^{12}\right)\right),\label{eq:26}
\end{align}
We also denote, for each $\alpha=ord_p(12n+13)$ with $p\equiv1\pmod{12}$,
\begin{align}
    r_\alpha&:=\#\{p\equiv1\pmod{12}:ord_p(12n+13)=\alpha\},\label{eq:29}\\
    A_\alpha&:=(x_1\cdots x_{r_\alpha})^{12\alpha},\label{eq:27}\\
    B_\alpha&:=(x_1\cdots x_{r_\alpha})^{12\alpha-2}\sum_{\substack{i_1<\cdots<i_{r_\alpha-1}\\j\neq i_s}}(x_{i_1}\cdots x_{i_{r_\alpha-1}}y_j)^2.\label{eq:28}
\end{align}
Now we state the second main result of this paper.
\begin{theorem}
Let $n$ be a nonnegative integer. We have that $b_{27}(n)$ is divisible by $3$ if and only if one of the following conditions holds.
\begin{itemize}
   \item $\#\{p : p\equiv7 \text{ or } 11\pmod{12}, \text{ } ord_p(12n+13) \text{ is odd}\}\neq0$.
    \item $\#\{p : p\equiv5\pmod{12}, \text{ } ord_p(12n+13) \text{ is odd}\}\neq0,2$.
    \item $\#\{p : p\equiv5\pmod{12}, \text{ } ord_p(12n+13) \text{ is odd}\}=2;\quad 9\mid(x+y) \text{ for at least one such } p$.
    \item $\#\{p : p\equiv5\pmod{12}, \text{ } ord_p(12n+13) \text{ is odd}\}=2;\quad 3\mid\mid(x+y) \text{ for both such } p;\\
    \#\{p : p\equiv1\pmod{12}, \text{ } ord_p(12n+13)\equiv2\pmod3\}\neq0$.
    \item $\#\{p : p\equiv5\pmod{12}, \text{ } ord_p(12n+13) \text{ is odd}\}=0;\quad k\equiv0\pmod3;\\
    2\prod_\alpha(\alpha+1)^{r_\alpha}\left(\sum_\alpha\left(\alpha B_\alpha\prod_{\beta\neq\alpha}A_\beta\right)\right)\\
    \text{ }\equiv41\prod_\alpha(\alpha+1)^{r_\alpha}\left(\sum_\alpha\left(\alpha(11\alpha+26)B_\alpha\prod_{\beta\neq\alpha}A_\beta\right)\right)\pmod{3^4},\\
    \text{where $\alpha$ varies over all distinct $ord_p(12n+13)$ with $p\equiv1\pmod{12}$.}$\\
    \item $\#\{p : p\equiv5\pmod{12}, \text{ } ord_p(12n+13) \text{ is odd}\}=0;\quad k\equiv\varepsilon\pmod3 \text{ where $\varepsilon=1$ or $2$};\\
    2\prod_\alpha(\alpha+1)^{r_\alpha}\left(\sum_\alpha\left(\alpha B_\alpha\prod_{\beta\neq\alpha}A_\beta\right)\right)\\
    \text{ }\equiv41(81d+1)\prod_\alpha(\alpha+1)^{r_\alpha}\left(\sum_\alpha\left(\alpha(11\alpha+26)B_\alpha\prod_{\beta\neq\alpha}A_\beta\right)\right)\pmod{3^4},\\
    \text{where $\alpha$ varies over all distinct $ord_p(12n+13)$ with $p\equiv1\pmod{12}$ and $d=\varepsilon d'$, $d'\in\mathbb Z$ is the}\\
    \text{inverse of $\prod_{\substack{p\mid(12n+13)\\p\equiv1(12)}}(-1)^{\alpha/2}p^{6\alpha}$ in $(\mathbb Z/3^5\mathbb Z)^*$ }$.
\end{itemize}
\end{theorem}

\section{\Large{\textbf{Preliminary for Hecke Eigenform}}}

Let's consider an imaginary quadratic field $K=\mathbb Q(\sqrt d)$ with discriminant $d_K$. We denote the ring of integers of $K$ by $\mathcal O_K$. Suppose, $c$ is a Hecke character on $K$ of exponent $k-1$ and conductor $\mathfrak f_c$, where $\mathfrak f_c$ is a nonzero ideal of $\mathcal O_K$.

Now we define the series
\begin{align}
    \phi_{K,c}(z):=\sum_{\mathfrak a}c(\mathfrak a)q^{N(\mathfrak a)}\quad(q:=e^{2\pi iz}, \Im(z)>0),\label{eq:2}
\end{align}
where the sum is taken over all ideals $\mathfrak a$ of $\mathcal O_K$ which are coprime to $\mathfrak f_c$. We have that $\phi_{K,c}(z)$ is a normalized Hecke eigenform of weight $k$, level $|d_K|\cdot N(\mathfrak f_c)$ and character $\epsilon_K\omega_c$, where $\epsilon_K$ and $\omega_c$ are two Dirichlet characters defined as
\begin{align*}
    \epsilon_K(p)=\left(\frac{d}{p}\right)\text{ for primes }p\text{ such that }p\nmid2d
\end{align*}
and
\begin{align*}
    \omega_c(n)=\frac{c(n\mathcal O_K)}{n^{k-1}}\text{ for integers }n\text{ such that the ideal }n\mathcal O_K\text{ is coprime to }\mathfrak f_c.
\end{align*}
For more details please refer to \cite{1,3}.

\section{\Large{\textbf{Proof of Theorem 1.1}}}

In (\ref{eq:1}), taking $l=9$, we get
\begin{align*}
    \sum_{n=0}^\infty b_9(n)q^n=\prod_{m=1}^\infty\frac{\left(1-q^{9m}\right)}{\left(1-q^m\right)}\equiv\prod_{m=1}^\infty\left(1-q^m\right)^8\pmod3.
\end{align*}
Thus, in view of (\ref{eq:30}), we have
\begin{align}
    \sum_{n=0}^\infty b_9(n)q^{3n+1}\equiv q\cdot\prod_{m=1}^\infty\left(1-q^{3m}\right)^8\equiv\eta^8(3z)\pmod3,\label{eq:3}
\end{align}

In \cite{3}, Serre showed that $\eta^8(3z)$ is a Hecke eigenform of weight $4$ and level $9$. Let's consider $K=\mathbb Q(\sqrt{-3})$ whose discriminant is $-3$. We have $\mathcal O_K=\mathbb Z[\zeta_3]$ where $\zeta_3$ is a primitive cube root of unity. Now we fix the ideal $\mathfrak f=\sqrt{-3}\cdot\mathcal O_K$; note that $N(\mathfrak f)=3$. We define a Hecke character $c$ on $K$ of exponent $3$ and conductor $\mathfrak f$.

Suppose $\mathfrak a$ is an arbitrary ideal of $\mathcal O_K$ coprime to $\mathfrak f$. Since $\mathcal O_K$ is a PID, therefore $\mathfrak a$ is a principal ideal. Furthermore, we can always choose a generator $a$ of $\mathfrak a$ such that $a\equiv1\pmod{\mathfrak f}$. We define $c(\mathfrak a)=a^3$. It can be easily verified that $c$ thus defined is a Hecke character on $K$ of exponent $3$ and conductor $\mathfrak f$. Also, $\epsilon_K\omega_c$ turns out to be the principal character here. So, $\phi_{K,c}(z)$ from (\ref{eq:2}) is a Hecke eigenform of weight $4$ and level $9$.

Since $\eta^8(3z)=\phi_{K,c}(z)$ (see \cite{3}), therefore $\eta^8(3z)$ is a Hecke eigenform of weight $4$ and level $9$. We write
\begin{align*}
    \phi_{K,c}(z)=\sum_{n=1}^\infty s(n)q^n.
\end{align*}
By (\ref{eq:3}), we get
\begin{align*}
    \sum_{n=0}^\infty b_9(n)q^{3n+1}\equiv\sum_{n=1}^\infty s(n)q^n\pmod3.
\end{align*}
Comparing the coefficients of the terms involving $q^{3n+1}$, we get $b_9(n)\equiv s(3n+1)\pmod3$ for every nonnegative integer $n$.

Let $3n+1=\prod_{i=1}^rp_i^{e_i}$ for some $r\geq0$ where $p_i$'s are distinct primes. In view of the properties of Hecke eigenforms, we have
\begin{align*}
    s(3n+1)=\prod_{i=1}^rs(p_i^{e_i}).
\end{align*}
So, we shift our focus to $s(p^j)$ for primes $p$.

For an odd prime $p\neq3$, note that
\begin{align*}
    p\text{ is totally split in }K&\Longleftrightarrow\left(\frac{-3}{p}\right)=1\\
    &\Longleftrightarrow p\text{ is represented by some primitive form of discriminant }-12\\
    &\Longleftrightarrow p=x^2+3y^2\text{ for some }x,y\in\mathbb Z\\
    &\Longleftrightarrow p\equiv1\pmod3.
\end{align*}
Consequently, $p$ is inert in $K$ $\Longleftrightarrow$ $p\equiv2\pmod3$. Also, $2$ is inert in $K$.

Let $p\equiv2\pmod3$. Since $p$ is inert, therefore no ideal of $\mathcal O_K$ has norm $p^j$ if $j$ is odd. Thus, $s(p^j)=0$ if $j$ is odd. If $j$ is even, then $p^{j/2}\mathcal O_K$ is the only ideal with norm $p^j$ and by definition, clearly $s(p^j)\not\equiv0\pmod3$ in this case.

Let $p\equiv1\pmod3$. We can write $p=x^2+3y^2$ for some $x,y\in\mathbb Z$ with $x\equiv1\pmod3$. Only two ideals of $\mathcal O_K$ have norm $p$, namely, $(x+y\sqrt{-3})\mathcal O_K$ and $(x-y\sqrt{-3})\mathcal O_K$. So,
\begin{align*}
    s(p)&=c\left((x+y\sqrt{-3})\mathcal O_K\right)+c\left((x-y\sqrt{-3})\mathcal O_K\right)\\
    &=(x+y\sqrt{-3})^3+(x-y\sqrt{-3})^3 \quad\quad [x\equiv1\pmod3\Longrightarrow x\pm y\sqrt{-3}\equiv1\pmod{\mathfrak f}]\\
    &=4x^3-12y^2x-px\\
    &\equiv2\pmod3.
\end{align*}
Also, $s(1)=1\equiv1\pmod3$. Now, by the properties of Hecke eigenforms, we have
\begin{align*}
    s(p^2)&=s(p)s(p)-p^3s(1)\\
    &\equiv2\cdot2-1\cdot1\pmod3\\
    &\equiv0\pmod3.
\end{align*}
Using mathematical induction, it can be easily proved that for any $k\geq0$,
\begin{align*}
    s(p^{3k})\equiv1\pmod3,\quad s(p^{3k+1})\equiv2\pmod3,\quad s(p^{3k+2})\equiv0\pmod3.
\end{align*}
Hence, the proof is completed.

\section{\Large{\textbf{Proof of Theorem 1.2}}}

In (\ref{eq:1}), taking $l=27$, we get
\begin{align*}
    \sum_{n=0}^\infty b_{27}(n)q^n=\prod_{m=1}^\infty\frac{\left(1-q^{27m}\right)}{\left(1-q^m\right)}\equiv\prod_{m=1}^\infty\left(1-q^m\right)^{26}\pmod3.
\end{align*}
Thus, in view of (\ref{eq:30}), we have
\begin{align}
    \sum_{n=0}^\infty b_{27}(n)q^{12n+13}\equiv q^{13}\cdot\prod_{m=1}^\infty\left(1-q^{12m}\right)^{26}\equiv\eta^{26}(12z)\pmod3.\label{eq:4}
\end{align}

In \cite{3}, Serre showed that $\eta^{26}(12z)$ is a linear combination of Hecke eigenforms of weight $13$, level $144$ and character $\chi_{-1}(\bullet):=\left(\frac{-1}{\bullet}\right)$.

Firstly, let's consider $K_1=\mathbb Q(\sqrt{-3})$ whose discriminant is $-3$. We have $\mathcal O_1=\mathcal O_{K_1}=\mathbb Z[\zeta_3]$ where $\zeta_3$ is a primitive cube root of unity. Now we fix the ideal $\mathfrak f_1=4\sqrt{-3}\cdot\mathcal O_1$; note that $N(\mathfrak f_1)=48$. We define Hecke characters $c_{1\pm}$ on $K_1$ of exponent $12$ and conductor $\mathfrak f_1$.

Suppose $\mathfrak a$ is an arbitrary ideal of $\mathcal O_1$ coprime to $\mathfrak f_1$. Since $\mathcal O_1$ is a PID, therefore $\mathfrak a$ is a principal ideal. Furthermore, we can always choose a generator $a=x+y\sqrt{-3}$ of $\mathfrak a$ with $x,y\in\mathbb Z$, $x+y\equiv1\pmod2$ and $x\equiv1\pmod3$. We define
\begin{align*}
    c_{1\pm}(\mathfrak a)=(-1)^{(x\mp y-1)/2}a^{12}.
\end{align*}
It can be easily verified that $c_{1\pm}$ thus defined are Hecke characters on $K_1$ of exponent $12$ and conductor $\mathfrak f_1$. Also, $\epsilon_{K_1}\omega_{c_{1+}}=\chi_{-1}=\epsilon_{K_1}\omega_{c_{1-}}$. So, $\phi_{K_1,c_{1\pm}}(z)$ from (\ref{eq:2}) are Hecke eigenforms of weight $13$, level $144$ and character $\chi_{-1}$.

Next, let's consider $K_2=\mathbb Q(i)$ whose discriminant is $-4$. We have $\mathcal O_2=\mathcal  O_{K_2}=Z[i]$. Now we fix the ideal $\mathfrak f_2=6\cdot\mathcal O_2$; note that $N(\mathfrak f_2)=36$. We define Hecke characters $c_{2\pm}$ on $K_2$ of exponent $12$ and conductor $\mathfrak f_2$.

Suppose $\mathfrak b$ is an arbitrary ideal of $\mathcal O_2$ coprime to $\mathfrak f_2$. Since $\mathcal O_2$ is a PID, therefore $\mathfrak b$ is a principal ideal. For a generator $b$ of $\mathfrak b$, we determine $m\in\mathbb Z/2\mathbb Z$ and $n\in\mathbb Z/8\mathbb Z$ such that
\begin{align*}
    b\equiv i^m\pmod{2\cdot\mathcal O_2} \quad \text{and} \quad b\equiv(1-i)^n\pmod{3\cdot\mathcal O_2}.
\end{align*}
We define
\begin{align*}
    c_{2\pm}(\mathfrak b)=(-1)^{3m}(\pm i)^{3n}b^{12}.
\end{align*}
It can be easily verified that $c_{2\pm}$ thus defined are Hecke characters on $K_2$ of exponent $12$ and conductor $\mathfrak f_2$. Also, $\epsilon_{K_2}\omega_{c_{2+}}=\chi_{-1}=\epsilon_{K_2}\omega_{c_{2-}}$. So, $\phi_{K_2,c_{2\pm}}(z)$ from (\ref{eq:2}) are Hecke eigenforms of weight $13$, level $144$ and character $\chi_{-1}$.

Since
\begin{align}
    \eta^{26}(12z)=\frac{1}{32617728}\left(\phi_{K_1,c_{1+}}(z)+\phi_{K_1,c_{1-}}(z)-\phi_{K_2,c_{2+}}(z)-\phi_{K_2,c_{2-}}(z)\right) \quad \text{ (see \cite{3})},\label{eq:9}
\end{align}
therefore $\eta^{26}(12z)$ is a linear combination of Hecke eigenforms of weight $13$, level $144$ and character $\chi_{-1}$. We write
\begin{align*}
    \phi_{K_1,c_{1\pm}}(z)=\sum_{n=1}^\infty t_{1\pm}(n)q^n, \quad \phi_{K_2,c_{2\pm}}(z)=\sum_{n=1}^\infty t_{2\pm}(n)q^n.
\end{align*}
By (\ref{eq:4}), we get
\begin{align*}
    \sum_{n=0}^\infty b_{27}(n)q^{12n+13}\equiv\frac{1}{32617728}\left(\sum_{n=1}^\infty\big(t_{1+}(n)+t_{1-}(n)-t_{2+}(n)-t_{2-}(n)\big)q^n\right)\pmod3.
\end{align*}
Comparing the coefficients of the terms involving $q^{12n+13}$, we get
\begin{align*}
b_{27}(n)\equiv\frac{1}{32617728}\big(t_{1+}(12n+13)+t_{1-}(12n+13)-t_{2+}(12n+13)-t_{2-}(12n+13)\big)\pmod3
\end{align*}
for every nonnegative integer $n$. Since $3^4\mid\mid32617728$, therefore
\begin{align*}
b_{27}(n)\equiv0\pmod3 \Longleftrightarrow t_{1+}(12n+13)+t_{1-}(12n+13)\equiv t_{2+}(12n+13)+t_{2-}(12n+13)\pmod{3^5}.
\end{align*}
In view of the properties of Hecke eigenforms, we have
\begin{align*}
    t_{1\pm}(12n+13)=\prod_{p\mid(12n+13)}t_{1\pm}(p^\alpha),\quad t_{2\pm}(12n+13)=\prod_{p\mid(12n+13)}t_{2\pm}(p^\alpha).
\end{align*}

Before proceeding further, let's have a look at $t_{1+}(p^\alpha)$, $t_{1-}(p^\alpha)$, $t_{2+}(p^\alpha)$, $t_{2-}(p^\alpha)$ for a prime $p\neq3$. Let $t$ denote any one among $t_{1\pm}$ and $t_{2\pm}$. In view of the properties of Hecke eigenforms, if $p\equiv1\pmod4$ then we have for any $\beta\geq0$,
\begin{align}
    t(p^{2\beta})&=t(p)^{2\beta}-\binom{2\beta-1}{1}p^{12}t(p)^{2\beta-2}+\cdots+(-1)^{\beta-1}\binom{\beta+1}{2}p^{12\beta-12}t(p)^2+(-1)^\beta p^{12\beta},\label{eq:5}\\
    t(p^{2\beta+1})&=t(p)^{2\beta+1}-\binom{2\beta}{1}p^{12}t(p)^{2\beta-1}+\cdots+(-1)^{\beta-1}\binom{\beta+2}{3}p^{12\beta-12}t(p)^3+(-1)^\beta\binom{\beta+1}{1}p^{12\beta}t(p).\label{eq:6}
\end{align}
If $p\equiv3\pmod4$ then we have for any $\beta\geq0$,
\begin{align}
    t(p^{2\beta})&=t(p)^{2\beta}+\binom{2\beta-1}{1}p^{12}t(p)^{2\beta-2}+\cdots+\binom{\beta+1}{2}p^{12\beta-12}t(p)^2+p^{12\beta},\label{eq:7}\\
    t(p^{2\beta+1})&=t(p)^{2\beta+1}+\binom{2\beta}{1}p^{12}t(p)^{2\beta-1}+\cdots+\binom{\beta+2}{3}p^{12\beta-12}t(p)^3+\binom{\beta+1}{1}p^{12\beta}t(p).\label{eq:8}
\end{align}

Firstly, let $p\equiv11\pmod{12}$. Since $p\equiv2\pmod3$ and $p\equiv3\pmod4$, therefore $p$ is inert in $K_1$ and $K_2$, respectively. Consequently, $t_{1\pm}(p)=0=t_{2\pm}(p)$. By (\ref{eq:7}) and (\ref{eq:8}), we have
\begin{align}\label{eq:10}
    t_{1\pm}(p^\alpha)=t_{2\pm}(p^\alpha)=
    \begin{cases}
    p^{6\alpha} &\text{ if $\alpha$ is even,}\\
    0 &\text{ if $\alpha$ is odd.}
    \end{cases}
\end{align}

Secondly, let $p\equiv7\pmod{12}$. Since $p\equiv3\pmod4$, therefore $p$ is inert in $K_2$. Consequently, $t_{2\pm}(p)=0$. By (\ref{eq:7}) and (\ref{eq:8}), we have
\begin{align}\label{eq:11}
    t_{2\pm}(p^\alpha)=
    \begin{cases}
    p^{6\alpha} &\text{ if $\alpha$ is even,}\\
    0 &\text{ if $\alpha$ is odd.}
    \end{cases}
\end{align}
Since $p\equiv1\pmod3$, therefore we can write $p=z^2+3w^2=(z+w\sqrt{-3})(z-w\sqrt{-3})$ for some $z,w\in\mathbb Z$ with $z\equiv1\pmod4$. Moreover, as $z^2+3w^2\equiv3\pmod4$, we must have $z$ even and $w$ odd and thus we can choose $z,w$ such that $z+w\equiv1\pmod4$ and $z-w\equiv3\pmod4$. Hence, we have
\begin{align}\label{eq:15}
    t_{1+}(p)=-(z+w\sqrt{-3})^{12}+(z-w\sqrt{-3})^{12}=-t_{1-}(p).
\end{align}
By (\ref{eq:8}), for any odd $\alpha$, $t_{1+}(p^\alpha)=-t_{1-}(p^\alpha)$. Further, it can be easily verified that
\begin{align}\label{eq:14}
    t_{1+}(p)^2=t_{1-}(p)^2\equiv0\pmod{3^5}.
\end{align}
By (\ref{eq:7}), we have for any even $\alpha$
\begin{align}\label{eq:16}
    t_{1\pm}(p^\alpha)\equiv p^{6\alpha}\pmod{3^5},
\end{align}

Thirdly, let $p\equiv5\pmod{12}$. Since $p\equiv2\pmod3$, therefore $p$ is inert in $K_1$.Consequently, $t_{1\pm}(p)=0$. By (\ref{eq:5}) and (\ref{eq:6}), we have
\begin{align}\label{eq:12}
    t_{1\pm}(p^\alpha)=
    \begin{cases}
    (-1)^{\alpha/2}p^{6\alpha} &\text{ if $\alpha$ is even,}\\
    0 &\text{ if $\alpha$ is odd.}
    \end{cases}
\end{align}
Since $p\equiv1\pmod4$, therefore we can write $p=x^2+y^2=(x+iy)(x-iy)$ for some $x,y\in\mathbb Z$ with $x$ odd and $y$ even. Moreover, as $x^2+y^2\equiv2\pmod3$, we must have $x\not\equiv0\pmod3$ and $y\not\equiv0\pmod3$ and thus we can choose $x,y$ such that $x\equiv1\equiv-y\pmod3$. Hence, we have
\begin{align}\label{eq:19}
    t_{2+}(p)=-i(x+iy)^{12}+i(x-iy)^{12}=-t_{2-}(p).
\end{align}
By (\ref{eq:6}), for any odd $\alpha$, $t_{2+}(p^\alpha)=-t_{2-}(p^\alpha)$. Further, it can be easily verified that
\begin{align}\label{eq:18}
    t_{2+}(p)^2=t_{2-}(p)^2\equiv
    \begin{cases}
    162\pmod{3^5} &\text{if $3\mid\mid(x+y)$,}\\
    0\pmod{3^5} &\text{if $9\mid(x+y)$.}
    \end{cases}
\end{align}
By (\ref{eq:5}), we have for any even $\alpha$
\begin{align}\label{eq:20}
    t_{2\pm}(p^\alpha)\equiv
    \begin{cases}
    (-1)^{\alpha/2-1}\left(\left(\frac{(\alpha+2)\alpha}{8}\right)p^{6\alpha-12}162-p^{6\alpha}\right)\pmod{3^5} &\text{if $3\mid\mid(x+y)$,}\\
    (-1)^{\alpha/2}p^{6\alpha}\pmod{3^5} &\text{if $9\mid(x+y)$,}
    \end{cases}
\end{align}

Finally, let $p\equiv1\pmod{12}$. Since $p\equiv1\pmod3$, therefore we can write $p=z^2+3w^2=(z+w\sqrt{-3})(z-w\sqrt{-3})$ for some $z.w\in\mathbb Z$ with $z\equiv1\pmod3$. Moreover, as $z^2+3w^2\equiv1\pmod4$, we must have $z$ odd and $w$ even and thus we have $z+w\equiv z-w\pmod4$. Hence, we have
\begin{align}\label{eq:13}
    t_{1\pm}(p)=
    \begin{cases}
    (z+w\sqrt{-3})^{12}+(z-w\sqrt{-3})^{12} &\text{if $z+w\equiv1\equiv z-w\pmod4$,}\\
    -(z+w\sqrt{-3})^{12}-(z-w\sqrt{-3})^{12} &\text{if $z+w\equiv3\equiv z-w\pmod4$.}
    \end{cases}
\end{align}
Since $p\equiv1\pmod4$, therefore we can write $p=x^2+y^2=(x+iy)(x-iy)$ for some $x,y\in\mathbb Z$ with either $x$ odd, $y$ even or $x$ even, $y$ odd. Moreover, as $x^2+y^2\equiv1\pmod3$, we can choose $x\equiv1\pmod3$ and $y\equiv0\pmod3$. Hence, we have
\begin{align}\label{eq:17}
    t_{2\pm}(p)=
    \begin{cases}
    (x+iy)^{12}+(x-iy)^{12} &\text{if $x$ odd, $y$ even,}\\
    -(x+iy)^{12}-(x-iy)^{12} &\text{if $x$ even, $y$ odd.}
    \end{cases}
\end{align}
From (\ref{eq:9}), it is clear that $t_{1+}(p)+t_{1-}(p)-t_{2+}(p)-t_{2-}(p)\equiv0\pmod{3^4}$. Note that
\begin{align*}
    \pm\left((z+w\sqrt{-3})^{12}+(z-w\sqrt{-3})^{12}+(x+iy)^{12}+(x-iy)^{12}\right)\equiv\pm2(x^{12}+z^{12})\equiv\pm1\not\equiv0\pmod3.
\end{align*}
Thus, we must have if $x$ odd, $y$ even then $z+w\equiv1\equiv z-w\pmod4$ and if $x$ even, $y$ odd then $z+w\equiv3\equiv z-w\pmod4$. In view of the equation $x^2+y^2=z^2+3w^2$, we can conclude that
\begin{align*}
    t_{1\pm}(p)^\alpha\equiv((-1)^y)^\alpha\left(2^\alpha x^{12\alpha}+12\alpha2^{\alpha-1}x^{12\alpha-2}y^2\right)\pmod{3^5}.
\end{align*}
We can easily conclude that
\begin{align*}
    t_{2\pm}(p)^\alpha\equiv((-1)^y)^\alpha\left(2^\alpha x^{12\alpha}+111\alpha2^{\alpha-1}x^{12\alpha-2}y^2\right)\pmod{3^5}.
\end{align*}
Also, for any $n$
\begin{align*}
    p^{12n}=(x^2+y^2)^{12n}\equiv x^{24n}+12nx^{24n-2}y^2\pmod{3^5}.
\end{align*}
Now by (\ref{eq:5}), we have for $\alpha=2\beta$,
\begin{align}
    t_{1\pm}(p^\alpha)&\equiv\left(\sum_{\delta=0}^\beta(-1)^\delta\binom{2\beta-\delta}{\delta}2^{2(\beta-\delta)}\right)x^{24\beta}+\left(\sum_{\delta=0}^\beta(-1)^\delta\binom{2\beta-\delta}{\delta}2^{2(\beta-\delta)}\right)12\beta x^{24\beta-2}y^2\pmod{3^5}\label{eq:21}\\
    &\equiv\left(\alpha+1\right)x^{12\alpha}+6\alpha\left(\alpha+1\right)x^{12\alpha-2}y^2\pmod{3^5},\notag\\
    t_{2\pm}(p^\alpha)&\equiv\left(\sum_{\delta=0}^\beta(-1)^\delta\binom{2\beta-\delta}{\delta}2^{2(\beta-\delta)}\right)x^{24\beta}\label{eq:22}\\
    &\quad+\left(\sum_{\delta=0}^\beta(-1)^\delta\binom{2\beta-\delta}{\delta}2^{2(\beta-\delta)}(111(\beta-\delta)+12\delta)\right)x^{24\beta-2}y^2\pmod{3^5}\notag\\
    &\equiv\left(\alpha+1\right)x^{12\alpha}+123\alpha(\alpha+1)(11\alpha+26)x^{12\alpha-2}y^2\pmod{3^5}\notag.
\end{align}
And by (\ref{eq:6}), we have for $\alpha=2\beta+1$,
\begin{align}
    t_{1\pm}(p^\alpha)&\equiv(-1)^y\Bigg(\left(\sum_{\delta=0}^\beta(-1)^\delta\binom{2\beta+1-\delta}{\delta}2^{2(\beta-\delta)+1}\right)x^{24\beta+12}\label{eq:23}\\
    &\quad+\left(\sum_{\delta=0}^\beta(-1)^\delta\binom{2\beta+1-\delta}{\delta}2^{2(\beta-\delta)}\right)12(2\beta+1)x^{24\beta+10}y^2\Bigg)\pmod{3^5}\notag\\
    &\equiv(-1)^y\left((\alpha+1)x^{12\alpha}+6\alpha(\alpha+1)x^{12\alpha-2}y^2\right)\pmod{3^5},\notag\\
    t_{2\pm}(p^\alpha)&\equiv(-1)^y\Bigg(\left(\sum_{\delta=0}^\beta(-1)^\delta\binom{2\beta+1-\delta}{\delta}2^{2(\beta-\delta)+1}\right)x^{24\beta+12}\label{eq:24}\\
    &\quad+\left(\sum_{\delta=0}^\beta(-1)^\delta\binom{2\beta+1-\delta}{\delta}2^{2(\beta-\delta)}(111(2\beta+1-2\delta)+12(2\delta))\right)x^{24\beta+10}y^2\Bigg)\pmod{3^5}\notag\\
    &\equiv(-1)^y\left((\alpha+1)x^{12\alpha}+123\alpha(\alpha+1)(11\alpha+26)x^{12\alpha-2}y^2\right)\pmod{3^5}\notag.
\end{align}

We now proceed to complete the proof. Let there exist a prime $p\equiv11\pmod{12}$ with $ord_p(12n+13)$ odd. By (\ref{eq:10}), it is clear that $b_{27}(n)\equiv0\pmod3$. Assume $ord_p(12n+13)$ is even for all $p\equiv11\pmod{12}$. Again by (\ref{eq:10}), we have
\begin{align*}
    \prod_{\substack{p\mid(12n+13)\\p\equiv11(12)}}t_{1\pm}(p^\alpha)=\prod_{\substack{p\mid(12n+13)\\p\equiv11(12)}}p^{6\alpha}=\prod_{\substack{p\mid(12n+13)\\p\equiv11(12)}}t_{2\pm}(p^\alpha),
\end{align*}
and $3\nmid p^{6\alpha}$ for all $p\equiv11\pmod{12}$. Thus,
\begin{align*}
    &b_{27}(n)\equiv0\pmod3\\
    &\Longleftrightarrow\prod_{\substack{p\mid(12n+13)\\p\not\equiv11(12)}}t_{1+}(p^\alpha)+\prod_{\substack{p\mid(12n+13)\\p\not\equiv11(12)}}t_{1-}(p^\alpha)\equiv\prod_{\substack{p\mid(12n+13)\\p\not\equiv11(12)}}t_{2+}(p^\alpha)+\prod_{\substack{p\mid(12n+13)\\p\not\equiv11(12)}}t_{2-}(p^\alpha)\pmod{3^5}.
\end{align*}

Let there exist a prime $p\equiv7\pmod{12}$ with $ord_p(12n+13)$ odd. By (\ref{eq:11}), it is clear that
\begin{align*}
    b_{27}(n)\equiv0\pmod3\Longleftrightarrow\prod_{\substack{p\mid(12n+13)\\p\not\equiv11(12)}}t_{1+}(p^\alpha)+\prod_{\substack{p\mid(12n+13)\\p\not\equiv11(12)}}t_{1-}(p^\alpha)\equiv0\pmod{3^5}.
\end{align*}
Note, in view of (\ref{eq:12}) and (\ref{eq:13}), that if $p\equiv1,5\pmod{12}$ then $t_{1+}(p^\alpha)=t_{1-}(p^\alpha)$ for any $\alpha$. Thus, we have
\begin{align*}
    \prod_{\substack{p\mid(12n+13)\\p\not\equiv11(12)}}t_{1+}(p^\alpha)+\prod_{\substack{p\mid(12n+13)\\p\not\equiv11(12)}}t_{1-}(p^\alpha)=\prod_{\substack{p\mid(12n+13)\\p\equiv1,5(12)}}t_{1+}(p^\alpha)\left(\prod_{\substack{p\mid(12n+13)\\p\equiv7(12)}}t_{1+}(p^\alpha)+\prod_{\substack{p\mid(12n+13)\\p\equiv7(12)}}t_{1-}(p^\alpha)\right).
\end{align*}
Also note, in view of (\ref{eq:14}), that if $p\equiv7\pmod{12}$ then $t_{1+}(p^\alpha)=t_{1-}(p^\alpha)$ for any even $\alpha$. As $t_{1+}(p^\alpha)=-t_{1-}(p^\alpha)$ for any odd $\alpha$, we have
\begin{align*}
    \prod_{\substack{p\mid(12n+13)\\p\equiv7(12)}}t_{1+}(p^\alpha)+\prod_{\substack{p\mid(12n+13)\\p\equiv7(12)}}t_{1-}(p^\alpha)&=\prod_{\substack{p\mid(12n+13)\\p\equiv7(12)\\\alpha \text{ even}}}t_{1+}(p^\alpha)\left(\prod_{\substack{p\mid(12n+13)\\p\equiv7(12)\\\alpha \text{ odd}}}t_{1+}(p^\alpha)+\prod_{\substack{p\mid(12n+13)\\p\equiv7(12)\\\alpha \text{ odd}}}t_{1-}(p^\alpha)\right)\\
    &=(1+(-1)^u)\prod_{\substack{p\mid(12n+13)\\p\equiv7(12)\\\alpha \text{ even}}}t_{1+}(p^\alpha)\prod_{\substack{p\mid(12n+13)\\p\equiv7(12)\\\alpha \text{ odd}}}t_{1+}(p^\alpha),
\end{align*}
where $u$ is the number of odd $\alpha$. If $u$ is odd, clearly $b_{27}(n)\equiv0\pmod3$. Suppose $u$ is even. Using (\ref{eq:15}) it can be verified that for any two primes $p_1,p_2\equiv7\pmod{12}$, $t_{1+}(p_1)t_{1+}(p_2)\equiv0\pmod{3^5}$. Thus, we get that $b_{27}(n)\equiv0\pmod{3}$. Assume $ord_p(12n+13)$ is even for all $p\equiv7\pmod{12}$. By (\ref{eq:11}) and (\ref{eq:16}), we have
\begin{align*}
    \prod_{\substack{p\mid(12n+13)\\p\equiv7(12)}}t_{1\pm}(p^\alpha)\equiv\prod_{\substack{p\mid(12n+13)\\p\equiv7(12)}}p^{6\alpha}\equiv\prod_{\substack{p\mid(12n+13)\\p\equiv7(12)}}t_{2\pm}(p^\alpha)\pmod{3^5},
\end{align*}
and $3\nmid p^{6\alpha}$ for all $p\equiv7\pmod{12}$. Thus,
\begin{align*}
    &b_{27}(n)\equiv0\pmod3\\
    &\Longleftrightarrow\prod_{\substack{p\mid(12n+13)\\p\equiv1,5(12)}}t_{1+}(p^\alpha)+\prod_{\substack{p\mid(12n+13)\\p\equiv1,5(12)}}t_{1-}(p^\alpha)\equiv\prod_{\substack{p\mid(12n+13)\\p\equiv1,5(12)}}t_{2+}(p^\alpha)+\prod_{\substack{p\mid(12n+13)\\p\equiv1,5(12)}}t_{2-}(p^\alpha)\pmod{3^5}.
\end{align*}

Let there exist a prime $p\equiv5\pmod{12}$ with $ord_p(12n+13)$ odd. By (\ref{eq:12}), it is clear that
\begin{align*}
    b_{27}(n)\equiv0\pmod3\Longleftrightarrow\prod_{\substack{p\mid(12n+13)\\p\equiv1,5(12)}}t_{2+}(p^\alpha)+\prod_{\substack{p\mid(12n+13)\\p\equiv1,5(12)}}t_{2-}(p^\alpha)\equiv0\pmod{3^5}.
\end{align*}
Note, in view of (\ref{eq:17}), that if $p\equiv1\pmod{12}$ then $t_{2+}(p^\alpha)=t_{2-}(p^\alpha)$ for any $\alpha$. Thus we have
\begin{align*}
    \prod_{\substack{p\mid(12n+13)\\p\equiv1,5(12)}}t_{2+}(p^\alpha)+\prod_{\substack{p\mid(12n+13)\\p\equiv1,5(12)}}t_{2-}(p^\alpha)=\prod_{\substack{p\mid(12n+13)\\p\equiv1(12)}}t_{2+}(p^\alpha)\left(\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)}}t_{2+}(p^\alpha)+\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)}}t_{2-}(p^\alpha)\right).
\end{align*}
Also note, in view of (\ref{eq:18}), that if $p\equiv5\pmod{12}$ then $t_{2+}(p^\alpha)=t_{2-}(p^\alpha)$ for any even $\alpha$. As $t_{1+}(p^\alpha)=-t_{1-}(p^\alpha)$ for any odd $\alpha$, we have
\begin{align*}
    \prod_{\substack{p\mid(12n+13)\\p\equiv5(12)}}t_{2+}(p^\alpha)+\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)}}t_{2-}(p^\alpha)&=\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)\\\alpha \text{ even}}}t_{2+}(p^\alpha)\left(\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)\\\alpha \text{ odd}}}t_{2+}(p^\alpha)+\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)\\\alpha \text{ odd}}}t_{2-}(p^\alpha)\right)\\
    &=(1+(-1)^u)\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)\\\alpha \text{ even}}}t_{2+}(p^\alpha)\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)\\\alpha \text{ odd}}}t_{2+}(p^\alpha),
\end{align*}
where $u$ is the number of odd $\alpha$. If $u$ is odd, clearly $b_{27}(n)\equiv0\pmod3$. Suppose $u$ is even. Using (\ref{eq:19}) it can be verified that for any two primes $p_1,p_2\equiv5\pmod{12}$, when written as $p_i=x_i^2+y_i^2$ for $i=1,2$,
\begin{align*}
    t_{2+}(p_1)t_{2+}(p_2)\equiv
    \begin{cases}
    81 \text{ or } 162 &\text{if $3\mid\mid(x_i+y_1)$ for both $i=1,2$,}\\
    0 &\text{if either $9\mid(x_1+y_1)$ or $9\mid(x_2+y_2)$.}
    \end{cases}
\end{align*}
Thus, if $u\geq4$ then $b_{27}(n)\equiv0\pmod3$. For $u=2$, if either $9\mid(x_1+y_1)$ or $9\mid(x_2+y_2)$ then also $b_{27}(n)\equiv0\pmod3$. Suppose $u=2$ and $3\mid\mid(x_i+y_1)$ for both $i=1,2$. In view of (\ref{eq:20}), we get
\begin{align*}
    \prod_{\substack{p\mid(12n+13)\\p\equiv5(12)\\\alpha \text{ even}}}t_{2+}(p^\alpha)\not\equiv0\pmod3.
\end{align*}
Hence, in view of (\ref{eq:22}) and (\ref{eq:24}), we get
\begin{align*}
  b_{27}(n)\equiv0\pmod3&\Longleftrightarrow\prod_{\substack{p\mid(12n+13)\\p\equiv1(12)}}t_{2+}(p^\alpha)\equiv0\pmod3\\
  &\Longleftrightarrow\exists\quad p\equiv1\pmod{12} \quad \text{with} \quad ord_p(12n+13)\equiv2\pmod3.
\end{align*}
Assume $ord_p(12n+13$ is even for all $p\equiv5\pmod{12}$. By (\ref{eq:12}) and (\ref{eq:20}), we have
\begin{align}
    \prod_{\substack{p\mid(12n+13)\\p\equiv5(12)}}t_{1\pm}(p^\alpha)&=\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)}}(-1)^{\alpha/2}p^{6\alpha},\notag\\
    \prod_{\substack{p\mid(12n+13)\\p\equiv5(12)}}t_{2\pm}(p^\alpha)&\equiv\underbrace{\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)}}\left((-1)^{\alpha/2-1}\frac{(\alpha+2)\alpha}{8}p^{6\alpha-12}162+(-1)^{\alpha/2}p^{6\alpha}\right)}_\text{those $p$ for which $3\mid\mid(x+y)$}\label{eq:25}\\
    &\quad\times\underbrace{\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)}}(-1)^{\alpha/2}p^{6\alpha}}_\text{those $p$ for which $9\mid(x+y)$}\pmod{3^5}\notag\\
    &\equiv k\cdot81+\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)}}(-1)^{\alpha/2}p^{6\alpha}\pmod{3^5}\notag,
\end{align}
where $k$ is defined in (\ref{eq:26}).

Assume $k\equiv0\pmod3$. We have
\begin{align*}
    &b_{27}(n)\equiv0\pmod3\\
    \Longleftrightarrow&\prod_{\substack{p\mid(12n+13)\\p\equiv1(12)}}t_{1+}(p^\alpha)\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)}}(-1)^{\alpha/2}p^{6\alpha}\equiv\prod_{\substack{p\mid(12n+13)\\p\equiv1(12)}}t_{2+}(p^\alpha)\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)}}(-1)^{\alpha/2}p^{6\alpha}\pmod{3^5}\\
    \Longleftrightarrow&\prod_{\substack{p\mid(12n+13)\\p\equiv1(12)}}t_{1+}(p^\alpha)\equiv\prod_{\substack{p\mid(12n+13)\\p\equiv1(12)}}t_{2+}(p^\alpha)\pmod{3^5}.
\end{align*}
Suppose $ord_{p_1}(12n+13)=ord_{p_2}(12n+13)=\cdots=ord_{p_r}(12n+13)=\alpha$, $p_l\equiv1\pmod{12}$ for each $l$. In view of (\ref{eq:21}), (\ref{eq:22}), (\ref{eq:23}) and (\ref{eq:24}), we have
\begin{align*}
    \prod_{l=1}^r t_{1+}(p_l^\alpha)&\equiv((-1)^{y_1+\cdots+y_r})^\alpha\prod_{l=1}^r\left((\alpha+1)x_l^{12\alpha}+6\alpha(\alpha+1)x_l^{12\alpha-2}y_l^2\right)\pmod{3^5}\\
    &\equiv((-1)^{y_1+\cdots+y_r})^\alpha(\alpha+1)^r\\
    &\quad\times\left((x_1\cdots x_r)^{12\alpha}+6\alpha(x_1\cdots x_r)^{12\alpha-2}\sum_{\substack{i_1<\cdots<i_{r-1}\\j\neq i_s}}(x_{i_1}\cdots x_{i_{r-1}}y_j)^2\right)\pmod{3^5},\\
    \prod_{l=1}^r t_{2+}(p_l^\alpha)&\equiv((-1)^{y_1+\cdots+y_r})^\alpha\prod_{l=1}^r\left((\alpha+1)x_l^{12\alpha}+123\alpha(\alpha+1)(11\alpha+26)x_l^{12\alpha-2}y_l^2\right)\pmod{3^5}\\
    &\equiv((-1)^{y_1+\cdots+y_r})^\alpha(\alpha+1)^r\\
    &\quad\times\left((x_1\cdots x_r)^{12\alpha}+123\alpha(11\alpha+26)(x_1\cdots x_r)^{12\alpha-2}\sum_{\substack{i_1<\cdots<i_{r-1}\\j\neq i_s}}(x_{i_1}\cdots x_{i_{r-1}}y_j)^2\right)\pmod{3^5}
\end{align*}
Thus, going by the notations of (\ref{eq:29}), (\ref{eq:27}) and (\ref{eq:28}), we get
\begin{align*}
    &\prod_{\substack{p\mid(12n+13)\\p\equiv1(12)}}t_{1+}(p^\alpha)\equiv\prod_{\substack{p\mid(12n+13)\\p\equiv1(12)}}t_{2+}(p^\alpha)\pmod{3^5}\\
    \Longleftrightarrow&\prod_\alpha(\alpha+1)^{r_\alpha}(A_\alpha+6\alpha B_\alpha)\equiv\prod_\alpha(\alpha+1)^{r_\alpha}(A_\alpha+123\alpha(11\alpha+26)B_\alpha)\pmod{3^5},
\end{align*}
where the product is taken over all distinct $\alpha=ord_p(12n+13)$ with $p\equiv1\pmod{12}$. Since $B_\alpha\equiv0\pmod9$ for each $\alpha$, therefore expanding the products on both sides involving the terms $A_\alpha, B_\alpha$ and comparing we obtain
\begin{align*}
    &\prod_{\substack{p\mid(12n+13)\\p\equiv1(12)}}t_{1+}(p^\alpha)\equiv\prod_{\substack{p\mid(12n+13)\\p\equiv1(12)}}t_{2+}(p^\alpha)\pmod{3^5}\\
    \Longleftrightarrow&6\left(\prod_\alpha(\alpha+1)^{r_\alpha}\right)\left(\sum_\alpha\left(\alpha B_\alpha\prod_{\beta\neq\alpha}A_\beta\right)\right)\\
    &\qquad\qquad\equiv123\left(\prod_\alpha(\alpha+1)^{r_\alpha}\right)\left(\sum_\alpha\left(\alpha(11\alpha+26)B_\alpha\prod_{\beta\neq\alpha}A_\beta\right)\right)\pmod{3^5}\\
    \Longleftrightarrow&2\left(\prod_\alpha(\alpha+1)^{r_\alpha}\right)\left(\sum_\alpha\left(\alpha B_\alpha\prod_{\beta\neq\alpha}A_\beta\right)\right)\\
    &\qquad\qquad\equiv41\left(\prod_\alpha(\alpha+1)^{r_\alpha}\right)\left(\sum_\alpha\left(\alpha(11\alpha+26)B_\alpha\prod_{\beta\neq\alpha}A_\beta\right)\right)\pmod{3^4}
\end{align*}

Assume $k\equiv\varepsilon\pmod3$ in (\ref{eq:25}) where $\varepsilon=1$ or $2$. We have
\begin{align*}
    &b_{27}(n)\equiv0\pmod3\\
    \Longleftrightarrow&\prod_{\substack{p\mid(12n+13)\\p\equiv1(12)}}t_{1+}(p^\alpha)\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)}}(-1)^{\alpha/2}p^{6\alpha}\equiv\prod_{\substack{p\mid(12n+13)\\p\equiv1(12)}}t_{2+}(p^\alpha)\left(81\varepsilon+\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)}}(-1)^{\alpha/2}p^{6\alpha}\right)\pmod{3^5}\\
    \Longleftrightarrow&\prod_{\substack{p\mid(12n+13)\\p\equiv1(12)}}t_{1+}(p^\alpha)\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)}}(-1)^{\alpha/2}p^{6\alpha}\equiv(81d+1)\prod_{\substack{p\mid(12n+13)\\p\equiv1(12)}}t_{2+}(p^\alpha)\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)}}(-1)^{\alpha/2}p^{6\alpha}\pmod{3^5}\\
    \Longleftrightarrow&\prod_{\substack{p\mid(12n+13)\\p\equiv1(12)}}t_{1+}(p^\alpha)\equiv(81d+1)\prod_{\substack{p\mid(12n+13)\\p\equiv1(12)}}t_{2+}(p^\alpha)\pmod{3^5}\\
    \Longleftrightarrow&2\left(\prod_\alpha(\alpha+1)^{r_\alpha}\right)\left(\sum_\alpha\left(\alpha B_\alpha\prod_{\beta\neq\alpha}A_\beta\right)\right)\\
    &\qquad\qquad\equiv41(81d+1)\left(\prod_\alpha(\alpha+1)^{r_\alpha}\right)\left(\sum_\alpha\left(\alpha(11\alpha+26)B_\alpha\prod_{\beta\neq\alpha}A_\beta\right)\right)\pmod{3^4}
\end{align*}
where $d=\varepsilon d'$, $d'\in\mathbb Z$ is the inverse of $\prod_{\substack{p\mid(12n+13)\\p\equiv5(12)}}(-1)^{\alpha/2}p^{6\alpha}$ in $(\mathbb Z/3^5\mathbb Z)^*$.

\section*{\textbf{Acknowledgement}}

The author is thankful to Prof. Srilakshmi Krishnamoorthy for introducing this particular area of research. The author is also thankful to Prof. David Penniston for his invaluable initial guidance regarding the scope of research in this area.


TITLE: Two ambient isotopic curve segments, one has the length and the other does not
QUESTION [2 upvotes]: Let me ask if the following is possible:
Let $L_1$ be some curve segment in the $\mathbb{R}^3$ space which has the length $1$.
Let $L_2$ be some curve segment in the $\mathbb{R}^3$ space which you can not define the length.
Then some $\mathbb{R}^3$ ambient isotopy takes $L_1$ to $L_2$.
In other words, can an $\mathbb{R}^3$ ambient isotopy take $L_1$ to some which you can not define the length?
Thank you in advance.

REPLY [2 votes]: Sure, why not? Pick a non-rectifiable Jordan curve in $\Bbb R^2$. There are lots of those. By the Schoenflies theorem there's an orientation preserving homeomorphism of $\Bbb R^2$ that takes the ugly curve to the standard circle. Now invoke that every orientation preserving homeomorphism of $\Bbb R^2$ is isotopic to the identity. Now cross all this with $\Bbb R$.


TITLE: Proving the following identity
QUESTION [0 upvotes]: Prove that
$${ \left( \frac { \cos  (\alpha +\beta ) }{ \cos  (\alpha -\beta ) } -\frac { \cos  (\alpha +\gamma ) }{ \cos  (\alpha -\gamma ) }  \right)  }^{ 2 }+{ \left( \frac { \sin  (\alpha +\beta ) }{ \cos  (\alpha -\beta ) } -\frac { \sin  (\alpha +\gamma ) }{ \cos  (\alpha -\gamma ) }  \right)  }^{ 2 }={ \left( \sec ^{ 2 }{ (\alpha -\beta ) } \sin ^{ 2 }{ (\beta -\gamma ) } \sec ^{ 2 }{ (\gamma -\alpha ) }  \right)  }$$
I brought everything to the common denominator noticing bot the fractions had the same denominator but after that I find I am stick with a mess

REPLY [0 votes]: We easily get LHS $ = \sec^2 (\alpha - \beta)+\sec^2 (\alpha-\gamma) - \dfrac{2\cos (\beta -\gamma)}{\cos (\alpha - \beta) \cos (\alpha - \gamma)}$
$= \sec^2 (\alpha - \beta)+\sec^2 (\alpha-\gamma) - \dfrac{2\cos (\beta -\alpha+\alpha-\gamma)}{\cos (\alpha - \beta) \cos (\alpha - \gamma)}$
$=\sec^2 (\alpha - \beta)+\sec^2 (\alpha-\gamma) -2 + 2\tan (\beta-\alpha) \tan (\alpha-\gamma)$
$=\tan^2 (\alpha - \beta)+\tan^2 (\alpha-\gamma)  + 2\tan (\beta-\alpha) \tan (\alpha-\gamma)$
$=\left(\tan (\beta-\alpha)+\tan  (\alpha-\gamma)\right)^2$
Now using $\tan A + \tan B = \dfrac{\sin (A+B)}{\cos A \cos B}$ we get further
$\left(\dfrac{\sin (\beta - \gamma)}{\cos (\beta -\alpha) \cos (\alpha-\gamma)}\right)^2$
$=\sec^2 (\beta -\alpha) \sin^2 (\beta - \gamma) \sec^2 (\alpha-\gamma)$ = RHS


TITLE: About partial derivatives
QUESTION [3 upvotes]: I'm reading the book "Teichmüller Theory and Applications to Geometry, Topology and Dynamics" by Hubbard and I have the following problem.
I need to compute $$\frac{d}{ds}\frac{\overline{\partial}z+\mu(t+s)\overline{z}}{\partial z+\mu(t+s)\overline{z}},$$ in $s=0$ and where $\mu$ is a Beltrami form on a Riemann Surface $X$ and $t\in[0,1]$. The books says that the complex derivatives are computed with respect to analytic coordinates on $X_{t\mu}$, i.e., with respect to $w=z+t\mu\overline{z}$. Then $$z=\frac{w-t\mu\overline{w}}{1-t^2|\mu|^2},\quad \overline{z}=\frac{\overline{w}-t\overline{\mu}{w}}{1-t^2|\mu|^2},$$ so that $$z+\mu(t+s)\overline{z}=\frac{w(1-t(t+s)|\mu|^2)+s\mu\overline{w}}{1-t^2|\mu|^2}$$
and the ratio of the derivatives becomes $$\left(\frac{\mu}{1-t(t+s)|\mu|^2}\right)\frac{d\overline{w}}{dw}.
$$
I understand all the calculations before the last step, but I think that the ratio of the derivatives will be $$\left(\frac{s\mu}{1-t(t+s)|\mu|^2}\right)\frac{d\overline{w}}{dw}.
$$
What I'm missing?
Thanks in advance !

REPLY [0 votes]: For future reference, this is equation 6.6.30 in Hubbard's book on Teichmueller theory Vol. 1.
You are correct, for this equation to be correct is should read:
$$\frac{d}{ds}\left(\frac{s\mu}{1-t(t+s)|\mu|^2}\right)\frac{d\overline{w}}{dw}\Big|_{s=0}=\frac{\mu}{1-t^2|\mu|^2}\frac{d\overline{w}}{dw}.$$
This is a typo, since Hubbard ends up obtaining the correct result on the right hand side of the equation.


TITLE: Associativity of the exterior multiplication of forms.
QUESTION [4 upvotes]: Let $\omega^{k}\in\bigwedge^{k}(V^{*})$ and $\eta^{l}\in\bigwedge^{l}(V^{*})$, be two exterior forms of degrees $k$ and $l$. The exterior product $\omega^{k}\wedge\eta^{l}$ is defined as $(k+l)$ form, by $$\omega^{k}\wedge\eta^{l}(v_{1},...,v_{k+l})=\dfrac{1}{k!l!}\sum_{\sigma\in S_{k+l}}{\operatorname{sgn}(\sigma)\omega^{k}(v_{\sigma(1)},...,v_{\sigma(k)})\eta^{l}(v_{k+1},...,v_{k+l})}$$
I wanna proof the exterior product has the following property: $(\omega^{k}\wedge\eta^{l})\wedge\mu^{m}=\omega^{k}\wedge(\eta^{l}\wedge\mu^{m})$
My approach: Note that, $\omega^{k}\wedge\eta^{l}$ is a multilinear and antisymmetric map acting on $(k+l)$ vectors. Then $$((\omega^{k}\wedge\eta^{l})\wedge\mu^{m})(v_{1},..v_{k+l+m})=$$
$$\dfrac{1}{(k+l)!m!}\sum_{\sigma\in S_{k+l+m}}{\operatorname{sgn}(\sigma)(\omega^{k}\wedge\eta^{l})(v_{\sigma(1)}.,v_{\sigma(k+l)})\mu^{m}(v_{k+l+1},.,v_{k+l+m})}$$
And now, descompose the permutation group $S_{k+l+m}$ into residual classes with respect to the subgroup $S_{k+l}\subset S_{k+l+m}$ formed by all permutations acting as the identity on the last m indices, then each residue class R thus consists of all permutations $\sigma\in S_{k+l+m}$ with fixed values $\sigma(k+l+1),...,\sigma(k+l+m)$, but how I can continuous?

REPLY [3 votes]: Let us call $\mathcal C$ the set of these residue classes. Note that each $R\in\mathcal C$ is isomorph to $S_{k+l}$. Choose one class $R$ and, within $R$, a particular permutation $\sigma_R$. Each element $\sigma\in R$ can be decomposed as $\sigma=\sigma_R\circ \pi$ where $\pi\in S_{k+l}$. Then:
$$
\DeclareMathOperator{\sgn}{sgn}
\begin{multline}
((w\wedge\eta)\wedge \mu)(v_1,\dots v_{k+l+m}) =\frac{1}{(k+l)!m!}\sum_{R\in\mathcal C} \sgn(\sigma_R)\left(\sum_{\sigma\in R}\sgn(\pi)\,(w\wedge\eta)(v_{\sigma(1)},\dots v_{\sigma(k+l)})\right) \\
 \mu(v_{\sigma_R(k+l+1)},\dots v_{\sigma_R(k+l+m)})
\end{multline}
$$
Now, note that all terms in the large parenthesis are equal, because they are permutations $\pi$ from a fixed ordering given by $\sigma_R$. Since $R$ is isomorph to $S_{k+l}$, there are $(k+l)!$ such terms, so:
$$
\DeclareMathOperator{\sgn}{sgn}
\begin{multline}
((w  \wedge\eta)\wedge \mu)  (v_1,\dots v_{k+l+m}) =\frac{1}{m!}\sum_{R\in\mathcal C}\sgn(\sigma_R) \,(w\wedge\eta)(v_{\sigma_R(1)},\dots v_{\sigma_R(k+l)})\,\mu(v_{\sigma_R(k+l+1)},\dots v_{\sigma_R(k+l+m)}) \\
=\frac{1}{k!l!m!}\sum_{R\in\mathcal C}\sgn(\sigma_R)\sum_{\tau\in S_{k+l}}  \sgn(\tau)\,w(v_{\tau(\sigma_R(1))},\dots v_{\tau(\sigma_R(k))})  \, \eta(v_{\tau(\sigma_R(k+1))},\dots v_{\tau(\sigma_R(k+l))}) \\\mu(v_{\sigma_R(k+l+1)},\dots v_{\sigma_R(k+l+m)})
\end{multline}
$$
But, again, all permutations $\sigma\in S_{k+l+m}$ can be decomposed as $\sigma=\tau\circ\sigma_R$ and, since $\tau$ acts as the identity on the last $m$ indices, we have $\sigma=\sigma_R$ for these indices used in the arguments of $\mu$. Thus we finally obtain:
$$
\DeclareMathOperator{\sgn}{sgn}
\begin{multline}
((w\wedge\eta)\wedge \mu)(v_1,\dots v_{k+l+m}) =\frac{1}{k!l!m!}\sum_{\sigma\in S_{k+l+m}}\sgn(\sigma)\,w(v_{\sigma(1)},\dots v_{\sigma(k)})  \, \eta(v_{\sigma(k+1)},\dots v_{\sigma(k+l)}) \\\mu(v_{\sigma(k+l+1)},\dots v_{\sigma(k+l+m)})
\end{multline}
$$
and the product does not depend on the order we associate the operations. $\square$
NOTE: By your wording I guess you are (or were, sorry I am late) reading Global Analysis by Agricola and Friedrichs. I am with it now :)


TITLE: kernel of linear combination
QUESTION [1 upvotes]: Let $T,S: V\to V$ be 2 linear transformations, and $\ker(T)=\{0\}$.
I need to prove why $\ker(T\circ S)=\ker(S)$.
I have no idea how to prove it.

REPLY [6 votes]: Since $\ker T = \{ 0 \}$, $T$ is injective. Therefore, $(T \circ S)v=0$ if and only if $Sv=0$.
[Both of these results require proofs, but I presume that you've either seen them before or can prove them yourself.]