A new conservation result of WKL0 over RCA0

In this paper we give a partial answer to a conjecture of Tanaka. We prove that: if WKL₀ proves a sentence of the form (∀X)(∃!Y)ψ(X, Y) for a Σ⁰ ₃-formula ψ, then so does RCA₀. Received: 12 April 1999 / Published online: 3 October 2001     

On the Π11‐separation principle

We study the proof‐theoretic strength of the Π₁¹‐separation axiom scheme, and we show that Π₁¹‐separation lies strictly in between the Δ₁¹‐comprehension and Σ₁¹‐choice axiom schemes over RCA₀. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Graph Coloring and Reverse Mathematics

Improving a theorem of Gasarch and Hirst, we prove that if 2 ≤ k ≤ m < ω, then the following is equivalent to WKL₀ over RCA₀ Every locally k‐colorable graph is m‐colorable.     

The birth and death processes with zero as their absorbing barrier

LetE=(0, 1,...), Q ^b=(q_ij), i, j=0, 1, ..., whereq _{i, i–1}=a_i, q_{i, i+1}=b_i, q_ii=–(a_i+b_i), q_ij=0, when|i–j|>1. a ₀=0, b₀=b>0, a_i, b_i>0 (i>0). Lettingb=0 inQ ^b, we get the matrixQ ⁰.The time homogeneous Markov processX ^b ={x ^b (t,w), 0t< ^b (w)} (X ⁰={x⁰(t,w), 0t<⁰(w)}), withQ ^b (Q ⁰, respectively) as its density matrix and withE as its state space, is calledQ ^b (Q ⁰, respectively) process in this paper.Q ^b andQ ⁰ processes are all called the birth and death processes, with zero being the reflecting barrier ofQ ^b processes, the absorbing barrier ofQ ⁰ processes.AllQ ^b processes have been constructed by both probability and analytical methods (Wang [2], Yang [1]). In this paper, theQ ⁰ processes are imbedded intoQ ^b processes and all theQ ⁰ processes are directly constructed from theQ ^b processes. The main results are:Letb>0 be arbitrarily fixed, then there is a one to one correspondence between theQ ⁰ processes and theQ ^b processes (in the sense of transition probability).TheQ ⁰ process is unique iffR ^*=. SupposingR<, then:IfX ⁰={x⁰(t,w), 0t<⁰(w)} is a non-minimalQ ⁰ process, then its eigensequence (p, q, r _n, n–1) satisfies § 4(7).Conversely, let a non-negative number sequence (p, q, r _n, n–1) satisfying § 4(7) be arbitrarily given, then there exists a unique non-minimalQ ⁰ processX ⁰ with eigensequence (p, q, r _n, n–1). The Laplace transform of the transition probability (p _ij ⁰ (t)) ofX ⁰ is determined by § 4(15). X ⁰ is honest iffr _–1=0.X ⁰ satisfies the forward equation iffp=0.     

Spectral Density for Third Order Cumulants under Strong Mixing Conditions

If X{X_v: v ^d} is a strictly stationary random field, with X₀ bounded and expressible as a sum of indicator functions satisfying certain conditions, if the mixing coefficient α(s) is summable over ^d (that, is, ∑_m m^d−1α(m)<∞), and if a mixing condition involving three sets is satisfied, then the third order cumulant Cum(X_a, X_b, X_c) of X has a continuous spectral density. We do not begin with the assumption that the cumulants are absolutely summable.     

Small Time One-Sided LIL Behavior for Lévy Processes at Zero

We specify a function b ₀(t) in terms of the Lévy triplet such that lim sup  _t→0 X _t /b ₀(t)∈[1,1.8] a.s. iff ò₀¹[` \varPi ]⁽⁺⁾(b₀(t)) dt < ￥\int_{0}^{1}\overline{ \varPi }^{(+)}(b_{0}(t))\,dt<\infty for any Lévy process X with unbounded variation and a Brownian component σ=0. We show with an example that there are cases where lim sup  _t→0 X _t /b(t)=1 a.s. but b(t) is not asymptotically equivalent to b ₀(t) as t tends to 0. We achieve this by introducing an integral criterion which checks whether lim sup  _t→0 X _t /b(t) is 0, infinity, or a finite positive value for b(t) satisfying very mild conditions and any Lévy process.     

Global continuation for first order systems over the half‐line involving parameters

Let X be one of the functional spaces W^1,p ((0, ∞), ?^N ) or C₀¹ ([0, ∞), ?^N ), we study the global continuation in λ for solutions (λ, u, ξ) ∈ ? × X × ?^k of the following system of ordinary differential equations: where ?^N = X₁ ⊕ X₂ is a given decomposition, with associated projection P: ?^N → X₁. Under appropriate conditions upon the given functions F and φ, this problem gives rise to a nonlinear Fredholm operator which is proper on the closed bounded subsets of ? × X × ?^k and whose zeros correspond to the solutions of the original problem. Using a new abstract continuation result, based on a recent degree theory for proper Fredholm mappings of index zero, we reduce the continuation problem to that of finding a priori estimates for the possible solutions (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Generating Random Vectors in (ℤ/<Emphasis Type="Italic">p</Emphasis>ℤ)<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript> via an Affine Random Process

This paper considers some random processes of the form X _n+1=T X _n +B _n (mod p) where B _n and X _n are random variables over (ℤ/pℤ) ^d and T is a fixed d×d integer matrix which is invertible over the complex numbers. For a particular distribution for B _n , this paper improves results of Asci to show that if T has no complex eigenvalues of length 1, then for integers p relatively prime to det (T), order (log p)² steps suffice to make X _n close to uniformly distributed where X ₀ is the zero vector. This paper also shows that if T has a complex eigenvalue which is a root of unity, then order p ^b steps are needed for X _n to get close to uniformly distributed for some positive value b≤2 which may depend on T and X ₀ is the zero vector.     

Logic Regression

Logic regression is an adaptive regression methodology that attempts to construct predictors as Boolean combinations of binary covariates. In many regression problems a model is developed that relates the main effects (the predictors or transformations thereof) to the response, while interactions are usually kept simple (two- to three-way interactions at most). Often, especially when all predictors are binary, the interaction between many predictors may be what causes the differences in response. This issue arises, for example, in the analysis of SNP microarray data or in some data mining problems. In the proposed methodology, given a set of binary predictors we create new predictors such as “X₁, X₂, X³, and X⁴ are true,” or “X⁵ or X⁶ but not X⁷ are true.” In more specific terms: we try to fit regression models of the form g(E[Y]) = b₀ + b₁ L₁ + · · · + b_n L_n , where L_j is any Boolean expression of the predictors. The L_j and b_j are estimated simultaneously using a simulated annealing algorithm. This article discusses how to fit logic regression models, how to carry out model selection for these models, and gives some examples.     

Successor levels of the Jensen hierarchy

I prove that there is a recursive function T that does the following: Let X be transitive and rudimentarily closed, and let X ′ be the closure of X ∪ {X } under rudimentary functions. Given a Σ₀‐formula φ (x) and a code c for a rudimentary function f, T (φ, c, ) is a Σ_ω ‐formula such that for any ∈ X, X ′ ? φ [f ( )] iff X ? T (φ, c, )[ ]. I make this precise and show relativized versions of this. As an application, I prove that under certain conditions, if Y is the Σ_ω extender ultrapower of X with respect to some extender F that also is an extender on X ′, then the closure of Y ∪ {Y } under rudimentary functions is the Σ₀ extender ultrapower of X′ with respect to F, and the ultrapower embeddings agree on X. (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Determinacy of Wadge classes and subsystems of second order arithmetic

In this paper we study the logical strength of the determinacy of infinite binary games in terms of second order arithmetic. We define new determinacy schemata inspired by the Wadge classes of Polish spaces and show the following equivalences over the system RCA₀*, which consists of the axioms of discrete ordered semi‐rings with exponentiation, Δ₁⁰ comprehension and Π₀⁰ induction, and which is known as a weaker system than the popularbase theory RCA₀: 1. Bisep(Δ₁⁰, Σ₁⁰)‐Det* ? WKL₀, (1) 2. Bisep(Δ₁⁰, Σ₂⁰)‐Det* ? ATR₀ + Σ₁¹ induction, (2) 3. Bisep(Σ₁⁰, Σ₂⁰)‐Det* ? Sep(Σ₁⁰, Σ₂⁰)‐Det* ? Π₁¹‐CA₀, (3) 4. Bisep(Δ₂⁰, Σ₂⁰)‐Det* ? Π₁¹‐TR₀, (4) where Det* stands for the determinacy of infinite games in the Cantor space (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the complexity of branch‐and‐bound search for random trees

Let T_n be a b‐ary tree of height n, which has independent, non‐negative, identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Consider the problem of finding the minimum leaf value of T_n. Assume that the edge random variable X is nondegenerate, has E {X^θ}<∞ for some θ>2, and satisfies bP{X=c}<1 where c is the leftmost point of the support of X. We analyze the performance of the standard branch‐and‐bound algorithm for this problem and prove that the number of nodes visited is in probability (β+o(1))ⁿ, where β∈(1, b) is a constant depending only on the distribution of the edge random variables. Explicit expressions for β are derived. We also show that any search algorithm must visit (β+o(1))ⁿ nodes with probability tending to 1, so branch‐and‐bound is asymptotically optimal where first‐order asymptotics are concerned. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14: 309–327, 1999     

The strong soundness theorem for real closed fields and Hilbert’s Nullstellensatz in second order arithmetic

By RCA₀, we denote a subsystem of second order arithmetic based on ⁰₁ comprehension and ⁰₁ induction. We show within this system that the real number system R satisfies all the theorems (possibly with non-standard length) of the theory of real closed fields under an appropriate truth definition. This enables us to develop linear algebra and polynomial ring theory over real and complex numbers, so that we particularly obtain Hilberts Nullstellensatz in RCA₀.Mathematics Subject Classification (2000): Primary 03F35; Secondary 03B30, 12D10     

On the law of the iterated logarithm for weighted sums of independent random variables in a Banach space

Assume that (X _n) are independent random variables in a Banach space, (b _n) is a sequence of real numbers, S_n= ₁ ⁿ b_iX_i, and B_n= ₁ ⁿ b _i ² . Under certain moment restrictions imposed on the variablesX _n, the conditions for the growth of the sequence (b_n) are established, which are sufficient for the almost sure boundedness and precompactness of the sequence (S_n/B _n ln ln B_n)^1/2).Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 45, No. 9, pp. 1225–1231, September, 1993.     

Almost sure central limit theorem for partial sums and maxima

Let X, X₁, X₂, … be i.i.d. random variables with nondegenerate common distribution function F, satisfying EX = 0, EX² = 1. Let X_i and M_n = max{X_i, 1 ≤ i ≤ n }. Suppose there exists constants a_n > 0, b_n ∈ R and a nondegenrate distribution G (y) such that Then, we have almost surely, where f (x, y) denotes the bounded Lipschitz 1 function and Φ(x) is the standard normal distribution function (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Harmonic analysis and asymptotic behavior of solutions to the abstract cauchy problem

LetC _ub ( $\mathbb{J}$ , X) denote the Banach space of all uniformly continuous bounded functions defined on $\mathbb{J}$ 2 ε {?⁺, ?} with values in a Banach spaceX. Let ? be a class fromC _ub( $\mathbb{J}$ ,X). We introduce a spectrumsp?(φ) of a functionφ εC _ub (?,X) with respect to ?. This notion of spectrum enables us to investigate all twice differentiable bounded uniformly continuous solutions on ? to the abstract Cauchy problem (*)ω′(t) =Aω(t) +φ(t),φ(0) =x,φ ε ?, whereA is the generator of aC ₀-semigroupT(t) of bounded operators. Ifφ = 0 andσ(A) ∩i? is countable, all bounded uniformly continuous mild solutions on ?⁺ to (*) are studied. We prove the bound-edness and uniform continuity of all mild solutions on ?⁺ in the cases (i)T(t) is a uniformly exponentially stableC ₀-semigroup andφ εC _ub(?,X); (ii)T(t) is a uniformly bounded analyticC ₀-semigroup,φ εC _ub (?,X) andσ(A) ∩i sp(φ) = Ø. Under the condition (i) if the restriction ofφ to ?⁺ belongs to ? = ?(?⁺,X), then the solutions belong to ?. In case (ii) if the restriction ofφ to ?⁺ belongs to ? = ?(?⁺,X), andT(t) is almost periodic, then the solutions belong to ?. The existence of mild solutions on ? to (*) is also discussed.     

On the stability of characterizations by an identical distribution property

Let X ₁, X ₂, … , X _n be i.i.d. random variables with common distribution F, and let b ₁, b ₂, … , b _n be real coefficients such that ∑ b _j ² = 1. We prove that F is close to the normal distribution in the Lévy metric whenever the distribution of the linear statistic ∑ b _j X _j is close to F.     

Recursive method for building Arnold’s triangle X p (a,b)

We give a recursive method for building X _p (a,b) for each prime p. Arnold’s triangle is composed of positive integers: for a>1 and 0<b<a, X _p (a,b) is the degree of the highest power of p dividing the difference of the binomial coefficients C _pa ^pb −C _a ^b .      

Generalized slant Toeplitz operators on H2

For an integer k ≥ 2, k^th‐order slant Toeplitz operator U_φ [1] with symbol φ in L^∞(??), where ?? is the unit circle in the complex plane, is an operator whose representing matrixM = (α_ij ) is given by α_ij = 〈φ, z^ki–j〉, where 〈. , .〉 is the usual inner product in L²(??). The operator V_φ denotes the compression of U_φ to H²(??) (Hardy space). Algebraic and spectral properties of the operator V_φ are discussed. It is proved that spectral radius of V_φ equals the spectral radius of U_φ, if φ is analytic or co‐analytic, and if T_φ is invertible then the spectrum of V_φ contains a closed disc and the interior of the disc consists of eigenvalues of infinite multiplicities. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)