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 & Continuous Dynamical Systems - S, 2013, 6 (3) : 619-635. doi: 10.3934/dcdss.2013.6.619

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

Gilberto Bini, Margarida Melo, Filippo Viviani. On GIT quotients of Hilbert and Chow schemes of curves. Electronic Research Announcements, 2012, 19: 33-40. doi: 10.3934/era.2012.19.33

[16]

Alice Silverberg. Some remarks on primality proving and elliptic curves. Advances in Mathematics of Communications, 2014, 8 (4) : 427-436. doi: 10.3934/amc.2014.8.427

[17]

Michael J. Jacobson, Jr., Monireh Rezai Rad, Renate Scheidler. Comparison of scalar multiplication on real hyperelliptic curves. Advances in Mathematics of Communications, 2014, 8 (4) : 389-406. doi: 10.3934/amc.2014.8.389

[18]

Leonardo Mora. Homoclinic bifurcations, fat attractors and invariant curves. Discrete & Continuous Dynamical Systems - A, 2003, 9 (5) : 1133-1148. doi: 10.3934/dcds.2003.9.1133

[19]

Farid Tari. Geometric properties of the integral curves of an implicit differential equation. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 349-364. doi: 10.3934/dcds.2007.17.349

[20]

Matteo Novaga, Enrico Valdinoci. Closed curves of prescribed curvature and a pinning effect. Networks & Heterogeneous Media, 2011, 6 (1) : 77-88. doi: 10.3934/nhm.2011.6.77

2016 Impact Factor: 0.8

Metrics

  • PDF downloads (12)
  • HTML views (53)
  • Cited by (0)

[Back to Top]