{"entities":{"Q1330880":{"pageid":1341630,"ns":120,"title":"Item:Q1330880","lastrevid":43033207,"modified":"2025-07-17T02:09:22Z","type":"item","id":"Q1330880","labels":{"en":{"language":"en","value":"Computing the Ehrhart polynomial of a convex lattice polytope"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 617323"}},"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":"Q1330880$FFF3E15B-CE3B-46A6-BF24-2626EDA3CA40","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6597e17c5d838d9fc228b87593af0297cd76d6dd","datavalue":{"value":{"text":"Computing the Ehrhart polynomial of a convex lattice polytope","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1330880$EC93F1EE-B794-4965-A98B-FC85E9F7029F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0c07a05712c148336f03c04138904fbcc247a95d","datavalue":{"value":"0804.52009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330880$CDB52ADE-C9A8-4209-800C-ACD42FF9FE84","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"02b03d15bde60c76e6f47b25c079f088a9122aaa","datavalue":{"value":"10.1007/BF02574364","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330880$EE574453-3423-483C-B76D-A7B657500D9B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330880$65A2D40B-02B4-499F-BF04-39462054C193","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fbc2ac0030a794298a44d66dd84da3932fc8da2c","datavalue":{"value":{"time":"+1994-08-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1330880$825F80A7-F26E-439E-93A4-13AD229C3233","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7d10fbac803e3a84a8a788387635b7c53439b6b5","datavalue":{"value":"https://eudml.org/doc/131316","type":"string"},"datatype":"url"},"type":"statement","id":"Q1330880$4461DA0D-FFAF-4A4C-ABAE-968D0EF38CA1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"686fec6100186f0352687e0ecb3c3b61c8997864","datavalue":{"value":"For a (convex) polytope \\(P \\subset \\mathbb{R}^ d\\) whose vertices belong to the integer lattice \\(\\mathbb{Z}^ d\\) the number of lattice points in \\(nP\\) can be expressed as a polynomial (in \\(n\\)) of degree \\(d\\), the Ehrhart polynomial of \\(P\\). (The constant coefficient \\(e_ 0(P) = 1\\), the highest coefficient \\(e_ d(P)\\) is the volume of \\(P\\), and \\(e_{d - 1}(P)\\) is half the volume of the \\((d - 1)\\)-dimensional `surface'.) Based on some identities of Morelli [\\textit{R. Morelli}, Adv. Math. 100, No. 2, 183-231 (1993; Zbl 0797.14018)] it is proved that, if \\(P\\) is given by \\(m\\) linear inequalities with input size \\(s(P)\\), then for any fixed \\(k\\) the coefficient \\(e_{d - k}(P)\\) can be computed using \\(O(m^ k)\\) calls of an oracle returning the volume of a face of \\(P\\), and both the number of operations necessary and the size of the numbers involved is bounded polynomially in \\(s(P)\\). This implies that for fixed dimension \\(d\\) the number of lattice points in a simplex \\(\\Delta\\) can be computed in polynomial time, thus reproving an earlier result of the author [Proc. 34th Symposium on the Foundations of Computer Science New York, 566-572 (1993)] but with a better bound (\\({d\\cdot s(\\Delta)}^{O(d)}\\)) on the complexity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330880$51F2E03D-ECD9-42CD-A3C8-ADAAB0AE722F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b01ad1b16eab7f86b2e20d189e8d8d07f644af25","datavalue":{"value":"52B20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330880$CAA6D347-283F-40C4-848A-0EB0FD34F2C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330880$64A28A04-7F2C-4A57-942F-7DA4B9023DCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"732c2501ca31f5ceeef797f80b885d9dde0d046f","datavalue":{"value":"11H06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330880$C1BD9FF2-698E-4CF5-9CC0-8EB58248912B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"83ad3d1e77c02a51c851213c2d0dd20baa7efa45","datavalue":{"value":"617323","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330880$E30BFF89-4511-45F0-89C2-BF932F99891C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59d44c0d4db845e761fb6e500e204f79ba9d02a3","datavalue":{"value":"geometry of numbers","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330880$4ABF5D0E-7EF5-4D06-B473-A48DE118CE45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"04b6761a3b8853d8ac0ba07c2df46cded7ee4ec8","datavalue":{"value":"lattice polytopes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330880$051D436F-8E6D-4E64-A5C6-713B49BF9327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ef9d04de1deeed7b10009935cc445131e0fb477","datavalue":{"value":"Ehrhart polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330880$F76DA4FF-8031-4CE4-826D-DC8BE721475F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e455a6fd7502d295a5538b8faaaa031044d33489","datavalue":{"value":{"entity-type":"item","numeric-id":1360053,"id":"Q1360053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330880$78D2261F-1E3C-4822-A415-80016E637319","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":"Q1330880$9293A4DB-C05F-4E70-A3E2-A8D184D56F15","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"12fff42a400d6a0ec1ed4d7ae5cb914ad0a917fa","datavalue":{"value":{"entity-type":"item","numeric-id":1091639,"id":"Q1091639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330880$C14198BF-408C-4FB4-A32B-058A75EB90E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11d8af2df779085adeca485e2691445d9b764369","datavalue":{"value":{"entity-type":"item","numeric-id":4296521,"id":"Q4296521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330880$98EC0E6D-D56B-4434-8D6C-E5C0414BBCEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98ff388f1854cc1183de8af7335052d365ad39ee","datavalue":{"value":{"entity-type":"item","numeric-id":3821581,"id":"Q3821581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330880$EA8E56CD-17B8-4BFA-8AE9-C60D164745BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f0ac1c52306853891fce6ccf2e5fd4faebcc828","datavalue":{"value":{"entity-type":"item","numeric-id":3142877,"id":"Q3142877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330880$9BEBCA59-BF3C-410E-AEFA-42B54FCDE305","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d16b4d29c0ba31b1bc8e06218af428a76fc8ce67","datavalue":{"value":{"entity-type":"item","numeric-id":1210712,"id":"Q1210712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330880$95194252-CC9A-4ECF-8188-57206984277B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34b74e05f8eeb34a69e1761409f15ac9e04c8087","datavalue":{"value":{"entity-type":"item","numeric-id":3780763,"id":"Q3780763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330880$6D2E9BA9-D00D-42AC-9B17-6FAE516DFC1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fcfb5268ea01c31e62ef508f1080fc0d6a7be51","datavalue":{"value":{"entity-type":"item","numeric-id":2366288,"id":"Q2366288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330880$1EA43276-59CD-4033-93B5-ADF0CC823431","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d98044f4e49a919116c7c8aa6f1196897cf01309","datavalue":{"value":{"entity-type":"item","numeric-id":5620207,"id":"Q5620207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330880$0F4A0BCD-9A6A-46A9-BE7E-4D2E1AAC18E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a86cf3e296cd629a88c1ddbaaab0e59a45d3a344","datavalue":{"value":{"entity-type":"item","numeric-id":1313382,"id":"Q1313382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330880$CFCFADED-887D-459F-902C-F6DE74CF4740","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f396b0fecde991325e5d1c8fbe3ecc7fce878152","datavalue":{"value":{"entity-type":"item","numeric-id":3204344,"id":"Q3204344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330880$C591508D-6545-4516-9B27-7B6AFC1BB03D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33ebd623f6b8e57b27792095bc1a5f936ffa53ab","datavalue":{"value":{"entity-type":"item","numeric-id":3748279,"id":"Q3748279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330880$8168FD00-8FEA-4D42-A29B-1B9451235B08","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb8e702e41b2c3217a49b337cb395068ba975c21","datavalue":{"value":{"entity-type":"item","numeric-id":3359328,"id":"Q3359328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6eff8b0c905bbe2d207bcc6e9168cfbf349572d","datavalue":{"value":{"amount":"+0.7992447","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1330880$EDBF0FC8-62E1-4ED0-BC4F-5ABCE718623A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8a4f276ad79d482e7faf4a9f4cac5f72b628df8","datavalue":{"value":{"entity-type":"item","numeric-id":5470061,"id":"Q5470061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc07677e6f9be9ac3038a3a970a40e7c33f10faa","datavalue":{"value":{"amount":"+0.7746946","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1330880$C8F199B4-7F45-4791-BA79-B96D6AE7CFEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0090835c2dc7e323d20e6cda76e79f42001c227","datavalue":{"value":{"entity-type":"item","numeric-id":3677173,"id":"Q3677173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b6a64b143d1345a781ca58d8892799eaf0f6ddf","datavalue":{"value":{"amount":"+0.77172464","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1330880$E3CB775F-350E-4078-A744-1C0EA2B9CC58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b63dd418e1d069b810943f7414dc3d7b6817c3c8","datavalue":{"value":{"entity-type":"item","numeric-id":4361783,"id":"Q4361783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82c90a8bca5fe6d1f483033a9e676cc9686c2282","datavalue":{"value":{"amount":"+0.7709598","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1330880$88690171-108C-4CC1-B42E-B58A41B6F2D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5eb0ebd62d64d2a8b0a16cff450f4552ebafb0c8","datavalue":{"value":{"entity-type":"item","numeric-id":4401017,"id":"Q4401017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04318f433ee87cfcea2653a06ac71a74c907360a","datavalue":{"value":{"amount":"+0.7668841","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1330880$DB30BF64-CEE2-4A1F-83A6-F6950F90EC3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ac003367c70af4dd31151482c26e85a66c9bd48","datavalue":{"value":{"entity-type":"item","numeric-id":3832046,"id":"Q3832046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee59ff8b08a0175b78ad2b9d72a52898c4622264","datavalue":{"value":{"amount":"+0.76278645","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1330880$520B97C6-4AD2-4A8F-A4BA-568DD49AD2E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58fd6e9018459fa770e30e02f82cdc53185de47b","datavalue":{"value":{"entity-type":"item","numeric-id":1356937,"id":"Q1356937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbc774d1c0852383233911aa3230fe3b0ba603ba","datavalue":{"value":{"amount":"+0.7615223","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1330880$D886D8A0-B6F9-4C69-9D30-E1D32470340E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab69509012ffb2b34e99977cfbb432796b8daa28","datavalue":{"value":{"entity-type":"item","numeric-id":4527038,"id":"Q4527038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72184c1a2cfa52ab1c6c519f025f94d711f5ef6a","datavalue":{"value":{"amount":"+0.759283","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1330880$B59B4273-9F80-41F9-BECE-7A8C85CBBF47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"469b996176c47f28a1cace3ea89c9b6489c9c8f5","datavalue":{"value":{"entity-type":"item","numeric-id":3387220,"id":"Q3387220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1fc63cdeae67a7c4eb1bf8cc2dd5003b7edd8dc","datavalue":{"value":{"amount":"+0.75576335","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1330880$8F638F05-7DD3-4FC1-8EEB-E241839C7959","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3bd16805b066330748bcabf1d9a18ff99e4de535","datavalue":{"value":{"entity-type":"item","numeric-id":5701854,"id":"Q5701854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"093178bc4feffe3976de52211d8a2126c21ec5e8","datavalue":{"value":{"amount":"+0.7513655","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1330880$FD0256A8-E32A-4CFD-9A6C-48EE795FB9EF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1330880","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1330880"}}}}}