# 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) \tag*{(1)}\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

## Parent

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

## Children

- 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]).
- 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]).
- 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.
- 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.
- Hansen toric code — Hansen toric codes are polynomial evaluation codes with \(\cal X\) being a toric 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]
- J. B. Little, “Algebraic geometry codes from higher dimensional varieties”, (2008) arXiv:0802.2349
- [3]
- D. Jaramillo, M. V. Pinto, and R. H. Villarreal, “Evaluation codes and their basic parameters”, (2020) arXiv:1907.13217
- [4]
- M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
- [5]
- S. G. Vléduts and Yu. 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

- Victor V. Albert (2022-08-11) — most recent

## Cite as:

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