Density of the Medvedev lattice of Π<Superscript>0</Superscript><Subscript>1</Subscript> classes

The partial ordering of Medvedev reducibility restricted to the family of ⁰₁ classes is shown to be dense. For two disjoint computably enumerable sets, the class of separating sets is an important example of a ⁰₁ class, which we call a ``c.e. separating class'. We show that there are no non-trivial meets for c.e. separating classes, but that the density theorem holds in the sublattice generated by the c.e. separating classes. Mathematics Subject Classification (2000): 03D30, 03D25     

Embeddings into the Medvedev and Muchnik lattices of Π<Superscript>0</Superscript><Subscript>1</Subscript> classes

Let _w and _M be the countable distributive lattices of Muchnik and Medvedev degrees of non-empty ₁⁰ subsets of 2, under Muchnik and Medvedev reducibility, respectively. We show that all countable distributive lattices are lattice-embeddable below any non-zero element of _w. We show that many countable distributive lattices are lattice-embeddable below any non-zero element of _M.Simpsons research was partially supported by NSF Grant DMS-0070718. We thank the anonymous referee for a careful reading of this paper and helpful comments.     

A Ring Theoretic Construction of Hadamard Difference Sets in ℤ<Subscript>8</Subscript><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>×ℤ<Subscript>2</Subscript><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

Let be the Galois ring of characteristic 2³ and rank n and let . We give an explicit construction of Hadamard difference sets in .}Research supported by NSA grant MDA 904-02-1-0080.     

On complexity reduction of Σ<Subscript>1</Subscript> formulas

 For a fixed q  ℕ and a given Σ₁ definition φ(d,x), where d is a parameter, we construct a model M of 1 Δ₀ + ? exp and a non standard d  M such that in M either φ has no witness smaller than d or phgr; is equivalent to a formula ϕ(d,x) having no more than q alternations of blocks of quantifiers. Received: 29 September 1998 / Revised version: 7 November 2001 Published online: 10 October 2002 RID="⋆" ID="⋆" Research supported in part by The State Committee for Scientific Research (Poland), KBN, grant number 2 PO3A 018 13. RID="⋆" ID="⋆" Research supported in part by The State Committee for Scientific Research (Poland), KBN, grant number 2 PO3A 018 13.     

Seas of squares with sizes from a Π<Stack><Subscript>1</Subscript><Superscript>0</Superscript></Stack> set

A family of sets is union-free if there are no three distinct sets in the family such that the union of two of the sets is equal to the third set. Kleitman proved that every union-free family has size at most (1+o(1))( _n/2 ⁿ ). Later, Burosch–Demetrovics–Katona–Kleitman–Sapozhenko asked for the number α(n) of such families, and they proved that \({2^{\left( {\begin{array}{*{20}{c}} n \\ {n/2} \end{array}} \right)}} \leqslant \alpha \left( n \right) \leqslant {2^{2\sqrt 2 \left( {\begin{array}{*{20}{c}} n \\ {n/2} \end{array}} \right)\left( {1 + o\left( 1 \right)} \right)}}\) They conjectured that the constant \(2\sqrt 2 \) can be removed in the exponent of the right-hand side. We prove their conjecture by formulating a new container-type theorem for rooted hypergraphs.     

A blend of methods of recursion theory and topology: A Π<Subscript>1</Subscript><Superscript>0</Superscript> tree of shadow points

This paper is a sequel to our [7]. In that paper we constructed a ₁⁰ tree of avoidable points. Here we construct a ₁⁰ tree of shadow points. This tree is a tree of sharp filters, where a sharp filter is a nested sequence of basic open sets converging to a point. In the construction we assign to each basic open set on the tree an address in 2^<. One interesting fact is that while our ₁⁰ tree of sharp filters (a subtree of ^<) is isomorphic to the tree of addresses (a subtree of 2^<), the tree of addresses is recursively enumerable but not recursive. To achieve this end we use a finite injury priority argument.Mathematics Subject Classification (2000): 03D45, 03D80, 03C57, 54A20     

The Δ<Superscript>0</Superscript><Subscript><Emphasis Type="Italic">α</Emphasis></Subscript>-Computable Enumerations of the Classes of Projective Planes

Studying computable representations of projective planes, for the classes K of pappian, desarguesian, and all projective planes, we prove that K ^c /? admits no hyperarithmetical Friedberg enumeration and admits a Friedberg Δ⁰_α+3-computable enumeration up to a Δ⁰ _α -computable isomorphism.     

Multi-self-similar Markov processes on ℝ<Subscript>+</Subscript><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> and their Lamperti representations

 A classical result, due to Lamperti, establishes a one-to-one correspondence between a class of strictly positive Markov processes that are self-similar, and the class of one-dimensional Lévy processes. This correspondence is obtained by suitably time-changing the exponential of the Lévy process. In this paper we generalise Lamperti's result to processes in n dimensions. For the representation we obtain, it is essential that the same time-change be applied to all coordinates of the processes involved. Also for the statement of the main result we need the proper concept of self-similarity in higher dimensions, referred to as multi-self-similarity in the paper. The special case where the Lévy process ξ is standard Brownian motion in n dimensions is studied in detail. There are also specific comments on the case where ξ is an n-dimensional compound Poisson process with drift. Finally, we present some results concerning moment sequences, obtained by studying the multi-self-similar processes that correspond to n-dimensional subordinators. Received: 22 August 2002 / Revised version: 10 February 2003 Published online: 15 April 2003 RID="*" ID="*" MaPhySto – Centre for Mathematical Physics and Stochastics, funded by a grant from the Danish National Research Foundation Mathematics Subject Classification (2000): 60G18, 60G51, 60J25, 60J60, 60J75 Key words or phrases: Lévy process – Self-similarity – Time-change – Exponential functional – Brownian motion – Bessel process – Piecewise deterministic Markov process – Moment sequence     

