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]

Tingting Pang, Nian Li, Li Zhang, Xiangyong Zeng. Several new classes of (balanced) Boolean functions with few Walsh transform values. Advances in Mathematics of Communications, 2021, 15 (4) : 757-775. doi: 10.3934/amc.2020095
[2]

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
[3]

Nikolaos Halidias, Ioannis S. Stamatiou. Boundary preserving explicit scheme for the Aït-Sahalia mode. Discrete and Continuous Dynamical Systems - B, 2022  doi: 10.3934/dcdsb.2022092
[4]

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

Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113-130. doi: 10.3934/amc.2020046
[6]

Lina Zhang, Li Ma, Shan Chen. Design of the integrated AFS and DYC scheme for vehicles via FTSM and SOSM techniques. Discrete and Continuous Dynamical Systems - S, 2022  doi: 10.3934/dcdss.2022077
[7]

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

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

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

Rabiaa Ouahabi, Nasr-Eddine Hamri. Design of new scheme adaptive generalized hybrid projective synchronization for two different chaotic systems with uncertain parameters. Discrete and Continuous Dynamical Systems - B, 2021, 26 (5) : 2361-2370. doi: 10.3934/dcdsb.2020182
[11]

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 and Management Optimization, 2010, 6 (3) : 621-639. doi: 10.3934/jimo.2010.6.621
[12]

María Chara, Ricardo A. Podestá, Ricardo Toledano. The conorm code of an AG-code. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021018
[13]

Ramalingam Sakthivel, Palanisamy Selvaraj, Yeong-Jae Kim, Dong-Hoon Lee, Oh-Min Kwon, Rathinasamy Sakthivel. Robust $ H_\infty $ resilient event-triggered control design for T-S fuzzy systems. Discrete and Continuous Dynamical Systems - S, 2022  doi: 10.3934/dcdss.2022028
[14]

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
[15]

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

Ruikuan Liu, Dongpei Zhang. Dynamic transitions for the S-K-T competition system. Discrete and Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021277
[17]

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 and Continuous Dynamical Systems - B, 2014, 19 (7) : 2267-2278. doi: 10.3934/dcdsb.2014.19.2267
[18]

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 and Management Optimization, 2018, 14 (2) : 561-582. doi: 10.3934/jimo.2017060
[19]

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

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

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (434)
  • HTML views (389)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy