\draw [style=map, bend right=15, looseness=1.00] (5) to (3); %e3
\draw [style=map, very thick, ->] (4) to (5); %e4
\draw [blue, ultra thick, bend left, looseness=1] (2) to (1); %eta1
\draw [style=map, ultra thick, bend left=15, looseness=1.00] (5) to (6);
\draw [style=map, bend right, looseness=1.00] (1) to (0);
\draw [style=map, ultra thick] (0) to (5);
\end{pgfonlayer}
\pgfresetboundingbox
\draw[draw=none, use as bounding box] (-1,-0.5) rectangle (3,3.5);
\end{tikzpicture} &
\begin{tikzpicture} %q_2,q_2^{e_2,-}
\begin{pgfonlayer}{nodelayer}
\node [style=vertex, label=left:$a$] (0) at (-1, -0) {};
\node [style=vertex, fill=red, draw=pink, label=above:$v$,label=right:$$] (1) at (-0.5, 0.75) {};
\node [style=vertex, label=$a$] (2) at (-0.7, 2.5) {};
\node [style=vertex, label=$a$] (3) at (0.25, 3) {};
\node [style=vertex, label=$a$] (4) at (1.75, 2.75) {};
\node [style=vertex, label=below:$a-1$] (5) at (0.95, 0.25) {};
\node [style=vertex, label=above right:$a-2$] (6) at (2.5, -0) {};

\node (7) at (-0.3, 1.75) {\contour{white}{$\eta_1$}};
\node (8) at (0.2, 2.1) {\contour{white}{$\eta_2$}};
\node (9) at (0.7, 2.25) {\contour{white}{$e_3$}};
\node (10) at (1.45, 1.75) {\contour{white}{$e_4$}};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\draw [style=tree] (0) to (1);
\draw [ultra thick, blue, dashed, bend left, looseness=1] (2) to (5); %e2
\draw [blue, ultra thick, bend right=15, looseness=1.00] (1) to (3); %eta2
\draw [style=map, bend right=15, looseness=1.00] (5) to (3); %e3
\draw [style=map, very thick, ->] (4) to (5); %e4
\draw [style=map, bend left, looseness=1] (2) to (1); %eta1
\draw [style=map, ultra thick, bend left=15, looseness=1.00] (5) to (6);
\draw [style=map, bend right, looseness=1.00] (1) to (0);
\draw [style=map, ultra thick] (0) to (5);
\end{pgfonlayer}
\pgfresetboundingbox
\draw[draw=none, use as bounding box] (-1,-0.5) rectangle (3,3.5);
\end{tikzpicture}\\
$\phi(t,\epsilon)$ & $(q_1,q_1^{e_1,-})$ & $(q_2,q_2^{e_2,-})$\\
& & \\
\begin{tikzpicture} %q_3,q_3^{e_3,-}
\begin{pgfonlayer}{nodelayer}
\draw[use as bounding box, white] (-1,-0.5) rectangle (2.5,3.5);
\node [style=vertex, label=left:$a$] (0) at (-1, -0) {};
\node [style=vertex, fill=red, draw=pink, label=above:$v$,label=right:$$] (1) at (-0.5, 0.75) {};
\node [style=vertex, label=$a$] (2) at (-0.7, 2.5) {};
\node [style=vertex, label=$a$] (3) at (0.25, 3) {};
\node [style=vertex, label=$a$] (4) at (1.75, 2.75) {};
\node [style=vertex, label=below:$a-1$] (5) at (0.95, 0.25) {};
\node [style=vertex, label=above right:$a-2$] (6) at (2.5, -0) {};

\node (7) at (-0.3, 1.75) {\contour{white}{$\eta_1$}};
\node (8) at (0.2, 2.1) {\contour{white}{$\eta_2$}};
\node (10) at (1.45, 1.75) {\contour{white}{$e_4$}};
\node (9) at (1.2, 2.2) {\contour{white}{$\eta_3$}};

\node (9) at (3.75, -0.9) {\fbox{\contour{white}{$P(q_3^{e_3,-},q_4)$}}};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\draw[dashed] (3.9,3.5)--(3.9,-0.5);
\draw [style=tree] (0) to (1);
\draw [style=map, bend right=15, looseness=1.00] (1) to (3); %eta2
\draw [blue, dashed, ultra thick, bend right=15, looseness=1.00] (5) to (3); %e3
\draw [style=map, very thick, ->] (4) to (5); %e4
\draw [style=map, bend left, looseness=1] (2) to (1); %eta1
\draw [blue, ultra thick] (4) to (1); %eta3
\draw [style=map, ultra thick, bend left=15, looseness=1.00] (5) to (6);
\draw [style=map, bend right, looseness=1.00] (1) to (0);
\draw [style=map, ultra thick] (0) to (5);
\end{pgfonlayer}
\pgfresetboundingbox
\draw[draw=none, use as bounding box] (-1,-0.5) rectangle (3,3.5);
\end{tikzpicture}&
\begin{tikzpicture} %q_4,q_4^{e_4,-}
\begin{pgfonlayer}{nodelayer}
\node [style=vertex, label=left:$a$] (0) at (-1, -0) {};
\node [style=vertex, fill=red, draw=pink, label=above:$v$,label=right:$$] (1) at (-0.5, 0.75) {};
\node [style=vertex, label=$a$] (2) at (-0.7, 2.5) {};
\node [style=vertex, label=$a$] (3) at (0.25, 3) {};
\node [style=vertex, label=$a$] (4) at (1.75, 2.75) {};
\node [style=vertex, label=below:$a-1$] (5) at (0.95, 0.25) {};
\node [style=vertex, label=above right:$a-2$] (6) at (2.5, -0) {};

\node (7) at (-0.3, 1.75) {\contour{white}{$\eta_1$}};
\node (8) at (0.2, 2.1) {\contour{white}{$\eta_2$}};
\node (9) at (1.2, 2.2) {\contour{white}{$\eta_3$}};
\node (10) at (1.45, 0.75) {\contour{white}{$\eta_4$}};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\draw [style=tree] (0) to (1);
\draw [style=map, bend right=15, looseness=1.00] (1) to (3); %eta2
\draw [ultra thick, blue, dashed] (4) to (5); %e4
\draw [style=map, bend left, looseness=1] (2) to (1); %eta1
\draw [style=map, ultra thick, bend left=15, looseness=1.00] (5) to (6);
\draw [style=map, bend right, looseness=1.00] (1) to (0);
\draw [style=map, ultra thick] (0) to (5);
\draw [ultra thick, blue, looseness=0.6] (1) to (6); %eta4
\draw [style=map, very thick, ->] (4) to (1); %eta3
\end{pgfonlayer}
\pgfresetboundingbox
\draw[draw=none, use as bounding box] (-1,-0.5) rectangle (3,3.5);
\end{tikzpicture}&
\begin{tikzpicture}
\begin{pgfonlayer}{nodelayer}
\node [style=vertex, label=left:$a$] (0) at (-1, -0) {};
\node [style=vertex, fill=red, draw=pink, label=above left:$v$,label=right:$a-1$] (1) at (-0.5, 0.75) {};
\node [style=vertex, label=$a$] (2) at (-0.7, 2.5) {};
\node [style=vertex, label=$a$] (3) at (0.25, 3) {};
\node [style=vertex, label=$a$] (4) at (1.75, 2.75) {};
\node [style=vertex, label=below:$a-1$] (5) at (0.95, 0.25) {};
\node [style=vertex, label=above right:$a-2$] (6) at (2.5, -0) {};

\node (7) at (-1, 0.45) {\contour{white}{$\eta_0$}};
\node (7) at (-0.3, 1.75) {\contour{white}{$\eta_1$}};
\node (8) at (0.2, 2.1) {\contour{white}{$\eta_2$}};
\node (9) at (1.2, 2.2) {\contour{white}{$\eta_3$}};
\node (10) at (1.45, 0.75) {\contour{white}{$\eta_4$}};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\draw [style=tree] (0) to (1);
\draw [style=map, bend left, looseness=1] (2) to (1);
\draw [style=map, bend right=15, looseness=1.00] (1) to (3);
\draw [style=map, very thick, ->] (4) to (1);
\draw [style=map, looseness=0.6] (1) to (6);
\draw [style=map, ultra thick, bend left=15, looseness=1.00] (5) to (6);
\draw [style=map, bend right, looseness=1.00] (1) to (0);
\draw [style=map, ultra thick] (0) to (5);
\end{pgfonlayer}
\pgfresetboundingbox
\draw[draw=none, use as bounding box] (-1,-0.5) rectangle (3,3.5);
\end{tikzpicture}\\
$(q_3,q_3^{e_3,-})$ & $(q_4,q_4^{e_4,-})$ & $\phi(t^{v,-},\epsilon)$ \\
\end{tabularx}
\caption{\label{fig:P(t,t^{v,-})}The flip path $P_\epsilon(t,t^{v,-})$. Since $q_1$ is rooted in $e_4$, a root rotating sequence is inserted right before flipping $e_4$, thus correctly rooting the final quadrangulation in $\eta_3$, i.e.~the flipped image of $e_3$.}
\end{figure}

\begin{lemma}\label{label move congestion}
Let $(q,e,s)$ be a triple with $q\in\sQ_n^\bullet$, $e\in E(q)$, $s\in\{+,-\}$; then there is a constant $C$ such that there are at most $C$ quadruples $(t,v,x,\epsilon)$, where $t\in\LT_n$, $v$ is a leaf in $t$, $x\in \{+,-,=\}$ and $\epsilon=\pm1$, for which $(q,e,s)$ appears in the flip path $P_\epsilon(t,t^{v,x})$.
\end{lemma}

\begin{proof}
Let us first consider quadruples of the form $(t,v,-,\epsilon)$.

Suppose $t,v$ are such that $l(v)-l(p(v))=1$ and $(q,e,s)$ appears in $P_\epsilon(t,t^{v,-})=(q_i,e_i,s_i)_{i=1}^k$ (that is, $q=q_l$, $e=e_l$ and $s=s_l$ for some $l\in\{1,\ldots,k\}$); we first consider the case where no root rotation sequence appears in $P_\epsilon(t,t^{v,-})$. Let $v_1$ and $v_2$ be the endpoints of $e$ in $q^{e,s}$; then $v$ corresponds to one of these two vertices in $q_1=\phi(t,\epsilon)$, since every edge $e_i$ is adjacent to $v$ in $q_i^{e_i,-}$ and subsequent quadrangulations in the flip path. In particular, since the degree of $v$ in $q_1$ is 1 and it increases by 1 with each flip in $P_\epsilon(t, t^{v,-})$, if $d_1$ and $d_2$ are the respective degrees of $v_1$ and $v_2$ in $q$, then $l=d_1$ or $l=d_2$, according to whether $v$ is $v_1$ or $v_2$. Suppose $v$ is $v_1$; let $\eta_0,\ldots,\eta_{d_1-1}$ be the edges incident to $v_1$ in $q$, in clockwise order around $v_1$, numbered so that $e$ will end up in between $\eta_{d_1-1}$ and $\eta_0$ in $q^{e,s}$. Then $q_1=\phi(t,\epsilon)=((q^{\eta_{d_1-1},+})^{\eta_2,+})^{\ldots})^{\eta_1,+}$, since $e_i$ corresponds to the edge $\eta_{d_{i-1}}$ in $q$. We therefore have only 2 possibilities for $(t,v)$.

Now suppose a root rotation sequence does appear in $P_\epsilon(t,t^{v,-})$; if it appears strictly after $(q,e,s)$, then the reasoning above is still valid. If it appears strictly before, then the root of $q$ is some $\eta_j$, and -- reasoning as before -- the quadrangulation $q_1$ is recovered by inserting the reverse of a root rotation sequence right before applying the clockwise flip of $\eta_j$ (or right at the end if $j=0$). We are left to deal with the case where $(q,e,s)$ actually belongs to a root rotation sequence. Notice that there is a finite number of possibilities for the quadrangulation $q'$ obtained at the end of the root rotation sequence, since the sequence only acts within (at most) three adjacent faces, two of which are adjacent to $e$. Having established some $q'$ to be the quadrangulation in question, the vertex $v$ must be one of the endpoints of the root edge $e'$ of $q'$. As before, we can now reconstruct $q_1$ by labelling $\eta_0,\ldots,\eta_{d_{i-1}}$ the edges incident to this endpoint and performing the appropriate reverse root rotation sequence, followed by clockwise flips on $\eta_{d_{i-1}},\ldots,\eta_1$.

Similarly, suppose $t,v$ are such that $l(v)=l(p(v))$ and $(q,e,s)$ appears in $P_\epsilon(t,t^{v,-})$; if $(q,e,s)$ appears in $P_\epsilon(t^{v,+},t^{v,-})$, then $\phi(t^{v,+},\epsilon)$ can be reconstructed as above, hence $t=(t^{v,+})^{v,=}$. Otherwise we have $(q,e,s)=P_\epsilon(t,t^{v,+})$, hence $q=\phi(t,\epsilon)$.

Now, since $(q,e,-)$ appears in $P_\epsilon(t,t^{v,-})$ if and only if $(q^{e,-}, e, +)$ appears in $P_\epsilon(t^{v,-}, t)$, we have thus also covered the cases where $(t,v,x)$ is such that $l(v)=l(p(v))-1$, which correspond to another 4 possibilities.

Finally, the missing cases ($x\in\{+,=\}$ and $l(v)-l(p(v))\in\{1,0\}$) are completely straightforward, since they correspond to a flip path of length 1, and therefore imply that $(t,\epsilon)=\phi^{-1}(q)$ and $v$ is the one vertex whose label is changed by the flip.

This results, indeed, in a finite number of possibilities for the quadruple $(t,v,x,\epsilon)$.
\end{proof}

\subsection{The leaf translation sequences $P_\epsilon(t,t^{v,\rightarrow})$, $P_\epsilon(t,t^{v,\leftarrow})$}\label{section: leaf translation}
The other type of ``move'' we wish to emulate via quadrangulation flips is the translation of a leaf left or right in the contour of the tree. In doing this, we may suppose the leaf has the same label as its parent, and deal with all other cases by prefixing and appending flip paths of the type $P_\epsilon(t,t^{v,=})$ and $P_\epsilon(t^{v,=},t)$, which we have constructed in the previous section.

\begin{figure}\centering
\begin{tikzpicture}
\begin{pgfonlayer}{nodelayer}
\node [style=vertex, label=below:$a$, label=left:$c_{l-1}$, label={[shift={(18pt,-4pt)}]$c_{l+1}$}] (0) at (-2, -0) {};
\node [style=vertex, fill=red, draw=pink, label=left:$a$, label=above:$v$,label=right:$c_l$] (1) at (-2, 1) {};
\node [style=vertex, label=below:$a-1$, label=above right:$c_{l+2}$] (2) at (-0.25, -0) {};
\node [style=vertex, label=left:$a$] (3) at (-1.25, 2.75) {};
\node [style=vertex, label=left:$a$] (4) at (0.5, 2.5) {};
\node [style=vertex, label=below:$a-2$, label=left:$t(c_{l+2})$] (5) at (2, -0.5) {};
\node [style=vertex, label=above:$a$] (6) at (0.25, 1.25) {};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\fill [red!10] (0) [in=105, out=135, looseness=3.25] to (2) [bend right=45, looseness=1.00] to (0);

\draw [style=b, bend left, looseness=1.00] (1) to (2);
\draw [style=b] (1) to (0);
\draw [style=b, in=105, out=135, looseness=3.25] (0) to (2);
\draw [style=b, bend left=45, looseness=1.00] (0) to (2);

