Top

Designs, Codes and Cryptography

Published in:

09-10-2018

Equiangular tight frames from group divisible designs

Authors: Matthew Fickus, John Jasper

Published in: Designs, Codes and Cryptography | Issue 7/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

An equiangular tight frame (ETF) is a type of optimal packing of lines in a real or complex Hilbert space. In the complex case, the existence of an ETF of a given size remains an open problem in many cases. In this paper, we observe that many of the known constructions of ETFs are of one of two types. We further provide a new method for combining a given ETF of one of these two types with an appropriate group divisible design (GDD) in order to produce a larger ETF of the same type. By applying this method to known families of ETFs and GDDs, we obtain several new infinite families of ETFs. The real instances of these ETFs correspond to several new infinite families of strongly regular graphs. Our approach was inspired by a seminal paper of Davis and Jedwab which both unified and generalized McFarland and Spence difference sets. Our main result is a combinatorial analog of their algebraic results.

previous article Factorization of a class of composed polynomials

next article Maximal contrast color visual secret sharing schemes

Abel R.J.R., Greig M.: BIBDs with small block size. In: Colbourn C.J., Dinitz J.H. (eds.) Handbook of Combinatorial Designs, 2nd edn, pp. 72–79. CRC Press, Boca Raton (2007).

Abel R.J.R., Colbourn C.J., Dinitz J.H.: Mutually orthogonal Latin squares (MOLS). In: Colbourn C.J., Dinitz J.H. (eds.) Handbook of Combinatorial Designs, 2nd edn, pp. 160–193. CRC Press, Boca Raton (2007).

Azarija J., Marc T.: There is no (75,32,10,16) strongly regular graph. arXiv:1509.05933.

Azarija J., Marc T.: There is no (95,40,12,20) strongly regular graph. arXiv:1603.02032.

Bajwa W.U., Calderbank R., Mixon D.G.: Two are better than one: fundamental parameters of frame coherence. Appl. Comput. Harmon. Anal. 33, 58–78 (2012).MathSciNetCrossRefMATH

Bandeira A.S., Fickus M., Mixon D.G., Wong P.: The road to deterministic matrices with the Restricted Isometry Property. J. Fourier Anal. Appl. 19, 1123–1149 (2013).MathSciNetCrossRefMATH

Barg A., Glazyrin A., Okoudjou K.A., Yu W.-H.: Finite two-distance tight frames. Linear Algebra Appl. 475, 163–175 (2015).MathSciNetCrossRefMATH

Bodmann B.G., Elwood H.J.: Complex equiangular Parseval frames and Seidel matrices containing \(p\)th roots of unity. Proc. Am. Math. Soc. 138, 4387–4404 (2010).CrossRefMATH

Bodmann B.G., Paulsen V.I., Tomforde M.: Equiangular tight frames from complex Seidel matrices containing cube roots of unity. Linear Algebra Appl. 430, 396–417 (2009).MathSciNetCrossRefMATH

10.

Bracken C., McGuire G., Ward H.: New quasi-symmetric designs constructed using mutually orthogonal Latin squares and Hadamard matrices. Des. Codes Cryptogr. 41, 195–198 (2006).MathSciNetCrossRefMATH

11.

Brouwer A.E.: Strongly regular graphs. In: Colbourn C.J., Dinitz J.H. (eds.) Handbook of Combinatorial Designs, 2nd edn, pp. 852–868. CRC Press, Boca Raton (2007).

12.

Brouwer A.E.: Parameters of strongly regular graphs. http://www.win.tue.nl/~aeb/graphs/srg/.

13.

Chang K.I.: An existence theory for group divisible designs. Ph.D. Thesis, The Ohio State University (1976).

14.

Chen Y.Q.: On the existence of abelian Hadamard difference sets and a new family of difference sets. Finite Fields Appl. 3, 234–256 (1997).MathSciNetCrossRefMATH

15.

Corneil D., Mathon R. (eds.): Geometry and Combinatorics: Selected Works of J. J. Seidel. Academic Press, New York (1991).

16.

Coutinho G., Godsil C., Shirazi H., Zhan H.: Equiangular lines and covers of the complete graph. Linear Algebra Appl. 488, 264–283 (2016).MathSciNetCrossRefMATH

17.

Davis J.A., Jedwab J.: A unifying construction for difference sets. J. Comb. Theory Ser. A 80, 13–78 (1997).MathSciNetCrossRefMATH

18.

Ding C., Feng T.: A generic construction of complex codebooks meeting the Welch bound. IEEE Trans. Inf. Theory 53, 4245–4250 (2007).MathSciNetCrossRefMATH

19.

Fickus M., Mixon D.G.: Tables of the existence of equiangular tight frames. arXiv:1504.00253 (2016).

20.

Fickus M., Mixon D.G., Tremain J.C.: Steiner equiangular tight frames. Linear Algebra Appl. 436, 1014–1027 (2012).MathSciNetCrossRefMATH

21.

Fickus M., Mixon D.G., Jasper J.: Equiangular tight frames from hyperovals. IEEE Trans. Inf. Theory 62, 5225–5236 (2016).MathSciNetCrossRefMATH

22.

Fickus M., Jasper J., Mixon D.G., Peterson J.D.: Tremain equiangular tight frames. J. Comb. Theory Ser. A 153, 54–66 (2018).MathSciNetCrossRefMATH

23.

Fickus M., Jasper J., Mixon D.G., Peterson J.D.: Hadamard equiangular tight frames. arXiv:1703.05353.

24.

Fickus M., Jasper J., Mixon D.G., Peterson J.D., Watson C.E.: Equiangular tight frames with centroidal symmetry. Appl. Comput. Harmon. Anal. (to appear).

25.

Fickus M., Jasper J., Mixon D.G., Peterson J.D., Watson C.E.: Polyphase equiangular tight frames and abelian generalized quadrangles. Appl. Comput. Harmon. Anal. (to appear).

26.

Fuchs C.A., Hoang M.C., Stacey B.C.: The SIC question: history and state of play. Axioms 6, 21 (2017).CrossRef

27.

Ge G.: Group divisible designs. In: Colbourn C.J., Dinitz J.H. (eds.) Handbook of Combinatorial Designs, 2nd edn, pp. 255–260. CRC Press, Boca Raton (2007).

28.

Godsil C.D.: Krein covers of complete graphs. Aust. J. Comb. 6, 245–255 (1992).MathSciNetMATH

29.

Goethals J.M., Seidel J.J.: Strongly regular graphs derived from combinatorial designs. Can. J. Math. 22, 597–614 (1970).MathSciNetCrossRefMATH

30.

Gordon D.: La Jolla covering repository. https://www.ccrwest.org/diffsets.html.

31.

Grassl M., Scott A.J.: Fibonacci-Lucas SIC-POVMs. J. Math. Phys. 58, 122201 (2017).MathSciNetCrossRefMATH

32.

Holmes R.B., Paulsen V.I.: Optimal frames for erasures. Linear Algebra Appl. 377, 31–51 (2004).MathSciNetCrossRefMATH

33.

Iverson J.W., Jasper J., Mixon D.G.: Optimal line packings from nonabelian groups. arXiv:1609.09836.

34.

Jasper J., Mixon D.G., Fickus M.: Kirkman equiangular tight frames and codes. IEEE Trans. Inf. Theory 60, 170–181 (2014).MathSciNetCrossRefMATH

35.

Jungnickel D., Pott A., Smith K.W.: Difference sets. In: Colbourn C.J., Dinitz J.H. (eds.) Handbook of Combinatorial Designs, 2nd edn, pp. 419–435. CRC Press, Boca Raton (2007).

36.

Lamken E.R., Wilson R.M.: Decompositions of edge-colored complete graphs. J. Comb. Theory Ser. A 89, 149–200 (2000).MathSciNetCrossRefMATH

37.

Lemmens P.W.H., Seidel J.J.: Equiangular lines. J. Algebra 24, 494–512 (1973).MathSciNetCrossRefMATH

38.

Mathon R., Rosa A.: \(2-(v, k,\lambda )\) designs of small order. In: Colbourn C.J., Dinitz J.H. (eds.) Handbook of Combinatorial Designs, 2nd edn, pp. 25–58. CRC Press, Boca Raton (2007).

39.

MacNeish H.F.: Euler squares. Ann. Math. 23, 221–227 (1922).MathSciNetCrossRefMATH

40.

