On the sum of squares of cell complexities in hyperplane arrangements (Q1320395)

For an arrangement \(A\) of \(n\) hyperplanes in \(\mathbb{R}^ d\) \((d \geq 2)\), let \(f_ i (c)\) denote the number of \(i\)-dimensional faces of a cell \(c\) of \(A\), and let \(f(c) = \sum^{d-1}_{i = 0} f_ i(c)\) be the complexity of the cell \(c\). The authors prove that \[ \sum_ c f(c)^ 2 = O \Bigl( n^ d \log^{\lfloor {d \over 2} \rfloor - 1}n \Bigr), \tag{*} \] where the sum extends over all cells of \(A\), and the constant of proportionality depends on \(d\). Moreover, it is shown that the total number of faces, bounding any \(m\) distinct cells of \(A\), is \(O(m^{{1 \over 2}} n^{{1 \over 2}} \log^{(\lfloor {1 \over 2} \rfloor - 1) \cdot {1 \over 2}} n)\), and several further applications regarding face count are added. Finally, in view of \((*)\) the authors conjecture that the correct bound is \(\Theta (n^ d)\).