Isomorphism types of Rogers semilattices for families from different levels of the arithmetical hierarchy

We investigate differences in isomorphism types for Rogers semilattices of computable numberings of families of sets lying in different levels of the arithmetical hierarchy. Supported by RFBR grant No. 05-01-00819 and by INTAS grant No. 00-499. Supported by NSFC grant No. 60310213. __________ Translated from Algebra i Logika, Vol. 45, No. 6, pp. 637–654, November–December, 2006.     

<Emphasis Type="Italic">e</Emphasis>-Principal numberings

We prove the existence of the computable families of finite sets and general recursive functions with no e-principal numbering. We give a series of examples of e-degrees such that the p-degrees of their computable numberings include no top p-degree.     

Numbered distributive semilattices

In this article, we consider several definitions of a Lachlan semilattice; i.e., a semilattice isomorphic to a principal ideal of the semilattice of computably enumerable m-degrees. We also answer a series of questions on constructive posets and prove that each distributive semilattice with top and bottom is a Lachlan semilattice if it admits a Σ ₃ ⁰ -representation as an algebra but need not be a Lachlan semilattice if it admits a Σ ₃ ⁰ -representation as a poset. The examples are constructed of distributive lattices that are constructivizable as posets but not constructivizable as join (meet) semilattices. We also prove that every locally lattice poset (in particular, every lattice and every distributive semilattice) possessing a Δ ₂ ⁰ -representation is positive.     

Minimal Coverings in the Rogers Semilattices of∑-Computable Numberings

Under study is the problem of existence of minimal and strong minimal coverings in Rogers semilattices of -computable numberings for n2. Two sufficient conditions for existence of minimal coverings and one sufficient condition for existence of strong minimal coverings are found. The problem is completely solved of existence of minimal coverings in Rogers semilattices of -computable numberings of a finite family.     

An arithmetical equation with respect to regular convolutions

It is well known that Euler’s totient function \(\phi \) satisfies the arithmetical equation \( \phi (mn)\phi ((m, n))=\phi (m)\phi (n)(m, n) \) for all positive integers m and n, where (m, n) denotes the greatest common divisor of m and n. In this paper we consider this equation in a more general setting by characterizing the arithmetical functions f with \(f(1)\ne 0\) which satisfy the arithmetical equation \( f(mn)f((m,n)) = f(m)f(n)g((m, n)) \) for all positive integers m, n with \(m,n \in A(mn)\), where A is a regular convolution and g is an A-multiplicative function. Euler’s totient function \(\phi _A\) with respect to A is an example satisfying this equation.     

Axiomatizing Provable <Emphasis Type="Italic">n</Emphasis>-Provability

The set of all formulas whose n-provability in a given arithmetical theory S is provable in another arithmetical theory T is a recursively enumerable extension of S. We prove that such extensions can be naturally axiomatized in terms of transfinite progressions of iterated local reflection schemata over S. Specifically, the set of all provably 1-provable sentences in Peano arithmetic PA can be axiomatized by an ε₀-times iterated local reflection schema over PA. The resulting characterizations provide additional information on the proof-theoretic strength of these theories and on the complexity of their axiomatization.     

Equivariant Classification of <Emphasis Type="Italic">b</Emphasis><Superscript><Emphasis Type="Italic">m</Emphasis></Superscript>-symplectic Surfaces

Inspired by Arnold’s classification of local Poisson structures [1] in the plane using the hierarchy of singularities of smooth functions, we consider the problem of global classification of Poisson structures on surfaces. Among the wide class of Poisson structures, we consider the class of b^m-Poisson structures which can be also visualized using differential forms with singularities as b^m-symplectic structures. In this paper we extend the classification scheme in [24] for b^m-symplectic surfaces to the equivariant setting. When the compact group is the group of deck-transformations of an orientable covering, this yields the classification of these objects for nonorientable surfaces. The paper also includes recipes to construct b^m-symplectic structures on surfaces. The feasibility of such constructions depends on orientability and on the colorability of an associated graph. The desingularization technique in [10] is revisited for surfaces and the compatibility with this classification scheme is analyzed in detail.     

Positive Presentations of Families Relative to <Emphasis Type="Italic">e</Emphasis>-Oracles

We introduce the notion of A-numbering which generalizes the classical notion of numbering. All main attributes of classical numberings are carried over to the objects considered here. The problem is investigated of the existence of positive and decidable computable A-numberings for the natural families of sets e-reducible to a fixed set. We prove that, for every computable A-family containing an inclusion-greatest set, there also exists a positive computable A-numbering. Furthermore, for certain families we construct a decidable (and even single-valued) computable total A-numbering when A is a low set; we also consider a relativization containing all cases of total sets (this in fact corresponds to computability with a usual oracle).     

A family of non-isomorphism results

We calculate the local groups of germs associated with the higher dimensional R. Thompson groups nV. For a given \({n\in N\cup\left\{\omega\right\}}\) , these groups of germs are free abelian groups of rank r, for r ≤ n (there are some groups of germs associated with nV with rank precisely k for each index 1 ≤ k ≤ n). By Rubin’s theorem, any conjectured isomorphism between higher dimensional R. Thompson groups induces an isomorphism between associated groups of germs. Thus, if m ≠ n the groups mV and nV cannot be isomorphic. This answers a question of Brin.     

Discrete universality of the <Emphasis Type="Italic">L</Emphasis>-functions of elliptic curves

A discrete universality theorem is obtained in the Voronin sense for the L-functions of elliptic curves. We use the difference of an arithmetical progression h > 0 such that \(\exp \left\{ {\frac{{2\pi k}}{h}} \right\}\) is rational for some k ≠ 0. A limit theorem in the space of analytic functions plays a crucial role in the proof.     

New Applications of the <Emphasis Type="Italic">p</Emphasis>-Adic Nevanlinna Theory

Let IK be an algebraically closed field of characteristic 0 complete for an ultrametric absolute value. Following results obtained in complex analysis, here we examine problems of uniqueness for meromorphic functions having finitely many poles, sharing points or a pair of sets (C.M. or I.M.) defined either in the whole field IK or in an open disk, or in the complement of an open disk. Following previous works in C, we consider functions fⁿ(x)f^m(ax + b), gⁿ(x)g^m(ax + b) with |a| = 1 and n ≠ m, sharing a rational function and we show that f/g is a n + m-th root of 1 whenever n + m ≥ 5. Next, given a small function w, if n, m ∈ IN are such that |n ? m|_∞ ≥ 5, then fⁿ(x)f^m(ax + b) ? w has infinitely many zeros. Finally, we examine branched values for meromorphic functions fⁿ(x)f^m(ax + b).     

<Emphasis Type="Italic">X</Emphasis>-decomposable finite groups for <Emphasis Type="Italic">X</Emphasis>={1, <Emphasis Type="Italic">m</Emphasis>, <Emphasis Type="Italic">m</Emphasis> + 1, <Emphasis Type="Italic">m</Emphasis> + 2}

A normal subgroup N of a finite group G is called n-decomposable in G if N is the union of n distinct G-conjugacy classes. We study the structure of nonperfect groups in which every proper nontrivial normal subgroup is m-decomposable, m+1-decomposable, or m+2-decomposable for some positive integer m. Furthermore, we give classification for the soluble case.     

Certain types of irregular <Emphasis Type="Italic">m</Emphasis>-polar fuzzy graphs

The notion of an m-polar fuzzy set is a generalization of a bipolar fuzzy set. We apply the concept of m-polar fuzzy sets to graphs. We introduce certain types of irregular m-polar fuzzy graphs and investigate some of their properties. We describe the concepts of types of irregular m-polar fuzzy graphs with several examples. We also present applications of m-polar fuzzy graphs in decision making and social network as examples.     

The Dedekind MacNeille site completion of a meet semilattice

The cuts of the classical Dedekind-MacNeille completion DM(S) of a meet semilattice S give rise to a natural cut coverage in the down-set frame \({\mathcal{D}S}\): down-set D covers element s if s lies below all upper bounds of D. This, in turn, leads to what we call the Dedekind-MacNeille frame extension DMF(S). The meet semilattices S for which DM(S) = DMF(S), which we refer to as proHeyting semilattices, can be specified by a simple formula, and we provide a number of equivalent characterizations. A sample result is that DM(S) = DMF(S) iff DM(S) is a Heyting algebra iff DM(S) coincides with the Bruns-Lakser injective envelope.     

The construction of infinite families of any κ-tight optimal and singular κ-tight optimal directed double loop networks

The double loop network (DLN) is a circulant digraph with n nodes and outdegree 2. It is an important topological structure of computer interconnection networks and has been widely used in the designing of local area networks and distributed systems. Given the number n of nodes, how to construct a DLN which has minimum diameter? This problem has attracted great attention. A related and longtime unsolved problem is for any given non-negative integer k, is there an infinite family of k-tight optimal DLN? In this paper, two main results are obtained (1) for any k ≥ 0, the infinite families of k-tight optimal DLN can be constructed, where the number n(k,e,c) of their nodes is a polynomial of degree 2 in e with integral coefficients containing a parameter c. (2) for any k ≥ 0,an infinite family of singular k-tight optimal DLN can be constructed.     

On (<Emphasis Type="Italic">m</Emphasis>, <Emphasis Type="Italic">n</Emphasis>)-absorbing ideals of commutative rings

Let R be a commutative ring with 1 ≠ 0 and U(R) be the set of all unit elements of R. Let m, n be positive integers such that m > n. In this article, we study a generalization of n-absorbing ideals. A proper ideal I of R is called an (m, n)-absorbing ideal if whenever a ₁?a _m ∈I for a ₁,…, a _m ∈R?U(R), then there are n of the a _i ’s whose product is in I. We investigate the stability of (m, n)-absorbing ideals with respect to various ring theoretic constructions and study (m, n)-absorbing ideals in several commutative rings. For example, in a Bézout ring or a Boolean ring, an ideal is an (m, n)-absorbing ideal if and only if it is an n-absorbing ideal, and in an almost Dedekind domain every (m, n)-absorbing ideal is a product of at most m ? 1 maximal ideals.     

The best <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript> approximation of the Laplace operator by linear bounded operators in the classes of functions of two and three variables

Close two-sided estimates are obtained for the best approximation in the space L _p (? ^m ), m = 2 and 3, 1 ≤ p ≤ ∞, of the Laplace operator by linear bounded operators in the class of functions for which the second power of the Laplace operator belongs to the space L _p (? ^m ). We estimate the best constant in the corresponding Kolmogorov inequality and the error of the optimal recovery of values of the Laplace operator on functions from this class given with an error. We present an operator whose deviation from the Laplace operator is close to the best.     

On the Second Parameter of an (<Emphasis Type="Italic">m</Emphasis>, <Emphasis Type="Italic">p</Emphasis>)-Isometry

A bounded linear operator T on a Banach space X is called an (m, p)-isometry if it satisfies the equation \({\sum_{k=0}^{m}(-1)^{k} {m \choose k}\|T^{k}x\|^{p}=0}\) , for all \({x \in X}\) . In this paper we study the structure which underlies the second parameter of (m, p)-isometric operators. We concentrate on determining when an (m, p)-isometry is a (μ, q)-isometry for some pair (μ, q). We also extend the definition of (m, p)-isometry, to include p = ∞ and study basic properties of these (m, ∞)-isometries.     

Arithmetical rank of binomial ideals

In this paper, we investigate the arithmetical rank of a binomial ideal J. We provide lower bounds for the binomial arithmetical rank and the J-complete arithmetical rank of J. Special attention is paid to the case where J is the binomial edge ideal of a graph. We compute the arithmetical rank of such an ideal in various cases.     

Parametric AE-solution sets to the parametric linear systems with multiple right-hand sides and parametric matrix equation A(p)X = B(p)

In this paper, the parametric matrix equation A(p)X = B(p) whose elements are linear functions of uncertain parameters varying within intervals are considered. In this matrix equation A(p) and B(p) are known m-by-m and m-by-n matrices respectively, and X is the m-by-n unknown matrix. We discuss the so-called AE-solution sets for such systems and give some analytical characterizations for the AE-solution sets and a sufficient condition under which these solution sets are bounded. We then propose a modification of Krawczyk operator for parametric systems which causes reduction of the computational complexity of obtaining an outer estimation for the parametric united solution set, considerably. Then we give a generalization of the Bauer-Skeel and the Hansen-Bliek-Rohn bounds for enclosing the parametric united solution set which also enables us to reduce the computational complexity, significantly. Also some numerical approaches based on Gaussian elimination and Gauss-Seidel methods to find outer estimations for the parametric united solution set are given. Finally, some numerical experiments are given to illustrate the performance of the proposed methods.