Splitter Sets and k -Radius Sequences

• Published in: IEEE transactions on information theory 2017-12, Vol.63 (12), p.7633-7645
• Main Authors: Zhang, Tao, Zhang, Xiande, Ge, Gennian
• Format: Article
• Language: English
• Subjects: <italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">k -additive sequences; <italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">k -radius sequences; conflict-avoiding codes; Context; Data transfer; Data transfer (computers); Electronic mail; Flash memories; flash memory; Indexes; lattice tilings; Lattices; Splitter sets
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2017.2695219

Splitter sets are closely related to lattice tilings, and have applications in flash memories and conflict-avoiding codes. The study of k-radius sequences was motivated by some problems occurring in large data transfer. It is observed that the existence of splitter sets yields k-radius sequences of short length. In this paper, we obtain several new results contributing to splitter sets and k-radius sequences. We give some new constructions of perfect splitter sets, as well as some nonexistence results on them. As a byproduct, we obtain some new results on optimal conflict-avoiding codes. Furthermore, we provide several explicit constructions of short k-radius sequences for certain values of n, by establishing the existence of k-additive sequences. In particular, we show that for any fixed k, there exist infinitely many values of n such that f k (n) = 2k/n 2 + O(n), where f k (n) denotes the shortest length of an n-ary k-radius sequence. This result partially affirms a conjecture posed by Bondy, Lonc, and Rza̧żewski.