# A Realistic Evaluation of Semi-Supervised Learning
for Fine-Grained Classification

Jong-Chyi Su Zezhou Cheng Subhransu Maji
University of Massachusetts Amherst
{jcsu, zezhoucheng<EMAIL_ADDRESS>
###### Abstract

We evaluate the effectiveness of semi-supervised learning (SSL) on a realistic
benchmark where data exhibits considerable class imbalance and contains images
from novel classes. Our benchmark consists of two fine-grained classification
datasets obtained by sampling classes from the Aves and Fungi taxonomy. We
find that recently proposed SSL methods provide significant benefits, and can
effectively use out-of-class data to improve performance when deep networks
are trained from scratch. Yet their performance pales in comparison to a
transfer learning baseline, an alternative approach for learning from a few
examples. Furthermore, in the transfer setting, while existing SSL methods
provide improvements, the presence of out-of-class is often detrimental. In
this setting, standard fine-tuning followed by distillation-based self-
training is the most robust. Our work suggests that semi-supervised learning
with experts on realistic datasets may require different strategies than those
currently prevalent in the literature.

##  1 Introduction

Figure 1: Accuracy of semi-supervised learning (SSL) algorithms on the Semi-
Aves and Semi-Fungi datasets (see Fig. 2) using (i) different pre-trained
models, and (ii) in-class ($U_{in}$) and out-of-class ($U_{in}+U_{out}$)
unlabeled data. The performances of the supervised baseline and supervised
oracle are also shown. Transfer learning from experts is far more effective
than SSL from _scratch_ , while in the transfer setting SSL provides modest
gains. Though out-of-class data ($U_{out})$ is valuable when training from
scratch, it is not the case when training from experts (details in Tab. 2 and
3). Figure 2: The proposed benchmark for semi-supervised learning. The
benchmark contains two datasets, with classes from the Aves and Fungi taxa
respectively. Each represents a 200-way classification task and the training
set contains (i) labeled images from these classes $L_{in}$, (ii) unlabeled
images from these classes $U_{in}$, and (iii) unlabeled images from related
classes $U_{out}$, as seen on figures to the right. Moreover, the classes
exhibit a long-tailed distribution with an imbalance ratio of 8 to 10. The
benchmark captures conditions observed in some realistic applications that are
not present in existing datasets used to evaluate semi-supervised learning.
See § 3 and Tab. 1 for details.

Semi-supervised learning (SSL) aims to exploit unlabeled data to train models
from a few labels, making them practical for applications where labels are a
bottleneck. Yet, the current literature on SSL with deep networks for image
classification has two main shortcomings. First, most methods are evaluated on
curated datasets such as CIFAR, SVHN, or ImageNet, where class distribution is
or is close to uniform and unlabeled data contains no novel classes. This is
implicit in methods that rely on the assumption that the data is uniformly
clustered, use a uniform instead of class-balanced loss, or categorize
unlabeled data into one of the labeled classes. In practice, however, class
distribution can be highly unbalanced or even unknown, and the unlabeled data
may contain novel classes. How effective is SSL in these situations?

Second, most literature has focused on training models from scratch. However,
a practical approach for few-shot learning is to use expert models trained on
large labeled datasets such as ImageNet [36] or iNaturalist [46]. What gains
does SSL provide in this setting, especially since many SSL methods are based
on learning invariances from data based on transformations which might have
already been learned by the experts during supervised training? Moreover, is
out-of-domain data beneficial when experts are available?

Our paper aims to answer these questions by conducting a systematic study of
SSL techniques (Fig. 1) on two fine-grained classification datasets that
exhibit a long-tailed distribution of classes and contain a large number of
out-of-class images (Fig. 2). These datasets are obtained by sampling classes
under the Aves (birds) and Fungi taxonomy. The out-of-class images are other
Aves (or Fungi) images not belonging to the classes within the labeled set.
The first dataset was part of the semi-supervised challenge at FGVC7 workshop
[41], while the second one is constructed from the FGVC fungi challenge [1]
following a similar scheme, details of which are described in § 3. We also
provide a benchmark on the CUB dataset [48] in the appendix.

On these datasets, we conduct a systematic study of existing deep-learning-
based semi-supervised learning approaches for image classification. We perform
experiments on SSL methods including Pseudo-Label [25], Curriculum Pseudo-
Label [8], FixMatch [39], self-training using distillation [52], self-
supervised learning (MoCo [18]), as well as their combinations when effective.
We investigate strategies for using unlabeled data when models are initialized
from experts. We also evaluate the performance of methods that use unlabeled
data from the same classes as the labeled dataset ($U_{in}$) and a practical
setting where the unlabeled data includes out-of-class images
($U_{in}+U_{out}$). The high-level summary of the experiments reported in Fig.
1, Tab. 2, 3, and Fig. 3 are as follows:

  * •

Some of the SSL methods are effective when models are trained from scratch,
especially those with self-supervised pre-training can significantly benefit
from out-of-class data (long blue whiskers and longer orange whiskers above
the _baseline_ for _scratch_ in Fig. 1). In this setting, self-supervised
learning followed by distillation-based self-training performs the best (Tab.
2 and 3).

  * •

The best SSL approach significantly under-performs the supervised fine-tuning
model trained on the labeled portion of the datasets (the _baseline_
performance of _ImageNet_ and _iNat_ is higher than any SSL model trained from
scratch in Fig. 1).

  * •

Picking the right expert provides further gains in this few-shot setting but
not when training using the entire labeled dataset (_oracle_ performance in
Fig. 1).

  * •

When training with experts, FixMatch gives the most improvements when having
$U_{in}$ only. However, the presence of out-of-class unlabeled data often
hurts performance. Self-Training was the most robust to the presence of out-
of-class data (Tab. 2, 3 and Fig. 3).

  * •

Surprisingly, we found that no method was able to reliably use out-of-class
data even though the domain shift is relatively small (the orange group is not
higher than the blue groups for _ImageNet_ and _iNat_ unlike _scratch_ in Fig.
1), echoing the experience of participants in the FGVC7 challenge [41].

  * •

The performance of SSL is far below the model trained using labels of the
entire in-class data suggesting that there is significant room for improvement
(_oracle_ performance in Fig. 1).

In summary, we conduct a systematic evaluation of several recently proposed
SSL techniques on two challenging datasets representing a long-tailed
distribution of fine-grained categories. We vary the initialization and the
domain of the unlabeled data and analyze the robustness of various SSL
approaches. Our experiments indicate that SSL does not work out-of-the-box in
a transfer learning setting, especially in the presence of out-of-domain data.
These results are in a similar vein to prior work on the evaluation of SSL
approaches that have analyzed the robustness of SSL techniques to the choice
of hyper-parameters [30], network architectures [9, 51], and domain shifts
[30, 42, 49], _etc_. However, the evaluation in a transfer learning setting on
the proposed benchmarks reveals additional insights. We hope these experiments
inspire practical methods that combine the benefits of supervised learning and
task-specific learning on partially labeled datasets.

##  2 Related Works

Semi-supervised learning has a long history in machine learning. In this
section, we describe the trends in recent techniques based on deep learning
and refer the reader to surveys on SSL for a comprehensive view [31, 56, 57,
45].

#### Self-Training.

These techniques use the model’s prediction to automatically generate labels
for the unlabeled data [27, 38]. Pseudo-Labeling [25] includes confident
predictions, _i.e_., those greater than a threshold for training. The pseudo-
labels can be added iteratively to induce a “curriculum” [8, 4, 17].
Alternatively, one can add an entropy penalty to encourage confident
predictions on the unlabeled data [15]. Other methods [52, 53, 58, 9] involve
re-training a “student model” from a “teacher model” using its prediction
computed in different ways. For example, adding noise and using a larger
student model [52, 58], selecting k-most confident pseudo-labels [53], or
using a distillation loss which softens the predictions [52, 9]. While these
methods have been shown to be successful in various datasets, the
effectiveness of the approach is critically dependent on the initial
performance of the model and the data distribution. Our experiments show that
the presence of out-of-class data negatively impacts some of these methods
while using expert initialization provides a significant benefit.

#### Consistency-based learning.

These methods learn by encouraging the consistency of the model’s predictions
on the unlabeled data. These could be across different augmentations of the
data [3, 34, 24, 37], including adversarial versions [28]. Alternatively,
consistency can be enforced across time, _e.g_., using moving average of the
predictions (_temporal ensembling_ [24]), using the moving average of model
parameters (_mean teacher_ [43]), or using a stochastic averaging of model
parameters [2]. A number of methods for _data augmentation_ have been proposed
which has generally improved both supervised and semi-supervised learning.
These include the variety of image augmentations proposed in RandAugment [11],
the CutOut scheme [12], linear combinations of images used in MixUp [55], and
even augmentations in the feature space [23]. These augmentations have been
incorporated in methods such as MixMatch [6], ReMixMatch [5], FixMatch [39],
UDA [51], and ICT [47] in different ways for consistency-based learning. We
choose FixMatch as the candidate approach which has shown state-of-the-art
results on existing SSL benchmarks, which we describe in detail in § 4. While
consistency via data-augmentation is effective when a model is trained from
scratch, it is unclear if this is effective when using a pre-trained model, as
invariance to these transformations may have been acquired during supervised
pre-training.

#### Self-supervised learning.

Another line of work has explored using self-supervised (or unsupervised)
learning objectives to improve semi-supervised learning. These include
incorporating pre-text tasks such as predicting image rotations [14], the
order of patches (jigsaw puzzle task) [29] during semi-supervised learning
[54, 42, 35]. Alternatively, self-supervised learning can be used as an
initialization before training with labels. The recent success of self-
supervised learning based on contrastive learning [32, 21, 18, 44, 9] has been
incorporated by several approaches leading to promising results on ImageNet
[9]. We also find that contrastive learning followed by self-training is the
best performing when trained from scratch on our benchmark. However, the value
of out-of-class data is diminished when using expert models.

#### Analysis of semi-supervised learning.

The most related to our work is that of Oliver  _et al_. [30] who provide a
benchmark for comparing deep-learning-based SSL methods for image
classification. While only CIFAR10 and SVHN datasets were used, the paper
pointed out that hyper-parameters can have a significant impact on
performance. Yet these are hard to tune without access to large amounts of
labeled data, which is precisely the setting in semi-supervised learning. In
our analysis, we pay careful attention to hyper-parameter optimization (see §
5.1). Their work also showed that transfer learning from experts can be more
effective, but did not explore if their combination with semi-supervised
learning can be helpful. In addition, they showed out-of-class unlabeled data
may be harmful, but the classes in $U_{in}$ and $U_{out}$ are widely
different. Last, their work as well as most SSL methods have been presented on
well-curated datasets. Our work focuses on the evaluation in a realistic
setting and includes an analysis of methods proposed since Oliver  _et al_.’s
paper. These include methods based on self-training, self-supervised training,
and FixMatch which outperform the consistency-based approach [28] analyzed in
their paper. More comparisons between [30] are provided in the appendix.

##  3 A Realistic Benchmark

Dataset | Classes | Images | Unlabeled | Image | Class | Imbalance
---|---|---|---|---|---|---
${L}_{in}$ / ${U}_{in}$ / ${U}_{out}$ |  ${L}_{in}$ / ${U}_{in}$ / ${U}_{out}$ | Class Domain | Resolution | Distribution | Ratio
CIFAR-10 | 10 / 10 / 0 | 4K / 40K / 0 | ${L}={U}$ | 32$\times$32 | uniform | 1
CIFAR-100 | 100 / 100 / 0 | 10K / 50K / 0 | ${L}={U}$ | 32$\times$32 | uniform | 1
SVHN | 10 / 10 / 0 | 1K / 65K / 0 | ${L}={U}$ | 32$\times$32 | uniform | 1
STL-10 | 10 / 0 / - | 5K / 0 / 100K | ${L}\neq{U}$ | 96$\times$96 | uniform | 1
ImageNet | 1000 / 1000 / 0 | 140K / 1.26M / 0 | ${L}={U}$ | 224$\times$224 |  $\approx$ uniform | 1.8
Semi-Aves | 200 / 200 / 800 | 6K / 27K / 122K | ${L}={U}_{in}\neq{U}_{out}$ | 224$\times$224 | long-tailed | 7.9
Semi-Fungi | 200 / 200 / 1194 | 4K / 13K / 65K | ${L}={U}_{in}\neq{U}_{out}$ | 224$\times$224 | long-tailed | 10.1
Table 1: A comparison of Semi-Aves and Semi-Fungi datasets with existing SSL
benchmarks. The Semi-Aves and Semi-Fungi present a challenge due to the large
number of classes, presence of novel images in the unlabeled set, long-tailed
distribution of classes as indicated by the class imbalance ratio (maximum /
minimum images per class) in the training set.

In SSL, we are provided with labeled training data $(x_{i},y_{i})\in{L}_{in}$
and unlabeled training data $(u_{i},\cdot)\in{U}$. The unlabeled data can
either belong to the same classes as the labeled data ($U_{in}$), or to novel
classes ($U_{out}$). In a realistic setting, one may expect that the unlabeled
data contains novel classes. In many applications it is easy to acquire images
from related domains through coarse labeling, _e.g_., it is easier to label an
image as a bird than a “yellow bunting”. Such images could be potentially used
to learn better representations. Thus we evaluate SSL methods in two settings,
one when the unlabeled data contains no novel images, and another when it
does, _i.e_., $U_{in}$ and $U_{in}+U_{out}$ respectively.

We use two datasets by sampling classes from the natural domains for our
benchmark. As shown in Fig. 2, the classes belong to the Aves and Fungi
taxonomy and contain a long-tailed distribution of classes, as commonly
observed in fine-grained domains. Tab. 1 shows a comparison with other
benchmarks. Larger image sizes, significant class imbalance, fine-grained
categories, and a large number of out-of-class images allow a more realistic
evaluation of SSL techniques. Below we describe each dataset.

#### Semi-Aves.

We use the dataset from the semi-supervised challenge at the FGVC7 workshop at
CVPR 2020 [41]. The dataset includes a subset of bird species from the Aves
kingdom of iNaturalist 2018 dataset [46]. However, there are no overlapping
images since the images were collected from recent years. There are 200 in-
class and 800 out-of-class categories. The training and validation set has a
total of 5959 labeled images, 26,640 and 122,208 in-class and out-of-class
unlabeled images, and 8000 test images. The training data in $L_{in}$,
$U_{in}$, and $U_{out}$ is long-tail distributed, specifically $L_{in}$ has 15
to 53 images and $U_{in}$ has 16 to 229 images per class. The test data has a
uniform distribution with 40 images per class.

#### Semi-Fungi.

We create a Semi-Fungi dataset following the similar strategy of the Semi-Aves
dataset. We use the train-val set of images from the FGVCx Fungi challenge at
the FGVC5 workshop at CVPR 2018 [1]. The dataset was collected from the
“Svampe Atlas”111https://svampe.databasen.org website, thus the image domain
is different from iNaturalist. The original dataset has 1394 fungi species
with a long-tailed distribution. We first sort the classes by frequency and
randomly select 200 of the top 600 classes as in-class categories. We then
select 20 images per class as the test set, and randomly select 4141 images as
labeled data and the rest 13,166 images as in-class unlabeled data. The rest
1194 species are used as out-of-class unlabeled images, which has a total of
64,871 images. In Semi-Fungi, there are 6 to 78 images per class in $L_{in}$,
and 16 to 276 images in $U_{in}$. The test set is uniformly distributed with
20 images per class.

##  4 Methods

In this section, we describe the details of the SSL methods we compared in our
benchmark.

(1) Supervised baseline / oracle:

We train the model only using labeled data $L_{in}$ with a cross-entropy loss.
For the oracle, we include the ground-truth labels of $U_{in}$ for training.

(2) Pseudo-Labeling [25]:

The approach uses a base model’s confident predictions on unlabeled images as
labels. Concretely, if the maximum probability of a class is greater than a
threshold $\tau$, we then take the class as the target label. Following the
implementation of Oliver _et al_. [30], we sample half of the batch from
$L_{in}$ and half from unlabeled data $U$ during training. Denote
$(x_{i},y_{i})$ as a labeled sample, the predictions on unlabeled data $u_{i}$
of the model $f$ as $q_{i}=f(u_{i})$, pseudo-label as
$\hat{q}_{i}=\operatorname*{argmax}(q_{i})$, and cross-entropy function as
$H(p,q)=-\sum_{r}p(r)\log q(r)$. Then, the objective for each batch is:

$\mathcal{L}=\sum_{j=1}^{n}H(y_{i},f(x_{i}))+\sum_{i=1}^{n}\mathds{1}\big{[}\max(q_{i})\geq\tau\big{]}H(\hat{q_{i}},q_{i}).$
(1)

(3) Curriculum Pseudo-Labeling [8]:

Unlike pseudo-labeling where labels are generated in an online manner,
curriculum labeling generates pseudo-labels after the training is finished on
the current labeled set before retraining. We first train a supervised model
on labeled data $L_{in}$, then select images with the highest predictions from
all the unlabeled data $u\in{U}$, and add them with their pseudo-labels to the
labeled dataset. In the next iteration, we retrain a model _from scratch_
using the new set of labeled data. We repeat this process 5 times and select
{20, 40, 60, 80, 100}% of the unlabeled data from the original pool of
unlabeled data $U$. The steps are as the following:

  1. (i)

Initialize $L=L_{in}$, $\beta=20$.

  2. (ii)

Supervised training on $L$ .

  3. (iii)

Generate predictions $q=f_{\theta}(x)$ for every $u\in{U}$.

  4. (iv)

From ${U}$ select $\beta$% examples with highest prediction scores and their
pseudo-labels as ${L}_{top}$.

  5. (v)

Add selected unlabeled data with their pseudo-labels to the labeled dataset
${L}={L_{in}}\cup{L}_{top}$.

  6. (vi)

If $\beta<$100, $\beta=\beta+$20 and repeat from step (ii) .

(4) FixMatch:

FixMatch combines pseudo-labeling and consistency regularization. For each
unlabeled image, it minimizes the cross-entropy between the pseudo-label
(thresholded prediction) of the weakly-augmented image and the predictions of
the strong-augmented image. For labeled data, only weak augmentations are
applied. Specifically, let $\alpha$ be a weak augmentation (image flipping in
our case) and $\mathcal{A}$ be a strong augmentation (RandAugment [11] in our
case). Let the predictions under strong and weak augmentations are
$Q_{i}=f(\mathcal{A}(u_{i}))$, $q_{i}=f(\alpha(u_{i}))$. The total loss for
labeled and unlabeled data is

$\mathcal{L}=\sum_{j=1}^{m}H(y_{j},f(\alpha(x_{j})))+\sum_{i=1}^{km}\mathds{1}\big{[}\max(q_{i})\geq\tau\big{]}H(\hat{q_{i}},Q_{i}).$
(2)

In the original implementation, each batch uses $m$ labeled and $km$ unlabeled
data with a total batch size $n=(k+1)m$, where the sampling ratio $k$ is a
hyper-parameter.

(5) Self-Training:

While the term of “Self-Training” is general, we use this to refer to the
following procedure using distillation [20]. We first train a supervised model
$f^{t}$ on the labeled data which we call the teacher model, then train a
student model $f^{s}$ with scaled cross-entropy loss on the unlabeled data and
cross-entropy loss on labeled data. Distillation was originally used for model
compression [7], but has been shown to improve the performance when training
the student model with the same architecture [13] or across different
modalities [44, 16, 40]. Given unlabeled data $(u,\cdot)$, let the _logits_
from teacher and student model as $z^{t}$ and $z^{s}$, and the prediction of
labeled data $(x,y)$ from the student model is $y^{s}$. The objective includes
the cross-entropy loss for labeled data $(x,y)$, and the distillation loss for
unlabeled data:

$\mathcal{L}=(1-\lambda)\sum_{j=1}^{n}H(y_{j},y_{j}^{s})+\lambda\sum_{i=1}^{n}H\left(\sigma\left(\frac{z_{i}^{t}}{T}\right),\sigma\left(\frac{z_{i}^{s}}{T}\right)\right),$
(3)

where $\lambda$ is the weight between supervised and distillation losses,
$\sigma$ is the softmax function, and $T$ is a temperature (scaling)
parameter.

(6) Self-Supervised Learning (MoCo [18]):

We use momentum contrastive (MoCo) learning as a strong baseline for self-
supervised training. MoCo learns an image encoder $f(x)$ that maps the image
$x$ to a representation $q=f(x)$ and uses a contrastive objective that
requires positive pairs to be closer than negative pairs in the representation
space. The positive pairs are sampled from two geometric or photometric
augmented views of a same images while negative images are augmentations from
different images. MoCo adapts the InfoNCE [32] loss as the objective function.
The loss for each encoded query $q$ is:

$\mathcal{L}_{q}=-\log\frac{\exp\left(q\cdot k^{+}/T\right)}{\exp(q\cdot
k^{+}/T)+\sum_{i}^{K}\exp(q\cdot k_{i}^{-}/T)},$ (4)

where $T$ is the temperature, $k^{+}$ and $k^{-}$ are the positive and
negative sample of the query $q$. The number of negative samples $K$ is
limited by the mini-batch size. In order to stabilize the training, MoCo uses
the memory bank [50] to store the negative samples and updates the encoder of
the keys in the memory bank based on momentum. After the self-supervised pre-
training, we remove the MLP layers after the global average pooling layer, add
a linear classifier (a fully convolutional layer followed by softmax), and
train the entire network with supervised cross-entropy loss. We found that
freezing the pre-trained backbone gives worse performance than fine-tuning the
entire network.

(7) MoCo + Self-Training:

Here we initialize the model using MoCo learning on the unlabeled data before
semi-supervised learning using Self-Training. A recent work by Chen  _et al_.
[9] has shown this to be a strong semi-supervised learning baseline. The
procedure is as follows:

  1. (i)

Pre-train the model using MoCo on $L_{in}$ and $U$.

  2. (ii)

Fine-tune the model on $L_{in}$ with a cross-entropy loss. Call this the
teacher model $f^{t}$.

  3. (iii)

Train a student model $f^{s}$ initialized from step (i) with distillation loss
(Eq. 3) using the teacher model $f^{t}$.

##  5 Experiments

| Method | from scratch | from ImageNet | from iNat
---|---|---|---|---
| Top1 | Top5 | Top1 | Top5 | Top1 | Top5
| Supervised baseline | 20.6$\pm$0.4 | 41.7$\pm$0.7 | 52.7$\pm$0.2 | 78.1$\pm$0.1 | 65.4$\pm$0.4 | 86.6$\pm$0.2
| Supervised oracle | 57.4$\pm$0.3 | 79.2$\pm$0.1 | 68.5$\pm$1.4 | 88.5$\pm$0.4 | 69.9$\pm$0.5 | 89.8$\pm$0.7
${U}_{in}$ | Pseudo-Label [25] | 16.7$\pm$0.2 | 36.5$\pm$0.8 | 54.4$\pm$0.3 | 78.8$\pm$0.3 | 65.8$\pm$0.2 | 86.5$\pm$0.2
Curriculum Pseudo-Label [8] | 20.5$\pm$0.5 | 41.7$\pm$0.5 | 53.4$\pm$0.8 | 78.3$\pm$0.5 | 69.1$\pm$0.3 | 87.8$\pm$0.1
FixMatch [39] | 28.1$\pm$0.1 | 51.8$\pm$0.6 | 57.4$\pm$0.8 | 78.5$\pm$0.5 | 70.2$\pm$0.6 | 87.0$\pm$0.1
Self-Training | 22.4$\pm$0.4 | 44.1$\pm$0.1 | 55.5$\pm$0.1 | 79.8$\pm$0.1 | 67.7$\pm$0.2 | 87.5$\pm$0.2
MoCo [18] | 28.2$\pm$0.3 | 53.0$\pm$0.1 | 52.7$\pm$0.1 | 78.7$\pm$0.2 | 68.6$\pm$0.1 | 87.7$\pm$0.1
MoCo + Self-Training | 31.9$\pm$0.1 | 56.8$\pm$0.1 | 55.9$\pm$0.2 | 80.3$\pm$0.1 | 70.1$\pm$0.2 | 88.1$\pm$0.1
${U}_{in}+{U}_{out}$ | Pseudo-Label [25] | 12.2$\pm$0.8 | 31.9$\pm$1.6 | 52.8$\pm$0.5 | 77.8$\pm$0.1 | 66.3$\pm$0.3 | 86.4$\pm$0.2
Curriculum Pseudo-Label [8] | 20.2$\pm$0.5 | 41.0$\pm$0.9 | 52.8$\pm$0.5 | 77.8$\pm$0.1 | 69.1$\pm$0.1 | 87.6$\pm$0.1
FixMatch [39] | 19.2$\pm$0.2 | 42.6$\pm$0.6 | 49.7$\pm$0.2 | 72.8$\pm$0.5 | 64.2$\pm$0.2 | 84.5$\pm$0.1
Self-Training | 22.0$\pm$0.5 | 43.3$\pm$0.2 | 55.5$\pm$0.3 | 79.7$\pm$0.2 | 67.6$\pm$0.2 | 87.6$\pm$0.1
MoCo [18] | 38.9$\pm$0.4 | 65.4$\pm$0.3 | 51.5$\pm$0.4 | 77.9$\pm$0.2 | 67.6$\pm$0.1 | 87.3$\pm$0.2
MoCo + Self-Training | 41.2$\pm$0.2 | 65.9$\pm$0.3 | 53.9$\pm$0.2 | 79.4$\pm$0.3 | 68.4$\pm$0.2 | 87.6$\pm$0.2
Table 2: Results on Semi-Aves benchmark. We experiment with six different SSL methods as well as supervised baselines under different settings: (1) using $U_{in}$ or $U_{in}+U_{out}$ as the unlabeled dataset, (2) training from scratch, or using ImageNet or iNat pre-trained model. We show that when training from scratch with $U_{in}$, MoCo + Self-Training performs the best. When having expert models, transfer learning is a strong baseline, and FixMatch and Self-Training can still give improvements. When adding unlabeled data from $U_{out}$, the performance pales except for the self-supervised method when training from scratch. The best results and those within the variance are marked in teal.  | Method | from scratch | from ImageNet | from iNat
---|---|---|---|---
| Top1 | Top5 | Top1 | Top5 | Top1 | Top5
| Supervised baseline | 31.0$\pm$0.4 | 54.7$\pm$0.8 | 53.8$\pm$0.4 | 80.0$\pm$0.4 | 52.4$\pm$0.6 | 79.5$\pm$0.5
| Supervised oracle | 60.2$\pm$0.8 | 83.3$\pm$0.9 | 73.3$\pm$0.1 | 92.5$\pm$0.3 | 73.8$\pm$0.3 | 92.4$\pm$0.3
${U}_{in}$ | Pseudo-Label [25] | 19.4$\pm$0.4 | 43.2$\pm$1.5 | 51.5$\pm$1.2 | 81.2$\pm$0.2 | 49.5$\pm$0.4 | 78.5$\pm$0.2
Curriculum Pseudo-Label [8] | 31.4$\pm$0.6 | 55.0$\pm$0.6 | 53.7$\pm$0.2 | 80.2$\pm$0.1 | 53.3$\pm$0.5 | 80.0$\pm$0.5
FixMatch [39] | 32.2$\pm$1.0 | 57.0$\pm$1.2 | 56.3$\pm$0.5 | 80.4$\pm$0.5 | 58.7$\pm$0.7 | 81.7$\pm$0.2
Self-Training | 32.7$\pm$0.2 | 56.9$\pm$0.2 | 56.9$\pm$0.3 | 81.7$\pm$0.2 | 55.7$\pm$0.3 | 82.3$\pm$0.2
MoCo [18] | 33.6$\pm$0.2 | 59.4$\pm$0.3 | 55.2$\pm$0.2 | 82.9$\pm$0.2 | 52.5$\pm$0.4 | 79.5$\pm$0.2
MoCo + Self-Training | 39.4$\pm$0.3 | 64.4$\pm$0.5 | 58.2$\pm$0.5 | 84.4$\pm$0.2 | 55.2$\pm$0.5 | 82.9$\pm$0.2
${U}_{in}+{U}_{out}$ | Pseudo-Label [25] | 15.2$\pm$1.0 | 40.6$\pm$1.2 | 52.4$\pm$0.2 | 80.4$\pm$0.5 | 49.9$\pm$0.2 | 78.5$\pm$0.3
Curriculum Pseudo-Label [8] | 30.8$\pm$0.1 | 54.4$\pm$0.3 | 54.2$\pm$0.2 | 79.9$\pm$0.2 | 53.6$\pm$0.3 | 79.9$\pm$0.2
FixMatch [39] | 25.2$\pm$0.3 | 50.2$\pm$0.8 | 51.2$\pm$0.6 | 77.6$\pm$0.3 | 53.1$\pm$0.8 | 79.9$\pm$0.1
Self-Training | 32.5$\pm$0.5 | 56.3$\pm$0.3 | 55.7$\pm$0.3 | 81.0$\pm$0.2 | 55.2$\pm$0.2 | 82.0$\pm$0.3
MoCo [18] | 44.6$\pm$0.4 | 72.6$\pm$0.5 | 52.9$\pm$0.3 | 81.2$\pm$0.1 | 51.0$\pm$0.2 | 78.5$\pm$0.3
MoCo + Self-Training | 48.6$\pm$0.3 | 74.7$\pm$0.2 | 55.9$\pm$0.1 | 82.9$\pm$0.2 | 54.0$\pm$0.2 | 81.3$\pm$0.3
Table 3: Results on Semi-Fungi benchmark. We experiment on Semi-Fungi using
the same hyper-parameters from Semi-Aves in Table 2. We can see similar
conclusions: When training from scratch, MoCo + Self-Training performs the
best and adding $U_{out}$ can give an extra performance boost. With expert
models, FixMatch and Self-Training (with or without MoCo) is often the best
performing one, but the latter is more robust to the out-of-class data.

###  5.1 Implementation details

#### Network architecture and pre-training.

For a fair comparison, we use a ResNet-50 network [19] on 224$\times$224
images for all our experiments. For transfer learning, we use pre-trained
models on ImageNet [36] and iNaturalist 2018 (iNat) [46] dataset, which
contains 8142 species including 1248 Aves and 321 Fungi species. Note that
there are _no overlapping images_ between iNat’s training set and Semi-Aves,
though there are overlapping categories. The images for Semi-Fungi images do
not overlap with iNaturalist, but we do not know how many overlapping classes
there are as species names were not provided in the original dataset [1] from
which it was constructed. However, this is less of a concern as we find that
iNat pre-trained model performs worse than an ImageNet pre-trained model on
Semi-Fungi, suggesting the class overlap is likely small if any. To obtain an
iNat pre-trained model, we train the model using SGD with momentum with a
learning rate of 0.0045 and a batch size of 64 for 75 epochs which matches the
reported 60% Top-1 accuracy222https://github.com/macaodha/inat_comp_2018. We
use the ImageNet pre-trained model from torchvision [33].

#### Data augmentation.

For the Semi-Fungi dataset, we first pre-process the images to have a maximum
of 300 pixels for each side, while Semi-Aves has a maximum of 500 pixels. We
use random-resize-crop to the size of 224$\times$224 and random-flipping for
data augmentation, for all the methods except for MoCo and FixMatch. MoCo
additionally uses Gaussian blur, color jittering, and random grayscale
conversion, while FixMatch uses RandAugment [11].

#### Hyperparameter search.

We found the SSL methods to be sensitive to hyper-parameters such as learning
rates, weight decay, etc. As noted in [30], a small validation set poses a
risk of picking sub-optimal hyper-parameters. Moreover, labeled data is best
used as a source of supervision. While k-fold cross-validation is an
alternative, it is expensive. Hence, we use the combined training and
validation set for training SSL methods in our experiments and report
performance on the test set which is sufficiently large. In particular,
hyperparameters for all methods were based on the performance on the Semi-Aves
dataset and kept fixed for the Semi-Fungi dataset (Tab. 3). Thus the results
in Tab. 2 should be seen as a validation set performance, while those in Tab.
3 represent a novel test set. However, the high-level conclusions are
identical across the two benchmarks.

#### Semi-supervised training.

For SSL methods except for FixMatch, we use SGD with a momentum of 0.9 and a
cosine learning rate decay schedule [26] following [22, 39] for optimization.
Learning rate and weight decay were picked from a range of [0.03, 0.0001]. We
use a batch size of 64 during training. When there is unlabeled data, we
select half of the batch from labeled and another half from unlabeled data (32
each). We train models for 10k and 50k iterations for training from expert
models and from scratch. Other hyper-parameters include threshold $\tau$ for
Pseudo-Labeling, which we select from {0.80, 0.85, 0.90, 0.95}. When training
from scratch, we use $\tau$=0.85 and 0.8 for with and without $U_{out}$; when
training from experts we use $\tau$=0.95. For Self-Training, we set $T$=1 and
$\lambda$=0.7 for all the experiments. For FixMatch [39], we are able to train
the model up to a batch size of 192 (32 labeled and 160 unlabeled images) on 4
GPUs. We find the performance drops significantly with small batch size
(_e.g_. 48), however, we are unable to use the same batch size as original
paper (_i.e_. 6144) due to limited resources. We use a learning rate of 0.01
and threshold $\tau$=0.80 to train FixMatch for 500 epochs when training from
scratch and 250 epochs with pre-trained models. We report the results from the
last training epoch for all the methods. We also notice that FixMatch has more
overfitting and the results could be further improved. More details are
provided in the appendix.

#### Self-supervised training.

We adopt the default settings of MoCo-v2 [10], including MLP projector, 800
training epochs, _etc_., but adapt the number of negative samples and learning
rate to our task. We use a batch size of 256 and 2048 negative samples in all
experiments. We find that using a large number of negative samples (_e.g_.
65,536) hurts the performance. When training the MoCo from scratch, we use the
default learning rate of 0.03; when training MoCo from ImageNet or iNaturalist
pre-trained model, we use a smaller learning rate (0.0003) and fewer training
epochs (200) to avoid the potential forgetting problem. In the end, we train a
classifier on the global average pooling features of ResNet-50 without
freezing the backbone. We find that freezing the feature encoder always leads
to worse performance than fine-tuning the entire network.

###  5.2 Results

Our experimental results on Semi-Aves and Semi-Fungi are shown in Tab. 2 and
3, respectively. To better visualize the results, we plot the relative gain of
each SSL method, _i.e_. the differences between supervised baseline in raw
accuracy, on both datasets in Fig. 3. We discuss the results of each setting
in the following.

#### Training from scratch.

We first discuss the results of training from scratch using only $U_{in}$ on
both datasets. Comparing to supervised baseline, Curriculum Pseudo-Label does
not give improvements and Pseudo-Label even underperforms the baseline. This
is possibly due to the low initial accuracy of the model which gets amplified
during pseudo labeling. FixMatch and Self-Training both result in
improvements. Self-supervised learning (MoCo) gives a good initialization and
the improvements are similar or even more than using FixMatch. Finally, Self-
Training using MoCo pre-trained model as the teacher model results in a
further 2-3% improvement.

Figure 3: Relative gains of SSL methods on Semi-Aves and Semi-Fungi. Left:
trained from scratch. Right: using expert models. For each SSL method, we plot
the relative gain, _i.e_. the difference between the supervised baseline in
raw accuracy, from the results in both Tab. 2 and 3. This shows that (1) the
presence of out-of-class data $U_{out}$ often hurts the performance, and (2)
Self-Training is often the best method when using pre-trained models.

#### Using expert models.

We then consider using an ImageNet or iNat pre-trained model for transfer
learning with $U_{in}$ only. The transfer learning baseline from either expert
model outperforms the best SSL method (MoCo + Self-Training) trained from
scratch by a large margin, showing that transfer learning is more powerful in
our realistic datasets. This observation echos Oliver  _et al_. [30] who
showed transferring from ImageNet to CIFAR10 performs better than SSL methods.
Next, we can see that most of the SSL methods, as well as MoCo pre-training,
provide improvements over the baselines. The only exception is Pseudo-Label on
Semi-Fungi. Among SSL methods, FixMatch and MoCo + Self-Training perform the
best.

#### Effect of out-of-class unlabeled data.

Now we consider the setting where the unlabeled data contains both in-class
and out-of-class data ($U_{in}+U_{out}$). This is the trade-off between more
unlabeled data at the cost of a distribution shift. This effect can be seen in
the orange vs. blue plot in Fig. 3. When training from scratch, the
performances of Pseudo-Label and FixMatch drop by 4-9%, while Curriculum
Pseudo-Label and Self-Training only drop by less than 1%, showing that they
are more robust to the domain shift of unlabeled data. On the other hand,
self-supervised pre-training (MoCo) can benefit significantly from $U_{out}$,
providing around 11% improvement over using $U_{in}$ only on both Aves and
Fungi datasets. Combining with Self-Training gives another 3-6% improvement,
making the gap between transfer learning baseline smaller.

Finally, we consider having $U_{in}+U_{out}$ with expert models. In Fig. 3 we
can see the performance often drops in the presence of $U_{out}$. Curriculum
Pseudo-Label and Self-Training are more robust and yield less than 1% decrease
in most cases, while FixMatch is less robust whose performance drops by around
6%. The performances of MoCo also drops around 1-3% and are sometimes worse
than the supervised baseline. Adding Self-Training however provides a 1-3%
boost in performance. Overall, Self-Training from either a supervised or a
self-supervised model is the most robust one.

#### Robustness to hyper-parameters and trends.

We found Pseudo-Label to be sensitive to the threshold $\tau$. When using
experts higher thresholds worked better. Increasing the threshold also
increased the robustness in the presence of novel classes. Curriculum Pseudo-
Label was found to be more robust in our benchmark, even when adding
$U_{out}$. Self-Training was the most robust to hyper-parameters, we chose the
same temperature $T$ and weight $\lambda$ for all the experiments and it
consistently improved results regardless of using an expert model or using
out-of-domain data.

##  6 Conclusion

There has been a significant interest in self-supervised and semi-supervised
learning towards the goal of learning from a few examples. However, these
methods should be studied in the broader context of approaches for transfer
learning, model selection, active learning, and hyperparameter optimization
for it to have an impact on realistic applications. Our benchmark is a step in
this direction where we find the strong performance on benchmarks like CIFAR
and ImageNet does not always translate to other datasets that violate
assumptions implicit in the learning methods.

Self-supervised learning followed by Self-Training is a strong baseline in the
absence of experts. Of surprise is the marginal gains some SSL methods provide
when experts are available. Of encouragement is that the simple baseline of
Self-Training from experts is robust to out-of-domain data. Moreover, no
method was able to reliably use a large number of out-of-class examples in
either domain despite our extensive search over model hyper-parameters and
small domain shifts. Yet, the performances of these methods are far from
saturated as indicated by the supervised oracle leaving much room for
improvement. We hope our proposed benchmarks and results lead to new
innovations in SSL.

#### Acknowledgements

This project is supported in part by NSF #1749833 and was performed using high
performance computing equipment obtained under a grant from the Collaborative
R&D Fund managed by the Massachusetts Technology Collaborative.

##  Appendix A Appendix

###  A.1 Results on Semi-Aves with a different split

Since the original split of Semi-Aves was used for hyper-parameter selection,
we create another split of the dataset for additional evaluation, which can be
seen as a two-fold cross-validation. We first merge the images from $L_{in}$,
$U_{in}$, and test sets, then randomly redistribute. The classes and the
number of images of each class are kept the same in each set. The $U_{out}$
set is also unchanged. Thus this split has roughly the same difficulty as the
original split but contains new in-domain training and test images. We show
the results of this split in Tab. A.2, using the same hyper-parameters of the
main paper. The trends are similar — Self-Training and FixMatch are both
effective, but FixMatch is affected negatively by the out-of-class data.

###  A.2 SSL benchmark on the CUB dataset

Since Semi-Aves and Semi-Fungi are new datasets, here we provide another
benchmark based on the widely-used Caltech-UCSD Birds-200-2011 (CUB) dataset
[48]. The original class labels are sorted by the species name. Hence, we
select the 100 _odd_ classes as in-class species and 100 _even_ classes as
out-of-class species, to ensure a low domain mismatch between $U_{in}$ and
$U_{out}$. There are 41-60 images per class originally (disregard the original
training/test split). For each in-class species, we select 5/5/10 images for
$L_{in}$, validation set, and test set. The rest (21-40 images) are used for
unlabeled data $U_{in}$. For out-of-class species, all the images are included
in $U_{out}$. The statistics of the dataset split is shown in Tab. A.1. Since
the dataset is quite small, we did not use self-supervised learning (MoCo) for
pre-training, and we use the validation set to select the best model. The
results on the CUB dataset are shown in Tab. A.3. In this benchmark, we can
see that both Curriculum Pseudo-Label and Self-Training are helpful, even when
having $U_{out}$ included. This is potentially due to the small domain
mismatch between the two sets of unlabeled data.

split $\rightarrow$ | $L_{in}$ | val | test | $U_{in}$ | $U_{out}$
---|---|---|---|---|---
#images $\rightarrow$ | 500 | 500 | 1000 | 3853 | 5903
Table A.1: Number of images in the CUB benchmark. | Method | from scratch | from ImageNet | from iNat
---|---|---|---|---
| Top1 | Top5 | Top1 | Top5 | Top1 | Top5
| Supervised baseline | 21.8 | 42.9 | 51.9 | 76.0 | 66.7 | 85.9
| Supervised oracle | 56.0 | 78.7 | 71.9 | 89.4 | 76.7 | 91.2
${U}_{in}$ | Pseudo-Label [25] | 18.0 | 37.4 | 54.3 | 79.1 | 66.3 | 86.4
Curriculum Pseudo-Label [8] | 20.0 | 41.5 | 53.4 | 79.0 | 70.0 | 88.7
FixMatch [39] | 24.0 | 47.6 | 58.2 | 79.6 | 70.4 | 88.2
Self-Training | 23.7 | 45.1 | 53.9 | 76.8 | 67.6 | 86.4
MoCo [18] | 28.5 | 54.7 | 52.8 | 79.2 | 69.4 | 88.3
MoCo + Self-Training | 34.0 | 58.9 | 56.6 | 80.1 | 71.1 | 88.3
${U}_{in}+{U}_{out}$ | Pseudo-Label [25] | 11.8 | 30.7 | 53.6 | 78.1 | 66.8 | 86.4
Curriculum Pseudo-Label [8] | 21.3 | 42.1 | 53.8 | 79.4 | 69.9 | 88.5
FixMatch [39] | 17.5 | 39.7 | 50.8 | 74.4 | 65.1 | 85.1
Self-Training | 23.0 | 45.0 | 54.3 | 77.1 | 68.0 | 86.1
MoCo [18] | 37.9 | 65.4 | 51.0 | 78.6 | 68.5 | 87.8
MoCo + Self-Training | 40.8 | 66.8 | 55.0 | 80.2 | 68.9 | 87.9
Table A.2: Results on Semi-Aves benchmark with a different split. Using the same hyper-parameters, we can see similar conclusions here as using the original split. Overall, Self-Training and FixMatch are effective but out-of-class data often hurts the performance.  | Method | from scratch | from ImageNet | from iNat
---|---|---|---|---
| Top1 | Top5 | Top1 | Top5 | Top1 | Top5
| Supervised baseline | 11.1 | 27.4 | 58.7 | 85.8 | 77.3 | 94.2
| Supervised oracle | 68.5 | 87.8 | 84.5 | 97.1 | 90.0 | 98.0
${U}_{in}$ | Pseudo-Label [25] | 13.5 | 32.1 | 57.0 | 85.3 | 78.3 | 95.7
Curriculum Pseudo-Label [8] | 14.5 | 31.4 | 57.3 | 84.7 | 80.1 | 96.7
FixMatch [39] | 10.7 | 26.6 | 53.2 | 79.8 | 81.6 | 95.2
Self-Training | 12.6 | 29.8 | 61.3 | 86.3 | 80.6 | 95.8
${U}_{in}+{U}_{out}$ | Pseudo-Label [25] | 11.9 | 30.8 | 59.1 | 86.1 | 77.7 | 94.8
Curriculum Pseudo-Label [8] | 12.9 | 32.3 | 59.6 | 86.5 | 81.2 | 96.8
FixMatch [39] | 10.7 | 27.1 | 52.8 | 81.7 | 78.6 | 95.7
Self-Training | 12.2 | 29.2 | 61.4 | 85.9 | 79.9 | 96.0
Table A.3: SSL benchmark on the CUB dataset. In this benchmark, we can see
both Curriculum Pseudo-Label and Self-Training are helpful, even with out-of-
class unlabeled data.

###  A.3 Related prior work on SSL analysis

On out-of-class unlabeled data. Oliver _et al_. [30] showed that out-of-class
unlabeled data negatively impacts performance, but analysis was done on
CIFAR-10 with images from 6 labeled and 4 unlabeled classes. The classes are
quite different making the problem of selecting in-domain images relatively
easy in comparison to fine-grained domains — in our benchmarks the out-of-
class data $U_{out}$ are other species of birds or fungi. In fact, we show
that more out-of-class data helps when using self-supervised and self-training
methods trained from scratch. However, the additional data does not seem to
help when initialized with experts.

On transfer learning. Oliver _et al_. showed a transfer learning accuracy of
87.9% on CIFAR-10 with 4k labels, outperforming many SSL methods including PL
[25] and VAT+EM [28]. Although recent results are better, the low resolution
of CIFAR-10 (32$\times$32 pixels) makes transfer learning from ImageNet less
effective. On STL-10 that has a higher resolution (96$\times$96 pixels), fine-
tuning a ImageNet pre-trained ResNet-50 model on 5k labels provides 97.2%
accuracy, while that trained on iNaturalist provides 95.0% accuracy. This
beats 94.8% of FixMatch using 5k labeled examples when trained from scratch.
Note that the iNaturalist dataset has no overlap with STL-10, yet transfer
learning is effective.

Figure A.1: Pseudo-label with different threshold $\tau$. Pseudo-label is
sensitive to the threshold. The negative impact of out-of-class unlabeled data
is reduced by increasing the threshold, yet when the initial performance is
low the scheme is not effective as seen by the performance of the ImageNet
pre-trained model.

Figure A.2: Predictions of unlabeled data using a supervised model. We plot
the distribution of the predictions of data from $U_{in}$ and $U_{out}$.
Specifically, we plot the maximum probability of the class predictions (left),
entropy of the predictions (middle), and the distillation loss between the
teacher and student model before the training starts (right). Unlabeled data
from the same distribution tend to have a higher maximum probability, a lower
entropy, or a higher distillation loss.

###  A.4 Analysis on out-of-class unlabeled data

The effect of threshold parameter for Pseudo-Label. We found Pseudo-Label
method is sensitive to the threshold parameter $\tau$. Fig. A.1 plots the
accuracy as a function of $\tau$ with different unlabeled data and experts on
Semi-Aves. A higher threshold performs better, especially in the presence of
out-of-class data $U_{out}$ as this excludes novel class images where the
confidence of prediction is likely to be low. On the other hand, lower values
work just as well when unlabeled data is in-domain $U_{in}$. However, this
scheme only appears to work when using strong experts (_e.g_., iNat) whose
confidence is likely calibrated, unlike random or ImageNet pre-trained model,
where the presence of out-of-class data reduces performance. This poses a
practical problem for this method — increasing the threshold increases
robustness but reduces the amount of unlabeled data that is used during
training.

###  A.5 The effect of out-of-class unlabeled data.

To see how the domain mismatch between $U_{in}$ and $U_{out}$ can affect SSL
methods, we analyze the predictions of the unlabeled data. We use the
supervised model trained on $L_{in}$ to compute the predictions of the
unlabeled data on the Semi-Aves dataset. We plot the histogram of the maximum
probability and the entropy of the predictions of $U_{in}$ and $U_{out}$ in
Fig. A.2 (left and middle). We also plot the distribution of the distillation
loss, which is calculated between the supervised model (teacher) and the
ImageNet pre-trained model (student), with a temperature $T=1$ (Fig. A.2
right). This is in the beginning of the self-training process and the last
layer of the student model is randomly initialized. Overall, the model is
generally more uncertain about the out-of-class data, which often has a higher
entropy or a smaller maximum probability. The distillation loss on $U_{in}$ is
also often higher than that of $U_{out}$, suggesting the model focuses more on
those from $U_{in}$ during training. However, there is still a good amount of
data from $U_{out}$ having a high maximum probability, which has a negative
impact for pseudo-label methods.

###  A.6 Implementation details of FixMatch

For FixMatch, we used the official Tensorflow code and a PyTorch re-
implementation for our experiments. The PyTorch version did reproduce the
results on CIFAR-10 with 4000 labels (95.68% vs 95.74% reported in the paper).
We found the optimization details such as learning rate, batch size, and
number of epochs to be crucial for FixMatch. Due to the limitation of our
resources, we can only use a batch size of 64 for labeled data (and 320 for
unlabeled data), where the original paper used a batch size of 1024 (and 5120
for unlabeled data). Since there is small discrepancy between the two
implementations, we reported the best result among the two for each setting:
Tensorflow version for training from scratch and PyTorch version when using
expert models.

###  A.7 Value for computing

Among the SSL methods, Pseudo-Label requires the least amount of computation,
but it does not uniformly lead to improvements in our benchmark. Curriculum
Pseudo-Label trains a model several times (six in our implementation), hence
is more expensive, though the performance saturates after the first few
iterations. FixMatch requires more training epochs and is the most time-
consuming comparing to other SSL methods, but the performance is the best when
having expert model with in-class unlabeled data only. Self-training only
needs two rounds of training, one for training the teacher model and one for
the student. However, it is often the best and is more robust to out-of-class
data.

## References

  * [1] 2018 FGVCx Fungi Classification Challenge.  https://github.com/visipedia/fgvcx_fungi_comp.
  * [2] Ben Athiwaratkun, Marc Finzi, Pavel Izmailov, and Andrew Gordon Wilson.  There are many consistent explanations of unlabeled data: Why you should average.  ICLR, 2019.
  * [3] Philip Bachman, Ouais Alsharif, and Doina Precup.  Learning with pseudo-ensembles.  In NeurIPS, 2014.
  * [4] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston.  Curriculum learning.  In ICML, 2009.
  * [5] David Berthelot, Nicholas Carlini, Ekin D Cubuk, Alex Kurakin, Kihyuk Sohn, Han Zhang, and Colin Raffel.  Remixmatch: Semi-supervised learning with distribution alignment and augmentation anchoring.  ICLR, 2020.
  * [6] David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel.  Mixmatch: A holistic approach to semi-supervised learning.  In NeurIPS, 2019.
  * [7] Cristian Buciluǎ, Rich Caruana, and Alexandru Niculescu-Mizil.  Model compression.  In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 535–541, 2006.
  * [8] Paola Cascante-Bonilla, Fuwen Tan, Yanjun Qi, and Vicente Ordonez.  Curriculum labeling: Self-paced pseudo-labeling for semi-supervised learning.  AAAI, 2021.
  * [9] Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey Hinton.  Big self-supervised models are strong semi-supervised learners.  NeurIPS, 2020.
  * [10] Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He.  Improved baselines with momentum contrastive learning.  arXiv preprint arXiv:2003.04297, 2020.
  * [11] Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le.  Randaugment: Practical automated data augmentation with a reduced search space.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 702–703, 2020.
  * [12] Terrance DeVries and Graham W Taylor.  Improved regularization of convolutional neural networks with cutout.  arXiv preprint arXiv:1708.04552, 2017.
  * [13] Tommaso Furlanello, Zachary C Lipton, Michael Tschannen, Laurent Itti, and Anima Anandkumar.  Born again neural networks.  ICML, 2018.
  * [14] Spyros Gidaris, Praveer Singh, and Nikos Komodakis.  Unsupervised representation learning by predicting image rotations.  In ICLR, 2018.
  * [15] Yves Grandvalet and Yoshua Bengio.  Semi-supervised learning by entropy minimization.  In NeurIPS, 2005.
  * [16] Saurabh Gupta, Judy Hoffman, and Jitendra Malik.  Cross modal distillation for supervision transfer.  In CVPR, 2016.
  * [17] Guy Hacohen and Daphna Weinshall.  On the power of curriculum learning in training deep networks.  ICML, 2019.
  * [18] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning.  In CVPR, 2020.
  * [19] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Identity mappings in deep residual networks.  In European conference on computer vision, pages 630–645. Springer, 2016.
  * [20] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  arXiv preprint arXiv:1503.02531, 2015.
  * [21] R Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildon, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio.  Learning deep representations by mutual information estimation and maximization.  In ICLR, 2019.
  * [22] Simon Kornblith, Jonathon Shlens, and Quoc V Le.  Do better imagenet models transfer better?  In CVPR, 2019.
  * [23] Chia-Wen Kuo, Chih-Yao Ma, Jia-Bin Huang, and Zsolt Kira.  Featmatch: Feature-based augmentation for semi-supervised learning.  ECCV, 2020.
  * [24] Samuli Laine and Timo Aila.  Temporal ensembling for semi-supervised learning.  ICLR, 2017.
  * [25] Dong-Hyun Lee.  Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks.  In Workshop on challenges in representation learning, ICML, 2013\.
  * [26] Ilya Loshchilov and Frank Hutter.  Sgdr: Stochastic gradient descent with warm restarts.  arXiv preprint arXiv:1608.03983, 2016.
  * [27] Geoffrey J McLachlan.  Iterative reclassification procedure for constructing an asymptotically optimal rule of allocation in discriminant analysis.  Journal of the American Statistical Association, 70(350):365–369, 1975.
  * [28] Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii.  Virtual adversarial training: a regularization method for supervised and semi-supervised learning.  IEEE transactions on pattern analysis and machine intelligence, 41(8):1979–1993, 2018.
  * [29] Mehdi Noroozi and Paolo Favaro.  Unsupervised learning of visual representations by solving jigsaw puzzles.  In ECCV, 2016.
  * [30] Avital Oliver, Augustus Odena, Colin A Raffel, Ekin Dogus Cubuk, and Ian Goodfellow.  Realistic evaluation of deep semi-supervised learning algorithms.  In NeurIPS, 2018.
  * [31] Chapelle Olivier, Scholkopf Bernhard, and Zien Alexander.  Semi-supervised learning.  20(3):542–542, 2006.
  * [32] Aaron van den Oord, Yazhe Li, and Oriol Vinyals.  Representation learning with contrastive predictive coding.  arXiv preprint arXiv:1807.03748, 2018.
  * [33] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  In NeurIPS, 2019.
  * [34] Antti Rasmus, Mathias Berglund, Mikko Honkala, Harri Valpola, and Tapani Raiko.  Semi-supervised learning with ladder networks.  In NeurIPS, 2015.
  * [35] Sylvestre-Alvise Rebuffi, Sebastien Ehrhardt, Kai Han, Andrea Vedaldi, and Andrew Zisserman.  Semi-supervised learning with scarce annotations.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 762–763, 2020.
  * [36] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.  ImageNet Large Scale Visual Recognition Challenge.  International Journal of Computer Vision (IJCV), 115(3):211–252, 2015.
  * [37] Mehdi Sajjadi, Mehran Javanmardi, and Tolga Tasdizen.  Regularization with stochastic transformations and perturbations for deep semi-supervised learning.  In NeurIPS, 2016.
  * [38] H Scudder.  Probability of error of some adaptive pattern-recognition machines.  IEEE Transactions on Information Theory, 11(3):363–371, 1965.
  * [39] Kihyuk Sohn, David Berthelot, Chun-Liang Li, Zizhao Zhang, Nicholas Carlini, Ekin D Cubuk, Alex Kurakin, Han Zhang, and Colin Raffel.  Fixmatch: Simplifying semi-supervised learning with consistency and confidence.  In NeurIPS, 2020.
  * [40] Jong-Chyi Su and Subhransu Maji.  Adapting models to signal degradation using distillation.  In BMVC, 2017.
  * [41] Jong-Chyi Su and Subhransu Maji.  The semi-supervised inaturalist-aves challenge at fgvc7 workshop, 2021\.
  * [42] Jong-Chyi Su, Subhransu Maji, and Bharath Hariharan.  When does self-supervision improve few-shot learning?  In ECCV, 2020.
  * [43] Antti Tarvainen and Harri Valpola.  Weight-averaged, consistency targets improve semi-supervised deep learning results.  CoRR,, vol. abs/1703, 2017, 1780.
  * [44] Yonglong Tian, Dilip Krishnan, and Phillip Isola.  Contrastive representation distillation.  ICLR, 2020.
  * [45] Jesper E Van Engelen and Holger H Hoos.  A survey on semi-supervised learning.  Machine Learning, 109(2):373–440, 2020.
  * [46] Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alex Shepard, Hartwig Adam, Pietro Perona, and Serge Belongie.  The inaturalist species classification and detection dataset.  In CVPR, 2018.
  * [47] Vikas Verma, Alex Lamb, Juho Kannala, Yoshua Bengio, and David Lopez-Paz.  Interpolation consistency training for semi-supervised learning.  In International Joint Conference on Artificial Intelligence, 2019\.
  * [48] C. Wah, S. Branson, P. Welinder, P. Perona, and S. Belongie.  The Caltech-UCSD Birds-200-2011 Dataset.  Technical Report CNS-TR-2011-001, California Institute of Technology, 2011\.
  * [49] Bram Wallace and Bharath Hariharan.  Extending and analyzing self-supervised learning across domains.  In ECCV, 2020.
  * [50] Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin.  Unsupervised feature learning via non-parametric instance discrimination.  In CVPR, 2018.
  * [51] Qizhe Xie, Zihang Dai, Eduard Hovy, Minh-Thang Luong, and Quoc V Le.  Unsupervised data augmentation for consistency training.  NeurIPS, 2020.
  * [52] Qizhe Xie, Minh-Thang Luong, Eduard Hovy, and Quoc V. Le.  Self-training with noisy student improves imagenet classification.  In CVPR, 2020.
  * [53] I Zeki Yalniz, Hervé Jégou, Kan Chen, Manohar Paluri, and Dhruv Mahajan.  Billion-scale semi-supervised learning for image classification.  arXiv preprint arXiv:1905.00546, 2019.
  * [54] Xiaohua Zhai, Avital Oliver, Alexander Kolesnikov, and Lucas Beyer.  S4L: Self-supervised semi-supervised learning.  ICCV, 2019.
  * [55] Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz.  mixup: Beyond empirical risk minimization.  In ICLR, 2018.
  * [56] Xiaojin Zhu and Andrew B Goldberg.  Introduction to semi-supervised learning.  Synthesis lectures on artificial intelligence and machine learning, 3(1):1–130, 2009.
  * [57] Xiaojin Jerry Zhu.  Semi-supervised learning literature survey.  Technical report, University of Wisconsin-Madison Department of Computer Sciences, 2005.
  * [58] Barret Zoph, Golnaz Ghiasi, Tsung-Yi Lin, Yin Cui, Hanxiao Liu, Ekin D Cubuk, and Quoc V Le.  Rethinking pre-training and self-training.  NeurIPS, 2020.


11institutetext: Indian Institute of Science Education and Research Bhopal
11email<EMAIL_ADDRESS>
22institutetext: Indian Institute of Technolgy Gandhinagar
22email<EMAIL_ADDRESS>
# The Frobenius Problem for the Proth Numbers

Pranjal Srivastava 11 Dhara Thakkar 22

###### Abstract

Let $n$ be a positive integer greater than $2$. We define the Proth numerical
semigroup, $P_{k}(n)$, generated by $\\{k2^{n+i}+1\,\mid\,i\in\mathbb{N}\\}$,
where $k$ is an odd positive number and $k<2^{n}$. In this paper, we introduce
the Frobenius problem for the Proth numerical semigroup $P_{k}(n)$ and give
formulas for the embedding dimension of $P_{k}(n)$. We solve the Frobenius
problem for $P_{k}(n)$ by giving a closed formula for the Frobenius number.
Moreover, we show that $P_{k}(n)$ has an interesting property such as being
Wilf.

###### Keywords:

Combinatorial techniques Frobenius problem Proth Number Numerical semigroup
Apéry Set pseudo-Frobenius number type Wilf’s conjecture

##  1 Introduction

The mathematician Ferdinand Frobenius defines the problem that asks to find
the largest integer that is not expressible as a non-negative integer linear
combination of elements of $L$, where $L$ is a set of $m$ coprime positive
integers.

The Frobenius problem is defined as follows: Given a set
$L=\\{l_{1},l_{2},...,l_{m}\\}$ of coprime positive integers and $l_{i}\geq
2$, find the largest natural number that is not expressible as a non-negative
linear combination of $l_{1},l_{2},...,l_{m}$. It is also known as the money
exchange or coin exchange problem in number theory. In literature, the
connection between graph theory, theory of computer science and Frobenius
problem has been developed (see [10, 11, 15, 14]). This is because the
Frobenius problem has attracted mathematicians as well as computer scientists
since the $19$-th century (see [3], Chapter 1 in [6], Problem C7 in [9],
[28]).

For the special case e.g., $m=2$, the explicit formula to find the Frobenius
number is known, it is $l_{1}l_{2}-l_{1}-l_{2}$ proved in [26]. In addition to
that, for the case $m=3$, semi-explicit formula is known to find the Frobenius
number [17]. Moreover, Rödseth [24], Selmer [25] and Beyer [4] have developed
algorithms to solve the Frobenius problem in the case $m=3$. In 1996, Ramírez-
Alfonsín showed that the Frobenius problem for variable $m$ is NP-hard [16].

The Frobenius problem has been studied for several special cases, e.g.,
numbers in a geometric sequence, arithmetic sequence, Pythagorean triples,
three consecutive squares or cubes [29, 30, 7, 13]. Moreover, the Frobenius
problem is defined on some special structure like Numerical semigroup (see the
definition below).

Let $\mathbb{N}$ and $\mathbb{Z}$ be the set of non-negative integers and set
of integers, respectively. A subset $S$ of $\mathbb{N}$ containing $0$ is a
_numerical semigroup_ if $S$ is closed under addition and has a finite
complement in $\mathbb{N}$. If $S$ is a numerical semigroup and $S=\langle
B\rangle$, then we call $B$, a system of generators of $S$. A system of
generators $B$ of $S$ is minimal if no proper subset of $B$ generates $S$. In
[18] Rosales et al. proved that every numerical semigroup admits a unique
minimal system of generators and such a system is finite. The cardinality of a
minimal system of generators of $S$ is called the _embedding dimension_ of $S$
denoted by $\mathrm{e}(S)$.

The Frobenius number of a numerical semigroup
$S=\langle\\{a_{1},a_{2},\dots,a_{n}\\}\rangle$ (denoted by $\mathrm{F}(S)$)
is the greatest integer that cannot be expressed as a sum
$\sum\limits_{i=1}^{n}t_{i}a_{i}$, where $t_{1},\dots,t_{n}\in\mathbb{N}$ [18,
2].

To solve the Frobenius problem for numerical semigroups, several methods were
introduced, e.g., see [5, 19, 18, 20]. In particular, in recent articles, the
method of computing the Apéry set (see Definition 1) and deduce the Frobenius
number using the Apéry set has been presented. In literature, there exists a
large list of publications devoted to solve the Frobenius problem for special
classes of numerical semigroup, including the Frobenius problem for Fibonacci
numerical semigroup [12], Mersenne numerical semigroup [21], Thabit numerical
semigroup [22] and repunit numerical semigroup [23]. We note that the study of
the Frobenius number for the mentioned numerical semigroups has been inspired
by special primes such as Fibonacci, Mersenne, Thabit and repunit primes. In
this paper, we introduce Proth numerical semigroup motivated by the Proth
number. The main aim of this paper is to study the Proth numerical semigroup
and its invariants like embedding dimension, Frobenius number, etc.

In number theory, the _Proth number_ (named in honor of the mathematician
François Proth) is a natural number of the form $k2^{n}+1$, where $n$ and $k$
are positive numbers and $k<2^{n}$ is an odd number. We say that a Proth
number is a _Proth prime_ if it is prime.

A numerical semigroup $S$ is the _Proth numerical semigroup_ if
$n\in\mathbb{N}$ such that
$S=\langle\\{k2^{n+i}+1\,\mid\,i\in\mathbb{N}\\}\rangle$, where $n$ and $k$
are positive numbers and $k<2^{n}$ is an odd number. We denote by $P_{k}(n)$
the numerical semigroup
$\langle\\{k2^{n+i}+1\,\mid\,i\in\mathbb{N}\\}\rangle$. It is easy to see that
when $k=1$ the Proth numerical semigroup is the Cunningham numerical semigroup
[27]. Hence, we can assume that $2^{r}<k<2^{r+1}$ for some $r$.

In this paper, we first prove that $\mathrm{e}(P_{k}(n))$ is $n+r+1$ where
$2^{r}<k<2^{r+1}$. Later, we find the Frobenius number of the Proth numerical
semigroup. More formally, we prove the following theorem.

###### Theorem 1.1

Let $n>2$ be a positive integer. Then
$\mathrm{F}(P_{2^{r}+1}(n))=2s_{1}+s_{n}+s_{n+r}-s_{0}$, where
$s_{i}=k2^{n+i}+1$ for $i\in\mathbb{N}$.

Let $S$ be a numerical semigroup. An integer $x$ is a _pseudo-Frobenius
number_ of $S$ if $x\in\mathbb{Z}\setminus S$ and $x+s\in S$ for all $s\in
S\setminus\\{0\\}$. The set of pseudo-Frobenius numbers of $S$ is denoted by
$\mathrm{PF}(S)$, and the cardinality of the set $\mathrm{PF}(S)$ is called
the _type_ of $S$ denoted by $\mathrm{t}(S)$ [18, 2].

We find the set of pseudo-Frobenius numbers of the Proth numerical semigroup
$P_{2^{r}+1}(n)$ and prove that its type is $n+r-1$.

In the context of a numerical semigroup, it is reasonable to study the
problems that connect the Frobenius number and other invariants of a numerical
semigroup. One such problem posed by Wilf (known as Wilf’s conjecture) in [31]
is as follows: Let $S$ be a numerical semigroup and $\nu(S)=|\\{s\in
S\,\mid\,s\leq\mathrm{F}(S)\\}|$, is it true that $\mathrm{F}(S)+1\leq
e(S)\nu(S)$, where $e(S)$ is the embedding dimension and $\mathrm{F}(S)$ is
the Frobenius number of $S$? Note that the numerical semigroups that satisfy
Wilf’s conjecture are called Wilf.

The conjecture is still open; in spite of it, an affirmative answer has been
given for a few special classes of a numerical semigroup. In this paper, we
prove that the Proth numerical semigroup $P_{2^{r}+1}(n)$ supports Wilf’s
conjecture.

This paper is an attempt to understand the Frobenius problem and Wilf
conjecture for arbitrary embedding dimension through the Proth numerical
semigroup. Our approach was inspired by the ideas discussed in [21, 22].
However, it is worth noting that our techniques to find the Apéry set of the
Proth numerical semigroups differ from the existing ones [21, 22].

The reader not familiarized with the study of numerical semigroup and the
terminologies like embedding dimension, pseudo-Frobenius numbers, type, etc.,
can refer to the literature [18, 2].

##  2 The Embedding Dimension

We begin this section by proving that $P_{k}(n)$ is a numerical semigroup.
Later, we prove that the embedding dimension of $P_{k}(n)$ is $n+r+1$. Some of
the techniques used in this section are introduced earlier see, e.g., [21, 22,
27].

###### Lemma 1

(Lemma 2.1 in [18]) Let $S$ be a nonempty subset of $\mathbb{N}$. Then
$\langle S\rangle$ is a numerical semigroup if and only if
$\mathrm{gcd}(S)=1$.

###### Theorem 2.1

Let $n>2$ be an integer, then $P_{k}(n)$ is a numerical semigroup.

###### Proof

It is clear that $P_{k}(n)\subseteq\mathbb{N}$ is closed under addition and
contains zero. Note that from Lemma 1 it is enough to show that
$\mathrm{gcd}(P_{k}(n))=1$. Let $k2^{n}+1$, $k2^{n+1}+1\in P_{k}(n)$. Then
$\mathrm{gcd}(k2^{n}+1,k2^{n+1}+1)=\mathrm{gcd}(k2^{n}+1,k2^{n+1}-k2^{n})=\mathrm{gcd}(k2^{n}+1,k2^{n})=1$.
Therefore, $P_{k}(n)$ is a numerical semigroup. ∎

Next we give the minimal system of generators of the Proth numerical
semigroup. To this purpose, we need some preliminary results.

###### Lemma 2

(Lemma 2.1 in [27]) Let $S$ be a numerical semigroup generated by a non-empty
set $M$ of positive integers. Then the following conditions are equivalent:

  1. (i)

$2m-1\in S$ for all $m\in M$;

  2. (ii)

$2s-1\in S$ for all $s\in S\setminus\\{0\\}$.

###### Theorem 2.2

Let $n>2$ be an integer, then
$P_{k}(n)=\langle\\{k2^{n+i}+1\,\mid\,i=0,\dots,n+r\\}\rangle$.

###### Proof

Let $P=\langle\\{k2^{n+i}+1\,\mid\,i\in\\{0,1,\dots,n+r\\}\big{\\}}\rangle$.
It is clear that $P\subseteq P_{k}(n)$. To prove the other direction it is
enough to prove that $k2^{n+i}+1\in P$ for all $i\in\mathbb{N}$. Let
$i\in\\{0,1,\dots,n+r-1\\}$, then $2(k2^{n+i}+1)-1=k2^{n+i+1}+1\in P$. For
$i=n+r$,
$2(k2^{n+n+r}+1)-1=((k-2^{r})2^{n+1}+3)(k2^{n}+1)+((2^{r+1}-k)2^{n}-2)(k2^{n+1}+1)\in
P$. From Lemma 2, we get $2s-1\in P$ for all $s\in P\setminus\\{0\\}$. By
induction, we can deduce that $k2^{n+i}+1\in P$ for all $i\geq n+r+1$ and
hence $P_{k}(n)=\langle\\{k2^{n+i}+1\,\mid\,i=0,\dots,n+r\\}\rangle$. ∎

Note that, Theorem 2.2 tells us that $\\{k2^{n+i}+1\,\mid\,i=0,\dots,n+r\\}$
is a system of generators of $P_{k}(n)$.

###### Lemma 3

Let $n>2$ be an integer, then
$k2^{n+n+r}+1\notin\langle\\{k2^{n+i}+1\,\mid\,i\in\\{0,1,\dots,n+r-1\\}\big{\\}}\rangle$.

###### Proof

Assume to the contrary that there exists
$a_{0},a_{1},\dots,a_{n+r-1}\in\mathbb{N}$ such that

$\displaystyle k2^{n+n+r}+1=$
$\displaystyle\sum\limits_{i=0}^{n+r-1}a_{i}(k2^{n+i}+1)$ $\displaystyle=$
$\displaystyle
k2^{n}\Big{(}\sum_{i=0}^{n+r-1}2^{i}a_{i}\Big{)}+\sum\limits_{i=0}^{n+r-1}a_{i}.$

Hence, $\sum_{i=0}^{n+r-1}a_{i}=1(\mathrm{mod}\,k2^{n})$ and we get,
$\sum_{i=0}^{n+r-1}a_{i}=tk2^{n}+1$ for some $t\in\mathbb{N}$. Observe that
$t\neq 0$. Thus, $\sum_{i=0}^{n+r-1}a_{i}\geq k2^{n}+1$. Therefore,
$k2^{n+n+r}+1=\sum\limits_{i=0}^{n+r-1}a_{i}(k2^{n+i}+1)\geq(\sum_{i=0}^{n+r-1}a_{i})(k2^{n}+1)\geq(k2^{n}+1)^{2}$.
Since $2^{r}<k$ we get

$\displaystyle 2^{r+n}<2^{n}k<2^{n}k+2$ $\displaystyle\Rightarrow
k2^{r+n+n}<k^{2}2^{2n}+2k2^{n}$ $\displaystyle\Rightarrow
k2^{r+n+n}+1<k^{2}2^{2n}+2k2^{n}+1$ $\displaystyle\Rightarrow
k2^{n+n+r}+1<(k2^{n}+1)^{2}.$

Hence, $k2^{n+n+r}+1\geq(k2^{n}+1)^{2}>k2^{n+n+r}+1$, which is a
contradiction. Therefore,
$k2^{n+n+r}+1\notin\big{\langle}\big{\\{}k2^{n+i}+1\,\mid\,i\in\\{0,1,\dots,n+r-1\\}\big{\\}}\big{\rangle}$.
∎

###### Theorem 2.3

Let $n>2$ be an integer and let $P_{k}(n)$ be the Proth numerical semigroup
associated to $n$, then $\mathrm{e}(P_{k}(n))=n+r+1$. Moreover,
$\\{k2^{n+i}+1\,\mid\,i\in\\{0,1,\dots,n+r\\}\big{\\}}$ is the minimal system
of generators of $P_{k}(n)$.

###### Proof

By Theorem 2.2, we know that $\\{k2^{n+i}+1\,\mid\,i\in 0,1,\dots,n+r\\}$ is a
system of generator for $P_{k}(n)$. Suppose that it is not minimal system of
generators of $P_{k}(n)$. Then there exists $l\in\\{1,2,\dots,n+r-1\\}$ such
that $k2^{n+l}+1\in\langle k2^{n+i}+1\,\mid\,i\in\\{0,1,\dots,l-1\\}\rangle$.
Let $T=\langle k2^{n+i}+1\,\mid\,i\in\\{0,1,\dots,l-1\\}\rangle$. If
$i\in\\{0,1,\dots,l-2\\}$, then $2(k2^{n+i}+1)-1=k2^{n+i+1}+1\in T$ and
$2(k2^{n+l-1}+1)-1=k2^{n+l}+1\in T$. From Lemma 2, we have $2t-1\in T$ for all
$t\in T\setminus\\{0\\}$. Hence, by induction we can obtain that
$k2^{n+i}+1\in T$ for all $i\geq l$, which is a contradiction as
$k2^{n+n+r}+1\notin T$ from Lemma 3. Therefore,
$\\{k2^{n+i}+1\,\mid\,i\in\\{0,1,\dots,n+r\\}\big{\\}}$ is the minimal system
of generators of $P_{k}(n)$ and $\mathrm{e}(P_{k}(n))=n+r+1$. ∎

##  3 The Apéry Set

In this section, we study the notion of Apéry set and give the explicit
description of the elements of the Apéry set of the Proth numerical semigroup
$P_{2^{r}+1}(n)$ for all $r\geq 1$. We denote by $s_{i}$ the element
$k2^{n+i}+1$ for all $i\in\mathbb{N}$. Thus, with this notation,
$\\{s_{0},s_{1},...,s_{n+r}\\}$ is the minimal system of generators of
$P_{k}(n)$.

###### Definition 1

[1, 18] Let $S$ be a numerical semigroup and $n\in S\setminus\\{0\\}$. The
Apéry set of $S$ with respect to $n$ is $\mathrm{Ap}(S,n)=\\{s\in
S\,\mid\,s-n\notin S\\}$.

It is clear from the following lemma that $|\mathrm{Ap}(S,n)|=n$.

###### Lemma 4

(Lemma 2.4 in [18]) Let $S$ be a numerical semigroup and let $n$ be a nonzero
element of $S$. Then $\mathrm{Ap}(S,n)=\\{w(0),w(1),\dots,w(n-1)\\}$, where
$w(i)$ is the least element of $S$ congruent with $i$ modulo $n$, for all
$i\in\\{0,\dots,n-1\\}$.

Our next goal is to describe the elements of $\mathrm{Ap}(P_{k}(n),s_{0})$.

######  Lemma 5 ()

Let $n>2$ be an integer. Then:

  1. (1)

if $0<i\leq j<n+r$ then $s_{i}+2s_{j}=2s_{i-1}+s_{j+1}$;

  2. (2)

if $0<i\leq n+r$ then $s_{i}+2s_{n+r}=2s_{i-1}+\alpha s_{0}+\beta s_{1}$,
where $\alpha=(k-2^{r})2^{n+1}+3$ and $\beta=(2^{r+1}-k)2^{n}-2$.

###### Proof

$(1)$ If $0<i\leq j<n+r$ then we have

$\displaystyle s_{i}+2s_{j}=$ $\displaystyle(k2^{n+i}+1)+2(k2^{n+j}+1)$
$\displaystyle=$ $\displaystyle
2(k2^{n+i-1}+1)+(k2^{n+j+1}+1)=2s_{i-1}+s_{j+1}.$

$(2)$ If $0<i\leq n+r$ then we get

$\displaystyle s_{i}+2s_{n+r}=$ $\displaystyle(k2^{n+i}+1)+2(k2^{n+n+r}+1)$
$\displaystyle=$ $\displaystyle 2(k2^{n+i-1}+1)+k2^{2n+r+1}+1$
$\displaystyle=$ $\displaystyle
2s_{i-1}+\alpha(k2^{n}+1)+\beta(k2^{n+1}+1)=2s_{i-1}+\alpha s_{0}+\beta
s_{1},$

where $\alpha=(k-2^{r})2^{n+1}+3,\beta=(2^{r+1}-k)2^{n}-2$. ∎

Let $P(r,n)$ denotes the set of all $n+r$-tuple $(a_{1},\dots,a_{n+r})$ that
satisfies the following conditions:

  1. 1.

for every $i\in\\{1,\dots,n+r\\}$, $a_{i}\in\\{0,1,2\\}$;

  2. 2.

if $a_{j}=2$ for some $j=2,\dots,n+r$ then $a_{i}=0$ for $i<j$.

###### Lemma 6

(Lemma 3.3 in [8]) The cardinality of $P(r,n)$ is equal to $2^{n+r+1}-1$.

###### Lemma 7

Let $n>2$ be an integer and let $P_{2^{r}+1}(n)$ be the Proth numerical
semigroup minimally generated by $\\{s_{0},s_{1},\dots,s_{n+r}\\}$. If
$s\in\mathrm{Ap}(P_{2^{r}+1}(n),s_{0})$ then there exist
$(a_{1},\dots,a_{n+r})\in P(r,n)$ such that
$s=a_{1}s_{1}+\dots+a_{n+r}s_{n+r}$.

###### Proof

Let $s\in\mathrm{Ap}(P_{2^{r}+1}(n),s_{0})$. We prove the result of lemma
using induction on $s$. When $s=0$ then result follows trivially. Assume that
$s>0$ and $j$ be the smallest element from $\\{0,1,\dots,n+r\\}$ such that
$s-s_{j}\in P_{2^{r}+1}(n)$. Since $s\in\mathrm{Ap}(P_{2^{r}+1}(n),s_{0})$ we
have $j\neq 0$ and $s-s_{j}\in\mathrm{Ap}(P_{2^{r}+1}(n),s_{0})$. Now from
induction hypothesis there exist $(a_{1},\dots,a_{n+r})\in P(r,n)$ such that
$s-s_{j}=a_{1}s_{1}+a_{2}s_{2}+\dots+a_{n+r}s_{n+r}$, hence
$s=a_{1}s_{1}+a_{2}s_{2}+\dots+(a_{j}+1)s_{j}+\dots+a_{n+r}s_{n+r}$. Note
that, to conclude the proof it suffices to prove that
$(a_{1},\dots,a_{j}+1,\dots,a_{n+r})\in P(r,n)$.

(1) To prove $(a_{1},a_{2},\dots,a_{j}+1,\dots,a_{n+r})\in\\{0,1,2\\}^{n+r}$,
it is enough to show that $a_{j}+1\neq 3$. If $a_{j}+1=3$ then from Lemma 5,

  * (i)

for $j<n+r$, we have $s_{j}+2s_{j}=2s_{j-1}+s_{j+1}$. This implies that,
$s-s_{j-1}=a_{1}s_{1}+\dots+s_{j-1}+(a_{j+1}+1)s_{j+1}+\dots+a_{n+r}s_{n+r}$.

  * (ii)

for $j=n+r$, we have, $s_{j}+2s_{j}=2s_{j-1}+\alpha s_{0}+\beta s_{1}$. This
implies that,
$s-s_{j-1}=\alpha
s_{0}+(a_{1}+\beta)s_{1}+a_{2}s_{2}+\dots+(a_{n+r-1}+1)s_{n+r-1}$.

In both the cases, we get $s-s_{j-1}\in P_{2^{r}+1}$, which is a contradiction
to the minimality of $j$. Hence, $a_{j}+1\neq 3$.

(2) From the minimality of $j$, we obtain that $a_{i}=0$ for all $1\leq i<j$.
Now assume that there exist $l>j$ such that $a_{l}=2$, then again from Lemma
5, we have

  * (i)

for $l<n+r$, we have $s_{j}+2s_{l}=2s_{j-1}+s_{l+1}$;

  * (ii)

for $l=n+r$, we have, $s_{j}+2s_{l}=2s_{j-1}+\alpha s_{0}+\beta s_{1}$.

Again by the same argument as in (1), we have $s-s_{j-1}\in P_{2^{r}+1}$,
which contradict the minimality of $j$.

Therefore, $(a_{1},\dots,a_{j}+1,\dots,a_{n+r})\in P(r,n)$. ∎

It follows from Lemma 7 that
$\mathrm{Ap}(P_{2^{r}+1}(n),s_{0})\subseteq\\{a_{1}s_{1}+\dots+a_{n+r}s_{n+r}\,\mid\,(a_{1},\dots,a_{n+r})\in
P(r,n)\\}$.

The next remark tells that the equality in the above expression does not hold
in general.

###### Remark 1

If possible suppose that,
$\mathrm{Ap}(P_{2^{r}+1}(n),s_{0})=\\{a_{1}s_{1}+\dots+a_{n+r}s_{n+r}\mid(a_{1},\dots,a_{n+r})\in
P(r,n)\\}$. Then
$|\mathrm{Ap}(P_{2^{r}+1}(n),s_{0})|=|\\{a_{1}s_{1}+\dots+a_{n+r}s_{n+r}\,\mid\,(a_{1},\dots,a_{n+r})\in
P(r,n)\\}|=2^{n+r+1}-1\neq s_{0}$.

Thus, it remains to find the elements of the set
$\\{a_{1}s_{1}+\dots+a_{n+r}s_{n+r}\,\mid\,(a_{1},\dots,a_{n+r})\in P(r,n)\\}$
which belongs to $\mathrm{Ap}(P_{2^{r}+1}(n),s_{0})$. To do so, we first
define the following sets:

$F_{1}=\big{\\{}a_{1}s_{1}+\dots+a_{n+r-1}s_{n+r-1}+s_{n+r}\,\mid\,a_{i}\in\\{0,1,2\\}\text{
for }1\leq i\leq n+r-2,\,a_{n+r-1}\in\\{1,2\\}\text{ and if }\,a_{j}=2\,\text{
for some }\,j\text{ then }a_{i}=0\text{ for }i<j\big{\\}}$; and

$F_{2}=\Big{(}\bigcup\limits_{l=0}^{r-2}E_{l}\cup\\{2s_{n+r}\\}\Big{)}\mathbin{\big{\backslash}}\\{s_{1}+s_{n}+s_{n+r},\,2s_{1}+s_{n}+s_{n+r},\,s_{n}+s_{n+r}\\}$,
where
$E_{l}=\big{\\{}a_{1}s_{1}+\dots+a_{n+l}s_{n+l}+s_{n+r}\,\mid\,a_{i}\in\\{0,1,2\\}\text{
for }1\leq i\leq n+l-1,\,a_{n+l}\in\\{1,2\\}\text{ and if }a_{j}=2\text{ then
}a_{i}=0\text{ for }i<j\big{\\}}$. Take $F=F_{1}\cup F_{2}$.

######  Lemma 8 ()

Under the standing hypothesis and notation, the following equalities hold.

  1. (a)

$s_{n+l}+s_{n+r}-s_{0}=((2^{n+r}-2^{n+l})+2^{n+1}+4)s_{0}+(2^{n+l}-2^{n}-3)s_{1}$,
for $1\leq l\leq r$;

  2. (b)

$s_{i}+s_{n}+s_{n+r}-s_{0}=((2^{r}+1)2^{n}+2-(2^{i}-4))s_{0}+(2^{i}-4)s_{1}$
for $2\leq i\leq n$;

  3. (c)

$s_{1}+s_{i}+s_{n}+s_{n+r}-s_{0}=((2^{r}+1)2^{n}+2-(2^{i}-4))s_{0}+(2^{i}-3)s_{1}$
for $2\leq i\leq n$;

###### Proof

(a) Let $1\leq l\leq r$. Consider

$\displaystyle(2^{n+r}-2^{n+l}+2^{n+1}+4)s_{0}+(2^{n+l}-2^{n}-3)s_{1}$
$\displaystyle=$
$\displaystyle(2^{n+r}-2^{n+l}+2^{n+1}+4)((2^{r}+1)2^{n}+1)+(2^{n+l}-2^{n}-3)((2^{r}+1)2^{n+1}+1)$
$\displaystyle=$ $\displaystyle(2^{r}+1)2^{n}(2^{n+r}-2^{n+l}+2\cdot
2^{n}+4+2(2^{n+l}-2^{n}-3))+2^{n+r}+2^{n}+1$ $\displaystyle=$
$\displaystyle(2^{r}+1)2^{n}(2^{n+r}+2^{n+l}-2)+2^{n+r}+2^{n}+1$
$\displaystyle=$ $\displaystyle(2^{r}+1)2^{n}(2^{n+r}+2^{n+l}-1)+1$
$\displaystyle=$
$\displaystyle(2^{r}+1)(2^{n+n+r})+1+(2^{r}+1)2^{n+n+l}+1-(2^{r}+1)2^{n}-1$
$\displaystyle=$ $\displaystyle s_{n+r}+s_{n+l}-s_{0}.$

(b) Let $2\leq i\leq n$. Consider

$\displaystyle((2^{r}+1)2^{n}+2-(2^{i}-4))s_{0}+(2^{i}-4)s_{1}$
$\displaystyle=$
$\displaystyle((2^{r}+1)2^{n}+2-(2^{i}-4))((2^{r}+1)2^{n}+1)+(2^{i}-4)((2^{r}+1)2^{n+1}+1)$
$\displaystyle=$ $\displaystyle(2^{r}+1)2^{n}((2^{r}+1)2^{n}+2-2^{i}+4+2\cdot
2^{i}-8)+(2^{r}+1)2^{n}+2$ $\displaystyle=$
$\displaystyle(2^{r}+1)2^{n}((2^{r}+1)2^{n}+2^{i}-2)+(2^{r}+1)2^{n}+2$
$\displaystyle=$ $\displaystyle(2^{r}+1)2^{n}((2^{r}+1)2^{n}+2^{i}-1)+2$
$\displaystyle=$
$\displaystyle(2^{r}+1)2^{n+n+r}+1+(2^{r}+1)2^{n+n}+1+(2^{r}+1)2^{n+i}+1-((2^{r}+1)2^{n}+1)$
$\displaystyle=$ $\displaystyle s_{n+r}+s_{n}+s_{i}-s_{0}.$

(c) Follows from the proof of part (b). ∎

The following lemmas give the explicit description of the elements in the
Apéry set $\mathrm{Ap}(P_{2^{r}+1}(n),s_{0})$.

###### Lemma 9

Let $n>2$ be an integer. Then
$F\,\cap\,\mathrm{Ap}(P_{2^{r}+1}(n),s_{0})=\phi$.

###### Proof

Let $a_{1}s_{1}+\dots+a_{n+r-1}s_{n+r-1}+s_{n+r}\in F_{1}$. From Lemma 8(a),
we have $s_{n+r-1}+s_{n+r}-s_{0}\in P_{2^{r}+1}(n)$. Since
$a_{n+r-1}\in\\{1,2\\}$, we have
$a_{1}s_{1}+\dots+a_{n+r-1}s_{n+r-1}+s_{n+r}-s_{0}=a_{1}s_{1}+\dots+(a_{n+r-1}-1)s_{n+r-1}+s_{n+r-1}+s_{n+r}-s_{0}\in
P_{2^{r}+1}(n)$.

Let $a_{1}s_{1}+\dots+a_{n+l}s_{n+l}+s_{n+r}\in F_{2}$ for $1\leq l\leq r-2$.
From Lemma 8(a), we have $s_{n+l}+s_{n+r}-s_{0}\in P_{2^{r}+1}(n)$. Similar
argument as above implies that
$a_{1}s_{1}+\dots+a_{n+l}s_{n+l}+s_{n+r}-s_{0}\in P_{2^{r}+1}(n)$.

Let $a_{1}s_{1}+\dots+a_{n}s_{n}+s_{n+r}\in F_{2}\,(\text{i.e. }l=0)$. Note
that $a_{i}\neq 0$ for some $i\in\\{2,\dots,n-1\\}$. From Lemma 8(b) and (c),
we have $s_{i}+s_{n}+s_{n+r}-s_{0}\in P_{2^{r}+1}(n)$ and
$s_{1}+s_{i}+s_{n}+s_{n+r}-s_{0}\in P_{2^{r}+1}(n)$. Since $a_{i}\neq 0$ for
$2\leq i\leq n-1$, we have $a_{1}s_{1}+\dots+a_{n}s_{n}+s_{n+r}-s_{0}\in
P_{2^{r}+1}(n)$.

Finally, consider $2s_{n+r}\in F_{2}$. From Lemma 8(a), we have
$2s_{n+r}-s_{0}\in P_{2^{r}+1}(n)$.
Thus, for any element of $F$ say $x$, we have $x-s_{0}\in P_{2^{r}+1}(n)$ and
hence $F\,\cap\,\mathrm{Ap}(P_{2^{r}+1}(n),s_{0})=\phi$. ∎

###### Lemma 10

Under the standing hypothesis and notation, we have $|F|=2^{n+r}-2^{n}-2.$

###### Proof

Consider the set
$L_{11}=\big{\\{}a_{1}s_{1}+\dots+a_{n+r-1}s_{n+r-1}+s_{n+r}\,\mid\,a_{i}\in\\{0,1\\}\text{
for }1\leq i\leq n+r-2\text{ and }a_{n+r-1}=1\big{\\}}$. Clearly,
$|L_{11}|=2^{n+r-2}$. Now we construct a new set $L_{12}$ as follows: Let
$a_{1}s_{1}+\dots+a_{n+r-1}s_{n+r-1}+s_{n+r}\in L_{11}$. Take the least index
$m\in\\{1,2,...,n+r-1\\}$ for which $a_{m}=1$, add an element
$b_{1}s_{1}+\dots+b_{n+r-1}s_{n+r-1}+s_{n+r}$ in $L_{12}$ with $b_{m}=2$ and
$b_{j}=a_{j}$ for all $j\neq m$. Clearly, $|L_{12}|=2^{n+r-2}$. Note that
$F_{1}$ is the disjoint union of $L_{11}$ and $L_{12}$. Hence,
$|F_{1}|=2^{n+r-1}$.

Consider the set
$L_{21}=\big{\\{}a_{1}s_{1}+\dots+a_{n+l}s_{n+l}+s_{n+r}\,\mid\,a_{i}\in\\{0,1\\}\text{
for }1\leq i\leq n+l-1\text{ and }a_{n+l}=1\big{\\}}$. Clearly,
$|L_{21}|=2^{n+l-1}$. Now we construct a new set $L_{22}$ as follows: Let
$a_{1}s_{1}+\dots+a_{n+l}s_{n+l}+s_{n+r}\in L_{21}$. Take the least index $m$
for which $a_{m}=1$, add an element $b_{1}s_{1}+\dots+b_{n+l}s_{n+l}+s_{n+r}$
in $L_{22}$ with $b_{m}=2$ and $b_{j}=a_{j}$ for all $j\neq m$. Clearly,
$|L_{22}|=2^{n+l-1}$. Note that $E_{l}$ is the disjoint union of $L_{21}$ and
$L_{22}$. Hence, $|E_{l}|=2^{n+l}$. Thus we get,
$|F_{2}|=\sum\limits_{l=0}^{r-2}|E_{l}|+1-3=\sum\limits_{l=0}^{r-2}2^{n+l}-2=2^{n+r-1}-2^{n}-2$.
Therefore, $|F|=|F_{1}|+|F_{2}|=2^{n+r-1}+2^{n+r-1}-2^{n}-2=2^{n+r}-2^{n}-2.$
∎

###### Theorem 3.1

Let $n>2$ be an integer. Then

$\mathrm{Ap}(P_{2^{r}+1}(n),s_{0})=\\{a_{1}s_{1}+\dots+a_{n+r}s_{n+r}\,\mid\,(a_{1},\dots,a_{n+r})\in
P(r,n)\\}\setminus F.$

###### Proof

Let
$P^{\prime}(r,n)=\\{a_{1}s_{1}+\dots+a_{n+r}s_{n+r}\,\mid\,(a_{1},\dots,a_{n+r})\in
P(r,n)\\}\setminus F$. Now from Lemma 7 and Lemma 9, it is clear that
$\mathrm{Ap}(P_{2^{r}+1}(n),s_{0})\subseteq P^{\prime}(r,n)$). Note that from
Lemma 6 and Lemma 10, we have

