American Institute of Mathematical Sciences

Advanced
February  2021, 15(1): 191-206. doi: 10.3934/amc.2020052

Properties of sets of subspaces with constant intersection dimension

Lisa Hernandez Lucas ,

Department of Mathematics, Vrije Universiteit Brussel, Pleinlaan 2, 1050 Brussels, Belgium

* Corresponding author: Lisa Hernandez Lucas

Received  April 2019 Revised  October 2019 Published  January 2020

A $ (k,k-t) $-SCID (set of Subspaces with Constant Intersection Dimension) is a set of $ k $-dimensional vector spaces that have pairwise intersections of dimension $ k-t $. Let $ \mathcal{C} = \{\pi_1,\ldots,\pi_n\} $ be a $ (k,k-t) $-SCID. Define $ S: = \langle \pi_1, \ldots, \pi_n \rangle $ and $ I: = \langle \pi_i \cap \pi_j \mid 1 \leq i < j \leq n \rangle $. We establish several upper bounds for $ \dim S + \dim I $ in different situations. We give a spectrum result under certain conditions for $ n $, giving examples of $ (k,k-t) $-SCIDs reaching a large interval of values for $ \dim S + \dim I $.

Keywords: Coding theory, vector spaces, random network coding, subspace codes, SCID.
Mathematics Subject Classification: Primary: 51E20; Secondary: 05B25, 51E23, 94B60.
Citation: Lisa Hernandez Lucas. Properties of sets of subspaces with constant intersection dimension. Advances in Mathematics of Communications, 2021, 15 (1) : 191-206. doi: 10.3934/amc.2020052
References:
[1]

R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung, Network information flow, IEEE Trans. Inform. Theory, 46 (2000), 1204-1216.  doi: 10.1109/18.850663.  Google Scholar

[2]

R. D. Barrolleta, L. Storme, E. Suárez-Canedo and P. Vandendriessche, On primitive constant dimension codes and a geometrical sunflower bound, Adv. Math. Commun., 11 (2017), 757-765.  doi: 10.3934/amc.2017055.  Google Scholar

[3]

A. Beutelspacher, Partial spreads in finite projective spaces and partial designs, Math. Zeit., 145 (1975), 211-229.  doi: 10.1007/BF01215286.  Google Scholar

[4]

A. Beutelspacher and J. Ueberberg, A characteristic property of geometric $t$-spreads in finite projective spaces, Europ. J. Combin., 12 (1991), 277-281.  doi: 10.1016/S0195-6698(13)80110-2.  Google Scholar

[5]

J. Eisfeld, On sets of $n$-dimensional subspaces of projective spaces intersecting mutually in an $(n-2)$-dimensional subspace, Discrete Math., 255 (2002), 81-85.  doi: 10.1016/S0012-365X(01)00390-9.  Google Scholar

[6]

T. Etzion, Problems on $q$-analogs in coding theory, Preprint, arXiv: 1305.6126. Google Scholar

[7]

T. Etzion and N. Raviv, Equidistant codes in the Grassmannian, Discrete Appl. Math., 186 (2015), 87-97.  doi: 10.1016/j.dam.2015.01.024.  Google Scholar

[8]

E. Gorla and A. Ravagnani, Equidistant subspace codes, Linear Algebra Appl., 490 (2016), 48-65.   Google Scholar

[9]

T. Ho, M. Médard, R. Koetter, D. R. Karger, M. Effros, J. Shi and B. Leong, A random linear network coding approach to multicast, IEEE Trans. Inform. Theory, 52 (2006), 4413-4430.  doi: 10.1109/TIT.2006.881746.  Google Scholar

[10]

R. Kötter and F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3579-3591.  doi: 10.1109/TIT.2008.926449.  Google Scholar

[11]

M. Lavrauw and G. Van de Voorde, Field reduction and linear sets in finite geometry, Topics in finite fields, Contemp. Math., Amer. Math. Soc., Providence, RI, 632 (2015), 271-293.  doi: 10.1090/conm/632/12633.  Google Scholar

[12]

S.-Y. R. Li, R. W. Yeung and N. Cai, Linear network coding, IEEE Trans. Inform. Theory, 49 (2003), 371-381.  doi: 10.1109/TIT.2002.807285.  Google Scholar

[13]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. I, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.  Google Scholar

[14]

K. Metsch and L. Storme, Partial $t$-spreads in PG$(2t+1, q)$, Des. Codes Cryptogr., 18 (1999), 199-216.  doi: 10.1023/A:1008305824113.  Google Scholar

[15]

O. Polverino, Linear sets in finite projective spaces, Discrete Math., 310 (2010), 3096-3107.  doi: 10.1016/j.disc.2009.04.007.  Google Scholar

[16]

B. Segre, Teoria di Galois, fibrazioni proiettive e geometrie non desarguesiane, Ann. Mat. Pura Appl., 64 (1964), 1-76.  doi: 10.1007/BF02410047.  Google Scholar

[17]

