# Additive regularization schedule for neural architecture search

Mark Potanin, Kirill Vayser, and Vadim Strijov111E-mail<EMAIL_ADDRESS>
###### Abstract

Neural network structures have a critical impact on the accuracy and stability
of forecasting. Neural architecture search procedures help design an optimal
neural network according to some loss function, which represents a set of
quality criteria. This paper investigates the problem of neural network
structure optimization. It proposes a way to construct a loss function, which
contains a set of additive elements. Each element is called the regularizer.
It corresponds to some part of the neural network structure and represents a
criterion to optimize. The optimization procedure changes the structure in
iterations. To optimize various parts of the structure, the procedure changes
the set of regularizers according to some schedule. The authors propose a way
to construct the additive regularization schedule. By comparing regularized
models with non-regularized ones for a collection of datasets the
computational experiments show that the proposed method finds efficient neural
network structure and delivers accurate networks of low complexity.

Keywords: machine learning; data science; stochastic processes; genetic
algorithms; neural architecture search; additive regularization

##  1 Introduction

A deep learning neural network of optimal structure approximates data as
accurately as possible. It models the initial unknown dependence of the target
variable $y$ given vectors $\mathbf{x}$ of the feature space. The model maps
the input $\mathbf{x}$ to the target $y$ as $f:(\mathbf{x},\mathbf{W})\mapsto
y$. In general, the deep learning model is a superposition of neurons:
generalized linear models and activation functions. It can contain a large
number of layers and neurons. It is assumed that the more complex the model,
the higher its approximation accuracy, that is, the lower the value of the
error function. The paper [1] enlightens the influence of the method of
constructing the error function on the choice of the structure of the deep
learning model.

We have to develop a method to reduce the complexity of the model while
maintaining its accuracy. The quality function consists of an approximation
loss function and a set of additive regularization elements to optimize the
model structure and parameters. These additive elements are weighted, so that
the quality function is treated as some linear combination. The authors
proposed a method, which set a schedule of the model structure optimization.
During the optimization procedure, the error function includes and excludes
certain regularization elements to choose the optimal structure.

_Regularization_ is a method to optimize the model parameters. It includes to
the loss function additional elements called regularizers $\mathcal{R}_{i}$.
Each element takes into account the specific requirements of the problem being
solved to modify the structure and the parameters of the model during the
optimization procedure. Regularization increases the stability of the forecast
in the case of multiple correlation of model parameters or variables of the
feature space. It promotes increasing the generalizing ability of the model
and reducing the risk of overfitting [2]. _Additive regularization_ is a kind
of regularization based on optimization of the weighted sum of regularizers.

The object of our research is a method of the error function constructing. We
study the influence of the weights of regularizes (1) on the complexity and
accuracy of the model. The additive regularization function [3] is

$L=\sum_{i=1}^{r}\lambda_{i}\mathcal{R}_{i},$

where $\mathcal{R}_{i}$ is a regularizer. It modifies parameters of the model
during optimization. Call the _metaparameters_ the weights of the regularizers
$\lambda_{i}$.

#### Method.

Values of the metaparameters $\lambda_{i}$ are changed in the run of the
structure optimization procedure. This change is called the  _optimization
schedule_. Unlike the regularization for linear models, metaparameters of
additive regularization are assigned to each of the layers of the neural
network. For example, an element of an error function with additive
regularization $\mathcal{R}$ is

$\lambda\|\mathbf{w}\|_{2}^{2},$

where $\lambda$ is the metaparameter of the error function, and $\mathbf{w}$
is the model parameters.

Varying the values of metaparameters adds or removes from consideration
individual terms of additive regularization, and changes their impact on the
error function. Individual regularizers for each layer of the neural network
are added to the error function, which is added sequentially. Our search for a
model structure works through the addition or removal of elements from the
structure of a neural network using a genetic algorithm. We call it GA-NAS
(Genetic Algorithm for Neural Architecture Search). The _structural
complexity_ of a neural network is the number of model parameters.

The model optimization algorithm consists of the following steps: 1) setting
an initial structure of the deep learning model, 2) optimizing the model
parameters, 3) optimizing the metaparameters, 4) pruning the structure with
GA-NAS. Figure 1 shows the scheme of the proposed algorithm. The model
parameters are optimized by a backpropagation algorithm. The metaparameters
are optimized using a genetic algorithm. We call this method GA-REG (Genetic
Additive REGularization). The research paper has proposed a method for the
simultaneous optimization of the model parameters and metaparameters of
additive regularization.

Figure 1: Functional diagram of the proposed method

#### Related work.

Tikhonov regularization solves the problem of multicollinearity in linear
regression, which commonly occurs in models with large numbers of parameters.
The $L_{2}$-regularization is described in [4]. It works by balancing bias and
variance. Its disadvantage is that it cannot create a sparse model, since it
retains the entire set of parameters. Another type $L_{1}$ of the
regularization was proposed in [5], and it leads to the automatic selection of
parameters. It also has several disadvantages, including:

  1. 1.

If we denote by $p$ the number of independent variables and by $n$ the number
of samples in the dataset, then in the case $p>n$ the Lasso regularization
chooses maximum $n$ of independent variables from the set.

  2. 2.

In the presence of groups of strongly correlated variables, the Lasso
regularization chooses only one variable from the group, not paying attention
to which one.

  3. 3.

In the case of $n>p$ and a high correlation between the variables, it has been
empirically shown that ridge regression performs much better than Lasso.

Thus, items 1) and 2) make Lasso an inapplicable technique in some problems
where feature selection is required. The listed problems are solved using
another technique of elastic net regularization [6]. It allows making
automatic selection of variables, adjusting their weights, as well as choosing
groups of correlating features. The elastic net regularization method is the
addition of two additional terms to the error function

$L\left(\lambda_{1},\lambda_{2},\lambda_{3},\mathbf{w}\right)=\lambda_{1}\|\mathbf{y}-\mathbf{X}\mathbf{w}\|^{2}+\lambda_{2}\|\mathbf{w}\|^{2}+\lambda_{3}\|\mathbf{w}\|_{1}.$

A generalization of Elastic Net is the Support Features Machine (SFM)
regularization [7]. The error function is

$\displaystyle\min_{\mathbf{w}}S(\mathbf{w})=C\sum_{i=1}^{l}\bigl{(}1-M_{i}(\mathbf{W})\bigr{)}_{+}+\sum_{j=1}^{n}\mathcal{R}_{\mu}\left(w_{j}\right),$
(2)
$\displaystyle\mathcal{R}_{\mu}\left(w_{j}\right)=\begin{cases}2\mu\left|w_{j}\right|,&\left|w_{j}\right|\leqslant\mu,\\\
\mu^{2}+w_{j}^{2},&\left|w_{j}\right|\geqslant\mu.\end{cases}$

The features are chosen using the selectivity parameter $\mu$. Noise features
$\left(\left|w_{j}\right|<\mu\right)$ are suppressed as in Lasso, significant
dependent features are grouped as in the elastic net. A method like Relevance
Features Machine (RFM) is similar to it. It is given as follows:

$\min_{\mathbf{w}}C\sum_{i=1}^{l}\bigl{(}1-M_{i}(\mathbf{w})\bigr{)}_{+}+\sum_{j=1}^{n}\ln\left(w_{j}^{2}+\frac{1}{\mu}\right).$
(3)

RFM (3) shows more effective feature selection than SFM (2).

In general, if the function $L$ is convex, then the Moreau-Yosida
regularization can be used. We write $\lambda>0$

$M_{\lambda
L}(\mathbf{x})=\inf_{\mathbf{u}}\left(L(\mathbf{u})+\frac{1}{2\lambda}\|\mathbf{x}-\mathbf{u}\|_{2}^{2}\right).$

This function has remarkable properties: 1) $M_{\lambda f}(\mathbf{x})$ is a
convex function by virtue of infimal convolution; 2) the set of minimum points
for $L$ and $M_{\lambda L}(\mathbf{x})$ coincide; 3) $M_{\lambda
L}(\mathbf{x})$ is a smooth function due to the strong convexity of its first
conjugate function and coincidence with second conjugate function.

The paper [8] presents several strategies for stabilizing the optimization of
the structure of deep networks. This article also provides a description of
the regularization that is sensitive to a smooth change in model parameters
between adjacent layers. In addition, as shown in numerical experiments, the
regularization increases the stability of the model.

For the practical use of additive regularization, it is important that the
model is interpretable in addition to the high accuracy of approximation. In
[9], the EYE regularization (expert yielded estimates) is considered. It
includes expert knowledge of the relationship between traits and the dependent
variable. The problem of minimizing empirical risk is

$\hat{\mathbf{W}}=\min S(\mathbf{W},\mathbf{X},\mathbf{y})+n\lambda
L(\mathbf{W},\boldsymbol{\Gamma}).$

It minimizes the sum of the error function and the regularizer $L$. There are
many $\mathcal{D}$ features, of which for the set where
$\mathcal{K}\subseteq\mathcal{D}$, there is additional information that these
features are important in the considered expert area. Therefore, sparseness is
required for $\hat{\mathbf{W}}_{\mathcal{D}\backslash\mathcal{K}}$, but not
for $\hat{\mathbf{W}}_{\mathcal{K}}$. Our basic approach is to use the $L_{1}$
and $L_{2}$ regularization. Their regularization term is

$L=(1-\beta)\|\boldsymbol{\Gamma}\odot\mathbf{W}\|_{2}^{2}+\beta\|(1-\boldsymbol{\Gamma})\odot\mathbf{W}\|_{1},$

where the parameter $\beta$ controls the balance between the features from
$\mathcal{K}$ and $\mathcal{D}\backslash\mathcal{K}$. The solution proposed in
[8] is

$L=\|(1-\boldsymbol{\Gamma})\odot\mathbf{W}\|_{1}+\sqrt{\|(1-\boldsymbol{\Gamma})\odot\mathbf{W}\|_{1}^{2}+\|\boldsymbol{\Gamma}\odot\mathbf{W}\|_{2}^{2}}.$
(4)

It made possible to obtain models in which the main features used strongly
overlap with factors that were considered significant in the medical
environment in problems of patient risk stratification. Also, it maintains
high prediction quality.

Some other methods of neural network regularization are: data augmentation
[10] reduces the approximation error, batch normalization [1] stabilizes the
model, and dropout [11] prevents overfitting.

Many regularization methods possess a significant disadvantage: metaparameters
are constant throughout the entire learning process. This research paper
proposes an approach that makes it possible to change the influence of
additive regularization on the error function during training, for example, to
enable regularization for individual layers of the neural network.

Efficient choice of a suitable neural network architecture is a hard and time-
consuming task, so automated solutions are highly required. In recent years, a
large number of related algorithms for Neural Architecture Search (NAS) have
emerged. The paper [12] provides detailed analysis of various algorithms for
automating the choice of the structure of a neural network, in particular,
based on reinforcement learning and the genetic principle. A narrower case of
using the choice of structure is considered in [13] and [14] for convolutional
networks. NAS in the problem of face recognition [15] achieves $98.77\%$
accuracy while maintaining a relatively small network size. NAS is applicable
for various machine learning tasks. In [16] it is used for machine
translation. In [17] a method is studied that generalizes regularized genetics
and MNAS achieves $94.46\%$ accuracy and a significant reduction in training
time using the MNIST dataset as an example. The problem of computationally
efficient use of NAS is studied in [18].

##  2 Formulation of the problem of choosing the optimal structure

To solve the model selection problem, we propose to construct a modified error
function. We construct an error function which includes additive
regularization to increase accuracy and reduce structural complexity of a deep
learning model. There given a finite set of pairs

$(\mathbf{x},y)\in\mathfrak{D},\quad\mathbf{x}\in\mathbb{R}^{n},\quad
y\in\mathbb{R},$ (5)

where $\mathbf{x}$ is a vector of independent variables, $y$ is a dependent
variable. One has to construct a structure of a model $f$:

$f(\mathbf{x})=\sigma_{k}\circ\underset{1\times
1}{\mathbf{w}_{k}^{\mathsf{T}}\boldsymbol{\sigma}_{k-1}}\circ\mathbf{W}_{k-1}^{\mathsf{T}}\boldsymbol{\sigma}_{k-2}\circ\dots\circ\underset{n_{2}\times
1}{\mathbf{W}_{2}^{\mathsf{T}}\boldsymbol{\sigma}_{1}}\circ\underset{n_{1}\times
n}{\mathbf{W}_{1}^{\mathsf{T}}}\underset{n\times 1}{\mathbf{x}}.$ (6)

The model structure includes a superposition of a linear model, a deep neural
network, and an autoencoder. The model parameters $\mathbf{w}$ to optimize
according to the error function is the concatenated vector

$\mathbf{w}=[\mathbf{w}_{k},\textbf{vec}(\mathbf{W}_{k-1},\dots,\textbf{vec}(\mathbf{W}_{1})]^{\mathsf{T}}.$

The problem of choice of the optimal model structure $\boldsymbol{\Gamma}$ is
stated using the binary matrices $\boldsymbol{\Gamma}$:

$f(\mathbf{x})=\sigma_{k}\circ\boldsymbol{\Gamma}_{k}\otimes\underset{1\times
1}{\mathbf{w}_{k}^{\mathsf{T}}\boldsymbol{\sigma}_{k-1}}\circ\boldsymbol{\Gamma}_{k-1}\otimes\mathbf{W}^{\mathsf{T}}_{k-1}\boldsymbol{\sigma}_{k-2}\circ\dots\circ\boldsymbol{\Gamma}_{2}\otimes\underset{n_{2}\times
1}{\mathbf{W}_{2}^{\mathsf{T}}\boldsymbol{\sigma}_{1}}\circ\boldsymbol{\Gamma}_{1}\otimes\underset{n_{1}\times
n}{\mathbf{W}_{1}^{\mathsf{T}}}\underset{n\times 1}{\mathbf{x}},$ (7)

where $\boldsymbol{\Gamma}$ is the matrix defining the structure of the model;
$\otimes$ is the Hadamard product, defined as an element-by-element
multiplication. If the element $\gamma\in\\{0,1\\}$ of the matrix
$\boldsymbol{\Gamma}$ is equal to zero, then the corresponding element of the
matrix of the parameters $\mathbf{W}$ is zeroed and does not participate in
the operation of the model. The set of non-zero elements of the matrix
$\Gamma$ forms the model structure. It is required to find model structure
that provides the minimum of the function

$\boldsymbol{\Gamma}^{*}=\arg\min
S\left(f_{\boldsymbol{\Gamma}}\mid\mathbf{w}^{*},\mathfrak{D}_{\mathcal{C}}\right)$

on partitioning of the dataset $\mathfrak{D}$ by the definite set of indices
$\mathcal{C}$. That is, it is required to reduce the number of features and
increase the stability of the model. The optimal model parameters are

$\mathbf{w}^{*}=\arg\min
S\left(\mathbf{w}\mid\mathfrak{D}_{\mathcal{C}},f_{\boldsymbol{\Gamma}}\right).$

The algorithm for finding the optimal network structure assumes minimizing the
error function.

#### Error function.

The key idea of this research paper is to construct a new error function using
metaparameters of additive regularization. We suggest a composite error
function that consists of several summands. The first summand corresponds to
the accuracy of approximation of the dependent variable. The second summand is
the accuracy of reconstruction of the independent variable by autoencoder. The
remaining $k$ of the summands are responsible for additive regularization. A
detailed discussion of the types of regularizers used is presented in
Supplementary.

Table 1: Catalog of additive error function regularizers Role in the additive regularization | Regularizer
---|---
Approximation error | $\|\mathbf{y}-\mathbf{f}(\mathbf{W})\|_{2}^{2}$
Reconstruction error | $\|\mathbf{x}-\mathbf{r}(\mathbf{x})\|_{2}^{2}$
$L_{1},L_{2}$ regularization | $\|\mathbf{w}-\mathbf{w}_{0}\|_{1},\left\|\mathbf{w}-\mathbf{w}_{0}\right\|_{2}^{2}$
Penalty for matrix non-orthogonality | $\left\|\mathbf{W}\mathbf{W}^{\mathsf{T}}-\mathbf{I}\right\|_{2}$
Tikhonov regularization | $\|\mathbf{BW}\|_{2}$
Penalty for the weights frequencies | $\|(\mathbf{I}-\mathbf{A})\mathbf{W}\|_{2}$

The error function includes summands (11) and (13) to optimize the parameters
of the model (6)

$S=\lambda_{x}E_{x}+\lambda_{y}E_{y}+\sum_{i=1}^{k}\lambda_{i}\mathcal{R}_{i}(\mathbf{W}),$
(8)

where
$\mathcal{R}_{i}=\mathcal{R}(\mathbf{W})=\left[\mathfrak{r}_{1}(\mathbf{W}),\cdots,\mathfrak{r}_{r}(\mathbf{W})\right]^{\mathsf{T}}$
is a vector consisting of the values of the regularizers of the $i$-th layer.

The metaparameters of additive regularization are collected in a matrix of
$k\times r$, where $k$ is the number of layers, and $r$ is the number of
regularizers in each layer:

$\left[\begin{array}[]{cccc}\lambda_{1,1}&\lambda_{1,2}&\ldots&\lambda_{1,r}\\\
\ldots&\ldots&\ldots&\ldots\\\
\lambda_{k,1}&\lambda_{k,2}&\ldots&\lambda_{k,r}\end{array}\right].$

In turn, $\boldsymbol{\lambda}_{i}$ is a vector

$\boldsymbol{\lambda}_{i}=\left[\lambda_{1},\lambda_{2},\ldots,\lambda_{r}\right]^{\mathsf{T}}.$
(10)

Each element $\lambda_{r}$ of this vector corresponds to the regularizer
$\mathfrak{r}_{r}$ of the corresponding $k$-th layer. This approach allows you
to vary the structure of the error function. For example, if we nullify errors
$E_{y}$ and additive regularization, leaving only the error $E_{x}$ in
function (8), then the layer will behave as an autoencoder. On the contrary,
with a weak regularization of the parameter $E_{x}$, an approximating layer is
obtained.

When optimizing the structure $\boldsymbol{\Gamma}$ of a deep learning model,
three types of quality criteria are used: accuracy, robustness, and
complexity.

#### Accuracy.

For the regression problem, the error function is

$E_{y}=\sum_{(\mathbf{x},y)\in\mathfrak{D}}\bigl{(}y-f(\mathbf{x})\bigr{)}^{2}.$
(11)

It includes the resulting model predictions $f$ and dependent variable values
$y$. Within regression, the approximation accuracy is

$\operatorname{MAE}=\frac{1}{|\mathfrak{D}|}{\sum_{(\mathbf{x},y)\in\mathfrak{D}}|y-f(\mathbf{x})|}.$
(12)

The principal component analysis model or autoencoder does not use dependent
variables. The error function $E_{\mathbf{x}}$ penalizes the residuals of the
restored input $\mathbf{x}_{i}$ :

$E_{\mathbf{x}}=\sum_{\mathbf{x}\in\mathfrak{D}}\|\mathbf{x}-\mathbf{r}(\mathbf{x})\|_{2}^{2},$
(13)

where $\mathbf{r}(\mathbf{x})$ is a linear reconstruction of the object
$\mathbf{x}$. The autoencoder parameters

$\mathbf{W}_{\mathrm{AE}}=\left\\{\mathbf{W}^{\prime},\mathbf{W},\mathbf{b}^{\prime},\mathbf{b}\right\\}$

are optimized in such a way (13) as to bring the reconstruction
$\mathbf{r}(\mathbf{x})$ closer to the original vector $\mathbf{x}$.

Introduce the _model robustness_ as the minimum variance of the error function
(5):

$\operatorname{var}(S)\rightarrow\min.$

Introduce the _structural complexity_ of the model as the number of optimized
parameters in (7). It also equals to the number of non-zero values in the
matrix $\boldsymbol{\Gamma}$.

#### Problem statement.

The minimization problem is stated as

$\hat{\mathbf{w}},\hat{\boldsymbol{\Gamma}},\hat{\boldsymbol{\lambda}}=\arg\min
S(\mathbf{w},\boldsymbol{\Gamma},\boldsymbol{\lambda}).$ (14)

The model parameters, additive regularization metaparameters, and structure
parameters are optimized to provide a minimum of the error function (8).

Figure 2: Expert task of the optimization schedule

##  3 Optimization schedule

To solve the problem (14), we create an optimization schedule for the
metaparameters of the regularization. We have to set the metaparameters
depending on the iteration number. To set $\boldsymbol{\lambda}$, we proposed
two approaches: 1) Expert schedule selection, and 2) Algorithmic schedule
selection.

Figure 3: Changes in the accuracy, complexity, and robustness of models with
iterations of the GA-REG algorithm

#### Expert schedule selection.

Let the number of layers of the neural network (7) equals $k$, and the number
of training iterations equals $T$.

  1. 1.

Train $s$ first layers as autoencoders, i.e. for $s$ layers $\lambda_{x}=1$
and for the last $k$ slayers $\lambda_{y}=1$. The metaparameters are equal to
zero, i.e. $i$ for $i=1,\dots,s$. Optimize the autoencoder parameters at the
end of the step.

  2. 2.

The number of iterations $T$ is equally split between unoptimized $k-s$ layers
of the neural network. At the first segment of iterations, all regularizers of
$s+1$ layer with metaparameters equals $1$ are added to (8). On the second
segment of iterations, all regularizers with parameters equal $1$ are added to
the layer $s+2$, and so on.

#### Algorithmic schedule selection.

The GA-REG is used as a method for setting up the optimization schedule. It is
proposed to combine the process of optimization of neural network parameters
with iterations of a genetic algorithm to optimize regularization
metaparameters. The regularization metaparameters of each layer (10) are
optimized by GA-REG during $\frac{k}{T}$ iterations. The optimization
procedure for each layer is:

  1. 1.

Initiate a population of alternative metaparameters
$\\{\boldsymbol{\lambda}_{1}\dots\boldsymbol{\lambda}_{p}\\}$.

  2. 2.

For each element of this set update the neural network parameters.

  3. 3.

If using one of the population vectors the error on the validation set
decreases, then this vector is used as regularization metaparameters for the
current layer of the neural network. If not, the current best candidate is
used as the regularization weights.

  4. 4.

Create a new population of regularization vectors using mutation and crossing
procedures.

  5. 5.

Iterate steps 2–4.

For this optimization procedure, at every $\frac{T}{k}$ iterations, obtain the
metaparameters for the current layer of the neural network. The result of the
operation of the algorithm after all iterations of training the network and
tuning the metaparameters is the matrix (9).

Table 2: Description of the datasets for the experiment Dataset $\mathfrak{D}$ | Size train | Size val | Size test | Objects | Features
---|---|---|---|---|---
Protein | 27438 | 9146 | 9146 | 45730 | 9
Airbnb | 6298 | 2100 | 2100 | 10498 | 16
Wine quality | 2938 | 980 | 980 | 4898 | 11
Synthetic | 6000 | 2000 | 2000 | 10000 | 30
online news | 23786 | 7929 | 7929 | 39644 | 58
conductivity | 12757 | 4253 | 4253 | 21263 | 81
concrete | 618 | 206 | 206 | 1030 | 8
electricity | 6000 | 2000 | 2000 | 10000 | 12
NASA | 901 | 301 | 301 | 1503 | 5

##  4 Computational experiment

The procedure for optimizing the structure of a neural network and the effect
of additive regularization on the quality of approximation are investigated.
We have to reduce the model complexity maintaining the accuracy (12). The
structure of the network $\boldsymbol{\Gamma}$ (7) is optimized using the GA-
NAS. The goal of the computational experiment is to determine the optimal
values of the regularization metaparameters, as well as to study the
dependence of the accuracy, complexity, and stability of the model on the
regularization procedure specified by the metaparameters. The algorithm GA-
REG, a procedure to construct a model is described in the previous paragraph.

