Computational Results for Regular Difference Systems of Sets Attaining or Being Close to the Levenshtein Bound |
| |
Authors: | Shoko Chisaki Nobuko Miyamoto |
| |
Institution: | 1. Graduate School of Science and Technology, Tokyo University of Science, Noda, Japan;2. Department of Information Science, Tokyo University of Science, Noda, Japan |
| |
Abstract: | Difference systems of sets (DSSs) are combinatorial structures arising in connection with code synchronization that were introduced by Levenshtein in 1971, and are a generalization of cyclic difference sets. In this paper, we consider a collection of m‐subsets in a finite field of prime order to be a regular DSS for an integer m, and give a lower bound on the parameter ρ of the DSS using cyclotomic numbers. We show that when we choose ‐subsets from the multiplicative group of order e, the lower bound on ρ is independent of the choice of subsets. In addition, we present some computational results for DSSs with block sizes and , whose parameter ρ attains or comes close to the Levenshtein bound for . |
| |
Keywords: | difference systems of sets cyclotomic cosets cyclotomic numbers |
|
|