Optimum quantization and its applications

Minimum sums of moments or, equivalently, distortion of optimum quantizers play an important role in several branches of mathematics. Fejes Tóth's inequality for sums of moments in the plane and Zador's asymptotic formula for minimum distortion in Euclidean d-space are the first precise pertinent results in dimension d?2. In this article these results are generalized in the form of asymptotic formulae for minimum sums of moments, resp. distortion of optimum quantizers on Riemannian d-manifolds and normed d-spaces. In addition, we provide geometric and analytic information on the structure of optimum configurations. Our results are then used to obtain information on

(i)

the minimum distortion of high-resolution vector quantization and optimum quantizers,

(ii)

the error of best approximation of probability measures by discrete measures and support sets of best approximating discrete measures,

(iii)

the minimum error of numerical integration formulae for classes of Hölder continuous functions and optimum sets of nodes,

(iv)

best volume approximation of convex bodies by circumscribed convex polytopes and the form of best approximating polytopes, and

(v)

the minimum isoperimetric quotient of convex polytopes in Minkowski spaces and the form of the minimizing polytopes.

     

Orbits of unbounded energy in quasi-periodic perturbations of geodesic flows

We show that certain mechanical systems, including a geodesic flow in any dimension plus a quasi-periodic perturbation by a potential, have orbits of unbounded energy.The assumptions we make in the case of geodesic flows are:

(a)

The metric and the external perturbation are smooth enough.

(b)

The geodesic flow has a hyperbolic periodic orbit such that its stable and unstable manifolds have a tranverse homoclinic intersection.

(c)

The frequency of the external perturbation is Diophantine.

(d)

The external potential satisfies a generic condition depending on the periodic orbit considered in (b).

The assumptions on the metric are C² open and are known to be dense on many manifolds. The assumptions on the potential fail only in infinite codimension spaces of potentials.The proof is based on geometric considerations of invariant manifolds and their intersections. The main tools include the scattering map of normally hyperbolic invariant manifolds, as well as standard perturbation theories (averaging, KAM and Melnikov techniques).We do not need to assume that the metric is Riemannian and we obtain results for Finsler or Lorentz metrics. Indeed, there is a formulation for Hamiltonian systems satisfying scaling hypotheses. We do not need to make assumptions on the global topology of the manifold nor on its dimension.     

Asymptotic cones of finitely presented groups

Let G be a connected semisimple Lie group with at least one absolutely simple factor S such that and let Γ be a uniform lattice in G.

(a)

If CH holds, then Γ has a unique asymptotic cone up to homeomorphism.

(b)

If CH fails, then Γ has 2^2ω asymptotic cones up to homeomorphism.

     

Topological graph dimension

In the invited chapter Discrete Spatial Models of the book Handbook of Spatial Logics, we have introduced the concept of dimension for graphs, which is inspired by Evako’s idea of dimension of graphs [A.V. Evako, R. Kopperman, Y.V. Mukhin, Dimensional properties of graphs and digital spaces, J. Math. Imaging Vision 6 (1996) 109-119]. Our definition is analogous to that of (small inductive) dimension in topology. Besides the expected properties of isomorphism-invariance and monotonicity with respect to subgraph inclusion, it has the following distinctive features:

•

Local aspect. That is, dimension at a vertex is basic, and the dimension of a graph is obtained as the sup over its vertices.

•

Dimension of a strong product G×H is dim(G)+dim(H) (for non-empty graphs G,H).

In this paper we present a short account of the basic theory, with several new applications and results.     

Products of straight spaces

A metric space X is straight if for each finite cover of X by closed sets, and for each real valued function f on X, if f is uniformly continuous on each set of the cover, then f is uniformly continuous on the whole of X. A locally connected space is straight iff it is uniformly locally connected (ULC). It is easily seen that ULC spaces are stable under finite products. On the other hand the product of two straight spaces is not necessarily straight. We prove that the product X×Y of two metric spaces is straight if and only if both X and Y are straight and one of the following conditions holds:

(a)

both X and Y are precompact;

(b)

both X and Y are locally connected;

(c)

one of the spaces is both precompact and locally connected.

In particular, when X satisfies (c), the product X×Z is straight for every straight space Z.Finally, we characterize when infinite products of metric spaces are ULC and we completely solve the problem of straightness of infinite products of ULC spaces.     

The topology of continua that are approximated by disjoint subcontinua

Suppose that is a collection of disjoint subcontinua of continuum X such that limi→∞dH(Yi,X)=0 where dH is the Hausdorff metric. Then the following are true:

(1)

X is non-Suslinean.

(2)

If each Yi is chainable and X is finitely cyclic, then X is indecomposable or the union of 2 indecomposable subcontinua.

(3)

If X is G-like, then X is indecomposable.

(4)

If all lie in the same ray and X is finitely cyclic, then X is indecomposable.

     

Noncompactness and noncompleteness in isometries of Lipschitz spaces

We solve the following three questions concerning surjective linear isometries between spaces of Lipschitz functions Lip(X,E) and Lip(Y,F), for strictly convex normed spaces E and F and metric spaces X and Y:

(i)

Characterize those base spaces X and Y for which all isometries are weighted composition maps.

(ii)

Give a condition independent of base spaces under which all isometries are weighted composition maps.

(iii)

Provide the general form of an isometry, both when it is a weighted composition map and when it is not.

In particular, we prove that requirements of completeness on X and Y are not necessary when E and F are not complete, which is in sharp contrast with results known in the scalar context.     

Extraordinary dimension of maps

We consider the extraordinary dimension dimL introduced recently by Shchepin [E.V. Shchepin, Arithmetic of dimension theory, Russian Math. Surveys 53 (5) (1998) 975-1069]. If L is a CW-complex and X a metrizable space, then dimLX is the smallest number n such that ΣnL is an absolute extensor for X, where ΣnL is the nth suspension of L. We also write dimLf?n, where is a given map, provided dimLf⁻¹(y)?n for every y∈Y. The following result is established: Supposeis a perfect surjection between metrizable spaces, Y a C-space and L a countable CW-complex. Then conditions (1)-(3) below are equivalent:

(1)

dimLf?n;

(2)

There exists a dense andGδsubsetGofC(X,In)with the source limitation topology such thatdimL(f×g)=0for everyg∈G;

(3)

There exists a mapis such thatdimL(f×g)=0;If, in addition, X is compact, then each of the above three conditions is equivalent to the following one;

(4)

There exists anFσsetA⊂Xsuch thatdimLA?n−1and the restriction mapf|(X?A)is of dimensiondimf|(X?A)?0.

     

CLP-compactness for topological spaces and groups

We study CLP-compact spaces (every cover consisting of clopen sets has a finite subcover) and CLP-compact topological groups. In particular, we extend a theorem on CLP-compactness of products from [J. Steprāns, A. Šostak, Restricted compactness properties and their preservation under products, Topology Appl. 101 (3) (2000) 213-229] and we offer various criteria for CLP-compactness for spaces and topological groups, that work particularly well for precompact groups. This allows us to show that arbitrary products of CLP-compact pseudocompact groups are CLP-compact. For every natural n we construct:

(i)

a totally disconnected, n-dimensional, pseudocompact CLP-compact group; and

(ii)

a hereditarily disconnected, n-dimensional, totally minimal, CLP-compact group that can be chosen to be either separable metrizable or pseudocompact (a Hausdorff group G is totally minimal when all continuous surjective homomorphisms G→H, with a Hausdorff group H, are open).

     

The Fréchet-Urysohn property of Pixley-Roy hyperspaces

Let F[X] be the Pixley-Roy hyperspace of a regular space X. In this paper, we prove the following theorem.

Theorem. For a space X, the following are equivalent:

(1)

F[X]is a k-space;

(2)

F[X]is sequential;

(3)

F[X]is Fréchet-Urysohn;

(4)

Every finite power of X is Fréchet-Urysohn for finite sets;

(5)

Every finite power ofF[X]is Fréchet-Urysohn for finite sets.

As an application, we improve a metrization theorem onF[X].     

Bounds on sets with few distances

We derive a new estimate of the size of finite sets of points in metric spaces with few distances. The following applications are considered:

•

we improve the Ray-Chaudhuri-Wilson bound of the size of uniform intersecting families of subsets;

•

we refine the bound of Delsarte-Goethals-Seidel on the maximum size of spherical sets with few distances;

•

we prove a new bound on codes with few distances in the Hamming space, improving an earlier result of Delsarte.

We also find the size of maximal binary codes and maximal constant-weight codes of small length with 2 and 3 distances.     

Norm continuity of weakly continuous mappings into Banach spaces

Let T be the class of Banach spaces E for which every weakly continuous mapping from an α-favorable space to E is norm continuous at the points of a dense subset. We show that:

•

T contains all weakly Lindelöf Banach spaces;

•

l^∞∉T, which brings clarity to a concern expressed by Haydon ([R. Haydon, Baire trees, bad norms and the Namioka property, Mathematika 42 (1995) 30-42], pp. 30-31) about the need of additional set-theoretical assumptions for this conclusion. Also, (l^∞/c₀)∉T.

•

T is stable under weak homeomorphisms;

•

E∈T iff every quasi-continuous mapping from a complete metric space to (E,weak) is densely norm continuous;

•

E∈T iff every quasi-continuous mapping from a complete metric space to (E,weak) is weakly continuous at some point.

     

Banach spaces with the Daugavet property, and the centralizer

We introduce representable Banach spaces, and prove that the class R of such spaces satisfies the following properties:

(1)

Every member of R has the Daugavet property.

(2)

It Y is a member of R, then, for every Banach space X, both the space L(X,Y) (of all bounded linear operators from X to Y) and the complete injective tensor product lie in R.

(3)

If K is a perfect compact Hausdorff topological space, then, for every Banach space Y, and for most vector space topologies τ on Y, the space C(K,(Y,τ)) (of all Y-valued τ-continuous functions on K) is a member of R.

(4)

If K is a perfect compact Hausdorff topological space, then, for every Banach space Y, most C(K,Y)-superspaces (in the sense of [V. Kadets, N. Kalton, D. Werner, Remarks on rich subspaces of Banach spaces, Studia Math. 159 (2003) 195-206]) are members of R.

(5)

All dual Banach spaces without minimal M-summands are members of R.

     

Bockstein basis and resolution theorems in extension theory

We prove a generalization of the Edwards-Walsh Resolution Theorem:

Theorem. Let G be an abelian group withPG=P, where. Letn∈Nand let K be a connected CW-complex withπn(K)≅G,πk(K)≅0for0?k<n. Then for every compact metrizable space X with XτK (i.e., with K an absolute extensor for X), there exists a compact metrizable space Z and a surjective mapπ:Z→Xsuch that

(a)

π is cell-like,

(b)

dimZ?n, and

(c)

ZτK.

     

Canonical matrices of bilinear and sesquilinear forms

Canonical matrices are given for

(i)

bilinear forms over an algebraically closed or real closed field;

(ii)

sesquilinear forms over an algebraically closed field and over real quaternions with any nonidentity involution; and

(iii)

sesquilinear forms over a field F of characteristic different from 2 with involution (possibly, the identity) up to classification of Hermitian forms over finite extensions of F; the canonical matrices are based on any given set of canonical matrices for similarity over F.

A method for reducing the problem of classifying systems of forms and linear mappings to the problem of classifying systems of linear mappings is used to construct the canonical matrices. This method has its origins in representation theory and was devised in [V.V. Sergeichuk, Classification problems for systems of forms and linear mappings, Math. USSR-Izv. 31 (1988) 481-501].     

Continuity of posets via Scott topology and sobrification

In this paper, posets which may not be dcpos are considered. The concept of embedded bases for posets is introduced. Characterizations of continuity of posets in terms of embedded bases and Scott topology are given. The main results are:

(1)

A poset is continuous iff it is an embedded basis for a dcpo up to an isomorphism;

(2)

A poset is continuous iff its Scott topology is completely distributive;

(3)

A topological T₀ space is a continuous poset equipped with the Scott topology in the specialization order iff its topology is completely distributive and coarser than or equal to the Scott topology;

(4)

A topological T₁ space is a discrete space iff its topology is completely distributive.

These results generalize the relevant results obtained by J.D. Lawson for dcpos.     

Intersection cohomology of the circle actions

A classical result says that a free action of the circle S¹ on a topological space X is geometrically classified by the orbit space B and by a cohomological class e∈H²(B,Z), the Euler class. When the action is not free we have a difficult open question:

(Π)

“Is the space X determined by the orbit space B and the Euler class?”

The main result of this work is a step towards the understanding of the above question in the category of unfolded pseudomanifolds. We prove that the orbit space B and the Euler class determine:

•

the intersection cohomology of X,

•

the real homotopy type of X.

     

On the OBDD size for graphs of bounded tree- and clique-width

We study the size of OBDDs (ordered binary decision diagrams) for representing the adjacency function f_G of a graph G on n vertices. Our results are as follows:

-

for graphs of bounded tree-width there is an OBDD of size O(logn) for f_G that uses encodings of size O(logn) for the vertices;

-

for graphs of bounded clique-width there is an OBDD of size O(n) for f_G that uses encodings of size O(n) for the vertices;

-

for graphs of bounded clique-width such that there is a clique-width expression for G whose associated binary tree is of depth O(logn) there is an OBDD of size O(n) for f_G that uses encodings of size O(logn) for the vertices;

-

for cographs, i.e. graphs of clique-width at most 2, there is an OBDD of size O(n) for f_G that uses encodings of size O(logn) for the vertices. This last result complements a recent result by Nunkesser and Woelfel [R. Nunkesser, P. Woelfel, Representation of graphs by OBDDs, in: X. Deng, D. Du (Eds.), Proceedings of ISAAC 2005, in: Lecture Notes in Computer Science, vol. 3827, Springer, 2005, pp. 1132-1142] as it reduces the size of the OBDD by an O(logn) factor using encodings whose size is increased by an O(1) factor.

     

Inversion arrangements and Bruhat intervals

Let W be a finite Coxeter group. For a given w∈W, the following assertion may or may not be satisfied:

(?)

The principal Bruhat order ideal of w contains as many elements as there are regions in the inversion hyperplane arrangement of w.

We present a type independent combinatorial criterion which characterises the elements w∈W that satisfy (?). A couple of immediate consequences are derived:

(1)

The criterion only involves the order ideal of w as an abstract poset. In this sense, (?) is a poset-theoretic property.

(2)

For W of type A, another characterisation of (?), in terms of pattern avoidance, was previously given in collaboration with Linusson, Shareshian and Sjöstrand. We obtain a short and simple proof of that result.

(3)

If W is a Weyl group and the Schubert variety indexed by w∈W is rationally smooth, then w satisfies (?).