Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In the following I am referring to a small argument made in "A counterexample to Borsuk's conjecture" by Jeff Kahn, Gil Kalai (see In this paper the authors bound a certain function via:

$f(d) \geq (1.203)^{\sqrt{d}}$

This inequality holds for $d = \binom{m}{2}-1$ where $m=4k$ for some prime power $k$. Then the claim is made that this also holds for sufficiently large general $d$ by the prime number theorem. Specifically they state that the bound is achieved for $d> 2,014$. Can someone elaborate on these last two points?

share|cite|improve this question
up vote 3 down vote accepted

Note their Theorem 1 claims a looser bound $f(d)>1.2^\sqrt{d}$ for general $d$.

Let $p_k$ be the $k$-th prime and $m_k=4p_k$ and $d_k = \binom{m_k}{2}-1$. Then $$ f(d_k+a)\ge f(d_k)>(1.203)^\sqrt{d_k}>1.2^\sqrt{d_k+a} $$ for small enough $a$ that satisfy the last inequality.

Take logs and square, and it's satisfied if $$ \begin{array}{c} d_k \log^2 1.203 > (d_k+a) \log^2 1.2 \\ a < d_k \left( \frac{\log^2 1.203}{\log^2 1.2} -1 \right) \\ a < (0.0275\ldots)d_k \end{array} $$

Thus the bound for $m_k=4p_k$ implies the $f(d)$ bound for all $d \in [d_k,\lfloor 1.0275 d_k\rfloor]$.

The prime number theorem implies that for $k$ large enough the primes are close together. For any $\epsilon>0$ there's a $k$ large enough so that we can bound $p_{n+1} < p_n (1+\epsilon)$ for all $n\ge k$. and since $d_k \simeq 8p_k^2$ we can bound $d_{n+1} < \lfloor 1.0275 d_n \rfloor$ for an appropriate choice of $\epsilon$. This will guarantee that $$ \bigcap_{n\ge k} [d_n,\lfloor 1.0275 d_n\rfloor] $$ is in fact all $d\ge d_k$.

Note that the paper doesn't claim that the bound holds for all $d>2014$, but that Borsuk's conjecture fails, i.e. that $f(d)>d+1$. Since 16 is a prime power, in their construction take $m=64$ and $d=\binom{m}{2}-1=2015$, then their explicit bound gives $f(2015)> 3751$ and hence that Borsuk's conjecture fails for $2014<d<3750$. The next prime power 17 gives $m=68,d=2277$ and $f(2277)>6329$ extending to $2014<d<6328$. Already the prime powers are dense enough to cover all $d>2014$ for this weaker bound.

share|cite|improve this answer

Zander explains well why $f(d)>1.2^d$ for large enough $d$. But with just the prime number theorem, it's hard to know how large is large enough. (Andrica's conjecture would give a nice explicit bound here.) Luckily for the second part of the question (why Borsuk fails for all $d>2014$) we don't need to know so much about prime numbers.

Taking the prime power $q=2^4$ gives $d=2015$ and disproves Borsuk for all dimensions between $d$ and $1.203^\sqrt d\approx 4008$. Taking $q=19$ gives $d=2849$ and disproves Borsuk up to dimension $1.203^\sqrt d\approx 19242$. Next we can take $q=32$ and from then on, successive powers of two suffice to disprove Borsuk for all higher dimensions.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.