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.     

Ternary Kloosterman sums modulo 4

Garaschuk and Lisoněk (2008) in [3] characterised ternary Kloosterman sums modulo 4, leaving the cases $K(a)\equiv 1(\mathrm{mod}4)$ and $K(a)\equiv 3(\mathrm{mod}4)$ as open problems. In this paper we complete the characterisation using well-known theorems on Gauss sums and Kloosterman sums. We also give the number of elements satisfying these congruences.     

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.     

New constructions of SSPDs and their applications

We present a new optimal construction of a semi-separated pair decomposition (i.e., SSPD) for a set of n points in ${\mathbb{R}}^d$. In the new construction each point participates in a few pairs, and it extends easily to spaces with low doubling dimension. This is the first optimal construction with these properties.As an application of the new construction, for a fixed $t>1$, we present a new construction of a t-spanner with $O(n)$ edges and maximum degree $O({\log }^{2}n)$ that has a separator of size $O(n^{1?1/d})$.     

The uniqueness of an indefinite nonlinear diffusion problem in population genetics,part II

We study the following Neumann problem which models the “complete dominance” case of population genetics of two alleles.

$\{\begin{array}{c}{u}_t=d{u}^{″}+g(x)u^2(1?u)\text{in}(0,1)\times (0,\infty ),\hfill \\ 0\le u\le 1\text{in}(0,1)\times (0,\infty ),\hfill \\ u^{\prime }(0,t)=u^{\prime }(1,t)=0\text{in}(0,\infty ),\hfill \end{array}$

where g changes sign in $(0,1)$. It is known that this equation has a nontrivial steady state $u_d$ for d sufficiently small [5]. It has been conjectured by Nagylaki and Lou [2] that $u_d$ is a unique nontrivial steady state if ${\int }_{\mathrm{\Omega }}g(x)dx\ge 0$. This was proved in [6] if g changes sign only once. In this paper under additional condition on $g(x)$ we treat the case when g has multiple zeros.     

Le nombre des diviseurs unitaires d'un entier dans les progressions arithmétiques

Let the functions $d_{k\text{,}l}^{*}(n)$ and $d_{k\text{,}l}(n)$ be number of unitary divisors (see below) and number of divisors n in arithmetic progressions $\{l+mk\}$; k and l are integers relatively prime such that $1?l?k$ and let, for $n?2$

$F(n\text{;}k\text{,}l)=\frac{\ln (d_{k\text{,}l}(n))\ln (\phi (k)\ln n)}{\ln n}\text{,}{F}^{*}(n\text{;}k\text{,}l)=\frac{\ln (d_{k\text{,}l}^{*}(n))\ln (\phi (k)\ln n)}{\ln n}\text{and}$

$D^{*}(n\text{;}k\text{,}l)=\frac{\ln (d_{k\text{,}l}(n)/d_{k\text{,}l}^{*}(n))\ln (\phi (k)\ln n)}{\ln n}\text{,}$

where $\phi (k)$ is Euler's totient. The function $F(n\text{;}k\text{,}l)$ has been studied in [A. Derbal, A. Smati, C. A. Acad. Sci. Paris, Ser. I 339 (2004) 87–90]. In this Note we study the functions $F^{*}(n\text{;}k\text{,}l)$ and $D^{*}(n\text{;}k\text{,}l)$. We give explicitly their maximal orders and we compute effectively the maximum of $F^{*}(n\text{;}k\text{,}l)$ for $k=1\text{,}2\text{,}3$ and that of $D^{*}(n\text{;}k\text{,}l)$ for $k=1\text{,}3\text{,}5\text{,}7\text{,}8\text{,}9\text{,}10\text{,}11\text{,}13$. To cite this article: A. Derbal, C. R. Acad. Sci. Paris, Ser. I 340 (2005).