Search

We show that, among free boundary minimal surfaces in the unit ball in the three-dimensional Euclidean space, the flat equatorial disk and the critical catenoid are characterised by a pinching condition on the length of their second fundamental form., 8 pages

Brenier's theorem is a landmark result in Optimal Transport. It postulates existence, monotonicity and uniqueness of an optimal map, with respect to the quadratic cost function, between two given probability measures (under some weak regularity conditions). We prove an effective version of Brenier's theorem: we show that for any two computable absolutely continuous measures on Rn, μ, and ν, with some restrictions on their support, there exists a computable convex function φ, whose gradient xφ is the optimal transport map between μ and ν. The main insight of the paper is the idea that an effective Brenier's theorem can be used to construct effective monotone maps on Rn with desired (non-)differentiability properties. We use it to solve several problems at the interface of algorithmic randomness and computable analysis. In particular, we show that z ∈ Rn is computably random if and only if every computable monotone function on Rn is differentiable at z. Furthermore, we prove the converse of the effective Aleksandrov theorem (Galicki 2015): we show that if z ∈ Rn is not computably random, there exists a computable convex function that is not twice differentiable at z. Finally, we prove several new characterisations of computable randomness in Rn: in terms of differentiability of computable measures, in terms of a particular Monge-Ampere equation and in terms of critical values of computable Lipschitz functions.

In this paper, we will prove a gap theorem for four-dimensional gradient shrinking soliton. More precisely, we will show that any complete four-dimensional gradient shrinking soliton with nonnegative and bounded Ricci curvature, satisfying a pinched Weyl curvature, either is flat, or $\lambda_1 + \lambda_2\ge c_0 R>0$ everywhere for some $c_0\approx 0.29167$, where $\{\lambda_i\}$ are the two least eigenvalues of Ricci curvature. Furthermore, we will show that $\lambda_1 + \lambda_2\ge \frac 13R>0$ under a better pinched Weyl tensor assumption. We point out that the lower bound $\frac 13R$ is sharp., Comment: 11 pages

Borwein and Ditor (Canadian Math. Bulletin 21 (4), 497–498, 1978) proved the following. Let \(\mathcal {A}\subset {\mathbb {R}}\) be a measurable set of positive measure and let \({\left\langle {r_m}\right\rangle }_{m\in \omega }\) be a null sequence of real numbers. For almost all \(z \in \mathcal {A}\), there is m such that \(z+r_m\in \mathcal {A}\).

The three gap theorem (or Steinhaus conjecture) asserts that there are at most three distinct gap lengths in the fractional parts of the sequence $\alpha,2\alpha,\ldots,N\alpha$, for any integer $N$ and real number $\alpha$. This statement was proved in the 1950s independently by various authors. Here we present a different approach using the space of two-dimensional Euclidean lattices., Comment: To appear in the American Mathematical Monthly

We prove a dichotomy theorem for the rank of propositional contradictions, uniformly generated from first-order sentences, in both the Lovasz-Schrijver (LS) and Sherali-Adams (SA) refutation systems. More precisely, we first show that the propositional translations of first-order formulae that are universally false, that is, fail in all finite and infinite models, have LS proofs whose rank is constant, independent of the size of the (finite) universe. In contrast to that, we prove that the propositional formulae that fail in all finite models, but hold in some infinite structure, require proofs whose SA rank grows polynomially with the size of the universe. Until now, this kind of so-called complexity gap theorem has been known for tree-like Resolution and, in somehow restricted forms, for the Resolution and Nullstellensatz systems. As far as we are aware, this is the first time the Sherali-Adams lift-and-project method has been considered as a propositional refutation system (since the conference version of this paper, SA has been considered as a refutation system in several further papers). An interesting feature of the SA system is that it simulates LS, the Lovasz-Schrijver refutation system without semi-definite cuts, in a rank-preserving fashion.

