数理解析研究所講究録
第 1872 巻 2014 年 39-48

39

MUTUALLY UNBIASED BASES, GAUSS SUMS AND THE
ASYMPTOTIC EXISTENCE OF BUTSON HADAMARD MATRICESFERENC SZ\"OLL\H{O}SI
Dedicated to the memory of Alton Thomas Butson (1926–1997)

ABSTRACT. In this paper we utilize a recent block construction due to McNulty and Weigert[25] and provide a new and more transparent proof of some of the results of Butson [3],Dawson [7] and de Launey and Dawson [8] on Butson-type complex Hadamard matrices.

2000 Mathematics Subject Classification. Primary $05B20$ , secondary $46L10.$
Keywords and phrases. Complex Hadamard matrix, Butson-type, Mutually unbiased
basis
1. INTRODUCTION
This paper is based on the talk given at a RIMS Symposium on Research on finite groups
and their representations, vertex operator algebras, and algebraic combinatorics, RIMS, Kyoto, January 7-10, 2013.
Hadamard matrices, real or generalized, have many applications in mathematics and quantum information theory.
real Hadamard matrix $H$ of order is anmatrix with
$A$$n\cross n$$n$$(-1,1)$ entries,

such that $HH^{T}=nI$ holds, whereis the identity matrix. Thus therows and columns of such a matrix are pairwise orthogonal.
real Hadamard matrix isnormalized, if the entries in its first row and column are all 1. Deciding the existence ofreal Hadamard matrices is a long standing open problem in combinatorics. The Hadamard
conjecture asserts that for every doubly even there exist a real Hadamard matrix. The
difficulty of this conjecture lead to the study of various generalizations of real Hadamard
matrices, including weighing matrices [20], modular Hadamard matrices [22] and complex
Hadamard matrices [30]. Studying these more general problems will hopefully shed somelight to this famous unresolved conjecture. Investigating the existence and structural properties of complex Hadamard matrices by the physicists community resulted in a number of
exciting new developments in this field very recently [24], $[25]$ . In particular, the concept ofmutually unbiased basis [13] turned out to be a valuable tool constructing new weighing andHadamard matrices [15].
$I$

$A$

$n$

In this paper we study a class of complex Hadamard matrices, which were introduced by
Butson in 1951 [3]. A Butson-type complex Hadamard matrix $H$ of order is anmatrixwhose all entries are some complex qth root of unity, satisfying $HH^{*}=nIwhere*$ denotes
the Hermitian transpose. We denote these matrices by $BH$ $(n, q)$ .
complex Hadamard
matrix may be thought of as the limiting caseof the $BH$ $(n, q)$ matrices. We say thatthe entries of such a matrix are unimodular.
$n$$n\cross n$$A$$qarrow\infty$

Date: May, 2013.
This work was supported by the Hungarian National Research Fund OTKA K-77748 and by the Grantsin-Aid for Scientific Research program of Japan $24\cdot 02807.$

40
FERENC SZ\"OLL\’OSI

It is well known that $BH$ $(n,4)$ matrices lead to the construction of real Hadamard matrices of order $2n$ . This result has substantially been improved in a breakthrough paper byCompton, Craigen and de Launey [4] who pointed out that $BH$ $(n, 6)$ matrices without any$(-1,1)$ entries lead to the construction of real Hadamard matrices of order $4n$ . Determining
the exact relation between $BH$ $(n, q)$ and real Hadamard matrices seems to be a challenging,yet extremely rewarding assignment.
It is worthwhile noting that Butson-type complex Hadamard matrices also have current
applications in frame theory [2], [29] and coding theory [1], [14], among other things [19].
The goal of this paper is to shed new light onto some classical constructions of Butson-typecomplex Hadamard matrices. We use a new, non-trivial block construction due to McNulty
and Weigert [25] and give a short proof to the existence of $BH$ $(2p,p)$ matrices for all primes. Then we show how these ideas can be used to settle the existence of $BH$ $(4p,p)$ matrices.
We believe that our approach is more transparent that of Dawson’s [7].
It is known that if is a prime number and a $BH$ $(n,p)$ matrix exists then $n=tp$ forsome positive integer $t[2],$ $[33]$ . However, determining those values for which there exists
a $BH$ $(tp,p)$ matrix is already unresolved for $p=2$ . The best asymptotic result in the realcase is due to Livinskyi [23], whose methods were influenced by work of Craigen [6], deLauney [10] and Seberry [31]. The analogous asymptotic result in the Butson case is due tode Launey and Dawson [8].
The outline of this paper is as follows. In Section 2 we first recall some number theoretic
tools essential to our results and then discuss some properties of mutually unbiased bases.
In Section 3 we present a construction of $BH$ $(4p,p)$ matrices which then will subsequently
be generalized in Section 4. To improve the readability of the main text, two rather large
matrices were moved to the Appendix.

$p$

$p$

$t$

2. PRELIMINARIESWe begin this section with fixing some notation. Throughout this paper is a prime
the Legendre symbol. We denote by $i=\sqrt{-1}$ the complex
number, and we denote byimaginary unit and introduce a scaling factor , which depends only on the prime number
as follows:$p$$(_{\overline{p}})$$\sigma_{p}$

$p$

(1)

$\sigma_{p}:=\frac{1}{\sqrt{p}}(-i)^{1/2-(\frac{-1}{p})/2}=\{\begin{array}{ll}1/\sqrt{p} if p\equiv 1(mod 4)-i/\sqrt{p} if p\equiv 3(mod 4)\end{array}$. Further, we use the following
Henceforth 7 will refer to the complex conjugate ofany
we define the exponential function
notation: for a prime number and forasWith this notation the Fourier matrix can be described as$e_{p}((i-1)(j-1))$ , which is a well-known example of $BH$ $(p,p)$ matrices.
Next we recall some standard facts from number theory which will be needed later. We
refer the reader to the monograph [18] for details.
Gauss proved that if $p\geq 3$ is a prime number, then$z\in \mathbb{C}$$p$$z\in \mathbb{C}$$e_{p}(z);=e^{\frac{2\pi I}{p}z}$(2)$\mathbb{R}om$$[\dot{F}_{p}]_{i,j}=$$\sum_{k=1}^{p}e_{p}(k^{2})=\{\begin{array}{ll}\sqrt{p} if p\equiv 1(mod 4)i\sqrt{p} if p\equiv 3(mod 4)\end{array}$this, it is easy to derive the following.

41
THE ASYMPTOTIC EXISTENCE OF BUTSON HADAMARD MATRICES

Lemma 2.1 (Quadratic Gauss sum). Let $p\geq 3$ be a prime number,$\sum_{k=1}^{p}e_{p}(ak^{2}+bk)=p\overline{\sigma_{p}}(\frac{a}{p})e_{p}(-2^{p-3}a^{p-2}b^{2})$$(a, b)\in \mathbb{Z}_{p}^{*}\cross \mathbb{Z}_{p}$. Then.

Proof. We use (2) and proceed by completing the square as follows:$\sum_{k=1}^{p}e_{p}(ak^{2}+bk)=e_{p}(-2^{p-3}a^{p-2}b^{2})\sum_{k=1}^{p}e_{p}(a(k+2^{p-2}a^{p-2}b)^{2})$$=p \overline{\sigma_{p}}(\frac{a}{p})e_{p}(-2^{p-3}a^{p-2}b^{2})$.

$\square$

The following is a deep result due to Andr\’e Weil.

Theorem 2.2 (Weil, [32]). Let $p\geq 3$ be a prime number. For any integer $m$ satisfying$1\leq m\leq p-1$ and for distinct, we have$a_{1},$(3)$a_{2},$$\ldots,$$a_{m}\in \mathbb{Z}_{p}$$| \sum_{k=1}^{p}\prod_{i=1}^{m}(\frac{k+a_{i}}{p})|\leq(m-1)\sqrt{p}.$The next result is interesting in its own, and will be a key ingredient to our construction.

Proposition 2.3 (cf. Hudson [16]). Let
residuesuch that$p$be a prime number. There exists a quadratic$r\in \mathbb{Z}_{p}$$( \frac{r}{p})=-(\frac{r+3}{p})=(\frac{r+6}{p})=-(\frac{r+8}{p})=-(\frac{r+11}{p})=(\frac{r+16}{p})=1,$

if and only if $p\in\{7,29,31,41,47,59,61\}$ or$p\geq 71.$

The argument is somewhat standard. We follow the one presented in [16].

Proof. It is easy to verify the statement for all primes $p<71$ . Therefore we can assume that$p\geq 71$. Let us define the quantity$S= \sum_{r=1}^{p-17}((\frac{r}{p})+1)((\frac{r+3}{p})-1)((\frac{r+6}{p})+1)$$\cross((\frac{r+8}{p})-1)((\frac{r+11}{p})-1)((\frac{r+16}{p})+1)$.

Note that each term in the sum is either or $-64$ , therefore if $S<0$ then clearly exists
an integer $1\leq r\leq p-17$ as claimed. After expanding the brackets we can rearrange theterms by collecting together products of Legendre symbols with the same number of factors.
We use the notation $:=\{0,3,6,8,11,16\}$ and we denote a nonempty subset
by. We have$0$$S$$\mathcal{A}\subseteq S$$\mathcal{A}=\{a_{1}, a_{2}, \ldots, a_{|\mathcal{A}|}\}$$S= \sum_{r=1}^{p-17}(-1)+|\mathcal{A}|\geq 1\sum_{\mathcal{A}\subseteq S}(-1)^{\xi(\mathcal{A})}\sum_{r=1}^{p-17}\prod_{i=1}^{|\mathcal{A}|}(\frac{r+a_{i}}{p})$,42
FERENC 8Z\"OLL\’OSIdenotes either or 1. We complete the sums by adding up the missing 17 terms
whereand, after using the triangle inequality, we apply Weil’s estimate (3) to conclude that foreach nonempty$0$$\xi(\mathcal{A})$$\mathcal{A}\subseteq S$$|(-1)^{\xi(A)} \sum_{r=1}^{p-17}\prod_{i=1}^{|A|}(\frac{r+a_{i}}{p})|\leq(|\mathcal{A}|-1)\sqrt{p}+17$

holds. Therefore$|S+p-17| \leq\sum_{i=1}^{6}(\begin{array}{l}6i\end{array})((i-1)\sqrt{p}+17)=1071+129\sqrt{p}.$If $S<17-p$ then $S<0$ follows. Otherwise, if $S\geq 17-p$ then for $p\geq 18757$ we find that
$S\leq 1088+129\sqrt{p}-p<0.$

It remains to be seen that all primes in the range $71\leq p<18757$ satisfy the claim. Thiscan be easily verified by computers.
After these number theoretic preliminaries we now turn to the discussion of mutually
and , are called mutually unbiased, if
unbiased bases. Two orthonormal bases of$f\rangle|=1/\sqrt{d}.$collection of orthonormal bases
we haveandfor every
are called (pairwise) mutually unbiased, if any two of them are unbiased.
Mutually unbiased bases form a fundamental concept in quantum tomography [13]. We
note that it is a major open problem to decide the maximum number of pairwise mutually
unbiased bases of non prime power orders [13], [24].
Throughout this paper we identify these bases with matrices of size whose column vectors
are the respective basis vectors. In this terminology, two unitary matrices $K$ and of size
is a complex Hadamard matrix.
are unbiased if and only if
Next we recall a construction of a complete set of mutually unbiased bases in prime orders.
We denote by $D$ the following diagonal matrix once and for all:$\square$$\mathbb{C}^{d},$$e\in \mathcal{B}_{1}$$\mathcal{B}_{1},$$|\langle e,$$f\in \mathcal{B}_{2}$$\mathcal{B}_{1}$$\mathcal{B}_{2}$$A$$\mathcal{B}_{k}$$\mathcal{B}_{2},$$\ldots,$

$d$

$L$

$\sqrt{d}K^{*}L$

$d$

(4)

$D$ $:=$

diag $[e_{p}(0^{2}), e_{p}(1^{2}), \ldots, e_{p}((p-1)^{2})].$

as in (4). Then the set
be a prime number and$p+1$
mutually
unbiased bases incollection
a
of
forms

Lemma 2.4 (See e. g. [17]). Let

$D$

$p$

$\mathbb{C}^{p}.$$\{I_{p}, \frac{1}{\sqrt{p}}F_{p}, \frac{1}{\sqrt{p}}DF_{p}, \ldots, \frac{1}{\sqrt{p}}D^{p-1}F_{p}\}$

Proof. It is clear that each of the matrices are unitary and hence, the identity matrix$I_{p}$

the productis unbiased to all further matrices. It remains to be seen that for all
We usematrix,
unimodular.
e.
its
entriesarei.
complex
Hadamardadescribes. In particular, we get
Lemma 2.1 to compute the $(i,j)$ th entry of the matrix$a\in \mathbb{Z}_{p}^{*}$$\frac{1}{\sqrt{p}}F_{p}^{*}D^{a}F_{p}$$F_{p}^{*}D^{a}F_{p}$(5)$[F_{p}^{*}D^{a}F_{p}]_{i,j}= \sum_{k=1}^{p}e_{p}(a(k-1)^{2}+(j-i)(k-1))=p\overline{\sigma_{p}}(\frac{a}{p})e_{p}(-2^{p-3}a^{p-2}(j-i)^{2})$.
$\square$Remark 2.5. From (5) it follows that the entries of the matrixof unity, or their negative, depending on the number$\sigma_{p}F_{p}^{*}D^{a}F_{p}$are either pth roots$a\in \mathbb{Z}_{p}^{*}.$’s construction [12]) is a fundaThe generalized Kronecker product (also called as
matrices of composite
complex
Hadamardofmental method obtaining parametric families
orders.
$Dit\dot{a}$43
THE ASYMPTOTIC EXISTENCE OF BUTSON HADAMARD MATRICES

Lemma 2.6. Let
be a complex Hadamard matrix of order andbe complex Hadamard matrices of order $m$ . Then the following block matrix$H=[h_{ij}]_{i,j=1}^{n}$$M=H\otimes[L_{1} L_{2} .

.

.

$n$

$L_{1},$ $L_{2},$$\ldots,$$L_{n}$

L_{n}]:=\{\begin{array}{llll}h_{11}L_{1} h_{12}L_{2} \cdots h_{1n}L_{n}h_{21}L_{1} h_{22}L_{2} h_{2n}L_{n}\vdots \ddots \vdots h_{n1}L_{1} h_{n2}L_{2} \cdots h_{nn}L_{n}\end{array}\}$is a complex Hadamard matrix of order $mn.$

Proof. It is clear that all entries of $M$ are unimodular. The identity $MM^{*}=mnI_{mn}$ follows
immediately upon block-multiplication.
$\square$

We conclude this section with our final ingredient, which is a remarkable generalization ofLemma 2.6.
Proposition 2.7 (McNulty-Weigert, [25]). Let
be a complex Hadamard matrix
$n,$
order
and
be unitary matrices of order $m$ , such thatofis unbiased to. Then the matrix
for all $i,j=1,2,$$H=[h_{ij}]_{i,j=1}^{n}$$K_{1},$ $K_{2},$$\ldots,$$K_{n}$$L_{1},$ $L_{2},$$L_{j}$$\ldots,$$\ldots,$$L_{n}$$K_{i}$$n$$M=\sqrt{m}\{\begin{array}{llll}h_{11}K_{1}^{*}L_{1} h_{12}K_{1}^{*}L_{2} \cdots h_{1n}K_{1}^{*}L_{n}h_{21}K_{2}^{*}L_{1} h_{22}K_{2}^{*}L_{2} h_{2n}K_{2}^{*}L_{n}\vdots \ddots \vdots h_{n1}K_{n}^{*}L_{1} h_{n2}K_{n}^{*}L_{2} \cdots h_{nn}K_{n}^{*}L_{n}\end{array}\}$is a complex Hadamard matrix of order $mn.$

Proof. On the one hand the unbiasedness condition ensures that all entries are unimodular. On the other hand the identity $MM^{*}=mnI_{mn}$ follows immediately upon blockmultiplication. Thus the array describes a complex Hadamard matrix.

$\square$

3. THE EXISTENCE OF BH $(4p, p)$ MATRICESMcNulty and Weigert have successfully constructed various new and interesting examples
of $BH$ $(n, q)$ matrices of small orders [25]. Among other things they have essentially rediscovered the following classical theorem of Butson. We include this here as a trivial warm-up
result.

Theorem 3.1 (Butson, [2]). Let $p\geq 3$ be a prime number, and let $1<s<p$ be a quadratic
nonresidue modulo . Then the matrix$p$$M=\{\begin{array}{ll}I_{p} 00 \sigma_{p}F_{p}^{*}D\end{array}\}[F_{p}F_{p} -D^{s-1}F_{p}D^{s-1}F_{p}]=\{\begin{array}{ll}F_{p} D^{s-1}F_{p}\sigma_{p}F_{p}^{*}DF_{p} -\sigma_{p}F_{p}^{*}D^{s}F_{p}\end{array}\},$

is

$a$

$BH$ $(2p,p)$matrix, where$\sigma_{p}$and $D$ are described by (1) and (4), respectively.

Proof. Follows immediately from Lemma 2.4, Remark 2.5 and Proposition 2.7.

$\square$Now we proceed further, and consider areal Hadamard matrix $H$ , and apply the
McNulty-Weigert construction to obtain the following result.
$4\cross 4$

44
FERENC sz\"o $LL$

$SI$

Proposition 3.2. Let $p\geq 3$ be a prime number, and assume that there exists
such that$(\alpha, \beta, \gamma)\in$$\mathbb{Z}_{p}\cross \mathbb{Z}_{p}\cross \mathbb{Z}_{p}$$( \frac{\alpha+1}{p})=(\frac{\beta+4}{p})=(\frac{\gamma+9}{p})=1$,

and$( \frac{\alpha+4}{p})=(\frac{\alpha+9}{p})=(\frac{\beta+1}{p})=(\frac{\beta+9}{p})=(\frac{\gamma+1}{p})=(\frac{\gamma+4}{p})=-1$

holds. Then
(6)

is

$a$

$M_{p}(\alpha, \beta,\gamma)=[\sigma_{p}F_{p}^{*}D^{9}F_{p}\sigma_{p}F_{p}^{*}D^{4}F_{p}\sigma_{p}F_{p}^{*}DF_{p}F_{p} -\sigma_{p}F_{p}^{*}D^{\alpha+4}F_{p}-\sigma_{p}F_{p}^{*}D^{\alpha+9}F_{p}\sigma_{p}F_{p}^{*}D^{\alpha+1}F_{p}D^{\alpha}F_{p} -\sigma_{p}F_{p}^{*}D^{\beta+1}F_{p}-\sigma_{p}F_{p}^{*}D^{\beta+9}F_{p}\sigma_{p}F_{p}^{*}D^{\beta+4}F_{p}D^{\beta}F_{p} -\sigma_{p}F_{p}^{*}D^{\gamma+4}F_{p}-\sigma_{p}F_{p}^{*}D^{\gamma+1}F_{p}\sigma_{p}F_{p}^{*}D^{\gamma+9}F_{p}D^{\gamma}F_{p}]$$BH$ $(4p,p)$matrix, where$\sigma_{p}$and $D$ are described by (1) and (4), respectively.

Proof. Follows immediately from Lemma 2.4, Remark 2.5 and Proposition 2.7.

$\square$satisfying the conditions of PropoIn Table 1 we have exhibited several triplets
sition 3.2 thus yielding examples of $BH$ $(4p,p)$ matrices.
$(\alpha, \beta, \gamma)$

TABLE 1. Triplets, yielding $BH$ $(4p,p)$ matrices via (6) for several values of$p.$

The following is a special case of a result of Dawson.

Theorem 3.3 (Dawson, [7]). There exists$a$$BH$ $(4p,p)$matrix for every prime number$p.$

Proof. The case $p=2$ is trivial, while the sporadic cases, corresponding to $p=3$ and $p=5$

are contained in the Appendix. Table 1 displays further 9 values of for which the existence$p$of $BH$ $(4p,p)$ matrices follow via the array described in (6).
Hence we can assume that is a prime number for which Proposition 2.3 applies, andsuch that the matrix $M_{p}(r-1, r+2, r+7)$ ,therefore there exist a quadratic residue
described by formula (6) in Proposition 3.2 is a $BH$ $(4p,p)$ matrix, as required.
$p$$r\in \mathbb{Z}_{p}$$\square$

4. THE DOUBLY EVEN CASE
The aim of this section is to generalize the methods presented in Section 3 and provide an
asymptotic result for the existence of $BH$ $(np,p)$ matrices for doubly even (see Theorem 4.1).
The idea is to blow up a real Hadamard matrix $H$ via the McNulty-Weigert construction
with similar ingredients what we used in the construction of (6). Let $H$ be a normalized real
Hadamard matrix of order $n\geq 4$ , and let us consider the following matrix:
$n$

(7)

$M(r) :=diag[I_{p}, \sigma_{p}F_{p}^{*}D, \sigma_{p}F_{p}^{*}D^{4}, \ldots, \sigma_{p}F_{p}^{*}D^{(n-1)^{2}}]$$\cross(H\otimes[F_{p}, D^{r}F_{p}, D^{r+(n-1)^{2}}F_{p}, \ldots, D^{r+(n-2)(n-1)^{2}}F_{p}])$.

45
THE ASYMPTOTIC EXISTENCE OF BUTSON HADAMARD MATRICESThis new array $M(r)$ has the property that (upon multiplying together its defining factors)
the exponents of $D$ are different, so that we can prescribe them to be either quadratic
residues or nonresidues depending on the underlying plus or minus $sign$ inherited from $H.$
To conclude that such a prescribed choice of exponents indeed exist for large we use
Hudson’s idea combined with Weil’s estimate in exactly the same way as in the $BH$ $(4p,p)$
$p$

case.

Theorem 4.1 (cf. [8]). Let be the order of a real Hadamard matrix, and $p>2^{2n^{2}+1}$ be aprime number. Then there exist $BH$ $(np,p)$ matrix.
$n$

$a$

We remark here that the obtained bound on is considerably larger than the one given
in [8]. The presented proof here serves illustrative purposes only.
$p$

Proof. We assume thatand take any normalized real Hadamard matrix $H.$
Our aim is to prove that there exist an
such that the array $M(r)$ , described by (7), is
composed of pth roots of unity. We introduce the following sets $:=\{1,4,9, \ldots, (n-1)^{2}\},$$:=\{0, (n-1)^{2},2(n-1)^{2}, \ldots, (n-2)(n-1)^{2}\}$ , and further$:=\{b+c:b\in \mathcal{B}, c\in C\}$
with distinct entries. Next we define, similarly as before, the quantity$n\geq 4,$ $p>2^{2n^{2}+1}$$r\in \mathbb{Z}_{p}$$\mathcal{B}$$C$$\mathcal{S}$$s_{1},$$s_{2},$(8)$\ldots,$ $s_{(n-1)^{2}}$$S= \sum_{r=1}^{p-(n-1)^{3}-1}\prod_{s_{i}\in S}((\frac{r+s_{i}}{p})\pm 1)$,

where the plus or minus $sign$ in a factor
is uniquely determined by the $sign$pattern of the underlying real Hadamard matrix $H$ as follows: there are unique indices$k\in\{1,2, \ldots, n-1\}$ such that $s_{i}=b_{j}+c_{k},$and $c_{k}\in C$ . We choose the plus $sign$$(1+\sqrt{b_{j}},2+c_{k}/(n-1)^{2})$in this factor if and only if theth entry of $H$ is 1. Otherwise we$H$$n\geq
4$ doubly even, each term withinchoose the minus $sign$ . Therefore, as is a normalized,
is either orHence, if we could argue that $S>0$ then clearly exists a suitable
integer for which $M(r)$ is a $BH$ $(np,p)$ matrix.
We expand and then rearrange (8) by collecting together products of Legendre symbols
with the same number of factors to obtain$( \frac{r+s_{i}}{p})\pm 1$$j,$$b_{j}\in \mathcal{B}$$S$$2^{(n-1)^{2}}$

$0$

$r$

$S= \sum_{r=1}^{p-(n-1)^{3}-1}(-1)^{n(n-1)/2}+|\mathcal{A}|\geq 1\sum_{\mathcal{A}\subseteq S}(-1)^{\xi(\mathcal{A})}\sum_{r=1}^{p-(n-1)^{3}-1}\prod_{i=1}^{|\mathcal{A}|}(\frac{r+a_{i}}{p})$

,

where
denotes either or 1. We complete the sums by adding up the missing $(n-1)^{3}+1$
terms and, after using the triangle inequality, we apply Weil’s estimate (3) to conclude thatfor each nonempty$0$$\xi(\mathcal{A})$$\mathcal{A}\subseteq S$$|(-1)^{\xi(A)} \sum_{r=1}^{p-(n-1)^{3}-1}\prod_{i=1}^{|\mathcal{A}|}(\frac{r+a_{i}}{p})|\leq(|\mathcal{A}|-1)\sqrt{p}+(n-1)^{3}+1$

holds. Therefore$|S-(p-(n-1)^{3}-1)| \leq\sum_{i=1}^{(n-1)^{2}}(\begin{array}{ll}(n -1)^{2} i\end{array})((i-1) \sqrt{p}+(n-1)^{3}+1)$$=(2^{(n-1)^{2}}-1)((n-1)^{3}+1-\sqrt{p})+2^{(n-1)^{2}-1}(n-1)^{2}\sqrt{p}$46
FERENC SZ\"OLL SI

If $S-(p-(n-1)^{3}-1)\geq 0$ then, as $p\geq(n-1)^{3}+2,$ $S\geq 1$ follows and we are done.
Otherwise, if $S-(p-(n-1)^{3}-1)<0$ we find that
$S\geq p-(2^{n^{2}-2n}(n^{2}-2n-1)+1)\sqrt{p}-2^{(n-1)^{2}}(n^{3}-3n^{2}+3n)$$>p-2^{n^{2}}\sqrt{p}-2^{n^{2}}>0,$

where the last inequality follows for $p>2^{2n^{2}+1}$ via elementary calculus.

$\square$

The bounds exhibited in Theorem 4.1 are admittedly enormous, however, when is fixed
one can improve upon these considerably by evaluating (8) with computers. Moreover, one
can use several free parameters as exponents in the array (7) similarly to (6) to exhibit
further $BH$ $(np,p)$ matrices with this structure. This approach, however, completely fails
when $p\leq 2n-1,$ ae in this case we simply do not have enough quadratic residues to build
up arrays of this type. Constructing these relatively small dimensional examples seems to
be a non-trivial task in general. See [21], [26] and [27].
Despite all these difficulties, we hope that the methods used in this paper combined withmore sophisticated number theoretic tools and non-trivial computer programming are strong
enough to conclude the existence of $BH$ $(np,p)$ matrices for further (relatively small) valuesof doubly even numbers . The first open case $n=8$ is particularly promising, as here theexistence of $BH$ $(8p,p)$ matrices has been confirmed for $p>19$ in [9]. However, dealing withthe single even case, and in particular determining the existence of $BH$ $(6p,p)$ matrices seems
to require some fundamentally new ideas in the future. Addressing the odd case, where
several non existence results are already known [5], [11], [33] looks even more elusive.
$n$

$n$

REFERENCES[1] K. AKIYAMA, M. OGAWA, C. SUETAKE: On $STD_{6}[18;3]s$ and $STD_{7}[21;3]s$ admitting a semiregular
automorphism group of order 9, Electron. J. Combin., 16, #R148, 21 pp. (2009).
[2] B. G. BODMANN, H. J. ELWOOD: Complex Equiangular Parseval Rrumes and Seidd Matrices containing pth roots of unity, Proceedings of the American Mathematical Society, 138, 4387-4404 (2010).
[3] A. T. BUTSON: Generalized Hadamard matrices, Proc. Am. Math. Soc., 13, 894-898 (1962).
[4] B. COMPTON, R. CRAIGEN, W. DE LAUNEY: Unreal $BH(n,$ 6)s and Hadamard matrices, Preprint,(2008).
[5] C. H. COOKE, I. HENG: On the non-existence of some generalized Hadamard matrices, AustralasianJ. Combin. 19, 137-148 (1999).
[6] R. CRAIGEN: Signed groups, sequences and the asymptotic existence of Hadamard matrices, J. Combin.
Theory A, 71,241-254 (1995).
[7] J. E. DAWSON: A construction for generalized Hadamard matrices GH(4q, $EA(q))$ , J. Stat. Plann. andInference 11, 103-110 (1985).
[8] J. E. DAWSON, W. DE LAUNEY: An Asymptotic Result on the Existence of Generalised Hadamard
matrices, J. Combin. Th. Ser. A 65, 158-163 (1994).
[9] J. E. DAWSON, W. DE LAUNEY: A note on the construction of GH(4tq; $EA(q))$ for t $=1,$ 2, Australas.
J. Combin. 6, 177-186 (1992).
[10] W. DE LAUNEY: On the asymptotic existence of Hadamar matrices, J. Combin. Theory A 116, 10021008 (2009).
[11] W. DE LAUNEY: On the non-eststence of generalized Hadamard matrices, J. Stat. Plann. and Inference
10, 385-396 (1984).
; Some results on the parametrization of complex Hadamard matrices, J. Phys. A: Math. Gen.,[12] P.
37, 5355-5374 (2004).
[13] T. DURT, B.-G. ENGLERT, I. BENGTSSON, K. YCZKOWSKl: On mutually unbiased bases, Int. J.
Quantum Information, 8, 535-uo (2010).
$DIT\dot{A}$$\dot{Z}$47
THE ASYMPTOTIC EXISTENCE OF BUTSON HADAMARD MATRICES[14] M. HARADA, C. LAM, A. MUNEMASA, V. D. TONCHEV: Classification of generalized Hadamard
matrices $H(6,$ 3) and quaternary Hermitian self-dual codes of length 18, Elec. J. Combin., 17, #R171,
14 pp. (2010).
[15] W. HOLZMANN, H. KHARAGHANI, W. ORRICK: On the real unbiased Hadamard matrices, Contemp.
Maths., Combinatorics and Graphs, 531, 243-250 (2010).
[16] R. H. HUDSON: On the first occurrence of certain patterns of quadratic residues and non-residues, Israel
Journal of Mathematics, 44, 23-32 (1983).
[17] I. D. IVANOVIC: Geometrical description of quantal state
mination, J. Phys. A: Math. Gen., 14,3241 (1981).
[18] H. IWANIEC, E. KOWALSKI: Analytic Number Theory, Colloqium publications (2004).
[19] M. KOLOUNTZAKIS, M. MATOLCSI: Complex Hadamard matrices and the spectral set conjecture, Collect. Math., Vol. Extra, 281-291 (2006).
[20] I. KOTSIREAS, C. KOUKOUVINOS, J. SEBERRY: Weighing matrices and string sorting, Ann. Comb.
13, 305-313 (2009).
[21] P. H. J. LAMPIO, P. \"OSTERGAoRD; Classification of difference matrices over cyclic groups, J. Statistical
Inference and Planning, 141, 1194-1207 (2011).
; Hadamard matrices modulo 5, J. Combin. Designs, to appear (2013).
[22] M. H. LEE, F. Sz[23] I. LIVINSKYI: Asymptotic existence of Hadamard matrices, Master’s thesis, University of Manitoba,$dete\gamma$$\"{o}_{LL}\’{o} SI$

2012.

[24] M. MATOLCSI, I. Z. RUZSA, M. WEINER: Systems of mutually unbiased Hadamard matrices containing
real and complex Matrices, The Australasian J. Combin. 55, p. 35 (2013).
[25] D. MCNULTY, S. WEIGERT: Isolated Hadamard matrices from mutually unbiased product bases, J.
Math. Phys. 53, 122202 (2012).
[26] G. E. MOORHOUSE: The $2-?$}nnsitive Complex Hadamard Matrices, Preprint, http: $//www$ . uwyo. $edu/$
moorhouse/pub/complex. pdf (2001).
[27] J. SEBERRY: A construction for generalized Hadamard matrices, J. Statistical Planning and Inference,
4, 365-368 (1980).
[28] E. SEIDEN: On the problem of construction of orthogonal arrays, Ann. Math. Statist. 25:1, 151-156(1954).

[29] F. Sz\"oLL\’osI: Complex Hadamard matrices and equiangular tight frames, Linear Algebra and its Applications 438, 1962-1967 (2013).
[30] F. Sz\"oLL\’osI: Construction, classification and parametnzation of complex Hadamard matrices, PhD
thesis, Central European University, Budapest, Hungary (2011).
[31] J. S. WALLIS: On the existence of Hadamard matrices, J. Combin. Theory 21, 188-195 (1976).
[32] A. WEIL: Sur les courbes alg\’ebriques et les varietes qui s’en d\’eduisent, Actuaht\’es Sci. Ind. 1041, Publ.
Inst. Math. Univ. Strasbourg 7 (1945), Hermann et Cie., Paris (1948).
[33] A. WINTERHOF: On the non-existence of generalised Hadamard matrices, J. Statist. Plann. Inference,
84, 337-342 (2000).

APPENDIX;A BH(12, 3) AND A BH (20, 5) MATRIXIn this section we exhibit two sporadic examples of BH(4p,p) matrices. For typographic
reasons we display these matrices in-form”, i.e. the entriesof the Butson-typecomplex Hadamard matrices are replaced by a number z. The first BH(12, 3) matrix$e_{p}(z)$$\log$$\in \mathbb{Z}_{p}$48
FERENC SZ\"OLL\’OSI

was found by Seiden [28]. Actually, it is a sporadic example of difference matrices (see [21]):$S_{12}=[010000020211000000220021000200002111000002002111000220222111022202221111000202222111000022222111000222211111000222211111002220211111000202111111]$

The following $BH$ $(20, 5)$ matrix is a particular example of an infinite family of generalized
Hadamard matrices, discovered by Seberry [27]:$S_{20}=\ovalbox{\tt\small REJECT} \ovalbox{\tt\small REJECT}$FERENC Sz\"oLL\’os : RESEARCH CENTER FOR PURE AND APPLIED MATHEMATICS, GRADUATE SCHOOL$I$

OF INFORMATION SCIENCES, TOHOKU UNIVERSITY, SENDAI 980-8579, JAPAN-mail address: szoferi@$E$$\Psi$

ail. com