McFarland R.L.: A family of difference sets in non-cyclic groups. J. Comb. Theory Ser. A 15, 1–10 (1973).MathSciNetCrossRefMATH

41.

McGuire G.: Quasi-symmetric designs and codes meeting the Grey-Rankin bound. J. Comb. Theory Ser. A 78, 280–291 (1997).MathSciNetCrossRefMATH

42.

Mohácsy H.: The asymptotic existence of group divisible designs of large order with index one. J. Comb. Theory Ser. A 118, 1915–1924 (2011).MathSciNetCrossRefMATH

43.

Renes J.M.: Equiangular tight frames from Paley tournaments. Linear Algebra Appl. 426, 497–501 (2007).MathSciNetCrossRefMATH

44.

Renes J.M., Blume-Kohout R., Scott A.J., Caves C.M.: Symmetric informationally complete quantum measurements. J. Math. Phys. 45, 2171–2180 (2004).MathSciNetCrossRefMATH

45.

Seidel J.J.: A survey of two-graphs. Coll. Int. Teorie Combin., Atti dei Convegni Lincei, vol. 17, pp. 481–511. Accademia Nazionale dei Lincei, Rome (1976).

46.

Spence E.: A family of difference sets. J. Comb. Theory Ser. A 22, 103–106 (1977).MathSciNetCrossRefMATH

47.

Strohmer T.: A note on equiangular tight frames. Linear Algebra Appl. 429, 326–330 (2008).MathSciNetCrossRefMATH

48.

Strohmer T., Heath R.W.: Grassmannian frames with applications to coding and communication. Appl. Comput. Harmon. Anal. 14, 257–275 (2003).MathSciNetCrossRefMATH

49.

Sustik M.A., Tropp J.A., Dhillon I.S., Heath R.W.: On the existence of equiangular tight frames. Linear Algebra Appl. 426, 619–635 (2007).MathSciNetCrossRefMATH

50.

Szöllősi F.: All complex equiangular tight frames in dimension 3. arXiv:1402.6429.

51.

Tropp J.A.: Complex equiangular tight frames. Proc. SPIE 5914, 591401/1–11 (2005).

52.

Tropp J.A., Dhillon I.S., Heath Jr. R.W., Strohmer T.: Designing structured tight frames via an alternating projection method. IEEE Trans. Inf. Theory 51, 188–209 (2005).MathSciNetCrossRefMATH

53.

Turyn R.J.: Character sums and difference sets. Pac. J. Math. 15, 319–346 (1965).MathSciNetCrossRefMATH

54.

van Lint J.H., Seidel J.J.: Equilateral point sets in elliptic geometry. Indag. Math. 28, 335–348 (1966).MathSciNetCrossRefMATH

55.

Waldron S.: On the construction of equiangular frames from graphs. Linear Algebra Appl. 431, 2228–2242 (2009).MathSciNetCrossRefMATH

56.

Welch L.R.: Lower bounds on the maximum cross correlation of signals. IEEE Trans. Inf. Theory 20, 397–399 (1974).CrossRefMATH

57.

Wilson R.M.: An existence theory for pairwise balanced designs I. Composition theorems and morphisms. J. Comb. Theory Ser. A 13, 220–245 (1972).MathSciNetCrossRefMATH

58.

Xia P., Zhou S., Giannakis G.B.: Achieving the Welch bound with difference sets. IEEE Trans. Inf. Theory 51, 1900–1907 (2005).MathSciNetCrossRefMATH

59.

Zauner G.: Quantum designs: foundations of a noncommutative design theory. Ph.D. Thesis, University of Vienna (1999).

Title: Equiangular tight frames from group divisible designs
Authors: Matthew Fickus
John Jasper
Publication date: 09-10-2018
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 7/2019
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-018-0569-z

Springer Professional

Equiangular tight frames from group divisible designs

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 7/2019

A secure and efficient on-line/off-line group key distribution protocol

A recursive construction of permutation polynomials over with odd characteristic related to Rédei functions

On existence theorems for simple t-designs

Optimal 2-D -optical orthogonal codes and related equi-difference conflict avoiding codes

Erasure combinatorial batch codes based on nonadaptive group testing

Constructing infinite families of low differential uniformity (n, m)-functions with

Premium Partner