# Rademacher, maxima, convex hulls

Let $$F\subset \mathbb{R}^n$$ be a finite set and $$\sigma$$ be uniformly distributed over $$\{-1,1\}^n$$. The usual Rademacher average of $$F$$ (modulo normalizing factors) is $$R_n(F)=\mathbb{E}_\sigma \max_{f\in F}\sum_{i=1}^n \sigma_if_i.$$ Now let us define two operations on $$F$$: $$\mathrm{conv}(F)$$ and $$[F]_\vee$$. The former is just the convex hull of the vector-set $$F$$ in $$\mathbb{R}^n$$. The latter is defined by $$[F]_\vee=\{ f\vee g :f,g \in F\},$$ where $$(f\vee g)_i=\max\{f_i,g_i\}$$ is the coordinate-wise maximum. It is well-known (and easy to show) that $$R_n( \mathrm{conv}(F)) = R_n( F)$$.

Question: is it true that $$R_n( [\mathrm{conv}(F)]_\vee) = R_n( [F]_\vee)$$ ?

The inequality $$R_n( [F]_\vee) \le R_n( [\mathrm{conv}(F)]_\vee)$$ holds due to set containment. Also, $$\mathrm{conv}(F)$$ is an infinite set, so the $$\max$$ in the definition should be replaced by a $$\sup$$.

Update. Fedor Petrov has constructed a counterexample, which I've accepted. The more general conjecture I had was as follows. Define the $$k$$-fold max operator $$[F]_k$$ by $$[F]_k=\{ f_1\vee f_2\ldots\vee f_k :f_i \in F\}.$$ Is there a universal constant $$c$$ (independent of $$n$$ and $$k$$) such that $$R_n( [\mathrm{conv}(F)]_k) \le c R_n( [F]_k)$$?

• But $[\mathrm{conv}(F)]_\vee$ is not already a finite set? And it looks that the maximum over a subset may be only less than a maximum over a large set, so the opposite inequality should take place. – Fedor Petrov Apr 30 at 19:53
• @FedorPetrov Please see edits. – Aryeh Kontorovich Apr 30 at 20:58
• so your question is equivalent to "is it true that $R_n( [\mathrm{conv}(F)]_\vee)=R_n( [F]_\vee)$"? – Fedor Petrov Apr 30 at 21:02
• yes, I edited again – Aryeh Kontorovich Apr 30 at 21:11

## 1 Answer

It looks that no. Take $$n=4$$ and $$F$$ containing four vectors: $$f=(2,-2,1,-5); g=(-2,2,1,-5); h=(0,0,-5,1)$$. We have $$f\vee g=(2,2,1,-5)$$, $$f\vee h=(2,0,1,1)$$, $$g\vee h=(0,2,1,1)$$. Thus $$\max_{w\in [F]_\vee} (w_3+w_4-w_1-w_2)=0$$. On the other hand $$\frac{f+g}2\vee h=(0,0,1,1)$$, therefore $$\max_{w\in [\mathrm{conv}(F)]_\vee} (w_3+w_4-w_1-w_2)\geqslant 2$$.

• Your example appears to work, but I think an additional calculation is needed. $F$ only contains the 3 vectors $f,g,h$, yes? Your calculation shows supremacy for a given choice of $\sigma$, not for the average over $\sigma$. I performed the calculation, though, and there's a gap, so the example seems valid. – Aryeh Kontorovich May 1 at 14:40
• The values that I get for the two Rademacher averages are 100 and 102, respectively -- not very large. – Aryeh Kontorovich May 1 at 14:49
• But for any $\sigma$ we have an inequality (may be non strict) in the same direction. Thus equality could only appear if all of them turn into equalities, right? – Fedor Petrov May 1 at 15:22
• Yes, point taken. So the question is, how much of a (multiplicative) gap can you force for a single $\sigma$? For what fraction of the $\sigma$'s? I've expanded the conjecture in case this challenge appeals to you :) – Aryeh Kontorovich May 1 at 15:47