May  2018, 12(2): 317-336. doi: 10.3934/amc.2018020

Locally recoverable codes with availability t≥2 from fiber products of curves

1. 

Department of Mathematics and Statistics, Villanova University, Villanova, PA 19085, USA

2. 

Department of Mathematics and Computer Science, Colorado College, Colorado Springs, CO 80903, USA

3. 

Department of Mathematical Sciences, Clemson University, Clemson, SC 29634, USA

* Corresponding author: Beth Malmskog

Received  December 2016 Revised  September 2017 Published  March 2018

Fund Project: The second author is supported by NSA grant H98230-16-1-0300.

We generalize the construction of locally recoverable codes on algebraic curves given by Barg, Tamo and Vlăduţ [4] to those with arbitrarily many recovery sets by exploiting the structure of fiber products of curves. Employing maximal curves, we create several new families of locally recoverable codes with multiple recovery sets, including codes with two recovery sets from the generalized Giulietti and Korchmáros (GK) curves and the Suzuki curves, and new locally recoverable codes with many recovery sets based on the Hermitian curve, using a fiber product construction of van der Geer and van der Vlugt. In addition, we consider the relationship between local error recovery and global error correction as well as the availability required to locally recover any pattern of a fixed number of erasures.

Citation: Kathryn Haymaker, Beth Malmskog, Gretchen L. Matthews. Locally recoverable codes with availability t≥2 from fiber products of curves. Advances in Mathematics of Communications, 2018, 12 (2) : 317-336. doi: 10.3934/amc.2018020
References:
[1]

M. AbdónJ. Bezerra and L. Quoos, Further examples of maximal curves, Journal of Pure and Applied Algebra, 213 (2009), 1192-1196.  doi: 10.1016/j.jpaa.2008.11.037.

[2]

E. Ballico and A. Ravagnani, Embedding Suzuki curves in $\Bbb P^4$, Journal of Commutative Algebra, 7 (2015), 149-166.  doi: 10.1216/JCA-2015-7-2-149.

[3]

A. Barg, K. Haymaker, E. W. Howe, G. L. Matthews and A. Várilly-Alvarado, Locally recoverable codes from algebraic curves and surfaces, Algebraic Geometry for Coding Theory and Cryptography, (2017), 95–127, arXiv: 1701.05212. doi: 10.1007/978-3-319-63931-4_4.

[4]

A. Barg, I. Tamo and S. Vlădut¸, Locally recoverable codes on algebraic curves, Proceedings of the IEEE Int. Symp. Info. Theory, (2015), 1252–1256, Extended version: arXiv: 1603.08876. doi: 10.1109/ISIT.2015.7282656.

[5]

A. Eid and I. Duursma, Smooth embeddings for the Suzuki and Ree curves, Proceedings of the conference on Arithmetic, Geometry and Coding Theory (AGCT 2013), Contemporary Mathematics Series (AMS), 637 (2015), 251–291.

[6]

A. GarciaC. Güneri and H. Stichtenoth, A generalization of the Giulietti-Korchmáros maximal curve, Advances in Geometry, 10 (2010), 427-434. 

[7]

M. Giulietti and G. Korchmáros, A new family of maximal curves over a finite field, Math. Ann., 343 (2009), 229-245.  doi: 10.1007/s00208-008-0270-z.

[8]

M. GiuliettiG. Korchmáros and F. Torres, Quotient curves of the Suzuki curve, Acta Arithmetica, 122 (2006), 245-274.  doi: 10.4064/aa122-3-3.

[9]

R. GuralnickB. Malmskog and R. Pries, The automorphism groups of a family of maximal curves, Journal of Algebra, 361 (2012), 92-106.  doi: 10.1016/j.jalgebra.2012.03.036.

[10]

J. Hansen, Deligne-Lusztig varieties and group codes, in Coding Theory and Algebraic Geometry, Lecture Notes in Mathematics, 1518 (1992), 63–81.

[11]

Q. Liu, Algebraic Geometry and Arithmetic Curves, Oxford Graduate Texts in Mathematics, 2002.

[12]

H.-G. Rück and H. Stichtenoth, A characterization of Hermitian function fields over finite fields, J. Reine Angew. Math., 457 (1994), 185-188. 

[13]

H. Stichtenoth, Algebraic Function Fields and Codes, Springer-Verlag, Berlin, 2009.

[14]

G. van der Geer and M. van der Vlugt, How to construct curves over finite fields with many points, in Arithmetic Geometry (Cortona, 1994), Symposia Mathematica Cambridge: Cambridge University Press, 37 (1997), 169–189.

show all references

References:
[1]

M. AbdónJ. Bezerra and L. Quoos, Further examples of maximal curves, Journal of Pure and Applied Algebra, 213 (2009), 1192-1196.  doi: 10.1016/j.jpaa.2008.11.037.

[2]

E. Ballico and A. Ravagnani, Embedding Suzuki curves in $\Bbb P^4$, Journal of Commutative Algebra, 7 (2015), 149-166.  doi: 10.1216/JCA-2015-7-2-149.

[3]

A. Barg, K. Haymaker, E. W. Howe, G. L. Matthews and A. Várilly-Alvarado, Locally recoverable codes from algebraic curves and surfaces, Algebraic Geometry for Coding Theory and Cryptography, (2017), 95–127, arXiv: 1701.05212. doi: 10.1007/978-3-319-63931-4_4.

[4]

A. Barg, I. Tamo and S. Vlădut¸, Locally recoverable codes on algebraic curves, Proceedings of the IEEE Int. Symp. Info. Theory, (2015), 1252–1256, Extended version: arXiv: 1603.08876. doi: 10.1109/ISIT.2015.7282656.

[5]

A. Eid and I. Duursma, Smooth embeddings for the Suzuki and Ree curves, Proceedings of the conference on Arithmetic, Geometry and Coding Theory (AGCT 2013), Contemporary Mathematics Series (AMS), 637 (2015), 251–291.

[6]

A. GarciaC. Güneri and H. Stichtenoth, A generalization of the Giulietti-Korchmáros maximal curve, Advances in Geometry, 10 (2010), 427-434. 

[7]

M. Giulietti and G. Korchmáros, A new family of maximal curves over a finite field, Math. Ann., 343 (2009), 229-245.  doi: 10.1007/s00208-008-0270-z.

[8]

M. GiuliettiG. Korchmáros and F. Torres, Quotient curves of the Suzuki curve, Acta Arithmetica, 122 (2006), 245-274.  doi: 10.4064/aa122-3-3.

[9]

R. GuralnickB. Malmskog and R. Pries, The automorphism groups of a family of maximal curves, Journal of Algebra, 361 (2012), 92-106.  doi: 10.1016/j.jalgebra.2012.03.036.

[10]

J. Hansen, Deligne-Lusztig varieties and group codes, in Coding Theory and Algebraic Geometry, Lecture Notes in Mathematics, 1518 (1992), 63–81.

[11]

Q. Liu, Algebraic Geometry and Arithmetic Curves, Oxford Graduate Texts in Mathematics, 2002.

[12]

H.-G. Rück and H. Stichtenoth, A characterization of Hermitian function fields over finite fields, J. Reine Angew. Math., 457 (1994), 185-188. 

[13]

H. Stichtenoth, Algebraic Function Fields and Codes, Springer-Verlag, Berlin, 2009.

[14]

G. van der Geer and M. van der Vlugt, How to construct curves over finite fields with many points, in Arithmetic Geometry (Cortona, 1994), Symposia Mathematica Cambridge: Cambridge University Press, 37 (1997), 169–189.

Figure 1.  A visualization of points on a fiber product of two curves. Points on the fiber product $\mathcal{X}$ may be thought of as tuples of points on the curves $\mathcal{Y}_1$ and $\mathcal{Y}_2$ which lie above the same point on $\mathcal{Y}$.
Figure 2.  The fiber product $\mathcal{X}$ of $t$ curves $\mathcal{Y}_j$.
Figure 3.  Function fields associated with the fiber product.
Figure 4.  Generalized GK curve as a fiber product.
Figure 5.  Suzuki curve and its quotients used for constructing LRC(2) with balanced recovery sets.
Figure 6.  Curves for locally recoverable codes with availability $t$.
Table 1.  The generalized GK curves $\mathcal{C}_3$ over $\mathbb{F}_{729}$ produce LRC(2)s of length $n = 6048$, with $N = 3$, $q = 3$, $r_1 = 6$, $r_2 = 2$, and $D = l\infty_y$, with $l$ determining $k$ and $d$ as above.
$l$ $k$ $d\geq$
270 3252 215
260 3132 425
250 3012 635
240 2892 845
230 2772 1055
220 2652 1265
210 2532 1475
$l$ $k$ $d\geq$
270 3252 215
260 3132 425
250 3012 635
240 2892 845
230 2772 1055
220 2652 1265
210 2532 1475
[1]

Valentina Casarino, Paolo Ciatti, Silvia Secco. Product structures and fractional integration along curves in the space. Discrete and Continuous Dynamical Systems - S, 2013, 6 (3) : 619-635. doi: 10.3934/dcdss.2013.6.619

