# Application of prime number theorem

In the following I am referring to a small argument made in "A counterexample to Borsuk's conjecture" by Jeff Kahn, Gil Kalai (see http://arxiv.org/abs/math.MG/9307229) 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?

-

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.

-

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.

-