\draw [style=map, bend left, looseness=1.00] (1) to (2);
\draw [style=map, bend left=15, looseness=1.00] (3) to (2);
\draw [style=map, bend right=45, looseness=1.00] (2) to (4);
\draw [style=map, ultra thick] (5) to (2);
\draw [style=tree] (1) to (0);
\draw [style=tree] (0) to (2);
\draw [style=map, in=105, out=135, looseness=3.25] (0) to (2);
\draw [style=map, bend left=45, looseness=1.00] (0) to (2);
\draw [style=map, bend right=15, looseness=1.00] (4) to (2);
\draw [style=map] (6) to (2);
\end{pgfonlayer}
\end{tikzpicture}
\begin{tikzpicture}
\begin{pgfonlayer}{nodelayer}
\node [style=vertex, label=left:$a$] (0) at (-2, -0) {};
\node [style=vertex, fill=red, draw=pink, label=above right:$a-1$, label=above left:$v$] (1) at (1.2, 0) {};
\node [style=vertex, label=below:$a-1$] (2) at (-0.25, -0) {};
\node [style=vertex, label=left:$a$] (3) at (-1.95, 1.75) {};
\node [style=vertex, label=left:$a$] (4) at (-0.4, 2.5) {};
\node [style=vertex, label=below:$a-2$] (5) at (2, -0.5) {};
\node [style=vertex, label=above:$a$] (6) at (-0.15, 1.25) {};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\fill [red!10] (2) [bend left=50, looseness=1.00] to (5.center) [bend left=15, looseness=1.00] to (2);

\draw [style=b] (1) to (2);
\draw [style=b, bend left=50, looseness=1.00] (2) to (5);
\draw [style=b, bend left=15] (5) to (2);

\draw [style=map] (1) to (5);
\draw [style=map, bend left=15, looseness=1.00] (3) to (2);
\draw [style=map, bend right=45, looseness=1.00] (2) to (4);
\draw [style=map, ultra thick, bend left=15] (5) to (2);
\draw [style=tree] (1) to (2);
\draw [style=tree] (0) to (2);
\draw [style=map, bend left=50, looseness=1.00] (2) to (5);
\draw [style=map, bend left=45, looseness=1.00] (0) to (2);
\draw [style=map, bend right=15, looseness=1.00] (4) to (2);
\draw [style=map] (6) to (2);
\end{pgfonlayer}
\end{tikzpicture}
\caption{\label{fig:leaf translation static}The quadrangulations $\phi(t,\epsilon)$ and $\phi(t^{v,\rightarrow},\epsilon)$, drawn in a case where $l(c_{l+2})=l(v)-1$.}
\end{figure}

The description of $\phi(t^{v,\rightarrow},\epsilon)$ in terms of $\phi(t,\epsilon)$ is rather simple and depicted in Figure~\ref{fig:leaf translation static}:
\begin{lemma}\label{leaf translation static}
Consider $(t,\epsilon)\in\LT_n\times\{-1,1\}$ and let $v$ be a leaf of $t$ such that $l(v)=l(p(v))$. Let $c_1,\ldots,c_{2n}$ be the clockwise contour of $t$ and suppose $c_l$, with $2\leq l\leq 2n-1$, is the corner of $v$ (notice that, if we had $l=2n$, we would have $t^{v,\rightarrow}=t$). Then $\phi(t^{v,\rightarrow},\epsilon)$ can be obtained from $\phi(t,\epsilon)$ by
\begin{itemize}
\item identifying the two edges $(c_{l-1}, t(c_{l-1}))$ and $(c_{l+1},t(c_{l+1}))$ and erasing the double edge $(c_l,c_{l+1})$ (that is eliminating the one degenerate face of $\phi(t,\epsilon)$ which corresponds to the tree edge $(p(v),v)$);
\item replacing the edge $(c_{l+2},t(c_{l+2}))$ by a degenerate face whose internal vertex is adjacent to the vertex of $t(c_{l+2})$.
\end{itemize}
Notice that it is possible that either the edge $(c_{l-1},t(c_{l-1}))$ (if $l=2$) or the edge $(c_{l+2},t(c_{l+2})))$ (if $l=2n-1$) is the root edge of $\phi(t,\epsilon)$. In the former case, the root of $\phi(t^{v,\rightarrow},\epsilon)$ is the edge obtained from identifying $(c_{l-1}, t(c_{l-1}))$ and $(c_{l+1},t(c_{l+1}))$, oriented as before; in the latter, it is the second edge of the new degenerate face in clockwise order around the vertex of $c_{l+2}$, oriented as $(c_{l+2},t(c_{l+2}))$ was.
\end{lemma}

\begin{proof}
Given $t\in\LT_n$ and $\epsilon\in\{-1,1\}$, a leaf $v$ such that $l(v)=l(p(v))$ is the internal vertex of a degenerate face in $\phi(t,\epsilon)$; removing the leaf (and the tree edge joining it to its parent) results in a tree $t'\in\LT_{n-1}$ and a quadrangulation $\phi(t',\epsilon)$ in which the face is eliminated by identifying the two edges of its boundary (into a root edge with the same orientation as before in the case where one of them was root edge in $\phi(t,\epsilon)$).

The quadrangulation $\phi(t^{v,\rightarrow})$ is obtained by performing the above operation and then its reverse in the appropriate way.
\end{proof}

The quadrangulation flip path $P_\epsilon(t,t^{v,\rightarrow})$ will depend on the label of the vertex $w$ of corner $c_{l+2}$ in $t$; since the cases where $l(w)=l(v)$ and $l(w)=l(v)+1$ are simpler (we can construct a path of length 1 in the first case and 3 in the second!), we refer to Figure~\ref{fig:-> over =} and Figure~\ref{fig:-> over +} for its construction, which only involves flips within two adjacent faces of $\phi(t,\epsilon)$. Notice that, furthermore, the construction preserves the edges issued from $c_{l-1}$ and $c_{l+2}$, so that the root edge is automatically the correct one in the quadrangulations $q_2$ from Figure~\ref{fig:-> over =} and $q_4$ from Figure~\ref{fig:-> over +}.

The case where $l(w)=l(v)-1$ is more complex, and will be treated in the following lemma.

\begin{figure}\centering
\begin{tikzpicture}
\begin{pgfonlayer}{nodelayer}
\node [style=vertex, label=left:$a$] (0) at (-5.5, 1) {};
\node [style=vertex, label=right:$a$] (1) at (-4.25, 1) {};
\node [style=vertex, label=left:$a$, label=above:$v$, draw=pink, fill=red] (2) at (-4.5, 2.25) {};
\node [style=vertex, label=above:$a-1$] (3) at (-3.25, 2.75) {};
\node (4) at (-4.5, 0.25) {$q_1=\phi(t,\epsilon)$};
\node (5) at (-1.5, 0.25) {$(q_1,q_2)$};
\node [style=vertex] (6) at (-1.25, 1) {};
\node [style=vertex] (7) at (-2.5, 1) {};
\node [style=vertex, label=above:$v$, draw=pink, fill=red] (8) at (-1.5, 2.25) {};
\node [style=vertex] (9) at (-0.25, 2.75) {};
\node [style=vertex, label=left:$a$] (10) at (0.5, 1) {};
\node [style=vertex, label=below right:$a$, label=above:$v$, draw=pink, fill=red] (11) at (1.5, 2.25) {};
\node [style=vertex, label=right:$a$] (12) at (1.75, 1) {};
\node [style=vertex, label=right:$a-1$] (13) at (2.75, 2.75) {};
\node (14) at (1.5, 0.25) {$q_2=\phi(t^{v,\rightarrow},\epsilon)$};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\draw [style=tree] (2) to (0);
\draw [style=tree] (0) to (1);
\draw [style=map, bend left=60, looseness=1.50] (0) to (3);
\draw [style=map] (0) to (3);
\draw [style=map] (2) to (3);
\draw [style=map] (1) to (3);
\draw [style=map, bend left=60, looseness=1.50] (7) to (9);
\draw [blue, very thick, dashed] (7) to (9);
\draw [style=map] (8) to (9);
\draw [blue, very thick, bend left=75, looseness=2.00] (6) to (9);
\draw [style=map] (6) to (9);
\draw [style=tree] (10) to (12);
\draw [style=map, bend left=60, looseness=1.50] (10) to (13);
\draw [style=map] (11) to (13);
\draw [style=map, bend left=75, looseness=2.00] (12) to (13);
\draw [style=map] (12) to (13);
\draw [style=tree] (11) to (12);
\end{pgfonlayer}
\end{tikzpicture}
\caption{\label{fig:-> over =}The flip path $P_\epsilon(t,t^{v,\rightarrow})$ has length 1 when the edge $(v,p(v))$ is replanted onto a vertex which has the same label as $v$ and $p(v)$. Notice that the edge that needs to be flipped in order to change $\phi(t,\epsilon)$ into $\phi(t^{v,\rightarrow},\epsilon)$ \emph{cannot} be the root edge of $\phi(t,\epsilon)$, since it is not issued from the first corner of $t$.}
\end{figure}

\begin{figure}\centering
\begin{tikzpicture}
\begin{pgfonlayer}{nodelayer}
\node [style=vertex, label=left:$a$] (0) at (-5.5, 1) {};
\node [style=vertex, label=right:$a+1$] (1) at (-4.25, 1) {};
\node [style=vertex, label=left:$a$, label=above:$v$, draw=pink, fill=red] (2) at (-4.75, 2.25) {};
\node [style=vertex, label=left:$a$] (3) at (-3.25, 1.75) {};
\node [style=vertex, label=above:$a-1$] (4) at (-3.25, 2.75) {};

\node [style=vertex] (5) at (-1.25, 1) {};
\node [style=vertex] (6) at (-0.25, 1.75) {};
\node [style=vertex] (7) at (-0.25, 2.75) {};
\node [style=vertex] (8) at (-2.5, 1) {};
\node [style=vertex, label=above:$v$, draw=pink, fill=red] (9) at (-1.75, 2.25) {};
\node [style=vertex, label=above:$v$, draw=pink, fill=red] (10) at (1.5, 2.25) {};
\node [style=vertex] (11) at (1.75, 1) {};
\node [style=vertex] (12) at (2.75, 2.75) {};
\node [style=vertex] (13) at (2.75, 1.75) {};
\node [style=vertex] (14) at (0.5, 1) {};
\node [style=vertex] (15) at (3.5, 1) {};
\node [style=vertex] (16) at (5.75, 1.75) {};
\node [style=vertex] (17) at (4.75, 1) {};
\node [style=vertex] (18) at (5.75, 2.75) {};
\node [style=vertex, label=above:$v$, draw=pink, fill=red] (19) at (4.5, 2.25) {};

\node [style=vertex, label=above:$v$, label=left:$a+1$, draw=pink, fill=red] (20) at (7.5, 2.25) {};
\node [style=vertex, label=right:$a+1$] (21) at (7.75, 1) {};
\node [style=vertex, label=above:$a-1$] (22) at (8.75, 2.75) {};
\node [style=vertex, label=right:$a$] (23) at (8.75, 1.75) {};
\node [style=vertex, label=left:$a$] (24) at (6.5, 1) {};

\node (x) at (-4.5,0.25) {$\phi(t,\epsilon)=q_1$};
\node (x) at (-1.5,0.25) {$(q_1,q_2)$};
\node (x) at (1.5,0.25) {$(q_2,q_3)$};
\node (x) at (4.5,0.25) {$(q_3,q_4)$};
\node (x) at (7.5,0.25) {$q_4=\phi(t^{v,\rightarrow},\epsilon)$};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\draw [style=tree] (2) to (0);
\draw [style=tree] (0) to (1);
\draw [style=map, bend left=60, looseness=1.50] (0) to (4);
\draw [style=map] (0) to (4);
\draw [style=map] (2) to (4);
\draw [style=map] (1) to (3);
\draw [style=map] (3) to (4);
\draw [style=map, bend left=60, looseness=1.50] (8) to (7);
\draw [blue, very thick, dashed] (8) to (7);
\draw [style=map] (9) to (7);
\draw [style=map] (5) to (6);
\draw [style=map] (6) to (7);
\draw [blue, very thick] (9) to (5);
\draw [style=map, bend left=60, looseness=1.50] (14) to (12);
\draw [blue, very thick, dashed] (10) to (12);
\draw [blue, very thick, bend left=105, looseness=4.25] (11) to (13);
\draw [style=map] (13) to (12);
\draw [style=map] (10) to (11);
\draw [style=map] (11) to (13);
\draw [style=map, bend left=60, looseness=1.50] (15) to (18);
\draw [style=map, bend left=105, looseness=4.25] (17) to (16);
\draw [style=map] (16) to (18);
\draw [blue, very thick, dashed] (19) to (17);
\draw [style=map] (17) to (16);
\draw [blue, very thick] (19) to (16);
\draw [style=map, bend left=60, looseness=1.50] (24) to (22);
\draw [style=map, bend left=105, looseness=4.25] (21) to (23);
\draw [style=map] (23) to (22);
\draw [style=map] (21) to (23);
\draw [style=map] (20) to (23);
\draw [style=tree] (24) to (21);
\draw [style=tree] (21) to (20);

\draw [style=map, bend right] (0) to (1);
\draw [style=map, bend right] (8) to (5);
\draw [style=map, bend right] (14) to (11);
\draw [style=map, bend right] (15) to (17);
\draw [style=map, bend right] (24) to (21);
\end{pgfonlayer}
\end{tikzpicture}
\caption{\label{fig:-> over +}The flip path $P_\epsilon(t,t^{v,\rightarrow})$ when $l(w)=l(v)+1$, where $w$ is the vertex that becomes the new parent of $v$ in $t^{v,\rightarrow}$.}
\end{figure}

\begin{lemma}[Flip path construction, leaf translation onto smaller label]\label{leaf translation construction} Consider  a tree $t\in\LT_n$ with contour $c_1,\ldots,c_{2n}$ and let $v$ be a leaf of $t$ such that $l(v)=l(p(v))$, adjacent to a corner $c_l$ with $2\leq l\leq 2n-1$. Let $w$ be the vertex of the corner $c_{l+2}$ and further suppose that $l(w)=l(v)-1$.

For $\epsilon\in\{-1,1\}$, let $e_1,\ldots,e_{k-1}$ be the edges of $\phi(t,\epsilon)$ that are adjacent to $w$ and lie strictly between the edge $e_k=(c_l,c_{l+2})$ and the edge $(c_{l+2},t(c_{l+2}))$, in clockwise order around $w$. If none of them is the root edge of $\phi(t,\epsilon)$, then we can set $P_\epsilon(t,t^{v,\rightarrow})=(q_i,e_i,-)_{i=1}^k$, and we have $q_{k+1}:=q_k^{e_k,-}=\phi(t^{v,\rightarrow},\epsilon)$.

If some $e_j$ is the root edge of $\phi(t,\epsilon)$, then we can set $P_\epsilon(t,t^{v,\rightarrow})$ to be the same flip path as above, with the root rotation flip sequence from Lemma~\ref{root rotation}, performed around the endpoint of the root edge that is not $w$, inserted right before the flip $(q_j,e_j,-)$.

