Exclusions for positive definite diagrams: trees, valency, labels, chains and arms

(Trigonometric values and comparisons.) From [F4] one gets the double-angle formula $\cos 2x=2{\cos }^{2}x-1$ and the triple-angle formula $\cos 3x=4{\cos }^{3}x-3\cos x$ for every real $x$. Cosine is strictly decreasing on $[0,\pi ]$ with $\cos (\pi \mathrm{/}2)=0>\cos \pi =-1$ and is positive on $[0,\pi \mathrm{/}2)$ [F5, F7]: (i) $\cos (\pi \mathrm{/}4)=\sqrt{2}\mathrm{/}2$ because ${\cos }^2(\pi \mathrm{/}4)=\frac{1+\cos (\pi \mathrm{/}2)}{2}=\frac{1}{2}$ and $\cos (\pi \mathrm{/}4)>0$ [F8]; (ii) writing $c_3=\cos (\pi \mathrm{/}3)$, the triple-angle formula at $x=\pi \mathrm{/}3$ gives $4c_3^3-3c_3+1=0=(c_3+1)(2c_3-1{)}^2$, and $c_3>0$ because $0<\pi \mathrm{/}3<\pi \mathrm{/}2$ forces $c_3=1\mathrm{/}2$; (iii) $\cos (\pi \mathrm{/}6)=\sqrt{3}\mathrm{/}2$ because ${\cos }^2(\pi \mathrm{/}6)=\frac{1+\cos (\pi \mathrm{/}3)}{2}=\frac{3}{4}$ and $\cos (\pi \mathrm{/}6)>0$ [F8]; (iv) since $\cos (\pi \mathrm{/}m)$ is strictly increasing in $m\in \{2,3,4,\dots \}$: for $m\ge 3$ one has $c(s,t)=\cos (\pi \mathrm{/}m)\ge 1\mathrm{/}2$, for $m\ge 4$ one has $c(s,t)\ge \sqrt{2}\mathrm{/}2$, and for $m\ge 6$ one has $c(s,t)\ge \cos (\pi \mathrm{/}6)=\sqrt{3}\mathrm{/}2$. Also $\cos (\pi \mathrm{/}5)=(1+\sqrt{5})\mathrm{/}4$: with $c_5=\cos (\pi \mathrm{/}5)$, iterating the recurrence of [F6] gives $T_2=2t^2-1$, $T_3=4t^3-3t$, $T_4=8t^4-8t^2+1$ and $T_5=16t^5-20t^3+5t$, so $T_5(c_5)=\cos (5\cdot \pi \mathrm{/}5)=\cos \pi =-1$ [F5, F6], that is $16c_5^5-20c_5^3+5c_5+1=(c_5+1)(4c_5^2-2c_5-1{)}^2=0$ by expansion; since $0<\pi \mathrm{/}5<\pi \mathrm{/}2$ gives $0<c_5<1$ [F5, F7], one has $c_5\mathrm{\ne }-1$ and $4c_5^2-2c_5-1=0$, i.e. $(c_5-\frac{1}{4}{)}^2=\frac{5}{16}$; by uniqueness of the nonnegative square root $c_5-\frac{1}{4}=\pm \frac{\sqrt{5}}{4}$, and $c_5>0$ excludes the negative alternative, which is $<0$ because $\sqrt{5}>1$ by $1<5$ and [F8]; hence $c_5=(1+\sqrt{5})\mathrm{/}4$ and $4{\cos }^2(\pi \mathrm{/}5)=(3+\sqrt{5})\mathrm{/}2$ satisfies $5\mathrm{/}2<4{\cos }^2(\pi \mathrm{/}5)<3$ because $2<\sqrt{5}<3$ [F8].

