| |||||||||||||||

## IMC2024: Day 1, Problem 5
Fedor Petrov, St Petersburg State University
where \(\displaystyle x_1,\ldots,x_n\in B\) are arbitrary points in general position and the summations are over all \(\displaystyle 2^n\) choices of signs (here \(\displaystyle o\) is identified with the origin, that is, \(\displaystyle x\) and \(\displaystyle -x\) are symmetric with respect to \(\displaystyle o\)). Indeed, taking the expectation in (1) over independent random uniform \(\displaystyle x_1,\ldots,x_n\), we get \(\displaystyle 2^nf(p)\geqslant 2^n f(q)\). (To be specific, here ``general position'' means that for any point set \(\displaystyle A\subset \{\pm x_1,\ldots,\pm x_n,p,q\}\), which does not contain simultaneosuly \(\displaystyle x_i\) and \(\displaystyle -x_i\), is not contained in an (affine) \(\displaystyle (|A|-2)\)-dimensional plane. This holds with probability 1.) To prove (1), we use the following formula for the characteristic function \(\displaystyle \chi_P\) of the convex polyhedron \(\displaystyle P\subset \mathbb{R}^d\): if \(\displaystyle P_1,\ldots,P_k\) are all facets of \(\displaystyle P\), and \(\displaystyle Q_i\) is the convex hull of \(\displaystyle o\) and \(\displaystyle P_i\), then \(\displaystyle \chi_P=\sum \pm \chi_{Q_i}\), where the sign is plus if \(\displaystyle o\) and \(\displaystyle P\) are on the same side of \(\displaystyle P_i\), and minus otherwise. Indeed, for every point \(\displaystyle p\) in general position look how the ray \(\displaystyle op\) intersects the boundary of \(\displaystyle P\) and realize that for at most two summands the contribution of the RHS at point \(\displaystyle p\) is non-zero, and the total contribution equals 1 when \(\displaystyle p\) is inside \(\displaystyle P\) and 0 (possibly as \(\displaystyle 0=1-1\)) otherwise. Use this formula for every polyhedron \(\displaystyle P\) with \(\displaystyle n\) vertices \(\displaystyle y_1,\ldots,y_n\), where each \(\displaystyle y_i\) is \(\displaystyle \pm x_i\). These polyhedrons are simplicial (all facets are simplices) because of the general position condition. Sum up over all \(\displaystyle 2^n\) such \(\displaystyle P\), we get the expression of \(\displaystyle \sum_P \chi_P\) as a linear combination of \(\displaystyle \chi_S\), where \(\displaystyle S\) are simplices formed by \(\displaystyle o\) and some \(\displaystyle d\) points in \(\displaystyle \{\pm x_1,\ldots,\pm x_n\}\) (not containing \(\displaystyle x_i\) and \(\displaystyle -x_i\) simultaneously). For proving (1), it suffices to verify that all coefficients of \(\displaystyle \chi_S\) in this linear combination are positive (since two sides of (1) are the values of the sum \(\displaystyle \sum_P \chi_P\) at \(\displaystyle p\) and \(\displaystyle q\)). Let's find a coefficient of \(\displaystyle \chi_S\), where, say, \(\displaystyle S\) is a simplex with vertices \(\displaystyle o,x_1,\ldots,x_d\). The plane \(\displaystyle \alpha\) through \(\displaystyle x_1,\ldots,x_d\) partitions \(\displaystyle \mathbb{R}^d\) onto two parts \(\displaystyle H^+\) (containing \(\displaystyle o\)) and \(\displaystyle H^{-}\) (not containing \(\displaystyle o\)). For every pair \(\displaystyle \{x_i,-x_i\}\) with \(\displaystyle i>d\), either both points belong to \(\displaystyle H^+\), or one belongs to \(\displaystyle H^{-}\) and another to \(\displaystyle H^+\). \(\displaystyle \chi_S\) goes with the plus sign for \(\displaystyle P\) with vertices \(\displaystyle x_1,\ldots,x_d\) and other vertices from \(\displaystyle H^+\), and with the minus sign for \(\displaystyle P\) with vertices \(\displaystyle x_1,\ldots,x_d\) and other vertices from \(\displaystyle H^-\). It is immediate that there are at least as many pluses as minuses. | |||||||||||||||

© IMC |