Categoricity of computable infinitary theories

Computable structures of Scott rank are an important boundary case for structural complexity. While every countable structure is determined, up to isomorphism, by a sentence of , this sentence may not be computable. We give examples, in several familiar classes of structures, of computable structures with Scott rank whose computable infinitary theories are each -categorical. General conditions are given, covering many known methods for constructing computable structures with Scott rank , which guarantee that the resulting structure is a model of an -categorical computable infinitary theory. Work on this paper began at the Workshop on Model Theory and Computable Structure Theory at University of Florida Gainesville, in February, 2007. The authors are grateful to the organizers of this workshop. They are also grateful for financial support from National Science Foundation grants DMS DMS 05-32644, DMS 05-5484. The second author is also grateful for the support of grants RFBR 08-01-00336 and NSc-335.2008.1.     

Applications of the topological representation of the pcf-structure

We consider simplified representation theorems in pcf-theory and, in particular, we prove that if then there are cofinally many sequences of regular cardinals such that is represented by these sequences modulo the ideal of finite subsets, using a topological approach to the pcf-structure. Supported by the Portuguese Foundation for Science and Technology, ref. BD\16650\2004.     

On a Zero-Sum Generalization of a Variation of Schur’s Equation

Let be a positive integer, and let denote the cyclic group of residues modulo m. Furthermore, let denote the minimum integer N such that for every function there exist m integers satisfying and (and ). It is shown that for every odd prime m. Daniel Schaal: Partially supported by a South Dakota Governor’s 2010 Individual Research Seed Grant.     

On the Circumference of 2-Connected $$\mathcal{P}_{3}$$-Dominated Graphs

Let G be a connected graph. For at distance 2, we define , and , if then . G is quasi-claw-free if it satisfies , and G is P ₃-dominated() if it satisfies , for every pair (x, y) of vertices at distance 2. Certainly contains as a subclass. In this paper, we prove that the circumference of a 2-connected P ₃-dominated graph G on n vertices is at least min or , moreover if then G is hamiltonian or , where is a class of 2-connected nonhamiltonian graphs.     

Solutions of elliptic problems with nonlinearities of linear growth

In this paper, we study existence of nontrivial solutions to the elliptic equation

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 .     

On formulas for the index of the circular distributions

A circular distribution is a Galois equivariant map ψ from the roots of unity μ _∞ to an algebraic closure of such that ψ satisfies product conditions, for ϵ ∈ μ _∞ and , and congruence conditions for each prime number l and with (l, s) = 1, modulo primes over l for all , where μ _l and μ _s denote respectively the sets of lth and sth roots of unity. For such ψ, let be the group generated over by and let be , where U _s denotes the global units of . We give formulas for the indices and of and inside the circular numbers P _s and units C _s of Sinnott over . This work was supported by the SRC Program of Korea Science and Engineering Foundation (KOSEF) grant funded by the Korea government (MOST) (No. R11-2007-035-01001-0). This work was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD, Basic Research Promotion Fund) (KRF-2006-312-C00455).     

Strong Enumeration Reducibilities

We investigate strong versions of enumeration reducibility, the most important one being s-reducibility. We prove that every countable distributive lattice is embeddable into the local structure of the s-degrees. However, is not distributive. We show that on sets s-reducibility coincides with its finite branch version; the same holds of e-reducibility. We prove some density results for . In particular is upwards dense. Among the results about reducibilities that are stronger than s-reducibility, we show that the structure of the bs-degrees is dense. Many of these results on s-reducibility yield interesting corollaries for Q-reducibility as well.     

Fine Properties of the Integrated Density of States and a Quantitative Separation Property of the Dirichlet Eigenvalues

We consider one-dimensional difference Schr?dinger equations with real analytic function V(x). Suppose V(x) is a small perturbation of a trigonometric polynomial V ₀(x) of degree k ₀, and assume positive Lyapunov exponents and Diophantine ω. We prove that the integrated density of states is H?lder continuous for any k > 0. Moreover, we show that is absolutely continuous for a.e. ω. Our approach is via finite volume bounds. I.e., we study the eigenvalues of the problem on a finite interval [1, N] with Dirichlet boundary conditions. Then the averaged number of these Dirichlet eigenvalues which fall into an interval , does not exceed , k > 0. Moreover, for , this averaged number does not exceed exp , for any . For the integrated density of states of the problem this implies that for any . To investigate the distribution of the Dirichlet eigenvalues of on a finite interval [1, N] we study the distribution of the zeros of the characteristic determinants with complexified phase x, and frozen ω, E. We prove equidistribution of these zeros in some annulus and show also that no more than 2k ₀ of them fall into any disk of radius exp. In addition, we obtain the lower bound (with δ > 0 arbitrary) for the separation of the eigenvalues of the Dirichlet eigenvalues over the interval [0, N]. This necessarily requires the removal of a small set of energies. Received: February 2006, Accepted: December 2007     

Degrees of difficulty of generalized r.e. separating classes

Important examples of classes of functions are the classes of sets (elements of ^ω 2) which separate a given pair of disjoint r.e. sets: . A wider class consists of the classes of functions f ∈ ^ω k which in a generalized sense separate a k-tuple of r.e. sets (not necessarily pairwise disjoint) for each k ∈ ω: . We study the structure of the Medvedev degrees of such classes and show that the set of degrees realized depends strongly on both k and the extent to which the r.e. sets intersect. Let denote the Medvedev degrees of those such that no m + 1 sets among A ₀,...,A _k-1 have a nonempty intersection. It is shown that each is an upper semi-lattice but not a lattice. The degree of the set of k-ary diagonally nonrecursive functions is the greatest element of . If 2 ≤ l < k, then 0 _M is the only degree in which is below a member of . Each is densely ordered and has the splitting property and the same holds for the lattice it generates. The elements of are exactly the joins of elements of for . Supported by National Science Foundation grants DMS 0554841, 0532644 and 0652732.     

Rational invariants of certain classical groups over finite fields

Let be a finite field with q elements, where q is a prime power. Let G be a subgroup of the general linear group over and be the rational function field over . We seek to understand the structure of the rational invariant subfield . In this paper, we prove that is rational (or, purely transcendental) by giving an explicit set of generators when G is the symplectic group. In particular, the set of generators we gave satisfies the Dickson property.      

Normal subgroups of nonstandard symmetric and alternating groups

Let be a nonstandard model of Peano Arithmetic with domain M and let be nonstandard. We study the symmetric and alternating groups S _n and A _n of permutations of the set internal to , and classify all their normal subgroups, identifying many externally defined such normal subgroups in the process. We provide evidence that A _n and S _n are not split extensions by these normal subgroups, by showing that any such complement if it exists, cannot be a limit of definable sets. We conclude by identifying an -valued metric on and (where B _S , B _A are the maximal normal subgroups of S _n and A _n identified earlier) making these groups into topological groups, and by showing that if is -saturated then and are complete with respect to this metric.      

Reduced Minimum Modulus Preserving in Banach Space

Let be the algebra of all bounded linear operators on a complex Banach space X and γ(T) be the reduced minimum modulus of operator . In this work, we prove that if , is a surjective linear map such that is an invertible operator, then , for every , if and only if, either there exist two bijective isometries and such that for every , or there exist two bijective isometries and such that for every . This generalizes for a Banach space the Mbekhta’s theorem [12].      

The Extremal Truncated Moment Problem

For a degree 2n real d-dimensional multisequence to have a representing measure μ, it is necessary for the associated moment matrix to be positive semidefinite and for the algebraic variety associated to β, , to satisfy rank card as well as the following consistency condition: if a polynomial vanishes on , then . We prove that for the extremal case , positivity of and consistency are sufficient for the existence of a (unique, rank -atomic) representing measure. We also show that in the preceding result, consistency cannot always be replaced by recursiveness of . The first-named author’s research was partially supported by NSF Research Grants DMS-0099357 and DMS-0400741. The second-named author’s research was partially supported by NSF Research Grant DMS-0201430 and DMS-0457138.     

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.     

An asymptotic version of Dumnicki’s algorithm for linear systems in $${\mathbb{CP}^2}$$

Using Dumnicki’s approach to showing non-specialty of linear systems consisting of plane curves with prescribed multiplicities in sufficiently general points on we develop an asymptotic method to determine lower bounds for Seshadri constants of general points on . With this method we prove the lower bound for 10 general points on .      

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.     

On the minimality of the p-harmonic ma p $$x/\|x\|$$ for weighted energy

In this paper, we study the minimality of the map for the weighted energy functional , where is a continuous function. We prove that for any integer and any non-negative, non-decreasing continuous function f, the map minimizes E _f,p among the maps in which coincide with on . The case p = 1 has been already studied in [Bourgoin J.-C. Calc. Var. (to appear)]. Then, we extend results of Hong (see Ann. Inst. Poincaré Anal. Non-linéaire 17: 35–46 (2000)). Indeed, under the same assumptions for the function f, we prove that in dimension n ≥  7 for any real with , the map minimizes E _f,p among the maps in which coincide with on .      

Velocity Averaging Lemmas in Hyperbolic Sobolev Spaces for the Kinetic Transport Equation with Velocity Field on the Sphere

We show how the methods of [6–8] can be used to prove velocity averaging lemmas in hyperbolic Sobolev spaces for the kinetic transport equation . Here v is allowed to vary in the whole space and the velocity field lies on the unit sphere. We work in dimensions and, in contrast with [6, 8], we allow right-hand sides with velocity derivatives in any direction and not necessarily tangential to the sphere.      

Semicrossed products of simple C*-algebras

Let and be C*-dynamical systems and assume that is a separable simple C*-algebra and that α and β are *-automorphisms. Then the semicrossed products and are isometrically isomorphic if and only if the dynamical systems and are outer conjugate. K. R. Davidson was partially supported by an NSERC grant. E. G. Katsoulis was partially supported by a summer grant from ECU