Skip to main content
The sharp bound in the two-dimensional case addressed
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141

It is a classical result of Barany and Grinberg (generalizing an earlier result of Spencer) that there exist $\lambda_1,\dotsc,\lambda_N\in\{\pm 1\}$ with $$ \|\lambda_1a_1+\dotsb+\lambda_Na_N\| \le 2n. $$ The paper of Barany-Grinberg was published in 1981, but they indicated that the problem goes back to a yearwas posed in 1963 paper by Dvoretzky. I was excited to learn that BaranyInterestingly, Barany and Grinberg, andalong with Gergely Ambrus, have just published another paper on this subject!.

Notice that for $n=2$, it is easy to get the sharp bound $$ \|\lambda_1a_1+\dotsb+\lambda_Na_N\| \le \sqrt 2; $$ it follows by using induction and observing that among any three vectors in $\mathbb R^2$ of length at most $1$, there are two vectors such that either their sum, or their difference has length at most $1$, and that for any two vectors of length at most $1$, either their sum, or their difference has length at most $\sqrt 2$.

It is a classical result of Barany and Grinberg (generalizing an earlier result of Spencer) that there exist $\lambda_1,\dotsc,\lambda_N\in\{\pm 1\}$ with $$ \|\lambda_1a_1+\dotsb+\lambda_Na_N\| \le 2n. $$ The paper of Barany-Grinberg was published in 1981, but they indicated that the problem goes back to a year 1963 paper by Dvoretzky. I was excited to learn that Barany, Grinberg, and Ambrus have just published another paper on this subject!

It is a classical result of Barany and Grinberg (generalizing an earlier result of Spencer) that there exist $\lambda_1,\dotsc,\lambda_N\in\{\pm 1\}$ with $$ \|\lambda_1a_1+\dotsb+\lambda_Na_N\| \le 2n. $$ The paper of Barany-Grinberg was published in 1981, but they indicated that the problem was posed in 1963 by Dvoretzky. Interestingly, Barany and Grinberg, along with Gergely Ambrus, have just published another paper on this subject.

Notice that for $n=2$, it is easy to get the sharp bound $$ \|\lambda_1a_1+\dotsb+\lambda_Na_N\| \le \sqrt 2; $$ it follows by using induction and observing that among any three vectors in $\mathbb R^2$ of length at most $1$, there are two vectors such that either their sum, or their difference has length at most $1$, and that for any two vectors of length at most $1$, either their sum, or their difference has length at most $\sqrt 2$.

added 173 characters in body
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141

Problems of this sort are well-studied. TheIt is a classical result of Barany and Grinberg (generalizing an earlier result of Spencer) is that there exist $\epsilon_1,\dotsc,\epsilon_N\in\{\pm 1\}$$\lambda_1,\dotsc,\lambda_N\in\{\pm 1\}$ with $$ \|\epsilon_1a_1+\dotsb+\epsilon_Na_N\| \le 2n. $$$$ \|\lambda_1a_1+\dotsb+\lambda_Na_N\| \le 2n. $$ Googling for "Erdos balancing vectors" gives lotsThe paper of further linksBarany-Grinberg was published in 1981, but they indicated that the problem goes back to a year 1963 paper by Dvoretzky. I was excited to learn that Barany, Grinberg, and Ambrus have just published another paper on this subject!

Problems of this sort are well-studied. The classical result of Barany and Grinberg (generalizing an earlier result of Spencer) is that there exist $\epsilon_1,\dotsc,\epsilon_N\in\{\pm 1\}$ with $$ \|\epsilon_1a_1+\dotsb+\epsilon_Na_N\| \le 2n. $$ Googling for "Erdos balancing vectors" gives lots of further links.

It is a classical result of Barany and Grinberg (generalizing an earlier result of Spencer) that there exist $\lambda_1,\dotsc,\lambda_N\in\{\pm 1\}$ with $$ \|\lambda_1a_1+\dotsb+\lambda_Na_N\| \le 2n. $$ The paper of Barany-Grinberg was published in 1981, but they indicated that the problem goes back to a year 1963 paper by Dvoretzky. I was excited to learn that Barany, Grinberg, and Ambrus have just published another paper on this subject!

Source Link
Seva
  • 23k
  • 2
  • 59
  • 141

Problems of this sort are well-studied. The classical result of Barany and Grinberg (generalizing an earlier result of Spencer) is that there exist $\epsilon_1,\dotsc,\epsilon_N\in\{\pm 1\}$ with $$ \|\epsilon_1a_1+\dotsb+\epsilon_Na_N\| \le 2n. $$ Googling for "Erdos balancing vectors" gives lots of further links.