{"entities":{"Q949786":{"pageid":951634,"ns":120,"title":"Item:Q949786","lastrevid":42782703,"modified":"2025-07-11T10:51:59Z","type":"item","id":"Q949786","labels":{"en":{"language":"en","value":"Near optimal bounds for the Erd\u0151s distinct distances problem in high dimensions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5355089"}},"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":"Q949786$1873520D-B7C8-4BBF-9672-766F11F74AD5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7f64d7e7f6c7450cbd471fc230f37a3ee0983fcb","datavalue":{"value":{"text":"Near optimal bounds for the Erd\u0151s distinct distances problem in high dimensions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q949786$CFB5CC7E-8957-4A91-A578-95B9E73837A3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"27ceded8321726a9f87b02c45f9a8fa61af04b56","datavalue":{"value":"1174.52009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949786$4D2D35FF-0EED-47BA-805D-1BDB8E3F9E71","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9dc503ac097ce954bc7e0ba8e899d11be9843bec","datavalue":{"value":{"entity-type":"item","numeric-id":224911,"id":"Q224911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949786$8C8ECE77-D73B-4DA4-B00D-91DE55376C04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3ac20003147c5e8ffc37ced247b8446bd4defdc1","datavalue":{"value":{"entity-type":"item","numeric-id":178484,"id":"Q178484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949786$97AE8DF2-4895-452E-AD60-0A6EE661F00D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949786$448E7965-DADA-4CAD-A593-342875A99DF1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b4a05105c8454225903df775b1ba3fdbda7455a","datavalue":{"value":{"time":"+2008-10-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q949786$7E7C3A41-B905-4D24-846A-B6ECEAB539F4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7a2e1afc08123ffc493f2db1bf3b59a532be5136","datavalue":{"value":"One of Erd\u0151s' most famous questions in combinatorial geometry is to determine \\(g_d(n)\\), the minimum number of distinct distances that can occur between \\(n\\) points in \\(\\mathbb R^d\\). An appropriately scaled integer lattice shows that \\(g_d(n)=O(n^{2/d})\\). It is conjectured that \\(g_d(n)\\) is not far from this bound when \\(d\\) is large.   In this paper it is shown that \\(g_3(n)=\\Omega(n^{0.5643})\\) and \\(g_d(n)=\\Omega(n^{\\frac{2}{d}-\\frac{2}{d(d+2)}})\\) for all \\(d\\geq 4\\). These bounds improve the previous records of \\textit{B. Aronov, J. Pach, M. Sharir}, and \\textit{G. Tardos} [Comb. Probab. Comput. 13, 283-293 (2004; Zbl 1052.52010)].  In fact, slightly better bounds are proven which follow from two recursive lower bounds that depend on the maximum number of points that lie on a hyperplane of codimension \\(1\\) and codimension \\(2\\), respectively. The proof is a clever counting argument based on a modification of the cutting lemma of \\textit{B. Chazelle} and \\textit{J. Friedman} [Combinatorica 10, 229-449 (1990; Zbl 0715.68036)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q949786$480E1AD8-F868-4CD1-8BB3-B25C5BA53E5C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ece2465280f4825557587fd8f853970958d7af4a","datavalue":{"value":{"entity-type":"item","numeric-id":193558,"id":"Q193558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949786$9A1342E6-7CD9-474F-B229-A9E892C3E852","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b81fed1ca06e8930440f3ae2c1b914de465c5f39","datavalue":{"value":"52C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949786$B166E075-AD95-4406-B96D-3BC273B32ED5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3421d3168519543a29f6c60b7a8202984d825ce4","datavalue":{"value":"5355089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949786$8D073AC7-F191-40C6-B19C-F73FC8F17173","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a68b9eec93b14310cc6be26ca81cbd39b883d5d","datavalue":{"value":"distinct distance problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q949786$2C082818-B33E-43BF-87FC-EF94ABD0226E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d2ccddf6493536afa08f9960baf29b5c2247d027","datavalue":{"value":"Erd\u0151s problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q949786$026F83CC-0592-4DE6-8B6B-52C21ECB9D89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"835824508baaa42ac9d7cbf84d54c454642f3033","datavalue":{"value":"cutting lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q949786$7B3B7D41-C950-4C48-9860-2789C42A2611","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d23d9143e74ca978fbd7eb6b9eb9a9fb9bc86bb","datavalue":{"value":"combinatorial geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q949786$53315E5D-14E7-4EB0-907C-AEE74EE26195","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":"Q949786$23FBED45-FE87-4330-8462-19D4C1B1A8F0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a3c6bd70072ddb833abbd7879e5890e40b69dfd2","datavalue":{"value":"https://doi.org/10.1007/s00493-008-2099-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q949786$F18EDB68-6DF0-4885-9458-134D67709959","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4eb225ed2fd030629a7bc0e2200af041d803c7e8","datavalue":{"value":"W2031397195","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949786$863C4583-2F9E-440B-BD84-D1137A72E9D3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0985bbeeaf0b2ab85c8613654515e7ca8bc0b207","datavalue":{"value":{"entity-type":"item","numeric-id":4819241,"id":"Q4819241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949786$07DF67F6-3791-42F1-9443-2C5A8D2A6E1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94d44c65f9584e97826a6445e2d0ce1d2234080f","datavalue":{"value":{"entity-type":"item","numeric-id":751816,"id":"Q751816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949786$B20A82E0-9B0B-4177-8BA2-7C3AC24C5038","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6177d76258b3097fdef740daf7f4cda1006d0453","datavalue":{"value":{"entity-type":"item","numeric-id":791525,"id":"Q791525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949786$64F2C586-2764-411F-831F-E40084059D61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"886cb0bd9d2713920ea308e68e5c07bea3402d9c","datavalue":{"value":{"entity-type":"item","numeric-id":1186077,"id":"Q1186077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949786$04A2D284-6C23-48C4-932A-D3FBC764158C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec8b4d9c8ab43c964ebd317432f831e9e03ea515","datavalue":{"value":{"entity-type":"item","numeric-id":917017,"id":"Q917017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949786$48F54A7E-00EF-4ABC-9303-3CBD7966C576","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8b198a6f339f053ba5ff1e212a4246d67f68f4f","datavalue":{"value":{"entity-type":"item","numeric-id":5836902,"id":"Q5836902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949786$E9B942EE-3357-48EE-A554-7E69BC416BD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d1e47570311f150a70f1fd7f9fc91030cb16167","datavalue":{"value":{"entity-type":"item","numeric-id":2756772,"id":"Q2756772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949786$CF8B258C-6BE1-4782-A9F1-556839BB2521","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c0a9666acc6b0e275d5ea67ba1e86c027665d5b","datavalue":{"value":{"entity-type":"item","numeric-id":5809549,"id":"Q5809549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949786$23511ACB-428F-4F78-8806-098CCE472D67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9b8cb03046b10b2415adb57db32a091585a6470","datavalue":{"value":{"entity-type":"item","numeric-id":5939473,"id":"Q5939473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949786$C3616836-F50B-4F01-A66D-984CBBDC8C7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2cd6290cb80648b81cbceeb9a977f969980c62c","datavalue":{"value":{"entity-type":"item","numeric-id":4657595,"id":"Q4657595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949786$FFBFF79D-322E-4789-A811-551421D5FEF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71446b2bd886e1848a46a78837492cb784025dc3","datavalue":{"value":{"entity-type":"item","numeric-id":4354594,"id":"Q4354594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949786$9DB82735-A5BD-4593-AE5F-4AF0B6ADD761","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55bbfc3c41934d1291a22f27cf8c8e395dccf90a","datavalue":{"value":{"entity-type":"item","numeric-id":1418004,"id":"Q1418004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949786$5D226880-C0C2-4838-B50F-B975DE6450AC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"61714cd1f6a552a4891ca125aaeec12b631da290","datavalue":{"value":"10.1007/S00493-008-2099-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949786$8C328064-B2A6-409E-B06E-4171A62FCE8D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ded243f5c12e2dbe89fcfa989b60e72e628741ae","datavalue":{"value":{"entity-type":"item","numeric-id":482909,"id":"Q482909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44467e3c6b6d9eb19fb303b3b1a55be6f40ff1db","datavalue":{"value":{"amount":"+0.89732933","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q949786$0A865805-39B4-47F7-9679-B12EC229399A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"829bf55594637f88e78f3afe86e5e02e6a2e6c47","datavalue":{"value":{"entity-type":"item","numeric-id":5502197,"id":"Q5502197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2a8b9f8321752bf2935829fe0d3c4856cb7aead","datavalue":{"value":{"amount":"+0.8919808","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q949786$16083860-D003-484F-AADA-FF7621C55F5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2caa84868a2753c6327fde73cbcf066ad18009d9","datavalue":{"value":{"entity-type":"item","numeric-id":5220109,"id":"Q5220109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb1a29c2805c3edd1629eec7cf524c47a08f8e76","datavalue":{"value":{"amount":"+0.88793087","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q949786$47449297-5C46-4665-86B4-1C3ECEEA9786","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9938caa8d447d1d297274f0964a3c7a22693f99","datavalue":{"value":{"entity-type":"item","numeric-id":1917053,"id":"Q1917053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d93e36fc020ac5e706897ddffe10aeadcbe16aa","datavalue":{"value":{"amount":"+0.8861561","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q949786$55A7FEBC-1548-4769-AC80-DD6DCD5DFF04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e0082701dbe2bc031d8cbef87b6f9f144711972","datavalue":{"value":{"entity-type":"item","numeric-id":2000647,"id":"Q2000647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b4d365b0eb981816d6eec85561f8cef44af8298","datavalue":{"value":{"amount":"+0.88140106","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q949786$88A18A91-08CB-461B-A184-2B7FF2CB918C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ffaec4788514e558e50813b4d5e4d302cd4ef2a","datavalue":{"value":{"entity-type":"item","numeric-id":2340417,"id":"Q2340417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c160d2cb0ddf57f2d4ef600451cb220b1f4d9ef","datavalue":{"value":{"amount":"+0.8805463","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q949786$8A731056-4F54-4DD6-ADC6-63442608F6C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f6e33ee6e27338327f7f0f74e1f8a83c52a614f","datavalue":{"value":{"entity-type":"item","numeric-id":4657595,"id":"Q4657595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06db4231183590d77bc90303c44f2c635c7e7baa","datavalue":{"value":{"amount":"+0.88038164","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q949786$50E33BAC-234F-4A9F-8320-0E9B34B665C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"210c138d38f8842d8f2be3491ec399e8ce4acc45","datavalue":{"value":{"entity-type":"item","numeric-id":4575604,"id":"Q4575604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c6c71d74d6f13f8171002237d90ec7f10482bee","datavalue":{"value":{"amount":"+0.87477416","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q949786$8FB7DF13-F486-4721-A9CF-583930C784E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91ac605064834e8cadb2f3a2cf806a73664e5ad1","datavalue":{"value":{"entity-type":"item","numeric-id":4657584,"id":"Q4657584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f94ff86752bc1e4db52a951a9a8c41b3087fb41a","datavalue":{"value":{"amount":"+0.8726858","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q949786$68F33BE9-2775-4B6A-8A5B-7421CB7E562E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:949786","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:949786"}}}}}