{"entities":{"Q1180406":{"pageid":1191155,"ns":120,"title":"Item:Q1180406","lastrevid":46214821,"modified":"2025-12-24T08:11:11Z","type":"item","id":"Q1180406","labels":{"en":{"language":"en","value":"On mod \\(p\\) transversals"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 25756"}},"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":"Q1180406$65441AFB-92D0-4641-9FD2-4D967420439C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d1deb8425cc88b164e5b492246656cb641f0b3f9","datavalue":{"value":{"text":"On mod \\(p\\) transversals","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1180406$E3FF4AC8-81B8-496F-91D1-ABC222289ECF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"64a3e1a1608bb56b38f2be9530b3de589b5b4c7c","datavalue":{"value":"0759.05096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180406$940B3751-54B4-49B5-9543-250C4F6830E4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7ecaece1b8d7e2a594d81cc4a14f38744cf361d1","datavalue":{"value":"10.1007/BF01375469","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180406$08E4603F-0C15-4B17-99C9-FF56EFC14D96","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":"Q1180406$8BB8287D-1786-4468-A6EE-17BD937500E0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70844ffc4666eabac4e20376c648613dbe8620f7","datavalue":{"value":{"time":"+1992-06-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1180406$F984177B-051F-4EE2-BAEB-12CA30FF13EF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"734f4f10c3a52b6cf477ef64ee4dc053aaedddce","datavalue":{"value":"A mod-\\(p\\) transversal in a affine space over the field \\(Z/2Z\\) is a set whose intersection with any hyperplane which does not contain the origin contains a number of points not divisible by \\(p\\). The author provides an estimate on the minimal size \\(f(p,n)\\) of such a transversal in terms of the prime \\(p\\) and the dimension \\(n\\) of the affine space. The result as given by theorem 1 reads:  \\[ e^{-1}(p-1)^{(n/p-1)}-(p-1)\\leq f(p,n)\\leq(p-1)2^{\\lceil(n/p-1)\\rceil}-(p-1). \\]  The upper bound is proven by means of a simple direct construction. The lower bound is obtained by means of techniques involving the finite Fourier transform. It involves a so-called uncertainty inequality for finite Abelian groups which states that the for a nonzero function the product of the sizes of the supports for a function and its transform exceeds the order of the group. The problem is motivated by its usage in the theory of lower bounds for circuit complexity. More in particular the possibility and/or complexity of replacing unbounded fan in or gates by mod-\\(n\\) gates is discussed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180406$3CA7F63B-5334-4319-B460-70AD0B5DF13D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ca9cd2a9131e1d8839142cee57f1e863d7371382","datavalue":{"value":{"entity-type":"item","numeric-id":582045,"id":"Q582045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180406$F75FDB2F-0010-420F-8BB0-4CABF491FEEE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1ad1bf428b79a0176d62afa9a160b2a17f8d9ea9","datavalue":{"value":"05D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180406$B7D1C131-5099-4CD1-A598-056E9C1EA4CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f0d1683dc539e8d2a37b0615ea6222a71b0b65bc","datavalue":{"value":"05B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180406$79170330-56ED-474E-9427-3D69EF9CF0FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180406$DF2D0F81-706F-4677-9CDA-107D9859D750","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180406$9F7A9295-7CDD-4670-842A-2055D439CC3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180406$D6C44647-B554-4867-B1C6-95DD0EF3B6C1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b45ab1b65dbbf654e7c94c195b7f8f20d07ddb26","datavalue":{"value":"25756","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180406$D1BD3AEF-1B6D-470F-9355-1F3E29F82DB6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68f0187c80f319f514f027e2a22d4128fa6f3b57","datavalue":{"value":"transversals","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180406$EE7D1C30-7105-4B01-9BEE-E88EB6164FB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7bff96c0998be14f000e1db2b7634129b6d2b907","datavalue":{"value":"mod-\\(p\\) circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180406$EA1B4B78-7EE3-4ABF-A6F7-23628AED8BE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180406$A509B411-DA16-4CDA-92C6-741D88B44E99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e92efef5b2340f98ceeaac77ccef50e77e812184","datavalue":{"value":"affine space","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180406$0461F135-985F-4599-947B-A585A8F6D88A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"994d7c10a73037bc0ad3d751aaec1f75d12928c0","datavalue":{"value":"Fourier transform","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180406$E05F348F-A9EB-44F5-A599-915E5A6498CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd567929e2ce537540b802f7b8096b1960d82947","datavalue":{"value":"uncertainty inequality","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180406$B2221BAF-1812-4F5C-A249-B07942FC2E14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f0cb341ca7876bc8468eee4ea8e9008984980e7","datavalue":{"value":"circuit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180406$7A29258C-E58E-4992-AFE4-09EB098608D5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d1a8b239d5a7f549910817e61d8809ac746dac16","datavalue":{"value":{"entity-type":"item","numeric-id":762169,"id":"Q762169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180406$425D9580-9EF0-4EBA-AE61-6352B061C246","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1d5f9b44dbc16076ab6a860f2d536a0d52667ef","datavalue":{"value":{"entity-type":"item","numeric-id":233554,"id":"Q233554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180406$FF67FA72-33EE-4E2D-99AD-C1868D63BC82","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":"Q1180406$CC672794-CB75-4EFA-81DE-D99D2938524F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"85332f45c574807884e55f6488cd3b450f276a8f","datavalue":{"value":{"entity-type":"item","numeric-id":1117696,"id":"Q1117696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180406$C27CE079-F96D-4A46-A81A-B02209C75C1E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a4e9a05863f34632a113fc6cc9d19e26a82d0fb0","datavalue":{"value":"https://doi.org/10.1007/bf01375469","type":"string"},"datatype":"url"},"type":"statement","id":"Q1180406$A29DDF88-E31F-4122-AE39-8F8CB8A08099","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"15f890d252d12b79e9a9433a84fb8d5b147cf3f6","datavalue":{"value":"W1481966678","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180406$5052537E-FE39-4097-BAAD-10907478AA44","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ac89276cfa7d61eafe084a6197fc8277fc833d2","datavalue":{"value":{"entity-type":"item","numeric-id":5461373,"id":"Q5461373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fdf8b8400a3bd958221d83701e2892eccb4aa50f","datavalue":{"value":{"amount":"+0.7358735799789429","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":"Q1180406$0CB8BBC0-3160-452C-BFF6-DDEDCC9790F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70968f6748e7c6ed156e1b8e703d2128ffc4b4dc","datavalue":{"value":{"entity-type":"item","numeric-id":2022742,"id":"Q2022742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb7a4b13b5729a2ffbdc5a8fc2fb60ccd409b727","datavalue":{"value":{"amount":"+0.719113826751709","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":"Q1180406$10903425-4100-4F17-8C78-D821026259DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9fc81e70dc8cfeb5303afdafa3b015837ffea685","datavalue":{"value":{"entity-type":"item","numeric-id":1590080,"id":"Q1590080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b94ad37a190cbc789282e7db15ec05534ad44ac6","datavalue":{"value":{"amount":"+0.7135350704193115","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":"Q1180406$85D2C1DF-8CF2-4C6A-9EFC-FA6E712F922A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3d655077f625425c25cb71678766e7fb9519911","datavalue":{"value":{"entity-type":"item","numeric-id":4437511,"id":"Q4437511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"861a233e63c1c38e5a343e404cc17f99c70ea25c","datavalue":{"value":{"amount":"+0.7132927179336548","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":"Q1180406$8A61D34D-5272-4A47-B93A-12D5B7F87932","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1180406","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1180406"}}}}}