686 Arithmetic, Geometry, Cryptography and Coding Theory 15th International Conference Arithmetic, Geometry, Cryptography and Coding Theory May 18–22, 2015 CIRM, Luminy, France Alp Bassa Alain Couvreur David Kohel Editors AmericanMathematicalSociety 686 Arithmetic, Geometry, Cryptography and Coding Theory 15th International Conference Arithmetic, Geometry, Cryptography and Coding Theory May 18–22, 2015 CIRM, Luminy, France Alp Bassa Alain Couvreur David Kohel Editors AmericanMathematicalSociety Providence,RhodeIsland EDITORIAL COMMITTEE Dennis DeTurck, Managing Editor Michael Loss Kailash Misra Catherine Yan 2010 Mathematics Subject Classification. Primary 11T71, 11G20,11G25, 14G15, 14H40, 94A60, 94B27. Library of Congress Cataloging-in-Publication Data Names: InternationalConferenceArithmetic,Geometry,CryptographyandCodingTheory(15th : 2015: Marseille,France)|Bassa,Alp,1982-editor. |Couvreur,Alain,1981-editor. |Kohel, DavidR.,1966-editor. Title: Arithmetic,geometry,cryptographyandcodingtheory: 15thInternationalConferenceon Arithmetic,Geometry,CryptographyandCodingTheory,May18-22,2015,CIRM,Marseille, France/AlpBassa,AlainCouvreur,DavidKohel,editors. Description: Providence, Rhode Island : American Mathematical Society, [2017] | Series: Con- temporarymathematics;volume686|Includesbibliographicalreferences. Identifiers: LCCN2016041988|ISBN9781470428105(alk. paper) Subjects: LCSH:Codingtheory–Congresses. |Geometry,Algebraic–Congresses. |Cryptography– Congresses. | Number theory–Congresses. | AMS: Number theory – Finite fields and com- mutative rings (number-theoretic aspects) – Algebraic coding theory; cryptography. msc | Numbertheory–Arithmeticalgebraicgeometry(Diophantinegeometry)–Curvesoverfinite and localfields. msc | Number theory – Arithmetic algebraic geometry(Diophantine geome- try) – Varieties over finite and localfields. msc| Algebraic geometry– Arithmetic problems. Diophantinegeometry–Finitegroundfields. msc|Algebraicgeometry–Curves–Jacobians, Prymvarieties. msc|Informationandcommunication,circuits–Communication,information – Cryptography. msc |Informationand communication, circuits – Theory oferror-correcting codesanderror-detectingcodes–Geometricmethods(including applicationsofalgebraicge- ometry). msc Classification: LCCQA268.I572015|DDC510–dc23 LCrecordavailableathttps://lccn.loc.gov/2016041988 DOI:http://dx.doi.org/10.1090/conm/686 Colorgraphicpolicy. Anygraphicscreatedincolorwillberenderedingrayscalefortheprinted versionunlesscolorprintingisauthorizedbythePublisher. Ingeneral,colorgraphicswillappear incolorintheonlineversion. Copying and reprinting. Individual readersofthispublication,andnonprofit librariesacting for them, are permitted to make fair use of the material, such as to copy select pages for use in teaching or research. Permission is granted to quote brief passages from this publication in reviews,providedthecustomaryacknowledgmentofthesourceisgiven. Republication,systematiccopying,ormultiplereproductionofanymaterialinthispublication is permitted only under license from the American Mathematical Society. Permissions to reuse portions of AMS publication content are handled by Copyright Clearance Center’s RightsLink(cid:2) service. Formoreinformation,pleasevisit: http://www.ams.org/rightslink. Sendrequestsfortranslationrightsandlicensedreprintstoreprint-permission@ams.org. Excludedfromtheseprovisionsismaterialforwhichtheauthorholdscopyright. Insuchcases, requestsforpermissiontoreuseorreprintmaterialshouldbeaddresseddirectlytotheauthor(s). Copyrightownershipisindicatedonthecopyrightpage,oronthelowerright-handcornerofthe firstpageofeacharticlewithinproceedingsvolumes. (cid:2)c 2017bytheAmericanMathematicalSociety. Allrightsreserved. TheAmericanMathematicalSocietyretainsallrights exceptthosegrantedtotheUnitedStatesGovernment. PrintedintheUnitedStatesofAmerica. (cid:2)∞ Thepaperusedinthisbookisacid-freeandfallswithintheguidelines establishedtoensurepermanenceanddurability. VisittheAMShomepageathttp://www.ams.org/ 10987654321 222120191817 Contents The exact limit of some cubic towers Nurdagu¨l Anbar, Peter Beelen, and Nhut Nguyen 1 Error-correction capability of Reed-Muller codes St´ephanie Dib and Franc¸ois Rodier 17 Optimal and maximal singular curves Yves Aubry and Annamaria Iezzi 31 An infinite class of Kasami functions that are not APN infinitely often Eric F´erard 45 Covariant algebra of the binary nonic and the binary decimic Reynald Lercier and Marc Olive 65 On some bounds for symmetric tensor rank of multiplication in finite fields St´ephane Ballet, Julia Pieltant, Matthieu Rambaud, and Jeroen Sijsling 93 Codes from Jacobian surfaces Safia Haloui 123 A new proof of a Thomae-like formula for non hyperelliptic genus 3 curves Enric Nart and Christophe Ritzenthaler 137 Remarks on the Tsfasman-Boguslavsky Conjecture and higher weights of projective Reed-Muller codes Mrinmoy Datta and Sudhir R. Ghorpade 157 Secret sharing schemes with strong multiplication and a large number of players from toric varieties Johan P. Hansen 171 Field extensions and index calculus on algebraic curves Vanessa Vitse 187 iii Preface The 15th edition of the conference Arithmetic Geometry Cryptography and CodingTheorytookplaceattheCentreInternationaldeRencontresMath´ematiques (CIRM) in Luminy from May 18 to 22, 2015. It gathered together nearly one hun- dred researchers from eighteen different countries, all working on aspects of alge- braic geometry over finite fields, number theory, cryptography and coding theory. Reaching 28 years since the first edition of the conference in 1987, the community remains extremely active. In particular, the significant participation of young re- searchersintheconferenceshowsthehighdynamismofthedomainreflectswellon its future prospect. Four plenary speakers were invited to give an overview on problems connected to the main themes of the conference. Alena Pirutka gave a talk on cycle class maps and surveyed known results and open questions related to Tate conjectures. Ernst-UlrichGekelerpresentedaconstructionoffamiliesofcurveswithmanypoints from higher-rank Drinfeld modular varieties. Antoine Joux discussed the discrete logarithmprobleminmultiplicativegroupsoffinitefieldsfollowinghisrecentbreak- through. Finally Bernard Le Stum gave an introductory talk on rigid cohomology. In addition to the invited speakers, there were more than forty talks covering a wide range of topics, such as estimates of the number of rational points of curves or higher dimensional varieties over finite fields, towers of global fields, algebraic geometric coding theory, abelian varieties, and public key cryptography. Certain topics, such as algebraic geometry codes, are among the historical themes of the conference,whileothers,suchasthearithmeticofabelianvarietiesandcurvebased cryptography have appeared more recently in the scope of the conference. This emphasizes the continual evolution of the community. The articles of the present volume represent a selection of research presented at this conference. We warmly thank all the speakers of the conference for their participation and the high quality of their presentations. We also express a deep gratitude to the CIRM’s team Olivia Barbaroux, Muriel Milton and Laure Stefanini for their remarkable efficiency. v ContemporaryMathematics Volume686,2017 http://dx.doi.org/10.1090/conm/686/13774 The exact limit of some cubic towers Nurdagu¨l Anbar, Peter Beelen, and Nhut Nguyen Abstract. Recently,anewexplicittoweroffunctionfieldswasintroducedby Bassa,Beelen,GarciaandStichtenoth(BBGS).Thisresultedincurrentlythe best known lower bound for Ihara’s constant in the case of non-prime finite fields. In particular over cubic fields, the tower’s limit is at least as good as Zink’sbound;i.e. λ(BBGS/Fq3)≥2(q2−1)/(q+2). Inthispaper,theexact valueofλ(BBGS/Fq3)iscomputed. WealsosettleaquestionstatedinIhara’s 2007paper. 1. Introduction LetF bethefinitefieldwithq elements, andletF beafunctionfieldwithfull q constantfieldF . ThenumberN(F)ofF -rationalplacesofF isboundedinterms q q of the genus g(F) and the cardinality of the finite field; namely N(F) ≤ 1+q+ √ 2g(F) q. ThisboundiscalledHasse-Weilboundanditisnotoptimalwheng(F)is largecomparedwiththecardinalityofthefinitefield[8,10]. Forsomeapplications in cryptography and coding theory (derived from algebraic geometry codes) [6], explicit function fields (or equivalently algebraic curves) F having many rational placesare of greatinterest. Inorder toinvestigate the asymptoticbehaviour of the number ofrationalplacesN(F)comparedtothegenusg(F)ofF, oneisinterested in Ihara’s constant max{N(F)|g(F)=g} A(q):=limsup , g→∞ g where each function field F has full constant field F . To investigate this constant q one can consider towers of function fields. A recursive tower F/F = (F ⊂ F ⊂ q 1 2 ···) over F is a sequence of function fields with full constant field F such that q q (i) F =F (x ) for some x ∈F , which is transcendental over F , 1 q 1 1 1 q (ii) for each i ≥ 1, we have F = F (x ) with [F : F ] > 1 and i+1 i i+1 i+1 i ϕ(x ,x )=0 for some separable polynomial ϕ(x ,T)∈F (x )[T], and i i+1 i q i (iii) g(F )→∞ as i→∞. i One says that the tower satisfies the recursion ϕ(x ,x ) = 0. For a tower F/F i i+1 q satisfying the recursion ϕ(x ,x )= 0, we call a tower G/F as the dual tower of i i+1 q F/F if G/F satisfies the recursion ϕ(x ,x ) = 0. Note that we do not assume q q i+1 i that ϕ(x ,T) is irreducible over F for all i. As a result full characterization of i i 2010 MathematicsSubjectClassification. Primary14H05;Secondary11R58. Key wordsand phrases. Functionfield,Ihara’sconstant,cubictower. (cid:2)c2017 American Mathematical Society 1 2 NURDAGU¨LANBAR,PETERBEELEN,ANDNHUTNGUYEN function fields in the tower may require further information. A tower F/F is q called good if its limit N(F ) λ(F/F ):= lim i q i→∞ g(Fi) is a positive real number. As the value of λ(F/F ) gives a lower bound for Ihara’s q constant A(q), we are interested in towers having a limit as large as possible. Over √ any finite field F , Drinfeld and Vladut [14] showed that A(q) ≤ q−1. On the q otherhand,Ihara[7],Tsfasman,VladutandZink[12]usedmodularcurvestoshow √ √ that A(q)≥ q−1 for square q. As a result it is known that A(q)= q−1 if q is square. The exact value of A(q) is still an open problem for non-square q. In this paper we focus on the case of cubic q. Zink [15] using degenerations of Shimura surfaces, gave the lower bound A(p3)≥2(p2−1)/(p+2) , for p prime. Later, van der Geer and van der Vlugt [13] presented an explicit example of a recursive tower over F with limit 3/2, thereby meeting Zink’s bound 8 forthecasep=2. ThenusinganexplicitrecursivetowerBeGS/F =(B ⊂B ⊂ q3 1 2 ···) of Bezerra, Garcia and Stichtenoth [4], Zink’s bound was generalized as (1) λ(BeGS/F )≥2(q2−1)/(q+2) . q3 It was shown by Beelen, Garcia and Stichtenoth [3] (using results from [2] and [4]) thatλ(BeGS/F )=2(q2−1)/(q+2). Recently,anewexplicittowerwasintroduced q3 by Bassa, Beelen, Garcia and Stichtenoth (BBGS) [1]. The tower’s limit gave the best known lower bound for A(qn) over any non-prime finite field F ; i.e. qn (cid:2) (cid:3) 1 1 −1 A(qn)≥2 + , qj −1 qn−j −1 where 1 ≤ j ≤ n−1. In this paper, we compute the exact limit of Tower BBGS over F (n = 3). To do this, we examine one of its subtowers arising from its q3 modular interpretation and satisfies (Y +1)Nn (X+1)Nn (2) = , YNj Xqn−jNj where N = (qi −1)/(q−1) for i ≥ 1 (see [1, Equation (38)]). We note that the i subtower satisfies an absolutely irreducible polynomial of degree qn−1. We prove that λ(BBGS/F )=2(q2−1)/(q+2) q3 and discuss the relationship between several towers. Our strategy to prove the exact limit of BBGS/F is as follows. For n=3, Equation (2) has two absolutely q3 irreducible factors: one of them is degree q+1, and the other is degree q2. The degree q2 factor can be used to construct a subtower of the BBGS tower as was done (for general n) in [1]. In Section 2, we use the factor of degree q + 1 to construct a tower Z/F , and we show that this is essentially the same as BeGS q3 Tower. Then we construct a subtower G/F of Tower Z. We prove that G/F is q3 q3 recursivelydefinedbythedegreeq2 factorofEquation(2),whichshowsthatG/F q3 isthesubtoweroftheBBGSTowerconsideredin[1]. Inotherwords, weshow that G/F isacommon subtower of thetowers Z/F andBBGS/F . InSection3, we q3 q3 q3 compute the exact limit of Tower G using the fact that it is a subtower of Z/F . q3 Then in Section 4, we conclude that λ(BBGS/F ) is equal to Zink’s bound. q3 THE EXACT LIMIT OF SOME CUBIC TOWERS 3 2. Various Cubic Towers In this section we investigate Equation (2) and a tower arising from a factor of it over cubic fields. We have two choices for j. However, for j = 1 (under the change of variable, replacing X by 1/X and Y by 1/Y) we obtain the dual tower of the one for j =2. Therefore, we without loss of generality assume that j =2. 2.1. The Tower Z. In the case of j =2, Equation (2) becomes (Y +1)q2+q+1 (X+1)q2+q+1 (3) = . Yq+1 Xq2+q Thisequationisnotirreducible. Moreprecisely,thepolynomial(Y+1)q2+q+1Xq2+q −Yq+1(X+1)q2+q+1 has two factors over F (X). One of them has degree q+1; q3 namely (4) F(X,Y)=Xq+1(Y +1)q+1−(X+1)Xq(Y +1)q−Y(X+1)q+1 =Xq+1Yq+1−XqYq−XqY −Xq−XY −Y and the other factor has degree q2. Later we will see that these two factors are absolutely irreducible (see the proof of Lemma 2.6). We are going to construct a tower Z/F = (Z ⊂ Z ⊂ ···), where Z := F (z ,...,z ) and the recursion q3 1 2 i q3 1 i F(z ,z ) = 0 holds for F given in Equation (4) for each i ≥ 1. Then z ∈ Z i i+1 3 3 satisfies the polynomial equation (5) zq+1(Y +1)q+1−(z +1)zq(Y +1)q−Y(z +1)q+1 =0 . 2 2 2 2 However, theleft-handsideinEquation(5)isnotirreducibleoverZ ; infactithas 2 a factor of degree q given as follows. (cid:2) (cid:3) (cid:2) (cid:3) 1 q−1 (z +1)q z +1 q (6) (z Y −1) z Y + − 2 − 1 2 2 z z z 1 2 1 Iteratively, Tower Z/F = (Z ⊂ Z ⊂ ···) is defined as a sequence of function q3 1 2 fields satisfying Z = Z (z ), where z ,z satisfy Equation (4); i.e. F(z ,z ) = 0 2 1 2 1 2 1 2 and Z =Z (z ) for i≥2, where i+1 i i (cid:2) (cid:3) (cid:2) (cid:3) (7) (z z −1) z z + 1 q−1− (zi+1)q − zi−1+1 q =0 . i i+1 i i+1 zi−1 zi zi−1 If we set α :=(z z −1)/(z +1) then from F(z ,z )=0 in Equation (4) we get 0 1 2 1 1 2 z =(α +1)/αq+1 and z =αq+1+α . 1 0 0 2 0 0 Asaresult,weseethatF(α )=F(z ,z )=Z . ConsiderthetowerC =(C ⊂C ⊂ 0 1 2 2 0 1 ···) with C =F(α ) and C =C (α ), where α satisfies the polynomial 0 0 i+1 i i+1 i+1 1 1 (8) Tq+1− T − αq+1+α αq+1+α i i i i over F(α ) for all i ≥ 0. In other words, αi+1+1 = αq+1 + α . Note that the i αq+1 i i i+1 polynomial inEquation(8)hasalinear factor; namely T+ 1 ; and hencefor the construction of Tower C we consider the factor of degree q.αWi+e1 will see in Lemma 2.1thatforeachi≥0thisfactorisabsolutelyirreducibleoverC sincethereexistsa i place totally ramified in C /C lying over either (α =0) or (α =∞). This also i+1 i 0 0 impliestheabsoluteirreducibilityofthefactorin(6)sinceTowerC isessentiallythe