Search

De Loera, O'Neill and Wilburne introduced a general model for random numerical semigroups in which each positive integer is chosen independently with some probability p to be a generator, and proved upper and lower bounds on the expected Frobenius number and expected embedding dimensions. We use a range of probabilistic methods to improve the upper bounds to within a polylogarithmic factor of the lower bounds in each case. As one of the tools to do this, we prove that for any prime q, if A is a random subset of the cyclic group Z_q whose size is of order log(q) and k is also of order log(q), then with high probability the k-fold sumset kA is all of Z_q., Comment: 17 pages, 4 figures. Corrected various minor mistakes, including constants that were incorrectly swapped between the two parts of the main theorem (Theorem 1.6). Added a new reference (Bac90) and associated discussion in the introduction

We present two families of numerical semigroups and show that for each family, the number of required components in an irreducible decomposition cannot be bounded by any given integer. This gives a negative answer to a question raised by Delgado, Garc\'ia-S\'anchez and Rosales., Comment: 4 pages

A Golomb ruler is a sequence of integers whose pairwise differences, or equivalently pairwise sums, are all distinct. This definition has been generalized in various ways to allow for sums of h integers, or to allow up to g repetitions of a given sum or difference. Beck, Bogart, and Pham applied the theory of inside-out polytopes of Beck and Zaslavsky to prove structural results about the counting functions of Golomb rulers. We extend their approach to the various types of generalized Golomb rulers., Comment: 15 pages, 2 figures

We examine two natural operations to create numerical semigroups. We say that a numerical semigroup $\mathcal{S}$ is $k$-normalescent if it is the projection of the set of integer points in a $k$-dimensional polyhedral cone, and we say that $\mathcal{S}$ is a $k$-quotient if it is the quotient of a numerical semigroup with $k$ generators. We prove that all $k$-quotients are $k$-normalescent, and although the converse is false in general, we prove that the projection of the set of integer points in a cone with $k$ extreme rays (possibly lying in a dimension smaller than $k$) is a $k$-quotient. The discrete geometric perspective of studying cones is useful for studying $k$-quotients: in particular, we use it to prove that the sum of a $k_1$-quotient and a $k_2$-quotient is a $(k_1+k_2)$-quotient. In addition, we prove several results about when a numerical semigroup is not $k$-normalescent.

A natural operation on numerical semigroups is taking a quotient by a positive integer. If $\mathcal S$ is a quotient of a numerical semigroup with $k$ generators, we call $\mathcal S$ a $k$-quotient. We give a necessary condition for a given numerical semigroup $\mathcal S$ to be a $k$-quotient, and present, for each $k \ge 3$, the first known family of numerical semigroups that cannot be written as a $k$-quotient. We also examine the probability that a randomly selected numerical semigroup with $k$ generators is a $k$-quotient.

We define two new families of polynomials that generalize permanents and prove upper and lower bounds on their determinantal complexities comparable to the known bounds for permanents. One of these families is obtained by replacing permutations by signed permutations, and the other by replacing permutations by surjective functions with preimages of prescribed sizes., Comment: 14 pages

The extension complexity of a polytope measures its amenability to succinct representations via lifts. There are several versions of extension complexity, including linear, real semidefinite, and complex semidefinite. We focus on the last of these, for which the least is known, and in particular on understanding which polytopes are complex psd-minimal. We prove the existence of an obstruction to complex psd-minimality which is efficiently computable via lattice membership problems. Using this tool, we complete the classification of complex psd-minimal polygons (geometrically as well as combinatorially). In dimension three we exhibit several new examples of complex psd-minimal polytopes and apply our obstruction to rule out many others., Comment: 20 pages, 6 figures

A wide variety of problems in combinatorics and discrete optimization depend on counting the set $S$ of integer points in a polytope, or in some more general object constructed via discrete geometry and first-order logic. We take a tour through numerous problems of this type. In particular, we consider families of such sets $S_t$ depending on one or more integer parameters $t$, and analyze the behavior of the function $f(t)=|S_t|$. In the examples that we investigate, this function exhibits surprising polynomial-like behavior. We end with two broad theorems detailing settings where this polynomial-like behavior must hold. The plethora of examples illustrates the framework in which this behavior occurs and also gives an intuition for many of the proofs, helping us create a toolbox for counting problems like these., Comment: The American Mathematical Monthly, to appear. 20 pages, 11 figures

We propose reducible algebraic curves as a mechanism to construct Partial MDS (PMDS) codes geometrically. We obtain new general existence results, new explicit constructions and improved estimates on the smallest field sizes over which such codes can exist. Our results are obtained by combining ideas from projective algebraic geometry, combinatorics and probability theory., Comment: 25 pages

A combinatorial polytope $P$ is said to be projectively unique if it has a single realization up to projective transformations. Projective uniqueness is a geometrically compelling property but is difficult to verify. In this paper, we merge two approaches to projective uniqueness in the literature. One is primarily geometric and is due to McMullen, who showed that certain natural operations on polytopes preserve projective uniqueness. The other is more algebraic and is due to Gouveia, Macchia, Thomas, and Wiebe. They use certain ideals associated to a polytope to verify a property called graphicality that implies projective uniqueness. In this paper, we show that that McMullen's operations preserve not only projective uniquness but also graphicality. As an application, we show that large families of order polytopes are graphic and thus projectively unique.

Let $f_1(n), \ldots, f_k(n)$ be polynomial functions of $n$. For fixed $n\in\mathbb{N}$, let $S_n\subseteq \mathbb{N}$ be the numerical semigroup generated by $f_1(n),\ldots,f_k(n)$. As $n$ varies, we show that many invariants of $S_n$ are eventually quasi-polynomial in $n$, such as the Frobenius number, the type, the genus, and the size of the $\Delta$-set. The tool we use is expressibility in the logical system of parametric Presburger arithmetic. Generalizing to higher dimensional families of semigroups, we also examine affine semigroups $S_n\subseteq \mathbb{N}^m$ generated be vectors whose coordinates are polynomial functions of $n$, and we prove similar results; for example, the Betti numbers are eventually quasi-polynomial functions of $n$., Comment: 10 pages

Given a parametric lattice with a basis given by polynomials in Z[t], we give an algorithm to construct an LLL-reduced basis whose elements are eventually quasi-polynomial in t: that is, they are given by formulas that are piecewise polynomial in t (for sufficiently large t), such that each piece is given by a congruence class modulo a period. As a consequence, we show that there are parametric solutions of the shortest vector problem (SVP) and closest vector problem (CVP) that are also eventually quasi-polynomial in t., Comment: 20 pages. Accepted for publication in SIAM Journal on Discrete Mathematics. Revised title and opening paragraphs, slightly modified statement of Theorem 1.4, added explanation of some steps in Section 3, and implemented various minor improvements suggested by anonymous referees

Two number fields are called arithmetically equivalent if they have the same Dedekind zeta function. In the 1970's Perlis showed that this is equivalent to the condition that for almost every rational prime $\ell$ the arithmetic type of $\ell$ is the same in each field. In the 1990's Perlis and Stuart gave an unexpected characterization for arithmetic equivalence; they showed that to be arithmetically equivalent it is enough for almost every prime $\ell$ to have the same number of prime factors in each field. Here, using an $\ell-p$ switch trick, we provide an elementary proof of that fact based on a classical result of Smith from the 1870's., Comment: 7 pages. Fixed an error in the proof of Lemma 2.1

We consider an expansion of Presburger arithmetic which allows multiplication by $k$ parameters $t_1,\ldots,t_k$. A formula in this language defines a parametric set $S_\mathbf{t} \subseteq \mathbb{Z}^{d}$ as $\mathbf{t}$ varies in $\mathbb{Z}^k$, and we examine the counting function $|S_\mathbf{t}|$ as a function of $\mathbf{t}$. For a single parameter, it is known that $|S_t|$ can be expressed as an eventual quasi-polynomial (there is a period $m$ such that, for sufficiently large $t$, the function is polynomial on each of the residue classes mod $m$). We show that such a nice expression is impossible with 2 or more parameters. Indeed (assuming \textbf{P} $\neq$ \textbf{NP}) we construct a parametric set $S_{t_1,t_2}$ such that $|S_{t_1, t_2}|$ is not even polynomial-time computable on input $(t_1,t_2)$. In contrast, for parametric sets $S_\mathbf{t} \subseteq \mathbb{Z}^d$ with arbitrarily many parameters, defined in a similar language without the ordering relation, we show that $|S_\mathbf{t}|$ is always polynomial-time computable in the size of $\mathbf{t}$, and in fact can be represented using the gcd and similar functions., Comment: 14 pages, 1 figure

Parametric Presburger arithmetic concerns families of sets S_t in Z^d, for t in N, that are defined using addition, inequalities, constants in Z, Boolean operations, multiplication by t, and quantifiers on variables ranging over Z. That is, such families are defined using quantifiers and Boolean combinations of formulas of the form a(t) x <= b(t), where a(t) is in Z[t]^d, b(t) in Z[t]. A function g: N -> Z is a quasi-polynomial if there exists a period m and polynomials f_0, ..., f_{m-1} in Q[t] such that g(t)=f_i(t) for t congruent to i (mod m.) Recent results of Chen, Li, Sam; Calegari, Walker; Roune, Woods; and Shen concern specific families in parametric Presburger arithmetic that exhibit quasi-polynomial behavior. For example, S_t might be an a quasi-polynomial function of t or an element x(t) in S_t might be specifiable as a function with quasi-polynomial coordinates, for sufficiently large t. Woods conjectured that all parametric Presburger sets exhibit this quasi-polynomial behavior. Here, we prove this conjecture, using various tools from logic and combinatorics., Comment: 34 pages, 1 figure. Minor changes, including to the title

We prove that the determinantal complexity of a hypersurface of degree $d > 2$ is bounded below by one more than the codimension of the singular locus, provided that this codimension is at least $5$. As a result, we obtain that the determinantal complexity of the $3 \times 3$ permanent is $7$. We also prove that for $n> 3$, there is no nonsingular hypersurface in $\mathbf{P}^n$ of degree $d$ that has an expression as a determinant of a $d \times d$ matrix of linear forms while on the other hand for $n \le 3$, a general determinantal expression is nonsingular. Finally, we answer a question of Ressayre by showing that the determinantal complexity of the unique (singular) cubic surface containing a single line is $5$., Comment: 7 pages, 0 figures