Article Contents
Article Contents

Maximum weight spectrum codes

The first author acknowledges the support of the NSERC of Canada Discovery Grant program.
The second author acknowledges the support of Swiss National Science Foundation grant n.169510.
• In the recent work [9], a combinatorial problem concerning linear codes over a finite field $\mathbb{F}_q$ was introduced. In that work the authors studied the weight set of an $[n,k]_q$ linear code, that is the set of non-zero distinct Hamming weights, showing that its cardinality is bounded above by $\frac{q^k-1}{q-1}$. They showed that this bound was sharp in the case $q = 2$, and in the case $k = 2$. They conjectured that the bound is sharp for every prime power $q$ and every positive integer $k$. In this work we quickly establish the truth of this conjecture. We provide two proofs, each employing different construction techniques. The first relies on the geometric view of linear codes as systems of projective points. The second approach is purely algebraic. We establish some lower bounds on the length of codes that satisfy the conjecture, and the length of the new codes constructed here are discussed.

Mathematics Subject Classification: Primary: 11T71; Secondary: 05D99, 94B05.

 Citation:

• Figure 1.

Figure 2.

Figure 3.

•  [1] T. L. Alderson and A. A. Bruen, Coprimitive sets and inextendable codes, Des. Codes Cryptogr., 47 (2008), 113-124.  doi: 10.1007/s10623-007-9079-0. [2] S. Ball, Finite Geometry and Combinatorial Applications, volume 82. Cambridge University Press, 2015. doi: 10.1017/CBO9781316257449. [3] P. Delsarte, Four fundamental parameters of a code and their combinatorial significance, Information and Control, 23 (1973), 407-438.  doi: 10.1016/S0019-9958(73)80007-5. [4] H. Enomoto, P. Frankl, N. Ito and K. Nomura, Codes with given distances, Graphs and Combinatorics, 3 (1987), 25-38.  doi: 10.1007/BF01788526. [5] A. Haily and D. Harzalla, On binary linear codes whose automorphism group is trivial, Journal of Discrete Mathematical Sciences and Cryptography, 18 (2015), 495-512.  doi: 10.1080/09720529.2014.927650. [6] J. MacWilliams, A theorem on the distribution of weights in a systematic code, The Bell System Technical Journal, 42 (1963), 79-94.  doi: 10.1002/j.1538-7305.1963.tb04003.x. [7] J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, Journal of the ACM (JACM), 27 (1980), 701-717.  doi: 10.1145/322217.322225. [8] M. Shi, X. Li, A. Neri and P. Solé, How many weights can a cyclic code have?, arXiv: 1807.08418, 15, November, 2018. [9] M. Shi, H. Zhu, P. Solé and G. D. Cohen, How many weights can a linear code have?, Des. Codes Cryptogr., (2018). doi: 10.1007/s10623-018-0488-z. [10] D. Slepian, A class of binary signaling alphabets, Bell Labs Technical Journal, 35 (1956), 203-234.  doi: 10.1002/j.1538-7305.1956.tb02379.x. [11] M. A. Tsfasman and S. G. Vlăduţ, Algebraic-geometric Codes, volume 58 of Mathematics and its Applications (Soviet Series), Kluwer Academic Publishers Group, Dordrecht, 1991. Translated from the Russian by the authors. doi: 10.1007/978-94-011-3810-9. [12] O. Veblen and J. W. Young, Projective Geometry, Vol. 1, Blaisdell Publishing Co. Ginn and Co. New York-Toronto-London, 1965.

Figures(3)