Discrete and Algorithmic Mathematics Red de Matemática Discreta y Algorítmica

Recent trends IV: From a naive question to a long-standing conjecture

04 May 2024

Let’s assume the reader was captured by the title of this post to browse a few sentences. I have to apologise for two little lies in it.

Firstly, the question I want to discuss is probably not naive. What I can say is that it is challenging. A great mathematician posed the question when computers were still barely available, thus without access to some hint that finding a counter-example would not be accessible shortly. He, for sure, suspected that finding a proof would require some profound research.

Secondly, referring to the conjecture as a long-standing one may sound exaggerated. Nevertheless, I estimate that half of this post’s readers were born later than the question, now called conjecture, was stated, and I count on their forgiveness for this overstatement. By referring to the fact that the conjecture is a relevant topic in a young but very active research area, I hope to count on the forgiveness of the remaining readers.

Writing a blog post rather than a scientific paper leaves me free to not disclose from the beginning what I am about to discuss. However, since the post is scientifically motivated, I will eventually have to stop breaking the rules.

My aim is to talk about a question on numerical semigroups posed by Herbert Wilf (Wilf 1978) in the late seventies. This question deserves to be included in the gallery of easy-to-state but dangerous problems. That it is easy to state will soon become apparent. It is dangerous because one may spend a lot of time thinking that a solution is just around the corner without reaching that corner. Fortunately, as happens with any problem that attracts the scientific community’s attention for a long time, partial results and distinct approaches give rise to other problems that have an interest in themselves. In this sense, Wilf’s conjecture is responsible for a relevant part of today’s research activity in numerical semigroups.

I can no longer avoid the statement of the question. Let $\mathbb{N} = \lbrace0,1,2,\ldots\rbrace$. A numerical semigroup $S\subseteq \mathbb{N}$ is a cofinite submonoid of $\mathbb{N}$ under addition, that is, $S$ is closed under addition, contains $0$ and $\mathbb{N}\setminus S$ is not infinite.

Next, I will need a few well-known facts and parameters attached to numerical semigroups. The parameters’ names may look funny to readers without previous contact with the area. In many cases, these names originate in the area of algebraic geometry, one of the many areas of mathematics where numerical semigroups appear. The books (Rosales and García Sánchez 2009; Assi, D’Anna, and García-Sánchez 2020) provide good introductions to the basics.

Let $S$ be a numerical semigroup. Denote by $m$ the smallest positive element of $S$ and by $c$ the biggest integer such that $c-1$ does not belong to $S$. The elements $m$ and $c$ are known as the multiplicity and the conductor of $S$, respectively. Elements of $S$ smaller than its conductor are known as left elements. The set of left elements is denoted $L$. The cardinality of the set $\mathbb{N}\setminus S$ is called the genus of $S$. It is well known that a numerical semigroup has a unique minimal set of generators. Its cardinality is called the embedding dimension and is denoted $e$. There are algorithms to compute the parameters just introduced, among many others. The GAP (GAP 2024) package numericalsgps (M. Delgado, Garcia-Sanchez, and Morais 2022) was created to calculate with numerical semigroups. Jointly with P. A. García-Sánchez, we maintain this package and, by frequent updates to include the best algorithms known, the package reflects the state of the art in the area.

The number $W(S)=e|L|-c$ is the Wilf number of $S$. In 1978, Wilf (Wilf 1978) posed the question of whether the inequality $W(S)\ge 0$ holds for all numerical semigroups. This intriguing question is nowadays known as Wilf’s conjecture. Many researchers have tackled the problem and used several approaches. As for up to 2020, a survey I wrote (Manuel Delgado 2020) gives an account of relevant developments.

For example, Eliahou (Eliahou 2018) showed, in a paper published in the J. Eur. Math. Soc., that Wilf’s conjecture is satisfied by all numerical semigroups such that $c\le 3m$. We call these semigroups generic since they are the vast majority of numerical semigroups, in the sense that the proportion of such semigroups goes to $1$ as the genus goes to infinity, as proved by Zhai (Zhai 2013). Zhai used this fact as an intermediate step to prove that, denoting the golden ratio by $\varphi =\frac{1+\sqrt{5}}{2}\simeq 1.618$ and representing by $n_g$ the number of numerical semigroups of genus $g$, $n_{g+1}$ approaches $\varphi\cdot n_{g}$ as $g$ tends to infinity. Thus the sequence $(n_g)$ behaves like the Fibonacci sequence, as conjectured by Bras-Amorós (Bras-Amorós 2008).

In his proof of the above-mentioned result, Eliahou associated with a numerical semigroup $S$ a number that is similar to Wilf’s number. We denote it $E(S)$. Eliahou proved that if $E(S)$ is non-negative, then so is $W(S)$ and then proved that generic semigroups have non-negative Eliahou numbers, thus concluding that generic semigroups satisfy Wilf’s conjecture.

Since generic semigroups are the vast majority of numerical semigroups, the probability of finding one with a negative Eliahou number by chance is almost null. However, numerical semigroups with negative Eliahou numbers exist. Eliahou exhibited the existing five numerical semigroups with genus up to $60$ (these are over $10^{13}$, see (Fromentin and Hivert 2016)) with $E(S)=-1$. Currently, several infinite families of numerical semigroups with negative Eliahou numbers (but positive Wilf numbers) are known (see (Manuel Delgado 2018; Eliahou and Fromentin 2019)). Bras-Amorós (Bras-Amorós 2024) recently studied semigroups with negative Eliahou numbers and used the results to conclude that Wilf’s conjecture holds for all numerical semigroups up to genus $66$.

Another result of Eliahou (Eliahou 2020) states that numerical semigroups such that $e\ge m/3$ are Wilf. Also the proportion of numerical semigroups in this class goes to $1$ as the genus goes to infinity. This fact was proved by Kaplan and Singhal (Kaplan and Singhal 2023), answering a question raised in (Manuel Delgado 2019) and showing that Eliahou’s result gives another asymptotic proof of Wilf’s conjecture.

The family of numerical semigroups such that $e\ge m/3$ is well suited for computations and an idea raised in (Manuel Delgado 2019) led, in joint work with Eliahou and Fromentin (Manuel Delgado, Eliahou, and Fromentin 2023), to extend the verification of Wilf’s conjecture from genus $66$ up to genus $100$.

Exact computations of $n_g$ up to genus $g=75$ (see (Manuel Delgado, Eliahou, and Fromentin 2023)) and the referred Fibonacci-like behaviour of the sequence $(n_g)$ leads to the following estimate for the number of numerical semigroups up to genus $100$: $6.78\times 10^{21}$. An exhaustive verification of Wilf’s conjecture for this huge number of numerical semigroups would require more than 4000 years s far from being doable by today’s computational means,

We achieved the verification by combining three main ingredients: Theory (mainly Eliahou’s result settling Wilf’s conjecture in the case $e \ge m/3$); an efficient trimming of the tree of numerical semigroups identifying and cutting out irrelevant subtrees; and the implementation of a fast parallelised algorithm for the construction up to a given genus.

For numerical semigroups satisfying $c\in m\mathbb{N}$ Eliahou (Eliahou 2024) extended the result to $e\ge m/4$. By using the same techniques but improving the efficiency of trimming, we extended the verification of Wilf’s conjecture for numerical semigroups satisfying $c\in m\mathbb{N}$ up to genus $120$.

References

  1. Assi, Abdallah, Marco D’Anna, and Pedro A García-Sánchez. 2020. Numerical Semigroups and Applications. RSME Springer series 3. Springer.
  2. Bras-Amorós, Maria. 2008. “Fibonacci-Like Behavior of the Number of Numerical Semigroups of a Given Genus.” Semigroup Forum 76 (2): 379–84.
  3. Bras-Amorós, Maria. 2024. “On the Seeds and the Great-Grandchildren of a Numerical Semigroup.” Math. Comp. 93 (345): 411–41.
  4. Delgado, Manuel. 2018. “On a Question of Eliahou and a Conjecture of Wilf.” Math. Z. 288 (1-2): 595–627.
  5. Delgado, Manuel. 2019. “Trimming the Numerical Semigroups Tree to Probe Wilf’s Conjecture to Higher Genus.” arXiv e-Prints.
  6. Delgado, Manuel. 2020. “Conjecture of Wilf: A Survey.” In Numerical Semigroups, edited by V. Barucci, S. Chapman, M. D’Anna, and R. Fröberg, 40:39–62. Springer INdAM Ser. Springer, Cham.
  7. Delgado, Manuel, Shalom Eliahou, and Jean Fromentin. 2023. “A Verification of Wilf’s Conjecture up to Genus 100.” arXiv e-Prints.
  8. Delgado, M., P. A. Garcia-Sanchez, and J. Morais. 2022. “NumericalSgps, a Package for Numerical Semigroups, Version 1.3.1.” <http://www.gap-system.org/Packages/numericalsgps.html>.
  9. Eliahou, Shalom. 2018. “Wilf’s Conjecture and Macaulay’s Theorem.” J. Eur. Math. Soc. (JEMS) 20 (9): 2105–29.
  10. Eliahou, Shalom. 2020. “A Graph-Theoretic Approach to Wilf’s Conjecture.” Electron. J. Combin. 27 (2): Article No P2.15, 31 pages.
  11. Eliahou, Shalom. 2024. “Divsets, numerical semigroups and Wilf’s conjecture.” HAL.
  12. Eliahou, Shalom, and Jean Fromentin. 2019. “Near-Misses in Wilf’s Conjecture.” Semigroup Forum 98 (2): 285–98.
  13. Fromentin, Jean, and Florent Hivert. 2016. “Exploring the Tree of Numerical Semigroups.” Math. Comp. 85 (301): 2553–68.
  14. GAP. 2024. *GAP – Groups, Algorithms, and Programming, Version 4.13.0*. The GAP Group. <https://www.gap-system.org>.
  15. Kaplan, Nathan, and Deepesh Singhal. 2023. “The Expected Embedding Dimension, Type and Weight of a Numerical Semigroup.” Enumer. Comb. Appl. 3 (2): Paper No. S2R14, 28.
  16. Rosales, J. C., and P. A. García Sánchez. 2009. Numerical Semigroups. Vol. 20. Developments in Mathematics. Springer, New York.
  17. Wilf, Herbert S. 1978. “A Circle-of-Lights Algorithm for the ‘Money-Changing Problem’.” Amer. Math. Monthly 85 (7): 562–65.
  18. Zhai, Alex. 2013. “Fibonacci-Like Growth of Numerical Semigroups of a Given Genus.” Semigroup Forum 86 (3): 634–62.

The author of this post, Manuel Delgado, is an associate professor at Centro de Matemática da Universidade do Porto.

Related posts