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.  Google Scholar

[2] E. F. Assmus Jr. and J. D. Key, Designs and Their Codes, Cambridge University Press, Cambridge, 1992.  doi: 10.1017/CBO9781316529836.  Google Scholar
[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.  Google Scholar

[4] T. Beth, D. Jungnickel and H. Lenz, Design Theory, Cambridge University Press, Cambridge, 1986.   Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8]

C. J. Colbourn and J. H. Dinitz, Handbook of Combinatorial Designs, 2nd edition, CRC Press, New York, 2007.  Google Scholar

[9]

P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl., 10 (1973), 1-97.   Google Scholar

[10]

P. Delsarte, Pairs of vectors in the space of an association scheme, Philips Res. Rep., 32 (1977), 373-411.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14] W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, Cambridge, 2003.  doi: 10.1017/CBO9780511807077.  Google Scholar
[15]

P. Keevash, The existence of designs, arXiv: 1401.3665v2 [math.CO]. Google Scholar

[16]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

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.  Google Scholar

[2] E. F. Assmus Jr. and J. D. Key, Designs and Their Codes, Cambridge University Press, Cambridge, 1992.  doi: 10.1017/CBO9781316529836.  Google Scholar
[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.  Google Scholar

[4] T. Beth, D. Jungnickel and H. Lenz, Design Theory, Cambridge University Press, Cambridge, 1986.   Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8]

C. J. Colbourn and J. H. Dinitz, Handbook of Combinatorial Designs, 2nd edition, CRC Press, New York, 2007.  Google Scholar

[9]

P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl., 10 (1973), 1-97.   Google Scholar

[10]

P. Delsarte, Pairs of vectors in the space of an association scheme, Philips Res. Rep., 32 (1977), 373-411.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14] W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, Cambridge, 2003.  doi: 10.1017/CBO9780511807077.  Google Scholar
[15]

P. Keevash, The existence of designs, arXiv: 1401.3665v2 [math.CO]. Google Scholar

[16]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

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]

Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020046
[4]

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

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

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

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

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

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

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

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

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

Constanza Riera, Pantelimon Stănică. Landscape Boolean functions. Advances in Mathematics of Communications, 2019, 13 (4) : 613-627. doi: 10.3934/amc.2019038
[16]

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

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

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

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

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

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (98)
  • HTML views (337)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences