A Note on the Number of General 4-holes in (Perturbed) Grids

O. Aichholzer, T. Hackl, P. Valtr, and B. Vogtenhuber

Abstract:

Considering a variation of the classical Erdos-Szekeres type problems, we count the number of general 4-holes (not necessarily convex, empty 4-gons) in squared Horton sets of size $\sqrt{n}\!\times\!\sqrt{n}$. Improving on previous upper and lower bounds we show that this number is $\Theta(n^2\log n)$, which constitutes the currently best upper bound on minimizing the number of general $4$-holes for any set of $n$ points in the plane. To obtain the improved bounds, we prove a result of independent interest. We show that $\sum_{d=1}^n \frac{\varphi(d)}{d^2} = \Theta(\log n)$, where $\varphi(d)$ is Euler's phi-function, the number of positive integers less than $d$ which are relatively prime to $d$. This arithmetic function is also called Euler's totient function and plays a role in number theory and cryptography.

Reference: O. Aichholzer, T. Hackl, P. Valtr, and B. Vogtenhuber. A note on the number of general 4-holes in (perturbed) grids. In J. Akiyama, H. Ito, T. Sakai, and Y. Uno, editors, Discrete and Computational Geometry and Graphs. JCDCGG 2015., volume 9943 of Lecture Notes in Computer Science (LNCS), pages 1-12. Springer, Cham, 2016.