Sometimes slow growing is fast growing

The slow growing hierarchy is commonly defined as follows: G₀(x) = 0, G_x−1(x) := G_x(x) + 1 and G_λ(x) := G_λ[x](x) where λ<₀ is a limit and ·[·]:₀∩ Lim × ω → ₀ is a given assignment of fundamental sequences for the limits below ₀. The first obvious question which is encountered when one looks at this definition is: How does this hierarchy depend on the choice of the underlying system of fundamental sequences? Of course, it is well known and easy to prove that for the standard assignment of fundamental sequence the hierarchy (G_x)_x<0 is slow growing, i.e. each G_x is majorized by a Kalmar elementary recursive function.

It is shown in this paper that the slow growing hierarchy (G_x)_x<0 — when it is defined with respect to the norm-based assignment of fundamental sequences which is defined in the article by Cichon (1992, pp. 173–193) — is actually fast growing, i.e. each PA-provably recursive function is eventually dominated by G_x for some <₀. The exact classification of this hierarchy, i.e. the problem whether it is slow or fast growing, has been unsolved since 1992. The somewhat unexpected result of this paper shows that the slow growing hierarchy is extremely sensitive with respect to the choice of the underlying system of fundamental sequences.

The paper is essentially self-contained. Only little knowledge about ordinals less than ₀ — like the existence of Cantor normal forms, etc. and the beginnings of subrecursive hierarchy theory as presented, for example, in the 1984 textbook of Rose — is assumed.     

On the weak Freese-Nation property of complete Boolean algebras

The following results are proved:

(a) In a model obtained by adding ₂ Cohen reals, there is always a c.c.c. complete Boolean algebra without the weak Freese-Nation property. (b) Modulo the consistency strength of a supercompact cardinal, the existence of a c.c.c. complete Boolean algebra without the weak Freese-Nation property is consistent with GCH. (c) If a weak form of □_μ and cof([μ]^₀,)=μ⁺ hold for each μ>cf(μ)=ω, then the weak Freese-Nation property of is equivalent to the weak Freese-Nation property of any of or for uncountable κ. (d) Modulo the consistency of (_ω+1,_ω)(₁,₀), it is consistent with GCH that does not have the weak Freese-Nation property and hence the assertion in (c) does not hold, and also that adding _ω Cohen reals destroys the weak Freese-Nation property of .

These results solve all of the problems except Problem 1 in S. Fuchino, L. Soukup, Fundament. Math. 154 (1997) 159–176, and some other problems posed by Geschke.     

Intermediate error estimates

Let R[f] be the remainder of some approximation method, having estimates of the form f;R[f]f; ρ_i ; f⁽ⁱ⁾ for i = 0,…, r. In many cases, ρ₀ and ρ_r are known, but not the intermediate error constants ρ₁,…,ρ_r−1. For periodic functions, Ligun (1973) has obtained an estimate for these intermediate error constants by ρ₀ and ρ_r. In this paper, we show that this holds in the nonperiodic case, too. For instance, the estimates obtained can be applied to the error of polynomial or spline approximation and interpolation, or to numerical integration and differentiation.     

On the efficiency of a testimator for the mean of an inverse Gaussian distribution

Though the sample mean is a natural estimator for the mean μ of an Inverse Gaussian (IG) distribution having another parameter λ, when a guess μ₀ for μ seems plausible, an alternative adaptive estimator which shrinks towards μ₀ when a preliminary test for H₀:μ = μ₀ is tenable or else towards , is considered a suitable competitor. Certain numerical illustrations are presented showing higher efficiency of such a testimator over in several situations when the sample size is small and λ is either known or unknown.     

On index of total boundedness of (strictly) o-bounded groups

Let G be a metrizable topological group. Denote by itb(G) the smallest cardinality of a cover of G by totally bounded subsets of G. A group G is defined to be σ-bounded if itb(G)₀. The group G is called o-bounded if for every sequence (U_n)_nω of neighborhoods of the identity in G there exists a sequence (F_n)_nω of finite subsets in G such that G=_nωF_n·U_n; G is called strictly o-bounded (respectively OF-determined) if the second player (respectively one of the players) has a winning strategy in the following game OF: two players, I and II, choose at every step n an open neighborhood U_n of the identity in G and a finite subset F_n of G, respectively. The player II wins if G=_nωF_n·U_n.

For a second countable group G the following results are proven. . If G is strictly o-bounded, then itb(G)₁ and G is σ-bounded or meager. If the space G is analytic, then the group is OF-determined and satisfies . G is σ-bounded if it is strictly o-bounded and one of the following conditions holds: (i) G is analytic; (ii) ; (iii) (MA+¬CH) holds; (iv) analytic games are determined; (v) there exists a measurable cardinal. Also we show that under (MA) every non-locally compact Polish Abelian divisible group contains a Baire o-bounded OF-undetermined subgroup.     

On cardinal sequences of scattered spaces

It was proved by Dow and Simon that there are 2^ω₁ (as many as possible) pairwise nonhomeomorphic compact, T₂, scattered spaces of height ω₁ and width ω. In this paper, we prove that if is an ordinal withω₁ < ω₂ and θ = κ_ξ: ξ < is a sequence of cardinals such that either κ_ξ = ω or κ_ξ = ω₁ for every ξ < , then there are 2^ω₁ pairwise nonhomeomorphic compact, T₂, scattered spaces whose cardinal sequence is θ.     

Embeddings of the base and bundle isomorphisms

Let π_i :E_i→M, i=1,2, be oriented, smooth vector bundles of rank k over a closed, oriented n-manifold with zero sections s_i :M→E_i. Suppose that U is an open neighborhood of s₁(M) in E₁ and F :U→E₂ a smooth embedding so that π₂Fs₁ :M→M is homotopic to a diffeomorphism f. We show that if k>[(n+1)/2]+1 then E₁ and the induced bundle f^*E₂ are isomorphic as oriented bundles provided that f have degree +1; the same conclusion holds if f has degree −1 except in the case where k is even and one of the bundles does not have a nowhere-zero cross-section. For n≡0(4) and [(n+1)/2]+1<kn we give examples of nonisomorphic oriented bundles E₁ and E₂ of rank k over a homotopy n-sphere with total spaces diffeomorphic with orientation preserved, but such that E₁ and f^*E₂ are not isomorphic oriented bundles. We obtain similar results and counterexamples in the more difficult limiting case where k=[(n+1)/2]+1 and M is a homotopy n-sphere.     

New constructions of divisible designs

A construction is given for a (p^2a(p+1),p²,p^2a+1(p+1),p^2a+1,p^2a(p+1)) (p a prime) divisible difference set in the group H×Z²_pa+1 where H is any abelian group of order p+1. This can be used to generate a symmetric semi-regular divisible design; this is a new set of parameters for λ₁≠0, and those are fairly rare. We also give a construction for a (p^a−1+p^a−2+…+p+2,p^a+2, p^a(p^a+p^a−1+…+p+1), p^a(p^a−1+…+p+1), p^a−1(p^a+…+p²+2)) divisible difference set in the group H×Z_p2×Z^a_p. This is another new set of parameters, and it corresponds to a symmetric regular divisible design. For p=2, these parameters have λ₁=λ₂, and this corresponds to the parameters for the ordinary Menon difference sets.     

Extremal properties of strong quadrature weights and maximal mass results for truncated strong moment problems

A bisequence of complex numbers {μ_n}_−∞^∞ determines a strong moment functional satisfying L[xⁿ] = μ_n. If is positive-definite on a bounded interval (a,b) R{0}, then has an integral representation , n=0, ±1, ±2,…, and quadrature rules {w_ni,x_ni} exist such that μ_k = ∑_i=i^n_ns_ni^kw_ni. This paper is concerned with establishing certain extremal properties of the weights w_ni and using these properties to obtain maximal mass results satisfied by distributions ψ(x) representing when only a finite bisequence of moments {μ_k}_k=−nⁿ⁻¹ is given.     

