Polynomial evaluation code

Description

Evaluation code of polynomials at points \({\cal P} = \left( P_1,P_2,\cdots,P_n \right)\) on an algebraic variety \(\cal X\). Codewords \begin{align} \left( f(P_1), f(P_2), \cdots, f(P_n) \right) \end{align} are evaluations of a linear space \(L\) of polynomials \(f\). If the space is taken to be all polynomials up to some degree, the code is called a Reed-Muller-type code or RM-type code of that degree.

One can specify the space \(L\) by the number of variables input into the polynomials as well as the polynomials' maximum degree. One can additionally select only polynomials that have zeroes at certain points with certain multiplicities. A bookkeeping device for this data is the divisor \(D\), and the corresponding vector space of polynomials defined using the variety \(\cal X\) and the divisor is the Riemann-Roch space \(L=L(D)\) ([1], pg. 313).

Notes

See Refs. [2][3] for reviews.

Parent

  • Evaluation code — Polynomial evaluation codes are evaluation codes of polynomials \(f\) for which \(\cal X\) is an algebraic variety.

Children

  • Complete-intersection RM-type code — Complete-intersection RM-type codes are polynomial evaluation codes with \(\cal X\) being a complete intersection.
  • Deligne-Lusztig code — Deligne-Lusztig codes are polynomial evaluation codes with \(\cal X\) a Deligne-Lusztig variety.
  • Flag-variety code — Flag-variety codes are polynomial evaluation codes with \(\cal X\) being a flag variety.
  • Generalized RM (GRM) code — GRM (PRM) codes are multivariate polynomial evaluation codes with \(\cal X\) being the entire \(m\)-dimensional affine (projective) space over \(GF(q)\) ([4], pgs. 44-46; [5][6]).
  • Generalized RS (GRS) code — GRS (RS) codes are in one-to-one correspondence with univariate polynomial evaluation codes with \(\cal X\) being the projective (affine) line ([1], Thm. 15.3.24; [4], Ch. 3.2; [6]).
  • Hansen toric code — Hansen toric codes are polynomial evaluation codes with \(\cal X\) being a toric variety.
  • Reed-Muller (RM) code — RM codes are multivariate polynomial evaluation codes with \(\cal X\) being the entire \(m\)-dimensional affine binary space ([4], pgs. 44-46; [5][6]).
  • Ruled-surface code — Ruled-surface codes are polynomial evaluation codes with \(\cal X\) being a ruled surface.
  • Serge-variety RM-type code — Serge-variety RM-type codes are polynomial evaluation codes with \(\cal X\) being a Serge variety.

Cousin

  • Evaluation AG code — Evaluation AG codes are evaluation codes on algebraic curves. Polynomial evaluation codes are evaluation codes of polynomials. Evaluation AG codes of polynomials are equivalent to polynomial evaluation codes on algebraic curves.

References

[1]
W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021). DOI
[2]
John B. Little, “Algebraic geometry codes from higher dimensional varieties”. 0802.2349
[3]
Delio Jaramillo, Maria Vaz Pinto, and Rafael H. Villarreal, “Evaluation codes and their basic parameters”. 1907.13217
[4]
M. A. Tsfasman and S. G. Vlăduţ, Algebraic-geometric Codes (Springer Netherlands, 1991). DOI
[5]
S. G. Vléduts and Y. I. Manin, “Linear codes and modular curves”, Journal of Soviet Mathematics 30, 2611 (1985). DOI
[6]
T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
Page edit log

Zoo code information

Internal code ID: evaluation_polynomial

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: evaluation_polynomial

Cite as:
“Polynomial evaluation code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/evaluation_polynomial
BibTeX:
@incollection{eczoo_evaluation_polynomial, title={Polynomial evaluation code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/evaluation_polynomial} }
Share via:
Twitter |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/evaluation_polynomial

Cite as:

“Polynomial evaluation code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/evaluation_polynomial

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/properties/evaluation_polynomial.yml.