Non-low<Subscript>2</Subscript>-ness and computable Lipschitz reducibility

In this paper, we prove that if a c.e. Turing degree d is non-low₂, then there are two left-c.e. reals β ₀, β ₁ in d, such that, if β ₀ is wtt-reducible to a left-c.e. real α, then β ₁ is not computable Lipschitz (cl-) reducible to α. As a corollary, d contains a left-c.e. real which is not cl-reducible to any complex (wtt-complete) left-c.e. real.     

On multiple ergodicity of affine cocycles over irrational rotations

Let \({T_\alpha }\) denote the rotation \({T_\alpha }x = x + \alpha \) (mod 1) by an irrational number α on the additive circle T = [0, 1). Let β ₁, …, β _d be d ≥ 1 parameters in [0, 1). One of the goals of this paper is to describe the ergodic properties of the cocycle (taking values in ? ^d+1) generated over \({T_\alpha }\) by the vectorial function Ψ _d+1(x):= (φ(x), φ(x+β ₁), …, φ(x+β _d )), with φ(x) = {x}?½. It was already proved in [LeMeNa03] that Ψ₂ is regular for α with bounded partial quotients. In the present paper we show that Ψ₂ is regular for any irrational α. For higher dimensions, we give sufficient conditions for regularity. While the case d = 2 remains unsolved, for d = 3 we provide examples of non-regular cocycles Ψ₄ for certain values of the parameters β ₁, β ₂, β ₃. We also show that the problem of regularity for the cocycle Ψ _d+1 reduces to the regularity of the cocycles of the form \({\Phi _d} = {({1_{[0,{\beta _j}]}} - {\beta _j})_{j = 1, \ldots ,d}}\) (taking values in ? ^d ). Therefore, a large part of the paper is devoted to the classification problems of step functions with values in ? ^d .     

CAT(0) groups and Coxeter groups whose boundaries are scrambled sets

In this paper, we study CAT(0) groups and Coxeter groups whose boundaries are scrambled sets. Suppose that a group G acts geometrically (i.e. properly and cocompactly by isometries) on a proper CAT(0) space X. (Such a group G is called a CAT(0) group.) Then the group G acts by homeomorphisms on the boundary ∂X of X and we can define a metric d_∂X on the boundary ∂X. The boundary ∂X is called a scrambled set if, for any α,β∈∂X with α≠β, (1) lim sup{d_∂X(gα,gβ)∣g∈G}>0 and (2) lim inf{d_∂X(gα,gβ)∣g∈G}=0. We investigate when boundaries of CAT(0) groups (and Coxeter groups) are scrambled sets.     

Dynamics of landslide model with time delay and periodic parameter perturbations

In present paper, we analyze the dynamics of a single-block model on an inclined slope with Dieterich–Ruina friction law under the variation of two new introduced parameters: time delay T_d and initial shear stress μ. It is assumed that this phenomenological model qualitatively simulates the motion along the infinite creeping slope. The introduction of time delay is proposed to mimic the memory effect of the sliding surface and it is generally considered as a function of history of sliding. On the other hand, periodic perturbation of initial shear stress emulates external triggering effect of long-distant earthquakes or some non-natural vibration source. The effects of variation of a single observed parameter, T_d or μ, as well as their co-action, are estimated for three different sliding regimes: β < 1, β = 1 and β > 1, where β stands for the ratio of long-term to short-term stress changes. The results of standard local bifurcation analysis indicate the onset of complex dynamics for very low values of time delay. On the other side, numerical approach confirms an additional complexity that was not observed by local analysis, due to the possible effect of global bifurcations. The most complex dynamics is detected for β < 1, with a complete Ruelle–Takens–Newhouse route to chaos under the variation of T_d, or the co-action of both parameters T_d and μ. These results correspond well with the previous experimental observations on clay and siltstone with low clay fraction. In the same regime, the perturbation of only a single parameter, μ, renders the oscillatory motion of the block. Within the velocity-independent regime, β = 1, the inclusion and variation of T_d generates a transition to equilibrium state, whereas the small oscillations of μ induce oscillatory motion with decreasing amplitude. The co-action of both parameters, in the same regime, causes the decrease of block’s velocity. As for β > 1, highly-frequent, limit-amplitude oscillations of initial stress give rise to oscillatory motion. Also for β > 1, in case of perturbing only the initial shear stress, with smaller amplitude, velocity of the block changes exponentially fast. If the time delay is introduced, besides the stress perturbation, within the same regime, the co-action of T_d (T_d < 0.1) and small oscillations of μ induce the onset of deterministic chaos.     

Partial difference sets

A (υ,k,α,β)-partial difference set in a finite group G of order υ is a subset D of G with k distinct elements such that expressions d_nd^?1₂ for d₁ and d₂ in D, represent each non-identity element not contained in D exactly α times and each non-identity element contained in D exactly α+β times. Such a set is closely related to association schemes of PBIB designs with two associate classes.     

Uniformity of a certain systems of functions of many-valued logic

For any finite system A of functions of many-valued logic taking values in the set {0,1} such that a projection of A generates the class of all monotone boolean functions, it is proved that there exists constants c and d such that for an arbitrary function f ε [A] the depth D(f) and the complexity L(f) of f in the class of formulas over A satisfy the relation D(f) ≤ clog₂ L(f) + d.     

A linear algorithm for nonhomogeneous spectra of numbers

Given a sequence of integers [a_i]_i=1ⁿ, an O(n) iterative algorithm is presented which decides whether there exist real numbers α and β such that a_i = [iα + β] (1 ? i ? n). In fact, the linear algorithm computes the partial quotients of the continued fraction expansions of $\text{d}$ and $\text{d}$ such that $\text{d < α <}\text{d}$ if and only if a_i = [iα + β] (1 ? i ? n) for suitable β = β(α).     

On Cohen braids

For a general connected surface M and an arbitrary braid α from the surface braid group B _n?1(M), we study the system of equations d ₁ β = … = d _n β = α, where the operation d _i is the removal of the ith strand. We prove that for M ≠ S ² and M ≠ ?P², this system of equations has a solution β ∈ B _n (M) if and only if d ₁ α = … = d _n?1 α. We call the set of braids satisfying the last system of equations Cohen braids. We study Cohen braids and prove that they form a subgroup. We also construct a set of generators for the group of Cohen braids. In the cases of the sphere and the projective plane we give some examples for a small number of strands.     

On predicate provability logics and binumerations of fragments of Peano arithmetic

Solovay proved (Israel J Math 25(3–4):287–304, 1976) that the propositional provability logic of any ∑₂-sound recursively enumerable extension of PA is characterized by the propositional modal logic GL. By contrast, Montagna proved in (Notre Dame J Form Log 25(2):179–189, 1984) that predicate provability logics of Peano arithmetic and Bernays–Gödel set theory are different. Moreover, Artemov proved in (Doklady Akademii Nauk SSSR 290(6):1289–1292, 1986) that the predicate provability logic of a theory essentially depends on the choice of a binumeration of the theory which is used to construct the provability predicate. In this paper, we compare predicate provability logics of I∑ _n ’s. For a binumeration α(x) of a recursive theory T, let PL _α(T) be the predicate provability logic of T defined by α(x). We prove that for any natural numbers i, j such that 0 < i < j, there exists a ∑₁ binumeration α(x) of some recursive axiomatization of I∑ _i such that ${{\sf PL}_\alpha({\rm I \Sigma}_i) \nsupseteq \bigcap_{\beta(x)}{\sf PL}_\beta({\rm I \Sigma}_j)}$ PL α ( I Σ i ) ? ? β ( x ) PL β ( I Σ j ) and ${{\sf PL}_\alpha({\rm I \Sigma}_i) \nsubseteq \bigcup_{\beta(x)}{\sf PL}_\beta({\rm I \Sigma}_j)}$ PL α ( I Σ i ) ? ? β ( x ) PL β ( I Σ j ) , where β(x) ranges over all ∑₁ binumerations of recursive axiomatizations of I∑ _j .     

Superlocalization of waves and electrons and hopping conductivity on classical and superconductive fractals

