| Sbornik: Mathematics |
|
|
|
|
|
Complete bipartite graphs flexible in the plane M. D. Kovaleva, S. Yu. Orevkovbc a Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia b Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia c Institut de Mathématiques de Toulouse, Université Paul Sabatier, Toulouse, France
Russian version:
Matematicheskii Sbornik, 2023, Volume 214, Number 10, DOI: https://doi.org/10.4213/sm9867 
Bibliographic databases:
    § 1. Introduction. Main resultsWe find necessary and sufficient conditions (Theorem 1 and Remarks 1 and 2) for the flexibility of frameworks corresponding to complete bipartite graphs $K_{m,n}$ in the Euclidean plane $E^2$. In §§ 8 and 9 we solve the same problem for the hyperbolic plane $H^2$ and for the sphere $S^2$. Most of the results are not new but we give complete self-contained proofs, which are almost the same for $E^2$, $H^2$ and $S^2$. We do not know whether the hyperbolic case can have any independent interest, but it serves as a very convenient bridge between the proof in the Euclidean and spherical cases. Namely, when passing from $E^2$ to $H^2$, only some formulae change but the geometric and combinatorial arguments are exactly the same. On the other hand, when passing from $H^2$ to $S^2$ all formulae remain the same (just with the cosine and sine functions instead of the hyperbolic cosine and sine), only the combinatorial part is slightly extended. We define a planar framework corresponding to the complete bipartite graph $K_{m,n}$ ($(m,n)$-framework for short) as a collection of points in the Euclidean plane $\mathbf{p}=(p_1,\dots,p_m;\,q_1,\dots,q_n)$ such that $p_i\ne q_j$ for all $i$ and $j$. The parts (of the bipartite graph) are $(p_1,\dots)$ and $(q_1,\dots)$. Speaking of $(m,n)$-frameworks, we call points $p_i$ and $q_j$ joints, and we call pairs of points $(p_i,q_j)$ from different parts rods. We say that an $(m,n)$-framework $\mathbf{p}$ is nonoverlapping if all of its joints are pairwise distinct. Finally, we say that an $(m,n)$-framework is flexible if it admits a flex, that is, a continuous nonconstant motion of its joints $\mathbf{p}(t)=(p_1(t),\dots,q_n(t))$, $t\in[0,1]$, such that $\mathbf{p}(0)=\mathbf{p}$, the lengths of the rods are constant (that is, $|p_i(t)-q_j(t)|$ does not depend on $t$ for all $i$ and $j$) and two joints in different parts do not move: $p_{i_0}(t)=p_{i_0}$ and $q_{j_0}(t)=q_{j_0}$. These definitions can obviously be extended to all connected graphs but we do not need this.1 Theorem 1. Let $\min(m,n)\geqslant 3$. Then a nonoverlapping $(m,n)$-framework is flexible if and only if one of the following conditions holds. (D1) The points $p_1,\dots,p_m$ lie on a straight line $P$, the points $q_1,\dots,q_n$ lie on another line $Q$, and these two lines are orthogonal to each other. (D2) One can choose an orthogonal coordinate system and two rectangles with sides parallel to the axes and with common centre of symmetry at the origin so that $p_1,\dots,p_m$ are at vertices of one rectangle and $q_1,\dots,q_n$ are at vertices of the other. Since all points are distinct, $m\leqslant 4$ and $n\leqslant 4$ in this case. Remark 1. It is easy to see that any $(1,n)$-framework is flexible (and has ${n-1}$ degrees of freedom), and a nonoverlapping $(2,n)$-framework is flexible if and only if it does not contain a quadruple of joints $p_i,q_j,p_k,q_l$ positioned in this order on some straight line (cf. Lemma 4). All nonoverlapping flexible $(m,n)$-frameworks with $\min(m,n)\geqslant 2$ have one degree of freedom. Remark 2. It is obvious that an $(m,n)$-framework $\mathbf{p}$ with overlapping joints is flexible if and only if so is the nonoverlapping bipartite framework $\overline{\mathbf{p}}$ obtained by identifying each pair of overlapping joints. It is also clear that the number of degrees of freedom $d(\mathbf{p})$ of $\mathbf{p}$ is equal to $\max_\mathbf{q} d(\overline{\mathbf{q}})$ where the maximum is taken over all frameworks $\mathbf{q}$ obtained from $\mathbf{p}$ by small flexes. Thus, $d(\mathbf{p})=d(\overline{\mathbf{p}})\leqslant 1$ unless $p_1=\dots=p_m$ (in which case $d(\mathbf{p})=n-1$) or, symmetrically, $q_1=\dots=q_n$, $d(\mathbf{p})=m-1$. In the case $m=n=3$ the flexible frameworks (D1) and (D2) were discovered by Dixon (see [2], § 27, (d), and § 28, (n)). They are called Dixon mechanisms of the first and second kind, respectively. We will use these names for any $m,n\geqslant 3$. The Dixon mechanism of the second kind for $m=n=4$ was apparently described for the first time by Bottema in [1] (see also [11]). One can reformulate (D1) and (D2) equivalently in terms of the rod lengths. In the case of (D2) we do this for $(m,n)=(3,3)$ only, but analogous conditions can easily be derived for $(3,4)$ and $(4,4)$. Proposition 1. (a) A nonoverlapping $(m,n)$-framework is a Dixon mechanism of the first kind (see Figure 1, a) if and only if, for each cycle $p_iq_jp_kq_l$, the sums of squared lengths of the opposite sides are equal. The number of these conditions is $\binom{m}2\binom{n}2=\frac14(m^2-m)(n^2-n)$ but it is easily seen that only $(m-1)(n-1)$ of them are independent; one can choose, for example, only the conditions corresponding to the cycles $p_iq_jp_kq_l$ for fixed $i$ and $j$ (in particular, four conditions are independent among the nine ones when $m=n=3$). (b) A flexible nonoverlapping $(3,3)$-framework $(p_0,p_1,p_2;\,q_0,q_1,q_2)$ is a Dixon mechanism of the second kind if and only if, up to renumbering the vertices in the parts, $|q_0p_0|= |q_1p_1|=|q_2p_2|=a$, $|q_0p_1|=|q_1p_0|=b$, $|q_0p_2|=|q_2p_0|=c$, $|q_1p_2|=|q_2p_1|=d$ (see Figure 2) and the relation $a^2+c^2=b^2+d^2$ holds. In this case all 4-cycles with two occurrences of sides of length $a$ are parallelogrammatic, that is, have opposite sides of equal lengths. Remark 3. The following example shows that statement (b) of Proposition 1 fails without the flexibility assumption: $p_0=(b,0)$, $p_1=(0,a)$, $p_2=(d,0)$, $q_0=(b,a)$, $q_1=(0,0)$ and $q_2=(d,a)$, where $a$, $b$ and $d$ are positive, $b\ne d$ and $bd=a^2$. Indeed, all conditions on the rod lengths are satisfied in this case, but the framework is not a Dixon mechanism of the second kind. This is also an example of two nonoverlapping $(3,3)$-frameworks with equal lengths of the corresponding rods, one of which is flexible (a Dixon mechanism of the second kind) and the other is rigid by Proposition 1. This example is a particular case of the example in Figure 1, b. The proof of Proposition 1 is not difficult, and it is presented at the end of this section. Notice that Theorem 1 was proved in [8] for $m\!\geqslant\! 3$ and $n\!\geqslant\! 5$. Also, as shown in [9], the lengths of the rods of flexible nonoverlapping $(3,3)$-frameworks are as in Proposition 1. This fact, combined with Proposition 1, yields Theorem 1 for $m=n=3$. Another proof of Theorem 1 for $m=n=3$ was presented in [5], Example 4.3. The reduction of the general case to ${m=n=3}$ is very simple. It is as follows. Proof of Theorem 1 (under the assumption that it holds for $m=n=3$). Consider a nonoverlapping $(m,n)$-framework with $n\geqslant m\geqslant 3$. The points $p_1$, $p_2$, $p_3$ and $q_1$, $q_2$, $q_3$ satisfy one of conditions (D1) and (D2).
