Sumsets of finite Beatty sequences

Jane Pitman

The electronic journal of combinatorics, The Fraenkel Festschrift volume, Tome 8 (2001) no. 2

Résumé

An investigation of the size of $S+S$ for a finite Beatty sequence $S=(s_i)=(\lfloor i\alpha+\gamma \rfloor)$, where $\lfloor \hphantom{x} \rfloor$ denotes "floor", $\alpha$, $\gamma$ are real with $\alpha\ge 1$, and $0\le i \le k-1$ and $k\ge 3$. For $\alpha>2$, it is shown that $|S+S|$ depends on the number of "centres" of the Sturmian word $\Delta S=(s_i-s_{i-1})$, and hence that $3(k-1)\le |S+S|\le 4k-6$ if $S$ is not an arithmetic progression. A formula is obtained for the number of centres of certain finite periodic Sturmian words, and this leads to further information about $|S+S|$ in terms of finite nearest integer continued fractions.

Détail

DOI : 10.37236/1614

Classification : 11B83, 11B75, 11A55, 11P99, 52C05
Mots-clés : structure theory of set addition, sumset, small doubling property, Sturmian sequences, Beatty sequences, cutting sequences, bracket function