TOPICS
Search

Generalized Steiner System


A generalized Steiner system GS(t,w,n,q) is a q-ary constant-weight code of length n and weight w, with minimum Hamming distance at least 2(w-t)+1, in which every word of weight t is covered by exactly one codeword (Etzion 1997, Wang et al. 2026). A word covers another when its nonzero coordinates include those of the other and their symbols agree at every such coordinate. Here q>=3 and 1<=t<w<=n are integers, and one symbol in the q-symbol alphabet is designated zero. The parameter q denotes alphabet size; literature using the group size instead writes q-1 in the last parameter. These are distinct from the subspace versions of Steiner systems in finite geometry.

Writing A_q(n,d,w) for the largest size of a q-ary constant-weight code with the indicated length, minimum distance, and weight, the covering count gives

 A_q(n,2w-2t+1,w)<=(q-1)^t((n; t))/((w; t)).

Equality holds exactly when the code is a generalized Steiner system. Necessary divisibility conditions are

 (w-i; t-i)|(q-1)^(t-i)(n-i; t-i),

for 0<=i<t. Wang et al. (2026, Theorem 1.3) proved that, for every fixed q>=3 and w>t>=1, these conditions are also sufficient for every sufficiently large n. The result is nonconstructive, with no explicit threshold for n supplied.

Their systems can additionally be chosen so that the supports of distinct codewords intersect in at most t coordinates. The supports then form a simple t-(n,w,(q-1)^t) design: each t-subset is contained in exactly (q-1)^t distinct supports (Wang et al. 2026, Theorem 1.5). This extra support property forces n>=t+(q-1)^t(w-t); it is stronger than the definition and need not hold at smaller admissible lengths.

For t>1, fixing a coordinate and one nonzero symbol, retaining the codewords with that symbol at the chosen coordinate, and deleting it gives a GS(t-1,w-1,n-1,q) (Etzion 1997, Wang et al. 2026).


See also

Block Design, Constant-Weight Code, Hamming Distance, Steiner System

Explore with Wolfram|Alpha

References

Etzion, T. "Optimal Constant Weight Codes over Z_k and Generalized Designs." Disc. Math. 169, 55-82, 1997. https://doi.org/10.1016/0012-365X(95)00333-R.Wang, X.; Li, S.; and Shi, M. "The Existence of Generalized Steiner Systems." 19 Nov 2026. https://arxiv.org/abs/2611.26226v1.

Cite this as:

Weisstein, Eric W. "Generalized Steiner System." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GeneralizedSteinerSystem.html

Subject classifications