On Lachlan’s major sub-degree problem

The Major Sub-degree Problem of A. H. Lachlan (first posed in 1967) has become a long-standing open question concerning the structure of the computably enumerable (c.e.) degrees. Its solution has important implications for Turing definability and for the ongoing programme of fully characterising the theory of the c.e. Turing degrees. A c.e. degree a is a major subdegree of a c.e. degree b > a if for any c.e. degree x, if and only if . In this paper, we show that every c.e. degree b ≠ 0 or 0′ has a major sub-degree, answering Lachlan’s question affirmatively. Both authors were funded by EPSRC Research Grant no. GR/M 91419, “Turing Definability”, by INTAS-RFBR Research Grant no. 97-0139, “Computability and Models”, and by an NSFC Grand International Joint Project Grant no. 60310213, “New Directions in Theory and Applications of Models of Computation”. Both authors are grateful to Andrew Lewis for helpful suggestions regarding presentation, technical aspects of the proof, and verification. A. Li is partially supported by National Distinguished Young Investigator Award no. 60325206 (People’s Republic of China).     

Convex sets with semidefinite representation

We provide a sufficient condition on a class of compact basic semialgebraic sets for their convex hull co(K) to have a semidefinite representation (SDr). This SDr is explicitly expressed in terms of the polynomials g _j that define K. Examples are provided. We also provide an approximate SDr; that is, for every fixed , there is a convex set such that (where B is the unit ball of ), and has an explicit SDr in terms of the g _j ’s. For convex and compact basic semi-algebraic sets K defined by concave polynomials, we provide a simpler explicit SDr when the nonnegative Lagrangian L _f associated with K and any linear is a sum of squares. We also provide an approximate SDr specific to the convex case.      

Skew Boolean algebras derived from generalized Boolean algebras

Every skew Boolean algebra S has a maximal generalized Boolean algebra image given by S/ where is the Green’s relation defined initially on semigroups. In this paper we study skew Boolean algebras constructed from generalized Boolean algebras B by a twisted product construction for which . In particular we study the congruence lattice of with an eye to viewing as a minimal skew Boolean cover of B. This construction is the object part of a functor from the category GB of generalized Boolean algebras to the category LSB of left-handed skew Boolean algebras. Thus we also look at its left adjoint functor . This paper was written while the second author was a Visiting Professor in the Department of Education at the University of Cagliari. The facilities and assistance provided by the University and by the Department are gratefully acknowledged.     

Orbits of the hyperoctahedral group as Euclidean designs

The hyperoctahedral group H in n dimensions (the Weyl group of Lie type B _n ) is the subgroup of the orthogonal group generated by all transpositions of coordinates and reflections with respect to coordinate hyperplanes.With e ₁ , ..., e _n denoting the standard basis vectors of ⁿ and letting x _k = e ₁ + ··· + e _k (k = 1, 2, ..., n), the set

The Birman–Craggs–Johnson homomorphism and abelian cycles in the Torelli group

In the 1970s, Birman–Craggs–Johnson (BCJ) (Trans AMS 237: 283–309, 1978; Trans AMS 261(1):423–422, 1980) used Rochlin’s invariant for homology 3-spheres to construct a remarkable surjective homomorphism , where is the Torelli group and B ₃ is a certain -vector space of Boolean (square-free) polynomials. By pulling back cohomology classes and evaluating them on abelian cycles, we construct dimensions worth of nontrivial elements of which cannot be detected rationally. These classes in fact restrict to nontrivial classes in the cohomology of the subgroup generated by Dehn twists about separating curves. We also use the “Casson–Morita algebra” and Morita’s integral lift of the BCJ map restricted to to give the same lower bound on . The first author is partially supported by NSF grant DMS-0606882 and was also supported in part by NSF grant DMS-0504208 and by a VIGRE postdoc under NSF grant 9983660 to Cornell University. The second author is supported in part by NSF grant DMS-0244542.     

Partitions of large Rado graphs

Let κ be a cardinal which is measurable after generically adding many Cohen subsets to κ and let be the κ-Rado graph. We prove, for 2 ≤ m < ω, that there is a finite value such that the set [κ] ^m can be partitioned into classes such that for any coloring of any of the classes C _i in fewer than κ colors, there is a copy of in such that is monochromatic. It follows that , that is, for any coloring of with fewer than κ colors there is a copy of such that has at most colors. On the other hand, we show that there are colorings of such that if is any copy of then for all , and hence . We characterize as the cardinality of a certain finite set of types and obtain an upper and a lower bound on its value. In particular, and for m > 2 we have where r _m is the corresponding number of types for the countable Rado graph. Research of M. Džamonja and J. A. Larson were partially supported by Engineering and Physical Sciences Research Council and research of W. J. Mitchell was partly supported by grant number DMS 0400954 from the United States National Science Foundation.     

Distinguishing non-standard natural numbers in a set theory within Łukasiewicz logic

In , a set theory with the comprehension principle within Łukasiewicz infinite-valued predicate logic, we prove that a statement which can be interpreted as “there is an infinite descending sequence of initial segments of ω” is truth value 1 in any model of , and we prove an analogy of Hájek’s theorem with a very simple procedure.      

