Solutions of the matrix equation (1):X m+A 1Xm−1+…+A m=0

SupposeX and the coefficientsA ₁, …,A _m aren×n matrices. LetB be anmn×mn matrix as in (7). LetJ be the Jordan canonical matrix ofB andB=PJP ⁻. LetE _i denote thei×i unit matrix.V is defined bydV/dt=JV andV(t=0)=E _mn. ThenZ=PV satisfiesdZ/dt=BZ.P ^* is a matrix which consists of the firstn rows ofP. The author proves: There is a solution of (1) ↔ there are anmn×n matrixC, ann×n matrixQ and ann×n function matrixN such thatP ^*VC=QN, where detQ≠0 andN is defined byN(t=0)=E _n anddN/dt=RN, in whichR is ann×n Jordan canonical matrix. There are three cases regarding the solutions of (1): No solution, finitek solutions, 1<k<C _n ^m , and infinite solutions which containj parameters, 1<-j<-mn ².     

The braid group B4 is linear

We study a linear representation ρ:B _n ? GL _m (Z[q ^±1,t ^±1]) with m=n(n-1)/2. We will show that for n=4, this representation is faithful. We prove a relation with the new Charney length function. We formulate a conjecture implying that ρ is faithful for all n. Oblatum 15-VI-1999 & 24-II-2000?Published online: 18 September 2000     

Random matrix products and applications to cellular automata

Let λ be the upper Lyapunov exponent corresponding to a product of i.i.d. randomm×m matrices (X _i) _i ^0/∞ over ℂ. Assume that theX _i's are chosen from a finite set {D ₀,D ₁...,D _t-1(ℂ), withP(X _i=D_j)>0, and that the monoid generated byD ₀, D₁,…, D_q−1 contains a matrix of rank 1. We obtain an explicit formula for λ as a sum of a convergent series. We also consider the case where theX _i's are chosen according to a Markov process and thus generalize a result of Lima and Rahibe [22]. Our results on λ enable us to provide an approximation for the numberN _≠0(F(x)ⁿ,r) of nonzero coefficients inF(x) ⁿ.(modr), whereF(x) ∈ ℤ[x] andr≥2. We prove the existence of and supply a formula for a constant α (<1) such thatN _≠0(F(x)ⁿ,r) ≈n ^α for “almost” everyn. Supported in part by FWF Project P16004-N05     

Test elements for endomorphisms of free groups and algebras

LetE be a bounded Borel subset of ℝⁿ,n≥2, of positive Lebesgue measure andP _E the corresponding ‘Pompeiu transform”. We prove thatP _E is injective onL ^p(ℝⁿ) if 1≤p≤2n/(n-1). We explore the connection between this problem and a Wiener-Tauberian type theorem for theM(n) action onL ^q(ℝⁿ) for various values ofq. We also take up the question of whenP _E is injective in caseE is of finite, positive measure, but is not necessarily a bounded set. Finally, we briefly look at these questions in the contexts of symmetric spaces of compact and non-compact type.     

A small embedding for partial even-cycle systems

Let m = 2k. We show that for some 0 ≤ ξ <1, a partial directed m-cycle system of order n can be embedded in a directed m-cycle system of order (mn)/2 + (2m² 1) √(8n + 1)/4 + 4m^{3 2} + 4 + 1/2. For fixed m, this is asymptotic in n to (mn)/2 and so for large n is roughly one-fourth the best known bound of 2mn + 1. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 205–215, 1999     

The intersection problem for m-cycle systems