$|P^{\prime}(r,n)|=2^{n+r+1}-1-(2^{n+r}-2^{n}-2)=s_{0}=|\mathrm{Ap}(P_{2^{r}+1}(n),s_{0})|.$

Thus,
$\mathrm{Ap}(P_{2^{r}+1}(n),s_{0})=\\{a_{1}s_{1}+\dots+a_{n+r}s_{n+r}\,\mid\,(a_{1},\dots,a_{n+r})\in
P(r,n)\\}\setminus F$. ∎

##  4 The Frobenius Problem

In this section, we give the formula for the Frobenius number of the Proth
numerical semigroup $P_{2^{r}+1}(n)$ for all $r\geq 1$. We recall Lemma 4 from
Section 3.

Let us begin with some preliminary lemmas.

###### Lemma 11

Let $s\in P_{2^{r}+1}(n)$ such that $s\not\equiv 0(\mathrm{mod}\,s_{0})$, then
$s+1\in P_{2^{r}+1}(n)$. Moreover, $w(i+1)\leq w(i)+1$ for $1\leq i\leq
s_{0}-1$.

###### Proof

Since $s\in P_{2^{r}+1}(n)$, there exist $a_{0},\dots,a_{n+r}\in\mathbb{N}$
such that $s=a_{0}s_{o}+\dots+a_{n+r}s_{n+r}$. If $s\not\equiv
0(\mathrm{mod}\,s_{0})$ then there exist $i\in\\{1,\dots,n+r\\}$ such that
$a_{i}\neq 0$ and we get,
$s+1=a_{0}s_{0}+\dots+(a_{i}-1)s_{i}+\dots+a_{n+r}s_{n+r}+s_{i}+1$.

