Pure mathematics Research News

A generalization of very odd sequences

KU Cheng Yeaw (Group Leader, Mathematics) () October 29, 2015
29 Oct 2015 NUS mathematicians described the classical theorems for very odd sequences and give a characterization of these new sequences.Suppose a = (a(0), a(1), …, a(n)) is a sequence of length n where each entry a(i) is 0 or 1. Let k be an integer between 0 and n-1, and let A(a, k) denote the sum of a(i)a(j) over all possible i and j where j – i = k and 0 ≤ i ≤ j ≤ n-1. The sequence a is called a very odd sequence if A(a,k) is odd for all 0 ≤ k ≤ n-1.

Pelikan [5] conjectured that very odd sequences of length n > 5 do not exist. Later, Alles [1] and MacWilliams and Odlyzko [4] proved that Pelikan conjecture is false. In fact, Inglis and Wiseman [2] and MacWilliams and Odlyzko [4] gave a necessary and sufficient condition for the existence of a very odd sequence of length n: A very odd sequence of length n > 1 exists if and only if the order of 2 is odd in the multiplicative group of integers modulo 2n – 1.

A team led by Dr KU Cheng Yeaw from the Department of Mathematics in NUS considered (y(k), p)-sequences where y(k) is an infinite sequence (y(0), y(1), …, ) where y(i) = (-1)i × k, and p is a prime number. In the special case when k=1 and p=2, these sequences reduce to very odd sequences.

There are some connections between the existence of very odd sequences of length n and error-correcting codes used in digital communications for transmitting data over unreliable channels subject to noise. In particular, the celebrated Golay code arises on taking n=12. Their results imply certain admissible values of the underlying parameters for the existence of codes in a more general setting.

They give a characterization of these new sequences: Let p be an odd prime, k ∈ Zp \ {0} and gcd(p, 2n − 1) = 1 = gcd(p − 1, 2n − 1). A (y(k), p)-sequence of length n > 1 exists if and only if

(a) the order of p is odd in U(2n−1), and

(b) k is a quadratic residue modulo p.

Here, Zp is the ring of integers modulo p and U(2n-1) is the multiplicative group of integers modulo n.

 ku cy oct

Suppose p is a prime, k ∈ Zp \ {0}, gcd(p, 2n − 1) = 1 = gcd(p − 1, 2n − 1), and there is any (y(k), p)-sequence of length n > 1. Consequently, by using the Quadratic Reciprocity Law (as shown in the figure above), one can show that, among others,

  1. if p =2 then n ≡ 0 or 1 mod 4,
  2. if p =3 then n ≡ 0 or 1 mod 6,
  3. if p =5 then n ≡ 0 or 1 mod 5,
  4. if p =7 then n ≡ 0, 1, 10, 13, 15, 16, 19, 24, 27, 28, 30, 33 mod 42.

 

References

1. P Alles. “On a conjecture of J. Pelikan, J. Combin.” Theory Ser. A 60 (1992) 312.

2. NFJ Inglis, JDA Wiseman. “Very odd sequences.” J. Combin. Theory Ser. A 71 (1995) 89.

3. CY Ku, KB Wong. “A generalization of very odd sequences.” The Electronic Journal of Combinatorics, 22(2) (2015) P2.

4. FJ MacWilliams, AM Odlyzko. “Pelikan’s conjecture and cyclotomic cosets.” J. Combin. Theory Ser. A 22 (1977) 1104.