{"entities":{"Q2022506":{"pageid":2033248,"ns":120,"title":"Item:Q2022506","lastrevid":57673839,"modified":"2026-03-31T21:08:22Z","type":"item","id":"Q2022506","labels":{"en":{"language":"en","value":"Simpler proof for nonlinearity of majority function"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7341230"}},"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":"Q2022506$CA4E89F6-05DF-463A-8AAE-6FAB7A1343F8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3eff51140b56a4e496c7d8923fd39d3d112f1442","datavalue":{"value":{"text":"Simpler proof for nonlinearity of majority function","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2022506$16F12852-AADD-43EC-8DDD-33D21AC2326F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5c1a7b69fc62f1a642f41907d10162da37dd0428","datavalue":{"value":"1491.94087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2022506$6DE4CD75-A4F3-4A5A-8570-0CE9974607E5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2022506$E97AA9F2-C187-4035-9F30-56557E0F64A0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6d23500e60ff764d81f80d2bfe210cd2ea479abb","datavalue":{"value":{"time":"+2021-04-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2022506$1C5346BA-14AB-4ED9-B966-7DFA831A4874","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"12497012e6ff7f48f0575f4faabf24fa00d81369","datavalue":{"value":"https://arxiv.org/abs/1710.02034","type":"string"},"datatype":"url"},"type":"statement","id":"Q2022506$C63E1681-A468-450A-A9DB-DFDF514EE01A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0e24261cc278db72ad483f3945a4a1b920a72526","datavalue":{"value":"Let \\(V_n = \\mathrm{GF}(2)^n\\), where \\(\\mathrm{GF}(2)\\) denotes the field of \\(2\\) elements. The Hamming weight of a vector \\(v\\in V_n\\) is denoted \\(wt(v)\\). Any function \\(f: V_n\\to \\mathrm{GF}(2)\\) may be identified with the vector of its values, which we also denote by \\(f\\) when there is no confusion. This function \\(f\\) may also be identified with a (unique) polynomial in \\(n\\) variables, called its algebraic normal form. If each term in this polynomial is (total) degree at most \\(1\\) then we call such a function affine. The distance between two functions, \\(f\\) and \\(g\\), is defined to be the Hamming weight of their sum, \\(d(f,g)=wt(f+g)\\). The nonlinearity of \\(f:V_n\\to \\mathrm{GF}(2)\\) is its minimum distance to an affine function, denoted \\[ N(f)=\\min_{a\\text{ affine}} d(f,a). \\] The first lemma in the paper under review states the following interesting result: If \\(f:V_n\\to \\mathrm{GF}(2)\\) has Hamming weight no larger than \\(2^{n-2}\\) then \\(N(f)=wt(f).\\) Roughly speaking, \\(\\mathrm{GF}(2)\\)-valued functions which are zero at least 75\\% of the time have nonlinearity equal to their Hamming weight.  This paper is devoted to the nonlinearity of the majority function, \\(M_n:V_n\\to \\mathrm{GF}(2)\\), defined by \\[ M_n(v)= \\begin{cases}1, & \\text{if } wt(v)\\geq \\frac{n-1}{2}+1\\ \\ \\ (n\\text{ odd}),\\\\ 1, & \\text{if } wt(v)\\geq \\frac{n}{2}\\ \\ \\ (n\\text{ even}),\\\\ 0, & \\text{otherwise}. \\end{cases} \\] The goal of the paper is to gives a simple proof of the following result.  \\textbf{Theorem}: If \\(n\\) is odd then \\(N(M_n)=2^{n-1}- \\binom{n-1}{\\frac{n-1}{2}}\\). If \\(n\\) is even then \\(N(M_n)=2^{n-1}-\\frac{1}{2}\\cdot \\binom{n}{\\frac{n}{2}}\\).  For further details, see the well-written paper itself.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2022506$0EFF84D3-1BDE-49AF-8B38-D773AB34D3BC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2bf534479b9242e973ca011ffc03f5c515318eab","datavalue":{"value":"94D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2022506$A1D26753-07C3-4585-8A55-A00459AC4912","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2022506$CDB34AD2-E6E0-4FE1-880E-EDBE09350A61","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"52ffca5273343f4c0cfcda6d3ea96063de7c00f6","datavalue":{"value":"7341230","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2022506$7D185640-A152-4EC2-8EA2-C6A4E607631D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05f855ca8375e22ee65dbedb12ed0c306fdccc2a","datavalue":{"value":"Hamming weight","type":"string"},"datatype":"string"},"type":"statement","id":"Q2022506$4DE3A0A1-1667-4150-8B6D-68A836C2A673","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48d526cc062a7adf792d73718762b7ebc375eacd","datavalue":{"value":"nonlinearity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2022506$558FD6D3-C437-4384-AA0D-0E29AF4BF41E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb5a830579b475e59eaac799be7398a9142f423b","datavalue":{"value":"Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2022506$235CC15F-7FE4-4C0C-BD7E-2E8DDB3256BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99af6ddbd8a52d77fd46256a869635f8d32fadf5","datavalue":{"value":"majority function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2022506$899126F2-81C0-4DC7-A000-95FB5D482858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a23e8d394e622fee75198f89e520da17b2aa9be3","datavalue":{"value":"Walsh transform","type":"string"},"datatype":"string"},"type":"statement","id":"Q2022506$6EE6E0C8-D7F0-4508-A8B4-FFC59F3786D2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b88092662f2247349f5cb95863af8d6fe82ad73","datavalue":{"value":{"entity-type":"item","numeric-id":267797,"id":"Q267797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2022506$D3E644B5-8918-4A24-B3FF-5141DE8CC65E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b2326afbe64b788dbdd9775d19f6c7a252d9bf11","datavalue":{"value":{"entity-type":"item","numeric-id":1675044,"id":"Q1675044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2022506$371C31EF-9D3F-4E1D-9152-7590A93A7798","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":"Q2022506$841A8F46-6F53-4416-A8EE-161CB6F1D545","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2a4ef0d1d3d3be08699f3c5c64c86bd85a04d57a","datavalue":{"value":"W3136789588","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2022506$68AC6959-A01F-4627-BAEE-1533241EFC55","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"441f2362c5521ecfc182221e33a2f36f5cbaf6b6","datavalue":{"value":{"entity-type":"item","numeric-id":5450975,"id":"Q5450975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2022506$0F3501F0-6218-4CF2-AE31-44776CAAD2BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e93ecfa962e7ab94d3de44ab64a79553e7f73d5b","datavalue":{"value":{"entity-type":"item","numeric-id":2510577,"id":"Q2510577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2022506$CE36A08E-EBC5-415E-92B5-7ECD25630474","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad8f54ec5eecebe30ece491b60850412dc3f205","datavalue":{"value":{"entity-type":"item","numeric-id":2834386,"id":"Q2834386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2022506$E64EB86D-4225-45C7-8B04-B87FE0261E25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb3207bf546f87213a463021fd7babad9081929a","datavalue":{"value":{"entity-type":"item","numeric-id":5473582,"id":"Q5473582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2022506$B719E2E8-B8BF-4452-BC73-8E45716577D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1eb7901bb5e6c5a2db5ab9f618794002b3fe54cd","datavalue":{"value":{"entity-type":"item","numeric-id":851733,"id":"Q851733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2022506$0E0DC832-F7C8-4EB7-B07A-75B269D3E4A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"950ff02cafd2d586eca67f0cefe4feb685f5a9ee","datavalue":{"value":{"entity-type":"item","numeric-id":1202027,"id":"Q1202027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2022506$42F6E52C-589B-425B-90B2-FF45AE90D4B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"199bfbcf984b0ba5e9138328b95686363a30b80c","datavalue":{"value":{"entity-type":"item","numeric-id":3648474,"id":"Q3648474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2022506$89EE3B3B-60C9-407A-9BD8-8597E5A516F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b1f032c21349f36af8ce3e1a930e36b7740a874","datavalue":{"value":{"entity-type":"item","numeric-id":5386105,"id":"Q5386105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2022506$CE12C983-DA93-4233-ACA6-71F6BEB00FAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d86b04a2c9d82ddf3fc29ad7e1c1dd11c90477f4","datavalue":{"value":{"entity-type":"item","numeric-id":2804022,"id":"Q2804022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2022506$D5D99A34-FF26-4BD1-9AFB-7BA2F98AB18F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9134bde9e811f9a54d6a87f59b431c9438cee2d","datavalue":{"value":{"entity-type":"item","numeric-id":2448066,"id":"Q2448066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2022506$6C6FB121-AF2F-4114-B85F-9335D3AAA643","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"39a513115f9ad3c66889a7aecdea33100ed2c73c","datavalue":{"value":"10.1016/J.DAM.2021.02.031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2022506$E079EB99-ABF6-4C42-B0D9-3F212A5D0226","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ef9db35be5520340eb6be9d39451aa3b5cbb183","datavalue":{"value":{"entity-type":"item","numeric-id":3842516,"id":"Q3842516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bddd24fc8a8de7c25182769d0221407850067bb7","datavalue":{"value":{"amount":"+0.7560779452323914","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":"Q2022506$F16CC7DF-DD20-415F-B149-13E6662CEACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4841f94023f5af2672ae6936b274b087dc280b52","datavalue":{"value":{"entity-type":"item","numeric-id":4917412,"id":"Q4917412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80c8c15a5c650c84860a03fa129141d8618c556b","datavalue":{"value":{"amount":"+0.742793083190918","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":"Q2022506$91860AD5-2A67-4D35-A744-E8906D11F868","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82acfaa524c57893680c7e9505b427cf46e2c453","datavalue":{"value":{"entity-type":"item","numeric-id":558225,"id":"Q558225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"252c67bf8e4d5af1ddbc876596fef8309e6ca707","datavalue":{"value":{"amount":"+0.7420317530632019","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":"Q2022506$8A4C874A-98F4-49AF-82EB-21BF98D8FDDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d5c3e3422e8136e0b2e18aa0f15ed29ecac5521","datavalue":{"value":{"entity-type":"item","numeric-id":6051967,"id":"Q6051967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2b9eca7f24ba1cbb53a714e504b8445fe42584b","datavalue":{"value":{"amount":"+0.7387051582336426","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":"Q2022506$E87307EE-C050-414E-AA7C-471AB0A8091B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6a5c1cec0d71f1734b2816454de554a39843b82","datavalue":{"value":{"entity-type":"item","numeric-id":4829485,"id":"Q4829485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2bbca14ca97f4d8cc4493faaad610be7b79eae7","datavalue":{"value":{"amount":"+0.736760675907135","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":"Q2022506$85333F9D-7E4B-4FFE-8927-ED00B38D837D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2022506","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2022506"}}}}}