Complexity of some natural problems on the class of computable I-algebras

We study computable Boolean algebras with distinguished ideals (I-algebras for short). We prove that the isomorphism problem for computable I-algebras is Σ ₁ ¹ -complete and show that the computable isomorphism problem and the computable categoricity problem for computable I-algebras are Σ ₃ ⁰ -complete.     

On the theta number of powers of cycle graphs

We give a closed formula for Lovász’s theta number of the powers of cycle graphs C _k ^d?1 and of their complements, the circular complete graphs K _k/d . As a consequence, we establish that the circular chromatic number of a circular perfect graph is computable in polynomial time. We also derive an asymptotic estimate for the theta number of C _k ^d .     

On the Dirichlet–Riquier problem for biharmonic equations

In the paper, it is proved that the distribution of a measurable polynomial on an infinite-dimensional space with log-concave measure is absolutely continuous if the polynomial is not equal to a constant almost everywhere. A similar assertion is proved for analytic functions and for some other classes of functions. Properties of distributions of norms of polynomial mappings are also studied. For the space of measurable polynomial mappings of a chosen degree, it is proved that the L ¹-norm with respect to a log-concave measure is equivalent to the L ¹-norm with respect to the restriction of the measure to an arbitrarily chosen set of positive measure.     

Index sets of decidable models

We study the index sets of the class of d-decidable structures and of the class of d-decidable countably categorical structures, where d is an arbitrary arithmetical Turing degree. It is proved that the first of them is m-complete ∑ ₃ ^{0, d} , and the second is m-complete ∑ ₃ ^{0, d} \∑ ₃ ^{0, d} in the universal computable numbering of computable structures for the language with one binary predicate.     

Heat Kernels, Smoothness Estimates, and Exponential Decay

In this article, we characterize functions whose Fourier transforms have exponential decay. We characterize such functions by showing that they satisfy a family of estimates that we call quantitative smoothness estimates (QSE). Using the QSE, we establish Gaussian decay in the “bad direction” for the □ _b -heat kernel on polynomial models in ? ⁿ⁺¹. On the transform side, the problem becomes establishing QSE on a heat kernel associated to the weighted $\bar{\partial}$ -operator on L ²(?). The bounds are established with Duhamel’s formula and careful estimation. In ?², we can prove both on and off-diagonal decay for the □ _b -heat kernel on polynomial models.     

Estimation of the algorithmic complexity of classes of computable models

