Linear codes and modular curves. (English. Russian original) Zbl 0629.94013

Vlèduts, S. G.; Manin, Yu. I.

J. Sov. Math. 30, 2611-2643 (1985); translation from Itogi Nauki Tekh., Ser. Sovrem. Probl. Mat. 25, 209-257 (1984).

Results of recent investigations at the juncture of coding theory, the theory of computability, and algebraic geometry over finite fields are presented. The basic problems of the asymptotic theory of codes and Goppa’s construction of codes on the basis of algebraic curves are presented, and a detailed algorithmic analysis is given of the codes arising on the modular curves of elliptic modules of V. G. Drinfel’d.

MSC:

94B05	Linear codes (general theory)
14H25	Arithmetic ground fields for curves
14G50	Applications to coding theory and cryptography of arithmetic geometry

Keywords:

asymptotic theory of codes; algebraic curves; modular curves; elliptic modules

References:

[1]	A. Aho and H. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley (1974). · Zbl 0326.68005
[2]	L. A. Bessalygo, V. V. Zyablov, and M. S. Pinsker, ”Problems of complexity in the theory of correcting codes,” Prob. Peredachi Inf.,13, No. 3, 5–17 (1977). · Zbl 0396.94017
[3]	é. L. Blokh and V. V. Zyablov, Linear Cascade Codes [in Russian], Svyaz’, Moscow (1982). · Zbl 0309.94031
[4]	S. G. Vléduts, ”Modular curves and codes with polynomial complexity of construction,” Preprint No. 3302-83 (1983).
[5]	S. G. Vléduts and V. G. Drinfel’d, ”On the number of points of an algebraic curve,” Funkts. Anal.,17, No. 1, 68–69 (1983). · Zbl 0574.32042 · doi:10.1007/BF01083190
[6]	S. G. Vléduts, G. L. Katsman, and M. A. Tsfasman, ”Modular curves and codes with polynomial complexity of construction,” Probl. Peredachi Inf.,20, No. 1, 3–15 (1984). · Zbl 0555.94008
[7]	V. D. Goppa, ”Codes on algebraic curves,” Dokl. Akad. Nauk SSSR,259, No. 6, 1289–1290 (1981). · Zbl 0489.94014
[8]	V. D. Goppa, ”Algebraicogeometric codes,” Izv. Akad. Nauk SSSR, Ser. Mat.,46, No. 4, 762–781 (1982).
[9]	P. Griffiths and J. Harris, Principles of Algebraic Geometry [Russian translation], Vols. 1, 2, Mir, Moscow (1982).
[10]	V. G. Drinfel’d, ”Elliptic modules,” Mat. Sb.,94, No. 4, 594–627 (1974).
[11]	T. Kasami, N. Tokura, E. Ivadari, and Ya. Inagaki, Coding Theory [Russian translation], Mir, Moscow (1978).
[12]	F. J. MacWilliams and N. J. A. Sloan, The Theory of Codes Correcting Errors [Russian translation], Svyaz’, Moscow (1979).
[13]	J. P. Serre, Algebraic Groups and Class Fields [Russian translation], Mir, Moscow (1959).
[14]	A. O. Slisenko, ”Complexity problems in the theory of computations,” Usp. Mat. Nauk,36, No. 6, 22–103 (1981). · Zbl 0484.68034
[15]	R. Hartshorn, Algebraic Geometry [Russian translation], Mir, Moscow (1981).
[16]	M. A. Tsfasman, ”Goppa codes lying above the Varshamov-Gilbert boundary,” Probl. Peredachi Inf.,18, No. 3, 3–6 (1982). · Zbl 0503.94025
[17]	N. G. Chebotarev, Introduction to the Theory of Algebraic Functions [in Russian], OGIZ, Moscow (1948).
[18]	I. R. Shafarevich, Foundations of Algebraic Geometry [in Russian], Nauka, Moscow (1972). · Zbl 0204.21301
[19]	G. Shimura, Introduction to the Arithmetic Theory of Automorphic Functions [Russian translation], Mir, Moscow (1973). · Zbl 0271.10030
[20]	D. Goss, ”The algebraist’s upper half plane,” Bull. Am. Math. Soc.,2, No. 3, 391–415 (1980). · Zbl 0433.14017 · doi:10.1090/S0273-0979-1980-14751-5
[21]	D. Goss, ”{\(\pi\)}-adic Eisenstein series for function fields,” Compos. Math.,41, No. 1, 3–38 (1980). · Zbl 0422.10020
[22]	Y. Ihara, ”Some remarks on the number of rational points of algebraic curves over finite fields,” J. Fac. Sci. Univ. Tokyo, Sec. IA,28, No. 3, 721–724 (1982). · Zbl 0509.14019
[23]	Y. Ihara, ”On the problems of congruence monodromy,” J. Math. Soc. Jpn.,20, No. 1–2, 107–121 (1968). · Zbl 0188.24802 · doi:10.2969/jmsj/02010107
[24]	Y. Ihara, ”On modular curves over finite fields,” Discrete Subgroups, Lie Groups, and Appl. Moduli, Papers, Bombay, Colloq. (1973), Oxford, e.a. (1975), pp. 160–202.
[25]	G. L. Katsman, M. A. Tsfasman, and S. G. Vladut, ”Modular curves and codes of polynomial construction,” IEEE Trans. Inf. Theory, 1984 (in press). · Zbl 0555.94008
[26]	Yu. I. Manin, ”What is the maximal number of points on a curve over F2?” J. Fac. Sci. Univ. Tokyo, Sec. 1A,28, No. 3, 715–720 (1981). · Zbl 0527.14021
[27]	J. P. Serre, ”Sur le nombre des points rationnels d’une courbe algebrique sur un corps fini,” C. R. Acad. Sci., Ser. 1,296, 397–402 (1983). · Zbl 0538.14015
[28]	M. A. Tsfasman, S. G. Vladut, and Th. Zink, ”Modular curves, Shimura curves, and Goppa codes better than the Varshamov-Gilbert bound,” Math. Nachr.,109, 21–28 (1982). · Zbl 0574.94013 · doi:10.1002/mana.19821090103