(Witness principle and form comparison.) By [F3], $B$ positive definite means $B(u,u)>0$ for every nonzero $u$; a nonzero $u\in V_T\subseteq V$ with $B(u,u)\le 0$ therefore contradicts positive definiteness, which is the first assertion of (1). For the comparison, let $u={\sum }_{s\in T}{u}_s{e}_s$ have all $u_s\ge 0$ and let ${\mathrm{\Gamma }}_0$ be a labelled graph on $T$ whose labels are at most the corresponding labels of ${\mathrm{\Gamma }}_T$; for distinct $s,t$ the comparison of labels gives $c_0(s,t)\le c_T(s,t)\le 1$ (with value $0$ exactly for the non-edges and $c_0\ge 0$ throughout), so $B_T(u,u)-B_0(u,u)=-2{\sum }_{s<t}(c_T(s,t)-c_0(s,t))u_s{u}_t\le 0,$ each term being $\le 0$; hence $B_T(u,u)\le B_0(u,u)$, and if $B_0(u,u)\le 0$ then $B(u,u)=B_T(u,u)\le 0$ with $u\mathrm{\ne }0$, excluding positive definiteness.

(Path determinant recursion.) Let $\mathrm{\Gamma }$ be a path with vertices $s_1,\dots ,s_n$ and $m_k=m(s_k,s_{k+1})$, and let $C$ be the cosine matrix $C=(B(e_s,e_t))$. Its leading $k\times k$ submatrix $C_k$ has diagonal entries $1$, sub- and super-diagonal entries $-c(s_k,s_{k+1})=-\cos (\pi \mathrm{/}{m}_k)$, and all other entries $0$. Put $d_k=\det C_k$, with $d_0=1$ and $d_1=\det (1)=1$. Expanding $\det C_k$ along its last row $(0,\dots ,0,-\cos (\pi \mathrm{/}{m}_{k-1}),1)$ for $k\ge 2$: the last entry contributes $\det C_{k-1}$, and writing $c=\cos (\pi \mathrm{/}{m}_{k-1})$, the other entry contributes $(-c)(-1{)}^{2k-1}\det M$, where $M$ is obtained by deleting row $k$ and column $k-1$. Its last column has the sole nonzero entry $-c$ in its last row, so expansion gives $\det M=-c\det C_{k-2}$; this contribution is therefore $-c^2{d}_{k-2}$, giving $d_k=d_{k-1}-{\cos }^2(\pi \mathrm{/}{m}_{k-1})d_{k-2}(k\ge 2)\mathrm{.}$

(Chain inequality.) Let $\mathrm{\Gamma }$ be a path, all of whose labels are $3$ except one edge $\{s_i,s_{i+1}\}$ labelled $m\ge 4$, with $1\le i\le j=n-i$; by [F3] and [F9] the form $B$ makes $V$ a finite-dimensional inner product space. Put $u={\sum }_{k=1}^{i}k{e}_{s_k}$ and $v={\sum }_{k=1}^{j}k{e}_{s_{n+1-k}}$, so that $u$ is supported on $\{s_1,\dots ,s_i\}$, $v$ on $\{s_{i+1},\dots ,s_n\}$, and the coefficients of the two endpoints $s_i,s_{i+1}$ of the large edge are $i$ and $j$. All internal edges of the two chains have label $3$, and $B(e_{s_k},e_{s_{k+1}})=-\frac{1}{2}$ by step 1.1, so the diagonal terms and the two symmetric terms for each internal edge give $B(u,u)={\sum }_{k=1}^i{k}^2-{\sum }_{k=1}^{i-1}k(k+1)=i^2-{\sum }_{k=1}^{i-1}k=\frac{i(i+1)}{2},B(v,v)=\frac{j(j+1)}{2},$ with the same computation for $v$, while every mixed pair contributes $0$ except $\{s_i,s_{i+1}\}$, giving $B(u,v)=-ij\cos (\pi \mathrm{/}m)$. Since $u,v$ are nonzero and supported on disjoint subsets of the basis $(e_s{)}_{s\in S}$, they are linearly independent [F12], so [F10] is strict, $B(u,v{)}^2<B(u,u)B(v,v)$, that is $i^2{j}^2{\cos }^2(\pi \mathrm{/}m)<\frac{i(i+1)}{2}\cdot \frac{j(j+1)}{2}$, which gives $(i+1)(j+1)>4ij{\cos }^2(\pi \mathrm{/}m)$.