Now, $s_{i}+1=k2^{n+i}+1+1=2k^{n+i-1}+2=2s_{i-1}$. Hence,
$s+1=a_{0}s_{o}+\dots+(a_{i-1}+2)s_{i-1}+(a_{i}-1)s_{i}+\dots+a_{n+r}s_{n+r}\in
P_{2^{r}+1}(n)$.

Moreover, by definition, $w(i)\not\equiv 0(\mathrm{mod}\,s_{0})$ for $1\leq
i\leq s_{0}-1$. Thus, $w(i)+1\in P_{2^{r}+1}(n)$. Now, $w(i)+1\equiv
i+1(\mathrm{mod}\,s_{0})$. As $w(i+1)$ is the least element of
$P_{2^{r}+1}(n)$ which is congruent with $i+1$ modulo $s_{0}$, we get
$w(i+1)\leq w(i)+1$. ∎

###### Lemma 12

Let $n>2$ be an integer. Then

  1. 1.

$w(2)=s_{1}+s_{n}+s_{n+r}$;

  2. 2.

$w(1)=2s_{1}+s_{n}+s_{n+r}$. Moreover, $w(1)-w(2)=s_{1}$.

###### Proof

(1) Consider

$\displaystyle s_{1}+s_{n}+s_{n+r}-2=$
$\displaystyle(2^{r}+1)2^{n+1}+1+(2^{r}+1)2^{n+n}+1+(2^{r}+1)2^{n+n+r}-1$
$\displaystyle=$ $\displaystyle
2\cdot(2^{r}+1)2^{n}+(2^{r}+1)2^{2n}(2^{r}+1)+1$ $\displaystyle=$
$\displaystyle(2^{r}+1)\cdot 2^{n}+1)^{2}=s_{0}^{2}.$

