Wilf's conjecture on numerical semigroups

A numerical semigroup is a set of non-negative integers that contains 0, is closed under addition and misses only finitely many numbers. In 1978 Herbert Wilf conjectured an inequality relating the number of generators to how dense the semigroup is below its largest gap; it has been checked for every semigroup with up to 60 gaps and proved in many special cases. The task is to find a counterexample or to prove it.

Problem

Let $S \subseteq \mathbb{N} = \{0, 1, 2, \dots\}$ be a numerical semigroup: $0 \in S$, $S + S \subseteq S$, and $\mathbb{N} \setminus S$ is finite and nonempty. Write

• $c(S)$ for the conductor, the least $c$ with $\{c, c+1, \dots\} \subseteq S$, which is one more than the largest gap;
• $e(S)$ for the embedding dimension, the size of the unique minimal generating set;
• $n(S) = \#\{ s \in S : s < c(S) \}$ for the number of elements below the conductor.

Wilf's conjecture. $e(S)\, n(S) \ge c(S)$ for every numerical semigroup $S$.

Task. Find a numerical semigroup with $e(S)\, n(S) < c(S)$, or prove the inequality.

For example, $S = \langle 5, 7, 9 \rangle$ has gaps $1, 2, 3, 4, 6, 8, 11, 13$, so $c = 14$, $e = 3$ and $n = 6$, and indeed $3 \cdot 6 \ge 14$.

Background

Wilf asked the question in a 1978 note on the money-changing (Frobenius) problem [1]. Epoch describes it as a strengthening of the classical coin problem, with connections to commutative algebra and algebraic geometry. Delgado's survey remarks that its simple statement makes it a "dangerous" problem, one on which a researcher risks spending much time without success [4].

What is known

• Every numerical semigroup with at most 60 gaps satisfies the conjecture, by exhaustive computation over the tree of numerical semigroups (Fromentin and Hivert, 2016) [2].
• It holds whenever the conductor is at most three times the multiplicity, $c(S) \le 3\, m(S)$, where $m(S)$ is the smallest positive element (Eliahou, 2018) [3]. By a theorem of Zhai, the proportion of semigroups with this property among those with $g$ gaps tends to 1 as $g \to \infty$ [4].
• It holds for embedding dimension at most 3 (Fröberg, Gottlieb and Häggkvist) and for many other families collected in Delgado's survey [4].

What would count as progress

• The generators of a semigroup with $e(S)\, n(S) < c(S)$. For moderate multiplicity the semigroup is built directly; for very large multiplicity, a certificate also lists the Apéry set $w_0, \dots, w_{m-1}$ ($w_r$ the least element of $S$ congruent to $r$ modulo $m$) with a predecessor link for each element, from which all invariants follow.
• Epoch scores submissions with its own verifier on a JSON certificate: the generators, and when the multiplicity exceeds 200000, the Apéry set and predecessor links.
• Extending the verified range of genus, or proving the conjecture for new infinite classes, is also progress.

References

1. H. S. Wilf, A circle-of-lights algorithm for the "money-changing problem", Amer. Math. Monthly 85 (1978), 562–565. doi:10.1080/00029890.1978.11994639
2. J. Fromentin and F. Hivert, Exploring the tree of numerical semigroups, Math. Comp. 85 (2016), 2553–2568. doi:10.1090/mcom/3075
3. S. Eliahou, Wilf's conjecture and Macaulay's theorem, J. Eur. Math. Soc. 20 (2018), 2105–2129. doi:10.4171/JEMS/807
4. M. Delgado, Conjecture of Wilf: a survey, in Numerical Semigroups, Springer INdAM Series (2020), 39–62. doi:10.1007/978-3-030-40822-0_4 (arXiv:1902.03461)

Source

Imported from FrontierMath: Open Problems, numerical-semigroups, curated by Epoch AI. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.