{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:05:12Z","timestamp":1750309512064,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,12,1]],"date-time":"2023-12-01T00:00:00Z","timestamp":1701388800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Commun. Comput. Algebra"],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:p>In 1874 Brill and Noether designed a seminal geometric method for computing bases of Riemann-Roch spaces. From then, their method has led to several algorithms, some of them being implemented in computer algebra systems. The usual proofs often rely on abstract concepts of algebraic geometry and commutative algebra. In this paper we present a short self-contained and elementary proof that mostly needs Newton polygons, Hensel lifting, bivariate resultants, and Chinese remaindering.<\/jats:p>","DOI":"10.1145\/3653002.3653004","type":"journal-article","created":{"date-parts":[[2024,3,15]],"date-time":"2024-03-15T22:04:51Z","timestamp":1710540291000},"page":"200-229","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A Proof of the Brill-Noether Method from Scratch"],"prefix":"10.1145","volume":"57","author":[{"given":"Elena","family":"Berardini","sequence":"first","affiliation":[{"name":"CNRS; Institut de Math\u00e9matiques de Bordeaux, Universit\u00e9 de Bordeaux, Talence, France and Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, the Netherlands"}]},{"given":"Alain","family":"Couvreur","sequence":"additional","affiliation":[{"name":"Inria &amp; Laboratoire d'informatique de l'\u00c9cole polytechnique, CNRS, \u00c9cole polytechnique, Institut Polytechnique de Paris, Palaiseau, France"}]},{"given":"Gr\u00e9goire","family":"Lecerf","sequence":"additional","affiliation":[{"name":"Laboratoire d'informatique de l'\u00c9cole polytechnique, CNRS, \u00c9cole polytechnique, Institut Polytechnique de Paris, Palaiseau, France"}]}],"member":"320","published-online":{"date-parts":[[2024,3,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"101666","DOI":"10.1016\/j.jco.2022.101666","article-title":"Computing Riemann-Roch spaces via Puiseux expansions","volume":"73","author":"Abelard S.","year":"2022","unstructured":"S. Abelard, E. Berardini, A. Couvreur, and G. Lecerf. Computing Riemann-Roch spaces via Puiseux expansions. J. Complexity, 73:101666, 2022.","journal-title":"J. Complexity"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1145\/3373207.3404053","volume-title":"Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation, ISSAC '20","author":"Abelard S.","year":"2020","unstructured":"S. Abelard, A. Couvreur, and G. Lecerf. Sub-quadratic time for Riemann-Roch spaces: case of smooth divisors over nodal plane projective curves. In A. Mantzaflaris, editor, Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation, ISSAC '20, pages 14--21. New York, NY, USA, 2020. ACM."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00200-022-00588-x"},{"key":"e_1_2_1_4_1","series-title":"Lect","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0066166","volume-title":"Geometric theory of algebraic space curves","author":"Abhyankar S. S.","year":"1974","unstructured":"S. S. Abhyankar and A. M. Sathaye. Geometric theory of algebraic space curves, volume 423 of Lect. Notes Math. Springer, Berlin, Heidelberg, 1974."},{"key":"e_1_2_1_5_1","series-title":"Grundlehren der mathematischen Wissenschaften","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-5323-3","volume-title":"Geometry of algebraic curves","author":"Arbarello E.","year":"1985","unstructured":"E. Arbarello, M. Cornalba, P. Griffiths, and J. D. Harris. Geometry of algebraic curves. Volume I, volume 267 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag New York, 1985."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2700859"},{"key":"e_1_2_1_7_1","first-page":"1","volume-title":"37th Computational Complexity Conference (CCC 2022), volume 234 of Leibniz International Proceedings in Informatics (LIPIcs)","author":"Bordage S.","year":"2022","unstructured":"S. Bordage, M. Lhotel, J. Nardi, and H. Randriam. Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes. In S. Lovett, editor, 37th Computational Complexity Conference (CCC 2022), volume 234 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1--30:45. Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_2_1_8_1","volume-title":"Palaiseau","author":"Bostan A.","year":"2017","unstructured":"A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy, and \u00c9. Schost. Algorithmes Efficaces en Calcul Formel. Fr\u00e9d\u00e9ric Chyzak (self-published), Palaiseau, France, 2017. Electronic version available from https:\/\/hal.archives-ouvertes.fr\/AECF."},{"issue":"2","key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF02104804","article-title":"Ueber die algebraischen Functionen und ihre Anwendung in der Geometrie","volume":"7","author":"Brill A.","year":"1874","unstructured":"A. Brill and M. Noether. Ueber die algebraischen Functionen und ihre Anwendung in der Geometrie. Math. Ann., 7(2-3):269--310, 1874.","journal-title":"Math. Ann."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-01-01390-4"},{"key":"e_1_2_1_11_1","volume-title":"the Brill and Noether Way","author":"Casas-Alvero E.","year":"2019","unstructured":"E. Casas-Alvero. Algebraic Curves, the Brill and Noether Way. Springer International Publishing, 2019."},{"key":"e_1_2_1_12_1","series-title":"Lect","first-page":"466","volume-title":"Advances in Cryptology - CRYPTO","author":"Cascudo I.","year":"2009","unstructured":"I. Cascudo, H. Chen, R. Cramer, and C. Xing. Asymptotically good ideal linear secret sharing with strong multiplication over any fixed finite field. In S. Halevi, editor, Advances in Cryptology - CRYPTO 2009, volume 5677 of Lect. Notes Comput. Sci., pages 466--486. Springer, Berlin, Heidelberg, 2009."},{"key":"e_1_2_1_13_1","series-title":"Lect","first-page":"685","volume-title":"Advances in Cryptology - CRYPTO","author":"Cascudo I.","year":"2011","unstructured":"I. Cascudo, R. Cramer, and C. Xing. The torsion-limit for algebraic function fields and its application to arithmetic secret sharing. In P. Rogaway, editor, Advances in Cryptology - CRYPTO 2011, volume 6841 of Lect. Notes Comput. Sci., pages 685--705. Springer, Berlin, Heidelberg, 2011."},{"key":"e_1_2_1_14_1","series-title":"Lect","first-page":"521","volume-title":"Advances in Cryptology - CRYPTO","author":"Chen H.","year":"2006","unstructured":"H. Chen and R. Cramer. Algebraic geometric secret sharing schemes and secure multi-party computations over small fields. In C. Dwork, editor, Advances in Cryptology - CRYPTO 2006, volume 4117 of Lect. Notes Comput. Sci., pages 521--536. Springer, Berlin, Heidelberg, 2006."},{"key":"e_1_2_1_15_1","volume-title":"HAL","author":"Couvreur A.","year":"2021","unstructured":"A. Couvreur. How arithmetic and geometry make error correcting codes better. Technical Report, HAL, 2021. https:\/\/hal.inria.fr\/hal-03400779. To appear, Soci\u00e9t\u00e9 Math\u00e9matique de France, Panoramas et Synth\u00e8ses."},{"key":"e_1_2_1_16_1","volume-title":"W. C. Huffman, J.-L","author":"Couvreur A.","year":"2021","unstructured":"A. Couvreur and H. Randriambololona. Algebraic geometry codes and some applications. In W. C. Huffman, J.-L. Kim, and P. Sol\u00e9, editors, Concise Encyclopedia of Coding Theory. Chapman and Hall\/CRC, 2021."},{"key":"e_1_2_1_17_1","series-title":"Graduate Texts in Mathematics","volume-title":"Using Algebraic Geometry","author":"Cox D.","year":"2005","unstructured":"D. Cox, J. Little, and D. O'Shea. Using Algebraic Geometry, volume 185 of Graduate Texts in Mathematics. Springer-Verlag New York, 2nd edition, 2005.","edition":"2"},{"key":"e_1_2_1_18_1","volume-title":"varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra","author":"Cox D.","year":"2013","unstructured":"D. Cox, J. Little, and D. O'Shea. Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra. Springer Science & Business Media, 2013."},{"key":"e_1_2_1_19_1","series-title":"Lect","first-page":"656","volume-title":"Advances in Cryptology - CRYPTO","author":"Cramer R.","year":"2021","unstructured":"R. Cramer, M. Rambaud, and C. Xing. Asymptotically-good arithmetic secret sharing over Z\/p&ell;Z with strong multiplication and its applications to efficient MPC. In T. Malkin and C. Peikert, editors, Advances in Cryptology - CRYPTO 2021, volume 12827 of Lect. Notes Comput. Sci., pages 656--686. Springer, Cham, 2021."},{"issue":"2","key":"e_1_2_1_20_1","first-page":"119","article-title":"Rational Puiseux expansions","volume":"70","author":"Duval D.","year":"1989","unstructured":"D. Duval. Rational Puiseux expansions. Compos. Math., 70(2):119--154, 1989.","journal-title":"Compos. Math."},{"key":"e_1_2_1_21_1","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-5350-1","volume-title":"Commutative algebra. With a view toward algebraic geometry","author":"Eisenbud D.","year":"1995","unstructured":"D. Eisenbud. Commutative algebra. With a view toward algebraic geometry, volume 150 of Graduate Texts in Mathematics. Springer-Verlag New York, 1995."},{"key":"e_1_2_1_22_1","unstructured":"W. Fulton. Algebraic Curves - An Introduction to Algebraic Geometry. Addison-Wesley 1989."},{"key":"e_1_2_1_23_1","first-page":"301","volume-title":"Adjoints and Max Noether's Fundamentalsatz","author":"Fulton W.","year":"2004","unstructured":"W. Fulton. Adjoints and Max Noether's Fundamentalsatz. In C. Christensen, A. Sathaye, G. Sundaram, and C. Bajaj, editors, Algebra, Arithmetic and Geometry with Applications: Papers from Shreeram S. Abhyankar's 70th Birthday Conference, pages 301--313. Springer, Berlin, Heidelberg, 2004."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065"},{"issue":"3","key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1090\/S0002-9947-1952-0049591-8","article-title":"An arithmetic theory of adjoint plane curves","volume":"72","author":"Gorenstein D.","year":"1952","unstructured":"D. Gorenstein. An arithmetic theory of adjoint plane curves. Trans. Am. Math. Soc., 72(3):414--436, 1952.","journal-title":"Trans. Am. Math. Soc."},{"key":"e_1_2_1_26_1","series-title":"Lect","first-page":"98","volume-title":"Algebraic Geometry. Summer Meeting","author":"Greco S.","year":"1978","unstructured":"S. Greco and P. Valabrega. On the theory of adjoints. In K. Lonsted, editor, Algebraic Geometry. Summer Meeting, Copenhagen, August 7-12, 1978, volume 732 of Lect. Notes Math., pages 98--123. Springer-Verlag Berlin Heidelberg, 1979."},{"key":"e_1_2_1_27_1","volume-title":"On the theory of adjoints II. Rendiconti del Circolo Matematico di Palermo, 31(1):5--15","author":"Greco S.","year":"1982","unstructured":"S. Greco and P. Valabrega. On the theory of adjoints II. Rendiconti del Circolo Matematico di Palermo, 31(1):5--15, 1982."},{"key":"e_1_2_1_28_1","series-title":"NATO Science Series II: Mathematics","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/978-94-010-1011-5_9","volume-title":"Applications of Algebraic Geometry to Coding Theory, Physics and Computation","author":"Greuel G.-M.","year":"2001","unstructured":"G.-M. Greuel, C. Lossen, and M. Schulze. Three algorithms in algebraic geometry, coding theory and singularity theory. In C. Ciliberto, F. Hirzebruch, R. Miranda, and M. Teicher, editors, Applications of Algebraic Geometry to Coding Theory, Physics and Computation, volume 36 of NATO Science Series II: Mathematics, Physics and Chemistry, pages 161--194. Springer Netherlands, 2001."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/3-540-60114-7_19","volume-title":"Applied Algebra, Algebraic Algorithms and Error-Correcting Codes","author":"Hach\u00e9 G.","year":"1995","unstructured":"G. Hach\u00e9. Computation in algebraic function fields for effective construction of algebraic-geometric codes. In G. Cohen, M. Giusti, and T. Mora, editors, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, pages 262--278. Springer Berlin Heidelberg, 1995."},{"key":"e_1_2_1_31_1","volume-title":"Universit\u00e9 de Limoges","author":"Hach\u00e9 G.","year":"1998","unstructured":"G. Hach\u00e9. L'algorithme de Brill-Noether appliqu\u00e9 aux courbes r\u00e9duites. Technical Report, Rapport de recherche n\u00b0 1998-01, Laboratoire d'Arithm\u00e9tique, de Calcul formel et d'Optimisation ESA - CNRS 6090, Universit\u00e9 de Limoges, France, 1998. https:\/\/www.unilim.fr\/laco\/rapports\/1998\/R1998_01.pdf."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.2001.0513"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1994.1063"},{"key":"e_1_2_1_34_1","volume-title":"Vorlesungen \u00fcber algebraische Geometrie","author":"Keller O. H.","year":"1974","unstructured":"O. H. Keller. Vorlesungen \u00fcber algebraische Geometrie. Akademie Verlag Leipzig, 1974."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-07-01989-8"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-43601-2","volume-title":"Computational Linear and Commutative Algebra","author":"Kreuzer M.","year":"2016","unstructured":"M. Kreuzer and L. Robbiano. Computational Linear and Commutative Algebra. Springer International Publishing, 2016."},{"issue":"6","key":"e_1_2_1_37_1","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/s11128-017-1618-7","article-title":"Good and asymptotically good quantum codes derived from algebraic geometry","volume":"16","author":"La Guardia G. G.","year":"2017","unstructured":"G. G. La Guardia and F. R. F. Pereira. Good and asymptotically good quantum codes derived from algebraic geometry. Quantum Inf. Process., 16(6):165, 2017.","journal-title":"Quantum Inf. Process."},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"S. Lang. Algebra volume 211 of Graduate Texts in Mathematics. Springer-Verlag New York 3rd edition 2002.","DOI":"10.1007\/978-1-4613-0041-0_1"},{"key":"e_1_2_1_39_1","volume-title":"Algorithme de Brill-Noether et codes de Goppa. Bulletin de la soci\u00e9t\u00e9 math\u00e9matique de France, 116(2):231--253","author":"Le Brigand D.","year":"1988","unstructured":"D. Le Brigand and J.-J. Risler. Algorithme de Brill-Noether et codes de Goppa. Bulletin de la soci\u00e9t\u00e9 math\u00e9matique de France, 116(2):231--253, 1988."},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","first-page":"2399","DOI":"10.1090\/mcom\/3517","article-title":"A fast randomized geometric algorithm for computing Riemann-Roch spaces","volume":"89","author":"Le Gluher A.","year":"2020","unstructured":"A. Le Gluher and P.-J. Spaenlehauer. A fast randomized geometric algorithm for computing Riemann-Roch spaces. Math. Comp., 89:2399--2433, 2020.","journal-title":"Math. Comp."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"e_1_2_1_42_1","volume-title":"Brillnoether.lib. A Singular 4.1.2 library for Riemann-Roch spaces of divisors on curves","author":"Stenger I.","year":"2019","unstructured":"I. Stenger and J. B\u00f6hm. Brillnoether.lib. A Singular 4.1.2 library for Riemann-Roch spaces of divisors on curves. 2019. http:\/\/www.singular.uni-kl.de."},{"key":"e_1_2_1_43_1","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-76878-4","volume-title":"Algebraic function fields and codes","author":"Stichtenoth H.","year":"2009","unstructured":"H. Stichtenoth. Algebraic function fields and codes, volume 254 of Graduate Texts in Mathematics. Springer-Verlag Berlin Heidelberg, 2nd edition, 2009.","edition":"2"},{"issue":"1","key":"e_1_2_1_44_1","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1002\/mana.19821090103","article-title":"Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound","volume":"109","author":"Tsfasman M. A.","year":"1982","unstructured":"M. A. Tsfasman, S. G. Vl\u0103du\u0163, and Th. Zink. Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound. Math. Nachr., 109(1):21--28, 1982.","journal-title":"Math. Nachr."},{"key":"e_1_2_1_45_1","series-title":"Lect","first-page":"221","volume-title":"L. M. Adleman and M.-D","author":"Volcheck E. J.","year":"1994","unstructured":"E. J. Volcheck. Computing in the Jacobian of a plane algebraic curve. In L. M. Adleman and M.-D. Huang, editors, Algorithmic Number Theory. First International Symposium, ANTS-I Ithaca, NY, USA, May 6--9, 1994. Proceedings, volume 87 of Lect. Notes Comput. Sci., pages 221--233. Springer Berlin Heidelberg, 1994."}],"container-title":["ACM Communications in Computer Algebra"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3653002.3653004","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3653002.3653004","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:59Z","timestamp":1750295879000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3653002.3653004"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["10.1145\/3653002.3653004"],"URL":"https:\/\/doi.org\/10.1145\/3653002.3653004","relation":{},"ISSN":["1932-2240"],"issn-type":[{"type":"print","value":"1932-2240"}],"subject":[],"published":{"date-parts":[[2023,12]]},"assertion":[{"value":"2024-03-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}