Pseudorandom binary functions on almost uniform trees (Q2905209)

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.