The metaparameters $\lambda$ are determined for each layer separately. The
metaparameter matrix is

$[\boldsymbol{\lambda}_{1},\boldsymbol{\lambda}_{2},\cdots,\boldsymbol{\lambda}_{k}]^{\mathsf{T}},$

the vector $\boldsymbol{\lambda}_{i}$ collects metaparameters for the $i$-th
layer.

Figure 4: Changing the regularization metaparameters over iterations

#### Datasets.

The quality of the proposed approach to constructing the error function is
evaluated on several datasets from the UCI repository [19] and one synthetic
dataset. The description of all datasets is presented in Table 1. The
synthetic dataset consists of features with different properties of
orthogonality and correlation with each other and with the target variable.
The procedure for generating synthetic data is described in [20]. Each dataset
is split into three parts.

  1. 1.

The training sample set includes $60\%$ of the dataset.

  2. 2.

The validation set includes $20\%$ of the dataset. The vectors of
regularization metaparameters are selected for this dataset. And then a
genetic algorithm is applied that looks for the optimal structure. These
procedures are called GA-REG and GA-NAS, respectively.

  3. 3.

The test sample set includes $20\%$ of the original set. It does not
participate in any way in optimizing the model structure and setting
parameters. This set is used only for comparison of models with and without
the additive regularization, for the original and optimized structures.

#### Algorithm implementation.

The main idea of the work is to develop a method for tuning regularization
metaparameters, that is, the weights of each regularizer. Figure 3 shows the
algorithmic selection method, which is described in Section 3. The legend on
the charts has the following interpretation:

  1. 1)

basic is a model without regularization,

  2. 2)

sequential is an optimization of regularization metaparameters by GA-REG. The
layer regularization uses the current best metaparameter vector from the
genetic population at each train iteration,

  3. 3)

cumulative means that for each layer of the neural network after all
iterations of the GA-REG, the best vector of regularization metaparameters is
determined. This vector is used during training iterations that match the
setting of the current layer. During the iterations corresponding to the
setting of the first layer, the regularization metaparameters of the remaining
layers are equal to zero,

  4. 4)

static means that the entire network is trained using the full regularization
matrix (9).

Figure 5: Left: the error (11) depends on the number of layers of the neural
network given the method of tuning metaparameters. Right: the model error on
the validation set over iterations of training.

Figure 6: The expert schedule; the error (11) depends on the configuration of
the model. Left: a two-dimensional slice, the number of layers of a fully
connected network. Right: Along the axis, the horizontal axes show the number
of layers in the autoencoder and fully connected network, vertical axis shows
the model error.

To reduce the structural complexity of the neural network the GA-NAS was used.
The result of the algorithm work is a binary matrix, each line of which
corresponds to a binary mask. The zeros in the mask mean that the
corresponding neuron in the network can be deleted and does not participate in
the model optimization procedure. Thus, the GA-NAS in this case acts as a
thinning procedure of a neural network, that is, a procedure for reducing the
structural complexity of the model. Figure 3 shows a study of the variation in
accuracy, complexity, and robustness of models. The iterations of the genetic
algorithm start at the top right corner of the cube of complexity-robustness-
error space (CRES) and end at the bottom left. The complexity shows the number
of non-zero model neurons. It is worth noting that all regularized models are
more stable than non-regularized ones, and also start with more accurate
solutions. According to this figure, it can be argued that a neural network
with regularized parameters converges to a less structurally complex and
qualitatively more accurate solution, and also has a higher stability compared
to a model that does not use additive regularization.

Table 3 shows the model error on the test sample set, depending on the
considered dataset. It is seen that in all cases the use of regularization
allows one to reduce the model error. For comparison with other models that
were used on the given data, the work [21] was chosen. In comparison with this
work, we managed to reduce the error by almost four times.

Figure 4 shows the process of adjusting the metaparameters over iterations of
training by GA-REG. Each color denotes a separate regularizer used in the
error function. A detailed description of regularizers is given in Table 1 and
the Supplementary section.

Figure 5 (left) shows the dependence of the neural network error on the test
sample set on the used method for setting the regularization weights and the
number of neural network layers. It is seen that for any configuration of the
neural network, the use of regularization allows one to obtain a smaller
error. Figure 5 (right) shows the error in the validation set during the
training of the neural network. It is seen that the use of regularization
leads to faster convergence and lower error.

Table 3: Model error on the test sample set depending on the considered dataset Dataset $\mathfrak{D}$ | basic | sequential | cumulative | static
---|---|---|---|---
airbnb | 208.59 $\pm$ 7.05 | 147.22 $\pm$ 5.22 | 168.18 $\pm$ 4.55 | 168.18 $\pm$ 4.55
protein | 654.79 $\pm$ 6.37 | 611.14 $\pm$ 5.9 | 643.65 $\pm$ 6.22 | 621.69 $\pm$ 6.23
wine | 174.33 $\pm$ 5.46 | 172.35 $\pm$ 5.43 | 162.66 $\pm$ 5.26 | 162.66 $\pm$ 5.26
synthetic | 2.69 $\pm$ 1.12 | 2.18 $\pm$ 1.04 | 0.39 $\pm$ 0.26 | 0.39 $\pm$ 0.26
conductivity | 113.62 $\pm$ 2.42 | 109.07 $\pm$ 2.43 | 114.04 $\pm$ 2.43 | 109.69 $\pm$ 2.42
online news | 1.54 $\pm$ 0.52 | 1.54 $\pm$ 0.52 | 1.54 $\pm$ 0.52 | 1.54 $\pm$ 0.52
concrete | 244.82 $\pm$ 18.05 | 244.02 $\pm$ 18.06 | 242.12 $\pm$ 17.6 | 243.43 $\pm$ 17.89
electricity | 140.42 $\pm$ 5.1 | 137.71 $\pm$ 4.91 | 140.42 $\pm$ 5.1 | 140.42 $\pm$ 5.1
NASA | 452.75 $\pm$ 23.8 | 450.74 $\pm$ 23.91 | 449.15 $\pm$ 23.99 | 447.71 $\pm$ 24.07

Figure 6 (left) and 6 (right) show the expert method of the regularization
from Section 3. This is an easier method than algorithmic scheduling. The
network configuration consists of a different number of autoencoder layers and
a fully connected network; these numbers are plotted along the horizontal
axes. With equal complexity, using additive regularization allows for less
error than using a non-regularized network. Since the dimension of the number
of layers in the autoencoder part of the network is hidden in 6 (left), the
same graph is shown in 3D 6 (right).

Figure 7: Variation of parameter variance over iterations

Figure 7 shows the dependence of the variance of parameters of the model on
the type of regularization used. The _basic_ type in the network does not use
regularization, the _accumulated_ type layers are sequentially included in the
regularization process, the _ordinal_ type as _accumulated_ type, only when
moving to a new layer, the regularization of the previous one is turned off.
It is seen that the regularized models have a lower variance of parameters.

The code of the computational experiment is available by request.

##  5 Conclusion

The research paper proposes a new method GA-REG for setting the model
regularization schedule. It connects the regularization metaparameters with
iterations of the training and optimizes the weight of each regularizer. It
studiesthe expert and algorithmic setting of the optimization schedule. Based
on the results in Table 3, the regularized models work and are more accurate
than the non-regularized models. With the help of additive regularization, it
was possible to achieve an increase in accuracy by $30\%$ and a decrease in
complexity by more than two times. The GA-NAS algorithm was applied to reduce
the structural complexity of the model. The computational experiment shown
that a neural network with correctly configured regularizers has a more
preferable structure than a network without regularizers. We plan to improve
our optimal structure selection method in several ways. First, we intend to
generate a neural network structure by generative algorithms like autoencoder
or GAN. This approach allows us to select the model structure for the specific
problem. Second, sampling is a stochastic process. We plan to analyze its
properties and create a more efficient generation for our tasks. Finally, we
hope to develop an optimal teacher model selection method that improves the
quality of knowledge distillation.

## References

  * [1] Mathias Kraus, Stefan Feuerriegel, and Asil Oztekin.  Deep learning in business analytics and operations research: Models, applications and managerial implications.  European Journal of Operational Research, 281(3):628 – 641, 2020\.  Featured Cluster: Business Analytics: Defining the field and identifying a research agenda.
  * [2] Christopher M. Bishop and Nasser M. Nasrabadi.  Pattern recognition and machine learning.  J. Electronic Imaging, 16(4):049901, 2007.
  * [3] Konstantin Vorontsov and Anna Potapenko.  Additive regularization of topic models.  Machine Learning, 101(1-3):303–323, 2015.
  * [4] A. N. Tikhonov.  Solution of incorrectly formulated problems and the regularization method.  Soviet Math. Dokl., 4:1035–1038, 1963.
  * [5] Robert J. Tibshirani.  Regression shrinkage and selection via the lasso.  Journal of the Royal Statistical Society, Series B, 58(1):267–288, 1996.
  * [6] Hui Zou and Trevor Hastie.  Regularization and variable selection via the elastic net.  Journal of the royal statistical society: series B (statistical methodology), 67(2):301–320, 2005.
  * [7] Alexander Tatarchuk, Eugene Urlov, Vadim Mottl, and David Windridge.  A support kernel machine for supervised selective combining of diverse pattern-recognition modalities.  In Neamat El Gayar, Josef Kittler, and Fabio Roli, editors, Multiple Classifier Systems, 9th International Workshop, MCS 2010, Cairo, Egypt, April 7-9, 2010. Proceedings, volume 5997 of Lecture Notes in Computer Science, pages 165–174. Springer, 2010.
  * [8] Eldad Haber and Lars Ruthotto.  Stable architectures for deep neural networks.  Inverse Problems, 34(1):014004, dec 2017.
  * [9] Jiaxuan Wang, Jeeheh Oh, Haozhu Wang, and Jenna Wiens.  Learning credible models.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2417–2426, 2018.
  * [10] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In Advances in neural information processing systems, pages 1097–1105, 2012.
  * [11] Nitish Srivastava, Geoffrey E. Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov.  Dropout: a simple way to prevent neural networks from overfitting.  J. Mach. Learn. Res, 15(1):1929–1958, 2014.
  * [12] Martin Wistuba, Ambrish Rawat, and Tejaswini Pedapati.  Automation of deep learning - theory and practice.  page 5–6, 2020.
  * [13] Maria G. Baldeon Calisto and Susana K. Lai-Yuen.  Self-adaptive 2d-3d ensemble of fully convolutional networks for medical image segmentation.  CoRR, abs/1907.11587, 2019.
  * [14] Y. Chen, Z. Wang, Z. J. Wang, and X. Kang.  Automated design of neural network architectures with reinforcement learning for detection of global manipulations.  IEEE Journal of Selected Topics in Signal Processing, pages 1–1, 2020.
  * [15] Ning Zhu, Zekuan Yu, and Caixia Kou.  A new deep neural architecture search pipeline for face recognition.  IEEE Access, 8:91303–91310, 2020.
  * [16] Y. Fan, F. Tian, Y. Xia, T. Qin, X. Li, and T. Liu.  Searching better architectures for neural machine translation.  IEEE/ACM Transactions on Audio, Speech, and Language Processing, 28:1574–1585, 2020.
  * [17] George Kyriakides and Konstantinos Margaritis.  Regularized evolution for macro neural architecture search.  pages 111–122, 2020.
  * [18] Thomas Cassimon, Simon Vanneste, Stig Bosmans, Siegfried Mercelis, and Peter Hellinckx.  Designing resource-constrained neural networks using neural architecture search targeting embedded devices.  Internet of Things, page 100234, 2020.
  * [19] Dheeru Dua and Casey Graff.  UCI machine learning repository, 2017.
  * [20] AM Katrutsa and VV Strijov.  Stress test procedure for feature selection algorithms.  Chemometrics and Intelligent Laboratory Systems, 142:172–183, 2015\.
  * [21] Paulo Cortez, António Cerdeira, Fernando Almeida, Telmo Matos, and José Reis.  Modeling wine preferences by data mining from physicochemical properties.  Decision Support Systems, 47(4):547–553, 2009.
  * [22] A Kolmogorov.  On the representation of continuous functions of several variables by superpositions of continuous functions of a smaller number of variables.  Amer. Math. Soc. Transl., (17):369–373, 1961.
  * [23] G. V. Cybenko.  Approximation by superpositions of a sigmoidal function.  Mathematics of Control Signals and Systems, 4(4):303–314, 1989\.
  * [24] Boris Hanin.  Universal function approximation by deep neural nets with bounded width and relu activations.  Mathematics, 7(10), 2019.

