A general 4-words inequality with consequences for 2-way communication complexity (Q1118569)

We describe the main result. Let \({\mathcal X}\) and \({\mathcal Y}\) be two finite sets. We consider functions \(f: {\mathcal X}\times {\mathcal Y}\to {\mathbb{Z}},\) where \({\mathbb{Z}}\) is the ring of integers. With f we associate the ``sum- type function'' \(f_ n: {\mathcal X}^ n\times {\mathcal Y}^ n\to {\mathbb{Z}}\) defined by \(f_ n(x^ n,y^ n)=\sum^{n}_{t=1}f(x_ t,y_ t).\) Let \({\mathcal P}(f,{\mathcal R},n)\) be the set of pairs (A,B), \(A\subset {\mathcal X}^ n\) and \(B\subset {\mathcal Y}^ n\), with the \({\mathcal R}\)-4-words property \[ f_ n(a^ n,b^ n)-f_ n(a^ n,b^{'n})+f_ n(a^{'n},b^{'n})-f_ n(a^{'n},b^ n)\in {\mathcal R}. \] For M(f,\({\mathcal R},n)=\max \{| A| | B|:(A,B)\in {\mathcal P}(f,{\mathcal R},n)\}\) we have the General 4-words inequality: For any \({\mathcal R}\subset {\mathbb{Z}},\) \(M(f,{\mathcal R},n)\leq M(f,{\mathcal R},1)^ n.\) Furthermore, if \(0\in {\mathcal R}\) and \(M(f,\{0\},1)=M(f,{\mathcal R},1),\) then equality holds. This inequality is much more general than its predecessors [\textit{R. Ahlswede}, \textit{A. El Gamal}, \textit{K. F. Pang}, Discrete Math. 49, 1-5 (1984; Zbl 0532.94013); \textit{R. Ahlswede}, \textit{M. Moers}, Eur. J. Comb. 9, No.2, 175-181 (1988; Zbl 0549.05007)]. The \({\mathcal R}\)-4-words property extends Yao's [\textit{A. Yao}, Proc. 11th Ann. ACM Sympos. Theory of Computing 1979, 209-219] notion of monochromatic rectangles and the inequality is a key tool in deriving (often asymptotically optimal) bounds on 2-way communication complexity.