American Institute of Mathematical Sciences

Advanced
August  2019, 13(3): 477-503. doi: 10.3934/amc.2019030

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

Eun-Kyung Cho 1, , Cunsheng Ding 2,, and  Jong Yoon Hyun 3,

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

Received  August 2018 Published  April 2019

Fund Project: 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)

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: Association scheme, Boolean function, code, Steiner system, t-design, Walsh transform.
Mathematics Subject Classification: Primary: 05B05, 06E30; Secondary: 51E22.
Citation: Eun-Kyung Cho, Cunsheng Ding, Jong Yoon Hyun. A spectral characterisation of $ t $-designs and its applications. Advances in Mathematics of Communications, 2019, 13 (3) : 477-503. doi: 10.3934/amc.2019030
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, 2nd 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), 2nd 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.

show all references

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, 2nd 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), 2nd 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.

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}\} $
Table Options

Download as excel

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}\} $
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 $
Table Options

Download as excel

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 $
[1]

Masaaki Harada, Ethan Novak, Vladimir D. Tonchev. The weight distribution of the self-dual $[128,64]$ polarity design code. Advances in Mathematics of Communications, 2016, 10 (3) : 643-648. doi: 10.3934/amc.2016032
[2]

Hans Rullgård, Eric Todd Quinto. Local Sobolev estimates of a function by means of its Radon transform. Inverse Problems & Imaging, 2010, 4 (4) : 721-734. doi: 10.3934/ipi.2010.4.721
[3]

Ruwu Xiao, Geng Li, Yuping Zhao. On the design of full duplex wireless system with chaotic sequences. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 783-793. doi: 10.3934/dcdss.2019052
[4]

Yulin Zhao. On the monotonicity of the period function of a quadratic system. Discrete & Continuous Dynamical Systems - A, 2005, 13 (3) : 795-810. doi: 10.3934/dcds.2005.13.795
[5]

Jae Man Park, Gang Uk Hwang, Boo Geum Jung. Design and analysis of an adaptive guard channel based CAC scheme in a 3G-WLAN integrated network. Journal of Industrial & Management Optimization, 2010, 6 (3) : 621-639. doi: 10.3934/jimo.2010.6.621
[6]

B. Emamizadeh, F. Bahrami, M. H. Mehrabi. Steiner symmetric vortices attached to seamounts. Communications on Pure & Applied Analysis, 2004, 3 (4) : 663-674. doi: 10.3934/cpaa.2004.3.663
[7]

Yueping Dong, Rinko Miyazaki, Yasuhiro Takeuchi. Mathematical modeling on helper T cells in a tumor immune system. Discrete & Continuous Dynamical Systems - B, 2014, 19 (1) : 55-72. doi: 10.3934/dcdsb.2014.19.55
[8]

Francesco Mainardi. On some properties of the Mittag-Leffler function $\mathbf{E_\alpha(-t^\alpha)}$, completely monotone for $\mathbf{t> 0}$ with $\mathbf{0<\alpha<1}$. Discrete & Continuous Dynamical Systems - B, 2014, 19 (7) : 2267-2278. doi: 10.3934/dcdsb.2014.19.2267
[9]

Wenxue Huang, Yuanyi Pan, Lihong Zheng. Proportional association based roi model. Big Data & Information Analytics, 2017, 2 (2) : 119-125. doi: 10.3934/bdia.2017004
[10]

Alejandro Cataldo, Juan-Carlos Ferrer, Pablo A. Rey, Antoine Sauré. Design of a single window system for e-government services: the chilean case. Journal of Industrial & Management Optimization, 2018, 14 (2) : 561-582. doi: 10.3934/jimo.2017060
[11]

Jongkeun Choi, Ki-Ahm Lee. The Green function for the Stokes system with measurable coefficients. Communications on Pure & Applied Analysis, 2017, 16 (6) : 1989-2022. doi: 10.3934/cpaa.2017098
[12]

Yi Ming Zou. Dynamics of boolean networks. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1629-1640. doi: 10.3934/dcdss.2011.4.1629
[13]

Tuvi Etzion, Alexander Vardy. On $q$-analogs of Steiner systems and covering designs. Advances in Mathematics of Communications, 2011, 5 (2) : 161-176. doi: 10.3934/amc.2011.5.161
[14]

Nora Aïssiouene, Marie-Odile Bristeau, Edwige Godlewski, Jacques Sainte-Marie. A combined finite volume - finite element scheme for a dispersive shallow water system. Networks & Heterogeneous Media, 2016, 11 (1) : 1-27. doi: 10.3934/nhm.2016.11.1
[15]

Ronald E. Mickens. A nonstandard finite difference scheme for the drift-diffusion system. Conference Publications, 2009, 2009 (Special) : 558-563. doi: 10.3934/proc.2009.2009.558
[16]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1
[17]

Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003
[18]

Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45
[19]

E. Compaan. A note on global existence for the Zakharov system on $ \mathbb{T} $. Communications on Pure & Applied Analysis, 2019, 18 (5) : 2473-2489. doi: 10.3934/cpaa.2019112
[20]

Qi Wang. Global solutions of a Keller--Segel system with saturated logarithmic sensitivity function. Communications on Pure & Applied Analysis, 2015, 14 (2) : 383-396. doi: 10.3934/cpaa.2015.14.383

2017 Impact Factor: 0.564

Tools

Metrics

  • PDF downloads (54)
  • HTML views (177)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences