An approximation algorithm for the hamiltonian walk problem on maximal planar graphs

A hamiltonian walk of a graph is a shortest closed walk that passes through every vertex at least once, and the length is the total number of traversed edges. The hamiltonian walk problem in which one would like to find a hamiltonian walk of a given graph is NP-complete. The problem is a generalized hamiltonian cycle problem and is a special case of the traveling salesman problem. Employing the techniques of divide-and-conquer and augmentation, we present an approximation algorithm for the problem on maximal planar graphs. The algorithm finds, in O(p²) time, a closed spanning walk of a given arbitrary maximal planar graph, and the length of the obtained walk is at most $\text{3}\text{2}$(p ? 3) if the graph has p (≥ 9) vertices. Hence the worst-case bound is $\text{3}\text{2}$.     

On Artin's conjecture

Let $\text{F}$ be a family of number fields which are normal and of finite degree over a given number field K. Consider the lattice L(scF) spanned by all the elements of $\text{F}$. The generalized Artin problem is to determine the set of prime ideals of K which do not split completely in any element H of L(scF), H≠K. Assuming the generalized Riemann hypothesis and some mild restrictions on $\text{F}$, we solve this problem by giving an asymptotic formula for the number of such prime ideals below a given norm. The classical Artin conjecture on primitive roots appears as a special case. In another case, if $\text{F}$ is the family of fields obtained by adjoining to $\text{Q}$ the q-division points of an elliptic curve E over $\text{Q}$, the Artin problem determines how often E($\text{F}$_p) is cyclic. If E has complex multiplication, the generalized Riemann hypothesis can be removed by using the analogue of the Bombieri-Vinogradov prime number theorem for number fields.     

Geometric Lipschitz spaces and applications to complex function theory and nilpotent groups

It is known that a function on $\text{R}$ⁿ which can be well approximated by polynomials, in the mean over Euclidean balls, is Lipschitz smooth in the usual sense. In this paper an analogous theorem is proved in which $\text{R}$ⁿ is replaced by a set X, the averages over balls are replaced by a family of sublinear operators satisfying certain axioms, and the polynomials are replaced by a class of functions having certain regularity properties with respect to the averaging operators. Applications are given to function theory on domains in $\text{C}$ⁿ, to nilpotent Lie groups, and to the classical Euclidean case. The first application provides a characterization of the duals of Hardy spaces on the ball in $\text{C}$ⁿ.     

The essential self-adjointness of generalized Schrödinger operators

A necessary and sufficient condition is given for the generalized Schrödinger operator $\text{A = ?(}\text{1}\text{2?}\text{) ∑}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{n}}\text{D}{}_{\mathrm{i}}\text{(?D}{}_{\mathrm{i}}\text{)}$ to be essentially self-adjoint in $\text{L}{}^2\text{(Ω;? dx)}$, under general assumptions on ? and for arbitrary domains Ω in $\text{R}$ⁿ. In particular, if ? is strictly positive and locally Lipschitz continuous on $\text{Ω = R}{}^{\mathrm{n}}$, then A is essentially. self-adjoint. Examples of non-essential self-adjointness and a complete discussion of the one-dimensional case are also given. These results have applications to the problem of the essential self-adjointness of quantum Hamiltonians and to the uniqueness problem of Markov processes.     

Localization in fine potential theory and uniform approximation by subharmonic functions

It is shown how the cone $\text{l}$(U) of superharmonic functions ?0 on an open set U in $\text{R}$ⁿ, n ? 3, can be recovered from the cone $\text{l}$ of superharmonic functions ?0 on the whole of $\text{R}$ⁿ by a process involving the operator of localization associated with U. Actually we treat the more general case where U is open in the Cartan-Brelot fine topology on $\text{R}$ⁿ. As an application we obtain a new proof of a theorem of J. Bliedtner and W. Hansen on uniform approximation by continuous subharmonic functions in open sets containing a given compact set K in $\text{R}$ⁿ.     

Unbounded derivations tangential to compact groups of automorphisms,II