Symmetric disk graphs are often used to model wireless communication networks. Given a set S of n points in R^d (representing n transceivers) and a transmission range assignment r:S->R, the symmetric disk graph of S (denoted SDG(S)) is the undirected graph over S whose set of edges is E={(u,v)|r(u)>=|uv| and r(v)>=|uv|}, where |uv| denotes the Euclidean distance between points u and v. We prove that the weight of the MST of any connected symmetric disk graph over a set S of n points in the plane, is only O(logn) times the weight of the MST of the complete Euclidean graph over S. We then show that this bound is tight, even for points on a line. Next, we prove that if the number of different ranges assigned to the points of S is only k, [email protected]?n, then the weight of the MST of SDG(S) is at most 2k times the weight of the MST of the complete Euclidean graph. Moreover, in this case, the MST of SDG(S) can be computed efficiently in time O(knlogn). We also present two applications of our main theorem, including an alternative proof of the Gap Theorem, and a result concerning range assignment in wireless networks. Finally, we show that in the non-symmetric model (where E={(u,v)|r(u)>=|uv|}), the weight of a minimum spanning subgraph might be as big as @W(n) times the weight of the MST of the complete Euclidean graph.

From the fundamental theorem of homomorphisms, it is well known that any homomorphism of groups (or rings or modules or vector spaces and of general universal algebras) can be decomposed as a composition of a monomorphism and an epimorphism. This result can also be extended to general functions defined on abstract sets; that is, any function can be expressed as a composition of an injection and a surjection. The main theorem in this paper called ‘Fundamental Theorem of Functions’ provides the uniqueness of such a decomposition of functions as a composition of an injection and a surjection. The uniqueness in this theorem is proved upto the level of associates by introducing the notion of an associate of functions.

We give a new characterization of the strict $$\forall {\Sigma^b_j}$$ sentences provable using $${\Sigma^b_k}$$ induction, for 1 ? j ? k. As a small application we show that, in a certain sense, Buss's witnessing theorem for strict $${\Sigma^b_k}$$ formulas already holds over the relatively weak theory PV. We exhibit a combinatorial principle with the property that a lower bound for it in constant-depth Frege would imply that the narrow CNFs with short depth j Frege refutations form a strict hierarchy with j, and hence that the relativized bounded arithmetic hierarchy can be separated by a family of $$\forall {\Sigma^b_1}$$ sentences.

In this paper, we prove that the mean curvature blows up at the same rate as the second fundamental form at the first singular time $T$ of any compact, Type I mean curvature flow. For the mean curvature flow of surfaces, we obtain similar result provided that the Gaussian density is less than two. Our proofs are based on continuous rescaling and the classification of self-shrinkers. We show that all notions of singular sets defined in \cite{St} coincide for any Type I mean curvature flow, thus generalizing the result of Stone who established that for any mean convex Type I Mean curvature flow. We also establish a gap theorem for self-shrinkers., Comment: 21 pages

We show that, for any abstract complexity measure in the sense of Blum and for any computable function f (or computable operator F), the class of problems that are f-speedable (or F-speedable) does not have effective measure 0. On the other hand, for sufficiently fast growing f (or F), the class of non-speedable computable problems does not have effective measure 0. These results answer some questions raised by Calude and Zimand. We also give a quantitative analysis of Borodin and Trakhtenbrot's Gap Theorem, which corrects a claim by Calude and Zimand.

We prove a generalization of Prömel's theorem to finite structures with both relations and functions.

We survey all known results in the area of quasigroup and loop theory to have been obtained with the assistance of automated theorem provers. We provide both informal and formal descriptions of selected problems, and compare the performance of selected state-of-the art first order theorem provers on them. Our analysis yields some surprising results, e.g., the theorem prover most often used by loop theorists does not necessarily yield the best performance.

Let P be a non empty poset. Observe that there exists a chain of P which is non empty. Let I1 be a relational structure. We say that I1 is chain-complete if and only if: (Def. 1) I1 is lower-bounded and for every chain L of I1 such that L is non empty holds sup L exists in I1. One can prove the following proposition (1) Let P1, P2 be non empty posets, K be a non empty chain of P1, and h be a monotone function from P1 into P2. Then h◦K is a non empty chain of P2. Let us note that there exists a poset which is strict, chain-complete, and non empty. Let us mention that every relational structure which is chain-complete is also lower-bounded.

