{"entities":{"Q2397618":{"pageid":2408361,"ns":120,"title":"Item:Q2397618","lastrevid":57894645,"modified":"2026-04-02T23:57:28Z","type":"item","id":"Q2397618","labels":{"en":{"language":"en","value":"Automatic sequences and curves over finite fields"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6722479"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$6E7BC784-0284-4E78-9529-597DA4167F0F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"486cdd7a5037ad4be387cf05f6d73d9f1c882bc0","datavalue":{"value":{"text":"Automatic sequences and curves over finite fields","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2397618$1B0FBFD7-9281-4439-A7B5-F5FB52F20F17","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"717ae529930f9466e9fd9c2c74fca46e457ad3c2","datavalue":{"value":"1425.11051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2397618$0A840522-7437-49BF-93DE-1B547641328B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0f82eff8888d1ec53c3ef15af3fd677dc6803d78","datavalue":{"value":{"entity-type":"item","numeric-id":1651764,"id":"Q1651764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$BD341A39-FD13-4162-AA6B-55F6301ACF35","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3867057a7d0226a86475a68a428f5c0a32f79af8","datavalue":{"value":{"entity-type":"item","numeric-id":246406,"id":"Q246406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$4BEE0C80-0407-40A8-8D44-B12915FB890B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e595cae23ba1377d80fb54bd8031e4449ce1aa94","datavalue":{"value":{"time":"+2017-05-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2397618$E73ABEC0-8270-4E66-A1EB-9CDEF356AD31","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4b0a71f3e189a0f00e538d5c2e6c6e721515997c","datavalue":{"value":"https://arxiv.org/abs/1604.08241","type":"string"},"datatype":"url"},"type":"statement","id":"Q2397618$E5291E85-4D2D-450C-8B27-EE36AD50CBE7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"370ab75079b5fef442483fa5f2cb78ae0f85c2a7","datavalue":{"value":"A well-known result of Christol states that a formal power series \\(y=\\sum_{n\\ge 0} a_n x^n\\) in \\(\\mathbb{F}_q[[x]]\\) is algebraic over \\(\\mathbb{F}_q(x)\\) if and only if the sequence \\((a_n)\\) of its coefficients is \\(q\\)-automatic (in the sense of Allouche and Shallit). For a \\(q\\)-automatic sequence, its (state) complexity is defined as the number of states of a minimal automaton generating it and fed with, least significant digit first, base-\\(q\\) expansions. The main aim of this paper is to give a quantitative result about Christol's theorem: an upper bound on such state complexity compared with the algebraic complexity of the series.   Let \\(y\\) be algebraic over \\(k(x)\\). The degree \\(d\\) of \\(y\\) is the field degree \\([k(x)[y]:k(x)]\\) and the height \\(h\\) is the minimal \\(x\\)-degree of a bivariate polynomial \\(P(x,T)\\in k[x,T]\\) such that \\(P(x,y)=0\\). The genus \\(g\\) of \\(y\\) is the genus of the normalization of the projective closure of the affine plane curve defined by the minimal polynomial of \\(y\\). With these definitions, the author proves that if \\(y=\\sum_{n\\ge 0} a_n x^n\\in \\mathbb{F}_q[[x]]\\) is algebraic over \\(\\mathbb{F}_q(x)\\), then the state complexity of \\((a_n)\\) is bounded by \\((1+o(1))q^{d+h+g-1}\\) and the error term tends to zero for large values of \\(q\\), \\(h\\), \\(d\\), or \\(g\\). When reading most significant digit first, the author also obtains an upper bound of the form \\(q^{h+2d+g-1}\\).  One of the main ingredient of this paper is to use algebraic geometry and in particular the Riemann-Roch theorem, existence of the Cartier operator acting on the space of K\u00e4hler differentials of the function field associated with \\(y\\), and asymptotics for the Landau function. Such an idea was introduced by David Speyer in 2010 to give an alternative proof for one direction of Christol's theorem.  The paper ends with some computations of the state complexity of an automatic sequence showing how the geometric approach can be useful. Note that recently, \\textit{B. Adamczewski} and \\textit{R. Yassawi} have obtained similar bounds using a method based on diagonals of bivariate rational functions, see ``A note on Christol's theorem''. \\url{arxiv:1906.08703}.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2397618$8C747162-8F0E-46A6-A6D5-0228092693F8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ee087b51e799847d019fb8239a9d1ca2f0176191","datavalue":{"value":{"entity-type":"item","numeric-id":236475,"id":"Q236475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$F5CA2240-660E-49B5-84D0-080A9C845EB5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1d3e055a17ce7fb6036131cf10d782136e2d9314","datavalue":{"value":"11B85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2397618$29F48618-8AAE-4174-8C0C-2FD9DA47AE4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ccf6cf9514426243b160a3a06e070c16a64dbff","datavalue":{"value":"11G20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2397618$B92BF2E1-FEF9-40FD-AC90-A0BA90012B8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2d47f0f7476488dd6b6b2436fba2dc33e26dfd17","datavalue":{"value":"14H05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2397618$FBD148EB-BAD9-440F-B094-31DC401F14A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"db2b8853a52c7f02af86453b6ee74c018fc3284f","datavalue":{"value":"14H25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2397618$9A9768AD-1EB1-4410-8DFD-5A2A3534231A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b1e817a7a1e05f89fa0d85b4587e5e12dd61d307","datavalue":{"value":"6722479","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2397618$8338950C-1551-40D2-B4E1-DFF167D0FC02","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e50b734d7a3583a654f5eb3937fc5e003966b3cc","datavalue":{"value":"automatic sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q2397618$08846051-ED6A-4C31-A47A-1C26075283FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3590eb8b47f26c41d61639b5166afe44752133e","datavalue":{"value":"formal power series","type":"string"},"datatype":"string"},"type":"statement","id":"Q2397618$C5E5716D-1975-44A2-8760-474FAAE45CC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d516c22531720e4453e883202f4d4205efddf019","datavalue":{"value":"algebraic curves","type":"string"},"datatype":"string"},"type":"statement","id":"Q2397618$1E683B2A-D5B8-4FB2-8AE2-591A46C3B57D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac07c7d6c5cdc2dbc4590f3ecbac0ebb59196bea","datavalue":{"value":"finite fields","type":"string"},"datatype":"string"},"type":"statement","id":"Q2397618$96F62FA5-35A7-43E6-851F-56CC4FCA7990","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$74E5F572-EEBF-4687-B5AE-26160E71FE32","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5f6991293c1a355625eb782f4d0a0748d5f2b2e5","datavalue":{"value":"W2423014504","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2397618$A1005133-1B85-45CC-AAD1-161DFF46E268","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e773fc5c920012d17cf64e9b90628f42ac0b786","datavalue":{"value":{"entity-type":"item","numeric-id":664335,"id":"Q664335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$E2996DAD-E768-4A20-AE67-D5E64EBBBCD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bcb75a349749941eebfaade2f75d01c63e89478","datavalue":{"value":{"entity-type":"item","numeric-id":5404648,"id":"Q5404648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$2A7B7F66-55B8-443D-96E3-2F6B1F678F51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"950f3bf0951443eb1e5bcbf62abe86752f7308ef","datavalue":{"value":{"entity-type":"item","numeric-id":4431260,"id":"Q4431260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$5F9B7DE6-BB23-4BAF-AFD4-ED07CC3B50E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8199cfc3eaffceac9735a00e8b928707bb9717a5","datavalue":{"value":{"entity-type":"item","numeric-id":3241273,"id":"Q3241273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$3371F37A-74F6-4EFA-B12C-08D9D218275F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"600d7be17304857c3a80394c2cb4b1f9d8930ef0","datavalue":{"value":{"entity-type":"item","numeric-id":1255781,"id":"Q1255781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$44F49BFE-6CA2-485D-92E5-7E5F11576B12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3afd0c4cd5e96965dc58343fdb8134a63c6270c","datavalue":{"value":{"entity-type":"item","numeric-id":3926680,"id":"Q3926680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$28CC9D32-B0AD-4685-B104-5612922020D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71fafffd6600066018fbade1968bde0808e2306d","datavalue":{"value":{"entity-type":"item","numeric-id":2457768,"id":"Q2457768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$9EFB22EE-53EB-4CC9-8371-413174C7A5BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36d84aa78f0d96f7d40459af01bc21793f5962fa","datavalue":{"value":{"entity-type":"item","numeric-id":4079524,"id":"Q4079524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$B67DC473-CB99-40B1-88C9-56348253FD02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6279ca15796647428fb79b7b22477fc7d5e838d2","datavalue":{"value":{"entity-type":"item","numeric-id":1969341,"id":"Q1969341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$40CEC6B6-774A-4043-A02F-2CB89BCA3530","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a51aca861fe78b6d65ad7f940be5bd838f88d21f","datavalue":{"value":{"entity-type":"item","numeric-id":1121952,"id":"Q1121952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$C620DC28-E0B7-48D9-BB19-7FCD811CEEA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89b8d34925123590e97396835d6e266910297ed6","datavalue":{"value":{"entity-type":"item","numeric-id":915794,"id":"Q915794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$EB3B500D-2E52-43F9-BC7D-223AB7848434","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83f629c180f6436ab6ea9a75b06b545548804bab","datavalue":{"value":{"entity-type":"item","numeric-id":4143433,"id":"Q4143433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$9E24DA2C-3AEC-4BBC-B51C-295A24A06C85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"face2e7e27151baf812189d1d7ab236fff1b6ae8","datavalue":{"value":{"entity-type":"item","numeric-id":3829621,"id":"Q3829621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$CBFBBC3B-93E0-4D18-98EB-8F018FDF17A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7779f790d7360fdf30d819fed13c80c73f9fe313","datavalue":{"value":{"entity-type":"item","numeric-id":3808194,"id":"Q3808194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$0374CD7A-0D86-49D5-9593-8806B9D568D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9caed992c28c62df1f1648c7aa91a03fdc3639c8","datavalue":{"value":{"entity-type":"item","numeric-id":3261838,"id":"Q3261838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$AE59FF75-50EC-4B71-9F7B-51D86E5404B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f99d516f03f630b465144bf2edfacff7e586661f","datavalue":{"value":{"entity-type":"item","numeric-id":3549457,"id":"Q3549457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$A8E34608-8A14-49C0-B592-5F1B6503FC9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36798c58369adb589e24b132bc9e998749698cf7","datavalue":{"value":{"entity-type":"item","numeric-id":3624407,"id":"Q3624407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$2BA2521C-82D5-4AFC-9AF6-7EDF6C821F5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"584ea5531b3c5b862220e7fd8ab5ff0b4431bd8a","datavalue":{"value":{"entity-type":"item","numeric-id":3539345,"id":"Q3539345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2397618$9F6CD8B4-C6D9-4A3C-B517-E443A3ADAA71","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4783355bb05ebdb8e5cc1d774b20cc60300470f4","datavalue":{"value":"10.2140/ANT.2017.11.685","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2397618$8841DF27-D5CA-4433-A557-3C6D77FB48FA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfc05c4cbe53dd28c645efe8354a04489f8e4ab3","datavalue":{"value":{"entity-type":"item","numeric-id":1382882,"id":"Q1382882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78fe809595ae286ec4c52daf3443024c3ad5c06e","datavalue":{"value":{"amount":"+0.7932702898979187","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2397618$371CBD09-92C4-482F-BF05-7E45E6A080A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96180f8d2b60cc6d17c1072541a740fe7168b9cf","datavalue":{"value":{"entity-type":"item","numeric-id":5936664,"id":"Q5936664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78fe809595ae286ec4c52daf3443024c3ad5c06e","datavalue":{"value":{"amount":"+0.7932702898979187","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2397618$D117ABC7-6597-43F0-A414-1E9F2C1A8221","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8812fa02e12a8a1c86ce6dfaebc9e44c8ec9fff3","datavalue":{"value":{"entity-type":"item","numeric-id":3798750,"id":"Q3798750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91da66900974f29aec40a60f8e4117b188976644","datavalue":{"value":{"amount":"+0.7880207300186157","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2397618$01A9B117-D271-4DB6-8AEF-9B52D9138239","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8a288d657b5ce0816faea757fb3f338b68d9c90","datavalue":{"value":{"entity-type":"item","numeric-id":1969341,"id":"Q1969341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1708ee9e305b6fd8b0caee9bf8ce2eb87517cdfc","datavalue":{"value":{"amount":"+0.784631073474884","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2397618$C4EB3ECE-E683-48BB-B7CC-DF360B9C1EC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7c7caeb71ab6fc9ab75bea48edec865f106eea0","datavalue":{"value":{"entity-type":"item","numeric-id":873839,"id":"Q873839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75dc895d303c5ddc5e0fbcdd86c0af2cbeb7c210","datavalue":{"value":{"amount":"+0.7846305966377258","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2397618$4DF6D01C-8F30-40A2-801B-6CED1935AFB8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2397618","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2397618"}}}}}