Trace operators and theta series for Γ<Subscript>0,n</Subscript>[q] and Γ<Subscript>n</Subscript>[q]

We consider the action of suitable trace operators on non homogeneous theta series that are Siegel modular forms for the principal congruence subgroups of the symplectic group of level q, _n[q]. Then, we prove that modular forms for the Hecke subgroup of level q, _0,n[q], that are linear combination of such theta series, can also be expressed as combination of (homogeneous) theta series that are modular forms with respect to _0,n[q].     

Quincunx multiresolution analysis for <Emphasis Type="Italic">L</Emphasis><Superscript>2</Superscript>(ℚ<Stack><Subscript>2</Subscript><Superscript>2</Superscript></Stack>)

With an eye on applications in quantum mechanics and other areas of science, much work has been done to generalize traditional analytic methods to p-adic systems. In 2002 the first paper on p-adic wavelets was published. Since then p-adic wavelet sets, multiresolution analyses, and wavelet frames have all been introduced. However, so far all constructions have involved dilations by p. This paper presents the first construction of a p-adic wavelet system with a more general matrix dilation, laying the foundation for further work in this direction.     

The geometric structure of Chebyshev sets in ℓ<Superscript>∞</Superscript>(<Emphasis Type="Italic">n</Emphasis>)

A subset M of a normed linear space X is called a Chebyshev set if each x X has a unique nearest point in M. We characterize Chebyshev sets in (n) in geometric terms and study the approximative properties of sections of Chebyshev sets, suns, and strict suns in (n) by coordinate subspaces.__________Translated from Funktsionalnyi Analiz i Ego Prilozheniya, Vol. 39, No. 1, pp. 1–10, 2005Original Russian Text Copyright © by A. R. AlimovSupported by RFBR grant No.02-01-00248.Translated by A. R. Alimov     

Dual Complexes of Cubical Subdivisions of ℝ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

We use a distortion to define the dual complex of a cubical subdivision of ℝ ⁿ as an n-dimensional subcomplex of the nerve of the set of n-cubes. Motivated by the topological analysis of high-dimensional digital image data, we consider such subdivisions defined by generalizations of quad- and oct-trees to n dimensions. Assuming the subdivision is balanced, we show that mapping each vertex to the center of the corresponding n-cube gives a geometric realization of the dual complex in ℝ ⁿ .     

Polysubharmonic Functions Near Infinity in ℜ<Superscript>n</Superscript>

For polyharmonic functions u of finite order defined outside a compact set in ⁿ, representations by means of -subharmonic functions defined on the whole of ⁿ are given. As a consequence, certain analogues of the classical Bôcher theorem are proved for u. Some of these results are extended to the case of polysubharmonic functions defined near infinity in ⁿ. Mathematics Subject Classification (2000) 31B30.     

Regular<Emphasis Type="Italic">n</Emphasis>-simplices in ℝ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> with vertices in ℤ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

In this paper theI andII regularn-simplices are introduced. We prove that the sufficient and necessary conditions for existence of anI regularn-simplex in ℝ ⁿ are that ifn is even thenn = 4m(m + 1), and ifn is odd thenn = 4m + 1 with thatn + 1 can be expressed as a sum of two integral squares orn = 4m - 1, and that the sufficient and necessary condition for existence of aII regularn-simplex in ℝ ⁿ isn = 2m ² - 1 orn = 4m(m + 1)(m ∈ ℕ). The connection between regularn-simplex in ℝ ⁿ and combinational design is given.     

Spin structures and spectra of ℤ<Subscript>2</Subscript><Superscript><Emphasis Type="Italic">k</Emphasis></Superscript>-manifolds

We give necessary and sufficient conditions for the existence of pin^± and spin structures on Riemannian manifolds with holonomy group ₂^k. For any n4 (resp. n6) we give examples of pairs of compact manifolds (resp. compact orientable manifolds) M₁, M₂, non homeomorphic to each other, that are Laplace isospectral on functions and on p-forms for any p and such that M₁ admits a pin^± (resp. spin) structure whereas M₂ does not.Mathematics Subject Classification (2000):58J53, 57R15, 20H15Partially supported by Conicet and grants from SecytUNC, Foncyt and AgCba.     

Siegmund Duality for Continuous Time Markov Chains on ℤ<Stack><Subscript>+</Subscript><Superscript>d</Superscript></Stack>

For the continuous time Markov chain with transition function P(t) on Z₊^d, we give the necessary and sufficient conditions for the existence of its Siegmund dual with transition function P(t). If Q, the q-matrix of P(t), is uniformly bounded, we show that the Siegmund dual relation can be expressed directly in terms of q-matrices, and a sufficient condition under which the Q-function is the Siegmund dual of some Q-function is also given.