C. E. Shannon, A mathematical theory of communication, Bell System Tech. J., 27 (1948), 379–423,623–656. doi: 10.1002/j.1538-7305.1948.tb01338.x.  Google Scholar

[18]

A. Weil, Adeles and Algebraic Groups, Progress in Mathematics, 23. Birkhäuser, Boston, Mass., 1982.  Google Scholar

show all references

References:
[1]

R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung, Network information flow, IEEE Trans. Inform. Theory, 46 (2000), 1204-1216.  doi: 10.1109/18.850663.  Google Scholar

[2]

R. D. Barrolleta, L. Storme, E. Suárez-Canedo and P. Vandendriessche, On primitive constant dimension codes and a geometrical sunflower bound, Adv. Math. Commun., 11 (2017), 757-765.  doi: 10.3934/amc.2017055.  Google Scholar

[3]

A. Beutelspacher, Partial spreads in finite projective spaces and partial designs, Math. Zeit., 145 (1975), 211-229.  doi: 10.1007/BF01215286.  Google Scholar

[4]

A. Beutelspacher and J. Ueberberg, A characteristic property of geometric $t$-spreads in finite projective spaces, Europ. J. Combin., 12 (1991), 277-281.  doi: 10.1016/S0195-6698(13)80110-2.  Google Scholar

[5]

J. Eisfeld, On sets of $n$-dimensional subspaces of projective spaces intersecting mutually in an $(n-2)$-dimensional subspace, Discrete Math., 255 (2002), 81-85.  doi: 10.1016/S0012-365X(01)00390-9.  Google Scholar

[6]

T. Etzion, Problems on $q$-analogs in coding theory, Preprint, arXiv: 1305.6126. Google Scholar

[7]

T. Etzion and N. Raviv, Equidistant codes in the Grassmannian, Discrete Appl. Math., 186 (2015), 87-97.  doi: 10.1016/j.dam.2015.01.024.  Google Scholar

[8]

E. Gorla and A. Ravagnani, Equidistant subspace codes, Linear Algebra Appl., 490 (2016), 48-65.   Google Scholar

[9]

T. Ho, M. Médard, R. Koetter, D. R. Karger, M. Effros, J. Shi and B. Leong, A random linear network coding approach to multicast, IEEE Trans. Inform. Theory, 52 (2006), 4413-4430.  doi: 10.1109/TIT.2006.881746.  Google Scholar

[10]

R. Kötter and F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3579-3591.  doi: 10.1109/TIT.2008.926449.  Google Scholar

[11]

M. Lavrauw and G. Van de Voorde, Field reduction and linear sets in finite geometry, Topics in finite fields, Contemp. Math., Amer. Math. Soc., Providence, RI, 632 (2015), 271-293.  doi: 10.1090/conm/632/12633.  Google Scholar

[12]

S.-Y. R. Li, R. W. Yeung and N. Cai, Linear network coding, IEEE Trans. Inform. Theory, 49 (2003), 371-381.  doi: 10.1109/TIT.2002.807285.  Google Scholar

[13]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. I, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.  Google Scholar

[14]

K. Metsch and L. Storme, Partial $t$-spreads in PG$(2t+1, q)$, Des. Codes Cryptogr., 18 (1999), 199-216.  doi: 10.1023/A:1008305824113.  Google Scholar

[15]

O. Polverino, Linear sets in finite projective spaces, Discrete Math., 310 (2010), 3096-3107.  doi: 10.1016/j.disc.2009.04.007.  Google Scholar

[16]

B. Segre, Teoria di Galois, fibrazioni proiettive e geometrie non desarguesiane, Ann. Mat. Pura Appl., 64 (1964), 1-76.  doi: 10.1007/BF02410047.  Google Scholar

[17]

C. E. Shannon, A mathematical theory of communication, Bell System Tech. J., 27 (1948), 379–423,623–656. doi: 10.1002/j.1538-7305.1948.tb01338.x.  Google Scholar

[18]

A. Weil, Adeles and Algebraic Groups, Progress in Mathematics, 23. Birkhäuser, Boston, Mass., 1982.  Google Scholar

Table 1.  Summary of the best bounds found for $\dim S +\dim I$, for different values of $n$, $k$ and $t$
Condition Upper bound $\dim S + \dim I$ Sharp? Theorem
$(k-t)(n-1) \leq k$ $nk$ yes Theorem 2.1 & 2.2
$k\geq 2t$, $n\geq 3$,$(k,n)\neq(2t,3)$ $2k+2(n-2)t-(n-3)$ unknown Theorem 2.5
$k <2t$ $(k-t)(n-1) > k$ $nk$ no Theorem 2.1 & 2.2
Table Options

Download as excel

Condition Upper bound $\dim S + \dim I$ Sharp? Theorem
$(k-t)(n-1) \leq k$ $nk$ yes Theorem 2.1 & 2.2
$k\geq 2t$, $n\geq 3$,$(k,n)\neq(2t,3)$ $2k+2(n-2)t-(n-3)$ unknown Theorem 2.5
$k <2t$ $(k-t)(n-1) > k$ $nk$ no Theorem 2.1 & 2.2
[1]

