Contact
cdoneill «at» sdsu.edu
GMCS Building, Room 570
Math & Stats Department
San Diego State University
5500 Campanile Dr
San Diego, CA 92182
U.S.A.
What is the Kunz Polyhedron?
Consider, for a moment, the hexagon embedded in \(\mathbb R^3\) with vertices \[(1,2,3), \quad (1,3,2), \quad (3,1,2), \quad (3,2,1), \quad (2,3,1), \quad (2,1,3).\] Since these vertices lie in the hyperplane \(x_1 + x_2 + x_3 = 6\), this is indeed a "flat" (i.e., 2-dimensional) shape. The 2-dimensional picture of the hexagon below is obtained by "looking at" the hexagon from above this hyperplane.
Notice that each edge connects 2 vertices whenever their coordinates differ by a transposition of two coordinates that differ by 1 (e.g., swapping the "2" and "3" in \((3,1,2)\) yields the adjacent vertex \((2,1,3)\)). If we instead label each vertex with the expression "\(a | b | c\)" to indicate a 1 is placed in the \(a\)'th coordinate, the 2 is placed in the \(b\)'th coordinate, and a 3 is placed in the \(c\)'th coordinate (as shown in light blue above), we see each edge corresponds to an adjacent transposition (this is known as the inverse permutation to the one in the coordinates).
Let's play the same game in one dimension higher. Consider the 24 points in \(\mathbb R^4\) obtained by permuting the coordinates of the point \((1, 2, 3, 4)\). These all lie in the hyperplane \(x_1 + x_2 + x_3 + x_4 = 10\), and form the vertices of a 3-dimensional polyhedron, depicted below. Just as in the hexagon example above, if we label each vertex with the "inverse" permutation, each edge corresponds to an adjacent transposition. This shape is known as the permutohedron, and there is one in each dimension: the \(d-1\) dimensional permutohedron lives in \(\mathbb R^d\) and has \(d!\) vertices, each obtained by permuting the coordinates of the point \((1, 2, \ldots, d)\).
The above examples illustrate an interesting phenomenon: the geometry of the permutohedron naturally identifies adjacent transpositions as important to the study of permutations. Moreover, the (geometric) fact that any two vertices of a polyhedron are connected by a sequence of edges yields a known fact from combinatorics: any two permutations differ by a sequence of adjacent transpositions (or, stated algebraically, adjacent transpositions generate the permutation group). There are many other examples of this phenomenon, such as the hypercube (whose vertices correspond to subsets of \(\{1,2,\ldots,n\}\)) and the associahedron (a relative of the permutohedron). In each of the polyhedra in these families, the vertices are in bijective correspondence with a well-studied combinatorial object, and the faces naturally highlight structural similarities therein.
Kunz polyhedra is another such family, one whose corresponding combinatorial objects are numerical semigroups. In each dimension \(m \ge 3\), there is a polyhedron \(P_m \subset \mathbb R^{m-1}\), shaped like a pointed cone, for which each point in \(P_m \cap \mathbb Z_{\ge 1}^{m-1}\) corresponds to a numerical semigroup \(S\) with smallest generator \(m\). Let us begin with the case \(m = 3\), so that \(P_3 \subset \mathbb R^2\) can be easily drawn. This polyhedron is depicted below, and has bounding inequalities \(2x_1 \ge x_2\) and \(2x_2 + 1 \ge x_1.\)
Each point \((x_1,x_2) \in P_3 \cap \mathbb Z_{\ge 1}^2\) corresponds to the numerical semigroup \[S = \langle 3, 3x_1 + 1, 3x_2 + 2 \rangle.\] For example, the point \((5,4)\), which lies in the interior of \(P_3\), corresponds to \(S = \langle 3, 16, 14 \rangle = \langle 3, 14, 16 \rangle\), while the point \((3,6)\), which lies on the upper boundary of \(P_3\), corresponds to \(S = \langle 3, 10, 20 \rangle = \langle 3, 10 \rangle\). The latter example illustrates what makes the points on the boundary of \(P_3\) special: their corresponding numerical semigroups have only 2 minimal generators, while any point in the interior of \(P_3\) corresponds to a numerical semigroup with 3 minimal generators.
Now, let's explore \(P_4 \subset \mathbb R^3\), depicted below with the cross section \(x_1 + x_2 + x_3 = 12\) highlighted and the 4 bounding inequalities \[2x_1 \ge x_2, \qquad x_1 + x_2 \ge x_3, \qquad x_2 + x_3 + 1 \ge x_1 \qquad \text{and} \qquad 2x_3 + 1\ge x_2\] labeled on the respective sides they bound.
Each integer point in the cross section corresponds to a numerical semigroup (each having exactly 12 gaps) via the bijective correspondence \[ (x_1, x_2, x_3) \in P_4 \cap \mathbb Z_{\ge 1}^3 \qquad \leftrightsquigarrow \qquad S = \langle 4, 4x_1 + 1, 4x_2 + 2, 4x_3 + 3 \rangle. \] Of these 18 points, \((2,4,6)\) is the only one that lies on an extremal ray, and it corresponds to the numerical semigroup \(S = \langle 4, 9 \rangle\) with 2 minimal generators. The remaining boundary points are \[ (3,6,3), \quad (5,5,2), \quad (5,1,6), \quad (4,2,6), \quad \text{and} \quad (3,3,6), \] each of which lives on a flat (i.e., 2-dimensional) face of \(P_4\) but not on an extremal ray, and each corresponds to a numerical semigroup with exactly 3 minimal generators. The remaining 12 points in the cross section correspond to numerical semigroups with 4 minimal generators (the largest possible number of minimal generators when the smallest generator is 4).
More generally, the integer points in \(P_m \cap \mathbb Z_{\ge 1}^{m-1}\) have a natural bijective correspondence \[ (x_1, x_2, \ldots, x_{m-1}) \in P_m \cap \mathbb Z_{\ge 1}^{m-1} \qquad \longmapsto \qquad S = \langle m, mx_1 + 1, mx_2 + 2, \ldots, mx_{m-1} + (m-1) \rangle \] to the numerical semigroups with smallest generator \(m\). To see the map in the reverse direction, given a numerical semigroup \(S\), each \(x_i\) is chosen to equal the number of gaps of \(S\) equivalent to \(i\) modulo \(m\). Equivalently, one can require that for each \(i\), the value \(a_i = mx_i + i \in S\) is the smallest element of \(S\) equivalent to \(i\) modulo \(m\). For example, if \(S = \langle 6, 9, 20\rangle\) is the McNugget semigroup, one can check that \(a_0 = 0\), \(a_1 = 49\), \(a_2 = 20\), \(a_3 = 9\), \(a_4 = 40\), and \(a_5 = 29\) are the smallest elements of \(S\) in their respective equivalence classes modulo 6, meaning \(S\) corresponds to the point \((8,3,1,6,4) \in P_6\). As expected, there are exactly 3 gaps equivalent to 2 modulo 6, namely \(2, 8, 14 \notin S\), while \(3 \notin S\) is the only gap equivalent to 3 modulo 6. Additionally, it is not a coincidence that \(x_1 = 8\) is the largest coordinate and the list \(1, 7, 13, \ldots, 43 \notin S\) of gaps equivalent to 1 modulo 6 terminates with the Frobenius number of \(S\). (The set \(\{0, a_1, \ldots, a_{m-1}\}\) is known as the Apéry set of \(S\), and plays a central role in computational problems).
We can also use this map to identify the inequalities of \(P_m\). Continue the notation from the previous paragraph, wherein each \(a_i\) detotes the smallest element of \(S\) equivalent to \(i\) modulo \(m\). The key observation is that \(a_i + a_j \in S\) is equivalent to \(i+j\) modulo \(m\), and thus must be at least as large as the smallest element in that equiavlence class (either \(a_{i+j}\) or \(a_{i+j-m}\), depending on whether or not \(i+j < m\)). This yields the general definition of the Kunz polyhdron \(P_m \subset \mathbb R^{m-1}\) via bounding inequalities \[ \begin{array}{r@{}c@{}l@{\qquad}l@{\qquad}l} x_i + x_j &\ge& x_{i+j} & \text{for} & 1 \le i \le j \le m-1 \qquad \text{with} \qquad i + j < m, \\ x_i + x_j + 1 &\ge& x_{i+j-m} & \text{for} & 1 \le i \le j \le m-1 \qquad \text{with} \qquad i + j > m, \end{array} \] which coincides with the inequalities for \(P_3\) and \(P_4\) given above. It turns out the only point satisfying every inequality above with equality is \((-\tfrac{1}{m}, -\tfrac{2}{m}, \ldots, -\tfrac{m-1}{m})\), which implies \(P_m\) is a pointed cone translated so that this rational point is its vertex.
As hinted above, if two points lie on the same face of \(P_m\), their corresponding numerical semigroups have some algebraic and combinatorial properties in common (e.g., the same number of minimal generators, and the same number of minimal relations between the generators). However, as the Kunz polyhedron is relatively new, much of the connection between its geometric structure and the numerical semigroups its points correspond to has yet to be explored.
Some of the 2022 SDSU Math REU projects will explore the geometry of the Kunz polyhedron and its connections to algebraic properties of numerical semigroups.
Further Reading
Wilf's conjecture in fixed multiplicity
(with Winfried Bruns, Pedro García-Sánchez, and Dane Wilbourne)
International Journal of Algebra and Computation 30 (2020), no. 4, 861-882. [doi] [arXiv:1903.04342]
Numerical semigroups, polyhedra, and posets I: the group cone
(with Nathan Kaplan)
to appear, Combinatorial Theory. [arXiv:1912.03741]
Numerical semigroups, polyhedra, and posets II: locating certain families of semigroups
(with Jackson Autry, *Abigail Ezell, *Tara Gomes, *Christopher Preuss, *Tarang Saluja, and *Eduardo Torres Davila)
to appear, Advances in Geometry. [arXiv:1912.04460]
Numerical semigroups, polyhedra, and posets III: minimal presentations and face dimension
(with Tara Gomes and *Eduardo Torres Davila)
[arXiv:2009.05921]