Analytic aspects of the circulant Hadamard conjecture

Banica, Teodor; Nechita, Ion; Schlenker, Jean-Marc

Analytic aspects of the circulant Hadamard conjecture
[Aspects analytiques de la conjecture d’Hadamard circulante]

Banica, Teodor ; Nechita, Ion ; Schlenker, Jean-Marc

Annales mathématiques Blaise Pascal, Tome 21 (2014), p. 25-59 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé
Abstract

On étudie la question de comptage pour les matrices d’Hadamard réelles ou complexes circulantes, en utilisant des méthodes analytiques. Notre remarque principale est que pour $| q_{0} | = ... = | q_{N - 1} | = 1$ la quantité $Φ = \sum_{i + k = j + l} \frac{q_{i} q_{k}}{q_{j} q_{l}}$ satisfait $Φ \geq N^{2}$ , avec égalité si et seulement si $q = (q_{i})$ est le vecteur des valeurs propres d’une matrice d’Hadamard complexe circulante. Ceci suggère trois problèmes analytiques, à savoir : (1) la minimisation directe de $Φ$ , (2) l’étude des points critiques de $Φ$ , et (3) le calcul des moments de $Φ$ . On explore ici ces questions, avec plusieurs résultats et conjectures.

We investigate the problem of counting the real or complex Hadamard matrices which are circulant, by using analytic methods. Our main observation is the fact that for $| q_{0} | = ... = | q_{N - 1} | = 1$ the quantity $Φ = \sum_{i + k = j + l} \frac{q_{i} q_{k}}{q_{j} q_{l}}$ satisfies $Φ \geq N^{2}$ , with equality if and only if $q = (q_{i})$ is the eigenvalue vector of a rescaled circulant complex Hadamard matrix. This suggests three analytic problems, namely: (1) the brute-force minimization of $Φ$ , (2) the study of the critical points of $Φ$ , and (3) the computation of the moments of $Φ$ . We explore here these questions, with some results and conjectures.

Publié le : 2014-01-01

MR 3248220 | Zbl 1297.05042

DOI : https://doi.org/10.5802/ambp.334
Classification: 05B20
Mots clés: Matrice d’Hadamard circulante

@article{AMBP_2014__21_1_25_0,
     author = {Banica, Teodor and Nechita, Ion and Schlenker, Jean-Marc},
     title = {Analytic aspects of the circulant Hadamard conjecture},
     journal = {Annales math\'ematiques Blaise Pascal},
     volume = {21},
     year = {2014},
     pages = {25-59},
     doi = {10.5802/ambp.334},
     zbl = {1297.05042},
     mrnumber = {3248220},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AMBP_2014__21_1_25_0}
}

Banica, Teodor; Nechita, Ion; Schlenker, Jean-Marc. Analytic aspects of the circulant Hadamard conjecture. Annales mathématiques Blaise Pascal, Tome 21 (2014) pp. 25-59. doi : 10.5802/ambp.334. http://gdmltest.u-ga.fr/item/AMBP_2014__21_1_25_0/

Bibliographie

[1] Agaian, S. S. Hadamard matrices and their applications, Springer-Verlag, Berlin, Lecture Notes in Mathematics, Tome 1168 (1985), pp. iii+227 | MR 818740 | Zbl 0575.05015

[2] Arasu, K. T.; De Launey, Warwick; Ma, S. L. On circulant complex Hadamard matrices, Des. Codes Cryptogr., Tome 25 (2002) no. 2, pp. 123-142 | Article | MR 1883962 | Zbl 1017.05030

[3] Backelin, Jörgen Square multiples n give infinitely many cyclic n-roots, Reports/Univ. of Stockholm (1989)

[4] Banica, Teo; Hiranandani, Gaurush; Nechita, Ion; Schlenker, Jean-Marc Small circulant complex Hadamard matrices of Butson type, arXiv preprint arXiv:1311.5390 (2013)

[5] Banica, Teo; Nechita, Ion; Schlenker, Jean-Marc Submatrices of Hadamard matrices: complementation results, arXiv preprint arXiv:1311.0764 (2013) | MR 3194951

[6] Banica, Teodor The Gale-Berlekamp game for complex Hadamard matrices, arXiv preprint arXiv:1310.1810 (2013) | MR 3028606

[7] Banica, Teodor; Collins, Benoît; Schlenker, Jean-Marc On orthogonal matrices maximizing the 1-norm, Indiana Univ. Math. J., Tome 59 (2010) no. 3, pp. 839-856 | Article | MR 2779063 | Zbl 1228.15013