We have found an unexpected paradoxical situation in the percolation transition: the superconductive behavior below and above the threshold. We have found also the two different density of states d_s=4/3 and d_v=1.05 and the inverse localization lengths for fractons with the scalar and vector interactions, respectively. In this concept the wave functions of electrons or waves on an incipient percolation cluster and fractal dilute structure exhibit superlocalization behavior of the form ψ(r)∝exp[−r^d_φ] with values of d_φ1=1.73 and d_φ2=2.4 for the former and the latter. Applications of these results for thermally activated hopping conductivity σ(t)∝exp[−(T₀/T)^β] between impurities on a random fractal structure give the values of β=2/5 for the scalar and β=1/2 (Mott's law) for the vector interactions, respectively. Band states are localized in classical and superlocalized in superconductive percolations.     

Joint Consistency of Fuzzy Theories

This paper is a contribution to the development of fuzzy logic in narrow sense with evaluated syntax and connectives interpreted in Łukasiewicz algebra. The main results concern model theory of fuzzy logic (various kinds of submodels, chains of models) and generalization of the Craig‐Robinson's theorem on joint consistency of fuzzy theories as well as Craig's interpolation theorem.     

Asymptotic Properties of Orthogonal Polynomials with Respect to a Non-discrete Jacobi-Sobolev Inner Product

Let {Q _n ^(α,β) (x)} _n=0 ^∞ denote the sequence of polynomials orthogonal with respect to the non-discrete Sobolev inner product

$\langle f,g\rangle=\int_{-1}^{1}f(x)g(x)d\mu_{\alpha,\beta}(x)+\lambda\int_{-1}^{1}f'(x)g'(x)d\nu_{\alpha,\beta}(x)$

where λ>0 and d μ _α,β(x)=(x?a)(1?x)^α?1(1+x)^β?1 dx, d ν _α,β(x)=(1?x) ^α (1+x) ^β dx with aα,β>0. Their inner strong asymptotics on (?1,1), a Mehler-Heine type formula as well as some estimates of the Sobolev norms of Q _n ^(α,β) are obtained.

     

On the Complexity of Multivalued Logic Functions over Some Infinite Basis

Under study is the complexity of the realization of k-valued logic functions (k ≥ 3) by logic circuits in the infinite basis consisting of the Post negation (i.e., the function (x + 1) mod k) and all monotone functions. The complexity of the circuit is the total number of elements of this circuit. For an arbitrary function f, we find the lower and upper bounds of complexity, which differ from one another at most by 1 and have the form 3 log₃(d(f)+ 1)+O(1), where d(f) is the maximal number of the decrease of the value of f taken over all increasing chains of tuples of values of the variables. We find the exact value of the corresponding Shannon function which characterizes the complexity of the most complex function of a given number of variables.     

Explicit Cost Bounds of Algorithms for Multivariate Tensor Product Problems

We study multivariate tenser product problems in the worst case and average case settings. They are defined on functions of d variables. For arbitrary d, we provide explicit upper bounds on the costs of algorithms which compute an ϵ-approximation to the solution. The cost bounds are of the form (c(d) + 2)β₁(β₂ + β₃(ln 1/ϵ)/(d − 1))^{β₄(d − 1)}(1/ϵ)^β₅. Here c(d) is the cost of one function evaluation (or one linear functional evaluation), and β_i′s do not depend on d; they are determined by the properties of the problem for d = 1. For certain tensor product problems, these cost bounds do not exceed c(d)Kϵ^−p for some numbers K and p, both independent of d. However, the exponents p which we obtain are too large. We apply these general estimates to certain integration and approximation problems in the worst and average case settings. We also obtain an upper bound, which is independent of d, for the number, n(ϵ, d), of points for which discrepancy (with unequal weights) is at most ϵ, n(ϵ, d) ≤ 7.26ϵ^−2.454, ∀d, ϵ ≤ 1.     

Tautologies with a unique craig interpolant,uniform vs. nonuniform complexity

If S?{0,1};^* and S′ = {0,1}^*\sbS are both recognized within a certain nondeterministic time bound T then, in not much more time, one can write down tautologies A_n→A′_n with unique interpolants I_n that define S∩{0,1}ⁿ; hence, if one can rapidly find unique interpolants, then one can recognize S within deterministic time T^p for some fixed p\s>0. In general, complexity measures for the problem of finding unique interpolants in sentential logic yield new relations between circuit depth and nondeterministic Turing time, as well as between proof length and the complexity of decision procedures of logical theories.     

Characterizing Belnap's Logic via De Morgan's Laws

The aim of this paper is technically to study Belnap's four-valued sentential logic (see [2]). First, we obtain a Gentzen-style axiomatization of this logic that contains no structural rules while all they are still admissible in the Gentzen system what is proved with using some algebraic tools. Further, the mentioned logic is proved to be the least closure operator on the set of {Λ, V, ?}-formulas satisfying Tarski's conditions for classical conjunction and disjunction together with De Morgan's laws for negation. It is also proved that Belnap's logic is the only sentential logic satisfying the above-mentioned conditions together with Anderson-Belnap's Variable-Sharing Property. Finally, we obtain a finite Hilbert-style axiomatization of this logic. As a consequence, we obtain a finite Hilbert-style axiomatization of Priest's logic of paradox (see [12]).     

Edge-disjoint spanners in tori

A spanning subgraph S=(V,E^′) of a connected graph G=(V,E) is an (x+c)-spanner if for any pair of vertices u and v, d_S(u,v)≤d_G(u,v)+c where d_G and d_S are the usual distance functions in G and S, respectively. The parameter c is called the delay of the spanner. We study edge-disjoint spanners in graphs in multi-dimensional tori. We show that each two-dimensional torus has a set of two edge-disjoint spanners of delay approximately the size of the smaller dimension. Moreover, we show that this delay is close to the best possible. In three-dimensional tori, we find a set of three edge-disjoint spanners with delay approximately the sum of the sizes of the two smaller dimensions when all dimensions are of even size. Surprisingly, we also find a set of two edge-disjoint spanners in three-dimensional tori of constant delay. In d-dimensional tori, we show that for any k≤d/5, there is a set of k edge-disjoint spanners with delay depending only on k and the size of the smaller k dimensions.     

A note on tight extensive game forms

Associated with each extensive game form are the α- and β-effectivity functions,E _α andE _β. These functions characterize the effective capabilities which coalitions command under pessimistic and optimistic cooperative behavior respectively. A game form is said to be tight whenE _α ≡E _β, in which case pessimistic, optimistic, and intermediate types of behavior all support the same effective power. Dalkey's condition for Nash consistency, essentially perfect information, is found to be a necessary and sufficient condition for a game form to be tight.     

Conjugated trees with minimum general Randi? index

The general Randi? index R_α(G) is the sum of the weights (d_G(u)d_G(v))^α over all edges uv of a (molecular) graph G, where α is a real number and d_G(u) is the degree of the vertex u of G. In this paper, for any real number α≤−1, the minimum general Randi? index R_α(T) among all the conjugated trees (trees with a Kekulé structure) is determined and the corresponding extremal conjugated trees are characterized. These trees are also extremal over all the conjugated chemical trees.     

An improved characterization of normal sets and some counter-examples

We strengthen G. Rauzy’s characterization of normal sets by observing that the so-called elementary sets are precisely the F_σδ sets. This answers in the affirmative Rauzy’s open question: Are finite unions of normal sets necessarily normal? We also generalize the notion and characterization of normal sets from subsets of ? to subsets of ? ^d . This allows us to answer a question of E. Lesigne and M. Wierdl with the following construction: There exist two sequences of real numbersU=(u _n ) _nε?,V=(v _n ) _nε? such thatαU+βV=(αu _n +βv _n ) _nε? is uniformly distributed mod 1 if and only if exactly one of the real numbers α, β vanishes. Additionally, we provide the ‘ultimate’ counter-example (stronger than that of H. G. Meijer and R. Sattler) to a conjecture of S. Uchiyama by constructing a sequence of integersU which is u.d. in ? (i.e. u.d. modk for allk ε ?), but such that for all realα, αU is not u.d. mod 1.