{"entities":{"Q1767486":{"pageid":1778228,"ns":120,"title":"Item:Q1767486","lastrevid":48433720,"modified":"2026-01-04T19:21:29Z","type":"item","id":"Q1767486","labels":{"en":{"language":"en","value":"Counting solutions to equations in many variables over finite fields"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2143886"}},"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":"Q1767486$57F7EFD5-10A8-4D42-8E2B-17C96A734A60","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"62ed78c61c04845611ac3791060048904e8ba5b8","datavalue":{"value":{"text":"Counting solutions to equations in many variables over finite fields","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1767486$46C39D76-B901-4E67-AE34-648BC6FA056F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6c6cd65ffcffeb326969e108d263f226e4f1a1ab","datavalue":{"value":"1076.11040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767486$AC212D45-3A69-4AF0-9F84-70F1B8DEEB05","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3a23d7ce6eeb5bf3de32b32f8ad6eae1208098ec","datavalue":{"value":{"entity-type":"item","numeric-id":1273219,"id":"Q1273219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767486$86D4D9E3-049E-44F8-894C-75FCBE2648E4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1de0dee9456ae54727642f6ba64e62fe6eaa93c2","datavalue":{"value":{"entity-type":"item","numeric-id":203859,"id":"Q203859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767486$2EFFA311-7419-489C-8086-958757D930C0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7a1e9f97959c3a0c8005f0f6e1f91f49b76b5347","datavalue":{"value":{"time":"+2005-03-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1767486$BB405609-A4D2-4CA2-B71F-2FDF37DC2C2D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"837eb51e84cb03b79d203482a10ce8ff1cef1934","datavalue":{"value":"Let \\(\\mathbb{F}_q\\) be the finite field with \\(q\\) elements. Let \\(f\\in\\mathbb{F}_q[x_1,\\dots, x_n]\\) be homogeneous of degree \\(d\\), where \\(n\\geq 2\\). For \\(k\\geq 1\\), denote by \\(N_k\\) the number of \\(\\mathbb{F}_{q^k}\\)-rational points on the projective hypersurface defined by the equation \\(f= 0\\). The zeta function of the projective surface defined by \\(f\\) is  \\[ Z(f/\\mathbb{F}_q,T)= \\exp\\Biggl(\\sum^\\infty_{k=1} N_k{T^k\\over k}\\Biggr). \\]  By a classical theorem of Dwork \\(Z(f/\\mathbb{F}_q,T)\\) is a rational function.  In this paper the author proves that there exists an explicit deterministic algorithm with the following input, output and bit complexity. The input is a polynomial \\(f\\in\\mathbb{F}_q[x_1,\\dots, x_n]\\) in an explicit Zariski dense open subset of the space of homogeneous polynomials of degree \\(d\\) in \\(n\\) variables over \\(\\mathbb{F}_q\\) with \\(\\text{gcd}(d,q)= 1\\) and \\(q\\) is not a power of 2. The output is the zeta function \\(Z(f/\\mathbb{F}_q,T)\\) of the projective surface defined by \\(f\\). The algorithm requires \\((pd^n\\log(q))^{O(1)}\\) bit operations.   An interesting consequence of this result is that for any explicit polynomial \\(f\\in\\mathbb{Z}[x_1,\\dots, x_n]\\), \\(f\\neq 0\\), and \\(\\varepsilon> 0\\) there exists an explicit deterministic algorithm which takes as input a prime \\(p\\), gives as output the number of solutions to the equation \\(f\\equiv 0\\pmod p\\) and takes \\(O(p^{2+\\varepsilon})\\) bit operations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767486$04B0BBCF-1033-40F8-BD35-F51DA9B7DDA3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fda67124f5cab049dd5667315a74bf87fdf7c975","datavalue":{"value":"11G25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767486$5887E7CE-01E4-455C-8FFB-309AB45C5684","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"528f7a48d12c334e1e8f805dbb30c6a6e0ed15e9","datavalue":{"value":"14G15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767486$B9ED0441-B29F-4331-9D7A-6D0229C7BA04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83f071a227a82a2fbae9e00865d40aae78fee790","datavalue":{"value":"11D45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767486$9D3799AE-E01A-4163-A644-E72E7A1A3468","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0e2417e055dac8201b2edbf4ce214140443124f6","datavalue":{"value":"11M38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767486$3E178697-34D2-477B-A646-262A039284EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767486$3C75C499-D50E-4187-B074-0FB1489D1BFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fef556d874a3250155d036ec9dcfe6f4f651276b","datavalue":{"value":"14F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767486$7E88461A-C77E-49B9-AF93-0840D10F87D6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"34ffc3c33f19f1f2ae401c54406ff7bb92637154","datavalue":{"value":"2143886","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767486$8DF38CF8-1BEE-4D74-8E74-F06DBD783D8C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3711b386902559bb22bf67091b7eca92012716a","datavalue":{"value":"finite field","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767486$1B56548A-E3C1-4AFA-B7EC-73E102AB1ECE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11661576ebffe728f3120d067317e0c5d14409dc","datavalue":{"value":"homogeneous polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767486$E6D71AEC-1E95-49C7-9929-5966898562B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"71911c8a7d6426551d2c7a6a7c6b0511ba23d5aa","datavalue":{"value":"projective hypersurface","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767486$B4029927-2509-48B2-A032-2F158042C7D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a18043ce842406adf7d9e4c8f3cd17b240a5165a","datavalue":{"value":"zeta function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767486$37D0B870-6B87-4A96-9148-D2C736622921","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767486$64888A5C-107F-4EFD-A3C4-23E64E947C42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c35e3bfd244e357b5a51ede57ec787c4ac84c884","datavalue":{"value":"Dwork cohomology","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767486$32B51FB1-C3DA-488A-951F-8D4A86C63116","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2d13e49d41df1f3f0b606434b67da3b14256111","datavalue":{"value":"deformation theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1767486$29D796D3-4982-4997-AF02-BFF3ADC6F823","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0c6b4cdaeea731b4d721d1e57817c51ed34c489d","datavalue":{"value":{"entity-type":"item","numeric-id":293716,"id":"Q293716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1767486$CAE0B7AD-2249-4E1C-B739-61297DDD0B33","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":"Q1767486$307516BE-C834-4634-B75B-A87027171974","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"300b08560a26b5acc2c54b86b0fe93db7934df10","datavalue":{"value":"https://doi.org/10.1007/s10208-003-0093-y","type":"string"},"datatype":"url"},"type":"statement","id":"Q1767486$46CA5DFD-955F-49AA-AA67-97C1EBB3F995","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1dd7016192b01392f2d4e8e51c90e6d52f7ba721","datavalue":{"value":"W2000578879","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767486$E77F2FD1-8647-49E4-A655-43E2AE148A96","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"633c25ee5de1bfc9afcf18d97c09fd1d67d99208","datavalue":{"value":"10.1007/S10208-003-0093-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1767486$0C8609DE-657E-48B3-B575-05DD59601B1B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfdf879111b57bf6e05302d87edd93dbcd02b52a","datavalue":{"value":{"entity-type":"item","numeric-id":4812523,"id":"Q4812523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aba76a5321198f0e7dd5cd9617e4a6b2a5f68c95","datavalue":{"value":{"amount":"+0.8599715828895569","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":"Q1767486$A9E3ECB2-8432-4C33-AEDF-1E7AD4FDC8BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49b3bef8232da608919da389408336bf0fe2bd44","datavalue":{"value":{"entity-type":"item","numeric-id":1029542,"id":"Q1029542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72c7ad92feb9665e1e7a473d9120d3832e0f08e5","datavalue":{"value":{"amount":"+0.8471373915672302","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":"Q1767486$ED7991D1-02C3-4FAC-8684-40873E09F722","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53d41fc3566e481bfa0e780f92cba61471e79119","datavalue":{"value":{"entity-type":"item","numeric-id":3615934,"id":"Q3615934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35de1949e1000a868b4c31c61f632c976870b326","datavalue":{"value":{"amount":"+0.8209684491157532","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":"Q1767486$CB634C2F-BA76-4ECE-90BF-92D28AC004CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35f5df7f55ced55e0af963470e759b44ecc5538d","datavalue":{"value":{"entity-type":"item","numeric-id":3548596,"id":"Q3548596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d4bc024dc381265f68971007afc980e65452ae1","datavalue":{"value":{"amount":"+0.8184728622436523","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":"Q1767486$C523BB89-7351-445D-AFBC-1819F4E8A2C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a6535dc2dc7e79dd5181619691b40aac3edcece","datavalue":{"value":{"entity-type":"item","numeric-id":5262784,"id":"Q5262784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03ae83107f8c850dac2e43ad00fb276060c513af","datavalue":{"value":{"amount":"+0.8142035603523254","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":"Q1767486$1274FAD5-5BF1-49A1-B7B3-56526A7B6DD7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1767486","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1767486"}}}}}