(No cycles.) Let $s_1,\dots ,s_r$ $(r\ge 3)$ be distinct vertices whose consecutive pairs are edges, and put $u=e_{s_1}+\cdots +e_{s_r}\mathrm{\ne }0$, a vector with all coordinates $\ge 0$ in the basis $(e_s)$. Every consecutive pair contributes $2B(e_{s_i},e_{s_{i+1}})=-2c(s_i,s_{i+1})\le -1$ because $c\ge \frac{1}{2}$ on edges [1.1], and every other pair contributes $2B\le 0$ (the value $0$ for non-edges, $\le -1$ for the remaining edges), so $B(u,u)\le r-r=0$; by the witness principle [1.2] this contradicts positive definiteness of $B$. Hence $\mathrm{\Gamma }$ contains no cycle. Connectedness gives a path between any two vertices, and two different simple paths would give a cycle between their first divergence and subsequent reunion; thus that path is unique. Removing a vertex separates its neighbours into distinct components, since a path between two neighbours avoiding the removed vertex would create a cycle. Finally, a finite connected acyclic graph of maximum degree at most $2$ is a path: a longest simple path has no extension at either end, and an additional vertex would have a path to it meeting an internal vertex (creating degree at least $3$) or an endpoint (extending it). These elementary consequences will be used below.

(Path with all labels $3$.) For the path with every label $3$ the recursion of [1.3] reads $d_k=d_{k-1}-\frac{1}{4}{d}_{k-2}$; by induction on $k$ [F13] one has $d_k=(k+1)\mathrm{/}{2}^k$ for all $k\ge 0$, since $d_0=1$, $d_1=1$ and $\frac{k}{2^{k-1}}-\frac{1}{4}\cdot \frac{k-1}{2^{k-2}}=\frac{2k-(k-1)}{2^k}=\frac{k+1}{2^k}$. In particular $d_k>0$, and multiplying the $n\times n$ matrix $C$ by $2$ scales its determinant by $2^n$, so $\det (2C)=2^n{d}_n=n+1$.

(Integer consequences of the chain inequality.) Write $c=\cos (\pi \mathrm{/}m)$ with $m\ge 4$, where $m=\mathrm{\infty }$ means $c=1$ [F2]. If $i\ge 2$, then $j\ge i\ge 2$ and $(i+1)(j+1)=ij+i+j+1\le 3ij$, because $3ij-(i+1)(j+1)=2ij-i-j-1=(i-1)(j-1)+ij-2\ge 1+4-2=3>0$. If $m\ge 6$, including $m=\mathrm{\infty }$, then $4c^2\ge 4{\cos }^2(\pi \mathrm{/}6)=3$ by [1.1], so $(i+1)(j+1)\le 3ij\le 4c^{2}ij$ and the inequality $(i+1)(j+1)>4c^{2}ij$ forces $i=1$; then it reads $2(j+1)>4c^{2}j$, i.e. $1>j(2c^2-1)\ge j\mathrm{/}2$ because $2c^2\ge 3\mathrm{/}2$, and hence $j=1$ (for $m=\mathrm{\infty }$ it reads $4>4$, false, so no infinite label occurs). If $m=5$, then $4c^2=(3+\sqrt{5})\mathrm{/}2$ and $4c^2-1=\frac{1+\sqrt{5}}{2}$ by [1.1]; for $i\ge 2$ the inequality fails because $4c^{2}ij-(i+1)(j+1)=(4c^2-1)ij-i-j-1\ge \frac{1+\sqrt{5}}{2}\cdot 2j-2j-1=(\sqrt{5}-1)j-1>0$ for $j\ge 2$, so $i=1$, and then $2(j+1)>4c^{2}j$ reads $j<2\mathrm{/}(4c^2-2)=4\mathrm{/}(\sqrt{5}-1)=\sqrt{5}+1$, so $j\le 3$. If $m=4$, then $4c^2=2$ by [1.1] and the inequality reads $i+j+1>ij$: for $i=1$ this holds for every $j\ge 1$, for $i=2$ it reads $j<3$, so $j=2$, and for $i\ge 3$ it fails since $ij-i-j-1=(i-1)(j-1)-2\ge 2>0$.

(Two large labels are impossible.) Suppose two distinct edges of $\mathrm{\Gamma }$ carry labels $\ge 4$. Since [2.2] shows that $\mathrm{\Gamma }$ is acyclic, the two edges are joined by a unique simple path; write its vertices as $x_0,x_1,\dots ,x_r$ so that $x_0,x_1$ and $x_{r-1},x_r$ are the two large edges, $r\ge 2$. Put $u=e_{x_0}+\sqrt{2}{\sum }_{h=1}^{r-1}{e}_{x_h}+e_{x_r}$ (all coordinates $\ge 0$). The diagonal contribution is $1+2(r-1)+1=2r$. The two large edges contribute $2(-\cos (\pi \mathrm{/}m))\sqrt{2}\le -2\sqrt{2}\cdot \frac{\sqrt{2}}{2}=-2$ each, by [1.1] and $m\ge 4$; each of the $r-2$ remaining path edges contributes $2(-\cos (\pi \mathrm{/}{m}_h))\cdot 2\le -2$; and all other pairs contribute $\le 0$. Hence $B(u,u)\le 2r-4-2(r-2)=0$, so by the witness principle [1.2] $B$ is not positive definite, a contradiction. Therefore at most one edge of $\mathrm{\Gamma }$ has label $\ge 4$.

(The neighbour inequality.) Fix $s\in S$ and let $t\mathrm{\ne }{t}^{\mathrm{\prime }}$ be neighbours of $s$. If $t,t^{\mathrm{\prime }}$ were joined by an edge, then $s,t,t^{\mathrm{\prime }}$ would be three distinct vertices whose consecutive pairs are edges, i.e. a cycle, which [2.2] excludes; so $B(e_t,e_{t^{\mathrm{\prime }}})=0$ for distinct neighbours. By [F2] each $B(e_t,e_t)=1$, and the restriction of $B$ to the subspace $P=\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n}\{e_t:t\in N(s)\}$ is an inner product, because $B$ is positive definite on $V$ [F3] and restricts to $V\times V$. Let $e_s=p+q$ with $p\in P$, $q\in P^{\perp }$ be the orthogonal decomposition of [F9]; then $p={\sum }_{t\in N(s)}B(e_s,e_t)e_t=-{\sum }_{t\in N(s)}c(s,t)e_t$ and $\mathrm{\parallel }p{\mathrm{\parallel }}^2={\sum }_{t\in N(s)}c(s,t{)}^2$. Since $e_s$ together with the $e_t$, $t\in N(s)$, consists of distinct vectors of the basis $(e_s{)}_{s\in S}$, the vector $e_s$ is not in $P$ [F12], so $q\mathrm{\ne }0$ and ${\sum }_{t\in N(s)}c(s,t{)}^2=\mathrm{\parallel }p{\mathrm{\parallel }}^2=\mathrm{\parallel }{e}_s{\mathrm{\parallel }}^2-\mathrm{\parallel }q{\mathrm{\parallel }}^2<\mathrm{\parallel }{e}_s{\mathrm{\parallel }}^2=B(e_s,e_s)=1.$

(Three-arm inequality.) Suppose $v$ has degree $3$ and every edge of $\mathrm{\Gamma }$ has label $3$, and the three components of $\mathrm{\Gamma }-v$ are paths with $p,q,r\ge 1$ vertices. Weight each arm from its far end toward $v$: if the arm of $v$ with $p$ vertices is $a_1-a_2-\cdots -a_p$ with $a_p$ adjacent to $v$, put $u={\sum }_{h=1}^{p}h{e}_{a_h}$, and define $w,z$ for the other two arms cyclically. Then $B(u,u)=p(p+1)\mathrm{/}2$ by the same computation as in [2.1], $B(e_v,u)=p\cdot (-\frac{1}{2})=-\frac{p}{2}$ since only the pair $\{v,a_p\}$ contributes, and $u,w,z$ are pairwise orthogonal because their supports lie in different components of $\mathrm{\Gamma }-v$, so no edge joins two of them [2.2]. Moreover $e_v\mathrm{\notin }\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n}\{u,w,z\}$, as $u,w,z$ involve only basis vectors different from $e_v$; hence the orthogonal decomposition of $e_v$ with respect to that subspace is strict and [F9] gives $1=\mathrm{\parallel }{e}_v{\mathrm{\parallel }}^2>\frac{B(e_v,u{)}^2}{B(u,u)}+\frac{B(e_v,w{)}^2}{B(w,w)}+\frac{B(e_v,z{)}^2}{B(z,z)}={\sum }_p\frac{p^2\mathrm{/}4}{p(p+1)\mathrm{/}2}=\frac{1}{2}{\sum }_p\frac{p}{p+1},$ i.e. $\sum 1\mathrm{/}(p+1)>1$.

(Local consequences.) Fix $s\in S$ and use ${\sum }_{t\in N(s)}c(s,t{)}^2<1$ [3.3] together with $c(s,t)\ge \frac{1}{2}$ for every neighbour and $c\le 1$. A neighbour with $m(s,t)=\mathrm{\infty }$ would have $c(s,t)=1$ and hence a sum $\ge 1$, so no label is $\mathrm{\infty }$; four neighbours would give a sum $\ge 4\cdot \frac{1}{4}=1$, so $\mathrm{\mid }N(s)\mathrm{\mid }\le 3$; if there are three neighbours and one of their edges has label $\ge 4$, that edge contributes at least $\frac{1}{2}$ while the other two each contribute at least $\frac{1}{4}$ by step 1.1, giving a sum $\ge 1$, a contradiction; hence all three edges have label $3$; and two neighbours with labels $m_1\le m_2$ and $c_j=\cos (\pi \mathrm{/}{m}_j)$ satisfy $c_1^2+c_2^2<1$: if $m_1\ge 4$ then $c_1^2\ge \frac{1}{2}$ and $c_2^2\ge c_1^2\ge \frac{1}{2}$ (cosine increases with $m$ [1.1]), a contradiction, so $m_1=3$ and then $c_2^2<\frac{3}{4}$; since ${\cos }^2(\pi \mathrm{/}6)=\frac{3}{4}$ and cosine increases with $m$, $m_2\ge 6$ would give $c_2^2\ge \frac{3}{4}$, so $m_2\le 5$. In particular $(m_1,m_2)=(4,4)$ gives $c_1^2+c_2^2=1$ and $(3,6)$ gives $\frac{1}{4}+\frac{3}{4}=1$, both excluded.

(Integer consequences of the three-arm inequality.) Let $1\le p\le q\le r$ with $1\mathrm{/}(p+1)+1\mathrm{/}(q+1)+1\mathrm{/}(r+1)>1$. If $p\ge 2$, then $p+1,q+1,r+1\ge 3$ and the sum is at most $1$, so $p=1$. Then $1\mathrm{/}(q+1)+1\mathrm{/}(r+1)>\frac{1}{2}$: if $q=1$ this holds for every $r\ge 1$; if $q=2$ it reads $1\mathrm{/}(r+1)>\frac{1}{6}$, i.e. $r<5$, so $r\in \{2,3,4\}$; and if $q\ge 3$ the sum is at most $\frac{1}{4}+\frac{1}{4}=\frac{1}{2}$, a contradiction. Hence, up to permutation, $(p,q,r)=(1,1,r)$ for some $r\ge 1$, or $(p,q,r)\in \{(1,2,2),(1,2,3),(1,2,4)\}$.

(At most one vertex of degree $3$.) Suppose $s\mathrm{\ne }t$ are two vertices of degree $\ge 3$. By [4.1] both have degree exactly $3$. By [2.2] the diagram is acyclic, so $s$ and $t$ are joined by a unique simple path $s=v_0,v_1,\dots ,v_L=t$ with $L\ge 1$, the remaining neighbours $a,a^{\mathrm{\prime }}$ of $s$ and $b,b^{\mathrm{\prime }}$ of $t$ lie outside this path, and all of $a,a^{\mathrm{\prime }},b,b^{\mathrm{\prime }}$ are pairwise distinct (two of them equal would create a second $s$-$t$ path, or a triangle when $L=1$). Put $u={\sum }_{h=0}^L{e}_{v_h}+\frac{1}{2}(e_a+e_{a^{\mathrm{\prime }}}+e_b+e_{b^{\mathrm{\prime }}})$, a nonzero vector with all coordinates $\ge 0$: its diagonal contribution is $(L+1)+4\cdot \frac{1}{4}=L+2$, the $L$ path edges contribute $2(-c)\le -1$ each, the four pendant edges contribute $2(-c)\cdot \frac{1}{2}=-c\le -\frac{1}{2}$ each, and all other pairs contribute $\le 0$; hence $B(u,u)\le (L+2)-L-2=0$, contradicting positive definiteness by the witness principle [1.2]. So at most one vertex of degree $3$ exists, and by [4.1] at most one of degree $\ge 3$.

(A degree-$3$ vertex excludes every large label.) Suppose $v$ has degree $3$ and some edge has label $m\ge 4$. Removing $v$ from the acyclic graph of [2.2] leaves three components, and the large edge lies in one of them: write $x_0=v,x_1,\dots ,x_k,y$ in order along a path, so that $\{x_k,y\}$ is the large edge (possibly $k=0$ with $y$ a neighbour of $v$), and let $b,b^{\mathrm{\prime }}$ be the neighbours of $v$ in the other two components. Then $b,b^{\mathrm{\prime }}$ and $x_0,\dots ,x_k,y$ are pairwise distinct except for the described edges, and $u={\sum }_{h=0}^k{e}_{x_h}+\cos (\pi \mathrm{/}m)e_y+\frac{1}{2}(e_b+e_{b^{\mathrm{\prime }}})$ is nonzero with all coordinates $\ge 0$; its diagonal contribution is $(k+1)+c^2+\frac{1}{2}$ with $c=\cos (\pi \mathrm{/}m)$, the $k$ path edges $v=x_0,\dots ,x_k$ contribute $2(-c_h)\le -1$ each, the large edge contributes $-2c^2$, the two edges at $v$ toward $b,b^{\mathrm{\prime }}$ contribute $-c(v,b)\le -\frac{1}{2}$ each, and all other pairs contribute $\le 0$. Hence $B(u,u)\le (k+1)+c^2+\frac{1}{2}-k-2c^2-1=\frac{1}{2}-c^2\le 0$ because $m\ge 4$ gives $c\ge \frac{\sqrt{2}}{2}$ and $c^2\ge \frac{1}{2}$ by [1.1]; by the witness principle [1.2] this contradicts positive definiteness. So if a large label exists, no vertex of degree $3$ exists; combined with [4.1] every degree is $\le 2$ and the acyclic connected $\mathrm{\Gamma }$ is a path.

(Conclusion.) Let $\mathrm{\Gamma }$ be connected and positive definite. By [2.2] it is acyclic, hence a tree. If $\mathrm{\Gamma }$ has no vertex of degree $3$, then by [4.1] all degrees are $\le 2$, so $\mathrm{\Gamma }$ is a path: with all labels $3$ it is $A_n$ ($n\ge 1$) [2.3]; otherwise by [3.2] exactly one edge has label $m\ge 4$ and [5.2] applies, and splitting the path at that edge into subpaths of $i\le j$ vertices, the inequality of [2.1] and its case analysis [3.1] give $(i,j)=(1,1)$ with $m\ge 6$, giving the single edge $I_2(m)$; $(i,j)=(1,1)$ with $m=4$ or $m=5$, giving $I_2(4)=B_2$ and $I_2(5)$; $(i,j)=(1,j)$ with $j\ge 2$ and $m=4$, giving the paths with labels $3,\dots ,3,4$ (type $B_{j+1}$, the label-$4$ edge at an end); $(i,j)=(1,2)$ and $(1,3)$ with $m=5$, giving the paths with labels $3,5$ (type $H_3$) and $3,3,5$ (type $H_4$); and $(i,j)=(2,2)$ with $m=4$, giving the path with labels $3,4,3$ (type $F_4$). If $\mathrm{\Gamma }$ has a vertex of degree $3$, it is unique by [5.1], its edges have label $3$ and no edge has label $\ge 4$ by [5.2] and [4.1], and the three arms have $p,q,r\ge 1$ vertices satisfying the inequality of [3.4]; by [4.2] they are $(1,1,r)$ with $r\ge 1$, giving the star with arms $1,1,r$, i.e. $D_{r+3}$ ($n=r+3\ge 4$), or $(1,2,2)$, $(1,2,3)$, $(1,2,4)$, giving $E_6$, $E_7$, $E_8$. Thus every connected positive definite diagram is one of $A_n$ ($n\ge 1$), $B_n$ ($n\ge 2$), $D_n$ ($n\ge 4$), $E_6,E_7,E_8$, $F_4$, $H_3$, $H_4$, $I_2(m)$ ($m\ge 3$) with the labels displayed in (7), which is the asserted list.