## Supplementary materials

### List of regularizers from the computational experiment

  1. 1.

Lasso, $L_{1}$ regularization:

$\mathfrak{r}_{1}(\mathbf{w})=\|\mathbf{w}\|_{1}.$

  2. 2.

Layers, penalty for the number of layers:

$\mathfrak{r}_{2}(k)=k.$

  3. 3.

Orthogonal, penalty for the matrix non-orthogonality:

$\mathfrak{r}_{3}(\mathbf{W})=\|\mathbf{W}\mathbf{W}^{\mathsf{T}}-\mathbf{I}\|.$

  4. 4.

Variants of Tikhonov regularization:

    1. (a)

Ridge, $L_{2}$ regularization:

$\mathfrak{r}_{4}(\mathbf{w})=\|\mathbf{w}\|_{2}^{2}.$

    2. (b)

High Frequency, penalty for the weight frequency:

$\mathbf{A}=\frac{1}{3}\begin{bmatrix}\frac{2}{3}&\frac{2}{3}&0&0&0&0&0\\\
1&1&1&1&0&0&0\\\ 0&0&1&1&1&0&0\\\ 0&0&0&1&1&1&0\\\ 0&0&0&0&1&1&1\\\
0&0&0&0&0&\frac{2}{3}&\frac{2}{3}\end{bmatrix},$
$\mathfrak{r}_{5}(\mathbf{W})=\|(\mathbf{I}-\mathbf{A})\mathbf{W}\|.$

    3. (c)

Local difference, penalty for the local differences in weights values:

$\mathbf{B}=\begin{bmatrix}-2&2&0&0&0&0&0\\\ -1&0&1&0&0&0&0\\\
0&-1&0&1&0&0&0\\\ 0&0&-1&0&1&0&0\\\ 0&0&0&-1&0&1&0\\\
0&0&0&0&0&-2&2\end{bmatrix},$
$\mathfrak{r}_{6}(\mathbf{W})=\|\mathbf{BW}\|.$

### Theorems on the universal approximation

Theorems 1, 2, 3 from the papers [22, 23, 24] are rewritten in the notations
of the present work. Below are brief version presented.

#### Theorem 1.

Any continuous function $f(\mathbf{x})$, defined in the $d$-dimensional unit
cube could be represented as

$f(\mathbf{x})=\sum_{i=1}^{2d+1}\sigma_{i}\left(\sum_{j=1}^{d}g_{ij}\left(x_{j}\right)\right),\text{
where }\mathbf{x}=\left[x_{1},\ldots,x_{d}\right]^{\mathsf{T}}.$

The functions $\sigma_{i}(\cdot),g_{ij}(\cdot)$ are continuous, and
$g_{ij}(\cdot)$ do not depend on the selection of $f$.

#### Theorem 2.

Let $\varphi$ be an arbitrary sigmoid function, say,

$\varphi(\xi)=\frac{1}{\left(1+e^{-\xi}\right)}.$

For any continuous real-valued function $f$ over $[0,1]^{n}$ (or any other
compact set in $\mathbb{R}^{n}$) and $\varepsilon>0$, there exist vectors
$\mathbf{w}_{1},\mathbf{w}_{2},\ldots,\mathbf{w}_{N},\boldsymbol{\alpha}$ and
$\boldsymbol{\theta}$, and a parametric function

$g(\,\cdot\,,\mathbf{W},\boldsymbol{\alpha},\boldsymbol{\theta}):[0,1]^{n}\rightarrow\mathbb{R}$

such that

$|g(\mathbf{x},\mathbf{W},\alpha,\theta)-f(\mathbf{x})|<|\varepsilon|,\quad\mathbf{x}\in[0,1]^{n},$

where

$g(\mathbf{x},\mathbf{W},\alpha,\theta)=\sum_{i=1}^{N}\alpha_{i}\varphi\left(\mathbf{w}_{i}^{\mathsf{T}}\mathbf{x}+\theta_{i}\right)$

and

$\mathbf{w}_{i}\in\mathbb{R}^{n},\quad\alpha_{i},\theta_{i}\in\mathbb{R},\quad\mathbf{W}=\left(\mathbf{w}_{1},\mathbf{w}_{2},\dots\mathbf{w}_{N}\right),\quad\boldsymbol{\alpha}=\left(\alpha_{1},\alpha_{2},\dots,\alpha_{N}\right)$

and

$\boldsymbol{\theta}=\left(\theta_{1},\theta_{2},\ldots,\theta_{N}\right).$

Before announcing Theorem 3, introduce the following notations. Use a unique
activation function $\operatorname{ReLU}$ for $n\geqslant 1$:

$\sigma=\operatorname{ReLU}\left(x_{1},\ldots,x_{n}\right)=\bigl{(}\max\left\\{0,x_{1}\right\\},\ldots,\max\left\\{0,x_{n}\right\\}\bigr{)}.$
(1)

For $n\geqslant 1$ and continuous function $f:[0,1]^{n}\rightarrow\mathbb{R}$
introduce the norm

$\|f\|_{C_{0}}:=\sup_{\mathbf{x}\in[0,1]^{n}}|f(\mathbf{x})|.$

Use the modulus of continuity

$\omega_{f}(\varepsilon):=\sup\\{|f(\mathbf{x})-f(\mathbf{y})|:|\mathbf{x}-\mathbf{y}|\leqslant\varepsilon\\}.$

Denote by $D_{1}$ a set of any admissible neural networks with input variable
in $\mathbb{R}^{n}$ and hidden layers in $\mathbb{R}^{s}$, that approximate
any continuous function $f$ that is positive-valued and defined on the unit
cube $[0,1]^{n}$. Define the minimal dimensionality of hidden layers of the
neural network with the input size $n$ from $D_{1}$ as

$\omega_{\min}(n):=\min_{s\in D_{1}}\\{s\\}.$

In a similar war, denote by $D_{2}$ a set of any admissible neural networks
with input variable in $\mathbb{R}^{n}$ and hidden layers in $\mathbb{R}^{s}$,
that approximate any continuous function $f$ that is positive-valued and
defined on the unit cube $[0,1]^{n}$. Define the minimal dimensionality of
hidden layers of the neural network with the input size $n$ from $D_{2}$ as

$\omega_{\min}^{\text{conv }}(n):=\min_{s\in D_{2}}\\{s\\}.$

#### Theorem 3.

Let $n\geqslant 1$ and $f:[0,1]^{n}\rightarrow\mathbb{R}_{+}$ is positive-
valued function with norm $\|f\|_{C_{0}}=1$. Then

_Part 1._ If $f$ is continuous, there exists a sequence of forward-propagation
neural networks $\mathcal{N}_{k}$ with activation functions (1), with input
size $n$, hidden size $n+2$, output size 1 (scalar) such that

$\lim_{k\rightarrow\infty}\left\|f-f_{\mathcal{N}_{k}}\right\|_{C^{0}}=0.$ (2)

In particular, $\omega_{\min}(n)\leqslant n+2$. if one fixes $\varepsilon>0$
and compute the modulus of continuality of the function
$f\omega_{f}(\varepsilon)$, the there exists a feed-forward neural network
$\mathcal{N}_{\varepsilon}$ with activation function ReLu (1), input size $n$,
hidden size $-n+3$, and output size $1$ and

$\operatorname{depth}\left(\mathcal{N}_{\varepsilon}\right)=\frac{2\cdot
n!}{\omega_{f}(\varepsilon)^{n}}$

such that

$\left\|f-f_{\mathcal{N}_{\varepsilon}}\right\|_{C_{0}}\leqslant\varepsilon.$

_Part 2._ If $f$ is convex then there exists a sequence of feed-forward neural
networks $\mathcal{N}_{m}$ wit activation functions $\operatorname{Re}LU$ (1),
input size $n$, hidden size $-n+1$, and output size $1$ such that

$\lim_{m\rightarrow\infty}\left\|f-f_{\mathcal{N}_{m}}\right\|_{C_{0}}=0.$ (3)

In particular, it holds $\omega_{\min}^{\mathrm{conv}}(n)\leqslant n+1$. Also,
there exists $C>0$ such that is $f$ convex and continuous with the Lipshitz
constant $L$ then neural networks $\mathcal{N}_{m}$ from (3) could be chosen
so that it holds

$\operatorname{depth}\left(\mathcal{N}_{m}\right)=m,\left\|f-f_{\mathcal{N}_{m}}\right\|_{C_{0}}\leqslant
CLn^{\frac{3}{2}}m^{-\frac{2}{n}}.$

_Part 3._ If $f$ is continous then there exists a constant $K$ that depend on
$n$ only and a constant $B$ that depends on maximum $K$ derivative of $f$ such
that for any $m\geqslant 3$ the neural networks $\mathcal{N}_{m}$ with size
$n+2$ from (2) could be chosen such that

$\operatorname{depth}\left(\mathcal{N}_{m}\right)=m,\left\|f-f_{\mathcal{N}_{m}}\right\|_{C_{0}}\leqslant
B(m-2)^{-\frac{1}{n}}.$


Combinatorial proofs of the Ramanujan type congruences modulo 3

Robert X. J. Hao

Department of Mathematics and Physics,

Nanjing Institute of Technology, Nanjing 211167, P. R. China

<EMAIL_ADDRESS>

Abstract. The partition statistic $V_{R}$-rank is introduced to give
combinatorial proofs of the Ramanujan type congruences mod 3 for certain
classes of partition functions.

Keywords: partition statistic; bijection; combinatorial proof; Ramanujan type
congruence;

AMS Classifications: 05A17, 11P83

##  1 Introduction

A partition $\lambda$ of a positive integer $n$ is a weakly-decreasing
sequence of positive integers
$\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{l}$ such that
$|\lambda|=\sum_{i=1}^{l}\lambda_{i}=n$. Here we adopt the convention that the
partition of 0 is the empty set. Let $p(n)$ denote the number of partitions of
$n$. In 1919, Ramanujan [14] found the following three congruences on $p(n)$

$\displaystyle p(5n+4)$ $\displaystyle\equiv 0\pmod{5},$ (1.1) $\displaystyle
p(7n+5)$ $\displaystyle\equiv 0\pmod{7},$ (1.2) $\displaystyle p(11n+6)$
$\displaystyle\equiv 0\pmod{11}.$ (1.3)

In 1988, Andrews and Garvan [1, 8] defined the partition statistic “crank”,
and provided combinatorial interpretations for congruences (1.1)–(1.3).

Later, Garvan, Kim, and Stanton [9] found different cranks, which also
explained all three congruences. It should be mentioned that they established
explicit bijections between various equinumerous classes, and in particular,
provided a combinatorial proof of (1.1).

By imposing certain restrictions on the parts of the partitions, one can
obtain variants of restricted partitions. For instance, an overpartition is a
partition for which the first occurrence of a part may be overlined and a
partition with designated summands is a partition formed by tagging exactly
one part among parts with equal size. Properties of these partition functions
have been investigated quite intensively in recent studies, see, for example
[2, 10, 4, 7, 18, 19]. Suppose that $t$ is a positive integer and $S$ is a set
of non-negative integers. Let us recall variants of significant restricted
partition sets given as

