On Motzkin's Problem in the Circle Group

Pablo Candela ; Carlos Catalá ; Juanjo Rué ; Oriol Serra

Informatics and Automation, Analytic and Combinatorial Number Theory, Tome 314 (2021), pp. 49-70

Résumé

Given a subset $D$ of the interval $(0,1)$, if a Borel set $A\subset [0,1)$ contains no pair of elements whose difference modulo $1$ is in $D$, then how large can the Lebesgue measure of $A$ be? This is the analogue in the circle group of a well-known problem of Motzkin, originally posed for sets of integers. We make a first treatment of this circle-group analogue, for finite sets $D$ of missing differences, using techniques from ergodic theory, graph theory and the geometry of numbers. Our results include an exact solution when $D$ has two elements at least one of which is irrational. When every element of $D$ is rational, the problem is equivalent to estimating the independence ratio of a circulant graph. In the case of two rational elements, we give an estimate for this ratio in terms of the odd girth of the graph, which is asymptotically sharp and also recovers the classical solution of Cantor and Gordon to Motzkin's original problem for two missing differences.