Remez-type inequality for discrete sets

The classical Remez inequality bounds the maximum of the absolute value of a polynomial P(x) of degree d on [−1, 1] through the maximum of its absolute value on any subset Z of positive measure in [−1, 1]. Similarly, in several variables the maximum of the absolute value of a polynomial P(x) of degree d on the unit cube Q ₁ ⁿ ⊂ ℝ ⁿ can be bounded through the maximum of its absolute value on any subset Z ⊂ Q ₁ ⁿ of positive n-measure. The main result of this paper is that the n-measure in the Remez inequality can be replaced by a certain geometric invariant ω _d (Z) which can be effectively estimated in terms of the metric entropy of Z and which may be nonzero for discrete and even finite sets Z.     

Semidefinite representation of convex sets

Let be a semialgebraic set defined by multivariate polynomials g _i (x). Assume S is convex, compact and has nonempty interior. Let , and ∂ S (resp. ∂ S _i ) be the boundary of S (resp. S _i ). This paper, as does the subject of semidefinite programming (SDP), concerns linear matrix inequalities (LMIs). The set S is said to have an LMI representation if it equals the set of solutions to some LMI and it is known that some convex S may not be LMI representable (Helton and Vinnikov in Commun Pure Appl Math 60(5):654–674, 2007). A question arising from Nesterov and Nemirovski (SIAM studies in applied mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 1994), see Helton and Vinnikov in Commun Pure Appl Math 60(5):654–674, 2007 and Nemirovski in Plenary lecture, International Congress of Mathematicians (ICM), Madrid, Spain, 2006, is: given a subset S of , does there exist an LMI representable set Ŝ in some higher dimensional space whose projection down onto equals S. Such S is called semidefinite representable or SDP representable. This paper addresses the SDP representability problem. The following are the main contributions of this paper: (i) assume g _i (x) are all concave on S. If the positive definite Lagrange Hessian condition holds, i.e., the Hessian of the Lagrange function for optimization problem of minimizing any nonzero linear function ℓ ^T x on S is positive definite at the minimizer, then S is SDP representable. (ii) If each g _i (x) is either sos-concave ( − ∇² g _i (x) = W(x) ^T W(x) for some possibly nonsquare matrix polynomial W(x)) or strictly quasi-concave on S, then S is SDP representable. (iii) If each S _i is either sos-convex or poscurv-convex (S _i is compact convex, whose boundary has positive curvature and is nonsingular, i.e., ∇g _i (x) ≠ 0 on ∂ S _i ∩ S), then S is SDP representable. This also holds for S _i for which ∂ S _i ∩ S extends smoothly to the boundary of a poscurv-convex set containing S. (iv) We give the complexity of Schmüdgen and Putinar’s matrix Positivstellensatz, which are critical to the proofs of (i)–(iii).      

On a matrix inequality

Let S_n be the set of all n×n real symmetric matrices. We give a complete characterization of the set of matrix-convex functions defined on S_n. We also consider connections between matrix monotonicity in the Löwner sense and matrix convexity.     

Remez-type inequality on sets with cusps

A Remez-type inequality is proved for a large family of sets with cusps in R^N${\mathbb{R}}^N$, including compact, fat and semialgebraic (or subanalytic) sets.     

Convex sets with semidefinite representation

We provide a sufficient condition on a class of compact basic semialgebraic sets for their convex hull co(K) to have a semidefinite representation (SDr). This SDr is explicitly expressed in terms of the polynomials g _j that define K. Examples are provided. We also provide an approximate SDr; that is, for every fixed , there is a convex set such that (where B is the unit ball of ), and has an explicit SDr in terms of the g _j ’s. For convex and compact basic semi-algebraic sets K defined by concave polynomials, we provide a simpler explicit SDr when the nonnegative Lagrangian L _f associated with K and any linear is a sum of squares. We also provide an approximate SDr specific to the convex case.      

A Cauchy-Khinchin matrix inequality

We derive a matrix inequality, which generalizes the Cauchy-Schwarz inequality for vectors, and Khinchin's inequality for zero–one matrices. Furthermore, we pose a related problem on the maximum irregularity of a directed graph with prescribed number of vertices and arcs, and make some remarks on this problem.     

A representation of convex semilinear sets