Let I_m(v) denote the set of integers k for which a pair of m-cycle systems of K_v, exist, on the same vertex set, having k common cycles. Let J_m(v) = {0, 1, 2,…, t_v ?2, t_v} where t_v = v(v ? 1)/2m. In this article, if 2mn + x is an admissible order of an m-cycle system, we investigate when I_m(2mn + x) = J_m(2mn + x), for both m even and m odd. Results include J^m(2mn + 1) = I^m(2mn + 1) for all n > 1 if m is even, and for all n > 2 if n is odd. Moreover, the intersection problem for even cycle systems is completely solved for an equivalence class x (mod 2m) once it is solved for the smallest in that equivalence class and for K_2m+1. For odd cycle systems, results are similar, although generally the two smallest values in each equivalence class need to be solved. We also completely solve the intersection problem for m = 4, 6, 7, 8, and 9. (The cased m = 5 was done by C-M. K. Fu in 1987.) © 1993 John Wiley & Sons, Inc.     

Asymptotic behavior of the critical probability for ρ-percolation in high dimensions

We consider oriented bond or site percolation on ℤ ^d ₊. In the case of bond percolation we denote by P _p the probability measure on configurations of open and closed bonds which makes all bonds of ℤ ^d ₊ independent, and for which P _p {e is open} = 1 −P _p e {is closed} = p for each fixed edge e of ℤ ^d ₊. We take X(e) = 1 (0) if e is open (respectively, closed). We say that ρ-percolation occurs for some given 0 < ρ≤ 1, if there exists an oriented infinite path v ₀ = 0, v ₁, v ₂, …, starting at the origin, such that lim inf _{n →∞} (1/n) ∑ _i=1 ⁿ X(e _i ) ≥ρ, where e _i is the edge {v _i−1 , v _i }. [MZ92] showed that there exists a critical probability p _c = p _c (ρ, d) = p _c (ρ, d, bond) such that there is a.s. no ρ-percolation for p < p _c and that P _p {ρ-percolation occurs} > 0 for p > p _c . Here we find lim _{d →∞} d ^1/ρ p _c (ρd, bond) = D ₁ , say. We also find the limit for the analogous quantity for site percolation, that is D ₂ = lim _{d →∞} d ^1/ρ p _c (ρ, d, site). It turns out that for ρ < 1, D ₁ < D ₂ , and neither of these limits equals the analogous limit for the regular d-ary trees. Received: 7 January 1999 / Published online: 14 June 2000     

On samples of independent random vectors in spaces of infinitely increasing dimension

We study the asymptotic behavior of a set of random vectors ξ_i, i = 1,..., m, whose coordinates are independent and identically distributed in a space of infinitely increasing dimension. We investigate the asymptotics of the distribution of the random vectors, the consistency of the sets M _m⁽ⁿ⁾ = ξ₁,..., ξ_m and X _n^λ = x ∈ X _n: ρ(x) ≤ λn, and the mutual location of pairs of vectors. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 12, pp. 1706–1711, December, 1998.     

Multidimensional version of M. A. Krasnoseľskii’s generalized contraction principle

Let M be a complete K-metric space with n-dimensional metric ρ(x, y): M × M → R ⁿ , where K is the cone of nonnegative vectors in R ⁿ . A mapping F: M → M is called a Q-contraction if ρ (Fx,Fy) ⩽ Qρ (x,y), where Q: K → K is a semi-additive absolutely stable mapping. A Q-contraction always has a unique fixed point x* in M, and ρ(x*,a) ⩽ (I - Q)^-1 ρ(Fa, a) for every point a in M. The point x* can be obtained by the successive approximation method x _k = Fx _k-1, k = 1, 2,..., starting from an arbitrary point x ₀ in M, and the following error estimates hold: ρ (x*, x _k ) ⩽ Q ^k (I - Q)^-1ρ(x ₁, _x ⁰) ⩽ (I - Q)^-1 Q ^k ρ(x ₁, x ₀), k = 1, 2,.... Generally the mappings (I - Q)^-1 and Q ^k do not commute. For n = 1, the result is close to M. A. Krasnosel’skii’s generalized contraction principle.     

Instances of the Conjecture of Chang