Let G be a compact abelian group, and τ an action of G on a C¹-algebra $\text{U}$, such that $\text{U}$^τ(γ)$\text{U}$^τ(γ)¹ = $\text{U}$^τ(0) $\text{U}$^τ for all $\text{γ ?}\text{G}\text{?}$, where $\text{U}$^τ(γ) is the spectral subspace of $\text{U}$ corresponding to the character γ on G. Derivations δ which are defined on the algebra $\text{U}$_F of G-finite elements are considered. In the special case δ¦_{$\text{U}$^τ} = 0 these derivations are characterized by a cocycle on $\text{G}\text{?}$ with values in the relative commutant of $\text{U}$^τ in the multiplier algebra of $\text{U}$, and these derivations are inner if and only if the cocycles are coboundaries and bounded if and only if the cocycles are bounded. Under various restrictions on G and τ properties of the cocycle are deduced which again give characterizations of δ in terms of decompositions into generators of one-parameter subgroups of τ(G) and approximately inner derivations. Finally, a perturbation technique is devised to reduce the case δ($\text{U}$_F) ? $\text{U}$_F to the case δ($\text{U}$_F) ? $\text{U}$_F and δ¦_{$\text{U}$^τ} = 0. This is used to show that any derivation δ with D(δ) = $\text{U}$_F is wellbehaved and, if furthermore G = T¹ and δ($\text{U}$_F) ? $\text{U}$_F the closure of δ generates a one-parameter group of ¹-automorphisms of $\text{U}$. In the case G = T^d, d = 2, 3,… (finite), and δ($\text{U}$_F) ? $\text{U}$_F it is shown that δ extends to a generator of a group of ¹-automorphisms of the σ-weak closure of $\text{U}$ in any G-covariant representation.     

L2 multipliers with power weights

Necessary and sufficient conditions are found for a multiplier operator to be bounded on L² of the line with weight |x|^2α. This paper is concerned primarily with the case $\text{α>}\text{1}\text{2}$. Multiplier operators are defined on these spaces by using the usual definition on a subspace that is shown to be dense in the space. The case $\text{α < ?}\text{1}\text{2}$ is treated by duality; $\text{|α| <}\text{1}\text{2}$ is briefly treated using a recent result on fractional integrals. The periodic case is also sketched.     

Null Lagrangians,weak continuity,and variational problems of arbitrary order

We consider the problem of minimizing integral functionals of the form $\text{I(u) = ∝}{}_{\mathrm{\Omega }}\text{F(x, ▽}{}^{\mathrm{[k]}}\text{u(x)) dx}$, where Ω ?$\text{R}$^p, u:ω →$\text{R}$ and ▽^[k]u denotes the set of all partial derivatives of u with orders ?k. The method is based on a characterization of null Lagrangians L(▽^ku) depending only on derivatives of order k. Applications to elasticity and other theories of mechanics are given.     

Factorial representations of path groups

The reduction of the energy representation of the group of mappings from I = [0, 1], S¹1, $\text{R}$₊ or $\text{R}$ into a compact semisimple Lie group G is given. For G = SU(2), the factoriality of the representation, which is of type III in the case I=$\text{R}$, is proved.     

Symmetric hyperbolic difference schemes and matrix problems

Sufficient conditions for the stability of multidimensional finite difference schemes are difficult to obtain. It is shown that for special families of amplification matrices G (A, B) a sufficient condition for power boundedness can be obtained by replacing the matrices by appropriate scalars, and so the problem is reduced to a scalar one. As one application it is shown that the Lax-Wendroff scheme in two dimensions is stable if |Au|^{$\text{2}\text{3}$} + |Bu|^{$\text{2}\text{3}$} ? 1 for all real unit vectors u. The Lax- Wendroff scheme with stabilizer does not always permit such large time steps. It is conjectured that the analysis for all symmetric hyperbolic schemes can be reduced to the scalar case.     

Some properties of Q-matrices

This paper deals with the class of Q-matrices, that is, the real n × n matrices M such that for every q ∈ $\text{R}$^n×1, the linear complementarity problem

$\text{Iw ? Mz = q}$

,

$\text{w ? 0, z ? 0, and w}{}^{\mathrm{T}}\text{z = 0}$

, has a solution. In general, the results are of two types. First, sufficient conditions are given on a matrix M so that M ∈ Q. Second, conditions are given so that M ? Q.     

Formulation of pseudoparabolic boundary control problems

Boundary control of a pseudoparabolic problem is studied. The trace of a solution y(T; ?) corresponding to a control ? is shown to belong to $\text{L}{}^2\text{(Ω)}$ and continuity properties are established. Two concrete examples are considered and regularity properties of the optimal control are determined in each case.     

Semi-crossed products of C1-algebras