Semilinear subelliptic problems with critical growth on Carnot groups

We prove existence and multiplicity of solutions for the semilinear subelliptic problem with critical growth in Ω, u = 0 on ∂Ω, where is a sublaplacian on a Carnot group , 2* = 2Q/(Q − 2) is the critical Sobolev exponent for and Ω is a bounded domain of .     

<Emphasis Type="Italic">L</Emphasis>-functions of symmetric products of the Kloosterman sheaf over Z

The classical n-variable Kloosterman sums over the finite field F _p give rise to a lisse -sheaf Kl _n+1 on , which we call the Kloosterman sheaf. Let L _p (G _{m, F p} , Sym ^k Kl _n+1, s) be the L-function of the k-fold symmetric product of Kl _n+1. We construct an explicit virtual scheme X of finite type over Spec Z such that the p-Euler factor of the zeta function of X coincides with L _p (G _{m, F p} , Sym ^k Kl _n+1, s). We also prove similar results for and . The research of L. Fu is supported by the NSFC (10525107).     

Chains and antichains in partial orderings

We study the complexity of infinite chains and antichains in computable partial orderings. We show that there is a computable partial ordering which has an infinite chain but none that is or , and also obtain the analogous result for antichains. On the other hand, we show that every computable partial ordering which has an infinite chain must have an infinite chain that is the difference of two sets. Our main result is that there is a computably axiomatizable theory K of partial orderings such that K has a computable model with arbitrarily long finite chains but no computable model with an infinite chain. We also prove the corresponding result for antichains. Finally, we prove that if a computable partial ordering has the feature that for every , there is an infinite chain or antichain that is relative to , then we have uniform dichotomy: either for all copies of , there is an infinite chain that is relative to , or for all copies of , there is an infinite antichain that is relative to .     

Branching in the {\Sigma^0_2} -enumeration degrees: a new perspective

We give an alternative and more informative proof that every incomplete -enumeration degree is the meet of two incomparable -degrees, which allows us to show the stronger result that for every incomplete -enumeration degree a, there exist enumeration degrees x ₁ and x ₂ such that a, x ₁, x ₂ are incomparable, and for all b  ≤  a, b  =  (b ∨ x ₁ ) ∧ (b ∨ x ₂ ). The first author would like to thank her advisor, Andrea Sorbi, whose guidance made this paper possible. The second author has been supported by a Marie Curie Incoming International Fellowship of the European Community FP6 Program under contract number MIFI-CT-2006-021702.     

Homotopy Categories for Simply Connected Torsion Spaces

For each n > 1 and each multiplicative closed set of integers S, we study closed model category structures on the pointed category of topological spaces, where the classes of weak equivalences are classes of maps inducing isomorphism on homotopy groups with coefficients in determined torsion abelian groups, in degrees higher than or equal to n. We take coefficients either on all the cyclic groups with s ∈ S, or in the abelian group where is the group of fractions of the form with s ∈ S. In the first case, for n > 1 the localized category is equivalent to the ordinary homotopy category of (n − 1)-connected CW-complexes whose homotopy groups are S-torsion. In the second case, for n > 1 we obtain that the localized category is equivalent to the ordinary homotopy category of (n − 1)-connected CW-complexes whose homotopy groups are S-torsion and the nth homotopy group is divisible. These equivalences of categories are given by colocalizations , obtained by cofibrant approximations on the model structures. These colocalization maps have nice universal properties. For instance, the map is final (in the homotopy category) among all the maps of the form Y → X with Y an (n − 1)-connected CW-complex whose homotopy groups are S-torsion and its nth homotopy group is divisible. The spaces , are constructed using the cones of Moore spaces of the form M(T, k), where T is a coefficient group of the corresponding structure of models, and homotopy colimits indexed by a suitable ordinal. If S is generated by a set P of primes and S ^p is generated by a prime p ∈ P one has that for n > 1 the category is equivalent to the product category . If the multiplicative system S is generated by a finite set of primes, then localized category is equivalent to the homotopy category of n-connected Ext-S-complete CW-complexes and a similar result is obtained for .     

Plane polynomial automorphisms of fixed multidegree

Let be the group of polynomial automorphisms of the complex affine plane. On one hand, can be endowed with the structure of an infinite dimensional algebraic group (see Shafarevich in Math USSR Izv 18:214–226, 1982) and on the other hand there is a partition of according to the multidegree (see Friedland and Milnor in Ergod Th Dyn Syst 9:67–99, 1989). Let denote the set of automorphisms whose multidegree is equal to d. We prove that is a smooth, locally closed subset of and show some related results. We give some applications to the study of the varieties (resp. ) of automorphisms whose degree is equal to m (resp. is less than or equal to m).     

Model theory of the regularity and reflection schemes

Abstract  This paper develops the model theory of ordered structures that satisfy Keisler’s regularity scheme and its strengthening REF (the reflection scheme) which is an analogue of the reflection principle of Zermelo-Fraenkel set theory. Here is a language with a distinguished linear order <, and REF consists of formulas of the form

