N EGATIVE C LIQUES IN S ETS OF

N EGATIVE C LIQUES IN S ETS OF

E QUIANGULAR L INES

Emily J. King

joint work with Matt Fickus, John Jasper, Dustin Mixon, and Xiaoxian Tang

University of Bremen

Tight Frames and Approximation February 20–23, 2018

O UTLINE

E

L

B

R

E

L

S

E

ETF

O UTLINE

E

L

B

R

E

L

S

E

ETF

3/35

O RTHONORMAL B ASES

LetΦ={ϕ_j}be an orthonormal basis forF^dforF=_R,C.

What are the nice properties ofΦ? 1. Each vector isunit length.

(No vector is weighted more than the others.) 2. The inner products between the vectors are

2A. optimallysmalland 2B. equal.

(Vectors represent “different information.”) 3. For anyx∈F^d,x=_∑jhx,ϕ_jiϕ_j.

(We can easily compute a change of basis.) How can we generalize these traits?

Equiangular tight frame =1,2A,2B,3(up to scaling) Equiangular lines =1,2B

O RTHONORMAL B ASES

LetΦ={ϕ_j}be an orthonormal basis forF^dforF=_R,C.

What are the nice properties ofΦ?

1. Each vector isunit length.

(No vector is weighted more than the others.) 2. The inner products between the vectors are

2A. optimallysmalland 2B. equal.

(Vectors represent “different information.”) 3. For anyx∈F^d,x=_∑jhx,ϕ_jiϕ_j.

(We can easily compute a change of basis.) How can we generalize these traits?

Equiangular tight frame =1,2A,2B,3(up to scaling) Equiangular lines =1,2B

4/35

O RTHONORMAL B ASES

LetΦ={ϕ_j}be an orthonormal basis forF^dforF=_R,C.

What are the nice properties ofΦ?

1. Each vector isunit length.

(No vector is weighted more than the others.)

2. The inner products between the vectors are 2A. optimallysmalland

2B. equal.

(Vectors represent “different information.”) 3. For anyx∈F^d,x=_∑jhx,ϕ_jiϕ_j.

(We can easily compute a change of basis.) How can we generalize these traits?

Equiangular tight frame =1,2A,2B,3(up to scaling) Equiangular lines =1,2B

O RTHONORMAL B ASES

LetΦ={ϕ_j}be an orthonormal basis forF^dforF=_R,C.

What are the nice properties ofΦ?

1. Each vector isunit length.

(No vector is weighted more than the others.) 2. The inner products between the vectors are

2A. optimallysmalland 2B. equal.

(Vectors represent “different information.”)

3. For anyx∈F^d,x=_∑jhx,ϕ_jiϕ_j.

(We can easily compute a change of basis.) How can we generalize these traits?

Equiangular tight frame =1,2A,2B,3(up to scaling) Equiangular lines =1,2B

4/35

O RTHONORMAL B ASES

LetΦ={ϕ_j}be an orthonormal basis forF^dforF=_R,C.

What are the nice properties ofΦ?

1. Each vector isunit length.

(No vector is weighted more than the others.) 2. The inner products between the vectors are

2A. optimallysmalland 2B. equal.

(Vectors represent “different information.”) 3. For anyx∈F^d,x=_∑jhx,ϕ_jiϕ_j.

(We can easily compute a change of basis.)

How can we generalize these traits?

Equiangular tight frame =1,2A,2B,3(up to scaling) Equiangular lines =1,2B

O RTHONORMAL B ASES

LetΦ={ϕ_j}be an orthonormal basis forF^dforF=_R,C.

What are the nice properties ofΦ?

1. Each vector isunit length.

(No vector is weighted more than the others.) 2. The inner products between the vectors are

2A. optimallysmalland 2B. equal.

(Vectors represent “different information.”) 3. For anyx∈F^d,x=_∑jhx,ϕ_jiϕ_j.

(We can easily compute a change of basis.) How can we generalize these traits?

