CIRCULANT q-BUTSON HADAMARD MATRICES TREVORHYDEANDJOSEPHKRAISLER 7 1 0 2 ABSTRACT. Ifq=pnisaprimepower,thenad-dimensionalq-ButsonHadamardmatrixHisa ar d×dmatrixwithallentriesqthrootsofunitysuchthatHH∗ =dId. Weusealgebraicnumber M theory to prove a strong constraint on the dimension of a circulant q-Butson Hadamard matrix whend=pmandthenexplicitlyconstructafamilyofexamplesinallpossibledimensions.These 5 resultsrelatetothelong-standingcirculantHadamardmatrixconjectureincombinatorics. 1 1. INTRODUCTION ] O For a prime power q = pn, a q-Butson Hadamard matrix (q-BH) of dimension d is a d d C × matrixH withallentriesqthrootsofunitysuchthat . h HH∗ = dI , t d a m whereH∗ istheconjugate transpose ofH. Ad dmatrixH issaidtobecirculant if × [ H = f(i j) ij − 2 for some function f defined modulo d. In this paper we investigate circulant q-BH matrices of v 1 dimension d= pm. 7 8 Theorem1. Ifq = pn isaprimepowerandd = pm,thenthereexistsad dcirculantq-Butson × 8 Hadamardmatrixifandonlyifm 2n,withoneexception when(m,n,p) = (1,1,2). 0 ≤ . Ouranalysis ofcirculant q-BHmatricesledustotheusefulnotionoffibrousfunctions. 1 0 Definition2. Letd 0andq = pn beaprimepower, 7 ≥ 1 (1) If X is a finite set, we say a function g : X Z/(q) is fibrous if the cardinality of the v: fiber g−1(b) dependsonlyonb modpn−1. → | | i (2) Wesayafunction f : Z/(d) Z/(q)isδ-fibrous iffor each k 0 mod dthe function X → 6≡ δ (x) = f(x+k) f(x)isfibrous. r k − a When q = d = p are both prime, δ-fibrous functions coincide with the concept of planar functions, which arise in the study of finite projective planes [2] and have applications in cryptography [6]. Circulant q-BH matrices of dimension d are equivalent to δ-fibrous functions f :Z/(d) Z/(q). → Theorem 3. Let q = pn be a prime power and ζ a primitive qth root of unity. There is a correspondence betweend dcirculantq-ButsonHadamardmatricesH andδ-fibrousfunctions × f :Z/(d) Z/(q)givenby → H = ζf(i−j) . ij Werestateourmainresultinthelangua(cid:0)ge o(cid:1)fδ-fi(cid:0)brous fu(cid:1)nctions. Date:March14th,2017. 1 2 TREVORHYDEANDJOSEPHKRAISLER Corollary4. Ifq = pnisaprimepower,thenthereexistδ-fibrousfunctionsf : Z/(pm) Z/(q) → ifandonlyifm 2nwithoneexception when(m,n,p) = (1,1,2). ≤ It would be interesting to know if δ-fibrous functions have applications to finite geometry or cryptography. When q = 2, q-BH matrices are called Hadamard matrices. Hadamard matrices are usually definedasd dmatricesH withallentries 1suchthatHHt = dI . BustonHadamardmatrices d × ± wereintroduced in[1]asageneralization ofHadamardmatrices. CirculantHadamardmatricesariseinthetheoryofdifference sets,combinatorial designs, and synthetic geometry [7,Chap. 9]. Therearearithmetic constraints onthepossible dimension ofa circulant Hadamardmatrix. Whenthedimension d= 2m isapoweroftwowehave: Theorem5(Turyn[9]). Ifd= 2m isthedimensionofacirculantHadamardmatrix,thenm = 0 orm = 2. Turyn’sproofusesalgebraicnumbertheory,morespecificallythefactthat2istotallyramifiedin the2nthcyclotomicextension Q(ζ2n)/Q;anelementaryexposition maybefoundinStanley[8]. Conjecturally thisaccounts forallcirculant Hadamardmatrices[7]. Conjecture6. Therearenod-dimensional circulant Hadamardmatricesford> 4. Circulant q-Butson Hadamard matrices provide a natural context within which to consider circulant Hadamard matrices. A better understanding of the former could lead to new insights onthe latter. Forexample, ourproof ofTheorem 1showsthat thetwopossible dimensions for a circulant Hadamard matrix given by Turyn’s theorem belong to larger family of circulant q-BH matriceswiththeomissionofd = 2beingadegenerate exception. Circulantq-BHmatriceshave been studied in some specific dimensions [3], but overall seem poorly understood. Weleave the existence ofq-BHmatriceswhenthedimension disnotapowerofpforfuturework. Acknowledgements. TheauthorsthankPadraigCathainforpointerstotheliterature, inparticu- larforbringingtheworkofdeLauney[4]toourattention. WealsothankJeffLagariasforhelpful feedback onanearlierdraft. 2. MAIN RESULTS Wealwaysletq =pn denoteaprimepower. Firstrecallthedefinitionsofq-ButsonHadamard andcirculant matrices. Definition 7. A d-dimensional q-Butson Hadamard matrix H (q-BH) is a d d matrix all of × whoseentriesareqthrootsofunitysatisfying HH∗ = dI , d whereH∗ istheconjugate transpose ofH. Ad-dimensional circulantmatrixC isad dmatrixwithcoefficients inaringRsuchthat × C = f(i j) ij − forsomefunction f :Z/(d) R. → Example8. Hadamardmatricesarethespecialcaseofq-BHmatriceswithq = 2. Theq-Fourier matrix (ζij)whereζ isaprimitive qthroot ofunity isan example ofaq-BHmatrix (whichmay CIRCULANTq-BUTSONHADAMARDMATRICES 3 also be interpreted as the character table of the cyclic group Z/(q).) When q = 3 and ω is a primitive3rdrootofunitythisisthematrix: 1 1 1 1 ω ω2   1 ω2 ω4   Thisexampleisnotacirculant 3-BHmatrix. Thefollowingisacirculant 3-BHmatrix: 1 ω ω ω 1 ω   ω ω 1   The remainder of the paper is divided into two sections: first we prove constraints on the dimensiondofacirculant q-BHmatrixwhendisapowerofp;nextweintroduce theconceptof δ-fibrousfunctionsandconstructexamplesofcirculantq-BHmatricesinallpossibledimensions. Constraintsondimension. Theorem9usestheramificationoftheprimepintheqthcyclotomic extension Q(ζ)/Qtodeducestrongconstraints onthedimension ofaq-BHmatrix. Theorem 9. If q = pn is a prime power and H is a circulant q-Butson Hadamard matrix of dimensiond = pm+n,thenm n. ≤ Notethatourindexingofmhaschangedfromtheintroduction; thischoicewasmadetoimprove notation inourproof. Weusethisindexingfortherestofthepaper. ProofofTheorem9. SupposeH = (a )isacirculantq-ButsonHadamardmatrixofdimension i−j d = pm+n. FromH beingq-BHofdimension dwehave HH∗ = dI , d hence det(H) = dd/2 and each eigenvalue α of H has absolute value α = √d = p(m+n)/2. ± | | Ontheotherhand,sinceH = (a )iscirculant, ithaseigenvalues i−j α = a ζjk. (1) k j j 1, as our con≥struction doesgivecirculant 2n−1-BHmatricesofdimension 2n. Lemma15. Ifq = pn isaprimepowerandthereexistsacirculantq-BHmatrixofdimension d, thenthereexistsacirculantpkq-BHmatrixofdimension dforallk 0. ≥ Proof. Everyqthrootofunity isalsoapkqthrootofunity, hence wemayviewacirculant q-BH matrixH ofdimension dasacirculant pkq-BHforallk 0. (cid:3) ≥ ProofofTheorem14. Ourstrategyistofirstconstruct asequence offunctions δ : Z/(pm) Z/(q) Z/(q) k × → which are fibrous for each k < pmq. If i : Z/(pm) Z/(q) Z/(pmq) is the bijection × → i(x,y) = x + pmy, we define f : Z/(pmq) Z/(q) such that f(z + k) f(z) = δ (x,y) k → − whenz = i(x,y). Hencef isδ-fibrousandTheorem12impliestheexistenceofacorresponding circulant q-BHmatrixofdimension pmq. Nowforeachk 0defineδ by k ≥ δ (x,y) = ky+ S (x), (4) k j j 0. The case (m,n,p) = (0,1,2) 6 is an exception as one can check explicitly that there are no 2-dimensional Hadamard matrices. Hence it follows that f is well-defined. Let i : Z/(pm) Z/(q) Z/(pmq) be the bijection × → i(x,y) = x+pmy. Tofinishtheconstruction wesupposez = i(x,y),show f z+k f z = δ (x,y), k − (cid:0) (cid:1) (cid:0) (cid:1) andthenourproofthatδ isfibrousforallk < pmqimpliesf isδ-fibrous. Theorem12translates k thisintotheexistence ofacirculant q-BHmatrixofdimensionpm+n. Now, f(z+k) f(z)= δ (0,0) δ (0,0) = S (0) = χ(i) z+k z j − − z≤j

Circulant q-Butson Hadamard matrices

Similar Circulant q-Butson Hadamard matrices