Simple disproof of Danzer — Grünbaum conjecture

204 Views Asked by At

A set of points in $\mathbb R^n$ is acute if any three points from this set form an acute triangle. In 1962 Danzer and Grünbaum conjectured that cardinality of acute set in $\mathbb R^d$ is $2d-1$, no more. In 1983 Erdős and Furedi disproved this conjecture in their famous article. They used the probabilistic method and proved that the cardinality of the set grows exponentially with respect to the dimension of the space. The first proofs with explicit construction was given much later, as I know.

I found an explicit construction so simple, that the situation with this conjecture looks somewhat curious. I do not know if this proof was published somewhere, so I'm asking to check it (I'm only an amateur).


Let us consider unit cube $[0,1]^n$ with vertices $x^i = (x^i_1, x^i_2, ..., x^i_n)$, $x^i_j \in \{0,1 \}$, $i = 1, ..., 2^n, \ j = 1, ..., n.$ The coordinates $x^i_1, x^i_2, ..., x^i_n$ we will call the base coordinates. We will denote the modulo-2 addition, or XOR, operation by $\oplus $. To each $x^i$ we add $\frac {n(n-1)}{2}$ additional coordinates (all pairwise XORs of base coordinates): $$\tilde x^i = (x^i_1, ..., x^i_n, \ x^i_1\oplus x^i_2, \ x^i_1\oplus x^i_3, \ldots, x^i_ {n-1}\oplus x^i_ {n}), \quad i = 1, \ldots, 2^n. \quad (1)$$

Lemma 1. The set (1) is acute set.

Lemma 2. Cardinality of the set (1) grows exponentially with respect to the dimension $n$ and, roughly, grows exponentially with respect to $\sqrt{D}$ where $D=n + \frac{n (n-1)}{2} = \frac{n (n + 1)}{2}$ .

Proof of Lemma 1.
Let us choose three arbitrary points from (1); we can prove that the triangle of these points is acute. It suffices to verify that any angle with vertex at the point $(0)=(0,0, ..., 0)\in [0,1]^D$ is acute.

Now, we choose arbitrary $p, q \in 2, 3, ..., 2^n, \ p \ne q,$ and check that for some coordinate $1 \le m \le D$ it is true that $\tilde x^p_m = \tilde x^q_m = 1$ (then the inner product of vectors from $(0)$ to $\tilde x_p$ and from $(0)$ to $\tilde x_q$ is positive, so the angle with the vertex at the point $(0)$ is acute).

We consider the first $n$ base coordinates of the vectors $\tilde x^p$ and $\tilde x^q$. Since these are non-zero vertices of unit cube $[0,1]^n$, there are $r, s \in [1, ..., n]$ such that $\tilde x^p_r = 1$ and $\tilde x^q_s = 1$. If, in addition, $ \tilde x^q_r = 1 $ or $ \tilde x^p_s = 1 $, then the Lemma 1 is proved with $m = r$ or $m = s$ respectively. Otherwise, $\tilde x^p_m = x^p_r\oplus x^p_s = 1$ and $\tilde x^q_m = x^q_r\oplus x^q_s = 1$ for some $m$. Q.E.D.

Proof of Lemma 2. Obvious.

In such a way, the Danzer — Grünbaum conjecture is disproved.

Update. In the proof above we consider only the case when the vertex of the angle is at the zero point. As Serg pointed out in the comment, the argumentation for this is insufficient. Therefore, I will consider separately the general case.

We use the fact that the angle constructed on the vertices of the unit cube can not be obtuse and all the summands of the inner product are nonnegative. Let us choose 3 arbitrary points $a, b, c$ from (1) and consider the angle with vertex in $a$. Let $\vec {ab}$ and $\vec {ac}$ be two vectors of this angle. Obviously, there are base coordinates $j_1, j_2 \in [1, n]$ such that $b_{j_1} \ne a_{j_1}$ and $c_ {j_2} \ne a_ {j_2}$. If $j_1=j_2$ or $b_{j_1} = c_{j_1}$ then the inner product $(\vec {ab}, \vec {ac})> 0$ (the summand $ab_ {j_1} \cdot ac_{j_1}> 0$). If $j_1 \ne j_2$ then the summand $(ab_ {j_1} \oplus ab_{j_2}) \cdot (ac_{j_1} \oplus ac_{j_2})>0$ in the inner product.