Equiangular tight frame =1,2A,2B,3(up to scaling) Equiangular lines =1,2B

4/35

O RTHONORMAL B ASES

LetΦ={ϕ_j}be an orthonormal basis forF^dforF=_R,C.

What are the nice properties ofΦ?

1. Each vector isunit length.

(No vector is weighted more than the others.) 2. The inner products between the vectors are

2A. optimallysmalland 2B. equal.

(Vectors represent “different information.”) 3. For anyx∈F^d,x=_∑jhx,ϕ_jiϕ_j.

(We can easily compute a change of basis.) How can we generalize these traits?

Equiangular tight frame =1,2A,2B,3(up to scaling)

E QUIANGULAR L INES D

LetF=CorR. LetΦ={ϕ_j}ⁿ_j=1⊂F^kwith ϕ_j

=1 for all j∈ {1, . . . ,n}. If there exists anαsuch that for allj6=`,

hϕ_j,ϕ_`i=α, Φis a set ofequiangular lines.

If further for allx∈F^k

∑

|hx,ϕ_ji|²= ⁿ

kkxk² ⇔ x= ⁿ k

∑

j

hx,ϕ_jiϕ_j, thenΦis anequiangular tight frame (ETF).

By slight abuse of notation,

I Φ= ϕ₁ ϕ2 . . . ϕn , and

I αis the “angle.”

T

(Goyal, Kovaˇcevi´c, Kelner 2001; Strohmer, Heath 2003; Benedetto, Kolesar 2006) ETFs are optimally robust against erasures and noise.

5/35

E XAMPLES IN R

I ONB, ETF

I ETF, maximal set of equiangular lines

I FUNTF, worst case coherence

I Equiangular lines which are not an ETF

R ESEARCH Q UESTIONS

Q1 : Givend(and 0<α<1), what is themaximal sizes(d)(resp., s_α(d)) of a set of equiangular lines (resp., with angleα) inR^d?

Q2 : Given a specific ETF or class of ETFs, what is thestructure of linear dependenciesof the vectors?

7/35

G RAM M ATRICES

Instead ofΦ, we will usually deal with theGram matrix G(Φ) =Φ^∗Φ.

LetInbe then×nidentity andJnthen×nall-ones matrix (where we writeIandJwhen clear from context).

Basic linear alg: IfG= (a−b)In+bJn, thenG has a simple eigenvalueλ₁=a+ (n−1)band an eigenvalueλ₂=a−bwith multiplicityn−1.











a b . . . b b a . . . b ... ... . .. ...

b b . . . a











G RAM M ATRICES , II

I

1 0

0 1

I





1 −¹₂ −¹₂

−¹₂ 1 −¹₂

−¹₂ −¹₂ 1





I









1 0 −1 0

0 1 0 −1

−1 0 1 0

0 −1 0 1









I 1

√ 2

√ 2 2

2 1

!

9/35

S WITCHING E QUIVALENCE

Basic linear algebra:G(_Φ) =G(_Ψ) ⇔ _Φ=_UΨfor some unitaryU.

GivenΦ={ϕ1, . . . ,ϕn}, ˜Φ={ϕn, . . . ,−ϕ1}has the same geometric and linear algebraic properties.

D

Two sets of unit vectorsΦandΨinF^dareswitching equivalent, denoted byΦ∼=Ψ, if there exists a diagonal matrixBwith unit norm diagonal entries and a permutation matrixCsuch that

(BC)·G(_Φ)·(BC)⁻¹ = G(_Ψ)_.

Φ∼=Ψ⇒there exists a unitaryU, diagonal(1,−1)-matrixBwith unit norm diagonal entries, and permutation matrixCsuch that

UΦ(BC)⁻¹=_Ψ.

=((Van Lindt & Seidel 1966+generalization toF) +permutations) = (Projective unitary equivalence+permutations)

S WITCHING E QUIVALENCE

Basic linear algebra:G(_Φ) =G(_Ψ) ⇔ _Φ=_UΨfor some unitaryU.

GivenΦ={ϕ1, . . . ,ϕn}, ˜Φ={ϕn, . . . ,−ϕ1}has the same geometric and linear algebraic properties.

D

Two sets of unit vectorsΦandΨinF^dareswitching equivalent, denoted byΦ∼=Ψ, if there exists a diagonal matrixBwith unit norm diagonal entries and a permutation matrixCsuch that

(BC)·G(_Φ)·(BC)⁻¹ = G(_Ψ)_.

Φ∼=Ψ⇒there exists a unitaryU, diagonal(1,−1)-matrixBwith unit norm diagonal entries, and permutation matrixCsuch that

UΦ(BC)⁻¹=_Ψ.

=((Van Lindt & Seidel 1966+generalization toF) +permutations) = (Projective unitary equivalence+permutations)

10/35

S WITCHING E QUIVALENCE

Basic linear algebra:G(_Φ) =G(_Ψ) ⇔ _Φ=_UΨfor some unitaryU.

GivenΦ={ϕ1, . . . ,ϕn}, ˜Φ={ϕn, . . . ,−ϕ1}has the same geometric and linear algebraic properties.

D

Two sets of unit vectorsΦandΨinF^dareswitching equivalent, denoted byΦ∼=Ψ, if there exists a diagonal matrixBwith unit norm diagonal entries and a permutation matrixCsuch that

(BC)·G(_Φ)·(BC)⁻¹ = G(_Ψ)_.

Φ∼=Ψ⇒there exists a unitaryU, diagonal(1,−1)-matrixBwith unit norm diagonal entries, and permutation matrixCsuch that

UΦ(BC)⁻¹=_Ψ.

=((Van Lindt & Seidel 1966+generalization toF) +permutations) =

T RIPLE P RODUCTS

T

(Godsil and Royle 2001; Chien and Waldron 2016) LetΦ,Ψ⊂F^dwith

|Φ|=|Ψ|=n be equiangular. ThenΦ∼=Ψif and only if there exists a σ∈Snsuch that for all i6=j6=k6=i.

hϕ_i,ϕ_jihϕ_j,ϕ_kihϕ_k,ϕ_ii=hψ_σ(i),ψ_σ(j)ihψ_σ(j),ψ_σ(k)ihψ_σ(k),ψ_σ(i)i. WhenF=Rand ignoring permutations, this gives precisely the structure of thetwo-graphwhich represents equivalence classes of switching equivalences. (With permutations, get isomorphisms of the two-graphs.)

11/35

N EGATIVE C LIQUES

D

LetΦbe a set of equiangular lines with angleα. IfX⊂Φis such that X∼=YwithG(Y) = (1+α)I−αJ, then we callXanegative clique.

I (K, Tang 2016) LetXbe a maximal negative clique in a givenΦ.

Xis called aK-base.

I (Fickus, Jasper, K, Mixon 2017) IfXis a negative clique of size 1+ (1/α), we callXa1/α-regular simplex.

Negative cliques have size≤1+1/α.

When the bound is saturated, they form a tight frame for their span (Fickus, Jasper, K, Mixon 2017);

otherwise they are linearly independent (e.g., Lemmens & Seidel 1973).

N EGATIVE C LIQUES

D

LetΦbe a set of equiangular lines with angleα. IfX⊂Φis such that X∼=YwithG(Y) = (1+α)I−αJ, then we callXanegative clique.

I (K, Tang 2016) LetXbe a maximal negative clique in a givenΦ.

Xis called aK-base.

I (Fickus, Jasper, K, Mixon 2017) IfXis a negative clique of size 1+ (1/α), we callXa1/α-regular simplex.

Negative cliques have size≤1+1/α.

When the bound is saturated, they form a tight frame for their span (Fickus, Jasper, K, Mixon 2017);

otherwise they are linearly independent (e.g., Lemmens & Seidel 1973).

12/35

O UTLINE

E

L

B

