American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2021061
Online First

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

Daniele Bartoli 1, and  Lins Denaux 2,,

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

*Corresponding author

Received  September 2021 Revised  October 2021 Early access December 2021

Fund Project: The research of Daniele Bartoli is supported by the Italian National Group for Algebraic and Geometric Structures and their Applications (GNSAGA - INdAM)

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.

Keywords: Finite projective geometry, Projective spaces, Coding theory, Small weight codewords, Minimal codewords.
Mathematics Subject Classification: Primary: 05B25, 94B05; Secondary: 94A62.
Citation: Daniele Bartoli, Lins Denaux. Minimal codewords arising from the incidence of points and hyperplanes in projective spaces. Advances in Mathematics of Communications, doi: 10.3934/amc.2021061
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.

Figure 1.  The application of Construction 3.5 to an example codeword $ c\in {\mathcal{C}}_1(2,q) $ of weight $ 9q-12 $. More specifically, we consider nine lines of $ {\rm{PG}}(2,q) $ and define the codeword $ c: = \alpha(a_0-a_1-a_2)+2\alpha\,\widetilde{a}+\beta(b_0-b_1-b_2-b_3)+3\beta\,\widetilde{b} $. For this specific example, we assume $ q $ not prime, $ q \geqslant529 $ if $ h = 2 $ (to be able to apply Result 1.3) and $ q \geqslant125 $, $ p\notin\{2,3,7,11,13\} $, if $ h>2 $. Furthermore, $ \alpha,\beta\in{\mathbb{F}}_q^* $ are two non-zero elements such that $ 3\alpha+4\beta = 0 $. Lines are clustered in four 'stages', each of which consists of 'clustering' the lines by following the rule of thumb described in Construction 3.5. Holes that are about to 'merge' clusters are indicated by squares instead of circles. In the first stage (top left), every line forms its own cluster. In the second stage (top right), the solid bold lines form one cluster, as well as the dashed bold lines; the remaining lines $ \widetilde{a} $ and $ \widetilde{b} $ form two clusters on their own. In the third stage (bottom left), the line $ \widetilde{a} $ gets merged into the solid bold cluster and the line $ \widetilde{b} $ gets merged into the dashed bold cluster. Finally, in the last stage (bottom right), both clusters get merged into one. To explain more clearly how this merging process works, consider the point $ A $ in the second stage. At this stage, $ A $ belongs to both the support of the solid bold line cluster $ \{a_0,a_1,a_2\} $ (with non-zero value $ -2\alpha $) and the support of the cluster $ \{\widetilde{a}\} $ (with non-zero value $ 2\alpha $), and thus meets Property $ 2. $ of Definition 3.4. Moreover, $ A $ is a hole of $ c $, as well as a hole of $ {{c}}_{|{{\mathcal{V}}}} $ for every other cluster (and therefore fulfils Property $ 1. $ and $ 3. $ of Definition 3.4). Hence, the clusters $ \{a_0,a_1,a_2\} $ and $ \{\widetilde{a}\} $ are adjacent and thus will get merged in the next stage as Construction 3.5 prescribes.
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  An example of a codeword $ c\in {\mathcal{C}}_1(2,q) $, $ p>3 $, that proves the sharpness of the bound of Theorem 3.8 for the case $ n = 2 $, $ |{\mathbb{H}}_c^\infty| = 3 $ (see Theorem 3.10)
Figure Options

Download full-size image

Download as PowerPoint slide

[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

  • PDF downloads (242)
  • HTML views (161)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy