Toric Initial Ideals of Δ-Normal Configurations: Cohen-Macaulayness and Degree Bounds

A normal (respectively, graded normal) vector configuration\({\cal A}\) defines the toric ideal \({I}_{\cal A}\) of a normal (respectively, projectively normal) toric variety. These ideals are Cohen-Macaulay, and when \({\cal A}\) is normal and graded, \({I}_{\cal A}\) is generated in degree at most the dimension of \({I}_{\cal A}\). Based on this, Sturmfels asked if these properties extend to initial ideals—when \({\cal A}\) is normal, is there an initial ideal of \({I}_{\cal A}\) that is Cohen-Macaulay, and when \({\cal A}\) is normal and graded, does \({I}_{\cal A}\) have a Gröbner basis generated in degree at most dim(\({I}_{\cal A}\)) ? In this paper, we answer both questions positively for Δ-normal configurations. These are normal configurations that admit a regular triangulation Δ with the property that the subconfiguration in each cell of the triangulation is again normal. Such configurations properly contain among them all vector configurations that admit a regular unimodular triangulation. We construct non-trivial families of both Δ-normal and non-Δ-normal configurations.     

Sequences of orthogonal Laurent polynomials,bi-orthogonality and quadrature formulas on the unit circle

In this paper, the construction of orthogonal bases in the space of Laurent polynomials on the unit circle is considered. As an application, a connection with the so-called bi-orthogonal systems of trigonometric polynomials is established and quadrature formulas on the unit circle based on Laurent polynomials are studied.     

On the universal Gröbner bases of toric ideals of graphs

The universal Gröbner basis of an ideal is a Gröbner basis with respect to all term orders simultaneously. We characterize in graph theoretical terms the elements of the universal Gröbner basis of the toric ideal of a graph. We also provide a new degree bound. Finally, we give examples of graphs for which the true degrees of their circuits are less than the degrees of some elements of the Graver basis.     

On the number of distinct multinomial coefficients

We study M(n), the number of distinct values taken by multinomial coefficients with upper entry n, and some closely related sequences. We show that both pP(n)/M(n) and M(n)/p(n) tend to zero as n goes to infinity, where pP(n) is the number of partitions of n into primes and p(n) is the total number of partitions of n. To use methods from commutative algebra, we encode partitions and multinomial coefficients as monomials.     

Characterization of Smoothness of Multivariate Refinable Functions in Sobolev Spaces

Wavelets are generated from refinable functions by using multiresolution analysis. In this paper we investigate the smoothness properties of multivariate refinable functions in Sobolev spaces. We characterize the optimal smoothness of a multivariate refinable function in terms of the spectral radius of the corresponding transition operator restricted to a suitable finite dimensional invariant subspace. Several examples are provided to illustrate the general theory.

     

Global Minimization of a Multivariate Polynomial using Matrix Methods

The problem of minimizing a polynomial function in several variables over R ⁿ is considered and an algorithm is given. When the polynomial has a minimum the algorithm returns the global minimal value and finds at least one point in every connected component of the set of minimizers. A characterization of such points is given. When the polynomial does not have a minimum the algorithm computes its infimum. No assumption is made on the polynomial.     

单位根上重Hermite插值多项式的逼近阶

设ｆ（ｚ）在｜ｚ｜≤１解析，在｜ｚ｜≤１连续．本文得到了基于单位根的扩充Ｈｅｒｍｉｔｅ插值多项式在｜ｚ｜≤１上一致收敛于ｆ（ｚ）的逼近阶和在｜ｚ｜＝１上平均收敛于ｆ（ｚ）的逼近阶，且一般说来，阶还是精确的．进而说明，重数不同的插值多项式的逼近阶不同于重数相同的插值多项式的逼近阶．     

多元q-Stancu多项式的收敛性及其收敛阶刻画

定义单纯形上的多元q-Stancu多项式,它是著名的Bernstein多项式,q-Bernstein多项式,Stancu多项式的推广.以多元函数的部分连续模及全连续模为度量,建立推广的多元q-Stancu多项式对连续函数的一致收敛定理与收敛阶估计,并以实例加以验证.     

