The Mixed Binary Euclid Algorithm

We present a new GCD algorithm for two integers that combines both the Euclidean and the binary gcd approaches. We give its worst case time analysis and we prove that its bit-time complexity is still $O(n^2)$ for two n-bit integers in the worst case. Our preliminar experiments show a potential speedup for small integers. A parallel version matches the best presently known time complexity, namely $O(n/\log n)$ time with $O(n^{1+\mathrm{ϵ}})$ processors, for any constant $\mathrm{ϵ}>0$.     

ON THE COMMUTATORS OF SINGULAR INTEGRAL OPERATORS

Lp(Rn) (1＜p＜∞) boundedness and a weak type endpoint estimate are considered for the commutators of singular integral operators. A condition on the associated kernel is given under which the L2(Rn) boundedness of the singular integral operators implies the Lp(Rn) boundedness (1＜p＜∞) and the weak type (H1(Rn), L1(Rn))boundedness for the corresponding commutators. A new interpolation theorem is also established.     

Number of Crossing-Free Geometric Graphs vs. Triangulations

We show that there is a constant $\alpha >0$ such that, for any set P of n⩾ 5 points in general position in the plane, a crossing-free geometric graph on P that is chosen uniformly at random contains, in expectation, at least $(\frac{1}{2}+\alpha )M$ edges, where M denotes the number of edges in any triangulation of P. From this we derive (to our knowledge) the first non-trivial upper bound of the form $c^n\cdot \mathsf{tr}(P)$ on the number of crossing-free geometric graphs on P; that is, at most a fixed exponential in n times the number of triangulations of P. (The trivial upper bound of $2^M\cdot \mathsf{tr}(P)$, or $c=2^{M/n}$, follows by taking subsets of edges of each triangulation.) If the convex hull of P is triangular, then $M=3n-6$, and we obtain $c<7.98$.Upper bounds for the number of crossing-free geometric graphs on planar point sets have so far applied the trivial $8^n$ factor to the bound for triangulations; we slightly decrease this bound to $O({343.11}^n)$.     

Higher genus Kashiwara–Vergne problems and the Goldman–Turaev Lie bialgebra

We define a family ${\mathrm{KV}}^{(g,n+1)}$ of Kashiwara–Vergne problems associated with compact connected oriented 2-manifolds of genus g with $n+1$ boundary components. The problem ${\mathrm{KV}}^{(0,3)}$ is the classical Kashiwara–Vergne problem from Lie theory. We show the existence of solutions to ${\mathrm{KV}}^{(g,n+1)}$ for arbitrary g and n. The key point is the solution to ${\mathrm{KV}}^{(1,1)}$ based on the results by B. Enriquez on elliptic associators. Our construction is motivated by applications to the formality problem for the Goldman–Turaev Lie bialgebra ${\mathfrak{g}}^{(g,n+1)}$. In more detail, we show that every solution to ${\mathrm{KV}}^{(g,n+1)}$ induces a Lie bialgebra isomorphism between ${\mathfrak{g}}^{(g,n+1)}$ and its associated graded $\mathrm{gr}{\mathfrak{g}}^{(g,n+1)}$. For $g=0$, a similar result was obtained by G. Massuyeau using the Kontsevich integral. For $g\ge 1$, $n=0$, our results imply that the obstruction to surjectivity of the Johnson homomorphism provided by the Turaev cobracket is equivalent to the Enomoto–Satoh obstruction.     

The visible perimeter of an arrangement of disks

Given a collection of n opaque unit disks in the plane, we want to find a stacking order for them that maximizes their visible perimeter, the total length of all pieces of their boundaries visible from above. We prove that if the centers of the disks form a dense point set, i.e., the ratio of their maximum to their minimum distance is $O(n^{1/2})$, then there is a stacking order for which the visible perimeter is $\Omega (n^{2/3})$. We also show that this bound cannot be improved in the case of a sufficiently small $n^{1/2}\times n^{1/2}$ uniform grid. On the other hand, if the set of centers is dense and the maximum distance between them is small, then the visible perimeter is $O(n^{3/4})$ with respect to any stacking order. This latter bound cannot be improved either.Finally, we address the case where no more than c disks can have a point in common.These results partially answer some questions of Cabello, Haverkort, van Kreveld, and Speckmann.