
-
Previous Article
Low-density and high-density asymmetric CT-burst correcting integer codes
- AMC Home
- This Issue
-
Next Article
Constructions for several classes of few-weight linear codes and their applications
Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.
Readers can access Online First articles via the “Online First” tab for the selected journal.
Minimal codewords arising from the incidence of points and hyperplanes in projective spaces
1. | Dipartimento di Matematica e Informatica, Università degli studi di Perugia, Perugia, Italy |
2. | Department of Mathematics: Analysis, Logic and Discrete Mathematics, Ghent University, Ghent, Belgium |
Over the past few years, the codes $ {\mathcal{C}}_{n-1}(n,q) $ arising from the incidence of points and hyperplanes in the projective space $ {\rm{PG}}(n,q) $ attracted a lot of attention. In particular, small weight codewords of $ {\mathcal{C}}_{n-1}(n,q) $ are a topic of investigation. The main result of this work states that, if $ q $ is large enough and not prime, a codeword having weight smaller than roughly $ \frac{1}{2^{n-2}}q^{n-1}\sqrt{q} $ can be written as a linear combination of a few hyperplanes. Consequently, we use this result to provide a graph-theoretical sufficient condition for these codewords of small weight to be minimal.
References:
[1] |
S. Adriaensen and L. Denaux,
Small weight codewords of projective geometric codes, J. Combin. Theory Ser. A, 180 (2021), 105395.
doi: 10.1016/j.jcta.2020.105395. |
[2] |
S. Adriaensen, L. Denaux, L. Storme and Z. Weiner,
Small weight code words arising from the incidence of points and hyperplanes in $ \rm PG $$(n,q)$, Des. Codes Cryptogr., 88 (2020), 771-788.
doi: 10.1007/s10623-019-00710-0. |
[3] |
A. Ashikhmin and A. Barg,
Minimal vectors in linear codes, IEEE Trans. Inform. Theory, 44 (1998), 2010-2017.
doi: 10.1109/18.705584. |
[4] |
E. F. Assmus and J. D. Key, Designs and Their Codes, Cambridge University Press, 1992.
doi: 10.1017/CBO9781316529836.![]() ![]() ![]() |
[5] |
B. Bagchi and S. P. Inamdar,
Projective geometric codes, J. Combin. Theory Ser. A, 99 (2002), 128-142.
doi: 10.1006/jcta.2002.3265. |
[6] |
D. Bartoli and M. Bonini,
Minimal linear codes in odd characteristic, IEEE Trans. Inform. Theory, 65 (2019), 4152-4155.
doi: 10.1109/TIT.2019.2891992. |
[7] |
E. Berlekamp, R. McEliece and H. van Tilborg,
On the inherent intractability of certain coding problems (corresp.), IEEE Trans. Inform. Theory, 24 (1978), 384-386.
doi: 10.1109/tit.1978.1055873. |
[8] |
G. R. Blakley, Safeguarding cryptographic keys, International Workshop on Managing Requirements Knowledge (MARK), (1979), 313–317.
doi: 10.1109/MARK.1979.8817296. |
[9] |
M. Bonini and M. Borello,
Minimal linear codes arising from blocking sets, J. Algebraic Combin., 53 (2021), 327-341.
doi: 10.1007/s10801-019-00930-6. |
[10] |
J. Bruck and M. Naor,
The hardness of decoding linear codes with preprocessing, IEEE Trans. Inform. Theory, 36 (1990), 381-385.
doi: 10.1109/18.52484. |
[11] |
H. Chabanne, G. D. Cohen and A. Patey,
Towards secure two-party computation from the wire-tap channel, Information Security and Cryptology – ICISC 2013, 8565 (2014), 34-46.
doi: 10.1007/978-3-319-12160-4_3. |
[12] |
K. Chouinard, Weight distributions of codes from finite planes, Ph.D thesis, University of Virginia. |
[13] |
G. D. Cohen, S. Mesnager and A. Patey,
On minimal and quasi-minimal linear codes, Cryptography and Coding, 8308 (2013), 85-98.
doi: 10.1007/978-3-642-45239-0_6. |
[14] |
C. Ding, Z. Heng and Z. Zhou,
Minimal binary linear codes, IEEE Trans. Inform. Theory, 64 (2018), 6536-6545.
doi: 10.1109/TIT.2018.2819196. |
[15] |
V. Fack, S. L. Fancsali, L. Storme, G. Van de Voorde and J. Winne,
Small weight codewords in the codes arising from Desarguesian projective planes, Des. Codes Cryptogr., 46 (2008), 25-43.
doi: 10.1007/s10623-007-9126-x. |
[16] |
Z. Heng, C. Ding and Z. Zhou,
Minimal linear codes over finite fields, Finite Fields Appl., 54 (2018), 176-196.
doi: 10.1016/j.ffa.2018.08.010. |
[17] |
M. Lavrauw, L. Storme, P. Sziklai and G. Van de Voorde,
An empty interval in the spectrum of small weight codewords in the code from points and $k$-spaces of ${\rm{PG}}(n, q)$, J. Combin. Theory Ser. A, 116 (2009), 996-1001.
doi: 10.1016/j.jcta.2008.09.004. |
[18] |
M. Lavrauw, L. Storme and G. Van de Voorde, Linear codes from projective spaces, Error-Correcting Codes, Finite Geometries and Cryptography, Contemp. Math., Amer. Math. Soc., Providence, RI, 523 (2010), 185–202.
doi: 10.1090/conm/523/10326. |
[19] |
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. II, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977 |
[20] |
J. L. Massey, Minimal codewords and secret sharing, Proc. 6th Joint Swedish-Russian Int. Workshop on Info. Theory, (1993), 276–279. |
[21] |
J. L. Massey, Some applications of coding theory in cryptography, Codes and Cyphers: Cryptography and Coding IV, (1995), 33–47. |
[22] |
O. Polverino and F. Zullo,
Codes arising from incidence matrices of points and hyperplanes in $ {\rm{PG}}(n, q)$, J. Combin. Theory Ser. A, 158 (2018), 1-11.
doi: 10.1016/j.jcta.2018.03.013. |
[23] |
L. D. Rudolph, A class of majority logic decodable codes, IEEE Trans. Inform. Theory, 13 (1967), 305–307, www.scopus.com, Cited By : 81. |
[24] |
A. Shamir,
How to share a secret, Commun. ACM., 22 (1979), 612-613.
doi: 10.1145/359168.359176. |
[25] |
T. Szőnyi and Z. Weiner,
Stability of $k\bmod p$ multisets and small weight codewords of the code generated by the lines of PG(2, $q$), J. Combin. Theory Ser. A, 157 (2018), 321-333.
doi: 10.1016/j.jcta.2018.02.005. |
[26] |
J. Yuan and C. Ding,
Secret sharing schemes from three classes of linear codes, IEEE Trans. Inform. Theory, 52 (2006), 206-212.
doi: 10.1109/TIT.2005.860412. |
show all references
References:
[1] |
S. Adriaensen and L. Denaux,
Small weight codewords of projective geometric codes, J. Combin. Theory Ser. A, 180 (2021), 105395.
doi: 10.1016/j.jcta.2020.105395. |
[2] |
S. Adriaensen, L. Denaux, L. Storme and Z. Weiner,
Small weight code words arising from the incidence of points and hyperplanes in $ \rm PG $$(n,q)$, Des. Codes Cryptogr., 88 (2020), 771-788.
doi: 10.1007/s10623-019-00710-0. |
[3] |
A. Ashikhmin and A. Barg,
Minimal vectors in linear codes, IEEE Trans. Inform. Theory, 44 (1998), 2010-2017.
doi: 10.1109/18.705584. |
[4] |
E. F. Assmus and J. D. Key, Designs and Their Codes, Cambridge University Press, 1992.
doi: 10.1017/CBO9781316529836.![]() ![]() ![]() |
[5] |
B. Bagchi and S. P. Inamdar,
Projective geometric codes, J. Combin. Theory Ser. A, 99 (2002), 128-142.
doi: 10.1006/jcta.2002.3265. |
[6] |
D. Bartoli and M. Bonini,
Minimal linear codes in odd characteristic, IEEE Trans. Inform. Theory, 65 (2019), 4152-4155.
doi: 10.1109/TIT.2019.2891992. |
[7] |
E. Berlekamp, R. McEliece and H. van Tilborg,
On the inherent intractability of certain coding problems (corresp.), IEEE Trans. Inform. Theory, 24 (1978), 384-386.
doi: 10.1109/tit.1978.1055873. |
[8] |
G. R. Blakley, Safeguarding cryptographic keys, International Workshop on Managing Requirements Knowledge (MARK), (1979), 313–317.
doi: 10.1109/MARK.1979.8817296. |
[9] |
M. Bonini and M. Borello,
Minimal linear codes arising from blocking sets, J. Algebraic Combin., 53 (2021), 327-341.
doi: 10.1007/s10801-019-00930-6. |
[10] |
J. Bruck and M. Naor,
The hardness of decoding linear codes with preprocessing, IEEE Trans. Inform. Theory, 36 (1990), 381-385.
doi: 10.1109/18.52484. |
[11] |
H. Chabanne, G. D. Cohen and A. Patey,
Towards secure two-party computation from the wire-tap channel, Information Security and Cryptology – ICISC 2013, 8565 (2014), 34-46.
doi: 10.1007/978-3-319-12160-4_3. |
[12] |
K. Chouinard, Weight distributions of codes from finite planes, Ph.D thesis, University of Virginia. |
[13] |
G. D. Cohen, S. Mesnager and A. Patey,
On minimal and quasi-minimal linear codes, Cryptography and Coding, 8308 (2013), 85-98.
doi: 10.1007/978-3-642-45239-0_6. |
[14] |
C. Ding, Z. Heng and Z. Zhou,
Minimal binary linear codes, IEEE Trans. Inform. Theory, 64 (2018), 6536-6545.
doi: 10.1109/TIT.2018.2819196. |
[15] |
V. Fack, S. L. Fancsali, L. Storme, G. Van de Voorde and J. Winne,
Small weight codewords in the codes arising from Desarguesian projective planes, Des. Codes Cryptogr., 46 (2008), 25-43.
doi: 10.1007/s10623-007-9126-x. |
[16] |
Z. Heng, C. Ding and Z. Zhou,
Minimal linear codes over finite fields, Finite Fields Appl., 54 (2018), 176-196.
doi: 10.1016/j.ffa.2018.08.010. |
[17] |
M. Lavrauw, L. Storme, P. Sziklai and G. Van de Voorde,
An empty interval in the spectrum of small weight codewords in the code from points and $k$-spaces of ${\rm{PG}}(n, q)$, J. Combin. Theory Ser. A, 116 (2009), 996-1001.
doi: 10.1016/j.jcta.2008.09.004. |
[18] |
M. Lavrauw, L. Storme and G. Van de Voorde, Linear codes from projective spaces, Error-Correcting Codes, Finite Geometries and Cryptography, Contemp. Math., Amer. Math. Soc., Providence, RI, 523 (2010), 185–202.
doi: 10.1090/conm/523/10326. |
[19] |
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. II, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977 |
[20] |
J. L. Massey, Minimal codewords and secret sharing, Proc. 6th Joint Swedish-Russian Int. Workshop on Info. Theory, (1993), 276–279. |
[21] |
J. L. Massey, Some applications of coding theory in cryptography, Codes and Cyphers: Cryptography and Coding IV, (1995), 33–47. |
[22] |
O. Polverino and F. Zullo,
Codes arising from incidence matrices of points and hyperplanes in $ {\rm{PG}}(n, q)$, J. Combin. Theory Ser. A, 158 (2018), 1-11.
doi: 10.1016/j.jcta.2018.03.013. |
[23] |
L. D. Rudolph, A class of majority logic decodable codes, IEEE Trans. Inform. Theory, 13 (1967), 305–307, www.scopus.com, Cited By : 81. |
[24] |
A. Shamir,
How to share a secret, Commun. ACM., 22 (1979), 612-613.
doi: 10.1145/359168.359176. |
[25] |
T. Szőnyi and Z. Weiner,
Stability of $k\bmod p$ multisets and small weight codewords of the code generated by the lines of PG(2, $q$), J. Combin. Theory Ser. A, 157 (2018), 321-333.
doi: 10.1016/j.jcta.2018.02.005. |
[26] |
J. Yuan and C. Ding,
Secret sharing schemes from three classes of linear codes, IEEE Trans. Inform. Theory, 52 (2006), 206-212.
doi: 10.1109/TIT.2005.860412. |


[1] |
Romar dela Cruz, Michael Kiermaier, Sascha Kurz, Alfred Wassermann. On the minimum number of minimal codewords. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2020130 |
[2] |
Linda Beukemann, Klaus Metsch, Leo Storme. On weighted minihypers in finite projective spaces of square order. Advances in Mathematics of Communications, 2015, 9 (3) : 291-309. doi: 10.3934/amc.2015.9.291 |
[3] |
Kristian Bjerklöv, Russell Johnson. Minimal subsets of projective flows. Discrete and Continuous Dynamical Systems - B, 2008, 9 (3&4, May) : 493-516. doi: 10.3934/dcdsb.2008.9.493 |
[4] |
Irene Márquez-Corbella, Edgar Martínez-Moro. Algebraic structure of the minimal support codewords set of some linear codes. Advances in Mathematics of Communications, 2011, 5 (2) : 233-244. doi: 10.3934/amc.2011.5.233 |
[5] |
Daniele Bartoli, Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Multiple coverings of the farthest-off points with small density from projective geometry. Advances in Mathematics of Communications, 2015, 9 (1) : 63-85. doi: 10.3934/amc.2015.9.63 |
[6] |
J. C. Alvarez Paiva and E. Fernandes. Crofton formulas in projective Finsler spaces. Electronic Research Announcements, 1998, 4: 91-100. |
[7] |
Carlos Durán, Diego Otero. The projective Cartan-Klein geometry of the Helmholtz conditions. Journal of Geometric Mechanics, 2018, 10 (1) : 69-92. doi: 10.3934/jgm.2018003 |
[8] |
Andreas Klein, Leo Storme. On the non-minimality of the largest weight codewords in the binary Reed-Muller codes. Advances in Mathematics of Communications, 2011, 5 (2) : 333-337. doi: 10.3934/amc.2011.5.333 |
[9] |
Thomas Honold, Ivan Landjev. The dual construction for arcs in projective Hjelmslev spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 11-21. doi: 10.3934/amc.2011.5.11 |
[10] |
Domenico Mucci. Maps into projective spaces: Liquid crystal and conformal energies. Discrete and Continuous Dynamical Systems - B, 2012, 17 (2) : 597-635. doi: 10.3934/dcdsb.2012.17.597 |
[11] |
Carlos Durán, Diego Otero. The projective symplectic geometry of higher order variational problems: Minimality conditions. Journal of Geometric Mechanics, 2016, 8 (3) : 305-322. doi: 10.3934/jgm.2016009 |
[12] |
Meng Chen, Yong Hu, Matteo Penegini. On projective threefolds of general type with small positive geometric genus. Electronic Research Archive, 2021, 29 (3) : 2293-2323. doi: 10.3934/era.2020117 |
[13] |
Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119 |
[14] |
Hiromichi Nakayama, Takeo Noda. Minimal sets and chain recurrent sets of projective flows induced from minimal flows on $3$-manifolds. Discrete and Continuous Dynamical Systems, 2005, 12 (4) : 629-638. doi: 10.3934/dcds.2005.12.629 |
[15] |
Jungkai A. Chen and Meng Chen. On projective threefolds of general type. Electronic Research Announcements, 2007, 14: 69-73. doi: 10.3934/era.2007.14.69 |
[16] |
Liliana Trejo-Valencia, Edgardo Ugalde. Projective distance and $g$-measures. Discrete and Continuous Dynamical Systems - B, 2015, 20 (10) : 3565-3579. doi: 10.3934/dcdsb.2015.20.3565 |
[17] |
Roland Hildebrand. Barriers on projective convex sets. Conference Publications, 2011, 2011 (Special) : 672-683. doi: 10.3934/proc.2011.2011.672 |
[18] |
Juan Carlos Fernández, Oscar Palmas, Jimmy Petean. Supercritical elliptic problems on the round sphere and nodal solutions to the Yamabe problem in projective spaces. Discrete and Continuous Dynamical Systems, 2020, 40 (4) : 2495-2514. doi: 10.3934/dcds.2020123 |
[19] |
Daniele Bartoli, Adnen Sboui, Leo Storme. Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Advances in Mathematics of Communications, 2016, 10 (2) : 355-365. doi: 10.3934/amc.2016010 |
[20] |
Mickaël Crampon. Entropies of strictly convex projective manifolds. Journal of Modern Dynamics, 2009, 3 (4) : 511-547. doi: 10.3934/jmd.2009.3.511 |
2020 Impact Factor: 0.935
Tools
Metrics
Other articles
by authors
[Back to Top]