tailieunhanh - Báo cáo toán học: " Sumsets of finite Beatty sequences."

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Sumsets of finite Beatty sequences. | Sumsets of finite Beatty sequences Jane Pitman Department of Pure Mathematics University of Adelaide Adelaide SA 5005 AUSTRALIA e-mail jpitman@ Submitted May 12 2000 Accepted August 15 2000 Dedicated to Aviezri Fraenkel with respect and gratitude. Abstract An investigation of the size of S S for a finite Beatty sequence S si ia yJ where J denotes floor a Y are real with a 1 and 0 i k 1 and k 3. For a 2 it is shown that S SI depends on the number of centres of the Sturmian word AS si si-1 and hence that 3 k 1 S SI 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 SI in terms of finite nearest integer continued fractions. 1 Introduction For the purposes of this paper an infinite sequence is a two-way inhnite sequence that is a sequence indexed by the set Z of all integers. An infinite Beatty sequence is a strictly increasing sequence of integers s si si i2Z such that for all integers i 1 Si ia 7J AMS Subject Classification 11B75 11P99 11B83 52C05 Key Words and Phrases Structure theory of set addition sumset small doubling property Sturmian two-distance bracket function Beatty cutting sequence. THE ELECTRONIC JOURNAL OF COMBINATORICS 8 no. 2 2001 R15 1 where L J denotes floor or integer part and a Y are fixed real numbers with a 1. Let s be such a sequence. It easily shown that for all integers i j with j 0 we have 2 si j - si2 jaJ LjaJ 1 and in particular that for all i 3 si 1 - si 2 LaJ LaJ 1 . The difference sequence of s is the sequence 4 As Ai iez where for all i 5 Ai si - si-1. From 3 we see that we can view As as a binary sequence in two symbols a and b by denoting one of LaJ LaJ 1 by a and the other by b. Both symbols must occur except in the special case when a is an integer. In this case As Ai is a constant sequence and the sequence s is an infinite arithmetic progression with common difference a LaJ or .