Therefore, $s_{1}+s_{n}+s_{n+r}\equiv 2(\mathrm{mod}s_{0})$. From Lemma 3.1 we
have, $s_{1}+s_{n}+s_{n+r}\in\mathrm{Ap}(P_{2^{r}+1}(n),s_{0})$. Thus,
$w(2)=s_{1}+s_{n}+s_{n+r}$.

(2) Note that from (1) we have $s_{1}+s_{n}+s_{n+r}-2=s_{0}^{2}$. Now

$\displaystyle 2s_{1}+s_{n}+s_{n+r}-1=$ $\displaystyle
s_{1}+s_{n}+s_{n+r}+2(2^{r}+1)2^{n}+1-1$ $\displaystyle=$ $\displaystyle
s_{1}+s_{n}+s_{n+r}-2+2s_{0}=s_{0}^{2}+2s_{0}.$

Therefore, $2s_{1}+s_{n}+s_{n+r}\equiv 1(\mathrm{mod}s_{0}).$ Again From Lemma
3.1 we have, $2s_{1}+s_{n}+s_{n+r}\in\mathrm{Ap}(P_{2^{r}+1}(n),s_{0})$. Thus,
$w(1)=2s_{1}+s_{n}+s_{n+r}$. Clearly, $w(1)-w(2)=s_{1}.$ ∎

