betaFeedback

WorksMathematics

Orthogonal bases of symmetric unitary matrices in odd dimensions and the mixed-unitary rank of the symmetric Werner–Holevo channel

Abstract

Let Sym_n denote the space of complex symmetric n×n matrices with the Hilbert–Schmidt inner product. Girard, Leung, Levick, Li, Paulsen, Poon and Watrous showed that the symmetric Werner–Holevo channel on M_n has minimal mixed-unitary rank binom(n+1,2) if and only if Sym_n admits an orthogonal basis consisting of unitary matrices. They established this for even n and for n=3, and conjectured it for all odd n; Levick and Rahaman settled the case of primes n≡7 (mod 8). We introduce a family of symmetric unitaries (“chirped circulants”) for odd n and prove that, for this family, the pairwise orthogonality conditions reduce exactly to a square system of (n^2-1)/4 real equations in as many unknown phases. Using this reduction we give (i) a fully explicit basis for n=5, with all entries in an explicit degree-8 number field and an exact-arithmetic verification, and (ii) a computer-assisted proof, based on the Krawczyk operator evaluated in Arb ball arithmetic, that a symmetric unitary orthogonal basis exists for every odd n with 3≤n≤67. Consequently the conjecture of Girard et al. holds for all n≤68. We also record several obstructions to natural approaches for general odd n, and a further reduction for prime n.

Introduction

For a positive integer nn let Sn={X∈Mn(C):XT=X}S_n = \{X \in M_n(\mathbb{C}) : X^{\mathsf{T}} = X\}, a complex vector space of dimension (n+12)\binom{n+1}{2}, equipped with the Hilbert–Schmidt inner product ⟨A,B⟩=tr⁡(AB∗)\langle A, B\rangle= \operatorname{tr}(AB^*). The following question was asked on MathOverflow in 2018 [6]:

Does SnS_n admit an orthogonal basis consisting of unitary matrices?

The question has a quantum-information interpretation. The symmetric Werner–Holevo channel [10] is

Φ0(X)=tr⁡(X)In+XTn+1,X∈Mn.\Phi_0(X) = \frac{\operatorname{tr}(X)\mathbb{I}_n + X^{\mathsf{T}}}{n+1}, \qquad X \in M_n.

Its Choi rank is (n+12)\binom{n+1}{2}, and its mixed-unitary rank (the least number of unitaries in a decomposition Φ0(X)=∑kpkUkXUk∗\Phi_0(X) = \sum_k p_k U_k X U_k^*) is at least the Choi rank.

Theorem 1 [2 Theorem 19]. The channel Φ0\Phi_0 on MnM_n has mixed-unitary rank (n+12)\binom{n+1}{2} if and only if SnS_n has an orthogonal basis consisting of unitary matrices.

(Theorem numbers for [2] refer to arXiv:2003.14405.) In [2] such bases are constructed for all even $n (Theorem 21 there) and for n=3(Theorem23)n = 3 (Theorem 23). For odd nn only the upper bound n(n+3)/2n(n+3)/2 on the mixed-unitary rank is proved (Theorem 22 there). Based on numerical evidence, the authors conjecture that Φ0\Phi_0 has minimal mixed-unitary rank for every nn. Numerical (nonrigorous) bases for odd nn up to 11 were also reported in [6].

Levick and Rahaman [5, Theorem 3.8, Corollary 3.12] (numbering as in arXiv:2105.00975) extended a construction of Bravyi and Smolin. Using real equiangular projections obtained from a construction of Calderbank, Hardin, Rains, Shor and Sloane [1], they settled the case of primes n=p≡−1(mod8)n=p\equiv-1\pmod{8}. Below 70 the odd values of nn covered by these results are n=3,7,23,31,47n=3,7,23,31,47. We did not find a rigorous treatment of any other odd nn in the literature.1

Results

For odd nn we introduce chirped circulants: matrices DcCDcD_cCD_c with CC a symmetric circulant unitary and Dc=diag⁡(ωca2)D_c=\operatorname{diag}(\omega^{ca^2}). From n+12\frac{n+1}{2} of them and the nn diagonal “shifts” V↦ZtVZtV\mapsto Z^tVZ^t we obtain (n+12)\binom{n+1}{2} symmetric unitaries.

  • Reduction. We prove (Theorem 5) that these (n+12)\binom{n+1}{2} matrices are pairwise orthogonal if and only if ((n+1)/22)\binom{(n+1)/2}{2} explicit scalar quantities EijE_{ij} vanish. After fixing a gauge, this is a square real system F:RN→RNF:\mathbb{R}^N\to\mathbb{R}^N with N=n2−12N=\frac{n^2-1}{2}.

  • n=5n=5 (Theorem 8). An explicit orthogonal basis of S5\mathcal{S}_5 by symmetric unitaries. All entries lie in the number field Q(ζ5,45−11)\mathbb{Q}(\zeta_5,\sqrt{4\sqrt{5}-11}). The proof is human-readable apart from two clearly marked polynomial identities. We also provide a complete exact-arithmetic verification.

  • 3≤n≤673\le n\le67 (Theorem 10). For every odd n≤67n\le67 the square system has a solution. The proof is computer-assisted: it applies the Krawczyk operator [4, 7, 8], evaluated rigorously in Arb midpoint–radius arithmetic [3], to an approximate solution.

Corollary 2. For every positive integer n≤68n\le68, the space Sn\mathcal{S}_n has an orthogonal basis of unitary matrices. Equivalently, the symmetric Werner–Holevo channel on Mn\mathcal{M}_n has mixed-unitary rank (n+12)\binom{n+1}{2}.

Proof. For n=1n=1 the claim is trivial (S1=C\mathcal{S}_1=\mathbb{C} with basis {1}\{1\}). For even nn this is [2 Theorem 21]; for odd 3≤n≤673\le n\le67 it is Theorem 10. Apply Theorem 1. □

The case of general odd nn remains open; see § 5 for a conjecture, obstructions and a reduction for prime nn.

Chirped circulants and the reduction lemma

Throughout, nn is odd, h=n−12h=\frac{n-1}{2} and m=h+1=n+12m=h+1=\frac{n+1}{2}. Indices are taken in Zn\mathbb{Z}_n, ω=e2πi/n\omega=e^{2\pi i/n}, and 2−1=n+122^{-1}=\frac{n+1}{2} denotes the inverse of 2 in Zn\mathbb{Z}_n. Let Z=diag⁡(ωa)a∈ZnZ=\operatorname{diag}(\omega^a)_{a\in\mathbb{Z}_n} and Dc=diag⁡(ωca2)a∈ZnD_c=\operatorname{diag}(\omega^{ca^2})_{a\in\mathbb{Z}_n} for c∈Znc\in\mathbb{Z}_n.

Definition 3. A vector μ=(μl)l∈Zn∈Cn\mu=(\mu_l)_{l\in\mathbb{Z}_n}\in\mathbb{C}^n is admissible if ∣μl∣=1|\mu_l|=1 and μ−l=μl\mu_{-l}=\mu_l for all ll. For admissible μ\mu put

kd=1n∑l∈Znμlωld(d∈Zn),k_d=\frac{1}{n}\sum_{l\in\mathbb{Z}_n}\mu_l\omega^{ld}\qquad(d\in\mathbb{Z}_n),

and let C(μ)=(kb−a)a,bC(\mu)=(k_{b-a})_{a,b} be the associated circulant. Given parameters c0,…,ch∈Znc_0,\ldots,c_h\in\mathbb{Z}_n and admissible μ(0),…,μ(h)\mu^{(0)},\ldots,\mu^{(h)}, define

V(i)=DciC(μ(i))Dci,i.e.Vab(i)=ωci(a2+b2)kb−a(i)V^{(i)}=D_{c_i}C(\mu^{(i)})D_{c_i},\qquad\text{i.e.}\qquad V^{(i)}_{ab}=\omega^{c_i(a^2+b^2)}k^{(i)}_{b-a}

and

Mi,t=ZtV(i)Zt,(Mi,t)ab=ωt(a+b)Vab(i)(0≤i≤h, t∈Zn).M_{i,t}=Z^tV^{(i)}Z^t,\qquad(M_{i,t})_{ab}=\omega^{t(a+b)}V^{(i)}_{ab}\qquad(0\le i\le h,\ t\in\mathbb{Z}_n).

This gives mn=(n+12)mn=\binom{n+1}{2} matrices.

Lemma 4. Each Mi,tM_{i,t} is symmetric and unitary.

Proof. With F=(ωja/n)j,aF=(\omega^{ja}/\sqrt{n})_{j,a} we have C(μ)=F∗diag⁡(μ)FC(\mu)=F^{*}\operatorname{diag}(\mu)F, so C(μ)C(\mu) is unitary. Since μ−l=μl\mu_{-l}=\mu_l we get k−d=kdk_{-d}=k_d, so C(μ)C(\mu) is symmetric. If UU is symmetric unitary and DD is diagonal unitary, then DUDDUD is symmetric unitary. Apply this twice. □

Theorem 5 (Reduction). For i,j∈{0,…,h}i,j\in\{0,\ldots,h\} put

Eij=∑d∈Znω(ci−cj)2−1d2kd(i)kd(j)‾.E_{ij}=\sum_{d\in\mathbb{Z}_n}\omega^{(c_i-c_j)2^{-1}d^2}k_d^{(i)}\overline{k_d^{(j)}}.

Then

⟨Mi,t,Mj,u⟩=Eij∑s∈Znω(t−u)s+(ci−cj)2−1s2.\langle M_{i,t},M_{j,u}\rangle=E_{ij}\sum_{s\in\mathbb{Z}_n}\omega^{(t-u)s+(c_i-c_j)2^{-1}s^2}.

and Eii=1E_{ii}=1. Consequently the matrices {Mi,t}\{M_{i,t}\} are pairwise orthogonal if and only if Eij=0E_{ij}=0 for all 0≤i<j≤h0\leq i<j\leq h. In that case ⟨Mi,t,Mj,u⟩=nδijδtu\langle M_{i,t},M_{j,u}\rangle=n\delta_{ij}\delta_{tu}, and {Mi,t}\{M_{i,t}\} is an orthogonal basis of Sn\mathcal{S}_n consisting of symmetric unitaries.

Proof. By definition

⟨Mi,t,Mj,u⟩=∑a,bω(t−u)(a+b)Vab(i)Vab(j)‾=∑sω(t−u)sGij(s),Gij(s)=∑aVa,s−a(i)Va,s−a(j)‾.\langle M_{i,t},M_{j,u}\rangle=\sum_{a,b}\omega^{(t-u)(a+b)}V_{ab}^{(i)}\overline{V_{ab}^{(j)}}=\sum_s\omega^{(t-u)s}G_{ij}(s),\qquad G_{ij}(s)=\sum_a V_{a,s-a}^{(i)}\overline{V_{a,s-a}^{(j)}}.

Fix ss. Since nn is odd, a↦d=s−2aa\mapsto d=s-2a is a bijection of Zn\mathbb{Z}_n. With b=s−ab=s-a we get a=2−1(s−d)a=2^{-1}(s-d), b=2−1(s+d)b=2^{-1}(s+d), b−a=db-a=d, and a2+b2=2−1(s2+d2)a^2+b^2=2^{-1}(s^2+d^2). Hence

Va,s−a(i)=ωci2−1(s2+d2)kd(i),Gij(s)=ω(ci−cj)2−1s2Eij.V_{a,s-a}^{(i)}=\omega^{c_i2^{-1}(s^2+d^2)}k_d^{(i)},\qquad G_{ij}(s)=\omega^{(c_i-c_j)2^{-1}s^2}E_{ij}.

This proves the displayed formula. By Parseval, Eii=∑d∣kd(i)∣2=1n∑l∣μl(i)∣2=1E_{ii}=\sum_d|k_d^{(i)}|^2=\frac{1}{n}\sum_l|\mu_l^{(i)}|^2=1, so ⟨Mi,t,Mi,u⟩=∑sω(t−u)s=nδtu\langle M_{i,t},M_{i,u}\rangle=\sum_s\omega^{(t-u)s}=n\delta_{tu}.

For i≠ji\ne j: if Eij=0E_{ij}=0 the inner products vanish. Conversely, if ⟨Mi,t,Mj,u⟩=0\langle M_{i,t},M_{j,u}\rangle=0 for all t,ut,u, then the discrete Fourier transform of s↦Gij(s)s\mapsto G_{ij}(s) vanishes. Hence Gij≡0G_{ij}\equiv0, and so Eij=0E_{ij}=0.

Finally, mn=dim⁡Snmn=\dim\mathcal{S}_n pairwise orthogonal nonzero matrices form a basis. □

Remark 6 (Square system). Multiplying μ(i)\mu^{(i)} by a unimodular constant multiplies EijE_{ij} by a unimodular constant, so we may fix μ0(i)=1\mu_0^{(i)}=1. Write μl(i)=eiθr(i)\mu_l^{(i)}=e^{i\theta_r^{(i)}} with r=min⁡(l,n−l)r=\min(l,n-l) and θ0(i)=0\theta_0^{(i)}=0. The unknowns are then θ=(θr(i))0≤i≤h, 1≤r≤h∈Rmh\theta=(\theta_r^{(i)})_{0\leq i\leq h,\,1\leq r\leq h}\in\mathbb{R}^{mh}. The conditions Re⁡Eij=Im⁡Eij=0\operatorname{Re}E_{ij}=\operatorname{Im}E_{ij}=0 (i<j)(i<j) are m(m−1)=mhm(m-1)=mh real equations. We obtain a smooth map

Fn:RN→RN,N=mh=n2−14,F_n:\mathbb{R}^{N}\to\mathbb{R}^{N},\qquad N=mh=\frac{n^2-1}{4},

whose zeros yield orthogonal bases of Sn\mathcal{S}_n by symmetric unitaries.

Remark 7 (Unbiased-vector form). Set ρi(d)=ωci2−1d2kd(i)\rho_i(d)=\omega^{c_i2^{-1}d^2}k_d^{(i)}. Then Eij=⟨ρi,ρj⟩CnE_{ij}=\langle\rho_i,\rho_j\rangle_{\mathbb{C}^n}. Hence the problem is equivalent to finding an orthonormal basis ρ0,…,ρh\rho_0,\ldots,\rho_h of the space of even functions on Zn\mathbb{Z}_n such that each ρi\rho_i, after removing the chirp ωci2−1d2\omega^{c_i2^{-1}d^2}, has a Fourier transform of constant modulus. Equivalently, ρi\rho_i is unbiased with respect to the “chirped Fourier basis” {ωci2−1d2+ld/n}l\{\omega^{c_i2^{-1}d^2+ld}/\sqrt{n}\}_l.

An explicit basis for n=5n=5

Let ω=e2πi/5\omega=e^{2\pi i/5}, 5=1+2(ω+ω4)\sqrt{5}=1+2(\omega+\omega^{4}), φ=1+52\varphi=\frac{1+\sqrt{5}}{2}, and

S=i11−45,S2=45−11=8ω+8ω4−7.S=i\sqrt{11-4\sqrt{5}},\qquad S^{2}=4\sqrt{5}-11=8\omega+8\omega^{4}-7.

All quantities below lie in K=Q(ω,S)K=\mathbb{Q}(\omega,S), a field of degree 8 over Q\mathbb{Q}. On KK, complex conjugation is the automorphism ω↦ω4\omega\mapsto\omega^{4}, S↦−SS\mapsto-S. Put

A=6+4ω+4ω3−4ω4,B=2+5ω+2ω2−2ω3−2ω4,C=4ω+6ω2−4ω3+4ω4,A=6+4\omega+4\omega^{3}-4\omega^{4},\qquad B=2+5\omega+2\omega^{2}-2\omega^{3}-2\omega^{4},\qquad C=4\omega+6\omega^{2}-4\omega^{3}+4\omega^{4},
μ=−B+5ωS2A=−311−544ω+311ω2+722ω3+S(211+744ω−211ω2−122ω3)≈−0.887915+0.460008i,\mu=\frac{-B+5\omega S}{2A}=-\frac{3}{11}-\frac{5}{44}\omega+\frac{3}{11}\omega^{2}+\frac{7}{22}\omega^{3}+S\left(\frac{2}{11}+\frac{7}{44}\omega-\frac{2}{11}\omega^{2}-\frac{1}{22}\omega^{3}\right)\approx-0.887915+0.460008i,
C1=(4ω+2ω2+4ω3)+μ(2−3ω−2ω2−2ω4),C0=(6ω−2ω2−4ω3)+μ(8+8ω+2ω2+2ω4),C_{1}=(4\omega+2\omega^{2}+4\omega^{3})+\mu(2-3\omega-2\omega^{2}-2\omega^{4}),\qquad C_{0}=(6\omega-2\omega^{2}-4\omega^{3})+\mu(8+8\omega+2\omega^{2}+2\omega^{4}),

and v=−C0/C1v=-C_{0}/C_{1}:

v=−611−2144ω−944ω2−2744ω3+S(411+2544ω+1744ω2+744ω3)≈−0.997329−0.073042i.v=-\frac{6}{11}-\frac{21}{44}\omega-\frac{9}{44}\omega^{2}-\frac{27}{44}\omega^{3}+S\left(\frac{4}{11}+\frac{25}{44}\omega+\frac{17}{44}\omega^{2}+\frac{7}{44}\omega^{3}\right)\approx-0.997329-0.073042i.

The minimal polynomial of μ\mu over Q\mathbb{Q} is 176x8+552x7+428x6−546x5−1195x4−546x3+428x2+552x+176176x^{8}+552x^{7}+428x^{6}-546x^{5}-1195x^{4}-546x^{3}+428x^{2}+552x+176. It is not monic, so μ\mu is not a root of unity.

Let (μ0,…,μ4)=(1,ω,μ,μ,ω)(\mu_{0},\ldots,\mu_{4})=(1,\omega,\mu,\mu,\omega), let kd=15∑jμjωjdk_{d}=\frac{1}{5}\sum_{j}\mu_{j}\omega^{jd}, and let JJ be the all-ones matrix. Define

V(1)=I+v−15J,Vab(2)=ω2(a2+b2)kb−a,Vab(3)=ω3(a2+b2)k3(b−a),V^{(1)}=I+\frac{v-1}{5}J,\qquad V_{ab}^{(2)}=\omega^{2(a^{2}+b^{2})}k_{b-a},\qquad V_{ab}^{(3)}=\omega^{3(a^{2}+b^{2})}k_{3(b-a)},

and Mi,t=ZtV(i)ZtM_{i,t}=Z^{t}V^{(i)}Z^{t} for i=1,2,3i=1,2,3 and t∈Z5t\in\mathbb{Z}_{5}.

These are chirped circulants with (c1,c2,c3)=(0,2,3)(c_{1},c_{2},c_{3})=(0,2,3) (in this section the seeds are indexed 1,2,31,2,3 instead of 0,1,20,1,2). Here V(1)=C(μ(1))V^{(1)}=C(\mu^{(1)}) with μ(1)=(v,1,1,1,1)\mu^{(1)}=(v,1,1,1,1). The circulant (k3(b−a))a,b(k_{3(b-a)})_{a,b} equals C(μ(3))C(\mu^{(3)}) with μl(3)=μ2l\mu^{(3)}_{l}=\mu_{2l}, i.e. μ(3)=(1,μ,ω,ω,μ)\mu^{(3)}=(1,\mu,\omega,\omega,\mu).

Theorem 8. The 15 matrices Mi,tM_{i,t} are symmetric unitaries and satisfy ⟨Mi,t,Mj,u⟩=5δijδtu\langle M_{i,t},M_{j,u}\rangle=5\delta_{ij}\delta_{tu}. Hence they form an orthogonal basis of S5S_{5}, and the symmetric Werner–Holevo channel on M5M_{5} has mixed-unitary rank 15.

The theorem can be verified directly: the script verify_exact.py works in the ring Q[x]/(x5−1)[S]/(S2−σ)\mathbb{Q}[x]/(x^{5}-1)[S]/(S^{2}-\sigma) using rational arithmetic only. It checks symmetry, MM∗=IMM^{*}=I for all 15 matrices, and all 120 Gram entries. The script verify_sympy.py is an independent check via Gröbner reduction (see § 6). The proof below explains the structure and isolates the two polynomial identities that we checked by computer.

Proof. Step 1 (∣μ∣=1|\mu|=1). Note that C=ω2A‾C=\omega^{2}\overline{A} and B=ω2B‾B=\omega^{2}\overline{B}. Conjugating p(z)=Az2+Bz+Cp(z)=Az^{2}+Bz+C shows that p(z)=0p(z)=0 implies p(1/z‾)=0p(1/\overline{z})=0, so the root set of pp is invariant under inversion in the unit circle.

One computes

B2−4AC=25ω2(8ω+8ω−1−7)=(5ωS)2≠0.B^{2}-4AC=25\omega^{2}(8\omega+8\omega^{-1}-7)=(5\omega S)^{2}\ne0.

Hence μ\mu is a root of pp, and the two roots are distinct. Moreover ∣A∣2=80−205|A|^{2}=80-20\sqrt{5} and ∣B∣2=45+205|B|^{2}=45+20\sqrt{5}, so ∣B∣2<4∣A∣2|B|^{2}<4|A|^{2}, i.e. ∣B/A∣<2|B/A|<2.

