Probing Wilf's conjecture up to a high genus

A numerical semigroup is just a subset of the nonnegative integers (\(\mathbb N\)) that is closed under addition, contains 0 and has finite complement in \(\mathbb N\). Despite being so simple mathematical objects, numerical semigroups hide very interesting combinatorial and computational problems.

 

Let \(S\) be a numerical semigroup. The largest integer that does not belong to \(S\) is its Frobenius number \(F(S)\). A numerical semigroup \(S\) has a unique minimal generating set \(P(S)\), which is finite. Let \(L(S)\) be the set of elements of \(S\) up to \(F(S)\).

 

In 1978 Wilf asked (in an equivalent form) whether the number \(W(S)=|L(S)||P(S)|-c(S)\) is non negative, for any numerical semigroup \(S\). The number \(W(S)\) is nowadays known as the Wilf number of \(S\) and the whole community is convinced that it is indeed nonnegative for any \(S\). Many partial results point in this direction.

 

The genus of \(S\) is the number of positive integers that do not belong to \(S\). All the over \(10^{13}\) numerical semigroups of genus up to 60 have non negative Wilf number. The estimated number of numerical semigroups of genus up to 100 is aproximately \(42\cdot 10^{20}\). An exaustive verification that all those numerical semigroups of genus up to 100 have nonnegative Wilf number (or the search for all the counter-examples among them) is completely out of reach, since such a computation would last for over 5000 years by using the presently available means. My aim is to show how to bring some theory into play in order to probe Wilf's conjecture up to genus 100, say. Some deep results by \(S\). Eliahou will be used; the records are to be broken in a joint work with J. Fromentin.

Date and Venue

Start Date
Venue
Room FC1 030, DMat-FCUP
End Date

Speaker

Manuel Delgado

Speaker's Institution

(CMUP-FCUP)

Files

Area

Semigroups, Automata and Languages

Financiamento