$\displaystyle\mathcal{P}_{t_{S}}=$ $\displaystyle\\{\lambda|s\in S,\lambda\
\textrm{is a partition into parts $\equiv s\pmod{t}$}\\},$
$\displaystyle\mathcal{D}_{t_{S}}=$ $\displaystyle\\{\lambda|s\in S,\lambda\
\textrm{is a partition into distinct parts $\equiv s\pmod{t}$}\\},$
$\displaystyle\overline{\mathcal{P}}=$ $\displaystyle\\{\lambda|\lambda\
\textrm{is an overpartition}\\},$ $\displaystyle\mathcal{S}=$
$\displaystyle\\{\lambda|\lambda\ \textrm{is a staircase partition}\\},$
$\displaystyle\mathcal{S}_{t-odd}=$ $\displaystyle\\{\lambda|\lambda\
\textrm{is a staircase partition into odd parts, with the part 1 can be
overlined}\\},$ $\displaystyle\mathcal{PD}=$ $\displaystyle\\{\lambda|\lambda\
\textrm{is a partition with designated summands}\\},$
$\displaystyle\mathcal{POD}=$ $\displaystyle\\{\lambda|\lambda\ \textrm{is a
partition with odd parts distinct}\\},$ $\displaystyle\mathcal{A}=$
$\displaystyle\left\\{\lambda|\lambda\ \textrm{is a 2-color partition colors
$r$ and $b$}\right.$ $\displaystyle\left.\textrm{such that the color $b$
appears only in even parts}\right\\}.$

For example, it is easy to see that $\mathcal{P}_{1_{\\{0\\}}}$ denotes the
set of ordinary partitions, and $\mathcal{D}_{2_{\\{1\\}}}$ denotes the set of
partitions into distinct odd parts. Correspondingly, for a given set of
partitions denoted by a script capital letter (or letters), e.g.,
$\mathcal{PD}$, we denote the script capital letters $\mathcal{PD}^{n}$ the
set of partitions $\lambda\in\mathcal{PD}$ with $|\lambda|=n$, and denote the
minuscules $pd(n)$ the number of elements in $\mathcal{PD}^{n}$.

For convenience, one may consider a special kind of restricted partition as
$k$-colored partition, which are $k$ ordered restricted or unrestricted
partitions $\lambda^{(1)},\lambda^{(2)},\dots,\lambda^{(k)}$. It is not hard
to check that $\lambda\in\mathcal{A}$ can be seen as a 2-colored partition
with
$\lambda^{(1)}\in\mathcal{P}_{1_{\\{0\\}}},\lambda^{(2)}\in\mathcal{P}_{2_{\\{0\\}}}$.
A special but important case is that
$\lambda^{(1)},\lambda^{(2)},\dots,\lambda^{(k)}$ subject to the same
restrictions, for example

$\displaystyle{\mathcal{P}_{-k}}=$
$\displaystyle\left\\{\overrightarrow{\lambda}=(\lambda^{(1)},\lambda^{(2)},\dots,\lambda^{(k)})|\lambda^{(i)}\in\mathcal{P}_{1_{\\{0\\}}}\
\textrm{for}\ 1\leq i\leq k\right\\},$
$\displaystyle\overline{\mathcal{P}}_{-k}=$
$\displaystyle\left\\{\overrightarrow{\lambda}=(\lambda^{(1)},\lambda^{(2)},\dots,\lambda^{(k)})|\lambda^{(i)}\in\overline{\mathcal{P}}\
\textrm{for}\ 1\leq i\leq k\right\\},$ $\displaystyle\mathcal{POD}_{-k}=$
$\displaystyle\left\\{\overrightarrow{\lambda}=(\lambda^{(1)},\lambda^{(2)},\dots,\lambda^{(k)})|\lambda^{(i)}\in\mathcal{POD}\
\textrm{for}\ 1\leq i\leq k\right\\}.$

By convention, we call a 2-colored partition bipartition.

In the studies of restricted partitions, some interesting Ramanujan type
congruences were established, see, for example, Andrews et al. [2], Chan [3],
and Chen et al. [5, 6].

$\displaystyle pd(3n+2)$ $\displaystyle\equiv 0\pmod{3},$ (1.4) $\displaystyle
a(3n+2)$ $\displaystyle\equiv 0\pmod{3},$ (1.5) $\displaystyle pod_{-2}(3n+2)$
$\displaystyle\equiv 0\pmod{3},$ (1.6) $\displaystyle\overline{p}_{-2}(3n+2)$
$\displaystyle\equiv 0\pmod{3}.$ (1.7)

Chen, Ji, Jin, Shen [4], Kim [12], and Chen, Lin [5, 6] provided combinatorial
interpretations of the above Ramanujan type congruences by introducing
partition statistics respectively.

In this paper, we aim to give combinatorial proofs for the above congruence
properties by organizing the set of restricted partitions into orbits such
that each orbit consists of 3 distinct members, and each element of the orbit
has a distinct partition statistic $\pmod{3}$. To do so, we consider a special
kind of $k$-colored partition and define the partition statistic $V_{R}$-rank.
We denote a set of restricted partitions by the script capital letter
$\mathcal{R}$, and for a partition $\lambda$, denote $\ell(\lambda)$ the
number of its parts.

######  Definition 1.1.

For $k\geq 3$, let

$\displaystyle V_{t,k}=$
$\displaystyle\left\\{\overrightarrow{\lambda}=(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)},\cdots,\lambda^{(k)})|\lambda^{(1)},\lambda^{(2)},\lambda^{(3)}\in\mathcal{P}_{t_{\\{0\\}}},\
\textrm{for}\ i>3,\right.$ $\displaystyle\left.\lambda^{(i)}\ \textrm{is an
ordinary partition or a restricted partition}\right\\}.$ (1.8)

######  Definition 1.2.

For a given set of restricted partitions $\mathcal{R}$ and
$\lambda\in\mathcal{R}$, if there exist a set $V_{t,k}$ and a bijection
$\Lambda:\mathcal{R}^{n}\rightarrow V_{t,k}^{n}$ such that
$\Lambda(\lambda)=(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)},\cdots,\lambda^{(k)})$,
the $V_{R}$-rank of $\lambda$, denoted by $r_{V}(\lambda)$, is defined as

$\displaystyle r_{V}(\lambda)=\ell(\lambda^{(1)})-\ell(\lambda^{(2)}).$

For convenience, we define the $V_{R}$-rank of $\overrightarrow{\lambda}\in
V_{t,k}$ as

$\displaystyle
r_{V}(\overrightarrow{\lambda})=\ell(\lambda^{(1)})-\ell(\lambda^{(2)}).$

The following theorem holds.

######  Theorem 1.3.

For a given set of restricted partitions $\mathcal{R}$, if there exist a set
$V_{t,k}$ and a bijection $\Lambda:\mathcal{R}^{n}\rightarrow V_{t,k}^{n}$
such that for any $\overrightarrow{\lambda}\in V_{t,k}$,

$\sum_{i=4}^{k}|\lambda^{(i)}|\not\equiv j\pmod{3},$ (1.9)

then the set $\mathcal{R}^{3n+j}$ can be organized into orbits, with each
orbit consists of 3 distinct members and each element of the orbit has a
distinct $V_{R}$-rank $\pmod{3}$, where the $V_{R}$-rank is defined by
Definition 1.2.

We establish bijections to give combinatorial proofs of (1.4)–(1.7) based on
Theorem 1.3.

##  2 Preliminaries

In this section, we prove Theorem 1.3.

_Proof of Theorem 1.3._ Let $\mathcal{R}$ fulfill the conditions of Theorem
1.3. Suppose $\lambda\in\mathcal{R}$ and
$\Lambda(\lambda)=(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)},\cdots,\lambda^{(k)})$.
By (1.9), we have that $\lambda\in\mathcal{R}^{3n+j}$ impiles

$|\lambda^{(1)}|+|\lambda^{(2)}|+|\lambda^{(3)}|\not\equiv 0\pmod{3}.$ (2.1)

If $t\equiv 0\pmod{3}$, the theorem follows immediately by the fact that

$|\lambda^{(1)}|+|\lambda^{(2)}|+|\lambda^{(3)}|\equiv 0\pmod{3}.$

Denote $\ell_{i}(\lambda^{(m)})\ \ (i=\pm 1,m=1,2,3)$ the number of parts
$\equiv i\pmod{3}$ in $\lambda^{(m)}$. If $t\not\equiv 0\pmod{3}$, one can
easily check (2.1) equates with

$\ell_{1}(\lambda^{(1)})+\ell_{1}(\lambda^{(2)})+\ell_{1}(\lambda^{(3)})-[\ell_{-1}(\lambda^{(1)})+\ell_{-1}(\lambda^{(2)})+\ell_{-1}(\lambda^{(3)})]\not\equiv
0\pmod{3}.$

Hence

$\ell_{1}(\lambda^{(1)})+\ell_{1}(\lambda^{(2)})+\ell_{1}(\lambda^{(3)})\not\equiv\ell_{-1}(\lambda^{(1)})+\ell_{-1}(\lambda^{(2)})+\ell_{-1}(\lambda^{(3)})\pmod{3}.$

Thus, for any $\lambda\in\mathcal{R}^{3n+j}$, there are two cases.

  * Case 1.

$\ell_{1}(\lambda^{(1)})+\ell_{1}(\lambda^{(2)})+\ell_{1}(\lambda^{(3)})\not\equiv
0\pmod{3};$

  * Case 2.

$\ell_{1}(\lambda^{(1)})+\ell_{1}(\lambda^{(2)})+\ell_{1}(\lambda^{(3)})\equiv
0\pmod{3},\ell_{-1}(\lambda^{(1)})+\ell_{-1}(\lambda^{(2)})+\ell_{-1}(\lambda^{(3)})\not\equiv
0\pmod{3}.$

We only consider the first case, and the second case can be justified in the
same manner. For the first case, we claim

$\displaystyle\ell_{1}(\lambda^{(1)})-\ell_{1}(\lambda^{(2)})$
$\displaystyle\not\equiv\ell_{1}(\lambda^{(3)})-\ell_{1}(\lambda^{(1)})\pmod{3},$
(2.2) $\displaystyle\ell_{1}(\lambda^{(3)})-\ell_{1}(\lambda^{(1)})$
$\displaystyle\not\equiv\ell_{1}(\lambda^{(2)})-\ell_{1}(\lambda^{(3)})\pmod{3},$
(2.3) $\displaystyle\ell_{1}(\lambda^{(2)})-\ell_{1}(\lambda^{(3)})$
$\displaystyle\not\equiv\ell_{1}(\lambda^{(1)})-\ell_{1}(\lambda^{(2)})\pmod{3}.$
(2.4)

Take (2.2) as an example. By

$\ell_{1}(\lambda^{(1)})+\ell_{1}(\lambda^{(2)})+\ell_{1}(\lambda^{(3)})\not\equiv
0\pmod{3},$

we have

$\ell_{1}(\lambda^{(1)})+\ell_{1}(\lambda^{(2)})+\ell_{1}(\lambda^{(3)})-3\ell_{1}(\lambda^{(1)})\not\equiv
0\pmod{3},$

which implies (2.2) immediately. The proofs of (2.3) and (2.4) are similar to
that of (2.2), and hence they are omitted. Invoking (2.2)-(2.4), we see that
each element of

$\ell_{1}(\lambda^{(1)})-\ell_{1}(\lambda^{(2)}),\ \
\ell_{1}(\lambda^{(3)})-\ell_{1}(\lambda^{(1)}),\ \
\ell_{1}(\lambda^{(2)})-\ell_{1}(\lambda^{(3)}),$

