Rational two-parameter families of spheres and rational offset surfaces

The present paper investigates two-parameter families of spheres in R³${\mathbb{R}}^3$ and their corresponding two-dimensional surfaces Φ$\Phi$ in R⁴${\mathbb{R}}^4$. Considering a rational surface Φ$\Phi$ in R⁴${\mathbb{R}}^4$, the envelope surface Ψ$\Psi$ of the corresponding family of spheres in R³${\mathbb{R}}^3$ is typically non-rational. Using a classical sphere-geometric approach, we prove that the envelope surface Ψ$\Psi$ and its offset surfaces admit rational parameterizations if and only if Φ$\Phi$ is a rational sub-variety of a rational isotropic hyper-surface in R⁴${\mathbb{R}}^4$. The close relation between the envelope surfaces Ψ$\Psi$ and rational offset surfaces in R³${\mathbb{R}}^3$ is elaborated in detail. This connection leads to explicit rational parameterizations for all rational surfaces Φ$\Phi$ in R⁴${\mathbb{R}}^4$ whose corresponding two-parameter families of spheres possess envelope surfaces admitting rational parameterizations. Finally we discuss several classes of surfaces sharing this property.     

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$.     

On the minimum of a positive polynomial over the standard simplex

We present a new positive lower bound for the minimum value taken by a polynomial P$P$ with integer coefficients in k$k$ variables over the standard simplex of R^k${\mathbb{R}}^k$, assuming that P$P$ is positive on the simplex. This bound depends only on the number of variables k$k$, the degree d$d$ and the bitsize τ$\tau$ of the coefficients of P$P$ and improves all the previous bounds for arbitrary polynomials which are positive over the simplex.     

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.     

Cubical local partial orders on cubically subdivided spaces—Existence and construction

The geometric models of higher dimensional automata (HDA) and Dijkstra's PV-model are cubically subdivided topological spaces with a local partial order. If a cubicalization of a topological space is free of immersed cubic Möbius bands, then there are consistent choices of direction in all cubes, such that any n  -cube in the cubic subdivision is dihomeomorphic to [0,1]ⁿ$[0,1{]}^n$ with the induced partial order from Rⁿ${\mathbb{R}}^n$. After subdivision once, any cubicalized space has a cubical local partial order. In particular, all triangularized spaces have a cubical local partial order. This implies in particular that the underlying geometry of an HDA may be quite complicated.     

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.     

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.     

Three concepts of decidability for general subsets of uncountable spaces

There is no uniquely standard concept of an effectively decidable set of real numbers or real n  -tuples. Here we consider three notions: decidability up to measure zero [M.W. Parker, Undecidability in Rⁿ${\mathsf{R}}^n$: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382], which we abbreviate d.m.z.; recursive approximability [or r.a.; K.-I. Ko, Complexity Theory of Real Functions, Birkhäuser, Boston, 1991]; and decidability ignoring boundaries [d.i.b.; W.C. Myrvold, The decision problem for entanglement, in: R.S. Cohen et al. (Eds.), Potentiality, Entanglement, and Passion-at-a-Distance: Quantum Mechanical Studies fo Abner Shimony, Vol. 2, Kluwer Academic Publishers, Great Britain, 1997, pp. 177–190]. Unlike some others in the literature, these notions apply not only to certain nice sets, but to general sets in Rⁿ${\mathsf{R}}^n$ and other appropriate spaces. We consider some motivations for these concepts and the logical relations between them. It has been argued that d.m.z. is especially appropriate for physical applications, and on Rⁿ${\mathsf{R}}^n$ with the standard measure, it is strictly stronger than r.a. [M.W. Parker, Undecidability in Rⁿ${\mathsf{R}}^n$: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382]. Here we show that this is the only implication that holds among our three decidabilities in that setting. Under arbitrary measures, even this implication fails. Yet for intervals of non-zero length, and more generally, convex sets of non-zero measure, the three concepts are equivalent.     

Column Subset Selection Problem is UG-hard

We address two problems related to selecting an optimal subset of columns from a matrix. In one of these problems, we are given a matrix A∈R^m×n$A\in {\mathbb{R}}^{m\times n}$ and a positive integer k, and we want to select a sub-matrix C of k   columns to minimize _{‖A−ΠCA‖F}${\Vert A-{\Pi }_{C}A\Vert }_F$, where _ΠC=CC⁺${\Pi }_C=C{C}^{+}$ denotes the matrix of projection onto the space spanned by C  . In the other problem, we are given A∈R^m×n$A\in {\mathbb{R}}^{m\times n}$, positive integers c and r, and we want to select sub-matrices C and R of c columns and r rows of A  , respectively, to minimize _{‖A−CUR‖F}${\Vert A-CUR\Vert }_F$, where U∈R^c×r$U\in {\mathbb{R}}^{c\times r}$ is the pseudo-inverse of the intersection between C and R. Although there is a plethora of algorithmic results, the complexity of these problems has not been investigated thus far. We show that these two problems are NP-hard assuming UGC.     

Computational topology for isotopic surface reconstruction

New computational topology techniques are presented for surface reconstruction of 2-manifolds with boundary, while rigorous proofs have previously been limited to surfaces without boundary. This is done by an intermediate construction of the envelope   (as defined herein) of the original surface. For any compact C²$C^2$-manifold M$M$ embedded in R³${\mathbf{R}}^3$, it is shown that its envelope is C^1,1$C^{1,1}$. Then it is shown that there exists a piecewise linear (PL) subset of the reconstruction of the envelope that is ambient isotopic to M$M$, whenever M$M$ is orientable. The emphasis of this paper is upon the formal mathematical proofs needed for these extensions. (Practical application examples have already been published in a companion paper.) Possible extensions to non-orientable manifolds are also discussed. The mathematical exposition relies heavily on known techniques from differential geometry and topology, but the specific new proofs are intended to be sufficiently specialized to prompt further algorithmic discoveries.     

Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor

We consider a two-edge connected, undirected graph G=(V,E)$G=(V,E)$, with n$n$ nodes and m$m$ non-negatively real weighted edges, and a single source shortest paths tree (SPT) T$T$ of G$G$ rooted at an arbitrary node r$r$. If an edge in T$T$ is temporarily removed, it makes sense to reconnect the nodes disconnected from the root by adding a single non-tree edge, called a swap edge  , instead of rebuilding a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a best possible swap edge. In this paper we focus on the most prominent one, that is the minimization of the average distance between the root and the disconnected nodes. To this respect, we present an O(mlog²n)$O\left(m{log}^{2}n\right)$ time and O(m)$O\left(m\right)$ space algorithm to find a best swap edge for every edge of T$T$, thus improving for m=o(n²/log²n)$m=o(n^2/{log}^{2}n)$ the previously known O(n²)$O\left(n^2\right)$ time and space complexity algorithm.     

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.     

Quasi-quadratic elliptic curve point counting using rigid cohomology

Let E$E$ be a nonsupersingular elliptic curve over the finite field with pⁿ$p^n$ elements. We present a deterministic algorithm that computes the zeta function and hence the number of points of such a curve E$E$ in time quasi-quadratic in n$n$. An older algorithm having the same time complexity uses the canonical lift of E$E$, whereas our algorithm uses rigid cohomology combined with a deformation approach. An implementation in small odd characteristic turns out to give very good results.