{"entities":{"Q486751":{"pageid":488518,"ns":120,"title":"Item:Q486751","lastrevid":62207226,"modified":"2026-04-11T04:29:38Z","type":"item","id":"Q486751","labels":{"en":{"language":"en","value":"On the complexity of families of pseudo-random subsets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6387274"}},"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":"Q486751$2B79DBC4-9117-4D01-B4FE-BD50E660771D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1784c8a3a8509d28c2fef41e2999ed8126484f87","datavalue":{"value":{"text":"On the complexity of families of pseudo-random subsets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q486751$E46C4F48-98F0-4E72-91E6-1C9C73DF6965","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1856a3512d7d4f3b0cd6eb75955406d95ee97bf0","datavalue":{"value":"1314.11048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q486751$7DB946F2-C93C-43E8-BC76-EFF71ED4263C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8d75d28b470ea2cbede3b521f9e73fd45aef50ac","datavalue":{"value":{"entity-type":"item","numeric-id":477554,"id":"Q477554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$42F60C28-4AA7-4396-AEA3-6E2D6B7E4C03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f3994b3ea7b242f980d845d7f38f3a45e589bc28","datavalue":{"value":{"entity-type":"item","numeric-id":592710,"id":"Q592710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$8A10B6BD-9C2C-4B6F-84AD-BE06C8777A56","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6b3471e36a9b536f7a0355f0f7dec82dcb833e25","datavalue":{"value":{"time":"+2015-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q486751$0A72B5BB-9500-4E37-968A-057A8AD6567C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ba374eacc19169e480741bc151e7b0b13f535151","datavalue":{"value":"https://arxiv.org/abs/1302.4622","type":"string"},"datatype":"url"},"type":"statement","id":"Q486751$E35B4972-C6DF-4018-AEFC-8099C1B123A3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"de4d5bcfd8f781ab20f96a1e407d7d1ab765edca","datavalue":{"value":"Let \\(p\\) a prime, \\(\\mathbb{F}_{p}\\) the finite field with \\(p\\) elements, \\(S\\subset \\mathbb{F}_{p}\\) and \\(\\mathcal{P}\\subset\\mathbb{F}_{p}[X]\\) a set of polynomials of bounded degree \\(\\leq d\\). The authors consider the problem to determine the integer \\(k\\) such that for all subsets \\(\\mathcal{A}, \\mathcal{B}\\subset\\; \\mathbb{F}_{p}\\) satisfying \\(\\mathcal{A}\\cap \\mathcal{B}=\\emptyset\\) and \\(|\\mathcal{A}\\cup \\mathcal{B}| =k,\\) there exists \\(P\\in \\mathcal{P}\\) such that \\(P(x)\\in S\\) if \\(x\\in \\mathcal{A}\\) and \\(P(x)\\notin S\\) if \\(x\\in \\mathcal{B}\\).  This problem is related to the study of the complexity of certain pseudorandom subsets.  The proofs are based on deep upper bounds for exponential sums and on character sums in finite fields. Furthermore, methods from additive number theory are used.","type":"string"},"datatype":"string"},"type":"statement","id":"Q486751$BEA257B5-F116-4186-86C9-C1EA298042CD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bf4743f5967bc42c7e3dc5b47222de4722471bb2","datavalue":{"value":{"entity-type":"item","numeric-id":180914,"id":"Q180914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$CE9EFFD3-C96D-4579-B023-D1C8027D8333","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cf81afcab7665ec308b53ada4821336ea108ff8c","datavalue":{"value":"11K45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q486751$2406619A-7FB9-4860-A65E-AEED742F3444","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ea78693e17c8554e13edc08c010b32c505af1dc3","datavalue":{"value":"11L07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q486751$89D1CDD4-3EE7-4087-99A6-13CC67F2E137","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"27714c785423c1e132f19cb058479d99cfdfe5f1","datavalue":{"value":"05B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q486751$E11EFF30-944B-4F9D-9B7B-F3F032005B87","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7e41a2227e1a01004d9a0f86fe298b8e3b7f1b22","datavalue":{"value":"6387274","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q486751$98AC91B1-AD06-46C5-B8FD-624D4036B457","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b20c3b8533e35d9d8474f7d42f21405746104025","datavalue":{"value":"pseudo-random subsets","type":"string"},"datatype":"string"},"type":"statement","id":"Q486751$50DAF93E-533A-42B0-9250-65B1172D21EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q486751$7BD22EA5-06F1-4DE5-905A-C0EED95FDB04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d0eb517400a7fceb799de77caacab49b788b7ebe","datavalue":{"value":"exponential sums","type":"string"},"datatype":"string"},"type":"statement","id":"Q486751$D2BFC3A4-BB8D-47FC-B501-E8D82C6C19DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6002cc885bf9252abbb051183aec49ec514dc6fb","datavalue":{"value":"character sums","type":"string"},"datatype":"string"},"type":"statement","id":"Q486751$8CA31803-FCA7-4487-A371-93E34938F274","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":"Q486751$DBFC695A-DDAE-4EEF-9347-C6E662363F99","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"094c43eca2155b2bafd8ef34fa51237899a5e0ec","datavalue":{"value":"W2962769037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q486751$E805B604-7AF4-4B14-AA64-DC162DFD891D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"edd48ee1fc229108d3a7af67e521f108eaeaf645","datavalue":{"value":{"entity-type":"item","numeric-id":757510,"id":"Q757510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$72DBCFA0-F6EF-4A38-A85F-D1F5F241D7A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1887c93a360b2859357c17b94f22dbd502b97cb2","datavalue":{"value":{"entity-type":"item","numeric-id":1878610,"id":"Q1878610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$CD7C8BDF-8038-4F2A-BD29-261672AAFA51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7850cc43bfa3db24d66ed0e020e66d204f0fec5b","datavalue":{"value":{"entity-type":"item","numeric-id":1062092,"id":"Q1062092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$C49982C8-B658-4F24-9EC6-48BD6B09F12D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ee754596f2a4b7b0df3780446c66fb85e641abf","datavalue":{"value":{"entity-type":"item","numeric-id":5558395,"id":"Q5558395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$EAE5D811-DFEC-4CB5-AB72-1F76382EA57B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7dad3f0f1feb8211c3786229e19cae1bce62249","datavalue":{"value":{"entity-type":"item","numeric-id":987532,"id":"Q987532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$9AFA4F2B-26E2-4E65-89E1-6D336982AF21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6210f2142e57d0cee16682a62a1c63fe9c08ca9b","datavalue":{"value":{"entity-type":"item","numeric-id":3505070,"id":"Q3505070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$911D997D-3D9A-47D9-A943-52A14C9B29A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"816fcb2007950892294e58eb4b90d13d4829c8ad","datavalue":{"value":{"entity-type":"item","numeric-id":2460691,"id":"Q2460691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$1C48C2C4-79F1-4E10-A784-7D83C18865C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51caa3ae818dc95ed6e679878c600e8626402413","datavalue":{"value":{"entity-type":"item","numeric-id":1945263,"id":"Q1945263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$7CBF378D-4626-4136-BD10-D8954238FEB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8be7ad34e82ac67e0e3a13efd4e701c7bc878cfa","datavalue":{"value":{"entity-type":"item","numeric-id":1845783,"id":"Q1845783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$D89BAC2A-4314-4A5D-976D-C29958F06180","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f22fe482d5f3dbd0aae49940e33772b040c78cd","datavalue":{"value":{"entity-type":"item","numeric-id":5561652,"id":"Q5561652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$BFB5C064-61EC-4B0C-9B12-A66548CA36DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5fd72823c849a4fbd32920d2edc16f6ddf8572e","datavalue":{"value":{"entity-type":"item","numeric-id":4314606,"id":"Q4314606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$B438069F-36FF-44C9-B994-EBDAC9637EF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89c1fcf4c4ef7855333712a63f5da02feeb35fa8","datavalue":{"value":{"entity-type":"item","numeric-id":2382245,"id":"Q2382245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$82E7CE14-B9D5-4947-BA78-B67DA7F36C40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45b97ecbe501f7580913bf613153e66ef6c73d61","datavalue":{"value":{"entity-type":"item","numeric-id":3949126,"id":"Q3949126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$B1D0E93F-4532-454B-8AE3-88EAF23080B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"594130c7bbbd248e7a9a3cefb556f275829b3598","datavalue":{"value":{"entity-type":"item","numeric-id":558307,"id":"Q558307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$A37A8311-FD9E-42F1-99B3-56F3D2954B72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbb56f2c0e6c202b641d2db83274bd3bebd51ba9","datavalue":{"value":{"entity-type":"item","numeric-id":5833284,"id":"Q5833284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$D6837D57-6858-4A18-BB38-6D464CB9FCCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b6d3f44cea5d5979d032c502c929204c327ac6c","datavalue":{"value":{"entity-type":"item","numeric-id":1881645,"id":"Q1881645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$11C8EB19-CAA7-4423-BFB8-A0AC7B961677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fc45277c8d069286a7edaad95ce5fbcd71be4f6","datavalue":{"value":{"entity-type":"item","numeric-id":4369666,"id":"Q4369666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$FC356138-A685-45E9-BB78-5BC5347D2213","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a7d519b0c3e9e2a83da1d766bad91503dad088e","datavalue":{"value":{"entity-type":"item","numeric-id":3437830,"id":"Q3437830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$6C290ECD-9E8D-4627-9B90-6C09F7AEDCEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd821e211b0adb2ba1ad6fb6157e35d4224f5a5a","datavalue":{"value":{"entity-type":"item","numeric-id":4780298,"id":"Q4780298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$D0225ED2-D3AC-4334-80BA-E477E6C45E21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a744c9c17719923d1a192e9214086e46257ed20d","datavalue":{"value":{"entity-type":"item","numeric-id":1227023,"id":"Q1227023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$FB424EF8-0064-48BF-B35E-FF4E82106FB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"feffca5c261d02754b6608fa507028f6a1aaaf0e","datavalue":{"value":{"entity-type":"item","numeric-id":4183410,"id":"Q4183410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$297E3241-CDD7-4474-8BC6-2C0DA5E5A423","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4d0e3440dbf0cc5fe07a3bfbbe27508957796d4b","datavalue":{"value":"10.5802/AIF.2847","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q486751$D439FD6D-B856-4A2D-A39B-B71B8C1A9165","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"dc1a1beeefbfbbcf5aa3adaae27b74e0e5ad168d","datavalue":{"value":{"entity-type":"item","numeric-id":4557581,"id":"Q4557581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486751$B4A38282-C1DE-4AA4-AE5D-F37D58DBE6CB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1cd80e1ebf2d4e23b0247dd763b54579d0843834","datavalue":{"value":{"entity-type":"item","numeric-id":1687703,"id":"Q1687703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"973db130d4045330e9535c44bda8eb8df7ff7cc3","datavalue":{"value":{"amount":"+0.8165016770362854","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":"Q486751$3F607965-F67B-443C-AC50-F4EE109EA69A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"959ac2540532c68b24bbbe2a494bc3fb5dc89855","datavalue":{"value":{"entity-type":"item","numeric-id":987532,"id":"Q987532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16969ba7c383558ac4df3026ff173f8fa40036ed","datavalue":{"value":{"amount":"+0.798661470413208","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":"Q486751$9FDA9183-C020-4E3D-BB04-F155DDCA4F83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4baa47e98ccf53f8e68e136662f1d1b4feaf53e2","datavalue":{"value":{"entity-type":"item","numeric-id":3505070,"id":"Q3505070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73920855d945d43a2bb89adeeecb7e8d7d75c8d6","datavalue":{"value":{"amount":"+0.7885660529136658","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":"Q486751$AC2D06CD-17E7-4BE2-9802-B8B295588012","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"835f5c33daf3041a7dc242426c6362da9506875c","datavalue":{"value":{"entity-type":"item","numeric-id":2052786,"id":"Q2052786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"62b54faf831c2221c975cbbcddb6227494db4e63","datavalue":{"value":{"amount":"+0.7819824814796448","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":"Q486751$29B0B36E-3B09-492C-90A1-0EA325FAF4E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0fc5fae5e21e597ef48d96d20fabd53fcc9e6a46","datavalue":{"value":{"entity-type":"item","numeric-id":2876596,"id":"Q2876596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6cb4890df62e5e442897b858ed43d778905e44e","datavalue":{"value":{"amount":"+0.7765502333641052","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":"Q486751$650411BF-4BB6-4A3B-941E-297D17FFF42C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of families of pseudo-random subsets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_families_of_pseudo-random_subsets"}}}}}