Integer-valued polynomials over matrices and divided differences

Let $D$ be an integrally closed domain with quotient field $K$ and $n$ a positive integer. We give a characterization of the polynomials in $K[X]$ which are integer-valued over the set of matrices $M_n(D)$ in terms of their divided differences. A necessary and sufficient condition on $f\in K[X]$ to be integer-valued over $M_n(D)$ is that, for each $k$ less than $n$ , the $k$ th divided difference of $f$ is integral-valued on every subset of the roots of any monic polynomial over $D$ of degree $n$ . If in addition $D$ has zero Jacobson radical then it is sufficient to check the above conditions on subsets of the roots of monic irreducible polynomials of degree $n$ , that is, conjugate integral elements of degree $n$ over $D$ .     

Sporadic Reinhardt Polygons

Let $n$ be a positive integer, not a power of two. A Reinhardt polygon is a convex $n$ -gon that is optimal in three different geometric optimization problems: it has maximal perimeter relative to its diameter, maximal width relative to its diameter, and maximal width relative to its perimeter. For almost all $n$ , there are many Reinhardt polygons with $n$ sides, and many of them exhibit a particular periodic structure. While these periodic polygons are well understood, for certain values of $n$ , additional Reinhardt polygons exist, which do not possess this structured form. We call these polygons sporadic. We completely characterize the integers $n$ for which sporadic Reinhardt polygons exist, showing that these polygons occur precisely when $n=pqr$ with $p$ and $q$ distinct odd primes and $r\ge 2$ . We also prove that a positive proportion of the Reinhardt polygons with $n$ sides is sporadic for almost all integers $n$ , and we investigate the precise number of sporadic Reinhardt polygons that are produced for several values of $n$ by a construction that we introduce.     

Towards a de Bruijn–Erdős Theorem in the L_1-Metric

A well-known theorem of de Bruijn and Erd?s states that any set of $n$ non-collinear points in the plane determines at least $n$ lines. Chen and Chvátal asked whether an analogous statement holds within the framework of finite metric spaces, with lines defined using the notion of betweenness. In this paper, we prove that the answer is affirmative for sets of $n$ points in the plane with the $L_1$ metric, provided that no two points share their $x$ - or $y$ -coordinate. In this case, either there is a line that contains all $n$ points, or $X$ induces at least $n$ distinct lines. If points of $X$ are allowed to share their coordinates, then either there is a line that contains all $n$ points, or $X$ induces at least $n/37$ distinct lines.     

Functional limit theorems for random regular graphs

Consider $d$ uniformly random permutation matrices on $n$ labels. Consider the sum of these matrices along with their transposes. The total can be interpreted as the adjacency matrix of a random regular graph of degree $2d$ on $n$ vertices. We consider limit theorems for various combinatorial and analytical properties of this graph (or the matrix) as $n$ grows to infinity, either when $d$ is kept fixed or grows slowly with $n$ . In a suitable weak convergence framework, we prove that the (finite but growing in length) sequences of the number of short cycles and of cyclically non-backtracking walks converge to distributional limits. We estimate the total variation distance from the limit using Stein’s method. As an application of these results we derive limits of linear functionals of the eigenvalues of the adjacency matrix. A key step in this latter derivation is an extension of the Kahn–Szemerédi argument for estimating the second largest eigenvalue for all values of $d$ and $n$ .     

Lattice-free sets,multi-branch split disjunctions,and mixed-integer programming

In this paper we study the relationship between valid inequalities for mixed-integer sets, lattice-free sets associated with these inequalities and the multi-branch split cuts introduced by Li and Richard (Discret Optim 5:724–734, 2008). By analyzing $n$ -dimensional lattice-free sets, we prove that for every integer $n$ there exists a positive integer $t$ such that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with $n$ integer variables is a $t$ -branch split cut. We use this result to give a finite cutting-plane algorithm to solve mixed-integer programs. We also show that the minimum value $t$ , for which all facets of polyhedral mixed-integer sets with $n$ integer variables can be generated as $t$ -branch split cuts, grows exponentially with $n$ . In particular, when $n=3$ , we observe that not all facet-defining inequalities are 6-branch split cuts.     

On Sets Defining Few Ordinary Lines

Let $P$ P be a set of $n$ n points in the plane, not all on a line. We show that if $n$ n is large then there are at least $n/2$ n / 2 ordinary lines, that is to say lines passing through exactly two points of $P$ P . This confirms, for large $n$ n , a conjecture of Dirac and Motzkin. In fact we describe the exact extremisers for this problem, as well as all sets having fewer than $n-C$ n - C ordinary lines for some absolute constant $C$ C . We also solve, for large $n$ n , the “orchard-planting problem”, which asks for the maximum number of lines through exactly 3 points of $P$ P . Underlying these results is a structure theorem which states that if $P$ P has at most $Kn$ K n ordinary lines then all but O(K) points of $P$ P lie on a cubic curve, if $n$ n is sufficiently large depending on $K$ K .     

Global symplectic coordinates on gradient Kähler–Ricci solitons

A classical result of McDuff [14] asserts that a simply connected complete Kähler manifold $(M,g,\omega )$ with non positive sectional curvature admits global symplectic coordinates through a symplectomorphism $\Psi \ : M \rightarrow \mathbb{R }^{2n}$ (where $n$ is the complex dimension of $M$ ), satisfying the following property (proved by E. Ciriza in [4]): the image $\Psi (T)$ of any complex totally geodesic submanifold $T\subset M$ through the point $p$ such that $\Psi (p)=0$ , is a complex linear subspace of $\mathbb C ^n\simeq \mathbb{R }^{2n}$ . The aim of this paper is to exhibit, for all positive integers $n$ , examples of $n$ -dimensional complete Kähler manifolds with non-negative sectional curvature globally symplectomorphic to $\mathbb{R }^{2n}$ through a symplectomorphism satisfying Ciriza’s property.     

Essential p-dimension of split simple groups of type A_n

We compute the essential $p$ -dimension of split simple groups of type $A_{n-1}$ in terms of the functor ${{\mathsf{\textit{Alg} }}}(n,m)$ of central simple algebras of degree $n$ and exponent dividing $m$ .     

f-Vectors Implying Vertex Decomposability

We prove that if a pure simplicial complex $\Delta $ of dimension $d$ with $n$ facets has the least possible number of $(d-1)$ -dimensional faces among all complexes with $n$ faces of dimension $d$ , then it is vertex decomposable. This answers a question of J. Herzog and T. Hibi. In fact, we prove a generalization of their theorem using combinatorial methods.     

Mod-discrete expansions

In this paper, we consider approximating expansions for the distribution of integer valued random variables, in circumstances in which convergence in law (without normalization) cannot be expected. The setting is one in which the simplest approximation to the $n$ -th random variable  $X_n$ is by a particular member $R_n$ of a given family of distributions, whose variance increases with  $n$ . The basic assumption is that the ratio of the characteristic function of  $X_n$ to that of  $R_n$ converges to a limit in a prescribed fashion. Our results cover and extend a number of classical examples in probability, combinatorics and number theory.     

Caffarelli–Kohn–Nirenberg inequality on metric measure spaces with applications

We prove that if a metric measure space satisfies the volume doubling condition and the Caffarelli–Kohn–Nirenberg inequality with the same exponent $n \ge 3$ , then it has exactly the $n$ -dimensional volume growth. As an application, if an $n$ -dimensional Finsler manifold of non-negative $n$ -Ricci curvature satisfies the Caffarelli–Kohn–Nirenberg inequality with the sharp constant, then its flag curvature is identically zero. In the particular case of Berwald spaces, such a space is necessarily isometric to a Minkowski space.     

Strengthening the cohomological crepant resolution conjecture for Hilbert–Chow morphisms

Given any smooth toric surface $S$ , we prove a SYM-HILB correspondence which relates the 3-point, degree zero, extended Gromov–Witten invariants of the $n$ -fold symmetric product stack $[\mathrm{Sym}^n(S)]$ of $S$ to the 3-point extremal Gromov–Witten invariants of the Hilbert scheme $\mathrm{Hilb}^n(S)$ of $n$ points on $S$ . As we do not specialize the values of the quantum parameters involved, this result proves a strengthening of Ruan’s Cohomological Crepant Resolution Conjecture for the Hilbert–Chow morphism $\mathrm{Hilb}^n(S) \rightarrow \mathrm{Sym}^n(S)$ and yields a method of reconstructing the cup product for $\mathrm{Hilb}^n(S)$ from the orbifold invariants of $[\mathrm{Sym}^n(S)]$ .     

A construction of integer-valued polynomials with prescribed sets of lengths of factorizations

For an arbitrary finite non-empty set $S$ of natural numbers greater $1$ , we construct $f\in \text{ Int }(\mathbb{Z })=\{g\in \mathbb{Q }[x]\mid g(\mathbb{Z })\subseteq \mathbb{Z }\}$ such that $S$ is the set of lengths of $f$ , i.e., the set of all $n$ such that $f$ has a factorization as a product of $n$ irreducibles in $\text{ Int }(\mathbb{Z })$ . More generally, we can realize any finite non-empty multi-set of natural numbers greater 1 as the multi-set of lengths of the essentially different factorizations of $f$ .     

Acyclic Systems of Permutations and Fine Mixed Subdivisions of Simplices

A fine mixed subdivision of a $(d-1)$ -simplex $T$ of size $n$ gives rise to a system of  ${d \atopwithdelims ()2}$ permutations of $[n]$ on the edges of $T$ , and to a collection of $n$ unit $(d-1)$ -simplices inside $T$ . Which systems of permutations and which collections of simplices arise in this way? The Spread Out Simplices Conjecture of Ardila and Billey proposes an answer to the second question. We propose and give evidence for an answer to the first question, the Acyclic System Conjecture. We prove that the system of permutations of $T$ determines the collection of simplices of $T$ . This establishes the Acyclic System Conjecture as a first step towards proving the Spread Out Simplices Conjecture. We use this approach to prove both conjectures for $n=3$ in arbitrary dimension.     

Rigidity of Einstein manifolds with positive scalar curvature

We prove that if $M^n(n\ge 4)$ is a compact Einstein manifold whose normalized scalar curvature and sectional curvature satisfy pinching condition $R_0>\sigma _{n}K_{\max }$ , where $\sigma _n\in (\frac{1}{4},1)$ is an explicit positive constant depending only on $n$ , then $M$ must be isometric to a spherical space form. Moreover, we prove that if an $n(\ge {\!\!4})$ -dimensional compact Einstein manifold satisfies $K_{\min }\ge \eta _n R_0,$ where $\eta _n\in (\frac{1}{4},1)$ is an explicit positive constant, then $M$ is locally symmetric. It should be emphasized that the pinching constant $\eta _n$ is optimal when $n$ is even. We then obtain some rigidity theorems for Einstein manifolds under $(n-2)$ -th Ricci curvature and normalized scalar curvature pinching conditions. Finally we extend the theorems above to Einstein submanifolds in a Riemannian manifold, and prove that if $M$ is an $n(\ge {\!\!4})$ -dimensional compact Einstein submanifold in the simply connected space form $F^{N}(c)$ with constant curvature $c\ge 0$ , and the normalized scalar curvature $R_0$ of $M$ satisfies $R_0>\frac{A_n}{A_n+4n-8}(c+H^2),$ where $A_n=n^3-5n^2+8n$ , and $H$ is the mean curvature of $M$ , then $M$ is isometric to a standard $n$ -sphere.     

Syzygies and tensor product of modules

We give an application of the New Intersection Theorem and prove the following: let $R$ be a local complete intersection ring of codimension $c$ and let $M$ and $N$ be nonzero finitely generated $R$ -modules. Assume $n$ is a nonnegative integer and that the tensor product $M\otimes _{R}N$ is an $(n+c)$ th syzygy of some finitely generated $R$ -module. If ${{\mathrm{Tor}}}^{R}_{>0}(M,N)=0$ , then both $M$ and $N$ are $n$ th syzygies of some finitely generated $R$ -modules.     

Characterization of Siegel cusp forms by the growth of their Fourier coefficients

We characterize all Siegel cusp forms of degree $n$ and large weight $k$ by the growth of their Fourier coefficients. More precisely we prove, among other related results, that if the Fourier coefficients of a modular form on the congruence subgroup $\Gamma _0^n(N)$ of square–free level $N$ satisfy the “Hecke bound” at the cusp $\infty $ , then it must be a cusp form, provided $k >2n+1$ .     

Planar Point Sets With Large Minimum Convex Decompositions

We show the existence of sets with $n$ points ( $n\ge 4$ ) for which every convex decomposition contains more than $\frac{35}{32}n-\frac{3}{2}$ polygons, which refutes the conjecture that for every set of $n$ points there is a convex decomposition with at most $n+C$ polygons. For sets having exactly three extreme points we show that more than $n+\sqrt{2(n-3)}-4$ polygons may be necessary to form a convex decomposition.     

Distinct Distances on Curves Via Rigidity

It is shown that $N$ points on a real algebraic curve of degree $n$ in ${\mathbb R}^d$ always determine $\gtrsim _{n,d}$ ${N^{1+\frac{1}{4}}}$ distinct distances, unless the curve is a straight line or the closed geodesic of a flat torus. In the latter case, there are arrangements of $N$ points which determine $\lesssim $ ${N}$ distinct distances. The method may be applied to other quantities of interest to obtain analogous exponent gaps. An important step in the proof involves understanding the structural rigidity of certain frameworks on curves.     

On the cohomology of moduli spaces of (weighted) stable rational curves

We give a recursive algorithm for computing the character of the cohomology of the moduli space ${\overline{M}}_{0,n}$ of stable $n$ -pointed genus zero curves as a representation of the symmetric group $\mathbb{S }_n$ on $n$ letters. Using the algorithm we can show a formula for the maximum length of this character. Our main tool is connected to the moduli spaces of weighted stable curves introduced by Hassett.