[8] Banica, Teodor; Collins, Benoit; Schlenker, Jean-Marc On polynomial integrals over the orthogonal group, J. Combin. Theory Ser. A, Tome 118 (2011) no. 3, pp. 778-795 | Article | MR 2745424 | Zbl 1231.05282

[9] Banica, Teodor; Nechita, Ion Almost Hadamard matrices: the case of arbitrary exponents, Discrete Appl. Math., Tome 161 (2013) no. 16-17, pp. 2367-2379 | Article | MR 3101716 | Zbl 1285.05023

[10] Banica, Teodor; Nechita, Ion; Życzkowski, Karol Almost Hadamard matrices: general theory and examples, Open Syst. Inf. Dyn., Tome 19 (2012) no. 4, pp. 1250024, 26 | Article | MR 3010913 | Zbl 1263.15030

[11] Bengtsson, Ingemar; Bruzda, Wojciech; Ericsson, Åsa; Larsson, Jan-Åke; Tadej, Wojciech; Życzkowski, Karol Mutually unbiased bases and Hadamard matrices of order six, J. Math. Phys., Tome 48 (2007) no. 5, pp. 052106, 21 | Article | MR 2326331 | Zbl 1144.81314

[12] Björck, Göran Functions of modulus $1$ on $Z_{n}$ whose Fourier transforms have constant modulus, and “cyclic $n$ -roots”, Recent advances in Fourier analysis and its applications (Il Ciocco, 1989), Kluwer Acad. Publ., Dordrecht (NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci.) Tome 315 (1990), pp. 131-140 | MR 1081347 | Zbl 0726.43004

[13] Björck, Göran; Fröberg, Ralf A faster way to count the solutions of inhomogeneous systems of algebraic equations, with applications to cyclic $n$ -roots, J. Symbolic Comput., Tome 12 (1991) no. 3, pp. 329-336 | Article | MR 1128248 | Zbl 0751.12001

[14] Bjorck, Goran; Haagerup, Uffe All cyclic p-roots of index 3, found by symmetry-preserving calculations, arXiv preprint arXiv:0803.2506 (2008)

[15] Butson, A. T. Generalized Hadamard matrices, Proc. Amer. Math. Soc., Tome 13 (1962), pp. 894-898 | Article | MR 142557 | Zbl 0109.24605

[16] Collins, Benoît; Śniady, Piotr Integration with respect to the Haar measure on unitary, orthogonal and symplectic group, Comm. Math. Phys., Tome 264 (2006) no. 3, pp. 773-795 | Article | MR 2217291 | Zbl 1108.60004

[17] Craigen, R.; Kharaghani, H. On the nonexistence of Hermitian circulant complex Hadamard matrices, Australas. J. Combin., Tome 7 (1993), pp. 225-227 | MR 1211281 | Zbl 0778.05025

[18] Faugère, Jean-Charles Finding all the solutions of Cyclic $9$ using Gröbner basis techniques, Computer mathematics (Matsuyama, 2001), World Sci. Publ., River Edge, NJ (Lecture Notes Ser. Comput.) Tome 9 (2001), pp. 1-12 | MR 1877437 | Zbl 1030.68112

[19] Gilbert, John; Rzeszotnik, Ziemowit The norm of the Fourier transform on finite abelian groups, Ann. Inst. Fourier (Grenoble), Tome 60 (2010) no. 4, pp. 1317-1346 http://aif.cedram.org/item?id=AIF_2010__60_4_1317_0 | Article | Numdam | MR 2722243 | Zbl 1202.42065

[20] Gorin, T. Integrals of monomials over the orthogonal group, J. Math. Phys., Tome 43 (2002) no. 6, pp. 3342-3351 | Article | MR 1902484 | Zbl 1060.22005

[21] Goyeneche, D. Mutually unbiased triplets from non-affine families of complex Hadamard matrices in dimension 6, J. Phys. A, Tome 46 (2013) no. 10, pp. 105301, 15 | Article | MR 3030161 | Zbl 1264.81074

[22] Haagerup, Uffe Orthogonal maximal abelian $*$ -subalgebras of the $n \times n$ matrices and cyclic $n$ -roots, Operator algebras and quantum field theory (Rome, 1996), Int. Press, Cambridge, MA (1997), pp. 296-322 | MR 1491124 | Zbl 0914.46045

[23] Haagerup, Uffe Cyclic p-roots of prime lengths p and related complex Hadamard matrices, arXiv preprint arXiv:0803.2629 (2008) | MR 2524079

[24] De La Harpe, Pierre; Jones, Vaughan Paires de sous-algèbres semi-simples et graphes fortement réguliers, C. R. Acad. Sci. Paris Sér. I Math., Tome 311 (1990) no. 3, pp. 147-150 | MR 1065880 | Zbl 0707.46039

