{"entities":{"Q2630874":{"pageid":2641617,"ns":120,"title":"Item:Q2630874","lastrevid":57955098,"modified":"2026-04-03T05:45:11Z","type":"item","id":"Q2630874","labels":{"en":{"language":"en","value":"Near invariance of the hypercube"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6605693"}},"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":"Q2630874$CDA7C22E-F81F-4C9E-9F9B-74272111BF96","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f8fde8dd4c3c11865d61eb9660b20edbc4126c22","datavalue":{"value":{"text":"Near invariance of the hypercube","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2630874$CAF21712-4679-4EDD-BF32-DD673F39A30D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6579a53135c9ad97851c21d5dcaea9d21c775b87","datavalue":{"value":"1350.15017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2630874$AE180969-63C8-4BE9-B7CB-CF69669EAEFC","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":"Q2630874$A4891FF6-A41F-4A8C-BBCA-247062CA8C48","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1d50f9b953eac0b2404563f86ad398ee3823cb48","datavalue":{"value":{"entity-type":"item","numeric-id":173732,"id":"Q173732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2630874$F2E700AD-7E52-45E3-8310-269D4F0DAEB5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"feb37f72a8cdcd68b43ae07ac4ed5aec5e9e9d96","datavalue":{"value":{"time":"+2016-07-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2630874$6876431B-F8A7-4B90-B04C-A956F475680E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"355bd59edbab833d55be7c273b6e9d327f066b55","datavalue":{"value":"https://arxiv.org/abs/1409.7447","type":"string"},"datatype":"url"},"type":"statement","id":"Q2630874$47B2ADD1-F40A-4342-B8E4-44E4DE270345","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a75381645fd09194c362babe9ddc0b7f8dd1fd0a","datavalue":{"value":"Let \\(M\\) be a square matrix of order \\(n\\) with real entries and let \\(\\mathbf{x}\\) be a vector chosen uniformly in the hypercube \\(C_{n}= \\{-1,1 \\}^{n}\\). The exact score function of \\(M\\) is defined as \\(s_{0} (M)= \\mathbf{P}_{\\mathbf{x} \\in C_{n}} (M\\mathbf{x}\\in C_{n})\\). It constitutes a measure of how the hypercube is preserved under \\(M\\), or how far the random vector \\(M\\mathbf{x}\\) is from being a Bernoulli vector.  The structure of matrices \\(M\\) with \\(s_{0} (M) >n^{-C}\\), for some positive real number \\(C\\), is deduced. Indeed, for fixed \\(0<\\varepsilon<1\\) and \\(C\\), there exists a submatrix \\(M'\\) of \\(M\\) of size \\(n_{1} \\times n_{2}\\), with \\(n_{1}, n_{2} = n- O_{C, \\varepsilon} (n^{1-\\varepsilon})\\) and a set \\(B\\) of \\(r= O_{C, \\varepsilon}(1)\\) vectors in \\(R^{n_{1}}\\) such that \\(M'= M'' + F.\\) Here, \\(F\\) is a \\(\\{-1,0,1\\}\\)-matrix of size \\(n_{1} \\times n_{2}\\) where each row contains at most one nonzero entry and \\(M''\\) belongs to the GAP of size \\(n^{O_{C, \\varepsilon}(1)}\\) generated by the vectors of \\(B\\). As a consequence, if \\(M\\) is nearly full rank, then \\(F\\) is nearly a permutation-reflection matrix modulo a low-rank perturbation. On the other hand, the authors also prove that general matrices of sufficient small entries cannot be near-invariant with respect to the hypercube.  When \\(M\\) is an orthogonal matrix with \\(s_{0} (M)> n^{-C},\\) then all but \\(O (n^{1-\\varepsilon})\\) rows of \\(M\\) contain a unique entry of absolute value at least \\(1- O(n^{-1+\\varepsilon})\\). The lower bound \\(1- O(n^{-1+o(1)})\\) on the large entries is tight. The proof of this result is based on the inverse Littlewood-Offord theory [\\textit{T. Tao} and \\textit{V. H. Vu}, Ann. Math. (2) 169, No. 2, 595--632 (2009; Zbl 1250.60023)]. Thus, permutation-reflection matrices are ``essentially'' the only orthogonal matrices with large exact score function, i.e., \\(s_{0} (M) > n^{-C}\\) for some positive real number \\(C\\).  Finally, in the case of stochastic square matrices of order \\(n\\) (rather than orthogonal matrices or matrices of bounded norm) such that \\(\\mathrm{Per} (M)\\geq n^{-O(1)},\\) then all but \\(O(\\log n)\\) of its rows are dominated by a single large entry. In that sense, \\(M\\) is close to a ``permutation matrix''.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2630874$328E3BA3-2D08-4842-877F-344A096DCE57","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a1c957ccb63d6375507b5e859fa7c56f0a5e93b3","datavalue":{"value":"15B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2630874$E21B1B9E-6CB8-47CB-B07E-E0CFA29492A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7af17f227fda8daecc6b4cd26e5d774fa965085f","datavalue":{"value":"81P68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2630874$CF5E8989-6B4B-4A8F-B5D0-79EC587580D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2a3b3e6e451112ae88a925a4babad921e127a616","datavalue":{"value":"15B34","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2630874$04ABE288-85F4-44A6-AEDB-0B67064DED20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5f35883713e23ca3f0ced48b60a92f4891f4d526","datavalue":{"value":"15A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2630874$8B9F5125-9AF0-4016-A2FF-D803A32A7CAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ba5f7486cfb64f062d1b1d8e48f356198d5bc8e7","datavalue":{"value":"15A03","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2630874$2540A510-93F9-4575-936E-E49F52AB4D0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e0bbeefc3d633ef2a2ca36004dc27235255343f","datavalue":{"value":"15B51","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2630874$4B7C34FE-7D10-4E43-A60A-B2D6BB39EE89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"772466e23f65811e4792a58a12ff09d79c338e5f","datavalue":{"value":"05B20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2630874$35982BF3-096A-4B38-8412-0A527890AB6D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"33c3b9ac6eb26b9178aa30e5a9520366daecea6f","datavalue":{"value":"6605693","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2630874$4A4C510C-9E85-4252-9D11-4A86E57AA9A9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84b39af02b6294cfc0ac85512f98aea0041760bd","datavalue":{"value":"hypercube","type":"string"},"datatype":"string"},"type":"statement","id":"Q2630874$C9B6872B-0568-4B55-B8B4-8547478E33B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e7bfb0e8308d6b293e3a7e6c017d225d627b980","datavalue":{"value":"Bernoulli random variables","type":"string"},"datatype":"string"},"type":"statement","id":"Q2630874$D4BD0DB3-1A88-4D52-8224-B2D6A3A9F249","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3764bff94efa15f24345bae7415545d90b490196","datavalue":{"value":"score function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2630874$3C368D0E-670C-4E17-BB7F-499064974D3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ccc158d93cd3fff3bdeb7c3caeb325296af49e3b","datavalue":{"value":"exact score function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2630874$E71923B4-255B-47E7-9369-A18948CDFF4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b91b53d582dd46c42c8a8a6c2058ac8b8b7e622d","datavalue":{"value":"permanents","type":"string"},"datatype":"string"},"type":"statement","id":"Q2630874$7B8CB8EA-F0FA-4CD3-B04E-C155882C5C1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f7dcffeb30903d8be373b7d42b8621dc9948c0c","datavalue":{"value":"reflection matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q2630874$7F9D62D6-7394-4BD6-8703-07BC1DC98ECC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b939017452c9a383c30b40160f01c77c9e0c35ca","datavalue":{"value":"orthogonal matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q2630874$8F3845ED-3630-47E3-BE9A-F9599B433C77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25994bff5d5a2f4c658b32cffe8911a4f8f43992","datavalue":{"value":"GAP of rank \\(r\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q2630874$E2EA1DB3-120D-4BD9-903B-DBD41D095A9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5d14ed177bd78a2aca04723a7b48e8ed64bfb37","datavalue":{"value":"abelian torsion-free groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q2630874$E2B7C3FF-E544-4981-8D8B-0ED63B6B1B28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d29eae965adfa31739b0f5e8282fd27aafe544f","datavalue":{"value":"stochastic matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q2630874$7D4665EB-AEF6-44AF-974D-81F7775291B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7cb2a892c7b2cdd350054dc00b81aa5f75df9dc8","datavalue":{"value":"\\(\\{-1,0,1\\}\\)-matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q2630874$522EEC73-3611-4044-AA08-54735E088F25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dc69bc35ae078bf783f0124583b928fdf663ace","datavalue":{"value":"low-rank perturbation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2630874$B6562B91-E858-44CD-A82A-DFABC4DB0E6F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e9b21f497ee9c92a9da223c188b40b8ca16d1dc1","datavalue":{"value":{"entity-type":"item","numeric-id":170418,"id":"Q170418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2630874$D64333D1-B5F5-4CDA-83E7-114355854753","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"eecff7672d98ddd92e9f59bf72dece031571efe6","datavalue":{"value":{"entity-type":"item","numeric-id":35496,"id":"Q35496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2630874$316AFD13-1626-431C-A586-51AB7D2A082F","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":"Q2630874$C770060A-4D60-4F65-95DA-19B801EDD742","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a4480262865370413380b30f448e5b4cd760a2a6","datavalue":{"value":"W1719552337","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2630874$D1D78EFF-89AD-4C96-AC1D-6BE16ADCABE0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca563f2af96484c4c7bc09b1c34d6c237d4135ee","datavalue":{"value":{"entity-type":"item","numeric-id":2389146,"id":"Q2389146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2630874$0B7C49ED-B7C4-4680-911C-31EC29693C6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f67f732beb2681320fb8cef422fa1990ba3b54b2","datavalue":{"value":{"entity-type":"item","numeric-id":3191572,"id":"Q3191572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2630874$AFF94169-BDFD-471D-A11F-46FEA1B9CF1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54f59301ba98ec3bb27385090337a77250bd504c","datavalue":{"value":{"entity-type":"item","numeric-id":3557502,"id":"Q3557502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2630874$B178DACA-9229-44D6-9BF2-5F20CEE4B273","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0b64ed9290ecc7b79953c10f6e8354cdd0f139d","datavalue":{"value":{"entity-type":"item","numeric-id":5842843,"id":"Q5842843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2630874$065E389A-3D1C-469B-8097-8E05D40A9F06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7674f9b3b86b72ad5caa74a6794505425c90dd25","datavalue":{"value":{"entity-type":"item","numeric-id":709260,"id":"Q709260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2630874$E1FE3CE5-BD49-4AFF-8E2F-1A66433E8754","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58e2a656266b4a3d88c2aac802da4588b5bb2e62","datavalue":{"value":{"entity-type":"item","numeric-id":633617,"id":"Q633617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2630874$879012F7-E2A3-42FD-ABF3-F2752EEE5133","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da71ace94062947f699455506be5b6f12f0bc04e","datavalue":{"value":{"entity-type":"item","numeric-id":3432742,"id":"Q3432742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2630874$3D486571-259E-4FEB-9660-9E683351D697","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"edfa7d8dff458feb58990c1580937ec9cd5a6744","datavalue":{"value":{"entity-type":"item","numeric-id":3061186,"id":"Q3061186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2630874$051450F3-F339-4F40-B394-F8F3169B1DA4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b4d14560ddcc93fff83f35ab66f5dd9dffabc76b","datavalue":{"value":"10.1007/S11856-016-1291-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2630874$59F121AB-D968-45EB-8AF0-5D1F74FA84EF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8f7b7308e37c6d3887ffd647b0f12651920603c","datavalue":{"value":{"entity-type":"item","numeric-id":866456,"id":"Q866456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b763a9f71d9588dbfb85189007b55690fb6ed43e","datavalue":{"value":{"amount":"+0.7249714136123657","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":"Q2630874$533904F5-E0ED-4235-848E-FBDF1A35FCA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e835f3ffcf03ce6958438c36258b119b8db5ff50","datavalue":{"value":{"entity-type":"item","numeric-id":5121907,"id":"Q5121907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25b0cc884dbbabd02423fe55e5e82af76ec80e44","datavalue":{"value":{"amount":"+0.7079591155052185","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":"Q2630874$D0217AC2-ABE0-447C-9E10-D6D3ED54DFE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0ae9532b2c0d86fc0d78c9b859bbde37ad2b0b3","datavalue":{"value":{"entity-type":"item","numeric-id":2080247,"id":"Q2080247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d94e0b75119b1aea77758d93efb2604af3747f0","datavalue":{"value":{"amount":"+0.7048318982124329","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":"Q2630874$AB2A56BF-622D-4929-B779-044BDB87AF5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03fb78076fe642713e53cc4b5818e73e3ecc6bae","datavalue":{"value":{"entity-type":"item","numeric-id":3167410,"id":"Q3167410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b20bc305223236033078c4a0e37429801eed2e1","datavalue":{"value":{"amount":"+0.6828119158744812","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":"Q2630874$650A0747-3FD2-4BCA-8860-E00B3F961F22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5977c5bbf068be0330849dcb02371fbd768ea763","datavalue":{"value":{"entity-type":"item","numeric-id":3191572,"id":"Q3191572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ae07f52f081595115e9da45f001ffea32236159","datavalue":{"value":{"amount":"+0.6822879910469055","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":"Q2630874$2A78721F-D15A-46C3-A4CE-8F1304297D58","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2630874","badges":[]}}}}}