\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P4.29}{21(4)}{2014}
\usepackage{latexsym}
\usepackage{amssymb}

 \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
%
% \arxiv uses hyperref, and hyperrref complains about non-PDF section headings
% maybe it does not allow a formula in a section heading?
% for now, a simpler \arxiv macro
%\newcommand{\arxiv}[1]{{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\newcommand{\maysplit}{\discretionary{}{}{}}
\newcommand{\mayhyph}{\discretionary{-}{}{}}

% \theoremstyle{plain}
\newtheorem{theorem}{Theorem}
% \theoremstyle{remark}
% \newtheorem{remark}[theorem]{Remark}

\newcommand{\Ff}{{\mathbb F}}
\newcommand{\Rr}{{\mathbb R}}
\newcommand{\adj}{{\,\sim\,}}
\newcommand{\nadj}{{\,\not\sim\,}}
\newcommand{\longbar}[1]{{\overline{#1}}}
% \newcommand{\kx}{{\kern -0.33pt}}

\title{\bf A 64-dimensional counterexample\\ to Borsuk's conjecture}
\author{Thomas Jenrich\\
 {\small\tt thomas.jenrich@gmx.de}
\and 
Andries E. Brouwer\\
{\small\tt aeb@cwi.nl}}

\date{\dateline{Feb 3, 2014}{Oct 28, 2014}{Nov 6, 2014}\\
\small Mathematics Subject Classifications: 51M25, 05E30}


\begin{document}
\maketitle

\begin{abstract}
Bondarenko's 65-dimensional counterexample to Borsuk's conjecture
contains a 64-dimensional counterexample.
It is a two-distance set of 352 points.
\end{abstract}

\section{Introduction}
In 1933 Karol Borsuk \cite{Bor} asked whether each bounded set in the
$n$-dimensional Euclidean space (containing at least two points) can be
divided into $n+1$ parts of smaller diameter.
(The diameter of a set $X$ is the least upper bound of the distances
of pairs of points in $X$.) The hypothesis that the answer to that question
is positive became famous under the name \emph{Borsuk's conjecture}.

The first counterexamples were given by Jeff~Kahn and Gil~Kalai~\cite{KK}
who showed that Borsuk's conjecture is false for $n = 1325$ and gave an
exponential lower bound $c^{\sqrt n}$ with $c = 1.2$ for the number of parts
needed for large $n$.
Subsequently, several authors found counterexamples in lower dimensions.

In 2013 Andriy V. Bondarenko \cite{Bon} constructed a 65-dimensional
two-distance set $S$ of 416 vectors that cannot be divided into fewer
than 84 parts of smaller diameter. That was not just the first known
two-distance counterexample to Borsuk's conjecture but also a
considerable reduction of the lowest known dimension the conjecture fails in
in general.

This article presents a 64-dimensional subset of $S$ of size 352
that cannot be divided into fewer than 71 parts of smaller diameter,
thus producing a two-distance counterexample to Borsuk's conjecture
in dimension 64.

\section{\kern-1.35pt Euclidean representation of strongly regular graphs}

We very briefly repeat the basic facts.
More details can be found in \cite{Bon} and \cite{BroHae}.

A finite graph $\Gamma$ without loops or multiple edges is called
a srg$(v,k,\lambda,\mu)$, where srg abbreviates `strongly regular graph',
when it has $v$ vertices, is regular of valency $k$, where $0 < k < v-1$,
and any two distinct vertices $x,y$ have $\lambda$ common neighbours when
$x$ and $y$ are adjacent (notation: $x \adj y$), and $\mu$ common neighbours
otherwise (notation: $x \nadj y$).

The adjacency matrix $A$ of $\Gamma$ is the matrix of order $v$
defined by \mbox{$A_{xy} = 1$} if $x \adj y$ and $A_{xy} = 0$ otherwise.
Let $I$ be the identity matrix of order $v$,
and let $J$ be the matrix of order $v$ with all entries equal to 1.
Then $A$ is a symmetric matrix with zero diagonal such that
$AJ = JA = kJ$ and $A^2 = kI + \lambda A + \mu (J-I-A)$.
It follows that the eigenvalues of $A$ are $k, r, s$, with $k \ge r \ge 0 > s$,
where $r,s$ are the two solutions of $x^2 + (\mu-\lambda)x + \mu-k = 0$,
so that $(A-rI)(A-sI) = \mu J$.
The multiplicities of $k, r, s$ are $1, f, g$ (respectively),
where $1+f+g = v$ and $k+fr+gs = 0$.

The matrix $M = A-sI-\frac{k-s}{v}J$ has rank $f$, so that the map
$x \mapsto \longbar{x}$ that sends each vertex $x$ to row $x$ of $M$
is a representation of $\Gamma$ in $\Rr^f$,
and the inner product $(\longbar{x},\longbar{y})$ depends only on whether
$x=y$, $x \adj y$ or $x \nadj y$.

\section{The $G_2(4)$ graph}
There exists a graph $\Gamma$ that is a srg(416,100,36,20)
with automorphism group $G_2(4)$:$2$ acting rank 3,
with point stabilizer $J_2$:$2$,
see, e.g., Hubaut \cite{Hubaut}, pp.~370,\,372.
Here $v = 416$, $k = 100$, $r=20$, $s=-4$ and $f=65$, $g=350$, so that
$M = A+4I-\frac14J$ and we have $M^2 = 24M = 24A + 96I - 6J$.
This means that
$$
(\longbar{x},\longbar{y}) = \left\{ \begin{array}{ll}
90 & \mbox{if~} x = y \\
18 & \mbox{if~} x \adj y \\
-6 & \mbox{if~} x \nadj y,
\end{array} \right.
$$
and $\| \longbar{x} - \longbar{y} \|^2 = 144$ when $x \adj y$,
and $\| \longbar{x} - \longbar{y} \|^2 = 192$ when $x \nadj y$.

This graph $\Gamma$ has maximal clique size 5
(because each point neighbourhood is a srg(100,36,14,12),
that has point neighbourhoods srg(36,14,4,6), which has
bipartite point neighbourhoods).

Bondarenko's example $S$ is the image of $\Gamma$ in $\Rr^{65}$.
Any subset of smaller diameter corresponds to a clique
and therefore has size at most 5. Since $|S| = 416$, at least 84 subsets
of smaller diameter are needed to cover the set.

% Our example is a subset $T$ of $S$, of size 352, on a hyperplane.
% This will be an example in $\Rr^{64}$ such that at least
% 71 subsets of smaller diameter are needed to cover it.

\section{Structure of the $G_2(4)$ graph}

The graph $\Gamma$ occurs as point neighbourhood in the Suzuki graph
$\Sigma$, which is a srg(1782,\maysplit 416,\maysplit 100,\maysplit 96)
(cf.~\cite{Hubaut}).
For two nonadjacent vertices $a,b$ of $\Sigma$, we can identify
the set of 416 neighbours of $a$ with the vertex set $X$ of $\Gamma$,
and then the 96 common neighbours of $a$ and $b$ form a 96-subset $B$ of $X$.

The graph $\Sigma$ has a triple cover $3\cdot\Sigma$ constructed by
Leonard Soicher \cite{Soicher}. It is distance-transitive
with intersection array \{416, 315, 64, 1;~1, 32, 315, 416\}
on 5346 vertices.

{\scriptsize

$$\begin{picture}(280,30)(0,-16)
\put(0,0){\circle{20}}\put(0,0){\makebox(0,0){1}}
\put(10,0){\line(1,0){50}}
\put(13,-8){\makebox(0,0)[l]{416}}
\put(57,-8){\makebox(0,0)[r]{1}}
\put(70,0){\circle{20}}\put(70,0){\makebox(0,0){416}}
\put(70,-18){\makebox(0,0){100}}
\put(80,0){\line(1,0){50}}
\put(83,-8){\makebox(0,0)[l]{315}}
\put(127,-8){\makebox(0,0)[r]{32}}
\put(140,0){\circle{20}}\put(140,0){\makebox(0,0){4095}}
\put(140,-18){\makebox(0,0){320}}
\put(150,0){\line(1,0){50}}
\put(153,-8){\makebox(0,0)[l]{64}}
\put(197,-8){\makebox(0,0)[r]{315}}
\put(210,0){\circle{20}}\put(210,0){\makebox(0,0){832}}
\put(210,-18){\makebox(0,0){100}}
\put(220,0){\line(1,0){50}}
\put(223,-8){\makebox(0,0)[l]{1}}
\put(267,-8){\makebox(0,0)[r]{416}}
\put(280,0){\circle{20}}\put(280,0){\makebox(0,0){2}}
\put(280,-13){\makebox(0,0){-}}
\end{picture}$$
}

We see that the 96-subset $B$ is the union of three mutually nonadjacent
subsets $B_1$, $B_2$ and $B_3$ of size 32.
% The graphs induced on $B_i$, $i=1,2,3$ are 2-coclique extensions
% of the folded 5-cube (and hence have valency 20).
Put $C = X \setminus B$ so that $|C| = 320$.
% Since $B_1$, $B_2$, $B_3$ are orbits of some group of automorphisms,
Since $3 \cdot \Sigma$ is tight (cf.~\cite{JKT}),
the partition $\{B_1,B_2,B_3,C\}$ of $X$ is regular (a.k.a. equitable)
with diagram

{\scriptsize

$$
\begin{picture}(100,90)(0,-10)
\put(0,35){\circle{20}}\put(0,35){\makebox(0,0){320}}
\put(10,35){\line(1,0){50}}
\put(8.94,39.47){\line(2,1){52.11}}
\put(8.94,30.53){\line(2,-1){52.11}}
\put(70,0){\circle{20}}\put(70,0){\makebox(0,0){32}}
\put(70,35){\circle{20}}\put(70,35){\makebox(0,0){32}}
\put(70,70){\circle{20}}\put(70,70){\makebox(0,0){32}}
\put(70,-15){\makebox(0,0){20}}
\put(70,20){\makebox(0,0){20}}
\put(70,55){\makebox(0,0){20}}
\put(52,1){\makebox(0,0){80}}
\put(52,39){\makebox(0,0){80}}
\put(52,69){\makebox(0,0){80}}
\put(14,22){\makebox(0,0){8}}
\put(18,39){\makebox(0,0){8}}
\put(14,48){\makebox(0,0){8}}
\put(0,20){\makebox(0,0){76}}
\end{picture}
$$
}
(that is, each vertex in $B_1$ has 20 neighbours in $B_1$,
none in $B_2$, $B_3$, and 80 in $C$, etc.).

Now we define
$T = \{ \longbar{x} \mid x \in B_1 \cup C \} \subseteq \Rr^{65}$.
Let $u$ be the vector
$$
u = \sum_{y \in B_2} \longbar{y} - \sum_{y \in B_3} \longbar{y} .
$$
Then $u$ is a vector in our $\Rr^{65}$, and for all $x \in T$ we have
$(u,x) = 0$. On the other hand, $(u,u) = 64 \cdot 576 \ne 0$.
It follows that $T$ lies in the hyperplane $u^\perp$,
a copy of $\Rr^{64}$. Because any subset of smaller diameter contains at most
5 vectors, we proved

\begin{theorem}
There is a $2$-distance set $T$ of size $352$ in $\Rr^{64}$ such that
any partition of $T$ into parts of smaller diameter has at least
$71$ parts.
\end{theorem}

\noindent{\bf Remark}~~
For more explicit constructions and a corresponding computer program,
see~\cite{Jen}.


\begin{thebibliography}{99}
\bibitem{Bon}
Andriy V. Bondarenko,
{\it On Borsuk's conjecture for two-distance sets},
Discrete and Computational Geometry {\bf 51} (2014) 509--515.
% 2013-05-19, \arxiv{1305.2584v2}~.

\bibitem{Bor}
Karol Borsuk,
{\it Drei S\"atze \"uber die $n$-dimensionale euklidische Sph\"are},
Fund. Math. {\bf 20} (1933) 177--190.

\bibitem{BroHae}
Andries E. Brouwer \& Willem H. Haemers,
{\it Spectra of graphs}, Springer, 2012.

\bibitem{Hubaut}
Xavier L. Hubaut,
{\it Strongly regular graphs},
Discr. Math. {\bf 13} (1975) 357--381.

\bibitem{Jen}
Thomas Jenrich,
{\it A 64-dimensional two-distance counterexample to Borsuk's conjecture},
2013-08-25, \arxiv{1308.0206v5}~.

\bibitem{JKT}
Aleksandar Juri\v{s}i\'c, Jack Koolen \& Paul Terwilliger,
{\it Tight distance-regular graphs},
J. Alg. Combin. {\bf 12} (2000) 163-197.

\bibitem{KK}
Jeff Kahn \& Gil Kalai,
{\it A counterexample to Borsuk's conjecture},
Bull. Amer. Math. Soc. (New Series) {\bf 29} (1993) 60--62.

\bibitem{Soicher}
Leonard H. Soicher,
{\it Three new distance-regular graphs},
Europ. J. Combin. {\bf 14} (1993) 501--505.

\end{thebibliography}


\end{document}