has a distinct residue mod 3. Based on this observation, we conclude that for
a given
$\overrightarrow{\lambda}=(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)},\cdots,\lambda^{(k)})\in
V_{t,k}^{3n+j}$, if we fix all the parts $\not\equiv 1\pmod{3}$ in
$\lambda^{(1)},\lambda^{(2)},\lambda^{(3)}$, and alternate the parts $\equiv
1\pmod{3}$ in them, we can establish
$\overrightarrow{\lambda},\overrightarrow{\lambda}_{\widehat{}},\overrightarrow{\lambda}_{\widehat{\widehat{}}}\in
V_{t,k}^{3n+j}$ such that each of them has a distinct $V_{R}$-rank $\pmod{3}$.

######  Example 2.1.

Let

$\displaystyle V_{1,4}=$
$\displaystyle\left\\{(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)},\lambda^{(4)})|\lambda^{(1)},\lambda^{(2)},\lambda^{(3)}\in\mathcal{P}_{1_{\\{0\\}}},\lambda^{(4)}\in\mathcal{S}\right\\},$
(2.5)

and $\overrightarrow{\lambda}\in V_{1,4}^{83}$ as given by

$\overrightarrow{\lambda}=(9+8+7+7+5+4,5+2+1,10+6+4+4+3+2,3+2+1).$

Since

$\ell_{1}(\lambda^{(1)})+\ell_{1}(\lambda^{(2)})+\ell_{1}(\lambda^{(3)})=7\not\equiv
0\pmod{3},$

alternating the parts $\equiv 1\pmod{3}$ in $\lambda^{(1)}$, $\lambda^{(2)}$,
$\lambda^{(3)}$, we establish the following three partitions belong to
$V_{1,4}^{83}$ as defined in (2.5).

$\displaystyle\overrightarrow{\lambda}=$
$\displaystyle(9+8+7+7+5+4,5+2+1,10+6+4+4+3+2,3+2+1),$
$\displaystyle\overrightarrow{\lambda}_{\widehat{}}=$
$\displaystyle(10+9+8+5+4+4,7+7+5+4+2,6+3+2+1,3+2+1),$
$\displaystyle\overrightarrow{\lambda}_{\widehat{\widehat{}}}=$
$\displaystyle(9+8+5+1,10+5+4+4+2,7+7+6+4+3+2,3+2+1).$

One can see

$\displaystyle r_{V}(\overrightarrow{\lambda})=$ $\displaystyle 6-3=3,$
$\displaystyle r_{V}(\overrightarrow{\lambda}_{\widehat{}})=$ $\displaystyle
6-5=1,$ $\displaystyle
r_{V}(\overrightarrow{\lambda}_{\widehat{\widehat{}}})=$ $\displaystyle
4-5=-1.$

To be more specific, for $i=\pm 1,m=1,2,3$, denote
$\lambda_{3_{\\{i\\}}}^{(m)}$ the partition consisting of all the parts
$\equiv i\pmod{3}$ of $\lambda^{(m)}$, and
$\lambda_{3_{\overline{\\{i\\}}}}^{(m)}$ the partition consisting of all the
parts $\not\equiv i\pmod{3}$ of $\lambda^{(m)}$ respectively. For the first
case, we give a new representation of
$\overrightarrow{\lambda}=(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)},\cdots,\lambda^{(k)})$
as follows

$\overrightarrow{\lambda}=(\overrightarrow{\lambda_{1}},\overrightarrow{\lambda_{\overline{1}}};\lambda^{(4)},\cdots,\lambda^{(k)}),$

where

$\overrightarrow{\lambda_{1}}=(\lambda_{3_{\\{1\\}}}^{(1)},\lambda_{3_{\\{1\\}}}^{(2)},\lambda_{3_{\\{1\\}}}^{(3)}),$

and

$\overrightarrow{\lambda_{\overline{1}}}=(\lambda_{3_{\overline{\\{1\\}}}}^{(1)},\lambda_{3_{\overline{\\{1\\}}}}^{(2)},\lambda_{3_{\overline{\\{1\\}}}}^{(3)}).$

It can be checked that under the following cyclic permutation

$\widehat{C}_{1}(\overrightarrow{\lambda_{1}})=(\lambda_{3_{\\{1\\}}}^{(3)},\lambda_{3_{\\{1\\}}}^{(1)},\lambda_{3_{\\{1\\}}}^{(2)})$

while $r_{V_{3}}(\overrightarrow{\lambda})$ increases or decreases by 1
$\pmod{3}$ under the map

$\widehat{O}_{1}(\overrightarrow{\lambda})=(\widehat{C}(\overrightarrow{\lambda_{1}}),\overrightarrow{\lambda_{\overline{1}}};\lambda^{(4)},\cdots,\lambda^{(k)}).$

For the second case, we can similarly construct $\widehat{O}_{2}$ which fixes
all the parts $\not\equiv-1\pmod{3}$ and alternate the parts
$\equiv-1\pmod{3}$ in $\lambda^{(1)}$, $\lambda^{(2)}$, $\lambda^{(3)}$. Let

$\widehat{O}=\begin{cases}\widehat{O}_{1}&\text{if
$\lambda\in\mathcal{R}^{3n+j}$ fulfills the condition in the first case};\\\
\widehat{O}_{2}&\text{if $\lambda\in\mathcal{R}^{3n+j}$ fulfills the
conditions in the second case}.\end{cases}$ (2.6)

Summing up the above suggests that the set $V_{t,k}^{3n+j}$ can be organized
into orbits, with each orbit consists of 3 distinct members

$\Lambda(\lambda),\widehat{O}(\Lambda(\lambda)),\widehat{O}^{2}(\Lambda(\lambda)),$

and each of their $V_{R}$-rank has distinct residue mod 3. Clearly, the total
number of such orbits is $\frac{v_{t,k}(3n+j)}{3}$, and this summarizes the
combinatorial proof of $v_{t,k}(3n+j)\equiv 0\pmod{3}$. Since $\Lambda$ is a
bijection and by the definition of $V_{R}$-rank, we conclude that the set
$\mathcal{R}^{3n+j}$ can be organized into orbits with each orbit consists of
three distinct members

$\lambda,\Lambda^{-1}\\{\widehat{O}[\Lambda(\lambda)]\\},\Lambda^{-1}\\{\widehat{O}^{2}[\Lambda(\lambda)]\\},$

and each element of the orbit has a distinct $V_{R}$-rank $\pmod{3}$. This
completes the proof.

##  3 Proof of congruence (1.4)

Let us give a quick overview of the notions for the 2-core and 2-quotient of
an ordinary partition which are crucial in our proofs. For a lucid exposition
see Schmidt [15], and a full account of these topics can be found in [11, pp.
75–85].

Firstly, recall that the Ferrers graph of the partition $\lambda$ is a set of
coordinates in the bottom right quadrant of the plane where the $i$-th row
contains $\lambda_{i}$ dots. We denote $\lambda^{\prime}$ the conjugate of
$\lambda$, which is the partition whose graph is obtained by reflecting the
Ferrers graph $\lambda$ about the main diagonal. For example, we give
$\lambda=4+4+2+2+1$ and its conjugate partition $\lambda^{\prime}=5+4+2+2$ in
Figure 1.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$
Figure 1: Ferrers graph of partitions $\lambda=(4,4,2,2,1)$ and
$\lambda^{\prime}=(5,4,2,2)$.

The 2-core of a partition $\lambda$ can be formed as follows. Draw the Ferrers
graph of $\lambda$ and successively remove 2-hooks $\bullet\ \ \bullet$ or
$\begin{matrix}\bullet\\\ \bullet\end{matrix}$, leaving a valid Ferrers graph
at each stage, until no more 2-hooks can be removed. It is easily to check the
Ferrers graph that remains is independent of the order in which the 2-hooks
are removed and the remaining graph is the 2-core of $\lambda$, denoted by
$\lambda_{2c}$ in this paper. Clearly, the 2-core of a partition is always a
staircase partition, i.e., a partition of the form

${n+1\choose 2}=n+(n-1)+\cdots+1.$

The 2-quotient of a partition $\lambda$ is a bipartition
$(\lambda_{q}^{(1)},\lambda_{q}^{(2)})\in\mathcal{P}_{-2}$ which can be
constructed as follows. Alternative write 0s and 1s on the coordinates in the
Ferrers graph for $\lambda$, starting with a 0 in the top, left-most
coordinate. Draw a horizontal line through any row that ends in 0 and a
vertical line through any column that ends in 1. The Ferrers graph of
$\lambda_{q}^{(1)}$ consists of the coordinates that are contained in both a
vertical and a horizontal line; these coordinates are then pushed toward the
northwest, in order to be justified with respect to the left and top, to form
the Ferrers graph of $\lambda_{q}^{(1)}$. For $\lambda_{q}^{(2)}$, we carry
out the same procedure with the roles of rows and columns reversed. An
essential result given in [13, 3, p. 83, Theorem 2.7.30] points out that the
triple

$(\lambda_{2c},\lambda_{q}^{(1)},\lambda_{q}^{(2)}),\lambda_{2c}\in\mathcal{S},\lambda_{q}^{(1)},\lambda_{q}^{(2)}\in\mathcal{P}_{1_{\\{0\\}}}$

uniquely determines $\lambda$, with

$|\lambda|=|\lambda_{2c}|+2|\lambda_{q}^{(1)}|+2|\lambda_{q}^{(2)}|.$

For simplicity, in this paper we denote the bijection

$\Phi:\mathcal{P}_{1_{\\{0\\}}}^{n}\rightarrow(\lambda_{2c},\lambda^{(1)},\lambda^{(2)}),$
(3.1)

where
$\lambda_{2c}\in\mathcal{S},\lambda^{(1)},\lambda^{(2)}\in\mathcal{P}_{2_{\\{0\\}}},|\lambda_{2c}|+|\lambda^{(1)}|+|\lambda^{(2)}|=n$.
Take $\lambda=4+4+2+2+1$ as an example. It is easily verified that

$\Phi(\lambda)=(\lambda_{2c},\lambda^{(1)},\lambda^{(2)})=(1,2,6+4).$

To establish combinatorial proofs of congruence (1.4), we need to give a new
representation of a partition with designated summands by a quintuple of
partitions.

######  Lemma 3.1.

There is a bijection $\Lambda_{pd}:\mathcal{PD}^{n}\rightarrow V_{2,5}^{n}$,
where

$\displaystyle V_{2,5}=$
$\displaystyle\left\\{(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)},\lambda^{(4)},\lambda^{(5)})|\lambda^{(1)},\lambda^{(2)},\lambda^{(3)}\in\mathcal{P}_{2_{\\{0\\}}},\lambda^{(4)}\in\mathcal{S},\lambda^{(5)}\in\mathcal{D}_{3_{\\{0\\}}}\right\\}.$

###### Proof.

Let $\lambda\in\mathcal{PD}^{n}$. Suppose that $d$ is a magnitude which
appears in $\lambda$ and there are $m_{d}$ parts equal to $d$ among which the
$i_{d}$-th (from left to right) part is designated. There are two cases.

  * (1)

If $i_{d}=1$, then move all the parts equal to $d$ (including the designated
part) in $\lambda$ to the partition $\alpha$;

  * (2)

If $i_{d}\neq 1$, then move $i_{d}$ parts equal to $d$ in $\lambda$ to $\beta$
and $(m_{d}-i_{d})$ parts equal to $d$ in $\lambda$ to $\alpha$.

Clearly, $\alpha$ is an ordinary partition and $\beta$ is a partition with
each part occurs at least twice. Write $\beta$ as in the form of
$(1^{m_{1}}2^{m_{2}}\ldots)$ where $m_{d}$ is the multiplicity of $d$. Since
$m_{d}\neq 1$ for any $d$, there are two cases.

  * (1)

If $m_{d}$ is even, add $\frac{m_{d}}{2}$ parts $2d$ in $\lambda^{(3)}$;

  * (2)

If $m_{d}$ is odd, add one part $3d$ in $\lambda^{(5)}$ and
$\frac{m_{d}-3}{2}$ parts $2d$ in $\lambda^{(3)}$.