The next Lemma is due to Selmer [25] gives us the relation among the Frobenius
number and Apéry Set.

###### Lemma 13

([25], Proposition 5 in [2]) Let $S$ be a numerical semigroup and let $n$ be a
non-zero element of $S$. Then $\mathrm{F}(S)=\max(\mathrm{Ap}(S,n))-n$.

###### Lemma 14

Under the standing notation, we have

$w(1)=\mathrm{max}(\mathrm{Ap}(P_{2^{r}+1}(n),s_{0})).$

###### Proof

From Lemma 11, $w(i+1)\leq w(i)+1$, for $1\leq i\leq s_{0}-1$. Thus, we get
$w(3)\leq w(2)+1,w(4)\leq w(3)+1\leq w(2)+2$. In general, for $3\leq j\leq
s_{0}-1$, we have $w(j)\leq w(2)+(j-2)$. Since $w(1)-w(2)=s_{1}$, we get
$w(j)\leq w(1)-s_{1}+(j-2)=w(1)-(s_{1}-(j-2))<w(1)$ as $s_{1}-(j-2)>0$.
Therefore, $w(1)\geq w(i)$ for $0\leq i\leq s_{0}-1$ and
$w(1)=\mathrm{max}(\mathrm{Ap}(P_{2^{r}+1}(n),s_{0}))$. ∎