We consider various forms of the Conjecture of Chang. Part A constitutes an introduction. Donder and Koepke have shown that if ρ is a cardinal such that ρ ≧ ω₁, and (ρ⁺⁺,ρ⁺↠(ρ⁺, ρ), then 0⁺ exists. We obtain the same conclusion in Part B starting from some other forms of the transfer hypothesis. As typical corollaries, we get: Theorem A.Assume that there exists cardinals λ, κ, such that λ ≧ K ⁺ ≧ω₂ and (λ⁺, λ)↠(K ⁺,K. Then 0⁺ exists. Theorem B.Assume that there exists a singularcardinal κ such that(K ⁺,K↠(ω₁, ω₀. Then 0⁺ exists. Theorem C.Assume that (λ ⁺⁺, λ). Then 0⁺ exists (also ifK=ω ₀. Remark. Here, as in the paper of Donder and Koepke, “O⁺ exists” is a matter of saying that the hypothesis is strictly stronger than “L(μ) exists”. Of course, the same proof could give a few more sharps overL(μ), but the interest is in expecting more cardinals, coming from a larger core model. Theorem D.Assume that (λ ⁺⁺, λ)↠(K ⁺, K) and thatK≧ω ₁. Then 0⁺ exists. Remark 2. Theorem B is, as is well-known, false if the hypothesis “κ is singular” is removed, even if we assume thatK≧ω ₂, or that κ is inaccessible. We shall recall this in due place. Comments. Theorem B and Remark 2 suggest we seek the consistency of the hypothesis of the form:K ⁺, K↠(ω_n +1, ω_n), for κ singular andn≧0. 0266 0152 V 3 The consistency of several statements of this sort—a prototype of which is (N _ω+1,N _ω)↠(ω₁, ω₀) —have been established, starting with an hypothesis slightly stronger than: “there exists a huge cardinal”, but much weaker than: “there exists a 2-huge cardinal”. These results will be published in a joint paper by M. Magidor, S. Shelah, and the author of the present paper.     

Rates of Best Uniform Rational Approximation of Analytic Functions by Ray Sequences of Rational Functions

In this paper, problems related to the approximation of a holomorphic function f on a compact subset E of the complex plane C by rational functions from the class of all rational functions of order (n,m) are considered. Let ρ _n,m = ρ _n,m (f;E) be the distance of f in the uniform metric on E from the class . We obtain results characterizing the rate of convergence to zero of the sequence of the best rational approximation { ρ _n,m(n) } _n=0 ^∞ , m(n)/n → θ ∈ (0,1] as n → ∞ . In particular, we give an upper estimate for the liminf _{n →∞} ρ _n,m(n) ^1/(n+m(n)) in terms of the solution to a certain minimum energy problem with respect to the logarithmic potential. The proofs of the results obtained are based on the methods of the theory of Hankel operators. June 16, 1997. Date revised: December 1, 1997. Date accepted: December 1, 1997. Communicated by Ronald A. DeVore.     

Approximation in Learning Theory

This paper addresses some problems of supervised learning in the setting formulated by Cucker and Smale. Supervised learning, or learning-from-examples, refers to a process that builds on the base of available data of inputs x_i and outputs y_i, i = 1,...,m, a function that best represents the relation between the inputs x ∈ X and the corresponding outputs y ∈ Y. The goal is to find an estimator f_z on the base of given data z := ((x₁,y₁),...,(x_m,y_m)) that approximates well the regression function f_ρ (or its projection) of an unknown Borel probability measure ρ defined on Z = X × Y. We assume that (x_i,y_i), i = 1,...,m, are independent and distributed according to ρ. We discuss the following two problems: I. the projection learning problem (improper function learning problem); II. universal (adaptive) estimators in the proper function learning problem. In the first problem we do not impose any restrictions on a Borel measure ρ except our standard assumption that |y|≤ M a.e. with respect to ρ. In this case we use the data z to estimate (approximate) the L₂(ρ_X) projection (f_ρ)_W of f_ρ onto a function class W of our choice. Here, ρ_X is the marginal probability measure. In [KT1,2] this problem has been studied for W satisfying the decay condition ε_n(W,B) ≤ Dn^-r of the entropy numbers ε_n(W,B) of W in a Banach space B in the case B = C(X) or B = L₂(\rho_X). In this paper we obtain the upper estimates in the case ε_n(W,L₁(ρ_X)) ≤ Dn^-r with an extra assumption that W is convex. In the second problem we assume that an unknown measure ρ satisfies some conditions. Following the standard way from nonparametric statistics we formulate these conditions of the form f_ρ ∈ Θ. Next, we assume that the only a priori information available is that f_ρ belongs to a class Θ (unknown) from a known collection {Θ} of classes. We want to build an estimator that provides approximation of f_ρ close to the optimal for the class Θ. Along with standard penalized least squares estimators we consider a new method of construction of universal estimators. This method is based on a combination of two powerful ideas in building universal estimators. The first one is the use of penalized least squares estimators. This idea works well in the case of general setting with rather abstract methods of approximation. The second one is the idea of thresholding that works very well when we use wavelets expansions as an approximation tool. A new estimator that we call the big jump estimator uses the least squares estimators and chooses a right model by a thresholding criteria instead of the penalization. In this paper we illustrate how ideas and methods of approximation theory can be used in learning theory both in formulating a problem and in solving it.     

On the Riesz means of coefficients of <Emphasis Type="Italic">m</Emphasis>th symmetric power <Emphasis Type="Italic">L</Emphasis>-functions

Let c _n be the Fourier coefficients of L(sym ^m   f, s), and Δρ(x; sym ^m   f) be the error term in the asymptotic formula for ∑ _n≪x c _n . In this paper, we study the Riesz means of Δρ(x; sym ^m   f) and obtain a truncated Voronoi-type formula under the hypothesis Nice(m, f).     

Half-factorial-domains

LetR be a commutative domain with 1. We termR an HFD (Half-Factorial-Domain) provided the equality Π _i=1 ⁿ χ_i=Π{_f=1/^m}y _f impliesm=n, whenever thex’s and they’s are non-zero, non-unit and irreducible elements ofR. The purpose of this note is to study HFD’s, in particular, Krull domains that are HFD’s, and to provide examples of HFD’s, that contradict a conjecture of Narkiewicz.     

On the description of overgroups of E(m,R)?E(n,R)

The subgroups E(m,R) ⊗ E(n,R) ≤ H ≤ G = GL(mn,R) are studied under the assumption that the ring R is commutative and m, n ≥ 3. The group GL _m ⊗GL _n is defined by equations, the normalizer of the group E(m,R) ⊗ E(n,R) is calculated, and with each intermediate subgroup H it is associated a uniquely determined lower level (A,B,C), where A,B,C are ideals in R such that mA,A ² ≤ B ≤ A and nA,A ² ≤ C ≤ A. The lower level specifies the largest elementary subgroup satisfying the condition E(m, n,R, A,B,C) ≤ H. The standard answer to this problem asserts that H is contained in the normalizer N _G (E(m,n,R, A,B,C)). Bibliography: 46 titles.     

Transformations with highly nonhomogeneous spectrum of finite multiplicity

This paper studies a spectral invariant ℳ _T for ergodic measure preserving transformationsT called theessential spectral multiplicities. It is defined as the essential range of the multiplicity function for the induced unitary operatorU _T. Examples are constructed where ℳ _T is subject only to the following conditions: (i) 1∈ℳ _T , (ii) lcm(n, m)∈ℳ _T wherevern, m ∈ ℳ _T , and (iii) sup ℳ _T <+∞. This shows thatD _T, definedD _T=card ℳ _T , may be an arbitrary positive integer. The results are obtained by an algebraic construction together with approximation arguments. This research was partially supported by NSF grant MCS 8102790.     

On embedding trees into uniformly convex Banach spaces

We investigate the minimum value ofD =D(n) such that anyn-point tree metric space (T, ρ) can beD-embedded into a given Banach space (X, ∥·∥); that is, there exists a mappingf :T →X with 1/D ρ(x,y) ≤ ∥f(x) −f(y)∥ ≤ρ(x,y) for anyx,y εT. Bourgain showed thatD(n) grows to infinity for any superreflexiveX (and this characterized super-reflexivity), and forX =ℓ _p, 1 <p < ∞, he proved a quantitative lower bound of const·(log logn)^min(1/2,1/p). We give another, completely elementary proof of this lower bound, and we prove that it is tight (up to the value of the constant). In particular, we show that anyn-point tree metric space can beD-embedded into a Euclidean space, with no restriction on the dimension, withD =O(√log logn). This paper contains results from my thesis [Mat89] from 1989. Since the subject of bi-Lipschitz embeddings is becoming increasingly popular, in 1997 I finally decided to publish this English version. Supported by Czech Republic Grant GAČR 0194 and by Charles University grants No. 193, 194.     

Comparison of germ expansion¶on inner forms of GL(n)

We prove that the germ expansion of a discrete series representation π^′ on GL _n (D) where D is a division algebra over k of index m and the germ expansion of the representation π of GL _mn (k) associated to π^′ by the Deligne–Kazhdan–Vigneras correspondence are closely related, and therefore certain coefficients in the germ expansion of a discrete series representation of GL _mn (k) can be interpreted (and therefore sometimes calculated) in terms of the dimension of a certain space of (degenerate) Whittaker models on GL _n (D). Received: 30 September 1999 / Revised version: 11 February 2000     

On classification of immersions ofn-manifolds in (2n−1)-manifolds

Under the assumption of (f, M ⁿ ,N ²ⁿ⁻¹) being trivial, the classification of immersions homotopic tof: M ⁿ →N ²ⁿ⁻¹ is obtained in many cases. The triviality of (f, M ⁿ ,P ²ⁿ⁻¹) is proved for anyM ⁿ andf. LetM, N be differentiable manifolds of dimensionn and2n−1 respectively. For a mapf: M → N, denote byI[M, N] _f the set of regular homotopy classes of immersions homotopic tof. It has been proved in [1] that, whenn>1,I[M, N] _f is nonempty for anyf. In this paper we will determine the setI[M, N] _f in some cases. For example, ifN=P ²ⁿ⁻¹ or more generally, the lens spacesS _m ²ⁿ⁻¹ =Z _m /S ²ⁿ⁻¹,M is any orientablen-manifold or nonorientable butn≡0, 1, 3 mod 4, then, for anyf, theI[M, N] _f is determined completely. WhenN=R ²ⁿ⁻¹, the setI[M, N] of regular homotopy classes of all immersions has been enumerated by James and Thomas in [2] and McClendon in [3] forn>3. Applying our results toN=R ²ⁿ⁻¹ we obtain their results again, except for the casen≡2 mod 4 andM nonorientable. Whenn=3, McClendon's results cannot be used. Our results include the casesn=3,M orientable or not (for orientableM, I[M, R⁵] is known by Wu [4]).     

Fibonacci and Lucas congruences and their applications

In this paper we obtain some new identities containing Fibonacci and Lucas numbers. These identities allow us to give some congruences concerning Fibonacci and Lucas numbers such as L _2mn+k ≡ (−1)^(m+1)n L _k (mod L _m ), F _2mn+k ≡ (−1)^(m+1)n F _k (mod L _m ), L _2mn+k ≡ (−1) ^mn L _k (mod F _m ) and F _2mn+k ≡ (−1) ^mn F _k (mod F _m ). By the achieved identities, divisibility properties of Fibonacci and Lucas numbers are given. Then it is proved that there is no Lucas number L _n such that L _n = L ₂ ^k t L _m x ² for m > 1 and k ≥ 1. Moreover it is proved that L _n = L _m L _r is impossible if m and r are positive integers greater than 1. Also, a conjecture concerning with the subject is given.