We study computable linear orders with computable neighborhood and block predicates. In particular, it is proved that there exists a computable linear order with a computable neighborhood predicate, having a Π 1 0 -initial segment which is isomorphic to no computable order with a computable neighborhood predicate. On the other hand, every Σ 1 0 -initial segment of such an order has a computable copy enjoying a computable neighborhood predicate. Similar results are stated for computable linear orders with a computable block predicate replacing a neighborhood relation. Moreover, using the results obtained, we give a simpler proof for the Coles–Downey–Khoussainov theorem on the existence of a computable linear order with Π 2 0 -initial segment, not having a computable copy.

Let us consider the interval [0,1) as a billiard table rectangle with perimeter 1 and a sequence F(m)∈[0,1),m∈N∪{0}, of successive rebounds of a billiard ball against the sides of a billiard rectangle. We prove that if I is an open segment of a billiard rectangle, then the differences between the successive values of m for which the F(m) lies in I, take at most one even and at most four distinct odd values.

Given a program of a linear bounded and bijective operator T , does there exist a program for the inverse operator T − 1 ? And if this is the case, does there exist a general algorithm to transfer a program of T into a program of T − 1 ? This is the inversion problem for computable linear operators on Banach spaces in its non-uniform and uniform formulation, respectively. We study this problem from the point of view of computable analysis which is the Turing machine based theory of computability on Euclidean space and other topological spaces. Using a computable version of Banach’s Inverse Mapping Theorem we can answer the first question positively. Hence, the non-uniform version of the inversion problem is solvable, while a topological argument shows that the uniform version is not. Thus, we are in the striking situation that any computable linear operator has a computable inverse while there exists no general algorithmic procedure to transfer a program of the operator into a program of its inverse. As a consequence, the computable version of Banach’s Inverse Mapping Theorem is a powerful tool which can be used to produce highly non-constructive existence proofs of algorithms. We apply this method to prove that a certain initial value problem admits a computable solution. As a preparation of Banach’s Inverse Mapping Theorem we also study the Open Mapping Theorem and we show that the uniform versions of both theorems are limit computable, which means that they are effectively Σ 2 0 -measurable with respect to the effective Borel hierarchy.

A classic result known as the speed-up theorem in machine-independent complexity theory shows that there exist some computable functions that do not have best programs for them (Blum in J. ACM 14(2):322–336, 1967 and J. ACM 18(2):290–305, 1971). In this paper we lift this result into type-2 computations. Although the speed-up phenomenon is essentially inherited from type-1 computations, we observe that a direct application of the original proof to our type-2 speed-up theorem is problematic because the oracle queries can interfere with the speed of the programs and hence the cancellation strategy used in the original proof is no longer correct at type-2. We also argue that a type-2 analog of the operator speed-up theorem (Meyer and Fischer in J. Symb. Log. 37:55–68, 1972) does not hold, which suggests that this curious speed-up phenomenon disappears in higher-typed computations beyond type-2. The result of this paper adds one more piece of evidence to support the general type-2 complexity theory under the framework proposed in Li (Proceedings of the Third International Conference on Theoretical Computer Science, pp. 471–484, 2004 and Proceedings of Computability in Europe: Logical Approach to Computational Barriers, pp. 182–192, 2006) and Li and Royer (On type-2 complexity classes: Preliminary report, pp. 123–138, 2001) as a reasonable setup.

In this paper, we show that any ancient solution to the Ricci flow with the reduced volume whose asymptotic limit is sufficiently close to that of the Gaussian soliton is isometric to the Euclidean space for all time. This is a generalization of Anderson's result for Ricci-flat manifolds. As a corollary, a gap theorem for gradient shrinking Ricci solitons is also obtained.

Let $X$ be a Polish space and $T_t$ a jointly Borel measurable action of $\mathbb{R}^+ = [0, \infty)$ on $X$ by surjective maps preserving some Borel probability measure $\mu$ on $X$. We show that if each $T_t$ is countable-to-1 and if $T_t$ has the "discrete orbit branching property'' (described in the introduction), then $(X, T_t)$ is isomorphic to a "semiflow under a function''.

We define the effective integrability of Fine-computable functions and effectivize some fundamental limit theorems in the theory of Lebesgue integrals such as the Bounded Convergence Theorem, the Dominated Convergence Theorem, and the Second Mean Value Theorem. It is also proved that the Walsh-Fourier coefficients of an effectively integrable Fine-computable function form a Euclidian computable sequence of reals which converges effectively to zero. This property of convergence is the effectivization of the Walsh-Riemann-Lebesgue Theorem. The article is closed with the effective version of Dirichlet's test. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)

In this article, we study various homological invariants of differential graded (DG for short) modules over a connected DG algebra following Frankild–Jorgensen. Two different versions of homological dimensions (resolutional and functorial) are defined. In some cases, they are proved to be simply the bound of the cohomology of the DG module. Some homological identities, such as Auslander–Buchsbaum formula and Bass formula, are proved for compact DG modules over a connected DG algebra.

We prove uniformly computable versions of the Implicit Function Theorem in its differentiable and non-differentiable forms. We show that the resulting operators are not computable if information about some of the partial derivatives of the implicitly defining function is omitted. Finally, as a corollary, we obtain a uniformly computable Inverse Function Theorem, first proven by M. Ziegler (2006). (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)

We consider the distribution of the maximum for finite, deterministic, periodic and quasiperiodic sequences, and contrast the extreme value distributions in these cases with the classical results for iidrv's. A significant feature in the case of deterministic sequences is a multi-step structure for the distribution function. The extreme value distribution for the circle map with an irrational parameter is obtained in closed form with the help of the three-gap theorem for the map Xj+1 = (Xj + a) mod 1 where a ∈ (0,1) is an irrational number.

Using the tools of computability theory and reverse mathematics, we study the complexity of two partition theorems, the Canonical Ramsey Theorem of Erdos and Rado, and the Regressive Function Theorem of Kanamori and McAloon. Our main aim is to analyze the complexity of the solutions to computable instances of these problems in terms of the Turing degrees and the arithmetical hierarchy. We succeed in giving a sharp characterization for the Canonical Ramsey Theorem for exponent 2 and for the Regressive Function Theorem for all exponents. These results rely heavily on a new, purely inductive, proof of the Canonical Ramsey Theorem. This study also unearths some interesting relationships between these two partition theorems, Ramsey's Theorem, and Konig's Lemma.

The theory of inner functions plays an important role in the study of bounded analytic functions. Inner functions are also very useful in applied mathematics. Two foundational results in this theory are Frostman's Theorem and the Factorization Theorem. We give a uniformly computable version of Frostman's Theorem. We then claim that the Factorization Theorem is not uniformly computably true. We then claim that for an inner function u, the Blaschke sum of u provides the exact amount of information necessary to compute the factorization of u. Along the way, we discuss some uniform computability results for Blaschke products. These results play a key role in the analysis of factorization. We also give some computability results concerning zeros and singularities of analytic functions. We use Type-Two Effectivity as our foundation.

We define the effective integrability of Fine-computable functions and effectivize some fundamental limit theorems in the theory of Lebesgue integral such as Bounded Convergence Theorem and Dominated Convergence Theorem. It is also proved that the Walsh-Fourier coefficients of an effectively integrable Fine-computable function form an E-computable sequence of reals and converge effectively to zero. The latter fact is the effectivization of Walsh-Riemann-Lebesgue Theorem. The article is closed with the effective version of Dirichlet's test.

The classical Hahn–Banach Theorem states that any linear bounded functional defined on a linear subspace of a normed space admits a norm-preserving linear bounded extension to the whole space. The constructive and computational content of this theorem has been studied by Bishop, Bridges, Metakides, Nerode, Shore, Kalantari Downey, Ishihara and others and it is known that the theorem does not admit a general computable version. We prove a new computable version of this theorem without unrolling the classical proof of the theorem itself. More precisely, we study computability properties of the uniform extension operator which maps each functional and subspace to the set of corresponding extensions. It turns out that this operator is upper semi-computable in a well-defined sense. By applying a computable version of the Banach–Alaoglu Theorem we can show that computing a Hahn–Banach extension cannot be harder than finding a zero in a compact metric space. This allows us to conclude that the Hahn–Banach extension operator is \({\bf {\Sigma^{0}_{2}}}\) -computable while it is easy to see that it is not lower semi-computable in general. Moreover, we can derive computable versions of the Hahn–Banach Theorem for those functionals and subspaces which admit unique extensions.

We introduce and study the notions of computable formal context and computable formal concept. We give some examples of computable formal contexts in which the computable formal concepts fail to form a lattice and study the complexity aspects of formal concepts in computable contexts. In particular, we give some sufficient conditions under which the computability or noncomputability of a formal concept could be recognized from its lattice-theoretic properties. We prove the density theorem showing that in a Cantor-like topology every formal concept can be approximated by computable ones. We also show that not all formal concepts have lattice-theoretic approximations as suprema or infima of families of computable formal concepts.

Bearing in mind the insight into the Hohenberg–Kohn theorem for Coulomb systems provided recently by Kryachko (Int J Quantum Chem 103:818, 2005), we present a re-statement of this theorem through an elaboration on Lieb’s proof as well as an extension of this theorem to finite subspaces.

In this paper we develop a bubble tree structure for a degenerating class of Riemannian metrics satisfying some global conformal bounds on compact manifolds of dimension 4. Applying the bubble tree structure, we establish a gap theorem, a finiteness theorem for diffeomorphism type for this class, and make a comparison of the solutions of the σk equations on a degenerating family of Bach-flat metrics.

We prove computable versions of the Implicit Function Theorem in the single and multivariable cases. We use Type Two Effectivity as our foundation.

Blum's speedup theorem is a major theorem in computational complexity, showing the existence of computable functions for which no optimal program can exist: for any speedup function r there exists a function fr such that for any program computing fr we can find an alternative program computing it with the desired speedup r. The main corollary is that algorithmic problems do not have, in general, a inherent complexity.Traditional proofs of the speedup theorem make an essential use of Kleene's fix point theorem to close a suitable diagonal argument. As a consequence, very little is known about its validity in subrecursive settings, where there is no universal machine, and no fixpoints. In this article we discuss an alternative, formal proof of the speedup theorem that allows us to spare the invocation of the fix point theorem and sheds more light on the actual complexity of the function fr.

We give a rigidity theorem of proper holomorphic mappings between generalized pseudoellipsoids. The theorem claims that any proper holomorphic mapping which is holomorphic extendable up to the boundary between generalized pseudoellipsoids of non-equidimensions is a collections of totally geodesic embeddings up to automorphisms.

In this paper, using estimates for the generalized Ricci curvature, we shall give some gap theorems for Ricci-harmonic solitons with compact domain manifolds by showing some necessary and sufficient conditions for the solitons to be harmonic-Einstein. Our results may be regarded as generalizations of recent works by H. Li, and M. Fernandez-Lopez and E. Garcia-Rio.

We adapt modulus of continuity estimates to the study of spectra of combinatorial graph Laplacians, as well as the Dirichlet spectra of certain weighted Laplacians. The latter case is equivalent to stoquastic Hamiltonians and is of current interest in both condensed matter physics and quantum computing. In particular, we introduce a new technique which bounds the spectral gap of such Laplacians (Hamiltonians) by studying the limiting behavior of the oscillations of their eigenvectors when introduced into the heat equation. Our approach is based on recent advances in the PDE literature, which include a proof of the fundamental gap theorem by Andrews and Clutterbuck., Comment: 22 pages, corrected citations, corrected compiler errors

