Narrow Results

We present a new extension of Conway's game of life for two players, which we call "p2life". P2life allows one of two types of token, black or white, to inhabit a cell and adds competitive elements into the birth and survival rules of the original game. We solve the mean-field equation for p2life and determine, using simulation, that the asymptotic density of p2life approaches 0.0362.

We introduce a family of multiplicative distributions {μ_s|s∈(0,1)} on a free group F and study it as a whole. In this approach, the measure of a given set R⊆F is a function μ(R) : s → μ_s(R), rather then just a number. This allows one to evaluate sizes of sets using analytical properties of their measure functions μ(R). We suggest a new hierarchy of subsets R in F with respect to their size, which is based on linear approximations of the function μ(R). This hierarchy is quite sensitive, for example, it allows one to differentiate between sets with the same asymptotic density. Estimates of sizes of various subsets of F are given.

We study connections between classical asymptotic density, computability and computable enumerability. In an earlier paper, the second two authors proved that there is a computably enumerable set A of density 1 with no computable subset of density 1. In the current paper, we extend this result in three different ways: (i) The degrees of such sets A are precisely the nonlow c.e. degrees. (ii) There is a c.e. set A of density 1 with no computable subset of nonzero density. (iii) There is a c.e. set A of density 1 such that every subset of A of density 1 is of high degree. We also study the extent to which c.e. sets A can be approximated by their computable subsets B in the sense that A\B has small density. There is a very close connection between the computational complexity of a set and the arithmetical complexity of its density and we characterize the lower densities, upper densities and densities of both computable and computably enumerable sets. We also study the notion of "computable at density r" where r is a real in the unit interval. Finally, we study connections between density and classical smallness notions such as immunity, hyperimmunity, and cohesiveness.

For $A\subseteq \omega$, the coarse similarity class of A, denoted by $[A]$, is the set of all $B\subseteq \omega$ such that the symmetric difference of A and B has asymptotic density 0. There is a natural metric $\delta$ on the space ${𝒮}$ of coarse similarity classes defined by letting $\delta ([A],[B])$ be the upper density of the symmetric difference of A and B. We study the metric space of coarse similarity classes under this metric, and show in particular that between any two distinct points in this space there are continuum many geodesic paths. We also study subspaces of the form $\{[A]:A\in {𝒰}\}$ where ${𝒰}$ is closed under Turing equivalence, and show that there is a tight connection between topological properties of such a space and computability-theoretic properties of ${𝒰}$.

We then define a distance between Turing degrees based on Hausdorff distance in the metric space $({𝒮},\delta )$. We adapt a proof of Monin to show that the Hausdorff distances between Turing degrees that occur are exactly 0, $1/2$, and 1, and study which of these values occur most frequently in the senses of Lebesgue measure and Baire category. We define a degree a to be attractive if the class of all degrees at distance $1/2$ from a has measure 1, and dispersive otherwise. In particular, we study the distribution of attractive and dispersive degrees. We also study some properties of the metric space of Turing degrees under this Hausdorff distance, in particular the question of which countable metric spaces are isometrically embeddable in it, giving a graph-theoretic sufficient condition for embeddability.

Motivated by a couple of issues arising in the above work, we also study the computability-theoretic and reverse-mathematical aspects of a Ramsey-theoretic theorem due to Mycielski, which in particular implies that there is a perfect set whose elements are mutually 1-random, as well as a perfect set whose elements are mutually 1-generic.

Finally, we study the completeness of $({𝒮},\delta )$ from the perspectives of computability theory and reverse mathematics.

Weiss (1981) established core equivalence and the existence of competitive equilibria in finitely additive exchange economies. To underline the relevance of finitely additive economies we present in this note an example with a close connection to finite exchange economies.

We show that the set of the numbers that are the sum of a prime and a Fibonacci number has positive lower asymptotic density.

Recently, it was shown that the density of abundant numbers has a simple series expression, which relies on the multiplicative property of the arithmetic function $\sigma (n)/n$. We generalize this result by determining a class of multiplicative functions for which the series result carries over.

We say that $n$ nonzero ideals of algebraic integers in a fixed number ring are $k$-wise relatively $r$-prime if any $k$ of them are relatively $r$-prime. In this paper, we provide an exact formula for the probability that $n$ nonzero ideals of algebraic integers in a fixed number ring are $k$-wise relatively $r$-prime.

In this paper, we prove that the set of integers which can be represented as the sum of a Fibonacci number and a prime in at least one and at most $37$ ways has the lower asymptotic density at least $0.143$.

In this paper, it is proved that there is a positive proportion of positive odd integers which can be uniquely represented as $p+2^{a^2}+2^{b^2}$, where p is a prime and $a,b$ are two positive integers with $a\le b$.

The binary sum-of-digits function $s$ returns the number of ones in the binary expansion of a nonnegative integer. Cusick’s Hamming weight conjecture states that for all integers $t\ge 0$ the set of integers $n\ge 0$ such that $s(n+t)\ge s(n)$ has asymptotic density strictly larger than $1/2$. So far, the strongest results are due to Spiegelhofer and Wallner, who showed that for t having sufficiently many blocks of $1$s in its binary expansion the conjecture holds and the difference $s(n+t)-s(n)$ is approximately normally distributed. In this paper, we are concerned with a related block-counting function $r$, returning the number of (overlapping) occurrences of the block $11$ in the binary expansion of n. Our main result is a similar central limit-type theorem for the difference $r(n+t)-r(n)$, where we give a stronger estimate of the uniform error of Gaussian approximation. As a corollary, we obtain a partial result toward an analogue of Cusick’s conjecture for $r$: the set of n satisfying $r(n+t)\ge r(n)$ has density $\ge 1/2-𝜀$ for t belonging to a set of density 1.