Logo image
Back
Camel sequences and quadratic residues
Journal article   Peer reviewed

Camel sequences and quadratic residues

V.A. Gurvich and Li Sheng
Discrete Applied Mathematics, v 124(1), pp 73-89
2002
DOI: https://doi.org/10.1016/S0166-218X(01)00331-6

Abstract

Camel sequences Extremal graph theory Maxmin Minmax Quadratic residues Vertex-enumerated graphs
Given an even cyclic (+1,−1) sequence s=( s 0,…, s 2 n−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 insert the obtained n 2 numbers into 2 n “boxes” b 0, b 1,…, b 2 n−1 , where box b k contains the multiplicity of k. The cyclic sequence B( s)=( b 0, b 1,…, b 2 n−1 ) is referred to as the box distribution of s. The average cardinality of a box is n 2/2 n= 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 41 3 40) ; n=7, s=(+1+1+1−1+1−1−1−1+1+1−1+1−1−1), B=(33333363333337)=(3 66 3 67) . In general, given an odd n, the box-distributions (⌊ n/2⌋ n−1 ( n−1)⌊ n/2⌋ n−1 n) and (⌈ n/2⌉ n−1 1⌈ n/2⌉ n−1 0) as well as the sequences which generate them, will be called the camel distributions and camel sequences, respectively, up-camel and down-camel. For example, the first sequence above is down-camel, and the second one is up-camel. Here we prove that there are infinitely many ‘camels’ of both types. More precisely, for every prime n=4 j−1 we construct an up-camel sequence and for every prime n=4 j+1 a down-camel one. In both cases these sequences are related to quadratic residues and non-residues modulo n. Camel sequences have applications in extremal graph theory.

Metrics

13 Record Views

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Collaboration types
Domestic collaboration
Web of Science research areas
Mathematics, Applied
Logo image