The reflection length of a transformation in the unitary group over a finite field

Let U be the unitary group over a finite field K where [K]≠3 and char K≠2. Every transformation π in U with detπ = ±1 is a product of reflections. We determine the length t of every such transformation π i.e. for each π we find reflections σ_i in U such that π=σ₁ σ_t and so that no factorization of π into fewer than t reflections exists.     

First passage time for some stationary processes

For a 1-dependent stationary sequence {X_n} we first show that if u satisfies p₁=p₁(u)=P(X₁>u)0.025 and n>3 is such that 88np₁³1, then

P{max(X₁,…,X_n)u}=ν·μⁿ+O{p₁³(88n(1+124np₁³)+561)}, n>3,

where

ν=1−p₂+2p₃−3p₄+p₁²+6p₂²−6p₁p₂,μ=(1+p₁−p₂+p₃−p₄+2p₁²+3p₂²−5p₁p₂)⁻¹

with

p_k=p_k(u)=P{min(X₁,…,X_k)>u}, k1

and

|O(x)||x|.

From this result we deduce, for a stationary T-dependent process with a.s. continuous path {Y_s}, a similar, in terms of P{max_0skTY_s<u}, k=1,2 formula for P{max_0stY_su}, t>3T and apply this formula to the process Y_s=W(s+1)−W(s), s0, where {W(s)} is the Wiener process. We then obtain numerical estimations of the above probabilities.     

Forcing closed unbounded subsets of ω2

It is shown that there is no satisfactory first-order characterization of those subsets of ω₂ that have closed unbounded subsets in ω₁,ω₂ and GCH preserving outer models. These “anticharacterization” results generalize to subsets of successors of uncountable regular cardinals. Similar results are proved for trees of height and cardinality κ⁺ and for partitions of [κ⁺]², when κ is an infinite cardinal.     

Error bounds on the power method for determining the largest eigenvalue of a symmetric, positive definite matrix

Let A be a positive definite, symmetric matrix. We wish to determine the largest eigenvalue, λ₁. We consider the power method, i.e. that of choosing a vector v₀ and setting v_k = A^kv₀; then the Rayleigh quotients R_k = (Av_k, v_k)/(v_k, v_k) usually converge to λ₁ as k → ∞ (here (u, v) denotes their inner product). In this paper we give two methods for determining how close R_k is to λ₁. They are both based on a bound on λ₁ − R_k involving the difference of two consecutive Rayleigh quotients and a quantity ω_k. While we do not know how to directly calculate ω_k, we can given an algorithm for giving a good upper bound on it, at least with high probability. This leads to an upper bound for λ₁ − R_k which is proportional to (λ₂/λ₁)^2k, which holds with a prescribed probability (the prescribed probability being an arbitrary δ > 0, with the upper bound depending on δ).     

Asymptotic behavior of a nonlinear delay difference equation

This paper considers a class of nonlinear difference equations

Δ₃y_n + ƒ(n, y_n, y_n−r) = 0, n N (n₀)

. A necessary and sufficient condition for the existence of a bounded nonoscillatory solution is given.     

Convex 4-valent polytopes

Let {p_k}_k≥3 be a sequence of nonnegative integers which satisfies 8 + Σ_k≥3 (k-4) p_k = 0 and p₄ ≥ p₃. Then there is a convex 4-valent polytope P in E³ such that P has exactly p_k k-gons as faces. The inequality p₄ ≥ p₃ is the best possible in the sense that for c < 1 there exist sequences that are not 4-realizable that satisfy both 8 + Σ_{k ≥3} (k - 4) p_k = 0 and p₄ > cp₃. When Σ_{k ≥ 5} p_k ≠ 1, one can make the stronger statement that the sequence {p_k} is 4-reliazable if it satisfies 8 + Σ_{k ≥ 3} (k - 4) p_k = 0 and p₄ ≥ 2Σ_{k ≥ 5} p_k + max{k ¦ p_k ≠ 0}.     

