## DIMACS TR: 99-40

## Camel Sequences and Quadratic Residues

### Authors: V. Gurvich and Li Sheng

**
ABSTRACT
**

Given an even cyclic $(+1,-1)$ sequence
$s = (s_0,..., s_{2n-1})$ which consists of
$n$ plus ones and $n$ minus ones,
let us compute $i + j \ (mod\ 2n)$
for all $n^2$ $(+1,-1)$-pairs $(s_i,s_j)$ and
distribute obtained $n^2$ numbers
between $2n$ "boxes" $1,2,...,2n-1,2n=0 \ (mod\ 2n)$.
The average cardinality of a box is
$\frac{n^2}{2n}=\frac{n}{2}$.
Some sequences have quite remarkable box-distributions,
"almost average everywhere with two big humps".
For example,

$n=5,
s = (+1+1-1-1+1-1+1-1-1+1),\ B = (3333133330) = (3^4 1 \, 3^4 0)\ $

$n=7,
s = (+1+1+1-1+1-1-1-1+1+1-1+1-1-1),\
B = (33333363333337) = (3^6 6 \, 3^6 7)$.

In general, given an {\em odd} $n$,
the box-distributions
$(\lfloor\frac{n}{2}\rfloor^{n-1} \ (n-1)
\\lfloor\frac{n}{2}\rfloor^{n-1} \
n)$ and
$(\lceil\frac{n}{2}\rceil^{n-1} \ 1 \ \lceil\frac{n}{2}\rceil^{n-1} \
0)$
as well as the sequences, which generate them,
will be called the {\em camel distributions}
and {\em camel sequences},
respectively {\em up-camel} and {\em down-camel}.
For example, the first sequence above is down-camel,
and the second one is up-camel.
Camel sequences have applications in extremal graph theory.
Here we prove that there are
infinitely many 'camels' of both types.
More precisely,
for every prime $n=4j-1$
we construct an up-camel sequence and
for every prime $n=4j+1$ a down-camel one.
In both cases these sequences are related to
quadratic residues and non-residues modulo $n$.
We conjecture that there are no other camel sequences.

**Key Words:** *
quadratic residues, camel sequences, maximin, minimax,
extremal graph theory, vertex-enumerated graphs.*

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-40.ps.gz

DIMACS Home Page