If F is an ordered field, a subset of n-space over F is said to be semilinear just in case it is a finite Boolean combination of translates of closed halfspaces, where a closed halfspace is the set of all points obeying a homogeneous weak linear inequality with coefficients from F. Andradas, Rubio, and Vélez have shown that closed (open) convex semilinear sets are finite intersections of translates of closed (open) halfspaces (an open halfspace is defined as before, but with a strict inequality). This paper represents arbitrary convex semilinear sets in a manner analogous to that of Andradas, Rubio, and Vélez.     

Minimal representation of convex polyhedral sets

A system of linear inequality and equality constraints determines a convex polyhedral set of feasible solutionsS. We consider the relation of all individual constraints toS, paying special attention to redundancy and implicit equalities. The main theorem derived here states that the total number of constraints together determiningS is minimal if and only if the system contains no redundant constraints and/or implicit equalities. It is shown that the existing theory on the representation of convex polyhedral sets is a special case of the theory developed here.The author is indebted to Dr. A. C. F. Vorst (Erasmus University, Rotterdam, Holland) for stimulating discussions and comments, which led to considerable improvements in many proofs. Most of the material in this paper originally appeared in the author's dissertation (Ref. 1). The present form was prepared with partial support from a NATO Science Fellowship for the Netherlands Organization for the Advancement of Pure Research (ZWO) and a CORE Research Fellowship.     

Stable theories and representation over sets

In this paper we give characterizations of the stable and ?₀‐stable theories, in terms of an external property called representation. In the sense of the representation property, the mentioned classes of first‐order theories can be regarded as “not very complicated”.     

A Cauchy--Khinchin--van Dam matrix inequality

We derive a matrix inequality, which generalizes the Cauchy inequality for vectors, Khinchin's inequality for zero-one matrices and van Dam's inequality for matrices.     

On the representation of partially ordered sets

It is well known that any distributive poset (short for partially ordered set) has an isomorphic representation as a poset (Q, ?) such that the supremum and the infimum of any finite setF ofP correspond, respectively to the union and intersection of the images of the elements ofF. Here necessary and sufficient conditions are given for similar isomophic representation of a poset where however the supremum and infimum of also infinite subsetsI correspond to the union and intersection of images of elements ofI.     

On the representation of partially ordered sets

It is well known that any distributive poset (short for partially ordered set) has an isomorphic representation as a poset (Q, ⊆) such that the supremum and the infimum of any finite setF ofP correspond, respectively to the union and intersection of the images of the elements ofF. Here necessary and sufficient conditions are given for similar isomophic representation of a poset where however the supremum and infimum of also infinite subsetsI correspond to the union and intersection of images of elements ofI.     

Boolean and distributive ordered sets: Characterization and representation by sets

Boolean ordered sets generalize Boolean lattices, and distributive ordered sets generalize distributive lattices. Ideals, prime ideals, and maximal ideals in ordered sets are defined, and some well-known theorems on Boolean lattices, such as the Glivenko-Stone theorem and the Stone representation theorem, are generalized to Boolean ordered sets. A prime ideal theorem for distributive ordered sets is formulated, and the Birkhoff representation theorem is generalized to distributive ordered sets. Fundamental are the embedding theorems for Boolean ordered sets and for distributive ordered sets.Financial support of the Grant Agency of the Czech Republic under the grant No. 201/93/0950 is gratefully acknowledged.     

Error bounds for inequality systems defining convex sets

The main goal in this paper is to devise an approach to explicitly calculate the constant in the Hoffman’s error bound for (not necessarily convex) inequality systems defining convex sets. We give a constructive proof of the Hoffman’s error bound and show that we can use our method to calculate the constant at least in simple cases.

     

Constructing finite sets from their representation functions

Acta Mathematica Hungarica - For any positive integer m, let $$\mathbb{Z}_{m}$$ be the set of residue classes modulo m. For $$A\subseteq \mathbb{Z}_{m}$$ and $$\overline{n}\in \mathbb{Z}_{m}$$ ,...     

Linear equations and sets of integers

We prove two results concerning solvability of a linear equation in sets of integers. In particular, it is shown that for every k∈ℕ, there is a noninvariant linear equation in k variables such that if A⫅{1,…,N} has no solution to the equation then |A|\leqq 2^-ck/(logk)2N|A|\leqq 2^{-ck/{(\log k)}^{2}}N, for some absolute constant c>0, provided that N is large enough.