On the complexity of solving quadratic Boolean systems

A fundamental problem in computer science is that of finding all the common zeros of m$m$ quadratic polynomials in n$n$ unknowns over _F2${\mathbb{F}}_2$. The cryptanalysis of several modern ciphers reduces to this problem. Up to now, the best complexity bound was reached by an exhaustive search in 4_log2n2ⁿ$4{log}_{2}n{2}^n$ operations. We give an algorithm that reduces the problem to a combination of exhaustive search and sparse linear algebra. This algorithm has several variants depending on the method used for the linear algebra step. We show that, under precise algebraic assumptions on the input system, the deterministic variant of our algorithm has complexity bounded by O(2^0.841n)$O\left(2^{0.841n}\right)$ when m=n$m=n$, while a probabilistic variant of the Las Vegas type has expected complexity O(2^0.792n)$O\left(2^{0.792n}\right)$. Experiments on random systems show that the algebraic assumptions are satisfied with probability very close to 1. We also give a rough estimate for the actual threshold between our method and exhaustive search, which is as low as 200, and thus very relevant for cryptographic applications.     

Orlicz空间中三角多项式倒数对周期可微函数的逼近定理

利用Orlicz空间内有关不等式技巧在Orlicz空间内研究了用三角多项式的倒数逼近周期可微函数的问题.得到了一个逼近定理及其推论.     

Moduli Spaces of Curves with Quasi-Symmetric Weierstrass GAp Seqnences

In this paper we give an explicit construction of the moduli space of the pointed complete Gorenstein curves of arithmetic genus g with a given quasi-symmetric Weierstrass semigroup, that is, a Weierstrass semigroup whose last gap is equal to 2g – 2. We identify such a curve with its image under the canonical embedding in the (g – 1)-dimensional projective space. By normalizing the coefficients of the quadratic relations and by constructing Gröbner bases of the canonical ideal, we obtain the equations of the moduli space in terms of Buchberger's criterion. Moreover, by analyzing syzygies of the canonical ideal we establish criteria that make the computations less expensive.     

An algebraic geometry algorithm for scheduling in presence of setups and correlated demands

We study here a problem of schedulingn job types onm parallel machines, when setups are required and the demands for the products are correlated random variables. We model this problem as a chance constrained integer program.Methods of solution currently available—in integer programming and stochastic programming—are not sufficient to solve this model exactly. We develop and introduce here a new approach, based on a geometric interpretation of some recent results in Gröbner basis theory, to provide a solution method applicable to a general class of chance constrained integer programming problems.Out algorithm is conceptually simple and easy to implement. Starting from a (possibly) infeasible solution, we move from one lattice point to another in a monotone manner regularly querying a membership oracle for feasibility until the optimal solution is found. We illustrate this methodology by solving a problem based on a real system.Corresponding author.     

The Order of Best Approximation in Some Classes of Functions

Starting from the equivalence between the Ditzian–Totik modulus and , where , in this article large classes of functions are introduced for which the modulus can be easily calculated. As a consequence, very good estimates for the bestapproximation are obtained. The attempts to estimate or calculate themodulus can be a very intricateproblem.     

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.     

Combinatorial Aspects of Total Weight Orders over Monomials of Fixed Degree

Among all the restrictions of weight orders to the subsets of monomials with a fixed degree, we consider those that yield a total order. Furthermore, we assume that each weight vector consists of an increasing tuple of weights. Every restriction, which is shown to be achieved by some monomial order, is interpreted as a suitable linearization of the poset arising by the intersection of all the weight orders. In the case of three variables, an enumeration is provided. For a higher number of variables, we show a necessary condition for obtaining such restrictions, using deducibility rules applied to homogeneous inequalities. The logarithmic version of this approach is deeply related to classical results of Farkas type, on systems of linear inequalities. Finally, we analyze the linearizations determined by sequences of prime numbers and provide some connections with topics in arithmetic.