Fast local searches and updates in bounded universes

Given a bounded universe $\{0,1,\dots ,U?1\}$, we show how to perform predecessor searches in $O(\log \log \mathrm{\Delta })$ expected time, where Δ is the difference between the element being searched for and its predecessor in the structure, while supporting updates in $O(\log \log \mathrm{\Delta })$ expected amortized time, as well. This unifies the results of traditional bounded universe structures (which support predecessor searches in $O(\log \log U)$ time) and hashing (which supports membership queries in $O(1)$ time). We also show how these results can be applied to approximate nearest neighbour queries and range searching.     

A note on two Erdősʼs proofs of the infinitude of primes

P. Erdős found numerous theorems, problems, results and conjectures in elementary number theory. Some of them are two Erdősʼs proofs of of the famous Euclidʼs theorem on the infinitude of primes. As noticed below, one of these proofs immediately implies the fact that the number of primes smaller than x is $⩾\log x/(2\log 2)$.     

On the stability of flat complex vector bundles over parallelizable manifolds

We investigate the flat holomorphic vector bundles over compact complex parallelizable manifolds $G/\mathrm{\Gamma }$, where G is a complex connected Lie group and Γ is a cocompact lattice in it. The main result proved here is a structure theorem for flat holomorphic vector bundles $E_{\rho }$ associated with any irreducible representation $\rho :\mathrm{\Gamma }?\text{GL}(r,\mathbb{C})$. More precisely, we prove that $E_{\rho }$ is holomorphically isomorphic to a vector bundle of the form $E^{\oplus n}$, where E is a stable vector bundle. All the rational Chern classes of E vanish, in particular, its degree is zero.We deduce a stability result for flat holomorphic vector bundles $E_{\rho }$ of rank 2 over $G/\mathrm{\Gamma }$. If an irreducible representation $\rho :\mathrm{\Gamma }?\text{GL}(2,\mathbb{C})$ satisfies the condition that the induced homomorphism $\mathrm{\Gamma }?\mathrm{PGL}(2,\mathbb{C})$ does not extend to a homomorphism from G, then $E_{\rho }$ is proved to be stable.     

Parametric CR-umbilical locus of ellipsoids in C2

For every real numbers $a?1$, $b?1$ with $(a,b)\ne (1,1)$, the curve parametrized by $\theta \in \mathbb{R}$ valued in ${\mathbb{C}}^2?{\mathbb{R}}^4$

$\gamma :\theta ?(x(\theta )+\sqrt{?1}y(\theta ),u(\theta )+\sqrt{?1}v(\theta ))$

with components:

$\begin{array}{c}x(\theta ):=\sqrt{\frac{a?1}{a(ab?1)}}\cos ?\theta ,y(\theta ):=\sqrt{\frac{b(a?1)}{ab?1}}\sin ?\theta ,\hfill \\ u(\theta ):=\sqrt{\frac{b?1}{b(ab?1)}}\sin ?\theta ,v(\theta ):=?\sqrt{\frac{a(b?1)}{ab?1}}\cos ?\theta ,\hfill \end{array}$

has image contained in the CR-umbilical locus:

$\gamma (\mathbb{R})?\mathsf{UmbCR}\left({\mathsf{E}}_{a,b}\right)?{\mathsf{E}}_{a,b}$

of the ellipsoid ${\mathsf{E}}_{a,b}?{\mathbb{C}}^2$ of equation $a{x}^2+y^2+b{u}^2+v^2=1$, where the CR-umbilical locus of a Levi nondegenerate hypersurface $M^3?{\mathbb{C}}^2$ is the set of points at which the Cartan curvature of M vanishes.     

Fast index for approximate string matching

We present an index that stores a text of length n such that given a pattern of length m, all the substrings of the text that are within Hamming distance (or edit distance) at most k from the pattern are reported in $O(m+\log \log n+\text{\#}\text{matches})$ time (for constant k). The space complexity of the index is $O(n^{1+?})$ for any constant $?>0$.     

A counterexample to the local–global principle of linear dependence for Abelian varieties

Let A be an Abelian variety defined over a number field k. Let P be a point in $A(k)$ and let X be a subgroup of $A(k)$. Gajda and Kowalski asked in 2002 whether it is true that the point P belongs to X if and only if the point $(P\mathrm{mod}\mathfrak{p})$ belongs to $(X\mathrm{mod}\mathfrak{p})$ for all but finitely many primes $\mathfrak{p}$ of k. We provide a counterexample.     

ISB-tree: A new indexing scheme with efficient expected behaviour

We present the interpolation search B-tree (ISB-tree), a new cache-aware indexing scheme that supports update operations (insertions and deletions) in $O(1)$ worst-case block transfers and search operations in $O({\log }_B\log n)$ expected block transfers, where B represents the disk block size and n denotes the number of stored elements. The expected search bound holds with high probability for a large class of (unknown) input distributions. The worst-case search bound of our indexing scheme is $O({\log }_{B}n)$ block transfers. Our update and expected search bounds constitute a considerable improvement over the $O({\log }_{B}n)$ worst-case block transfer bounds for search and update operations achieved by the B-tree and its numerous variants. This is also verified by an accompanying experimental study.