R

E

L

S

E

ETF

P ILLAR D ECOMPOSITION

D

(Lemmens & Seidel 1973) LetΦ∈_R^dbe equiangular withK-baseX.

LetΞdenote the subspace spanned byX. Elements ofΦwhich lie in the same coset ofΞ^⊥are called pillars.

P

(Lemmens & Seidel 1973; K, Tang 2016) Letϕ∈Φ\X. If any K-base is of size1+1/α, then the norm of P_Ξ⊥ϕis equal toα. If any K-base is of size

<1+1/α, then the norm of P_Ξ⊥ϕdepends on the number of negative inner productshϕ,x_ii, x_i∈X.

14/35

B ASIC P ROCEDURE OF K, T ANG 2016

I (Lemmens & Seidel 1973) We only need to compute upper bounds onsα(d)forαthe reciprocal of an odd integer between 5 and a√

2d+1. (3 solved.)

I For each possibleα, we consider all of the possible sizes of K-bases. (≥2,≤1+ (1/α)).

I For eachK-base size, we partitionΦ\Xinto equivalence classes based on thenumberof negative inner products withXand analyze these (using combinatorics, graph theory, and linear algebra).

I We further split the above equivalence classes into classes based onwith whichelements ofXthe elements have a negative inner product and analyze these. (This will sometimes involve a bound of a size of particular spherical two-distance sets.)

B ASIC P ROCEDURE OF K, T ANG 2016

I (Lemmens & Seidel 1973) We only need to compute upper bounds onsα(d)forαthe reciprocal of an odd integer between 5 and a√

2d+1. (3 solved.)

I For each possibleα, we consider all of the possible sizes of K-bases. (≥2,≤1+ (1/α)).

I For eachK-base size, we partitionΦ\Xinto equivalence classes based on thenumberof negative inner products withXand analyze these (using combinatorics, graph theory, and linear algebra).

I We further split the above equivalence classes into classes based onwith whichelements ofXthe elements have a negative inner product and analyze these. (This will sometimes involve a bound of a size of particular spherical two-distance sets.)

15/35

B ASIC P ROCEDURE OF K, T ANG 2016

I (Lemmens & Seidel 1973) We only need to compute upper bounds onsα(d)forαthe reciprocal of an odd integer between 5 and a√

2d+1. (3 solved.)

I For each possibleα, we consider all of the possible sizes of K-bases. (≥2,≤1+ (1/α)).

I For eachK-base size, we partitionΦ\Xinto equivalence classes based on thenumberof negative inner products withXand analyze these (using combinatorics, graph theory, and linear algebra).

I We further split the above equivalence classes into classes based onwith whichelements ofXthe elements have a negative inner product and analyze these. (This will sometimes involve a bound of a size of particular spherical two-distance sets.)

B ASIC P ROCEDURE OF K, T ANG 2016

I (Lemmens & Seidel 1973) We only need to compute upper bounds onsα(d)forαthe reciprocal of an odd integer between 5 and a√

2d+1. (3 solved.)

I For each possibleα, we consider all of the possible sizes of K-bases. (≥2,≤1+ (1/α)).

I For eachK-base size, we partitionΦ\Xinto equivalence classes based on thenumberof negative inner products withXand analyze these (using combinatorics, graph theory, and linear algebra).

I We further split the above equivalence classes into classes based onwith whichelements ofXthe elements have a negative inner product and analyze these. (This will sometimes involve a bound of a size of particular spherical two-distance sets.)

15/35

S PHERICAL T WO -D ISTANCE S ETS

D

LetΦ={ϕ₁, . . . ,ϕn} ⊂_R^dbe a set of unit normed vectors and let α,β∈_{R. TheΦ}is aspherical two-distance setifhϕ_i,ϕ_ji ∈ {α,β}for alli,j∈ {1, . . . ,n},i6=j. We denote bys(d,α,β)the largest size of a spherical two-distance set with the given parameters.

