Premium
Computational Results for Regular Difference Systems of Sets Attaining or Being Close to the Levenshtein Bound
Author(s) -
Chisaki Shoko,
Miyamoto Nobuko
Publication year - 2016
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21512
Subject(s) - mathematics , combinatorics , generalization , upper and lower bounds , integer (computer science) , discrete mathematics , multiplicative function , block (permutation group theory) , order (exchange) , computer science , mathematical analysis , finance , economics , programming language
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 p = e f + 1 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 ( e − 1 ) ‐subsets from the multiplicative group of order e , the lower bound on ρ is independent of the choice of e − 1 subsets. In addition, we present some computational results for DSSs with block sizes f l o o r ( e / 2 ) and f l o o r ( e / 3 ) , whose parameter ρ attains or comes close to the Levenshtein bound for p < 100 .