Divergence bounded computable real numbers

A real x$x$ is called h$h$-bounded computable  , for some function h:N→N$h:\mathbb{N}\to \mathbb{N}$, if there is a computable sequence (_xs)$(x_s)$ of rational numbers which converges to x$x$ such that, for any n∈N$n\in \mathbb{N}$, at most h(n)$h(n)$ non-overlapping pairs of its members are separated by a distance larger than 2^-n$2^{-n}$. In this paper we discuss properties of h$h$-bounded computable reals for various functions h$h$. We will show a simple sufficient condition for a class of functions h$h$ such that the corresponding h$h$-bounded computable reals form an algebraic field. A hierarchy theorem for h$h$-bounded computable reals is also shown. Besides we compare semi-computability and weak computability with the h$h$-bounded computability for special functions h$h$.     

Rotation-minimizing osculating frames

An orthonormal frame (_f1,_f2,_f3)$({\mathbf{f}}_1,{\mathbf{f}}_2,{\mathbf{f}}_3)$ is rotation-minimizing   with respect to _fi${\mathbf{f}}_i$ if its angular velocity ω   satisfies ω⋅_fi≡0$\mathit{\omega }\cdot {\mathbf{f}}_i\equiv 0$ — or, equivalently, the derivatives of _fj${\mathbf{f}}_j$ and _fk${\mathbf{f}}_k$ are both parallel to _fi${\mathbf{f}}_i$. The Frenet frame (t,p,b)$(\mathbf{t},\mathbf{p},\mathbf{b})$ along a space curve is rotation-minimizing with respect to the principal normal p, and in recent years adapted frames that are rotation-minimizing with respect to the tangent t have attracted much interest. This study is concerned with rotation-minimizing osculating   frames (f,g,b)$(\mathbf{f},\mathbf{g},\mathbf{b})$ incorporating the binormal b, and osculating-plane vectors f, g that have no rotation about b. These frame vectors may be defined through a rotation of t, p by an angle equal to minus the integral of curvature with respect to arc length. In aeronautical terms, the rotation-minimizing osculating frame (RMOF) specifies yaw-free rigid-body motion along a curved path. For polynomial space curves possessing rational Frenet frames, the existence of rational RMOFs is investigated, and it is found that they must be of degree 7 at least. The RMOF is also employed to construct a novel type of ruled surface, with the property that its tangent planes coincide with the osculating planes of a given space curve, and its rulings exhibit the least possible rate of rotation consistent with this constraint.     

Compatibility of unrooted phylogenetic trees is FPT

A collection of _T1,_T2,…,_Tk$T_1,T_2,\dots ,T_k$ of unrooted, leaf labelled (phylogenetic) trees, all with different leaf sets, is said to be compatible   if there exists a tree T$T$ such that each tree _Ti$T_i$ can be obtained from T$T$ by deleting leaves and contracting edges. Determining compatibility is NP-hard, and the fastest algorithm to date has worst case complexity of around Ω(n^k)$\mathrm{\Omega }(n^k)$ time, n$n$ being the number of leaves. Here, we present an O(nf(k))$\mathrm{O}(\mathit{nf}(k))$ algorithm, proving that compatibility of unrooted phylogenetic trees is fixed parameter tractable   (FPT) with respect to the number k$k$ of trees.     

Modular Las Vegas algorithms for polynomial absolute factorization

Let f(X,Y)∈Z[X,Y]$f(X,Y)\in \mathbb{Z}[X,Y]$ be an irreducible polynomial over Q$\mathbb{Q}$. We give a Las Vegas absolute irreducibility test based on a property of the Newton polytope of f$f$, or more precisely, of f$f$ modulo some prime integer p$p$. The same idea of choosing a p$p$ satisfying some prescribed properties together with LLL$LLL$ is used to provide a new strategy for absolute factorization of f(X,Y)$f(X,Y)$. We present our approach in the bivariate case but the techniques extend to the multivariate case. Maple computations show that it is efficient and promising as we are able to construct the algebraic extension containing one absolute factor of a polynomial of degree up to 400.     

Algorithms for a class of infinite permutation groups

Motivated by the famous 3n+1$3n+1$ conjecture, we call a mapping from Z$\mathbb{Z}$ to Z$\mathbb{Z}$residue-class-wise affine   if there is a positive integer m$m$ such that it is affine on residue classes (mod m$m$). This article describes a collection of algorithms and methods for computation in permutation groups and monoids formed by residue-class-wise affine mappings.     

