\documentstyle[12pt]{article}

\def\e{\varepsilon} 
\def\a{\alpha}
\def\b{\beta}
\def\l{\lambda}
\def\s{\sigma}
\def\ph{\varphi}
\def\ra{\rightarrow}
\def\Z{{\bf Z}}
\def\N{{\bf N}}
\def\R{{\bf R}}
\def\Rplus{\R^+}
\def\RO{\R^{\geq 0}}
\def\mod{\;\mbox{\rm mod}}
\def\qed{$\Box$\par\bigskip\noindent}
\def\xx{\overline{x}}
\newtheorem{th}{THEOREM}
\newtheorem{lem}{LEMMA}
\newtheorem{conj}{CONJECTURE}

\title{Notes on one-dimensional coverage problem} 
\author{D.~G.~Fon-Der-Flaass
\thanks{Supported by the U.K. Radiocommunications Agency}
\\Centre for Discrete and Applied Mathematics
\\London School of Economics
\\Houghton St. London WC2A 2AE, U.K.}

\date{}

\begin{document}

\maketitle

\section{One-dimensional case}

This paper discusses the one-dimensional case of a line of research that
was previously considered in [1]. The notation of that paper is used.
\medskip

We consider infinitely many transmitters of equal power equally spaced
along the line; that is, the coverage region $\Omega=\R$ and the set of
transmitters $T=\Z$. We assume the propagation law to satisfy the condition
$(*)$ of [1]; so the points with worst noise-to-signal ratio are $n+1/2$,
$n\in\Z$. We need to impose another condition on the function $N(r)$
without which the problem would become meaningless (the noise at each point
of $\Omega$ would become infinitely big):

\medskip
$(**)$\quad $\sum_{n=1}^\infty N(n)<\infty$.

In addition, we assume that only a finite set of equally spaced channels is
used --- as it is always so in practice. Let $C=\{0,1,\ldots,k-1\}$, and
$\lambda=e^{-\beta}$ --- the interference fall between neighbouring
channels. It is natural to measure the total span by the number
$sp=\lambda^{1-k}$; one of our aims will be to compare channel assignments
with different values of $k$ but with equal spans.

Define a function $f:\N\ra\R$ by the formula
$f(n)=\frac{N(n-1/2)}{N(1/2)}$. We have $f(1)=1$, and $f$ monotonically
decreases. Then the value of NSR at every point $n+1/2$ is a polynomial in
$\l$ of degree at most $k-1$ with non-negative coefficients; and all
coefficients are sums of certain values of the function $f$. The value of
NSR for a receiver at a point $n+1/2$ tuned to the frequency $c(n)$ (resp.
$c(n+1)$) will be denoted by $NSR(n,-)$ (resp. $NSR(n,-)$). The coefficient
at $\l^i$ will be denoted respectively by $a_i^{(n,-)},\quad a_i^{(n,+)}$.

An assignment $c:T\ra C$ is called {\em periodic} if for $c(n)=c(n+L)$ for
some constant value $L$. An assignment is called {\em strictly periodic} if
all frequencies within a period are different, and {\em permutational} if
there exists a permutation $\s$ of $\{0,1,\ldots,k-1\}$ such that
$c(n)=\s(n\mod k)$. For any strictly periodic assignment of period $L$, and
for any point $n+1/2$ where $n\in\Z$, the constant term in NSR has the same
value
$$\sum_{i\geq 1}(f(iL)+f(iL+1))=M^{(L)}.$$

\begin{th}\label{th2}
For any periodic assignment $c$ with given value of $k$,
$$\max(a_0^{(n,\e)}\mid n\in\Z,\;\e\in \{+,-\})\geq M^{(k)},$$
and the inequality is strict unless the assignment is permutational.
\end{th}

The following lemma, which will be used in the proof of the theorem, looks
like a special case of some more general result from theoretical mechanics.
We shall give it an elementary proof which is more in the spirit of the
present paper.

Denote by $\R_L$ the metric space $\R/L\Z$: the interval $[0,L)$ viewed as
the circle of length $L$, with the natural metric
$d(x,y)=\min(|x-y|,L-|x-y|)$ ($x,y\in[0,L)$). The maximum distance between
two points in $\R_L$ is $L/2$.

\begin{lem}\label{lem1}
Let $f:\Rplus\ra\RO$ be any strictly convex decreasing function.

$(i)$. For any positive numbers $x_1,\ldots,x_n,S$ such that
$x_1+\ldots+x_n\leq S$, we have
$$f(x_1)+\ldots+f(x_n)\geq nf(S/n),$$
with the equality only when $x_1=\ldots=x_n=S/n$.

$(ii)$. Let $(M,d)$ be the metric space $R_L$ defined above. For every
finite set $X\subset M$ define
$$f(X)=\sum_{\{x,y\}\subseteq X,\;x\neq y}f(d(x,y)).$$
Then the minimum value of $f(X)$ over all $n$-element sets $X\subset M$ is
achieved only on the set $X_0=\{0,L/n,2L/n,\ldots,(n-1)L/n\}$, and on its
cyclic shifts.
\end{lem}

PROOF.\quad
$(i)$ is a standard inequality about convex functions.

$(ii)$ For any $x,y\in [0,L)$, define oriented distance $d'(x,y)$ as
$$d'(x,y)=\left\{
\begin{array}{lll}y-x&when&y\geq x\\L+y-x&when&y<x\end{array}
\right..$$
Obviously, $d(x,y)\leq d'(x,y)$.  
Denote elements of $X$ by $0\leq x_0<x_1<\ldots<x_{n-1}$.
Regroup the summands in the formula for $f(X)$ as follows:
$$f(X)=\sum_{1\leq i<n/2}\sum_{k=0}^{n-1}f(d(x_k,x_{k+i}))$$
when $n$ is odd, and
$$f(X)=\sum_{1\leq i<n/2}\sum_{k=0}^{n-1}f(d(x_k,x_{k+i}))+
\sum_{k=0}^{n/2-1}f(d(x_k,x_{k+n/2}))$$
when $n$ is even. Here indices are considered modulo $n$.

Now, for each $i<n/2$ we have
$$\sum_{k=0}^{n-1}d'(x_k,x_{k+i})=iL.$$
Therefore $\sum d(x_k,x_{k+i})\leq iL$, and by $(i)$ we have:
\begin{equation}\label{lem1eq1}
\sum_{k=0}^{n-1}f(d(x_k,x_{k+i}))\geq nf(iL/n).
\end{equation}
The last sum in the formula for $f(X)$ for even $n$ is estimated as
follows:
\begin{equation}\label{lem1eq2}
\sum_{k=0}^{n/2-1}f(d(x_k,x_{k+n/2}))\geq (n/2)f(L/2).
\end{equation}
Note that only when $X=X_0$, or $X$ is a cyclic shift of $X_0$, all
inequalities (1) and (2) become equalities. Adding together all these
inequalities, we get the desired inequality $f(X)\geq f(X_0)$.
\qed

PROOF OF THEOREM. \quad Let $c$ be any periodic colouring of $\Z$ by $k$
colours. Taking, if necessary, $k$ periods, we can ensure that the period
length $L=kn$ is a multiple of $k$.

First we replace the real line $\R$ with $\R_L$. As in the original
problem, the signal from a transmitter located at $x$ (which now represents
an infinite set of transmitters, all of the same frequency) in a point $y$
depends on $d=d(x,y)$ only; and is given by the formula
$$N'(d)=\sum_{i\geq0}N(d+iL)+\sum_{i\geq 0}N(L-d+iL).$$
The function $N'$ is defined for all $d\neq iL$ (we set $N'(iL)=\infty$);
it is monotonely decreasing on $(0,L/2]$, and convex on $(0,L)$, with a
minimum at $L/2$.

The colouring $c$ is obtained by periodically repeating the sequence
$$(c(0),\ldots,c(L-1));$$
we shall consider it as a colouring of $L$ integer points of the circle.
What we need to show is that there exist a colour $c$, an integer
$t\in\{0,\ldots,L-1\}$ such that $c(t)=c$, and a receiver position
$x\in\{t-1/2,t+1/2\}$ (operations modulo $L$) such that
%
$$\sum_{i:\;c(i)=c}N'(d(x,i))\geq\sum_{0\leq i\leq n-1}N'(d(1/2,ki))=N_0.$$
%
Let $c$ be any colour which appears in the period at least $n$ times. Let
$X\subseteq\{0,\ldots,L-1\}$ be any set of $n$ points coloured by $c$.
Also, let $X_0=\{0,k,2k,\ldots,(n-1)k\}$.

For every point $z=x_0\pm 1/2$, $x_0\in X_0$, the total signal from $X_0$
at $z$ is the same, and is equal to $N_0$. We shall prove that
\begin{equation}\label{th2eq1}
\sum_{x\neq y\in X}\sum_{z=x\pm 1/2}N'(d(z,y))\geq 
  \sum_{x\neq y\in X_0}\sum_{z=x\pm 1/2}N'(d(z,y))=2n(n-1)N_0;
\end{equation}
this will suffice to prove the theorem.

Define a function $f:(0,L/2]\ra\RO$ as follows:
$$f(d)=2N'(d+\frac{1}{2})+2N'(d-\frac{1}{2}).$$
The function $f$, like $N'$, is monotonely decreasing and convex on
$(0,L/2]$. The inequality (3) which we want to prove can now be written as
$$\sum_{\{x,y\}\subseteq X,\;x\neq y}f(d(x,y))\geq \sum_{\{x,y\}\subseteq
X_0,\;x\neq y}f(d(x,y)),$$
and it immediately follows from Lemma 1$(ii)$.
\qed

Thus, asymptotically, when $\l\ra 0$, permutational assignments are the
best possible among periodic assignments. It is very likely that the
condition of periodicity in Theorem 1 may be replaced by some weaker
condition, or altogether dropped.

\section{Permutational assignments}

In this section we shall find optimal permutational assignments for small
values of $k$. We shall compare the effectiveness of these assignments
having the same total span $sp=\l^{1-k}$. We assume that the propagation
function $N(d)$ satisfies $(*)$ and $(**)$; and use the notation from the
previous section.

Let $c$ be a permutational assignment; i.e. a $k$-colouring with period of
length $k$. In addition to
$$M^{(k)}=\sum_{i\geq 1}(f(ik)+f(ik+1)),$$
we introduce the numbers
$$M^{(k)}_j=\sum_{i\geq 0}(f(ik+j)+f(ik+k+1-j))$$
for $1\leq j\leq k$. We have: $M^{(k)}_1=M^{(k)}+1$, and
$M^{(k)}_j=M^{(k)}_{k+1-j}$, and $M_1>M_2>\ldots>M_{(k+1)/2}$.

Each frequency is assigned to a set of transmitters at equal distances $k$;
the total signal from such set at every point $n+1/2$ is equal to
$M^{(k)}_j$ where $j/2$ is the distance from the point to the set. Thus,
every value of $NSR(n,\e)$ is the sum of $M^{(k)}$ (co-channel
interference) and a linear combination of powers of $\l$ with coefficients
$M^{(k)}_1$, $M^{(k)}_2$, $M^{(k)}_2$, etc., $M^{(k)}_{k/2}$. Let us
consider small values of $k$; for simplicity of notation we shall omit the
upper index $(k)$ whenever possible.

\medskip
For $k=2$ the assignment is unique: $\ldots 010101\ldots$, and NSR at all
points is equal to $M+\l M_1=(1+\l)M-1$.

\medskip
For $k=3$ the assignment is also unique up to symmetry: $\ldots
012012\ldots$, and NSR is equal to $M+M_1\l+M_2\l^2$ or to $M+(M_1+M_2)\l$.
The latter is the worst value of NSR.

\medskip
For $k=4$ there are three essentially different assignments,

$\ldots 01230123\ldots$,

$\ldots 01320132\ldots$, and

$\ldots 03120312\ldots$: the worst value of NSR in all three cases is 
$M+(M_1+M_2)\l+M_2\l^2$.

\medskip
For $k=5$ there are 12 essentially different assignments, but we don't need
to consider all of them to choose the best one. Indeed, consider a receiver
between two transmitters one of is assigned the channel 2, tuned to the
channel 2 (the channels being 0,1,2,3,4). The value of NSR for this
receiver is the sum of $M$ and a linear combination of $\l,\l,\l^2,\l^2$
with coefficients $M_1,M_2,M_2,M_3$ in a certain order. The minimum
possible value of such combination is $(M_2+M_3)\l+(M_1+M_2)\l^2$, so a
lower bound for NSR is
$$M+(M_2+M_3)\l+(M_1+M_2)\l^2.$$
But the assignment $\ldots 0241302413\ldots$ has exactly this value of the
worst NSR. So, this is an optimal assignment. Note that it is also the best
solution of the binary constraints problem with constraints

$|c(i)-c(i+1)|\geq 2$,

$|c(i)-c(i+2)|\geq 1$.

\medskip
Given any choice of the propagation law, it is easy to calculate the values
of $M^{(k)}_i$, and to compare optimal assignments with different number of
channels but with equal values of total span (that is,
$\l_1^{1-k_1}=\l_2^{1-k_2}$).

As an example, let us compare assignments of period 2 and period 3 with the
same span: $\ldots 020202\ldots$ and $\ldots 012012\ldots$.

The worst values of NSR are equal respectively to
$N_2=M^{(2)}_1-1+\l^2M^{(2)}_1$, and
$N_3=M^{(3)}_1-1+\l(M^{(3)}_1+M^{(3)}_2)$. We have:
$$N_3-N_2=M^{(3)}_1-M^{(2)}_1+\l(M^{(3)}_1+M^{(3)}_2)-\l^2M^{(2)}_1=$$
$$=M^{(2)}_1(1-\l)(\l-B),$$
where
$$B=\frac{M^{(2)}_1-M^{(3)}_1}{M^{(2)}_1}.$$
Using obvious identities $M^{(1)}_1=2M^{(2)}_1=2M^{(3)}_1+M^{(3)}_2$, we
get $B=M^{(3)}_2/M^{(1)}_1$. The assignment of period 2 is better than that
of period 3 with the same span if and only if the interference fall $\l$ is
greater than $B$. In the particular case of the propagation function
$d^{-\alpha}$, one can find that the threshold value $B=3^{-\alpha}$.
  


\begin{thebibliography}{9}
\bibitem{BF} N.Biggs, D.Fon-Der-Flaass. 
Optimizing the signal-to-noise ratio, 
{\em CDAM Research Report Series},
LSE-CDAM-98-16 (1998), 4 pp.
\end{thebibliography}
\end{document}
