Hyperbolic Image-Text Representations

Karan Desaiumich
Maximilian Nickelmeta
Tanmay Rajpurohitind
Justin Johnsonumich,meta
Ramakrishna Vedantamnyu

umichUniversity of Michigan
metaMeta AI
nyuNew York University
indIndependent Researcher

Karan Desai
vision and language, representation learning, riemannian geometry, transformers

KD and Rama did this work while at Meta.

Visual and linguistic concepts naturally organize themselves in a hierarchy, where a textual concept “dog” entails all images that contain dogs.
Despite being intuitive, current large-scale vision and language models such as CLIP [Radford et al., 2021] do not explicitly capture such hierarchy.
We propose MERU, a contrastive model that yields hyperbolic representations of images and text.
Hyperbolic spaces have suitable geometric properties to embed tree-like data,
so MERU can better capture the underlying hierarchy in image-text datasets.
Our results show that MERU learns a highly interpretable and structured representation space
while being competitive with CLIP's performance on standard multi-modal tasks
like image classification and image-text retrieval.
Our code and models are available at:

[Atigh et al., 2022]
Atigh, M. G., Schoep, J., Acar, E., van Noord, N., and Mettes, P.
Hyperbolic Image Segmentation.
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2022.

[Bai et al., 2021]
Bai, Y., Ying, R., Ren, H., and Leskovec, J.
Modeling Heterogeneous Hierarchies with Relation-specific Hyperbolic
In Advances in Neural Information Processing Systems
(NeurIPS), 2021.

[Baumgartner et al., 2020]
Baumgartner, J., Zannettou, S., Keegan, B., Squire, M., and Blackburn, J.
The Pushshift Reddit Dataset.
arXiv preprint arXiv:2001.08435, 2020.

[Bossard et al., 2014]
Bossard, L., Guillaumin, M., and Van Gool, L.
Food-101 – Mining Discriminative Components with Random Forests.
In Proceedings of European Conference on Computer Vision
(ECCV), 2014.

[Bulent Sariyildiz et al., 2020]
Bulent Sariyildiz, M., Perez, J., and Larlus, D.
Learning visual representations with caption annotations.
In Proceedings of European Conference on Computer Vision
(ECCV), 2020.

[Changpinyo et al., 2021]
Changpinyo, S., Sharma, P., Ding, N., and Soricut, R.
Conceptual 12m: Pushing web-scale image-text pre-training to
recognize long-tail visual concepts.
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2021.

[Chen et al., 2016]
Chen, T., Xu, B., Zhang, C., and Guestrin, C.
Training deep nets with sublinear memory cost.
arXiv preprint arXiv:1604.06174, 2016.

[Chen et al., 2015]
Chen, X., Fang, H., Lin, T.-Y., Vedantam, R., Gupta, S., Dollár, P., and
Zitnick, C. L.
COCO captions: Data collection and evaluation server.
arXiv preprint arXiv:1504.00325, 2015.

[Chen et al., 2021]
Chen, X., Xie, S., and He, K.
An empirical study of training self-supervised vision transformers.
In Proceedings of IEEE International Conference on Computer
Vision (ICCV), 2021.

[Cheng et al., 2017]
Cheng, G., Han, J., and Lu, X.
Remote Sensing Image Scene Classification: Benchmark and State of
the Art.
Proceedings of the IEEE, 2017.

[Cimpoi et al., 2014]
Cimpoi, M., Maji, S., Kokkinos, I., Mohamed, S., and Vedaldi, A.
Describing Textures in the Wild.
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2014.

[Coates et al., 2011]
Coates, A., Ng, A., and Lee, H.
An Analysis of Single Layer Networks in Unsupervised Feature
In Proceedings of the International Conference on Artificial
Intelligence and Statistics (AISTATS), 2011.

[Dasgupta et al., 2020]
Dasgupta, S. S., Boratko, M., Zhang, D., Vilnis, L., Li, X. L., and McCallum,
Improving Local Identifiability in Probabilistic Box Embeddings.
arXiv preprint arXiv:2010.04831, 2020.

[Deng et al., 2009]
Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L.
ImageNet: A Large-Scale Hierarchical Image Database.
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2009.

[Desai & Johnson, 2021]
Desai, K. and Johnson, J.
VirTex: Learning Visual Representations from Textual Annotations.
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2021.

[Desai et al., 2021]
Desai, K., Kaul, G., Aysola, Z., and Johnson, J.
RedCaps: Web-curated image-text data created by the people, for the
In NeurIPS Datasets and Benchmarks, 2021.

[Dijkstra, 1959]
Dijkstra, E. W.
A note on two problems in connexion with graphs.
Numerische mathematik, 1959.

[Doersch et al., 2015]
Doersch, C., Gupta, A., and Efros, A. A.
Unsupervised Visual Representation Learning by Context Prediction.
In Proceedings of IEEE International Conference on Computer
Vision (ICCV), 2015.

[Dosovitskiy et al., 2021]
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X.,
Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S.,
Uszkoreit, J., and Houlsby, N.
An Image is Worth 16x16 Words: Transformers for Image Recognition at
In Proceedings of the International Conference on Learning
Representations (ICLR), 2021.

[Einstein, 1905]
Einstein, A.
Zur Elektrodynamik bewegter Körper.
Annalen der physik, 1905.

[Einstein et al., 2015]
Einstein, A., Lorentz, H. A., Minkowski, H., and Weyl, H.
The Principle of Relativity: A Collection of Original Memoirs
on the Special and General Theory of Relativity.
Martino Fine Books, 2nd edition, 2015.

[El Banani et al., 2023]
El Banani, M., Desai, K., and Johnson, J.
Learning Visual Representations via Language-Guided Sampling.
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2023.

[Elhoseiny et al., 2013]
Elhoseiny, M., Saleh, B., and Elgammal, A.
Write a Classifier: Zero-Shot Learning Using Purely Textual
In Proceedings of IEEE International Conference on Computer
Vision (ICCV), 2013.

[Ermolov et al., 2022]
Ermolov, A., Mirvakhabova, L., Khrulkov, V., Sebe, N., and Oseledets, I.
Hyperbolic vision transformers: Combining improvements in metric
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2022.

[Fei-Fei et al., 2004]
Fei-Fei, L., Fergus, R., and Perona, P.
Learning Generative Visual Models from Few Training Examples: An
Incremental Bayesian Approach Tested on 101 Object Categories.
CVPR Workshop, 2004.

[Frome et al., 2013]
Frome, A., Corrado, G. S., Shlens, J., Bengio, S., Dean, J., Ranzato, M. A.,
and Mikolov, T.
Visual-Semantic Embedding Model.
In Advances in Neural Information Processing Systems
(NeurIPS). Curran Associates, Inc., 2013.

[Fürst et al., 2022]
Fürst, A., Rumetshofer, E., Lehner, J., Tran, V. T., Tang, F., Ramsauer,
H., Kreil, D., Kopp, M., Klambauer, G., Bitto, A., et al.
Cloob: Modern hopfield networks with infoloob outperform clip.

[Ganea et al., 2018]
Ganea, O.-E., Bécigneul, G., and Hofmann, T.
Hyperbolic Entailment Cones for Learning Hierarchical Embeddings.
arXiv preprint arXiv:1804.01882, 2018.

[Ge et al., 2023]
Ge, S., Mishra, S., Kornblith, S., Li, C.-L., and Jacobs, D.
Hyperbolic Contrastive Learning for Visual Representations beyond
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2023.

[Gu et al., 2022]
Gu, X., Lin, T.-Y., Kuo, W., and Cui, Y.
Open-vocabulary Object Detection via Vision and Language Knowledge
In Proceedings of the International Conference on Learning
Representations (ICLR), 2022.

[Halevy et al., 2009]
Halevy, A., Norvig, P., and Pereira, F.
The Unreasonable Effectiveness of Data.
IEEE Intelligent Systems, 2009.

[He et al., 2020]
He, K., Fan, H., Wu, Y., Xie, S., and Girshick, R.
Momentum contrast for unsupervised visual representation learning.
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2020.

[He et al., 2022]
He, K., Chen, X., Xie, S., Li, Y., Dollár, P., and Girshick, R.
Masked autoencoders are scalable vision learners.
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2022.

[Helber et al., 2019]
Helber, P., Bischke, B., Dengel, A. R., and Borth, D.
EuroSAT: A Novel Dataset and Deep Learning Benchmark for Land Use
and Land Cover Classification.
IEEE Journal of Selected Topics in Applied Earth Observations
and Remote Sensing, 2019.

[Honnibal et al., 2020]
Honnibal, M., Montani, I., Van Landeghem, S., and Boyd, A.
spaCy: Industrial-strength Natural Language Processing in Python,
URL <https://doi.org/10.5281/zenodo.1212303>.

[Ilharco et al., 2021]
Ilharco, G., Wortsman, M., Wightman, R., Gordon, C., Carlini, N., Taori, R.,
Dave, A., Shankar, V., Namkoong, H., Miller, J., Hajishirzi, H., Farhadi, A.,
and Schmidt, L.
OpenCLIP, 2021.
URL <https://doi.org/10.5281/zenodo.5143773>.

[Jia et al., 2021]
Jia, C., Yang, Y., Xia, Y., Chen, Y.-T., Parekh, Z., Pham, H., Le, Q., Sung,
Y.-H., Li, Z., and Duerig, T.
Scaling Up Visual and Vision-Language Representation Learning With
Noisy Text Supervision.
In Proceedings of the International Conference on Machine
Learning (ICML), 2021.

[Johnson et al., 2017]
Johnson, J., Hariharan, B., van der Maaten, L., Fei-Fei, L., Zitnick, C. L.,
and Girshick, R. B.
CLEVR: A Diagnostic Dataset for Compositional Language and
Elementary Visual Reasoning.
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2017.

[Karpathy & Fei-Fei, 2015]
Karpathy, A. and Fei-Fei, L.
Deep Visual-Semantic Alignments for Generating Image Descriptions.
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2015.

[Khrulkov et al., 2020]
Khrulkov, V., Mirvakhabova, L., Ustinova, E., Oseledets, I., and Lempitsky,
V. S.
Hyperbolic Image Embeddings.
Proceedings of IEEE Conference on Computer Vision and Pattern
Recognition (CVPR), 2020.