Keisuke Minami, Takahiro Matsuda, Tetsuya Takine, Taku Noguchi. Asynchronous multiple source network coding for wireless broadcasting. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 577-592. doi: 10.3934/naco.2011.1.577
[2]

Min Ye, Alexander Barg. Polar codes for distributed hierarchical source coding. Advances in Mathematics of Communications, 2015, 9 (1) : 87-103. doi: 10.3934/amc.2015.9.87
[3]

Stefan Martignoli, Ruedi Stoop. Phase-locking and Arnold coding in prototypical network topologies. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 145-162. doi: 10.3934/dcdsb.2008.9.145
[4]

Giuseppe Bianchi, Lorenzo Bracciale, Keren Censor-Hillel, Andrea Lincoln, Muriel Médard. The one-out-of-k retrieval problem and linear network coding. Advances in Mathematics of Communications, 2016, 10 (1) : 95-112. doi: 10.3934/amc.2016.10.95
[5]

T. Jäger. Neuronal coding of pacemaker neurons -- A random dynamical systems approach. Communications on Pure & Applied Analysis, 2011, 10 (3) : 995-1009. doi: 10.3934/cpaa.2011.10.995
[6]

Carla Mascia, Giancarlo Rinaldo, Massimiliano Sala. Hilbert quasi-polynomial for order domains and application to coding theory. Advances in Mathematics of Communications, 2018, 12 (2) : 287-301. doi: 10.3934/amc.2018018
[7]

Daniel Heinlein, Sascha Kurz. Binary subspace codes in small ambient spaces. Advances in Mathematics of Communications, 2018, 12 (4) : 817-839. doi: 10.3934/amc.2018048
[8]

Gokhan Calis, O. Ozan Koyluoglu. Architecture-aware coding for distributed storage: Repairable block failure resilient codes. Advances in Mathematics of Communications, 2018, 12 (3) : 465-503. doi: 10.3934/amc.2018028
[9]

Arseny Egorov. Morse coding for a Fuchsian group of finite covolume. Journal of Modern Dynamics, 2009, 3 (4) : 637-646. doi: 10.3934/jmd.2009.3.637
[10]

Miguel Mendes. A note on the coding of orbits in certain discontinuous maps. Discrete & Continuous Dynamical Systems, 2010, 27 (1) : 369-382. doi: 10.3934/dcds.2010.27.369
[11]

Maxim Sølund Kirsebom. Extreme value theory for random walks on homogeneous spaces. Discrete & Continuous Dynamical Systems, 2014, 34 (11) : 4689-4717. doi: 10.3934/dcds.2014.34.4689
[12]

Antonio Cossidente, Sascha Kurz, Giuseppe Marino, Francesco Pavese. Combining subspace codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021007
[13]

Vincent Astier, Thomas Unger. Galois extensions, positive involutions and an application to unitary space-time coding. Advances in Mathematics of Communications, 2019, 13 (3) : 513-516. doi: 10.3934/amc.2019032
[14]

Qian Guo, Thomas Johansson, Erik Mårtensson, Paul Stankovski Wagner. Some cryptanalytic and coding-theoretic applications of a soft stern algorithm. Advances in Mathematics of Communications, 2019, 13 (4) : 559-578. doi: 10.3934/amc.2019035
[15]

Shinsuke Koyama, Lubomir Kostal. The effect of interspike interval statistics on the information gain under the rate coding hypothesis. Mathematical Biosciences & Engineering, 2014, 11 (1) : 63-80. doi: 10.3934/mbe.2014.11.63
[16]

Angela Aguglia, Antonio Cossidente, Giuseppe Marino, Francesco Pavese, Alessandro Siciliano. Orbit codes from forms on vector spaces over a finite field. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020105
[17]

Heide Gluesing-Luerssen, Carolyn Troha. Construction of subspace codes through linkage. Advances in Mathematics of Communications, 2016, 10 (3) : 525-540. doi: 10.3934/amc.2016023
[18]

Ernst M. Gabidulin, Pierre Loidreau. Properties of subspace subcodes of Gabidulin codes. Advances in Mathematics of Communications, 2008, 2 (2) : 147-157. doi: 10.3934/amc.2008.2.147
[19]

Georgy L. Alfimov, Pavel P. Kizin, Dmitry A. Zezyulin. Gap solitons for the repulsive Gross-Pitaevskii equation with periodic potential: Coding and method for computation. Discrete & Continuous Dynamical Systems - B, 2017, 22 (4) : 1207-1229. doi: 10.3934/dcdsb.2017059
[20]

Lassi Roininen, Markku S. Lehtinen. Perfect pulse-compression coding via ARMA algorithms and unimodular transfer functions. Inverse Problems & Imaging, 2013, 7 (2) : 649-661. doi: 10.3934/ipi.2013.7.649

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (238)
  • HTML views (491)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences