\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\newcommand{\cyc}{\varPhi}
\newcommand{\red}[1]{\textcolor{red}{#1}}
\renewcommand{\(}{\bigl(}
\renewcommand{\)}{\bigr)}
\newcommand{\llbrace}{\{\mkern-3mu\{}
\newcommand{\rrbrace}{\}\mkern-3mu\}}
\newcommand{\calM}{\mathcal{M}}
\newcommand{\calA}{\mathcal{A}}
\newcommand{\calR}{\mathcal{R}}
\newcommand{\calL}{\mathcal{L}}
\newcommand{\abs}[1]{\mathopen|#1\mathclose|}
\newcommand{\Sd}{\varSigma_d}
\newcommand{\redto}{\rightarrowtail}
\renewcommand{\dfrac}[2]{\lower0.12ex\hbox{\large$\textstyle\frac{#1}{#2}$}}
\def\nicebreak{\vskip0pt plus50pt\penalty-300\vskip0pt plus-50pt }
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf Paths Through Equally Spaced \\
\vskip .1in
Points on a Circle
}
\vskip 1cm
\large
Brendan D. McKay\footnote{This project employed resources
from the National Computational Infrastructure of Australia.}\\
School of Computing\\
Australian National University\\
Canberra, ACT 2601 \\
Australia\\
\href{mailto:brendan.mckay@anu.edu.au}{\tt brendan.mckay@anu.edu.au}\\
\ \\
Tim Peters\\
Python Software Foundation\\
USA\\
\href{mailto:tim@python.org}{\tt tim@python.org}
\end{center}
\vskip .2 in
\begin{abstract}
Consider $n$ points evenly spaced on a circle, and a
path of $n-1$ chords that uses each point once.
There are $m=\lfloor n/2\rfloor$ possible chord lengths, so
the path defines a multiset of $n-1$ elements drawn
from $\{1,2,\ldots,m\}$.
The first problem we consider is to characterize the multisets which are
realized by some path.
Buratti conjectured that all multisets can be realized when~$n$
is prime, and a generalized conjecture for all~$n$ was
proposed by Horak and Rosa. Previously the conjecture was proved
for $n\leq 19$ and $n=23$; we extend this to $n\leq 37$.
The second problem is to determine the number of distinct
(euclidean) path lengths that can be realized. For this
there is no conjecture; we extend current knowledge from
$n\leq16$ to $n\leq37$.
When $n$ is prime, twice a prime, or a power of~2, we prove
that two paths have the same length only if
they have the same multiset of chord lengths.
\end{abstract}
\section{Introduction}
Consider $n$ points equally spaced around a circle.
There are $m=\lfloor n/2\rfloor$ possible chord lengths.
The \textit{type} of a chord is its position in the list
of chord lengths in increasing order; thus
a chord of type~1 is between two adjacent points and
a chord of type~$m$ is between two points as antipodal
as possible.
If the points are numbered cyclically, the type of the chord
between points~$i$ and~$j$ is $\min\{\abs{i-j},n-\abs{i-j}\}$.
Now connect the points by a polygonal path using each point exactly once.
The \textit{associated multiset} of the path is the multiset of the types of the
chords.
We consider two questions:
\medskip
(Q1) Which multisets are the associated multiset of some path?
(Q2) How many distinct (euclidean) lengths can paths have?
\medskip
We denote a multiset by the notation
$[\ell_1,\ldots,\ell_m]$, where $\ell_j$ is the number of elements
equal to~$j$.
Figure~\ref{circle} shows the associated multiset of a path
in this notation.
\begin{figure}[H]
\[ \includegraphics[scale=1]{circle} \]
\caption{A path for $n=9$ with associated multiset $[2,3,1,2]$.\label{circle}}
\end{figure}
Three classes of multisets are relevant to this study.
\begin{itemize}\itemsep=0pt
\item[(a)] $\calM_n$ is the class of all multisets
$[\ell_1,\ldots,\ell_m]$ such that $m=\lfloor n/2\rfloor$ and
$\sum_{j=1}^m \ell_j=n-1$.
\item[(b)] The \textit{admissible} multisets are the class
$\calA_n\subseteq \calM_n$ of multisets with this additional
property: for each divisor $d$ of $n$,
$\sum_{j=1}^{\lfloor m/d\rfloor} \ell_{jd} \leq n-d$.
\item[(c)] The \textit{realizable} multisets are the class
$\calR_n\subseteq \calM_n$ of multisets associated
with some path.
\end{itemize}
In 2007, Marco Buratti communicated to Alex Rosa the conjecture
that $\calR_n=\calM_n$ if $n$ is prime~\cite{HorakRosa}.
Despite its simple statement, the conjecture remains open,
though Mariusz Meszka confirmed it by computer for $n\leq 23$~\cite{Meszka}.
It is easy to see that the primality of $n$ is essential for
$\calR_n=\calM_n$, however Horak and Rosa proposed a more
general conjecture that has drawn a lot of attention~\cite{HorakRosa}.
\begin{conjecture}[Buratti--Horak--Rosa]\label{BHR}
$\calR_n=\calA_n$ for $n\geq 1$.
\end{conjecture}
Horak and Rosa noted that $\calR_n\subseteq\calA_n$; for a
self-contained proof see Pasotti and Pellegrini~\cite{PasottiPellegrini1}.
Meszka confirmed the conjecture for $n\leq 18$~\cite{Meszka}.
In addition, Conjecture~\ref{BHR} has been proved for a considerable
number of special cases~\cite{Capparelli,Chand,Ollis,OllisGrow,
PasottiPellegrini1,PasottiPellegrini2,Vazquez}.
We will prove:
\begin{theorem}\label{mainthm}
The Buratti--Horak--Rosa conjecture is true for $n\leq 37$.
\end{theorem}
For question Q2, the first investigation we are aware of was carried out
in the mid-1980s by Daniel Gittelson, then at the University of Michigan
School of Medicine. Gittelson found the counts up to 12~points~\cite{DLG}.
T. D. Noe added the counts up to 16~points in 2007~\cite{Noe}.
We will continue the sequence up to $n=37$.
\section{Realization of multisets}
Our most computationally challenging task was to find paths that
realize each of approximately $6.4\times 10^{13}$ admissible multisets.
For this
a simple backtrack search is by far not efficient enough for large~$n$,
so we designed several improved algorithms.
Here we describe the two most successful.
Note that, although many special cases of Conjecture~\ref{BHR} have
been proved, they are only a small fraction of cases for large~$n$,
so we chose to not exclude them from our search.
One observation used by both methods is this: if $k$ is an
integer coprime to $n$, then $kM$ is realizable if and only
if $M$ is realizable, where
$kM = \llbrace k\ell \bmod n \mid \ell \in M\rrbrace$.
(Here double braces indicate that we are dealing with a multiset.)
Thus, only one of the multisets in each equivalence class
defined by this congruence need be tested.
One approach was a randomized form of hill-climbing.
Figure~\ref{pathflip} shows three ways to transform a path,
which were employed for theoretical purposes by Horak and Rosa~\cite{HorakRosa}.
In each case, the induced multiset loses one element and
gains another (perhaps equal).
The idea is to start with some path and then repeatedly apply
transformations until the required multiset is achieved.
\begin{figure}[H]
\[ \includegraphics[scale=0.8]{pathflip} \]
\caption{A path and three types of modification\label{pathflip}}
\end{figure}
Choice of transformation was made at random with a strong
bias towards beneficial moves. Transformations which moved
away from the target (fewer chords matched the required
multiset) were given a weight of 1, sideways transformations
(same number of matches) a weight of 100, and transformations
that moved closer to the target had a weight of 10000 (or $\infty$ if the
target multiset was immediately reached). The admissible
multisets were processed in lexicographic order, meaning that
each multiset was usually very similar to the one before.
This meant it was efficient to use the solution for each
multiset as the starting point to search for a solution for the
following multiset.
There was a large limit on the number of iterations, with
code to start over with a random path if the limit was reached,
but this never happened.
As an example, for $n=34$ the average number of iterations
was~$104$.
The second method for realizing multisets was a mixture of
random and deterministic search.
A boolean array indexed by a multiset ranking function
kept track of which multisets had been realized, while simultaneously
one process generated random paths and another realized
multisets using a backtracking search. In both cases, multisets
related by coprime multiplication (as described above) and by the last
operation in Figure~\ref{pathflip} were also marked off.
The backtracking search had some problem-specific features
that we now describe.
At each recursion level, we have a path so far, and a multiset of
chord types that still need to be used. For each distinct chord
type remaining, there can be 0, 1 or 2 unused points that can
reached by such a chord. The order in which the possibilities
are attempted is important for the average efficiency.
When all possibilities are exhausted, backtrack to the previous
level occurs.
Heuristics are used to try to guess at a good order in which to try
chord types. In general, the program favors a pair of chord type and
next point that leaves the next point with the fewest number of possible
exits,
and also favors chord types of which the fewest remain to be used.
This all has much in common with the usual heuristics in backtracking
Hamiltonian path solvers, including various conditions that allow to
prune a search ``early''.
There are also some specializations, driven by experience. For
example, if $n$ is even, and only one instance of an odd chord type
remains, there is only one possible place that chord can appear in the
remaining path.
This usually worked very well, but in a small percentage of cases
would take hundreds of times longer. A pleasant surprise was that
Limited Discrepancy Search (LDS)~\cite{LDS}, adapted for non-binary
trees, proved extremely effective, 99.9\%\ of the time finding a
path with discrepancy no larger than 1, and with
discrepancy 2 in 99\%\ of the remaining cases.
However, particularly for the largest size $n=28$ completed by this
method, a handful of cases required discrepancies as high as 14
and took minutes of cpu time each.
For both implementations, whenever a realization is found it is
checked in separate code.
The result of the computations was that all admissible multisets
for $n\leq 37$ are realizable.
All cases for $n\leq 28$ were completed with both methods.
\section{When two paths have the same length}\label{identities}
For definiteness we will assume a circle of radius~1.
The length of a chord of type~$j$ is $2\sin(j\pi/n)$.
Therefore, realizable multisets $[\ell_1,\ldots,\ell_m]$
and $[\ell'_1,\ldots,\ell'_m]$ have the same length if and
only if $\sum_{j=1}^m (\ell'_j-\ell_j) \sin(j\pi/n)=0$.
Also note that $\sum_{j=1}^m (\ell'_j-\ell_j)=0$, since
all multisets in $\calM_n$ have $n-1$ elements.
We will call a sequence $(a_1,\ldots,a_m)$ of rational
numbers an \textit{identity} if
\begin{align}
\sum_{j=1}^m a_j\sin\Bigl(\frac {j\pi}{n}\Bigr) &= 0, \
\text{~~and} \label{eq1} \\[-0.8ex]
\sum_{j=1}^m a_j &= 0. \label{eq0}
\end{align}
%
Let $z=e^{i\pi/n}$, which is a primitive $(2n)$-th root of~1.
Then $\sin\bigl( \frac {j\pi}{n}\bigr) = \dfrac{1}{2i}(z^j-z^{-j})$.
Thus~\eqref{eq1} can be written
\[
\frac{1}{2i} \sum_{j=1}^m a_j (z^j-z^{-j}) = 0.
\]
Since $z\ne 0$, this is equivalent to $P_n(z)=0$, where
\begin{equation}\label{eq3}
P_n(z) = z^m \sum_{j=1}^m a_j (z^j-z^{-j})
= \sum_{j=1}^{m} a_j z^{m+j} - \sum_{j=1}^m a_j z^{m-j}.
\end{equation}
Note that $P_n(z)$ is a polynomial with rational coefficients.
The \textit{cyclotomic polynomial} of order $2n$ is the
monic polynomial $\cyc_{2n}(x)$ whose zeros are the primitive
$(2n)$-th roots of unity. In particular, $\cyc_{2n}(z)=0$.
For the theory of cyclotomic polynomials, see Prasolov~\cite[pp.~89--99]{Prasolov}.
We will require these properties: (1) up to scaling, $\cyc_{2n}(z)$ is the
unique nonzero rational polynomial of least degree that has~$z$ as a zero;
(2) the degree of $\cyc_{2n}(x)$ is Euler's totient function $\varphi(2n)$
(the number of positive integers less than $2n$ and coprime to $2n$);
(3) $\cyc_{2n}(x)$ is palindromic (the list of coefficients reads the same
forwards and backwards).
Perform a rational polynomial division:
\[
P_n(x) = C_n(x)\cyc_{2n}(x) + R_n(x),
\]
where $C_n(x)$ is a rational polynomial and $R_n(x)$ has lower degree than
$\cyc_{2n}(x)$.
Since $R_n(z)=0$, the minimality of $\cyc_{2n}(x)$ implies
that $R_n(x)$ is identically zero.
The coefficients of $R_n(x)$ are linear combinations of $a_1,\ldots,a_m$
which must equal~0.
Including equation~\eqref{eq0}, we have a linear system whose solution
space is the vector space of all identities.
\subsection{Example}
Consider $n=15$, $m=7$.
%
The cyclotomic polynomial is
\[
\cyc_{30}(x) = x^8 + x^7 - x^5 - x^4 - x^3 + x + 1.
\]
Performing the division, we find $P_{15}(x) = C_{15}(x) \cyc_{30}(x) + R_{15}(x)$,
where
\begin{align*}
C_{15}(x) &= a_7x^6 + (a_6-a_7)x^5 + (a_5-a_6+a_7)x^4
+ (a_4-a_5+a_6)x^3 \\
&{\qquad} + (a_3-a_4+a_5)x^2
+ (a_2-a_3+a_4+a_7)x + a_1-a_2+a_3+a_6-a_7, \\
R_{15}(x) &= (-a_1+a_2+a_5-a_6+a_7)x^7 + (-a_1+a_2+a_4+a_7) x^6
+ (a_1-a_2+a_3+a_6) x^5 \\
&{\qquad} + (a_1-a_3+a_6-a_7) x^4 + (a_1-a_2-a_4-a_7) x^3
+ (-a_2-2a_5-a_7)x^2 \\
&{\qquad} + (-a_1-a_4-2a_6) x - a_1+a_2-a_3-a_6.
\end{align*}
Now we require $R_{15}(x)=0$ identically, so we can set each of
the coefficients to 0 and we also need $a_1+a_2+a_3+a_4+a_5+a_6+a_7=0$.
In matrix form:
\[
\begin{bmatrix}
-1 & 1 & -1 & 0 & 0 & -1 & 0
\\
-1 & 0 & 0 & -1 & 0 & -2 & 0
\\
0 & -1 & 0 & 0 & -2 & 0 & -1
\\
1 & -1 & 0 & -1 & 0 & 0 & -1
\\
1 & 0 & -1 & 0 & 0 & 1 & -1
\\
1 & -1 & 1 & 0 & 0 & 1 & 0
\\
-1 & 1 & 0 & 1 & 0 & 0 & 1
\\
-1 & 1 & 0 & 0 & 1 & -1 & 1
\\
1 & 1 & 1 & 1 & 1 & 1 & 1
\end{bmatrix}\;
%
\begin{bmatrix}
a_1\\a_2\\a_3\\a_4\\a_4\\a_6\\a_7
\end{bmatrix}
=
\begin{bmatrix}
0\\0\\0\\0\\0\\0\\0\\0\\0
\end{bmatrix}
.
\]
The solution space has dimension 2:
\[
\bigl\langle
(1, 0, -1, -1, -1, 0, 2), (0, 1, 0, -2, -1, 1, 1)
\bigr\rangle.
\]
\subsection{What is the dimension?}
We now determine the dimension of the vector space of identities.
For those values of~$n$ where the dimension is~0, only
paths with the same multiset of chord types have the same length.
\begin{theorem}\label{dimen0}
For all $n\geq 1$, the dimension of the vector space of identities is
\[
\max\bigl\{ 0, m - \tfrac12\varphi(2n) - 1\bigr\}.
\]
In particular, the dimension is~0 if
and only if $n=9$, or $n$ is a prime, twice a prime, or a power of~2.
\end{theorem}
%
\begin{proof}
For a polynomial $f(x)=\sum_{j=0}^k b_j x^j$, we say that $f(x)$
is \textit{$k$-palindromic} if $b_{k-j}=b_j$ for all~$j$, and
\textit{$k$-antipalindromic} if $b_{k-j}=-b_j$ for all~$j$.
These properties are respectively equivalent to
$x^kf(1/x)=f(x)$ and $x^kf(1/x)=-f(x)$.
As examples, $\cyc_{2n}(x)$ is $\varphi(2n)$-palindromic,
while $P_n(x)$ defined in~\eqref{eq3} is $2m$-antipalindromic.
Consider the equation $P_n(x)=C_n(x)\cyc_{2n}(x)$. The degree
of $C_n(x)$ is at most $t=2m-\varphi(2n)$. Note that
$\varphi(2n)$ is even, so $t$ is also even. Also,
\[
x^t C_n(1/x) = \frac{x^{2m} P_n(1/x)}{x^{\varphi(2n)}\cyc_{2n}(1/x)}
= \frac{-P_n(x)}{\cyc_{2n}(x)} = -C_n(x),
\]
so $C_n(x)$ is $t$-antipalindromic. By the same logic, if
$C_n(x)$ is $t$-antipalindromic then $P_n(x)$ is $2m$-antipalindromic
and so corresponds to a solution of~\eqref{eq1}.
Choosing a basis of $t/2$ linearly independent $t$-antipalindromic
polynomials for $C_n(x)$, such as $x^j-x^{t-j}$ for $0\leq j\leq \frac12 t-1$,
we find that the vector space of solutions of~\eqref{eq1} has
dimension~$t/2$.
If that vector space lies within the hyperplane defined by~\eqref{eq0},
the vector space of identities has dimension $t/2$; otherwise it
has dimension~$t/2-1$.
Recall that $\varphi(2n) = n\prod_p\,(1-1/p)$ where the
product is over all distinct odd primes~$p$ dividing~$n$.
From this, a little calculation shows that $t=0$ only
if $n$ is an odd prime ($\varphi(2n)=n-1$) or a power of~2
($\varphi(2n)=n$).
To show that the dimension is $t/2-1$ rather
than $t/2$ when $t\geq 2$, we have only to find $(a_1,\ldots,a_m)$ that
satisfies~\eqref{eq1} but not~\eqref{eq0}.
Let's call this an \textit{improper identity}.
Note that if $(a_1,\ldots,a_{\lfloor n/2\rfloor})$ is an improper
identity for $n$ then
$(a'_1,\ldots, a'_{\lfloor kn/2\rfloor})$ is an improper
identity for $kn$, where
$a'_{kj}=a_j$ for $1\leq j\leq m$ and $a'_{kj}=0$ otherwise.
Therefore, it suffices to find improper identities for some
values of $n$ that divide any value of $n$ giving $t\geq 2$.
The minimum set is: twice an odd prime, the square of an odd prime,
and the product of two distinct odd primes.
First, suppose that $n$ is twice an odd prime. Then
$\cyc_{2n}(x)=\sum_{j=0}^{n-1} (-1)^j x^{2j}$ and $t=2$.
Taking $C_n(x)=x^2-1$,
notice that the coefficients of $C_n(x)\cyc_{2n}(x)$ are
all $\pm 2$ except for the first and last which are $\pm 1$.
Therefore, condition~\eqref{eq0} is not satisfied
and we have an improper identity.
Next suppose that $n=p^2$ where $p$ is an odd prime.
Then $\cyc_{2n}(x) = \sum_{j=0}^{p-1} x^{jp}$ and
$t=p-1$. Consider $C_n(x)=x^{t/2-1}-x^{t/2+1}$,
so $C_n(x)\cyc_{2n}(x) = \sum_{j=0}^{p-1} \,(x^{jp+t/2-1}-x^{jp+t/2+1})$.
The coefficients are thus in $\pm 1$ pairs, but for $j=(p-1)/2$ the
pair is $x^{m-1}-x^{m+1}$. Thus, $\sum_{j=0}^m a_j$, which is
the sum of the coefficients up to and including that of $x^{m-1}$,
equals~1 and condition~\eqref{eq0} is violated. So this is
an improper identity.
Finally, consider $n=pq$ where $3\leq p