Let them satisfy (D1). Then $p_1$, $p_2$, $p_3$ and $q_1$, $q_2$, $q_j$, $j\geqslant3$, do not satisfy (D2). Hence, since the subgraph spanned by them is flexible, they satisfy (D1), that is, $q_j$ is on the line $Q$. Thus, all of $q_1,\dots,q_n$ are on $Q$. For the same reason all of $p_1,\dots,p_m$ are on $P$. Now suppose that $p_1$, $p_2$, $p_3$ and $q_1$, $q_2$, $q_3$ satisfy (D2). Consider the $(3,3)$-framework $(p_1,p_2,p_3;\,q_1,q_2,q_j)$, $j\geqslant 3$. It also satisfies (D2) because (D1) cannot hold (for $p_1$, $p_2$ and $p_3$ are not collinear). A priori, (D2) could hold for another choice of the axes of symmetry; however, the triangle $p_1p_2p_3$ has only one pair of mutually orthogonal sides, which determines the rectangle uniquely and therefore determines the axes. Notice also that a rectangle which is symmetric with respect to the origin and has sides parallel to the axes is determined by any of its vertices. Therefore $q_1$, $q_2$, $q_3$ and $q_j$ are at the vertices of the same rectangle. Analogously, $p_1,\dots,p_m$ are at the vertices of the same rectangle. The theorem is proved. The rest of this section is devoted to the proof of Proposition 1. In §§ 2–7 we give a self-contained proof of Theorem 1 for $m=n=3$. In §§ 8 and 9 we treat the hyperbolic and spherical cases, respectively. Lemma 1. Let $m,n\geqslant2$. Then any flex of a nonoverlapping $(m,n)$-framework (see the definition above) leaves unmovable only two joints. This statement follows from the fact that the if any two joints in one part are fixed, then all joints in the other part are too. Lemma 2. The diagonals of a (maybe, self-crossing) quadrilateral are orthogonal if and only if the sums of the squared lengths of the opposite sides are equal. Proof. Let $u$, $v$ and $w$ be the vectors corresponding to three consecutive sides of the quadrilateral. Then twice the dot product of the diagonals is $2(u+v)(v+w)=v^2+(u+v+w)^2-u^2-w^2$. The lemma is proved. It is clear that any parallelogrammatic nonoverlapping quadrangle is either a parallelogram (when its opposite sides are pairwise parallel) or an antiparallelogram (when its diagonals are parallel). It is both simultaneously if and only if it is degenerate, that is, all of its vertices are collinear. Proof of Proposition 1. (a) The statement follows from Lemma 2.
(b) The condition on the lengths is derived from (D2) by direct computation. Let us prove the reverse implication. Since $a^2+c^2=b^2+d^2$, Lemma 2 implies that the diagonals of the quadrangle $p_0q_1p_1q_2$ are mutually orthogonal. The same is true for the diagonals of $q_0p_1q_1p_2$ (see Figure 2), that is, $p_0p_1\perp q_1q_2$ and $q_0q_1\perp p_1p_2$. By hypothesis, the cycles $\Pi_{ij}=p_iq_ip_jq_j$, $i<j$, are parallelogrammatic. Suppose that both $\Pi_{01}$ and $\Pi_{12}$ are nondegenerate parallelograms (see Figure 1, b). Then $p_0q_0q_2p_2$ is also a parallelogram and, since its both diagonals are of length $c$, it is a rectangle with sides $a$ and $\sqrt{c^2-a^2}$. Hence any flex fixing $p_0$ and $q_0$ fixes $p_2$ and $q_2$ too, which contradicts Lemma 1. The contradiction obtained shows that $\Pi_{01}$ or $\Pi_{12}$ is an antiparallelogram (maybe, degenerate). Let it be $\Pi_{01}$ (the case of $\Pi_{12}$ is analogous). Then $q_1q_2\perp p_0p_1\parallel q_0q_1\perp p_1p_2$, hence $q_1q_2\parallel p_1p_2$, that is, $\Pi_{12}$ is also an antiparallelogram. Hence $q_0$ and $q_2$ are symmetric to $q_1$ with respect to the mutually orthogonal symmetry axes of these antiparallelograms (see Figure 2). The same is true for $p_0$, $p_2$, and $p_1$. The proposition is proved. AcknowledgementWe thank Matteo Gallet for informing us about [3] and [5] and for making some comments on those papers. § 2. A general scheme of the proof of Theorem 1 for $m=n=3$Consider a flex of a nonoverlapping $(3,3)$-framework $\mathbf{p}=(p_0,p_1,p_2;\,q_0,q_1,q_2)$ such that the joints $p_0$ and $q_0$ are fixed. Then $p_1$, $p_2$, $q_1$ and $q_2$ move along circles, which we denote by $P_1$, $P_2$, $Q_1$ and $Q_2$, respectively. Forget about the joint $p_2$ for a while. Then, generically (when the line segment $q_1p_1$ is not orthogonal to $P_1$), the displacement of $q_1$ determines uniquely the displacement of $p_1$, which in its turn determines generically the displacement of $q_2$. We obtain a dependence2 $q_2={\mathcal F}_1(q_1)$ (see Figure 3). Analogously, $p_2$ ensures a dependence $q_2={\mathcal F}_2(q_1)$. In order that our $(3,3)$-framework not be jammed, the functions ${\mathcal F}_1$ and ${\mathcal F}_2$ must coincide. The point $(q_1,{\mathcal F}_i(q_1))$, $i=1,2$, moves along a certain real algebraic curve $C_i$ on the torus $Q_1\times Q_2$. The flexibility of $\mathbf{p}$ requires that $C_1$ and $C_2$ have an irreducible component in common. Let us proceed to a more formal exposition. Fix two points $p_0,q_0\in{\mathbb{R}}^2$. Without loss of generality we can set $q_0=(0,0)$ and $p_0=(r,0)$. Fix real positive numbers $r_{ij}$, $i,j\in\{0,1,2\}$, where $r_{00}=r$ (one can set $r=1$ in the Euclidean case). Also set $R_i=r_{i0}$ and $r_i=r_{0i}$, $i=1,2$. Let $M$ be the set of all quadruples $(p_1,p_2;\,q_1,q_2)$ such that $|p_iq_j|=r_{ij}$, $i,j\in\{0,1,2\}$. It is natural to consider $M$ as the moduli space of $(3,3)$-frameworks with a prescribed matrix of lengths. Abusing the language we also call elements of $M$ $(3,3)$-frameworks, assuming them implicitly to include $p_0$ and $q_0$. As above, we define the circles
$$
\begin{equation*}
P_k=\{p_k\in{\mathbb{R}}^2 \colon |q_0p_k|=R_k\} \quad\text{and}\quad Q_k=\{q_k\in{\mathbb{R}}^2 \colon |p_0q_k|=r_k\}, \qquad k=1,2,
\end{equation*}
\notag
$$
and set $Q=Q_1\times Q_2$. For $k=1,2$ consider the space of $(2,3)$-frameworks $(p_0,p_k;\,q_0,q_1,q_2)$ with the following lengths:
$$
\begin{equation*}
M_k=\{(p_k,q_1,q_2)\in P_k\times Q\colon |p_kq_1|=r_{k1},\, |p_kq_2|=r_{k2}\}.
\end{equation*}
\notag
$$
Set $C_k=\tau_k(M_k)$, where the $\tau_k\colon P_k\times Q\to Q$, $k=1,2$, are the standard projections (these are the curves that appeared in the above discussion of transmission functions). It is clear that, generically, $C_1$ and $C_2$ are algebraic curves on $Q$ (though if, for example, $M$ has an element such that $p_0=p_k$, then $C_k=Q$). Let us find the defining equations for $C_1$ and $C_2$. As in [9], we parametrize the circle $Q_j$, $j=1,2$, by a complex number $t_j$ ranging over the circle $|t_j|=r_j/r$ in the complex plane. The coordinates of the vector $p_0q_j$ are $(r\operatorname{Re} t_j,r\operatorname{Im} t_j)$; in other words, the parameter corresponding to $q_j$ is the image of the vector $\frac1r p_0q_j$ under the standard identification of $\mathbb{R}^2$ with $\mathbb{C}$. We choose analogously parameters $T_i$ on the circles $P_i$. In these coordinates the conditions $|p_iq_j|=r_{ij}$, $i,j=1,2$, take the form $f_{ij}(T_i,t_j)=0$, where $f_{ij}$ is the numerator of the rational function obtained from the expression $r^2(1+T_i - t_j)(1+\overline T_i - \overline t_j)-r_{ij}^2$ by the substitution $\overline T_i = R_i^2/(r^2 T_i)$, $\overline t_j = r_j^2/(r^2 t_j)$, that is,
$$
\begin{equation*}
f_{ij}(T_i,t_j)=(1+T_i-t_j)(r^2 T_it_j+R_i^2 t_j-r_j^2 T_i)-r_{ij}^2T_it_j
\end{equation*}
\notag
$$
(cf. [9], (6)–(9)). Each $C_i$ is the projection of the set of solutions of the system of equations $f_{i1}=f_{i2}=0$, hence it is given by the equation $F_i(t_1,t_2)=0$, where
$$
\begin{equation}
F_i(t_1,t_2)=R_i^{-2}\operatorname*{Res}_{T_i}(f_{i1},f_{i2})
\end{equation}
\tag{2.1}
$$
(see Remark 4 below). The expression for $F_i$ (as a polynomial in $t_1$, $t_2$ and all the $r_{ij}$) has 126 monomials, and we have $\deg_{t_j}F_i=4$. In the case of a nonoverlapping flex, the images of $M$ in $Q_j$ are not discrete by Lemma 1, which implies the following fact. Thus the search of all flexible $(3,3)$-frameworks is reduced to a computation of the resultant of $F_1$ and $F_2$ and a solution of the system of equations obtained by equating all of its coefficients to zero. This is the way in which Walter and Husty obtained in [9] the result (mentioned in the introduction) that the lengths of the rods of flexible nonoverlapping $(3,3)$-frameworks are always as in Dixon mechanisms. According to [9], $\operatorname{Res}(F_1,F_2)$ contains 4 900 722 monomials, and it was said in [9] that “the computations are very extensive with respect to time and memory”. Also, as far as we have understood from [9], one needs to do some programming to interpret the solutions obtained with the use of Maple or Singular. When we started working on flexible $(3,3)$-frameworks (without knowing about the paper [9]), we also tried to solve this system of equations. However, we did not succeed in overcoming computational difficulties and looked for how to avoid them.3 So we found the proof exposed below. The longest computation in our proof is that of the resultant (7.1), which takes 25 ms of CPU time. It should be pointed out that the choice of the parameters $T_i$ and $t_j$ borrowed from [9] simplified further the computations in Lemma 6 (initially, we used the standard parametrization of the circle by the tangent of the half-angle). The outline of our proof is as follows. If $M$ contains a flexible nonoverlapping $(3,3)$-framework, then the curves $C_1$ and $C_2$ have a common component, that is, the polynomials $F_1$ and $F_2$ have a common divisor. If one of $F_1$ and $F_2$ is irreducible, then they are proportional. This gives us equations which are easy to solve. If $F_1$ and $F_2$ have a common divisor not being proportional, then we look how the complexifications of the curves $M_i$, $C_i$, $C_{ij}=\{f_{ij}=0\}$ and $P_i$ are mapped to each other under the projections. A not difficult study shows that for each $i=1,2$ either one of the $C_{ij}$ is reducible, or the projections $C_{i1}\to P_i$ and $C_{i2}\to P_i$ are ramified over the same points. Both conditions lead to equations which allow us to conclude that the framework contains either a parallelogrammatic cycle or a deltoid (a 4-cycle symmetric with respect to a diagonal) arranged in a certain way with respect to $p_0$ and $q_0$. By varying the choice of the fixed joints we arrive either to a Dixon mechanism of the first kind or to a framework containing three parallelogrammatic cycles adjacent to each other as in Dixon mechanisms of the second kind. In the latter case the resultant of $F_1$ and $F_2$ is easy to compute. Remark 4. Even when the coefficients of $T_i^2$ in $f_{ij}$ vanish, the resultant in (2.1) is understood as the resultant of quadratic polynomials ($R_{2,2}$ in the notation of [4], Ch. 12, that is, the determinant of the $4\times 4$ Sylvester matrix). In a similar way the resultants in (2.2) and the discriminants $D_j$ and $\Delta_j^\pm$ in § 6 always correspond to $R_{4,4}$ and $D_2$ in [4], Ch. 12. § 3. Preliminary lemmasLemma 4 (immediate from Lemma 1). If an $(m,n)$-framework, $m,n\geqslant 2$, contains a 4-cycle with a rod whose length is equal to the sum of the lengths of the three other rods of the cycle, then the framework is not flexible. Lemma 5. Let $\mathbf{p}=(p_0,p_1,p_2;\,q_0,q_1,q_2)$ be a flexible nonoverlapping $(3,3)$-framework. Suppose that $|p_0q_j|=|p_1q_j|$ for all $j=0,1,2$, that is, the joints $p_0$ and $p_1$ are equidistant from each of $q_0$, $q_1$ and $q_2$. Then $\mathbf{p}$ is a Dixon mechanism of the first kind. Since flexible frameworks are infinitesimally flexible, this lemma follows from Whiteley’s theorem4 [10], according to which a nonoverlapping $(m,n)$-framework with $\min(m,n)\geqslant 3$ is infinitesimally flexible if and only if either all joints lie on a second-order curve, or all joints of one part and at least one joint of the other part are collinear (for $m=n=3$ the second condition is a particular case of the first). However, since we are presenting a self-contained proof of Theorem 1, we prove Lemma 5 directly. Proof of Lemma 5. We denote the rod lengths by $r_i=|p_0q_i|=|p_1q_i|$ and ${R_i\,{=}\,|p_2q_i|}$, $i=0,1,2$. Consider a continuous deformation $\mathbf{p}(t)$. The equidistance condition implies that the points $q_j$ rest collinear and $q_0q_1\perp p_0p_1$ during this deformation. Hence without loss of generality we may assume that the $q_j$ remain on the axis $y=0$, whereas $p_0$ and $p_1$ remain on the axis $x=0$. Set $q_i=(x_i,0)$, $i=0,1,2$, and denote the $x$-coordinate of $p_2$ by $a$. Then Differentiating these identities with respect to $t$ we obtain a system of four linear homogeneous equations for $x'_0$, $x'_1$, $x'_2$ and $a'$. Its determinant is $a(x_0-x_1)(x_0-x_2)(x_1-x_2)$. Flexibility implies the existence of a nonzero solution, thus, $a=0$. The lemma is proved.
§ 4. General case: $F_1$ and $F_2$ are proportionalLet the notation be as in § 2. Suppose that $M$ contains a flexible nonoverlapping $(3,3)$-framework $\mathbf{p}=(p_0,p_1,p_2;\,q_0,q_1,q_2)$. Lemma 6. If $F_1=\lambda F_2$ for some number $\lambda$, then $\mathbf{p}$ is a Dixon mechanism of the first kind. Proof. Set $F=F_1-\lambda F_2$. This is a polynomial of the form $\sum_{k,l=0}^4 c_{kl}\,t_1^k t_2^l$, where the $c_{kl}$ are polynomials in $r_{ij}^2$ and we have $c_{00}=c_{01}=c_{43}=c_{44}=0$. By hypothesis the $c_{kl}$ must vanish identically. There is a symmetry $c_{4-k,4-l}=r_1^{2k-4}r_2^{2l-4}c_{k,l}$, hence only 11 of these 21 equations are distinct. A computation shows that
Case 1: $\lambda=0$. Then the equations $c_{04}=c_{20}=c_{02}=0$ yield $R_1=r$, $r_1=r_{11}$ and $r_2=r_{12}$, hence the joints $p_0$ and $p_1$ are equidistant from all the $q_j$ and the result follows from Lemma 5. Case 2: $\lambda=1$. Then the equations $c_{04}=c_{20}=c_{02}=0$ yield $R_1=R_2$, $r_{11}=r_{21}$ and $r_{12}=r_{22}$, hence the joints $p_1$ and $p_2$ are equidistant from all the $q_j$ and, again, the result follows from Lemma 5. Case 3: $R_2=r$ and $\lambda(1-\lambda)\ne 0$. Then the equation $c_{04}=0$ implies that $R_1=r$. We find $r_{11}^2$ and $r_{12}^2$ from the equations $c_{20}=c_{02}=0$ and plug the result into $c_{12}+c_{13}=0$. Then we obtain the equation so that $r_{22}=r_2$, and the equation $c_{21}=0$ takes the form Thus, $R_2=r$, $r_{21}=r_1$ and $r_{22}=r_2$, hence the joints $p_0$ and $p_2$ are equidistant from all the $q_j$ and, once again, the result follows from Lemma 5.Case 4: $R_2\ne r$ and $\lambda(1-\lambda)\ne 0$. From $c_{04}=0$ we find that $\lambda=(R_1^2-r^2)/(R_2^2- r^2)$. Then the conditions $\lambda\ne 0$ and $\lambda\ne 1$ imply that $R_1\ne r$ and $R_1\ne R_2$. We find $r_{11}^2$ and $r_{12}^2$ from the equations $c_{20}=0$ and $c_{02}=0$, respectively, and substitute the result (and the expression found for $\lambda$) into the equations $c_{12}+c_{13}=0$ and $c_{21}=0$. Then we obtain $\mu r_1^2(A+B)^2=0$ and $\mu r_2^2 AB=0$, respectively, where
$$
\begin{equation*}
\begin{gathered} \, \mu=r_1^2(R_1^2-R_2^2)(R_1^2-r^2)(R_2^2-r^2)^{-2},\quad A=r^2+r_{21}^2-r_1^2-R_2^2, \\ \quad B=r_1^2+r_{22}^2-r_2^2-r_{21}^2\quad\text{and} \quad A+B=r^2+r_{22}^2-r_2^2-R_2^2. \end{gathered}
\end{equation*}
\notag
$$
Since $\mu\ne0$, we have $AB=A+B=0$, so that $A=B=0$. We plug the expression for $a$ into $c_{20}$ and $c_{02}$, and then make the substitutions $R_2^2=r^2+r_{21}^2-r_1^2$ (in $c_{20}$) and $R_2^2=r^2+r_{22}^2-r_2^2$ (in $c_{02}$). Then we obtain $r^2+r_{11}^2=r_1^2+R_1^2$ and $r^2+r_{12}^2=r_2^2+R_1^2$, respectively. These conditions, together with $A=0$ and $B=0$, span all conditions on rod lengths in Proposition 1, (a). The lemma is proved. § 5. Complexification and compactification of the curves under considerationInstead of the affine coordinates $T_i$ and $t_j$ (see § 2), it will be more convenient for us to use the projective (homogeneous) coordinates $(T_i:S_i)$ and $(t_j:s_j)$ ranging over the circles $\{r^2 T_i{\overline T}_i=R_i^2 S_i{\overline S}_i\}$ and $\{r^2 t_j{\overline t}_j=r_j^2 s_j{\overline s}_j\}$ in the complex projective line $\mathbb{CP}^1$. In this and the next sections $P_i$ and $Q_j$ denote copies of ${\mathbb{CP}}^1$ endowed with own coordinates. Accordingly, $M$, $M_i$, and $C_i$ denote the compactifications of the complexifications of the respective algebraic sets introduced in § 2. Namely, $M=\{\widehat f_{11}=\dots=\widehat f_{22}=0\}\subset P_1\times P_2\times Q$, $M_i=\{\widehat f_{i1}=\widehat f_{i2}=0\}\subset P_i\times Q$ and $C_i=\{\widehat F_i=0\}\subset Q$, where $Q=Q_1\times Q_2={\mathbb{CP}}^1\times{\mathbb{CP}}^1$,
$$
\begin{equation*}
\widehat f_{ij}(T_i,S_i;\,t_j,s_j)=S_i^2 s_j^2 f_{ij}\biggl(\frac{T_i}{S_i}, \frac{t_j}{s_j}\biggr) \quad\text{and}\quad \widehat F_i(t_1,s_1;\,t_2,s_2)=s_1^4 s_2^4 F_i\biggl(\frac{t_1}{s_1}, \frac{t_2}{s_2}\biggr).
\end{equation*}
\notag
$$
We also define the curves $C_{ij} = \{\widehat f_{ij} = 0\}\subset P_i\times Q_j$. Despite the fact that we have extended $M$, we still reserve the term $(3,3)$-framework for ‘true $(3,3)$-frameworks’ only, that is, for elements of $M$ all of whose coordinates belong to the circles $\{r^2 T_i{\overline T}_i=R_i^2 S_i{\overline S}_i\}$ and $\{r^2 t_j{\overline t}_j=r_j^2 s_j{\overline s}_j\}$; we denote the set of them (that is, ‘the old $M$’) by ${\mathbb R}M$. This is the fixed point set of the antiholomorphic involution that acts on each factor $P_i$ and $Q_j$ by
$$
\begin{equation}
(T_i:S_i)\mapsto (R_i^2{\overline S}_i : r^2{\overline T}_i),\qquad (t_j:s_j)\mapsto (r_j^2{\overline s}_j : r^2{\overline t}_j).
\end{equation}
\tag{5.1}
$$
§ 6. Consequences of the reducibility of $\widehat f_{ij}$ and $\widehat F_i$We introduce the notation as in § 5. Assume that $M$ contains a flexible nonoverlapping $(3,3)$-framework $\mathbf{p}$. In this section we find necessary conditions for the reducibility of $\widehat F_1$. Let us simplify the notation: $T=T_1$, $S=S_1$, $R=R_1$,
$$
\begin{equation*}
a_j=r_{1j}, \qquad A_0^\pm=R\pm r \quad\text{and}\quad A_j^\pm=a_j\pm r_j, \qquad j=1,2
\end{equation*}
\notag
$$
(that is, $A_j^\pm=r_{1j}\pm r_{0j}$, $j=0,1,2$). Set $D_j=\operatorname{Discr}_{t_j}(f_{1j})$. The computation shows that
$$
\begin{equation}
D_j=d_j^+ d_j^-, \quad\text{where } d_j^\pm=T^2+(R^2+r^2-(A_j^\pm)^2)T+R^2, \qquad j=1,2,
\end{equation}
\tag{6.1}
$$
and for $\Delta_j^\pm = \operatorname{Discr}_T(d_j^\pm)$ we have
$$
\begin{equation}
\Delta_j^\pm=(A_j^\pm+A_0^+)(A_j^\pm-A_0^+)(A_j^\pm+A_0^-)(A_j^\pm-A_0^-).
\end{equation}
\tag{6.2}
$$
It follows from Lemma 4 that
$$
\begin{equation}
A_j^+ \pm A_k^- \ne 0 \quad\text{and}\quad A_j^++A_k^+ \ne 0, \qquad j,k=0,1,2.
\end{equation}
\tag{6.3}
$$
Lemma 7 (proof is obvious). If two polynomials $T^2+b_k T + R^2$, $k=1,2$, have a common zero, then they coincide. Recall that a deltoid is a 4-cycle symmetric with respect to one of its diagonals, which we call in this case the axis of the deltoid. Lemma 8. The polynomial $\widehat f_{1j}$, $j=1,2$, is reducible over $\mathbb{C}$ if and only if the 4-cycle $p_0q_0p_1q_j$ is either parallelogrammatic or a deltoid.5 Proof. The reducibility in the deltoid case is obvious. For a parallelogrammatic cycle which is not a deltoid, it is also easily seen: the irreducible components correspond to parallelograms and antiparallelograms. Let us prove that there are no other cases of reducibility.
Let $\widehat f_{1j}$ be reducible. Consider first the case when $\widehat f_{1j}$ has a nonconstant divisor $\widehat f_0$ of degree zero in $t_j$. We write $\widehat f_{1j}=c_2t_j^2+c_1s_jt_j+c_0s_j^2$. Then $\widehat f_0$ divides all coefficients $c_k(S,T)$. We have $c_0=r^2_jT(S-T)$ and $c_2=S(r^2T-R^2S)$. Hence $R=r$ and $\widehat f_0=S-T$, that is, the polynomial $c_1$ must vanish identically in $T$ after the substitution $R=r$, $S=T$. Performing this substitution we obtain $c_1=(r_j^2-a_j^2)T^2$. Hence $R=r$ and $r_j=a_j$, which corresponds to a deltoid. Now consider the case when $\widehat f_{1j}$ does not have nonconstant divisors of degree zero in $t_j$. Then $\widehat f_{1j}=\widehat f_1\widehat f_2$, where $\deg_{t_j}\widehat f_k=1$, $k=1,2$. In this case the discriminant $D_j$ must be a complete square. We have $d_j^+-d_j^-=4a_jr_jT$ (see (6.1)), hence $d_j^+$ and $d_j^-$ do not coincide. This fact, combined with Lemma 7, implies that $d_j^\pm$ are also complete squares, that is, $\Delta_j^+=\Delta_j^-=0$. Then by (6.2) and (6.3), Solving these systems of equations, we obtain either $a_j=R$ and $r_j=r$ (a deltoid), or $a_j=r$ and $r_j=R$ (a parallelogram). The lemma is proved.Lemma 9. Suppose that $\widehat f_{11}$ and $\widehat f_{12}$ are irreducible. Then (a) the projection of $M_1$ onto each of the factors $P_1$, $Q_1$ and $Q_2$ is finite (that is, the preimage of each point is finite), and therefore $M_1$ is an algebraic curve; (b) the surfaces $\{\widehat f_{1j}=0\}\subset P_1\times Q$, $j=1,2$, cross transversally everywhere except for, maybe, a finite number of points. Proof. (a) We denote by $\operatorname{pr}_j:P_1\times Q\to P_1\times Q_j$, $j=1,2$, the standard projections. If $\operatorname{pr}_1^{-1}(p,q) \subset M_1$, then $\{p\}\times Q_2\subset\operatorname{pr}_2(M_1)=C_{12}$, which contradicts the irreducibility of $\widehat f_{12}$. Hence the projection of $M_1$ onto $P_1\times Q_1$ is finite. In the same way we prove the finiteness of the projections of $M_1$ onto $P_1\times Q_2$ and $Q$. The finiteness of the projection of $C_{1j}$ (and therefore of $M_1$) onto $P_1$ and $Q_j$ is immediate from the irreducibility of $\widehat f_{1j}$.
(b) Consider the affine chart $(T,t_1,t_2)$ on $P_1\times Q$ (the arguments for other affine charts are the same). In this chart $M_1$ is defined by the equations ${f_{11}=f_{12}=0}$. The gradients have the form $\nabla f_{11}=(a,b,0)$ and $\nabla f_{12}=(c,0,d)$. If these vectors are proportional, then $b=0$ or $d=0$, which means that one of the partial derivatives $\partial f_{1j}/\partial t_j$ is equal to zero. This can happen only on a finite number of lines of the form $T,t_j=\mathrm{const}$. By (a) each such line crosses $M_1$ in a finite number of points, which completes the proof. Lemma 10. If $\widehat f_{11}$ and $\widehat f_{12}$ are irreducible and $\widehat F_1$ is a nontrivial reducible polynomial which is not a power of an irreducible polynomial, then the 4-cycle $p_0q_1p_1q_2$ is either parallelogrammatic, or a deltoid with axis $p_0p_1$. Proof. Recall that $C_{1j} = \{\widehat f_{1j} = 0\}\subset P_1\times Q_j$. Let $\widetilde\pi_j\colon M_1\to C_{1j}$ and $\pi_j\colon {C_{1j}\,{\to}\, P_1}$ be the standard projections $P_1\times Q\to P_1\times Q_j\to P_1$ restricted to the corresponding curves. By hypothesis the image of $M_1$ under the projection $P_1\times Q\to Q$ is the reducible curve $C_1=\{\widehat F_1=0\}$, hence the curve $M_1$ is also reducible. Let $M'_1$ and $M''_1$ be two distinct irreducible components of $M_1$. By Lemma 9 none of them can be contracted to a point by the projections $\widetilde\pi_j$. Therefore, since these projections are two-fold (recall that the degree of $f_{ij}$ in each variable is 2), their restrictions to each component of $M_1$ are bijective. Hence the composition has the same branch points (critical values) as $\pi_2$. Since $\eta=\pi_1$, we conclude that $\pi_1$ and $\pi_2$ have the same branch points.
The branch points of $\pi_j$ are the zeros of $D_j$ of odd multiplicity (see (6.1)), hence $D_1D_2$ is a complete square. Since $\pi_j$ is a two-fold projection of the irreducible curve $C_{1j}$, each of $\pi_1$ and $\pi_2$ has branch points. Then $D_1$ and $D_2$ have a common root. Hence, by Lemma 7 one of $d_1^\pm$ coincides with one of $d_2^\pm$. Note that $d_1^+ - d_2^- = (A_2^- + A_1^+)(A_2^- - A_1^+)T$, so that $d_1^+\not\equiv d_2^-$ by (6.3). Similarly, $d_1^-\not\equiv d_2^+$. Hence one of the following cases takes place. Case 1: $d_1^+\equiv d_2^+$ and $d_1^-\equiv d_2^-$. Since $d_1^\pm - d_2^\pm = (A_2^\pm + A_1^\pm)(A_2^\pm - A_1^\pm)T$, we derive from (6.3) that
$$
\begin{equation}
A_2^+-A_1^+=A_2^--A_1^-=0 \quad\text{or}\quad A_2^+-A_1^+=A_2^-+A_1^-=0.
\end{equation}
\tag{6.5}
$$
By solving these systems of equations we obtain either $a_1=r_2$ and $a_2=r_1$ (a parallelogram), or $a_1=a_2$ and $r_1=r_2$ (a deltoid with axis $p_0p_1$).
Case 2: $d_1^-\equiv d_2^-$ and $\Delta_1^+=\Delta_2^+=0$. Due to (6.2) and (6.3), the second condition yields $A_1^+ - A_0^+ = A_2^+ - A_0^+ = 0$. Eliminating $A_0^+$ and factorizing $d_1^- - d_2^-$ (as in Case 1) we obtain (6.5) again. Case 3: $d_1^+\equiv d_2^+$ and $\Delta_1^-=\Delta_2^-=0$. By (6.2) and (6.3) the second condition yields
$$
\begin{equation}
(A_1^--A_0^-)(A_1^-+A_0^-)=(A_2^--A_0^-)(A_2^-+A_0^-)=0,
\end{equation}
\tag{6.6}
$$
which is equivalent to four systems of linear equations. Eliminating $A_0^-$ from each of them and combining the result with the equation $A_2^+ - A_1^+=0$ (which follows from $d_1^+\equiv d_2^+$), each time we obtain one of the systems of equations in (6.5).
The lemma is proved. Lemma 11. Suppose that $\widehat f_{11}$ and $\widehat f_{12}$ are irreducible and $\widehat F_1=F^m$, $m\geqslant 1$, where $F$ is either identically equal to zero or is an irreducible polynomial. Then $\mathbf{p}$ is a Dixon mechanism of the first kind.6 Proof. If $F=0$, then this is a particular case ($\lambda=0$) of Lemma 6, so let $F\ne 0$. If $m=1$ (that is, $\widehat F_1$ is irreducible), then, since $\widehat F_1$ and $\widehat F_2$ are bihomogeneous polynomials of the same bidegree which have a common divisor, the result follows from Lemma 6 again.
Let $m\geqslant 2$. Let us prove that the projection $\pi\colon M_1\to C_1$ is two-fold in this case. Suppose that $C_1$ contains a smooth point $q$ with a single preimage. Let $\gamma\colon ({\mathbb C},0)\to(Q,q)$ be a holomorphic germ transverse to $C_1$. By Lemma 9 we may assume that the surfaces $\widehat f_{1j}=0$ are smooth and cross transversally over $q$. Using the expression for the resultant of two polynomials in terms of their roots (see, for example, [4], Ch. 12, (1.3)) one can easily derive that $F_1(\gamma(t))$ has a first-order zero at $t=0$. This fact contradicts the condition $m\geqslant 2$, hence the projection $\pi$ cannot be one-fold. Since $\deg_T\widehat f_{ij}=2$, we conclude that it is two-fold. Thus almost all points of $C_1$ have two preimages in $M_1$. Since $\mathbf{p}$ is flexible, we may then assume that $\pi^{-1}(q_1,q_2)=\{(p_1,q_1,q_2),(p'_1,q_1,q_2)\}$, $p'_1\ne p_1$. This set itself and one of its elements are invariant under the antiholomorphic involution (5.1), hence the other element is invariant too. Therefore, ${(p'_1,p_2;\,q_1,q_2)\in{\mathbb R}M}$. Moreover, all this remains true during a deformation of $\mathbf{p}$. Hence the $(4,3)$-framework $(p_0,p_1,p_2,p'_1;\,q_0,q_1,q_2)$ is flexible. Its joints $p_1$ and $p'_1$ are equidistant from all the $q_j$. With the help of Lemma 5 it is easy to derive from this fact that $\mathbf{p}$ is a Dixon mechanism of the first kind. The lemma is proved. Recall our assumption that $M$ contains a flexible nonoverlapping $(3,3)$-framework $\mathbf{p}$. We say that a cycle in $\mathbf{p}$ is fastened, if it contains the edge $p_0q_0$. One can summarize Lemmas 8, 10 and 11 as follows. Lemma 12 (main lemma). If $\mathbf{p}$ is not a Dixon mechanism of the first kind, then the $(2,3)$-framework $(p_0,p_1;\,q_0,q_1,q_2)$ contains either a parallelogrammatic cycle, or a fastened deltoid, or a not fastened deltoid with axis $p_0p_1$. § 7. Completing the proof of Theorem 1Let $\mathbf{p}$ be a flexible nonoverlapping $(3,3)$-framework that is not a Dixon mechanism of the first kind. We show that $\mathbf{p}$ is a Dixon mechanism of the second kind. Proof. Suppose that $\mathbf{p}$ contains a deltoid $\Delta$ that is not a rhombus. We renumber the joints so that $\Delta=p_0q_1p_1q_2$ and $|p_0q_1|=|p_1q_1|\ne|p_0q_2|=|p_1q_2|$ (see Figure 4, a). By Lemma 12 the $(2,3)$-framework $(p_0,p_1;\,q_0,q_1,q_2)$ must contain a 4-cycle $\Delta'$ realizing one of the following cases. In each of them (except the last one) we show that $p_0$ and $p_1$ are equidistant from $q_0$, which contradicts Lemma 5.
Case 1: a parallelogrammatic cycle. Then $\Delta'$ contains both $p_0$, $p_1$, and also at least one of the $q_i$, $i=1, 2$. Since $|p_0q_i|=|p_1q_i|$, we conclude that $\Delta'$ is a rhombus. But $\Delta'\ne\Delta$ (since $\Delta$ is not a rhombus), hence $q_0\in\Delta'$. Therefore, $p_0$ and $p_1$ are equidistant from $q_0$. Case 2: a fastened deltoid with axis $p_0p_1$. We may assume that $\Delta'=p_0q_0p_1q_1$, $|p_0q_0|=|p_0q_1|$ and $|p_1q_1|=|p_1q_0|$. Then $|p_0q_0|=|p_0q_1|=|p_1q_1|=|p_1q_0|$. Case 3: a fastened deltoid with axis $q_0q_j$. By definition $|p_0q_0|=|p_1q_0|$. Case 4: a not fastened deltoid with axis $p_0p_1$. Then $\Delta'=\Delta$ and this is a deltoid with two axes, that is, a rhombus. This is a contradiction. The lemma is proved. Lemma 14. $\mathbf{p}$ cannot contain two distinct parallelogrammatic cycles with three common vertices. Proof. Suppose that $\mathbf{p}$ contains two distinct parallelogrammatic cycles $\Pi_1$ and $\Pi_2$ with three common vertices. Up to renumbering we may assume that these are $q_0p_0q_1p_1$ and $p_0q_1p_1q_2$ (see Figure 4, b). Then $q_0p_0q_2p_1$ is a deltoid. By Lemma 13 it must be a rhombus. Hence $\Pi_1$ and $\Pi_2$ are rhombi as well. It is easy to check that this is impossible. The lemma is proved. Lemmas 12 and 13 imply that each $(2,3)$-framework obtained from $\mathbf{p}$ by the removal of one joint contains a parallelogrammatic 4-cycle. Using Lemma 14 it is easy to derive from this fact that the joints of $\mathbf{p}$ can be numbered so that the three 4-cycles $\Pi_{ij}=p_iq_ip_jq_j$, $i<j$, become parallelogrammatic. This means that one can denote the lengths of the rods by $a$, $b$, $c$ and $d$ as in Proposition 1, (b). It remains to prove that the relation $a^2+c^2=b^2+d^2$ holds up to renumbering the joints. In the notation of § 2 we have
$$
\begin{equation*}
r=r_{11}=r_{22}=a, \qquad R_1=r_1=b, \qquad R_2=r_2=c\quad\text{and} \quad r_{12}=r_{21}=d.
\end{equation*}
\notag
$$
Making these substitutions we express the coefficients of $F_1$ and $F_2$ as polynomials in $a$, $b$, $c$ and $d$. By Lemma 3 the resultant of $F_1$ and $F_2$ with respect to $t_1$ vanishes identically. Hence the resultant of $F_1(t_1,-c/a)$ and $F_2(t_1,-c/a)$ is zero. A computation shows that it is equal to
$$
\begin{equation}
16\, b^8 c^{16} (a+c)^8 (a^2+b^2-c^2-d^2)^4 (a^2+d^2-b^2-c^2)^4 (a^2+c^2-b^2-d^2)^4,
\end{equation}
\tag{7.1}
$$
which completes the proof of Theorem 1.
§ 8. Flexibility of hyperbolic bipartite frameworksLet $H^2$ be the standard hyperbolic plane, that is, a complete simply connected Riemannian 2-manifold of constant curvature $-1$. We denote the distance in $H^2$ by $d_H(\,{\cdot}\,{,}\,{\cdot}\,)$. The flexibility condition (D1) extends without changes to the hyperbolic case. Condition (D2) admits the following equivalent reformulation, which also extends to the hyperbolic case. (D2) There are two orthogonal lines and two quadrilaterals symmetric with respect to each of them and with vertices not belonging to them such that $p_1,\dots,p_m$ are at the vertices of one quadrilateral and $q_1,\dots,q_n$ are at the vertices of the other. Theorem 2. Theorem 1 holds for $H^2$. The proof of Theorem 2 is almost the same as for Theorem 1. In this section we just explain which elements of the proof (mostly, formulae) should be modified. 8.1. Lobachevsky coordinates in $H^2$. The hyperbolic version of §§ 1 and 3It is obvious that Lemmas 1 and 4 are valid for $H^2$. For other facts from §§ 1 and 3 it is convenient to use the following hyperbolic analogue of the Cartesian coordinate system, which is called a Lobachevsky coordinate system. Fix an oriented line $\ell$ and a point $O\in\ell$. Then the coordinates $(x,y)$ of a point $p$ are $x=\pm d_H(O,q)$ and $y=\pm d_H(p,q)$, where $q\in\ell$ is such that $pq\perp\ell$ and the signs are chosen according to the quadrant containing $p$. In these coordinates we have
$$
\begin{equation}
\cosh d_H\bigl((x_1,y_1),(x_2,y_2)\bigr) =\cosh y_1\cosh y_2\cosh(x_2-x_1)-\sinh y_1\sinh y_2.
\end{equation}
\tag{8.1}
$$
The following is a hyperbolic analogue of Lemma 2. Lemma 15. The diagonals of a (maybe, self-crossing) quadrilateral are orthogonal if and only if $\cosh a \cosh c=\cosh b \cosh d$ where $a$, $b$, $c$ and $d$ are the lengths of its consecutive sides. Proof. Consider a quadrilateral $p_1p_2p_3p_4$ with $d_H(p_1,p_2)=a$, $d_H(p_2,p_3)=b$, $d_H(p_3,p_4)=c$ and $d_H(p_4,p_1)=d$. We introduce a Lobachevsky coordinate system with $x$-axis $p_1p_3$. Let $(x_k,y_k)$ be the coordinates of $p_k$ (then $y_1=y_3=0$). By (8.1) we have so that we have the following identity, which implies the result: The lemma is proved. For the sake of coherence with the Euclidean case, we still say that a $4$-cycle is parallelogrammatic if opposite sides have equal lengths (though parallelism no longer plays any role). We call it an antiparallelogram (a parallelogram) if it is either degenerate, that is, all of its vertices are collinear, or otherwise, if it is (respectively, is not) self-crossing. The following is a hyperbolic analogue of Proposition 1, and the proof is also similar. Proposition 2. Let $\mathbf{p}=(p_0,\dots,p_{m-1};\,q_0,\dots,q_{n-1})$ be a nonoverlapping $(m,n)$-framework in $H^2$. Set $u_{ij}=\cosh d_H(p_i,q_j)$. (a) $\mathbf{p}$ satisfies (D1) if and only if, for each cycle $p_iq_jp_kq_l$, one has $u_{ij}u_{kl}=u_{il}u_{jk}$. As in Proposition 1, these conditions for cycles with fixed $i$ and $j$ generate all the others. (b) If $\mathbf{p}$ is flexible and $m=n=3$, then $\mathbf{p}$ satisfies (D2) if and only if, up to renumbering, one has $u_{00}=u_{11}=u_{22}$, $u_{01}=u_{10}$, $u_{12}=u_{21}$, $u_{20}=u_{02}$ and $u_{00}+u_{02} = u_{01} + u_{12}$. Proof. (a) This immediately follows from Lemma 15.
(b) The condition on the lengths is derived from (D2) by a direct computation in Lobachevsky coordinates. Let us prove the reverse implication. Let $\mathbf{p}$ be flexible and satisfy the condition on the lengths. Consider a smooth deformation $\mathbf{p}=\mathbf{p}(t)$ with constant $u_{ij}$s. The cycles $\Pi_{ij}=p_iq_ip_jq_j$ are parallelogrammatic. Suppose that $\Pi_{01}$ and $\Pi_{12}$ are parallelograms. We choose Lobachevsky coordinates so that the $x$-axis is the line passing through the centres of symmetry of $\Pi_{01}$ and $\Pi_{12}$ (we may assume that this condition is fulfilled for each $t$). Then the composition of these central symmetries is a shift $(x,y)\mapsto(x+a,y)$ such that $p_0\mapsto p_2$ and $q_0\mapsto q_2$. Since $u_{02}=u_{20}$, this fact, combined with (8.1), implies that $p_0$ and $q_0$ (as well as $p_2$ and $q_2$) have equal $x$-coordinates. Hence $p_k=(x_k,(-1)^k y_p)$ and $q_k=(x_k,(-1)^k y_q)$, $k=0,1,2$. By a shift of the $x$-coordinate we can achieve that $x_1(t)=0$ for each $t$. Then by (8.1) we have
$$
\begin{equation*}
\begin{gathered} \, u_{00}=\cosh(y_p-y_q), \\ u_{02}-u_{00}=\cosh y_p\cosh y_q(\cosh(x_2-x_0)-1), \\ u_{01}+u_{00}=\cosh y_p\cosh y_q(\cosh x_0+1) \end{gathered}
\end{equation*}
\notag
$$
and
Differentiating these identities with respect to $t$ we obtain four linear homogeneous equations for $x'_0$, $x'_2$, $y'_p$ and $y'_q$ (cf. the proof of Lemma 5). The determinant is equal to
$$
\begin{equation*}
(1+\cosh x_0)(1+\cosh x_2)(\cosh y_p\cosh y_q)^2 (1-\cosh(x_2-x_0)) \sinh(y_p+y_q)\sinh(y_p-y_q).
\end{equation*}
\notag
$$
It vanishes only when $y_p+y_q=0$ (since $\mathbf{p}$ is nonoverlapping), which means that $\mathbf{p}$ is symmetric with respect to the $x$-axis. However, this condition cannot be kept during a nonidentity deformation.
The contradiction obtained shows that $\Pi_{01}$ or $\Pi_{12}$ is an antiparallelogram. Let it be $\Pi_{01}$ (the case of $\Pi_{12}$ is analogous). Then we can choose Lobachevsky coordinates so that $p_0=(x_p,y_p)$, $q_0=(x_q,y_q)$, $p_1=(x_p,-y_p)$ and $q_1=(x_q,-y_q)$. Shifting the $x$-coordinates we can achieve that $p_2=(-x_p,-y)$ for some $y\in\mathbb R$. Then by (8.1) we have
$$
\begin{equation*}
u_{00}+u_{02}-u_{01}-u_{12}=2(\sinh y-\sinh y_p)\sinh y_q,
\end{equation*}
\notag
$$
so that $p_2=(-x_p,-y_p)$. Then $q_2=(-x_q,-y_q)$ because $q_2$ is uniquely determined by its distances to the three noncollinear points $p_0$, $p_1$ and $p_2$.
The lemma is proved. Using Lobachevsky coordinates, the proof of Lemma 5 can be repeated word-for-word in the hyperbolic setting but identities (3.1) should be replaced by
$$
\begin{equation*}
\frac{\cosh x_j}{\cosh x_0}=\frac{\cosh r_j}{\cosh r_0}, \quad \frac{\cosh(x_j-a)}{\cosh(x_0-a)}=\frac{\cosh R_j}{\cosh R_0}, \qquad j=1,2,
\end{equation*}
\notag
$$
and then the determinant of the linear system for $x'_0$, $x'_1$, $x'_2$ and $a'$ becomes
$$
\begin{equation*}
\frac{\sinh a\sinh(x_0-x_1)\sinh(x_0-x_2)\sinh(x_1-x_2)}{\cosh x_0\cosh x_1\cosh x_2\cosh(x_0-a) \cosh(x_1-a)\cosh(x_2-a)}.
\end{equation*}
\notag
$$
8.2. The Poincaré model of $H^2$. The hyperbolic version of §§ 2 and 4–7In this subsection we use the Poincaré model of $H^2$ in the unit disc $\mathbb D\subset\mathbb C$, where the geodesics are circles orthogonal to $\partial\mathbb D$ and the distance is
$$
\begin{equation}
\cosh d_H(p,q)=1+\frac{2(p-q)(\overline p-\overline q)}{(1-p\overline p)(1-q\overline q)};
\end{equation}
\tag{8.2}
$$
in particular, the $d_H$-circle of radius $r$ centred at $0$ is the $\mathbb C$-circle $\{|z|=l\}$, where $u=\cosh r$ and $l=\rho_H(u)$, and the function $\rho_H\colon[1,+\infty)\mapsto[0,1)$ is defined by $\rho_H(u)=\sqrt{(u-1)/(u+1)}$. We still denote the rod lengths by $r_{ij}=d_H(p_i,q_j)$, $R_i=r_{i0}$, $r_j=r_{0j}$ and $r=r_{00}$. We also set
$$
\begin{equation}
\begin{gathered} \, u_{ij}=\cosh r_{ij}, \qquad U_i=\cosh R_i, \qquad u_j=\cosh r_j, \qquad u=\cosh r, \\ l_{ij}=\rho_H(u_{ij}), \qquad L_i=\rho_H(U_i), \qquad l_j=\rho_H(u_j), \qquad l=\rho_H(u). \end{gathered}
\end{equation}
\tag{8.3}
$$
Let $q_0=0$ and $p_0=l$ (then $d_H(p_0,q_0)=r$). For the circles
$$
\begin{equation*}
P_k=\{p_k\in\mathbb D\mid d_H(q_0,p_k)=R_k\}, \quad Q_k=\{q_k\in\mathbb D\mid d_H(p_0,q_k)=r_k\}, \qquad k=1,2,
\end{equation*}
\notag
$$
we choose the parametrizations $p_i(T_i) = l T_i$ and $q_j(t_j) = (l+lt_j)/(l^2t_j+1)$, where the parameters $T_i$ and $t_j$ range over the circles $|T_i|=L_i/l$ and $|t_j|=l_j/l$, respectively. In order to check that $t_j\mapsto q_j(t_j)$ parametrizes $Q_j$, observe that $Q_j$ is the image of the circle
$$
\begin{equation*}
Q_j^*=\{q_j^*\in\mathbb D\mid d_H(q_0,q_j^*)=r_j\} =\{|z|=l_j\}
\end{equation*}
\notag
$$
under the mapping $z\mapsto(l+z)/(lz+1)$, which is a conformal isomorphism of $\mathbb D$ taking $0$ to $l$ (that is, taking $q_0$ to $p_0$). We define the algebraic sets $M$, $M_i$, $C_i$ and $C_{ij}$ as in the Euclidean case. Then the curve $C_{ij}$ has the defining equation $f_{ij}(T_i,t_j)=0$ where $f_{ij}$ is the numerator of the rational function in $T_i$ and $t_j$ obtained from $d_H(p_i(T_i),q_j(t_j))-u_{ij}$ by applying (8.2) and making the substitutions $\overline T_i=L_i^2/(l^2T_i)$ and $\overline t_j=l_j^2/(l^2t_j)$. So we can define $f_{ij}$ by setting
$$
\begin{equation*}
\frac{f_{ij}(T_i,t_j)}{4(u+1)T_it_j} = 1+\frac{2(lT_i-q_j(t_j)) ({L_i^2}/({lT_i})-q_j({l_j^2}/({l^2t_j})))} {(1-L_i^2)(1- q_j(t_j)q_j({l_j^2}/({l^2t_j})))}-u_{ij}
\end{equation*}
\notag
$$
($f_{ij}$ is invariant under the substitution $T_i\leftrightarrow-t_j$, $L_i\leftrightarrow l_j$, though this is not immediately clear in this formula). We see that $f_{ij}$ is a polynomial in $T_i$ and $t_j$ of degree 2 in each variable; its coefficients are rational functions of $l^2$, $L_i^2$, $l_j^2$, $u$ and $u_{ij}$. By the substitution $l=\rho_H(u)$, $L_i=\rho_H(U_i)$ and $l_j=\rho_H(u_j)$ we express $f_{ij}$ as a sum of 72 monomials in $T_i$, $t_j$, $u$, $U_i$, $u_j$ and $u_{ij}$, $i,j=1,2$. We set
$$
\begin{equation*}
F_i(t_1,t_2)=\frac{\operatorname{Res}_{T_i}(f_{i1},f_{i2})}{16(1+u)^4(1-U_i^2)} .
\end{equation*}
\notag
$$
It is a sum of 445 monomials in $t_1$, $t_2$ and all the $u_{ij}$. As in § 2, $\deg_{t_j}F_i=4$ for all $i$ and $j$. Below we use the notation $A\doteq B$ to say that $A=n\mu B$ where $n\in\mathbb Q$ and $\mu$ is a product of some factors of the form $(u_{ij}\pm 1)^{\pm1}$, $i,j=0,1,2$. Proof of Lemma 6 in the hyperbolic setting. Let $c_{kl}$ be the coefficient of $t_1^k t_2^l$ in $F_1-\lambda F_2$. We have
$$
\begin{equation*}
\begin{gathered} \, c_{04} \doteq U_1^2-u^2-\lambda U_2^2+\lambda u^2, \\ c_{20}\doteq u_1^2(\lambda-1)-\lambda u_{21}^2+u_{11}^2 \quad\text{and}\quad c_{02} \doteq u_2^2(\lambda-1)-\lambda u_{22}^2+u_{12}^2; \end{gathered}
\end{equation*}
\notag
$$
thus, if $\lambda(1-\lambda)=0$, then the arguments as in the proof of Lemma 6 yield the result. Assume that $\lambda(1-\lambda)\ne0$. Let $\Lambda=\mathbb Q[\lambda,u_{ij}]_{i,j=0,1,2}$ be the ring of polynomials in $\lambda$ and all the $u_{ij}$. The coefficients $c_{kl}$ are represented by elements of $\Lambda$. Let $e_{kl}$ be obtained from $c_{kl}$ by factorizing it in $\Lambda$ and discarding all factors of the form $u_{ij}\pm 1$. We are going to show that any real solution of the system of equations $c_{kl}=0$, $k,l=0,\dots,4$, such that $u_{ij}>1$ and $\lambda(1-\lambda)\ne0$ is a solution of the system of equations $b_{ij}=0$, $i,j=1,2$, where $b_{ij} = u_{00}u_{ij}-u_{i0}u_{0j}$. To do this it is enough to show that the ideal in $\Lambda[w_0,\dots,w_4]$ contains $1$. This fact can be checked by computing the Gröbner basis (which can be done very rapidly in this case using a computer). The lemma is proved. In the proof of Lemma 8, in the case when $\widehat f_{1j}$ has a nonconstant divisor $\widehat f_0$ of degree zero in $t_j$, we have $\operatorname{Res}_{\,T}(c_0,c_2)\doteq(U_1^2-u^2)S^4$. Hence $U_1=u$, which gives
$$
\begin{equation}
c_0\doteq(S-T) ((1-u)S+(1+u)T ) \quad\text{and}\quad c_2\doteq(S-T) ((1+u)S+(1-u)T ).
\end{equation}
\tag{8.4}
$$
Thus, $\widehat f_0=S-T$, and after the substitution $S=T$, $U_1=u$ we obtain $c_1\doteq(u_1-u_{1j})T^2$. The rest of § 6 is repeated word-for-word using the following equalities, where (as in § 6) we set $A_j^\pm=r_{1j}\pm r_{0j}$, $j=0,1,2$, and use the notation ${\mathfrak s}(x)$ for $\sinh(x/2)$:
$$
\begin{equation}
d_j^\pm \doteq (u-1)(U_1+1)T^2+2\bigl(u_j u_{1j}-u U_1 \pm{\mathfrak s}(2r_j){\mathfrak s}(2r_{1j})\bigr)T+(u+1)(U_1-1),
\end{equation}
\tag{8.5}
$$
$$
\begin{equation}
{\Delta_j^\pm} \doteq {\mathfrak s}(A_j^\pm+A_0^+)\,{\mathfrak s}(A_j^\pm-A_0^+)\, {\mathfrak s}(A_j^\pm+A_0^-)\,{\mathfrak s}(A_j^\pm-A_0^-),
\end{equation}
\tag{8.6}
$$
$$
\begin{equation}
d_2^{\pm_2}-d_1^{\pm_1}\doteq{\mathfrak s}(A_2^{\pm_2}+A_1^{\pm_1})\, {\mathfrak s}(A_2^{\pm_2}-A_1^{\pm_1})\,T
\end{equation}
\tag{8.7}
$$
(here $\pm_1$ and $\pm_2$ are independent signs). The hyperbolic version of the computation at the end of § 7 is as follows: if
$$
\begin{equation*}
u_{11}=u_{22}=u, \qquad U_1=u_1, \qquad U_2=u_2 \quad\text{and}\quad u_{12}=u_{21},
\end{equation*}
\notag
$$
then the resultant of $lF_1(t_1,\pm l_2/l)$ and $lF_2(t_1,\pm l_2/l)$ with respect to $t_1$ is equal to
$$
\begin{equation}
\begin{aligned} \, \notag &(l\pm l_2)^8(ll_2\pm\varepsilon)^8 (u+1)^{16}(u_1^2-1)^4(u_2-1)^8(u+u_1+u_2+u_{12})^4 \\ &\qquad\qquad \times(u+u_1-u_2-u_{12})^4(u+u_2-u_1-u_{12})^4(u+u_{12}-u_1-u_2)^4 \end{aligned}
\end{equation}
\tag{8.8}
$$
for $\varepsilon=1$ (here it is sufficient to take ‘$+$’ as ‘$\pm$’, but both signs are needed at the end of § 9.4).
§ 9. Flexibility of spherical bipartite frameworksSpherical $(m,n)$-frameworks and their flexibility are defined as in the planar case but the points $p_i$ and $q_j$ are chosen on the unit sphere ${\{x^2+y^2+z^2=1\}\subset{\mathbb R}^3}$, so that $p_i\ne\pm q_j$ for any $i,j$. We say that a spherical $(m,n)$-framework is $\mathbb{P}^2$-nonoverlapping if $p_i\ne\pm p_j$ and $q_i\ne\pm q_j$ for $i\ne j$. The flexibility conditions (D1) and (D2) repeat themselves almost word-for-word in the spherical case (cf. [11], § 6). They can be formulated as follows. (SD1) $p_1,\dots,p_n$ lie on one plane, $q_1,\dots,q_m$ lie on another plane, and these planes are orthogonal to each other and pass through the origin. (SD2) There are two orthogonal planes passing through the origin and two rectangles symmetric with respect to each of them and with vertices not belonging to them such that $p_1,\dots,p_m$ are at vertices of one rectangle and $q_1,\dots,q_n$ are at vertices of the other. For $m=n=3$ the following spherical analogue of Theorem 1 was proved in [3]. Theorem 3. Let $\min(m,n)\geqslant 3$. Let $\mathbf{p}$ be a $\mathbb{P}^2$-nonoverlapping spherical $(m,n)$-framework. Then $\mathbf{p}$ is flexible if and only if it satisfies either (SD1) or one of the following conditions: (PD2) $\mathbf{p}$ satisfies (SD2) after applying the antipodal involution to some joints; (CDA) $\langle p_1,q_1\rangle=\langle q_1,p_2\rangle =\langle p_2,q_2\rangle=-\langle q_2,p_1\rangle$ and $\langle p_0,q_k\rangle=\langle q_0,p_k\rangle=0$, $k=1,2$, where $m=n=3$, $\mathbf{p}=(p_0,p_1,p_2;\,q_0,q_1,q_2)$, and $\langle\,\cdot\,{,}\,\cdot\,\rangle$ is the scalar product in ${\mathbb R}^3$. The paradoxical motion of $\mathbf{p}$ in case (CDA) was called a constant diagonal angle motion in [3]. The proof of Theorem 3 under the assumption that it holds for $m=n=3$ is almost the same as that of the reduction of Theorem 1 to its case $m=n=3$ (see § 1), except that Lemmas 16 and 17 should be taken into account. Following [3], we say that points on a sphere are cocircular if they lie on a geodesic circle. Lemma 16. If a $\mathbb{P}^2$-nonoverlapping spherical $(3,3)$-framework satisfies (PD2) or (CDA), then in neither part the points are cocircular. Proof. The case of (PD2) is obvious. Suppose that $\mathbf{p}$ satisfies (CDA) but $p_0$, $p_1$ and $p_2$ are cocircular. Then we can choose coordinates so that $p_0=(1,0,0)$, $p_1=(x_1,y_1,0)$ and $p_2=(x_2,y_2,0)$. Then $\langle p_0,q_1\rangle=\langle p_0,q_2\rangle=0$ implies that $q_1=(0,y_3,z_3)$ and $q_2=(0,y_4,z_4)$, while $\langle q_0,p_1\rangle=\langle q_0,p_2\rangle=0$ implies that $q_0=(0,0,\pm1)$, and we may assume that $q_0=(0,0,1)$. The conditions on $\langle p_i,q_j\rangle$, $j=1,2$, read $y_1y_3=y_2y_3=y_2y_4=-y_1y_4$, hence $(y_1-y_2)y_3=(y_1+y_2)y_4=0$, that is, either $y_3y_4=0$ or $y_1=y_2=0$. If $y_3y_4=0$, then $q_0=\pm q_1$ or $q_0=\pm q_2$. If $y_1=y_2=0$, then $p_0=\pm p_1$. Both cases are impossible for $\mathbb{P}^2$-nonoverlapping frameworks. The lemma is proved. Lemma 17. If a $\mathbb{P}^2$-nonoverlapping spherical $(3,3)$-framework $\mathbf{p}$ satisfies (CDA) and a $\mathbb{P}^2$-nonoverlapping framework $\mathbf{p}'$ is obtained from $\mathbf{p}$ by replacing some $q_i$ by $q'_i\ne\pm q_i$, then $\mathbf{p}'$ does not satisfy any of the conditions (SD1), (PD2) or (CDA). Proof. $\mathbf{p}'$ does not satisfy (SD1) by Lemma 16. It does not satisfy (CDA) because any five joints of a framework satisfying (CDA) determine the sixth uniquely up to the antipodal involution. Let us show that $\mathbf{p}'$ does not satisfy (PD2). Suppose it does. Condition (CDA) is invariant under applying the antipodal involution to any joint. Hence we may assume that $\mathbf{p}'$ satisfies (SD2) while $\mathbf{p}$ still satisfies (CDA). Then one can choose coordinates so that each part of $\mathbf{p}'$ sits at the vertices of a rectangle invariant under the reflections $\xi\colon(x,y,z)\mapsto(-x,y,z)$ and $\eta\colon(x,y,z)\mapsto(x,-y,z)$.
If $q_i=q_0$, then $q_2$ is the image of $q_1$ under $\xi$, $\eta$ or $\xi\eta$. Then the condition $\langle p_0q_1\rangle=\langle p_0q_2\rangle=0$ implies that $p_0$ belongs to $\{y=0\}$, $\{x=0\}$ or $\{z=0\}$, respectively (see Figure 5). This contradicts the conditions that $\mathbf{p}$ is $\mathbb{P}^2$-nonoverlapping.  Figure 5.The projection onto the $xy$-plane in the proof of Lemma 17: (a) ${q_2=\xi(q_1)}$; (b) $q_2=\eta(q_1)$; (c) $q_2=\xi\eta(q_1)$. If $q_i\ne q_0$, then the arguments are the same but involve $q_0$, $p_1$ and $p_2$ instead of $p_0$, $q_1$ and $q_2$. The lemma is proved. Remark 5. Examples as in Remark 3 can also be constructed in the spherical case. Below we give a proof of Theorem 3 which is an adaptation of the proof of Theorem 2. All computations are exactly the same (just with $\cosh x$ and $\sinh x$ replaced by $\cos x$ and $\sqrt{-1}\sin x$). However there are more cases to consider because of the antipodal involution, which can be applied to any joint. 9.1. Geographic coordinates. The spherical version of § 8.1We define the distance $d_S$ on $S^2\subset\mathbb R^3$ as the length of the shortest geodesic: $d_S(p,q)=\arccos\langle p,q\rangle$. A Lobachevsky coordinate system in $H^2$ is the hyperbolic analogue of the usual geographic coordinates on the unit sphere: $x$ (the longitude) and $y\in[-\pi/2,\pi/2]$ (the latitude). So $(x,y)$ are the geographic coordinates of the point $(\cos x\cos y,\,\sin x\cos y,\sin y)$. In these coordinates
$$
\begin{equation}
\cos d_S\bigl((x_1,y_1),(x_2,y_2)\bigr) =\cos y_1\cos y_2 \cos(x_2-x_1)+\sin y_1\sin y_2.
\end{equation}
\tag{9.1}
$$
Almost everything in § 8.1 becomes true if one replaces $d_H$, $\cosh$, $\sinh$, ‘Lobachevsky coordinates’, ‘collinear’ and ‘nonoverlapping’ by $d_S$, $\cos$, $\sqrt{-1}\sin$, ‘geographic coordinates’, ‘cocircular’ and ‘$\mathbb P^2$-nonoverlapping’, respectively (for example, compare (8.1) with (9.1)). The only difference is as follows. Remark 6. In Proposition 2, (a), for $S^2$ it is wrong in general that the conditions $u_{ik}u_{jl}=u_{il}u_{jk}$ with fixed $i$ and $j$ generate all the other conditions (for example, when $p_i$ is at the north pole and all the other joints are on the equator). However, this is true when $u_{ij}\ne0$. 9.2. The stereographic projection onto $ {\mathbb C}$. The spherical version of § 8.2While Lobachevsky coordinate system is an analogue of geographic coordinates, the Poincaré model is an analogue of the stereographic projection $S^2\to\mathbb C\cup\{\infty\}$ (in fact, the Poincaré model is the stereographic projection of a hyperboloid in $\mathbb R^3$ endowed with the Minkowski $(2,1)$-distance). The stereographic projection identifies $(x,y,z)\in S^2$ with $(x+y\sqrt{-1}\,)/(1-z)\in\mathbb C\cup\{\infty\}$. Under this identification we have (cf. (8.2))
$$
\begin{equation}
\cos d_S(p,q)=1-\frac{2(p-q)(\overline{p}-\overline{q})} {(1+p\overline{p})(1+q\overline{q})};
\end{equation}
\tag{9.2}
$$
in particular, the $d_S$-circle of radius $r$ centred at $0$ is the $\mathbb C$-circle $\{|z| = l\}$, where $u = \cos r$ and $l = \rho_S(u)$ and the function $\rho_S\colon [-1,1]\to[0,+\infty]$ is defined by $\rho_S(u) = \sqrt{(1-u)/(1+u)}$. As in § 8.2, we set $r_{ij}=d_S(p_i,q_j)$, $R_i=r_{i0}$, $r_j=r_{0j}$ and $r=r_{00}$, and we also set
$$
\begin{equation}
\begin{gathered} \, u_{ij}=\cos r_{ij}, \qquad U_i=\cos R_i, \qquad u_j=\cos r_j, \qquad u=\cos r, \\ l_{ij}=\rho_S(u_{ij}), \qquad L_i=\rho_S(U_i), \qquad l_j=\rho_S(u_j), \qquad l=\rho_S(u) \end{gathered}
\end{equation}
\tag{9.3}
$$
(cf. (8.3)). We define the circles $P_i$, $Q_j$, their parametrizations and the polynomials $f_{ij}$ and $F_i$ by the same formulae as in § 8.2 but use $d_S$ in place of $d_H$ and set $q_j(t_j) = (l+lt_j)/(1-l^2_j)$. It turns out that the expressions for $f_{ij}$ and $F_i$ in terms of $u_{ij}$ are exactly the same as in § 8.2. In particular, equalities (8.4)–(8.7) for ${\mathfrak s}(x)=\sqrt{-1}\,\sin(x/2)$ and (8.8) for $\varepsilon=-1$ hold for spherical frameworks. Lemma 18 (cf. Lemma 6). If $u\ne 0$, $\mathbf{p}$ is $\mathbb P^2$-nonoverlapping and $F_1=\lambda F_2$, then $\mathbf{p}$ satisfies (SD1). Proof. The hyperbolic proof of the case $\lambda(1-\lambda)\ne0$ of Lemma 6 (see § 8.2) goes without any change in the spherical setting in view of the assumption $u\ne 0$ (see Remark 6).
The proof of Lemma 6 in the case when $\lambda(1-\lambda)=0$ does not extend to the sphere directly because $u_{ij}$ can be negative, but one can use the same arguments as when $\lambda(1-\lambda)\ne0$. Namely, the computation of the Gröbner bases shows that the ideals
$$
\begin{equation*}
\begin{gathered} \, \biggl(e_{02}, e_{20}, e_{03}, e_{30}, e_{04}, \lambda, 1+\sum_j(u_{0j}-u_{1j})v_j, 1+\sum_j(u_{0j}+u_{1j})w_j,\,1+u_{00}z\biggr), \\ \biggl(e_{11}, e_{02}, e_{20}, e_{03}, e_{30}, e_{04}, 1{\kern1pt}{-}{\kern1pt}\lambda, 1{\kern1pt}{+}\sum_j(u_{1j}{\kern1pt}{-}{\kern1pt}u_{2j})v_j, 1{\kern1pt}{+}\sum_j(u_{1j}{\kern1pt}{+}{\kern1pt}u_{2j})w_j, 1{\kern1pt}{+}{\kern1pt}u_{00}z\biggr) \end{gathered}
\end{equation*}
\notag
$$
of the ring $\Lambda[v_0,v_1,v_2,w_0,w_1,w_2,z]$ contain $1$. This means (cf. the proof of Lemma 6) that the condition $\lambda=k$ (where $k=0,1$), combined with $u\ne0$, implies that $p_1$ and either $p_{2k}$ or its antipode are equidistant from each $q_j$. Hence $\mathbf{p}$ satisfies (SD1) by Lemma 5. The lemma is proved. 9.3. Reducibility conditions for $\widehat F_i$Let the notation be as § 6 (adapted to the spherical case). We assume that $M$ contains a flexible $\mathbb P^2$-nonoverlapping $(3,3)$-framework $\mathbf{p}$. Recall that $A_j^\pm=r_{1j}\pm r_{0j}$, $j=0,1,2$, and $\mathfrak s(x)=\sqrt{-1}\,\sin\frac{x}{2}$. As in § 6, we simplify the notation by setting $T=T_1$, $S=S_1$, $R=R_1$ and $a_j=r_{1j}$. Without loss of generality we may assume that
$$
\begin{equation}
2r_{ij}\leqslant\pi \quad\text{when } i=0 \text{ or } j=0
\end{equation}
\tag{9.4}
$$
(this condition can always be achieved by replacing some joints by their antipodes). Lemma 4 combined with (9.4) implies that for $j,k=0,1,2$, $j\ne k$, we have
$$
\begin{equation}
{\mathfrak s}(A_j^+-A_k^-)\ne 0,\qquad {\mathfrak s}(A_j^+ + A_0^-)\ne 0,\qquad {\mathfrak s}(A_j^-+A_0^+)\ne 0,
\end{equation}
\tag{9.5}
$$
$$
\begin{equation}
{\mathfrak s}(A_j^-+A_0^-)=0 \quad\Longrightarrow\quad A_j^-+A_0^-=0,
\end{equation}
\tag{9.6}
$$
$$
\begin{equation}
{\mathfrak s}(A_j^\pm-A_k^\pm)=0 \quad\Longrightarrow\quad A_j^\pm-A_k^\pm=0,
\end{equation}
\tag{9.7}
$$
$$
\begin{equation}
{\mathfrak s}(A_j^++A_k^\pm)=0 \quad\Longrightarrow\quad A_j^++A_k^\pm=2\pi\quad\text{and} \quad jk\ne 0.
\end{equation}
\tag{9.8}
$$
Abusing the language, we define parallelogrammatic cycles and (anti)parallelograms as in § 8.1. We say that a 4-cycle is a $\mathbb P^2$-(anti)parallelogram (a $\mathbb P^2$-deltoid) if it becomes an (anti)parallelogram (a deltoid, respectively) after applying the antipodal involution to some vertices. Lemma 19 (cf. Lemma 8). The polynomial $\widehat f_{1j}$, $j=1,2$, is reducible over $\mathbb C$ if and only if the 4-cycle $p_0q_0p_1q_j$ is either $\mathbb P^2$-parallelogrammatic or a $\mathbb P^2$-deltoid. Proof. Let $\widehat f_{ij}$ be reducible. Suppose that $\widehat f_{ij}$ contains a factor $\widehat f_0$ of degree zero in $t_j$. Set $\widehat f_{1j}=c_2 t_j^2+c_1 s_j t_j + c_0 s_j^2$. As in § 8.2, we have $\operatorname{Res}_{\,T}(c_0,c_2)\doteq(U_1^2-u^2)S^4$, which implies that $U_1=u$ because $U_1,u\geqslant 0$ by (9.4). Then $c_0$ and $c_2$ are as in (8.4). Thus either $\widehat f_0=S-T$, or $u=0$ and $\widehat f_0=S+T$. If $\widehat f_0=S-T$, then we conclude (as in § 6 and § 8.2) that $U_1=u$ and $u_1=u_{11}$, which corresponds to a deltoid. If ${u=0}$ and $\widehat f_0=S+T$, then $c_1$ must vanish identically in $T$ after the substitutions $U_1=u=0$ and $S=-T$. Performing these substitutions we obtain $c_1=4(u_j+u_{1j})T^2$. Hence $u_{1j}=-u_j$ and $U_1=u=0$. If we replace $p_1$ by its antipode, then we change the sign of $u_{1j}$ and obtain a deltoid again.
Suppose now that $\widehat f_{ij}$ does not contain any factor of degree zero in $t_j$. As in the proof of Lemma 8, we have to consider the following two cases. Case 1: $d_j^+ \equiv d_j^-$. This is impossible because $d_j^+ - d_j^- = 4T\sin r_j\sin a_j$ (by (8.5) for ${\mathfrak s}(x)=\sqrt{-1}\,\sin(x/2)$) and $r_j,a_j\in{]}0,\pi{[}$ since $\mathbf{p}$ is $\mathbb P^2$-nonoverlapping. Case 2: $\Delta_j^+=\Delta_j^-=0$. Then by (8.6), combined with (9.5)–(9.8), we have
$$
\begin{equation*}
(A_j^++A_0^+-2\pi)(A_j^+-A_0^+)= (A_j^-+A_0^-)(A_j^--A_0^-)=0.
\end{equation*}
\notag
$$
This is equivalent to four systems of linear equations. Two of them are (6.4). The other two are equivalent to $a_j+R=r_j+r=\pi$ and $a_j+r=r_j+R=\pi$. Applying the antipodal involution to $q_j$ (for the former system) or to $p_1$ (for the latter one), we obtain a deltoid or a parallelogrammatic cycle, respectively.
The lemma is proved. Lemma 20 (cf. Lemma 10). If $\widehat f_{11}$ and $\widehat f_{12}$ are irreducible and $\widehat F_1$ is a nontrivial reducible polynomial which is not a power of an irreducible polynomial, then the 4-cycle $p_0q_1p_1q_2$ is either $\mathbb P^2$-parallelogrammatic, or a $\mathbb P^2$-deltoid with axis $p_0p_1$. Proof. The arguments are as in the proof of Lemma 10 but more cases are to be considered.
Case 1: $d_1^+\equiv d_2^+$ and $d_1^-\equiv d_2^-$. By (8.7), combined with (9.6)–(9.8), we have
$$
\begin{equation}
(A_2^++A_1^+-2\pi)(A_2^+-A_1^+)= (A_2^-+A_1^-) (A_2^--A_1^-)=0.
\end{equation}
\tag{9.9}
$$
This gives us four systems of equations: (6.5) and two other systems, which are equivalent to $a_1+a_2=r_1+r_2=\pi$ and $a_1+r_2=r_1+a_2=\pi$, respectively. Applying the antipodal involution to $q_1$ or $p_1$ we obtain a deltoid or a parallelogrammatic cycle respectively.
Case 2: $d_1^-\equiv d_2^-$ and $\Delta_1^+ = \Delta_2^+ = 0$. By (8.6) and (9.5)–(9.8) the second condition yields
$$
\begin{equation*}
(A_1^++A_0^+-2\pi)(A_1^+-A_0^+)= (A_2^++A_0^+-2\pi)(A_2^+-A_0^+)=0.
\end{equation*}
\notag
$$
Elimination of $A_0^+$ yields $(A_2^+ + A_1^+ - 2\pi)(A_2^+ - A_1^+)=0$. For $d_1^-\equiv d_2^-$, this yields (9.9).
Case 3: $d_1^+\equiv d_2^+$ and $\Delta_1^- = \Delta_2^- = 0$. By (8.6) and (9.5)–(9.8) the second condition yields (6.6). Eliminating $A_0^-$ from it we obtain $(A_2^- + A_1^-)(A_2^- - A_1^-)=0$. Combining this with $d_1^+\equiv d_2^+$ we obtain (9.9) again. Case 4: $d_1^+\equiv d_2^-$ and $d_1^-\equiv d_2^+$. By (8.7), combined with (9.5) and (9.8), we obtain $A_1^+ + A_2^- = A_1^- + A_2^+ = 2\pi$, so that $r_1=r_2$ and $a_1+a_2=2\pi$. This is a contradiction. Case 5: $d_1^+\equiv d_2^-$ and $\Delta_1^- = \Delta_2^+ = 0$ (the same arguments hold for the swapped indices 1 and 2). By (8.7) and (9.5) the condition $d_1^+\equiv d_2^-$ implies that ${{A_1^+} + {A_2^-} = 2\pi}$. By (8.6) and (9.5) the conditions $\Delta_1^-=0$ and $\Delta_2^+=0$ imply that $\pm{A_0^-} - {A_1^-} = 0$ and $({A_0^+} - \pi) \pm ({A_2^+} - \pi) = 0$, respectively. Summing the three equations divided by 2 we obtain $r_1 + c = 2\pi - a_2$ or $r_1 + c = \pi + r_2$ where $c$ is equal to $r$ or $R$. This contradicts (9.4). The lemma is proved. We summarize Lemmas 19, 20 and 11 as follows. Lemma 21 (cf. Lemma 12). Suppose that $u\ne 0$ and $\mathbf{p}$ does not satisfy (SD1). Then the $(2,3)$-framework $(p_0,p_1;\,q_0,q_1,q_2)$ contains either a $\mathbb P^2$-parallelogrammatic cycle, or a fastened $\mathbb P^2$-deltoid, or a not fastened $\mathbb P^2$-deltoid with axis $p_0p_1$. 9.4. Completing the proof of Theorem 3Let $\mathbf{p}=(p_0,p_1,p_2;\,q_0,q_1,q_2)$ be a flexible $\mathbb P^2$-nonoverlapping spherical $(3,3)$-framework that does not satisfy (SD1). Let us show that $\mathbf{p}$ satisfies (PD2) or (CDA). In this subsection we do not identify $S^2$ with $\mathbb C\cup\{\infty\}$, thus $p_i$ and $q_j$ are just points in $S^2\subset\mathbb R^3$, and $-p_i$ is the antipode of $p_i$. As above, we set $u_{ij} = \langle p_i,q_j\rangle = \cos d_S(p_i,p_j)$. Lemma 22. (a) $\mathbf{p}$ cannot contain a rhombus with side length $\pi/2$; (b) (follows from Lemma 5) $(u_{0j},u_{1j},u_{2j})\ne(0,0,0)$ for any $j=0,1,2$. Lemma 23 (cf. Lemma 13). If $\mathbf{p}$ contains a $\mathbb P^2$-deltoid that is not a $\mathbb P^2$-rhombus, then $\mathbf{p}$ satisfies (CDA). Proof. Suppose that $\mathbf{p}$ contains a $\mathbb P^2$-deltoid $\Delta$ that is not a $\mathbb P^2$-rhombus. Without loss of generality we may assume that $\Delta$ is a deltoid. We renumber the joints so that $\Delta=p_0q_1p_1q_2$ and the axis of $\Delta$ coincides with $q_1q_2$, that is, $u_{01}=u_{11}\ne u_{02}=u_{12}$ (see Figure 4, a).
If $u_{00}=u_{10}$, then $p_0$ and $p_1$ are equidistant from each $q_j$ and $\mathbf{p}$ satisfies (SD1) by Lemma 5. Hence one of the quantities $u_{00}$ and $u_{10}$ is nonzero. Up to interchanging $p_0$ and $p_1$ we may assume that $u_{00}\ne0$. Then by Lemma 21 there exist $4$-cycles $\Delta'$ and $\Delta^*$ such that: $\Delta'$ is contained in $(p_0,p_1;\,q_0,q_1,q_2)$, $\Delta^*$ is obtained from $\Delta'$ by the antipodal involution applied to some joints, and $\Delta^*$ realizes one of the cases considered below. In each case we treat only the subcases not covered in the proof of Lemma 13. We consider the subcases up to swapping $p_0\leftrightarrow p_1$ and $q_1\leftrightarrow q_2$. If $p_i$ and $q_j$ are vertices of $\Delta'$, then we denote the corresponding vertices of $\Delta^*$ by $p_i^*$, $q_j^*$ and set $u_{ij}^*=\langle p_i^*, q_j^*\rangle$. Case 1: $\Delta^*$ is a parallelogrammatic cycle. Subcase 1a: $\Delta'=\Delta$. Let $\mathbf{u}^*=(u_{01}^*,u_{02}^*,u_{11}^*,u_{12}^*)$.
Subcase 1b: $\Delta'=p_0q_0p_1q_1$ and $(u_{00}^*,u_{01}^*,u_{10}^*,u_{11}^*)=(u_{00},\varepsilon u_{01},\varepsilon\delta u_{10},\delta u_{11})$, $\delta,\varepsilon=\pm 1$. Then $u_{00}=\delta u_{11}=\delta u_{01}=u_{10}$, hence $p_0$ and $p_1$ are equidistant from each $q_j$, which contradicts Lemma 5 because of our assumption that $\mathbf{p}$ does not satisfy (SD1). Case 2: $\Delta^*$ is a fastened deltoid with axis $p_0p_1$. We may assume that $\Delta'=p_0q_0p_1q_1$ and $(u_{00}^*,u_{01}^*,u_{10}^*,u_{11}^*)= (u_{00},\varepsilon u_{01},\varepsilon\delta u_{10},\delta u_{11})$, $\delta,\varepsilon=\pm 1$. Then $u_{00}=\varepsilon u_{01}=\varepsilon u_{11}=u_{10}$ and we conclude as in Subcase 1b. Case 3: $\Delta^*$ is a fastened deltoid with axis $q_0q_j$ (the most interesting case). We may assume that $\Delta'=p_0q_0p_1q_2$. Let $\mathbf{u}^*=(u_{00}^*,u_{02}^*,u_{10}^*,u_{12}^*)$. If $\mathbf{u}^*=(-u_{00},u_{02},-u_{10},u_{12})$, then $u_{00}=u_{10}$ and we conclude as in Subcase 1b. Otherwise we may assume that $\mathbf{u}^*=(-u_{00},\varepsilon u_{02},u_{10},-\varepsilon u_{12})$, $\varepsilon=\pm 1$. Then $u_{02}=u_{12}$ (since $\Delta$ is a deltoid with axis $q_1q_2$) and $u_{02}=-u_{12}$ (since $\Delta^*$ is a deltoid with axis $q_0q_2$). Hence $u_{02}=u_{12}=0$. We also have $u_{00}=-u_{10}$. Set $u=u_{10}=-u_{00}$ and $v=u_{01}=u_{11}$. Then $uv\ne 0$ by Lemma 22, (a). Consider the $(3,2)$-framework $(p_0,p_1,p_2;\,q_0,q_2)$. By Lemma 21 it contains either a $\mathbb P^2$-parallelogrammatic cycle or a $\mathbb P^2$-deltoid. Then one can check that, up to renumbering and antipodal involutions, the $u_{ij}$ are as in Figure 6. The $(2,3)$-framework $(p_0,p_2;\,q_0,q_1,q_2)$ also contains a $\mathbb P^2$-parallelogrammatic cycle or a $\mathbb P^2$-deltoid. Since $u_{22}\ne 0$ by Lemma 22(b), this is possible only when $w=0$ in Figure 6, (c), which means that $\mathbf{p}$ satisfies (CDA). Case 4: $\Delta'=\Delta$ and $\Delta^*$ is a deltoid with axis $p_0p_1$. Let $\mathbf{u}^*=(u_{01}^*,u_{02}^*,u_{11}^*,u_{12}^*)$.
The lemma is proved. Lemma 24. Let $\Pi$ be a $\mathbb P^2$-parallelogrammatic cycle, and let $\Pi^*$ be obtained from $\Pi$ by applying the antipodal involution to one of its vertices. Then either $\Pi$ or $\Pi^*$ is parallelogrammatic. Lemma 25 (cf. Lemma 14). $\mathbf{p}$ cannot contain two distinct $\mathbb P^2$-parallelogrammatic cycles with three common vertices. The rest of § 7 extends easily to the spherical case by use of Lemma 24, but the following additional argument is needed at the final step. Suppose that $\mathbf{p}$ does not satisfy (PD2). Then $u+u_1+u_2+u_{12}\ne 0$ because otherwise $(p_0,-p_1,p_2;\,q_0,-q_1,q_2)$ would satisfy (SD2). Recall that the spherical version of (7.1) is (8.8) with $\varepsilon=-1$. This product vanishes for each choice of sign in ‘$\pm$’ only if $l=l_2=1$, that is, only if $u=u_2=0$, but this condition contradicts Lemma 22, (a). 
Citation in format AMSBIB
\Bibitem{KovOre23} |
|
||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|