{"entities":{"Q1578508":{"pageid":1589248,"ns":120,"title":"Item:Q1578508","lastrevid":47015229,"modified":"2025-12-26T01:28:43Z","type":"item","id":"Q1578508","labels":{"en":{"language":"en","value":"Efficient \\(p\\)-adic cell decompositions for univariate polynomials"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1499172"}},"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":"Q1578508$ABE2122F-B267-4C35-8EAD-5CD3A4948AFD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e53fcd278cefec63dee3822af887b1096588cd51","datavalue":{"value":{"text":"Efficient \\(p\\)-adic cell decompositions for univariate polynomials","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1578508$0D47E336-24CF-4563-87E5-842033139F88","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a592fc6a0ff5e1451302b680ca931996afaaf9b6","datavalue":{"value":"0962.11039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578508$504BF3F9-26F4-4BD5-9859-4036621F85D1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"040b14cdd3aa90607fb117ee281442a7615a3d34","datavalue":{"value":{"entity-type":"item","numeric-id":876818,"id":"Q876818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578508$E55C7E44-F8D3-4F88-B091-937C55267C5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7de46e056e0bc651af8f502f6560d673e401ea54","datavalue":{"value":{"entity-type":"item","numeric-id":755676,"id":"Q755676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578508$047ECA1D-912F-42BD-A47E-8A38FF9D2EA7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f728e963338f0590fef2609026707340c65ee9d2","datavalue":{"value":{"entity-type":"item","numeric-id":162057,"id":"Q162057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578508$B438472C-3495-4EFB-B12C-7DD1C04C82D7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6eacf4c507e5bfaa195367e34eb507d8ad8ab29b","datavalue":{"value":{"time":"+2000-09-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1578508$9E49E7D7-29A6-435B-8F60-B264A87BE341","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"325b1aa0d9a7236a969d6ae13a5f40e9991ee93a","datavalue":{"value":"This paper follows the algebraic approach developed by \\textit{Cohen} (1969). Cohen's cells are sets of the form \\(C= \\{x\\in \\mathbb{Q}_p\\mid x= x_0+ p^a u\\), \\(u\\in \\mathbb{Z}_p\\}\\). Cell decompositions are a standard technique in the theory of \\(p\\)-adics: the \\(p\\)-adic numbers are covered by finite collections of cells, constructed so that on each cell the polynomial is ``well behaved'', in a specified way.    In this paper cell decompositions are constructed for polynomials \\(f(x)\\in \\mathbb{Z}_p[x]\\) of degree \\(n\\), such that \\(n< p\\), using \\(O(n^2)\\) cells. When \\(f\\) is square-free this yields a polynomial-time algorithm for counting and approximating roots in \\(\\mathbb{Z}_p\\).    These results extend to give a polynomial-time algorithm in the model for \\(f\\in \\mathbb{Z}[x]\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578508$2003BE19-1447-4971-8895-A75A09532D39","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2db7c2ef637f895a1617542f6fec055c0c00e7f5","datavalue":{"value":"11S80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578508$DBC5452F-536E-4D79-88EA-99850CF084DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578508$90750999-704A-45EA-A500-95B182B55181","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a470ca3704d22da637e23b90becb1551cee1a253","datavalue":{"value":"11S05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578508$C63FBA6F-B41F-4A33-B80C-91266DE2A478","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4f41f645805b4459bebbafbd0cbee79555533b95","datavalue":{"value":"1499172","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578508$A900756B-3901-4700-91EB-690BC608B030","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"171a7b1b31430e53ea7e3d70fd2639e541be22d5","datavalue":{"value":"Cohen cells","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578508$D2973367-45B9-4225-AA6C-8CAD476CFF90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"040f0fc4a150fc0d66e7f8c63eeccfabb8fddb9b","datavalue":{"value":"cell decompositions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578508$61B81FBB-3083-4B44-A432-859FF7D963FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90de93f86e91936d29a76bdc1f2638454ef51f34","datavalue":{"value":"\\(p\\)-adic numbers","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578508$72B5451B-0B23-4C1D-BA59-623AFFD7B9F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578508$EA5CAFF5-4725-4524-A20E-4EA66847198C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"35ea846fbd37eef2bf04aa3916128060dde76b2f","datavalue":{"value":{"entity-type":"item","numeric-id":277571,"id":"Q277571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578508$F92A9984-71C4-453C-A5CF-BA5A150D4E43","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":"Q1578508$102E5361-94EA-44A0-8912-0EE059DC9FA1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4dc43d0479bd208b7eea03972728fcc1ee23b7e3","datavalue":{"value":"https://doi.org/10.1006/jcom.1999.0520","type":"string"},"datatype":"url"},"type":"statement","id":"Q1578508$E02C3B5C-24E0-42AF-A565-54A5FD25ABA6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"239d0eadfb61eae0bb04b957fdbf4322da76429a","datavalue":{"value":"W1979747255","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578508$21564D6C-39F0-4772-85AA-ADCCE3913A43","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1efc6d224ffe0d7322355df220a9a0a92863a911","datavalue":{"value":{"entity-type":"item","numeric-id":4729768,"id":"Q4729768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578508$F8C46E77-A1AF-4BEE-B4E7-614D31EBDB19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"671e3e5cc6049d11acb4210fe316f19f166497cc","datavalue":{"value":{"entity-type":"item","numeric-id":3726220,"id":"Q3726220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578508$CE804CB1-9C7D-479E-B725-3626BE3463E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f215b4be5d109fd9d816f69f638d95cc094372e","datavalue":{"value":{"entity-type":"item","numeric-id":5552751,"id":"Q5552751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578508$C5699774-203D-4494-81A3-358DD8C3AD4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"661e527ee52403f296d6d8813ef2cce6a7d0bcc8","datavalue":{"value":{"entity-type":"item","numeric-id":3708875,"id":"Q3708875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578508$6604ACD0-9DA1-4825-89D9-29AF911AA7C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1f6aa5a7dbb8eced91175201c5b61a84466f7ef","datavalue":{"value":{"entity-type":"item","numeric-id":3259107,"id":"Q3259107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578508$3A8BE223-A697-4EA1-BD73-6F5BF405677D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49277a830e62c64c6bddf874b08b88e6e61070d9","datavalue":{"value":{"entity-type":"item","numeric-id":4138813,"id":"Q4138813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578508$3736ECB3-6C77-405E-BCEE-ACAA3D9B6A01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0422dbaab910c5a7f3e097381b94ce94eaaf540","datavalue":{"value":{"entity-type":"item","numeric-id":3321471,"id":"Q3321471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578508$F2F9A4A0-85B4-42B3-A7FA-C426E5D64856","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8f4ac3f710aa0e3501adaea85266318426047f5","datavalue":{"value":{"entity-type":"item","numeric-id":2520840,"id":"Q2520840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578508$7B2D7694-8BB0-495A-88AA-A9EE77BCD5D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fe24a9c1333654b6bba320bd8604b0aafcd0166","datavalue":{"value":{"entity-type":"item","numeric-id":1368832,"id":"Q1368832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578508$9B0129D4-7B50-42B5-8A9D-3E182D653BC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6f0b37435a4ca25cb57e0b1193e0c76d2ffda8e","datavalue":{"value":{"entity-type":"item","numeric-id":4717952,"id":"Q4717952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578508$C7F53D39-7BFD-4C21-9A3D-269286E8BBC4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"854c78662a638ae3f5d5628f6e7565423c498c96","datavalue":{"value":"10.1006/JCOM.1999.0520","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578508$A7BE8B7C-CAEE-434E-B506-C979BD903203","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b51186407af574e77322bac3938889784c0823d5","datavalue":{"value":{"entity-type":"item","numeric-id":3021921,"id":"Q3021921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24df71d48738a2fc7b56f71734ce756a59a86ee9","datavalue":{"value":{"amount":"+0.7722687721252441","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":"Q1578508$6A9AFE3D-1EBA-41C9-8A7D-8655A5228F98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e2c9636e8a8913996a5a3691ae4ea549a20de85","datavalue":{"value":{"entity-type":"item","numeric-id":4010518,"id":"Q4010518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e452ff28d04d3c82da082ccd8fc58d9c53924ef5","datavalue":{"value":{"amount":"+0.7671495676040649","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":"Q1578508$102434D4-9CBD-45A6-936C-1035B30A4C71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b888d29bb152aa4b8fbbdd60529cf61fa9f2780","datavalue":{"value":{"entity-type":"item","numeric-id":2739443,"id":"Q2739443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e177ce5fdaac3d6602893b29ae61f85a685cc42","datavalue":{"value":{"amount":"+0.7646647095680237","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":"Q1578508$481BA52D-3C5B-4F94-AAE2-158A755DB839","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1578508","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1578508"}}}}}