Search

We prove a characterization of F-rationality in terms of tight closure of products of parameter ideals. Our results are inspired by the theory of complete ideals for surfaces and, in particular, the fundamental results of Lipman-Teissier and Cutkosky characterizing rational surface singularities in terms of products of complete ideals, but are valid also in higher dimensions.

It is shown that $S(G) = O\left(m/\log_2 m + d\right)$ pebbles are sufficient to pebble any DAG $G=(V,E)$, with $m$ edges and maximum in-degree $d$. It was previously known that $S(G) = O\left(d n/\log n\right)$. The result builds on two novel ideas. The first is the notion of $B-budget\ decomposition$ of a DAG $G$, an efficiently computable partition of $G$ into at most $2^{\lfloor \frac{m}{B} \rfloor}$ sub-DAGs, whose cumulative space requirement is at most $B$. The second is the challenging vertices technique, which constructs a pebbling schedule for $G$ from a pebbling schedule for a simplified DAG $G'$, obtained by removing from $G$ a selected set of vertices $W$ and their incident edges. This technique also yields improved pebbling upper bounds for DAGs with bounded genus and for DAGs with bounded topological depth.

Asymptotically tight lower bounds are derived for the Input/Output (I/O) complexity of a class of dynamic programming algorithms including matrix chain multiplication, optimal polygon triangulation, and the construction of optimal binary search trees. Assuming no recomputation of intermediate values, we establish an $\Omega\left(\frac{n^3}{\sqrt{M}B}\right)$ I/O lower bound, where $n$ denotes the size of the input and $M$ denotes the size of the available fast memory (cache). When recomputation is allowed, we show the same bound holds for $M < cn$, where $c$ is a positive constant. In the case where $M \ge 2n$, we show an $\Omega\left(n/B\right)$ I/O lower bound. We also discuss algorithms for which the number of executed I/O operations matches asymptotically each of the presented lower bounds, which are thus asymptotically tight. Additionally, we refine our general method to obtain a lower bound for the I/O complexity of the Cocke-Younger-Kasami algorithm, where the size of the grammar impacts the I/O complexity. An upper bound with asymptotically matching performance in many cases is also provided.

In this article we obtain uniform effective upper bounds for the projective dimension and the Castelnuovo-Mumford regularity of homogeneous ideals inside a standard graded polynomial ring $S$ over a field. Such bounds are independent of the number of variables of $S$, in the spirit of Stillman's conjecture and of the Ananyan-Hochster's theorem, and depend on partial data extracted from the beginning or the end of the resolution. In this direction, we extend a result of McCullough from 2012 regarding a bound on regularity in terms of half the syzygies to a bound on the projective dimension and the regularity of an ideal in terms of a fraction of the syzygies.

Let $(R,\mathfrak{m})$ be a complete local ring, and $G={\rm gr}_{\mathfrak{m}}(R)$ be its associated graded ring. We introduce a homogenization technique which allows to relate $G$ to the special fiber and $R$ to the generic fiber of a "Gr\"obner-like" deformation. Using this technique we prove sharp results concerning the connectedness of $R$ and $G$. We also construct a family of local domains which fail to satisfy Abhyankar's inequality for the Hilbert-Samuel multiplicity. However, we prove a version of the inequality which holds when $R$ is connected in codimension one.

The purpose of this note is to show that a finitely generated graded module $M$ over $S=k[x_1,\ldots,x_n]$, $k$ a field, is sequentially Cohen-Macaulay if and only if its arithmetic degree ${\rm adeg}(M)$ agrees with ${\rm adeg}(F/{\rm gin}_{revlex}(U))$, where $F$ is a graded free $S$-module and $M \cong F/U$. This answers positively a conjecture of Lu and Yu from 2016., Comment: 7 pages

In this article we show that the symbolic Rees algebra of a mixed ladder determinantal ideal is strongly $F$-regular. Furthermore, we prove that the symbolic associated graded algebra of a mixed ladder determinantal ideal is $F$-pure. The latter implies that mixed ladder determinantal rings are $F$-pure. We also show that ideals of the poset of minors of a generic matrix give rise to $F$-pure algebras with straightening law., Comment: 19 pages, 2 figures

The rate of a standard graded $K$-algebra $A$ is a measure of the growth of the shifts in a minimal free resolution of $K$ as an $A$-module. In particular $A$ has rate one if and only if it is Koszul. It is known that a generic Artinian Gorenstein algebra of embedding dimension $n \geq 3$ and socle degree $s=3$ is Koszul. We prove that a generic Artinian Gorenstein algebra with $n\geq 4$ and $s \ge 3 $ has rate $ \lfloor \frac{s}{2} \rfloor. $ In the process we show that such an algebra is generated in degree $\lfloor \frac{s}{2} \rfloor +1. $ This gives a partial positive answer to a longstanding conjecture stated by the first author on the minimal free resolution of a generic Artinian Gorenstein ring of odd socle degree., Comment: 13 pages

In this survey paper we first present the main properties of sequentially Cohen-Macaulay modules. Some basic examples are provided to help the reader with quickly getting acquainted with this topic. We then discuss two generalizations of the notion of sequential Cohen-Macaulayness which are inspired by a theorem of J\"urgen Herzog and the third author.

Inspired by methods in prime characteristic in commutative algebra, we introduce and study combinatorial invariants of seminormal monoids. We relate such numbers with the singularities and homological invariants of the semigroup ring associated to the monoid. Our results are characteristic independent., Comment: to appear in Mathematische Zeitschrift

We introduce the notion of an $r$-visit of a Directed Acyclic Graph DAG $G=(V,E)$, a sequence of the vertices of the DAG complying with a given rule $r$. A rule $r$ specifies for each vertex $v\in V$ a family of $r$-enabling sets of (immediate) predecessors: before visiting $v$, at least one of its enabling sets must have been visited. Special cases are the $r^{(top)}$-rule (or, topological rule), for which the only enabling set is the set of all predecessors and the $r^{(sin)}$-rule (or, singleton rule), for which the enabling sets are the singletons containing exactly one predecessor. The $r$-boundary complexity of a DAG $G$, $b_{r}\left(G\right)$, is the minimum integer $b$ such that there is an $r$-visit where, at each stage, for at most $b$ of the vertices yet to be visited an enabling set has already been visited. By a reformulation of known results, it is shown that the boundary complexity of a DAG $G$ is a lower bound to the pebbling number of the reverse DAG, $G^R$. Several known pebbling lower bounds can be cast in terms of the $r^{(sin)}$-boundary complexity. A visit partition technique for I/O lower bounds, which generalizes the $S$-partition I/O technique introduced by Hong and Kung in their classic paper "I/O complexity: The Red-Blue pebble game". The visit partition approach yields tight I/O bounds for some DAGs for which the $S$-partition technique can only yield an $\Omega(1)$ lower bound., Comment: Extended version of manuscript published in the Proceedings of FSTTCS22

We survey results produced from the interaction between methods in prime characteristic and combinatorial commutative algebra. We showcase results for edge ideals, toric varieties, Stanley-Reisner rings, and initial ideals that were proven via Frobenius. We also discuss results for monomial ideals obtained using Frobenius-like maps. Finally, we present results for $F$-pure rings that were inspired by work done for Stanley-Reisner rings., Comment: 35 pages

We study when blowup algebras are $F$-split or strongly $F$-regular. Our main focus is on algebras given by symbolic and ordinary powers of ideals of minors of a generic matrix, a symmetric matrix, and a Hankel matrix. We also study ideals of Pfaffians of a skew-symmetric matrix. We use these results to obtain bounds on the degrees of the defining equations for these algebras. We also prove that the limit of the normalized regularity of the symbolic powers of these ideals exists and that their depth stabilizes. Finally, we show that, for determinantal ideals, there exists a monomial order for which taking initial ideals commutes with taking symbolic powers. To obtain these results we develop the notion of $F$-split filtrations and symbolic $F$-split ideals., Comment: Final version. This preprint corrects, replaces, and expands the work done in preprint arXiv:2004.03831, which contains a mistake Lemma 5.4. The new version changes some terminology. We also added a new result about F-regularity for symbolic Rees algebras of ideals associated to symmetric matrices (Theorem 6.16)

Let $S$ be a polynomial ring over any field $\Bbbk$, and let $P \subseteq S$ be a non-degenerate homogeneous prime ideal of height $h$. When $\Bbbk$ is algebraically closed, a classical result attributed to Castelnuovo establishes an upper bound on the number of linearly independent quadrics contained in $P$ which only depends on $h$. We significantly extend this result by proving that the number of minimal generators of $P$ in any degree $j$ can be bounded above by an explicit function that only depends on $j$ and $h$. In addition to providing a bound for generators in any degree $j$, not just for quadrics, our techniques allow us to drop the assumption that $\Bbbk$ is algebraically closed. By means of standard techniques, we also obtain analogous upper bounds on higher graded Betti numbers of any radical ideal., Comment: 15 pages

We survey most of the known results concerning the Eisenbud-Green-Harris Conjecture. Our presentation includes new proofs of several theorems, as well as a unified treatment of many results which are otherwise scattered in the literature. We include a final section with some applications, and examples., Comment: 25 pages, minor changes from previously posted version

We estimate the Castelnuovo-Mumford regularity of ideals in a polynomial ring over a field by studying the regularity of certain modules generated in degree zero and with linear relations. In dimension one, this process gives a new type of upper bounds. By means of recursive techniques this also produces new upper bounds for ideals in any dimension., Comment: 8 pages; comments are welcome

We prove an explicit uniform Chevalley theorem for direct summands of graded polynomial rings in mixed characteristic. Our strategy relies on the introduction of a new type of differential powers, which do not require the existence of a p-derivation on the direct summand., Comment: Final version

IoT technologies pose serious challenges to digital Forensics. The acquisition of digital evidence is hindered by the number and extreme variety of IoT items, often lacking physical interfaces, connected in unprotected networks, feeding data to uncontrolled cloud services. In this paper we address "Information Quality" in IoT Forensics, taking into account different levels of complexity and included human factors. After drawing a theoretical framework on data quality and information quality, we focus on forensic analysis challenges in IoT environments, providing a use case of evidence collection for investigative purposes. At the end, we propose a formal framework for assessing information quality of IoT devices for Forensics analysis., Comment: accepted for publication in Journal of Applied Logics (2020)

We present COPSIM a parallel implementation of standard integer multiplication for the distributed memory setting, and COPK a parallel implementation of Karatsuba's fast integer multiplication algorithm for a distributed memory setting. When using $\mathcal{P}$ processors, each equipped with a local non-shared memory, to compute the product of tho $n$-digits integer numbers, under mild conditions, our algorithms achieve optimal speedup of the computational time. That is, $\mathcal{O}\left(n^2/\mathcal{P}\right)$ for COPSIM, and $\mathcal{O}\left(n^{\log_2 3}/\mathcal{P}\right)$ for COPK. The total amount of memory required across the processors is $\mathcal{O}\left(n\right)$, that is, within a constant factor of the minimum space required to store the input values. We rigorously analyze the Input/Output (I/O) cost of the proposed algorithms. We show that their bandwidth cost (i.e., the number of memory words sent or received by at least one processors) matches asymptotically corresponding known I/O lower bounds, and their latency (i.e., the number of messages sent or received in the algorithm's critical execution path) is asymptotically within a multiplicative factor $\mathcal{O}\left(\log^2_2 \mathcal{P}\right)$ of the corresponding known I/O lower bounds. Hence, our algorithms are asymptotically optimal with respect to the bandwidth cost and almost asymptotically optimal with respect to the latency cost.

We prove that deformation of F-injectivity holds for local rings $(R,\mathfrak{m})$ that admit secondary representations of $H^i_{\mathfrak{m}}(R)$ which are stable under the natural Frobenius action. As a consequence, F-injectivity deforms when $(R,\mathfrak{m})$ is sequentially Cohen-Macaulay (or more generally when all the local cohomology modules $H^i_{\mathfrak{m}}(R)$ have no embedded attached primes). We obtain some additional cases if $R/\mathfrak{m}$ is perfect or if $R$ is $\mathbb{N}$-graded., Comment: 9 pages. Minor changes from previous version

Let $S$ be a standard graded polynomial ring over a field, and $I$ be a homogeneous ideal that contains a regular sequence of degrees $d_1,\ldots,d_n$. We prove the Eisenbud-Green-Harris conjecture when the forms of the regular sequence satisfy $d_i \geqslant \sum_{j=1}^{i-1}(d_j-1)$, improving a result obtained in 2008 by the first author and Maclagan. Except for the sporadic case of a regular sequence of five quadrics, recently proved by G\"unt\"urk\"un and Hochster, the results of this article recover all known cases of the conjecture where only the degrees of the regular sequence are fixed, and include several additional ones., Comment: 8 pages; minor modifications from previous version; change of title

We prove a Cayley-Bacharach-type theorem for points in projective space $\mathbb{P}^n$ that lie on a complete intersection of $n$ hypersurfaces. This is made possible by new bounds on the growth of the Hilbert function of almost complete intersections., Comment: 12 pages, 1 figure. Minor modifications, citations added, acknowledged a result which was known in the literature

We introduce the notion of E-depth of graded modules over polynomial rings to measure the depth of certain Ext modules. First, we characterize graded modules over polynomial rings with (sufficiently) large E-depth as those modules whose (sufficiently) partial general initial submodules preserve the Hilbert function of local cohomology modules supported at the irrelevant maximal ideal, extending a result of Herzog and Sbarra on sequentially Cohen-Macaulay modules. Second, we describe the cone of local cohomology tables of modules with sufficiently high E-depth, building on previous work of the second author and Smirnov. Finally, we obtain a non-Artinian version of a socle-lemma proved by Kustin and Ulrich., Comment: 23 pages; we corrected some inaccuracies from previous version and performed minor changes

We study the problem of $\mathfrak{m}$-adic stability of F-singularities, that is, whether the property that a quotient of a local ring $(R,\mathfrak{m})$ by a non-zero divisor $x \in \mathfrak{m}$ has good F-singularities is preserved in a sufficiently small $\mathfrak{m}$-adic neighborhood of $x$. We show that $\mathfrak{m}$-adic stability holds for F-rationality in full generality, and for F-injectivity, F-purity and strong F-regularity under certain assumptions. We show that strong F-regularity and F-purity are not stable in general. Moreover, we exhibit strong connections between stability and deformation phenomena, which hold in great generality., Comment: Comments are welcome