A combinatorial problem for vector spaces over finite fields. (English) Zbl 0747.11063

Let \(V\) be a vector space over an arbitrary field of finite dimension \(m\geq 1\) and let \(s\) and \(m_ 1,m_ 2,\ldots,m_ s\) be positive integers. For a system \(C\) of vectors of the form \(c_ j^{(i)}\in V\), for \(1\leq j\leq m_ i\), \(1\leq i\leq s\) define \(\rho(C)=\min\sum^ s_{i=1}d_ i\) where the minimum is extended over all integers \(d_ 1,\ldots,d_ s\) with \(0\leq d_ i\leq m_ i\) for \(1\leq i\leq s\) and \(\sum^ s_{i=1}d_ i\geq 1\) for which the subsystem \(\{c_ j^{(i)}:1\leq j\leq d_ i\), \(1\leq i\leq s\}\) is linearly dependent in \(V\). If there are no such \(d_ 1,\ldots,d_ s\) then define \(\rho(C)=m+1\). This paper studies the number \(R(V;m_ 1,\ldots,m_ s)=\max\rho(C)\) where the maximum is taken over all systems \(C\) of the noted form. It was previously shown that if the field of scalars is infinite then \(R(V;m_ 1,\ldots,m_ s)=m+1\) and it thus suffices to consider \(V\) over a finite field. The relationship of this problem with coding theory is also considered.


11T99 Finite fields and commutative rings (number-theoretic aspects)
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
94B40 Arithmetic codes
15B33 Matrices over special rings (quaternions, finite fields, etc.)
Full Text: DOI


[1] Berlekamp, E. R., Algebraic Coding Theory (1968), McGraw-Hill: McGraw-Hill New York · Zbl 0199.54101
[2] Lidl, R.; Niederreiter, H., Finite Fields (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0554.12010
[3] MacWilliams, F. J.; Sloane, N. J.A., The Theory of Error-Correcting Codes (1977), North-Holland: North-Holland Amsterdam · Zbl 0369.94008
[4] McEliece, R. J., The Theory of Information and Coding (1977), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0376.94011
[5] Niederreiter, H., Point sets and sequences with small discrepancy, Monatsh. Math., 104, 273-337 (1987) · Zbl 0626.10045
[6] van Lint, J. H., Introduction to Coding Theory (1982), Springer: Springer Berlin · Zbl 0485.94015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.