{"entities":{"Q1034545":{"pageid":1036393,"ns":120,"title":"Item:Q1034545","lastrevid":69472578,"modified":"2026-04-13T07:14:16Z","type":"item","id":"Q1034545","labels":{"en":{"language":"en","value":"Almost vanishing polynomials for sets of limited precision points"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5626904"}},"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":"Q1034545$447CAC3C-C5A5-4044-A0AF-984C697F853F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"efdc4a87ac0eec4966a6049f488ab840305d8d53","datavalue":{"value":{"text":"Almost vanishing polynomials for sets of limited precision points","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1034545$B2589C4B-5E66-43DF-A347-48456E368593","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3af81360e6a1ce968602c035df7860b94522187c","datavalue":{"value":"1203.13029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1034545$FEFC7821-45ED-4022-B1E2-1BE50D500660","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d90203b18b5c8f9a79668ef74a8911ad15dc0c97","datavalue":{"value":{"entity-type":"item","numeric-id":247261,"id":"Q247261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034545$D9AD6241-09D4-4A1C-B656-98BDE08F8AF5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea72303f92787da89554ee5fa15621068821a762","datavalue":{"value":{"entity-type":"item","numeric-id":99061,"id":"Q99061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034545$148A4478-6DAE-4238-8A2C-DA03B3603CA8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5c80b38051786df2940873db0a591fda80f5fbfc","datavalue":{"value":{"time":"+2009-11-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1034545$43EDE5D5-9DE8-4232-9838-A8AF33D086DB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7bb649d8fa1395db459036df0fa3f979e33f4078","datavalue":{"value":"https://arxiv.org/abs/0807.3412","type":"string"},"datatype":"url"},"type":"statement","id":"Q1034545$55E4B8FE-5BC8-49EE-B631-EE77A2341CCF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"56b2162799b76c2fa9e0ac9dac97ad973ee8e727","datavalue":{"value":"Given a set \\(\\mathbb{X}\\) of \\(s\\) points in \\(\\mathbb{R}^n\\) whose coordinates are known only with limited precision \\(\\epsilon\\), each `admissible perturbation' \\({\\tilde{\\mathbb{X}}}\\) of \\(s\\) points whose coordinates differ from those of the original set by less than the specified precision are possible candidates for the `true' set of points. Thus there are multiple possibilities for specifying a set of polynomials to describe \\(\\mathbb{X}\\), depending upon one's goals.  In this paper, the author presents an algorithm which produces a set of polynomials \\(\\mathcal{J}\\), with support \\(\\mathcal{O}\\), that describes \\(\\mathbb{X}\\) and all of its admissible perturbations in the sense that the polynomials are `almost vanishing', w.r.t. the norm of their coefficient vectors, at the original set of points and each of its admissible perturbations. Additionally, if there is a `nice' geometrical structure upon which all of the points of some admissible perturbation lie, it is \\textit{possible} (though not guaranteed) that the algorithm will find the polynomial(s) describing the structure.  The algorithm, appropriately named the ``numerical Buchberger-M\u00f6ller (NBM) algorithm'', is based on Buchberger and M\u00f6ller's algorithm [\\textit{H.M. M\u00f6ller} and \\textit{B. Buchberger}, in: Computer algebra, EUROCAM '82, Conf. Marseille/France 1982, Lect. Notes Comput. Sci. 144, 24--31 (1982; Zbl 0549.68026)] which, given a term order \\(\\sigma\\), computes the \\(\\sigma\\)-Gr\u00f6bner basis GB of the vanishing ideal of \\(\\mathbb{X}\\). The NBM algorithm is appropriately modified to handle approximate data: A key requirement of the Buchberger/M\u00f6ller algorithm is the ability to assert the linear independence of power products evaluated at a set of points. The NBM algorithm accomplishes this in the presence of limited precision by using ``the sensitivity of the least squares problem''.  The modified algorithm does not, in general, produce a Gr\u00f6bner basis of the vanishing ideal of \\(\\mathbb{X}\\). However, the author gives several examples where it produces `approximately vanishing' polynomials describing the geometric structure(s) from which the test points were perturbed. The algorithm has been implemented in the \\texttt{CoCoALib} (\\texttt{CoCoA} release 4.7, available at \\url{http://apcocoa.org}) under the name \\texttt{StableBBasisNBM5}.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1034545$30657133-A0AE-48AD-BF4C-3AC9FF0E509A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"173b0c3afec7c4f9f987722665cc7bdb6b8f5813","datavalue":{"value":"13P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1034545$7C551CA7-48A3-4AD4-A0C3-EF11FBEE4637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e57e2977a9ed0e05339dd5f1673c9f0c9ab91235","datavalue":{"value":"65H10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1034545$890A5A95-7653-4963-A3C7-9723C8CE7B24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"faf5fa4f05db998aa651c0c32ce49d873d9dceaa","datavalue":{"value":"14Q99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1034545$FD71DF7F-0021-4142-BF6A-C33438D8AC25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"28cc557c6c35aaa162b4d5c0a30d55d28da55f24","datavalue":{"value":"26C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1034545$B6BA6CFB-0127-44DD-B393-E221F3A5C0B3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ed64503cd65fa0563f18ac61fa60fa34c000e0c6","datavalue":{"value":"5626904","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1034545$464976B5-7880-4131-AE5A-9472AA5A1311","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06c861732a238ced000f0a7e08213f6dc45eae10","datavalue":{"value":"vanishing ideal","type":"string"},"datatype":"string"},"type":"statement","id":"Q1034545$2AFDA9AB-3A33-40DD-9ED8-29D3D9AFB4CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d841070a32f52a1a3e89bbc5481c0e30f663f249","datavalue":{"value":"border bases","type":"string"},"datatype":"string"},"type":"statement","id":"Q1034545$E25DA6DD-4DE9-446B-B505-4D10126A7C21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99c239dc77a316f7da47f9d2d7c645993f6cd8d7","datavalue":{"value":"Gr\u00f6bner bases","type":"string"},"datatype":"string"},"type":"statement","id":"Q1034545$1F8DB36E-0BDD-4B72-908E-0C2D616188F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89f0fe694d10aa18a146b73013160c974d0122a8","datavalue":{"value":"limited precision data","type":"string"},"datatype":"string"},"type":"statement","id":"Q1034545$046E9968-698B-456E-988A-8D258A01C3D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a5df109e74d26d1a83e8bb5762edaf35c4cb253","datavalue":{"value":"stable order ideal","type":"string"},"datatype":"string"},"type":"statement","id":"Q1034545$869BCA1D-C55E-4773-958F-E48C33DAD4F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66c7e13a8c0c04a672782837171d69f1b0b82c77","datavalue":{"value":"\\texttt{CoCoA}","type":"string"},"datatype":"string"},"type":"statement","id":"Q1034545$CB886FDC-2369-4B11-9EF7-BA8ADAA5DE3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5677dc1aeedd1fbf8738138bcce0b87747c5e39","datavalue":{"value":"approximate vanishing ideal","type":"string"},"datatype":"string"},"type":"statement","id":"Q1034545$EB67765C-4085-4CB6-B892-BE8EFEC88FF7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4f216bf5315f119cd6b8e6e21478a01c8d73dc22","datavalue":{"value":{"entity-type":"item","numeric-id":1264427,"id":"Q1264427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034545$E7158694-14A6-44AE-B9F9-12E036D118FA","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"fa859a176b380c904926f72bb8898555ec74f098","datavalue":{"value":{"entity-type":"item","numeric-id":18764,"id":"Q18764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034545$BE44E8C1-B6D8-477B-BAEA-F1DEB12BD45C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"c9c1f58b8025297b76815155d9e858d1b402d938","datavalue":{"value":{"entity-type":"item","numeric-id":12911,"id":"Q12911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034545$8A953791-F0AC-42A6-93A2-3111CB31F010","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"bc2b2680c6c8d1107d491dd7bc325e46943fcb90","datavalue":{"value":{"entity-type":"item","numeric-id":12912,"id":"Q12912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034545$6B35409B-E7C2-4450-B68A-8DF63BF94884","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"01c2299540ebf147301373cf1e74a8061493ffb4","datavalue":{"value":{"entity-type":"item","numeric-id":18472,"id":"Q18472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034545$CDEDA345-5324-4E28-ACBD-A95D18F8789C","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":"Q1034545$C2CD1817-ECD6-4F5A-B17F-12D619122709","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7883e1b0e861433ce94128640d5df7feab35b81d","datavalue":{"value":"W2017337676","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1034545$8C95597A-3FD4-419C-9FBC-3E923159BBBC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3da693f69996519ad8727e60b47359aaa502ba9","datavalue":{"value":{"entity-type":"item","numeric-id":2468362,"id":"Q2468362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034545$65CE20AF-671D-44C4-BF33-E51370821EEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f079d03a00d969fb408643990534ef96b2fbd1de","datavalue":{"value":{"entity-type":"item","numeric-id":999088,"id":"Q999088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034545$91287231-0425-41BA-91E7-E8C0EED7820A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"832e3ccd914223ef7a030ab6742847f050ecf758","datavalue":{"value":{"entity-type":"item","numeric-id":3341887,"id":"Q3341887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034545$097A228F-C47F-40FF-9A8B-BCD1F443C9C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"028674f36489448e2bfe8c75d587bf81f7f59376","datavalue":{"value":{"entity-type":"item","numeric-id":731932,"id":"Q731932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034545$0B1EFEE5-2FE2-461F-8E6D-D5E8C3F91F29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43ce7fb3f0d696969f04465b66d8551230e5915e","datavalue":{"value":{"entity-type":"item","numeric-id":4325914,"id":"Q4325914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034545$BDA1C0C2-3BA8-417C-8C38-7C4879FF1353","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8eeaa7dfd1d5aa46fe4ef30cb5d8e2f1a04648ae","datavalue":{"value":{"entity-type":"item","numeric-id":4507801,"id":"Q4507801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034545$5AD4A95D-5879-48E6-A681-5AC3948D6C75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39f0ca245493771193c72b8e649abd5334ef4752","datavalue":{"value":{"entity-type":"item","numeric-id":5317677,"id":"Q5317677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034545$B1B70580-3A08-46EC-B062-8F5FD2F840C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eeb39a2facd34aabea069787364dafa7c0676769","datavalue":{"value":{"entity-type":"item","numeric-id":2458336,"id":"Q2458336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034545$30676E3A-87DA-4EE7-B5B5-D69AD131B7F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cfe615ea5f7186e72efc9cb84dbfcd4f1df54c4","datavalue":{"value":{"entity-type":"item","numeric-id":1565834,"id":"Q1565834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034545$D49901C4-A5B7-441B-8858-675D38BD386F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67fa8b9d59ef163551dbe1443d99ac92693ebb1c","datavalue":{"value":{"entity-type":"item","numeric-id":3156429,"id":"Q3156429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034545$65506594-8F18-447F-AC4E-89081D081C5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7dab45334e3943852955e00477efebd5f8b8388f","datavalue":{"value":{"entity-type":"item","numeric-id":4825151,"id":"Q4825151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034545$3C04B18D-72A8-4782-BF56-69A333B47EB6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"edf230d812f718e3d43e6fa759d533aa850b701b","datavalue":{"value":"10.1016/J.JSC.2009.06.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1034545$A2818881-BDCD-4A80-9A25-AC32F0F7E06C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a205258768ca109adcf59b923fdfefcefffa5fa6","datavalue":{"value":{"entity-type":"item","numeric-id":731932,"id":"Q731932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d91b8b35ad84d16b50ad8eb935bf5fdcf748b98a","datavalue":{"value":{"amount":"+0.8313940167427063","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":"Q1034545$61FE8B8D-4448-4431-A564-FA702F459889","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22e62dc0b4f1958315532ca6218ddeafe3a04aaa","datavalue":{"value":{"entity-type":"item","numeric-id":2458336,"id":"Q2458336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7feb7fb0a0d40ca827112474a886a77dcb4bcc7","datavalue":{"value":{"amount":"+0.828135073184967","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":"Q1034545$FFD9132D-898E-48FC-890B-7D8DF5A3A991","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"282fa6004948a30e62ca105acbcb7410d16703f0","datavalue":{"value":{"entity-type":"item","numeric-id":3110293,"id":"Q3110293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efe1aa59a1c574c4bbc198df896b74d4741f9202","datavalue":{"value":{"amount":"+0.7876275181770325","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":"Q1034545$6BB12AFE-5BB7-44A0-8B18-9D9EFFA751BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d865185e637b8e2d2ff1072f57e2c0a71ece0b0e","datavalue":{"value":{"entity-type":"item","numeric-id":4627683,"id":"Q4627683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90749ba5baebd00fda7c7666faf50817c593e721","datavalue":{"value":{"amount":"+0.7850102782249451","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":"Q1034545$3665A6F6-6C5A-4E76-A2E3-D7A6E182481A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba4c01ce8e8e2ac6b8dcd931af251850abe27e89","datavalue":{"value":{"entity-type":"item","numeric-id":385012,"id":"Q385012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e4773d108d40ba3e7c8892bef0b8f46e3d5b32b","datavalue":{"value":{"amount":"+0.7763260006904602","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":"Q1034545$29BC3639-3F6F-4C1F-B01B-454389B01771","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Almost vanishing polynomials for sets of limited precision points","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Almost_vanishing_polynomials_for_sets_of_limited_precision_points"}}}}}