We estimate the algorithmic complexity of the index set of some natural classes of computable models: finite computable models (Σ ₂ ⁰ -complete), computable models with ω-categorical theories (Δ _ω ⁰ -complex Π _ω+2 ⁰ -set), prime models (Δ _ω ⁰ -complex Π _ω+2 ⁰ -set), models with ω ₁-categorical theories (Δ _ω ⁰ -complex Σ _ω+1 ⁰ -set. We obtain a universal lower bound for the model-theoretic properties preserved by Marker’s extensions (Δ _ω ⁰ .     

Decay parameter and related properties of n-type branching processes

We consider decay properties including the decay parameter, invariant measures, invariant vectors, and quasistationary distributions for n-type Markov branching processes on the basis of the 1-type Markov branching processes and 2-type Markov branching processes. Investigating such behavior is crucial in realizing life period of branching models. In this paper, some important properties of the generating functions for n-type Markov branching q-matrix are firstly investigated in detail. The exact value of the decay parameter λC of such model is given for the communicating class C = Zn+ \ 0. It is shown that this λC can be directly obtained from the generating functions of the corresponding q-matrix. Moreover, the λC -invariant measures/vectors and quasi-distributions of such processes are deeply considered. λC -invariant measures and quasi-stationary distributions for the process on C are presented.     

The algebraic structure of the isomorphic types of tally,polynomial time computable sets

 We investigate the polynomial time isomorphic type structure of (the class of tally, polynomial time computable sets). We partition P _T into six parts: D ⁻, D^ ⁻ , C, S, F, F^, and study their p-isomorphic properties separately. The structures of , , and are obvious, where F, F^, and C are the class of tally finite sets, the class of tally co-finite sets, and the class of tally bi-dense sets respectively. The following results for the structures of and will be proved, where D^ is the class of tally, co-dense, polynomial time computable sets and S is the class of tally, scatted (i.e., neither dense nor co-dense), polynomial time computable sets. 1. is a countable distributive lattice with the greatest element. 2. Infinitely many intervals in can be distinguished by first order formulas. 3. There exist infinitely many nontrivial automorphisms for . 4. is not distributive, but any interval in is a countable distributive lattice. RID="ID=" <E5>Mathematics Subject Classification (2000):</E5> 03D15, 03D25, 03D30, 03D35, 06A06, 06B20 RID="ID=" <E5>Key words or phrases:</E5> Computational complexity &ndash; Polynomial time &ndash; Degree structure &ndash; Lattice &ndash; Isomorphism RID="ID=" Part of this work was done when the author was a PhD student at the University of Heidelberg under the direction of Professor Ambos-Spies. Received: 23 July 1999 / Published online: 27 March 2002 RID=" ID=" <E5>Mathematics Subject Classification (2000):</E5> 03D15, 03D25, 03D30, 03D35, 06A06, 06B20 RID=" ID=" <E5>Key words or phrases:</E5> Computational complexity &ndash; Polynomial time &ndash; Degree structure &ndash; Lattice &ndash; Isomorphism RID=" ID=" Part of this work was done when the author was a PhD student at the University of Heidelberg under the direction of Professor Ambos-Spies.     

Hyper-bent functions and cyclic codes

Bent functions are those Boolean functions whose Hamming distance to the Reed-Muller code of order 1 equal 2^n-1-2^n/2-1 (where the number n of variables is even). These combinatorial objects, with fascinating properties, are rare. Few constructions are known, and it is difficult to know whether the bent functions they produce are peculiar or not, since no way of generating at random bent functions on 8 variables or more is known.The class of bent functions contains a subclass of functions whose properties are still stronger and whose elements are still rarer. Youssef and Gong have proved the existence of such hyper-bent functions, for every even n. We prove that the hyper-bent functions they exhibit are exactly those elements of the well-known PS_ap class, introduced by Dillon, up to the linear transformations x?δx, . Hyper-bent functions seem still more difficult to generate at random than bent functions; however, by showing that they all can be obtained from some codewords of an extended cyclic code H_n with small dimension, we can enumerate them for up to 10 variables. We study the non-zeroes of H_n and we deduce that the algebraic degree of hyper-bent functions is n/2. We also prove that the functions of class PS_ap are some codewords of weight 2^n-1-2^n/2-1 of a subcode of H_n and we deduce that for some n, depending on the factorization of 2ⁿ-1, the only hyper-bent functions on n variables are the elements of the class , obtained from PS_ap by composing the functions by the transformations x?δx, δ≠0, and by adding constant functions. We prove that non- hyper-bent functions exist for n=4, but it is not clear whether they exist for greater n. We also construct potentially new bent functions for n=12.     

Isomorphisms,definable relations,and Scott families for integral domains and commutative semigroups

In the present article, we prove the following four assertions: (1) For every computable successor ordinal α, there exists a Δ _α ⁰ -categorical integral domain (commutative semigroup) which is not relatively Δ _α ⁰ -categorical (i.e., no formally Σ _α ⁰ Scott family exists for such a structure). (2) For every computable successor ordinal α, there exists an intrinsically Σ _α ⁰ -relation on the universe of a computable integral domain (commutative semigroup) which is not a relatively intrinsically Σ _α ⁰ -relation. (3) For every computable successor ordinal α and finite n, there exists an integral domain (commutative semigroup) whose Δ _α ⁰ -dimension is equal to n. (4) For every computable successor ordinal α, there exists an integral domain (commutative semigroup) with presentations only in the degrees of sets X such that Δ _α ⁰ (X) is not Δ _α ⁰ . In particular, for every finite n, there exists an integral domain (commutative semigroup) with presentations only in the degrees that are not n-low.     

Complexities of Winning Strategies in Diophantine Games

This paper considers the computational complexity of computing winning strategies in diophantine games, where two players take turns choosing natural numbers x₁, x₂, x₃, . . . , x_n and the win condition is a polynomial equation in the variables x₁, x₂, . . . , x_n. A diophantine game G₄ of length 4 is constructed with the propertythat neither player has a polynomial time computable winning strategy. Also a diophantine game G₆ of length 6 is constructed with the property that one of the players has a polynomial time computable winning strategy in G₆ iff P = NP. Finally a diophantine game N_b of length 6 is constructed such that one of the players has a polynomial time computable winning strategy in it iff co-NP = NP.     

Shephard–Todd–Chevalley Theorem for Skew Polynomial Rings

We prove the following generalization of the classical Shephard–Todd–Chevalley Theorem. Let G be a finite group of graded algebra automorphisms of a skew polynomial ring \(A:=k_{p_{ij}}[x_1,\cdots,x_n]\). Then the fixed subring A ^G has finite global dimension if and only if G is generated by quasi-reflections. In this case the fixed subring A ^G is isomorphic to a skew polynomial ring with possibly different p _ij ’s. A version of the theorem is proved also for abelian groups acting on general quantum polynomial rings.     

Normal number constructions for Cantor series with slowly growing bases

Let Q = (q_n)_n=1^∞ be a sequence of bases with q_i ≥ 2. In the case when the q_i are slowly growing and satisfy some additional weak conditions, we provide a construction of a number whose Q-Cantor series expansion is both Q-normal and Q-distribution normal. Moreover, this construction will result in a computable number provided we have some additional conditions on the computability of Q, and from this construction we can provide computable constructions of numbers with atypical normality properties.     

Polynomial approximation inL p(S) forp>0

For a simple polytopeS inR ^d andp>0 we show that the best polynomial approximationE _n(f)_p≡E_n(f)L_p(S) satisfies $$E_n \left( f \right)_p \leqslant C\omega _S^r \left( {f,\frac{1}{n}} \right)p,$$ where ω _S ^r is a measure of smoothness off. This result is the best possible in the sense that a weak-type converse inequality is shown and a realization of ω _S ^r (f,t)_p via polynomial approximation is proved.     

On the reducibility of some composite polynomials over finite fields

Let g(x)?=?x ⁿ ?+?a _n-1 x ^n-1?+?. . .?+?a ₀ be an irreducible polynomial over ${\mathbb{F}_q}$ . Varshamov proved that for a?=?1 the composite polynomial g(x ^p ?ax?b) is irreducible over ${\mathbb{F}_q}$ if and only if ${{\rm Tr}_{\mathbb{F}_q/\mathbb{F}_p}(nb-a_{n-1})\neq 0}$ . In this paper, we explicitly determine the factorization of the composite polynomial for the case a?=?1 and ${{\rm Tr}_{\mathbb{F}_q/\mathbb{F}_p}(nb-a_{n-1})= 0}$ and for the case a?≠ 0, 1. A recursive construction of irreducible polynomials basing on this composition and a construction with the form ${g(x^{r^kp}-x^{r^k})}$ are also presented. Moreover, Cohen’s method of composing irreducible polynomials and linear fractions are considered, and we show a large number of irreducible polynomials can be obtained from a given irreducible polynomial of degree n provided that gcd(n, q ³ ? q)?=?1.     

Exponential laws for ultrametric partially differentiable functions and applications

We establish exponential laws for certain spaces of differentiable functions over a valued field $\mathbb{K}$ . For example, we show that $$C^{(\alpha ,\beta )} \left( {U \times V,E} \right) \cong C^\alpha \left( {U,C^\beta \left( {V,E} \right)} \right)$$ if α ∈ (?₀ ∪ {∞}) ⁿ , β ∈ (?₀ ∪ {∞}) ^m , $U \subseteq \mathbb{K}^n$ and $V \subseteq \mathbb{K}^m$ are open (or suitable more general) subsets, and E is a topological vector space. As a first application, we study the density of locally polynomial functions in spaces of partially differentiable functions over an ultrametric field (thus solving an open problem by Enno Nagel), and also global approximations by polynomial functions. As a second application, we obtain a new proof for the characterization of C ^r -functions on (? _p ) ⁿ in terms of the decay of their Mahler expansions. In both applications, the exponential laws enable simple inductive proofs via a reduction to the one-dimensional, vector-valued case.