Analytic aspects of the circulant Hadamard conjecture
[Aspects analytiques de la conjecture d’Hadamard circulante]
Annales Mathématiques Blaise Pascal, Tome 21 (2014) no. 1, pp. 25-59.

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é Φ= i+k=j+l q i q k q j q l satisfait Φ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 Φ= i+k=j+l q i q k q j q l satisfies Φ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.

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 = {Teodor Banica and Ion Nechita and Jean-Marc Schlenker},
     title = {Analytic aspects of the circulant Hadamard conjecture},
     journal = {Annales Math\'ematiques Blaise Pascal},
     pages = {25--59},
     publisher = {Annales math\'ematiques Blaise Pascal},
     volume = {21},
     number = {1},
     year = {2014},
     doi = {10.5802/ambp.334},
     mrnumber = {3248220},
     zbl = {1297.05042},
     language = {en},
     url = {https://ambp.centre-mersenne.org/articles/10.5802/ambp.334/}
}
Teodor Banica; Ion Nechita; Jean-Marc Schlenker. Analytic aspects of the circulant Hadamard conjecture. Annales Mathématiques Blaise Pascal, Tome 21 (2014) no. 1, pp. 25-59. doi : 10.5802/ambp.334. https://ambp.centre-mersenne.org/articles/10.5802/ambp.334/

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

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

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

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

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

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

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

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

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

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

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

[12] Göran Björck 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) (NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci.) Volume 315, Kluwer Acad. Publ., Dordrecht, 1990, pp. 131-140 | MR 1081347 | Zbl 0726.43004

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

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

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

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

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

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

[19] John Gilbert; Ziemowit Rzeszotnik The norm of the Fourier transform on finite abelian groups, Ann. Inst. Fourier (Grenoble), Volume 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] T. Gorin Integrals of monomials over the orthogonal group, J. Math. Phys., Volume 43 (2002) no. 6, pp. 3342-3351 | Article | MR 1902484 | Zbl 1060.22005

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

[22] Uffe Haagerup Orthogonal maximal abelian *-subalgebras of the n×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] Uffe Haagerup Cyclic p-roots of prime lengths p and related complex Hadamard matrices, arXiv preprint arXiv:0803.2629 (2008) | MR 2524079

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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