Inequalities for quadratic polynomials in Hermitian and dissipative operators

Let T be a Hermitian operator on a Banach space and let P be a real quadratic polynomial. Among other inequalities we give lower bounds for |P(T)x| in terms of |x|, |Tx|, and |T²x|. As a special case we deduce extensions of some classical inequalities involving derivatives of a function and obtain some new inequalities of this kind.     

Searching ordered structures

Suppose distinct real numbers are assigned to the elements of a finite partially ordered set P in an order preserving manner. The problem of determining the fewest numbers of comparisons required to locate a given number x in P is investigated. Some general bounds are provided for the problem and analyzed in detail for the case that P is a product of chains and that P is a rooted forest.     

Systems of second-order linear ODE’s with constant coefficients and their symmetries

Starting from the study of the symmetries of systems of 4 second-order linear ODEs with constant real coefficients, we determine the dimension and generators of the symmetry algebra for systems of n equations described by a diagonal Jordan canonical form. We further prove that some dimensions between the lower and upper bounds cannot be attained in the diagonal case, and classify the Levi factors of the symmetry algebras.     

Hausdorff and upper box dimension estimate of hyperbolic recurrent sets

In this paper, under the open set condition we have determined the lower and upper bounds of the Hausdorff dimensions and the upper box-counting dimensions of the limit sets of hyperbolic recurrent iterated function systems in terms of the unique zeros h and H of the two pressure functions. In addition, we have estimated the bounds of h, H-dimensional Hausdorff and packing measures. The result in this paper generalizes existing results about fractal dimensions of many other iterated function systems.     

Computing bounds for the probability of the union of events by different methods

Let A ₁,??,A _n be arbitrary events. The underlying problem is to give lower and upper bounds on the probability P(A ₁?????A _n ) based on $P(A_{i_{1}}\cap\cdots\cap A_{i_{k}})$ , 1??i ₁<?<i _k ??n, where k=1,??,d, and d??n (usually d?n) is a certain integer, called the order of the problem or the bound. Most bounding techniques fall in one of the following two main categories: those that use (hyper)graph structures and the ones based on binomial moment problems. In this paper we compare bounds from the two categories with each other, in particular the bounds yielded by univariate and multivariate moment problems are compared with Bukszár??s hypermultitree bounds. In the comparison we considered several numerical examples, most of which have important practical applications, e.g., the approximation of the values of multivariate cumulative distribution functions or the calculation of network reliability. We compare the bounds based on how close they are to the real value and the time required to compute them, however, the problems arising in the implementations of the methods as well as the limitations of the usability of the bounds are also illustrated.     

Distance bounds for algebraic geometric codes

Various methods have been used to obtain improvements of the Goppa lower bound for the minimum distance of an algebraic geometric code. The main methods divide into two categories, and all but a few of the known bounds are special cases of either the Lundell-McCullough floor bound or the Beelen order bound. The exceptions are recent improvements of the floor bound by Güneri, Stichtenoth, and Taskin, and by Duursma and Park, and of the order bound by Duursma and Park, and by Duursma and Kirov. In this paper, we provide short proofs for all floor bounds and most order bounds in the setting of the van Lint and Wilson AB method. Moreover, we formulate unifying theorems for order bounds and formulate the DP and DK order bounds as natural but different generalizations of the Feng-Rao bound for one-point codes.     

Lower Bounds for Scheduling on Identical Parallel Machines with Heads and Tails

In this paper, we investigate new lower bounds for the P|r _j ,q _j |C _max scheduling problem. A new bin packing based lower bound, as well as several new lifting procedures are derived for this strongly NP -hard problem. Extensive numerical experiments show that the proposed lower bounds consistently outperform the best existing ones.     

Invariants of real rational symplectic 4-manifolds and lower bounds in real enumerative geometry

Following the approach of Gromov and Witten, we construct invariants under deformation of real rational symplectic 4-manifolds. These invariants provide lower bounds for the number of real rational J-holomorphic curves in a given homology class passing through a given real configuration of points. To cite this article: J.-Y. Welschinger, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

Markov-Bernstein inequalities for generalized Gegenbauer weight

The Markov-Bernstein inequalities for generalized Gegenbauer weight are studied. A special basis of the vector space Pn of real polynomials in one variable of degree at most equal to n is proposed. It is produced by quasi-orthogonal polynomials with respect to this generalized Gegenbauer measure. Thanks to this basis the problem to find the Markov-Bernstein constant is separated in two eigenvalue problems. The first has a classical form and we are able to give lower and upper bounds of the Markov-Bernstein constant by using the Newton method and the classical qd algorithm applied to a sequence of orthogonal polynomials. The second is a generalized eigenvalue problem with a five diagonal matrix and a tridiagonal matrix. A lower bound is obtained by using the Newton method applied to the six term recurrence relation produced by the expansion of the characteristic determinant. The asymptotic behavior of an upper bound is studied. Finally, the asymptotic behavior of the Markov-Bernstein constant is O(n²) in both cases.     

Overlaps help: Improved bounds for group testing with interval queries

Given a finite ordered set of items and an unknown distinguished subset P of up to p positive elements, identify the items in P by asking the least number of queries of the type ‘‘does the subset Q intersect P?”, where Q is a subset of consecutive elements of {1,2,…,n}. This problem arises, e.g., in computational biology, in a particular method for determining splice sites in genes. We consider time-efficient algorithms where queries are arranged in a fixed number s of stages: In each stage, queries are performed in parallel. In a recent bioinformatics paper, we proved optimality (subject to lower-order terms) with respect to the number of queries, of some strategies for the special cases p=1 or s=2. Exploiting new ideas, we are now able to provide improved lower bounds for any p?2 and s?3 and improved upper bounds for larger s. Most notably, our new bounds converge as s grows. Our new query scheme uses overlapping query intervals within a stage, which is effective for large enough s. This contrasts with our previous results for s?2 where optimal strategies were implemented by disjoint queries. The main open problem is whether overlaps help already in the case of small s?3. Anyway, the remaining gaps between the current upper and lower bounds for any fixed s?3 amount to small constant factors in the main term. The paper ends with a discussion of practical implications in the case that the positive elements are well separated.     

Mixed-norm estimates for a class of nonisotropic directional maximal operators and Hilbert transforms

For all d?2 and p∈(1,max(2,(d+1)/2)], we prove sharp Lp to Lp(Lq) estimates (modulo an endpoint) for a directional maximal operator associated to curves generated by the dilation matrices exp((logt)P), where P has real entries and eigenvalues with positive real part. For the corresponding Hilbert transform we prove an analogous result for all d?2 and p∈(1,2]. As corollaries, we prove Lp bounds for variable kernel singular integral operators and Nikodym-type maximal operators taking averages over certain families of curved sets in Rd.     

Bounding the First Dirichlet Eigenvalue of a Tube Around a Complex Submanifold of ℂP n (λ) in Terms of the Degrees of the Polynomials Defining It

We obtain upper bounds for the first Dirichlet eigenvalue of a tube around a complex submanifold P of ?P ⁿ (λ) which depends only on the radius of the tube, the degrees of the polynomials defining P, and the first eigenvalue of the tube around some model centers. The bounds are sharp on these models. Moreover, when the models used are ?P ^q (λ) or Q ^n?1(λ) these bounds also provide gap phenomena and comparison results.     

Soft car sequencing with colors: Lower bounds and optimality proofs

This paper is a study of the car sequencing problem, when feature spacing constraints are soft and colors of vehicles are taken into account. Both pseudo-polynomial algorithms and lower bounds are presented for parts of the problem or family of instances. With this set of lower bounds, we establish the optimality (up to the first non-trivial criteria) of 54% of best known solutions for the benchmark used for the Roadef Challenge 2005. We also prove that the optimal penalty for a single ratio constraint N/P can be computed in O(P) and that determining the feasibility of a car sequencing instance limited to a pair of simple ratio constraints can be achieved by dynamic programming. Finally, we propose a solving algorithm exploiting these results within a local search approach. To achieve this goal, a new meta-heuristic (star relinking) is introduced, designed for the optimization of an aggregation of criteria, when the optimization of each single criterion is a polynomial problem.     

On Markov?CKrein characterization of the mean waiting time in M/G/K and other queueing systems

We propose a new research direction to reinvigorate research into better understanding of the M/G/K and other queueing systems??via obtaining tight bounds on the mean waiting time as functions of the moments of the service distribution. Analogous to the classical Markov?CKrein theorem, we conjecture that the bounds on the mean waiting time are achieved by service distributions corresponding to the upper/lower principal representations of the moment sequence. We present analytical, numerical, and simulation evidence in support of our conjectures.     

Natural limitations of decision procedures for arithmetic with bounded quantifiers

We study the complexity of the decision problem of a variant of arithmetic with bounded quantifiers. By contrast with the usual asymptotic complexity results, where one only deals with suitably long sentences, our limitative results have a concrete character, so as to find application in physics. We develop the mathematical framework for our lower bounds up to the point where their physical meaning is evident. Imagining that Turing machineM materializes as a real computerM′, we give a rigorous formulation of the simplest space-time features ofM′, by essentially requiring that (i) each state ofM occupies some space, (ii) no signal between states and scanning head can travel at infinite speed. WhenM provides a decision procedure for arithmetic with bounded quantifiers, there exist stringent lower bounds for the “time”t(j) needed byM′ to solve the hardest problems of length smaller thanj, no matter the number of states ofM. We discuss several applications of our results.     

On some classes of polynomials with nonnegative coefficients and a given factor

For a given real polynomial f without positive roots we study polynomials g of lowest degree such that the product gf has positive (nonnegative, respectively) coefficients. We show that for quadratic f with negative linear coefficient every such g must have positive coefficients and exhibit an easy procedure for the determination of g. If f has only integer coefficients we show that g with integer coefficients can be found. Furthermore, for some classes of polynomials f we give upper (lower, respectively) bounds for the degrees of g.     

Lower bounds for positive and negative parts of measures and the arrangement of singularities of their Laplace transforms

For a real measure with variation V(x) satisfying the estimate V(x) ≤ c ₀ exp(Cx) and for the Laplace transform holomorphic in the disk {¦ -C¦ ≤ C} and having at least one pole of order m, we obtain lower bounds for the positive and negative parts of the measure V _± (x) > cx ^m , x > x ₀. We establish lower bounds for V _+- (x) on “short” intervals. Applications to number theory of the results obtained are considered.     

The distance from a matrix polynomial to matrix polynomials with a prescribed multiple eigenvalue

For a matrix polynomial P(λ) and a given complex number μ, we introduce a (spectral norm) distance from P(λ) to the matrix polynomials that have μ as an eigenvalue of geometric multiplicity at least κ, and a distance from P(λ) to the matrix polynomials that have μ as a multiple eigenvalue. Then we compute the first distance and obtain bounds for the second one, constructing associated perturbations of P(λ).     

Completely reducible hypersurfaces in a pencil

We study completely reducible fibers of pencils of hypersurfaces on Pn and associated codimension one foliations of Pn. Using methods from theory of foliations we obtain certain upper bounds for the number of these fibers as functions only of n. Equivalently this gives upper bounds for the dimensions of resonance varieties of hyperplane arrangements. We obtain similar bounds for the dimensions of the characteristic varieties of the arrangement complements.     

Bounds for codes and designs in complex subspaces

We introduce the concepts of complex Grassmannian codes and designs. Let $\mathcal{G}_{m,n}$ denote the set of m-dimensional subspaces of ? ⁿ : then a code is a finite subset of $\mathcal{G}_{m,n}$ in which few distances occur, while a design is a finite subset of $\mathcal{G}_{m,n}$ that polynomially approximates the entire set. Using Delsarte’s linear programming techniques, we find upper bounds for the size of a code and lower bounds for the size of a design, and we show that association schemes can occur when the bounds are tight. These results are motivated by the bounds for real subspaces recently found by Bachoc, Bannai, Coulangeon and Nebe, and the bounds generalize those of Delsarte, Goethals and Seidel for codes and designs on the complex unit sphere.