\def\inbar{\,\vrule height1.5ex width.4pt depth0pt}
\def\IQ{\relax\hbox{$\inbar\kern-.3em{\rm Q}$}}
\def\IN{\relax{\rm I\kern-.18em N}}
\def\IR{\relax{\rm I\kern-.18em R}}
\def\ind{{\rm In}\,}
\def\trc{{\rm Tr}\,}
\def\beginproof{\underline{Proof}\nopagebreak}
\def\endproof{\nopagebreak\begin{flushright}$\Box$
\end{flushright}}
\newtheorem{problem}{Problem}
\newtheorem{conjecture}{Conjecture}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{alternative}{Alternative}
\renewcommand{\thedefinition}{\thesection.\arabic{definition}}
\renewcommand{\thetheorem}{\thesection.\arabic{theorem}}
\newcommand{\reset}{\setcounter{definition}{0}\setcounter{theorem}
{0}}
\documentstyle[11pt,twoside,epsf]{article}
%empirical parameters for 2.5cm margins (A4 paper)
%TeXview preferences must be Left Margin: 1.0in, Top Margin: 1.5in
\oddsidemargin 0.80truecm
\evensidemargin -0.19truecm
\topmargin -1.65truecm
\headheight 0.00truecm
\headsep 0.00truecm
\textheight 23.50truecm
\textwidth 15.00truecm
\footheight 0.00truecm
\footskip 1.20truecm
\raggedbottom
\title{Maximizing Irregularity and the Golomb Ruler Problem}
\author{D. Kent Freeman \\
C.N.R.S. -- LUMINY -- CASE 907 \\
Centre de Physique Th\'{e}orique \\
F-13288 Marseille CEDEX 9 \\
FRANCE}
\begin{document}
\maketitle
\begin{abstract}
The problem of attempting to construct radar signals whose
ambiguity
functions are sharply peaked in both time and frequency gives
rise to a quantitative concept of the
{\em irregularity} of a distribution of points. The problem of
maximizing the irregularity of $N$
points distributed on a bounded closed interval is here examined.
A discrete mathematical tool for
studying the irregularity function is developed --- Pascal-like
triangles constructed from
non-negative integers obeying a particular addition rule. These
triangles make explicit the
structure of the irregularity function; all questions about the
(continuous) irregularity function
become questions about this integral construction, many of which
can be answered easily and
elegantly. One important question about the integral construction
has been previously studied under
the name of the {\em Golomb Ruler Problem}. It turns out that
maximizing irregularity and
constructing Golomb rulers are closely related problems, each
providing a interesting new
perspective from which to study the other.
\end{abstract}
\clearpage
\begin{section}{Introduction}
\reset
Quite recently, A.~Grossmann introduced a canonical way of
defining
a continuous function that can be used to describe the
``degree of irregularity'' of a distribution
of~$N$ points~\cite{AG}. Such functions occur naturally
in the search for radar or sonar signals
with ``optimal`` autocorrelation properties. In this
context, the~$N$ points naturally live in (some
compact subset of) the $2$-dimensional phase space.
More generally, however, the problem of
maximizing irregularity can be formulated as a point
placement problem on any $D$-dimensional
surface --- subject to certain topological and group
theoretic restrictions~\cite{AG}.
In the present work, we treat the simplest case of~$N$
points distributed on a bounded closed ($1$-dimensional) interval.
In this case, one can define the ``degree of irregularity'' of a
distribution of~$N$ points to be simply the {\em minimum
difference of differences} attained among those~$N$ points. The
result is a continuous function on the $N$-dimensional hypercube
which, despite its deceptively simple definition, is surprisingly
rich in structure. Exploring this structure by using the idea of
``rulers'', or representations of integers by differences is the
unifying theme.
Reference~\cite{AG} should be regarded as a companion
paper to the present work. Although independent, that work
contains two things which are of particular relevance. First, it
contains the more general group-theoretic definition of {\em
irregularity}, of which the present treatment is a special case.
Secondly, it gives a detailed description of how the concept of
irregularity arises naturally in radar theory, and can be used to
construct signals with {\em ambiguity functions} which are sharply
peaked in phase space. As this second item provides the primary
motivation for the present work, we will provide a very brief
summary. A clear introductory treatment of radar theory, which has
more detailed explanations of the terminology and concepts used
below, is given in reference~\cite{REB}.
Let $f \in L^2(\IR)$. The (narrowband) {\em ambiguity function}
of~$f$ is defined to be the inner product of~$f$ with a copy of
itself which has been shifted in both time and frequency. We
define an operator which effects this time-frequency shift by
\begin{equation}
\left[E_{\tau,\omega}f\right](t) \equiv f(t-\tau)
e^{-i\omega t}.
\end{equation}
The ambiguity function of~$f$ is then
\begin{eqnarray}
A_f(\tau,\omega) & \equiv & (f,E_{\tau,\omega}f) \nonumber \\
& = & \int_{-\infty}^{\infty} dt\, f^*(t)
f(t-\tau)
e^{-i\omega t}.
\end{eqnarray}
This function can be used to characterize the performance
of the waveform~$f(t)$ in radar and sonar applications. In
particular, the shape of $A_f(\tau,\omega)$ near the origin
determines the accuracy of time and frequency shift measurements
using the waveform~$f(t)$, and its ability to resolve closely
spaced targets; therefore, we would like $A_f(\tau,\omega)$ to be
as sharply ``peaked'' as possible. Due to the close relationship
it bears with the Fourier transform, many simple properties of the
ambiguity function can easily be proved~\cite{REB}. For our
purposes, the following two are most relevant:
\begin{eqnarray}
|A_f(\tau,\omega)| & \le & |A_f(0,0)|; \label{eq:origin} \\
\frac{1}{2 \pi} \int_{-\infty}^{\infty} d\tau
\int_{-\infty}^{\infty} d\omega\,
|A_f(\tau,\omega)|^2 & = & |A_f(0,0)|^2.
\end{eqnarray}
The first property says that the maximum value of
$|A_f(\tau,\omega)|$ is attained at the origin. The second
property says that the total volume under
$|A_f(\tau,\omega)|^2$ is proportional to the square of
this maximum value. Taken together, these two properties say
roughly that any attempt to make the main lobe narrower must
result in an increase of $|A_f(\tau,\omega)|$ somewhere else. This
is a consequence of the Heisenberg uncertainty principle.
In an attempt to overcome the above constraint (in as much
as this is possible), the following idea has been proposed.
Suppose the signal~$f$ is actually a superposition of time and
frequency shifted copies of some more basic function~$f_0$; i.e.,
\begin{equation}
f = \sum_j E_{\tau_j,\omega_j}f_0.
\end{equation}
The function~$f_0$ may be, for example, a Gaussian.\footnote{It
is easy to show that if $f_0$ is a Gaussian then
$|A_{f_0}(\tau,\omega)|$ is a ($2$-dimensional) Gaussian.} We wish
to express $A_f(\tau,\omega)$ in terms of
$A_{f_0}(\tau,\omega)$. This is a straighforward calculation
which uses the following two easily-proved properties of
$E_{\tau,\omega}$:
\begin{eqnarray}
E^*_{\tau,\omega} & = & e^{i\omega\tau} E_{-\tau,-\omega}; \\
E_{\tau,\omega} E_{\tau',\omega'} & = & e^{i\omega'\tau}
E_{\tau+\tau',\omega+\omega'}.
\end{eqnarray}
The result is
\begin{eqnarray}
A_f(\tau,\omega) = &A_{f_0}(\tau,\omega)&
\sum_j e^{i(\omega_j\tau-\omega\tau_j)} \nonumber \\ &+&
\sum_{j \ne k} e^{i(\omega_j\tau_j+\omega_k\tau-\omega
\tau_j-\omega_k\tau_j)}
A_{f_0}(\tau+\tau_k-\tau_j,\omega+\omega_k-\omega_j).
\label{eq:mess}
\end{eqnarray}
The first term represents the main lobe, and is peaked at
the origin as dictated by~(\ref{eq:origin}). The second term
represents the sum of the sidelobes. These sidelobes are located
at the {\em differences} of the original time and frequency
shifts; i.e., whenever
${(\tau,\omega)=(\tau_j-\tau_k,\omega_j-\omega_k)}$. The idea is
to assure that these sidelobes do not reinforce one another so
that the ambiguity function $A_f(\tau,\omega)$ is, in effect,
sharply peaked. This is achieved by choosing the time and
frequency shifts $(\tau_j,\omega_j)$ so as to minimize the overlap
between the sidelobes. In other words, we wish to choose these
coordinates in in such a way as to maximize the {\em minimum
difference of differences}.\footnote{The maximum allowable values
of $\tau_j$ and $\omega_j$ are determined by the constraint that
the signal be physically realizable.} This is precisely our
definition of {\em irregularity}. In accepting this discussion as
our motivation for studying $1$-dimensional irregularity, we
ignore two important issues --- the effect of the phase factors in
equation~(\ref{eq:mess}) and the relationship between the
$1$-dimensional and $2$-dimensional problems. These questions are
addressed in the companion paper~\cite{AG}.
The {\em Golomb Ruler Problem}, simply stated, is to find the
shortest possible ``ruler'' with~$n$ integral tick marks, which
has the property that the distances measured between each pair of
tick marks are distinct~\cite{HT}. An excellent survey treatment
of this problem is given in reference~\cite{AKD}. More generally,
the problem falls under the study of {\em difference bases}; i.e.,
the representation of a set of numbers by differences of other
numbers~\cite{GSB1}. Golomb rulers and their generalizations are
applicable in numerous and diverse areas of mathematics, physics,
and electrical engineering --- including graph theory, x-ray
crystallography, radar pulse codes, and the efficient layout of
electronic circuits~\cite{GSB1,GSB2}. Despite this applicability,
however, the amount of published literature on the subject is
surprisingly small. Consequently, Golomb rulers seem to be
periodically rediscovered~\cite{HT}, as happened in the case of
the present work. As anyone who has ``discovered'' the first few
Golomb rulers can attest, the problem is intriguing independently
of its potential for application. It is simply stated, easily
explored, and possesses an inherent mathematical
beauty~\cite{AKD}.
Even from the qualitative definitions given above, it is clear
that maximizing irregularity and finding Golomb rulers are closely
related problems. This work explores the relationship between
these two problems in detail. In the process of the exploration,
it will become clear that Golomb rulers are an important tool for
studying the continuous irregularity function. On the other hand,
one may also regard the study of irregularity as a continuous
analogue of the Golomb Ruler Problem. In this spirit, we postulate
that the results developed herein will stimulate further progress
in the search for new Golomb rulers.
We conclude this introduction by providing a road map through
the rather lengthy discourse which is to follow. In
Section~\ref{se:irreg}, we formally define the $N$-point
irregularity function in one dimension, discuss its symmetries and
other structural properties, and explicitly compute it for the
cases $N=1$ and $N=2$. It will become evident that, for larger
values of~$N$, an alternative approach to studying irregularity
is needed. With this in mind, in Section~\ref{se:biject}, we
formally map the study of the continuous irregularity function
onto the study of integral ``difference triangles'', such as are
used in studying Golomb rulers. In Section~\ref{se:PNP}, we
restate the Golomb Ruler Problem in terminology suitable for the
subsequent analysis, and conjecture that maximizing irregularity
and finding Golomb rulers are actually equivalent problems. We
then turn our attention to interpreting and proving this
equivalence conjecture. Section~\ref{se:globmax} details exactly
what we mean by saying that maximizing irregularity and finding
Golomb rulers are equivalent problems. In Section~\ref{se:indep},
we digress in order to study some properties of ``difference
triangles'' which will be needed in the subsequent analysis.
Sections~\ref{se:suplocmax} and~\ref{se:convex} are the
focal point of the paper. Here, we develop the theory of local
maxima of the irregularity function by using various ideas from
convex analysis and the theory of integer linear programming. This
will allow us to see under exactly which situations the two
problems are equivalent or almost equivalent. This technical
material is followed, in Section~\ref{se:examples}, by two
illustrative examples.
In Section~\ref{se:recur}, we study a recursion relation
obeyed by the irregularity function and note its consequences for
both the continuous and discrete problems. Finally, for
completeness, Section~\ref{se:ubvga} discusses some simple bounds
and algorithms closely related to the Golomb Ruler Problem. This
section is important primarily in the application of irregularity
to constructing sharply peaked ambiguity functions, as discussed
in reference~\cite{AKD}.
\end{section}
\begin{section}{Irregularity in One Dimension}
\reset
\begin{subsection}{Definition and Symmetries}
Motivated by the preceding discussion and following
Grossmann~\cite{AG}, we begin by attaching a precise definition to
the intuitive concept of {\em irregularity}. The basic idea is to
place $N$ points on a line in such a way as to maximize the
minimum difference of differences. Clearly this problem can only
have a solution if the points are confined to a bounded interval;
therefore, we proceed as follows. Let $x \in [0,1]^N$ and put
$x_0=0$ and $x_{N+1}=1$. We wish to consider the set of
differences between any two distinct components of $x$ or
endpoints, and enumerate the set of functions measuring the
difference between any two distinct elements of this set; i.e.,
the set of functions measuring the difference of differences. This
set of functions is simply
\begin{equation}
f_{i,j,k,l}(x) \equiv \Big| |x_i-x_j|-|x_k-x_l| \Big|;\qquad
i \neq j,\ k \neq l,\ (i,j) \neq (k,l);
\label{eq:f_ijkl}
\end{equation}
where $0 \le i,j,k,l \le N+1$. Intuitively, one would expect
the {\em irregularity} of a distribution of points to be large
provided that none of the functions defined by
equation~(\ref{eq:f_ijkl}) is too small. Accordingly, the
$N$-point irregularity function $F_N(x)$ is defined to measure the
worst case scenario; i.e.,
\begin{equation}
F_N(x) \equiv \min f_{i,j,k,l}(x),
\label{eq:F_N}
\end{equation}
the minimum being taken over the set of all functions
$f_{i,j,k,l}(x)$ in equation~(\ref{eq:f_ijkl}). The $N$-point
irregularity function $F_N(x)$ is therefore a continuous
piecewise-linear function on the $N$-dimensional hypercube. The
fundamental problem which is to be addressed is to maximize
$F_N(x)$. We state this problem formally as
\begin{problem}
For a given $N$, find all global maxima of the $N$-point
irregularity function $F_N(x)$.
\label{pr:max_F}
\end{problem}
It will be seen that what makes this problem interesting
and nontrivial is the
extremely rapid rate at which the number of local maxima
of $F_N(x)$ grows with $N$.
The $N$-point irregularity function has two simple symmetries.
First, the definition of $F_N(x)$ is manifestly symmetric under
the interchange of any two components of $x$. This invariance will
be referred to as the {\em permutation symmetry}. In light of this
symmetry, it is sufficient to study the behavior of $F_N(x)$ on
the restricted domain
\begin{equation}
\Big\{ x \in [0,1]^N \ \Big|\ x_1 \le \ldots \le x_N \Big\}.
\end{equation}
This defines an $N$-dimensional simplex which will be called the
{\em ordered-$x$ simplex.}
Secondly, it is intuitively obvious that the ``mirror image''
of a distribution of points should have the same irregularity as
the distribution itself. In order to make this more precise, for
any point $x$ in the ordered-$x$ simplex define $x^*$ by
\begin{equation}
(x_1,\ \ldots,\ x_N)^* \equiv (1-x_N,\ \ldots,\ 1-x_1).
\end{equation}
It is then easy to see that $x^*$ is also in the ordered-$x$
simplex and that $F_N(x)=F_N(x^*)$. We will call $x^*$ the {\em
conjugate} of $x$ (since, for example, $x^{**} = x$) and the
associated invariance the {\em conjugate symmetry}. If ${x_1 \le
1-x_N}$ then trivially ${x^*_1 \ge 1-x^*_N}$, thus the conjugate
symmetry can be eliminated by enforcing the former inequality. It
is therefore sufficient to study the behavior of $F_N(x)$ on the
additionally restricted domain
\begin{equation}
\Big\{ x \in [0,1]^N \ \Big|\ x_1 \le \ldots \le x_N \le 1 -
x_1 \Big\}.
\end{equation}
This is again an $N$-dimensional simplex and will be referred
to as the {\em conjugate-free} ordered-$x$ simplex. The full
$N$-dimensional hypercube is composed of $2 \cdot N!$ copies of
this simplex, on each of which $F_N(x)$ exhibits the exact same
behavior.
\end{subsection}
\begin{subsection}{Counting Component Functions}
Having restricted the domain of $F_N(x)$ as much as possible,
it is natural to ask how many of the component functions
$f_{i,j,k,l}(x)$ actually contribute to $F_N(x)$ on the resulting
simplexes. In other words, we wish to enumerate a minimal set of
functions $f_{i,j,k,l}(x)$ which are sufficient to construct
$F_N(x)$. An obvious practical benefit of this enumeration is that
it will allow one to calculate $F_N(x)$ efficiently. In the
present section, this problem will be solved somewhat
heuristically (but nonetheless correctly). The justification for
the assertions made herein will be a consequence of the analysis
contained in subsequent sections.
The number of component functions which contribute to $F_N(x)$
can be counted by using elementary combinatorics together with the
following two observations, which are direct consequences of
equation~(\ref{eq:F_N}). Firstly, if a component function is
dominated by some other component function on the entire domain of
consideration, the dominating function certainly does not
contribute to $F_N(x)$. Secondly, if a particular component
function vanishes on some subset of the domain of consideration,
then (roughly speaking) this component function determines
$F_N(x)$ near these zero sets. With these two observations in
mind, we first consider the ordered-$x$ simplex. On this domain,
the set of functions defined by equation~(\ref{eq:f_ijkl}) reduces
immediately to
\begin{equation}
f_{i,j,k,l}(x) = |x_i-x_j-x_k+x_l|;\qquad
i > j,\ k > l,\ (i,j) \neq (k,l).
\label{eq:f_ijkl_ord}
\end{equation}
There are then three mutually exclusive and exhaustive
possibilities.
The first possibility is that some component of $x$ inside
the absolute value in equation~(\ref{eq:f_ijkl_ord}) is repeated
with the opposite sign. This gives rise to $\left( {N+2} \atop 2
\right)$ distinct component functions corresponding to the choice
of the remaining two points. However, by the first observation
above, the minimum in equation~(\ref{eq:F_N}) can only be attained
by one of the $N+1$ elementary differences
\begin{equation}
x_i-x_{i-1},\qquad
1 \le i \le N+1.
\label{eq:type_I}
\end{equation}
These $N+1$ component functions are significant in that setting
each one to zero determines a {\em facet}~\cite{AS} of the
ordered-$x$ simplex. This means that the $N$-point irregularity
function $F_N(x)$ vanishes on the boundary of the ordered-$x$
simplex, which in turn implies (by the second observation above)
that sufficiently close to one of the facets, the minimum in
equation~(\ref{eq:F_N}) is determined by the corresponding
component function~(\ref{eq:type_I}).
The second possibility is that some component of $x$ inside the
absolute value in equation~(\ref{eq:f_ijkl_ord}) is repeated with
the same sign. This gives rise to $\left( {N+2} \atop 3 \right)$
distinct component functions which can be enumerated as
\begin{equation}
|x_i-2 x_j+x_l|,\qquad
0 \le l < j < i \le N+1.
\label{eq:type_II}
\end{equation}
It is not difficult to see that the zero set of each of these
component functions intersects the interior of the ordered-$x$
simplex; and therefore, each function contributes to $F_N(x)$.
The third and final possibility is that all four components
of $x$ inside the absolute value in equation~(\ref{eq:f_ijkl_ord})
are distinct. This gives rise to $\left( {N+2} \atop 4 \right)$
distinct component functions which can be enumerated as
\begin{equation}
|x_i-x_j-x_k+x_l|,\qquad
0 \le l < k < j < i \le N+1.
\label{eq:type_III}
\end{equation}
As before (by the second observation above), each of these
functions must contribute to $F_N(x)$. The third possibility also
forces one to consider component functions of the form
\begin{equation}
|x_i-x_j+x_k-x_l|,\qquad
0 \le l < k < j < i \le N+1.
\end{equation}
However,
\begin{eqnarray}
|x_i-x_j+x_k-x_l| & = & |x_i-x_j|+|x_k-x_l| \nonumber \\
& \ge & \Big| |x_i-x_j|-|x_k-x_l| \Big|
\nonumber \\
& = & |x_i-x_j-x_k+x_l|;
\end{eqnarray}
therefore, the first observation implies that these functions
cannot contribute to $F_N(x)$.
Summarizing, in addition to the $N+1$ ``facet functions'' given
by~(\ref{eq:type_I}), there are
\begin{equation}
\left( {N+2} \atop 3 \right) + \left( {N+2} \atop 4 \right) =
\left( {N+3} \atop 4 \right)
\label{eq:ccf}
\end{equation}
component functions given by equations~(\ref{eq:type_II})
and~(\ref{eq:type_III}) which contribute to $F_N(x)$ on the
ordered-$x$ simplex. With this in mind, one can now ask how this
set of component functions is further reduced when one restricts
$x$ to the {\em conjugate-free} ordered-$x$ simplex; i.e., when
the condition $x_1 \le 1 - x_N$ is enforced. In this case,
\begin{equation}
|1-x_N-x_1| = 1-x_N-x_1 \le 1-x_N,
\end{equation}
which means that $|1-x_N-x_1|$
(given by equation~(\ref{eq:type_III}) with $i=N+1$, $j=N$, $k=1$,
and $l=0$) becomes a facet function replacing $1-x_N$ (given by
equation~(\ref{eq:type_I}) with $i=N+1$), thus reducing the total
number of component functions by one. This implies that $F_N(x)$
vanishes on the boundary of the conjugate-free ordered-$x$ simplex
as well. In addition, we have
\begin{equation}
0 \le 1-x_N-x_1 \le 1-x_j-x_1 = |1-x_j-x_1|,\qquad
1 \le j \le N-1;
\end{equation}
which results in a further reduction of $N-1$ component
functions, making the total reduction $N$ relative to the previous
count. Each of the remaining component functions has a zero set
which intersects the interior of the conjugate-free ordered-$x$
simplex; and therefore, each contributes to $F_N(x)$ on this
domain.
\label{se:ccf}
\end{subsection}
\begin{subsection}{The Cases $N=1$ and $N=2$}
The concepts and terminology presented in the previous section
will now be elucidated. First, the simplest two cases, $N=1$ and
$N=2$, will be treated more or less completely. Secondly, the
cases $N=3$ and $N=6$ will be briefly examined in order to
illustrate how rapidly the complexity of the problem increases
with $N$. Again, the present treatment is heuristic and intuitive;
the more formal treatment is presented in the following
sections.
We begin with the case $N=1$. As $x$ has only one component,
the ordered-$x$ simplex is the entire interval $[0,1]$. According
to the arguments in the preceding section, there are $N+1=2$ facet
functions and $\left( {N+3} \atop 4 \right)=1$ additional
component function which contribute to $F_1(x)$. These are easily
determined from equations~(\ref{eq:type_I}) and~(\ref{eq:type_II})
so that the $1$-point irregularity function is just
\begin{equation}
F_1(x) = \min\left\{
\begin{array}{l}
x \\
1-x \\
|1-2x|
\end{array}
\right\}.
\end{equation}
The graph of this function is shown in Figure~\ref{fi:F_1}.
\begin{figure}[tb]
\setlength{\unitlength}{1.0cm}
\begin{picture}(15.0,10.0)(-3.5,-1.0)
\put(0.0,0.0){\line(1,1){2.66667}}
\put(2.66667,2.66667){\line(1,-2){1.33333}}
\put(4.0,0.0){\line(1,2){1.33333}}
\put(5.33333,2.66667){\line(1,-1){2.66667}}
\put(0.0,0.0){\line(1,0){8.0}}
\put(8.0,0.0){\line(0,1){8.0}}
\put(8.0,8.0){\line(-1,0){8.0}}
\put(0.0,8.0){\line(0,-1){8.0}}
\put(0.0,0.0){\line(0,-1){0.15}}
\put(2.66667,0.0){\line(0,-1){0.15}}
\put(5.33333,0.0){\line(0,-1){0.15}}
\put(8.0,0.0){\line(0,-1){0.15}}
\put(0.0,0.0){\line(-1,0){0.15}}
\put(0.0,2.66667){\line(-1,0){0.15}}
\put(0.0,5.33333){\line(-1,0){0.15}}
\put(0.0,8.0){\line(-1,0){0.15}}
\put(-0.1,-0.50){$0$}
\put(2.41667,-0.50){$1/3$}
\put(5.08333,-0.50){$2/3$}
\put(7.9,-0.50){$1$}
\put(-0.45,-0.1){$0$}
\put(-0.80,2.56667){$1/3$}
\put(-0.80,5.23333){$2/3$}
\put(-0.45,7.9){$1$}
\put(3.9,-0.60){$x$}
\put(-1.30,3.9){$F_1(x)$}
\end{picture}
\caption{$N=1$ Irregularity Function}
\label{fi:F_1}
\end{figure}
The three points where $F_1(x)=0$ (two of which determine
the facets of the ordered-$x$ simplex) are just the zeros of the
three component functions. It is trivial to show (and evident from
Figure~\ref{fi:F_1}) that there are two solutions to
Problem~\ref{pr:max_F}: ${x=1/3}$ or ${x=2/3}$. These two
solutions are conjugates of one another. The conjugate-free
ordered-$x$ simplex is obtained by enforcing the condition ${x \le
1-x}$; i.e., ${x \le 1/2}$. In this interval, the irregularity
function is simply
\begin{equation}
F_1(x) = \min\left\{
\begin{array}{l}
x \\
1-2x
\end{array}
\right\}
\end{equation}
and the solution to Problem~\ref{pr:max_F} is unique.
For $N=2$, the irregularity function starts to become
interesting; the graph of $F_2(x)$ on $[0,1] \times [0,1]$ is
shown in Figure~\ref{fi:F_2}.
\begin{figure}[tb]
\setlength{\unitlength}{1.0cm}
\begin{picture}(15.0,10.0)(-3.5,-1.0)
\put(-1.13,-2.0){
\epsfxsize=10.0cm
\epsffile{n2.eps}
}
\put(0.0,0.0){\line(1,0){8.0}}
\put(8.0,0.0){\line(0,1){8.0}}
\put(8.0,8.0){\line(-1,0){8.0}}
\put(0.0,8.0){\line(0,-1){8.0}}
\put(0.0,0.0){\line(0,-1){0.15}}
\put(8.0,0.0){\line(0,-1){0.15}}
\put(0.0,0.0){\line(-1,0){0.15}}
\put(0.0,8.0){\line(-1,0){0.15}}
\put(-0.1,-0.50){$0$}
\put(7.9,-0.50){$1$}
\put(-0.45,-0.1){$0$}
\put(-0.45,7.9){$1$}
\put(3.9,-0.60){$x_1$}
\put(-0.80,3.9){$x_2$}
\end{picture}
\caption{$N=2$ Irregularity Function}
\label{fi:F_2}
\end{figure}
The ordered-$x$ simplex is the triangular region
${0 \le x_1 \le x_2 \le 1}$.
According to the arguments in the preceding section,
there are $N+1=3$ facet functions and $\left( {N+3} \atop 4
\right)=5$ additional component function which contribute to
$F_2(x)$ on the ordered-$x$ simplex. By using
equations~(\ref{eq:type_I}), (\ref{eq:type_II}),
and~(\ref{eq:type_III}) to determine these functions, the
$2$-point irregularity function can be written as
\begin{equation}
F_2(x) = \min\left\{
\begin{array}{l}
x_1 \\
x_2-x_1 \\
1-x_2 \\
|x_2-2x_1| \\
|1-2x_1| \\
|1-2x_2| \\
|1-2x_2+x_1| \\
|1-x_2-x_1|
\end{array}
\right\}.
\end{equation}
The zero sets of the first three component functions
(those with no absolute-value sign) are just the three boundary
lines of the ordered-$x$ simplex. The zero sets of the remaining
five component functions coincide with the five white lines which
can be seen intersecting the interior of the ordered-$x$ simplex
in Figure~\ref{fi:F_2}. The conjugate-free ordered-$x$ simplex is
the lower half of the ordered-$x$ simplex; i.e., the triangular
region ${0 \le x_1 \le x_2 \le 1-x_1}$. According to the above
analysis, $F_2(x)$ restricted to this domain simplifies to
\begin{equation}
F_2(x) = \min\left\{
\begin{array}{l}
x_1 \\
x_2-x_1 \\
1-x_2-x_1 \\
|x_2-2x_1| \\
|1-2x_2| \\
|1-2x_2+x_1|
\end{array}
\right\}.
\end{equation}
As in the previous case, the zero set of each of these
component functions is a line --- which either determines a
boundary or intersects the interior of the simplex under
consideration. Again, this correspondence can easily be seen from
Figure~\ref{fi:F_2}. By using this minimal set of six component
functions (and with the help of Figure~\ref{fi:F_2}), the
existence of five local maxima of $F_2(x)$ in the conjugate-free
ordered-$x$ simplex can be verified and their values can be
calculated and compared. The largest of these (determined by the
intersection of $x_1$, $1-x_2-x_1$, and $-1+2x_2-x_1$) occurs at
$x=(1/6,2/3)$ where the irregularity function takes on a value of
$1/6$. This is the solution to Problem~\ref{pr:max_F} for the case
$N=2$. Like the case $N=1$, the solution is unique on the
conjugate-free ordered-$x$ simplex.
For $N \ge 3$, the brute-force procedure used above for
solving Problem~\ref{pr:max_F} is no longer practical. A slice of
the graph of $F_3(x)$ with $x_3$ fixed is shown in
Figure~\ref{fi:F_3}.
\begin{figure}[tb]
\setlength{\unitlength}{1.0cm}
\begin{picture}(15.0,10.0)(-3.5,-1.0)
\put(-1.13,-2.0){
\epsfxsize=10.0cm
\epsffile{n3.eps}
%\special{illustration n3.eps}
}
\put(0.0,0.0){\line(1,0){8.0}}
\put(8.0,0.0){\line(0,1){8.0}}
\put(8.0,8.0){\line(-1,0){8.0}}
\put(0.0,8.0){\line(0,-1){8.0}}
\put(0.0,0.0){\line(0,-1){0.15}}
\put(8.0,0.0){\line(0,-1){0.15}}
\put(0.0,0.0){\line(-1,0){0.15}}
\put(0.0,8.0){\line(-1,0){0.15}}
\put(-0.1,-0.50){$0$}
\put(7.9,-0.50){$1$}
\put(-0.45,-0.1){$0$}
\put(-0.45,7.9){$1$}
\put(3.9,-0.60){$x_1$}
\put(-0.80,3.9){$x_2$}
\put(8.5,4.8){$x_3=9/11$}
\end{picture}
\caption{$N=3$ Irregularity Function}
\label{fi:F_3}
\end{figure}
The value of $x_3$ was chosen so that four global maxima
are visible. We here state without justification that, within the
conjugate-free ordered-$x$ simplex alone, $F_3(x)$ possesses
sixty-one local maxima and {\em two} distinct global maxima, so
the solution to Problem~\ref{pr:max_F} is no longer unique. These
two global maxima occur at $x=(1/11,4/11,9/11)$ and
$(2/11,7/11,8/11)$ where the irregularity function takes on a
value of $1/11$. The two darkest ``pyramids'' in the region $x_1
\le x_2$ of Figure~\ref{fi:F_3} depict the global maxima occurring
at $x=(1/11,4/11,9/11)$ and $(3/11,4/11,9/11)$, the conjugate of
the second point above. This example illustrates the tremendous
difference in complexity between the $N=2$ and the $N=3$
irregularity functions.
As $N$ continues to increase, the number of local maxima
of the $N$-point irregularity function $F_N(x)$ grows extremely
rapidly. As a final example, a slice of the graph of $F_6(x)$ with
$x_3$, $x_4$, $x_5$, and $x_6$ fixed is shown in
Figure~\ref{fi:F_6}.
\begin{figure}[tb]
\setlength{\unitlength}{1.0cm}
\begin{picture}(15.0,10.0)(-3.5,-1.0)
\put(-1.13,-2.0){
\epsfxsize=10.0cm
\epsffile{n6.eps}
%\special{illustration n6.eps}
}
\put(0.0,0.0){\line(1,0){8.0}}
\put(8.0,0.0){\line(0,1){8.0}}
\put(8.0,8.0){\line(-1,0){8.0}}
\put(0.0,8.0){\line(0,-1){8.0}}
\put(0.0,0.0){\line(0,-1){0.15}}
\put(8.0,0.0){\line(0,-1){0.15}}
\put(0.0,0.0){\line(-1,0){0.15}}
\put(0.0,8.0){\line(-1,0){0.15}}
\put(-0.1,-0.50){$0$}
\put(7.9,-0.50){$1$}
\put(-0.45,-0.1){$0$}
\put(-0.45,7.9){$1$}
\put(3.9,-0.60){$x_1$}
\put(-0.80,3.9){$x_2$}
\put(8.5,4.80){$x_3=9/34$}
\put(8.5,4.20){$x_4=15/34$}
\put(8.5,3.60){$x_5=22/34$}
\put(8.5,3.00){$x_6=32/34$}
\end{picture}
\caption{$N=6$ Irregularity Function}
\label{fi:F_6}
\end{figure}
In this case, Problem~\ref{pr:max_F} again has a unique
solution on the conjugate-free ordered-$x$ simplex (which can be
seen in Figure~\ref{fi:F_6}); however, the number of local maxima
is not yet known.
{}From these examples, the need for an alternative approach
to studying irregularity is evident. This alternative approach is
developed in the remainder of the paper.
\label{se:N1N2}
\end{subsection}
\label{se:irreg}
\end{section}
\begin{section}{The $N$-Triangle Bijection}
\reset
Because $F_N(x)$ is piecewise linear, all local maxima
(as well as all other points at which the behavior of $F_N(x)$ is
``interesting'') occur at the intersection of at least $N+1$
hyperplanes (of dimension $N$). The components of $x$ at all such
points of intersection must be rational, as the coefficient of
each $x_i$ in the equation defining each intersecting hyperplane
can only be $0$, $\pm 1$, or $\pm 2$. More formally, we will see
that the {\em hypograph}~\cite{JS} of $F_N(x)$ is the union of
suitably defined, manifestly rational polyhedra; so that the
points at which the behavior of $F_N(x)$ is ``interesting'' are
precisely the vertices of these polyhedra. Consequently, it is
sufficient to study the behavior of $F_N(x)$ on the {\em rational}
ordered-$x$ simplex, which will be denoted by $X_N$; i.e.,
\begin{equation}
X_N \equiv \Big\{ x \in \IQ^N \ \Big|\ 0 \le x_1 \ldots
\le x_N \le 1 \Big\}.
\label{eq:X_N}
\end{equation}
Suppose $x \in X_N$. There are $\left( {N+2} \atop 2 \right)$
distinct positive differences ${x_i-x_j}$ (including the trivial
difference ${x_{N+1}-x_0=1}$). These are conveniently tabulated in
a triangular format as shown in Figure~\ref{fi:xtri}.
\begin{figure}[tb]
\begin{displaymath}
\begin{array}{llllllll}
x_1 & & & & & & & \\
& x_2 & & & & & \\
x_2 - x_1 & & x_3 & & & & & \\
& x_3 - x_1 & & & & & & \\
x_3 - x_2 & & & & & & & \\
& & & & & & x_N & \\
\vdots & \vdots & \vdots & \cdots & & & & 1 \\
& & & & & & 1 - x_1 & \\
x_{N-1} - x_{N-2} & & & & & & & \\
& x_N - x_{N-2} & & & & & & \\
x_N - x_{N-1} & & 1 - x_{N-2} & & & & & \\
& 1 - x_{N-1} & & & & & & \\
1 - x_N & & & & & & &
\end{array}
\end{displaymath}
\caption{Differences Displayed in Triangular Format}
\label{fi:xtri}
\end{figure}
Note that each entry in the triangle is the sum of adjacent
elementary differences in the first column. For example,
\begin{equation}
x_3 = x_1 + (x_2-x_1) + (x_3-x_2).
\end{equation}
When the differences are displayed in this format, $F_N(x)$
is (by definition) just the minimum positive difference between
any two entries in the triangle. Thus, instead of studying the
behavior of $F_N(x)$ on $X_N$, one can study the properties of
this triangular construction.
We take this idea one step further. As all of the entries
in the triangle of Figure~\ref{fi:xtri} are rational, they can be
normalized to integers by multiplying through by the least common
denominator. Therefore, with proper bookkeeping, it is sufficient
to restrict the study of the above construction to those triangles
with integral entries. Accordingly, we define a space of integral
vectors corresponding to the integer-normalized elementary
differences and denote this space by $P_N$; i.e.,
\begin{equation}
P_N \equiv \Big\{ p \in \Big[\{0\} \cup \IN \Big]^{N+1}
\ \Big|\ p \neq 0
\Big\}.
\end{equation}
If $p \in P_N$, we will call $p$ an {\em N-triangle generator}
or simply a {\em generator}. For a given generator $p$, we define
its {\em $N$-triangle expansion} by
\begin{equation}
p_{i,j} \equiv \sum_{k=i}^j p_k, \qquad 0 \le i \le j \le N.
\label{eq:gal}
\end{equation}
This expansion is shown explicitly in Figure~\ref{fi:ptri}.
\begin{figure}[tb]
\begin{displaymath}
\begin{array}{llllllll}
p_{0,0} & & & & & & & \\
& p_{0,1} & & & & & \\
p_{1,1} & & p_{0,2} & & & & & \\
& p_{1,2} & & & & & & \\
p_{2,2} & & & & & & & \\
& & & & & & p_{0,N-1} & \\
\vdots & \vdots & \vdots & \cdots & & & & p_{0,N} \\
& & & & & & p_{1,N} & \\
p_{N-2,N-2} & & & & & & & \\
& p_{N-2,N-1} & & & & & & \\
p_{N-1,N-1} & & p_{N-2,N} & & & & & \\
& p_{N-1,N} & & & & & & \\
p_{N,N} & & & & & & &
\end{array}
\end{displaymath}
\caption{$N$-triangle expansion of $p$}
\label{fi:ptri}
\end{figure}
Loosely, we will refer to either an $N$-triangle generator
$p$ or its $N$-triangle expansion $p_{i,j}$ as simply an {\em
$N$-triangle}. The addition law~(\ref{eq:gal}) can be written in a
``local'' form provided that $p_{i,j}$ is taken to be zero when $i
> j$, namely
\begin{equation}
p_{i,j}=p_{i,j-1}+p_{i+1,j}-p_{i+1,j-1}, \qquad 0 \le i
< j \le N.
\label{eq:lal}
\end{equation}
This version will sometimes be more convenient.
The correspondence between the spaces $X_N$ and $P_N$ will
be exploited throughout the remainder of the paper, thus it will
now be made explicit. Proceeding formally, we define a mapping
$T:\, X_N \rightarrow P_N$ by
\begin{equation}
p_j = C_x(x_{j+1}-x_j), \qquad 0 \le j \le N;
\label{eq:T}
\end{equation}
where
\begin{equation}
C_x ={\rm LCD}\ (x_1,\ldots,x_N).
\end{equation}
We will call $T$ the {\em $N$-triangle bijection}; the name
will be justified by Theorem~\ref{th:eqth0}. From the definition
of $T$ it follows that, if
$x \in X_N$ and $p = T(x)$, the components of $p$ are relatively
prime. Therefore, in order for $T$ to be surjective, it will be
necessary to regard all $N$-triangles which differ only in
normalization as being equivalent.
\begin{definition}
Let $p,q \in P_N$. Then $p$ and $q$ are said to be
\underline{equivalent} (written as $p \approx q$) whenever
${\exists m,n \in \IN \mid mp=nq}$.
\label{de:equiv}
\end{definition}
With this definition, it is easy to see that there is a
unique member of each
$\approx$-equivalence class whose components are relatively prime.
However, dealing with $\approx$-equivalence classes rather than
these canonical representatives will eliminate the cumbersome task
of checking for relative primeness. This is illustrated by the
following theorem, which is also of fundamental importance.
\begin{theorem}
The mapping $T$ is a bijection from $X_N$ onto
$\approx$-equivalence classes of $P_N$.
\label{th:eqth0}
\end{theorem}
\beginproof
We first prove injectivity. Let $x,y \in X_N$ and suppose $T(x)
\approx T(y)$. According to equation~(\ref{eq:T}) and
Definition~\ref{de:equiv}, this implies that ${\exists m,n \in
\IN}$ such that
\begin{equation}
m C_x(x_{j+1}-x_j) = n C_y(y_{j+1}-y_j), \qquad 0 \le j \le N.
\end{equation}
Summing both sides of this equation for $0 \le j \le i-1$ yields
\begin{equation}
m C_x x_i = n C_y y_i, \qquad 1 \le i \le N+1.
\end{equation}
Putting $i=N+1$ then implies $m C_x = n C_y$, which in turn
implies $x=y$.
The proof of surjectivity is equally simple. Let $p \in P_N$ and
define
\begin{equation}
x_i = p_{0,i-1}\, / \,p_{0,N}, \qquad 1 \le i \le N.
\label{eq:T_inv}
\end{equation}
Note that this defines the same $x \in X_N$ for all members of
a particular equivalence class. Substituting into
equation~(\ref{eq:T}) yields
\begin{equation}
[T(x)]_j = C_x\frac{p_{0,j}-p_{0,j-1}}{p_{0,N}} =
C_x\frac{p_j}{p_{0,N}}.
\end{equation}
Therefore $p_{0,N}\, T(x) = C_x\, p$ which, by
Definition~\ref{de:equiv}, implies $T(x) \approx p$. Both parts of
the proof make use of the fact that equation~(\ref{eq:T_inv}) is
an explicit formula for the mapping $T^{-1}:\, P_N \rightarrow
X_N$.
\endproof
We remark that if $x^*$ is the conjugate of $x$ and
${p^* = T(x^*)}$ then
\begin{equation}
p^*_{i,j}=p_{N-j,N-i}
\end{equation}
so that a given $N$-triangle can be regarded as representing
both $x$ and $x^*$.
Theorem~\ref{th:eqth0} allows one to study subsets of $X_N$
on which $F_N(x)$ possesses some property of interest by studying
the corresponding subsets of $P_N$. With Problem~\ref{pr:max_F} in
mind, we define the following subsets of $X_N$:
\begin{eqnarray}
X'_N & \equiv & \Big\{ x \in X_N \ \Big|\ F_N(x) > 0 \Big\}
\\
X''_N & \equiv & \Big\{ x \in X_N \ \Big|\ x {\rm\ is\ a\
local\ maximum\
of\ } F_N(x) \Big\} \\
X'''_N & \equiv & \Big\{ x \in X_N \ \Big|\ x {\rm\ is\ a\
global\ maximum\
of\ } F_N(x) \Big\}
\end{eqnarray}
and remark that $X_N \supset X'_N \supset X''_N \supset X'''_N$.
We then seek a concise description of the image of each of these
subsets under the $N$-triangle bijection $T$. The first of these,
as given by the following definitions and theorem, is trivial.
\begin{definition}
Let $p \in P_N$. Then $p$ is said to be \underline{Good} whenever
\begin{displaymath}
p_{i,j}=p_{k,l} \Longleftrightarrow (i,j)=(k,l); \qquad \forall
i,j,k,l.
\end{displaymath}
\end{definition}
In other words, $p$ is Good if and only if all of the elements
in its $N$-triangle expansion are distinct. We capitalize ``Good''
in order to distinguish the technical meaning from the everyday
usage, and will use this convention with other adjectives as well.
Define
\begin{equation}
P'_N \equiv \Big\{ p \in P_N \ \Big|\ p {\rm\ is\ Good} \Big\}.
\end{equation}
We then have the following theorem.
\begin{theorem}
The mapping $T$ restricted to $X'_N$ is a bijection from $X'_N$
onto $\approx$-equivalence classes of $P'_N$.
\label{th:eqthI}
\end{theorem}
\beginproof
As previously mentioned, $F_N(x)$ is (by definition) just the
minimum positive difference between any two entries in the
triangle of Figure~\ref{fi:xtri}. Thus $F_N(x)>0$ if and only if
all of these entries are distinct. On the other hand, $p=T(x)$ is
Good if and only if all of the entries in its $N$-triangle
expansion (shown in Figure~\ref{fi:ptri}) are distinct. Since
these two triangles differ only in normalization, the theorem
follows immediately. \endproof This theorem may be abbreviated as
$T(X'_N) \approx P'_N$ while keeping in mind that injectivity is
inherited from the injectivity of $T$ on the larger domain $X_N$.
In the following sections, statements similar to
Theorem~\ref{th:eqthI} will be abbreviated in this way.
\label{se:biject}
\end{section}
\begin{section}{The Perfect $N$-Triangle Problem}
\reset
Our primary objective is to solve Problem~\ref{pr:max_F}. In
this section, we propose (without formal justification) a solution
to this problem and examine some of its consequences. Beginning in
the next section, we consider the issues involved in actually
proving that our solution is valid. As a by-product of these
considerations, we will gain a rather detailed understanding of
the irregularity function $F_N(x)$.
In light of Theorem~\ref{th:eqth0}, solving Problem~\ref{pr:max_F}
is equivalent to calculating $T(X'''_N)$ as a subset of $P_N$.
Since
${X'''_N \subset X'_N}$, Theorem~\ref{th:eqthI} implies that
$T(X'''_N)$ should actually be a subset of the class of Good
$N$-triangles $P'_N$.
Let $p \in P_N$ and $x = T^{-1}(p)$. With reference to the
discussion following equation~(\ref{eq:X_N}), note that $F_N(x)$
can be calculated by first dividing each element of the
$N$-triangle by $p_{0,N}$, and then calculating the minimum
positive difference between any two entries in the resulting
triangular array. This array is just the differences $x_i-x_j$
displayed in triangular format, as shown in Figure~\ref{fi:xtri}.
Evidently, the $N$-triangle element~$p_{0,N}$ is of particular
importance; therefore, for any $p \in P_N$, we define its {\em
trace} to be
\begin{equation}
\trc p \equiv \sum_{k=0}^N p_k\ (= p_{0,N}).
\end{equation}
The terminology is appropriate, since $\trc p$ is the sum of
the ``diagonal'' ($i=j$) elements of the $N$-triangle
expansion~$p_{i,j}$. If $p$ is Good then, loosely speaking, the
smaller $\trc p$ is, the larger $F_N(x)$ will be. It is therefore
natural to ask how small of a trace can be attained subject to the
constraint that $p$ must be Good. We will denote this minimal
value of the trace by $D_N$, and those Good $N$-triangles which
satisfy $\trc p = D_N$ will be called {\em Perfect}
$N$-triangles. We formalize this concept with the following
definition.
\begin{definition}
Let $p \in P'_N$. Then $p$ is said to be \underline{Perfect}
whenever
\begin{displaymath}
\trc p \le \trc q, \qquad \forall q \in P'_N. \end{displaymath}
\label{de:perf}
\end{definition}
Thus $D_N$ is the common trace of all Perfect $N$-triangles.
Define
\begin{equation}
P'''_N \equiv \Big\{ p \in P_N \ \Big|\ p {\rm\ is\ Perfect}
\Big\}.
\label{eq:P'''_N}
\end{equation}
As the number of partitions of $D_N$ is finite, so must be the
cardinality of $P'''_N$. The problem of actually computing the
elements of $P'''_N$ will be formally called the Perfect
$N$-Triangle Problem.
\begin{problem}
For a given $N$, find all Perfect $N$-triangles.
\label{pr:PNP}
\end{problem}
In contrast to Problem~\ref{pr:max_F}, this problem is purely
combinatorial. Nevertheless, the main proposition of the present
work is that these two problems are, in fact, equivalent. More
precisely, we propose the following conjecture.
\begin{conjecture}
\begin{displaymath}
T(X'''_N) \approx P'''_N.
\end{displaymath}
\label{co:eqthIII}
\end{conjecture}
This assertion turns out to be trivial for $N=1$ and $N=2$ and
can been proved by brute force for $N=3$ and $N=4$ (see
Appendix~\ref{ap:proof}). The majority of the remainder of this
work is devoted to the development of ideas pertaining to the
proof for arbitrary $N$.
Assume for the moment that Conjecture~\ref{co:eqthIII} is true.
Then Problem~\ref{pr:max_F} is equivalent to the purely
combinatorial Problem~\ref{pr:PNP}. Indeed, given a Perfect
$N$-triangle $p$, one can simply read off the corresponding value
of $x$ (at which $F_N(x)$ attains a global maximum) from its upper
diagonal according to equation~(\ref{eq:T_inv}). The strength of
this statement can be appreciated by considering the first few
values of $N$.
Appendix~\ref{ap:perfects} lists all Perfect $N$-triangles
(modulo conjugacy) for ${N \le 9}$. Even without the assistance of
a computer, this list can be verified for $N=1$, $2$, $3$, $4$,
and perhaps $N=5$. The cases $N=1$ and $N=2$ are quite trivial; it
requires only a few seconds thought to write down a solution to
Problem~\ref{pr:PNP} and verify its uniqueness. This should be
contrasted with the (relatively) complicated analysis of
Section~\ref{se:N1N2}.
For $N=3$, the difference in the amount of work involved is even
more dramatic. It is easy to verify that if the generator $p$ is
any permutation of $\{1,2,3,4\}$, the $N$-triangle is not
Good.\footnote{Clearly, the $1$ cannot be adjacent to the $2$ or
$3$; therefore, the $1$ must be at the end of the generator and
adjacent to the $4$. But then the $N$-triangle expansion contains
two $5$'s.} The next best possibility is a permutation of
$\{1,2,3,5\}$; there are two such permutations (modulo conjugacy)
which yield Perfect $N$-triangles. Thus $F_3(x)$ possesses two
distinct global maxima within the conjugate-free ordered-$x$
simplex, in accordance with the discussion of Figure~\ref{fi:F_3}.
The proof of this fact by direct analysis of the irregularity
function $F_3(x)$ would require determining which hyperplanes
intersect to form each of the $61$ local maxima, calculating each
point of intersection and the corresponding value of $F_3(x)$, and
comparing these values to determine which are the global maxima
--- a formidable task in comparison to the Perfect $N$-triangle
approach.
Problem~\ref{pr:PNP} has been previously studied under the name
of the
{\em Golomb Ruler Problem}~\cite{HT,AKD}; a Golomb ruler with
$N+2$ tick marks is exactly the same thing as a Perfect
$N$-triangle. As of 1985, all Golomb rulers with fewer than~$13$
tick marks ($N \le 11$) were known~\cite{HT,AKD}. Since then, a
few more values of~$N$ have undoubtedly been conquered. Beyond
this, however, the results are only speculative, as the number of
possibilities which need to be checked has essentially collided
with the capabilities of modern computing.
Finding Perfect $N$-triangles (or constructing Golomb rulers)
is {\em not} the emphasis of the present work; rather, we
concentrate on proving the equivalence of Problem~\ref{pr:max_F}
and Problem~\ref{pr:PNP} by exploiting the correspondence between
the continuous and $N$-triangle formulations. For this purpose,
the notation and terminology of $N$-triangles will be maintained.
Some other aspects of the previous work on Golomb rulers will be
mentioned at the point at which they become relevant.
\label{se:PNP}
\end{section}
\begin{section}{Globally Maximal $N$-Triangles}
\reset
In order to understand what is involved in proving
Conjecture~\ref{co:eqthIII}, we must first introduce another
important characteristic of $N$-triangles. Let $p \in P_N$ and $x
= T^{-1}(p)$. Again with reference to the discussion following
equation~(\ref{eq:X_N}), note that $F_N(x)$ can just as well be
calculated by {\em first} calculating the minimum positive
difference between any two entries in the $N$-triangle, and then
dividing by $\trc p$. Accordingly, for any $p \in P_N$, we define
its {\em index} to be
\begin{equation}
\ind p \equiv \min |p_{i,j}-p_{k,l}|, \qquad (i,j) \neq (k,l).
\label{eq:in}
\end{equation}
It follows that
\begin{equation}
F_N(x) = \frac{\ind p}{\trc p}.
\label{eq:funfac}
\end{equation}
This equation is really the fundamental fact underlying the
usefulness of $N$-triangles in studying the continuous
irregularity function $F_N(x)$; it enables all questions about the
latter to be translated into questions about the former. As a
result of this equality, it is natural to call the quantity on the
right-hand side of equation~(\ref{eq:funfac}) the {\em
irregularity} of the $N$-triangle $p$. In the same spirit, we can
use equation~(\ref{eq:funfac}) to define the concept of a {\em
globally maximal} $N$-triangle in such a way that $p$ is globally
maximal if and only if $p \in T(X'''_N)$ (the image of the set of
points at which $F_N(x)$ attains a global maximum).
\begin{definition}
Let $p \in P_N$. Then $p$ is said to be \underline{globally
maximal} whenever
\begin{displaymath}
\frac{\ind p}{\trc p} \ge \frac{\ind q}{\trc q}, \qquad
\forall q \in P_N.
\end{displaymath}
\label{de:gmax}
\end{definition}
This completely characterizes $T(X'''_N)$ as a subset of $P_N$.
As previously remarked, $T(X'''_N)$ is actually a subset of
$P'_N$, the set of Good $N$-triangles. Moreover, $q \in P_N
\setminus P'_N$ if and only if
$\ind q = 0$. Consequently, both occurrences of $P_N$ in
Definition~\ref{de:gmax} can be replaced by $P'_N$ without
changing its meaning.
Conjecture~\ref{co:eqthIII} says that Perfect and globally
maximal $N$-triangles are the same thing, modulo
$\approx$-equivalence. In order to see exactly what this means,
one must compare the two definitions. In doing so, one observes
that, mechanically, Definition~\ref{de:gmax} can be transformed
into Definition~\ref{de:perf} by replacing $P_N$ by $P'_N$ and
both $\ind p$ and $\ind q$ by $1$. Very roughly speaking, this
observation suggests that Conjecture~\ref{co:eqthIII} will be true
if all the ``important'' $N$-triangles have unit index. In order
to make this precise, let $A_N$ denote the class of $N$-triangles
which have unit index; i.e.,
\begin{equation}
A_N \equiv \Big\{ p \in P_N \ \Big|\ \ind p = 1 \Big\}.
\end{equation}
We then seek to understand the set-theoretic relations between
$A_N$, $P'''_N$, and $T(X'''_N)$.
A highly intuitive (but not quite obvious) fact is that
$P'''_N \subset A_N$.
Indeed, a larger value of $\ind p$ should force $\trc p$ to be
larger (this intuition will be justified by Theorem~\ref{th:C_N}).
Therefore, since Perfect $N$-triangles are precisely those Good
$N$-triangles with minimal trace, one would expect their index to
be as small as allowable for Good $N$-triangles.
\begin{theorem}
If $p$ is Perfect then $\ind p = 1$ ($P'''_N \subset A_N$).
\label{th:pi1}
\end{theorem}
\beginproof
Let $p \in P _N$ and suppose $\ind p \ge 2$. This certainly
implies that no element $p_{i,j}$ of the $N$-triangle expansion
can equal $1$. Let $p'$ denote the $N$-triangle obtained by
replacing $p_0$ by $1$. Except when $i=0$, $p'_{i,j}=p_{i,j}$, so
this subset of the elements of the $N$-triangle $p'$ are all
distinct. In addition, when ${j \ge 1}$,
${p'_{0,j}=p'_{0,0}+p'_{1,j}=1+p_{1,j}}$, so these elements are
also distinct. Thus if two elements of the $N$-triangle $p'$ are
identical, they must be of the form ${p'_{k,l}=p'_{0,j}}$ with $j,
k \ge 1$. But this is the same as $p_{k,l}-p_{1,j}=1$, which is
impossible since $\ind p \ge 2$. Therefore $p'$ is Good and $\trc
p' < \trc p$, which implies that $p$ cannot be Perfect.
\endproof
A trivial but important consequence is that
\begin{corollary}
All Perfect $N$-triangles have irregularity $D_N^{-1}$.
\label{co:pi1-1}
\end{corollary}
This corollary, in turn, implies that
\begin{corollary}
If $T(X'''_N) \cap P'''_N \ne \emptyset$ then $P'''_N \subset
T(X'''_N)$.
\label{co:pi1-2}
\end{corollary}
In other words, if one Perfect $N$-triangle is globally maximal
then all must be globally maximal.
By using Theorem~\ref{th:pi1} and comparing
Definitions~\ref{de:perf} and~\ref{de:gmax}, one concludes that
Perfect $N$-triangles have maximal irregularity among all those
$N$-triangles in the class $A_N$. It follows that, in order for
Conjecture~\ref{co:eqthIII} to be true, it is necessary and
sufficient that every globally maximal $N$-triangle be
$\approx$-equivalent to some $N$-triangle in the class $A_N$. This
assertion is proved as part of Theorem~\ref{th:3prop}. However,
one can still partially characterize the relationship between
$P'''_N$ and $T(X'''_N)$ without knowing the relationship between
$A_N$ and $T(X'''_N)$. This is the content of the following
theorem, which is similar to Corollary~\ref{co:pi1-2}, but
stronger.
\begin{theorem}
If $T(X'''_N) \cap A_N \ne \emptyset$ then $P'''_N = T(X'''_N)
\cap A_N$.
\label{th:TAP}
\end{theorem}
\beginproof
Assume $T(X'''_N) \cap A_N \ne \emptyset$ and let
$p \in T(X'''_N) \cap A_N$. Since $p$ is globally maximal and
$\ind p = 1$, Definition~\ref{de:gmax} implies
\begin{equation}
\frac{1}{\trc p} = \frac{\ind p}{\trc p} \ge
\frac{\ind q}{\trc q} \ge \frac{1}{\trc q}; \qquad \forall q
\in P'_N.
\end{equation}
Thus, by Definition~\ref{de:perf}, $p \in P'''_N$. This proves
$P'''_N \supset T(X'''_N) \cap A_N$. Since $p \in T(X'''_N)
\cap P'''_N$, Corollary~\ref{co:pi1-2} implies $P'''_N \subset
T(X'''_N)$. By Theorem~\ref{th:pi1}, $P'''_N \subset A_N$;
therefore,
$P'''_N \subset T(X'''_N) \cap A_N$.
\endproof
Our immediate goal is to use Theorem~\ref{th:TAP} (along with
Theorem~\ref{th:pi1} and its corollaries) to give a less abstract
(but equivalent) formulation of Conjecture~\ref{co:eqthIII}.
First, however, it is necessary to note the consequences of
multiplying an $N$-triangle generator by a positive integer.
\begin{theorem}
Let $q \in P_N$, $k \in \IN$, and $p = k q$. Then $p \in P_N$,
$\ind p = k\, \ind q$, and $\trc p = k\, \trc q$.
\label{th:trivial}
\end{theorem}
\beginproof
If $p = k q$ then $p_{i,j} = k q_{i,j}$ for all $i,j$ satisfying
$0 \le i \le j \le N$; i.e., every element in the $N$-triangle
expansion is multiplied by $k$. All three assertions then follow
trivially.
\endproof
Thus, if $p = k q$ then $p$ and $q$ have the same irregularity.
We now can give two equivalent formulations of
Conjecture~\ref{co:eqthIII}.
\begin{theorem}
The following three propositions are equivalent:
\begin{enumerate}
\item $T(X'''_N) \approx P'''_N$ (Conjecture~\ref{co:eqthIII}).
\item For every $p \in P_N$, $p$ is globally maximal if and only
if $p=k q$, where $k \in \IN$ and $q$ is Perfect.
\item For every $p \in P_N$, if $p$ is locally maximal then $p$
is divisible by $\ind p$.
\end{enumerate}
\label{th:3prop}
\end{theorem}
\beginproof
Propositions~1 and~2 are essentially the same thing written in
different notations. To see this, recall that ${p \approx q}$
means that
${\exists m,n \in \IN \mid mp=nq}$ (Definition~\ref{de:equiv}),
which implies ${m\,\ind p = n\,\ind q}$
(Theorem~\ref{th:trivial}). If $q$ is Perfect then ${\ind q =1}$
(Theorem~\ref{th:pi1}), which implies that $n$ is divisible by
$m$. Let ${k = n/m = \ind p}$. The equivalence of propositions~1
and~2 follows. Proposition~3, in turn, is a direct corollary of
proposition~2. We will complete the proof of the theorem by
arguing that proposition~3 implies proposition~2.
Assume proposition~3 is true and suppose $p$ is globally maximal.
Then $p$ is divisible by $\ind p$, which means precisely that
$p=k q$ with $\ind p = k$ and $\ind q = 1$. By
Theorem~\ref{th:trivial}, $q$ has the same irregularity as $p$,
hence $q$ is globally maximal. Therefore, by Theorem~\ref{th:TAP},
$q$ is Perfect. This proves the forward implication in
proposition~2. On the other hand, Corollary~\ref{co:pi1-1}
together with Theorem~\ref{th:trivial} implies that any multiple
of a Perfect $N$-triangle must have the same irregularity as $q$;
therefore, any multiple of a Perfect $N$-triangle must be globally
maximal. This proves the reverse implication in proposition~2.
\endproof
As a result of this theorem, we will henceforth refer to any or
all of the above propositions as Conjecture~\ref{co:eqthIII}.
In Appendix~\ref{ap:proof}, we will prove
Conjecture~\ref{co:eqthIII} directly for the first few values of
$N$. From the proof, it will become evident that the
generalization of this direct approach to arbitrary $N$ is
difficult or impossible to carry out. Our strategy, then, will be
to approach the proof indirectly by developing the theory of {\em
locally} maximal $N$-triangles (corresponding to local maxima of
the continuous irregularity function). This is the subject of
Section~\ref{se:suplocmax}.
We conclude this section by proving that, for fixed index, the
trace is bounded below (or, for fixed trace, the index is bounded
above). First, define
\begin{equation}
C_N \equiv \left( {N+2} \atop 2 \right) = \frac{(N+2)(N+1)}{2}.
\end{equation}
This quantity plays a fundamental role in the following theorem
and corollaries.
\begin{theorem}
Let $p \in P_N$. Then
\begin{equation}
\trc p \ge \ind p\, C_N.
\end{equation}
\label{th:C_N}
\end{theorem}
\beginproof
Let $p \in P_N$ and put $k = \ind p$. Clearly, the smallest
component of the $N$-triangle generator $p$ must be at least $k$;
otherwise, there will be two $N$-triangle elements which differ by
less than $k$. Similarly, the second smallest component of $p$
must be at least $2k$; otherwise, it will differ from the smallest
component by less than $k$. Continuing in this manner, the largest
component of $p$ must be at least $(N+1)k$. Therefore,
\begin{equation}
\trc p \ge k\sum_{i=1}^{N+1} i = k\, C_N.
\end{equation}
Since $k = \ind p$, the theorem is proved.
\endproof
According to equation~(\ref{eq:funfac}), this theorem provides
a simple upper bound on the continuous irregularity function
$F_N(x)$.
\begin{corollary}
\begin{equation}
F_N(x) \le C_N^{-1}.
\end{equation}
\end{corollary}
On the other hand, if $p$ is Perfect then Theorem~\ref{th:pi1}
and Theorem~\ref{th:C_N} imply
\begin{corollary}
\begin{equation}
D_N \ge C_N.
\end{equation}
\label{co:LB}
\end{corollary}
With reference to Appendix~\ref{ap:perfects}, we remark that
this bound is actually attained for $N=1$ ($D_1=C_1=3$) and
$N=2$
($D_2=C_2=6$). For
${N \ge 3}$, it is not difficult to show that the lower bound
$C_N$ is never attained~\cite{AKD}. In connection with the Golomb
Ruler Problem, much effort has been directed towards improving
this lower bound on $D_N$ for the purpose of making the computer
search for Golomb rulers more efficient~\cite{HT}. These more
sophisticated bounds will not be needed in the present work; the
simple lower bound $C_N$ will be sufficient. The quantity $C_N$
will appear frequently in the following sections because of its
dual significance as both the number of elements in an
$N$-triangle expansion and a lower bound on $D_N$.
\label{se:globmax}
\end{section}
\begin{section}{Independent $N$-Triangle Elements}
\reset
In calculating the index of an $N$-triangle using
equation~(\ref{eq:in}), it is clearly not necessary to consider
every possible choice of two elements. For example, if $i
0}$. This partitioning of $X_N$ can be seen clearly for the
${N=2}$ case of Figure~\ref{fi:F_2}.
It is not difficult to see that, restricted to each of these
regions, $F_N(x)$ is polyhedral; i.e., the corresponding
component of the {\em hypograph} of $F_N(x)$ is a
$(N+1)$-dimensional polyhedron.\footnote{The hypograph of $F_N(x)$
is the set $\{ (x,z) \mid 0 \le z \le F_N(x) \}$.} The polyhedral
components of $X_N$ should not be confused with the corresponding
polyhedral components of the hypograph.
We may now ask how to characterize the polyhedral components of
$X_N$ in the language of $N$-triangles. A moment's reflection
leads one to the conclusion that, if the relative order of any two
$N$-triangle elements is reversed, the component function
corresponding to the difference between those two elements must
pass through a zero somewhere in between the values of $x$
corresponding to the two $N$-triangles. Thus, all $N$-triangles
whose elements have the same relative ordering correspond to
values of $x$ which lie in the same connected component of $X'_N$.
This motivates the following definition.
\begin{definition}
Let $p,q \in P'_N$. Then $p$ and $q$ are said to have the same
\underline{structure} (written as $p \sim q$) whenever
\begin{displaymath}
p_{i,j}>p_{k,l} \Longleftrightarrow q_{i,j}>q_{k,l}; \qquad
\forall i,j,k,l.
\end{displaymath}
\label{de:struct}
\end{definition}
This is also an equivalence relation, but it is weaker than
$\approx$-equivalence; i.e., if $p,q \in P'_N$ then
\begin{equation}
p \approx q \Longrightarrow p \sim q.
\end{equation}
Also note that the concept of structure is only defined for
Good $N$-triangles; therefore, the set of $\sim$-equivalence
classes form a partition of $P'_N$. Definition~\ref{de:struct}
allows us to define a localized analogue of Perfect
$N$-triangles.
\begin{definition}
Let $p \in P'_N$. Then $p$ is said to be \underline{Superb}
whenever
\begin{displaymath}
\trc p \le \trc q, \qquad \forall q \mid q \sim p.
\end{displaymath}
\label{de:superb}
\end{definition}
The adjectives have been chosen so that Perfect $\Longrightarrow$
Superb $\Longrightarrow$ Good, naturally. In analogy with
equation~(\ref{eq:P'''_N}), define
\begin{equation}
P''_N \equiv \Big\{ p \in P_N \ \Big|\ p {\rm\ is\ Superb}
\Big\}
\end{equation}
so that $P'''_N \subset P''_N \subset P'_N \subset P_N$.
Thus far, we have not defined precisely what we mean by a local
maximum of $F_N(x)$, having instead relied on the intuitive or
technical concept. We now remedy this situation by first defining
the concept of a {\em locally maximal} $N$-triangle in analogy
with Definition~\ref{de:gmax}.
\begin{definition}
Let $p \in P'_N$. Then $p$ is said to be \underline{locally
maximal} whenever
\begin{displaymath}
\frac{\ind p}{\trc p} \ge \frac{\ind q}{\trc q},\qquad \forall
q \mid q \sim p.
\end{displaymath}
\label{de:locmax}
\end{definition}
We then say that $F_N(x)$ attains a local maximum at some point
$x$ (i.e., $x \in X''_N$) if and only if $p = T(x)$ is locally
maximal. That this definition agrees with the usual definition of
local maxima follows from the fact that, when restricted to the
corresponding polyhedral subset of $X_N$, $F_N(x)$ is polyhedral
and hence concave. This point will be elucidated in
Section~\ref{se:convex}.
According to Theorem~\ref{th:3prop}, Conjecture~\ref{co:eqthIII}
is true if and only if every globally maximal $N$-triangle is
divisible by its index. It is a much stronger statement to assert
that every {\em locally} maximal $N$-triangle is divisible by its
index. In other words, the property in question arises from the
local maximality of $p$, not the global maximality. If this is
true, then Superb and locally maximal $N$-triangles are related in
the same way as Perfect and globally maximal $N$-triangles. We
conjecture that this is indeed the case.
\begin{conjecture}
\begin{displaymath}
T(X''_N) \approx P''_N
\end{displaymath}
\label{co:eqthII}
\end{conjecture}
Even though this is much stronger than
Conjecture~\ref{co:eqthIII}, by using convex analysis, we will be
able to obtain a much deeper understanding of its content.
To conclude this section, we briefly develop a sort of special
convex analysis for the integral space $P_N$. This is really just
standard convex analysis for the space $X_N$ translated into the
language of $N$-triangles. We exploit this fact in choosing the
terminology, but do not attempt to formalize it until
Section~\ref{se:convex}. In the next section, these convexity
results will be used to prove some basic facts about Superb and
locally maximal $N$-triangles.
Let $p,q \in P_N$ and define the {\em open segment} spanned by
$p$ and $q$ according to
\begin{equation}
(p,q) \equiv \{ r \mid r=mp+nq;\quad m,n \in \IN\}.
\label{eq:Rpq}
\end{equation}
It is trivial fact that $(p,q) \subset P_N$; i.e., with respect
to this definition of ``open segment'', the space $P_N$ is
``convex''. In the same sense, each structure equivalence class is
also convex.
\begin{theorem}
Let $p,q \in P'_N$. Then
\begin{displaymath}
p \sim q \Longrightarrow \forall r \in (p,q),\ r \sim p.
\end{displaymath}
\label{th:eqc}
\end{theorem}
\beginproof
Let $m,n \in \IN$ and put $r = mp+nq$. Suppose $p_{i,j}>p_{k,l}$.
Then since $p \sim q$, $q_{i,j}>q_{k,l}$. Consequently,
${mp_{i,j}+nq_{i,j}>mp_{k,l}+nq_{k,l}}$, or $r_{i,j}>r_{k,l}$. The
same trivial argument applies for ``$<$''; therefore, $r \sim p$.
\endproof
Continuing in the same spirit, we can prove that the index
(viewed as a function on some fixed structure equivalence class)
is a concave function.
\begin{theorem}
Let $p,q \in P'_N$. Then
\begin{displaymath}
p \sim q \Longrightarrow \forall r \in (p,q),\
\ind r \ge m\,\ind p + n\,\ind q.
\end{displaymath}
\label{th:fc}
\end{theorem}
\beginproof
Let $m,n \in \IN$ and put $r = mp+nq$. Define $(p)_k$ to be the
$k^{\rm th}$ smallest element of the $N$-triangle $p$ so that
${(p)_1 < (p)_2 < \cdots < (p)_{C_N}}$. With analogous definitions
for $(q)_k$ and $(r)_k$, Theorem~\ref{th:eqc} implies that ${(r)_k
= m(p)_k+n(q)_k}$. Using this notation, we have
\begin{eqnarray}
\ind p &=& \min_k\{(p)_{k+1} - (p)_k\} \nonumber \\
\ind q &=& \min_k\{(q)_{k+1} - (q)_k\} \nonumber \\
\ind r &=& \min_k\{m[(p)_{k+1} - (p)_k]+n[(q)_{k+1} - (q)_k]\}.
\end{eqnarray}
It follows that ${\ind r \ge m\,\ind p + n\,\ind q}$.
\endproof
Finally, the above two theorems allow us to give an alternative
definition of {\em structure}.
\begin{theorem}
Let $p,q \in P'_N$. Then
\begin{displaymath}
p \sim q \Longleftrightarrow \forall r \in (p,q),\
\ind r > 0.
\end{displaymath}
\label{th:struct}
\end{theorem}
\beginproof
The ``$\Longrightarrow$'' part of the implication follows from
Theorem~\ref{th:fc}. To prove ``$\Longleftarrow$'', suppose $p
\not\sim q$. Then $\exists i,j,k,l \mid p_{i,j} > p_{k,l}$ and
$q_{i,j} < q_{k,l}$. Set $n=p_{i,j}-p_{k,l}$, $m=q_{k,l}-q_{i,j}$,
and put $r = mp+nq$. Then
\begin{eqnarray}
r_{i,j}-r_{k,l} & = & m(p_{i,j}-p_{k,l}) + n(q_{i,j}-q_{k,l})
\nonumber \\
& = & mn - mn = 0.
\end{eqnarray}
So $\ind r = 0$, which completes the proof.
\endproof
\label{se:defconres}
\end{subsection}
\begin{subsection}{The Index Reduction Property}
We will now use the convexity results developed in the previous
section to prove some facts concerning Superb and locally maximal
$N$-triangles. Unlike the convexity results themselves, these
facts do not translate directly into useful statements about the
continuous irregularity function; rather, the results are offered
as heuristic evidence in favor of Conjecture~\ref{co:eqthII}. The
main result is that Superb and locally maximal $N$-triangles both
possess a distinctive property which we will call the {\em index
reduction property}. A few of the intermediate results will also
be of importance.
We first prove a simple lemma which says that if any one
component of an $N$-triangle generator is changed by an amount
$k$, the index cannot change by more than $k$.
\begin{lemma}
Let $p \in P_N$ and let $l$ and $k$ be integers satisfying
$0 \le l \le N$ and $k \le p_l$. Define $q$ by
$q_j=p_j-k\,\delta_{j,l}$ so that $q \in P_N$. Then
\begin{equation}
\ind p -|k| \le \ind q \le \ind p + |k|.
\end{equation}
\label{le:index}
\end{lemma}
\beginproof
For each choice of two elements from the $N$-triangle $q$,
either
\begin{eqnarray}
|q_{i,j}-q_{i',j'}| & = & |p_{i,j}-p_{i',j'}| \nonumber\\
& \ge & \ind p \\
\noalign {\rm or}
|q_{i,j}-q_{i',j'}| & = & |p_{i,j}-p_{i',j'} \pm k|
\nonumber\\
& \ge & |p_{i,j}-p_{i',j'}| - |k|
\nonumber\\
& \ge & \ind p -|k|.
\end{eqnarray}
It follows that $\ind q \ge \ind p - |k|$. Since
$p_j=q_j+k\,\delta_{j,l}$, the same argument can be applied with
the roles of $p$ and $q$ reversed. Therefore, it is also true that
$\ind p \ge \ind q - |k|$, which completes the proof.
\endproof
Of course, changing one component of an $N$-triangle generator
by an amount $k$ will not, in general, preserve the structure of
the $N$-triangle. However, if
$|k|$ is no larger than the index, the structure will be preserved
provided that the perturbed $N$-triangle is Good. Otherwise, the
perturbed $N$-triangle lies on the ``boundary'' of the structure
equivalence class of the original $N$-triangle. Nevertheless,
the conclusion of Theorem~\ref{th:fc} still holds. Basically,
this last assertion is true because of the {\em Accessibility
Lemma for Polyhedra}~\cite{JS}. We prove these assertions as
the following theorem.
\begin{theorem}
Let $p \in P'_N$ and let $l$ and $k$ be integers satisfying
$0 \le l \le N$ and $|k| \le \ind p$. Define $q$ by $q_j=p_j-k\,
\delta_{j,l}$ so that $q \in P_N$. Then:
\begin{enumerate}
\item $\forall r \in (p,q)$, ${\ind r \ge m\,\ind p + n\,\ind q}$.
\item $\ind q > 0 \Longrightarrow q \sim p$.
\end{enumerate}
\label{th:2part}
\end{theorem}
\beginproof
Let $m,n \in \IN$ and put $r = mp+nq$ so that ${r_j = (m+n)\,
p_j - nk\,\delta_{j,l}}$. Applying the previous lemma with the
replacements $q \rightarrow r$, $p \rightarrow (m+n)\, p$, and $k
\rightarrow nk$ yields
\begin{eqnarray}
\ind r & \ge & (m+n)\,\ind p - n|k| \nonumber\\
& = & m\,\ind p + n(\ind p - |k|) \nonumber\\
& \ge & m\,\ind p > 0.
\end{eqnarray}
If $\ind q = 0$ then this proves the first assertion and the
second assertion is vacuous. If $\ind q > 0$ then this result
together with Theorem~\ref{th:struct} implies $q \sim p$, which
proves the second assertion. The first assertion then follows from
Theorem~\ref{th:fc}.
\endproof
As a corollary to Theorem~\ref{th:2part}, we have the following
fundamental result.
\begin{corollary}
If $p$ is Superb then $\ind p = 1$ ($P''_N \subset A_N$).
\label{co:si1}
\end{corollary}
\beginproof
Let $p \in P_N$ and suppose $\ind p \ne 1$. As $P''_N \subset
P'_N$, we may assume $\ind p \ge 2$. With reference to the
notation of Theorem~\ref{th:2part}, define $q$ by putting $k=1$
and choosing any integer $l$ satisfying $0 \le l \le N$. Then
according to Lemma~\ref{le:index}, ${\ind q \ge \ind p - 1 \ge
1}$. Theorem~\ref{th:2part} then implies that $q \sim p$. On the
other hand, ${\trc q =\trc p - 1}$; therefore, $p$ cannot be
Superb.
\endproof
Thus, Corollary~\ref{co:si1} implies Theorem~\ref{th:pi1}.
The complete picture is
\begin{equation}
P'''_N \subset P''_N \subset A_N \subset P'_N \subset P_N.
\end{equation}
It is interesting to note that the above argument is not just
a single proof that Superb $N$-triangles have index equal to
unity, but actually $N+1$ ``linearly independent'' proofs of this
fact --- one corresponding to each choice of generator component.
If some component of an $N$-triangle generator is reduced by
the index, the perturbed $N$-triangle may or may not be Good. If
{\em every} choice of generator component yields an $N$-triangle
which is {\em not} Good, then, roughly speaking, the $N$-triangle
elements are tightly packed together (relative to the index).
Intuitively, we would expect this to be true if the $N$-triangle
is either Superb or locally maximal. We formally define this
property as follows.
\begin{definition}
Let $p \in P'_N$. With reference to the notation of
Theorem~\ref{th:2part}, put ${k=\ind p}$ and suppose that, for
each integer $l$ satisfying $0 \le l \le N$, $\ind q = 0$. We then
say that $p$ has the \underline{index reduction property}.
\end{definition}
All the examples of $N$-triangles in Section~\ref{se:ubvga},
as well as the Perfect $N$-triangles tabulated in
Appendix~\ref{ap:perfects}, have the index reduction property.
More generally, we have the following two theorems.
\begin{theorem}
If $p$ is Superb then $p$ has the index reduction property.
\label{th:supirp}
\end{theorem}
\beginproof
Let $p \in P'_N$ and suppose $p$ does {\em not} have the index
reduction property. As $P''_N \subset A_N$, we may assume $\ind p
= 1$. With reference to the notation of Theorem~\ref{th:2part},
define $q$ by putting $k=1$ and choosing an integer $l$ satisfying
$0 \le l \le N$ which yields $\ind q > 0$. Such an $l$ must exist
since $p$ does not have the index reduction property.
Theorem~\ref{th:2part} then implies that $q \sim p$. On the other
hand, ${\trc q=\trc p - 1}$; therefore, $p$ cannot be Superb.
\endproof
\begin{theorem}
If $p$ is locally maximal then $p$ has the index reduction
property.
\label{th:lmirp}
\end{theorem}
\beginproof
Let $p$ be locally maximal and let $l$ and $k$ be integers
satisfying $0 \le l \le N$ and $1 \le k \le \ind p$. We again rely
on the notation of Theorem~\ref{th:2part}, but regard $l$ as fixed
while making explicit the dependence of $q$ on $k$; i.e., define
$q^k$ by $q^k_j=p_j-k\,\delta_{j,l}$ so that $q^k \in P_N$. We can
now prove the theorem by induction on $k$.
First consider $k=1$. According to Lemma~\ref{le:index},
${\ind q^1 \ge \ind p - 1}$. If ${\ind q^1 =0}$ then it must be
true that ${\ind p=1}$ and we are finished. Otherwise
Theorem~\ref{th:2part} implies that $q^1 \sim p$. In this case, by
using Definition~\ref{de:locmax} and ${\trc q^1 =\trc p - 1}$, the
local maximality of $p$ implies that
\begin{equation}
\ind q^1 \le (1-1/\trc p)\, \ind p < \ind p.
\end{equation}
It follows that ${\ind q^1 = \ind p - 1}$.
We now assume that
\begin{equation}
\ind q^{k-1} = \ind p - (k - 1).
\label{eq:induc}
\end{equation}
According to Lemma~\ref{le:index}, ${\ind q^k \ge \ind p - k}$;
thus, in order to complete the proof by induction, we must show
the reverse inequality. We make use of the simple algebraic fact
\begin{equation}
k q^{k-1} = p + (k-1) q^k.
\end{equation}
According to equation~(\ref{eq:Rpq}), this implies that $k q^{k-1}
\in R(p,q^k)$ (with $m=1$ and $n=k-1$). Theorem~\ref{th:2part}
then implies that
\begin{equation}
k\, \ind q^{k-1} \ge \ind p + (k-1)\, \ind q^k.
\end{equation}
{\em provided that} $k \le \ind p$. By substituting
equation~(\ref{eq:induc}), this is algebraically equivalent to
${\ind q^k \le \ind p - k}$. It follows that ${\ind q^k = \ind
p - k}$, which completes the proof.
\endproof
The reverse implication is not true in either case. In order
to see this, consider the $N$-triangle shown in
Figure~\ref{fi:irp}.
\begin{figure}[htb]
\begin{displaymath}
\begin{array}{rrrr}
1 & & & \\
& 7 & & \\
6 & & 12 & \\
& 11 & & 15 \\
5 & & 14 & \\
& 8 & & \\
3 & & &
\end{array}
\end{displaymath}
\caption{Example of an $N$-triangle with the Index Reduction
Property}
\label{fi:irp}
\end{figure}
It is easy to verify that this $N$-triangle has the index
reduction property; i.e., reducing any of the generators by~$1$
yields an $N$-triangle which is not Good. However, the
$N$-triangle in Figure~\ref{fi:irp} is neither Superb nor locally
maximal, as simultaneously reducing the~$5$ and~$6$ by~$1$ yields
a Good $N$-triangle with the same structure, smaller trace, and
larger irregularity. The reason for this situation is that the
$N$-triangle in Figure~\ref{fi:irp} lacks another crucial property
closely related to Superbness and local maximality --- the {\em
vertex property}. This property will be discussed in
Section~\ref{se:spvp}.
We conclude this section with the following theorem, which
is really a comment on the proof of Theorem~\ref{th:lmirp}. In
effect, it says that proving ${\ind q = \ind p-k}$ by {\em
reverse} induction on $k$ is trivial, even with no special
assumptions on $p$.
\begin{theorem}
Let $p \in P_N$. With reference to the notation of
Theorem~\ref{th:2part}, suppose that for some choice of integers
$l$ and $k$ satisfying ${0 \le l \le N}$ and ${k \le p_l}$, it is
true that ${\ind q = \ind p-k}$. Then
\begin{equation}
\ind q' = \ind p-k',\qquad \forall k' \mid 0 \le k' \le k;
\end{equation}
where $q'$ is defined by $q'_j=p_j-k'\,\delta_{j,l}$.
\end{theorem}
\beginproof
Define $q$ and $q'$ as above and assume ${\ind q = \ind p-k}$.
According to Lemma~\ref{le:index}, we have ${\ind q' \ge \ind p -
k'}$. Assume strict inequality holds. Write $q$ as
${q_j=q'_j-(k-k')\,\delta_{j,l}}$ and apply Lemma~\ref{le:index}
again to yield
\begin{eqnarray}
\ind q & \ge & \ind q'-(k-k') \nonumber\\
& > & (\ind p - k') - (k-k') \nonumber\\
& = & \ind p - k.
\end{eqnarray}
This contradicts the main assumption on $q$; therefore,
${\ind q' = \ind p - k'}$.
\endproof
\end{subsection}
\begin{subsection}{Counting Structure Equivalence Classes}
As previously mentioned, the relation ``$\sim$'' is an
equivalence relation on $P'_N$; therefore, $P'_N$ is the disjoint
union of $\sim$-equivalence classes. In light of
Definition~\ref{de:struct}, the number of $\sim$-equivalence
classes is trivially bounded by the number of permutations of
$C_N$ objects, and therefore finite. We will denote the number of
$\sim$-equivalence classes by $2 S_N$, the factor of two being an
explicit acknowledgement of the conjugate symmetry. Loosely
speaking, $2 S_N$ is the number of ways of ordering the $C_N$
elements of the $N$-triangle subject to the constraint that these
orderings must respect the $N$-triangle addition law. In terms of
the continuous irregularity function $F_N(x)$, $2 S_N$ is the
number of connected components of the disconnected set $X'_N$
(with respect to the Euclidean metric). The closure of each of
these connected components is a polyhedron whose faces are
determined by the intersections of the zero hyperplanes of
$F_N(x)$.
For the case $N=1$, it easy to see that there are only two
possible structures for Good $N$-triangles and that they are
conjugates of one another. For $N=2$, it can likewise be verified
(by brute force) that there are ten. In light of
Theorem~\ref{th:struct}, the values of $2 S_1$ and $2 S_2$ can
also be determined by simply counting the number of polyhedrons
which make up the ordered-$x$ simplex in Figures~\ref{fi:F_1}
and~\ref{fi:F_2}.
For $N \ge 3$, both of the above methods for determining $S_N$
become impractical or impossible. Instead of directly counting
the number of $N$-triangles with distinct structures, we introduce
a class of objects called {\em structure triangles} which will be
easier to count. Intuitively, a structure triangle is just an
ordering of the $C_N$ elements of the $N$-triangle which
``respects the $N$-triangle addition law''. The following
definition formalizes this idea.
\begin{definition}
A \underline{structure triangle} is a bijective mapping
\begin{equation}
s:\{(i,j) \mid 0 \le i \le j \le N\} \rightarrow
\{1,2,\ldots,C_N\}
\end{equation}
which satisfies the following two criteria:
\begin{enumerate}
\item $\forall i,j$ with $0 \le i < j \le N$,
\begin{equation}
s_{i,j}>s_{i,j-1} \qquad {\rm and} \qquad s_{i,j}>s_{i+1,j}.
\end{equation}
\item $\forall i,j,k,l$ with $0 \le i < k \le j < l \le N$,
\begin{equation}
s_{i,j}>s_{k,l} \Longleftrightarrow s_{i,k-1}>s_{j+1,l}.
\end{equation}
\end{enumerate}
\label{de:stri}
\end{definition}
Thus a structure triangle is an object with the same ``data
structure'' as an ordinary $N$-triangle, but it does not
(necessarily) obey the addition law of equation~(\ref{eq:gal}). It
serves only to indicate an admissible ordering of the $C_N$
elements for some Good $N$-triangle. For each Good $N$-triangle
there exists a unique structure triangle satisfying
\begin{equation}
p_{i,j}>p_{k,l} \Longleftrightarrow s_{i,j}>s_{k,l}; \qquad
\forall i,j,k,l.
\label{eq:ps}
\end{equation}
In this situation, we will say that $s$ is the structure
triangle of $p$.
The two criteria in the above definition can be understood
by again referring to Figure~\ref{fi:indep}. First, assuming $p$
is Good, $p_{i,j}$ must be strictly greater than all elements in
region~(2) and strictly less than all elements in region~(3). By
using equation~(\ref{eq:ps}), this condition transforms directly
into an analogous condition on $s_{i,j}$. Moreover, it is easy to
see that this is true if and only if each $s_{i,j}$ (with $i p_{i',j'}}$. Then $p_{i,j}$ and $p_{i',j'}$
are said to be \underline{consecutive} if there are no
other elements of the $N$-triangle expansion of $p$
which fall between them; i.e., there is no $p_{k,l}$
satisfying ${p_{i,j} > p_{k,l} > p_{i',j'}}$.
\label{de:consec}
\end{definition}
Let $s$ be a structure equivalence class of $P'_N$ and consider
the matrix $A_s$ defined as follows. Choose $p$ to be any
representative of $s$. Define the first row of $A_s$ by placing a
$1$ in the column corresponding to the smallest component of the
generator $p$ (which is also necessarily the smallest element in
the $N$-triangle expansion of $p$) and zeros in the remaining
columns. Define the second row of $A_s$ as follows. Let $p_{i,j}$
and $p_{i',j'}$ be the smallest pair of elements satisfying
${p_{i,j} > p_{i',j'}}$ which are {\em both consecutive and
independent}. Place a $1$ in columns $i$ through $j$, a $-1$ in
columns $i'$ through $j'$, and zeros in the remaining columns.
Define the third row of $A_s$ in the same way by considering the
second smallest pair of elements which are both consecutive and
independent. Continue until all such pairs have been exhausted.
The matrix $A_s$ defined by this procedure will be called the
{\em structure matrix} of $p$. For simplicity, we will sometimes
write $A$ instead of $A_s$ when $s$ can be regarded as fixed.
Clearly $A_s$ depends only on the structure equivalence class $s$,
not on the chosen representative $p$. In fact, rather than
applying the above procedure to the $N$-triangle expansion
$p_{i,j}$ of a particular representative of $s$, it can equally
well be applied to the structure triangle $s_{i,j}$ introduced in
Definition~\ref{de:stri} --- the same matrix $A_s$ results.
Returning to the proof of Theorem~\ref{th:strucmat},
equation~(\ref{eq:strucmat}) follows immediately provided that
$A_s$ is taken to be the structure matrix defined according to the
above procedure. In this case, $M$ (the row order of $A_s$) is one
greater than the number of pairs of $N$-triangle elements which
are both consecutive and independent. This number must be at least
$N+1$; otherwise $A_s$ could not even contain sufficient
information for ordering the $N+1$ components of the generator. On
the other hand, $M$ is certainly less than or equal to $C_N$, the
total number of elements in an $N$-triangle expansion. We remark
that, whereas the lower bound on $M$ is attainable (and therefore
optimal), the upper bound is admittedly not very good. This
suggests the question ``What is the maximum number of consecutive
independent pairs that can actually be attained in a Good
$N$-triangle?'' This (presently unknown) number is the best
possible upper bound on $M$.
The primary importance of structure matrices is that they will
allow us to characterize structure equivalence classes as
polyhedra, thereby transforming questions involving $N$-triangles
into standard linear and integer programming terminology. This is
the subject of the following section. Another property which will
also be important is that the structure matrix provides a simple
formula for the index of an $N$-triangle in terms of the
components of the generator, namely
\begin{equation}
\ind p = \min_i\left\{\sum_{j=0}^N A_{i,j}\, p_j\right\}.
\label{eq:altin}
\end{equation}
This formula follows from the definition of the structure matrix,
together with the observation that the index must be attained
between $N$-triangle elements which are both independent and
consecutive. Of course $p$ must be a member of the structure
equivalence class defined by $A$ in order for
equation~(\ref{eq:altin}) to be valid.
Because of their importance, it would be useful to have a simple
procedure for generating the entire set of structure matrices for
fixed $N$. Assuming Conjecture~\ref{co:stri} is true, this can be
done by first generating the set of structure {\em triangles}
according to Definition~\ref{de:stri}, and then applying the above
procedure for generating structure matrices to each one. It would
be more useful, however, to have explicit necessary and sufficient
conditions for determining directly if a given $(0,\pm 1)$-matrix
is a structure matrix. Although some further properties
characterizing structure matrices are noted below, this complete
characterization is still an open question.
\label{se:structmat}
\end{subsection}
\begin{subsection}{Structure Polyhedra and the Vertex Property}
Let $A$ be a structure matrix and define $\wp \subset \IR^{N+1}$
according to
\begin{equation}
\wp = \{p \in \IR^{N+1} \mid A p \ge 1\}.
\label{eq:poly}
\end{equation}
By definition, $\wp$ is a (convex) polyhedron~\cite{AS}.
Polyhedra which are defined by structure matrices according to
equation~(\ref{eq:poly}) will be called {\em structure polyhedra}.
The relationship between structure polyhedra and
equation~(\ref{eq:strucmat}) depends on the simple observation
that, if
${p \in \wp}$ and $p$ is integral, the set of inequalities
${A p \ge 1}$ forces $p$ to belong to $P'_N$. In other words,
\begin{eqnarray}
\{p \in \wp \mid p\ {\rm integral}\}
&=& \{p \in \IR^{N+1} \mid A p \ge 1;\ p\ {\rm integral}\}
\nonumber \\
&=& \{p \in P'_N \mid A p \ge 1\}.
\end{eqnarray}
Hence, the set of all $N$-triangles with a given structure
matrix $A$ is precisely the set of all integral vectors in the
corresponding structure polyhedron~(\ref{eq:poly}).
The following theorem lists some trivial properties of structure
polyhedra using the standard terminology of convex
analysis~\cite{AS,JS}.
\begin{theorem}
Let $\wp$ be a structure polyhedron. Then $\wp$ is nonvacuous,
rational, unbounded, and pointed.
\label{th:wp_prop}
\end {theorem}
\beginproof
Let $A$ denote the structure matrix which defines $\wp$. The
assertion that $\wp$ is nonvacuous follows trivially from the
definition of $A$. The assertion that $\wp$ is rational is a
consequence of the fact that the system of inequalities ${A p \ge
1}$ is rational. (In fact, the only coefficients are $0$ and $\pm
1$.) To see that $\wp$ is unbounded, let ${p \in P'_N}$, ${k \in
\IN}$, and put ${q = k p}$. Clearly ${q \sim p}$. It follows that
$\wp$ is unbounded. Finally, a polyhedron is pointed if and only
if it contains no line~\cite{JS}. If $p \in \wp$ then all of the
components of $p$ must be positive (again by the definition
of~$A$). Therefore $\wp$ cannot contain a line and therefore must
be pointed.
\endproof
A polyhedron is pointed if and only if it has vertices. If a
pointed polyhedron is rational, the coordinates of its vertices
will be rational. Thus a structure polyhedron $\wp$ always
possesses rational vertices. Each rational vertex of $\wp$ is
determined by $N+1$ linearly independent equations from the system
${Ap = 1}$~\cite{AS}. We do not know a priori if these vertices
are necessarily {\em integral}, and hence belong to $P'_N$. This
question will be of fundamental importance. However, even if some
vertex of $\wp$ is not integral, it can be made so by
multiplication by an appropriate integer. Thus all vertices of
$\wp$ are ``represented'' by some $p \in P'_N$. This motivates the
following definition.
\begin{definition}
Let $p \in P'_N$, $k =\ind p$, and $\wp$ be the structure
polyhedron of $p$. If
$p/k$ is a vertex of $\wp$, we say $p$ has the \underline{vertex
property}.
\label{de:vp}
\end{definition}
The use of $k =\ind p$ is justified by equation~(\ref{eq:altin})
and the preceding discussion. Loosely speaking, $p$ has the vertex
property if and only if there are $N+1$ independent occurrences of
the index in the $N$-triangle expansion of $p$. All the
examples of $N$-triangles in Section~\ref{se:ubvga}, as well as
the Perfect $N$-triangles tabulated in Appendix~\ref{ap:perfects},
have the vertex property. In fact, all these $N$-triangles are
actually vertices of structure polyhedra, since all have $\ind p
=1$.
We now seek to establish a connection between $N$-triangles which
have the vertex property and $N$-triangles which are Superb
and/or locally maximal. This is possible because the latter two
properties can be formulated in terms of solutions to certain
integer linear or linear programs~\cite{AS}, respectively. To this
end, we have the following two theorems.
\begin{theorem}
Let $p \in P'_N$ and $A$ be the structure matrix of $p$. Then $p$
is Superb if and only if $p$ is a solution to the integer linear
program
\begin{equation}
\min\left\{ \trc p\ \Big|\ Ap \ge 1;\ p\ {\rm integral}\right\}.
\label{eq:ILP}
\end{equation}
\label{th:ILP}
\end{theorem}
\beginproof
This follows immediately from Definition~\ref{de:superb}.
\endproof
\begin{theorem}
Let $p \in P'_N$ and $A$ be the structure matrix of $p$.
Then $p$ is locally maximal if and only if ${p=k\rho}$, where $k
\in \IN$ and $\rho$ is a rational solution to the linear program
\begin{equation}
\min\left\{\sum_{j=0}^N \rho_j\ \Big|\ A\rho \ge 1\right\}.
\label{eq:LP}
\end{equation}
\label{th:LP}
\end{theorem}
\beginproof
Suppose $p$ is locally maximal and $\eta$ is a rational solution
to the above linear program. Set ${k = \ind p}$, ${\rho = p / k}$,
${l={\rm LCD}(\eta_0,\ldots,\eta_N)}$, and ${q = l\eta}$.
Equation~(\ref{eq:altin}) implies that $Ap \ge k$, hence $A\rho
\ge 1$. Furthermore,
\begin{equation}
\min_i\left\{\sum_j A_{i,j}\, \eta_j\right\}=1,
\end{equation}
since otherwise one could divide through by the minimum difference
thereby reducing the objective function; hence, ${\ind q=l}$. It
follows that
\begin{equation}
\frac{\trc p}{\ind p} = \sum_{j=0}^N \rho_j
\qquad {\rm and} \qquad
\frac{\trc q}{\ind q} = \sum_{j=0}^N \eta_j.
\end{equation}
The fact that $p$ is locally maximal implies that the quantities
in the first equation are less than or equal to the quantities in
the second; whereas, the fact that $\eta$ solves the linear
program implies that the quantities in the second equation are
less than or equal to the quantities in the first. Therefore, all
four quantities are equal, which implies that $q$ is locally
maximal and $\rho$ is a rational solution to the linear program.
\endproof
In this proof, it has been assumed that a rational solution to
the linear program~(\ref{eq:LP}) exists. A comment on this
assumption is in order. Firstly, if a linear function is bounded
below on a nonvacuous polyhedron, the function attains a minimum
on that polyhedron~\cite{JS}. In the linear program~(\ref{eq:LP}),
the objective function is bounded below by $C_N$. Secondly, it
is a fundamental fact of linear programming theory that, if a
solution to a linear program exists, it can be taken to be a
vertex of the underlying polyhedron (provided that the polyhedron
is pointed). Since structure polyhedra are pointed and rational,
it follows that the linear program~(\ref{eq:LP}) possesses a
rational solution.
We can now characterize the relationship between Superb and
locally maximal $N$-triangles more or less completely. The main
point underlying this relationship is that the linear
program~(\ref{eq:LP}) is the {\em LP-relaxation}~\cite{AS} of the
integer linear program~(\ref{eq:ILP}); in other words, it is
exactly the same problem with the integrality constraint removed.
However, the situation is complicated by the fact that we do not
know if the solution to the linear program~(\ref{eq:LP}) is
unique. The best possible scenario is summarized by the following
theorem, which is analogous to Theorem~\ref{th:3prop}.
\begin{theorem}
The following four propositions are equivalent:
\begin{enumerate}
\item $T(X''_N) \approx P''_N$ (Conjecture~\ref{co:eqthII}).
\item For every $p \in P_N$, $p$ is locally maximal if and only
if
$p=k q$, where $k \in \IN$ and $q$ is Superb.
\item For every $p \in P_N$, if $p$ is locally maximal then $p$
is divisible by $\ind p$.
\item For every structure matrix $A$, the solution to the linear
program~(\ref{eq:LP}) is unique and integral.
\end{enumerate}
\label{th:4prop}
\end{theorem}
\beginproof
The proof of the equivalence of the first three propositions is
exactly
parallel to the proof of Theorem~\ref{th:3prop}. We will complete
the proof of the theorem by arguing that proposition~4 implies
proposition~2, and that the negation of proposition~4 implies the
negation of proposition~3.
Assume proposition~4 is true and denote the unique integral
solution to the linear program~(\ref{eq:LP}) by $q$. Then $q$ is
also the unique solution to the integer linear
program~(\ref{eq:ILP}); hence, $q$ is the unique Superb
$N$-triangle with structure matrix $A$. Then, according to
Theorem~\ref{th:LP}, $p$ is locally maximal if and only if $p=k
q$, where $k \in \IN$. This is just proposition~2.
Now assume proposition~4 is false. This means that (for some
structure matrix $A$) the solution to the linear
program~(\ref{eq:LP}) is either non-unique or non-integral. Since
any convex combination of solutions to a linear program must also
be a solution, an entirely integral solution set consisting of
more than one point is impossible. Consequently, we may assume
that there exists a rational non-integral solution to the linear
program~(\ref{eq:LP}). Denote this solution by $\rho$ and choose
$k$ so that ${p=k\rho}$ is integral. By Theorem~\ref{th:LP}, $p$
is locally maximal. On the other hand, ${k = \ind p}$, so $p$ is
not divisible by
$\ind p$. This is the negation of proposition~3.
\endproof
As a result of this theorem, we will henceforth refer to any or
all of the above propositions as Conjecture~\ref{co:eqthII}. As
previously stated, if Conjecture~\ref{co:eqthII} is true then
Conjecture~\ref{co:eqthIII} is also true; i.e.,
Problem~\ref{pr:max_F} is equivalent to Problem~\ref{pr:PNP}, the
Perfect $N$-triangle (Golomb Ruler) Problem. All available
evidence supports this desirable state of affairs. In contrast,
the worst possible scenario is the following alternative to
Conjecture~\ref{co:eqthII}.
\setcounter{alternative}{-1}
\begin{alternative}
For some structure matrix $A$, the linear program~(\ref{eq:LP})
possesses only non-integral solutions.
\end{alternative}
If this were the case, there would be (in general) no
correspondence between Superb and locally maximal $N$-triangles,
regardless of the question of uniqueness. There are many possible
intermediate situations, two of which we briefly discuss.
The first intermediate situation is the following weaker
alternative to Conjecture~\ref{co:eqthII}.
\begin{alternative}
For every structure matrix $A$, there exists an integral solution
to the linear program~(\ref{eq:LP}).
\label{al:int1}
\end{alternative}
Assume for the moment that Alternative~\ref{al:int1} is true and
denote the integral solution by $q$. Then $q$ is also a solution
to the integer linear program~(\ref{eq:ILP}); hence, $q$ is
Superb. If any other Superb $N$-triangles (with the same
structure) exist, they must have the same irregularity as $q$;
therefore, one can again conclude that all Superb $N$-triangles
are locally maximal. However, in order to distinguish
Alternative~\ref{al:int1} from the analogous proposition in
Theorem~\ref{th:4prop}, one may assume that (for some structure
matrix $A$) the linear program~(\ref{eq:LP}) possesses
non-integral solutions as well. In general, there will be no
direct relationship between the Superb $N$-triangles and the
local maxima corresponding to these non-integral solutions.
Consequently, one may conclude that Perfect $N$-triangles are
globally maximal, but there may be other globally maximal
$N$-triangles as well.
A much cleaner situation which does not presume uniqueness is
the following alternative to Conjecture~\ref{co:eqthII}. This
alternative is stronger than Alternative~\ref{al:int1}, but still
weaker than Conjecture~\ref{co:eqthII}.
\begin{alternative}
For every structure matrix $A$, all basic solutions to the linear
program~(\ref{eq:LP}) are integral.\footnote{A basic solution is
a solution which is a vertex of the underlying
polyhedron~\cite{AS}.}
\label{al:int2}
\end{alternative}
Assume for the moment that Alternative~\ref{al:int2} is true and
denote the set of basic solutions by $\{q_i\}$. Then each $q_i$
is also a solution to the integer linear program~(\ref{eq:ILP});
hence, each $q_i$ is Superb. If any other Superb $N$-triangles
(with the same structure) exist, they must have the same
irregularity as the $q_i$'s; therefore, one can again conclude
that all Superb $N$-triangles are locally maximal. Furthermore,
the set $\{q_i\}$ consists of precisely those Superb $N$-triangles
which have the vertex property. The set of all rational solutions
to the linear program~(\ref{eq:LP}) is simply the rational convex
hull of the basic solutions $\{q_i\}$. By using
Definition~\ref{de:equiv} and Theorem~\ref{th:LP}, it is not
difficult to show that $p$ is locally maximal if and only if
\begin{equation}
p \approx \sum_i k_i q_i,
\label{eq:int2}
\end{equation}
where ${k_i}$ is any set of non-negative integers which are not
all zero. This is a rather nice generalization of the analogous
proposition in Theorem~\ref{th:4prop}. Moreover, provided that no
two {\em Perfect} $N$-triangles share the same structure,
Alternative~\ref{al:int2} (like Conjecture~\ref{co:eqthII})
implies Conjecture~\ref{co:eqthIII}. If this is not the case, one
simply forms integral combinations of those Perfect $N$-triangles
which do share the same structure (by using
equation~(\ref{eq:int2})) in order to generate the complete set
of
globally maximal $N$-triangles.
We conclude this section with a brief discussion of four
additional conjectures which are logically interrelated with
Conjecture~\ref{co:eqthII} and its alternatives. These conjectures
are consistent with one another, with Conjecture~\ref{co:eqthII},
and with all available empirical evidence.
First, note that Conjecture~\ref{co:eqthII} implies that there
exists a {\em unique} Superb $N$-triangle corresponding to each
structure. We state this assertion independently as the following
conjecture.
\begin{conjecture}
For each structure matrix $A$, there is a unique Superb
$N$-triangle.
\label{co:supuniq}
\end{conjecture}
The only difference between Conjecture~\ref{co:eqthII} and
Alternative~\ref{al:int2} is with regard to this uniqueness. In
fact, Alternative~\ref{al:int2} together with
Conjecture~\ref{co:supuniq} is equivalent to
Conjecture~\ref{co:eqthII}.
According to Conjecture~\ref{co:eqthII}, the unique Superb
$N$-triangle corresponding to each structure is a vertex of the
structure polyhedron. On the other hand, it has been proved that
Superb $N$-triangles have unit index (Corollary~\ref{co:si1}) and
posses the index reduction property (Theorem~\ref{th:supirp}). We
conjecture that these properties taken together completely
characterize Superb $N$-triangles.
\begin{conjecture}
Suppose $p \in P_N$. Then $p$ is Superb if and only if $p$ has
the vertex property, $p$ has the index reduction property, and
$\ind p = 1$.
\label{co:superb}
\end{conjecture}
By Definition~\ref{de:vp}, if $p$ has the vertex property and
$\ind p = 1$ then $p$ is actually a vertex of the underlying
structure polyhedron. However, even assuming
Conjecture~\ref{co:eqthII}, the fact that $p$ is an integral
vertex of the underlying structure polyhedron is not sufficient
in
itself to make $p$ Superb; i.e., in some cases integral vertices
exist which are not locally maximal (see
Section~\ref{se:examples}).
A simply stated assertion which would guarantee that
Alternative~\ref{al:int2} holds is given by the following
conjecture.
\begin{conjecture}
Every structure polyhedron $\wp$ is an integral polyhedron.
\label{co:spi}
\end{conjecture}
Since structure polyhedra are pointed, a structure polyhedron
$\wp$ is integral if and only if each vertex of $\wp$ is integral.
As remarked above, in some cases integral vertices exist which
are not locally maximal. For this reason,
Alternative~\ref{al:int2} is {\em not} equivalent to
Conjecture~\ref{co:spi} --- the latter assertion is stronger.
Taken together, Conjecture~\ref{co:spi} and
Conjecture~\ref{co:supuniq} imply Conjecture~\ref{co:eqthII}.
Conjecture~\ref{co:spi} is more than just wishful thinking based
on empirical evidence; polyhedra which arise from combinatorial
problems frequently turn out to be integral~\cite{AS}. For
structure polyhedra, the vector on the right-hand side of the
system of inequalities is always the same --- its components are
all equal to one. Thus, whether or not a structure polyhedron is
integral depends only on the properties of the structure matrix.
A particularly simple class of matrices which yield integral
polyhedra (assuming the vector on the right-hand side of the
system of inequalities is integral) is the class of {\em totally
unimodular} matrices~\cite{AS}. A matrix is totally unimodular if
and only if every possible square submatrix has determinant $0$ or
$\pm 1$. Since structure matrices consist only of the elements $0$
and $\pm 1$ they are prime candidates for total unimodularity.
Unfortunately, this is not the case in general (see
Section~\ref{se:examples}). However, there is somewhat weaker
condition on structure matrices which also guarantees integral
structure polyhedra.
Let $A$ be a structure matrix and $\wp$ the associated structure
polyhedron. Suppose that every maximal square submatrix of $A$
(i.e., every square submatrix of order $N+1$) has determinant $0$
or $\pm 1$. Since each vertex of $\wp$ is determined by $N+1$
linearly independent equations from the system ${Ap =
1}$~\cite{AS}, this guarantees that all vertices of $\wp$ are
integral.\footnote{Consider Cramer's rule.} A square matrix is
said to be {\em unimodular} if its elements are integral and
its determinant is $\pm 1$. According to the usual definition of
unimodularity applicable to more general matrices~\cite{AS}, a
structure matrix $A$ will have the above property precisely when
the transpose of $A$ is unimodular. We conjecture that this is, in
fact, the case.
\begin{conjecture}
For every structure matrix $A$, the transpose of $A$ is
unimodular.
\label{co:smuni}
\end{conjecture}
This purpose of replacing Conjecture~\ref{co:spi} by this
stronger statement is that presumedly Conjecture~\ref{co:smuni}
can be proved more directly since the theory of unimodular
matrices is well developed. However, as discussed in
Section~\ref{se:structmat}, a complete characterization of the
class of structure matrices is needed first.
\label{se:spvp}
\end{subsection}
\label{se:suplocmax}
\end{section}
\begin{section}{Convexity and the Irregularity Function}
\reset
We now interpret some of the results of
Sections~\ref{se:suplocmax} in the context of the continuous
irregularity function~$F_N(x)$. In one sense this is trivial,
since equation~(\ref{eq:funfac}) (together with the $N$-triangle
bijection~$T$) gives the complete story as far as translating
between the continuous and $N$-triangle domains. What is
interesting is the naturalness with which standard convexity
statements in the continuous domain translate into statements
about $N$-triangles. This is the fundamental reason that the
present work should stimulate further progress on the widely
applicable Golomb Ruler Problem.
Before demonstrating how convexity translates from one domain
to the other, we make two additional remarks regarding
$\approx$-equivalence. Firstly, Theorem~\ref{th:eqth0} implies
that ${p \approx T(x)}$ if and only if
${x = T^{-1}(p)}$. We will normally write the former relation.
Secondly, by summing both sides of equation~(\ref{eq:T}), it
follows that if ${p = T(x)}$ then ${\trc p = C_x}$. If ${p \approx
T(x)}$ then the latter equality does not hold; nevertheless,
equation~(\ref{eq:T_inv}) implies
\begin{equation}
p_j = \trc p\,(x_{j+1} - x_j).
\label{eq:T_alt}
\end{equation}
We begin our discussion of convexity in the usual way. Let
${x,y \in X_N}$ and define the {\em open segment} spanned by $x$
and $y$ according to
\begin{equation}
(x,y) \equiv \{ z \mid z = \lambda x + (1-\lambda) y;\quad
\lambda \in (0,1) \cap \IQ \}
\end{equation}
This is identical to the standard definition of convex
analysis~\cite{JS} except that our underlying space is rational.
It is easy to see that $(x,y) \subset X_N$; i.e., $X_N$ is convex.
In equation~(\ref{eq:Rpq}), we defined the open segment spanned
by~$p$ and~$q$, where $p,q \in P_N$. We justify this redundant use
of terminology by the following theorem.
\begin{theorem}
Let ${x,y \in X_N}$ and ${p,q \in P_N}$, and suppose that
${p \approx T(x)}$ and ${q \approx T(y)}$. Then
\begin{equation}
(p,q) \approx T \Big((x,y)\Big).
\end{equation}
\label{th:segment}
\end{theorem}
\beginproof
Let $r \in (p,q)$ so that $r = mp + nq$ for some $m,n \in \IN$.
Define
\begin{equation}
\lambda = \frac{m\,\trc p}{m\,\trc p + n\,\trc q}
\label{eq:lambda}
\end{equation}
and put ${z = \lambda x + (1-\lambda)y}$ so that ${z \in (x,y)}$.
Then, for
$0 \le j \le N+1$,
\begin{eqnarray}
z_j & = & \lambda x_j + (1-\lambda)y_j \nonumber \\
\noalign{\vskip 6pt}
& = & \frac{m\,\trc p\,x_j + n\,\trc q\,y_j}
{m\,\trc p + n\,\trc q} \nonumber \\
& = & \frac{m \sum_{k=0}^{j-1} p_k + n \sum_{k=0}^{j-1} q_k}
{m\,\trc p + n\,\trc q} \nonumber \\
& = & \frac{1}{\trc r} \sum_{k=0}^{j-1} r_k.
\end{eqnarray}
Therefore $r \approx T(z) \in T \Big((x,y)\Big)$.
Now let $z \in (x,y)$ so that $z = \lambda x + (1-\lambda)y$
where $\lambda=s/t$ for some $s,t \in \IN$ satisfying $0~~0}$ on the
entire open segment spanned by $x$ and $y$. In the reverse
direction, it is interesting to note how these intuitive
statements about $F_N(x)$ translate into non-intuitive but simple
and useful facts about $N$-triangles.
{}From the discussion at the beginning of
Section~\ref{se:defconres}, we know that the closure of each
connected component of $X'_N$ is an $N$-dimensional polyhedron.
Each facet of one of these polyhedra is the intersection of the
polyhedron itself with an $(N-1)$-dimensional hyperplane of the
form ${f_{i,j,k,l}(x)=0}$. Thus, each of these polyhedra is
determined by a set of inequalities, each of which is of the form
\begin{equation}
x_i-x_j-x_k+x_l \ge 0
\end{equation}
for some admissible $i,j,k,l$. It follows that each of these
polyhedra can be described as ${\{ x \mid Bx \ge 0 \}}$, where~$B$
is some matrix whose elements can only be~$0$, $\pm 1$, or $\pm
2$. It is important to note that, in this representation, $x$ must
include the component ${x_{N+1}=1}$, so that the column order
of~$B$ is~$N+1$. Consequently, the system of inequalities is not
really homogeneous, and therefore does not describe a {\em
polyhedral cone}~\cite{AS} in~$X_N$. Of course, these polyhedra
must be intimately related to the structure polyhedra introduced
in Section~\ref{se:defconres}. We make this relationship explicit
as follows.
The first step is to establish the relationship between the
structure matrix~$A$ and the matrix~$B$, which turns out to be
trivial. Each row of $B$ represents the difference between two
entries in the triangle of Figure~\ref{fi:xtri}; whereas, each row
of $A$ represents the difference between two entries in the
triangle of Figure~\ref{fi:ptri}. Since these two triangles differ
only by a normalization factor of $\trc p$, we have
\begin{equation}
\frac{1}{\trc p} \sum_{j=0}^N A_{i,j} p_j = \sum_{j=1}^{N+1}
B_{i,j} x_j.
\label{eq:AB}
\end{equation}
Then, by using equation~(\ref{eq:T_alt}), it is easy to show that
\begin{equation}
B_{i,j} = \left\{
\begin{array}{ll}
A_{i,j-1} - A_{i,j}, & \mbox{$1 \le j \le N$} \\
\noalign{\vskip 0.25cm}
A_{i,N}, & \mbox{$j=N+1$}
\end{array}
\right.
\end{equation}
and
\begin{equation}
A_{i,j} = \sum_{k=j+1}^{N+1} B_{i,k},\qquad 0 \le j \le N;
\end{equation}
i.e., the matrices~$A$ and~$B$ are related by elementary column
operations.
Suppose~$A$ and~$B$ are related in the above manner and let~$\wp$
be the structure polyhedron defined by~$A$. Then the interior of
the polyhedron
${\{ x \mid Bx \ge 0 \}}$ is the inverse image (with respect
to~$T$) of the integral vectors in $\wp$; in other words,
\begin{equation}
T(\{ x \mid Bx > 0 \}) \approx \{p \mid A p \ge 1;\ p\ {\rm
integral}\}.
\end{equation}
This, however, is not the most useful interpretation of the
structure polyhedron~$\wp$. Its primary importance comes from its
relationship to the hypograph of $F_N(x)$ restricted to ${\{ x
\mid Bx \ge 0 \}}$. We denote this object by~$\chi$; i.e.,
\begin{equation}
\chi = \{ (x,z) \mid Bx \ge 0;\quad 0 \le z \le F_N(x) \}.
\end{equation}
As previously remarked, $F_N(x)$ restricted to ${\{ x \mid Bx
\ge 0 \}}$ is polyhedral; i.e., $\chi$ itself is an
$(N+1)$-dimensional polyhedron. In order to see this, note that if
${Bx \ge 0}$ then
\begin{equation}
F_N(x) = \min_i\left\{\sum_{j=1}^{N+1} B_{i,j} x_j\right\}.
\end{equation}
This is just the continuous analogue of equation~(\ref{eq:altin}).
It follows that~$\chi$ can also be written in the (manifestly
polyhedral) form
\begin{equation}
\chi = \{ (x,z) \mid Bx \ge z \ge 0 \}.
\end{equation}
In Section~\ref{se:spvp}, we established a relationship between
the vertices of~$\wp$ (or $N$-triangles with the vertex property)
and local maximality. The following theorem, which establishes a
relationship between~$\chi$ and~$\wp$, both explains and
generalizes this earlier result.
\begin{theorem}
Let $\wp$ be a structure polyhedron and $\chi$ the corresponding
polyhedral component of the hypograph of $F_N(x)$. Then $(x,z)$
is a vertex of $\chi$ satisfying $z > 0$ if and only if $p = T(x)$
has the vertex of property.
\label{th:chi}
\end{theorem}
\beginproof
Let $(x,z)$ be a vertex of $\chi$ satisfying ${z > 0}$ and let
${p = T(x)}$. Then there is a submatrix $\tilde{B}$ consisting of
$N+1$ linearly independent rows of $B$ such that ${\tilde{B}x =
z}$. Being a vertex, $(x,z)$ must certainly lie on the boundary of
$\chi$; therefore, as $z>0$, one must conclude that $z = F_N(x)$.
By using equations~(\ref{eq:funfac}) and~(\ref{eq:AB}), it follows
that there is a submatrix $\tilde{A}$ consisting of $N+1$ linearly
independent rows of $A$ such that ${\tilde{A}p = \ind p}$. This
means precisely that $p$ has the vertex property; i.e., $\rho = p
/ \ind p$ is a vertex of the structure polyhedron $\wp$. The
converse argument is analogous.
\endproof
Thus, the structure polyhedra formulation suppresses those
points where $F_N(x)$ vanishes while simultaneously capturing all
of the interesting behavior of $F_N(x)$ as vertices. This is
precisely why the $N$-triangle method is so powerful in analyzing
$F_N(x)$.
We conclude this section with the following theorem, which
partially answers the uniqueness question for local maxima.
\begin{theorem}
The polyhedron $\{ x \mid Bx \ge 0 \}$ is an $N$-dimensional
simplex if and only if the corresponding polyhedron $\chi$ is an
$(N+1)$-dimensional simplex.
\label{th:simplex}
\end{theorem}
\beginproof
Suppose $\{ x \mid Bx \ge 0 \}$ is an $N$-dimensional simplex.
Then, possibly after removing some redundant inequalities, we may
assume that the matrix $B$ has $N+1$ rows~\cite{AS}. Thus, after
removing the corresponding redundant inequalities, the matrix $A$
also has $N+1$ rows. From Theorem~\ref{th:wp_prop}, we know
that~$\wp$ is pointed; hence, it must have at least one vertex. On
the other hand, as there are only $N+1$ inequalities which define
$\wp$, it cannot have more than one vertex. Thus $\wp$ has exactly
one vertex. Then, as a consequence of Theorem~\ref{th:chi}, $\chi$
must be an $(N+1)$-dimensional simplex. The converse implication
is trivial.
\endproof
The proof is interesting in that is uses the structure
polyhedron~$\wp$ as an intermediary between the other two
polyhedra. If either of the propositions are true then $F_N(x)$
attains a unique local maximum on $\{ x \mid Bx \ge 0 \}$.
\label{se:convex}
\end{section}
\begin{section}{Two Examples}
\reset
We will now consider two examples. In addition to illustrating
many of the concepts thus far presented, we will develop (but not
attempt to formalize) a procedure for parameterizing the set of
all $N$-triangles with a given structure. For both examples, we
take as a starting point the structure triangle introduced by
Definition~\ref{de:stri}.
\begin{subsection}{Example I}
Consider the $N=3$ structure triangle shown in
Figure~\ref{fi:striExI}. \begin{figure}[htb]
\begin{displaymath}
\begin{array}{rrrr}
1 & & & \\
& 4 & & \\
3 & & 8 & \\
& 7 & & 10 \\
5 & & 9 & \\
& 6 & & \\
2 & & &
\end{array}
\end{displaymath}
\caption{Structure Triangle for Example I}
\label{fi:striExI}
\end{figure}
This structure triangle specifies one of the~$61$ (modulo
conjugacy) admissible orderings for the~$10$ distinct elements of
a Good $3$-triangle; hence it defines an equivalence class of
$P'_3$. As usual, denote the associated structure matrix and
structure polyhedron by~$A$ and~$\wp$, respectively. By following
the previously explained procedure for constructing $A$, the
matrix equation ${Ap \ge 1}$ (which defines~$\wp$) can be written
out explicitly as
\begin{equation}
\left[
\begin{array}{rrrr}
1 & 0 & 0 & 0 \\
-1 & 0 & 0 & 1 \\
0 & 1 & 0 & -1 \\
-1 & -1 & \phantom{-}1 & 0
\end{array}
\right]
\left[
\begin{array}{r}
p_0 \\
p_1 \\
p_2 \\
p_3
\end{array}
\right] \ge
\left[
\begin{array}{r}
1 \\
1 \\
1 \\
1
\end{array}
\right].
\label{eq:ExI}
\end{equation}
In other words, not counting the~$1$ (which determines the
first row of~$A$), there are only three consecutive independent
pairs: {1--2}, {2--3}, and {4--5}. This is the minimal number of
rows for a ${N=3}$ structure matrix, as $A$ must contain
sufficient information for ordering the four components of the
generator. The matrix~$B$ (related to~$A$ by
equation~(\ref{eq:AB})) is given by
\begin{equation}
B =
\left[
\begin{array}{rrrr}
1 & 0 & 0 & 0 \\
-1 & 0 & -1 & 1 \\
-1 & 1 & 1 & -1 \\
0 & -2 & 1 & 0
\end{array}
\right].
\end{equation}
The fact that~$B$ has only four rows implies that the polyhedron
${\{ x \mid Bx \ge 0 \} \subset X_N}$ is a simplex. The structure
polyhedron itself cannot be a simplex as it is unbounded. In order
to see exactly what~$\wp$ looks like, we proceed as follows.
Suppose $p \in \wp \cap P_N$. The first inequality
in~(\ref{eq:ExI}) says that $p_0$ must be positive. Thus, for any
${\alpha \in \IN}$, we can put ${p_0 = \alpha}$. The second
inequality in~(\ref{eq:ExI}) says that ${p_3 - p_0}$ must be
positive. Thus, for any ${\beta \in \IN}$, we can put ${p_3 =
\alpha + \beta}$. Continuing in this manner, for any
${\gamma,\delta \in \IN}$, we can put ${p_1 = \alpha + \beta +
\gamma}$ and ${p_2 = 2\alpha + \beta + \gamma + \delta}$. So we
have
\begin{equation}
\left[
\begin{array}{r}
p_0 \\
p_1 \\
p_2 \\
p_3
\end{array}
\right] =
\left[
\begin{array}{rrrr}
1 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 \\
2 & 1 & 1 & 1 \\
1 & 1 & 0 & 0
\end{array}
\right]
\left[
\begin{array}{r}
\alpha \\
\beta \\
\gamma \\
\delta
\end{array}
\right].
\label{eq:ExI_param}
\end{equation}
This parameterizes the structure equivalence class in terms of
a single vector with arbitrary positive integral
components.\footnote{According to reference~\cite{AS}, the concept
of an {\em integral Hilbert basis} can be used to give a
parametric representation of the integral vectors in any rational
polyhedron.} Moreover, we have
\begin{eqnarray}
\trc p & = & 5\alpha + 3\beta + 2\gamma + \delta; \nonumber\\
\ind p & = & \min\{\alpha,\beta,\gamma,\delta\}.
\label{eq:ExI_ti}
\end{eqnarray}
Thus, it is trivial to prove the existence of a unique Superb
$N$-triangle --- just put ${\alpha = \beta = \gamma = \delta =
1}$. This yields the first $N=3$ Perfect $N$-triangle listed in
Appendix~\ref{ap:perfects}. As it happens, this $N$-triangle can
be mechanically obtained from the structure triangle of
Figure~\ref{fi:striExI} by increasing the numbers~$6$ through~$10$
by~$1$.
If we drop the integrality constraint on the parameter-vector,
the structure polyhedron itself is parameterized by the same
equation (each component must still be greater than or equal to
one). Therefore, with reference to Theorems~\ref{th:ILP}
and~\ref{th:LP}, the unique Superb $N$-triangle must also be a
unique locally maximal $N$-triangle.\footnote{This is also easy to
prove directly by using equation~(\ref{eq:ExI_ti}) and
Definition~\ref{de:locmax}.} Furthermore, the unique Superb
$N$-triangle is clearly a vertex of~$\wp$, as all four
inequalities in~(\ref{eq:ExI}) are saturated. In fact, as there
are only four inequalities from which to choose, it is the only
vertex of~$\wp$; hence, $\wp$ is integral. Of course, this
situation is in accordance with (and provides an excellent
illustration of) Theorem~\ref{th:chi}.
In light of the above considerations, the structure
polyhedron~$\wp$ can be visualized as an unbounded, four-sided,
cone-like polyhedron, situated in the space $(\IR^+)^4$,
whose apex (which is the unique Superb $N$-triangle) is the
closest point in~$\wp$ to the origin. The $N$-dimensional
generalization of this picture is actually a rather accurate
description for {\em any} structure polyhedron, except that there
may be more than $N+1$ sides and/or there may be more than one
vertex. Both of these situations are illustrated in Example~II.
This example (and the next one) supports the point of view that,
once restricted to a particular structure polyhedron, finding
Superb $N$-triangles and proving their correspondence with local
maxima are relatively easy --- the real challenge is determining
how the connected components of $X'_N$ are put together. The
following observation, which at least on the surface is truly
remarkable, takes this point of view to its extreme.
Consider the column vectors of the matrix in
equation~(\ref{eq:ExI_param}). It can be readily verified that
these vectors are the generators of the (necessarily not Good)
$N$-triangles corresponding to the four vertices of the simplex
${\{ x \mid Bx \ge 0 \}}$. Recall that this polyhedra is only
$3$-dimensional; hence, each vertex must saturate three of the
inequalities and merely satisfy the fourth. This is remarkable
because the unique Superb $N$-triangle is given by the sum of the
four $N$-triangles corresponding to these vertices. We state this
property formally as the following conjecture.
\begin{conjecture}
Restricted to each polyhedron ${\{ x \mid Bx \ge 0 \}}$,
$F_N(x)$ attains a unique local maximum --- whose corresponding
(Superb) $N$-triangle is given by the sum of the $N$-triangles
corresponding to the vertices of ${\{ x \mid Bx \ge 0 \}}$.
\label{co:vertex}
\end{conjecture}
In addition to this example, it can be verified case by case
that this conjecture is universally true for ${N=1}$ and ${N=2}$.
If it is true in general, then knowledge of the vertices defining
the connected components of $X'_N$ gives immediate knowledge of
the local maxima. However, Conjecture~\ref{co:vertex} may be true
only if ${\{ x \mid Bx \ge 0 \}}$ is a simplex, or if it is
weakened in some other way.
Finally, we remark that, for this example, it is easy to verify
that the structure matrix~$A$ is {\em totally unimodular}. With
reference to the discussion following Conjecture~\ref{co:spi},
this provides a direct proof that this particular structure
polyhedron is integral.
\end{subsection}
\begin{subsection}{Example II}
Now consider the $N=3$ structure triangle shown in
Figure~\ref{fi:striExII}.
\begin{figure}[htb]
\begin{displaymath}
\begin{array}{rrrr}
2 & & & \\
& 4 & & \\
1 & & 7 & \\
& 5 & & 10 \\
3 & & 9 & \\
& 8 & & \\
6 & & &
\end{array}
\end{displaymath}
\caption{Structure Triangle for Example II}
\label{fi:striExII}
\end{figure}
We proceed as in Example~I, but only comment on those aspects
which are different from the previous analysis. The matrix
equation ${Ap \ge 1}$ written out explicitly is
\begin{equation}
\left[
\begin{array}{rrrr}
0 & 1 & 0 & 0 \\
1 & -1 & 0 & 0 \\
-1 & 0 & 1 & 0 \\
1 & 1 & -1 & 0 \\
0 & -1 & -1 & 1 \\
1 & 1 & 1 & -1
\end{array}
\right]
\left[
\begin{array}{r}
p_0 \\
p_1 \\
p_2 \\
p_3
\end{array}
\right] \ge
\left[
\begin{array}{r}
1 \\
1 \\
1 \\
1 \\
1 \\
1
\end{array}
\right].
\label{eq:ExII}
\end{equation}
In this case, there are five consecutive independent pairs
of $N$-triangle elements (not counting the~$1$).
Suppose $p \in \wp \cap P_N$. Proceeding as in Example~I,
the first three inequalities in~(\ref{eq:ExII}) give ${p_1 =
\alpha}$, ${p_0 = \alpha + \beta}$, and ${p_2 = \alpha + \beta +
\gamma}$. The fourth inequality then tells us that
\begin{equation}
(2\alpha + \beta) - (\alpha + \beta + \gamma) = \alpha -
\gamma \ge 1.
\end{equation}
We satisfy this inequality by defining ${\alpha = \alpha' +
\gamma}$, where $\alpha' \in \IN$. Substituting into the first
three inequalities gives ${p_1 = \alpha' + \gamma}$, ${p_0 =
\alpha' + \beta + \gamma}$, and ${p_2 = \alpha' + \beta +
2\gamma}$. The fifth inequality then gives ${p_3 = 2\alpha' +
\beta + 3\gamma + \delta}$. Finally, the sixth inequality tells
us
that
\begin{equation}
(3\alpha' + 2\beta + 4\gamma) - (2\alpha' + \beta + 3\gamma
+ \delta) =
\alpha' + \beta + \gamma - \delta \ge 1.
\end{equation}
Thus, by dropping the prime on $\alpha$, we have
\begin{equation}
\left[
\begin{array}{r}
p_0 \\
p_1 \\
p_2 \\
p_3
\end{array}
\right] =
\left[
\begin{array}{rrrr}
1 & 1 & 1 & 0 \\
1 & 0 & 1 & 0 \\
1 & 1 & 2 & 0 \\
2 & 1 & 3 & 1
\end{array}
\right]
\left[
\begin{array}{r}
\alpha \\
\beta \\
\gamma \\
\delta
\end{array}
\right].
\label{eq:ExII_param}
\end{equation}
This parameterizes the structure equivalence class in terms of
a single vector with positive integral components; however, these
components must satisfy the additional constraint ${\alpha + \beta
+ \gamma - \delta \ge 1}$. In this case, we have
\begin{eqnarray}
\trc p & = & 5\alpha + 3\beta + 7\gamma + 1\delta; \nonumber\\
\ind p & = & \min\{\alpha,\beta,\gamma,\delta,
\alpha + \beta + \gamma - \delta\}.
\label{eq:ExII_ti}
\end{eqnarray}
The inequality ${p_1 \ge 1}$ is not represented in the formula
for the index. This is because it is {\em redundant}~\cite{JS};
i.e., it is implied by the other inequalities.
Again, it is trivial to prove the existence of a unique Superb
$N$-triangle by putting ${\alpha = \beta = \gamma = \delta = 1}$.
The resulting $N$-triangle will be denoted by~$p$, and is shown in
Figure~\ref{fi:ExII}.
\begin{figure}[htb]
\begin{displaymath}
p = \left\{
\begin{array}{rrrr}
3 & & & \\
& 5 & & \\
2 & & 9 & \\
& 6 & & 16 \\
4 & & 13 & \\
& 11 & & \\
7 & & &
\end{array}
\right.\qquad
q = \left\{
\begin{array}{rrrr}
3 & & & \\
& 5 & & \\
2 & & 9 & \\
& 6 & & 17 \\
4 & & 14 & \\
& 12 & & \\
8 & & &
\end{array}
\right.
\end{displaymath}
\caption{$N$-Triangles with the Vertex Property for Example II}
\label{fi:ExII}
\end{figure}
As in Example~I, there are several ways to see that~$p$ must also
be a unique locally maximal $N$-triangle. First, we note that~$p$
is again a vertex of~$\wp$, as four inequalities
in~(\ref{eq:ExII}) are saturated. In this case, however, there is
a second $N$-triangle which is also a vertex of~$\wp$, but is not
Superb. This peculiar $N$-triangle is obtained by putting ${\alpha
= \beta = \gamma = 1}$ and ${\delta = 2}$ so that ${\alpha + \beta
+ \gamma - \delta = 1}$ is the fourth saturated inequality. The
resulting $N$-triangle will be denoted by~$q$, and is also shown
in Figure~\ref{fi:ExII}. It is not difficult to argue that~$p$
and~$q$ are the only vertices of the structure polyhedron~$\wp$;
hence, $\wp$ is integral. The conclusion that~$p$ is the unique
locally maximal $N$-triangle with the given structure then follows
{}from the analysis of Section~\ref{se:spvp}.
For this example, whether or not the column vectors of the matrix
in equation~(\ref{eq:ExII_param}) correspond to vertices of the
polyhedron ${\{ x \mid Bx \ge 0 \}}$ has not been checked.
However, from Theorems~\ref{th:chi} and~\ref{th:simplex} and the
fact that the structure polyhedron~$\wp$ has two vertices, we know
that ${\{ x \mid Bx \ge 0 \}}$ is {\em not} a simplex. Thus, it
must have at least five vertices, and therefore, the column
vectors of the matrix in equation~(\ref{eq:ExII_param}) cannot
give the whole story. Nevertheless, Conjecture~\ref{co:vertex} may
still be true.
Incidentally, for this example, the structure matrix~$A$ is
{\em not} totally unimodular, as it contains $2 \times 2$
submatrices with determinant $\pm 2$.
\end{subsection}
\label{se:examples}
\end{section}
\begin{section}{The Recurrence Property}
\reset
We now return temporarily to the continuous domain in order
to point out an interesting property of the irregularity function
$F_N(x)$. As a consequence of this digression, we will be able to
identify a sizable family of structures whose Superb $N$-triangles
cannot possibly be Perfect. In order to illustrate this property,
we refer to the slice of $F_3(x)$ shown in Figure~\ref{fi:rp1}.
\begin{figure}[tb]
\setlength{\unitlength}{1.0cm}
\begin{picture}(15.0,10.0)(-3.5,-1.0)
\put(-1.13,-2.0){
\epsfxsize=10.0cm
\epsffile{n3_rp1.eps}
%\special{illustration n3_rp1.eps}
}
\put(0.0,0.0){\line(1,0){8.0}}
\put(8.0,0.0){\line(0,1){8.0}}
\put(8.0,8.0){\line(-1,0){8.0}}
\put(0.0,8.0){\line(0,-1){8.0}}
\put(0.0,0.0){\line(0,-1){0.15}}
\put(8.0,0.0){\line(0,-1){0.15}}
\put(0.0,0.0){\line(-1,0){0.15}}
\put(0.0,8.0){\line(-1,0){0.15}}
\put(-0.1,-0.50){$0$}
\put(7.9,-0.50){$1$}
\put(-0.45,-0.1){$0$}
\put(-0.45,7.9){$1$}
\put(3.9,-0.60){$x_1$}
\put(-0.80,3.9){$x_2$}
\put(8.5,4.80){$x_3=6/13$}
\end{picture}
\caption{The Recurrence Property}
\label{fi:rp1}
\end{figure}
This figure is interesting in that it contains an exact scaled
reproduction of the graph of $F_2(x)$ (shown in
Figure~\ref{fi:F_2}) in the lower left-hand corner. We will call
this phenomenon the {\em recurrence property} of $F_N(x)$. In
order to understand this property, we proceed as follows.
For each $x \in X_N \setminus \{0\}$, define $x' \in X_{N-1}$ by
\begin{equation}
x' \equiv (x_1/x_N,\cdots,x_{N-1}/x_N).
\end{equation}
We then ask for which values of $x \in X_N \setminus \{0\}$ the
following recurrence relation holds:
\begin{equation}
F_N(x) = x_N\, F_{N-1}(x').
\label{eq:recur}
\end{equation}
This question can be most easily answered after translation into
the language of $N$-triangles. With reference to
Figure~\ref{fi:ptri}, let $p'$ denote the $(N-1)$-triangle
obtained by deleting the bottom diagonal of the $N$-triangle $p$
so that ${p'_{i,j}=p_{i,j}}$ for ${0 \le i \le j \le N-1}$. From
the definition of $T$, it follows easily that\footnote{In the
first equation ${T:\, X_N \rightarrow P_N}$; whereas in the
second, ${T:\, X_{N-1} \rightarrow P_{N-1}}$; thus technically,
the notation should distinguish between the two mappings.}
\begin{equation}
p=T(x) \Longrightarrow p' \approx T(x').
\end{equation}
By using equation~(\ref{eq:funfac}), the recurrence relation
translates directly into
\begin{equation}
\frac{\ind p}{\trc p} =
\frac{\trc p'}{\trc p} \cdot \frac{\ind p'}{\trc p'}.
\end{equation}
This equation (and hence the recurrence) holds precisely when
${\ind p=\ind p'}$. It is automatically true that ${\ind p \le
\ind p'}$; thus, this condition is equivalent to saying that the
minimum difference (which determines the index of $p$) is attained
between two elements which lie in $p'$. We will not attempt to
characterize the entire subset of $X_N$ where this condition
holds, but only a portion thereof. In particular, it is easy to
see that
\begin{equation}
p_N \ge \trc p' + \ind p' \Longrightarrow
\ind p=\ind p'.
\end{equation}
The translation of the left-hand side of this implication back
into the continuous domain is
\begin{equation}
x_N \le \frac{1}{2+F_{N-1}(x')}.
\end{equation}
The term $F_{N-1}(x')$ in the denominator may be replaced by
anything larger in order to obtain a simple sufficient condition
for the recurrence relation to hold. The strongest such condition
that depends only on $x_N$ is given by the following theorem.
\begin{theorem}
For all $x \in X_N \setminus \{0\}$ satisfying $x_N \le [2 +
\max F_{N-1}(x)]^{-1}$, the recurrence relation~(\ref{eq:recur})
holds.
\label{th:rp}
\end{theorem}
According to this theorem, the value $x_3=6/13$ used in
Figure~\ref{fi:rp1} is the largest possible value which guarantees
that the recurrence property holds. The breakdown of this property
for $6/13 < x_3 \le 1/2$ is illustrated in Figure~\ref{fi:rp2}.
\begin{figure}[tb]
\setlength{\unitlength}{1.0cm}
\begin{picture}(15.0,10.0)(-3.5,-1.0)
\put(-1.13,-2.0){
\epsfxsize=10.0cm
\epsffile{n3_rp2.eps}
%\special{illustration n3_rp2.eps}
}
\put(0.0,0.0){\line(1,0){8.0}}
\put(8.0,0.0){\line(0,1){8.0}}
\put(8.0,8.0){\line(-1,0){8.0}}
\put(0.0,8.0){\line(0,-1){8.0}}
\put(0.0,0.0){\line(0,-1){0.15}}
\put(8.0,0.0){\line(0,-1){0.15}}
\put(0.0,0.0){\line(-1,0){0.15}}
\put(0.0,8.0){\line(-1,0){0.15}}
\put(-0.1,-0.50){$0$}
\put(7.9,-0.50){$1$}
\put(-0.45,-0.1){$0$}
\put(-0.45,7.9){$1$}
\put(3.9,-0.60){$x_1$}
\put(-0.80,3.9){$x_2$}
\put(8.5,4.80){$x_3=25/52$}
\end{picture}
\caption{Breakdown of the Recurrence Property}
\label{fi:rp2}
\end{figure}
The reason for this breakdown is that $F_3(x)$ is determined by
the component function $|1-2x_3|$ near $x_3=1/2$. In the figure,
this component function manifests itself as a black surface of
constant height. As $x_3$ approaches unity, another exact scaled
image of $F_2(x)$ appears in the upper right-hand corner of the
graph, as can be seen in Figure~\ref{fi:F_3}. This new recurrence
can be easily understood in terms of the symmetry properties of
$F_N(x)$; however, it is of no interest in the present
development, as the image falls outside of the ordered-$x$
simplex. Finally, we remark that Theorem~\ref{th:rp} can be
applied recursively. For example, if ${x_3 \le 6/13}$ and
${x_2/x_3 \le 3/7}$ then ${F_3(x)=x_2 F_1(x)}$. If, in addition,
${x_1/x_2 \le 1/3}$ then ${F_3(x)=x_1}$, at which point the
recurrence property has become trivial.
The constraining value of $x_N$ in Theorem~\ref{th:rp} approaches
$1/2$ monotonically from below as $N$ tends to infinity. Thus, in
the region
$x_N < 1/2$, it is reasonable to suppose that $F_N(x)$ possesses
local maxima corresponding to the local maxima of $F_{N-1}(x')$
via the recurrence relation~(\ref{eq:recur}). We will argue
informally (by means of an example) that these are the only local
maxima in the region $x_N < 1/2$ and that they cannot possibly be
global maxima. The formal motivation behind this informal argument
is Theorem~\ref{th:pp'}, which is written in the language of
$N$-triangles. Instead of treating local maximality, however, the
theorem treats the closely related vertex property.
Let $x \in X_N$ and $p = T(x)$. First we note how the condition
$x_N < 1/2$ is translated into a condition on $p$. As before, let
$p'$ denote the $(N-1)$-triangle obtained by deleting the bottom
diagonal of the $N$-triangle $p$. By using the fact that ${p_N =
\trc p\,(1 - x_N)}$, it is easy to show that
\begin{equation}
x_N < 1/2 \Longleftrightarrow 2 p_N - \trc p > 0
\Longleftrightarrow p_N - \trc p' > 0.
\label{eq:half}
\end{equation}
In other words, $x_N < 1/2$ if and only if the generator component
$p_N$ is greater than the sum of all the other generator
components. We can now give a recursive characterization of the
vertex property for those $N$-triangles which satisfy this
condition.
\begin{theorem}
Let $p \in P_N$ and suppose that the inequalities
in~(\ref{eq:half}) hold. Then $p$ has the vertex property if and
only if $p'$ has the vertex property and
\begin{equation}
p_N - \trc p' = \ind p'.
\label{eq:pp'}
\end{equation}
\label{th:pp'}
\end{theorem}
\beginproof
The inequality $p_N - \trc p' > 0$ implies that the structure
matrices of $p$ and $p'$ are related by
\begin{equation}
A = \left[
\begin{array}{cccc}
& & & 0 \\
& A' & & \vdots \\
& & & 0 \\
-1 & \cdots & -1 & 1
\end{array}
\right]
\end{equation}
Assume $p$ has the vertex property. Then there is a submatrix
$\tilde{A}$ consisting of $N+1$ linearly independent rows of $A$
such that
${\tilde{A}p = \ind p}$. One of these rows must be the bottom
row of $A$ since otherwise $\tilde{A}$ would be singular;
therefore, ${p_N - \trc p' = \ind p}$. The other $N$ rows must be
contained in $A'$; i.e., there is a submatrix $\tilde{A'}$
consisting of $N$ linearly independent rows of $A'$ such that
${\tilde{A'}p' = \ind p}$. Trivially, ${\ind p \le \ind p'}$. On
the other hand, with the help of equation~(\ref{eq:altin}), we can
conclude the reverse inequality; therefore, ${\ind p = \ind p'}$.
It follows that $p'$ has the vertex property and ${p_N - \trc p' =
\ind p'}$.
Now assume $p'$ has the vertex property and ${p_N - \trc p' =
\ind p'}$. Then there is a submatrix $\tilde{A'}$ consisting of
$N$ linearly independent rows of $A'$ such that ${\tilde{A'}p' =
\ind p'}$. Together with
${p_N - \trc p' = \ind p'}$ (corresponding to the bottom row of
$A$), these form a submatrix $\tilde{A}$ consisting of $N+1$
linearly independent rows of $A$ such that ${\tilde{A}p = \ind
p'}$. In this case, it is immediate that ${\ind p = \ind p'}$. It
follows that $p$ has the vertex property.
\endproof
Equation~(\ref{eq:pp'}) implies that ${\ind p = \ind p'}$ and
${\trc p = 2\trc p' + \ind p'}$. We remark that it easy to
produce an $N$-triangle with the same index and trace (and thus
the same irregularity) which does {\em not} have the vertex
property. Indeed, consider the $N$-triangle generated by
\begin{equation}
q_k = \left\{
\begin{array}{ll}
\ind p', & \mbox{$k = 0$} \\
\noalign{\vskip 0.25cm}
2p'_{k-1}, & \mbox{$1 \le k \le N$}
\end{array}
\right..
\label{eq:q_k}
\end{equation}
Theorem~\ref{th:pp'} and the preceding remark are significant
for the following reason. Suppose Conjecture~\ref{co:eqthII} is
true. Then the phrase ``has the vertex property'' can be replaced
by either ``is Superb'' or ``is locally maximal'' in both the
theorem and the remark. This implies that, among other things, the
Superb $N$-triangles corresponding to the family of structures
described by equation~(\ref{eq:half}) cannot possibly be Perfect.
Thus, for each successive value of $N$, the part of $F_N(x)$ which
is easily understood in terms of $F_{N-1}(x)$ is irrelevant in
solving Problem~\ref{pr:max_F}.
As an example, let $p'$ be the Perfect $2$-triangle given in
Appendix~\ref{ap:perfects}. We know from previous considerations
that this Perfect $2$-triangle has the vertex property and is
globally maximal. According to Theorem~\ref{th:pp'}, we can form a
$3$-triangle $p$ with the vertex property by appending $p_3=7$.
This $3$-triangle is shown in Figure~\ref{fi:pp'}.
\begin{figure}[htb]
\begin{displaymath}
p = \left\{
\begin{array}{rrrr}
1 & & & \\
& 4 & & \\
3 & & 6 & \\
& 5 & & 13 \\
2 & & 12 & \\
& 9 & & \\
7 & & &
\end{array}
\right.\qquad
q = \left\{
\begin{array}{rrrr}
1 & & & \\
& 3 & & \\
2 & & 9 & \\
& 8 & & 13 \\
6 & & 12 & \\
& 10 & & \\
4 & & &
\end{array}
\right.
\end{displaymath}
\caption{Example ($N=3$) of Theorem \protect\ref{th:pp'}}
\label{fi:pp'}
\end{figure}
By carrying out an analysis similar to that of
Section~\ref{se:examples}, it is easy to show that $p$ is both
Superb and locally maximal. However, by using
equation~(\ref{eq:q_k}), we can construct an $N$-triangle $q$
(also shown in Figure~\ref{fi:pp'}) which lacks the vertex
property and thus cannot be Superb. It follows that the Superb
$N$-triangle with the same structure as $q$ has a smaller trace
than $p$; hence, $p$ is {\em not} Perfect.\footnote{Of course,
{}from Appendix~\ref{ap:perfects}, we know $p$ is not Perfect.}
Finally, we remark that, as a consequence of the conjugate
symmetry, analagous results must hold for the region ${x_1 >
1/2}$. If any of the other elementary differences exceed $1/2$;
i.e., ${x_{j+1} - x_j > 1/2}$ for some $j$ satisfying ${1 \le j
\le N-1}$, then again we would expect that the irregularity is not
particularly large. In this situation, one can show that no
vertices (and hence, certainly no local maxima) can exist.
\label{se:recur}
\end{section}
\begin{section}{Upper Bounds on $D_N$ and the VG-Algorithm}
\reset
\begin{subsection}{An Exponential Bound}
Because $D_N$ is, by definition, the minimal trace attained
among all Good $N$-triangles, the trace of any particular Good
$N$-triangle which can be exhibited is an upper bound on $D_N$. As
will be detailed in Section~\ref{su:vga}, for a fixed value of
$N$, there is a simple algorithm for producing a large supply of
Good $N$-triangles. However, this algorithm does not readily yield
an explicit formula for the dependence of the trace on $N$, and
consequently, an analytical bound on $D_N$. Thus, there are really
two issues at hand: (1) finding an analytical bound on $D_N$ which
is valid for all $N$ and (2) for a fixed value of $N$, exhibiting
an $N$-triangle whose trace is as near minimal as possible.
Section~\ref{su:vga} addresses the second problem.
In order to solve the first problem, one must find an algorithm
which yields Good $N$-triangles for every $N$, and for which an
explicit formula for the trace can be produced. Perhaps the
simplest such algorithm is to proceed sequentially assigning to
each generator the integer one greater than the sum of all of the
previous ones. This procedure, as illustrated by
Figure~\ref{fi:exp}, yields the following simple theorem and
corollary:
\begin{theorem}
The $N$-triangle with generator
\begin{equation}
p_k = 2^k,\qquad 0 \le k \le N
\end{equation}
is Good.
\label{th:exp}
\end{theorem}
\begin{figure}[tb]
\begin{displaymath}
\begin{array}{rrrrrr}
1 & & & & & \\
& 3 & & & & \\
2 & & 7 & & & \\
& 6 & & 15 & & \\
4 & & 14 & & 31 & \\
& 12 & & 30 & & \ddots \\
8 & & 28 & & & \\
& 24 & & \ddots & & \\
16 & & & & & \\
& \ddots & & & &
\end{array}
\end{displaymath}
\caption{$N$-triangle Expansion for Theorem \protect\ref{th:exp}}
\label{fi:exp}
\end{figure}
\begin{corollary}
\begin{equation}
D_N \le 2^{N+1}-1.
\end{equation}
\end{corollary}
As might be expected, one can do much better than this
exponential bound.
\end{subsection}
\begin{subsection}{Cubic Bounds}
We here prove an analytical bound on $D_N$ which is cubic
in $N$. The idea is to use a generator consisting of
linearly-ordered consecutive integers with the smallest integer
chosen so as to guarantee that the $N$-triangle is Good. This
procedure yields the following theorem:
\begin{theorem}
The $N$-triangle with generator
\begin{equation}
p_k = a + k,\qquad 0 \le k \le N
\label{eq:cubic1}
\end{equation}
is Good provided that $a > N^2 / 4$.
\label{th:cubic1}
\end{theorem}
\begin{figure}[tb]
\begin{displaymath}
\begin{array}{llllll}
a & & & & & \\
& 2a+1 & & & \\
a+1 & & 3a+3 & & & \\
& 2a+3 & & & & \\
a+2 & & & & & \\
& & & & & \\
\vdots & \vdots & \vdots & \cdots & & (N+1)(a+N/2) \\
& & & & & \\
a+N-2 & & & & & \\
& 2a+2N-3 & & & & \\
a+N-1 & & 3a+3N-3 & & & \\
& 2a+2N-1 & & & & \\
a+N & & & & &
\end{array}
\end{displaymath}
\caption{$N$-triangle Expansion for Theorem
\protect\ref{th:cubic1}}
\label{fi:cubic1}
\end{figure}
\beginproof
The $N$-triangle expansion of the generator~(\ref{eq:cubic1})
is shown in Figure~\ref{fi:cubic1}. Define $m_j$ and $M_j$ to be
respectively the smallest and largest elements in the $j^{\rm th}$
column ($0 \le j \le N$) of this $N$-triangle. Then the
$N$-triangle will be Good provided that $a$ can be chosen to
guarantee that $m_j-M_{j-1}$ is strictly positive for $1 \le j \le
N$. From Figure~\ref{fi:cubic1}, it is easy to see that $m_j =
p_{0,j}$ and
$M_j = p_{N-j,N}$. A simple calculation then gives
\begin{equation}
m_j = (j+1)(a + j/2)
\end{equation}
and
\begin{equation}
M_j = (j+1)(a + N - j/2),
\label{eq:M_j}
\end{equation}
so that
\begin{equation}
m_j - M_{j-1} = a - j(N-j).
\end{equation}
By elementary calculus, the right-hand side cannot be any smaller
than when $j=N/2$, so
\begin{equation}
m_j - M_{j-1} \ge a - N^2/4.
\end{equation}
Thus choosing $a > N^2 / 4$ guarantees that the $N$-triangle
is Good. \endproof
\begin{figure}[tb]
\begin{displaymath}
\begin{array}{rrrrrrrrrrr}
26 & & & & & & & & & & \\
& 53 & & & & & & & & & \\
27 & & 81 & & & & & & & & \\
& 55 & & 110 & & & & & & & \\
28 & & 84 & & 140 & & & & & & \\
& 57 & & 114 & & 171 & & & & & \\
29 & & 87 & & 145 & & 203 & & & & \\
& 59 & & 118 & & 177 & & 236 & & & \\
30 & & 90 & & 150 & & 210 & & 270 & & \\
& 61 & & 122 & & 183 & & 244 & & 305 & \\
31 & & 93 & & 155 & & 217 & & 279 & & 341 \\
& 63 & & 126 & & 189 & & 252 & & 315 & \\
32 & & 96 & & 160 & & 224 & & 288 & & \\
& 65 & & 130 & & 195 & & 260 & & & \\
33 & & 99 & & 165 & & 231 & & & & \\
& 67 & & 134 & & 201 & & & & & \\
34 & & 102 & & 170 & & & & & & \\
& 69 & & 138 & & & & & & & \\
35 & & 105 & & & & & & & & \\
& 71 & & & & & & & & & \\
36 & & & & & & & & & &
\end{array}
\end{displaymath}
\caption{Example ($N=10$) of Theorem \protect\ref{th:cubic1}}
\label{fi:cubic1_ex}
\end{figure}
Figure~\ref{fi:cubic1_ex} illustrates an application of this
theorem for $N=10$ with the smallest possible choice of $a$. Note
that this results in an $N$-triangle with $N+1$ independent
occurrences of the index --- $N$ times within the generator and
once between 170 and 171.
A direct consequence of Theorem~\ref{th:cubic1} is that
\begin{corollary}
\begin{equation}
D_N \le (N+1) \Bigg\{ \left\lceil \frac{N^2}{4} \right\rceil +
\frac{N}{2} \Bigg\};
\end{equation}
\label{co:cubic1}
\end{corollary}
therefore, $D_N$ is bounded above by a cubic polynomial in $N$.
The following theorem demonstrates that the coefficient of $N^3$
in this bound can be improved somewhat. Again, a generator
composed of consecutive integers is used, but now these integers
are mixed up ``as much as possible'' rather than linearly ordered.
The priced paid for this improved bound is a slightly more
complicated proof.
\begin{theorem}
The $N$-triangle with generator
\begin{equation}
p_k = \left\{
\begin{array}{ll}
a + 2k, & \mbox{$0 \le k \le N/2$} \\
\noalign{\vskip 0.25cm}
a + 2(N-k) + 1, & \mbox{$N/2 < k \le N$}
\end{array}
\right.
\label{eq:cubic2}
\end{equation}
is Good provided that $a > (2N-1)^2 / 24$.
\label{th:cubic2}
\end{theorem}
\begin{figure}[tb]
\begin{displaymath}
\begin{array}{llllll}
a & & & & & \\
& 2a+2 & & & \\
a+2 & & 3a+6 & & & \\
& 2a+6 & & & & \\
a+4 & & & & & \\
& & & & & \\
\vdots & \vdots & \vdots & \cdots & & (N+1)(a+N/2) \\
& & & & & \\
a+5 & & & & & \\
& 2a+8 & & & & \\
a+3 & & 3a+9 & & & \\
& 2a+4 & & & & \\
a+1 & & & & &
\end{array}
\end{displaymath}
\caption{$N$-triangle Expansion for Theorem
\protect\ref{th:cubic2}}
\label{fi:cubic2}
\end{figure}
\beginproof
The $N$-triangle expansion of the generator~(\ref{eq:cubic2})
is shown in Figure~\ref{fi:cubic2}. The same strategy will be
adopted which was used to prove the previous theorem. Define $m_j$
and $M_j$ as before. Again, as can be seen from
Figure~\ref{fi:cubic2}, $m_j = p_{0,j}$ and a simple calculation
gives
\begin{equation}
m_j = \left\{
\begin{array}{ll}
(j+1)(a+j), & \mbox{$0 \le j \le N/2$} \\
\noalign{\vskip 0.25cm}
(j+1)a + (N+1)N/2 - (N-j)^2, & \mbox{$N/2 < j \le N$}
\end{array}
\right..
\label{eq:m_j}
\end{equation}
The largest element of each column of the $N$-triangle expansion
of Figure~\ref{fi:cubic2} occurs roughly in the middle of that
column. Explicit formulas for the indices of this element (which
attains $M_j$) are tedious and unnecessary, as it is evident that
$M_j$ is just the sum of the $j+1$ largest elements in the
generator; and thus, it is again given by~(\ref{eq:M_j}).
First assume that $1 \le j \le N/2$; i.e., $m_j$ is given by the
first part of~(\ref{eq:m_j}). In this case
\begin{equation}
m_j - M_{j-1} = a - \frac{1}{2}[(2N-1)j-3j^2].
\end{equation}
By elementary calculus, the right-hand side cannot be any smaller
than when $j=(2N-1)/6$, so
\begin{equation}
m_j - M_{j-1} \ge a - (2N-1)^2/24.
\end{equation}
Thus choosing $a > (2N-1)^2/24$ guarantees that $m_j - M_{j-1}$
is strictly positive for $1 \le j \le N/2$. It remains to be shown
that the same condition will also guarantee that $m_j - M_{j-1}$
is strictly positive for
$N/2 < j \le N$; i.e., when $m_j$ is given by the second part
of~(\ref{eq:m_j}). In this case
\begin{equation}
m_j - M_{j-1} = a - \frac{1}{2}[j^2-(2N-1)j+N(N-1)].
\end{equation}
\endproof
\begin{figure}[tb]
\begin{displaymath}
\begin{array}{rrrrrrrrrrr}
16 & & & & & & & & & & \\
& 34 & & & & & & & & & \\
18 & & 54 & & & & & & & & \\
& 38 & & 76 & & & & & & & \\
20 & & 60 & & 100 & & & & & & \\
& 42 & & 84 & & 126 & & & & & \\
22 & & 66 & & 110 & & 151 & & & & \\
& 46 & & 92 & & 135 & & 174 & & & \\
24 & & 72 & & 117 & & 158 & & 195 & & \\
& 50 & & 97 & & 140 & & 179 & & 214 & \\
26 & & 75 & & 120 & & 161 & & 198 & & 231 \\
& 51 & & 98 & & 141 & & 180 & & 215 & \\
25 & & 74 & & 119 & & 160 & & 197 & & \\
& 48 & & 95 & & 138 & & 177 & & & \\
23 & & 69 & & 114 & & 155 & & & & \\
& 44 & & 88 & & 131 & & & & & \\
21 & & 63 & & 105 & & & & & & \\
& 40 & & 80 & & & & & & & \\
19 & & 57 & & & & & & & & \\
& 36 & & & & & & & & & \\
17 & & & & & & & & & &
\end{array}
\end{displaymath}
\caption{Example ($N=10$) of Theorem \protect\ref{th:cubic2}}
\label{fi:cubic2_ex}
\end{figure}
Figure~\ref{fi:cubic2_ex} illustrates an application of this
theorem for $N=10$ with the smallest possible choice of $a$. Note
that this again results in an $N$-triangle with $N+1$ independent
occurrences of the index --- $N$ times within the generator and
once between 75 and 76. The upper bound corresponding to
Theorem~\ref{th:cubic2} is given by
\begin{corollary}
\begin{equation}
D_N \le (N+1) \Bigg\{ \left\lceil \frac{(2N-1)^2}{24}
\right\rceil +
\frac{N}{2} \Bigg\}.
\end{equation}
\label{co:cubic2}
\end{corollary}
This is the best analytical bound on $D_N$ which is currently
known by this author.
\end{subsection}
\begin{subsection}{The VG-Algorithm and the Quadratic Bound
Conjecture}
As previously mentioned, finding Perfect $N$-triangles (or
Golomb rulers) is not the objective of the present work. For
completeness, however, we do present a simple algorithm for
constructing Good $N$-triangles whose trace is not too large. A
special case of this algorithm has been previously studied in
connection with the Golomb Ruler Problem. The original idea was
conceived by S.~W.~Golomb under the name of the ``midsegment
algorithm'', and later refined by D.~S.~Robertson. For an overview
and numerous examples, see reference~\cite{HT}.
The basic idea is to fill in the components of the generator in
some pre-chosen order and in such a way that, at each step, all
the $N$-triangle elements that can be calculated are distinct. We
formalize this idea by defining the {\em
VG-algorithm}\footnote{Very Good} for generating a Good
$N$-triangle.
\begin{definition}
Let $\{j_m\}_{m=0}^N$ be a permutation of $\{0, 1,\cdots,N\}$ and
define ${p \in P'_N}$ as follows. Let ${p_{j_0} = 1}$. For ${1
\le m \le N}$, proceed sequentially choosing each $p_{j_m}$ to be
the smallest integer strictly greater than $p_{j_{m-1}}$ which
guarantees that all of the $N$-triangle elements which have only
$p_{j_0}$ through $p_{j_m}$ as summands are distinct. We then say
that $p$ is generated by the \underline{VG-algorithm} using the
permutation $\{j_m\}_{m=0}^N$.
\end{definition}
Golomb's ``midsegment algorithm'' is recovered by using the
permutation
\begin{equation}
\{j_m\}_{m=0}^N = \{0,N,1,N-1,2,N-2,\cdots\}.
\label{eq:flipflop}
\end{equation}
As first noted by Golomb, the $N$-triangle generated by the
VG-algorithm using this permutation is particularly Good. In fact,
it is Perfect for ${N \le 5}$. For ${N=6}$, the VG-algorithm using
the above permutation yields a $6$-triangle with ${\trc p=36}$ as
compared to the Perfect trace ${D_6=34}$.
As an explicit example, the $10$-triangle generated by the
VG-algorithm using the permutation given by
equation~(\ref{eq:flipflop}) is shown in
Figure~\ref{fi:flipflop_ex}.
\begin{figure}[tb]
\begin{displaymath}
\begin{array}{rrrrrrrrrrr}
1 & & & & & & & & & & \\
& 4 & & & & & & & & & \\
3 & & 10 & & & & & & & & \\
& 9 & & 21 & & & & & & & \\
6 & & 20 & & 40 & & & & & & \\
& 17 & & 39 & & 64 & & & & & \\
11 & & 36 & & 63 & & 87 & & & & \\
& 30 & & 60 & & 86 & & 101 & & & \\
19 & & 54 & & 83 & & 100 & & 109 & & \\
& 43 & & 77 & & 97 & & 108 & & 114 & \\
24 & & 66 & & 91 & & 105 & & 113 & & 116 \\
& 47 & & 80 & & 99 & & 110 & & 115 & \\
23 & & 61 & & 88 & & 104 & & 112 & & \\
& 37 & & 69 & & 93 & & 106 & & & \\
14 & & 45 & & 74 & & 95 & & & & \\
& 22 & & 50 & & 76 & & & & & \\
8 & & 27 & & 52 & & & & & & \\
& 13 & & 29 & & & & & & & \\
5 & & 15 & & & & & & & & \\
& 7 & & & & & & & & & \\
2 & & & & & & & & & &
\end{array}
\end{displaymath}
\caption{Example ($N=10$) of the VG-Algorithm}
\label{fi:flipflop_ex}
\end{figure}
Note that, using this particular permutation, the $N$-triangle
generated by the VG-algorithm can be obtained from the analogous
$(N-1)$-triangle by adding a new component to the ``middle'' of
the generator. Thus, Figure~\ref{fi:flipflop_ex} also tells us
the
components of the generators of the analogous $N$-triangles for
${N \le 9}$.
The VG-algorithm is important because it gives a rich supply
of Good $N$-triangles with relatively little effort. In
applications where optimality is not necessarily needed, these
$N$-triangles may serve the required purpose. This is the
situation for the problem of constructing radar signals with
sharply peaked ambiguity functions~\cite{AG}.
The VG-algorithm is also important for the following reason.
It is easy to see that if~$p$ is an $N$-triangle generated by the
VG-Algorithm (using any permutation) then~$p$ has the vertex
property, $p$ has the index reduction property, and $\ind p = 1$.
Thus, if Conjecture~\ref{co:superb} is true then these
$N$-triangles are all Superb; and if, in addition,
Conjecture~\ref{co:eqthII} is true then they are also locally
maximal. This is most probably the case. However, the VG-algorithm
can find only ${(N+1)!/2}$ (one for each permutation modulo
conjugacy) out of a total of $S_N$ Superb
$N$-triangles.\footnote{Here, we are assuming
Conjecture~\ref{co:supuniq} is true.} Nevertheless, supported by
all known Perfect $N$-triangles, we make the following conjecture.
\begin{conjecture}
Every Perfect $N$-triangles can be generated by the VG-algorithm
using a suitable permutation.
\end{conjecture}
If this conjecture is true, one can simply apply the VG-algorithm
to each of the ${(N+1)!/2}$ permutations; those resulting
$N$-triangles with minimal trace will be the Perfect
$N$-triangles. Moreover, one may be able to eliminate certain
classes of permutations a priori by using arguments similar to
those of Section~\ref{se:recur}.
Finally, in Table~\ref{ta:D_N}, we give a summary of the various
upper bounds which have been discussed, in comparison with the
actual values of $D_N$.
\begin{table}[tb]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|} \hline
$N$ & $C_N$ & $D_N$ & Cor. \ref{co:cubic1} & Cor.
\ref{co:cubic2} & VG-Alg. &
$\lfloor 1.5 C_N \rfloor$ \\ \hline
0 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline
1 & 3 & 3 & 3 & 3 & 3 & 4 \\ \hline
2 & 6 & 6 & 9 & 6 & 6 & 9 \\ \hline
3 & 10 & 11 & 18 & 14 & 11 & 15 \\ \hline
4 & 15 & 17 & 35 & 25 & 17 & 22 \\ \hline
5 & 21 & 25 & 57 & 39 & 25 & 31 \\ \hline
6 & 28 & 34 & 91 & 63 & 36 & 42 \\ \hline
7 & 36 & 44 & 132 & 92 & 50 & 54 \\ \hline
8 & 45 & 55 & 189 & 126 & 69 & 67 \\ \hline
9 & 55 & 72 & 255 & 175 & 92 & 82 \\ \hline
10 & 66 & 85 & 341 & 231 & 116 & 99 \\ \hline
11 & 78 & 106 & 438 & 294 & 141 & 117 \\ \hline
12 & 91 & 127 & 559 & 377 & 172 & 136 \\ \hline
\end{tabular}
\caption{Comparison of Upper Bounds on $D_N$}
\label{ta:D_N}
\end{table}
We know (from Corollaries~\ref{co:LB} and~\ref{co:cubic1})
that~$D_N$ is bounded below by a quadratic in~$N$ and bounded
above by a cubic in~$N$. However, as~$D_N$ seems to be diverging
{}from the cubic bounds (and based on other analytical and empirical
evidence), we conjecture that~$D_N$ is, in fact, bounded above by
a quadratic in~$N$. Of course, for this to be true, it is
sufficient (but not necessary) for the trace of the $N$-triangle
generated by the VG-algorithm using the permutation given by
equation~(\ref{eq:flipflop}) (the sixth column in
Table~\ref{ta:D_N}) to be bounded above by a quadratic in~$N$. If
it is true, this latter assertion may be easier to prove. Without
loss of generality, we state the quadratic bound conjecture as
\begin{conjecture}
There exists some $\alpha \in \IR$ such that $D_N \le \alpha C_N$
for all
$N \in \IN$.
\label{co:quad}
\end{conjecture}
For the purpose of comparison, we tabulate this pseudo-bound for
${\alpha = 1.5}$ in the last column of Table~\ref{ta:D_N}; we do
not claim that this value of~$\alpha$ works for all $N \in \IN$.
\label{su:vga}
\end{subsection}
\label{se:ubvga}
\end{section}
\begin{section}{Conclusion and Open Problems}
\reset
To conclude, we first summarize the key results concerning the
relationship between maximizing irregularity
(Problem~\ref{pr:max_F}) and the Golomb Ruler Problem
(Problem~\ref{pr:PNP}). We then collect into one place the many
interesting unresolved issues which have arisen, and supplement
them with a few miscellaneous problems and conjectures.
A summary of the main results contained herein can conveniently
be organized around the following four assertions, which we will
call the {\em {$X$--$P$} equivalence theorems}:
\begin{enumerate}
\item $T(X_N) \approx P_N$ (Theorem~\ref{th:eqth0})
\item $T(X'_N) \approx P'_N$ (Theorem~\ref{th:eqthI})
\item $T(X''_N) \approx P''_N$ (Conjecture~\ref{co:eqthII})
\item $T(X'''_N) \approx P'''_N$ (Conjecture~\ref{co:eqthIII}).
\end{enumerate}
The first step in the analysis was to map the study of the
continuous irregularity function $F_N(x)$ onto the study of
discrete $N$-triangles (or ``rulers'' in the terminology of the
Golomb Ruler Problem). The first {$X$--$P$} equivalence theorem
says that $X_N$, the natural domain of $F_N(x)$, can be mapped
bijectively onto ($\approx$-equivalence classes of) $P_N$, the
space of $N$-triangles. Together with equation~(\ref{eq:funfac}),
which provides an explicit formula for calculating $F_N(x)$
directly from ${p = T(x)}$, this theorem allows one to translate
any statement about $F_N(x)$ into an equivalent statement about
$N$-triangles (and vice versa).
The second {$X$--$P$} equivalence theorem is a trivial
consequence of the first. It says that an $N$-triangle ${p =
T(x)}$ is Good (i.e., all its elements are distinct) if and only
if ${F_N(x) > 0}$. Although trivial to prove, this theorem is
important for two reasons. Firstly, many statements about $F_N(x)$
are more naturally formulated on ${X'_N \equiv \{ x \in X_N \mid
F_N(x) > 0 \}}$ than $X_N$; and similarly, many statements about
$N$-triangles are more naturally formulated on ${P'_N \equiv \{ p
\in P_N \mid p {\rm\ is\ Good} \}}$ than $P_N$. Secondly, it
serves as a simple prelude for the more substantial {$X$--$P$}
equivalence theorems which follow.
The fourth {$X$--$P$} equivalence theorem is an abstract
statement of the assertion that maximizing irregularity and
finding Golomb rulers are equivalent problems. It says that an
$N$-triangle ${p = T(x)}$ is Perfect (i.e., it is a Golomb ruler)
if and only if $F_N(x)$ attains a global maximum at the point~$x$.
This is precisely what we want to prove; however, we have been
completely successful only for $N \le 4$. For the general case, we
have focused instead on the stronger assertion given by the third
{$X$--$P$} equivalence theorem.
The third {$X$--$P$} equivalence theorem is a localized
version of the fourth. In order to achieve this localization, we
defined {\em structure} equivalence classes of~$P_N$ which
correspond (via the $N$-triangle bijection~$T$) to open polyhedral
regions of~$X_N$ on which $F_N(x)$ is strictly positive and
concave. The third {$X$--$P$} equivalence theorem says that an
$N$-triangle ${p = T(x)}$ is Superb (i.e., it is a Golomb ruler
{\em relative to a particular structure equivalence class}) if and
only if $F_N(x)$ attains a {\em local} maximum at the point~$x$.
Therefore, the third {$X$--$P$} equivalence theorem is much
stronger than what we originally set out to prove; it implies the
fourth {$X$--$P$} equivalence theorem.
Nevertheless, for the following reasons, the third {$X$--$P$}
equivalence theorem has been the focal point of the present work.
First, all empirical evidence indicates that it is true, thus
suggesting that the issue in question is more closely related to
local maximality than global maximality. Secondly, as has been
demonstrated, the methods of convex analysis and linear
programming can be applied to the localized version, thus allowing
us to obtain a deeper understanding of it content as compared to
the global version. This deeper understanding is manifested by the
similarity between Theorems~\ref{th:ILP} and~\ref{th:LP}, which,
in turn, gives us the additional proposition in
Theorem~\ref{th:4prop} as compared to Theorem~\ref{th:3prop}. This
additional proposition --- which relates the third {$X$--$P$}
equivalence theorem to the theory of integral polyhedra --- leads
directly to a deeper understanding of the continuous irregularity
function $F_N(x)$, as reflected by Theorem~\ref{th:chi}. Finally,
though we do not actually succeed in proving the third {$X$--$P$}
equivalence theorem, we are able to tie it logically to more
traditional mathematical assertions, like Conjectures~\ref{co:spi}
and~\ref{co:smuni}.
We conclude with a list of open problems. First, we have
Conjectures~{1--10} which are given throughout the paper. The
proofs of these conjectures are likely to range from easy
(Conjecture~\ref{co:stri}) to difficult
(Conjecture~\ref{co:vertex}). It is important to keep in mind that
many of these are logically interdependent, especially those in
Section~\ref{se:spvp}. Although all have been tested to some
extent, they do carry differing degrees of conviction. For
example, it is strongly believed that Conjectures~\ref{co:supuniq}
and~\ref{co:spi} are true, which, in turn, implies that
Conjecture~\ref{co:eqthII} (and hence Conjecture~\ref{co:eqthIII})
is true. On the other hand,
Conjectures~{\ref{co:vertex}--\ref{co:quad}} are more speculative.
In addition to these formal conjectures, we have mentioned
the following three problems.
\begin{enumerate}
\item For fixed~$N$, determine the largest value of~$M$ that
can be attained in Theorem~\ref{th:strucmat}. In other words,
what
is the maximum number of consecutive independent pairs of
elements
that any Good $N$-triangle can have?
\item For fixed $N$, find a complete characterization of
the class of structure matrices.
\item Determine $S_N$ for $N \ge 4$ and/or its asymptotic
behavior.
\end{enumerate}
The first problem is relatively easy; whereas, the second
is likely to be difficult. The third problem is purely
combinatorial; the next few values of $S_N$ should be easily
accessible by computer. Another interesting problem is to
determine the distribution of those points in $X_N$ whose
corresponding $N$-triangles have unit index. Preliminary
investigations for ${N=2}$ have been quite intriguing.
Thirdly, we have the following miscellaneous conjecture.
\begin{conjecture}
Suppose ${p \in P_N}$ and ${\ind p \ge 2}$. Then, for some
${q,r \in P_N}$, $p$ can be decomposed as ${p = q + r}$, where
${\ind q = \ind p - 1}$ and ${\ind r = 1}$.
\end{conjecture}
This is an example of an ``algebraic'' assertion about
$N$-triangles, in the sense that it has nothing do with maximizing
irregularity or Golomb Rulers, at least on the surface. Many
interesting conjectures of this type can be formulated. This one
is particularly interesting in that it actually implies
Conjecture~\ref{co:eqthIII} without implying
Conjecture~\ref{co:eqthII}. It is easy to prove for ${N=1}$ and
no
counter examples have yet been found for ${N \ge 2}$.
Finally, of course, we have the problem of actually finding
Perfect $N$-Triangles (Golomb rulers) for ${N \ge 12}$. This
problem is discussed in more detail in the
references~\cite{HT,AKD}. We also have the closely related
problem of determining $D_N$ and/or the number of distinct Perfect
$N$-triangles (as a function of $N$) either exactly or
asymptotically. The present work may stimulate further progress in
this direction, at least for the asymptotic results.
\end{section}
\appendix
\renewcommand{\theequation}{\thesection.\arabic{equation}}
\newcommand{\reseteq}{\setcounter{equation}{0}}
\clearpage
\begin{section}{Perfect $N$-Triangles for $N \le 9$}
\reset\reseteq
\setlength{\unitlength}{1.0cm}
\begin{picture}(14.0,20.0)
\put(1.5,19.5){\underline{$N=1$}}
\put(1.5,18.0){$
\begin{array}{rr}
1 & \\
& 3 \\
2 &
\end{array}
$}
\put(10.0,19.5){\underline{$N=2$}}
\put(10.0,17.5){$
\begin{array}{rrr}
1 & & \\
& 4 & \\
3 & & 6 \\
& 5 & \\
2 & &
\end{array}
$}
\put(1.5,15.0){\underline{$N=3$}}
\put(1.5,12.5){$
\begin{array}{rrrr}
1 & & & \\
& 4 & & \\
3 & & 9 & \\
& 8 & & 11 \\
5 & & 10 & \\
& 7 & & \\
2 & & &
\end{array}
$}
\put(10.0,12.5){$
\begin{array}{rrrr}
2 & & & \\
& 7 & & \\
5 & & 8 & \\
& 6 & & 11 \\
1 & & 9 & \\
& 4 & & \\
3 & & &
\end{array}
$}
\put(1.5,9.0){\underline{$N=4$}}
\put(1.5,6.0){$
\begin{array}{rrrrr}
1 & & & & \\
& 4 & & & \\
3 & & 10 & & \\
& 9 & & 15 & \\
6 & & 14 & & 17 \\
& 11 & & 16 & \\
5 & & 13 & & \\
& 7 & & & \\
2 & & & &
\end{array}
$}
\put(10.0,6.0){$
\begin{array}{rrrrr}
1 & & & & \\
& 4 & & & \\
3 & & 10 & & \\
& 9 & & 12 & \\
6 & & 11 & & 17 \\
& 8 & & 16 & \\
2 & & 13 & & \\
& 7 & & & \\
5 & & & &
\end{array}
$}
\put(1.5,0.5){$
\begin{array}{rrrrr}
1 & & & & \\
& 8 & & & \\
7 & & 11 & & \\
& 10 & & 13 & \\
3 & & 12 & & 17 \\
& 5 & & 16 & \\
2 & & 9 & & \\
& 6 & & & \\
4 & & & &
\end{array}
$}
\put(10.0,0.5){$
\begin{array}{rrrrr}
1 & & & & \\
& 8 & & & \\
7 & & 12 & & \\
& 11 & & 14 & \\
4 & & 13 & & 17 \\
& 6 & & 16 & \\
2 & & 9 & & \\
& 5 & & & \\
3 & & & &
\end{array}
$}
\end{picture}
\clearpage
\begin{picture}(14.0,20.0)
\put(1.0,18.0){\underline{$N=5$}}
\put(1.0,14.5){$
\begin{array}{rrrrrr}
1 & & & & & \\
& 4 & & & & \\
3 & & 10 & & & \\
& 9 & & 18 & & \\
6 & & 17 & & 23 & \\
& 14 & & 22 & & 25 \\
8 & & 19 & & 24 & \\
& 13 & & 21 & & \\
5 & & 15 & & & \\
& 7 & & & & \\
2 & & & & &
\end{array}
$}
\put(9.0,14.5){$
\begin{array}{rrrrrr}
1 & & & & & \\
& 11 & & & & \\
10 & & 16 & & & \\
& 15 & & 19 & & \\
5 & & 18 & & 23 & \\
& 8 & & 22 & & 25 \\
3 & & 12 & & 24 & \\
& 7 & & 14 & & \\
4 & & 9 & & & \\
& 6 & & & & \\
2 & & & & &
\end{array}
$}
\put(1.0,8.0){$
\begin{array}{rrrrrr}
1 & & & & & \\
& 7 & & & & \\
6 & & 11 & & & \\
& 10 & & 20 & & \\
4 & & 19 & & 23 & \\
& 13 & & 22 & & 25 \\
9 & & 16 & & 24 & \\
& 12 & & 18 & & \\
3 & & 14 & & & \\
& 5 & & & & \\
2 & & & & &
\end{array}
$}
\put(9.2,8.0){$
\begin{array}{rrrrrr}
2 & & & & & \\
& 3 & & & & \\
1 & & 10 & & & \\
& 8 & & 16 & & \\
7 & & 14 & & 21 & \\
& 13 & & 19 & & 25 \\
6 & & 18 & & 23 & \\
& 11 & & 22 & & \\
5 & & 15 & & & \\
& 9 & & & & \\
4 & & & & &
\end{array}
$}
\put(5.0,1.5){$
\begin{array}{rrrrrr}
2 & & & & & \\
& 7 & & & & \\
5 & & 13 & & & \\
& 11 & & 21 & & \\
6 & & 19 & & 22 & \\
& 14 & & 20 & & 25 \\
8 & & 15 & & 23 & \\
& 9 & & 18 & & \\
1 & & 12 & & & \\
& 4 & & & & \\
3 & & & & &
\end{array}
$}
\end{picture}
\clearpage
\begin{picture}(14.0,20.0)
\put(0.0,18.0){\underline{$N=6$}}
\put(0.0,14.5){$
\begin{array}{rrrrrrr}
1 & & & & & & \\
& 4 & & & & & \\
3 & & 9 & & & & \\
& 8 & & 15 & & & \\
5 & & 14 & & 22 & & \\
& 11 & & 21 & & 32 & \\
6 & & 18 & & 31 & & 34 \\
& 13 & & 28 & & 33 & \\
7 & & 23 & & 30 & & \\
& 17 & & 25 & & & \\
10 & & 19 & & & & \\
& 12 & & & & & \\
2 & & & & & &
\end{array}
$}
\put(8.0,18.0){\underline{$N=7$}}
\put(8.0,14.0){$
\begin{array}{rrrrrrrr}
1 & & & & & & & \\
& 5 & & & & & & \\
4 & & 12 & & & & & \\
& 11 & & 25 & & & & \\
7 & & 24 & & 27 & & & \\
& 20 & & 26 & & 35 & & \\
13 & & 22 & & 34 & & 41 & \\
& 15 & & 30 & & 40 & & 44 \\
2 & & 23 & & 36 & & 43 & \\
& 10 & & 29 & & 39 & & \\
8 & & 16 & & 32 & & & \\
& 14 & & 19 & & & & \\
6 & & 17 & & & & & \\
& 9 & & & & & & \\
3 & & & & & & &
\end{array}
$}
\put(4.0,7.0){\underline{$N=8$}}
\put(4.0,2.5){$
\begin{array}{rrrrrrrrr}
1 & & & & & & & & \\
& 6 & & & & & & & \\
5 & & 10 & & & & & & \\
& 9 & & 23 & & & & & \\
4 & & 22 & & 26 & & & & \\
& 17 & & 25 & & 34 & & & \\
13 & & 20 & & 33 & & 41 & & \\
& 16 & & 28 & & 40 & & 53 & \\
3 & & 24 & & 35 & & 52 & & 55 \\
& 11 & & 31 & & 47 & & 54 & \\
8 & & 18 & & 43 & & 49 & & \\
& 15 & & 30 & & 45 & & & \\
7 & & 27 & & 32 & & & & \\
& 19 & & 29 & & & & & \\
12 & & 21 & & & & & & \\
& 14 & & & & & & & \\
2 & & & & & & & &
\end{array}
$}
\end{picture}
\clearpage
\begin{picture}(14.0,20.0)
\put(2.0,18.0){\underline{$N=9$}}
\put(2.0,13.0){$
\begin{array}{rrrrrrrrrr}
1 & & & & & & & & & \\
& 4 & & & & & & & & \\
3 & & 13 & & & & & & & \\
& 12 & & 28 & & & & & & \\
9 & & 27 & & 33 & & & & & \\
& 24 & & 32 & & 47 & & & & \\
15 & & 29 & & 46 & & 54 & & & \\
& 20 & & 43 & & 53 & & 64 & & \\
5 & & 34 & & 50 & & 63 & & 70 & \\
& 19 & & 41 & & 60 & & 69 & & 72 \\
14 & & 26 & & 51 & & 66 & & 71 & \\
& 21 & & 36 & & 57 & & 68 & & \\
7 & & 31 & & 42 & & 59 & & & \\
& 17 & & 37 & & 44 & & & & \\
10 & & 23 & & 39 & & & & & \\
& 16 & & 25 & & & & & & \\
6 & & 18 & & & & & & & \\
& 8 & & & & & & & & \\
2 & & & & & & & & &
\end{array}
$}
\put(2.0,2.5){$
\begin{array}{rrrrrrrrrr}
1 & & & & & & & & & \\
& 9 & & & & & & & & \\
8 & & 19 & & & & & & & \\
& 18 & & 24 & & & & & & \\
10 & & 23 & & 31 & & & & & \\
& 15 & & 30 & & 52 & & & & \\
5 & & 22 & & 51 & & 56 & & & \\
& 12 & & 43 & & 55 & & 58 & & \\
7 & & 33 & & 47 & & 57 & & 69 & \\
& 28 & & 37 & & 49 & & 68 & & 72 \\
21 & & 32 & & 39 & & 60 & & 71 & \\
& 25 & & 34 & & 50 & & 63 & & \\
4 & & 27 & & 45 & & 53 & & & \\
& 6 & & 38 & & 48 & & & & \\
2 & & 17 & & 41 & & & & & \\
& 13 & & 20 & & & & & & \\
11 & & 16 & & & & & & & \\
& 14 & & & & & & & & \\
3 & & & & & & & & &
\end{array}
$}
\end{picture}
\label{ap:perfects}
\end{section}
\begin{section}{Proof of Conjecture~\protect\ref{co:eqthIII}
for $N \le 4$}
\reset\reseteq
We first develop a few general results, after which, the cases
$N=1$ and $N=2$ will follow immediately.\footnote{That
Conjecture~\ref{co:eqthIII} holds for these trivial cases should
come as no surprise --- the existence of a unique global maximum
corresponding to the unique Perfect $N$-triangle (on the
conjugate-free ordered-$x$ simplex) is apparent in
Figures~\ref{fi:F_1} and~\ref{fi:F_2}.} The case $N=3$ will then
be proved completely and the case $N=4$ will be outlined. The
detailed treatment of the case $N=4$ is quite involved; the
generalization to $N=5$ is not immediately apparent.
We take as a starting point the form of
Conjecture~\ref{co:eqthIII} given by the second proposition in
Theorem~\ref{th:3prop}. We abbreviate this as
\begin{equation}
p = k q,\quad q \in P'''_N \Longleftrightarrow
p \in T(X'''_N),
\label{eq:prop1}
\end{equation}
where throughout this section, we assume $k$ is some positive
integer. We wish to develop another equivalent form of this
proposition which will be easier to prove.
First, from Corollary~\ref{co:pi1-1} and
Theorem~\ref{th:trivial}, we know that if $q \in P'''_N$ and
$p =
k q$ then $p$ has irregularity $D_N^{-1}$. It follows
that~(\ref{eq:prop1}) is equivalent to
\begin{equation}
p \ne k q,\quad q \in P'''_N \Longrightarrow
\frac{\ind p}{\trc p} < \frac{1}{D_N}.
\label{eq:prop2}
\end{equation}
Secondly, we remark that the inequality on the right-hand side
of~(\ref{eq:prop2}) is equivalent to
\begin{equation}
\trc p \le k' D_N \Longrightarrow \ind p < k'.
\label{eq:lemma}
\end{equation}
Moreover, without loss of generality, the left-hand side
of~(\ref{eq:lemma}) may be replaced by
\begin{equation}
(k'-1) D_N < \trc p \le k' D_N .
\end{equation}
This defines $k'$ uniquely for any given $p \in P_N$. If $p$
satisfies this inequality and $p = k q$ with $q \in P'''_N$ then
the only possibility is that
$k = k'$. It follows that~(\ref{eq:prop2}) is equivalent to
\begin{equation}
\left.
\begin{array}{c}
(k-1) D_N < \trc p \le k D_N \\
\noalign{\vskip 5pt}
p \ne k q,\quad q \in P'''_N
\end{array}
\right\} \Longrightarrow \ind p < k.
\end{equation}
This is the form in which we will prove
Conjecture~\ref{co:eqthIII}. If
$\trc p \le D_N$ and $p$ is not Perfect then (by the definition
of $D_N$)
$\ind p = 0$. Therefore, we may assume $k \ge 2$. We now commence
with the proof proper by using the method of {\em reductio ad
absurdum}.
Let $p \in P_N$ and suppose
\begin{equation}
\begin{array}{l}
(k-1) D_N < \trc p \le k D_N,\quad k \ge 2; \\
\noalign{\vskip 5pt}
p \ne k q,\quad q \in P'''_N; \\
\noalign{\vskip 5pt}
\ind p \ge k.
\end{array}
\label{eq:assume}
\end{equation}
Define $q$ and $r$ to be the quotient and remainder
(respectively) resulting from the division of $p$ by $k$; i.e.,
for ${0 \le j \le N}$, put ${q_j = \lfloor p_j / k \rfloor}$ and
${r_j = p_j - k q_j}$ so that
\begin{equation}
p_j = k q_j + r_j,\quad 0 \le r_j \le k-1.
\end{equation}
{}From the assumptions~(\ref{eq:assume}), it follows that neither
$q$ nor $r$ can be identically zero; therefore, $q \in P_N$ and
$r \in P_N$. We then have
\begin{equation}
\trc p = k\,\trc q + \trc r \le k D_N.
\label{eq:trcp}
\end{equation}
This, in turn, implies
\begin{equation}
\trc q < D_N
\label{eq:trace_q}
\end{equation}
so that $q$ is {\em not} Good. Nevertheless, $q$ cannot be too
bad in the following sense.
Let $\{j_m\}_{m=0}^N$ be a permutation of $\{0, 1,\cdots,N\}$
such that
\begin{equation}
p_{j_0} < p_{j_1} < \cdots < p_{j_N}.
\end{equation}
Then, for ${1 \le m \le N}$,\footnote{For completeness,
this and all similar arguments should also be applied to the
special case obtained by making the replacement ${p_{j_m} -
p_{j_{m-1}}} \rightarrow p_{j_0}$.}
\begin{equation}
k \le \ind p \le p_{j_m} - p_{j_{m-1}} = k (q_{j_m} -
q_{j_{m-1}}) +
(r_{j_m} - r_{j_{m-1}}).
\label{eq:dpi1}
\end{equation}
So
\begin{equation}
q_{j_m} - q_{j_{m-1}} \ge 1 - \frac{r_{j_m} - r_{j_{m-1}}}{k}
\ge
1 - \frac{k-1}{k} > 0.
\end{equation}
In other words, the components of the generator of $q$ are
distinct positive integers with the same relative ordering as the
components of the generator of $p$.
At this point, we can obtain an absurdity (and thus conclude
the proof) for the cases $N=1$ and $N=2$. Recall that for these
two cases, $D_N = C_N$; hence, (\ref{eq:trace_q}) becomes $\trc q
< C_N$. On the other hand, if the components of the generator of
$q$ are distinct positive integers then $\trc q \ge C_N$. Thus
the existence of $q$ is absurd.
The reason that Conjecture~\ref{co:eqthIII} can be proved for
$N=3$ and $N=4$ is that the number of possibilities for $q$ is
relatively small, and each leads to an absurdity. Our basic
strategy for uncovering this absurdity is as follows. Since $q$ is
not Good, we can find {\em independent} (see
Definition~\ref{de:indep}) elements $q_{i,j}$ and $q_{i',j'}$
satisfying ${q_{i,j} = q_{i',j'}}$, in which case
\begin{equation}
|p_{i,j}- p_{i',j'}| = |r_{i,j}- r_{i',j'}|.
\label{eq:dpdr}
\end{equation}
We will then show ${|r_{i,j}- r_{i',j'}| \le k-1}$, which
contradicts the assumption that $\ind p \ge k$.
Consider $N=3$. As the components of the generator of $q$ must
be distinct positive integers satisfying ${\trc q < D_3 = 11}$,
the only possibility is a permutation of $\{1,2,3,4\}$. Therefore
${q_{j_m} - q_{j_{m-1}} = 1}$ and (\ref{eq:dpi1}) implies
${r_{j_m} - r_{j_{m-1}} \ge 0}$, or more explicitly
\begin{equation}
0 \le r_{j_0} \le r_{j_1} \le r_{j_2} \le r_{j_3} \le k-1.
\label{eq:ares3}
\end{equation}
We now consider three exhaustive (but non-mutually exclusive)
cases.
\begin{description}
\item{\underline{Case Ia: $p_{j_0}$ and $p_{j_1}$ are adjacent}}
For some $p_{i,j}$ (with $j=i$) and some $p_{i',j'}$
(with $j'=i'+1$) we have ${p_{i,j} = p_{j_2}}$ and ${p_{i',j'} =
p_{j_0} + p_{j_1}}$. Since ${q_{j_2} - q_{j_0} - q_{j_1} = 0}$
and~(\ref{eq:ares3}) gives ${0 \le r_{j_2} - r_{j_1} \le k-1}$ and
${0 \le r_{j_0} \le k-1}$, it follows that
\begin{equation}
|p_{i,j}-p_{i',j'}| = |(r_{j_2} - r_{j_1}) - r_{j_0}| \le k-1.
\end{equation}
This contradicts the assumption that $\ind p \ge k$.
\item{\underline{Case Ib: $p_{j_0}$ and $p_{j_2}$ are adjacent}}
For some $p_{i,j}$ (with $j=i$) and some $p_{i',j'}$
(with $j'=i'+1$) we have ${p_{i,j} = p_{j_3}}$ and ${p_{i',j'} =
p_{j_0} + p_{j_2}}$. Since ${q_{j_3} - q_{j_0} - q_{j_2} = 0}$
and~(\ref{eq:ares3}) gives ${0 \le r_{j_3} - r_{j_2} \le k-1}$ and
${0 \le r_{j_0} \le k-1}$, it follows that
\begin{equation}
|p_{i,j}-p_{i',j'}| = |(r_{j_3} - r_{j_2}) - r_{j_0}| \le k-1.
\end{equation}
This contradicts the assumption that $\ind p \ge k$.
\item{\underline{Case Ic: $p_{j_0}$ and $p_{j_3}$ are adjacent
{\em and}
$p_{j_1}$ and $p_{j_2}$ are adjacent}}
For some $p_{i,j}$ (with $j=i+1$) and some $p_{i',j'}$ (with
$j'=i'+1$) we have ${p_{i,j} = p_{j_1} + p_{j_2}}$ and ${p_{i',j'}
= p_{j_0} + p_{j_3}}$. Since ${q_{j_1} + q_{j_2} - q_{j_0} -
q_{j_3} = 0}$ and~(\ref{eq:ares3}) gives $0 \le r_{j_1} - r_{j_0}
\le k-1$ and ${0 \le r_{j_3} - r_{j_2} \le k-1}$, it follows that
\begin{equation}
|p_{i,j}-p_{i',j'}| = |(r_{j_1} - r_{j_0}) - (r_{j_3} -
r_{j_2})| \le k-1.
\end{equation}
This contradicts the assumption that $\ind p \ge k$.
\end{description}
This concludes the proof for $N=3$.
Now consider $N=4$. In this case, the components of the generator
of $q$ must be distinct positive integers satisfying ${\trc q <
D_4 = 17}$; therefore, $q$ is either a permutation of
$\{1,2,3,4,5\}$ or a permutation of $\{1,2,3,4,6\}$. For the
first possibility, the proof can be carried out in essentially the
same way as before. The crucial point is that~(\ref{eq:dpi1})
again implies
\begin{equation}
0 \le r_{j_0} \le r_{j_1} \le r_{j_2} \le r_{j_3} \le r_{j_4}
\le k-1.
\label{eq:ares4}
\end{equation}
One possible breakdown into an exhaustive set of cases is as
follows.
\begin{description}
\item{Case Ia: $p_{j_0}$ and $p_{j_1}$ are adjacent}
\item{Case Ib: $p_{j_0}$ and $p_{j_2}$ are adjacent}
\item{Case Ic: $p_{j_0}$ and $p_{j_3}$ are adjacent}
\item{Case Id: $p_{j_1}$ and $p_{j_2}$ are adjacent}
\item{Case Ie: $p_{j_0}$ and $p_{j_4}$ are adjacent {\em and}
$p_{j_1}$ and $p_{j_3}$ are adjacent}
\end{description}
Each of these cases can be treated exactly as was done for $N=3$.
The second possibility is that $q$ is a permutation of
$\{1,2,3,4,6\}$. In this case, we have ${q_{j_4} - q_{j_3} = 2}$,
which means that~(\ref{eq:dpi1}) allows us to
conclude~(\ref{eq:ares3}) but not~(\ref{eq:ares4}). In other
words, the only thing we know about $r_{j_4}$ is that ${0 \le
r_{j_4} \le k-1}$. Again, we propose an exhaustive set of cases.
\begin{description}
\item{Case IIa: $p_{j_0}$ and $p_{j_1}$ are adjacent}
\item{Case IIb: $p_{j_0}$ and $p_{j_2}$ are adjacent}
\item{Case IIc: $p_{j_0}$ and $p_{j_3}$ are adjacent {\em and}
$p_{j_1}$ and $p_{j_2}$ are adjacent}
\item{Case IId: $p_{j_1}$ and $p_{j_3}$ are adjacent}
\item{Case IIe: $p_{j_0}$ and $p_{j_5}$ are adjacent {\em and}
$p_{j_2}$ and $p_{j_3}$ are adjacent}
\item{Case IIf: $q = (1,4,3,6,2)$ (modulo conjugacy)}
\end{description}
Cases~IIa--IIc can be treated exactly as was done for $N=3$
because, with reference to the discussion preceding
equation~(\ref{eq:dpdr}), $|p_{i,j}- p_{i',j'}|$ does not depend
on $r_{j_4}$. Cases~IId--IIf require a different argument, and we
procede as follows.
{}From~(\ref{eq:trcp}), we know ${\trc r \le k (D_N - \trc q) = k}$.
Therefore, again with reference to the discussion preceding
equation~(\ref{eq:dpdr}), we know
\begin{equation}
k \le \ind p \le |p_{i,j}- p_{i',j'}|=|r_{i,j}- r_{i',j'}|
\le \trc r \le k.
\end{equation}
Thus we conclude
\begin{equation}
|r_{i,j}- r_{i',j'}| = k.
\label{eq:drk}
\end{equation}
Note that the application of the triangle inequality relies
critically on the independence of $r_{i,j}$ and $r_{i',j'}$.
We now apply~(\ref{eq:drk}) to obtain an absurdity for Case~IId.
There are two subcases corresponding to the two choices of sign
arising from the absolute value.
\begin{description}
\item{Case IId: $p_{j_1}$ and $p_{j_3}$ are adjacent}
For some $p_{i,j}$ (with $j=i$) and some $p_{i',j'}$ (with
$j'=i'+1$) we have ${p_{i,j} = p_{j_4}}$ and ${p_{i',j'} = p_{j_1}
+ p_{j_3}}$. Since ${q_{j_4} - q_{j_1} - q_{j_3} = 0}$ and by
using~(\ref{eq:drk}), we have
\begin{equation}
|p_{i,j}-p_{i',j'}| = |r_{j_4} - r_{j_1} - r_{j_3}| = k.
\end{equation}
If the argument of the absolute value is postive then
\begin{eqnarray}
r_{j_4} = r_{j_1} + r_{j_3} + k
& \Longrightarrow & \nonumber \\
\trc r = r_{j_0} + 2r_{j_1} + r_{j_2} + 2r_{j_3} + k \le k
& \Longrightarrow & \nonumber \\
r_{j_0} = r_{j_1} = r_{j_2} = r_{j_3} = 0
& \Longrightarrow & \nonumber \\
r_{j_4} = k. &&
\end{eqnarray}
The last equality contradicts the assumption that ${r_{j_4}
\le k-1}$.
Similarly, if the argument of the absolute value is negative
then
\begin{eqnarray}
r_{j_1} + r_{j_3} = r_{j_4} + k
& \Longrightarrow & \nonumber \\
\trc r = r_{j_0} + r_{j_2} + 2r_{j_4} + k \le k
& \Longrightarrow & \nonumber \\
r_{j_0} = r_{j_1} = r_{j_2} = r_{j_4} = 0
& \Longrightarrow & \nonumber \\
r_{j_3} = k. &&
\end{eqnarray}
The last equality contradicts the assumption that ${r_{j_3}
\le k-1}$; we have used~(\ref{eq:ares3}) to obtain ${r_{j_1} =
0}$.
\end{description}
For Cases~IIe and~IIf, the above method can be applied to the
subcases corresponding to one choice of sign arising from the
absolute value. For the subcases corresponding to the other choice
of sign, the method fails; one can only conclude that ${r_{j_0} =
r_{j_1} = r_{j_4} = 0}$ and ${r_{j_2} + r_{j_3} = k}$, which is
not manifestly contradictory. However, there are only four
possible permutations (modulo conjugacy) which are covered
exclusively by these two cases. For each one, we obtain a
contradiction as follows.
\begin{description}
\item{\underline{Case IIe.1: $q = (2,6,1,4,3)$}}
\begin{equation}
p_{3,4} = (4k + r_{j_3}) + (3k + r_{j_2}) = 8k = p_{0,1}.
\end{equation}
\item{\underline{Case IIe.2: $q = (1,6,2,3,4)$}}
\begin{equation}
p_{3,4} = (3k + r_{j_2}) + (4k + r_{j_3}) = 8k = p_{1,2}.
\end{equation}
\item{\underline{Case IIe.3: $q = (1,6,4,3,2)$}}
\begin{eqnarray}
p_{2,4} & = & (4k + r_{j_3}) + (3k + r_{j_2}) + 2k = 10k,
\nonumber \\
p_{1,2} & = & 6k + (4k + r_{j_3}) = 10k + r_{j_3};
\end{eqnarray}
$$\Longrightarrow$$
\begin{equation}
p_{1,2} - p_{2,4} = r_{j_3} \le k-1.
\end{equation}
\item{\underline{Case IIf: $q = (1,4,3,6,2)$}}
\begin{equation}
p_{1,2} = (4k + r_{j_3}) + (3k + r_{j_2}) = 8k = p_{3,4}.
\end{equation}
\end{description}
This concludes (the outline of) the proof for $N=4$.
The proof is not elegant; no one argument will work for all
of the various cases. Also, for both $N=3$ and $N=4$, we have used
either ${\trc q = C_N}$ or ${\trc q = D_N - 1}$ in each of the
arguments. Since for $N=5$, there will be cases where neither of
these hold, the generalization of the proof is not immediately
apparent. Presumedly, this lack of elegance is due to the fact
that we are trying to prove a property based on the globally
maximal nature of an $N$-triangle, when in actuality, it is the
locally maximal nature which gives rise to the property.
\label{ap:proof}
\end{section}
\section*{Acknowledgements}
Above all, the author would like to thank Alex Grossmann for
introducing him to the concept of irregularity, for supplying the
graphics software, and for patiently discussing most of the
preliminary results. Thanks are also due to N.~J.~Sloane for
identifying the sequence $\{1,3,6,11,17,\cdots\}$, and to
S.~W.~Golomb for supplying some of the references. Finally, the
author would like to thank everyone at the Centre de Physique
Th\'{e}orique, in particular Maryse Cohen-Solal, for making his
stay in Marseille productive and enjoyable.
\clearpage
\begin{thebibliography}{99}
\bibitem{AG} A.~Grossmann and D.~K.~Freeman, ``Maximizing
Irregularity and the Construction of Signals with Optimal
Ambiguity Function'', in preparation.
\bibitem{REB} R.~E.~Blahut, ``Theory of Remote Surveillance
Algorithms'', {\em Radar and Sonar --- Part~I} (IMA Volumes in
Mathematics and its Applications), vol.~32, Springer-Verlag,
1991.
\bibitem{HT} H.~Taylor and S.~W.~Golomb, ``Rulers Part~I'', CSI
Technical Report \#85--05--01, 1985.
\bibitem{AKD} A.~K.~Dewdney, {\em Scientific American}, vol.~253,
num.~6, pp.~16--20, 1985.
\bibitem{GSB1} G.~S.~Bloom and S.~W.~Golomb, ``Applications of
Numbered Undirected Graphs'', Proceedings of the IEEE, vol.~65,
no.~4, 1977.
\bibitem{GSB2} G.~S.~Bloom and S.~W.~Golomb, {\em Theory and
Applications of Graphs} (Proc. Internat. Conf., Western Mich.
Univ., Kalamazoo, Mich., 1976), Lecture Notes in Math., vol.~642,
pp.~53--65, Springer, 1978.
\bibitem{AS} A.~Schrijver, {\em Theory of Linear and Integer
Programming}, John Wiley \& Sons, 1986.
\bibitem{JS} J.~Stoer and C.~Witzgall, {\em Convexity and
Optimization in Finite Dimensions~I}, Springer-Verlag, 1970.
\end{thebibliography}
\clearpage
\pagestyle{empty}
\tableofcontents
\clearpage
\listoffigures
\listoftables
\end{document}
~~