L. Ciungu and B. Riecan proved in [2] that any real state on IF-sets can be represented by integrals in sense that $$m{\left(\left(\mu_A, \nu_A\right)\right)}=\int{\mu_A\mathrm{d}P}+\alpha\left(1-\int{\left(\mu_A+\nu_A\right)\mathrm{d}Q}\right).$$ However the formulation is unappropriate for general case with values from arbitrary Riesz space. This article shows that only small change in formulation make it appropriate for the general case.

P. Hertling [Lecture Notes in Computer Science, vol. 2380, Springer, Berlin, 2002, pp. 962–972; Ann. Pure Appl. Logic 132 (2005) 227–246] showed that there exists a sequentially computable function mapping all computable real numbers to computable real numbers that is not effectively continuous. Here, that result is strengthened: a sequentially computable function on the computable real numbers is constructed that is not effectively continuous at any point.

We present computable versions of the Fréchet–Riesz Representation Theorem and the Lax–Milgram Theorem. The classical versions of these theorems play important roles in various problems of mathematical analysis, including boundary value problems of elliptic equations. We demonstrate how their computable versions yield computable solutions of the Neumann and Dirichlet boundary value problems for a simple non-symmetric elliptic differential equation in the one-dimensional case. For the discussion of these elementary boundary value problems, we also provide a computable version of the Theorem of Schauder, which shows that the adjoint of a computably compact operator on Hilbert spaces is computably compact again.

In this work we obtain a gap theorem for spacelike submanifolds with parallel mean curvature vector in a semi-Riemannian space form.

We study computable Boolean algebras with distinguished ideals (I-algebras for short). We prove that the isomorphism problem for computable I-algebras is Σ 1 1 -complete and show that the computable isomorphism problem and the computable categoricity problem for computable I-algebras are Σ 3 0 -complete.

The Dushnik{Miller Theorem states that every innite countable linear ordering has a nontrivial self-embedding. We examine computability-theoretical aspects of this classical theorem.

In this paper, we present a generalization of a result due to Hollmann, Korner, and Litsyn [9]. They prove that each partition of the n-dimensional binary Hamming space into spheres consists of either one or two or at least n + 2 spheres. We prove a q-ary version of that gap theorem and consider the problem of the next gaps. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 183–201, 2006

We study the computational complexity of the distance function associated with a polynomial-time computable two-dimensional domains, in the context of the Turing machine-based complexity theory of real functions. It is proved that the distance function is not necessarily computable even if a two-dimensional domain is polynomial-time recognizable. On the other hand, if both the domain and its complement are strongly polynomial-time recognizable, then the distance function is polynomial-time computable if and only if P=NP.

In this article we give an extension of a theorem of N. Levinson (see Theorem 2.1). As an application, we get a variation of the Fabry Gap theorem (see Theorem 2.3) concerning the location of singularities of Taylor–Dirichlet series, on the boundary of convergence.

The classical Hahn-Banach Theorem states that any linear bounded functional defined on a linear subspace of a normed space admits a norm-preserving linear bounded extension to the whole space. The constructive and computational content of this theorem has been studied by Bishop, Bridges, Metakides, Nerode, Shore, Kalantari, Downey, Ishihara and others and it is known that the theorem does not admit a general computable version. We prove a new computable version of this theorem without unrolling the classical proof of the theorem itself. More precisely, we study computability properties of the uniform extension operator which maps each functional and subspace to the set of corresponding extensions. It turns out that this operator is upper semi-computable in a well-defined sense. By applying a computable version of the Banach-Alaoglu Theorem we can show that computing a Hahn-Banach extension cannot be harder than finding a zero on a compact metric space. This allows us to conclude that the Hahn-Banach extension operator is ∑20–computable while it is easy to see that it is not lower semi-computable in general. Moreover, we can derive computable versions of the Hahn-Banach Theorem for those functionals and subspaces which admit unique extensions.

Let K K be an algebraically closed field, and let R R be a finitely graded K K -algebra which is a domain. We show that R R cannot have Gelfand-Kirillov dimension strictly between 2 2 and 3 3 .