November  2018, 12(4): 691-705. doi: 10.3934/amc.2018041

Bent and vectorial bent functions, partial difference sets, and strongly regular graphs

1. 

Altınbaş University, School of Engineering and Natural Sciences, Bağcılar, 34217 İstanbul, Turkey

2. 

Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Altenbergerstrasse 69, 4040-Linz, Austria

Received  May 2017 Published  September 2018

Bent and vectorial bent functions have applications in cryptography and coding and are closely related to objects in combinatorics and finite geometry, like difference sets, relative difference sets, designs and divisible designs. Bent functions with certain additional properties yield partial difference sets of which the Cayley graphs are always strongly regular. In this article we continue research on connections between bent functions and partial difference sets respectively strongly regular graphs. For the first time we investigate relations between vectorial bent functions and partial difference sets. Remarkably, properties of the set of the duals of the components play here an important role. Seeing conventional bent functions as 1-dimensional vectorial bent functions, some earlier results on strongly regular graphs from bent functions follow from our more general results. Finally we describe a recursive construction of infinitely many partial difference sets with a secondary construction of p-ary bent functions.

Citation: Ayça Çeşmelioğlu, Wilfried Meidl. Bent and vectorial bent functions, partial difference sets, and strongly regular graphs. Advances in Mathematics of Communications, 2018, 12 (4) : 691-705. doi: 10.3934/amc.2018041
References:
[1]

A. Bernasconi and B. Codenotti, Spectral analysis of Boolean functions as a graph eigenvalue problem, IEEE Trans. Comput., 48 (1999), 345-351.  doi: 10.1109/12.755000.

[2]

A. BernasconiB. Codenotti and J. M. VanderKam, A characterization of bent functions in terms of strongly regular graphs, IEEE Trans. Comput., 50 (2001), 984-985.  doi: 10.1109/12.954512.

[3]

A. E. Brouwer, Web database of strongly regular graphs, http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html (online).

[4]

A. Çeşmelioğlu and W. Meidl, A Construction of bent functions from plateaued functions, Des. Codes Cryptogr., 66 (2013), 231-242.  doi: 10.1007/s10623-012-9686-2.

[5]

A. ÇeşmelioğluW. Meidl and A. Pott, On the dual of (non)-weakly regular bent functions and self-dual bent functions, Advances in Mathematics of Communications, 7 (2013), 425-440.  doi: 10.3934/amc.2013.7.425.

[6]

A. ÇeşmelioğluW. Meidl and A. Pott, There are infinitely many bent functions for which the dual is not bent, IEEE Trans. Inform. Theory, 62 (2016), 5204-5208.  doi: 10.1109/TIT.2016.2586081.

[7]

A. ÇeşmelioğluW. Meidl and A. Pott, Vectorial bent functions and their duals, Linear Algebra and its Applications, 548 (2018), 305-320.  doi: 10.1016/j.laa.2018.03.016.

[8]

Y. M. CheeY. Tan and Y. D. Zhang, Strongly regular graphs constructed from $p$-ary bent functions, J. Algebraic Combin., 34 (2011), 251-266.  doi: 10.1007/s10801-010-0270-4.

[9]

E. Z. Chen, Web database of two-weight codes, http://moodle.tec.hkr.se/~chen/research/2-weight-codes/search.php (online).

[10]

E. R. van Dam and M. Muzychuk, Some implications on amorphic association schemes, J. Combin. Theory Ser. A, 117 (2010), 111-127.  doi: 10.1016/j.jcta.2009.03.018.

[11]

T. Feng, B. Wen, Q. Xiang and J. Yin, Partial difference sets from quadratic forms and p-ary weakly regular bent functions, Number Theory and Related Areas, Adv. Lect. Math. (ALM), Int. Press, Somerville, MA, 27 (2013), 25-40.

[12]

T. Helleseth and A. Kholosha, Monomial and quadratic bent functions over the finite fields of odd characteristic, IEEE Trans. Inform. Theory, 52 (2006), 2018-2032.  doi: 10.1109/TIT.2006.872854.

[13]

P. V. KumarR. A. Scholtz and L. R. Welch, Generalized bent functions and their properties, J. Combin. Theory Ser. A, 40 (1985), 90-107.  doi: 10.1016/0097-3165(85)90049-4.

[14]

J. H. van Lint and A. Schrijver, Constructions of strongly regular graphs, two-weight codes and partial geometries by finite fields, Combinatorica, 1 (1981), 63-73.  doi: 10.1007/BF02579178.

[15]

S. L. Ma, A survey of partial difference sets, Des., Codes, Cryptogr., 4 (1994), 221-261.  doi: 10.1007/BF01388454.

[16]

S. Mesnager, Bent Functions. Fundamentals and Results, Springer, 2016. doi: 10.1007/978-3-319-32595-8.

[17]

K. Nyberg, Perfect nonlinear S-boxes. Advances in cryptology-EUROCRYPT '91 (Brighton, 1991), 378-386, Lecture Notes in Comput. Sci., 547, Springer, Berlin, 1991. doi: 10.1007/3-540-46416-6_32.

[18]

A. PottY. TanT. Feng and S. Ling, Association schemes arising from bent functions, Des., Codes, Cryptogr., 59 (2011), 319-331.  doi: 10.1007/s10623-010-9463-z.

[19]

Y. TanA. Pott and T. Feng, Strongly regular graphs associated with ternary bent functions, J. Combin. Theory Ser. A, 117 (2010), 668-682.  doi: 10.1016/j.jcta.2009.05.003.

show all references

References:
[1]

A. Bernasconi and B. Codenotti, Spectral analysis of Boolean functions as a graph eigenvalue problem, IEEE Trans. Comput., 48 (1999), 345-351.  doi: 10.1109/12.755000.

[2]

A. BernasconiB. Codenotti and J. M. VanderKam, A characterization of bent functions in terms of strongly regular graphs, IEEE Trans. Comput., 50 (2001), 984-985.  doi: 10.1109/12.954512.

[3]

A. E. Brouwer, Web database of strongly regular graphs, http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html (online).

[4]

A. Çeşmelioğlu and W. Meidl, A Construction of bent functions from plateaued functions, Des. Codes Cryptogr., 66 (2013), 231-242.  doi: 10.1007/s10623-012-9686-2.

[5]

A. ÇeşmelioğluW. Meidl and A. Pott, On the dual of (non)-weakly regular bent functions and self-dual bent functions, Advances in Mathematics of Communications, 7 (2013), 425-440.  doi: 10.3934/amc.2013.7.425.

[6]

A. ÇeşmelioğluW. Meidl and A. Pott, There are infinitely many bent functions for which the dual is not bent, IEEE Trans. Inform. Theory, 62 (2016), 5204-5208.  doi: 10.1109/TIT.2016.2586081.

[7]

A. ÇeşmelioğluW. Meidl and A. Pott, Vectorial bent functions and their duals, Linear Algebra and its Applications, 548 (2018), 305-320.  doi: 10.1016/j.laa.2018.03.016.

[8]

Y. M. CheeY. Tan and Y. D. Zhang, Strongly regular graphs constructed from $p$-ary bent functions, J. Algebraic Combin., 34 (2011), 251-266.  doi: 10.1007/s10801-010-0270-4.

[9]

E. Z. Chen, Web database of two-weight codes, http://moodle.tec.hkr.se/~chen/research/2-weight-codes/search.php (online).

[10]

E. R. van Dam and M. Muzychuk, Some implications on amorphic association schemes, J. Combin. Theory Ser. A, 117 (2010), 111-127.  doi: 10.1016/j.jcta.2009.03.018.

[11]

T. Feng, B. Wen, Q. Xiang and J. Yin, Partial difference sets from quadratic forms and p-ary weakly regular bent functions, Number Theory and Related Areas, Adv. Lect. Math. (ALM), Int. Press, Somerville, MA, 27 (2013), 25-40.

[12]

T. Helleseth and A. Kholosha, Monomial and quadratic bent functions over the finite fields of odd characteristic, IEEE Trans. Inform. Theory, 52 (2006), 2018-2032.  doi: 10.1109/TIT.2006.872854.

[13]

P. V. KumarR. A. Scholtz and L. R. Welch, Generalized bent functions and their properties, J. Combin. Theory Ser. A, 40 (1985), 90-107.  doi: 10.1016/0097-3165(85)90049-4.

[14]

J. H. van Lint and A. Schrijver, Constructions of strongly regular graphs, two-weight codes and partial geometries by finite fields, Combinatorica, 1 (1981), 63-73.  doi: 10.1007/BF02579178.

[15]

S. L. Ma, A survey of partial difference sets, Des., Codes, Cryptogr., 4 (1994), 221-261.  doi: 10.1007/BF01388454.

[16]

S. Mesnager, Bent Functions. Fundamentals and Results, Springer, 2016. doi: 10.1007/978-3-319-32595-8.