One can see that
$\lambda^{(3)}\in\mathcal{P}_{2_{\\{0\\}}},\lambda^{(5)}\in\mathcal{D}_{3_{\\{0\\}}}$
and $|\beta|=|\lambda^{(3)}|+|\lambda^{(5)}|$. Denote this bijection by
$\Psi$. Recollect the bijection $\Phi$ from an ordinary partition to triples
$(\lambda_{2c},\lambda^{(1)},\lambda^{(2)})$, and let
$\Phi(\alpha)=(\lambda^{(4)},\lambda^{(1)},\lambda^{(2)})$. Now we can combine
bijections $\Delta$, $\Psi$ and $\Phi$ into a single bijection $\Lambda_{pd}$
given as

$\Lambda_{pd}(\lambda)=(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)},\lambda^{(4)},\lambda^{(5)}).$

For instance, let

$\lambda=20+20+20^{\prime}+4+4^{\prime}+4+4+2^{\prime}+2+1+1+1+1+1+1+1^{\prime}+1,$

be a partition of 88 with designated summands. Naturally,

$\Delta(\lambda)=(\alpha,\beta)=(4+4+2+2+1,20+20+20+4+4+1+1+1+1+1+1+1).$

Then we have

$\Phi(\alpha)=(\lambda^{(4)},\lambda^{(1)},\lambda^{(2)})=(1,2,6+4),$

and

$\Psi(\beta)=(\lambda^{(3)},\lambda^{(5)})=(8+2+2,60+3).$

Eventually, we obtain

$\Lambda_{pd}(\lambda)=(2,6+4,8+2+2,1,60+3).$

One can check $\Lambda_{pd}$ is a bijection, and the generating functions of
$\lambda^{(4)},\lambda^{(5)}$ can be given as

$\sum_{n=0}^{\infty}q^{n+1\choose 2},(-q^{3};q^{3})_{\infty},$

respectively.

_Proof of congruence ( 1.4)._ Combining

${n+1\choose 2}\equiv 0\ \ \textrm{or}\ \ 1\pmod{3},$

and the fact $|\lambda^{(5)}|\equiv 0\pmod{3}$, we can deduce

$\sum_{i=4}^{5}|\lambda^{(i)}|\not\equiv 2\pmod{3}.$

Applying Theorem 1.3 leads to a combinatorial proof of congruence (1.4).

For example, in Table 3.1 we list out the 15 partitions of $5$ with designated
summands. Apparently, there are $5$ orbits and each orbit contains 3 elements.

Table 3.1: The case for $n=5$. $\lambda$ | $(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)},\lambda^{(4)},\lambda^{(5)})$ | $r_{V}(\lambda)$ | $orbit$
---|---|---|---
$5^{\prime}$ | $\left(4,\emptyset,\emptyset,1,\emptyset\right)$ | $1$ | $O_{1}$
$4^{\prime}+1^{\prime}$ | $\left(\emptyset,2,\emptyset,2+1,\emptyset\right)$ | $-1$ | $O_{2}$
$3^{\prime}+2^{\prime}$ | $\left(2+2,\emptyset,\emptyset,1,\emptyset\right)$ | $2$ | $O_{3}$
$3^{\prime}+1^{\prime}+1$ | $(2,2,\emptyset,1,\emptyset)$ | $0$ | $O_{4}$
$3^{\prime}+1+1^{\prime}$ | $(2,\emptyset,2,1,\emptyset)$ | $1$ | $O_{4}$
$2^{\prime}+2+1^{\prime}$ | $(\emptyset,4,\emptyset,1,\emptyset)$ | $-1$ | $O_{1}$
$2+2^{\prime}+1^{\prime}$ | $(\emptyset,\emptyset,4,1,\emptyset)$ | $0$ | $O_{1}$
$2^{\prime}+1^{\prime}+1+1$ | $(2,\emptyset,\emptyset,2+1,\emptyset)$ | $1$ | $O_{2}$
$2^{\prime}+1+1^{\prime}+1$ | $(\emptyset,\emptyset,2,2+1,\emptyset)$ | $0$ | $O_{2}$
$2^{\prime}+1+1+1^{\prime}$ | $(\emptyset,2,\emptyset,\emptyset,3)$ | $-1$ | $O_{5}$
$1^{\prime}+1+1+1+1$ | $(\emptyset,2+2,\emptyset,1,\emptyset)$ | $-2$ | $O_{3}$
$1+1^{\prime}+1+1+1$ | $(\emptyset,2,2,1,\emptyset)$ | $-1$ | $O_{4}$
$1+1+1^{\prime}+1+1$ | $(2,\emptyset,\emptyset,\emptyset,3)$ | $1$ | $O_{5}$
$1+1+1+1^{\prime}+1$ | $(\emptyset,\emptyset,2+2,1,\emptyset)$ | $0$ | $O_{3}$
$1+1+1+1+1^{\prime}$ | $(\emptyset,\emptyset,2,\emptyset,3)$ | $0$ | $O_{5}$

##  4 Proof of congruence (1.5)

In [12], Kim interpreted $a(n)$ as the number of 2-color restricted partitions
of $n$ with colors $r$ and $b$ such that the color $b$ appears only in even
parts. For instance, there are 3 such partitions of 2:

$2^{r},2^{b},1^{r}+1^{r}.$

Invoking Theorem 1.3, the combinatorial proof of congruence (1.5) follows
immediately according to the lemma given below.

######  Lemma 4.1.

There is a bijection $\Lambda_{a}:\mathcal{A}^{n}\rightarrow V_{2,4}^{n}$,
where

$\displaystyle V_{2,4}=$
$\displaystyle\left\\{(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)},\lambda^{(4)})|\lambda^{(1)},\lambda^{(2)},\lambda^{(3)}\in\mathcal{P}_{2_{\\{0\\}}},\lambda^{(4)}\in\mathcal{S}\right\\}.$

###### Proof.

Let $\lambda\in\mathcal{A}^{n}$. Clearly, we can split $\lambda$ into the
bipartition $(\alpha,\lambda^{(3)})$ in accordance with the color of the
parts, namely, where $\alpha$ is consisted of the parts colored $r$ and
$\lambda^{(3)}$ is composed of the parts colored $b$. It is obvious that
$\alpha\in\mathcal{P}_{1_{\\{0\\}}}$ and
$\lambda^{(3)}\in\mathcal{P}_{2_{\\{0\\}}}$. Recollect the bijection $\Phi$
from ordinary partition to triples
$\left(\lambda_{2c},\lambda_{0},\lambda_{1}\right)$, and let
$\Phi(\alpha)=(\lambda^{(4)},\lambda^{(1)},\lambda^{(2)})$. Summing up the
above, we reach Lemma 4.1, as claimed.

The proof of congruence (1.5) is similar to that of congruence (1.4), and
hence it is omitted. We just give an example in Table 4.2.

Table 4.2: The case for $n=5$. $\lambda$ | $\left(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)},\lambda^{(4)}\right)$ | $r_{V}(\lambda)$ | $orbit$
---|---|---|---
$5^{r}$ | $\left(4,\emptyset,\emptyset,1\right)$ | $1$ | $O_{1}$
$4^{r}+1^{r}$ | $\left(\emptyset,2,\emptyset,2+1\right)$ | $-1$ | $O_{2}$
$4^{b}+1^{r}$ | $\left(\emptyset,\emptyset,4,1\right)$ | $0$ | $O_{1}$
$3^{r}+2^{r}$ | $(2+2,\emptyset,\emptyset,1)$ | $2$ | $O_{3}$
$3^{r}+2^{b}$ | $(2,\emptyset,2,1)$ | $1$ | $O_{4}$
$3^{r}+1^{r}+1^{r}$ | $(2,2,\emptyset,1)$ | $0$ | $O_{4}$
$2^{r}+2^{r}+1^{r}$ | $(\emptyset,4,\emptyset,1)$ | $-1$ | $O_{1}$
$2^{b}+2^{r}+1^{r}$ | $(\emptyset,\emptyset,2,2+1)$ | $0$ | $O_{2}$
$2^{b}+2^{b}+1^{r}$ | $(\emptyset,\emptyset,2+2,1)$ | $0$ | $O_{3}$
$2^{r}+1^{r}+1^{r}+1^{r}$ | $(2,\emptyset,\emptyset,2+1)$ | $1$ | $O_{2}$
$2^{b}+1^{r}+1^{r}+1^{r}$ | $(\emptyset,2,2,1)$ | $-1$ | $O_{4}$
$1^{r}+1^{r}+1^{r}+1^{r}+1^{r}$ | $(\emptyset,2+2,\emptyset,1)$ | $-2$ | $O_{3}$

##  5 Proofs of congruences (1.6) and (1.7)

We first prove congruence (1.6).

######  Lemma 5.1.

There is a bijection $\Lambda_{pod}:\mathcal{POD}_{-2}^{n}\rightarrow
V_{2,4}^{n}$, where

$\displaystyle V_{2,4}=$
$\displaystyle\left\\{(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)},\lambda^{(4)})|\lambda^{(1)},\lambda^{(2)},\lambda^{(3)}\in\mathcal{P}_{2_{\\{0\\}}},\lambda^{(4)}\in\mathcal{S}_{t-odd}\right\\}.$

###### Proof.

To avoid conflicts on the symbols, in the proof of Lemma 5.1, we write a
partition as $\lambda=(\lambda_{1},\ldots,\lambda_{l})$. For a given
bipartition
$(\lambda_{pod}^{(1)},\lambda_{pod}^{(2)})\in\mathcal{POD}_{-2}^{n}$, take out
all the even parts in $\lambda_{pod}^{(1)}$ to form $\lambda^{(1)}$, and all
the even parts in $\lambda_{pod}^{(2)}$ to form $\lambda^{(2)}$. Clearly, the
remaining parts in $(\lambda_{pod}^{(1)},\lambda_{pod}^{(2)})$ form a
bipartition $(\mu^{(1)},\mu^{(2)})$ with
$\mu^{(1)},\mu^{(2)}\in\mathcal{D}_{2_{\\{1\\}}}$. Hence it suffices to show
that there is a bijection between bipartitions $(\mu^{(1)},\mu^{(2)})$ of $n$
and bipartitions $(\lambda^{(3)},\lambda^{(4)})$ of $n$ where
$\lambda^{(3)}\in\mathcal{P}_{2_{\\{0\\}}}$ and
$\lambda^{(4)}\in\mathcal{S}_{t-odd}$. A graceful modified version of the
Wright map $\varphi$ constructed by Seo and Yee [16] is significant for our
proof in this part, and we denote this modified version by $\varphi_{m}$ (see
[20, 22] for details of the Wright map). Recall that a Frobenius symbol of $n$
is a two-rowed array[21]

$F=\left(\begin{array}[]{ccccc}a_{1}&a_{2}&\cdots&a_{l}\\\
b_{1}&b_{2}&\cdots&b_{l}\end{array}\right),$

where $a_{1}>a_{2}>\ldots>a_{l}\geq 0$, $b_{1}>b_{2}>\ldots>b_{l}\geq 0$ and
$n=\sum_{i=1}^{l}(a_{i}+b_{i})+l$. Given the Ferrers graph of an ordinary
partition, $a_{i}$ form rows to the right of the diagonal, and $b_{i}$ form
columns below the diagonal. As a result, there is a natural bijection between
the Frobenius symbols of $n$ and the ordinary partitions of $n$. We are now
ready to apply the bijection $\varphi_{m}$ for $(\mu^{(1)},\mu^{(2)})$, namely

$\displaystyle\mu^{(1)}$
$\displaystyle=(2a_{1}+1,2a_{2}+1,\ldots,2a_{l+m}+1),$
$\displaystyle\mu^{(2)}$ $\displaystyle=(2b_{1}+1,2b_{2}+1,\ldots,2b_{l}+1),$