Note: An equiangular set of lines is a spherical two-distance set w.r.t α,−α, and thussα(d) =s(d,α,−α).

N EW U PPER B OUND ON s

( _d )

T

(K, Tang 2016) LetΦ⊂R^dbe an equiangular set with angle1/5. If d>60, then

|Φ| ≤ 148+3·s(d, 1/13,−5/13) ≤ 148+^648d(d+2) 47d+169 .

17/35

A TASTE OF THE CASES T

(K, Tang 2016) For n=1, . . . ,bK/2cand for each equivalence class x⊂X(_K,n), we have the following upper bounds on|x|.

(1) If n=1, then

|x| ≤

(r−K, 1≥K−^(1/α)+1₂

1−α

l(K,1)−α, 1<K−^(1/α)+1₂ . (2) If1<n<K−^(1/α)+1₂ , then|x| ≤ r+1.

(3) If n=K−^(1/α)+1₂ , then|x| ≤ r−K+b2α^r−K_1−αc. (4) If K−^(1/α)+1₂ <n<b^K₂c, then

|x| ≤ s(r,β,γ), whereβ= ^α_1−l(K,n)^−l(K,n)andγ= ⁻_1−l(K,n)^α−l(K,n).

E QUIANGULAR L INES IN R

T

(K, T

2016)

Let m be the largest positive integer such that(2m+1)²≤d+2. Then

s(d) ≤















4d(m+1)(m+2)

(2m+3)²−d , d=44, 45, 46, 76, 77, 78, 117, 118, 166, 222, 286, 358

(^(2m+1)2−2)(^(2m+1)2−1)

2 , other k between44and400

.

Applied the SDP approach of [Bachoc, Valentin 2008; Barg, Yu 2014]

to bound the size of certain spherical two distance sets in the cases they arose.

19/35

N EW B OUND VS . O LD

FIGURE:K, Tang 2016 andsdp(d,¹₅,−¹₅)

— :^d(d+1)₂ ? ? ?:sdp(d,¹₅,−¹₅) +++: K, Tang 2016

FIGURE:K, Tang 2016 andsdp(d,¹₇,−¹₇)

— :^k(k+1)₂ ? ? ?:sdp(d,¹₇,−¹₇) +++: K, Tang 2016

P OSITIVE C LIQUES

One may similarly define apositive clique.

For all 0≤α<1 there exist at leastdvectors In F^dwith pairwise inner productα

Geometrically, one may think of “pushing”

vectors in an onb together.

One may analyze projections onto orthogonal complements of positive cliques and use Ramsey theory to obtain asymptotic relative bounds. (Balla, Dr¨axler, Keevash, Sudakov 2018)

21/35

O UTLINE

E

L

B

R

E

L

S

E

ETF

B INDERS

D

(F

, J

, K, M

2017)

LetΦbe an ETF. The set of subsets of vectors (or the corresponding incidence matrix) which are 1/α-regular simplices is thebinder.

These are the smallest sets of linearly dependent vectors in the ETF:

For a general set of unit vectorsΦ,

size of the smallest set of linearly dependent vectors inΦ ≥ 1+ ¹ µ(_Φ)^. (Gerschgorin circle theorem applied to the Gram matrix. Donoho, Elad 2003)

23/35

B INDER F INDER

BinderFinderis a relatively short Matlab code that uses triple

products and some clever combinatorial tricks to compute the binder of a given ETF.

(Could also be used on sets of equiangular lines.)

Code available for download at:

http://www.math.uni-bremen.de/cda/

B INDERS OF ETF S IN C

Perhaps the first investigation of linear dependencies in equiangular Gabor frames (SIC-POVMs) was presented in a talk by Hughston in 2007 (cited in Dang, Blanchfield, Bengtsson, Appleby 2013), where the linear dependencies of certain SIC-POVMs inC³were shown to be represented by the Hesse configuration.

I came to the question via the construction of ETFs in (Jasper, Mixon, Fickus 2013). This construction involves a tensor-like construction of an incidence matrix of a BIBD with a 1/α-regular simplex. (Bad algebraic spread, butgoodgeometric spread?!?!?)

25/35

B INDERS OF ETF S IN C

Perhaps the first investigation of linear dependencies in equiangular Gabor frames (SIC-POVMs) was presented in a talk by Hughston in 2007 (cited in Dang, Blanchfield, Bengtsson, Appleby 2013), where the linear dependencies of certain SIC-POVMs inC³were shown to be represented by the Hesse configuration.

I came to the question via the construction of ETFs in (Jasper, Mixon, Fickus 2013). This construction involves a tensor-like construction of an incidence matrix of a BIBD with a 1/α-regular simplex. (Bad algebraic spread, butgoodgeometric spread?!?!?)

H ESSE C ONFIGURATION

The Hesse configuration is the set of all lines inF²₃:

FIGURE: By David Eppstein - Own work, CC0,

https://commons.wikimedia.org/w/index.php?curid=18920067

26/35

“N ORMAL ” C ONFIGURATION

Letζ=e^2πi/3,θ∈[0, 2π/6]\{0, 2π/9}.

SIC-POVMs:(Hughston 2007; Dang, Blanchfield, Bengtsson, Appleby 2013)





0 0 0 −e^iθ −e^iθζ −e^iθζ² 1 1 1

1 1 1 0 0 0 −e^iθ −e^iθζ −e^iθζ²

−e^iθ −e^iθζ −e^iθζ² 1 1 1 0 0 0





Kirkman ETFs(Fickus, Jasper, Mixon 2013):

BIBD(3, 2, 1) D₃





0 1 1 1 0 1 1 1 0



 &





1 1 1

1 ζ ζ² 1 ζ² ζ



=:



 w0

w1

w₂





⇒





0 0 0 w0 w1

w1 0 0 0 w0

w w 0 0 0





“N ORMAL ” C ONFIG . B INDER & G RAM OF B INDER

Left: Binder of a “normal” SIC-POVM inC³, Right: The Gram matrix of the binder.

28/35

O BTAINING THE H ESSE C OFIGURATION

Letζ=e^2πi/3,θ∈ {0, 2π/9}.

SIC-POVMs:(Hughston 2007; Dang, Blanchfield, Bengtsson, Appleby 2013)





0 0 0 −e^iθ −e^iθζ −e^iθζ² 1 1 1

1 1 1 0 0 0 −e^iθ −e^iθζ −e^iθζ²

−e^iθ −e^iθζ −e^iθζ² 1 1 1 0 0 0





Polyphase BIBD ETFs(Fickus, Jasper, Mixon, Peterson, Watson 2017;

Fickus, Jasper, K, Mixon 2017):

BIBD(3, 2, 1) D₃





0 1 1 1 0 1 1 1 0



 &





1 1 1

1 ζ ζ² 1 ζ² ζ



=:



 w₀ w₁ w2





⇒





0 0 0 w₀ −w₁

−w₁ 0 0 0 w₀





H ESSE C ONFIGURATION AS A B INDER

Left: Hesse Configuration binder of a SIC-POVM inC³, Right: The Gram matrix of the binder.

30/35

B INDER OF H OGGAR ’ S L INES

Left: Binder of Hoggar’s lines (non-Gabor SIC POVM inC⁸with 1008 simplices), Right: The Gram matrix of the binder.

C ONCLUSION

I Fond memories (nightmares?) of using Sylowp-groups in the classification of finite simple groups.

I

32/35

M ISSING C OMRADES

Thanks to Shayne for

organizing/chauffeuring and to New Zealand for being so beautiful!

[email protected]

http://www.math.uni-bremen.de/cda/

“New Upper Bounds for Equiangular Lines by Pillar Decomposition”

on arXiv (the paper formerly known as “Computing Upper Bounds for Equiangular Lines in Euclidean Space”)

“Equiangular tight frames that contain regular simplices” on arXiv

34/35