An augmented weighted Tchebycheff method with adaptively chosen parameters for discrete bicriteria optimization problems

The augmented weighted Tchebycheff norm was introduced in the context of multicriteria optimization by Steuer and Choo [21] in order to avoid the generation of weakly nondominated points. It augments a weighted _l∞-norm$l_{\infty }\mathrm{-}\mathrm{norm}$ with an l₁-term, multiplied by a “small” parameter ρ>0$\rho >0$. However, the appropriate selection of the parameter ρ$\rho$ remained an open question: A too small value of ρ$\rho$ may cause numerical difficulties, while a too large value of ρ$\rho$ may lead to the oversight of some nondominated points.     

Affine-evasive sets modulo a prime

In this work, we describe a simple and efficient construction of a large subset S   of _Fp${\mathbb{F}}_p$, where p   is a prime, such that the set A(S)$A(S)$ for any non-identity affine map A   over _Fp${\mathbb{F}}_p$ has small intersection with S.     

On asymptotic extrapolation

Consider a power series f∈R[[z]]$f\in \mathbb{R}\left[\left[z\right]\right]$, which is obtained by a precise mathematical construction. For instance, f$f$ might be the solution to some differential or functional initial value problem or the diagonal of the solution to a partial differential equation. In cases when no suitable method is available beforehand for determining the asymptotics of the coefficients _fn$f_n$, but when many such coefficients can be computed with high accuracy, it would be useful if a plausible asymptotic expansion for _fn$f_n$ could be guessed automatically.     

Origami fold as algebraic graph rewriting

We formalize paper fold (origami) by graph rewriting. Origami construction is abstractly described by a rewriting system (O,?)$(\mathbb{O},?)$, where O$\mathbb{O}$ is the set of abstract origamis and ?$?$ is a binary relation on O$\mathbb{O}$, that models fold  . An abstract origami is a structure (Π,∽,?)$(\Pi ,\backsim ,?)$, where Π$\Pi$ is a set of faces constituting an origami, and ∽$\backsim$ and ?$?$ are binary relations on Π$\Pi$, each representing adjacency and superposition relations between the faces.     

A quantitative Pólya’s Theorem with zeros

Let R[X]:=R[_X1,…,_Xn]$\mathbb{R}\left[X\right]:=\mathbb{R}[X_1,\dots ,X_n]$. Pólya’s Theorem says that if a form (homogeneous polynomial) p∈R[X]$p\in \mathbb{R}\left[X\right]$ is positive on the standard n$n$-simplex _Δn${\Delta }_n$, then for sufficiently large N$N$ all the coefficients of (_X1+?+_Xn)^Np${(X_1+?+X_n)}^{N}p$ are positive. The work in this paper is part of an ongoing project aiming to explain when Pólya’s Theorem holds for forms if the condition “positive on _Δn${\Delta }_n$” is relaxed to “nonnegative on _Δn${\Delta }_n$”, and to give bounds on N$N$. Schweighofer gave a condition which implies the conclusion of Pólya’s Theorem for polynomials f∈R[X]$f\in \mathbb{R}\left[X\right]$. We give a quantitative version of this result and use it to settle the case where a form p∈R[X]$p\in \mathbb{R}\left[X\right]$ is positive on _Δn${\Delta }_n$, apart from possibly having zeros at the corners of the simplex.     

Bounding the radii of balls meeting every connected component of semi-algebraic sets

We prove an explicit bound on the radius of a ball centered at the origin which is guaranteed to contain all bounded connected components of a semi-algebraic set S⊂R^k$S\subset {\mathbb{R}}^k$ defined by a weak sign condition involving s$s$ polynomials in Z[_X1,…,_Xk]$\mathbb{Z}[X_1,\dots ,X_k]$ having degrees at most d$d$, and whose coefficients have bitsizes at most τ$\tau$. Our bound is an explicit function of s,d,k$s,d,k$ and τ$\tau$, and does not contain any undetermined constants. We also prove a similar bound on the radius of a ball guaranteed to intersect every connected component of S$S$ (including the unbounded components). While asymptotic bounds of the form 2^τdO(k)$2^{\tau d^{O\left(k\right)}}$ on these quantities were known before, some applications require bounds which are explicit and which hold for all values of s,d,k$s,d,k$ and τ$\tau$. The bounds proved in this paper are of this nature.