h-Vectors of Gorenstein polytopes

We show that the Ehrhart h-vector of an integer Gorenstein polytope with a regular unimodular triangulation satisfies McMullen's g-theorem; in particular, it is unimodal. This result generalizes a recent theorem of Athanasiadis (conjectured by Stanley) for compressed polytopes. It is derived from a more general theorem on Gorenstein affine normal monoids M: one can factor K[M] (K a field) by a “long” regular sequence in such a way that the quotient is still a normal affine monoid algebra. This technique reduces all questions about the Ehrhart h-vector of P to the Ehrhart h-vector of a Gorenstein polytope Q with exactly one interior lattice point, provided each lattice point in a multiple cP, c∈N, can be written as the sum of c lattice points in P. (Up to a translation, the polytope Q belongs to the class of reflexive polytopes considered in connection with mirror symmetry.) If P has a regular unimodular triangulation, then it follows readily that the Ehrhart h-vector of P coincides with the combinatorial h-vector of the boundary complex of a simplicial polytope, and the g-theorem applies.     

Reduced arithmetically Gorenstein schemes and simplicial polytopes with maximal Betti numbers

An SI-sequence is a finite sequence of positive integers which is symmetric, unimodal and satisfies a certain growth condition. These are known to correspond precisely to the possible Hilbert functions of graded Artinian Gorenstein algebras with the weak Lefschetz property, a property shared by a nonempty open set of the family of all graded Artinian Gorenstein algebras having a fixed Hilbert function that is an SI sequence. Starting with an arbitrary SI-sequence, we construct a reduced, arithmetically Gorenstein configuration G of linear varieties of arbitrary dimension whose Artinian reduction has the given SI-sequence as Hilbert function and has the weak Lefschetz property. Furthermore, we show that G has maximal graded Betti numbers among all arithmetically Gorenstein subschemes of projective space whose Artinian reduction has the weak Lefschetz property and the given Hilbert function. As an application we show that over a field of characteristic zero every set of simplicial polytopes with fixed h-vector contains a polytope with maximal graded Betti numbers.     

Finite lattices and Gröbner bases

Gröbner bases of binomial ideals arising from finite lattices will be studied. In terms of Gröbner bases and initial ideals, a characterization of finite distributive lattices as well as planar distributive lattices will be given.     

Gröbner bases of balanced polyominoes

We introduce balanced polyominoes and show that their ideal of inner minors is a prime ideal and has a squarefree Gröbner basis with respect to any monomial order, and we show that any row or column convex and any tree‐like polyomino is simple and balanced.     

Regular polytopes of type {4,4,3} and {4,4,4}

Abstract regular polytopes generalize the classical concept of a regular polytope and regular tessellation to more complicated combinatorial structures with a distinctive geometrical and topological flavour. In this paper the authors give an almost complete classification of the (universal) locally toroidal regular 4-polytopes of Schläfli types {4,4,3} and {4,4,4}.     

Algebraic geometry of Gaussian Bayesian networks

Conditional independence models in the Gaussian case are algebraic varieties in the cone of positive definite covariance matrices. We study these varieties in the case of Bayesian networks, with a view towards generalizing the recursive factorization theorem to situations with hidden variables. In the case when the underlying graph is a tree, we show that the vanishing ideal of the model is generated by the conditional independence statements implied by graph. We also show that the ideal of any Bayesian network is homogeneous with respect to a multigrading induced by a collection of upstream random variables. This has a number of important consequences for hidden variable models. Finally, we relate the ideals of Bayesian networks to a number of classical constructions in algebraic geometry including toric degenerations of the Grassmannian, matrix Schubert varieties, and secant varieties.     

On odd points and the volume of lattice polyhedra

Denote by _n ³ ,n 2, the lattice consisting of all pointsx in ³ such thatnx belongs to the fundamental lattice ³ of points with integer coordinates. Letl _n be the subset of _n ³ consisting of all points whose coordinates are odd multiples of 1/n. The purpose of this paper is to give several new Pick-type formulae for the volume of three-dimensional lattice polyhedra, that is, polyhedra with vertices in ³. Our formulae are in terms of numbers of only thel _n-points belonging to a lattice polyhedronP in contrast to already known formulae which employ numbers of all the _n ³ -points inP. On our way to establishing the formulae we show that the number of points froml _n belonging to a three-dimensional lattice polyhedronP has some polynomiality properties similar to those of the well-known Ehrhart polynomial expressing the number of points of _n ³ inP. The paper contains also some comments on a problem of finding a volume formula which would employ only the setsl _n and which would be applicable to lattice polyhedra in arbitrary dimensions.Research partially supported by KBN Grant 2 P03A 008 10.     

On the construction of highly symmetric tight frames and complex polytopes

Many “highly symmetric” configurations of vectors in C^d${\mathbb{C}}^d$, such as the vertices of the platonic solids and the regular complex polytopes, are equal-norm tight frames by virtue of being the orbit of the irreducible unitary action of their symmetry group. For nonabelian groups there are uncountably many such tight frames up to unitary equivalence. The aim of this paper is to single out those orbits which are particularly nice, such as those which are the vertices of a complex polytope. This is done by defining a finite class of tight frames of n   vectors for C^d${\mathbb{C}}^d$ (n and d fixed) which we call the highly symmetric tight frames. We outline how these frames can be calculated from the representations of abstract groups using a computer algebra package. We give numerous examples, with a special emphasis on those obtained from the (Shephard–Todd) finite reflection groups. The interrelationships between these frames with complex polytopes, harmonic frames, equiangular tight frames, and Heisenberg frames (maximal sets of equiangular lines) are explored in detail.     

Minimal and reduced pairs of convex bodies

We give a new proof for the existence and uniqueness (up to translation) of plane minimal pairs of convex bodies in a given equivalence class of the Hörmander-R»dström lattice, as well as a complete characterization of plane minimal pairs using surface area measures. Moreover, we introduce the so-called reduced pairs, which are special minimal pairs. For the plane case, we characterize reduced pairs as those pairs of convex bodies whose surface area measures are mutually singular. For higher dimensions, we give two sufficient conditions for the minimality of a pair of convex polytopes, as well as a necessary and sufficient criterion for a pair of convex polytopes to be reduced. We conclude by showing that a typical pair of convex bodies, in the sense of Baire category, is reduced, and hence the unique minimal pair in its equivalence class.     

Normal toric ideals of low codimension

Every normal toric ideal of codimension two is minimally generated by a Gröbner basis with squarefree initial monomials. A polynomial time algorithm is presented for checking whether a toric ideal of fixed codimension is normal.     

Gröbner bases for the Hilbert ideal and coinvariants of the dihedral group D2p

We consider a finite dimensional representation of the dihedral group D_2p over a field of characteristic two where p is an odd integer and study the corresponding Hilbert ideal I_H. We show that I_H has a universal Gröbner basis consisting of invariants and monomials only. We provide sharp bounds for the degree of an element in this basis and in a minimal generating set for I_H. We also compute the top degree of coinvariants when p is prime.     

The computation of the logarithmic cohomology for plane curves

We will give algorithms of computing bases of logarithmic cohomology groups for square-free polynomials in two variables.     

New developments in the theory of Gröbner bases and applications to formal verification

We present foundational work on standard bases over rings and on Boolean Gröbner bases in the framework of Boolean functions. The research was motivated by our collaboration with electrical engineers and computer scientists on problems arising from formal verification of digital circuits. In fact, algebraic modelling of formal verification problems is developed on the word-level as well as on the bit-level. The word-level model leads to Gröbner basis in the polynomial ring over Z/2ⁿ while the bit-level model leads to Boolean Gröbner bases. In addition to the theoretical foundations of both approaches, the algorithms have been implemented. Using these implementations we show that special data structures and the exploitation of symmetries make Gröbner bases competitive to state-of-the-art tools from formal verification but having the advantage of being systematic and more flexible.     

The Gergonne and Nagel centers of an n-dimensional simplex

In contrast with the analogous situation for a triangle, the cevians that join the vertices of a tetrahedron to the points where the faces touch the insphere (or the exspheres) are not concurrent in general. This observation led the present author and P. Walker in [4] to devise alternative definitions of the Gergonne and Nagel centers of a tetrahedron that do not assume the concurrence of such cevians and that coincide with the ordinary definitions in the case of a triangle. They then proved that the Gergonne center exists and is unique for all tetrahedra and that the Nagel center, though unique, exists only for tetrahedra that satisfy certain conditions. In this article, we extend these definitions to simplices of any dimension. By keeping the requirement that the Gergonne center be interior and relaxing such a condition for the Nagel center, we prove that both centers exist and are unique for all simplices, thus polishing the definitions and generalizing the results of the above-mentioned article.     

H-bases for polynomial interpolation and system solving

The H-basis concept allows, similarly to the Gröbner basis concept, a reformulation of nonlinear problems in terms of linear algebra. We exhibit parallels of the two concepts, show properties of H-bases, discuss their construction and uniqueness questions, and prove that n polynomials in n variables are, under mild conditions, already H-bases. We apply H-bases to the solution of polynomial systems by the eigenmethod and to multivariate interpolation.     

The first variation of the total mass of log-concave functions and related inequalities

On the class of log-concave functions on Rⁿ${\mathbb{R}}^n$, endowed with a suitable algebraic structure, we study the first variation of the total mass functional, which corresponds to the volume of convex bodies when restricted to the subclass of characteristic functions. We prove some integral representation formulae for such a first variation, which suggest to define in a natural way the notion of area measure for a log-concave function. In the same framework, we obtain a functional counterpart of Minkowski’s first inequality for convex bodies; as corollaries, we derive a functional form of the isoperimetric inequality, and a family of logarithmic-type Sobolev inequalities with respect to log-concave probability measures. Finally, we propose a suitable functional version of the classical Minkowski’s problem for convex bodies, and prove some partial results towards its solution.     

Expected intrinsic volumes and facet numbers of random beta‐polytopes

Let be i.i.d. random points in the d‐dimensional Euclidean space sampled according to one of the following probability densities: and We compute exactly the expected intrinsic volumes and the expected number of facets of the convex hull of . Asymptotic formulae were obtained previously by Affentranger [The convex hull of random points with spherically symmetric distributions, 1991]. By studying the limits of the beta case when , respectively , we can also cover the models in which are uniformly distributed on the unit sphere or normally distributed, respectively. We obtain similar results for the random polytopes defined as the convex hulls of and . One of the main tools used in the proofs is the Blaschke–Petkantschin formula.     

Character theory of symmetric groups, subgroup growth of Fuchsian groups, and random walks

We develop a number of statistical aspects of symmetric groups (mostly dealing with the distribution of cycles in various subsets of Sn), asymptotic properties of (ordinary) characters of symmetric groups, and estimates for the multiplicities of root number functions of these groups. As main applications, we present an estimate for the subgroup growth of an arbitrary Fuchsian group, a finiteness result for the number of Fuchsian presentations of such a group (resolving a long-standing problem of Roger Lyndon), as well as a proof of a well-known conjecture of Roichman concerning the mixing time of random walks on symmetric groups.