[17]

K. Nyberg, Perfect nonlinear S-boxes. Advances in cryptology-EUROCRYPT '91 (Brighton, 1991), 378-386, Lecture Notes in Comput. Sci., 547, Springer, Berlin, 1991. doi: 10.1007/3-540-46416-6_32.

[18]

A. PottY. TanT. Feng and S. Ling, Association schemes arising from bent functions, Des., Codes, Cryptogr., 59 (2011), 319-331.  doi: 10.1007/s10623-010-9463-z.

[19]

Y. TanA. Pott and T. Feng, Strongly regular graphs associated with ternary bent functions, J. Combin. Theory Ser. A, 117 (2010), 668-682.  doi: 10.1016/j.jcta.2009.05.003.

[1]

Li Zhang, Xiaofeng Zhou, Min Chen. The research on the properties of Fourier matrix and bent function. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 571-578. doi: 10.3934/naco.2020052

[2]

J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413

[3]

Ayça Çeşmelioǧlu, Wilfried Meidl, Alexander Pott. On the dual of (non)-weakly regular bent functions and self-dual bent functions. Advances in Mathematics of Communications, 2013, 7 (4) : 425-440. doi: 10.3934/amc.2013.7.425

[4]

Bimal Mandal, Aditi Kar Gangopadhyay. A note on generalization of bent boolean functions. Advances in Mathematics of Communications, 2021, 15 (2) : 329-346. doi: 10.3934/amc.2020069

[5]

Feng Ma, Jiansheng Shu, Yaxiong Li, Jian Wu. The dual step size of the alternating direction method can be larger than 1.618 when one function is strongly convex. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1173-1185. doi: 10.3934/jimo.2020016

[6]

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

[7]

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

[8]

Sanyi Tang, Wenhong Pang. On the continuity of the function describing the times of meeting impulsive set and its application. Mathematical Biosciences & Engineering, 2017, 14 (5&6) : 1399-1406. doi: 10.3934/mbe.2017072

[9]

Yanfeng Qi, Chunming Tang, Zhengchun Zhou, Cuiling Fan. Several infinite families of p-ary weakly regular bent functions. Advances in Mathematics of Communications, 2018, 12 (2) : 303-315. doi: 10.3934/amc.2018019

[10]

Yuri Latushkin, Alim Sukhtayev. The Evans function and the Weyl-Titchmarsh function. Discrete and Continuous Dynamical Systems - S, 2012, 5 (5) : 939-970. doi: 10.3934/dcdss.2012.5.939

[11]

H. N. Mhaskar, T. Poggio. Function approximation by deep networks. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4085-4095. doi: 10.3934/cpaa.2020181

[12]

Hassan Emamirad, Philippe Rogeon. Semiclassical limit of Husimi function. Discrete and Continuous Dynamical Systems - S, 2013, 6 (3) : 669-676. doi: 10.3934/dcdss.2013.6.669

[13]

Ken Ono. Parity of the partition function. Electronic Research Announcements, 1995, 1: 35-42.

[14]

Tomasz Downarowicz, Yonatan Gutman, Dawid Huczek. Rank as a function of measure. Discrete and Continuous Dynamical Systems, 2014, 34 (7) : 2741-2750. doi: 10.3934/dcds.2014.34.2741

[15]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37

[16]

Junchao Zhou, Yunge Xu, Lisha Wang, Nian Li. Nearly optimal codebooks from generalized Boolean bent functions over $ \mathbb{Z}_{4} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020121

[17]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems and Imaging, 2021, 15 (2) : 315-338. doi: 10.3934/ipi.2020070

[18]

Robert Baier, Thuy T. T. Le. Construction of the minimum time function for linear systems via higher-order set-valued methods. Mathematical Control and Related Fields, 2019, 9 (2) : 223-255. doi: 10.3934/mcrf.2019012

[19]

Giovanni Colombo, Khai T. Nguyen. On the minimum time function around the origin. Mathematical Control and Related Fields, 2013, 3 (1) : 51-82. doi: 10.3934/mcrf.2013.3.51

[20]

Welington Cordeiro, Manfred Denker, Michiko Yuri. A note on specification for iterated function systems. Discrete and Continuous Dynamical Systems - B, 2015, 20 (10) : 3475-3485. doi: 10.3934/dcdsb.2015.20.3475

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (420)
  • HTML views (341)
  • Cited by (0)

Other articles
by authors

[Back to Top]