Equidistant families of sets (Q1899407)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Equidistant families of sets |
scientific article |
Statements
Equidistant families of sets (English)
0 references
29 September 1996
0 references
This is a very interesting paper on the relation between large equidistant codes and combinatorial designs. The authors use the terminology of set theory. In this review, we will use \({\mathbf a}\) for the binary word of length \(v\) which has 1's in the positions corresponding to the subset \(A\) of \([v]:= \{1, 2,\dots, v\}\). In this terminology \({\mathbf a}+ {\mathbf b}\) corresponds to the symmetric difference \(A \Delta B\). Two families of subsets are called equivalent if the corresponding binary codes are translates. Of the two main results, the first concerns an equidistant code \(C\) of length \(v\) \((v\geq 3)\), distance \(d\) and cardinality \(v\). It states that if \(v= 2d\), then \(C\) is equivalent to a code consisting of the all one vector and the \(v- 1\) blocks of a Hadamard 3-design with no two blocks being complementary, and if \(v\neq 2d\), then \(C\) is equivalent to the block-set of a symmetric 2-design. The other main result extends a theorem of \textit{D. R. Stinson} and \textit{G. H. J. van Rees} [The equivalence of certain equidistant binary codes and symmetric BIBDs, Combinatorica 4, 357-362 (1984; Zbl 0556.05010)]. They proved that an equidistant binary code with wordlength \(v= 4k+ 1\) and distance \(d= 2k\) exists if and only if \(k= {1\over 2} (u^2+ u)\) and there exists a 2-\((2u^2+ 2u+ 1, u^2, {1\over 2}(u^2- u))\) design. The present authors give an alternative proof of this result and they extend it to the cases \(v\equiv 0, 2, 3\pmod 4\). In each of these cases the code is equivalent to some design. The proofs are based on the method of linear polynomials. For an equidistant code of length \(v\) and distance \(d\), associate with the set \(A\) (corresponding to codeword \({\mathbf a})\) the function \[ f_A(x_1, x_2,\dots, x_v):= \sum_{i\not\in A} x_i- \sum_{i\in A} x_i+ |A|- d. \] For any subset \(X\) of \([v]\) we have \[ f_A(X)= |A \Delta X|- d.\tag{\(*\)} \] The relation \((*)\) easily leads to the result of \textit{P. Delsarte} [Four fundamental parameters of a code and their combinatorial significance, Inform. and Control 23, 407-438 (1973; Zbl 0274.94010)] stating that an equidistant binary code of length \(v\) has cardinality \(\leq v+ 1\). The authors show this by proving that the linear polynomials corresponding to codewords form a basis of the space of linear polynomials in \(v\) variables. If the code has cardinality \(v\), then the constant 1 and the polynomials again are a basis. To prove their first main result, the authors express the monomials \(x_i\) in this basis and then apply the resulting equation to the sets \(\varnothing\), \(\{i\}\), and \([v]\). Manipulating the three equations yields a quadratic equation in \(v\), \(d\), and the number \(r_i\), denoting the number of codewords with \(i\)th coordinate 1. An analysis of three cases produces the theorem. The other main result is a consequence of the earlier theorems.
0 references
Hadamard design
0 references
equidistant codes
0 references
combinatorial designs
0 references
binary codes
0 references
linear polynomials
0 references
codewords
0 references
0 references