Quelques Résultats sur les Algèbres Flexibles Préhilbertiennes sans Diviseurs de Zéro Vérifiant ∥a 2∥ = ∥a∥2

Résumé. Soit A une algèbre réelle. On suppose que l’espace vectoriel A est muni d’une norme ∥.∥ préhilbertienne vérifiant ∥a ²∥ = ∥a∥² pour tout . Si A est flexible, sans diviseurs de zéro et de dimension ≤ 4, alors A est isomorphe à ou , ce qui généralise un théorème d’El-Mallah [1]. Si A est flexible, sans diviseurs de zéro, contenant un idempotent central et vérifiant la propriété d’Osborn, alors A est de dimension finie et isomorphe à , ou . Enfin nous montrons qu’une algèbre normée préhilbertienne unitaire d’unité e telle que ∥e∥ = 1 est flexible et vérifie ∥a ²∥ = ∥ a∥².

---

Let A be a real algebra. Assuming that a vector space A is endowed with a pre-Hilbert norm ∥.∥ satisfying ∥a ²∥ = ∥a∥² for all . If A is flexible, without divisor of zero and of a dimension ≤ 4, then A is isomorphic to or , which generalize El-Mallah’s theorem [1]. If A is flexible, without divisor of zero, containing a central idempotent and satisfying Osborn’s properties, then A is finite dimensional and isomorphic to , or . Finally we prove that a normed pre-Hilbert algebra with unit e such that ∥e∥ = 1 is flexible and satisfies ∥a ²∥ = ∥a∥².

     

Effectively closed sets and enumerations

An effectively closed set, or class, may viewed as the set of infinite paths through a computable tree. A numbering, or enumeration, is a map from ω onto a countable collection of objects. One numbering is reducible to another if equality holds after the second is composed with a computable function. Many commonly used numberings of classes are shown to be mutually reducible via a computable permutation. Computable injective numberings are given for the family of classes and for the subclasses of decidable and of homogeneous classes. However no computable numberings exist for small or thin classes. No computable numbering of trees exists that includes all computable trees without dead ends. Research partially supported by National Science Foundation grants DMS 0554841, 0532644 and 0652732.     

A new family of maximal curves over a finite field

It has been known for a long time that the Deligne–Lusztig curves associated to the algebraic groups of type and defined over the finite field all have the maximum number of -rational points allowed by the Weil “explicit formulas”, and that these curves are -maximal curves over infinitely many algebraic extensions of . Serre showed that an -rational curve which is -covered by an -maximal curve is also -maximal. This has posed the problem of the existence of -maximal curves other than the Deligne–Lusztig curves and their -subcovers, see for instance Garcia (On curves with many rational points over finite fields. In: Finite Fields with Applications to Coding Theory, Cryptography and Related Areas, pp. 152–163. Springer, Berlin, 2002) and Garcia and Stichtenoth (A maximal curve which is not a Galois subcover of the Hermitan curve. Bull. Braz. Math. Soc. (N.S.) 37, 139–152, 2006). In this paper, a positive answer to this problem is obtained. For every q = n ³ with n = p ^r  > 2, p ≥ 2 prime, we give a simple, explicit construction of an -maximal curve that is not -covered by any -maximal Deligne–Lusztig curve. Furthermore, the -automorphism group Aut has size n ³(n ³ + 1)(n ² − 1)(n ² − n + 1). Interestingly, has a very large -automorphism group with respect to its genus . Research supported by the Italian Ministry MURST, Strutture geometriche, combinatoria e loro applicazioni, PRIN 2006–2007.     

<Emphasis Type="Italic">h</Emphasis>-Principles for curves and knots of constant curvature

We prove that curves of constant curvature satisfy, in the sense of Gromov, the relative -dense h-principle in the space of immersed curves in Euclidean space R ^{n ≥ 3}. In particular, in the isotopy class of any given knot f there exists a knot f͂ of constant curvature which is -close to f. More importantly, we show that if f is , then the curvature of f͂ may be set equal to any constant c which is not smaller than the maximum curvature of f. We may also require that f͂ be tangent to f along any finite set of prescribed points, and coincide with f over any compact set with an open neighborhood where f has constant curvature c. The proof involves some basic convexity theory, and a sharp estimate for the position of the average value of a parameterized curve within its convex hull. The author’s research was supported in part by NSF CAREER award DMS-0332333.     

Generalised twists,stationary loops,and the Dirichlet energy over a space of measure preserving maps

Let be a bounded Lipschitz domain and consider the Dirichlet energy functional

A subdiffusive behaviour of recurrent random walk in random environment on a regular tree

We are interested in the random walk in random environment on an infinite tree. Lyons and Pemantle (Ann. Probab. 20, 125–136, 1992) give a precise recurrence/transience criterion. Our paper focuses on the almost sure asymptotic behaviours of a recurrent random walk (X _n ) in random environment on a regular tree, which is closely related to Mandelbrot’s (C. R. Acad. Sci. Paris 278, 289–292, 1974) multiplicative cascade. We prove, under some general assumptions upon the distribution of the environment, the existence of a new exponent such that behaves asymptotically like . The value of ν is explicitly formulated in terms of the distribution of the environment.