============================================================================= FPSAC/SFCA '94 - Open Problem Proposed by Einar Steingrimsson e-mail: einar@math.chalmers.se Matematiska Institutionen CTH & GU 412 96 Goteborg Sweden (Feb. 19, '94) ----------------------------------------------------------------------------- %%%%%%% This is a plain text file concatenated with a LaTeX file with %%%%% %%%%%%% further information about the problem %%%%% ----------------------------------------------------------------------------- Classifying Ehrhart polynomials of lattice simplices The problem is to classify Ehrhart polynomials of lattice simplices or, more exactly, their Ehrhart h^*-polynomials (or delta-polynomials/vectors). For definitions and some properties of these, see the Latex-file at the end of this file (which also contains more technical information on the problem). The crucial part in our approach to the problem is to replace each lattice simplex by a matrix in Hermite canonical form. This approach was devised by Richard Stanley, and used by him to find a counterexample to the conjecture (of T. Hibi?) that the h^*-vector of a d-dimensional lattice simplex satisfied h_i \geq h_{d+1-i}, where i \leq d/2. This reduces the problem to a simply stated problem involving just a little elementary number theory. Here is a description of the problem, after these reductions. Pick a dimension d, say d = 4, and a number p, let's say p = 17 (making p a prime simplifies the situation substantially, but I hope that solving that case will be the key to solving the whole problem). Pick a partition of p, say 17 = 1 + 3 + 3 + 10. You can think of this as the element (1,3,3,10) in the group Z_17 x Z_17 x Z_17 x Z_17. Write all the powers (multiples) of this element in the group, one on each line, and write the sum of each line, divided by 17, on the right (call this number the weight). Now, count the number of 0's appearing in the right hand column (always just one), the number of 1's and so on. This is the delta-vector (or h^*-vector) of a certain simplex. That is, the i-th coordinate of the delta-vector is the number of lines with weight i. THE GOAL IS TO CLASSIFY ALL VECTORS THAT APPEAR IN THIS WAY (preferably without the restriction p a prime, but that will be a later headache). Solving this will amount to classifying the delta-vectors of lattice simplices whose associated group (see the Latex-file) is cyclic of order p. If we succeed in doing that, maybe the solution can be extended to arbitrary groups and thus arbitrary lattice simplices. The rest of the file contains examples, beginning with the one described in the paragraph ``Pick a dimension ...'', and then a Latex-file with the more technical details. I have a couple of C programs, which do the computations shown in the included examples, and I can supply them on request. weight 1 3 3 10 1 (we call 1 3 3 10 the generator) 2 6 6 3 1 3 9 9 13 2 4 12 12 6 2 5 15 15 16 3 6 1 1 9 1 7 4 4 2 1 8 7 7 12 2 9 10 10 5 2 10 13 13 15 3 11 16 16 8 3 12 2 2 1 1 13 5 5 11 2 14 8 8 4 2 15 11 11 14 3 16 14 14 7 3 1 5 6 5 0 <----- the delta-vector (= h^*-vector) Another example: 1 4 5 7 1 2 8 10 14 2 3 12 15 4 2 4 16 3 11 2 5 3 8 1 1 6 7 13 8 2 7 11 1 15 2 8 15 6 5 2 9 2 11 12 2 10 6 16 2 2 11 10 4 9 2 12 14 9 16 3 13 1 14 6 2 14 5 2 13 2 15 9 7 3 2 16 13 12 10 3 1 2 12 2 0 A few things are immediately obvious: The 0-th coordinate is always 1 and the last coordinate is always 0. Since p is a prime, the weight in the k-th row is d minus (weight in the (p-k)-th row) and hence the delta-vector is symmetric (disregarding the 0-th coordinate). A further limitation which might be desirable to impose is that the first coordinate of the delta-vector be nonzero (as in the above cases). This means that any vector arises from a generator with weight 1. If we look at all the vectors that arise in the case d = 4 and p = 17, here is what we get (I am omitting the first coordinate (always 1) and only writing the first ``half'' of each vector. E.g., 0 16 really means 1 0 16 0 0 and 1 14 means 1 1 14 1 0. Note also that that I am including delta-vectors (there is only one) with first coordinate 0): Volume : 17 Parts : 4 delta- generating vector partition 0 16 1 1 16 16 0 16 1 2 15 16 0 16 1 3 14 16 0 16 1 4 13 16 0 16 1 5 12 16 0 16 1 6 11 16 0 16 1 7 10 16 0 16 1 8 9 16 1 14 1 4 14 15 1 14 1 8 10 15 1 14 1 8 12 13 1 14 1 10 11 12 2 12 1 2 3 11 2 12 1 3 5 8 2 12 1 4 5 7 2 12 1 6 12 15 2 12 1 6 13 14 2 12 1 7 11 15 2 12 1 8 11 14 2 12 1 9 10 14 3 10 1 1 4 11 3 10 1 1 7 8 3 10 1 2 4 10 3 10 1 2 5 9 3 10 1 2 6 8 3 10 1 3 4 9 3 10 1 3 6 7 3 10 1 3 15 15 3 10 1 5 5 6 3 10 1 5 13 15 3 10 1 5 14 14 3 10 1 7 12 14 3 10 1 7 13 13 3 10 1 9 11 13 4 8 1 1 2 13 4 8 1 1 3 12 4 8 1 1 5 10 4 8 1 2 7 7 4 8 1 4 4 8 4 8 1 4 6 6 4 8 1 9 9 15 4 8 1 9 12 12 4 8 1 10 10 13 5 6 1 1 1 14 5 6 1 1 6 9 5 6 1 2 2 12 5 6 1 3 3 10 5 6 1 11 11 11 An obvious, but false, guess is that the vectors arising are all possible unimodal ones (disregarding the 0-th coordinate, which is always 1). Here are all the vectors with nonzero first coordinate arising in the case d = 6, p = 43 (omitting the 0-th coordinate): 1 3 34 3 1 1 4 32 4 1 1 5 30 5 1 1 6 28 6 1 1 7 26 7 1 1 8 24 8 1 1 9 22 9 1 1 10 20 10 1 1 11 18 11 1 1 12 16 12 1 1 13 14 13 1 1 14 12 14 1 1 15 10 15 1 2 4 30 4 2 2 5 28 5 2 2 6 26 6 2 2 7 24 7 2 2 8 22 8 2 2 9 20 9 2 2 10 18 10 2 2 11 16 11 2 2 12 14 12 2 2 13 12 13 2 2 14 10 14 2 3 6 24 6 3 3 7 22 7 3 3 8 20 8 3 3 9 18 9 3 3 10 16 10 3 3 11 14 11 3 3 12 12 12 3 3 13 10 13 3 3 14 8 14 3 4 7 20 7 4 4 8 18 8 4 4 9 16 9 4 4 10 14 10 4 4 11 12 11 4 5 7 18 7 5 5 8 16 8 5 5 9 14 9 5 5 10 12 10 5 5 11 10 11 5 5 12 8 12 5 6 9 12 9 6 6 10 10 10 6 7 7 14 7 7 8 9 8 9 8 It would be interesting, and might be a way of solving the problem, to be able to explain when two generators give rise to the same delta-vector. This happens, of course, when two generators belong to the same orbit, i.e. each is a power (multiple) of the other. But there are also cases where two generators not in the same orbit give the same delta-vector: 1 1 4 11 1 2 2 8 5 1 3 3 12 16 2 4 4 16 10 2 5 5 3 4 1 6 6 7 15 2 7 7 11 9 2 8 8 15 3 2 9 9 2 14 2 10 10 6 8 2 11 11 10 2 2 12 12 14 13 3 13 13 1 7 2 14 14 5 1 2 15 15 9 12 3 16 16 13 6 3 1 3 10 3 0 1 2 4 10 1 2 4 8 3 1 3 6 12 13 2 4 8 16 6 2 5 10 3 16 2 6 12 7 9 2 7 14 11 2 2 8 16 15 12 3 9 1 2 5 1 10 3 6 15 2 11 5 10 8 2 12 7 14 1 2 13 9 1 11 2 14 11 5 4 2 15 13 9 14 3 16 15 13 7 3 1 3 10 3 0 If you look at all the generators which give 1 5 6 5 0, they are these: 1 1 1 14 1 1 6 9 Of these, 1 1 1 14 and 1 11 11 11 lie in 1 2 2 12 the same orbit and the remaining three, 1 3 3 10 i.e. 1 1 6 9, 1 3 3 10 and 1 11 11 11 1 2 2 12 lie in the same orbit. Here are the orbits of all generators of weight 1 which give rise to the delta-vector 1 3 10 3 (see the list at the beginning of the examples): 1 1 4 11 1 2 2 8 5 1 3 3 12 16 2 4 4 16 10 2 5 5 3 4 1 6 6 7 15 2 7 7 11 9 2 8 8 15 3 2 9 9 2 14 2 10 10 6 8 2 11 11 10 2 2 12 12 14 13 3 13 13 1 7 2 14 14 5 1 2 15 15 9 12 3 16 16 13 6 3 1 1 7 8 1 2 2 14 16 2 3 3 4 7 1 4 4 11 15 2 5 5 1 6 1 6 6 8 14 2 7 7 15 5 2 8 8 5 13 2 9 9 12 4 2 10 10 2 12 2 11 11 9 3 2 12 12 16 11 3 13 13 6 2 2 14 14 13 10 3 15 15 3 1 2 16 16 10 9 3 1 2 4 10 1 2 4 8 3 1 3 6 12 13 2 4 8 16 6 2 5 10 3 16 2 6 12 7 9 2 7 14 11 2 2 8 16 15 12 3 9 1 2 5 1 10 3 6 15 2 11 5 10 8 2 12 7 14 1 2 13 9 1 11 2 14 11 5 4 2 15 13 9 14 3 16 15 13 7 3 1 2 5 9 1 2 4 10 1 1 3 6 15 10 2 4 8 3 2 1 5 10 8 11 2 6 12 13 3 2 7 14 1 12 2 8 16 6 4 2 9 1 11 13 2 10 3 16 5 2 11 5 4 14 2 12 7 9 6 2 13 9 14 15 3 14 11 2 7 2 15 13 7 16 3 16 15 12 8 3 1 2 6 8 1 2 4 12 16 2 3 6 1 7 1 4 8 7 15 2 5 10 13 6 2 6 12 2 14 2 7 14 8 5 2 8 16 14 13 3 9 1 3 4 1 10 3 9 12 2 11 5 15 3 2 12 7 4 11 2 13 9 10 2 2 14 11 16 10 3 15 13 5 1 2 16 15 11 9 3 1 3 4 9 1 2 6 8 1 1 3 9 12 10 2 4 12 16 2 2 5 15 3 11 2 6 1 7 3 1 7 4 11 12 2 8 7 15 4 2 9 10 2 13 2 10 13 6 5 2 11 16 10 14 3 12 2 14 6 2 13 5 1 15 2 14 8 5 7 2 15 11 9 16 3 16 14 13 8 3 1 3 6 7 1 2 6 12 14 2 3 9 1 4 1 4 12 7 11 2 5 15 13 1 2 6 1 2 8 1 7 4 8 15 2 8 7 14 5 2 9 10 3 12 2 10 13 9 2 2 11 16 15 9 3 12 2 4 16 2 13 5 10 6 2 14 8 16 13 3 15 11 5 3 2 16 14 11 10 3 1 5 5 6 1 2 10 10 12 2 3 15 15 1 2 4 3 3 7 1 5 8 8 13 2 6 13 13 2 2 7 1 1 8 1 8 6 6 14 2 9 11 11 3 2 10 16 16 9 3 11 4 4 15 2 12 9 9 4 2 13 14 14 10 3 14 2 2 16 2 15 7 7 5 2 16 12 12 11 3 Just one more comment about the problem. Obviously, if one didn't reduce modulo p, the weight of each line (multiple of the generator) would be d+(weight of previous line), i.e. line k would have weight k if the generator had weight 1. What happens is that every now and then one of the numbers decreases from one line to the next. It's trivial to find out when these drops occur for a given number, but the problem is to understand how different numbers in a single generator interact in this respect. If one wanted to phrase this in a fancy way, one could say that the drops for a given number n correspond to descents in the permutation word which is the image of n under the canonical (Cayley?) embedding of Z_p in S_p, namely, a column in the table giving the orbit of a generator gives a permutation in S_p and the descents of this permutation are the places where the number decreases in a column. Example: 0 0 0 0 0 1 1 2 3 1 2 2 4 6 2 3 3 6 2 2 4 4 1 5 2 5 5 3 1 2 6 6 5 4 3 1 1 4 1 0 The permutation corresponding to 2 is 0246135 and for 3 it is 0362514. But, I haven't been able to use this to crack the problem. So far, my main idea of how to tackle the problem has been to try to understand when two generators (not in the same orbit) give the same delta-vector. I guess what I'm hoping for is some algorithm akin to the compression used to prove the Kruskal-Katona theorem, which would allow one to successively interchange a generator with another one, preserving the delta-vector but reducing some "measure" on the generators until reaching a minimal one. Then one would, hopefully, have a nice description of "minimal" generators which would lead to a theorem about what their delta-vectors can be like. But maybe this is not a fruitful approach. Finally, here is the Latex-file. Note that, depending on your Latex version, you may have to alter the definitions of \clp and \mbf at the beginning of the file (in the way described). %%%%%%%%%%%%%%%%%%%%%% LaTeX file - additional information %%%%%%%%%%%%%%%%% \documentstyle[12pt]{article} \begin{document} \newcommand\clp{{\cal P}} %%Replace \cal by \mathcal ? \newcommand\mbf{\bf} %%Replace \bf by \mathbf ? \centerline{Further information in connection with} \centerline{FPSAC/SFCA '94 \ \ \ \ Open Problem} \centerline{proposed by Einar Steingrimmson, February 19, 1994} \vspace{12pt} \centerline{\large Ehrhart polynomials} \vspace{12pt} Let ${\clp}$ be a $d$--dimensional polytope or a $(d-1)$--dimensional simplicial complex in ${\mbf R}^{n}$ with integral (lattice) vertices, i.e. $v_i \in {\mbf Z}^{n}$ for all vertices $v_i$ of ${\clp}$. For $k \in {\mbf N}$ let $k{\clp} = \{ kx \hspace{2pt} | \hspace{2pt} x \in {\clp} \}$, i.e. $k{\clp}$ is the (lattice) polytope (or complex) obtained by dilating ${\clp}$ by a factor of $k$. \noindent For $k \in {\mbf N}$ define the function $$ i({\clp}, k) = \# \{ x\in {\mbf R}^{n} \hspace{2pt} | \hspace{2pt} x \in k{\clp} \cap {\mbf Z}^{n} \}. $$ Thus, $i({\clp}, k)$ is the number of lattice points contained in $k{\clp}$. By Cor. 4.6.28 in \cite{ECI}, $i({\clp},k)$ is a polynomial in $k$ of degree $d$, called the {\it Ehrhart polynomial} of ${\clp}$. Now define the generating function $$ E({\clp}, t) = \sum_{k \geq 0}{i({\clp},k) t^{k}} . $$ \noindent By Thm. 2.1 in \cite{decrat}, we have $$ E({\clp}, t) = \frac{h^{*}({\clp}, t)} {(1-t)^{d+1}} $$ where $h^{*}({\clp}, t)$ is a polynomial of degree at most $d$ with non-negative integer coefficients, called the {\em Ehrhart $h^{*}$-polynomial of} ${\clp}$. Its coefficients are the coordinates of the Ehrhart $h^*$--{\em vector} $h^*({\clp})$ of ${\clp}$. \vspace{12pt} \centerline{\large The matrix approach} \vspace{12pt} Let $\Delta$ be a $d$--dimensional lattice simplex embedded in ${\mbf R}^d$. We may assume, without loss of generality, that one of its vertices is the origin in ${{\mbf R}}^{d}$ and we represent the other vertices of $\Delta$ as the rows of a $d\times d$ matrix $S$. Abusing notation, we now identify a lattice simplex (which contains the origin as a vertex) with its corresponding matrix. If $A$ is any matrix in the special linear group $SL(d,{\mbf Z})$ then $h^*(S) = h^*(SA).$ In particular, there is a (unique) matrix $T$ such that $T = SA$ for some $A \in SL(d,{\mbf Z})$ and such that $T$ is in {\em Hermite normal form}, i.e. $T$ is upper triangular with diagonal entries $a_{11},a_{22},\ldots,a_{dd}$, such that $a_{ij} < a_{ii}$ for $j>i.$ %Thus, we can restrict our attention to simplices represented by %matrices in Hermite normal form. One can now compute $h^{*}(T)$ as follows: Let $v_i$ be the $i$-th row vector of $T$, let $v_0 = (0,0,\ldots,0)$ and let $v^{\prime}_i = (v_i,1)\in {\mbf R}^{d+1}$. Let $G = {\mbf Z}^{d+1}/H$ where $H$ is the subgroup of ${\mbf Z}^{d+1}$ generated by the $v^{\prime}_i$. Then $G$ is isomorphic to ${{\mbf Z}_{a_{11}}}\times {{\mbf Z}_{a_{22}}} \times \cdots\times {{\mbf Z}_{a_{dd}}}$, and its elements, which are coset representatives of $H$ in ${\mbf Z}^{d+1}$, correspond to integer points in the half-open parallelotope $P = \{\sum{\alpha_i v^{\prime}_i} | 0 \leq \alpha_i < 1\}$ (see, e.g.,\cite{Macdon}). We can now compute $h^*(T)$ by computing the distribution of {\em weights} of all vectors ${\mbf k} = (k_0,k_2,\ldots,k_d)$ in $[0,1]^{d+1}$ such that $\sum{k_i v^{\prime}_i} \in {\mbf Z}^{d+1}$, where weight is defined by $w(k_{0}, k_{2},\ldots,k_{d}) = \sum{k_{i}}$. \begin{thebibliography}{99} \bibitem{Macdon} I.G. Macdonald: The volume of a lattice polyhedron, Proc. Camb. Phil. Soc. {\bf 59} (1963), 719--726. \bibitem{decrat} R. Stanley: Decompositions of rational convex polytopes, Ann. Discrete Math. {\bf 6} (1980), 333-342. \bibitem{ECI} R. Stanley: Enumerative combinatorics, vol. I, Wadsworth $\&$ Brooks/Cole, Pacific Grove, California, 1986. \end{thebibliography} \end{document}