[Kornblith et al., 2019]
Kornblith, S., Shlens, J., and Le, Q. V.
Do better imagenet models transfer better?
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2019.

[Krause et al., 2013]
Krause, J., Stark, M., Deng, J., and Fei-Fei, L.
3D Object Representations for Fine-Grained Categorization.
In 4th International IEEE Workshop on 3D Representation and
Recognition (3dRR-13), 2013.

[Krizhevsky, 2009]
Krizhevsky, A.
Learning Multiple Layers of Features from Tiny Images.
<https://www.cs.toronto.edu/ kriz/learning-features-2009-TR.pdf>.

[Krizhevsky et al., 2012]
Krizhevsky, A., Sutskever, I., and Hinton, G. E.
Imagenet classification with deep convolutional neural networks.
In Advances in Neural Information Processing Systems
(NeurIPS), 2012.

[Kusupati et al., 2022]
Kusupati, A., Bhatt, G., Rege, A., Wallingford, M., Sinha, A., Ramanujan, V.,
Howard-Snyder, W., Chen, K., Kakade, S. M., Jain, P., and Farhadi, A.
Matryoshka Representation Learning.
In Advances in Neural Information Processing Systems
(NeurIPS), 2022.

[Law et al., 2019]
Law, M. T., Liao, R., Snell, J., and Zemel, R. S.
Lorentzian Distance Learning for Hyperbolic Representations.
In Proceedings of the International Conference on Machine
Learning (ICML), 2019.

[Le et al., 2019]
Le, M., Roller, S., Papaxanthos, L., Kiela, D., and Nickel, M.
Inferring Concept Hierarchies from Text Corpora via Hyperbolic
In Proceedings of the Annual Meeting on Association for
Computational Linguistics (ACL), 2019.

[LeCun et al., 2010]
LeCun, Y., Cortes, C., and Burges, C.
MNIST handwritten digit database.
ATT Labs [Online]. Available:
http://yann.lecun.com/exdb/mnist, 2010.

[Lee, 2019]
Lee, J. M.
Introduction to Riemannian Manifolds.
Graduate Texts in Mathematics. Springer International Publishing,
ISBN 9783319917542.
URL <https://books.google.com/books?id=UIPltQEACAAJ>.

[Li et al., 2017]
Li, A., Jabri, A., Joulin, A., and van der Maaten, L.
Learning visual n-grams from web data.
In Proceedings of IEEE International Conference on Computer
Vision (ICCV), 2017.

[Li et al., 2022]
Li, Y., Liang, F., Zhao, L., Cui, Y., Ouyang, W., Shao, J., Yu, F., and Yan, J.
Supervision Exists Everywhere: A Data Efficient Contrastive
Language-Image Pre-training Paradigm.
In Proceedings of the International Conference on Learning
Representations (ICLR), 2022.

[Liu & Nocedal, 1989]
Liu, D. C. and Nocedal, J.
On the limited memory BFGS method for large scale optimization.
Mathematical programming, 1989.

[Liu et al., 2019]
Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M.,
Zettlemoyer, L., and Stoyanov, V.
RoBERTa: A robustly optimized bert pretraining approach.
arXiv preprint arXiv:1907.11692, 2019.

[Loshchilov & Hutter, 2016]
Loshchilov, I. and Hutter, F.
SGDR: Stochastic gradient descent with warm restarts.
arXiv preprint arXiv:1608.03983, 2016.

[Loshchilov & Hutter, 2019]
Loshchilov, I. and Hutter, F.
Decoupled Weight Decay Regularization.
In Proceedings of the International Conference on Learning
Representations (ICLR), 2019.

[Maji et al., 2013]
Maji, S., Rahtu, E., Kannala, J., Blaschko, M. B., and Vedaldi, A.
Fine-Grained Visual Classification of Aircraft.
arXiv preprint arXiv:1306.5151, 2013.

[Micikevicius et al., 2018]
Micikevicius, P., Narang, S., Alben, J., Diamos, G., Elsen, E., Garcia, D.,
Ginsburg, B., Houston, M., Kuchaiev, O., Venkatesh, G., et al.
Mixed precision training.
In Proceedings of the International Conference on Learning
Representations (ICLR), 2018.

[Miller, 1992]
Miller, G. A.
WordNet: A Lexical Database for English.
In Speech and Natural Language: Proceedings of a Workshop Held
at Harriman, New York, 1992.

[Minkowski, 1908]
Minkowski, H.
Raum und Zeit.
Physikalische Zeitschrift, 1908.

[Mu et al., 2022]
Mu, N., Kirillov, A., Wagner, D., and Xie, S.
Slip: Self-supervision meets language-image pre-training.
In Proceedings of European Conference on Computer Vision
(ECCV), 2022.

[Murphy, 2013]
Murphy, K. P.
Machine learning : a probabilistic perspective.
MIT Press, 2013.

[Nguyen et al., 2017]
Nguyen, K. A., Köper, M., im Walde, S. S., and Vu, N. T.
Hierarchical Embeddings for Hypernymy Detection and Directionality.
In Proceedings of the Conference on Empirical Methods in
Natural Language Processing (EMNLP), 2017.

[Nickel & Kiela, 2017]
Nickel, M. and Kiela, D.
Poincaré Embeddings for Learning Hierarchical Representations.
In Advances in Neural Information Processing Systems
(NeurIPS), 2017.

[Nickel & Kiela, 2018]
Nickel, M. and Kiela, D.
Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic
In Proceedings of the International Conference on Machine
Learning (ICML), 2018.

[Nilsback & Zisserman, 2008]
Nilsback, M.-E. and Zisserman, A.
Automated Flower Classification over a Large Number of Classes.
In ICVGIP, 2008.

[Noroozi & Favaro, 2016]
Noroozi, M. and Favaro, P.
Unsupervised Learning of Visual Representations by Solving Jigsaw
In Proceedings of European Conference on Computer Vision
(ECCV), 2016.

[Parkhi et al., 2012]
Parkhi, O., Vedaldi, A., Zisserman, A., and Jawahar, C. V.
Cats and Dogs.
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2012.

[Paszke et al., 2019]
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen,
T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E.,
DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L.,
Bai, J., and Chintala, S.
PyTorch: An Imperative Style, High-Performance Deep Learning
In Advances in Neural Information Processing Systems
(NeurIPS), 2019.

[Pedregosa et al., 2011]
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel,
O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J.,
Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E.
Scikit-learn: Machine Learning in Python.
Journal of Machine Learning Research, 2011.

[Radford et al., 2021]
Radford, A., Kim, J. W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry,
G., Askell, A., Mishkin, P., Clark, J., et al.
Learning Transferable Visual Models From Natural Language
In Proceedings of the International Conference on Machine
Learning (ICML), 2021.

[Ratcliffe, 2006]
Ratcliffe, J. G.
Foundations of Hyperbolic Manifolds.
Graduate Texts in Mathematics. Springer New York, 2006.
ISBN 9780387331973.
URL <https://books.google.com/books?id=JV9m8o-ok6YC>.

[Russakovsky et al., 2014]
Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z.,
Karpathy, A., Khosla, A., Bernstein, M. S., Berg, A. C., and Fei-Fei, L.
ImageNet Large Scale Visual Recognition Challenge.
International Journal of Computer Vision, 2014.

[Schuhmann et al., 2021]
Schuhmann, C., Vencu, R., Beaumont, R., Kaczmarczyk, R., Mullis, C., Katta, A.,
Coombes, T., Jitsev, J., and Komatsuzaki, A.
Laion-400m: Open dataset of clip-filtered 400 million image-text
arXiv preprint arXiv:2111.02114, 2021.

[Schuhmann et al., 2022]
Schuhmann, C., Beaumont, R., Vencu, R., Gordon, C., Wightman, R., Cherti, M.,
Coombes, T., Katta, A., Mullis, C., Wortsman, M., et al.
LAION-5B: An open large-scale dataset for training next generation
image-text models.
arXiv preprint arXiv:2210.08402, 2022.

[Selvaraju et al., 2017]
Selvaraju, R. R., Cogswell, M., Das, A., Vedantam, R., Parikh, D., and Batra,
Grad-cam: Visual explanations from deep networks via gradient-based
In Proceedings of IEEE International Conference on Computer
Vision (ICCV), 2017.

[Sennrich et al., 2016]
Sennrich, R., Haddow, B., and Birch, A.
Neural Machine Translation of Rare Words with Subword Units.
In Proceedings of the Annual Meeting on Association for
Computational Linguistics (ACL), 2016.

[Sharma et al., 2018]
Sharma, P., Ding, N., Goodman, S., and Soricut, R.
Conceptual captions: A cleaned, hypernymed, image alt-text dataset
for automatic image captioning.
In Proceedings of the Annual Meeting on Association for
Computational Linguistics (ACL), 2018.

[Socher et al., 2013]
Socher, R., Perelygin, A., Wu, J., Chuang, J., Manning, C. D., Ng, A., and
Potts, C.
Recursive Deep Models for Semantic Compositionality Over a Sentiment
In Proceedings of the Conference on Empirical Methods in
Natural Language Processing (EMNLP), 2013.

[Sohn, 2016]
Sohn, K.
Improved Deep Metric Learning with Multi-class N-pair Loss
In Advances in Neural Information Processing Systems
(NeurIPS), 2016.

[Song et al., 2015]
Song, H. O., Xiang, Y., Jegelka, S., and Savarese, S.
Deep Metric Learning via Lifted Structured Feature Embedding.
arXiv preprint arXiv:1511.06452, 2015.

[Speer, 2019]
Speer, R.
ftfy, 2019.
URL <https://doi.org/10.5281/zenodo.2591652>.

[Sun et al., 2017]
Sun, C., Shrivastava, A., Singh, S., and Gupta, A.
Revisiting unreasonable effectiveness of data in deep learning era.
In Proceedings of IEEE International Conference on Computer
Vision (ICCV), 2017.

[Thomee et al., 2016]
Thomee, B., Shamma, D. A., Friedland, G., Elizalde, B., Ni, K., Poland, D.,
Borth, D., and Li, L.-J.
YFCC100M: The New Data in Multimedia Research.
Communications of the ACM, 2016.

[Tifrea et al., 2018]
Tifrea, A., Bécigneul, G., and Ganea, O.
Poincaré GloVe: Hyperbolic Word Embeddings.
arXiv preprint arXiv:1810.06546, 2018.

[Touvron et al., 2021]
Touvron, H., Cord, M., Douze, M., Massa, F., Sablayrolles, A., and Jégou,
Training data-efficient image transformers & distillation through
In Proceedings of the International Conference on Machine
Learning (ICML), 2021.

[Vaswani et al., 2017]
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N.,
Kaiser, Ł., and Polosukhin, I.
Attention is all you need.
In Advances in Neural Information Processing Systems
(NeurIPS), 2017.

[Veeling et al., 2018]
Veeling, B. S., Linmans, J., Winkens, J., Cohen, T., and Welling, M.
CNNs for Digital Pathology.
arXiv preprint arXiv:1806.03962, 2018.

[Vendrov et al., 2016]
Vendrov, I., Kiros, R., Fidler, S., and Urtasun, R.
Order-embeddings of images and language.
In Proceedings of the International Conference on Learning
Representations (ICLR), 2016.

[Vilnis et al., 2018]
Vilnis, L., Li, X. L., Murty, S., and McCallum, A.
Probabilistic Embedding of Knowledge Graphs with Box Lattice
In Proceedings of the Annual Meeting on Association for
Computational Linguistics (ACL), 2018.

[Wah et al., 2011]
Wah, C., Branson, S., Welinder, P., Perona, P., and Belongie, S. J.
The Caltech-UCSD Birds-200-2011 Dataset.

[Wightman, 2019]
Wightman, R.
PyTorch Image Models.
<https://github.com/rwightman/pytorch-image-models>, 2019.

[Wu et al., 2018]
Wu, Z., Xiong, Y., Yu, S. X., and Lin, D.
Unsupervised feature learning via non-parametric instance
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2018.

[Xiao et al., 2010]
Xiao, J., Hays, J., Ehinger, K. A., Oliva, A., and Torralba, A.
SUN database: Large-scale scene recognition from abbey to zoo.
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2010.

[Yao et al., 2022]
Yao, L., Huang, R., Hou, L., Lu, G., Niu, M., Xu, H., Liang, X., Li, Z., Jiang,
X., and Xu, C.
FILIP: Fine-grained Interactive Language-Image Pre-Training.
In Proceedings of the International Conference on Learning
Representations (ICLR), 2022.

[Young et al., 2014]
Young, P., Lai, A., Hodosh, M., and Hockenmaier, J.
From image descriptions to visual denotations: New similarity
metrics for semantic inference over event descriptions.
In Proceedings of the Annual Meeting on Association for
Computational Linguistics (ACL), 2014.

[Zareian et al., 2021]
Zareian, A., Rosa, K. D., Hu, D. H., and Chang, S.-F.
Open-vocabulary object detection using captions.
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2021.

[Zhai et al., 2019]
Zhai, X., Puigcerver, J., Kolesnikov, A., Ruyssen, P., Riquelme, C., Lucic, M.,
Djolonga, J., Pinto, A. S., Neumann, M., Dosovitskiy, A., Beyer, L., Bachem,
O., Tschannen, M., Michalski, M., Bousquet, O., Gelly, S., and Houlsby, N.
A Large-scale Study of Representation Learning with the Visual Task
Adaptation Benchmark.
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2019.

[Zhang et al., 2016]
Zhang, R., Isola, P., and Efros, A. A.
Colorful Image Colorization.
In Proceedings of European Conference on Computer Vision
(ECCV), 2016.

§ ACKNOWLEDGMENTS

We thank our wonderful colleagues for helpful discussions and feedback on the paper
(in alphabetical order, grouped by their affiliation during the undertaking of this project):

* Meta:
Léon Bottou, Kamalika Chaudhuri, Ricky Chen, Piotr Dollár, Surya Ganguli, Rohit Girdhar, Naman Goyal, Wei-Ning Hsu, Mark Ibrahim, Ishan Misra, Ari Morcos, Devi Parikh, David Schwab, Mannat Singh, Shubham Toshniwal, and Karen Ullrich.

* University of Michigan:
Mohamed El Banani, Ang Cao, Daniel Geng, Richard Higgins, Gaurav Kaul, Nilesh Kulkarni, Andrew Lee, Tiange Luo, Andrew Owens, Jeongsoo Park, Chris Rockwell, Dandan Shan, Ayush Shrivastava, and Stella Yu.

* Meta (intern cohort):
Desi Ivanova, Lyle Kim, Andre Niyongabo Rubungo, Elizabeth Salesky, and Sagar Vaze.

KD thanks Julius Berner and Steffen Schneider for fruitful discussions over fruity cocktails.
KD also thanks Cannelle and many other cafés in Ann Arbor for their high-quality espresso shots and many hours of free Wi-Fi.


# The complexity of a numerical semigroup

J. I. García-García111 Departamento de Matemáticas/INDESS (Instituto
Universitario para el Desarrollo Social Sostenible), Universidad de Cádiz,
E-11510 Puerto Real (Cádiz, Spain). E-mail<EMAIL_ADDRESS>
M. A. Moreno-Frías222 Departamento de Matemáticas, Universidad de Cádiz,
E-11510 Puerto Real (Cádiz, Spain). Partially supported by MTM2017-84890-P and
by Junta de Andalucía group FQM-298. E-mail<EMAIL_ADDRESS>
J. C. Rosales 333 Dpto. de Álgebra, Facultad de Ciencias, Universidad de
Granada, E-18071, Granada. (Spain). Partially supported by MTM2017-84890-P and
by Junta de Andalucía group FQM-343. E-mail<EMAIL_ADDRESS>
A. Vigneron-Tenorio444 Departamento de Matemáticas/INDESS (Instituto
Universitario para el Desarrollo Social Sostenible), Universidad de Cádiz,
E-11406 Jerez de la Frontera (Cádiz, Spain). E-mail<EMAIL_ADDRESS>
###### Abstract

Let $S$ and $\Delta$ be numerical semigroups. A numerical semigroup $S$ is an
$\mathbf{I}(\Delta)$-semigroup if $S\backslash\\{0\\}$ is an ideal of
$\Delta$. We will denote by $\mathcal{J}(\Delta)=\\{S\mid S\text{ is an
$\mathbf{I}(\Delta)$-semigroup}\\}.$ We will say that $\Delta$ is an ideal
extension of  $S$ if $S\in\mathcal{J}(\Delta).$ In this work, we present an
algorithm that allows to build all the ideal extensions of a numerical
semigroup. We can recursively denote by
$\mathcal{J}^{0}(\mathbb{N})=\mathbb{N},$
$\mathcal{J}^{1}(\mathbb{N})=\mathcal{J}(\mathbb{N})$ and
$\mathcal{J}^{k+1}(\mathbb{N})=\mathcal{J}(\mathcal{J}^{k}(\mathbb{N}))$ for
all $k\in\mathbb{N}.$ The complexity of a numerical semigroup $S$ is the
minimun of the set $\\{k\in\mathbb{N}\mid S\in\mathcal{J}^{k}(\mathbb{N})\\}.$
In addition, we will give an algorithm that allows us to compute all the
numerical semigroups with fixed multiplicity and complexity.

Keywords: numerical semigroup, ideal, extension, complexity,
${\mathrm{i}}$-chain, ${\mathrm{i}}$-pertinent map.

2020 Mathematics Subject Classification: 11B13, 11P70, 13P25, 20M12, 20M14.

## Introduction

Let $\mathbb{Z}=\\{0,1,-1,2,-2,\dots\\}$ be the set of integer numbers and
$\mathbb{N}=\\{x\in\mathbb{Z}\mid x\geq 0\\}$. A numerical semigroup is a
subset $S$ of $\mathbb{N}$ containing the zero element, closed by the sum and
such that $\mathbb{N}\backslash S=\\{x\in\mathbb{N}\mid x\notin S\\}$ is
finite.

If $A$ is a subset nonempty of $\mathbb{N}$, we denote by $\langle A\rangle$
the submonoid of $(\mathbb{N},+)$ generated by $A$, the set $\langle
A\rangle=\\{\lambda_{1}a_{1}+\dots+\lambda_{n}a_{n}\mid
n\in\mathbb{N}\setminus\\{0\\},\,\\{a_{1},\dots,a_{n}\\}\subseteq
A,\,\\{\lambda_{1},\dots,\lambda_{n}\\}\subseteq\mathbb{N}\\}.$ By [11, Lemma
2.1], we know that $\langle A\rangle$ is a numerical semigroup if and only if
$\gcd(A)=1.$ If $S$ is a numerical semigroup and $S=\langle A\rangle$, we say
that $A$ is a system of generators of $S$. Moreover, if $S\neq\langle
B\rangle$ for all $B\varsubsetneq A$, then $A$ is called a minimal system of
generators of $S$. In [11, Corollary 2.8] is shown that every numerical
semigroup has a unique minimal system of generator which is always finite. We
denote by ${\mathrm{msg}}(S)$ the minimal system of generators of $S$. The
cardinality of ${\mathrm{msg}}(S)$ is called the embedding dimension of $S$
and will be denoted by $\mathrm{e}(S).$

If $S$ is a numerical semigroup, then
$\mathrm{F}(S)=\mbox{max}(\mathbb{Z}\backslash S)$,
$\mathrm{g}(S)=\sharp(\mathbb{N}\backslash S)$, where $\sharp A$ denote the
cardinality of a set $A$, and $\mbox{m}(S)=\mbox{min}(S\setminus\\{0\\})$.
They are three important invariants of $S$ which we are known as the Frobenius
number, the genus and the multiplicity of $S$, respectively.

The study of numerical semigroups is a clasical topic and it has been
motivated by the named Frobenius problem (see [8]). It consists on finding
formulas that calculate the Frobenius number and the genus of a numerical
semigroup from its minimal system of generators. This problem was solved by
Sylvester (see [12]) for numerical semigroups with embedding dimension two.
Nowadays, the problem remains unsolved for numerical semigroups with embedding
dimension equal to or greater than or three.

Let $\Delta$ be a numerical semigroup. An ideal of $\Delta$ is a nonempty
subset $I$ of $\Delta$ such that $I+\Delta=\\{a+b\mid a\in I\mbox{ and
}b\in\Delta\\}\subseteq I.$ For every ideal $I$ of $\Delta$, the set
$I\cup\\{0\\}$ is also a numerical semigroup. This fact leads us to give the
following definition: a numerical semigroup $S$ is an
$\mathbf{I}(\Delta)$-semigroup if and only if $S\backslash\\{0\\}$ is an ideal
of $\Delta$. We denote by $\mathcal{J}(\Delta)$ the set $\\{S\mid S\text{ is
an $\mathbf{I}(\Delta)$-semigroup}\\}$, and if ${\mathscr{F}}$ is a family of
numerical semigroups, then $\mathcal{J}({\mathscr{F}})$ denotes the set
$\bigcup_{\Delta\in{\mathscr{F}}}\mathcal{J}(\Delta).$

The main motivation of this work is that ordinary numerical and elementary
numerical semigroups are those with a simpler structure, in that order. In
that line we will prove that $\mathcal{J}(\mathbb{N})$ is the set of ordinary
numerical semigroup and that
$\mathcal{J}^{2}(\mathbb{N})=\mathcal{J}(\mathcal{J}(\mathbb{N}))$ is equal to
the set of elementary numerical semigroup.

Following the idea of the previous paragraph we give the definition of
complexity of a numerical semigroup as follows: the complexity  of a numerical
semigroup $S$, denoted by ${\mathrm{C}}(S)$, is the number
$\min\\{k\in\mathbb{N}\mid S\in\mathcal{J}^{k}(\mathbb{N})\\}.$

Let $S$ and $\Delta$ be numerical semigroups. We say that $\Delta$ is an ideal
extension of  $S$ whenever $S\in\mathcal{J}(\Delta).$ An i-chain of length n
connecting the numerical semigroups $S$ and $T$ is a chain of numerical
semigroups $S_{0}\subseteq S_{1}\subseteq S_{2}\subseteq\dots\subseteq S_{n}$
such that $S_{0}=S,$ $S_{n}=T$ and $S_{i}\in\mathcal{J}(S_{i+1})$ for every
$i\in\\{0,\dots,n-1\\}.$

The content of this work is organized as follows. In the first section, we
give some definitions and recall some results. In Section 2, we present an
algorithm that allows to build all the ideal extensions of a numerical
semigroup $S.$ Section 3 is devoted to prove that ${\mathrm{C}}(S)$ is the
minimun of the lenghts of the $i$-chain connecting $S$ and $\mathbb{N}.$ In
Section 4, we show how we can build one of these chains with minimun lenght.
As a consequence, we obtain that
${\mathrm{C}}(S)=\left\lfloor{\frac{{\mathrm{F}}(S)}{{\mathrm{m}}(S)}}\right\rfloor+1$
(where $\lfloor q\rfloor$ is defined as $\max\\{z\in\mathbb{Z}\mid z\leq q\\}$
for every $q\in\mathbb{Q}$). In Section 5, we give an algorithm to compute all
the numerical semigroups with fixed multiplicity and complexity. Finally, we
prove that the cardinal of the set of numerical semigroups with multiplicity
$m$ and complexity $c$ is less than or equal to the cardinality of the set of
numerical semigroups with multiplicity $m$ and complexity equal to $c+1$.

##  1 Ideal extensions of a numerical semigroup

Let $S$ and $T$ be numerical semigroups. We will say that $T$ is an ideal
extension of $S$ if $S\backslash\\{0\\}$ is an ideal of $T$. The ideal
extensions of semigroups were introduced in [5] and thenceforth they have been
extensively studied (see, for instant [7]).

Following the notation introduced in [9], we say that an integer $x$ is a
pseudo-Frobenius number of a numerical semigroup $S$, if $x\notin S$ and
$x+s\in S$ for all $s\in S\backslash\\{0\\}.$ We denote by ${\mathrm{PF}}(S)$
the set of pseudo-Frobenius numbers of $S$. The cardinality of
${\mathrm{PF}}(S)$ is an important invariant of $S$ (see, for instance [2])
that is called the type of $S$ and is denoted by ${\mathrm{t}}(S)$.

The following result is found in [11, Corollary 2.23].

######  Proposition 1.

If $S$ is a numerical semigroup such that $S\neq\mathbb{N},$ then
${\mathrm{t}}(S)\leq{\mathrm{m}}(S)-1.$

Observe that if $S$ is a numerical semigroup such that $S\neq\mathbb{N}$ and
$\\{x,y\\}\subseteq{\mathrm{PF}}(S),$ then $x+y\in S$ or
$x+y\in{\mathrm{PF}}(S).$ Therefore, we can state the following result.

######  Proposition 2.

If $S$ is a numerical semigroup and $S\neq\mathbb{N},$ then
$S\cup{\mathrm{PF}}(S)$ is also a numerical semigroup.

The following result indicates how the ideal extensions of a numerical
semigroup are.

######  Theorem 3.

Let $S$ and $\Delta$ be numerical semigroups. Then $\Delta$ is an ideal
extension of $S$ if and only if $S\subseteq\Delta\subseteq
S\cup{\mathrm{PF}}(S).$

###### Proof.

Necessity. If $\Delta$ is an ideal extension of $S,$ then $S\subseteq\Delta$
and $(S\backslash\\{0\\})+\Delta\subseteq S\backslash\\{0\\}.$ Therefore, if
$x\in\Delta\backslash S,$ then $\\{x\\}+(S\backslash\\{0\\})\subseteq S.$
Hence, $x\in{\mathrm{PF}}(S).$ Consequently, $\Delta\subseteq
S\cup{\mathrm{PF}}(S).$

Sufficiency. If $S\subseteq\Delta\subseteq S\cup{\mathrm{PF}}(S),$ then
$(S\backslash\\{0\\})+\Delta\subseteq S\backslash\\{0\\}.$ Thus,
$S\backslash\\{0\\}$ is an ideal of $\Delta$ and so $\Delta$ is an ideal
extension of $S.$ ∎

As an immediate consequence of the previous theorem, we have the following
result.

######  Corollary 4.

Let $S$ be a numerical semigroup. Then the cardinality of the set
$\\{\Delta\mid\Delta\mbox{ is an ideal extension of }S\\}$ is less than or
equal to $2^{{\mathrm{t}}(S)}.$

Our purpose now is to present an algorithm to compute all the ideal extensions
of a numerical semigroup $S$. In order to do that, we introduce the following
concepts and results.

Let $S$ be a numerical semigroup and $n\in S\backslash\\{0\\}.$ We define, in
honour of [1], the Apéry set of n in S, as $\mathrm{Ap}(S,n)=\\{s\in S\mid
s-n\notin S\\}.$

The following result is in [11, Lemma 2.4].

######  Proposition 5.

Let $S$ be a numerical semigroup and $n\in S\backslash\\{0\\}.$ Then
$\mathrm{Ap}(S,n)$ has cardinality $n.$ Moreover,
$\mathrm{Ap}(S,n)=\\{0=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\\}.$

Let $S$ be a numerical semigroup. We define over $\mathbb{Z}$ the following
binary relation: $a\leq_{S}b$ if $b-a\in S$. In [11] it is proved that
$\leq_{S}$ is an order relation (reflexive, antisymmetric and transitive).

The following result is found in [11, Proposition 2.20].

######  Proposition 6.

If $S$ is a numerical semigroup and $n\in S\setminus\\{0\\},$ then

$\mathrm{PF}(S)=\\{w-n\mid w\in{\rm Maximals}_{\leq_{S}}\mathrm{Ap}(S,n)\\}.$

We illustrate the content of the previous proposition with an example.

######  Example 7.

If $S=\\{0,5,6,8,\rightarrow\\}$ (the symbol $\rightarrow$ means that every
integer greater than $8$ belongs to the set), then
$\mathrm{Ap}(S,5)=\\{0,6,8,9,12\\}$ and ${\rm Maximals}_{\leq_{S}}\\{0,6,8,\\\
9,12\\}=\\{8,9,12\\}.$ By applying Proposition 6, we have
${\mathrm{PF}}(S)=\\{3,4,7\\}.$

By Theorem 3, we know that a numerical semigroup $\Delta$ is an ideal
extension of a numerical semigroup $S$ if and only if there is
$A\subseteq{\mathrm{PF}}(S)$ such that $\Delta=S\cup A.$ The following result
is easy to prove and shows the property that a subset $A$ of
${\mathrm{PF}}(S)$ must verify so that the set $S\cup A$ is a numerical
semigroup.

######  Proposition 8.

Let $S$ be a numerical semigroup such that $S\neq\mathbb{N}$ and
$A\subseteq{\mathrm{PF}}(S).$ Then the following conditions are equivalents:

  1. 1)

$S\cup A$ is a numerical semigroup.

  2. 2)

If $\\{a,b\\}\subseteq A$ and $a+b\in{\mathrm{PF}}(S),$ then $a+b\in A.$

###### Proof.

1) implies 2). If $\\{a,b\\}\subseteq A,$ then $a+b\in S\cup A.$ As
$a+b\in{\mathrm{PF}}(S),$ then $a+b\notin S$ and so $a+b\in A.$

2) implies 1). The sum of two elements of $S$ belongs again to $S.$ As
$A\subseteq{\mathrm{PF}}(S),$ then the sum of an element of $A$ and a nonzero
element of $S$, belongs also to $S.$ Therefore, to prove that $S\cup A$ is a
numerical semigroup, it will be enough to see that the sum of two elements
belonging to $A$ is in $S\cup A.$ Indeed, if $\\{a,b\\}\subseteq A$ and
$a+b\notin S,$ then by the previous comment to Proposition 2, we know that
$a+b\in{\mathrm{PF}}(S).$ Thus, $a+b\in A.$ ∎

The above proposition leads to the following definition.

Let $S$ be a numerical semigroup. We say that a set $A$ is an
${\mathrm{i}}(S)$-pertinent set if it verifies the following conditions:

  1. 1)

$A\subseteq{\mathrm{PF}}(S)$ and

  2. 2)

if $\\{a,b\\}\subseteq A$ and $a+b\in{\mathrm{PF}}(S),$ then $a+b\in A.$

As an immediate consequence of Theorem 3 and Proposition 8, we have the
following result.

######  Corollary 9.

Let $S$ be a numerical semigroup such that $S\neq\mathbb{N}.$ Then the set
formed by the ideal extensions of $S$ is $\\{S\cup A\mid A\mbox{ is an
}{\mathrm{i}}(S)\mbox{-pertinent set}\\}.$

We are already able to provide the previously announced algorithm.

Data: A numerical semigroup $S\neq\mathbb{N}.$

Result: $\\{\Delta\mid\Delta\mbox{ is an ideal extension of }S\\}.$

1 Compute ${\mathrm{PF}}(S)$;

2 Compute $B=\\{A\mid A\subseteq{\mathrm{PF}}(S)\mbox{ and }A\mbox{ is an
}{\mathrm{i}}(S)\mbox{-pertinent set}\\}$;

3 return $\\{S\cup A\mid A\in B\\}$;

Algorithm 1 Computation of the set of ideal extensions of a numerical
semigroup.

We finish this section illustrating how the previous algorithm works.

######  Example 10.

If $S=\\{0,5,6,8,\rightarrow\\},$ then by Example 7 we know that
${\mathrm{PF}}(S)=\\{3,4,7\\}.$ We calculate
${\mathscr{P}}(\\{3,4,7\\})=\\{\emptyset,\\{3\\},\\{4\\},\\{7\\},\\{3,4\\},\\{3,7\\},\\{4,7\\},\\\
\\{3,4,7\\}\\}.$ A simple check shows that $\\{3,4\\}$ is the only element of
${\mathscr{P}}(\\{3,4,7\\})$ which is not ${\mathrm{i}}(S)$-pertinent.
Algorithm 10 asserts that all the ideal extensions of $S$ are:
$S\cup\emptyset$, $S\cup\\{3\\},$ $S\cup\\{4\\},$ $S\cup\\{7\\},$
$S\cup\\{3,7\\},$ $S\cup\\{4,7\\}$ and $S\cup\\{3,4,7\\}.$

The code below have is found in complexityOfNS.ipynb, is part of [6] and uses
the library [4].

    gap> S:=NumericalSemigroup(5,6,8,9,10,11,12);;
    gap> lDeltas:=idealExtensionsOfNS(S);;
    gap> List(lDeltas,x->MinimalGeneratingSystemOfNumericalSemigroup(x));

The output obtained is

    [ [ 3, 5 ], [ 4, 5, 6 ], [ 5, 6, 7, 8, 9 ], [ 3, 4, 5 ],
    [ 3, 5, 7 ], [ 4, 5, 6, 7 ] ]

which is the list of system of generators of the proper ideal extensions of
$S$.

##  2 The complexity and the ${\mathrm{i}}$-chains

Our first objetive in this section is to prove that if $S$ is a numerical
semigroup, there is $k\in\mathbb{N}$ such that
$S\in\mathcal{J}^{k}(\mathbb{N}).$ Recall that
$\mathcal{J}^{0}(\mathbb{N})=\mathbb{N},$
$\mathcal{J}^{1}(\mathbb{N})=\mathcal{J}(\mathbb{N})$ and
$\mathcal{J}^{k+1}(\mathbb{N})=\mathcal{J}(\mathcal{J}^{k}(\mathbb{N}))$ for
all $k\in\mathbb{N}.$

######  Proposition 11.

Let $S$ be a numerical semigroup and $k\in\mathbb{N}.$ Then
$S\in\mathcal{J}^{k}(\mathbb{N})$ if and only if there exists an
${\mathrm{i}}$-chain of lenght $k$ connecting $S$ with $\mathbb{N}.$

###### Proof.

We proceed by induction on $k.$ For $k=0$ the result is trivial. Assume the
result is true for $k-1$ and obtain the result for $k$.

Necessity. If $S\in\mathcal{J}^{k}(\mathbb{N}),$ then
$S\in\mathcal{J}(\mathcal{J}^{k-1}(\mathbb{N}))$ and so there exists
$S_{1}\in\mathcal{J}^{k-1}(\mathbb{N})$ such that $S\subseteq S_{1}$ is an
${\mathrm{i}}$-chain. By the induction hypothesis, there is an
${\mathrm{i}}$-chain $S_{1}\subseteq S_{2}\subseteq\dots\subseteq
S_{k}=\mathbb{N}$ of lenght $k-1$ connecting $S_{1}$ with $\mathbb{N}.$ It is
clear that $S\subseteq S_{1}\subseteq S_{2}\subseteq\dots\subseteq
S_{k}=\mathbb{N}$ is an ${\mathrm{i}}$-chain of length $k$ connecting $S$ and
$\mathbb{N}.$

Sufficiency. If $S=S_{0}\subseteq S_{1}\subseteq\dots\subseteq
S_{k}=\mathbb{N}$ is an ${\mathrm{i}}$-chain of lenght $k$, then
$S_{1}\subseteq\dots\subseteq S_{k}=\mathbb{N}$ is an ${\mathrm{i}}$-chain of
length $k-1.$ By the induction hypothesis
$S_{1}\in\mathcal{J}^{k-1}(\mathbb{N}).$ Since $S\in\mathcal{J}(S_{1}),$ then
$S\in\mathcal{J}(\mathcal{J}^{k-1}(\mathbb{N}))=\mathcal{J}^{k}(\mathbb{N}).$
∎

Let $\mathcal{L}=\\{S\mid S\mbox{ is a numerical semigroup}\\}.$ We will say
the map
$\theta:\mathcal{L}\backslash\\{\mathbb{N}\\}\to{\mathscr{P}}(\mathbb{N})$ is
an ${\mathrm{i}}$-pertinent map if $\theta(S)$ is a nonempty
${\mathrm{i}}(S)$-pertinent set for all
$S\in\mathcal{L}\backslash\\{\mathbb{N}\\}.$

The following result shows us the large number of ${\mathrm{i}}$-pertinent
functions that exist.

######  Proposition 12.

The map
$\theta:\mathcal{L}\backslash\\{\mathbb{N}\\}\to{\mathscr{P}}(\mathbb{N})$
defined by

  1. 1.

$\theta(S)={\mathrm{PF}}(S)$ is an ${\mathrm{i}}$-pertinent map.

  2. 2.

$\theta(S)=\\{{\mathrm{F}}(S)\\}$ is an ${\mathrm{i}}$-pertinent map.

  3. 3.

$\theta(S)=\\{x\in{\mathrm{PF}}(S)\mid x\geq\frac{{\mathrm{F}}(S)}{2}\\}$ is
an ${\mathrm{i}}$-pertinent map.

  4. 4.

$\theta(S)=\\{x\in{\mathrm{PF}}(S)\mid x>{\mathrm{F}}(S)-{\mathrm{m}}(S)\\}$
is an ${\mathrm{i}}$-pertinent map.

  5. 5.

$\theta(S)=\\{x\in{\mathrm{PF}}(S)\mid x>{\mathrm{F}}(S)-\mathrm{g}(S)\\}$ is
an ${\mathrm{i}}$-pertinent map.

  6. 6.

$\theta(S)=\\{\min\\{x\in{\mathrm{PF}}(S)\mid
x>\frac{{\mathrm{F}}(S)}{2}\\}\\}$ is an ${\mathrm{i}}$-pertinent map.

If $\theta$ is an ${\mathrm{i}}$-pertinent map and $S$ is a numerical
semigroup, then we can build a sequence of numerical semigroups as follows:

  * •

$S_{0}=S,$

  * •

$S_{n+1}=\left\\{\begin{array}[]{lr}S_{n}\cup\theta(S_{n})&\mbox{if
}S_{n}\neq\mathbb{N}\\\ \mathbb{N}&\mbox{otherwise.}\end{array}\right.$

######  Theorem 13.

Let $S$ be a numerical semigroup, $\theta$ be an ${\mathrm{i}}$-pertinent map
and $\\{S_{n}\\}_{n\in\mathbb{N}}$ be the sequence defined above. Then, there
exists $\mu(\theta,S)\in\mathbb{N}$ such that $S=S_{0}\subsetneq
S_{1}\subsetneq\dots\subsetneq S_{\mu(\theta,S)}=\mathbb{N}.$ Moreover, this
chain is an ${\mathrm{i}}$-chain.

###### Proof.

If $S_{i}\neq\mathbb{N},$ then $\theta(S_{i})\neq\emptyset$ and
$\theta(S_{i})\subseteq\mathbb{N}\backslash S_{i}.$ Therefore,
$\mathrm{g}(S_{i+1})<\mathrm{g}(S_{i}).$ Thus there is
$\mu(\theta,S)\in\mathbb{N}$ such that $S=S_{0}\subsetneq
S_{1}\subsetneq\dots\subsetneq S_{\mu(\theta,S)}=\mathbb{N}.$ Moreover, as a
consequence of Corollary 9, we have that $S_{i}\in\mathcal{J}(S_{i+1})$ for
all $i\in\\{0,\dots,\mu(\theta,S)-1\\}.$ Hence, $S=S_{0}\subsetneq
S_{1}\subsetneq\dots\subsetneq S_{\mu(\theta,S)}=\mathbb{N}$ is an
${\mathrm{i}}$-chain. ∎

As a consequence of Proposition 11 and Theorem 13 we have the following
result.

######  Corollary 14.

If $S$ is a numerical semigroup, then there exists $k\in\mathbb{N}$ such that
$S\in\mathcal{J}^{k}(\mathbb{N}).$

The previous corollary allows us to give the following definition: the
complexity of a numerical semigroup $S$, denoted by ${\mathrm{C}}(S)$, is the
minimun of the set $\\{k\in\mathbb{N}\mid S\in\mathcal{J}^{k}(\mathbb{N})\\}.$
Note that $\mathbb{N}$ is the unique numerical semigroup with complexity zero.

As an immediate consequence of Proposition 11, we have the following result.

######  Proposition 15.

Let $S$ be a numerical semigroup. Then ${\mathrm{C}}(S)$ is the minimum of the
lenghts of the ${\mathrm{i}}$-chains connecting $S$ with $\mathbb{N}.$

The following result is an immediate consequence from previous proposition.

######  Corollary 16.

If $S$ is a numerical semigroup and $\theta$ is an ${\mathrm{i}}$-pertinent
map, then ${\mathrm{C}}(S)\leq\mu(\theta,S).$

We complete this section by showing the numerical semigroups with complexities
one and two. For this purpose, we need to recall the definition of ordinary
numerical semigroups: a numerical semigroup $S$ is ordinary when $S$ is equal
to $\\{0,{\mathrm{m}}(S),\rightarrow\\}.$

######  Proposition 17.

Let $S$ be a numerical semigroup. Then ${\mathrm{C}}(S)=1$ if and only if $S$
is an ordinary numerical semigroup and $S\neq\mathbb{N}.$

###### Proof.

Necessity. If ${\mathrm{C}}(S)=1,$ then $S\subsetneq\mathbb{N}$ is an
${\mathrm{i}}$-chain and $S\in\mathcal{J}(\mathbb{N})$. By Theorem 3,
${\mathrm{PF}}(S)=\mathbb{N}\setminus S$, and thus
$S=\\{0,{\mathrm{m}}(S),\rightarrow\\}$.

Sufficienty. If $S$ is an ordinary semigroup and $S\neq\mathbb{N},$ then there
is $m\in\mathbb{N}\backslash\\{0,1\\}$ such that $S=\\{0,m,\rightarrow\\}.$ It
is clear that $\\{0,m,\rightarrow\\}\subsetneq\mathbb{N}$ is an
${\mathrm{i}}$-chain. By applying now Proposition 15, we have
${\mathrm{C}}(S)=1.$ ∎

Following the notation introduced in [3], a numerical semigroup $S$ is
elementary  if ${\mathrm{F}}(S)<2\,{\mathrm{m}}(S).$ The following result is
deduced from Lemma 2.1 of [10].

######  Lemma 18.

A numerical semigroup $S$ is elementary and not ordinary if and only if
$S=\\{0,m\\}\cup A\cup\\{2m,\rightarrow\\}$ where
$m\in\mathbb{N}\backslash\\{0,1\\}$ and $A\subsetneq\\{m+1,m+2,\dots,2m-1\\}.$

######  Proposition 19.

Let $S$ be a numerical semigroup. Then ${\mathrm{C}}(S)=2$ if and only if $S$
is an elementary and not ordinary semigroup.

###### Proof.

Necessity. If ${\mathrm{C}}(S)=2,$ then $S$ is not an ordinary semigroup since
these semigroups have complexity $0$ or $1$. Moreover, by Proposition 15, we
know that there is an ${\mathrm{i}}$-chain $S=S_{0}\subsetneq S_{1}\subsetneq
S_{2}=\mathbb{N}.$ Then we deduce that ${\mathrm{C}}(S_{1})=1$ and by
Proposition 17 we have $S_{1}=\\{0,m,\rightarrow\\}$ for some
$m\in\mathbb{N}\backslash\\{0,1\\}.$ As $S\in\mathcal{J}(S_{1}),$ then
$m\leq{\mathrm{m}}(S)$ and $\\{{\mathrm{m}}(S)+m,\rightarrow\\}\subseteq S.$
Thus, ${\mathrm{F}}(S)<{\mathrm{m}}(S)+m\leq 2\,{\mathrm{m}}(S).$ Hence $S$ is
an elementary and not ordinary semigroup.

Sufficienty. If $S$ is an elementary and not ordinary semigroup, then by Lemma
18, we know that $S=\\{0,m\\}\cup A\cup\\{2m,\rightarrow\\}$ with
$m\in\mathbb{N}\backslash\\{0,1\\}$ and $A\subsetneq\\{m+1,\dots,2m-1\\}.$ It
is clear that $S\subsetneq\\{0,m,\rightarrow\\}\subsetneq\mathbb{N}$ is an
${\mathrm{i}}$-chain. By Proposition 15, ${\mathrm{C}}(S)=2.$ ∎

##  3 A formula for the complexity

Let $S$ be a numerical semigroup. By Proposition 17, we know that
${\mathrm{C}}(S)=1$ if and only if
$0\cdot{\mathrm{m}}(S)<{\mathrm{F}}(S)<1\cdot{\mathrm{m}}(S).$ Also observe
that from Proposition 19, we deduce ${\mathrm{C}}(S)=2$ if and only if
$1\cdot{\mathrm{m}}(S)<{\mathrm{F}}(S)<2\cdot{\mathrm{m}}(S).$ The following
result generalizes these two properties.

######  Theorem 20.

Let $S$ be a numerical semigroup such that $S\neq\mathbb{N}.$ Then,
${\mathrm{C}}(S)=k$ if and only if
$(k-1){\mathrm{m}}(S)<{\mathrm{F}}(S)<k{\mathrm{m}}(S).$

###### Proof.

We make this proof by induction on $k$. For $k\in\\{1,2\\}$ the result is
true, so we assume $k\geq 3$.

Necessity. If ${\mathrm{C}}(S)=k$, then, by the induction hypothesis, we have
that $(k-1){\mathrm{m}}(S)<{\mathrm{F}}(S)$. We also know that
$S\backslash\\{0\\}$ is ideal of a numerical semigroup $\Delta$ such that
${\mathrm{C}}(\Delta)=k-1$. Using the induction hypothesis, we have
$(k-2){\mathrm{m}}(\Delta)<{\mathrm{F}}(\Delta)<(k-1){\mathrm{m}}(\Delta)$.
Since $S\backslash\\{0\\}$ is an ideal of $\Delta$, we have that
$\\{{\mathrm{m}}(S)+(k-1){\mathrm{m}}(\Delta),\to\\}\subseteq S$ and
${\mathrm{m}}(\Delta)\leq{\mathrm{m}}(S)$. Hence
$\\{k{\mathrm{m}}(S),\to\\}\subseteq S$, and thus
${\mathrm{F}}(S)<k{\mathrm{m}}(S)$.

Sufficienty. If $(k-1){\mathrm{m}}(S)<{\mathrm{F}}(S)$, then, by the induction
hypothesis, ${\mathrm{C}}(S)\geq k$. Clearly
$T=S\cup\\{(k-1){\mathrm{m}}(S),\to\\}$ is a numerical semigroup. By the
induction hypothesis, it fulfills that ${\mathrm{C}}(T)\leq k-1$. It is
straightforward to prove that $S\backslash\\{0\\}$ is an ideal of $T$.
Therefore ${\mathrm{C}}(S)\leq{\mathrm{C}}(T)+1=k$ and thus
${\mathrm{C}}(S)=k$. ∎

As an immediate consequence of previous theorem we have the following result.

######  Corollary 21.

If $S$ is a numerical semigroup, then
${\mathrm{C}}(S)=\left\lfloor\frac{{\mathrm{F}}(S)}{{\mathrm{m}}(S)}\right\rfloor+1.$

######  Example 22.

Let $S=\langle
5,7\rangle=\\{0,5,7,10,12,14,15,17,19,20,21,22,24,25,\rightarrow\\}.$ Then
${\mathrm{m}}(S)=5$ and ${\mathrm{F}}(S)=23.$ By applying Corollary 21, we
have that ${\mathrm{C}}(S)=\left\lfloor\frac{23}{5}\right\rfloor+1=5.$

By Proposition 15, we know that if $S$ is a numerical semigroup then there is
an ${\mathrm{i}}$-chain of length ${\mathrm{C}}(S)$ connecting $S$ and
$\mathbb{N}.$ Our next aim in this section is to present an
${\mathrm{i}}$-chain with these conditions.

If $S$ is a numerical semigroup such that $S\neq\mathbb{N},$ then we denote by
$\gamma(S)=\\{x\in\mathbb{N}\backslash S\mbox{ such that
}\left\lfloor\frac{{\mathrm{F}}(S)}{{\mathrm{m}}(S)}\right\rfloor{\mathrm{m}}(S)\leq
x\leq{\mathrm{F}}(S)\\}.$ It is clear that the map
$\gamma:\mathcal{L}\backslash\\{\mathbb{N}\\}\to{\mathscr{P}}(\mathbb{N})$ is
an ${\mathrm{i}}$-pertinent map.

######  Proposition 23.

Let $S$ be a numerical semigroup such that
$S\neq\\{0,{\mathrm{m}}(S),\rightarrow\\}$ and $T=S\cup\gamma(S).$ The
following properties are satisfied.

  1. (1)

$T$ is a numerical semigroup.

  2. (2)

$S\backslash\\{0\\}$ is an ideal of $T.$

  3. (3)

${\mathrm{m}}(T)={\mathrm{m}}(S).$

  4. (4)

${\mathrm{C}}(T)={\mathrm{C}}(S)-1.$

###### Proof.

(1) and (2). Since $\gamma$ is an ${\mathrm{i}}$-pertinent map, $\gamma(S)$ is
a noempty ${\mathrm{i}}$-pertinent set. Therefore, $T=S\cup\gamma(S)$ is a
numerical semigroup and $S\backslash\\{0\\}$ is an ideal of $T.$

(3). Since $S\neq\\{0,{\mathrm{m}}(S),\rightarrow\\},$ then
${\mathrm{F}}(S)>{\mathrm{m}}(S)$ and so
$\gamma(S)\subseteq\\{{\mathrm{m}}(S),\rightarrow\\}.$ Hence
${\mathrm{m}}(T)={\mathrm{m}}(S).$

(4). It is clear that
$\left(\left\lfloor\frac{{\mathrm{F}}(S)}{{\mathrm{m}}(S)}\right\rfloor-1\right){\mathrm{m}}(S)<{\mathrm{F}}(T)<\left\lfloor\frac{{\mathrm{F}}(S)}{{\mathrm{m}}(S)}\right\rfloor{\mathrm{m}}(S).$
By applying that ${\mathrm{m}}(T)={\mathrm{m}}(S)$, Corollary 21 and Theorem
20, we have ${\mathrm{C}}(T)={\mathrm{C}}(S)-1.$

∎

######  Corollary 24.

If $S$ is a numerical semigroup, then ${\mathrm{C}}(S)=\mu(\gamma,S).$

We illustrate the content of previous corollary with an example.

######  Example 25.

Let $S=\langle
5,7\rangle=\\{0,5,7,10,12,14,15,17,19,20,21,22,24,25,\rightarrow\\}.$ By
Example 22, we know that ${\mathrm{C}}(S)=5.$ Associated to the numerical
semigroup $S$ and to the ${\mathrm{i}}$-pertinent map (see Theorem 13) we have
the ${\mathrm{i}}$-chain $S=S_{0}\subsetneq S_{1}\subsetneq\dots\subsetneq
S_{\mu(\gamma,S)}=\mathbb{N},$ where $S_{n+1}=S_{n}\cup\gamma(S_{n})$ for all
$n\in\\{0,\dots,\mu(\gamma,S)-1\\}.$ Specifically, we have the chain

$S=S_{0}\subsetneq S_{1}=S\cup\\{23\\}\subsetneq
S_{2}=S_{1}\cup\\{16,18\\}\subsetneq S_{3}=\\\ S_{2}\cup\\{11,13\\}\subsetneq
S_{4}=S_{3}\cup\\{6,8,9\\}\subsetneq S_{5}=\mathbb{N}.$

Corollary 24 tells us that this ${\mathrm{i}}$-chain connects $S$ and
$\mathbb{N}$ and it has minimum length. This chain is also obtained with the
function chainOfGamma of complexityOfNS.ipynb:

    gap> lGamma:=chainGamma(NumericalSemigroup(5,7));;
    gap> List(lGamma,x->MinimalGeneratingSystemOfNumericalSemigroup(x));

The output is the following list of minimal system of generators:

    [ [ 5, 7, 23 ], [ 5, 7, 16, 18 ], [ 5, 7, 11, 13 ],
    [ 5, 6, 7, 8, 9 ], [ 1 ] ]

We end this section with some questions concerning the set of pseudo-Frobenius
numbers.

######  Remark 26.

By Proposition 12, the map
$\theta:\mathcal{L}\backslash\\{\mathbb{N}\\}\to{\mathscr{P}}(\mathbb{N})$
defined by $\theta(S)={\mathrm{PF}}(S)$ is an ${\mathrm{i}}$-pertinent map.
Since $\theta(S)$ is always the largest set among all the possible ones, we
wonder if it is true that ${\mathrm{C}}(S)=\mu(\theta,S)$. Surprisingly, the
answer is not. The numerical semigroup with the smallest Frobenius number not
satisfying that property is $S=\langle 4,6,9,11\rangle$ and the
${\mathrm{i}}$-chain obtained is

$S=S_{0}\subsetneq S_{1}=\langle 2,5\rangle=S\cup\\{2,5,7\\}\subsetneq
S_{2}=\langle 2,3\rangle=S_{1}\cup\\{3\\}\subsetneq S_{3}=\mathbb{N}.$

Note that ${\mathrm{C}}(S)=\lfloor\frac{7}{4}\rfloor+1=2$, but the length of
the ${\mathrm{i}}$-chain is $3$. The next one is $\langle 5,7,9,11,13\rangle$
which has Frobenius number $8$. As we increase the Frobenius number, we obtain
more examples. In addition to the obtained examples we can obtain new ones
like for example $\langle 4,6,9\rangle$ from our first example and $\langle
5,7\rangle$ from our second example.

If we examine the numerical semigroups verifying that
${\mathrm{C}}(S)=\mu(\theta,S)$, we see that the vast majority verify this
property. Since apparently their proportion is smaller, an interesting
question is to give a characterization of the family of numerical semigroups
for which this property is not verified.

An example of a family that satisfies that adding ${\mathrm{PF}}(S)$ yields a
chain that achieves complexity is that formed by the numerical semigroups of
the form

$S_{k}=\\{0,m,2m,\dots,km\\}\cup\\{km+1,\to\\}$

with $k,m\in\mathbb{N}\backslash\\{0\\}$. For this it is sufficient to take
into account that ${\mathrm{PF}}(S_{k})=\\{(k-1)m+1,\dots,km-1\\}$ and that
$\lfloor\frac{km-1}{m}\rfloor+1=(k-1)+1=k$. The ${\mathrm{i}}$-chain obtained
is $S_{k}\subsetneq S_{k-1}\subsetneq\dots\subsetneq
S_{1}=\\{0,m,\to\\}\subsetneq\mathbb{N}$.

Consider now the numerical semigroups of the form $\\{0,4,6,2\cdot 4,3\cdot
4,\dots,k\cdot 4\\}\cup\\{4k+1,\to\\}$ with $k\geq 2$. In the
${\mathrm{i}}$-chain obtained with $\theta(S)={\mathrm{PF}}(S)$, we find the
semigroup $\langle 4,6,9,11\rangle=\\{0,4,6,8,\to\\}$. Hence, the length of
this chain is larger than their complexity. This can be generalized as
follows. Let $S=S_{0}$ be the numerical semigroup equal to
$\\{0,2k,3k,4k,\to\\}$. The set ${\mathrm{PF}}(S)$ is
$\\{k,2k+1,\dots,4k-1\\}$ and therefore
$S_{1}=S\cup{\mathrm{PF}}(S)=\\{0,k,2k,\to\\}$. The set of pseudo-Frobenius
numbers of $S_{1}$ is $\\{k+1,\dots,2k-1\\}$ and so
$S_{2}=S_{1}\cup{\mathrm{PF}}(S_{1})=\\{0,5,\to\\}$ which is an ordinary
semigroup and the length of the ${\mathrm{i}}$-chain obtained is $3$, but the
complexity of $S$ is
$\lfloor\frac{{\mathrm{F}}(S)}{m(S)}\rfloor+1=\lfloor\frac{4k-1}{2k}\rfloor+1=2$.

##  4 Numerical semigroups with a fixed multiplicity and complexity

If $m\in\mathbb{N}\backslash\\{0,1\\}$, then we denote by

$\mathcal{L}_{m}=\\{S\mid S\mbox{ is a numerical semigroup and
}{\mathrm{m}}(S)=m\\}.$

For $S\in\mathcal{L}_{m}$ define the following sequence:

  * •

$S_{0}=S,$

  * •

$S_{n+1}=\left\\{\begin{array}[]{lr}S_{n}\cup\gamma(S_{n}),&\mbox{if
}S_{n}\neq\\{0,m,\rightarrow\\}\\\
\\{0,m,\rightarrow\\},&\mbox{otherwise.}\end{array}\right.$

The following result is obtained from Proposition 23 and Corollary 24.

######  Corollary 27.

Let $m\in\mathbb{N}\backslash\\{0,1\\},$ $S\in\mathcal{L}_{m}$ and let
$\\{S_{n}\\}_{n\in\mathbb{N}}$ be the sequence defined above. Then,
$S=S_{0}\subsetneq S_{1}\subsetneq\dots\subsetneq
S_{{\mathrm{C}}(S)-1}=\\{0,m,\rightarrow\\}.$ In addition, we have the
following:

  1. 1.

$S_{i}\in\mathcal{L}_{m}$ for all $i\in\\{0,1,\dots,{\mathrm{C}}(S)-1\\}.$

  2. 2.

$S_{i}\backslash\\{0\\}$ is an ideal of $S_{i+1}$ for all
$i\in\\{0,1,\dots,{\mathrm{C}}(S)-2\\}.$

  3. 3.

${\mathrm{C}}(S_{i})={\mathrm{C}}(S)-i$ for all
$i\in\\{0,1,\dots,{\mathrm{C}}(S)-1\\}.$

A graph $G$ is a pair $(V,E)$, where $V$ is a nonempty set and $E$ is a subset
of $\\{(u,v)\in V\times V\mid u\neq v\\}.$ The elements of $V$ and $E$ are
called vertices and edges of $G$, respectively. A path, of length $n$,
connecting the vertices $u$ and $v$ of $G$ is a sequence of different edges of
the form $(v_{0},v_{1}),(v_{1},v_{2}),\ldots,(v_{n-1},v_{n})$ such that
$v_{0}=u$ and $v_{n}=v$.

We say that a graph $G$ is a tree if there exists a vertex $r$ (known as the
root of $G$) such that for any other vertex $v$ of $G$ there exists a unique
path connecting $v$ and $r$. If $(u,v)$ is an edge of the tree $G$, then we
say that $u$ is a child of $v$.

If $m\in\\{0,1\\},$ then we define the graph $G(m)$ as follows:
$\mathcal{L}_{m}$ is its set of vertices and
$(S,T)\in\mathcal{L}_{m}\times\mathcal{L}_{m}$ is an edge if
$T=S\cup\gamma(S).$

As a consequence of Corollary 27, we have the following result.

######  Corollary 28.

If $m\in\mathbb{N}\backslash\\{0,1\\},$ then $G(m)$ is a tree with root
$\\{0,m,\rightarrow\\}.$ Moreover,
$\\{S\in\mathcal{L}_{m}\mid{\mathrm{C}}(S)=k\\}=\\{S\in\mathcal{L}_{m}\mid
S\mbox{ is connected with }\\{0,m,\rightarrow\\}\mbox{through a path of length
}k-1\\}.$

It is evident that a tree can be constructed recursively by starting from the
root and connecting with an edge the vertices already constructed with their
children. We are interested in characterizing how are the children of an
arbitrary vertex of $\mathbf{G}(m)$.

######  Proposition 29.

Let $m\in\mathbb{N}\backslash\\{0,1\\}$ and $T\in\mathcal{L}_{m}.$ Then, the
set formed by all the children of $T$ in the tree $G(m)$ is

$\left\\{T\backslash A\mid\emptyset\neq
A\subseteq\left\\{x\in{\mathrm{msg}}(T)\mid
x>\left(\left\lfloor\frac{{\mathrm{F}}(T)}{{\mathrm{m}}(T)}\right\rfloor+1\right)m\right\\}\right\\}.$

###### Proof.

If $S$ is a child of $T$ in the tree $G(m),$ then $T=S\cup\gamma(S)$ and so
$S=T\backslash\gamma(S).$ It is clear that $S$ is a numerical semigroup with
complexity ${\mathrm{C}}(T)+1.$ Hence
$\emptyset\neq\gamma(S)\subseteq\left\\{x\in{\mathrm{msg}}(T)\mid
x>\left(\left\lfloor\frac{{\mathrm{F}}(T)}{{\mathrm{m}}(T)}\right\rfloor+1\right)m\right\\}.$

Conversely, if $\emptyset\neq A\subseteq\\{x\in{\mathrm{msg}}(T)\mid
x>\left(\left\lfloor\frac{{\mathrm{F}}(T)}{{\mathrm{m}}(T)}\right\rfloor+1\right)m\\},$
then
$A\subseteq\left\\{\left(\left\lfloor\frac{{\mathrm{F}}(T)}{{\mathrm{m}}(T)}\right\rfloor+1\right)m+1,\dots,\left(\left\lfloor\frac{{\mathrm{F}}(T)}{{\mathrm{m}}(T)}\right\rfloor+2\right)m-1\right\\}$,
since if $x\in{\mathrm{msg}}(T)$ then
$x\leq{\mathrm{F}}(T)+m<\left(\left\lfloor\frac{{\mathrm{F}}(T)}{{\mathrm{m}}(T)}\right\rfloor+1\right)m+m=\left(\left\lfloor\frac{{\mathrm{F}}(T)}{m}\right\rfloor+2\right)m.$
Thus, $S=T\backslash A$ is a numerical semigroup and $\gamma(S)=A.$
Consequently, $S\in\mathcal{L}_{m}$ and $S\cup\gamma(S)=T.$ Therefore, $S$ is
a child of $T.$ ∎

######  Example 30.

Next we can see the tree $G(2)$.

|  |  |  |  |  |  |  |  |  |  |
---|---|---|---|---|---|---|---|---|---|---|---
|  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |
$\textstyle{\langle 2,3\rangle}$$\textstyle{[2]}$$\textstyle{\langle
2,5\rangle\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\\{3\\}}$$\textstyle{[4]}$$\textstyle{\langle
2,7\rangle\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\\{5\\}}$$\textstyle{[6]}$$\textstyle{\langle
2,9\rangle\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\\{7\\}}$$\textstyle{[8]}$

The number $[k]$ indicates
$\left(\left\lfloor\frac{{\mathrm{F}}(T)}{2}\right\rfloor+1\right)2$ and
$\begin{array}[]{l}P\\\ \Big{\uparrow}{\\{x\\}}\\\ Q\end{array}$ means that
$Q=P\backslash\\{x\\}.$ We see that the vertices of $G(2)$ are of the form
$\langle 2,2k+1\rangle$ where $k$ is the complexity of the semigroup.

######  Example 31.

We now use Proposition 29 to obtain the tree $G(3)$.
$\textstyle{\langle 3,4,5\rangle}$$\textstyle{\,[3]}$$\textstyle{\langle
3,5,7\rangle\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\\{4\\}}$$\textstyle{\langle
3,4\rangle\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\\{5\\}}$$\textstyle{\langle
3,7,8\rangle\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\\{4,5\\}}$$\textstyle{\,[6]}$$\textstyle{\langle
3,5\rangle\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\\{7\\}}$$\textstyle{\langle
3,8,10\rangle\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\\{7\\}}$$\textstyle{\langle
3,7,11\rangle\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\\{8\\}}$$\textstyle{\langle
3,10,11\rangle\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\\{7,8\\}}$$\textstyle{\,[9]}$$\textstyle{\langle
3,8,13\rangle\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\\{10\\}}$$\textstyle{\langle
3,7\rangle\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\\{11\\}}$$\textstyle{\langle
3,11,13\rangle\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\\{10\\}}$$\textstyle{\langle
3,10,14\rangle\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\\{11\\}}$$\textstyle{\langle
3,13,14\rangle\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\\{10,11\\}}$$\textstyle{\,[12]}$

Our next aim is to present an algorithm to compute all the numerical
semigroups with a given multiplicity and complexity. For this reason we
introduce some concepts and results.

If $G=(V,E)$ is a tree and $v$ is a vertex of $G$, then the depth of $v$,
denoted by $\mathrm{d}(v)$, is the length of the only path connecting $v$ with
the root. The following result is an immediate consequence of Corollary 28.

######  Proposition 32.

If $m\in\mathbb{N}\backslash\\{0,1\\}$ and $S$ is a vertex of $G(m),$ then
$G(S)=\mathrm{d}(S)+1$.

If $G=(V,E)$ is a tree, then we denote by ${\rm N}(G,n)=\\{x\in V\mid
d(x)=n\\}.$

######  Example 33.

From Example 31, we easily deduce ${\rm N}(G(3),2)=\\{\langle
3,5\rangle,\langle 3,8,10\rangle,\\\ \langle 3,7,11\rangle,\langle
3,10,11\rangle\\}.$ Therefore, by applying Proposition 32, we have
$\\{S\in\mathcal{L}_{3}\mid{\mathrm{C}}(S)=3\\}=\\{\langle 3,5\rangle,\langle
3,8,10\rangle,\langle 3,7,11\rangle,\langle 3,10,11\rangle\\}.$

The proof of the following result is straightforward.

######  Proposition 34.

If $G=(V,E)$ is a tree and $r$ is its root, then ${\rm N}(G,0)=\\{r\\}$ and
${\rm N}(G,n+1)=\\{v\in V\mid v\mbox{ is a child of a vertex from }{\rm
N}(G,n)\\}$ for all $n\in\mathbb{N}.$

The algorithm for the calculation of the above sets is as follows.

Data: An positive integer $c$ and $m\in\mathbb{N}\backslash\\{0,1\\}.$

Result: $\\{S\in\mathcal{L}_{m}\mid{\mathrm{C}}(S)=c\\}.$

1 $A:=\\{\\{0,m,\rightarrow\\}\\}$;

2 $i:=1$;

3 if  _$i=c$_ then

4 return $A$;

5 Compute $B:=\\{S\in\mathcal{L}_{m}\mid S\mbox{ is a child of an element of
}A\\}$;

6 $A:=B$;

7 $i:=i+1$;

8 Goto line 3;

Algorithm 2 Computation of the set of numerical semigroups with multiplicity
$m$ and complexity $c$.

We proceed to illustrate how the previous algorithm works with an example.

######  Example 35.

We proceed now to compute the set
$\\{S\in\mathcal{L}_{3}\mid{\mathrm{C}}(S)=4\\}$ using the previous algorithm.

  * •

$A=\\{\\{0,3,\rightarrow\\}\\},$ $i=1.$

  * •

$A=\\{\langle 3,5,7\rangle,\langle 3,4\rangle,\langle 3,7,8\rangle\\},$ $i=2.$

  * •

$A=\\{\langle 3,5\rangle,\langle 3,8,10\rangle,\langle 3,7,11\rangle,\langle
3,10,11\rangle\\},$ $i=3.$

  * •

$A=\\{\langle 3,8,13\rangle,\langle 3,7\rangle,\langle 3,11,13\rangle,\langle
3,10,14\rangle,\langle 3,13,14\rangle\\},$ $i=4.$

Thus, $\\{S\in\mathcal{L}_{3}\mid{\mathrm{C}}(S)=4\\}=\\{\langle
3,8,13\rangle,\langle 3,7\rangle,\langle 3,11,13\rangle,\langle
3,10,14\rangle,\langle 3,13,14\rangle\\}.$

This list is obtained with the function NSWithMultiplicityAndComplexity of
complexityOfNS.ipynb:

    gap> l34:=NSWithMultiplicityAndComplexity(3,4);;
    gap> List(l34,x->MinimalGeneratingSystemOfNumericalSemigroup(x));

The result obtained is:

    [ [ 3, 8, 13 ], [ 3, 7 ], [ 3, 11, 13 ], [ 3, 10, 14 ],
    [ 3, 13, 14 ] ]

The following result easily follows.

######  Lemma 36.

If $S$ is a numerical semigroup, then $T=(\\{{\mathrm{m}}(S)\\}+S)\cup\\{0\\}$
is again a numerical semigroup. In addition,
${\mathrm{m}}(T)={\mathrm{m}}(S)$,
${\mathrm{F}}(T)={\mathrm{F}}(S)+{\mathrm{m}}(S)$ and
${\mathrm{C}}(T)={\mathrm{C}}(S)+1.$

The following proposition can be deduced from previous lemma.

######  Proposition 37.

The map
$f:\\{S\in\mathcal{L}_{m}\mid{\mathrm{C}}(S)=c\\}\to\\{S\in\mathcal{L}_{m}\mid{\mathrm{C}}(S)=c+1\\}$
defined by $f(S)=(\\{{\mathrm{m}}(S)\\}+S)\cup\\{0\\}$, is injective.

As an immediate consequence from above proposition, we have the following
result.

######  Corollary 38.

If $c\in\mathbb{N}$ and $m\in\mathbb{N}\backslash\\{0\\}$, then the
cardinality of $\\{S\in\mathcal{L}_{m}\mid{\mathrm{C}}(S)=c\\}$ is less than
or equal to the cardinality of
$\\{S\in\mathcal{L}_{m}\mid{\mathrm{C}}(S)=c+1\\}.$

## References

  * [1] R. Apéry,  _Sur les branches superlinéaires des courbes algébriques,_ C.R. Acad. Sci. Paris 222 (1946), 1198–2000.
  * [2] V. Barucci, D. E. Dobbs and M. Fontana,  _Maximality Properties in Numerical Semigroups and Applications to One-Dimensional Analitycally Irreducible Local Domains,_ Memoirs Amer. Math. Soc. 598 (1997).
  * [3] V. Blanco and J. C. Rosales,  _The set of numerical semigroups of a given genus,_ Forum Math. 85 (2012), 255–267.
  * [4] M. Delgado, P. A. Garcia-Sanchez and J. Morais,  _NumericalSgps, a package for numerical semigroups_ ,  Version 1.2.0. https://gap-packages.github.io/numericalsgps, Apr 2019. Refereed GAP package.
  * [5] A. H. Clifford,  _Extensions of semigroups,_ Trans. Amer. Math. Soc. 68 (1950), 165–173.
  * [6] J. I. García-García, D. Marín-Aragón, A. Sánchez-R.-Navarro, and A. Vigneron-Tenorio,  CommutativeMonoids, computations in finitely generated commutative monoids.  Available at https://github.com/D-marina/CommutativeMonoids.
  * [7] P. A. Grillet,  _Semigroups. An Introduction to the structure theory,_ Marcel Dekker, New York, 1995.
  * [8] J. L. Ramírez Alfonsín,  _The Diophantine Frobenius Problem,_ Oxford University Press, 2005.
  * [9] J. C. Rosales, and M. B. Branco,  _Numerical Semigroups that can be expressed as an intersection of symmetric numerical semigroups,_ J. Pure Appl. Algebra 171 (2002), 303–314.
  * [10] J. C. Rosales, M. B. Branco,  _On the enumeration of the set of elementary numerical semigroups with fixed multiplicity, Frobenius number or genus,_ Kragujevac J. Math. 46 (2022), 433–442.
  * [11] J. C. Rosales and P. A. García-Sánchez,  _Numerical Semigroups,_ Developments in Mathematics, Vol. 20, Springer, New York, 2009.
  * [12] J. J. Sylvester,  _Problem 7382,_ Educat. Times J. College Preceptors New Ser. 36 (1883), 177.