Path determinants $d_k=d_{k-1}-{\cos }^2(\pi \mathrm{/}m)d_{k-2}$ and the three-arm inequality

(The recursion by expansion.) Set $d_0:=1$; the leading $1\times 1$ matrix is $(1)$, so $d_1=1$ [F2]. For $2\le k\le n$ let $C_k$ be the leading $k\times k$ submatrix and put $a:=\cos (\pi \mathrm{/}{m}_{k-1})$, with $a=1$ for an infinite label. By [F1, F2] its diagonal entries are $1$, its adjacent off-diagonal entries are $-\cos (\pi \mathrm{/}{m}_j)$ and all others are $0$. In the last-row Laplace expansion [F4], the diagonal entry contributes $d_{k-1}$. Deleting row $k$ and column $k-1$ leaves a matrix whose last column has only its bottom entry $-a$; expanding that column gives determinant $-a{d}_{k-2}$, also for $k=2$ with the empty minor. The last-row cofactor sign at $(k,k-1)$ is $-1$, so the other contribution is $-a^2{d}_{k-2}$. Therefore $d_k=d_{k-1}-a^2{d}_{k-2}$ without any positivity assumption.

(The integer cases.) Let $1\le p\le q\le r$ satisfy the inequality of (ii). If $p\ge 2$ then $\frac{1}{p+1}+\frac{1}{q+1}+\frac{1}{r+1}\le 3\cdot \frac{1}{3}=1$ with equality only for $p=q=r=2$, so $p=1$. Then $\frac{1}{q+1}+\frac{1}{r+1}>\frac{1}{2}$: for $q=1$ this holds for every $r\ge 1$; for $q=2$ it says $\frac{1}{r+1}>\frac{1}{6}$, i.e. $r<5$, so $r\in \{2,3,4\}$; and for $q\ge 3$ the sum is at most $\frac{1}{4}+\frac{1}{4}=\frac{1}{2}$, a contradiction. Hence the triples are $(1,1,r)$ for $r\ge 1$, $(1,2,2)$, $(1,2,3)$ and $(1,2,4)$ up to order. The equality cases $\frac{1}{p+1}+\frac{1}{q+1}+\frac{1}{r+1}=1$ are found the same way: $p\ge 3$ gives a sum $\le \frac{3}{4}<1$; $p=2$ forces $q=r=2$; and $p=1$ forces $\frac{1}{q+1}+\frac{1}{r+1}=\frac{1}{2}$, i.e. $q=2,r=5$ or $q=3,r=3$. Thus $(2,2,2)$, $(1,2,5)$ and $(1,3,3)$ are exactly the boundary triples.

(The all-$3$ path.) First $\cos (\pi \mathrm{/}3)=1\mathrm{/}2$: putting $c=\cos (\pi \mathrm{/}3)$, [F7] gives $2c^2-1=\cos (2\pi \mathrm{/}3)=-c$, so $(2c-1)(c+1)=0$, and $c>-1$ because $0<\pi \mathrm{/}3<\pi$, cosine is strictly decreasing on $[0,\pi ]$ and $\cos \pi =-1$ [F7], hence $c=1\mathrm{/}2$. If every label is $3$, then $\cos (\pi \mathrm{/}{m}_j)=1\mathrm{/}2$, so the recursion of 1.1 reads $d_k=d_{k-1}-\frac{1}{4}{d}_{k-2}$ with $d_0=d_1=1$; by the induction principle [F8] the formula $d_k=(k+1)\mathrm{/}{2}^k$ holds for all $k\ge 0$, since $\frac{k}{2^{k-1}}-\frac{1}{4}\cdot \frac{k-1}{2^{k-2}}=\frac{k+1}{2^k}$. Hence $d_k>0$ for every $k$, the leading principal minors of $2C$ are $2^k{d}_k=k+1>0$ by [F5], and $2C$ and $C$ are positive definite by [F6]; in particular $\det (2C)=2^n{d}_n=n+1$.

(One large edge: the two-subpath formula.) Let the path have all labels $3$ except one edge labelled $m$ between the $i$-th and $(i+1)$-st vertices, and put $c:=\cos (\pi \mathrm{/}m)$, $j:=n-i\ge 1$. Write ${\delta }_k:=(k+1)\mathrm{/}{2}^k$ for the determinant of an all-$3$ path on $k$ vertices, including ${\delta }_0=1$, as proved in 2.1 [step 2.1]; these are distinct from the leading minors $d_k$ of the labelled path. Then $\det C={\delta }_i{\delta }_j-c^2{\delta }_{i-1}{\delta }_{j-1}\mathrm{.}$ Proof by induction on $j$ [F8], writing $C(i,j)$ for this matrix: for $j=1$ the large edge is the last one and expansion along the last row [F4] gives $\det C(i,1)={\delta }_i-c^2{\delta }_{i-1}={\delta }_i{\delta }_1-c^2{\delta }_{i-1}{\delta }_0$; for $j=2$ the last edge has label $3$, so the recurrence of 1.1 [step 1.1] gives $\det C(i,2)=\det C(i,1)-\frac{1}{4}{\delta }_i={\delta }_i({\delta }_1-\frac{1}{4}{\delta }_0)-c^2{\delta }_{i-1}$, which is ${\delta }_i{\delta }_2-c^2{\delta }_{i-1}{\delta }_1$ since ${\delta }_2=\frac{3}{4}$; for $j\ge 3$ the last edge again has label $3$, so $\det C(i,j)=\det C(i,j-1)-\frac{1}{4}\det C(i,j-2)$, and substituting the induction hypothesis and the recursion ${\delta }_j={\delta }_{j-1}-\frac{1}{4}{\delta }_{j-2}$ of 2.1 [step 2.1] gives the formula. With ${\delta }_k=(k+1)\mathrm{/}{2}^k$ of 2.1 [step 2.1] this is $\det C=\frac{(i+1)(j+1)-4ij{c}^2}{2^n};$ and since positive definiteness of the path would give $\det C>0$ by [F6], such a path satisfies $(i+1)(j+1)>4ij{\cos }^2(\pi \mathrm{/}m)$, which is the constraint of Exclusions for positive definite diagrams: trees, valency, labels, chains and arms (5)(ii).

(The arm vectors.) For the star of (ii) with centre $v$ and arm spans $A_1,A_2,A_3$ on the three arms, $V=\mathbb{R}{e}_v\oplus A_1\oplus A_2\oplus A_3$ and the arm spans are pairwise $B$-orthogonal, because distinct arms share no edge [F1, F2]. On the arm with vertices $s_1,\dots ,s_p$ ($s_p$ adjacent to $v$) put $w:={\sum }_{k=1}^{p}k{e}_{s_k}$. Then $B(w,w)={\sum }_{k=1}^p{k}^2-{\sum }_{k=1}^{p-1}k(k+1)=p^2-{\sum }_{k=1}^{p-1}k=\frac{p(p+1)}{2}$ and $B(e_v,w)=-\frac{p}{2}$ by [F2], and for every $u={\sum }_{k=1}^p{u}_k{e}_{s_k}$ the identity $B(w,u)=\frac{p+1}{2}{u}_p$ holds, because the coefficient of $u_k$ in $B(w,u)$ is $k-\frac{k-1}{2}-\frac{k+1}{2}=0$ for $1<k<p$ (also for $k=1$ when $p>1$), while the coefficient of $u_p$ is $p-\frac{p-1}{2}=\frac{p+1}{2}$; for $p=1$ the coefficient is $1=(p+1)\mathrm{/}2$ directly. In particular $B(e_v,u)=-\frac{u_p}{2}=-\frac{B(w,u)}{p+1}$ on the arm span. By 2.1 and [F6] the form restricted to each arm span (an all-$3$ path) is positive definite; hence $B$ is positive definite on all of $A=A_1\oplus A_2\oplus A_3$, since a nonzero element $z_1+z_2+z_3$ has some nonzero component and $B(z,z)={\sum }_{i}B(z_i,z_i)\ge B(z_j,z_j)>0$.