Thus, from Lemma 13 and 14 we obtain the following formula for the Frobenius
number of $P_{2^{r}+1}(n)$.

###### Theorem 4.1

Let $n>2$ be a positive integer. Then
$\mathrm{F}(P_{2^{r}+1}(n))=2s_{1}+s_{n}+s_{n+r}-s_{0}$.

Next we define the genus of a numerical semigroup.

###### Definition 2

_Let $S$ be a numerical semigroup then the set $\mathbb{N}\setminus S$ is
called _set of gaps of $S$_ and its cardinality is said to be _genus of $S$_
denoted by $g(S)$._

###### Remark 2

It is well known that (see Lemma 3 in [2]),
$g(S)\geq\frac{\mathrm{F}(S)+1}{2}$.

###### Corollary 1

Let $n>2$ be a positive integer. Then, $g(P_{2^{r}+1}(n))\geq
k(2^{n+1}+2^{2n-1}+2^{2n+r-1}-2^{n-1})+2$.

##  5 Pseudo-Frobenius Numbers and Type

Our purpose in this section is to give the pseudo-Frobenius set and the
formula for the type of the Proth numerical semigroup $P_{2^{r}+1}(n)$ for all
$r\geq 1$. Let us recall the definition of pseudo-Frobenius numbers.

Let $S$ be a numerical semigroup. An integer $x$ is a _pseudo-Frobenius
number_ of $S$ if $x\in\mathbb{Z}\setminus S$ and $x+s\in S$ for all $s\in
S\setminus\\{0\\}$.

