{"entities":{"Q640803":{"pageid":642651,"ns":120,"title":"Item:Q640803","lastrevid":57113235,"modified":"2026-03-26T16:27:46Z","type":"item","id":"Q640803","labels":{"en":{"language":"en","value":"A nearly-optimal method to compute the truncated theta function, its derivatives, and integrals"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5960718"}},"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":"Q640803$8548E6A8-DEF9-4E4C-A19A-A1C085167BD9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0e6f9fe1b2c4266ec1bcb38e8830a20388a7eb61","datavalue":{"value":{"text":"A nearly-optimal method to compute the truncated theta function, its derivatives, and integrals","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q640803$DC7A8886-37EA-4F75-A595-ADF988B2F684","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bd14a5830467f6e61618bad4613e8b45a168c926","datavalue":{"value":"1243.11117","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640803$034BFA64-D562-4AB3-9D2B-CBA80BF4E6DF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"92e60bc454a6c55b384734c1f70bfc0961ab2144","datavalue":{"value":{"entity-type":"item","numeric-id":640802,"id":"Q640802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640803$D447F91A-D19F-4FFB-A21C-E58E2B9ACECB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"553c7ad508f4615999d4ef926cfdf75d436f510c","datavalue":{"value":{"entity-type":"item","numeric-id":175062,"id":"Q175062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640803$7F639A56-CE93-4032-95E0-C35EDC31AF90","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b69bc7fde4176f984e607281ea120e74d6960617","datavalue":{"value":{"time":"+2011-10-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q640803$BDE3EE26-7BD1-44AF-AD34-3381721C7695","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7ea002bbf8c3540451837375e0ee21a3f4f0d98d","datavalue":{"value":"https://arxiv.org/abs/0711.5002","type":"string"},"datatype":"url"},"type":"statement","id":"Q640803$F3FA18C4-64D8-45E4-B117-668E3A53D459","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b15dbdc20e89a21199b66a9907beb9faf5cc8934","datavalue":{"value":"This paper describes an iterative procedure for the approximate evaluation of exponential sums of the form  \\[ F(K,j;a,b):=K^{-j}\\sum_{k=0}^K k^j\\exp(2\\pi iak+2\\pi ibk^2), \\]  for non-negative integers \\(j\\) and real parameters \\(a\\) and \\(b\\). It is shown that there are absolute constants \\(\\kappa\\) and \\(A\\) with the following property. If \\(\\varepsilon<e^{-1}\\), and if \\(\\nu:=(j+1)\\log(K/\\varepsilon)\\) then for any positive integer \\(K\\), any non-negative integer \\(j\\), and any real \\(a,b\\in[0,1)\\), one can evaluate \\(F(K,j;a,b)\\) to within \\(\\pm A\\nu^{\\kappa}\\varepsilon\\), using at most \\(A\\nu^{\\kappa}\\) arithmetic operations on numbers of at most \\(A\\nu^2\\) bits. Loosely speaking this means that one can evaluate \\(F(K,j;a,b)\\) in polynomial time.  The basic idea is to normalize \\(F(K,j;a,b)\\) so that \\(0\\leq b\\leq 1/4\\). One then applies the van der Corput B-process so as to transform \\(F(K,j;a,b)\\) into a linear combination of terms \\(F(K',j';a',b')\\) with \\(K'=[a+2bK]\\), together with various error terms which are considered at length. Since \\(K'\\) is (essentially) at most \\(K/2\\) one reaches sums of trivial length in \\(O(\\log K)\\) iterations.  The basic theorem is applied in the author's work on computing the Riemann zeta-function [Ann. Math. (2) 174, No. 2, 891--946 (2011; Zbl 1243.11118)]. A second application, described in the present paper, shows that one can find the number of solutions to a congruence of the form  \\[ \\sum_{i=1}^n(a_1k_i+b_ik_i^2)\\equiv 0\\pmod{M} \\]  with integers \\(0\\leq k_i\\leq K\\), in time \\(M(MK)^{o(1)}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q640803$134DEE84-D0D3-4EDC-92CC-416FE90BC53A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640803$E46F1F31-58D5-4C52-ABFF-FA65C26A7C92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3712e16db20438a95aed4eaea58fd3550f6638c4","datavalue":{"value":"11L15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640803$915B0BC4-A70A-4862-AE45-21ABA0CF0F2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8934daafe177ca6a34713db654e3be7923140375","datavalue":{"value":"11Y35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640803$D2D6BA0B-8D5A-459E-A4DA-2F7BA811814E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7611e57e2a4c78fc8ea159241004f360760d30a8","datavalue":{"value":"5960718","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640803$8491ADF8-F0B9-457D-A17D-3A8D2121C566","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75c48417838c73f6ae60c6cc1411bb16ed114357","datavalue":{"value":"exponential sum","type":"string"},"datatype":"string"},"type":"statement","id":"Q640803$A33D958A-A91F-4F31-AC73-462B1289297D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90b2ed3c130c30bac7174fa9b54a06645cc1227f","datavalue":{"value":"computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q640803$0F19CCD6-752A-4941-BE33-E35A0F3719EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q640803$F8B699AA-2C8E-4365-A8DA-4A2A4A7EA344","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62f906d34f614a64371bca7c057d4124a85f6c9a","datavalue":{"value":"quadratic polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q640803$F1F19CC0-553F-4E2A-A762-E3B4B923D741","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a5825a50171de7e7ac2aa9c081dec0b769185a6d","datavalue":{"value":"B-process","type":"string"},"datatype":"string"},"type":"statement","id":"Q640803$34D4A410-D9D5-4C3A-A6D1-BF956633FA9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"97a3580fefb9f9a05b9104da92afdd215835bc22","datavalue":{"value":"transformation","type":"string"},"datatype":"string"},"type":"statement","id":"Q640803$513EF980-3D3A-4C13-A156-8F73C1D1E5D0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8f9d2210fd31daf1b0c32117558fba88c34088c9","datavalue":{"value":{"entity-type":"item","numeric-id":177007,"id":"Q177007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640803$F369A908-7ACA-4B70-A5D5-A4D424FF052E","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":"Q640803$30D10FF6-E00E-41CA-AA9E-9E4B7C8E85C5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d8d0247dabee86b458d95817aedbc80f706e632c","datavalue":{"value":"W2154953962","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640803$FAE632F3-14F5-4B67-9AFA-FCFDAAF023BC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fac52b4bbc73b71b26aba705170eb05d66db2ce","datavalue":{"value":{"entity-type":"item","numeric-id":4520255,"id":"Q4520255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640803$525D630A-4E11-4B24-A700-237A1C813394","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ae31c475bd2146f75c3e332b9c3ca45d243e2d0","datavalue":{"value":{"entity-type":"item","numeric-id":2732559,"id":"Q2732559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640803$B24DFDF5-2578-4AAA-ADE2-BAFEF4F060EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ec19ca13c38e7210b34c01b443529e66a825fe7","datavalue":{"value":{"entity-type":"item","numeric-id":4692762,"id":"Q4692762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640803$A8753C63-2F29-4DBD-B566-2F2FD24FD5F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c04189343926195d95742f6593ff94c530719a5","datavalue":{"value":{"entity-type":"item","numeric-id":640804,"id":"Q640804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640803$AB42469F-8E63-4575-9712-41B0FD2983EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4f7eb6f8a7d0c68b1c8757ac4cf298229a6ed53","datavalue":{"value":{"entity-type":"item","numeric-id":4893761,"id":"Q4893761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640803$6B62B211-70D3-4E54-8892-09BA2BCF0A1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4eb723e37e1deffaeaf389c8229da7c2dba852df","datavalue":{"value":{"entity-type":"item","numeric-id":5703969,"id":"Q5703969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640803$95237680-C0CD-4F4C-B2E9-6BE86F294194","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac537c87ebc9d83909a56086879ff01950d286b2","datavalue":{"value":{"entity-type":"item","numeric-id":3024118,"id":"Q3024118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640803$DEA19113-4CDF-48B5-9C66-AB7A95E32A7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0faf3c14b36fecc0a37a26c5c339ea808a1cfcb","datavalue":{"value":{"entity-type":"item","numeric-id":4003239,"id":"Q4003239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640803$72F2176F-22B3-43ED-A6CE-561B2788F323","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3adbed9afbf4e4f4ef2d884e3c10ef1245f6016","datavalue":{"value":{"entity-type":"item","numeric-id":1876232,"id":"Q1876232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640803$D943AE7E-AC69-4B3C-8F70-88C0B10550F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e17b872abab44825effcecfedf3d7b6e89abcd5e","datavalue":{"value":{"entity-type":"item","numeric-id":1838549,"id":"Q1838549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640803$E95F9002-6113-4EF9-A232-3B21B0D5A0C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"162307fb0ced465259be4de97702c2401ace600a","datavalue":{"value":{"entity-type":"item","numeric-id":3487499,"id":"Q3487499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640803$73713FCB-A43D-40AD-8E40-A88B51D302A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ed3f79f18d598d7773662b18dc1e8d13ab06f54","datavalue":{"value":{"entity-type":"item","numeric-id":5482844,"id":"Q5482844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640803$DE8BCA1C-D8A6-48FB-9F61-6A47B7D9E385","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9018f87737e241c9efb83879b029bb382b55d8d","datavalue":{"value":{"entity-type":"item","numeric-id":1812812,"id":"Q1812812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640803$313EAB1A-0AB9-42B1-93EB-9E4660EC7D50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf9b43bb259d051f6e312dbb5997a6b7ba416319","datavalue":{"value":{"entity-type":"item","numeric-id":3735790,"id":"Q3735790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640803$75987982-7383-431B-9C54-8C093F296136","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ff1bffa77604f4c8b521b88b75870874b2f234e","datavalue":{"value":{"entity-type":"item","numeric-id":5830713,"id":"Q5830713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640803$AEE2B060-6702-4B4B-87FE-3B386D4A808E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"43d3fee2274e63ae90b76f2cb7ce2a2de45e7800","datavalue":{"value":"10.4007/ANNALS.2011.174.2.3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640803$C2FBAAEE-D71F-457A-B574-EEA7AD8AD113","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e1cc53a2e0d94c7f4b127b8561f1b98e7e80e24","datavalue":{"value":{"entity-type":"item","numeric-id":5501151,"id":"Q5501151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"075109f069d598892d65eedf71686045aa49dc74","datavalue":{"value":{"amount":"+0.8228520154953003","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":"Q640803$C407C584-2EF3-47A8-895F-5B9A81857A66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"389013931d92a0af33e140381a6d197dee36d7ec","datavalue":{"value":{"entity-type":"item","numeric-id":640804,"id":"Q640804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"08a09f6acb11341b7efb57744386864c39cb6039","datavalue":{"value":{"amount":"+0.783696174621582","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":"Q640803$96E09E91-4AD2-4E88-9CC9-2C072BA98812","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"546fef31b5a8278657481f2cf345bb8a46c76b19","datavalue":{"value":{"entity-type":"item","numeric-id":4605708,"id":"Q4605708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9fea3261013877558de94be6428268f70aabea2","datavalue":{"value":{"amount":"+0.7594985961914062","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":"Q640803$A32F88FB-602D-427A-BF44-EAA4A8347EBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"864f296128a367eec8af6638209ccf21cac1c0bd","datavalue":{"value":{"entity-type":"item","numeric-id":2708178,"id":"Q2708178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf1540ecb307515971fa6414e61d7b5a06ab9450","datavalue":{"value":{"amount":"+0.7557564973831177","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":"Q640803$28EA0D6A-5AF3-4CAF-A485-3C6E6951C64C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e6de37857d7520314d1df02980e0417e42ce68f","datavalue":{"value":{"entity-type":"item","numeric-id":3768988,"id":"Q3768988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8840e289cb31bdfd6bde26bc7a57f59266a3ba8","datavalue":{"value":{"amount":"+0.7528956532478333","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":"Q640803$C0127C9B-5456-4C91-9280-BF4E5E36CABD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:640803","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:640803"}}}}}