A spectral characterisation of $ t $-designs and its applications

Eun-Kyung Cho; Cunsheng Ding; Jong Yoon Hyun

doi:10.3934/amc.2019030

Article Contents

2019, Volume 13, Issue 3: 477-503. Doi: 10.3934/amc.2019030

This issue Previous Article A subspace code of size

$ \bf{333} $

in the setting of a binary

$ \bf{q} $

-analog of the Fano plane Next Article A conjecture on permutation trinomials over finite fields of characteristic two

A spectral characterisation of $ t $-designs and its applications

1.
Department of Mathematics, Pusan National University, Republic of Korea
2.
Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong, China
3.
Korea Institute for Advanced Study (KIAS), Seoul, Republic of Korea

^* Corresponding author
^* Corresponding author

Received: July 31, 2018

Published: August 2019

C. Ding was supported by The Hong Kong Grants Council, Proj. No. 16300418. J. Y. Hyun was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MEST) (NRF-2017R1D1A1B05030707)

Abstract Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

There are two standard approaches to the construction of $ t $-designs. The first one is based on permutation group actions on certain base blocks. The second one is based on coding theory. The objective of this paper is to give a spectral characterisation of all $ t $-designs by introducing a characteristic Boolean function of a $ t $-design. The spectra of the characteristic functions of $ (n-2)/2 $-$ (n, n/2, 1) $ Steiner systems are determined and properties of such designs are proved. Delsarte's characterisations of orthogonal arrays and $ t $-designs, which are two special cases of Delsarte's characterisation of $ T $-designs in association schemes, are slightly extended into two spectral characterisations. Another characterisation of $ t $-designs by Delsarte and Seidel is also extended into a spectral one. These spectral characterisations are then compared with the new spectral characterisation of this paper.

Keywords:

Mathematics Subject Classification: Primary: 05B05, 06E30; Secondary: 51E22.

Citation:

Full Text(HTML)

Table 1. Spectrum of $ f_{ {\mathbb{D}}} $

Weight of $ w $	Multiset $ \{ \hat{f}_{ {\mathbb{D}}}(w) \} $
$ 0, 12 $	$ \{ 132 \} $
$ 1, 11 $	$ \{ 0^{12} \} $
$ 2, 10 $	$ \{ -12^{66} \} $
$ 3, 9 $	$ \{ 0^{220} \} $
$ 4, 8 $	$ \{ 4^{495} \} $
$ 5, 7 $	$ \{ 0^{792} \} $
$ 6 $	$ \{ -12^{792}, 52^{132}\} $

| Show Table

DownLoad: CSV

Table 2. Weight distribution

Weight $ w $	No. of codewords $ A_w $
$ 0 $	$ 1 $
$ 132 $	$ 1 $
$ 2^{11}-12 $	$ 924 $
$ 2^{11} $	$ 6143 $
$ 2^{11}+4 $	$ 990 $
$ 2^{11}+52 $	$ 132 $
$ 2^{11}+132 $	$ 1 $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	W. O. Alltop, Extending t-designs, J. Comb. Theory A, 18 (1975), 177-186. doi: 10.1016/0097-3165(75)90006-0.
[2]	E. F. Assmus Jr. and J. D. Key, Designs and Their Codes, Cambridge University Press, Cambridge, 1992. doi: 10.1017/CBO9781316529836.
[3]	A. H. Baartmans, I. Bluskov and V. D. Tonchev, The Preparata codes and a class of 4-designs, J. Combinatorial Designs, 2 (1994), 167-170. doi: 10.1002/jcd.3180020307.
[4]	T. Beth, D. Jungnickel and H. Lenz, Design Theory, Cambridge University Press, Cambridge, 1986.
[5]	A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin Heidelberg, 1989. doi: 10.1007/978-3-642-74341-2.
[6]	C. Carlet and C. Ding, Nonlinearities of S-boxes, Finite Fields and Their Applications, 13 (2007), 121-135. doi: 10.1016/j.ffa.2005.07.003.
[7]	S. Chang and J. Y. Hyun, Linear codes from simplicial complexes, Des. Codes Cryptogr., 86 (2018), 2167-2181. doi: 10.1007/s10623-017-0442-5.
[8]	C. J. Colbourn and J. H. Dinitz, Handbook of Combinatorial Designs, 2^nd edition, CRC Press, New York, 2007.
[9]	P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl., 10 (1973), 1-97.
[10]	P. Delsarte, Pairs of vectors in the space of an association scheme, Philips Res. Rep., 32 (1977), 373-411.
[11]	P. Delsarte and J. J. Seidel, Fisher type inequalities for Euclidean t-designs, Linear Algebra and Its Applications, 114/115 (1989), 213-230. doi: 10.1016/0024-3795(89)90462-X.
[12]	C. Ding, A construction of binary linear codes from Boolean functions, Discrete Mathematics, 339 (2016), 2288-2303. doi: 10.1016/j.disc.2016.03.029.
[13]	C. Ding and Z. Zhou, Parameters of 2-designs from some BCH codes, in: Codes, Cryptography and Information Security (eds. S. El Hajji, A. Nitaj and E. M. Souidi), Lecture Notes in Computer Science, Vol. 10194, Springer, (2017), 110–127.
[14]	W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, Cambridge, 2003. doi: 10.1017/CBO9780511807077.
[15]	P. Keevash, The existence of designs, arXiv: 1401.3665v2 [math.CO].
[16]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.
[17]	L. Teirlinck, Nontrivial t-designs without repeated blocks exist for all t, Discrete Math., 65 (1987), 301-311. doi: 10.1016/0012-365X(87)90061-6.
[18]	V. D. Tonchev, A class of Steiner 4-wise balanced designs derived from Preparata codes, J. Combinatorial Designs, 4 (1996), 203-204. doi: 10.1002/(SICI)1520-6610(1996)4:3<203::AID-JCD3>3.0.CO;2-J.
[19]	V. D. Tonchev, Codes and designs, in: Handbook of Coding Theory (eds. V. S. Pless and W. C. Huffman), Vol. Ⅱ, Elsevier, Amsterdam, (1998), 1229–1267.
[20]	V. D. Tonchev, Codes, in Handbook of Combinatorial Designs (eds. C. J. Colbourn and J. H. Dinitz), 2^nd edition, CRC Press, New York, (2007), 677–701.
[21]	T. Wadayama, T. Hada, K. Wakasugi and M. Kasahara, Upper and lower bounds on maximum nonlinearity of n-input m-output Boolean function, Designs, Codes Cryptography, 23 (2001), 23-33. doi: 10.1023/A:1011207501748.