[2]

Joseph H. Silverman. Local-global aspects of (hyper)elliptic curves over (in)finite fields. Advances in Mathematics of Communications, 2010, 4 (2) : 101-114. doi: 10.3934/amc.2010.4.101

[3]

Eric Todd Quinto, Hans Rullgård. Local singularity reconstruction from integrals over curves in $\mathbb{R}^3$. Inverse Problems and Imaging, 2013, 7 (2) : 585-609. doi: 10.3934/ipi.2013.7.585

[4]

Stefano Marò. Relativistic pendulum and invariant curves. Discrete and Continuous Dynamical Systems, 2015, 35 (3) : 1139-1162. doi: 10.3934/dcds.2015.35.1139

[5]

Gian-Italo Bischi, Laura Gardini, Fabio Tramontana. Bifurcation curves in discontinuous maps. Discrete and Continuous Dynamical Systems - B, 2010, 13 (2) : 249-267. doi: 10.3934/dcdsb.2010.13.249

[6]

Carlos Munuera, Alonso Sepúlveda, Fernando Torres. Castle curves and codes. Advances in Mathematics of Communications, 2009, 3 (4) : 399-408. doi: 10.3934/amc.2009.3.399

[7]

Vladimir Georgiev, Eugene Stepanov. Metric cycles, curves and solenoids. Discrete and Continuous Dynamical Systems, 2014, 34 (4) : 1443-1463. doi: 10.3934/dcds.2014.34.1443

[8]

Martin Möller. Shimura and Teichmüller curves. Journal of Modern Dynamics, 2011, 5 (1) : 1-32. doi: 10.3934/jmd.2011.5.1

[9]

Lawrence Ein, Wenbo Niu, Jinhyung Park. On blowup of secant varieties of curves. Electronic Research Archive, 2021, 29 (6) : 3649-3654. doi: 10.3934/era.2021055

[10]

Philip N. J. Eagle, Steven D. Galbraith, John B. Ong. Point compression for Koblitz elliptic curves. Advances in Mathematics of Communications, 2011, 5 (1) : 1-10. doi: 10.3934/amc.2011.5.1

[11]

Adrian Tudorascu. On absolutely continuous curves of probabilities on the line. Discrete and Continuous Dynamical Systems, 2019, 39 (9) : 5105-5124. doi: 10.3934/dcds.2019207

[12]

Nicholas Hoell, Guillaume Bal. Ray transforms on a conformal class of curves. Inverse Problems and Imaging, 2014, 8 (1) : 103-125. doi: 10.3934/ipi.2014.8.103

[13]

M. J. Jacobson, R. Scheidler, A. Stein. Cryptographic protocols on real hyperelliptic curves. Advances in Mathematics of Communications, 2007, 1 (2) : 197-221. doi: 10.3934/amc.2007.1.197

[14]

Philip Korman. Curves of equiharmonic solutions, and problems at resonance. Discrete and Continuous Dynamical Systems, 2014, 34 (7) : 2847-2860. doi: 10.3934/dcds.2014.34.2847

[15]

Michael Khanevsky. Non-autonomous curves on surfaces. Journal of Modern Dynamics, 2021, 17: 305-317. doi: 10.3934/jmd.2021010

[16]

Nazar Arakelian, Saeed Tafazolian, Fernando Torres. On the spectrum for the genera of maximal curves over small fields. Advances in Mathematics of Communications, 2018, 12 (1) : 143-149. doi: 10.3934/amc.2018009

[17]

Koichi Osaki, Hirotoshi Satoh, Shigetoshi Yazaki. Towards modelling spiral motion of open plane curves. Discrete and Continuous Dynamical Systems - S, 2015, 8 (5) : 1009-1022. doi: 10.3934/dcdss.2015.8.1009

[18]

Stefania Fanali, Massimo Giulietti, Irene Platoni. On maximal curves over finite fields of small order. Advances in Mathematics of Communications, 2012, 6 (1) : 107-120. doi: 10.3934/amc.2012.6.107

[19]

Knut Hüper, Irina Markina, Fátima Silva Leite. A Lagrangian approach to extremal curves on Stiefel manifolds. Journal of Geometric Mechanics, 2021, 13 (1) : 55-72. doi: 10.3934/jgm.2020031

[20]

Chuangqiang Hu, Shudi Yang. Multi-point codes from the GGS curves. Advances in Mathematics of Communications, 2020, 14 (2) : 279-299. doi: 10.3934/amc.2020020

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (272)
  • HTML views (291)
  • Cited by (4)

[Back to Top]