Given a C¹-algebra $\text{U}$ and endomorphim α, there is an associated nonselfadjoint operator algebra $\text{Z}$⁺ X_α$\text{U}$, called the semi-crossed product of $\text{U}$ with α. If α is an automorphim, $\text{Z}$⁺ X_α$\text{U}$ can be identified with a subalgebra of the C¹-crossed product $\text{Z}$⁺ X_α$\text{U}$. If $\text{U}$ is commutative and α is an automorphim satisfying certain conditions, $\text{Z}$⁺ X_α$\text{U}$ is an operator algebra of the type studied by Arveson and Josephson. Suppose S is a locally compact Hausdorff space, φ: S → S is a continuous and proper map, and α is the endomorphim of U=C₀(S) given by α(?) = ? ō φ. Necessary and sufficient conditions on the map φ are given to insure that the semi-crossed product Z⁺X_αC₀(S) is (i) semiprime; (ii) semisimple; (ii) strongly semisimple.     

Localizability of the embedding problem with symplectic kernel

In this paper we consider the question of how much information is supplied by local solutions to a global embedding problem for the special case in which the normal subgroup belonging to the given group extension is the projective symplectic group PSp(2m, q). It is proved that for suitable Galois extensions K of a given number field k (which constitute part of the data of the embedding problem), the local solutions in a sense determine whether or not an extension K ? K, Galois over k, with $\text{G(}\text{L}\text{K}\text{) ≈ PSp(2m, q)}$, represents a global solution to the embedding problem.     

Operator-selfdecomposable distributions as limit distributions of processes of Ornstein-Uhlenbeck type

Processes of Ornstein-Uhlenbeck type on $\text{R}$^d are analogues of the Ornstein-Uhlenbeck process on $\text{R}$^d with the Brownian motion part replaced by general processes with homogeneous independent increments. The class of operator-selfdecomposable distributions of Urbanik is characterized as the class of limit distributions of such processes. Continuity of the correspondence is proved. Integro-differential equations for operator-selfdecomposable distributions are established. Examples are given for null recurrence and transience of processes of Ornstein-Uhlenbeck type on $\text{R}$¹.     

Sur la structure galoisienne du groupe des unités d'un corps abélien réel de type (p, p)

Let p be a rational prime. We classify those $\text{Z}$[($\text{Z}$/p$\text{Z}$)²]-modules arising as submodules of the units (mod. torsion) of a real abelian field K with Galois group ($\text{Z}$/p$\text{Z}$)², up to isomorphism and up to genus. Explicit results are given when p is 2 or 3. We apply our classification to discuss the existence of a Minkowski unit in K for arbitrary p.     

On the spectral synthesis problem for hypersurfaces of RN

Let F¹(Rⁿ) denote the Fourier algebra on $\text{R}$ⁿ, and $\text{D}$($\text{R}$ⁿ) the space of test functions on $\text{R}$ⁿ. A closed subset E of $\text{R}$ⁿ is said to be of spectral synthesis if the only closed ideal J in F¹(Rⁿ) which has E as its hull

$\text{h(J)={x ? R}{}^{\mathrm{n}}\text{:f(x)=0}\text{for all}\text{f ? J}}$

is the ideal

$\text{k(E)={f?F}{}^1\text{(R}{}^{\mathrm{n}}\text{):f(E)=0}}$

. We consider sufficiently regular compact subsets of smooth submanifolds of $\text{R}$ⁿ with constant relative nullity. For such sets E we give an estimate of the degree of nilpotency of the algebra $\text{(k(E)∩D(R}{}^{\mathrm{n}}\text{))}{}^{\mathrm{?}}\text{j(E)}$, where j(E) denotes the smallest closed ideal in F¹(Rⁿ) with hull E. Especially in the case of hypersurfaces this estimate turns out to be exact. Moreover for this case we prove that k(E)∩D(Rⁿ) is dense in k(E). Together this solves the synthesis problem for such sets.     

Limit behavior of solutions of singular difference equations

Necessary and sufficient conditions for a solution {z_k} of the difference equation $\text{A}\text{z}{}_{\mathrm{k+1}}\text{+}\text{B}\text{z}{}_{\mathrm{k}}\text{= b, k ?0}$, with $\text{A}$ singular, to be a convergent sequence of vectors are given under a variety of assumptions. Theoretical results on iterative schemes for solving Ax = b by singular splittings, $\text{A =}\text{A}\text{+}\text{B}$, are given first. In particular, the case when $\text{A = A}{}^1$ and $\text{A}$ is positive semi-definite is considered. Then applications to discrete control problems and backwards population projection are discussed.