See Figure~\ref{fig:P(t,t^{v,->})} for the construction.
\end{lemma}
\begin{figure}[t]
\centering\begin{tabularx}{.9\textwidth}{>{\centering\arraybackslash}X>{\centering\arraybackslash}X>{\centering\arraybackslash}X}
%\hline %ROW 1
& & \\
\begin{tikzpicture} %q_1^e_1,-
\begin{pgfonlayer}{nodelayer}
\node [style=vertex, label=left:$a$] (0) at (-2, -0) {};
\node [style=vertex, fill=red, draw=pink, label=right:$a$, label=above:$v$] (1) at (-1.6, 1) {};
\node [style=vertex, label=below:$a-1$] (2) at (-0.25, -0) {};
\node [style=vertex, label=left:$a$] (3) at (-1.25, 2.75) {};
\node [style=vertex, label=left:$a$] (4) at (0.5, 2.5) {};
\node [style=vertex, label=below:$a-2$] (5) at (2, -0.5) {};
\node [style=vertex, label=above:$a$] (6) at (0.25, 1.25) {};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
%\fill[blue, opacity=0.1, use as bounding box, rounded corners] (-2.7,-1.5) rectangle (2.6,3.2);
\draw [style=map, bend left, looseness=1.00] (1) to (2);
\draw [style=map, bend left=15, looseness=1.00] (3) to (2);
\draw [style=map, bend right=45, looseness=1.00] (2) to (4);
\draw [style=map, ultra thick] (5) to (2);
\draw [blue, ultra thick, dashed, in=105, out=100, looseness=3.25] (0) to (2);
\draw [style=map, bend left=15, looseness=1.00] (0) to (2);
\draw [style=map, bend right=15, looseness=1.00] (4) to (2);
\draw [style=map] (6) to (2);
\draw [blue, ultra thick, in=155, out=-125, looseness=2] (3) to (2);

\node (e1) at (-0.9, 0.75) {\contour{white}{$e_6$}};
\node (e1) at (-2.3, 1.55) {\contour{white}{$e_1$}};
\node (e2) at (-0.65, 1.95) {\contour{white}{$e_2$}};
\node (e3) at (0.2, 1.95) {\contour{white}{$e_3$}};
\node (e4) at (0, 0.65) {\contour{white}{$e_4$}};
\node (e5) at (0.85, 1.65) {\contour{white}{$e_5$}};
\end{pgfonlayer}
\end{tikzpicture} &
\begin{tikzpicture} %q_2^e_2,-
\begin{pgfonlayer}{nodelayer}
\node [style=vertex, label=left:$a$] (0) at (-2, -0) {};
\node [style=vertex, fill=red, draw=pink, label=left:$a$, label=above:$v$] (1) at (-1, 1) {};
\node [style=vertex, label=below:$a-1$] (2) at (-0.25, -0) {};
\node [style=vertex, label=left:$a$] (3) at (-1.25, 2.75) {};
\node [style=vertex, label=right:$a$] (4) at (0.5, 2.5) {};
\node [style=vertex, label=below:$a-2$] (5) at (2, -0.5) {};
\node [style=vertex, label=above:$a$] (6) at (0.25, 1.25) {};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
%\fill[blue!80!green, opacity=0.1, use as bounding box, rounded corners] (-2.7,-1.5) rectangle (2.6,3.2);
\draw [style=map] (1) to (2);
\draw [blue, very thick, dashed, bend left=15, looseness=1.00] (3) to (2); %%%%%
\draw [blue, very thick, in=180, out=150, looseness=1.80] (2) to (4); %%%%%
\draw [style=map, bend right=45, looseness=1.00] (2) to (4);
\draw [style=map, ultra thick] (5) to (2);
\draw [style=map, bend left=15, looseness=1.00] (0) to (2);
\draw [style=map, bend right=15, looseness=1.00] (4) to (2);
\draw [style=map] (6) to (2);
\draw [style=map, in=155, out=-125, looseness=2] (3) to (2);

\node (e1) at (-0.7, 0.55) {\contour{white}{$e_6$}};
%\node (e1) at (-1.7, 1.95) {\contour{white}{$e_1$}};
\node (e2) at (-0.65, 1.95) {\contour{white}{$e_2$}};
\node (e3) at (0.2, 1.95) {\contour{white}{$e_3$}};
\node (e4) at (0, 0.65) {\contour{white}{$e_4$}};
\node (e5) at (0.85, 1.65) {\contour{white}{$e_5$}};
\end{pgfonlayer}
\end{tikzpicture} &
\begin{tikzpicture} %q_3^e_3,-
\begin{pgfonlayer}{nodelayer}
\node [style=vertex, label=left:$a$] (0) at (-2, -0) {};
\node [style=vertex, fill=red, draw=pink, label=left:$a$, label=above:$v$] (1) at (-0.5, 1.2) {};
\node [style=vertex, label=below:$a-1$] (2) at (-0.25, -0) {};
\node [style=vertex, label=left:$a$] (3) at (-1.25, 2.75) {};
\node [style=vertex, label=right:$a$] (4) at (0.5, 2.5) {};
\node [style=vertex, label=below:$a-2$] (5) at (2, -0.5) {};
\node [style=vertex, label=above:$a$] (6) at (0.25, 1.25) {};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
%\fill[blue!60!green, opacity=0.1, rounded corners, use as bounding box] (-2.7,-1.5) rectangle (2.6,3.2);
\draw [style=map] (1) to (2);
\draw [style=map, in=180, out=150, looseness=1.80] (2) to (4);
\draw [style=map, bend right=45, looseness=1.00] (2) to (4);
\draw [style=map, ultra thick] (5) to (2);
\draw [style=map, bend left=15, looseness=1.00] (0) to (2);
\draw [blue, ultra thick,dashed, bend right=15, looseness=1.00] (4) to (2); %%%
\draw [blue, ultra thick, in=150, out=140, looseness=2.2] (2) to (6);
\draw [style=map] (6) to (2);
\draw [style=map, in=155, out=-125, looseness=2] (3) to (2);

\node (e1) at (-0.4, 0.75) {\contour{white}{$e_6$}};
%\node (e1) at (-1.7, 1.95) {\contour{white}{$e_1$}};
%\node (e2) at (-1, 1.95) {\contour{white}{$e_2$}};
\node (e3) at (0.2, 1.95) {\contour{white}{$e_3$}};
\node (e4) at (0, 0.65) {\contour{white}{$e_4$}};
\node (e5) at (0.85, 1.65) {\contour{white}{$e_5$}};
\end{pgfonlayer}
\end{tikzpicture}\\
$(\phi(t,\epsilon),q_2)=(q_1,q_1^{e_1,-})$ & $(q_2,q_2^{e_2,-})$ & $(q_3,q_3^{e_3,-})$\\
& & \\
\begin{tikzpicture} %q_4^e_4,-
\begin{pgfonlayer}{nodelayer}
\node [style=vertex, label=left:$a$] (0) at (-2, -0) {};
\node [style=vertex, fill=red, draw=pink, label=left:$a$, label=above:$v$] (1) at (-0.2, 0.75) {};
\node [style=vertex, label=below:$a-1$] (2) at (-0.25, -0) {};
\node [style=vertex, label=left:$a$] (3) at (-1.25, 2.75) {};
\node [style=vertex, label=right:$a$] (4) at (0.5, 2.5) {};
\node [style=vertex, label=below:$a-2$] (5) at (2, -0.5) {};
\node [style=vertex, label=above:$a$] (6) at (0.05, 1.95) {};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
%\fill[blue!40!green, opacity=0.1, rounded corners, use as bounding box] (-2.7,-1.5) rectangle (2.6,3.2);
\draw [style=map] (1) to (2);
\draw [style=map, in=180, out=150, looseness=1.80] (2) to (4);
\draw [style=map, bend right=45, looseness=1.00] (2) to (4);
\draw [style=map, ultra thick] (5) to (2);
\draw [style=map, bend left=15, looseness=1.00] (0) to (2);
\draw [style=map, in=180, out=140, looseness=1.8] (2) to (6);
\draw [ultra thick, blue, dashed, bend left] (6) to (2); %%%
\draw [ultra thick, blue, in=-90, out=130,looseness=1.50] (2) to (4);
\draw [style=map, in=155, out=-125, looseness=2] (3) to (2);

\node (e1) at (-0.2, 0.35) {\contour{white}{$e_6$}};
%\node (e1) at (-1.7, 1.95) {\contour{white}{$e_1$}};
%\node (e2) at (-1, 1.95) {\contour{white}{$e_2$}};
%\node (e3) at (-0.3, 2) {\contour{white}{$e_3$}};
\node (e4) at (0.2, 0.65) {\contour{white}{$e_4$}};
\node (e5) at (0.85, 1.65) {\contour{white}{$e_5$}};
\end{pgfonlayer}
\end{tikzpicture}&
\begin{tikzpicture} %q_5^e_5,-
\begin{pgfonlayer}{nodelayer}
\node [style=vertex, label=left:$a$] (0) at (-2, -0) {};
\node [style=vertex, fill=red, draw=pink, label=left:$a$, label=above:$v$] (1) at (-0.2, 0.75) {};
\node [style=vertex, label=below:$a-1$] (2) at (-0.25, -0) {};
\node [style=vertex, label=left:$a$] (3) at (-1.25, 2.75) {};
\node [style=vertex, label=right:$a$] (4) at (0.5, 2.5) {};
\node [style=vertex, label=below:$a-2$] (5) at (2, -0.5) {};
\node [style=vertex, label=above:$a$] (6) at (0.05, 1.95) {};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
%\fill[blue!20!green, opacity=0.1, rounded corners, use as bounding box] (-2.7,-1.5) rectangle (2.6,3.2);
\draw [style=map] (1) to (2);
\draw [style=map, in=180, out=150, looseness=1.80] (2) to (4);
\draw [ultra thick, blue, dashed, bend right=45, looseness=1.00] (2) to (4);%%%
\draw [ultra thick, blue, in=120, out=120, looseness=1.80] (2) to (5);
\draw [style=map, ultra thick] (5) to (2);
\draw [style=map, bend left=15, looseness=1.00] (0) to (2);
\draw [style=map, in=180, out=140, looseness=1.8] (2) to (6);
\draw [style=map, in=-90, out=130,looseness=1.50] (2) to (4);
\draw [style=map, in=155, out=-125, looseness=2] (3) to (2);

\node (e1) at (-0.2, 0.35) {\contour{white}{$e_6$}};
%\node (e1) at (-1.7, 1.95) {\contour{white}{$e_1$}};
%\node (e2) at (-1, 1.95) {\contour{white}{$e_2$}};
%\node (e3) at (-0.3, 2) {\contour{white}{$e_3$}};
%\node (e4) at (0.2, 1.55) {\contour{white}{$e_4$}};
\node (e5) at (0.85, 1.65) {\contour{white}{$e_5$}};
\end{pgfonlayer}
\end{tikzpicture}&
\begin{tikzpicture} %q_6^e_6,-
\begin{pgfonlayer}{nodelayer}
\node [style=vertex, label=left:$a$] (0) at (-2, -0) {};
\node [style=vertex, fill=red, draw=pink, label=left:$a$, label=above:$v$] (1) at (-0.2, 0.75) {};
\node [style=vertex, label=below:$a-1$] (2) at (-0.25, -0) {};
\node [style=vertex, label=left:$a$] (3) at (-1.25, 2.75) {};
\node [style=vertex, label=right:$a$] (4) at (0.5, 2.5) {};
\node [style=vertex, label=below:$a-2$] (5) at (2, -0.5) {};
\node [style=vertex, label=above:$a$] (6) at (0.05, 1.95) {};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
%\fill[green, opacity=0.1, rounded corners, use as bounding box] (-2.7,-1.5) rectangle (2.6,3.2);
\draw [blue, ultra thick, dashed] (1) to (2); %%%
\draw [blue, ultra thick] (1) to (5);
\draw [style=map, in=180, out=150, looseness=1.80] (2) to (4);
\draw [style=map, in=120, out=120, looseness=1.80] (2) to (5);
\draw [style=map, ultra thick] (5) to (2);
\draw [style=map, bend left=15, looseness=1.00] (0) to (2);
\draw [style=map, in=180, out=140, looseness=1.8] (2) to (6);
\draw [style=map, in=-90, out=130,looseness=1.50] (2) to (4);
\draw [style=map, in=155, out=-125, looseness=2] (3) to (2);