[25] Horadam, K. J. Hadamard matrices and their applications, Princeton University Press, Princeton, NJ (2007), pp. xiv+263 | MR 2265694 | Zbl 1145.05014

[26] Jedwab, Jonathan; Lloyd, Sheelagh A note on the nonexistence of Barker sequences, Des. Codes Cryptogr., Tome 2 (1992) no. 1, pp. 93-97 | Article | MR 1157481 | Zbl 0762.94009

[27] Jones, V.; Sunder, V. S. Introduction to subfactors, Cambridge University Press, Cambridge, London Mathematical Society Lecture Note Series, Tome 234 (1997), pp. xii+162 | Article | MR 1473221 | Zbl 0903.46062

[28] Lam, T. Y.; Leung, K. H. On vanishing sums of roots of unity, J. Algebra, Tome 224 (2000) no. 1, pp. 91-109 | Article | MR 1736695 | Zbl 1099.11510

[29] De Launey, Warwick On the nonexistence of generalised weighing matrices, Ars Combin., Tome 17 (1984) no. A, pp. 117-132 | MR 746179 | Zbl 0538.05017

[30] De Launey, Warwick; Levin, David A. A Fourier-analytic approach to counting partial Hadamard matrices, Cryptogr. Commun., Tome 2 (2010) no. 2, pp. 307-334 | Article | MR 2719847 | Zbl 1225.05056

[31] Leung, Ka Hin; Schmidt, Bernhard New restrictions on possible orders of circulant Hadamard matrices, Des. Codes Cryptogr., Tome 64 (2012) no. 1-2, pp. 143-151 | Article | MR 2914407 | Zbl 1242.15027

[32] Pólya, Georg Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz, Math. Ann., Tome 84 (1921) no. 1-2, pp. 149-160 | Article | MR 1512028

[33] Popa, Sorin Orthogonal pairs of $*$ -subalgebras in finite von Neumann algebras, J. Operator Theory, Tome 9 (1983) no. 2, pp. 253-268 | MR 703810 | Zbl 0521.46048

[34] Prosen, T.; Seligman, T. H.; Weidenmüller, H. A. Integration over matrix spaces with unique invariant measures, J. Math. Phys., Tome 43 (2002) no. 10, pp. 5135-5144 | Article | MR 1927357 | Zbl 1060.81033

[35] Ryser, Herbert John Combinatorial mathematics, Published by The Mathematical Association of America, The Carus Mathematical Monographs, No. 14 (1963), pp. xiv+154 | MR 150048 | Zbl 0112.24806

[36] Schmidt, Bernhard Cyclotomic integers and finite geometry, J. Amer. Math. Soc., Tome 12 (1999) no. 4, pp. 929-952 | Article | MR 1671453 | Zbl 0939.05016

[37] Szöllősi, Ferenc Exotic complex Hadamard matrices and their equivalence, Cryptogr. Commun., Tome 2 (2010) no. 2, pp. 187-198 | Article | MR 2719838 | Zbl 1228.05097

[38] Szöllősi, Ferenc A two-parameter family of complex Hadamard matrices of order 6 induced by hypocycloids, Proc. Amer. Math. Soc., Tome 138 (2010) no. 3, pp. 921-928 | Article | MR 2566558 | Zbl 1189.15035

[39] Tadej, Wojciech; Życzkowski, Karol A concise guide to complex Hadamard matrices, Open Syst. Inf. Dyn., Tome 13 (2006) no. 2, pp. 133-177 | Article | MR 2244963 | Zbl 1105.15020

[40] Tao, Terence Fuglede’s conjecture is false in 5 and higher dimensions, Math. Res. Lett., Tome 11 (2004) no. 2-3, pp. 251-258 | Article | MR 2067470 | Zbl 1092.42014

[41] Tao, Terence An uncertainty principle for cyclic groups of prime order, Math. Res. Lett., Tome 12 (2005) no. 1, pp. 121-127 | Article | MR 2122735 | Zbl 1080.42002

[42] Turyn, Richard J. Character sums and difference sets, Pacific J. Math., Tome 15 (1965), pp. 319-346 | Article | MR 179098 | Zbl 0135.05403

[43] Werner, R. F. All teleportation and dense coding schemes, J. Phys. A, Tome 34 (2001) no. 35, pp. 7081-7094 (Quantum information and computation) | Article | MR 1863141 | Zbl 1024.81006

[44] Winterhof, Arne On the non-existence of generalized Hadamard matrices, J. Statist. Plann. Inference, Tome 84 (2000) no. 1-2, pp. 337-342 | Article | MR 1747512 | Zbl 0958.05014