Adjusting a conjecture of Erdős

Walter Carnielli, Pietro K. Carolino

Abstract


We investigate a conjecture of Paul Erdős, the last unsolved problem among those proposed in his landmark paper [2]. The conjecture states that there exists an absolute constant $C > 0$ such that, if $v_1, \dots, v_n$ are unit vectors in a Hilbert space, then at least $C \frac{2n}{n}$ of all $\epsilon \in \{-1,1\}^n$ are such that $|\sum_{i=1}^n \epsilon_i v_i| \leq 1$.

We disprove the conjecture. For Hilbert spaces of dimension $d > 2,$ the counterexample is quite strong, and implies that a substantial weakening of the conjecture is necessary. However, for $d = 2,$ only a minor modification is necessary, and it seems to us that it remains a hard problem, worthy of Erdős.

We prove some weaker related results that shed some light on the hardness of the problem.

Full Text:

PDF


PID: http://hdl.handle.net/10515/sy53j39f9

Contributions to Discrete Mathematics. ISSN: 1715-0868