{"entities":{"Q2075306":{"pageid":2086048,"ns":120,"title":"Item:Q2075306","lastrevid":55870054,"modified":"2026-02-20T16:45:36Z","type":"item","id":"Q2075306","labels":{"en":{"language":"en","value":"Evaluation of polynomials over finite rings via additive combinatorics"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7473084"}},"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":"Q2075306$5DA02BFE-59D7-4AB4-AE2A-498215CF2C9C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"532423f9049e13852dd8d394954da06dfed558fd","datavalue":{"value":{"text":"Evaluation of polynomials over finite rings via additive combinatorics","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2075306$BBE4CFD4-084F-4DD6-902C-F62087688F3A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5d4adcb789606a129fa78fbb4e9a20acc170a757","datavalue":{"value":"10.5565/PUBLMAT6612208","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2075306$AB2F998A-21DB-404E-A16A-F9BC8F25CCC0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$9582B9F1-6C72-4427-9ECC-4826196742D0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ed4f513c94031f8bf32d9d524c1126dddff8b76b","datavalue":{"value":{"entity-type":"item","numeric-id":195374,"id":"Q195374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$9521E06D-CD11-42BC-AB15-45F303072BC8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"44a4e856a85631fb651bf9ad5803d8b27e9b05d7","datavalue":{"value":{"time":"+2022-02-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2075306$8D09B0F2-DC37-4FB4-9FD3-9AD1587936F3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f2bfe0aff6595fd30debb85fd1835763e32d3a10","datavalue":{"value":"https://arxiv.org/abs/1809.06543","type":"string"},"datatype":"url"},"type":"statement","id":"Q2075306$149C99F9-CDAE-4C65-856E-8FE71F04B22C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3e957bbf90c3c5903edc5d0375c334f7bdd976a8","datavalue":{"value":"Let us consider a finite ring \\(R\\) and denote by \\(R^{(i)}\\) an ideal that contains all the finite sums of terms \\(\\prod_{j=1}^i c_j \\), such that \\(c_1,\\dots,c_i \\in R\\). If there is a positive \\(i\\in \\mathbb{Z}\\) such that \\(R^{(i)}=0\\) the ring is \\textit{nilpotent} with \\textit{nilpotency class} given by the minimal such \\(i\\).  Let us now focus on two problems: \\begin{itemize} \\item \\textit{Equivalence problem over a finite ring:} is it true that two polynomials define the same function over a given ring? \\item \\textit{Equation solvability problem:} is it true that two polynomials over some ring have at least one substitution, where they get the same value? It is related to the existence of a root or for the solution of an equation. \\end{itemize}  These problems originate from ring/field theory and they have been investigated in literature. The first problem has been proved to be decidable in polynomial time on a nilpotent ring and to be co-NP-complete in the other cases [\\textit{S. Burris} and \\textit{J. Lawrence}, J. Symb. Comput. 15, No. 1, 67--71 (1993; Zbl 0779.16007)]. Also the second problem is NP-complete for rings that are not nilpotent. In [\\textit{G. Horv\u00e1th}, Algebra Univers. 66, No. 4, 391--403 (2011; Zbl 1236.16046)] the author proves that for nilpotent rings the problem can be decided in polynomial time. If \\(R\\) is our nilpotent ring with size \\(m\\) and nilpotency class \\(l\\), let \\(f\\) a polynomial over \\(R\\) in \\(n\\) variables, we call \\(\\|f\\|\\) the number of operations that define it (that is also the complexity of evaluating it at a point in \\(R^n\\)). Now, according to [loc. cit.] the substitutions needed to decide whether \\(f\\) has a root or not is \\(O(\\|f\\|^t)\\), where \\(t=t(m,l)\\) comes from the Ramsey number of a specific colored hypergraph and is a big number.  This paper reduces the exponent to \\(m\\log(m)\\), via additive combinatorics' methods. In particular, the main theorem says   Theorem. Let \\(R\\) be a nilpotent ring of size \\(m\\). For an \\(n\\)-variable polynomial \\(f\\in R[x_1,\\dots,x_n]\\), it can be decided in \\(O(\\|f\\|n^{m\\log(m)})\\), time whether or not \\(f\\) has a root in \\(R\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2075306$C1543A5D-3C5C-4559-9AA6-C2B8FC35BD42","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c6ce988fa7e5875f3ae97d2a288c07e1385ccc33","datavalue":{"value":{"entity-type":"item","numeric-id":480674,"id":"Q480674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$90952F7E-3EAE-496A-AA43-5A88539AFB7C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"09c34d6a9e51500cf32e007c02afdb05751a7030","datavalue":{"value":"16Z05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2075306$C6583D7A-F1E2-430B-A547-BDA49227CFB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4bceb4852f142c7ae840ef027a3d11ea672a1bc4","datavalue":{"value":"11B75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2075306$F9ED8830-43BD-48F6-80BA-E9A04BF7EAD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f360e274e44c6661f68cb82803afb25b4e85933","datavalue":{"value":"13M10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2075306$3B4EB402-BA25-4467-BD43-EFABF63FF6E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"46cc6f74904d93d783c1cf8007a9494ea0b980f2","datavalue":{"value":"16P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2075306$18B0DEAC-F322-4BD6-8A2D-5219A2059845","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"11a9c23b98d2f33fc17687d2807f8efe459d6bed","datavalue":{"value":"7473084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2075306$47E45571-58B4-45FF-9F07-E4E2C272500A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f76c961d13b0be6c6be0a730f3c9f86ee2be4ae6","datavalue":{"value":"additive combinatorics","type":"string"},"datatype":"string"},"type":"statement","id":"Q2075306$88592F59-9B79-42AC-88B9-FD767CB7B2F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c301a3092df2608b84876f2c61e85d4495dd95f3","datavalue":{"value":"Chevalley's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2075306$A545EC01-98B3-4436-81E1-C3505689E29E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b987be565609a99f8666695ba29384cff98521a9","datavalue":{"value":"dichotomy","type":"string"},"datatype":"string"},"type":"statement","id":"Q2075306$710CC897-4207-44C1-A635-4765FB9BCC3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19a7b2170c25fbffde0df33fce7fce707931081c","datavalue":{"value":"nilpotent rings","type":"string"},"datatype":"string"},"type":"statement","id":"Q2075306$ED08F751-2B76-435E-978C-58FD00168DAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b0119df19c82c5d6639c9b718f64ab0a4947437","datavalue":{"value":"Olson's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2075306$8D86092E-363F-4F14-98E1-61A2B42F2357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3165f528617525bcf4e7137e7ba02ca73240ea3a","datavalue":{"value":"polynomial method","type":"string"},"datatype":"string"},"type":"statement","id":"Q2075306$4D85F385-8DB3-4366-B104-9EE40C6C9443","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"275ce014b03a778b3a67bc42f16c700bd3acc16d","datavalue":{"value":"equation solvability problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2075306$DEC8DB60-A1BE-42E7-8EDA-A5F8A43780C9","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":"Q2075306$F5184D6D-1D6A-4776-A469-E8F0A1E1F9DC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"be7db333626b4af6a4d1f5926a14044d83f3eb91","datavalue":{"value":{"entity-type":"item","numeric-id":843593,"id":"Q843593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$AC642615-644F-4008-9418-A0E0893CB121","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"137be7bb46b7bcc3c5a7932a133f5c3d20af31b3","datavalue":{"value":{"entity-type":"item","numeric-id":653989,"id":"Q653989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$8FB14ACB-1774-4385-961E-88938BB6B29D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fa217a0c47396d6ab8ac4bc3663f02514d3e5be","datavalue":{"value":{"entity-type":"item","numeric-id":2366112,"id":"Q2366112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$A672689F-F982-42A1-AFBA-7B63481BF5FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a92bee14c1f5fa161696b9a19446326ed851f30e","datavalue":{"value":{"entity-type":"item","numeric-id":1840215,"id":"Q1840215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$069FFEDA-BCB6-43C6-AB2E-20A7CDFDA782","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7778d0975981c8bd2a8a99aab069a603ce718b5f","datavalue":{"value":{"entity-type":"item","numeric-id":2986663,"id":"Q2986663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$6F72D5FF-A3F9-4C5B-B6B3-8551757864BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f782269f0f8b46a09681f64cd29970f9d9696745","datavalue":{"value":{"entity-type":"item","numeric-id":3067781,"id":"Q3067781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$E8622316-CE8A-4DAB-A8F2-085EFE238F31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a73750d8f43d9587474cd54a0ab45809c28e57f","datavalue":{"value":{"entity-type":"item","numeric-id":652516,"id":"Q652516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$71AC3F64-3FD1-4F87-828F-D97F8C174F14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17d15d6f8472bca9e9c3f836d0853bcaf59e0f15","datavalue":{"value":{"entity-type":"item","numeric-id":2343499,"id":"Q2343499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$48D06492-7292-494E-BE22-CA63F621936F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22cc34e2b1a03db880ac158b96f94bc594065d1c","datavalue":{"value":{"entity-type":"item","numeric-id":5414556,"id":"Q5414556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$4C56D674-3B1B-4F49-A671-34C051962260","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"669646dc6c821a7e79d3f2e2788af0f95e160688","datavalue":{"value":{"entity-type":"item","numeric-id":1934970,"id":"Q1934970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$9C0932FA-6418-4CBC-AD68-3BB48E808686","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94e57296c2438ccd115121977cc1d0b48c250032","datavalue":{"value":{"entity-type":"item","numeric-id":758209,"id":"Q758209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$8475EF8A-37D4-44AB-A82E-FFFC09796E31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1163b75feea329c267b3957b69fa43261ded1771","datavalue":{"value":{"entity-type":"item","numeric-id":2655464,"id":"Q2655464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$AB70B46F-85AB-459C-9A1E-187A26B67106","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56a99194ffdcfb99e94dc45ea09f2903b01855db","datavalue":{"value":{"entity-type":"item","numeric-id":2531039,"id":"Q2531039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$771330D0-823F-477C-AFE0-A8A2332FB2F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8239bc34d68d16291764250f5261e8f500de57c1","datavalue":{"value":{"entity-type":"item","numeric-id":1211535,"id":"Q1211535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$A7D41451-8678-4922-91BE-40084C9E40AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"778ebebc3476a42954d13011cebbf7300b845339","datavalue":{"value":{"entity-type":"item","numeric-id":2491185,"id":"Q2491185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$A392A1B0-7AAC-441F-BC93-638CA8235E80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcde32a2f7e378b7951f262803337779a86e4f59","datavalue":{"value":{"entity-type":"item","numeric-id":4658713,"id":"Q4658713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2075306$69D45577-AE92-4867-8E8C-B774A840E8DB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f2f83d3f3af0610d9156c3f9f9c740ce23024ef","datavalue":{"value":{"entity-type":"item","numeric-id":652516,"id":"Q652516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee88edfdb2749046fbec6f7eb8c48ef67dae37cc","datavalue":{"value":{"amount":"+0.7762948870658875","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":"Q2075306$BF5B0C9F-B495-42CC-AEB0-33BD8BD9A63A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5fa744ac8e88b438a5f99140368b75538d05bbb","datavalue":{"value":{"entity-type":"item","numeric-id":3006615,"id":"Q3006615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3066e9acff7bb77fe77ed8fcec3679f43104678c","datavalue":{"value":{"amount":"+0.7482656836509705","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":"Q2075306$BD1D96A2-BC99-4CD0-95B8-4D36E5F2882D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78af9618de0f5c129baa94ecd9ef9cc94c84f25f","datavalue":{"value":{"entity-type":"item","numeric-id":3116848,"id":"Q3116848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4e2d5484265bc04e899f5df0336d8e785eb4e47","datavalue":{"value":{"amount":"+0.7280086874961853","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":"Q2075306$0096B067-798D-4170-A87C-8F404E3D0C6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28495ef39b5145a1c44799fb0dae182383722136","datavalue":{"value":{"entity-type":"item","numeric-id":2986663,"id":"Q2986663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd5664c91e8f03928b89231b6f77b1c8746cca06","datavalue":{"value":{"amount":"+0.7247123718261719","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":"Q2075306$286384BE-A8A2-432E-ABA0-914E22971B98","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2075306","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2075306"}}}}}