Communication complexity of some number theoretic functions (Q2470553)

The communication complexity \(C(b)\)\, of a Boolean function \(b(x,y)\),\, where \(x,y\)\, are \(n\)-bits integers, is the smallest possible number of bits exchanged by a two-party communication protocol which allows at least one party to compute the value \(b(x,y)\). In the paper the author obtains lower bounds for the communication complexity of three Boolean functions ``which naturally arise from some decision problems having a clear number theoretic flavour''. Explicitly: the parity \(f(x,y)\)\, of the sum of the binary digits of \(x+y\),\, the parity \(g(x,y)\)\, of the total number of prime divisors of \(x+y\)\, (counted with their multiplicity) and the function \(h(x,y)\)\, defined as 1 if the largest prime divisor of \(x+y\)\, is greater or equal than the threshold \(2^{e^{-1/2}n}\)\, and 0 otherwise. After listing in the Section 2 some auxiliary results the wanted bounds are provided in Section 3 (theorems 1-3): \begin{itemize} \item(1) \(C(f)\geq \beta n+O(1)\),\,\, where \(\beta=\frac{3}{2}(1-\frac{1}{2}\log_2\frac{\sqrt 2}{\sin(\pi/8)})=0.085667\dots\) \item (2) \(C(g)\geq \frac{3}{2}\log_2(n)+O(1)\) \item (3) \(C(h)\geq \frac{3}{2}\log_2(n)+O(1)\) Finally the author shortly discusses (Section 4) some other number theoretic functions for which similar bounds can be obtained.\end{itemize}