A lower bound for the complexity of separating functions (Q1070000)

Mostowski's separation theorem asserts that given two disjoint semi- algebraic subsets X and Y of \({\mathbb{R}}^ n\), there is a function f such that \(f(X)>0\) and \(f(Y)<0\) which is a sum of \(P_ i\sqrt{Q_ i}\), where \(P_ i\) and \(Q_ i\) are polynomials and \(Q_ i>0\). The result announced in this note is a lower bound for the number of summands needed: in \({\mathbb{R}}^{2^ M+1}\), one needs at least \(M+2\) summands in f for some X and Y.