Computing the dimension of a semi-algebraic set

In this paper, we consider the problem of computing the real dimension of a given semi-algebraic subset of R ^k, where R is a real closed field. We prove that the dimension k′ of a semi-algebraic set described by s polynomials of degree d in k variables can be computed in time

On the cardinality of a semi-algebraic set

It is shown that the cardinality of a finite semi-algebraic subset over a real closed field can be computed in terms of signatures of effectively constructed quadratic forms.     

Borel measures with a density on a compact semi-algebraic set

Let ${\mathbf{K} \subset \mathbb{R}^n}$ be a compact basic semi-algebraic set. We provide a necessary and sufficient condition (with no à priori bounding parameter) for a real sequence y = (y _α), ${\alpha \in \mathbb{N}^n}$ , to have a finite representing Borel measure absolutely continuous w.r.t. the Lebesgue measure on K, and with a density in ${\cap_{p \geq 1} L_p(\mathbf{K})}$ . With an additional condition involving a bounding parameter, the condition is necessary and sufficient for the existence of a density in L _∞(K). Moreover, nonexistence of such a density can be detected by solving finitely many of a hierarchy of semidefinite programs. In particular, if the semidefinite program at step d of the hierarchy has no solution, then the sequence cannot have a representing measure on K with a density in L _p (K) for any p ≥ 2d.     

The complexification of a lattice seminormed space

We introduce tensor products in the category of lattice seminormed spaces. We show that the reasonable cross vector seminorms on the complexification of a lattice seminormed space are the same as the admissible vector seminorms. We then specialize these results to complexifications of Archimedean Riesz spaces.     

The complexification of engineering

This paper deals with the arrow of complexification of engineering. We claim that the complexification of engineering consists in (a) that shift throughout which engineering becomes a science; thus it ceases to be a (mere) praxis or profession; (b) becoming a science, engineering can be considered as one of the sciences of complexity. In reality, the complexification of engineering is the process by which engineering can be studied, achieved, and understood in terms of knowledge, and not of goods and services any longer. Complex engineered systems and bio‐inspired engineering are so far the two expressions of a complex engineering. © 2011 Wiley Periodicals, Inc. Complexity, 2012     

The Schwartz space of a smooth semi-algebraic stack

Schwartz functions, or measures, are defined on any smooth semi-algebraic (“Nash”) manifold, and are known to form a cosheaf for the semi-algebraic restricted topology. We extend this definition to smooth semi-algebraic stacks, which are defined as geometric stacks in the category of Nash manifolds. Moreover, when those are obtained from algebraic quotient stacks of the form X/G, with X a smooth affine variety and G a reductive group defined over a number field k, we define, whenever possible, an “evaluation map” at each semisimple k-point of the stack, without using truncation methods. This corresponds to a regularization of the sum of those orbital integrals whose semisimple part corresponds to the chosen k-point. These evaluation maps produce, in principle, a distribution which generalizes the Arthur–Selberg trace formula and Jacquet’s relative trace formula, although the former, and many instances of the latter, cannot actually be defined by the purely geometric methods of this paper. In any case, the stack-theoretic point of view provides an explanation for the pure inner forms that appear in many versions of the Langlands, and relative Langlands, conjectures.     

The link of the germ of a semi-algebraic metric space

In this paper we investigate the metric properties of semi-algebraic germs. More precisely we introduce a counterpart to the notion of link for semi-algebraic metric spaces, which is often used to study the topology. We prove that it totally determines the metric type of the germ. We give a nice consequence for semi-algebraically bi-Lipschitz homeomorphic semi-algebraic germs.

     

On the topology of semi-algebraic functions on closed semi-algebraic sets

We consider a closed semi-algebraic set ${X \subset \mathbb{R}^n}$ and a C ² semi-algebraic function ${f : \mathbb{R}^n \rightarrow\mathbb{R}}$ such that ${f_{\vert X}}$ has a finite number of critical points. We relate the topology of X to the topology of the sets ${X \cap \{ f * \alpha \}}$ , where ${* \in \{\le,=,\ge \}}$ and ${\alpha \in \mathbb{R}}$ , and the indices of the critical points of ${f_{\vert X}}$ and ${-f_{\vert X}}$ . We also relate the topology of X to the topology of the links at infinity of the sets ${X \cap \{ f * \alpha\}}$ and the indices of these critical points. We give applications when ${X=\mathbb{R}^n}$ and when f is a generic linear function.     

On the least size of a graph with a given degree set

The degree set of a finite simple graph G is the set of distinct degrees of vertices of G. A theorem of Kapoor et al. [Degree sets for graphs, Fund. Math. 95 (1977) 189-194] asserts that the least order of a graph with a given degree set D is 1+max(D). We look at the analogous problem concerning the least size of a graph with a given degree set D. We determine the least size for the sets D when (i) |D|?3; (ii) D={1,2,…,n}; and (iii) every element in D is at least |D|. In addition, we give sharp upper and lower bounds in all cases.     

Computing roadmaps of semi-algebraic sets on a variety

We consider a semi-algebraic set defined by polynomials in variables which is contained in an algebraic variety . The variety is assumed to have real dimension the polynomial and the polynomials defining have degree at most . We present an algorithm which constructs a roadmap on . The complexity of this algorithm is . We also present an algorithm which, given a point of defined by polynomials of degree at most , constructs a path joining this point to the roadmap. The complexity of this algorithm is These algorithms easily yield an algorithm which, given two points of defined by polynomials of degree at most , decides whether or not these two points of lie in the same semi-algebraically connected component of and if they do computes a semi-algebraic path in connecting the two points.

     

The union of a Riesz set and a Lust-Piquard set is a Riesz set

We prove that the union of a Riesz set and a Lust-Piquard set is a Riesz set. This gives as corollaries known results of Y. Katznelson, R.E. Dressler-L. Pigno, and D. Li. Moreover, we give an example of a Rosenthal set which is dense in Z for the Bohr topology.     

Cohomology of locally closed semi-algebraic subsets

Let k be a non-Archimedean field, let ? be a prime number distinct from the characteristic of the residue field of k. If χ is a separated k-scheme of finite type, Berkovich’s theory of germs allows to define étale ?-adic cohomology groups with compact support of locally closed semi-algebraic subsets of χ ^an . We prove that these vector spaces are finite dimensional continuous representations of the Galois group of k ^sep /k, and satisfy the usual long exact sequence and Künneth formula. This has been recently used by E. Hrushovski and F. Loeser in a paper about the monodromy of the Milnor fibration. In this statement, the main difficulty is the finiteness result, whose proof relies on a cohomological finiteness result for affinoid spaces, recently proved by V. Berkovich.     

Covering the vertex set of a graph with subgraphs of smaller degree

The problem of covering the vertex set of a graph with subsets spanning subgraphs of smaller degree is studied. The result of this study is applied to give a new bound on the chromatic number of a graph in terms of the maximum vertex-degree of the graph and the maximum number of vertices in a clique of the graph. By using this bound, it is shown that if d is at least 7 and e is at least 4, then there is no regular graph of valency d, chromatic number d, whose smallest circuit has at least e edges; this settles a conjecture of Branko Grünbaum.     

Solution of the problem of complexification of devices of a single type

Translated fromIssledovaniya po Prikladnoi Matematike, No. 20, 1992, pp. 107–115.