GOLAY SEQUENCES



© Nickolay A. Balonin, Dragomir Z. Djokovic, 1.05.2014

Hadamard matrix catalogue and on-line algorithms


Two Golay sequences a, b allow to construct Hadamard matrix with two circulant matrices A=circ(a), B=circ(b). The two-circulant Hadamard matrices can be built by periodic Golay pairs. Using also R – reversed identity matrix, we have two versions:

H=
A
B
 BT 
 –AT 
H=
A
 BR 
 BR 
 –A 


Порядок n=2 (mod 4). Матрицы A, B на порядках Адамара могут быть построены на базе пары комплементарных последовательностей Голея (Golay seq). Необходимое условие существования: размер парных последовательностей должен быть суммой двух квадратов (где один квадрат может быть 0): 1, 2, 4, 8, 10, 16, 20, 26, 32, 40, 52, 64, 80 (n<100).

Исходные примитивы имеют порядки 2, 10 (и еще есть 10), и 26, остальное n<100 строится на их основе для n=2a10b26c [1, 2]. Неисследованные случаи таковы: n = 106, 116, 122, 130, 136, 146, 148, 164, 170, 178, 194 (n<200), см. примеры [3]. Последовательности Голея – основа для вычисления регулярных матриц Адамара [4].

1. Dragomir Z. Djokovic, Equivalence classes and representatives of Golay sequences, Discrete Mathematics 189 (1998) pp. 79-93 (PDF).
2. P.B. Borwein and R.A. Ferguson, A complete description of Golay pairs for lengths up to 100, Mathematics of Computation, 73 (2003), 967-985.
3. C. Koukouvinos, Sequences with zero autocorrelation, in CRC Handbook of Combinatorial Designs, C.J. Colbourn and J.H. Dinitz (Eds.), CRC Press, (1996), 452-456.
4. The review of Mikhail Muzychuk and Qing Xiang (PDF) is also useful.

MULTIPLICATION OF GOLAY SEQUENCES

Golay's multiplication gives pairs A×C;B×D and A×D*;–B×C* of lengths 2nm, where C*, D* – reversed sequences. R.J. Turyn proposed modification (to get length nm, см. WIKI):

A×(C+D)/2 + B*×(C–D)/2 and B×(C+D)/2 – A*×(C–D)/2.




Hadamar matrices H8, H16

.

Weighing matrices can be build including zero with ordinary Golay sequences, periodic Golay pairs cannot be used this way (in common) due known rule about the sum two squares.



Table of two squares sum


PERIODIC GOLAY SEQUENCES

The text is under correction


From Jennifer's letter. Non-periodic Golay sequences are the most powerful because they can give two sequences of lengths g=(2a + α)(10b + β)(26c + γ) (α, β, γ are non-negative integers and add zeros to the sequences). Periodic Golay sequences can be combined with non-periodic Golay sequences for s1, s2, s3, ... in the set S={1, 34, 50, 58, 72, 74, 82, 122, 202, 226}. This allows us to have two sequences of periodic Golay sequences for lengths g×s1t1×s2t2×s3t3 and so on for t1, t2, t3, ... non-negative integers.

From Dragomir's letter. We note that periodic Golay sequences of length m exist for m=gs where g=2a10b26c (a, b, c non-negative integers) and s belongs to the set S={1, 34, 50, 58, 72, 74, 82, 122, 202, 226}. Thus, up to 200, these lengths are {1, 2, 4, 8, 10, 16, 20, 26, 32, 34, 40, 50, 52, 58, 64, 68, 72, 74, 80, 82, 100, 104, 116, 122, 128, 136, 144, 148, 160, 164, 200}. They give Hadamard matrices for orders {[2], [4], [8], [16], [20], [32], [40], [52], [64], 68, [80], 100, [104], 116, [128], 136, 144, 148, [160], 164, 200, [208], 232, 244, [256], 272, 288, 296, [320], 328, 400}.

Ordinary non-periodic Golay pairs lead to orders given in brackets. They give W(2n,2n–2) with determinant (2n–2)n for orders n={4, 6, 10, 18, 22, 34, 42, 54, 66, 82, 106, 130, 162, 210, 258, 322}. In the cases 22, 34, 66, 106, 130, 162, 210, 322 there are no corresponding conference matrices [3].

The first periodic Golay pair whose length, 34, is not a Golay number has been found in 1998 by Dragomir [1]. (In fact two non-equivalent such pairs were found.) Periodic Golay pairs of length 50 have been found by Djokovic [2] and Kotsireas and Koukouvinos [3].



Dragomir's matrices H68 by SDS(34;16,13;12)





Four non regular two-circulant matrices H100 by SDS (58;27,24;22)


Four pictures H100 built by SDS (58;27,24;22), n=2v, v must be even, taken from the paper of Djokovic and Kotsireas [4].



Regular two-circulant matrix H100 by (50; 25, 20; 20)



Regular two-circulant matrix H144 by (72;36,30;30)


This SDS for regular H100 above is given in Dragomir's paper in Annals of Comb (2011); note added in proof: Subsequent to the posting of the first version of paper on 14th July 2007, I.S. Kotsireas and C. Koukouvinos constructed by a completely different method another example of SDS with parameters (50; 25, 20; 20) [3]. The two examples are indeed nonequivalent. Look also: (PDF).

Since all Golay numbers in the range 1, 2, . . . , 100 are known, we deduce that 34, 50, 58, 68, 72, 74, 82 are the only periodic Golay numbers for which we are presently sure that they are not Golay numbers [4]. The parameters for the periodic Golay pairs of length 50 (one of them) for regular matrix are (50;25,20;20). Thus, one of the circulant blocks has 0 row sum. Consequently we get regular H100.

Note that periodic Golay pairs are a generalization of the ordinary Golay pairs (so there is no need to treat Golay pairs separately). Recently several new periodic Golay pairs (of new orders) have been constructed by Ilias and Dragomir. In particular see the paper "Some new periodic Golay pairs" on arXiv:1310.5773v2 [math.CO] 27 Aug 2014 (it has been just published on-line in Numerical Algorithms).

There was also constructed periodic Golay pairs of length 72 with parameter set (72;36,30;30). This means that we also have have a regular two circulant H144 [5]. Moreover, the periodic Golay pairs can be "multiplied" with ordinary Golay pairs to produce longer periodic Golay pairs as recently proved by Georgiou et al in Biometrika (2014), pp. 17.

Conjecture: there are no periodic Golay pairs of length n>32 with (at least) one of the sequences symmetric.

Dragomir propose that all two circulant Hadamard Matrices be collected together under the heading of Periodic Golay Pairs. Another note: If we want to get regular two circulant Hadamard matrix then the corresponding periodic Golay pair must have parameters of the form (2x2; x2, x2x; x2x) where x>0 is an integer.

Some of these parameter sets have to be discarded because they do not pass the Arasu-Xiang test (necessary condition). For instance there are no periodic Golay pairs with such parameter sets for x=3, 7. However they could to be exist for infinitely many x's. The special cases of interest are x=5 which gave us regular H100 and x=6 which gives a regular H144. There have not to be matrix H196 periodic Golay pairs based.

A year ago there was written an article [7] with 31 non-equivalent periodic Golay pairs of length 68. By checking their index of symmetry, Dragomir found one with index 10. Among the 8 periodic Golay pairs, paper [5], there are 8 non-equivalent periodic Golay pairs of length 72. Here the List from Dragomir: first parameter v – the length of the sequences. Second – the symmetry index of the first sequence A. Third – the symmetry index of the second sequence B. Fourth – this is just the number of the solution in Dragomir's list of the SDS. For v=68 and v=72 the lists are given in the two papers posted on arXiv.

1. Dragomir Z. Djokovic, Note on periodic complementary sets of binary sequences, Des. Codes, Cryptogr. 13 (1998), 251–256.
2. Dragomir Z. Djokovic, Cyclic (v; r, s; ) difference families with two base blocks and v ≤ 50. Ann. Comb. 15 (2011), no. 2, 233–254.
3. I. S. Kotsireas, C. Koukouvinos, Periodic complementary binary sequences of length 50. Int. J. Appl. Math. 21 (2008), 509–514.
4. Dragomir Z. Djokovic, Ilias S. Kotsireas, Some new periodic Golay pairs. arXiv:1310.5773v2 [math.CO] 27 Aug 2014 (PDF) AND arXiv:1409.5969v2 [math.CO] 27 Jan 2015
5. Dragomir Z. Djokovic, Ilias S. Kotsireas Periodic Golay pairs of length 72. arXiv:1409.5969v1 [math.CO] 21 Sep 2014. (PDF)
6. W. D. Wallis, Anne Penfold Street, and Jennifer Seberry Wallis, Combinatorics: Room Squares, Sum-Free Sets, Hadamard Matrices, Springer-Verlag, Berlin 1972.
7. Dragomir Z. Djokovic, Ilias Kotsireas, Daniel Recoskie, and Joe Sawada, Charm bracelets and their application to the construction of periodic Golay pairs. arXiv:1405.7328.

SYMMETRIES


Балонин Н. А., Джокович Д. Ж. Симметрия двуциклических матриц Адамара и периодические пары Голея. // Информационно-управляющие системы. 2015. № 3. С. 2–16.


Rambler's Top100