Suppose a root zz had ∣z∣≠1|z|\ne1. Then the other root is 1/z‾1/\overline{z}, and ∣B/A∣=∣z+1/z‾∣=∣z∣+∣z∣−1>2|B/A|=|z+1/\overline{z}|=|z|+|z|^{-1}>2, a contradiction. Thus ∣μ∣=1|\mu|=1, and μ(2),μ(3)\mu^{(2)},\mu^{(3)} are admissible.

Step 2 (∣v∣=1|v|=1). [Computer-checked identity] In KK one has C0C0‾=C1C1‾C_{0}\overline{C_{0}}=C_{1}\overline{C_{1}} and C1≠0C_{1}\ne0, hence ∣v∣=1|v|=1. Thus μ(1)\mu^{(1)} is admissible, and by Lemma 4 all Mi,tM_{i,t} are symmetric unitaries.

Step 3 (reduction). By Theorem 5 it suffices to show E12=E13=E23=0E_{12}=E_{13}=E_{23}=0. Here kd(1)=ydk_d^{(1)}=y_d, with y0=4+v5y_0=\frac{4+v}{5} and yd=v−15y_d=\frac{v-1}{5} for d≠0d\ne0, and

E12=∑dydω−d2kd‾,E13=∑dydωd2k3d‾,E23=∑dω2d2kd‾k3d.E_{12}=\sum_d y_d\omega^{-d^2}\overline{k_d},\qquad E_{13}=\sum_d y_d\omega^{d^2}\overline{k_{3d}},\qquad E_{23}=\sum_d\omega^{2d^2}\overline{k_d}k_{3d}.

Substituting d=2ed=2e in E13E_{13} gives 3d=e3d=e and d2≡−e2d^2\equiv-e^2, while y2e=yey_{2e}=y_e; hence E13=E12E_{13}=E_{12}.

[Computer-checked identity] Expanding with μ‾=μ−1\overline{\mu}=\mu^{-1} and ω‾=ω−1\overline{\omega}=\omega^{-1} and reducing modulo Φ5\Phi_5 gives

E12=C1v+C025ωμ,E23=Aμ2+Bμ+C25ωμ.E_{12}=\frac{C_1v+C_0}{25\omega\mu},\qquad E_{23}=\frac{A\mu^2+B\mu+C}{25\omega\mu}.

Both numerators vanish by the definitions of μ\mu and vv. □

Remark 9. Replacing SS by −S-S (the other root of pp) gives a second basis; we checked this numerically. The two computer-checked identities are finite polynomial computations in Q(ω)[S]\mathbb{Q}(\omega)[S]. They are verified by verify_exact.py (the identity ∣C0∣2=∣C1∣2|C_0|^2=|C_1|^2, together with μμ‾=vv‾=1\mu\overline{\mu}=v\overline{v}=1) and by reduce_eqs.py (the expansions of E12,E23E_{12},E_{23}).

Odd n≤67n\le67: a computer-assisted proof

Theorem 10. For every odd nn with 3≤n≤673\le n\le67 and the choice ci=ic_i=i (0≤i≤h0\le i\le h), the system Fn(θ)=0F_n(\theta)=0 of Remark 6 has a solution. Consequently SnS_n has an orthogonal basis of n+12\frac{n+1}{2} symmetric unitary matrices.

Method

We use the following classical result [4, 7]; see also [8].

Krawczyk’s theorem. Let X⊂RNX\subset\mathbb{R}^N be a box, F:X→RNF:X\to\mathbb{R}^N continuously differentiable, x~∈X\widetilde{x}\in X, and Y∈RN×NY\in\mathbb{R}^{N\times N}. Let JJ be an interval matrix containing the Jacobian F′(x)F'(x) for every x∈Xx\in X, and put

K(X)=x~−YF(x~)+(I−YJ)(X−x~)K(X)=\widetilde{x}-YF(\widetilde{x})+(I-YJ)(X-\widetilde{x})

(evaluated in interval arithmetic). If K(X)⊆int⁡XK(X)\subseteq\operatorname{int}X, then FF has exactly one zero in XX.

For each nn we proceed as follows.

  1. Approximate solution. Starting from random phases, a Levenberg–Marquardt least-squares solve followed by five Newton steps gives x~∈RN\widetilde{x}\in\mathbb{R}^N in IEEE double precision, with max⁡∣Fn(x~)∣≲10−14\max|F_n(\widetilde{x})|\lesssim10^{-14}. The numbers x~k\widetilde{x}_k are taken as exact binary rationals.

  1. Box. X=x~+[−r,r]NX=\widetilde{x}+[-r,r]^N with r=10−9r=10^{-9} (rounded upward to Arb’s radius format; the same radius is used for X−x~X-\widetilde{x}).

  1. Rigorous enclosures. Using Arb [3] through python-flint 0.9.0 [9], at a working precision of 128 bits, we compute an enclosure of Fn(x~)F_n(\widetilde{x}) and an interval matrix JJ enclosing Fn′(X)F'_n(X):

    • the roots of unity ωk=exp⁡(πi⋅2k/n)\omega^k=\exp(\pi i\cdot2k/n) and the phases eiθe^{i\theta} are evaluated as rigorous complex balls;

    • the entries of Fn′F'_n are given by the explicit formulas

∂kd(i)∂θr(i)=in∑l:min⁡(l,n−l)=rμl(i)ωld,\frac{\partial k_d^{(i)}}{\partial\theta_r^{(i)}}=\frac{i}{n}\sum_{l:\min(l,n-l)=r}\mu_l^{(i)}\omega^{ld},

combined by the product rule in EijE_{ij}.

  1. Preconditioner. YY is the floating-point inverse of Fn′(x~)F'_n(\widetilde{x}), converted exactly to a ball matrix. Any real YY is admissible in the theorem.

  1. Check. We evaluate K(X)K(X) in ball arithmetic and test K(X)⊆int⁡XK(X)\subseteq\operatorname{int}X componentwise. In every case max⁡k∣K(X)k−x~k∣\max_k|K(X)_k-\widetilde{x}_k| (an upper bound computed in ball arithmetic) is at most 2×10−122\times10^{-12}, far inside the radius 10−910^{-9}.

Results

Table 1 lists, for each odd n≤67n \le67: the dimension N=n2−14N = \frac{n^2-1}{4} of the system; the bound on max⁡k∣K(X)k−x~k∣\max_k |K(X)_k-\tilde{x}_k|; and the wall-clock time of certify.py n --from-center (excluding Python start-up and imports; almost all of it is the interval phase) on an 8-core Intel Xeon virtual machine (single-threaded). The last column indicates whether the case was covered by [2, 5] (“known”) or not (“new”; i.e. not covered by these papers and not found in our literature search). All 33 cases are certified, which proves Theorem 10.

nnNNδ\deltasnnNNδ\deltas
324.646×10−164.646 \times10^{-16}0.0known373421.275×10−131.275 \times10^{-13}0.4new
565.619×10−155.619 \times10^{-15}0.0new393801.386×10−131.386 \times10^{-13}0.5new
7121.360×10−151.360 \times10^{-15}0.0known414203.365×10−133.365 \times10^{-13}0.6new
9205.107×10−155.107 \times10^{-15}0.0new434621.840×10−131.840 \times10^{-13}0.8new
11303.553×10−153.553 \times10^{-15}0.0new455063.970×10−133.970 \times10^{-13}1.0new
13429.263×10−159.263 \times10^{-15}0.0new475523.566×10−133.566 \times10^{-13}1.2known
15569.963×10−159.963 \times10^{-15}0.0new496005.444×10−135.444 \times10^{-13}1.4new
17726.560×10−156.560 \times10^{-15}0.0new516503.357×10−133.357 \times10^{-13}1.7new
19904.204×10−144.204 \times10^{-14}0.0new537025.442×10−135.442 \times10^{-13}2.1new
211105.123×10−145.123 \times10^{-14}0.0new557565.458×10−135.458 \times10^{-13}2.3new
231323.152×10−143.152 \times10^{-14}0.1known578126.198×10−136.198 \times10^{-13}2.8new
251566.686×10−146.686 \times10^{-14}0.1new598701.630×10−121.630 \times10^{-12}3.5new
271821.696×10−131.696 \times10^{-13}0.1new619306.108×10−136.108 \times10^{-13}4.6new
292101.325×10−131.325 \times10^{-13}0.1new639929.658×10−139.658 \times10^{-13}4.3new
312409.280×10−149.280 \times10^{-14}0.2known6510566.430×10−136.430 \times10^{-13}4.9new
332727.574×10−147.574 \times10^{-14}0.2new6711221.888×10−121.888 \times10^{-12}5.7new
353063.756×10−133.756 \times10^{-13}0.3new

Table 1. Krawczyk certification, box radius r=10−9r = 10^{-9}, precision 128 bits. “δ\delta” = max⁡k∣K(X)k−x~k∣\max_k |K(X)_k-\tilde{x}_k| (rigorous upper bound); “s” = seconds.

Proof of Theorem 10. For each nn in Table 1 the inclusion K(X)⊆int⁡XK(X) \subseteq\operatorname{int} X holds. By Krawczyk’s theorem FnF_n has a (unique) zero θ∗∈X\theta^* \in X. By Remark 6 and Theorem 5, the corresponding matrices Mi,tM_{i,t} form an orthogonal basis of SnS_n by symmetric unitaries. □\square

Consistency checks

These checks are not part of the proof.

  • The analytic Jacobian agrees with central finite differences to about 2.5×10−102.5 \times10^{-10}, and the ball Jacobian agrees with the floating-point one to about 2×10−162 \times10^{-16} (checked for n=7n = 7).

  • Negative control. Shifting the centre by 10−610^{-6}, so that the true zero lies outside the box, makes the script report “not certified” (checked for n=13n = 13).

  • For every nn in Table 1, all (n+12)\binom{n+1}{2} matrices were also assembled in floating point directly from the archived centre (without using the formula for EijE_{ij}). Their Gram matrix agrees with nInI to 5×10−135 \times10^{-13}, and symmetry and unitarity hold to 2×10−142 \times10^{-14}.

  • The Jacobians at the solutions are well conditioned (e.g. cond⁡Fn′(x~)≤8×102\operatorname{cond} F'_n(\tilde{x}) \le8 \times10^2 for n≤41n \le41).

Remarks, obstructions, and open problems

General odd nn

In every case we tried, a handful of random starting points sufficed to find a nondegenerate zero of FnF_n. This suggests:

Conjecture 11. For every odd n≥3n \ge3, the system Fn=0F_n = 0 (with ci=ic_i = i) has a nondegenerate real solution. In particular SnS_n has an orthogonal basis of symmetric unitaries for every nn.

A natural approach would be a direct algebraic construction or a topological existence argument. We record several obstructions.

(1) Equal chirp parameters fail. Suppose all cic_i equal cc. Let φl(d)=ωc2−1d2+ld/n\varphi_l(d)=\omega^{c2^{-1}d^2+ld}/\sqrt{n}, and take the orthonormal basis f0=φ0f_0=\varphi_0, fl=(φl+φ−l)/2f_l=(\varphi_l+\varphi_{-l})/\sqrt{2} (1≤l≤h1\le l\le h) of the even functions. By Remark 7, ∣⟨ρi,f0⟩∣2=1/n|\langle\rho_i,f_0\rangle|^2=1/n for every ii. If ρ0,…,ρh\rho_0,\ldots,\rho_h were an orthonormal basis of the even functions, the matrix (⟨ρi,fl⟩)i,l(\langle\rho_i,f_l\rangle)_{i,l} would be unitary. Its 0-th column would then have squared norm m/n=(n+1)/(2n)≠1m/n=(n+1)/(2n)\ne1, a contradiction.

(2) Pure chirp spectra fail for prime n=pn=p. Suppose every μl(i)=ωαil2\mu_l^{(i)}=\omega^{\alpha_i l^2} with αi∈Zp\alpha_i\in\mathbb{Z}_p. If αi≠0\alpha_i\ne0 then kd(i)=p−1g(αi)ω−(4αi)−1d2k_d^{(i)}=p^{-1}g(\alpha_i)\omega^{-(4\alpha_i)^{-1}d^2}, where g(α)=∑lωαl2g(\alpha)=\sum_l\omega^{\alpha l^2} is a quadratic Gauss sum with ∣g(α)∣=p|g(\alpha)|=\sqrt{p}; if αi=0\alpha_i=0 then kd(i)=δd,0k_d^{(i)}=\delta_{d,0}. Hence each EijE_{ij} is either a value k0(j)k_0^{(j)} or its conjugate (modulus p−1/2p^{-1/2} or 1), or equals p−2g(αi)g(αj)‾∑dωβd2p^{-2}g(\alpha_i)\overline{g(\alpha_j)}\sum_d\omega^{\beta d^2} for some β∈Zp\beta\in\mathbb{Z}_p, of modulus p−1⋅pp^{-1}\cdot\sqrt{p} or p−1⋅pp^{-1}\cdot p. In no case does EijE_{ij} vanish.

(3) Tensor products do not close the problem. Under Mn1n2=Mn1⊗Mn2M_{n_1n_2}=M_{n_1}\otimes M_{n_2} one has Sn1n2=(Sn1⊗Sn2)⊕(Kn1⊗Kn2)S_{n_1n_2}=(S_{n_1}\otimes S_{n_2})\oplus(K_{n_1}\otimes K_{n_2}), where KK denotes antisymmetric matrices. Since antisymmetric matrices of odd size are singular, KniK_{n_i} contains no unitaries when nin_i is odd. So bases for odd n1,n2n_1,n_2 do not directly yield one for n1n2n_1n_2.

(4) No degree argument. FnF_n is 2π2\pi-periodic in each variable, so it induces a map from the compact torus TNT^N to RN\mathbb{R}^N. Such a map is never surjective, so its degree is 0: if 0 is a regular value, the zeros on TNT^N counted with the sign of det⁡Fn′\det F_n' sum to 0. Hence existence of zeros cannot be obtained from a global degree count alone.

A further reduction for prime n=pn=p

For u∈Zp∗u\in\mathbb{Z}_p^* let (Puρ)(d)=ρ(u−1d)(P_u\rho)(d)=\rho(u^{-1}d). Since even functions are fixed by P−1P_{-1}, PuP_u depends only on the class of uu in H=Zp∗/{±1}H=\mathbb{Z}_p^*/\{\pm1\}, a group of order hh. In the notation of Remark 7:

Proposition 12. Let pp be an odd prime. Take the chirp parameters {0}∪{u−2:u∈H}={0}∪QRp\{0\}\cup\{u^{-2}:u\in H\}=\{0\}\cup\mathrm{QR}_p. Let ρ0=δ0+p−1v\rho_0=\delta_0+p^{-1}v with ∣v∣=1|v|=1, and ρu−2=Puρ1\rho_{u^{-2}}=P_u\rho_1, where ρ1(d)=ωu−2d2k(d)\rho_1(d)=\omega^{u^{-2}d^2}k(d) and kk has admissible spectrum. Then all ρc\rho_c are admissible for their chirp parameters. Moreover, the orthonormality conditions of Remark 7 reduce to

(A)⟨Puρ1,ρ1⟩=0(u∈H∖{1}),(B)⟨ρ0,ρ1⟩=0.(A)\quad\langle P_u\rho_1,\rho_1\rangle=0\quad(u\in H\setminus\{1\}),\qquad(B)\quad\langle\rho_0,\rho_1\rangle=0.

Proof. First, (Puρ1)(d)=ωu−22−1d2k(u−1d)(P_u\rho_1)(d)=\omega^{u^{-2}2^{-1}d^2}k(u^{-1}d). The Fourier spectrum of k∘u−1k\circ u^{-1} is a permutation of that of kk, so it is again admissible. Next, ρ0\rho_0 corresponds to the circulant with spectrum (v,1,…,1)(v,1,\ldots,1) and is PuP_u-invariant. Hence

⟨ρ0,Puρ1⟩=⟨Pu−1ρ0,ρ1⟩=⟨ρ0,ρ1⟩and⟨Puρ1,Pu′ρ1⟩=⟨Pu/u′ρ1,ρ1⟩.\langle\rho_0,P_u\rho_1\rangle=\langle P_{u^{-1}}\rho_0,\rho_1\rangle=\langle\rho_0,\rho_1\rangle \quad\text{and}\quad \langle P_u\rho_1,P_{u'}\rho_1\rangle=\langle P_{u/u'}\rho_1,\rho_1\rangle.

Up to gauge this is a square system with about h+1h+1 real unknowns (namely vv and the phases of the spectrum of kk). For p≤59p\le59 we found nondegenerate numerical solutions; this is evidence, not proof. For p=5p=5 and p=7p=7 there are solutions (verified numerically to 60 significant digits; we have not written out an exact proof) in which the spectrum of kk is a single chirp off the origin, μl=ωαl2\mu_l=\omega^{\alpha l^2} (l≠0l\ne0), with μ0\mu_0 free. For p=7p=7 these have cos⁡(arg⁡μ0)∈{−34,38}\cos(\arg\mu_0)\in\{-\frac{3}{4},\frac{3}{8}\}, and for p=5p=5 we get cos⁡(arg⁡μ0)=13−558\cos(\arg\mu_0)=\frac{13-5\sqrt{5}}{8}. Numerically, this one-parameter family has no solutions for 11≤p≤4311\le p\le43. A heuristic Weil-bound argument suggests that it fails for all large pp. Cose-t-wise (Gauss-period) generalizations of index 2 and 3 produced no solutions in our tests (p≤41p\le41). A proof for infinitely many primes along these lines would need a genuinely new explicit family.

Reproducibility

The ancillary files contain the following.

  • verify_exact.py: pure-Python exact verification of Theorem 8 (fractions only, about 1 s).

  • verify_sympy.py: an independent Gröbner-basis verification (about 50 s).

  • reduce_eqs.py: the expansions in Step 3.

  • certify.py: the Krawczyk certification.

    • python3 certify.py n searches for a solution and certifies it.

    • python3 certify.py n --from-center re-certifies the archived centre centers/cert_sol_nn.npy, which is exactly the centre used for Table 1.

  • logs/: the original logs and the run used for the table (recertify_from_centers.out).

The certification relies on the correctness of Arb’s ball arithmetic and of Krawczyk’s theorem. Floating-point computations are used only to produce the centre x~\tilde{x} and the preconditioner YY, neither of which needs to be accurate for the validity of the proof.

Acknowledgements

The author used AI assistance in the literature search, in designing and running the computational experiments, in writing the accompanying verification and certification code, and in drafting the manuscript. The human author is solely responsible for verifying all results, for the correctness of the proofs and computations, and for the final text.

Tools used: Codex (OpenAI) and Claude (Anthropic), used as research and writing assistants. Specific version numbers were not recorded. AI is not listed as an author.

References

References

  1. [1]A. R. Calderbank, R. H. Hardin, E. M. Rains, P. W. Shor, and N. J. A. Sloane, A group-theoretic framework for the construction of packings in Grassmannian spaces, J. Algebraic Combin. 9 (1999), no. 2, 129–140.DOI
  2. [2]Mark Girard, Debbie Leung, Jeremy Levick, Chi-Kwong Li, Vern Paulsen, Xiu-Tung Wong, and John Watrous, On the mixed-unitary rank of quantum channels, Comm. Math. Phys. 394 (2022), no. 2, 919–951, arXiv:2003.14405.DOI
  3. [3]Fredrik Johansson, Arb: efficient arbitrary-precision midpoint-radius interval arithmetic, IEEE Trans. Comput. 66 (2017), no. 8, 1281–1292.arxiv.org/abs/1611.02831
  4. [4]R. Krawczyk, Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken, Computing 4 (1969), no. 3, 187–201.DOI
  5. [5]Jeremy Levick and Mizanur Rahaman, An extension of Bravyi–Smolin’s construction for UMEBs, Quantum Inf. Process. 20 (2021), no. 11, Paper No. 369, arXiv:2105.00975.DOI
  6. [6]Luftbahnfahrer, Existence of orthogonal basis of symmetric n × n matrices, where each matrix is unitary?, MathOverflow, question 316985, 2018, https://mathoverflow.net/questions/316985.
  7. [7]R. E. Moore, A test for existence of solutions to nonlinear systems, SIAM J. Numer. Anal. 14 (1977), no. 4, 611–615.DOI
  8. [8]Siegfried M. Rump, Verification methods: rigorous results using floating-point arithmetic, Acta Numer. 19 (2010), 287–449.
  9. [9]The FLINT team, python-flint: Python bindings for FLINT (incl. Arb), version 0.9.0, https://github.com/flintlib/python-flint, PyPI package python-flint.
  10. [10]R. F. Werner and A. S. Holevo, Counterexample to an additivity conjecture for output purity of quantum channels, J. Math. Phys. 43 (2002), no. 9, 4353–4357.DOI

Paper details

vlnc:W_wytper4c
Version
v1 · latest
Published
Fresh — published within the last 30 days
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Codex, Claude

View statement
Looking for related papers…
Contents