Gröbner bases and cocyclic Hadamard matrices

Gr¨obner bases and cocyclic Hadamard matrices ´ Alvarez, Armario, Falc´on, Frau and Gudiel University of Seville 5th Workshop on Real and Complex Hadamard Matrices and Applications Gudiel Gr¨obner bases ... Budapest, July 2017 1 / 15 Outline 1Hadamard cocyclic ideals 2Cocyclic advantages 3Fine tuning 4Future work Gudiel Gr¨obner bases ... Budapest, July 2017 2 / 15 Hadamard cocyclic ideals Hadamard ideals - Kotsireas, Koukouvinos, Seberry (2006) Polynomial equations ←→ Hadamard matrices with 1 and 2-circulant core Gis a group of order 4t, a cocycle ψover Gis a mapping ψ:G×G→ h−1isatisfying ψ(1,1) = ψ(g,1) = ψ(1,g) = 1,g∈Gand the cocycle equation: ψ(gi,gj)ψ(gigj,gk)ψ(gi,gjgk)ψ(gj,gk)=1,gi,gj,gk∈G.(1) Gudiel Gr¨obner bases ... Budapest, July 2017 3 / 15 Hadamard cocyclic ideals Hadamard ideals - Kotsireas, Koukouvinos, Seberry (2006) Polynomial equations ←→ Hadamard matrices with 1 and 2-circulant core Gis a group of order 4t, a cocycle ψover Gis a mapping ψ:G×G→ h−1isatisfying ψ(1,1) = ψ(g,1) = ψ(1,g) = 1,g∈Gand the cocycle equation: ψ(gi,gj)ψ(gigj,gk)ψ(gi,gjgk)ψ(gj,gk)=1,gi,gj,gk∈G.(1) Gudiel Gr¨obner bases ... Budapest, July 2017 3 / 15 Hadamard cocyclic ideals Hadamard ideals - Kotsireas, Koukouvinos, Seberry (2006) Polynomial equations ←→ Hadamard matrices with 1 and 2-circulant core Gis a group of order 4t, a cocycle ψover Gis a mapping ψ:G×G→ h−1isatisfying ψ(1,1) = ψ(g,1) = ψ(1,g) = 1,g∈Gand the cocycle equation: ψ(gi,gj)ψ(gigj,gk)ψ(gi,gjgk)ψ(gj,gk)=1,gi,gj,gk∈G.(1) Gudiel Gr¨obner bases ... Budapest, July 2017 3 / 15 Pros & Cons Pros Faster Hadamard test Search performed in terms of a basis of cocyles {coboundaries}∪{inflation}∪{transgression} Cons {Cocyclic Hadamard Matrices }⊂{Hadamard Matrices } Gudiel Gr¨obner bases ... Budapest, July 2017 4 / 15 Pros & Cons Pros Faster Hadamard test Search performed in terms of a basis of cocyles {coboundaries}∪{inflation}∪{transgression} Cons {Cocyclic Hadamard Matrices }⊂{Hadamard Matrices } Gudiel Gr¨obner bases ... Budapest, July 2017 4 / 15 Pros & Cons Pros Faster Hadamard test Search performed in terms of a basis of cocyles {coboundaries}∪{inflation}∪{transgression} Cons {Cocyclic Hadamard Matrices }⊂{Hadamard Matrices } Gudiel Gr¨obner bases ... Budapest, July 2017 4 / 15 The idea Use the Algebraic Geometry artillery (namely Gr¨obner basis techniques) to determine both the cardinality and the elements of the set HGof cocyclic Hadamard matrices over a multiplicative finite group Gof 4telements. Gudiel Gr¨obner bases ... Budapest, July 2017 5 / 15 Complexity Set of polynomials defining IG: O(t3) polynomials of degree up to 2 over O(t2) variables Lakshman and Lazard (1991) −→ 2O(t2)!! Open computer algebra system for polynomial computations Singular CocGM(t,G,opt) http://personales.us.es/raufalgan/LS/hadamard.lib G= 1 ⇒Zt×Z2 2,G= 2 ⇒D4t opt = 1 ⇒]HG,opt = 2 ⇒ HG t≤3 Gudiel Gr¨obner bases ... Budapest, July 2017 7 / 15 Basis of normalized cocycles Fixed a representative cocycle ρ, and a basis for normalized cocycles B. Q[X] be the polynomial ring over {X}={xi:i∈ {1,...,k}} Theorem (´ Alvarez et al. )[2008] The matrix Mψis Hadamard if and only if the vector of coordinates (x1,...,xk)Bof ψwith regards to Bsatisfies the following system of 4t−1equations and kunknowns      (m1 2,1)x1. . . (mk 2,1)xk+. . . + (m1 2,4t)x1. . . (mk 2,4t)xk= 0 . . . (m1 4t,1)x1. . . (mk 4t,1)xk+. . . + (m1 4t,4t)x1· · · (mk 4t,4t)xk= 0 (2)  Gudiel Gr¨obner bases ... Budapest, July 2017 8 / 15 Basis of normalized cocycles Fixed a representative cocycle ρ, and a basis for normalized cocycles B. Q[X] be the polynomial ring over {X}={xi:i∈ {1,...,k}} Theorem (´ Alvarez et al. )[2008] The matrix Mψis Hadamard if and only if the vector of coordinates (x1,...,xk)Bof ψwith regards to Bsatisfies the following system of 4t−1equations and kunknowns      (m1 2,1)x1. . . (mk 2,1)xk+. . . + (m1 2,4t)x1. . . (mk 2,4t)xk= 0 . . . (m1 4t,1)x1. . . (mk 4t,1)xk+. . . + (m1 4t,4t)x1· · · (mk 4t,4t)xk= 0 (2)  Gudiel Gr¨obner bases ... Budapest, July 2017 8 / 15 Theorem The set Hρ Gcan be identified with the set of zeros of the following zero-dimensional ideal of Q[X]. JG:= hx2 i−xi:i∈ {1,...,k−m} i +h 4t X h=1 sl,h(X): l∈ {1, . . . 4t−1} i. s(l,h)is defined in terms of paths and intersections, and deg(sl,h)≤2. Now, Lakshman and Lazard =⇒2O(t) CocGB(t,G,opt) G= 1 ⇒Zt×Z2 2,G= 2 ⇒D4t opt = 1 ⇒]HG,opt = 2 ⇒ HG t≤7,D4t Gudiel Gr¨obner bases ... Budapest, July 2017 9 / 15 Theorem The set Hρ Gcan be identified with the set of zeros of the following zero-dimensional ideal of Q[X]. JG:= hx2 i−xi:i∈ {1,...,k−m} i +h 4t X h=1 sl,h(X): l∈ {1, . . . 4t−1} i. s(l,h)is defined in terms of paths and intersections, and deg(sl,h)≤2. Now, Lakshman and Lazard =⇒2O(t) CocGB(t,G,opt) G= 1 ⇒Zt×Z2 2,G= 2 ⇒D4t opt = 1 ⇒]HG,opt = 2 ⇒ HG t≤7,D4t Gudiel Gr¨obner bases ... Budapest, July 2017 9 / 15 Theorem The set Hρ Gcan be identified with the set of zeros of the following zero-dimensional ideal of Q[X]. JG:= hx2 i−xi:i∈ {1,...,k−m} i +h 4t X h=1 sl,h(X): l∈ {1, . . . 4t−1} i. s(l,h)is defined in terms of paths and intersections, and deg(sl,h)≤2. Now, Lakshman and Lazard =⇒2O(t) CocGB(t,G,opt) G= 1 ⇒Zt×Z2 2,G= 2 ⇒D4t opt = 1 ⇒]HG,opt = 2 ⇒ HG t≤7,D4t Gudiel Gr¨obner bases ... Budapest, July 2017 9 / 15 Theorem The set Hρ Gcan be identified with the set of zeros of the following zero-dimensional ideal of Q[X]. JG:= hx2 i−xi:i∈ {1,...,k−m} i +h 4t X h=1 sl,h(X): l∈ {1, . . . 4t−1} i. s(l,h)is defined in terms of paths and intersections, and deg(sl,h)≤2. Now, Lakshman and Lazard =⇒2O(t) CocGB(t,G,opt) G= 1 ⇒Zt×Z2 2,G= 2 ⇒D4t opt = 1 ⇒]HG,opt = 2 ⇒ HG t≤7,D4t Gudiel Gr¨obner bases ... Budapest, July 2017 9 / 15 Theorem The set Hρ Gcan be identified with the set of zeros of the following zero-dimensional ideal of Q[X]. JG:= hx2 i−xi:i∈ {1,...,k−m} i +h 4t X h=1 sl,h(X): l∈ {1, . . . 4t−1} i. s(l,h)is defined in terms of paths and intersections, and deg(sl,h)≤2. Now, Lakshman and Lazard =⇒2O(t) CocGB(t,G,opt) G= 1 ⇒Zt×Z2 2,G= 2 ⇒D4t opt = 1 ⇒]HG,opt = 2 ⇒ HG t≤7,D4t Gudiel Gr¨obner bases ... Budapest, July 2017 9 / 15 Fine tuning: Zt×Z2 2 Diagrammatic properties:  −−−×××− −−×−×−× −−−−×−− ××−−×−−  CocAH(t,col,dist,H)    col: parity of columns dist: sum of each row H: fixed values of some coordinates Gudiel Gr¨obner bases ... Budapest, July 2017 10 / 15 Fine tuning: Zt×Z2 2 Diagrammatic properties:  −−−×××− −−×−×−× −−−−×−− ××−−×−−  CocAH(t,col,dist,H)    col: parity of columns dist: sum of each row H: fixed values of some coordinates Gudiel Gr¨obner bases ... Budapest, July 2017 10 / 15 Fine tuning: D4t CocDH(t,col,dist,H) dist: number of new intersections in each row [2,t] H: fixed values of some coordinates Gudiel Gr¨obner bases ... Budapest, July 2017 12 / 15 Fine tuning: D4t CocDH(t,col,dist,H) dist: number of new intersections in each row [2,t] H: fixed values of some coordinates Gudiel Gr¨obner bases ... Budapest, July 2017 12 / 15 Fine tuning: D4t CocDH(t,col,dist,H) dist: number of new intersections in each row [2,t] H: fixed values of some coordinates Gudiel Gr¨obner bases ... Budapest, July 2017 12 / 15 Fine tuning: D4t, example t= 31 dist 1,1,2,2,3,3,2,3,0,1,0,4,2,2,3,2,3,2,2,0,0,3,1,1,2,1,3,2,2,3 H= 5,6,17,36,48,63,64,84,95,115,117 21172424E984E2E3FC6B06D5527CA70 Gudiel Gr¨obner bases ... Budapest, July 2017 13 / 15 Fine tuning: D4t, example t= 31 dist 1,1,2,2,3,3,2,3,0,1,0,4,2,2,3,2,3,2,2,0,0,3,1,1,2,1,3,2,2,3 H= 5,6,17,36,48,63,64,84,95,115,117 21172424E984E2E3FC6B06D5527CA70 Gudiel Gr¨obner bases ... Budapest, July 2017 13 / 15 Fine tuning: D4t, example t= 31 dist 1,1,2,2,3,3,2,3,0,1,0,4,2,2,3,2,3,2,2,0,0,3,1,1,2,1,3,2,2,3 H= 5,6,17,36,48,63,64,84,95,115,117 21172424E984E2E3FC6B06D5527CA70 Gudiel Gr¨obner bases ... Budapest, July 2017 13 / 15 Fine tuning: D4t, example t= 31 dist 1,1,2,2,3,3,2,3,0,1,0,4,2,2,3,2,3,2,2,0,0,3,1,1,2,1,3,2,2,3 H= 5,6,17,36,48,63,64,84,95,115,117 21172424E984E2E3FC6B06D5527CA70 Gudiel Gr¨obner bases ... Budapest, July 2017 13 / 15 Future work Improve the quality of the helping information to get better results ! Gudiel Gr¨obner bases ... Budapest, July 2017 14 / 15 Future work Improve the quality of the helping information to get better results ! Gudiel Gr¨obner bases ... Budapest, July 2017 14 / 15 Thank you and farewell !!! Gudiel Gr¨obner bases ... Budapest, July 2017 15 / 15