{"entities":{"Q674920":{"pageid":676769,"ns":120,"title":"Item:Q674920","lastrevid":63425859,"modified":"2026-04-11T13:01:00Z","type":"item","id":"Q674920","labels":{"en":{"language":"en","value":"Nondegenerate functions and permutations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 987768"}},"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":"Q674920$3D2648C9-2C8F-4B57-AF7C-1C85A6D47B75","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"118e2e9570e87ea00dbdaa9ebd8d8ed797c92043","datavalue":{"value":{"text":"Nondegenerate functions and permutations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q674920$9037EB4D-773B-4B5E-8EEB-1640281FA090","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"217961797e9b0e3704a0e47d16f1b46e6eb498ad","datavalue":{"value":"0871.94036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674920$FAAB13CA-5D9D-45A2-B233-525D3071EBA0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e6b2d4ed5535b06ed3b34a71745f585eac6769c0","datavalue":{"value":"10.1016/0166-218X(95)00117-A","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674920$1A9939BD-AC1E-45A9-99F4-72140BDD9C3F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c9c33f382e448bed1b771ba7956c8f35345adc71","datavalue":{"value":{"entity-type":"item","numeric-id":673912,"id":"Q673912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$07D64B23-D2AA-4E4A-A431-BA24E1D804EA","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":"Q674920$DAE4EF2B-5457-4FB4-953B-8E429C75ED69","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"53ca32303030cbcdd57a20141335cf713f9048cc","datavalue":{"value":{"time":"+1997-10-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":"Q674920$2D40FEE5-39F2-4741-83FA-739551E8F170","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3395a2cd6863e39784161d0f578415f36fc38e6f","datavalue":{"value":"http://www.elsevier.com/locate/dam","type":"string"},"datatype":"url"},"type":"statement","id":"Q674920$652C4055-8AB6-4CB1-8551-B3EEB6FF20CB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6e1f942bc427ebdddcdad5214f969de8a4eb3272","datavalue":{"value":"A Boolean function \\(f(x_1, \\dots, x_n)\\) is called degenerate if for all \\(x_i, \\dots, x_n\\in \\{0,1\\}^n\\)  \\[ f(x_1, \\dots, x_i, \\dots, x_n) =f(x_1, \\dots, x_i+1, \\dots, x_n); \\]  otherwise \\(f\\) is said to be nondegenerate. The author proves that nondegeneracy in Boolean function can be verified in linear time on average. If for a Boolean function \\(f(x_1, \\dots, x_n)\\) the equation \\(|\\{X: f(X) =1\\), \\(X\\in \\{0,1\\}^n\\} |= 2^{n-1}\\) holds than the author proves that, on average, at least \\(n-\\lceil \\log n \\rceil- 2\\) variables must be held constant before a degenerate subfunction is induced. A function \\(F:\\{0,1\\}^n \\to\\{0,1\\}^n\\) is called an \\((n,n)\\)-bit function, and is nondegenerate if for all \\(i\\) the \\(i\\)-th bit of \\(F\\) is realized by the nondegenerate Boolean function. Let \\(N^{n,n}\\) be the set of invertible nondegenerate \\((n,n)\\)-bit function, the author derives bounds \\(L_n\\), \\(U_n \\in 0(1)\\) such that \\(1-L_n <{|N^{n,n} |\\over 2^n!} <1-L_n+ U_n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q674920$D4A6FCDE-6EE8-499F-8A55-2DA8931D411C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674920$B237679C-1EF1-4636-A9F5-1E29F82FB478","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f3eb9b2932c3fdc120e877804d57f4cb2d94e9","datavalue":{"value":"06E30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674920$4A4BA5BF-FEBA-40C9-97AE-B382A697B920","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"17fda014c54610e9c3ec7f8e5ef2739b9f4992e3","datavalue":{"value":"987768","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674920$25C5CCD6-C048-4837-B02F-783F76F50564","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cdcc858e642c37f46f6fa377f2e2634fe466a35","datavalue":{"value":"permutation","type":"string"},"datatype":"string"},"type":"statement","id":"Q674920$A9D46E4A-A6AC-47FD-8CBD-815343008097","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c611f6f4402e754ef97ca421747c209d6305db8b","datavalue":{"value":"evaluation of cardinality of some sets of functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q674920$ECE415CB-FD0C-4B20-AEF1-C1412D65BA19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0062bff246f10874c360cb4d691bf5c2195f236c","datavalue":{"value":"Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q674920$F6078DC1-7CF2-47A4-A8CD-84917685A062","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b4ce8b4f1992b8454237185a2d389f6c6170b4b","datavalue":{"value":"nondegeneracy","type":"string"},"datatype":"string"},"type":"statement","id":"Q674920$998DAA96-63C6-45F0-A8D9-F71A1C9E7704","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":"Q674920$918A4922-0EE9-4731-8D9A-B485A46DA6D7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5813d9b17f2cf9f1b2d261a8bfa7c9a6631b230","datavalue":{"value":{"entity-type":"item","numeric-id":3722412,"id":"Q3722412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$3BCC3FFE-3D34-47BF-8FB6-1DA8DAECDE7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"136268be74516023355560e5ad574246f787f3d5","datavalue":{"value":{"entity-type":"item","numeric-id":4100258,"id":"Q4100258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$65BEF441-9E1C-422A-9D04-42D93662F2C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d04c5ed6af2609950d2dfa03d08d7bb208eb9f0c","datavalue":{"value":{"entity-type":"item","numeric-id":3691050,"id":"Q3691050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$2368542F-7FDA-465E-906A-B70CAD883489","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbbb17670f182002203fd5be94c755135b73e3c5","datavalue":{"value":{"entity-type":"item","numeric-id":3323836,"id":"Q3323836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$235687FA-EB7F-466E-9B18-79AE121173F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$1E96E9AD-263D-4EC0-BF74-4C74F21508E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70dc07534eba676d59722b415a0bd27b41786f77","datavalue":{"value":{"entity-type":"item","numeric-id":5593643,"id":"Q5593643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$C451AEBD-D2B6-47BA-BD88-662B60D347D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec072e65bba566a40310ac435638180ad8e5ea1b","datavalue":{"value":{"entity-type":"item","numeric-id":3773321,"id":"Q3773321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$B574D133-6CFF-46A0-90C4-33A6F697FCF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5e03c93478c4dd5550bd120f748813b33812a23","datavalue":{"value":{"entity-type":"item","numeric-id":5562602,"id":"Q5562602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$13D42CE2-5B07-4FC4-84BD-4E9164BF8619","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8205cc7d8c14e9f3f180942f8bfb48e8bad16560","datavalue":{"value":{"entity-type":"item","numeric-id":3856133,"id":"Q3856133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$04BE33E2-01A8-4B26-B9F3-E850A2B012BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f652bd3f1177e6145feff32945d51b6e8753247e","datavalue":{"value":{"entity-type":"item","numeric-id":3705340,"id":"Q3705340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$EE4E8F44-111C-4EB4-A969-A77326190DF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3446f09f014c631d5542c49666c3ad1874f07c13","datavalue":{"value":{"entity-type":"item","numeric-id":3710461,"id":"Q3710461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$ACB1FF13-CF5D-408E-B8CF-658EBF880FA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6778f8c3b9da3262a4f23887fb9944c0c3c7d56","datavalue":{"value":{"entity-type":"item","numeric-id":5547604,"id":"Q5547604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$49414FEB-1043-4647-9D63-07AD7FB4ECD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7dca74a606b1d1e836ad905e4526743121ceab67","datavalue":{"value":{"entity-type":"item","numeric-id":918500,"id":"Q918500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$763453EF-4265-4ECF-A598-709D4F814B76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c7cd4e2cc9ffe4ceb6d96c49cee8f00bf6c5cd2","datavalue":{"value":{"entity-type":"item","numeric-id":5597672,"id":"Q5597672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$4CBB7F10-7C60-4B69-852B-B6285AC03D51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e01cb1275b52e14b6ed77783ca852fcea9888bfd","datavalue":{"value":{"entity-type":"item","numeric-id":2974493,"id":"Q2974493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$9F244AD2-7402-4FA1-8009-F84798EA311E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e30882b2eca656f4a5fadfd37b7a9f7d9d139ec5","datavalue":{"value":{"entity-type":"item","numeric-id":1230079,"id":"Q1230079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$8ABF3DC5-82DE-4474-B55F-8D1AFB1334BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17ab2eaa22970af4e0a752f84fc41bb8c74bbe54","datavalue":{"value":{"entity-type":"item","numeric-id":3801067,"id":"Q3801067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$41CE4C3C-ED59-4B7F-AD5D-3B0382D7CBDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff2616a6ad9d2f1fc155736cddd05cfc686cc179","datavalue":{"value":{"entity-type":"item","numeric-id":4739783,"id":"Q4739783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$72C15296-C9A6-41B7-95E9-9DDDAEE07290","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"acd07ddaa269258622e37627a099ca556219d154","datavalue":{"value":{"entity-type":"item","numeric-id":3218059,"id":"Q3218059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674920$4AC4F444-BF84-4E00-9690-05854991EAB5","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"0b20dbe14437e9f4bb89af4bf37a60614023b5f0","datavalue":{"value":"Q127372812","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674920$2B58320D-6209-4845-8063-DED513506222","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06ca332bd3090ce06ecfe29d148a1efef7ee53a6","datavalue":{"value":{"entity-type":"item","numeric-id":4037481,"id":"Q4037481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e06a91c584a033611adb2640037356ad51032df8","datavalue":{"value":{"amount":"+0.8386146426200867","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":"Q674920$CB939D5F-0D9F-47E7-95EE-D8C80DE6CAAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca13a9862b0f4b3f10f38de22fbc13a5bea01446","datavalue":{"value":{"entity-type":"item","numeric-id":1432316,"id":"Q1432316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8421a1126040cc98119f7316faf69f8df8ffd8a2","datavalue":{"value":{"amount":"+0.8300545811653137","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":"Q674920$15C1D2E2-E02C-4438-A344-C937F6333EA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8aa35b2738e92e78ea420cf649e3b665f6a9cad1","datavalue":{"value":{"entity-type":"item","numeric-id":2366362,"id":"Q2366362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b94c9d0965362ec13d510c9a87fc13a8f64b3761","datavalue":{"value":{"amount":"+0.7961100339889526","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":"Q674920$745B6019-FA53-4946-881A-C1147510F99C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Nondegenerate functions and permutations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Nondegenerate_functions_and_permutations"}}}}}