Articles producció científica> Enginyeria Informàtica i Matemàtiques

ON THE SEEDS AND THE GREAT-GRANDCHILDREN OF A NUMERICAL SEMIGROUP

  • Identification data

    Identifier: imarina:9329031
    Authors:
    Bras-Amorós, M
    Abstract:
    We present a revisit of the seeds algorithm to explore the semigroup tree. First, an equivalent definition of seed is presented, which seems easier to manage. Second, we determine the seeds of semigroups with at most three left elements. And third, we find the great-grandchildren of any numerical semigroup in terms of its seeds. The the right-generators descendant (RGD) algorithm is the fastest known algorithm at the moment. But if one compares the originary seeds algorithm with the RGD algorithm, one observes that the seeds algorithm uses more elaborated mathematical tools while the RGD algorithm uses data structures that are better adapted to the final C implementations. For genera up to around one half of the maximum size of native integers, the newly defined seeds algorithm performs significantly better than the RGD algorithm. For future compilators allowing larger native sized integers this may constitute a powerful tool to explore the semigroup tree up to genera never explored before. The new seeds algorithm uses bitwise integer operations, the knowledge of the seeds of semigroups with at most three left elements and of the great-grandchildren of any numerical semigroup, apart from techniques such as parallelization and depth first search as wisely introduced in this context by Fromentin and Hivert [Math. Comp. 85 (2016) pp. 2553-2568]. The algorithm has been used to prove that there are no Eliahou semigroups of genus 66, hence proving the Wilf conjecture for genus up to 66. We also found three Eliahou semigroups of genus 67. One of these semigroups is neither of Eliahou-Fromentin type, nor of Delgado's type. However, it is a member of a new family suggested by Shalom Eliahou.
  • Others:

    Author, as appears in the article.: Bras-Amorós, M
    Department: Enginyeria Informàtica i Matemàtiques
    URV's Author/s: Bras Amoros, Maria
    Keywords: Conjecture
    Abstract: We present a revisit of the seeds algorithm to explore the semigroup tree. First, an equivalent definition of seed is presented, which seems easier to manage. Second, we determine the seeds of semigroups with at most three left elements. And third, we find the great-grandchildren of any numerical semigroup in terms of its seeds. The the right-generators descendant (RGD) algorithm is the fastest known algorithm at the moment. But if one compares the originary seeds algorithm with the RGD algorithm, one observes that the seeds algorithm uses more elaborated mathematical tools while the RGD algorithm uses data structures that are better adapted to the final C implementations. For genera up to around one half of the maximum size of native integers, the newly defined seeds algorithm performs significantly better than the RGD algorithm. For future compilators allowing larger native sized integers this may constitute a powerful tool to explore the semigroup tree up to genera never explored before. The new seeds algorithm uses bitwise integer operations, the knowledge of the seeds of semigroups with at most three left elements and of the great-grandchildren of any numerical semigroup, apart from techniques such as parallelization and depth first search as wisely introduced in this context by Fromentin and Hivert [Math. Comp. 85 (2016) pp. 2553-2568]. The algorithm has been used to prove that there are no Eliahou semigroups of genus 66, hence proving the Wilf conjecture for genus up to 66. We also found three Eliahou semigroups of genus 67. One of these semigroups is neither of Eliahou-Fromentin type, nor of Delgado's type. However, it is a member of a new family suggested by Shalom Eliahou.
    Thematic Areas: Mathematics, applied Matemática / probabilidade e estatística Interdisciplinar Computational mathematics Ciência da computação Applied mathematics Algebra and number theory
    licence for use: https://creativecommons.org/licenses/by/3.0/es/
    Author's mail: maria.bras@urv.cat
    Author identifier: 0000-0002-3481-004X
    Record's date: 2024-08-03
    Papper version: info:eu-repo/semantics/acceptedVersion
    Link to the original source: https://www.ams.org/journals/mcom/2024-93-345/S0025-5718-2023-03881-9/
    Licence document URL: https://repositori.urv.cat/ca/proteccio-de-dades/
    Papper original source: Mathematics Of Computation. 93 (345): 411-441
    APA: Bras-Amorós, M (2024). ON THE SEEDS AND THE GREAT-GRANDCHILDREN OF A NUMERICAL SEMIGROUP. Mathematics Of Computation, 93(345), 411-441. DOI: 10.1090/mcom/3881
    Article's DOI: 10.1090/mcom/3881
    Entity: Universitat Rovira i Virgili
    Journal publication year: 2024
    Publication Type: Journal Publications
  • Keywords:

    Algebra and Number Theory,Applied Mathematics,Computational Mathematics,Mathematics, Applied
    Conjecture
    Mathematics, applied
    Matemática / probabilidade e estatística
    Interdisciplinar
    Computational mathematics
    Ciência da computação
    Applied mathematics
    Algebra and number theory
  • Documents:

  • Cerca a google

    Search to google scholar