Consider the following relation on the set of integers $\mathbb{Z}$:
$a\leq_{S}b$ if $b-a\in S$. Note that this relation is an order relation i.e.,
it is reflexive, transitive and antisymmetric (see [18]). The next lemma
characterizes pseudo-Frobenius numbers in terms of the Apéry set using the
relation defined above.

###### Lemma 15

(Proposition 2.20 in [18]) Let $S$ be a numerical semigroup and let $n$ be a
nonzero element of $S$. Then

$\mathrm{PF}(S)=\\{w-n\,\mid\,w\in maximals_{\leq S}(\mathrm{Ap}(S,n)\\}.$

###### Remark 3

[22] If $w,w^{\prime}\in\mathrm{Ap}(S,x)$, then $w^{\prime}-w\in S$ if and
only if $w^{\prime}-w\in\mathrm{Ap}(S,x)$. Hence
$maximal_{\leq_{S}}(\mathrm{Ap}(S,x))=\big{\\{}w\in\mathrm{Ap}(S,x)\,\mid\,w^{\prime}-w\notin\mathrm{Ap}(S,x)\setminus\\{0\\}\text{
for all }w^{\prime}\in\mathrm{Ap}(S,x)\big{\\}}$.

Let $n>2$ be an integer. We define the set $X$ as follows:
$X=\\{(a_{1},\dots,a_{n+r})\,\mid\,a_{1}s_{1}+\dots+a_{n+r}s_{n+r}\in F\\}$.
Let us consider $M(n)=P(r,n)\setminus X$. It is clear that maximal elements in
$M(n)$ (with respect to the product order) are
$\bullet(2,1,\dots,1,1,0),\dots,(0,\dots,0,\overset{\begin{subarray}{c}r\\\
\downarrow\end{subarray}}{2},1,\dots,1,0),\dots,(0,\dots,0,2,0)$;
$\bullet(2,1,\dots,\overset{\begin{subarray}{c}n-1\\\
\downarrow\end{subarray}}{1},0,\dots,0,1),\dots,(0,\dots,0,2,\overset{\begin{subarray}{c}n-1\\\
\downarrow\end{subarray}}{1},0,\dots,0,1)$;
$\bullet(0,\dots,0,\overset{\begin{subarray}{c}n-1\\\
\downarrow\end{subarray}}{2},0,\dots,0,1),(2,0,\dots,0,\overset{\begin{subarray}{c}n\\\
\downarrow\end{subarray}}{1},0,\dots,0,1)$.

As a consequence of Theorem 3.1, we get the following lemma.

###### Lemma 16

Under the standing notation, we have

$maximal_{\leq
P_{2^{r}+1}(n)}(\mathrm{Ap}(P_{2^{r}+1}(n),s_{0}))=maximal_{\leq
P_{2^{r}+1}(n)}\big{\\{}\\{2s_{i}+s_{i+1}+\dots+s_{n+r-1}\,\mid\,1\leq i\leq
n+r-1\\}\cup\\{2s_{j}+s_{j+1}+\dots+s_{n-1}+s_{n+r}\,\mid\,1\leq j\leq
n-2\\}\cup\\{2s_{n-1}+s_{n+r},2s_{1}+s_{n}+s_{n+r}\\}\big{\\}}$.

We are now already to give the main result of this section.

######  Theorem 5.1 ()

Let $n>2$ be an integer and let $P_{2^{r}+1}(n)$ be the Proth numerical
semigroup associated to $n$. Then $maximal_{\leq
P_{2^{r}+1}(n)}(\mathrm{Ap}(P_{2^{r}+1}(n),s_{0}))=\\{2s_{i}+s_{i+1}+\dots+s_{n+r-1}\,\mid\,1\leq
i\leq r\\}\cup\\{2s_{j}+s_{j+1}+\dots+s_{n-1}+s_{n+r}\,\mid\,1\leq j\leq
n-2\\}\cup\\{2s_{1}+s_{n}+s_{n+r}\\}$.

###### Proof

Let $i\in\\{r+1,...,n+r-1\\}$, then

$\displaystyle
2s_{i}+s_{i+1}+\cdots+s_{n-1}+s_{n+r}-(2s_{r+i}+s_{r+i+1}+\cdots+s_{n}+s_{n+r-1})$
$\displaystyle=k2^{n+i}+k2^{n+i}(2^{r}-1)+r+k2^{2n+r}+2-(k2^{2n}(2^{r}-1)+r+k2^{n+r+i}+1)$
$\displaystyle=(k2^{2n}+1)=s_{n}.$

Also,
$2s_{1}+s_{n}+s_{n+r}-(2s_{n-1}+s_{n+r})=2s_{1}+k2^{n}+1-2(k2^{n-1}+1)=s_{2}$.

Hence, we get
$2s_{r+i}+s_{r+i+1}+\cdots+s_{n}+s_{n+r-1}\leq_{P_{2^{r}+1}(n)}2s_{i}+s_{i+1}+\cdots+s_{n-1}+s_{n+r}$
for $i\in\\{r+1,...,n+r-1\\}$ and
$2s_{n-1}+s_{n+r}\leq_{P_{2^{r}+1}(n)}2s_{1}+s_{n}+s_{n+r}$. From Lemma 16 we
obtain that $maximal_{\leq
P_{2^{r}+1}(n)}(\mathrm{Ap}(P_{2^{r}+1}(n),s_{0}))=maximal_{\leq
P_{2^{r}+1}(n)}\big{\\{}\\{2s_{i}+s_{i+1}+\dots+s_{n+r-1}\,\mid\,1\leq i\leq
r\\}\cup\\{2s_{j}+s_{j+1}+\dots+s_{n-1}+s_{n+r}\,\mid\,1\leq j\leq
n-2\\}\cup\\{2s_{1}+s_{n}+s_{n+r}\\}\big{\\}}$.

Consider a set $L_{1}=\\{p_{i}=2s_{i}+s_{i+1}+\dots+s_{n+r-1}\,\mid\,1\leq
i\leq r\\}$ and
$L_{2}=\\{q_{j}=2s_{j}+s_{j+1}+\dots+s_{n-1}+s_{n+r}\,\mid\,1\leq j\leq
n-2\\}$. Take $L=L_{1}\cup L_{2}\cup\\{2s_{1}+s_{n}+s_{n+1}\\}$. We show that
$L=maximal_{\leq P_{2^{r}+1}(n)}(\mathrm{Ap}(P_{2^{r}+1}(n),s_{0}))$.

Thus, to conclude the proof, it is enough to show that, for any $x,y\in L$,
$x\not\leq_{P_{2^{r}+1}(n)}y$.

Let $p_{i},p_{i+1}\in L_{1}$, then

$\displaystyle p_{i+1}-p_{i}$
$\displaystyle=2s_{i+1}+s_{i+2}+\dots+s_{n+r-1}-(2s_{i}+s_{i+1}+\dots+s_{n+r-1})$
$\displaystyle=-2s_{i}+s_{i+1}=-1.$

Thus, the difference between any two element of $L_{1}$ is smaller than
$r<s_{0}$. Which implies that $p_{i}\not\leq_{P_{2^{r}+1}(n)}p_{j}$ for any
$1\leq i,j\leq r$ and $i\neq j$.

Similarly, one can check that for $q_{i},q_{i+1}\in L_{2}$, $q_{i+1}-q_{i}=-1$
and $q_{i}\not\leq_{P_{2^{r}+1}(n)}q_{j}$ for any $1\leq i,j\leq n-2$ and
$i\neq j$.

Let $p_{i}\in L_{1}$ and $q_{j}\in L_{2}$. Note that,
$q_{1}-p_{1}=s_{n+r}-(s_{n}+\dots+s_{n+r-1})=k2^{2n}+1-r$. Now consider
$q_{j}-p_{i}=q_{1}-(j-1)-(p_{1}-(i-1))=q_{1}-p_{1}-(j-i)=k2^{2n}+1-r-j+i$.

Suppose that $k2^{2n}+1-r-j+i\in P_{2^{r}+1}(n)$, then there exists
$\lambda_{0},\lambda_{1},...,\lambda_{n+r}\in\mathbb{N}$ such that

$\displaystyle k2^{2n}+1-r-j+i$
$\displaystyle=\lambda_{0}s_{0}+\lambda_{1}s_{1}+\cdots+\lambda_{n+r}s_{n+r}$
$\displaystyle=(\lambda_{0}+\cdots+\lambda_{n+r})+k2^{n}(\lambda_{0}+2\lambda_{1}+\cdots+2^{n+r}\lambda_{n+r}).$

We get, $(\lambda_{0}+\cdots+\lambda_{n+r})=1-r-j+i\leq 0$ which is a
contradiction as $\lambda_{i}\in\mathbb{N}$. Thus, $q_{j}-p_{i}\notin
P_{2^{r}+1}(n)$ and hence $p_{i}\not\leq_{P_{2^{r}+1}(n)}q_{j}$ for $1\leq
i\leq r$, $1\leq j\leq n-2$.

Now consider,

$\displaystyle 2s_{1}+s_{n}+s_{n+r}-p_{i}$
$\displaystyle=2s_{1}+s_{n}+s_{n+r}-(p_{1}-(i-1))$
$\displaystyle=-s_{2}-\cdots-s_{n-1}-s_{n+1}-\cdots-s_{n+r-1}+s_{n+r}+i-1$
$\displaystyle=(k2^{n+2}-(n-3))+k2^{2n}-r+1+(i-1)$
$\displaystyle=k2^{n}(4+2^{n})-n-r+3+i.$

If possible suppose that $k2^{2n}+k2^{n+2}-n-r+3+i\in P_{2^{r}+1}(n)$, then
there exists $\lambda_{0},\lambda_{1},...,\lambda_{n+r}\in\mathbb{N}$ such
that

$\displaystyle k2^{n}(4+2^{n})-n-r+3+i$
$\displaystyle=\lambda_{0}s_{0}+\lambda_{1}s_{1}+\cdots+\lambda_{n+r}s_{n+r}$
$\displaystyle=(\lambda_{0}+\cdots+\lambda_{n+r})+k2^{n}(2^{0}\lambda_{0}+\cdots+2^{n+r}\lambda_{n+r}).$

We get, $(\lambda_{0}+\cdots+\lambda_{n+r})=-(n+r-3-i)\leq 0$, which is a
contradiction as $\lambda_{i}\in\mathbb{N}$. Therefore,
$p_{i}\not\leq_{P_{2^{r}+1}(n)}2s_{1}+s_{n}+s_{n+r}$ for $1\leq i\leq r$.

Similarly, it is clear that $2s_{1}+s_{n}+s_{n+r}-q_{j}=k2^{n+2}+(j-n+2)\notin
P_{2^{r}+1}(n)$. Therefore,
$q_{j}\not\leq_{P_{2^{r}+1}(n)}2s_{1}+s_{n}+s_{n+r}$ for $1\leq j\leq n-2$.

Hence, difference between any two elements of $L$ do not belongs to
$P_{2^{r}+1}(n)$. Thus, from Remark 3, we have $L=maximal_{\leq
P_{2^{r}+1}(n)}(\mathrm{Ap}(P_{2^{r}+1}(n),s_{0}))$. ∎

By applying Lemma 15 and Theorem 5.1 we obtained the following theorem.

###### Theorem 5.2

Let $n>2$ be an integer and let $P_{2^{r}+1}(n)$ be the Proth numerical
semigroup. Then

$\mathrm{PF}(P_{2^{r}+1}(n))=\\{2s_{i}+s_{i+1}+\dots+s_{n+r-1}-s_{0}\,\mid\,1\leq
i\leq r\\}\,\cup$ $\\{2s_{j}+s_{j+1}+\dots+s_{n-1}+s_{n+r}-s_{0}\,\mid\,1\leq
j\leq n-2\\}$ $\cup\,\\{2s_{1}+s_{n}+s_{n+r}-s_{0}\\}$
and $\mathrm{t}(P_{2^{r}+1}(n))=|\mathrm{PF}(P_{2^{r}+1}(n)|=r+n-1$.

##  6 Wilf’s Conjecture

In this section, we prove that the Proth numerical semigroup $P_{2^{r}+1}(n)$
supports Wilf’s conjecture. Let us begin with the statement of Wilf’s
conjecture.

###### Conjecture 1

[31] Let $S$ be a numerical semigroup, and $\mathrm{\nu}(S)=|\\{s\in
S\,\mid\,s\leq\mathrm{F}(S)\\}|$, then

$\mathrm{F}(S)+1\leq\mathrm{e}(S)\mathrm{\nu}(S),$

where $\mathrm{e}(S)$ is the embedding dimension of $S$ and $\mathrm{F}(S)$ is
the Frobenius number of $S$.

###### Lemma 17

(Corollary 5 in [2]) Let $S$ be a numerical semigroup. We have
$\mathrm{F}(S)+1\leq(\mathrm{t}(S)+1)\mathrm{\nu}(S)$.

From the previous lemma we obtain the following theorem.

###### Theorem 6.1

The Proth numerical semigroup $P_{2^{r}+1}(n)$ satisfies Wilf’s conjecture.

###### Proof

Recall that $\mathrm{e}(P_{2^{r}+1}(n))=n+r+1$ and from Lemma 17

$\displaystyle\mathrm{F}(P_{2^{r}+1}(n))+1\leq$
$\displaystyle\,(\mathrm{t}(P_{2^{r}+1}(n))+1)\,\mathrm{\nu}(P_{2^{r}+1}(n))$
$\displaystyle=$ $\displaystyle\,(n+r)\,\mathrm{\nu}(P_{2^{r}+1}(n))$
$\displaystyle<$ $\displaystyle\,(n+r+1)\,\mathrm{\nu}(P_{2^{r}+1}(n))$
$\displaystyle=$
$\displaystyle\,\mathrm{e}(P_{2^{r}+1}(n))\,\mathrm{\nu}(P_{2^{r}+1}(n).$

∎

##  7 Conclusion

In this work, we obtained the formula for the embedding dimension of the Proth
numerical semigroup $P_{k}(n)$. As a main result, we solved the Frobenius
problem for $P_{2^{r}+1}(n)$. Moreover, we also attained the pseudo-Frobenius
set and the type of $P_{2^{r}+1}(n)$. We concluded the paper by examining that
$P_{2^{r}+1}(n)$ supports Wilf’s conjecture. The following is an immediate
open question to investigate: Is there a formula to find the Frobenius number
and other invariants of the Proth numerical semigroup $P_{k}(n)$ for arbitrary
$k$?

## References

  * [1] Apéry, R.: Sur les branches superlinéaires des courbes algébriques. Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences. 222, 1198-1200 (1946)
  * [2] Assi, A., D’Anna, M., García-Sánchez, P.A.: Numerical semigroups and applications. Springer Nature (2020)
  * [3] Alfonsín, J.L.: The diophantine Frobenius problem. OUP Oxford (2005)
  * [4] Beyer, Ö., Selmer, E.S.: On the linear diophantine problem of Frobenius in three variables (1978)
  * [5] Bras-Amorós, M.: Bounds on the number of numerical semigroups of a given genus. Journal of Pure and Applied Algebra. 213(6), 997-1001 (2009)
  * [6] Beck, M., Robins, S.: Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra. Undergrad. Texts in Math (2007)
  * [7] Gil, B.K., Han, J.W., Kim, T.H., Koo, R.H., Lee, B.W., J., Nam, K.S., Park, H.W., Park, P.S.: Frobenius numbers of Pythagorean triples. International Journal of Number Theory. 11(02), 613-9 (2015)
  * [8] Gu, Ze, and Xilin, T.: The Frobenius problem for a class of numerical semigroups. International Journal of Number Theory 13, no. 05 (2017)
  * [9] Guy, R.: Unsolved problems in number theory. Springer Science (2004)
  * [10] Heap, B.R., Lynn, M.S.: On a linear Diophantine problem of Frobenius: an improved algorithm. Numerische Mathematik. 7(3), 226-31 (1965)
  * [11] Hujter, M., Vizvári, B:. The exact solutions to the Frobenius problem with three variables. Ramanujan Math. Soc. 2(2), 117-43 (1987)
  * [12] Marín, J. M., Ramírez- Alfonsín, J. L, Revuelta, M. P.: On the Frobenius number of Fibonacci numerical semigroups. Integers. Electronic Journal of Combinatorial Number Theory (2007)
  * [13] Lepilov, M., O’Rourke, J., Swanson, I.: Frobenius numbers of numerical semigroups generated by three consecutive squares or cubes. Semigroup Forum. 91, pp. 238-259 (2015)
  * [14] Owens, R.W.: An algorithm to solve the Frobenius problem. Mathematics magazine. 76(4), 264-75 (2003)
  * [15] Raczunas, M., C. Astowski-Wachtel, P.: A Diophantine problem of Frobenius in terms of the least common multiple. Discrete Math (1996)
  * [16] Ramirez-Alfonsin, J.L.: Complexity of the Frobenius problem. Combinatorica. 16(1), pp.143-147 (1996)
  * [17] Rosales, J., Robles-Pérez A.: The Frobenius problem for numerical semigroups with embedding dimension equal to three. Mathematics of Computation. 81(279), 1609-17 (2012)
  * [18] Rosales, J. C., García-Sánchez, P.A.: Numerical semigroups. New York: Springer (2009)
  * [19] Rosales, J. C.: Numerical semigroups with Apéry sets of unique expression. Journal of Algebra. 226, 479-487 (2000)
  * [20] Rosales, J. C., García-Sánchez, P. A., García-García, J.I., Jiménez Madrid, J. A.: Fundamental gaps in numerical semigroups. Journal of pure and applied algebra. 189, 301-313 (2004)
  * [21] Rosales, J.C., Branco, M., Torrão, D.: The Frobenius problem for Mersenne numerical semigroups. Mathematische Zeitschrift. 286(1), 741-9 (2017)
  * [22] Rosales, J.C., Branco, M., Torrão, D.: The Frobenius problem for Thabit numerical semigroups. Journal of Number Theory. 155, 85-99 (2015)
  * [23] Rosales, J.C., Branco, M., Torrão, D.: The Frobenius problem for repunit numerical semigroups. The Ramanujan Journal. 40(2), 323-34 (2016)
  * [24] Rödseth, Ö.J.: On a linear Diophantine problem of Frobenius (1978)
  * [25] Selmer, E. S.: On the linear diophantine problem of Frobenius (1977).
  * [26] Sylvester, J.: Mathematical questions with their solutions. Educational times. 41(21), 171-8 (1884)
  * [27] Song, K.: The Frobenius problem for numerical semigroups generated by the Thabit numbers of the first, second kind base b and the Cunningham numbers. Bulletin of the Korean Mathematical Society. 57(3), 623-47 (2020)
  * [28] Sylvester, J.: On subvariants, i.e. semi-invariants to binary quantics of an unlimited order. American Journal of Mathematics. 5(1), 79-136 (1882)
  * [29] Tripathi, A.: On the Frobenius problem for geometric sequences. Integers. 8(1), i43 (2008)
  * [30] Tripathi, A.: The Frobenius problem for modified arithmetic progressions. Journal of Integer Sequences. 16(2) (2013)
  * [31] Wilf, H.: A circle-of-lights algorithm for the “money-changing problem. The American Mathematical Monthly. 85, 562-565 (1978)