×

zbMATH — the first resource for mathematics

Generalized perfect arrays and Menon difference sets. (English) Zbl 0767.05030
Given an \(s_ 1\times\cdots\times s_ r\) integer-valued array \(A\) and a \((0,1)\) vector \({\mathbf z}=(z_ 1,\dots,z_ r)\), form the array \(A'\) from \(A\) by recursively adjoining a negative copy of the current array for each dimension \(i\) where \(z_ i=1\). \(A\) is a generalized perfect array type \({\mathbf z}\) if all periodic autocorrelation coefficients of \(A'\) are zero, except for shifts \((u_ 1,\dots,u_ r)\) where \(u_ i\equiv 0\pmod{s_ i}\) for all \(i\). The array is perfect if \({\mathbf z}=(0,\dots,0)\) and binary if the array elements are all \(\pm 1\). A non- trivial perfect binary array (PBA) is equivalent to a Menon difference set in an Abelian group.
Using only elementary techniques, we prove various construction theorems for generalized perfect arrays and establish conditions on their existence. We show that a generalized PBA whose type is not \((0,\dots,0)\) is equivalent to a relative difference set in an Abelian factor group. We recursively construct several infinite families of generalized PBAs, and deduce nonexistence results for generalized PBAs whose type is not \((0,\dots,0)\) from well-known nonexistence results for PBAs. A central result is that a PBA with \(2^{2y} 3^{2u}\) elements and no dimension divisible by 9 exists if and only if no dimension is divisible by \(2^{y+2}\). The results presented here include and enlarge the set of sizes of all previously known generalized PBAs.
Reviewer: J.Jedwab (Bristol)

MSC:
05B10 Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.)
05B15 Orthogonal arrays, Latin squares, Room squares
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] S. Alquaddoomi and R.A. Scholtz, On the nonexistence of Barker arrays and related matters, IEEE Trans. Inform. Theory vol. 35, pp. 1048-1057, 1989. · doi:10.1109/18.42220
[2] M.F.M. Antweiler, L. Bömer, and H.-D. Lüke, Perfect ternary arrays, IEEE Trans. Inform. Theory vol. 36, pp. 696-705, 1990. · Zbl 0703.94007 · doi:10.1109/18.54895
[3] K.T. Arasu, Recent results on difference sets, in D. Ray-Chaudhuri, editor, The IMA Volumes in Mathematics and its Applications, Vol. 21: Coding Theory and Design Theory, Springer-Verlag, New York, 1990, pp. 1-23. · Zbl 0747.05013
[4] K.T. Arasu and J. Reis, On abelian groups of order 64 that have difference sets, Wright State University, Technical Report 1987.10, 1987.
[5] L.D. Baumert, Cyclic Difference Sets, Lecture Notes in Mathematics 182, Springer-Verlag, New York, 1971. · Zbl 0218.05009
[6] G. Berman, Families of skew-circulant weighing matrices, Ars Combin. vol. 4, pp. 293-307, 1977. · Zbl 0401.05026
[7] T. Beth, D. Jungnickel, and H. Lenz, Design Theory, Cambridge University Press, Cambridge, 1986.
[8] L. Bömer and M. Antweiler, Perfect binary arrays with 36 elements, Electron. Lett. vol. 23, pp. 730-732, 1987. · doi:10.1049/el:19870518
[9] L. Bömer and M. Antweiler, Two-dimensional perfect binary arrays with 64 elements, IEEE Trans. Inform. Theory vol. 36, pp. 411-414, 1990. · doi:10.1109/18.52492
[10] D. Calabro and J.K. Wolf, On the synthesis of two-dimensional arrays with desirable correlation properties, Inform. Control vol. 11, pp. 537-560, 1968. · Zbl 0157.49405 · doi:10.1016/S0019-9958(67)90755-3
[11] W.-K. Chan and M.-K. Siu, Authors’ correction to ldSummary of perfect s \(\times\) t arrays, 1 ? s ? t ? 100,rd Electron. Lett. vol. 27, p. 1112, 1991. · Zbl 0737.05025 · doi:10.1049/el:19910692
[12] W.-K. Chan and M.-K. Siu, Summary of perfect s \(\times\) t arrays, 1 ? s ? t ? 100, Electron. Lett. vol. 27, pp. 709-710, 1991. · Zbl 0737.05025 · doi:10.1049/el:19910441
[13] Y.K. Chan, M.K. Siu, and P. Tong, Two-dimensional binary arrays with good autocorrelation, Inform. Control vol. 42, pp. 125-130, 1979. · Zbl 0421.05010 · doi:10.1016/S0019-9958(79)90617-X
[14] J.A. Chang, Ternary sequence with zero correlation, Proc. IEEE vol. 55, pp. 1211-1213, 1967. · doi:10.1109/PROC.1967.5793
[15] J. Davis, Difference sets in abelian 2-groups, J. Combin. Theory (A) vol. 57, pp. 262-286, 1991. · Zbl 0746.05012 · doi:10.1016/0097-3165(91)90050-Q
[16] J. Davis, Difference sets in abelian 2-groups, Ph.D. thesis, University of Virginia, 1987.
[17] P. Delsarte, J.M. Goethals, and J.J. Seidel, Orthogonal matrices with zero diagonal II, Canad. J. Math. vol. 23, pp. 816-832, 1971. · Zbl 0219.05010 · doi:10.4153/CJM-1971-091-x
[18] J.F. Dillon, Difference sets in 2-groups, Contemporary Math. vol. 111, pp. 65-72, 1990.
[19] P. Eades and R.M. Hain, On circulant weighing matrices, Ars Combin. vol. 2, pp. 265-284, 1976. · Zbl 0349.05017
[20] J.E.H. Elliott and A.T. Butson, Relative difference sets, Illinois J. Math. vol. 10, pp. 517-531, 1966. · Zbl 0145.01503
[21] E.E. Fenimore and T.M. Cannon, Coded aperture imaging with uniformly redundant arrays, Applied Optics vol. 17, pp. 337-347, 1978. · doi:10.1364/AO.17.000337
[22] A.V. Geramita and J. Seberry, Orthogonal Designs: Quadratic Forms and Hadamard Matrices, Marcel Dekker, New York, 1979. · Zbl 0411.05023
[23] J. Hammer and J.R. Seberry, Higher dimensional orthogonal designs and applications, IEEE Trans. Inform. Theory vol. IT-27, pp. 772-779, 1981. · Zbl 0475.05021 · doi:10.1109/TIT.1981.1056426
[24] J.E. Hershey and R. Yarlagadda, Two-dimensional synchronisation, Electron. Lett. vol. 19, pp. 801-803, 1983. · doi:10.1049/el:19830546
[25] T. Høholdt and J. Justesen, Ternary sequences with perfect periodic autocorrelation, IEEE Trans. Inform. Theory vol. IT-29, pp. 597-600, 1983. · Zbl 0505.94012 · doi:10.1109/TIT.1983.1056707
[26] D.R. Hughes and F.C. Piper, Design Theory, Cambridge University Press, Cambridge, 1985.
[27] V.P. Ipatov, Ternary sequences with ideal periodic autocorrelation properties, Radio Engng. Electron. Phys. vol. 24, pp. 75-79, 1979.
[28] V.P. Ipatov, Contribution to the theory of sequences with perfect periodic autocorrelation properties, Radio Engng. Electron. Phys. vol. 25, pp. 31-34, 1980.
[29] V.P. Ipatov, V.D. Platonov, and I.M. Samoilov, A new class of ternary sequences with ideal periodic autocorrelation properties, Soviet Math. (Izvestiya VUZ) vol. 27, pp. 57-61, 1983. English translation. · Zbl 0524.12011
[30] J. Jedwab, Barker arrays I?even number of elements, 1991. Submitted. · Zbl 0779.05010
[31] J. Jedwab, Nonexistence of perfect binary arrays, Electron. Lett. vol. 27, pp. 1252-1254, 1991. · Zbl 0722.94022 · doi:10.1049/el:19910785
[32] J. Jedwab, Nonexistence results for Barker arrays, in C. Mitchell, editor The Institute of Mathematics and its Applications Conference Series (New Series) No. 33: Cryptography and Coding II, Oxford University Press, New York, 1992, pp. 121-126. · Zbl 0773.05026
[33] J. Jedwab, Perfect arrays, Barker arrays and difference sets, Ph.D. thesis, University of London, 1991. · Zbl 0722.94022
[34] J. Jedwab, S. Lloyd, and M. Mowbray, Barker arrays II?odd number of elements, 1991. Submitted. · Zbl 0779.05011
[35] J. Jedwab and C. Mitchell, Constructing new perfect binary arrays, Electron. Lett. vol. 24, pp. 650-652, 1988. · doi:10.1049/el:19880440
[36] J. Jedwab, C. Mitchell, F. Piper, and P. Wild, Perfect binary arrays and difference sets, 1991. Submitted. · Zbl 0801.05013
[37] J. Jedwab and C.J. Mitchell, Infinite families of quasiperfect and doubly quasiperfect binary arrays, Electron. Lett. vol. 26, pp. 294-295, 1990. · Zbl 0732.68106 · doi:10.1049/el:19900194
[38] D. Jungnickel, On automorphism groups of divisible designs, Canad. J. Math. vol. 34, pp. 257-297, 1982. · Zbl 0488.05012 · doi:10.4153/CJM-1982-018-x
[39] L.E. Kopilovich, On perfect binary arrays, Electron. Lett. vol. 24, pp. 566-567, 1988. · Zbl 0686.05015 · doi:10.1049/el:19880385
[40] R.G. Kraemer, Proof of a conjecture on Hadamard 2-groups. Preprint. · Zbl 0771.05020
[41] E.S. Lander, Symmetric Designs: An Algebraic Approach. London Mathematical Society Lecture Notes Series 74, Cambridge University Press, Cambridge, 1983. · Zbl 0502.05010
[42] H.D. Lüke, Sequences and arrays with perfect periodic correlation, IEEE Trans. Aerosp. Electron. Syst. vol. 24, pp. 287-294, 1988. · doi:10.1109/7.192096
[43] H.D. Lüke, L. Bömer, and M. Antweiler, Perfect binary arrays, Signal Proc. vol. 17, pp. 69-80, 1989. · doi:10.1016/0165-1684(89)90073-X
[44] F.J. MacWilliams and N.J.A. Sloane, Pseudo-random sequences and arrays, Proc. IEEE vol. 64, pp. 1715-1729, 1976. · doi:10.1109/PROC.1976.10411
[45] S.J. Martin, M.A. Butler, and C.E. Land, Ferroelectric optical image comparator using PLZT thin films, Electron. Lett. vol. 24, pp. 1486-1487, 1988. · doi:10.1049/el:19881014
[46] D.B. Meisner, Families of Menon difference sets, in Annals of Discrete Mathematics: Proc. Combinatorics ’90, Gaeta, Italy, 1990, North-Holland, Amsterdam. In press. · Zbl 0772.05014
[47] P. Kesava Menon, On difference sets whose parameters satisfy a certain relation, Proc. Amer. Math. Soc. vol. 13, pp. 739-745, 1962. · Zbl 0122.01504 · doi:10.2307/2034166
[48] K. Pasedach and E. Haase, Random and guided generation of coherent two-dimensional codes, Optics Comm. vol. 36, pp. 423-428, 1981. · doi:10.1016/0030-4018(81)90182-6
[49] H.J. Ryser, Combinatorial Mathematics, Carus Mathematical Monographs No. 14, Math. Assoc. Amer., Washington, DC, 1963.
[50] N. Zagaglia Salvi, On the non-existence of certain difference sets, in A. Barlotti, M. Marchi, and G. Tallini, editors, Annals of Discrete Mathematics 37: Proc. Combinatorics ’86, Trento, Italy, 1986, North-Holland, Amsterdam, 1988, pp. 479-484.
[51] D. A. Shedd and D.V. Sarwate, Construction of sequences with good correlation properties, IEEE Trans. Inform. Theory vol. IT-25, pp. 94-97, 1979. · doi:10.1109/TIT.1979.1055998
[52] G.P. Sillitto, An extension property of a class of balanced incomplete block designs, Biometrika vol. 44, pp. 278-279, 1957. · Zbl 0077.33702
[53] G.K. Skinner, X-ray imaging with coded masks, Scientific American vol. 259, pp. 66-71, August 1988. · doi:10.1038/scientificamerican0888-84
[54] R. Turyn and J. Storer, On binary sequences, Proc. Amer. Math. Soc. vol. 12, pp. 394-399, 1961. · Zbl 0116.01006 · doi:10.1090/S0002-9939-1961-0125026-2
[55] R.J. Turyn, Character sums and difference sets, Pacific J. Math. vol. 15, pp. 319-346, 1965. · Zbl 0135.05403
[56] R.J. Turyn, Sequences with small correlation, in H.B. Mann, editor, Error Correcting Codes, Wiley, New York, 1968, pp. 195-228.
[57] R.J. Turyn, A special class of Williamson matrices and difference sets, J. Combin. Theory (A) vol. 36, pp. 111-115, 1984. · Zbl 0523.05016 · doi:10.1016/0097-3165(84)90083-9
[58] A. Vincent, Applications of combinatorial designs to the theory of communications, Ph.D. thesis, RHBNC, University of London, 1989.
[59] P. Wild, Infinite families of perfect binary arrays, Electron. Lett. vol. 24, pp. 845-847, 1988. · Zbl 0686.05016 · doi:10.1049/el:19880575
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.