%\node (e1) at (-0.2, 0.35) {\contour{white}{$e_6$}};
%\node (e1) at (-1.7, 1.95) {\contour{white}{$e_1$}};
%\node (e2) at (-1, 1.95) {\contour{white}{$e_2$}};
%\node (e3) at (-0.3, 2) {\contour{white}{$e_3$}};
%\node (e4) at (0.2, 1.55) {\contour{white}{$e_4$}};
%\node (e5) at (0.85, 0.75) {\contour{white}{$e_5$}};
\end{pgfonlayer}
\end{tikzpicture}\\
$(q_4,q_4^{e_4,-})$ & $(q_5,q_5^{e_5,-})$ & $(q_6,q_6^{e_6,-})=(q_6,\phi(t^{v,\rightarrow},\epsilon))$\\
\end{tabularx}
\caption{\label{fig:P(t,t^{v,->})}The flip path $P_\epsilon(t,t^{v,\rightarrow})$ in the case where the edge $(v,p(v))$ is followed by a corner labelled $p(v)-1$ in the clockwise contour of $t$.}
\end{figure}
\begin{proof}
One can show inductively that, for $i=2,\ldots,k-1$, the quadrangulation $q_i$ is obtained from $q_1$ by collapsing the face that contains the edge $e_k$ in $q_1$ and replacing the edge $e_i$ with a degenerate face whose internal vertex is adjacent to $w$; furthermore, the natural edge identification between $q_1$ and $q_i$ has $e_k$ correspond to the internal edge of the degenerate face, while $e_i$ corresponds to the `rightmost' boundary edge of the newly created degenerate face in clockwise order around $w$. Then, $q_k$ is obtained by flipping $e_{k-1}$ counterclockwise. By Lemma~\ref{leaf translation static}, the only difference between $q_k$ and $\phi(t^{v,\rightarrow},\epsilon)$ is the fact that the internal edge of the new degenerate face is incident to $w$ in $q_k$ and, potentially, the choice of the root edge (in the case where the root edge of $q_1$ is among the flipped edges $e_1,\ldots,e_{k-1}$). Flipping $e_k$ in $q_k$ -- thus obtaining $q_{k+1}$ -- is enough to fix the first issue, and yields $\phi(t^{v,\rightarrow},\epsilon)$ up to rerooting. Suppose now that the root edge of $q_1$ is some $e_j$ (with $1\leq j\leq k-1$); the edge issued from the same corner in $q_{k+1}$ is actually the flipped version of edge $e_{j-1}$ (or the edge out of $c_{l+1}$, which never gets flipped, in the case where $l=2$: for ease of notation we will call it $e_0$). In the quadrangulation $q_j$, $e_j$ (not yet flipped and still the root edge) and $e_{j-1}$ (already flipped, unless $j=1$) are consecutive in clockwise order around their endpoint that is not $w$. Performing the root rotation sequence before $(q_j,e_j,-)$ thus simply results in rerooting $q_j$ in its edge $e_{j-1}$ (with the correct orientation), which will not be flipped again and will end up being the correct root edge in $q_{k+1}$ once the rest of the flips are performed.
\end{proof}

As mentioned before, we construct $P_\epsilon(t,t^{v,\rightarrow})$ in general as the concatenation of $P_\epsilon(t,t^{v,=})$, $P_\epsilon(t^{v,=},(t^{v,=})^{v,\rightarrow})$ and $P_\epsilon((t^{v,=})^{v,\rightarrow},((t^{v,=})^{v,\rightarrow})^{v,c})$, where $c$ is chosen so as to ``restore'' the colour of $(v,p(v))$ to the original one from $t$. We can further set $P_\epsilon(t^{v,\rightarrow},(t^{v,\rightarrow})^{v,\leftarrow})$ to be the reverse sequence of $P_\epsilon(t,t^{v,\rightarrow})$ (keeping in mind that $P_\epsilon(t,t)$ is already set to be empty). Notice that, using Lemma~\ref{label move path length} and the fact that the construction from Lemma~\ref{leaf translation construction}, excluding root rotation sequences, does not flip the same edge twice, we immediately have \begin{equation}\label{translation sequence length}\left|P_\epsilon(t^{v,d},t)\right|\leq 6n+17\end{equation}
for all $t\in\LT_n$, $v$ leaf of $t$, $d\in\{\rightarrow,\leftarrow\}$, $\epsilon\in\{-1,1\}$.

Additionally, we have the following lemma.

\begin{lemma}\label{leaf translation congestion}
Let $(q,e,s)$ be a triple with $q\in\sQ^\bullet_n$, $e\in E(q)$, $s\in\{+,-\}$; then there is a constant $C$ such that there are at most $C$ quadruples $(t,v,d,\epsilon)$, where $t\in\LT_n$, $v$ is a leaf in $t$, $d\in \{\rightarrow, \leftarrow\}$ and $\epsilon=\pm1$, for which $(q,e,s)$ appears in the flip path $P_\epsilon(t,t^{v,d})$.
\end{lemma}

\begin{proof}
By lemma \ref{label move congestion}, the number of such quadruples is at most a constant times the number of those where $l(v)=l(p(v))$, so we shall restrict ourselves to the latter case; since $P_\epsilon(t,t^{v,\rightarrow})$ is the reverse of $P_\epsilon(t^{v,\rightarrow},t)$, we may also suppose $d=\rightarrow$.

Suppose $(t,v,\rightarrow,\epsilon)$ is a quadruple such that $l(v)=l(p(v))$ and $(q,e,s)$ appears in $P_\epsilon(t,t^{v,\rightarrow})$, and let $c_1,\ldots,c_{2n}$ be the clockwise contour of $t$, with $c_l$ being the corner of $v$. If $l(c_{l+2})=l(v)$, then $q=\phi(t,\epsilon)$ and $v$ is uniquely determined from the flip $(q,e,s)$.

If $l(c_{l+2})=l(v)+1$, then there are a few possibilities (refer again to Figure~\ref{fig:-> over +}). If $q$ has one more degree one vertex than $q^{e,s}$, then $q=\phi(t,\epsilon)$ and $v$ is that degree one vertex. If $q^{e,s}$ has one more degree one vertex than $q$, let $e'$ be the edge issued from that vertex; then $v$ is the vertex in question and $\phi(t^{v,\rightarrow},\epsilon)=(q^{e,s})^{e',-}$. Otherwise, $e$ is a double edge within a degenerate face, $q^{e,s}=\phi(t^{v,\rightarrow},\epsilon)$ and $v$ is its degree one endpoint.

Finally, if $l(c_{l+2})=l(v)-1$, then consider the edge $e$ in $q^{e,s}$. First, let's suppose that $(q,e,s)$ does not belong to a root rotating sequence. If $e$ is the interior edge of a degenerate face, then $\phi(t^{v,\rightarrow},\epsilon)=q^{e,s}$ and $v$ is its endpoint of degree 1. Otherwise, consider the two endpoints $w_1$, $w_2$ of $e$ in $q^{e,s}$; one of them must play the role of the vertex $w$ from Lemma~\ref{leaf translation construction}. If it is $w_1$, then to the right of the oriented edge $(w_1,w_2)$ in $q^{e,s}$ lies a degenerate face with an internal vertex connected to $w_1$. If $(w_1,u)$ is the first oriented edge in clockwise order around $w$ starting with $(w_1,w_2)$ such that $u$ is strictly nearer to $\delta$ than $w_1$, the construction of the flip path implies that $\phi(t^{v,\rightarrow},\epsilon)$ can be obtained from $q^{e,s}$ by collapsing the face lying right of $(w_1,w_2)$ and replacing $(w_1,u)$ with a new degenerate face whose internal edge is issued from $u$ and has $v$ as the other endpoint. An analogous argument holds for $w_2$, giving rise to only two possibilities for $(t,v,\rightarrow)$. If $(q,e,s)$ actually belongs to a root rotation sequence, then there is a finite number of possibilities for the final quadrangulation $q'$ obtained by completing the sequence; we can then use $q'$ and its root edge in place of $q^{e,s}$ and $e$ to reconstruct the final quadrangulation $\phi(t^{v,\rightarrow},\epsilon)$  and its vertex $v$ (from which one determines $t$ as $(t^{v,\rightarrow})^{v,\leftarrow}$) in (at most) two ways.\end{proof}

\subsection{The final comparison between $\F^{n,\bullet}$ and $\VLT$}\label{section: final comparison}

\begin{proof}[Proof of Theorem~\ref{main theorem}]
The upper bound for the spectral gap of $\F^n$ is Proposition~\ref{upper bound}; we set out to prove the lower bound.

Consider the chains $\VLT$ and $\F^{n,\bullet}$ from Section~\ref{chain comparison} and their respective spectral gaps $\widetilde{\gamma}$ and $\nu_n^\bullet$, and let $\nu_n$ be the spectral gap of $\F^n$. Also recall the Schaeffer correspondence $\phi:\LT_n\times\{-1,1\}\to\sQ_n^\bullet$ from Section~\ref{section: Schaeffer} and the flip paths $P(t)$ and $P_\epsilon(t,t^{v,x})$ constructed throughout Sections~\ref{section: rerooting}, \ref{section: colour change} and~\ref{section: leaf translation}.

Let $f:\sQ_n^\bullet\to\mathbb{R}$ be a function such that $\V_{\pi^\bullet}(f)=1$ (where $\pi^\bullet$ is the uniform measure on $\sQ_n^\bullet$) and $\mathcal{E}_{\F^{n,\bullet}}(f,f)=\nu_n^\bullet$. Then thanks to Corollary~\ref{leaf translation variant gap} we have

$$=\frac12\sum_{\substack{t\in\LT_n\\v\mbox{ leaf of }t\\x\in\{\rightarrow,\leftarrow,+,-,=\}\\\epsilon\in\{1,-1\}
\sum_{\substack{t\in\LT_n

Now we may rewrite each difference within the sums above in terms of the images of subsequent quadrangulations appearing in the paths $P_\epsilon(t,t^{v,x})$ and $P(t)$, apply the Cauchy-Schwarz inequality and tweak the constants in order to recover factors of the form $p_{\F^{n,\bullet}}(q,q')$. We obtain that the expression above is at most
$$\frac{1}{2|\LT_n|}\frac{1}{n}\left(\sum_{\substack{t\in\LT_n\\v\mbox{ leaf of }t\\x\in\{\rightarrow,\leftarrow,+,-,=\}\\\epsilon\in\{1,-1\}}}
\left(\sum_{\substack{i=0,\ldots,|P_\epsilon(t,t^{v,x})|\\P_\epsilon(t,t^{v,x})=(q_i,e_i,s_i)_{i=1}^N}}
\sum_{\substack{t\in\LT_n}}
\left(\sum_{\substack{i=0,\ldots,|P(t)|\\P(t)=(q_i,e_i,s_i)_{i=1}^N}}f(q_i)-f(q_i^{e_i,s_i})\right)^2\right)$$

$$\leq6\sum_{\substack{t\in\LT_n\\v\mbox{ leaf of }t\\x\in\{\rightarrow,\leftarrow,+,-,=\}\\\epsilon\in\{1,-1\}}}
\sum_{\substack{i=0,\ldots,|P_\epsilon(t,t^{v,x})|\\P_\epsilon(t,t^{v,x})=(q_i,e_i,s_i)_{i=1}^N}}
\sum_{\substack{i=0,\ldots,|P(t)|\\P(t)=(q_i,e_i,s_i)_{i=1}^N}}(f(q_i)-f(q_i^{e_i,s_i}))^2\frac{1}{|\sQ^\bullet_n|}\frac{1}{6n}.$$

Given $q\in\sQ_n^\bullet$, $e\in E(q)$, $s\in\{+,-\}$, write $C(q,e,s)$ for
$$\left|\{t,v,x,\epsilon\st(q,e,s)\mbox{ appears in }P_\epsilon(t,t^{v,x})\}\right|+\left|\{t\st(q,e,s)\mbox{ appears in }P(t)\}\right|.$$
Thanks to Lemma~\ref{root reversal estimates}, Lemma~\ref{label move congestion} and Lemma~\ref{leaf translation congestion}, there is a constant $M$ independent of $n$ such that $C(q,e,s)\leq M$ for all $q,e,s$. Furthermore, Lemma~\ref{root reversal estimates}, Lemma~\ref{label move path length} and \eqref{translation sequence length} imply that $\max\{|P(t)|,|P_\epsilon(t,t^{v,x})|\}\leq 7n$ for all $n\geq 17$, $t\in\LT_n$, $v$ leaf of $t$, $x\in\{\rightarrow,\leftarrow,+,=,-\}$, $\epsilon\in\{-1,1\}$. From this we obtain that, for some constant $C'$,
$$Cn^{-\frac{9}{2}}\leq \frac{C'n}{2} \sum_{\substack{q\in\sQ^\bullet_n\\e\in E(q)\\s\in\{+,-\}}}C(q,e,s)(f(q)-f(q^{e,s}))^2\frac{1}{|\sQ^\bullet_n|}\frac{1}{6n}\leq
C'n M\cdot\mathcal{E}_{\F^{n,\bullet}}(f,f)=C'n M\nu_n^\bullet\leq C'M n \nu_n,$$
where the last inequality follows from Lemma~\ref{pointed comparison}. Following the chain of inequalities, we have indeed shown that $\nu_n\geq C_1n^{-\frac{11}{2}}$ for some constant $C_1$ independent of $n$.
\end{proof}

\bibliographystyle{siam}
\begin{thebibliography}{10}

[1]
{\sc D.~Aldous}, {\em The continuum random tree. {II}. {A}n overview}, in
Stochastic analysis ({D}urham, 1990), vol.~167 of London Math. Soc. Lecture
Note Ser., Cambridge Univ. Press, Cambridge, 1991, pp.~23--70.

[2]
{\sc D.~Aldous}, {\em Triangulating the circle, at random.}, Amer. Math.
Monthly, 101 (1994).

[3]
{\sc D.~Aldous}, {\em Mixing time for a markov chain on cladograms},
Combinatorics, Probability and Computing, 9 (2000), p.~191–204.

[4]
{\sc S.~Bravyi, L.~Caha, R.~Movassagh, D.~Nagaj, and P.~W. Shor}, {\em
Criticality without frustration for quantum spin-1 chains}, Phys. Rev. Lett.,
109 (2012).

[5]
{\sc T.~Budzinski}, {\em On the mixing time of the flip walk on triangulations
of the sphere}, Comptes Rendus Mathematique, 355 (2017), pp.~464 -- 471.

[6]
{\sc S.~Cannon, D.~Levin, and A.~Stauffer}, {\em Polynomial mixing of the
edge-flip markov chain for unbiased dyadic tilings}, in Approximation,
Randomization, and Combinatorial Optimization. Algorithms and Techniques -
20th International Workshop, APPROX 2017 and 21st International Workshop,
RANDOM 2017, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl
Publishing, 2017.

[7]
{\sc S.~Cannon, S.~Miracle, and D.~Randall}, {\em Phase transitions in random
dyadic tilings and rectangular dissections}, SIAM Journal on Discrete
Mathematics, 32 (2018), pp.~1966--1992.

[8]
{\sc P.~Caputo, F.~Martinelli, A.~Sinclair, and A.~Stauffer}, {\em Random
lattice triangulations: {S}tructure and algorithms}, Ann. Appl. Probab., 25
(2015), pp.~1650--1685.

[9]
\leavevmode\vrule height 2pt depth -1.6pt width 23pt, {\em Dynamics of lattice
triangulations on thin rectangles}, Electron. J. Probab., 21 (2016), p.~22.

[10]
{\sc P.~Chassaing and G.~Schaeffer}, {\em Random planar lattices and integrated
super{B}rownian excursion}, Probab. Theory Related Fields, 128 (2004),

[11]
{\sc E.~{Cohen}, P.~{Tetali}, and D.~{Yeliussizov}}, {\em {Lattice Path
Matroids: Negative Correlation and Fast Mixing}}, ArXiv e-prints,  (2015).

[12]
{\sc R.~Cori and B.~Vauquelin}, {\em Planar maps are well labeled trees},
Canad. J. Math., 33 (1981), pp.~1023--1042.

[13]
{\sc N.~Curien, L.~M{\'e}nard, and G.~Miermont}, {\em A view from infinity of
the uniform infinite planar quadrangulation}, Lat. Am. J. Probab. Math.
Stat., 10 (2013), pp.~45--88.

[14]
{\sc P.~Diaconis and L.~Saloff-Coste}, {\em Comparison theorems for reversible
markov chains}, Ann. Appl. Probab., 3 (1993), pp.~696--730.

[15]
{\sc P.~Diaconis and L.~Saloff-Coste}, {\em Logarithmic {S}obolev inequalities
for finite {M}arkov chains}, Ann. Appl. Probab., 6 (1996), pp.~695--750.

[16]
{\sc J.-F. Le~Gall}, {\em Uniqueness and universality of the {B}rownian map},
Ann. Probab., 41 (2013), pp.~2880--2960.

[17]
{\sc D.~Levin and Y.~Peres}, {\em Markov Chains and Mixing Times: Second
Edition}, MBK, American Mathematical Society, 2017.

[18]
{\sc W.~{L{\"o}hr}, L.~{Mytnik}, and A.~{Winter}}, {\em {The {A}ldous chain on
cladograms in the diffusion limit}}, ArXiv e-prints,  (2018).

[19]
{\sc L.~McShine and P.~Tetali}, {\em On the mixing time of the triangulation
walk and other {C}atalan structures}, in Randomization Methods in Algorithm
Design, Proceedings of a {DIMACS} Workshop, Princeton, New Jersey, USA,
December 12-14, 1997, 1997, pp.~147--160.

[20]
{\sc L.~M{\'e}nard}, {\em The two uniform infinite quadrangulations of the
plane have the same law}, Ann. Inst. H. Poincar\'e Probab. Statist., 46
(2010), pp.~190--208.

[21]
{\sc G.~Miermont}, {\em The {B}rownian map is the scaling limit of uniform
random plane quadrangulations}, Acta Math., 210 (2013), pp.~319--401.

[22]
{\sc M.~Molloy, B.~Reed, and W.~Steiger}, {\em On the mixing rate of the
triangulation walk}, in Randomization methods in algorithm design
({P}rinceton, {NJ}, 1997), vol.~43 of DIMACS Ser. Discrete Math. Theoret.
Comput. Sci., Amer. Math. Soc., Providence, RI, 1999, pp.~179--190.

[23]
{\sc R.~{Movassagh}}, {\em {The gap of Fredkin quantum spin chain is
polynomially small}}, ArXiv e-prints,  (2016).

[24]
{\sc R.~Movassagh and P.~W. Shor}, {\em Supercritical entanglement in local
systems: Counterexample to the area law for quantum matter}, Proceedings of
the National Academy of Sciences, 113 (2016), pp.~13278--13282.

[25]
{\sc J.~Schweinsberg}, {\em An ${O}(n^2)$ bound for the relaxation time of a
{M}arkov chain on cladograms}, Random Struct. Algorithms, 20 (2002),

[26]
{\sc A.~Stauffer}, {\em A {L}yapunov function for {G}lauber dynamics on lattice
triangulations}, Probability Theory and Related Fields, 169 (2017),

[27]
{\sc D.~B. Wilson}, {\em Mixing times of lozenge tiling and card shuffling
{M}arkov chains}, The Annals of Applied Probability, 14 (2004), pp.~274--325.

\end{thebibliography}

\end{document}


# On the Largest Prime factor of the $k$–generalized Lucas numbers

Herbert Batte1,∗ and Florian Luca2

###### Abstract

Let $(L_{n}^{(k)})_{n\geq 2-k}$ be the sequence of $k$–generalized Lucas
numbers for some fixed integer $k\geq 2$ whose first $k$ terms are
$0,\ldots,0,2,1$ and each term afterwards is the sum of the preceding $k$
terms. For an integer $m$, let $P(m)$ denote the largest prime factor of $m$,
with $P(0)=P(\pm 1)=1$. We show that if $n\geq k+1$, then
$P(L_{n}^{(k)})>(1/86)\log\log n$. Furthermore, we determine all the
$k$–generalized Lucas numbers $L_{n}^{(k)}$ whose largest prime factor is at
most $7$.

Keywords and phrases: $k$–generalized Lucas numbers; greatest prime factor;
linear forms in logarithms.

2020 Mathematics Subject Classification: 11B39, 11D61, 11D45.

∗ Corresponding author

##  1 Introduction

###  1.1 Background

Let $k\geq 2$ be an integer. The $k$–generalized Lucas numbers is the sequence
defined by the recurrence relation

$L_{n}^{(k)}=L_{n-1}^{(k)}+\cdots+L_{n-k}^{(k)},~{}~{}\text{for
all}~{}~{}n\geq 2,$

with the initial condition $L_{0}^{(k)}=2$, $L_{1}^{(k)}=1$ for all $k\geq 2$
and $L_{2-k}^{(k)}=\cdots=L_{-1}^{(k)}=0$ for all $k\geq 3$. When $k=2$, this
sequence is the classical sequence of Lucas numbers and in this case we omit
the superscript (k) in the notation.

For an integer $m$, let $P(m)$ be the largest prime factor of $m$ with the
convention $P(0)=P(\pm 1)=1$. The challenge of determining lower bounds for
the largest prime factor of terms in linear recurrence sequences has sparked
much interest among mathematicians. Numerous studies have been conducted on
this topic, see, for example [1]. In this work, our focus is on the sequence
of $k$–generalized Lucas numbers. Specifically, we aim to derive effective
lower bounds for $P(L_{n}^{(k)})$ in relation to both $k$ and $n$. We prove
the following results.

###  1.2 Main Results

######  Theorem 1.1.

Let $(L_{n}^{(k)})_{n\geq 2-k}$ be the sequence of $k$–generalized Lucas
numbers. Then, the inequality

$\displaystyle P(L_{n}^{(k)})>\dfrac{1}{86}\log\log n,$

holds for all $n\geq k+1$.

######  Theorem 1.2.

The only solutions to the Diophantine equation

$\displaystyle L_{n}^{(k)}=2^{a}\cdot 3^{b}\cdot 5^{c}\cdot 7^{d},$ (1.1)

in nonnegative integers $n$, $k$, $a$, $b$, $c$, $d$ with $k\geq 2$ and $n\geq
k+1$, are

$\displaystyle
L_{3}^{(2)}=4,~{}~{}~{}~{}L_{4}^{(2)}=7,~{}~{}~{}~{}L_{6}^{(2)}=18,~{}~{}~{}~{}L_{4}^{(3)}=10,~{}~{}~{}~{}L_{6}^{(3)}=35,$
$\displaystyle
L_{7}^{(3)}=64,~{}~{}~{}~{}L_{12}^{(3)}=1350,~{}~{}~{}~{}L_{15}^{(3)}=8400,~{}~{}~{}~{}L_{8}^{(4)}=160~{}~{}\text{and}~{}~{}L_{15}^{(10)}=24500.$

In addition, $L_{n}^{(k)}=3\cdot 2^{n-2}$ for all $2\leq n\leq k$.

##  2 Methods

###  2.1 Preliminaries

It is known that

$\displaystyle L_{n}^{(k)}=3\cdot 2^{n-2},\qquad\text{for all}\qquad 2\leq
n\leq k.$ (2.1)

In particular, $P(L_{n}^{(k)})=3$ for all $n,k$ in the range $2\leq n\leq k$.
Additionally, $L_{k+1}^{(k)}=3\cdot 2^{k-1}-2$ and by induction one proves
that

$L_{n}^{(k)}<3\cdot 2^{n-2}\qquad{\text{\rm holds for all}}\qquad n\geq k+1.$
(2.2)

Next, we revisit some properties of the $k$–generalized Lucas numbers. They
form a linearly recurrent sequence of characteristic polynomial

$\Psi_{k}(x)=x^{k}-x^{k-1}-\cdots-x-1,$

which is irreducible over $\mathbb{Q}[x]$. The polynomial $\Psi_{k}(x)$
possesses a unique real root $\alpha(k)>1$ and all the other roots are inside
the unit circle, see [9]. The root $\alpha(k):=\alpha$ is in the interval

$\displaystyle 2(1-2^{-k})<\alpha<2$ (2.3)

as noted in [14]. As in the classical case when $k=2$, it was shown in [2]
that

$\displaystyle\alpha^{n-1}\leq L_{n}^{(k)}\leq 2\alpha^{n},\quad\text{holds
for all}\quad n\geq 1,~{}k\geq 2.$ (2.4)

Let $k\geq 2$ and define

$f_{k}(x):=\dfrac{x-1}{2+(k+1)(x-2)}.$ (2.5)

We have

$\frac{df_{k}(x)}{dx}=-\frac{(k-1)}{(2+(k+1)(x-2))^{2}}<0\qquad{\text{\rm
for~{}all}}\qquad x>0.$

In particular, inequality (2.3) implies that

$\displaystyle\dfrac{1}{2}=f_{k}(2)<f_{k}(\alpha)<f_{k}(2(1-2^{-k}))\leq\dfrac{3}{4},$
(2.6)

for all $k\geq 3$. It is easy to check that the above inequality holds for
$k=2$ as well. Further, it is easy to verify that $|f_{k}(\alpha_{i})|<1$, for
all $2\leq i\leq k$, where $\alpha_{i}$ are the remaining roots of
$\Psi_{k}(x)$ for $i=2,\ldots,k$.

The following lemma will be useful in our applications of Baker’s theory. It
is Lemma 2 in [5].

######  Lemma 2.1 (Lemma 2, [5]).

For all $k\geq 2$, the number $f_{k}(\alpha)$ is not an algebraic integer.

Moreover, it was shown in [2] that

$\displaystyle
L_{n}^{(k)}=\displaystyle\sum_{i=1}^{k}(2\alpha_{i}-1)f_{k}(\alpha_{i})\alpha_{i}^{n-1}~{}~{}\text{and}~{}~{}\left|L_{n}^{(k)}-f_{k}(\alpha)(2\alpha-1)\alpha^{n-1}\right|<\dfrac{3}{2},$
(2.7)

for all $k\geq 2$ and $n\geq 2-k$. This means that

$L_{n}^{(k)}=f_{k}(\alpha)(2\alpha-1)\alpha^{n-1}+e_{k}(n),\qquad{\text{\rm
where}}\qquad|e_{k}(n)|<1.5.$ (2.8)

The left expression in (2.7) is known as the Binet-like formula for
$L_{n}^{(k)}$. Furthermore, the right inequality expression in (2.7) shows
that the contribution of the zeros that are inside the unit circle to
$L_{n}^{(k)}$ is small.

Next, let $n\geq 3$ and $L_{n}^{(k)}=p_{1}^{\beta_{1}}\cdot
p_{2}^{\beta_{2}}\cdots p_{s}^{\beta_{s}}$ be the prime factorization of the
positive integer $L_{n}^{(k)}$, where $2=p_{1}<p_{2}<\cdots<p_{s}$ is the
increasing sequence of prime numbers and the numbers $\beta_{i}$, for
$i=1,2,\ldots,s$, are nonnegative integers. By the right-hand side of relation
(2.4), we have

$\log L_{n}^{(k)}\leq\log 2+n\log\alpha<(n+1)\log 2,$

since $\alpha<2$, for all $k\geq 2$ in (2.3). Therefore, we can write

$\displaystyle\log\prod_{i=1}^{s}p_{i}^{\beta_{i}}$
$\displaystyle=\sum_{i=1}^{s}\beta_{i}\log p_{i}=\log L_{n}^{(k)}<(n+1)\log
2,$ $\displaystyle\sum_{i=1}^{s}\beta_{i}\log 2$
$\displaystyle\leq\sum_{i=1}^{s}\beta_{i}\log p_{i}<(n+1)\log
2,\quad\text{since}\quad 2\leq p_{i},\quad\text{for all}\quad i=1,2,\ldots s,$

from which we get

$\sum_{i=1}^{s}\beta_{i}<n+1.$

In particular,

$\displaystyle\beta_{i}<n+1,$ (2.9)

for all $i=1,2,\ldots s$. Lastly, for $k\geq 3$ one checks that
$1/\log\alpha\leq 2$ by using $\alpha\geq 2(1-1/2^{k})\geq 2(1-1/2^{3})$. When
$k=2$, the number $\alpha$ represents the golden ratio for which
$1/\log\alpha<2.1.$ Thus, the inequality

$\displaystyle\frac{1}{\log\alpha}<2.1\quad{\text{\rm holds~{}for~{}all}}\quad
k\geq 2.$ (2.10)

###  2.2 Linear forms in logarithms

We use Baker-type lower bounds for nonzero linear forms in logarithms of
algebraic numbers. There are many such bounds mentioned in the literature but
we use one of Matveev from [8]. Before we can formulate such inequalities, we
need the notion of height of an algebraic number recalled below.

######  Definition 2.1.

Let $\gamma$ be an algebraic number of degree $d$ with minimal primitive
polynomial over the integers

$a_{0}x^{d}+a_{1}x^{d-1}+\cdots+a_{d}=a_{0}\prod_{i=1}^{d}(x-\gamma^{(i)}),$

where the leading coefficient $a_{0}$ is positive. Then, the logarithmic
height of $\gamma$ is given by

$h(\gamma):=\dfrac{1}{d}\Big{(}\log
a_{0}+\sum_{i=1}^{d}\log\max\\{|\gamma^{(i)}|,1\\}\Big{)}.$

In particular, if $\gamma$ is a rational number represented as $\gamma=p/q$
with coprime integers $p$ and $q\geq 1$, then $h(\gamma)=\log\max\\{|p|,q\\}$.
The following properties of the logarithmic height function $h(\cdot)$ will be
used in the rest of the paper without further reference:

$\displaystyle h(\gamma_{1}\pm\gamma_{2})$ $\displaystyle\leq
h(\gamma_{1})+h(\gamma_{2})+\log 2;$ $\displaystyle
h(\gamma_{1}\gamma_{2}^{\pm 1})$ $\displaystyle\leq
h(\gamma_{1})+h(\gamma_{2});$ $\displaystyle h(\gamma^{s})$
$\displaystyle=|s|h(\gamma)\quad{\text{\rm valid for}}\quad s\in\mathbb{Z}.$

With these properties, it was easily computed in Section 3, equation (12) of
[1] that

$\displaystyle h\left(f_{k}(\alpha)\right)<3\log k,~{}~{}\text{for
all}~{}~{}k\geq 2.$ (2.11)

A linear form in logarithms is an expression

$\Lambda:=b_{1}\log\gamma_{1}+\cdots+b_{t}\log\gamma_{t},$ (2.12)

where for us $\gamma_{1},\ldots,\gamma_{t}$ are positive real algebraic
numbers and $b_{1},\ldots,b_{t}$ are integers. We assume, $\Lambda\neq 0$. We
need lower bounds for $|\Lambda|$. We write
${\mathbb{K}}:={\mathbb{Q}}(\gamma_{1},\ldots,\gamma_{t})$ and $D$ for the
degree of ${\mathbb{K}}$ over ${\mathbb{Q}}$. We give Matveev’s inequality
from [8].

######  Theorem 2.1 (Matveev, [8]).

Put $\Gamma:=\gamma_{1}^{b_{1}}\cdots\gamma_{t}^{b_{t}}-1=e^{\Lambda}-1$. Then

$\log|\Gamma|>-1.4\cdot 30^{t+3}\cdot t^{4.5}\cdot D^{2}(1+\log D)(1+\log
B)A_{1}\cdots A_{t},$

where $B\geq\max\\{|b_{1}|,\ldots,|b_{t}|\\}$ and
$A_{i}\geq\max\\{Dh(\gamma_{i}),|\log\gamma_{i}|,0.16\\}$ for $i=1,\ldots,t$.

During the calculations, upper bounds on the variables are obtained which are
too large, thus there is need to reduce them. To do so, we use some results
from approximation lattices and the so–called LLL–reduction method from [7].
We explain this in the following subsection.

###  2.3 Reduced Bases for Lattices and LLL–reduction methods

Let $k$ be a positive integer. A subset $\mathcal{L}$ of the $k$–dimensional
real vector space ${\mathbb{R}^{k}}$ is called a lattice if there exists a
basis $\\{b_{1},b_{2},\ldots,b_{k}\\}$ of $\mathbb{R}^{k}$ such that

$\displaystyle\mathcal{L}=\sum_{i=1}^{k}\mathbb{Z}b_{i}=\left\\{\sum_{i=1}^{k}r_{i}b_{i}\mid
r_{i}\in\mathbb{Z}\right\\}.$

We say that $b_{1},b_{2},\ldots,b_{k}$ form a basis for $\mathcal{L}$, or that
they span $\mathcal{L}$. We call $k$ the rank of $\mathcal{L}$. The
determinant $\text{det}(\mathcal{L})$, of $\mathcal{L}$ is defined by

$\displaystyle\text{det}(\mathcal{L})=|\det(b_{1},b_{2},\ldots,b_{k})|,$

with the $b_{i}$’s being written as column vectors. This is a positive real
number that does not depend on the choice of the basis (see [3], Section 1.2).

Given linearly independent vectors $b_{1},b_{2},\ldots,b_{k}$ in
$\mathbb{R}^{k}$, we refer back to the Gram–Schmidt orthogonalization
technique. This method allows us to inductively define vectors $b^{*}_{i}$
(with $1\leq i\leq k$) and real coefficients $\mu_{i,j}$ (for $1\leq j\leq
i\leq k$). Specifically,

$\displaystyle b^{*}_{i}$
$\displaystyle=b_{i}-\sum_{j=1}^{i-1}\mu_{i,j}b^{*}_{j},~{}~{}~{}\mu_{i,j}=\dfrac{\langle
b_{i},b^{*}_{j}\rangle}{\langle b^{*}_{j},b^{*}_{j}\rangle},$

where $\langle\cdot,\cdot\rangle$ denotes the ordinary inner product on
$\mathbb{R}^{k}$. Notice that $b^{*}_{i}$ is the orthogonal projection of
$b_{i}$ on the orthogonal complement of the span of $b_{1},\ldots,b_{i-1}$,
and that $\mathbb{R}b_{i}$ is orthogonal to the span of
$b^{*}_{1},\ldots,b^{*}_{i-1}$ for $1\leq i\leq k$. It follows that
$b^{*}_{1},b^{*}_{2},\ldots,b^{*}_{k}$ is an orthogonal basis of
$\mathbb{R}^{k}$.

######  Definition 2.2.

The basis $b_{1},b_{2},\ldots,b_{n}$ for the lattice $\mathcal{L}$ is called
reduced if

$\displaystyle\|\mu_{i,j}\|$
$\displaystyle\leq\frac{1}{2},\quad\text{for}\quad 1\leq j<i\leq
n,~{}~{}\text{and}$ $\displaystyle\|b^{*}_{i}+\mu_{i,i-1}b^{*}_{i-1}\|^{2}$
$\displaystyle\geq\frac{3}{4}\|b^{*}_{i-1}\|^{2},\quad\text{for}\quad 1<i\leq
n,$

where $\|\cdot\|$ denotes the ordinary Euclidean length. The constant
${3}/{4}$ above is arbitrarily chosen, and may be replaced by any fixed real
number $y$ in the interval ${1}/{4}<y<1$ (see [7], Section 1).

Let $\mathcal{L}\subseteq\mathbb{R}^{k}$ be a $k-$dimensional lattice with
reduced basis $b_{1},\ldots,b_{k}$ and denote by $B$ the matrix with columns
$b_{1},\ldots,b_{k}$. We define

$l\left(\mathcal{L},y\right)=\left\\{\begin{array}[]{c}\min_{x\in\mathcal{L}}||x-y||\quad;~{}~{}y\not\in\mathcal{L}\\\
\min_{0\neq
x\in\mathcal{L}}||x||\quad;~{}~{}y\in\mathcal{L}\end{array}\right.,$

where $||\cdot||$ denotes the Euclidean norm on $\mathbb{R}^{k}$. It is well
known that, by applying the LLL–algorithm, it is possible to give in
polynomial time a lower bound for $l\left(\mathcal{L},y\right)$, namely a
positive constant $c_{1}$ such that $l\left(\mathcal{L},y\right)\geq c_{1}$
holds (see [13], Section V.4).

######  Lemma 2.2.

Let $y\in\mathbb{R}^{k}$ and $z=B^{-1}y$ with $z=(z_{1},\ldots,z_{k})^{T}$.
Furthermore,

  1. (i)

if $y\not\in\mathcal{L}$, let $i_{0}$ be the largest index such that
$z_{i_{0}}\neq 0$ and put $\sigma:=\\{z_{i_{0}}\\}$, where $\\{\cdot\\}$
denotes the distance to the nearest integer.

  2. (ii)

if $y\in\mathcal{L}$, put $\sigma:=1$.

Finally, let

$c_{2}:=\max\limits_{1\leq j\leq
k}\left\\{\dfrac{||b_{1}||^{2}}{||b_{j}^{*}||^{2}}\right\\}.$

Then,

$l\left(\mathcal{L},y\right)^{2}\geq
c_{2}^{-1}\sigma^{2}||b_{1}||^{2}:=c_{1}^{2}.$

In our application, we are given real numbers
$\eta_{0},\eta_{1},\ldots,\eta_{k}$ which are linearly independent over
$\mathbb{Q}$ and two positive constants $c_{3}$ and $c_{4}$ such that

$\displaystyle|\eta_{0}+x_{1}\eta_{1}+\cdots+x_{k}\eta_{k}|\leq
c_{3}\exp(-c_{4}H),$ (2.13)

where the integers $x_{i}$ are bounded as $|x_{i}|\leq X_{i}$ with $X_{i}$
given upper bounds for $1\leq i\leq k$. We write $X_{0}:=\max\limits_{1\leq
i\leq k}\\{X_{i}\\}$. The basic idea in such a situation, due to [4], is to
approximate the linear form (2.13) by an approximation lattice. So, we
consider the lattice $\mathcal{L}$ generated by the columns of the matrix

$\mathcal{A}=\begin{pmatrix}1&0&\ldots&0&0\\\ 0&1&\ldots&0&0\\\
\vdots&\vdots&\vdots&\vdots&\vdots\\\ 0&0&\ldots&1&0\\\ \lfloor
C\eta_{1}\rfloor&\lfloor C\eta_{2}\rfloor&\ldots&\lfloor
C\eta_{k-1}\rfloor&\lfloor C\eta_{k}\rfloor\end{pmatrix},$

where $C$ is a large constant usually of the size of about $X_{0}^{k}$ . Let
us assume that we have an LLL–reduced basis $b_{1},\ldots,b_{k}$ of
$\mathcal{L}$ and that we have a lower bound $l\left(\mathcal{L},y\right)\geq
c_{1}$ with $y:=(0,0,\ldots,-\lfloor C\eta_{0}\rfloor)$. Note that $c_{1}$ can
be computed by using the results of Lemma 2.2. Then, with these notations the
following result is Lemma VI.1 in [13].

######  Lemma 2.3 (Lemma VI.1 in [13]).

Let $S:=\displaystyle\sum_{i=1}^{k-1}X_{i}^{2}$ and
$T:=\dfrac{1+\sum_{i=1}^{k}X_{i}}{2}$. If $c_{1}^{2}\geq T^{2}+S$, then
inequality (2.13) implies that we either have $x_{1}=x_{2}=\cdots=x_{k-1}=0$
and $x_{k}=-\dfrac{\lfloor C\eta_{0}\rfloor}{\lfloor C\eta_{k}\rfloor}$, or

$H\leq\dfrac{1}{c_{4}}\left(\log(Cc_{3})-\log\left(\sqrt{c_{1}^{2}-S}-T\right)\right).$

Finally, we present an analytic argument which is Lemma 7 in [6].

######  Lemma 2.4 (Lemma 7 in [6]).

If $m\geq 1$, $T>(4m^{2})^{m}$ and $T>\displaystyle\frac{x}{(\log x)^{m}}$,
then

$x<2^{m}T(\log T)^{m}.$

SageMath 9.5 is used to perform all computations in this work.

##  3 Proof of Theorem 1.1.

In this section, we prove Theorem 1.1. To do this, we first state and prove
some preliminary results. We start with the following.

###  3.1 An upper bound on $n$ in terms of $s$ and $k$.

######  Lemma 3.1.

Let $n\geq k+1$ and $L_{n}^{(k)}=p_{1}^{\beta_{1}}\ldots p_{s}^{\beta_{s}}$,
be the prime factorization of $L_{n}^{(k)}$ with $\beta_{i}\geq 0$, for all
$i=1,2,\ldots,s$. Then

$\log n<35s\log s+3s\log k+3\log(12s+k).$

###### Proof.

We use Theorem 2.1 to get the inequality in Lemma 3.1. Because of our earlier
deduction that $P(L_{n}^{(k)})\leq 3$ for all $n\leq k$, we can assume that
$n\geq k+1$. Moreover, the main result in [11] tells us that the only
$k$–generalized Lucas numbers that are powers of 2 are $L_{0}^{(k)}=2$,
$L_{1}^{(k)}=1$ (for any $k\geq 2$), $L_{3}^{(2)}=2^{2}$ and
$L_{7}^{(3)}=2^{6}$. So, we may further assume that $s\geq 2$ and $n\geq
k+1\geq 3$.

Now, by the prime factorization of $L_{n}^{(k)}$ and (2.7), we have

$\displaystyle\left|p_{1}^{\beta_{1}}\ldots
p_{s}^{\beta_{s}}-f_{k}(\alpha)(2\alpha-1)\alpha^{n-1}\right|<\dfrac{3}{2}.$
(3.1)

Dividing both sides by $f_{k}(\alpha)(2\alpha-1)\alpha^{n-1}$, which is
positive because $\alpha>1$, we get

$\displaystyle\left|p_{1}^{\beta_{1}}\ldots
p_{s}^{\beta_{s}}\cdot(2\alpha-1)^{-1}\cdot\alpha^{-(n-1)}\cdot(f_{k}(\alpha))^{-1}-1\right|$
$\displaystyle<\dfrac{3}{2f_{k}(\alpha)(2\alpha-1)\alpha^{n-1}}$
$\displaystyle<\dfrac{6}{(2\alpha-1)\alpha^{n-1}}$
$\displaystyle<\dfrac{6}{\alpha^{n-1}},$ (3.2)

where in the second inequality, we used relation (2.6); i.e.,
$f_{k}(\alpha)>1/2$. Let

$\Gamma=p_{1}^{\beta_{1}}\ldots
p_{s}^{\beta_{s}}\cdot(2\alpha-1)^{-1}\cdot\alpha^{-(n-1)}\cdot(f_{k}(\alpha))^{-1}-1=e^{\Lambda}-1.$

Notice that $\Lambda\neq 0$, otherwise we would have

$\displaystyle p_{1}^{\beta_{1}}\ldots p_{s}^{\beta_{s}}$
$\displaystyle=(2\alpha-1)\alpha^{n-1}f_{k}(\alpha)$
$\displaystyle=\dfrac{\alpha-1}{2+(k+1)(\alpha-2)}(2\alpha-1)\alpha^{n-1}.$
(3.3)

Conjugating the above relation by some automorphism of the Galois group of the
splitting field of $\Psi_{k}(x)$ over $\mathbb{Q}$ which sends $\alpha$ to
$\alpha_{i}$ for some $i>1$ and then taking absolute values, we get

$\displaystyle p_{1}^{\beta_{1}}\ldots p_{s}^{\beta_{s}}$
$\displaystyle=\left|\dfrac{\alpha_{i}-1}{2+(k+1)(\alpha_{i}-2)}(2\alpha_{i}-1)\alpha_{i}^{n-1}\right|.$
(3.4)

Note that from (3.4), we have that
$|2+(k+1)(\alpha_{i}-2)|\geq(k+1)|\alpha_{i}-2|-2>k-1$, as shown on page 1355
of [1]. Hence, the right-hand side of (3.4) becomes

$\displaystyle 6$ $\displaystyle=\min\\{L_{4}^{(3)},L_{4}^{(2)}\\}\leq
L_{n}^{(k)}=\left|\dfrac{\alpha_{i}-1}{2+(k+1)(\alpha_{i}-2)}(2\alpha_{i}-1)\alpha_{i}^{n-1}\right|<\dfrac{|\alpha_{i}-1|\cdot|2\alpha_{i}-1|\cdot|\alpha_{i}|^{n-1}}{k-1}\leq\dfrac{2\cdot
3\cdot 1}{k-1}$ $\displaystyle<6,$

for $k\geq 3$ (so, $n\geq k+1\geq 4$), or $k=2$ and $n\geq 4$, a
contradiction. One can check directly that (3.1) does not hold for the
remaining case $k=2,~{}n=3$. So, $\Lambda\neq 0$.

The algebraic number field containing the following $\gamma_{i}$’s is
$\mathbb{K}:=\mathbb{Q}(\alpha)$. We have $D=k$, $t:=s+3$,

$\displaystyle\gamma_{i}$
$\displaystyle:=p_{i}~{}~{}\text{for}~{}i=1,2,\ldots,s,~{}~{}~{}\gamma_{s+1}:=2\alpha-1,~{}~{}~{}\gamma_{s+2}:=\alpha,~{}~{}~{}\gamma_{s+3}:=f_{k}(\alpha),$
$\displaystyle b_{i}$
$\displaystyle:=\beta_{i}~{}~{}\text{for}~{}i=1,2,\ldots,s,~{}~{}~{}b_{s+1}:=-1,~{}~{}~{}b_{s+2}:=-(n-1),~{}~{}~{}b_{s+3}:=-1.$

Since $h(\gamma_{i})=\log p_{i}\leq\log p_{s}$ for all $i=1,2,\ldots,s$, we
take $A_{i}:=k\log p_{s}$ for all $i=1,2,\ldots,s$. Furthermore,
$h(\gamma_{s+1})<3/k$, for all $k\geq 2$, so we take $A_{s+1}:=3$.
Additionally, $h(\gamma_{s+2})=(\log\alpha)/k<0.7/k$, so we take
$A_{s+2}:=0.7$. Lastly, $h(\gamma_{s+3})<3\log k$ by relation (2.11). Hence,
we take $A_{s+3}:=3k\log k$.

Next, $B\geq\max\\{|b_{i}|:i=1,2,\ldots,s,\ldots,s+3\\}$. Notice that
$b_{i}=\beta_{i}<n+1$, for all $i=1,2,\ldots,s$ by relation (2.9), so we take
$B:=n+1$. Now, by Theorem 2.1,

$\displaystyle\log|\Gamma|$ $\displaystyle>-1.4\cdot
30^{s+6}\cdot(s+3)^{4.5}\cdot k^{2}(1+\log k)(1+\log(n+1))\cdot(k\log
p_{s})^{s}\cdot 3\cdot 0.7\cdot 3k\log k$ $\displaystyle>-1.4\cdot 30^{s}\cdot
30^{6}\cdot s^{4.5}\cdot 3^{4.5}\cdot k^{2}\cdot 3\log k\cdot 2\log(n+1)\cdot
k^{s}(\log p_{s})^{s}\cdot 3\cdot 0.7\cdot 3k\log k$ $\displaystyle>-5.5\cdot
10^{12}\cdot 30^{s}s^{4.5}k^{3+s}(\log k)^{2}(\log p_{s})^{s}\log(n+1).$ (3.5)

Comparing (3.1) and (3.1), we get

$\displaystyle(n-1)\log\alpha-\log 6$ $\displaystyle<5.5\cdot 10^{12}\cdot
30^{s}s^{4.5}k^{3+s}(\log k)^{2}(\log p_{s})^{s}\log(n+1),$

which leads to

$\displaystyle n-1$ $\displaystyle<1.2\cdot 10^{13}\cdot
30^{s}s^{4.5}k^{3+s}(\log k)^{2}(\log p_{s})^{s}\log(n+1),$

and adding $2$ to both sides yields

$\displaystyle n+1$ $\displaystyle<1.21\cdot 10^{13}\cdot
30^{s}s^{4.5}k^{3+s}(\log k)^{2}(\log p_{s})^{s}\log(n+1).$ (3.6)

Now, recall our assumption that $n\geq k+1$ implies $k\leq n-1<n+1$. Moreover,
the inequality $p_{m}<m^{2}$ holds for all $m\geq 2$. This is the Corollary to
Theorem 3 on page 69 of [12]. With these, inequality (3.6) becomes

$\displaystyle\dfrac{n+1}{(\log(n+1))^{3}}$ $\displaystyle<1.21\cdot
10^{13}s^{4.5}k^{3+s}(60\log s)^{s}.$

We apply Lemma 2.4 with $x:=n+1$, $m:=3$ and $T:=1.21\cdot
10^{13}s^{4.5}k^{3+s}(60\log s)^{s}>(4m^{2})^{m}=46656$. We get

$\displaystyle n+1$ $\displaystyle<2^{3}\cdot 1.21\cdot
10^{13}s^{4.5}k^{3+s}(60\log s)^{s}(\log(1.21\cdot
10^{13}s^{4.5}k^{3+s}(60\log s)^{s}))^{3}$ $\displaystyle=9.68\cdot
10^{13}s^{4.5}k^{3+s}(60\log s)^{s}\left(\log(1.21\cdot 10^{13})+4.5\log
s+(3+s)\log k+s\log(60\log s)\right)^{3}$ $\displaystyle<9.68\cdot
10^{13}s^{4.5}k^{3+s}(60\log s)^{s}\cdot
s^{3}\left(\dfrac{31}{s}+\dfrac{4.5}{s}\log s+\left(1+\dfrac{3}{s}\right)\log
k+\log(60\log s)\right)^{3}$ $\displaystyle<9.68\cdot
10^{13}s^{7.5}k^{3+s}(60\log s)^{s}(12s+k)^{3},$

where we have used the fact that $(1+3/s)\log k<k$ for $k\geq 2$, $s\geq 2$
and

$(31/s)+(4.5/s)\log s+\log(60\log s)<12s\qquad{\text{\rm for}}\qquad s\geq 2.$

Therefore,

$\displaystyle n$ $\displaystyle<9.7\cdot 10^{13}s^{7.5}k^{3+s}(60\log
s)^{s}(12s+k)^{3},$

and hence

$\displaystyle\log n$ $\displaystyle<\log(9.7\cdot 10^{13})+7.5\log
s+(3+s)\log k+s\log(60\log s)+3\log(12s+k)$ $\displaystyle<33+7.5\log
s+s\log(60\log s)+3s\log
k+3\log(12s+k),~{}~{}\text{since}~{}3+s<3s~{}~{}\text{for all}~{}s\geq 2,$
$\displaystyle=s\log s\left(\dfrac{33}{s\log
s}+\dfrac{7.5}{s}+\dfrac{\log(60\log s)}{\log s}\right)+3s\log
k+3\log(12s+k),$ $\displaystyle<35s\log s+3s\log k+3\log(12s+k).$

This completes the proof of Lemma 3.1. ∎

To proceed, observe that if $k\leq s$, then Lemma 3.1 implies that

$\displaystyle\log n$ $\displaystyle<38s\log s+3\log(13s)$
$\displaystyle<s\log s\left(38+\dfrac{8}{s\log s}+\dfrac{3}{s}\right)$
$\displaystyle<46s\log s,$

for $s\geq 2$. Using the well-known fact that $p_{s}>s\log s$, which is
relation (3.12) from page 69 of [12], we have that

$\displaystyle p_{s}>s\log s>\dfrac{1}{46}\log n.$

We therefore assume that $s<k$ for the remainder of this section. With this
assumption, the conclusion of Lemma 3.1 becomes

$\displaystyle\log n$ $\displaystyle<38s\log k+3\log(13k)$
$\displaystyle<s\log k\left(38+\dfrac{8}{s\log k}+\dfrac{3}{s}\right)$
$\displaystyle<46s\log k,$ (3.7)

for $s\geq 2$ and $k\geq 2$. We proceed by distinguishing between two cases.

###  3.2 The case $n\geq 2^{k/2}$

Here, we have that

$\displaystyle\dfrac{k}{2}\log 2\leq\log n,$

so that

$\displaystyle k\leq\dfrac{2}{\log 2}\log n<\dfrac{2}{\log 2}\cdot 46s\log
k<133s\log k.$

From the above, we have $k/\log k<133s$. We apply Lemma 2.4 with the data:
$x:=k$, $m:=1$ and $T:=133s>(4m^{2})^{m}=4$, for all $s\geq 2$. We get

$\displaystyle k<2\cdot 133s\log(133s)=266s(\log 133+\log s)\leq 266s\log
s\left(\frac{\log 133}{\log 2}+1\right)<2143s\log s.$ (3.8)

Therefore,

$\displaystyle\log k<\log 2143+\log s+\log\log s<\left(\dfrac{\log 2143}{\log
2}+2\right)s\log s<14\log s,$ (3.9)

holds for $s\geq 2$. Finally, we use Lemma 3.1 again together with relations
(3.8) and inequality (3.9) to conclude that

$\displaystyle\log n$ $\displaystyle<35s\log s+3s\cdot 14\log
s+3\log(12s+2143s\log s)<77s\log s+3\log(2155s^{2})$ $\displaystyle=77s\log
s+6\log s+\log(2155)<s\log s\left(77+\frac{6}{s}+\frac{\log(2155)}{s\log
s}\right)$ $\displaystyle<86s\log s,$

for $s\geq 2$. In the above, we used that $\log s<s$. Consequently,
$p_{s}>s\log s>(1/86)\log n$ in this case.

###  3.3 The case $n<2^{k/2}$

Let $\lambda>0$ be such that $\alpha+\lambda=2$. Since $2(1-2^{-k})<\alpha<2$,
then we get that $\lambda<2-2(1-2^{-k})=1/2^{k-1}$. That is,
$\lambda\in(0,1/2^{k-1})$. Moreover,

$\displaystyle\alpha^{n-1}$
$\displaystyle=(2-\lambda)^{n-1}=2^{n-1}\left(1-\frac{\lambda}{2}\right)^{n-1}$
$\displaystyle=2^{n-1}\left(e^{\log(1-\lambda/2)}\right)^{n-1}$
$\displaystyle\geq 2^{n-1}e^{-\lambda(n-1)}$ $\displaystyle\geq
2^{n-1}(1-\lambda(n-1)),$

where we used the fact that $\log(1-x)>-2x$ for all $x<1/2$ and $e^{-x}\geq
1-x$ for all $x\in\mathbb{R}$.

Furthermore,

$\lambda(n-1)<\dfrac{n-1}{2^{k-1}}<\dfrac{2^{k/2}}{2^{k-1}}=2^{k/2-1},$

implying that $\alpha^{n-1}>2^{n-1}(1-2^{k/2-1})$. It follows since
$2(1-2^{-k})<\alpha<2$ that

$2^{n-1}-\frac{2^{n}}{2^{k/2}}<\alpha^{n-1}<2^{n-1}<2^{n-1}+\frac{2^{n}}{2^{k/2}},$

or

$\left|\alpha^{n-1}-2^{n-1}\right|<\frac{2^{n}}{2^{k/2}}.$ (3.10)

Next, consider the function $f_{k}(x)$ given at (2.5). By the Mean-Value
Theorem, there exists some $\omega\in(\alpha,2)$ such that
$f_{k}(\alpha)=f_{k}(2)+(\alpha-2)f_{k}^{\prime}(\omega)$. Observe that when
$k\geq 2$, we obtain

$\displaystyle|f_{k}^{\prime}(\omega)|$
$\displaystyle=\dfrac{k-1}{(2+(k+1)(\omega-2))^{2}}$
$\displaystyle<\dfrac{k-1}{(2-(k+1)/2^{k-1})^{2}},~{}~{}\text{since}~{}\omega\in(\alpha,2)\subset(2-1/2^{k-1},2),$
$\displaystyle<k$

for $k\geq 3$, since $2^{k-1}\geq k+1$ for $k\geq 3$. It can be checked that
the same holds for $k=2$. Hence,

$|f_{k}(\alpha)-f_{k}(2)|=|\alpha-2||f^{\prime}_{k}(\omega)|=\lambda|f^{\prime}_{k}(\omega)|<k\lambda<\dfrac{k}{2^{k-1}}=\dfrac{2k}{2^{k}}.$
(3.11)

Finally here, $2\alpha-1=2(2-\lambda)-1=3-2\lambda<3$ and

$\displaystyle
2\alpha-1=3-2\lambda>3-2\cdot\dfrac{1}{2^{k-1}}=3-\dfrac{4}{2^{k}},$

implying that

$\displaystyle|(2\alpha-1)-3|<\dfrac{4}{2^{k}}.$ (3.12)

From the above, if we write

$\alpha^{n-1}=2^{n-1}+\delta,\qquad
f_{k}(\alpha)=f_{k}(2)+\eta\quad\text{and}\quad 2\alpha-1=3+\phi,$

then inequalities (3.10), (3.11) and (3.12) become

$|\delta|<\frac{2^{n}}{2^{k/2}},\quad|\eta|<\frac{2k}{2^{k}}\quad\text{and}\quad|\phi|<\dfrac{4}{2^{k}}.$
(3.13)

Moreover, since $f_{k}(2)=1/2$ for all $k\geq 2$, we have

$\displaystyle f_{k}(\alpha)\alpha^{n-1}(2\alpha-1)$
$\displaystyle=\left(f_{k}(2)+\eta\right)(2^{n-1}+\delta)(3+\phi)$
$\displaystyle=\left(2^{n-2}+\frac{\delta}{2}+2^{n-1}\eta+\eta\delta\right)(3+\phi)$
$\displaystyle=3\cdot 2^{n-2}+\frac{3}{2}\delta+3\cdot
2^{n-1}\eta+3\eta\delta+2^{n-2}\phi+\frac{\delta}{2}\phi+2^{n-1}\eta\phi+\eta\delta\phi.$
(3.14)

Therefore, using (2.7) and relations (3.13) and (3.3), we get

$\displaystyle\left|p_{1}^{\beta_{1}}\cdots p_{s}^{\beta_{s}}-3\cdot
2^{n-2}\right|$
$\displaystyle=\left|\left(L^{(k)}_{n}-f_{k}(\alpha)\alpha^{n-1}(2\alpha-1)\right)+\left(\frac{3}{2}\delta+3\cdot
2^{n-1}\eta+3\eta\delta+2^{n-2}\phi+\frac{\delta}{2}\phi+2^{n-1}\eta\phi+\eta\delta\phi\right)\right|$
$\displaystyle<\frac{3}{2}+\dfrac{3\cdot 2^{n-1}}{2^{k/2}}+\frac{3\cdot
2^{n}k}{2^{k}}+\frac{3\cdot
2^{n+1}k}{2^{3k/2}}+\dfrac{2^{n}}{2^{k}}+\dfrac{2^{n+1}}{2^{3k/2}}+\dfrac{2^{n+2}k}{2^{2k}}+\dfrac{2^{n+3}k}{2^{5k/2}}$
$\displaystyle<3\cdot
2^{n-2}\left(\frac{1}{2^{n-1}}+\dfrac{2}{2^{k/2}}+\frac{4k}{2^{k}}+\frac{8k}{2^{3k/2}}+\dfrac{4/3}{2^{k}}+\dfrac{8/3}{2^{3k/2}}+\dfrac{16k/3}{2^{2k}}+\dfrac{32k/3}{2^{5k/2}}\right)$
$\displaystyle<3\cdot
2^{n-2}\left(\frac{1}{2^{k/2}}+\dfrac{2}{2^{k/2}}+\frac{5}{2^{k/2}}+\frac{4}{2^{k/2}}+\dfrac{2}{2^{k/2}}+\dfrac{3}{2^{k/2}}+\dfrac{8}{2^{k/2}}+\dfrac{11}{2^{k/2}}\right)$
$\displaystyle=3\cdot 2^{n-2}\frac{36}{2^{k/2}}.$

In the above, we used that $k\leq 2^{k-1}$ and that $k<(5/4)2^{k/2}$ for
$k\geq 2$. Dividing both sides above by $3\cdot 2^{n-2}$, having in mind that
$p_{1}=2$ and $p_{2}=3$, we get

$\displaystyle\left|p_{1}^{\beta_{1}-n+2}\cdot p_{2}^{\beta_{2}-1}\cdots
p_{s}^{\beta_{s}}-1\right|<\frac{36}{2^{k/2}}.$ (3.15)

Now, we intend to apply Theorem 2.1 on the left-hand side of (3.15). Let

$\Gamma_{1}=p_{1}^{\beta_{1}-n+2}\cdot p_{2}^{\beta_{2}-1}\cdots
p_{s}^{\beta_{s}}-1=e^{\Lambda_{1}}-1.$

Notice that $\Lambda_{1}\neq 0$, otherwise we would have
$L_{n}^{(k)}=p_{1}^{\beta_{1}}\ldots p_{s}^{\beta_{s}}=3\cdot 2^{n-2}$ but
since $n\geq k+1$, this contradicts (2.2). Here, $t:=s$,

$\displaystyle\gamma_{i}$
$\displaystyle:=p_{i}~{}~{}\text{for}~{}i=1,2,\ldots,s,~{}~{}~{}b_{1}:=\beta_{1}-n+2,~{}~{}~{}b_{2}:=\beta_{2}-1~{}~{}~{}b_{i}$
$\displaystyle:=\beta_{i}~{}~{}\text{for}~{}i=3,\ldots,s.$

The algebraic number field containing $\gamma_{i}$’s is
$\mathbb{K}:=\mathbb{Q}$, so we take $D=1$. Since $h(\gamma_{i})=\log
p_{i}\leq\log p_{s}$ for all $i=1,2,\ldots,s$, we take $A_{i}:=\log p_{s}$ for
all $i=1,2,\ldots,s$.

Again, $B\geq\max\\{|b_{i}|:i=1,2,\ldots,s\\}$. Notice that
$b_{i}=\beta_{i}<n+1$, for all $i=1,2,\ldots,s$ by relation (2.9), so we take
$B:=n+1$. Now, by Theorem 2.1,

$\displaystyle\log|\Gamma_{1}|$ $\displaystyle>-1.4\cdot 30^{s+3}\cdot
s^{4.5}\cdot 1^{2}(1+\log 1)(1+\log(n+1))\cdot(\log p_{s})^{s}$
$\displaystyle>-1.4\cdot 30^{s}\cdot 30^{3}\cdot s^{4.5}\cdot 2\log
2n\cdot(\log p_{s})^{s}$ $\displaystyle>-10^{5}\cdot 30^{s}s^{4.5}\log
n\cdot(\log p_{s})^{s}.$ (3.16)

Comparing (3.15) and (3.3), we get

$\displaystyle\dfrac{k}{2}\log 2-\log 36$ $\displaystyle<10^{5}\cdot
30^{s}s^{4.5}\log n\cdot(\log p_{s})^{s}$ $\displaystyle k$
$\displaystyle<3\cdot 10^{5}\cdot s^{4.5}\log n\cdot(60\log
s)^{s},~{}~{}\text{since}~{}p_{s}<s^{2},$ $\displaystyle<3\cdot 10^{5}\cdot
s^{4.5}(46s\log k)\cdot(60\log s)^{s},$

since $\log n<46s\log k$ in (3.1). Therefore, we can write

$\displaystyle\dfrac{k}{\log k}<1.4\cdot 10^{7}s^{5.5}\cdot(60\log s)^{s}.$

We again apply Lemma 2.4 with the data: $x:=k$, $m:=1$ and $T:=7\cdot
10^{6}s^{5.5}\cdot(60\log s)^{s}>(4m^{2})^{m}=4$, for $s\geq 2$. We get

$\displaystyle k$ $\displaystyle<2^{1}\cdot 1.4\cdot 10^{7}s^{5.5}\cdot(60\log
s)^{s}(\log(1.4\cdot 10^{7}s^{5.5}\cdot(60\log s)^{s})^{1}$
$\displaystyle=2.8\cdot 10^{7}s^{5.5}(60\log s)^{s}\left(\log(1.4\cdot
10^{7})+5.5\log s+s\log(60\log s)\right)$ $\displaystyle=2.8\cdot
10^{7}s^{5.5}(60\log s)^{s}\cdot s\log s\left(\dfrac{17}{s\log
s}+\dfrac{5.5}{s}+\dfrac{\log 60}{\log s}+\dfrac{\log\log s}{\log s}\right)$
$\displaystyle<6\cdot 10^{8}s^{6.5}(60\log s)^{s}\log s.$

As a result,

$\displaystyle\log k$ $\displaystyle<\log 6\cdot 10^{8}+6.5\log s+s\log(60\log
s)+\log\log s$ $\displaystyle<21+6.5\log s+s\log 60+s\log\log s+\log\log s$
$\displaystyle=s\log s\left(\dfrac{21}{s\log s}+\dfrac{6.5}{s}+\dfrac{\log
60}{\log s}+\dfrac{\log\log s}{\log s}+\dfrac{\log\log s}{s\log s}\right)$
$\displaystyle<26s\log s.$ (3.17)

To finish the proof, recall we are treating the case when $n<2^{k/2}$ ,
therefore $\log n<(k/2)\log 2<k$. This and relation (3.3) tell us that
$\log\log n<\log k<26s\log s$, hence $p_{s}>s\log s>(1/26)\log\log n$. This
completes the proof of Theorem 1.1.

##  4 Proof of Theorem 1.2

We proceed in a way similar as in Section 3. Specifically, we prove following
estimates.

######  Lemma 4.1.

If $P(L_{n}^{(k)})\leq 7$, then:

  1. (a)

The inequality

$n<1.4\cdot 10^{27}k^{7}(\log k)^{3},$

holds for $k\geq 2$ and $n\geq 3$.

  2. (b)

If $k>1000$, then

$k<1.64\cdot 10^{20}$ and $~{}n<4.6\cdot 10^{173}$.

###### Proof.

  1. (a)

To prove the first part, we use the same arguments used in Subsection 3.1.
Indeed, for $s=4$, we have from inequality (3.1) that

$\displaystyle\left|2^{a}\cdot 3^{b}\cdot 5^{c}\cdot
7^{d}\cdot(2\alpha-1)^{-1}\cdot\alpha^{-(n-1)}\cdot(f_{k}(\alpha))^{-1}-1\right|$
$\displaystyle<\dfrac{6}{\alpha^{n-1}},$ (4.1)

for which we obtain as before, by substituting $s=4$ in (3.6), that

$\displaystyle n+1$ $\displaystyle<1.21\cdot 10^{13}\cdot 30^{4}\cdot
4^{4.5}k^{3+4}(\log k)^{2}(\log 7)^{4}\log(n+1)$ $\displaystyle<7.2\cdot
10^{24}k^{7}(\log k)^{2}\log(n+1).$

In particular, we have

$\displaystyle\dfrac{n+1}{\log(n+1)}$ $\displaystyle<7.2\cdot
10^{24}k^{7}(\log k)^{2}.$

We now apply Lemma 2.4 with $x:=n+1$, $m:=1$, $T:=7.2\cdot 10^{24}k^{7}(\log
k)^{2}>(4m^{2})^{m}=4$ for $k\geq 2$. We get

$\displaystyle n+1$ $\displaystyle<2\cdot 7.2\cdot 10^{24}k^{7}(\log
k)^{2}\log(7.2\cdot 10^{24}k^{7}(\log k)^{2})$ $\displaystyle=1.44\cdot
10^{25}k^{7}(\log k)^{2}\left(\log(7.2\cdot 10^{24})+7\log k+2\log\log
k\right)$ $\displaystyle=1.44\cdot 10^{25}k^{7}(\log
k)^{3}\left(\dfrac{58}{\log k}+7+\dfrac{2\log\log k}{\log k}\right)$
$\displaystyle<1.4\cdot 10^{27}k^{7}(\log k)^{3}.$

  2. (b)

In the second part, if $k>1000$, then

$\displaystyle n<1.4\cdot 10^{27}k^{7}(\log k)^{3}<2^{k/2}.$

For this reason, we can use the same arguments from Subsection 3.3 relation
(3.15) to write

$\displaystyle\left|2^{a-n+2}\cdot 3^{b-1}\cdot 5^{c}\cdot
7^{d}-1\right|<\frac{36}{2^{k/2}},$ (4.2)

from which after applying Matveev’s result with $s=4$ as in Subsection 3.3 we
get

$\displaystyle k<3\cdot 10^{8}\cdot 4^{6.5}(60\log 4)^{4}\log 4<1.64\cdot
10^{20}.$

Lastly, we substitute this upper bound on $k$ in part (a) of Lemma 4.1 to get

$\displaystyle n$ $\displaystyle<1.4\cdot 10^{27}(1.64\cdot 10^{20})^{7}(\log
1.64\cdot 10^{20})^{3}<4.6\cdot 10^{173}.$

This completes the proof of Lemma 4.1. ∎

To complete the proof of Theorem 1.2, we proceed in two cases, that is, the
case $k\leq 1000$ and the case $k>1000$. We use similar analyses given on
pages 1363 and 1364 of [1].

###  4.1 The case $k\leq 1000$.

In this subsection, we treat the cases when $k\in[2,1000]$. Note that when
$k\leq 1000$, then $n<4.62\cdot 10^{50}$ by Lemma 4.1. The next step is to
reduce this large upper bound on $n$. To do this, we let

$\tau_{1}:=a\log 2+b\log 3+c\log 5+d\log
7-\log(2\alpha-1)-(n-1)\log\alpha-\log f_{k}(\alpha),$

so that (4.1) can be rewritten as

$|e^{\tau_{1}}-1|<\frac{6}{\alpha^{n-1}}.$ (4.3)

Observe that $\tau_{1}\neq 0$. Moreover, if $\tau_{1}>0$, then
$e^{\tau_{1}}-1>0$, so from (4.3) we obtain

$0<\tau_{1}<\frac{6}{\alpha^{n-1}},$

where we used the fact that $x\leq e^{x}-1$ for all $x\in\mathbb{R}$. Next, we
treat the case $\tau_{1}<0$. Note that if $n\geq 7$, then $6/\alpha^{n-1}<1/2$
for all $k\geq 2$. Thus, from (4.3), we get that $|e^{\tau_{1}}-1|<1/2$ or
$e^{\tau_{1}}<2$. Since $\tau_{1}<0$, we obtain

$0<|\tau_{1}|\leq
e^{|\tau_{1}|}-1=e^{|\tau_{1}|}|e^{\tau_{1}}-1|<\frac{12}{\alpha^{n-1}}.$

Thus, in all cases, the inequality

$|\tau_{1}|<\frac{12}{\alpha^{n-1}}$ (4.4)

holds for $k\geq 2$ and $n\geq 7$. Observe that $|\tau_{1}|$ is an expression
of the form

$|x_{1}\log 2+x_{2}\log 3+x_{3}\log 5+x_{4}\log
7+x_{5}\log(2\alpha-1)+x_{6}\log\alpha+x_{7}\log f_{k}(\alpha)|,$

where $x_{1}:=a$, $x_{2}:=b$, $x_{3}:=c$, $x_{4}:=d$, $x_{5}:=-1$,
$x_{6}:=-(n-1)$, $x_{7}:=-1$ are integers with

$\max\\{|x_{i}|:1\leq i\leq 7\\}<n<1.4\cdot 10^{27}k^{7}(\log k)^{3},$

where we used Lemma 4.1.

For each $k\in[2,1000]$, we used the LLL–algorithm to compute a lower bound
for the smallest nonzero number of the form $|\tau_{1}|$, with integer
coefficients $x_{i}$ not exceeding $1.4\cdot 10^{27}k^{7}(\log k)^{3}$ in
absolute value. Specifically, we consider the approximation lattice

$\mathcal{A}=\begin{pmatrix}1&0&0&0&0&0&0\\\ 0&1&0&0&0&0&0\\\ 0&0&1&0&0&0&0\\\
0&0&0&1&0&0&0\\\ 0&0&0&0&1&0&0\\\ 0&0&0&0&0&1&0\\\ \lfloor C\log
2\rfloor&\lfloor C\log 3\rfloor&\lfloor C\log 5\rfloor&\lfloor C\log
7\rfloor&\lfloor C\log(2\alpha-1)\rfloor&\lfloor C\log\alpha\rfloor&\lfloor
C\log f_{k}(\alpha)\rfloor\end{pmatrix},$

with $C:=10^{355}$ and choose $y:=\left(0,0,0,0,0,0,0\right)$. Now, by Lemma
2.2, we get

$l\left(\mathcal{L},y\right)^{2}>c_{1}^{2}=5.96\cdot 10^{106}.$

So, Lemma 2.3 gives $S=1.5\cdot 10^{102}$ and $T=1.7\cdot 10^{51}$. Since
$c_{1}^{2}\geq T^{2}+S$, then choosing $c_{3}:=12$ and $c_{4}:=\log\alpha$, we
get $n-1\leq 1448$.

Finally, we wrote a simple program in SageMath (see Appendix 1), to look at
$k$-generalized Lucas numbers for $2\leq k\leq 1000$ and $k+1\leq n\leq 1449$.
Instead of factoring the numbers fully, we checked if they could be divided by
$2$, $3$, $5$, and $7$ until we couldn’t divide them anymore. This way, we
found out if each number could be written using only these primes. The numbers
we got are the ones given in Theorem 1.2. This completes the analysis in the
case $k\in[2,1000]$.

###  4.2 The case $k>1000$

Lastly, we treat the case when $k>1000$. At this point, we need to reduce our
absolute upper bound on $k$, see Lemma 4.1, by using again the LLL–algorithm
described in Lemma 2.3. To do this, let

$\tau_{2}:=(a-n+2)\log 2+(b-1)\log 3+c\log 5+d\log 7,$

so that we can rewrite (4.2) as

$|e^{\tau_{2}}-1|<\frac{36}{2^{k/2}}.$ (4.5)

Again, it is clear that $\tau_{2}\neq 0$. If $\tau_{1}>0$, then
$e^{\tau_{1}}-1>0$, so from (4.5) we obtain

$0<\tau_{2}<\frac{36}{2^{k/2}},$

by similar arguments as before. If $\tau_{2}<0$, then we can note from (4.5)
that $36/2^{k/2}<1/2$ for all $k>1000$. Hence, it follows from (4.5) that
$|e^{\tau_{2}}-1|<1/2$ which implies $e^{\tau_{2}}<2$. Since $\tau_{2}<0$, we
obtain that

$0<|\tau_{2}|\leq
e^{|\tau_{2}|}-1=e^{|\tau_{2}|}|e^{\tau_{2}}-1|<\frac{72}{2^{k/2}}.$

Thus, in all cases, we have

$|\tau_{2}|<\frac{72}{2^{k/2}}.$ (4.6)

Like before, observe that $|\tau_{2}|$ is an expression of the form

$|x_{1}\log 2+x_{2}\log 3+x_{3}\log 5+x_{4}\log 7|,$

where $x_{1}:=a-n+2$, $x_{2}:=b-1$, $x_{3}:=c$, $x_{4}:=d$. From the second
part of Lemma 4.1, we have

$\max\\{|x_{i}|:1\leq i\leq 4\\}<n<4.6\times 10^{173}.$

At this point, we consider the approximation lattice

$\mathcal{A}=\begin{pmatrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\ \lfloor C\log
2\rfloor&\lfloor C\log 3\rfloor&\lfloor C\log 5\rfloor&\lfloor C\log
7\rfloor\end{pmatrix},$

with $C:=10^{695}$ and choose $y:=\left(0,0,0,0\right)$. By Lemma 2.2, we get

$l\left(\mathcal{L},y\right)^{2}>c_{1}^{2}=10^{350}.$

So, Lemma 2.3 gives $S=8.5\cdot 10^{347}$ and $T=9.2\cdot 10^{173}$. Since
$c_{1}^{2}\geq T^{2}+S$, then choosing $c_{3}:=72$ and $c_{4}:=\log 2$, we get
$k/2\leq 1733$. This implies that $k\leq 3466$ and the first part of Lemma 4.1
tells us that $n<4.6\cdot 10^{54}$.

With this new upper bound for $n$ we repeat the LLL–algorithm once again to
get a lower bound of $|\tau_{2}|$, where now the coefficients $x_{i}$ are
integers satisfying

$\max\\{|x_{i}|:1\leq i\leq 4\\}<n<4.6\cdot 10^{54}.$

With the same approximation lattice and $C:=10^{220}$, we get
$c_{1}^{2}=10^{111}$, $S=8.464\cdot 10^{109}$ and $T=9.2\cdot 10^{54}$. We
then obtain that $k\leq 1106$. After repeating this process 2 more times, we
finally find that $k<1000$, which is a contradiction. Thus, Theorem 1.2 is
proved. ∎

## Acknowledgments

The first author thanks the Eastern Africa Universities Mathematics Programme
(EAUMP) for funding his doctoral studies. The second author worked on this
paper during a fellowship at STIAS in the second part of 2023. This author
thanks STIAS for hospitality and support.

## Addresses

1 Department of Mathematics, School of Physical Sciences, College of Natural
Sciences, Makerere University, Kampala, Uganda

Email<EMAIL_ADDRESS>

2 School of Mathematics, Wits University, Johannesburg, South Africa

Email<EMAIL_ADDRESS>
## References

  * [1] Bravo, J. J., & Luca, F. (2013). On the largest prime factor of the $k$–Fibonacci numbers, International Journal of Number Theory 9, 1351–1366.
  * [2] Bravo, J. J., & Luca, F. (2014). Repdigits in $k$–Lucas sequences. Proceedings-Mathematical Sciences 124, 141–154.
  * [3] Cassels, J. W. S. (2012). An introduction to the geometry of numbers. Springer Science & Business Media.
  * [4] de Weger, B. M. (1987). Solving exponential Diophantine equations using lattice basis reduction algorithms, Journal of Number Theory 26, 325–367.
  * [5] Gómez–Ruiz, C. A., & Luca, F. (2016). Multiplicative independence in $k-$generalized Fibonacci sequences. Lithuanian Mathematical Journal 56 503–517.
  * [6] Gúzman–Sanchez, S., & Luca, F. (2014). Linear combinations of factorials and S-units in a binary recurrence sequence. Annales Mathématiques du Québec 38, 169–188.
  * [7] Lenstra, A. K., Lenstra, H. W., & LovÃ¡sz, L. (1982). Factoring polynomials with rational coefficients. Mathematisches Annalen 261, 515–534.
  * [8] Matveev, E. M. (2000). An explicit lower bound for a homogeneous rational linear form in the logarithms of algebraic numbers. II. Izvestiya: Mathematics 64, 1217.
  * [9] Miles, E. P. (1960). Generalized Fibonacci numbers and associated matrices. The American Mathematical Monthly 67, 745–752.
  * [10] Miller, M. D. (1971). On generalized Fibonacci numbers. The American Mathematical Monthly 78 1108-1109.
  * [11] Rihane, S. E., Faye, B., Luca, F., & TogbÃ©, A. (2020). Powers of Two in Generalized Lucas Sequences, The Fibonacci Quarterly 58, 254-260.
  * [12] Rosser, J. B., & Schoenfeld, L. (1962). Approximate formulas for some functions of prime numbers. Illinois Journal of Mathematics 6, 64–94.
  * [13] Smart, N. P. (1998). The algorithmic resolution of Diophantine equations: a computational cookbook (Vol. 41). Cambridge University Press.
  * [14] Wolfram, D. A. (1998). Solving generalized Fibonacci recurrences. The Fibonacci Quarterly 36, 129–145.

## Appendices

### Appendix 1

    Ψ# Define a memoization dictionary to store previously computed values
    Ψmemo = {}
    Ψ
    Ψdef k_generalized_lucas_iterative(n, k):
    Ψ# Base cases
    Ψif n == 0:
    Ψreturn 2
    Ψelif n == 1:
    Ψreturn 1
    Ψelif n < 2 - k:
    Ψreturn 0
    Ψ
    Ψ# Check if we have already computed the value
    Ψif (n, k) in memo:
    Ψreturn memo[(n, k)]
    Ψ
    Ψ# Initialize a list with the base cases
    Ψlucas_nums = [0] * (2 - k) + [2, 1] + [None] * (n - 1)
    Ψ
    Ψ# Compute the k-generalized Lucas numbers iteratively
    Ψfor i in range(2, n + 1):
    Ψlucas_nums[i] = sum(lucas_nums[i - j] for j in range(1, k + 1) if i - j >= 0)
    Ψ# Store the computed number in the memo dictionary
    Ψmemo[(i, k)] = lucas_nums[i]
    Ψ
    Ψreturn lucas_nums[n]
    Ψ
    Ψdef is_of_form_2a_3b_5c_7d(lucas_val):
    Ψfor prime in [2, 3, 5, 7]:
    Ψwhile lucas_val % prime == 0:
    Ψlucas_val //= prime
    Ψreturn lucas_val == 1
    Ψ
    Ψ# Check for solutions
    Ψfor k in range(2, 1001):
    Ψfor n in range(k + 1, 1450):
    Ψlucas_val = k_generalized_lucas_iterative(n, k)
    Ψif is_of_form_2a_3b_5c_7d(lucas_val):
    Ψprint(f"For k={k}, n={n}: L_n^{(k)} = {lucas_val}")