Changing cofinalities and collapsing cardinals in models of set theory

If a˜cardinal κ₁, regular in the ground model M, is collapsed in the extension N to a˜cardinal κ₀ and its new cofinality, ρ, is less than κ₀, then, under some additional assumptions, each cardinal λ>κ₁ less than cc(P(κ₁)/[κ₁]^<κ₁) is collapsed to κ₀ as well. If in addition N=M[f], where f : ρ→κ₁ is an unbounded mapping, then N is a˜|λ|=κ₀-minimal extension. This and similar results are applied to generalized forcing notions of Bukovský and Namba.     

On the existence of kernels and h-kernels in directed graphs

A directed graph D with vertex set V is called cyclically h-partite (h2) provided one can partition V=V₀+V₁++V_h−1 so that if (u, υ) is an arc of D then uεV_i, and υεV_i+1 (notation mod h). In this communication we obtain a characterization of cyclically h-partite strongly connected digraphs. As a consequence we obtain a sufficient condition for a digraph to have a h-kernel.     

Uniqueness theorems for 3D inverse problems with incomplete data

In Ramm, Phys. Lett. 99A, (1983), 258-260, it is proved that a compactly supported inhomogeneity in the velocity profile is uniquely determined by the values of the acoustic pressure collected for all positions of the source and receiver on the surface of the earth ( on the whole plane P) at low frequencies. Here it is proved that the data collected on ω₁ x ω₂ suffice for the uniqueness theorem to hold, where ω₁ and ω₂ are arbitrary open sets on the plane P. This result holds also for the data collected on ω₁ × ω₂ at a fixed frequency.     

Vibration of a stamp partially adhering to an elastic medium : PMM, vol. 42, no. 6, 1978, pp. 1085–1092

There is examined the problem of vibration of a stamp of arbitrary planform occupying a space Ω and vibrating harmonically in an elastic medium with plane boundaries. It is assumed that the elastic medium is a packet of layers with parallel boundaries, at rest in the stiff or elastic half-space. Contact of three kinds is realized under the stamp: rigid adhesion in the domain Ω₁, friction-free contact in domain Ω₂, there are no tangential contact stresses, and “film” contact without normal force in domain Ω₃ (there are no normal contact stresses, only tangential stresses are present.). It is assumed that the boundaries of all the domains have twice continuously differentiable curvature and Ω = Ω₁ Ω₂ Ω₃.

The problem under consideration assumes the presence of a static load pressing the stamp to the layer and hindering the formation of a separation zone. Moreover, a dynamic load, harmonic in time, acts on the stamp causing dynamical stresses which are of the greatest interest since the solution of the static problem is obtained as a particular case of the dynamic problem for ω = 0 (ω is the frequency of vibration). The general solution is constructed in the form of a sum of static and dynamic solutions.

A uniqueness theorem is established for the integral equation of the problem mentioned and for the case of axisymmetric vibration of a circular stamp partially coupled rigidly to the layer, partially making friction-free contact, the problem is reduced to an effectively solvable system of integral equations of the second kind, which reduce easily to a Fredholm system.

These results are an extension of the method elucidated in [1], where by the approach in [1] must be altered qualitatively to obtain them.     

Coupling and harmonic functions in the case of continuous time Markov processes

Consider two transient Markov processes (X^v_t)_tεR·, (X^μ_t)_tεR· with the same transition semigroup and initial distributions v and μ. The probability spaces supporting the processes each are also assumed to support an exponentially distributed random variable independent of the process.

We show that there exist (randomized) stopping times S for (X^v_t), T for (X^μ_t) with common final distribution, L(X^v_S|S < ∞) = L(X^μ_T|T < ∞), and the property that for t < S, resp. t < T, the processes move in disjoint portions of the state space. For such a coupling (S, T) it is shown

where denotes the bounded harmonic functions of the Markov transition semigroup. Extensions, consequences and applications of this result are discussed.