where $a_{1}>a_{2}>\cdots>a_{l+m}\geq 0$ and $b_{1}>b_{2}>\cdots>b_{l}\geq 0$.
Suppose that $\mu$ and $\nu$ are two partitions. For convenience, let
$\mu\cup\nu$ be the partition consisting of all the parts of $\mu$ and $\nu$,
and denote $2\mu$ as the partition whose parts are $2$ times each part of
$\mu$. For instance, let $\mu=(9,6,6,2,1)$. Accordingly,
$2\mu=(18,12,12,4,2)$. For $m\geq 0$, we construct a Forbenius symbol

$\displaystyle\mu=\left(\begin{array}[]{llll}a_{1+m}&a_{2+m}&\cdots&a_{l+m}\\\\[5.0pt]
b_{1}&b_{2}&\cdots&b_{l}\end{array}\right)$

and a partition $\nu=(a_{1}-m+1,a_{2}-m+2,\ldots,a_{m})$. We define
$\varphi_{m}(\mu^{(1)},\mu^{(2)})=(\pi,\triangle)$, where $\pi=2(\mu\cup\nu)$
and $\triangle=(2(m-1)+1,2(m-2)+1,\ldots,3,1)$. When $m=0$, we see that
$\triangle=\emptyset$. For $m<0$, a Forbenius symbol

$\displaystyle\mu=\left(\begin{array}[]{llll}b_{1-m}&b_{2-m}&\cdots&b_{l}\\\\[5.0pt]
a_{1}&a_{2}&\cdots&a_{l+m}\end{array}\right)$

and a partition $\nu=(b_{1}+m+1,b_{2}+m+2,\ldots,b_{-m})$ are built. We define
$\varphi_{m}(\mu^{1},\mu^{2})=(\pi,\triangle)$, where
$\pi=2(\mu\cup\nu)^{\prime}$ and
$\triangle=(2(-m-1)+1,2(-m-2)+1,\ldots,3,\overline{1})$. For instance, give
$(\mu^{(1)},\mu^{(2)})$ as

$\displaystyle\mu^{(1)}$ $\displaystyle=(9,7,3)=(2\times 4+1,2\times
3+1,2\times 1+1),$ $\displaystyle\mu^{(2)}$
$\displaystyle=(17,15,11,7,3,1)=(2\times 8+1,2\times 7+1,2\times 5+1,2\times
3+1,2\times 1+1,2\times 0+1).$

In light of the modified Wright’s map $\varphi_{m}$, we get

$\displaystyle\mu=\left(\begin{array}[]{lll}b_{4}&b_{5}&b_{6}\\\\[5.0pt]
a_{1}&a_{2}&a_{3}\end{array}\right)=\begin{pmatrix}3&1&0\\\
4&3&1\end{pmatrix}=(4,3,3,3,2),$
$\displaystyle\nu=(8-3+1,7-3+2,5-3+3)=(6,6,5).$

Hence we obtain

$\displaystyle\varphi_{m}(\mu^{(1)},\mu^{(2)})=(\pi,\triangle)=(2(\mu\cup\nu)^{\prime},((3-1)\times
2+1,(2-1)\times 2+1,\overline{1}))$ $\displaystyle=$
$\displaystyle(2(6,6,5,4,3,3,3,2)^{\prime},(5,3,\overline{1}))=((16,16,14,8,6,4),(5,3,\overline{1})).$

It can be checked that
$|\mu^{1}|+|\mu^{2}|=|\pi|+|\triangle|,\pi\in\mathcal{P}_{2_{\\{0\\}}},\triangle\in\mathcal{S}_{t-odd}$
and the generating function of $\triangle$ can be given as

$q^{0}+2\sum_{n=1}^{\infty}q^{n^{2}}=\sum_{n=-\infty}^{\infty}q^{n^{2}}.$

By now we complete the proof of Lemma 5.1.

_Proof of congruence ( 1.6)._ Since $n^{2}\not\equiv 2\pmod{3}$, invoking
Theorem 1.3, we give a combinatorial proof of congruence (1.6). Here we give
an example in Table 5.3.

Table 5.3: The case for $n=5$. $\lambda$ | $\left(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)},\lambda^{(4)}\right)$ | $r_{V}(\lambda)$ | $orbit$
---|---|---|---
$(5,\emptyset)$ | $\left(\emptyset,\emptyset,4,1\right)$ | $0$ | $O_{1}$
$(\emptyset,5)$ | $\left(\emptyset,\emptyset,2+2,\overline{1}\right)$ | $0$ | $O_{2}$
$(4+1,\emptyset)$ | $\left(4,\emptyset,\emptyset,1\right)$ | $1$ | $O_{1}$
$(\emptyset,4+1)$ | $\left(\emptyset,4,\emptyset,\overline{1}\right)$ | $-1$ | $O_{3}$
$(4,1)$ | $\left(4,\emptyset,\emptyset,\overline{1}\right)$ | $1$ | $O_{3}$
$(1,4)$ | $\left(\emptyset,4,\emptyset,1\right)$ | $-1$ | $O_{1}$
$(3+2,\emptyset)$ | $\left(2,\emptyset,2,1\right)$ | $1$ | $O_{4}$
$(\emptyset,3+2)$ | $\left(\emptyset,2,2,\overline{1}\right)$ | $-1$ | $O_{5}$
$(3,2)$ | $\left(\emptyset,2,2,1\right)$ | $-1$ | $O_{4}$
$(2,3)$ | $\left(2,\emptyset,2,\overline{1}\right)$ | $1$ | $O_{5}$
$(3+1,1)$ | $\left(\emptyset,\emptyset,2+2,1\right)$ | $0$ | $O_{6}$
$(1,3+1)$ | $\left(\emptyset,\emptyset,4,\overline{1}\right)$ | $0$ | $O_{3}$
$(2+2+1,\emptyset)$ | $\left(2+2,\emptyset,\emptyset,1\right)$ | $2$ | $O_{6}$
$(\emptyset,2+2+1)$ | $\left(\emptyset,2+2,\emptyset,\overline{1}\right)$ | $-2$ | $O_{2}$
$(2+2,1)$ | $\left(2+2,\emptyset,\emptyset,\overline{1}\right)$ | $2$ | $O_{2}$
$(1,2+2)$ | $\left(\emptyset,2+2,\emptyset,1\right)$ | $-2$ | $O_{6}$
$(2+1,2)$ | $\left(2,2,\emptyset,1\right)$ | $0$ | $O_{4}$
$(2,2+1)$ | $\left(2,2,\emptyset,\overline{1}\right)$ | $0$ | $O_{5}$

Congruence (1.7) can be justified in the same manner according to the Wright
bijection, and hence it is omited.

######  Remarks 5.2.

Let $O$ be an injective map on $V_{t,k}$ defined as

$\displaystyle
O((\lambda^{(1)},\lambda^{(2)},\lambda^{(3)},\lambda^{(4)}\cdots,\lambda^{(k)}))=(\lambda^{(3)},\lambda^{(1)},\lambda^{(2)},\lambda^{(4)}\cdots,\lambda^{(k)}).$

It is obvious that the fixed-point set of the injective map $O$ is the subset
of $V_{t,k}$ subject to the restriction that
$\lambda^{(1)}=\lambda^{(2)}=\lambda^{(3)}$. In light of this observation, if
$\mathcal{R}$ fulfills the conditions of Theorem 1.3, we can give another
method to organize the set $\mathcal{R}^{3n+j}$ into orbits under the
injective map $O$, such that each orbit consists of 3 distinct members.

######  Remarks 5.3.

Denote

$\displaystyle\mathcal{R}_{g}=$ $\displaystyle\\{\lambda|\lambda\ \textrm{is a
partition subjects to given restrictions}\\}.$

Let

$\displaystyle V_{R_{g},k}=$
$\displaystyle\left\\{(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)},\cdots,\lambda^{(k)})|\lambda^{(1)},\lambda^{(2)},\lambda^{(3)}\in\mathcal{R}_{g},\
\textrm{for}\ i>3,\right.$ $\displaystyle\left.\lambda^{(i)}\ \textrm{is an
ordinary partition or a restricted partition}\right\\}$ (5.2)

subjecting to the restriction that $\widehat{O}$ is an injective map on
$V_{R_{g},k}$, where $\widehat{O}$ is defined by (2.6). Clearly, if we replace
$V_{t,k}^{n}$ by $V_{R_{g},k}^{n}$ in Theorems 1.3, the theorem still holds.
Based on this observation one can easily give combinatorial proofs of the
congruences mod 3 given by Toh [17], and we omit the details.

Acknowledgments.

The author was supported by the Scientific Research Foundation of Nanjing
Institute of Technology.

## References

  * [1] Andrews, G. E., Garvan, F. G.: Dyson’s crank of a partition, Bull. Amer. Math. Soc. 18, 167–171 (1988)
  * [2] Andrews, G. E., Lewis, R. P., Lovejoy, J.: Partitions with designated summands, Acta Arith. 105, 51–66 (2002)
  * [3] Chan, H.-C.: Ramanujan’s cubic continued fraction and an analog of his “most beautiful identity”, Int. J. Number Theory 06, 673–680 (2010)
  * [4] Chen, W. Y. C., Ji, K. Q., Jin, H-T., Shen, E. Y. Y.: On the number of partitions with designated summands, J. Number Theory 133, 2929–2938 (2013)
  * [5] Chen, W. Y. C., Lin, B. L. S.: Congruences for bipartitions with odd parts distinct, Ramanujan J. 25, 277–293 (2011)
  * [6] Chen, W. Y. C., Lin, B. L. S.: Arithmetic properties of overpartition pairs, Acta Arithmetica (2012)
  * [7] Fu, S. S., Tang D. Z.: Multiranks and classical Theta functions, Int. J. Number Theory 14, 549–566 (2017).
  * [8] Garvan, F. G.: New combinatorial interpretations of Ramanujan’s partition congruences mod $5$, $7$, $11$, Trans. Amer. Math. Soc. 305, 47–77 (1988)
  * [9] Garvan, F. G., Kim, D., Stanton, D.: Cranks and $t$-cores, Invent. Math. 101, 1–17 (1990)
  * [10] Hirschhorn, M. D., Sellers, J. A.: Arithmetic relations for overpartitions, J. Comb. Math. Comb. Comp. 53, 65–73 (2005)
  * [11] James, G., Kerber, A.: The Representation Theory of the Symmetric Group, Reading, MA: Addison-Wesley, 1981.
  * [12] Kim, B.: An analog of crank for a certain kind of partition function arising from the cubic continued fraction, Acta Arithmetica 148, 1–19 (2010)
  * [13] Nakayama, T.: On some modular properties of irreducible representations of a symmetric group, I, II, Japan. J. Math. 17, 165–184, 411–423 (1940)
  * [14] Ramanujan, S.: Some properties of $p(n)$, the number of partitons of $n$, Proc. Cambridge Philos. Soc. 19, 214–216 (1919)
  * [15] Schmidt, F.: Integer partitions and binary trees, Advances in Applied Mathematics, (2002).
  * [16] Seo, S., Yee, A. J.:, Overpartitions and singular overpartitions, analytic number theory, modular forms and $q$-Hypergeometric series: In Honor of Krishna Alladi’s 60th Birthday, University of Florida, Gainesville, 693–711 (2016)
  * [17] Toh, P. C.: Ramanujan type identities and congruences for partition pairs, Discrete Math. 312, 1244–1250 (2012)
  * [18] Wang, L. Q.: Congruences modulo powers of 11 for some partition functions, Proceedings of the American Mathematical Society 146, 1515–1528 (2017)
  * [19] Wang, C., Yee, A. J.: Truncated Hecke-Rogers type series, Adv. Math. 365, 51–70 (2020)
  * [20] Wright, E. M.: An enumerative proof of an identity of Jacobi, J. London Math. Soc. 40, 55–57 (1965)
  * [21] Yee, A. J.: Combinatorial proofs of generating function identities for F-partitions, J. Combin. Ser. A 102, 217–228 (2003)
  * [22] Yee, A. J.: Truncated Jacobi triple product theorem, J. Combin. Ser. A 130, 1–14 (2015)