(Completing the square: equivalence of positive definiteness and the inequality.) Keep the notation of 3.2 [step 3.2] with arms of $p_1,p_2,p_3$ vertices and vectors $w_1,w_2,w_3$, put $\mu :={\sum }_i\frac{p_i}{2(p_i+1)}$ and $\bar{w}:=-{\sum }_i\frac{w_i}{p_i+1}\in A:=A_1\oplus A_2\oplus A_3$, so that $\bar{w}\mathrm{\ne }0$ because its components in the distinct summands are the nonzero multiples $-w_i\mathrm{/}(p_i+1)$. Then $B(\bar{w},u)=B(e_v,u)$ for every $u\in A$ by the last identity of 3.2 [step 3.2], and $B(\bar{w},\bar{w})={\sum }_i\frac{p_i(p_i+1)\mathrm{/}2}{(p_i+1{)}^2}=\mu$. Since $\bar{w}$ is a nonzero vector of $A$, on which $B$ is positive definite [step 3.2], every $u\in V$ has a unique form $u=\alpha e_v+\gamma \bar{w}+z$ with $\alpha ,\gamma \in \mathbb{R}$, $z\in A$ and $B(\bar{w},z)=0$: the $e_v$-coordinate $\alpha$ is forced, and $u-\alpha e_v\in A$ has the unique orthogonal decomposition $\gamma \bar{w}+z$ along $\bar{w}$ in the inner product space $(A,B)$, with $\gamma =B(u-\alpha e_v,\bar{w})\mathrm{/}B(\bar{w},\bar{w})$ and $z=u-\alpha e_v-\gamma \bar{w}$. Then $B(u,u)={\alpha }^2+2\alpha (\gamma B(e_v,\bar{w})+B(e_v,z))+{\gamma }^{2}B(\bar{w},\bar{w})+B(z,z)={\alpha }^2(1-\mu )+\mu (\gamma +\alpha {)}^2+B(z,z),$ because $B(e_v,\bar{w})=B(\bar{w},\bar{w})=\mu$ and $B(e_v,z)=B(\bar{w},z)=0$ [F2]. If $1-\mu >0$ then $B(u,u)$ is a sum of three terms that are $\ge 0$ and is $0$ only when $\alpha =0$, $\gamma =-\alpha =0$ and $z=0$, i.e. only for $u=0$; conversely, if $1-\mu \le 0$, then $u=e_v-\bar{w}\mathrm{\ne }0$ (its $e_v$-coordinate is $1$) has $B(u,u)=1-\mu \le 0$, so $B$ is not positive definite [F6]. Hence $B$ is positive definite if and only if $1-\mu >0$, and $1-\mu >0$ is equivalent to ${\sum }_i\frac{p_i}{p_i+1}<2$, i.e. to $3-{\sum }_i\frac{1}{p_i+1}<2$, which is the inequality of (ii). When $B$ is positive definite, the same identity exhibits the strict Cauchy-Schwarz bound $B(\bar{w},\bar{w})<B(e_v,e_v)=1$ of the projection of $e_v$ onto $A$ used in Exclusions for positive definite diagrams: trees, valency, labels, chains and arms (6), strict because $e_v\mathrm{\notin }A$ [F7].

(Conclusion.) The recursion and the all-$3$ values of (i) are steps 1.1 and 2.1 [step 1.1, step 2.1], and the two-subpath determinant formula giving the constraint $(i+1)(j+1)>4ij{\cos }^2(\pi \mathrm{/}m)$ is step 3.1 [step 3.1]. The equivalence of (ii) is step 4.1 [step 4.1], proved by completing the square along the three positive definite arms of 3.2 [step 3.2]. The list of triples of (iii) and the boundary triples are step 1.2 [step 1.2], and the boundary star $(1,2,5)$ is the one with the non-positive vector of A cycle and an overlong arm: explicit non-positive witnesses [F10]; the names $D_{r+3},E_6,E_7,E_8$ of the surviving triples are those of the classification [F9].