Analytic aspects of the circulant Hadamard conjecture

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

doi:10.5802/ambp.334

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

Banica, Teodor ¹ ; Nechita, Ion ² ; Schlenker, Jean-Marc ³

¹ Department of Mathematics, Cergy-Pontoise University, 95000 Cergy-Pontoise, France
² CNRS, Laboratoire de Physique Théorique, IRSAMC, Université de Toulouse, UPS, 31062 Toulouse, France
³ University of Luxembourg, Campus Kirchberg, Mathematics Research Unit, 6 rue Richard Coudenhove-Kalergi, L-1359 Luxembourg

Annales mathématiques Blaise Pascal, Tome 21 (2014) no. 1, pp. 25-59.

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.

MR Zbl

DOI : 10.5802/ambp.334

Classification : 05B20
Keywords: Circulant Hadamard matrix
Mot clés : Matrice d’Hadamard circulante

Affiliations des auteurs :

Banica, Teodor ¹ ; Nechita, Ion ² ; Schlenker, Jean-Marc ³

@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},
     pages = {25--59},
     publisher = {Annales math\'ematiques Blaise Pascal},
     volume = {21},
     number = {1},
     year = {2014},
     doi = {10.5802/ambp.334},
     zbl = {1297.05042},
     mrnumber = {3248220},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/ambp.334/}
}

TY  - JOUR
AU  - Banica, Teodor
AU  - Nechita, Ion
AU  - Schlenker, Jean-Marc
TI  - Analytic aspects of the circulant Hadamard conjecture
JO  - Annales mathématiques Blaise Pascal
PY  - 2014
SP  - 25
EP  - 59
VL  - 21
IS  - 1
PB  - Annales mathématiques Blaise Pascal
UR  - http://www.numdam.org/articles/10.5802/ambp.334/
DO  - 10.5802/ambp.334
LA  - en
ID  - AMBP_2014__21_1_25_0
ER  -

%0 Journal Article
%A Banica, Teodor
%A Nechita, Ion
%A Schlenker, Jean-Marc
%T Analytic aspects of the circulant Hadamard conjecture
%J Annales mathématiques Blaise Pascal
%D 2014
%P 25-59
%V 21
%N 1
%I Annales mathématiques Blaise Pascal
%U http://www.numdam.org/articles/10.5802/ambp.334/
%R 10.5802/ambp.334
%G en
%F 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) no. 1, pp. 25-59. doi : 10.5802/ambp.334. http://www.numdam.org/articles/10.5802/ambp.334/

Bibliographie
Cité par

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

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

[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

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

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

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

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

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

[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., Volume 48 (2007) no. 5, pp. 052106, 21 | DOI | MR | Zbl

[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) (NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci.), Volume 315, Kluwer Acad. Publ., Dordrecht, 1990, pp. 131-140 | MR | Zbl

[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., Volume 12 (1991) no. 3, pp. 329-336 | DOI | MR | Zbl

[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., Volume 13 (1962), pp. 894-898 | DOI | MR | Zbl

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

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

[18] Faugère, Jean-Charles 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 | Zbl

[19] Gilbert, John; Rzeszotnik, Ziemowit The norm of the Fourier transform on finite abelian groups, Ann. Inst. Fourier (Grenoble), Volume 60 (2010) no. 4, pp. 1317-1346 | DOI | Numdam | MR | Zbl

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

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

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

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

[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., Volume 311 (1990) no. 3, pp. 147-150 | MR | Zbl

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

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

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

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

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

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

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

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

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

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

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

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

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

[38] Szöllősi, Ferenc 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 | DOI | MR | Zbl

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

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

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

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

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

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

Cité par Sources :