American Institute of Mathematical Sciences

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

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

Kathryn Haymaker 1, , Beth Malmskog 2,, and  Gretchen L. Matthews 3,

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.

Keywords: Fiber product, GK curves, local recovery, Suzuki curves, availability.
Mathematics Subject Classification: Primary: 14G50, 94B27; Secondary: 11T71.
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ón, J. 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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[6]

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

[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. Google Scholar

[8]

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

[9]

R. Guralnick, B. 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. Google Scholar

[10]

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

[11]

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

[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. Google Scholar

[13]

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

[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. Google Scholar

show all references

References:
[1]

M. Abdón, J. 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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[6]

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

[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. Google Scholar

[8]

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

[9]

R. Guralnick, B. 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. Google Scholar

[10]

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

[11]

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

[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. Google Scholar

[13]

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

[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. Google Scholar

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 Options

Download full-size image

Download as PowerPoint slide

Figure 2.  The fiber product $\mathcal{X}$ of $t$ curves $\mathcal{Y}_j$.
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Function fields associated with the fiber product.
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Generalized GK curve as a fiber product.
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  Suzuki curve and its quotients used for constructing LRC(2) with balanced recovery sets.
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  Curves for locally recoverable codes with availability $t$.
Figure Options

Download full-size image

Download as PowerPoint slide

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
Table Options

Download as excel

$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]

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 & Imaging, 2013, 7 (2) : 585-609. doi: 10.3934/ipi.2013.7.585
[4]

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
[5]

Stefano Marò. Relativistic pendulum and invariant curves. Discrete & Continuous Dynamical Systems - A, 2015, 35 (3) : 1139-1162. doi: 10.3934/dcds.2015.35.1139
[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 & Continuous Dynamical Systems - A, 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]

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]

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

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
[15]

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
[16]

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
[17]

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
[18]

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
[19]

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
[20]

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

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (48)
  • HTML views (239)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences