{"entities":{"Q2905209":{"pageid":2915934,"ns":120,"title":"Item:Q2905209","lastrevid":51535529,"modified":"2026-01-18T16:45:38Z","type":"item","id":"Q2905209","labels":{"en":{"language":"en","value":"Pseudorandom binary functions on almost uniform trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6072446"}},"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":"Q2905209$48F33608-0749-432B-A3AE-5EA3DCBD6EE6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d5776484f780a63c851d21823241f83439c307ae","datavalue":{"value":"1254.11075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2905209$8B7B95AC-B227-47EB-91EC-9F446CAFEA65","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"06f3bc845549649de9f51c98d4930123765c2014","datavalue":{"value":{"entity-type":"item","numeric-id":213647,"id":"Q213647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2905209$21B88924-3646-46B8-941B-951EEC9484E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"356bb4c266bf9e3ca3c21020d756884c1f8075a9","datavalue":{"value":{"entity-type":"item","numeric-id":169095,"id":"Q169095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2905209$BD316184-335A-4DCD-B39A-4C2875D3130A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f0c3d276717394fe802c49433b5c508ad63c9f5d","datavalue":{"value":{"entity-type":"item","numeric-id":178493,"id":"Q178493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2905209$99B0767D-DBE3-43BB-94FF-DFDA870E4FFB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2fb48138cd3ab2fa344ede5e5ab8bd9f00883a6e","datavalue":{"value":{"time":"+2012-08-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2905209$359614A9-EBAE-4EB2-896B-2281989AF5AF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cf81afcab7665ec308b53ada4821336ea108ff8c","datavalue":{"value":"11K45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2905209$5CB3EE81-D982-49AA-B7B7-205856B6E108","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2905209$1C22D328-F6A5-4DB9-AA17-DE3D29683D67","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a125ef6d7cd23a33d7d991b96b33e48ad0536b7c","datavalue":{"value":"6072446","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2905209$5395C5F7-42BF-4C6A-9183-A8B65CB25D27","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1bb77b2c1bfe5c3305b095a9e38ba52e57a8f30e","datavalue":{"value":"pseudorandom binary function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2905209$026C2950-C56E-4265-8773-12CE8FFB35C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1938182d7458afd340caab93d280aab707a5dc6f","datavalue":{"value":"uniform tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2905209$D7BBA3AD-DD67-4545-8522-5BCCE1A06922","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac6aac01a1d75372fe6ec054328aa4a1f0ece96a","datavalue":{"value":"correlation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2905209$F14208DC-D36B-4619-88EE-0D01740A50B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2761bdc40553125e7de6ae63b64d38a792ebd166","datavalue":{"value":"Legendre symbol","type":"string"},"datatype":"string"},"type":"statement","id":"Q2905209$7E1354C5-8B1F-410C-AFAA-2722A3E7453F","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":"Q2905209$2A88CA80-12E0-4BEB-8E33-EB716BBD3332","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"04560c054db54c9d4a425934f175e89f9fa997ac","datavalue":{"value":{"text":"Pseudorandom binary functions on almost uniform trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2905209$053DA945-6186-48FC-BE9A-06950252D122","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4e90764d5ef25d1fc3a66af56be90ba25802facd","datavalue":{"value":{"entity-type":"item","numeric-id":6771202,"id":"Q6771202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2905209$C68FD82E-1512-4740-82DD-696AF9A7A703","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"244f5829d63d1e462378ed37272d414eb74d0aaf","datavalue":{"value":"Let \\(r, s \\in \\mathbb N\\) and\\ \\(r\\geq 2\\), \\(s\\geq 2\\), then a tree is called an \\(r\\)-almost, \\(s\\)-uniform tree if the root has \\(r\\) children and, except for the vertices in the last row, all the other vertices have \\(s\\) children, and also denotes a binary function on the tree \\(T\\) is a function \\(f\\) of the type \\(f: \\rho(T)\\rightarrow \\{-1, 1\\}\\),\\ where \\(\\rho(T)\\) is the set of the vertices of a tree \\(T\\).NEWLINENEWLINEIn this paper, the authors consider the pseudorandomness of binary functions defined on the \\(r\\)-almost, \\(s\\)-uniform tree, which introduces the measures of pseudo-randomness of binary functions of this type and analyze the connection between these measures. Then we can obtain NEWLINE\\[NEWLINE \\widetilde{C}_{k,l}(f, T)\\leq (k+1)C_{l}(E_{N}(f, T)), NEWLINE\\]NEWLINE and give a well low bound that NEWLINE\\[NEWLINE \\delta N^{1/2}<\\widetilde{C}_{l}(f, T), NEWLINE\\]NEWLINE where \\(\\widetilde{C}_{l}(f, T)\\) is the universal correlation measure of order \\(l\\) of \\(f\\) over \\(T\\) and the binary sequence \\(E_{N}(f, T)\\). In addition, the authors have investigated the uniform binary tree \\(T'\\). Then we have NEWLINE\\[NEWLINE \\widetilde{C}_{2}(\\lambda', T')\\ll N^{1/2}(\\log N)^{2}\\quad \\text{and}\\quad C_{2}(E_{N'}(\\lambda', T'))\\gg N'. NEWLINE\\]NEWLINE Finally, the authors also study the normality measure \\(\\overline{N}_{k}(\\rho, T)\\) of order \\(k\\) of the binary function of the above type. Then we have the following results NEWLINE\\[NEWLINE \\overline{N}_{k}(\\lambda, T)>\\frac{2^{2^{k+1}-1-k}-1}{2^{2^{k+1}-1}}(2^{K-k+1}-1) NEWLINE\\]NEWLINE and NEWLINE\\[NEWLINE \\overline{N}_{k}(\\rho, T)\\leq 20(2{k-1}-1)p^{1/2}\\log p \\, (\\ll2^{k}N^{1/2}\\log N), NEWLINE\\]NEWLINE where \\(\\lambda\\) and \\(\\rho\\) are binary functions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2905209$FFA91D7C-032C-4691-B63A-0BCEA807793F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9421b8b7f29b543c4cce5f443b47e928081c391","datavalue":{"value":{"entity-type":"item","numeric-id":2869641,"id":"Q2869641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e45c9e6dc04a0cd09b001841c3216091e583f198","datavalue":{"value":{"amount":"+0.9142444133758544","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":"Q2905209$355E6B91-EE03-44FC-A6BF-0F3805ED5A30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93c61ab44eca2ff5b24bd6ca161ed180617e264c","datavalue":{"value":{"entity-type":"item","numeric-id":5232592,"id":"Q5232592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fec1d97852c5f554c9120171f5a91930af8cedc1","datavalue":{"value":{"amount":"+0.8259917497634888","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":"Q2905209$6B368F34-33B2-484E-947C-9B3E25B6E934","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a49bb75e32aab965880e6f02ac7529c5edbea41b","datavalue":{"value":{"entity-type":"item","numeric-id":4548854,"id":"Q4548854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3e7c2a740f39d236f314c433a87fe07ddca8954","datavalue":{"value":{"amount":"+0.7490135431289673","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":"Q2905209$EF2B4C10-B1FE-4ADD-A55A-D508426290FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b37f81b0cddd04184caf07dd00744d44f254528","datavalue":{"value":{"entity-type":"item","numeric-id":2826765,"id":"Q2826765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b4207f082c8ab4845dd0c7d968171374dff03e4","datavalue":{"value":{"amount":"+0.7477180361747742","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":"Q2905209$F25155E9-2ED1-4F1C-818E-BFFC14EEA65C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94063ce1396616badca2c4224f90816c0f67469e","datavalue":{"value":{"entity-type":"item","numeric-id":3079942,"id":"Q3079942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f6e1a9788dedd5ed49f62ed62a1b0a042406454","datavalue":{"value":{"amount":"+0.7468560338020325","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":"Q2905209$670C0FCA-76BE-4396-9C20-40A5B7CD70CD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2905209","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2905209"}}}}}