Goldbach-Linnik type problems involving one prime,

four prime cubes and powers of 2

Xue Han and Huafeng Liu

School of Mathematics and Statistics, Shandong Normal University

Jinan 250358, Shandong, China

Email<EMAIL_ADDRESS><EMAIL_ADDRESS>

Abstract. In this paper, we prove that every pair of sufficiently large odd
integers can be represented in the form of a pair of one prime, four prime
cubes and $48$ powers of $2$.

Keywords and phrases. Goldbach-Linnik type problem, the Hardy-Littlewood
method, powers of $2$

Mathematics Subject Classification (2020). 11P05, 11P32, 11P55

##  1 Introduction

In 1950s, Linnik [6, 7] approximated the even Goldbach conjecture in a
different way by proving that every sufficiently large even integer $N$ can be
represented in the form of two primes and $k_{1}$ powers of 2, namely

$N=p_{1}+p_{2}+2^{v_{1}}+2^{v_{2}}+\cdots+2^{v_{k_{1}}}.$ (1.1)

It can be easily deduced that (1.1) with $k_{1}=0$ is equivalent to the even
Goldbach conjecture. In 1998, Liu, Liu and Wang [10] first got the explicit
value of $k_{1}$ and showed that $k_{1}=54000$ is admissible in (1.1). Later,
the value of $k_{1}$ was improved by many scholars. Up to now the best result
is $k_{1}=8$ established by Pintz and Ruzsa [16].

In 2001, Liu and Liu [9] proved that every sufficiently large even integer $N$
can be written as a sum of eight prime cubes and $k_{2}$ powers of $2$, namely

$N=p_{1}^{3}+p_{2}^{3}+\cdots+p_{8}^{3}+2^{v_{1}}+2^{v_{2}}+\cdots+2^{v_{k_{2}}}.$
(1.2)

In 2010, Liu and Lü [14] proved that $k_{2}=358$ is admissible in (1.2).
Subsequently, the value of $k_{2}$ was improved by many scholars. So far the
best result is $k_{2}=28$ established by the authors [4].

As a hybrid problem of (1.1) and (1.2), Liu and Lü [15] proved that every
sufficiently large odd integer $N$ can be written as a sum of one prime, four
prime cubes and $k_{3}=106$ powers of $2$, namely

$N=p_{1}+p_{2}^{3}+p_{3}^{3}+p_{4}^{3}+p_{5}^{3}+2^{v_{1}}+2^{v_{2}}+\cdots+2^{v_{k_{3}}}.$
(1.3)

Recently, Ching and Tsang [3] proved that $k_{3}=15$ is admissible.

In analytic number theory, when we have a method of handling a representation
problem such as (1.3) described above, it is meaningful and interesting to
examine to what extent the method can be applied to the pairs of corresponding
forms. For example, Liu and Tsang [13] studied the simultaneous representation
of pairs of linear equations in three prime variables. In this paper, we
consider the simultaneous representation of pairs of sufficiently large odd
integers $N_{1}$ and $N_{2}$ satisfying $N_{1}\asymp N_{2}$ in the form

$\left\\{\begin{array}[]{l}N_{1}=p_{1}+p_{2}^{3}+p_{3}^{3}+p_{4}^{3}+p_{5}^{3}+2^{v_{1}}+2^{v_{2}}+\cdots+2^{v_{k}},\\\
N_{2}=p_{6}+p_{7}^{3}+p_{8}^{3}+p_{9}^{3}+p_{10}^{3}+2^{v_{1}}+2^{v_{2}}+\cdots+2^{v_{k}},\end{array}\right.$
(1.4)

where $k$ is a positive integer. We shall give the acceptable value of $k$
such that the equations (1.4) are solvable in the following theorem.

######  Theorem 1.

The equations (1.4) with $k=48$ are solvable for every pair of sufficiently
large odd integers $N_{1}$ and $N_{2}$ with $N_{1}\asymp N_{2}$.

Result of this type was also considered by Chen [2] who proved that $k=231$ is
acceptable in (1.4). Our result largely improves Chen’s result.

To prove Theorem 1, we mainly apply the Hardy-Littlewood method. The key point
is to transfer the weighted number of solutions $\mathrm{R}(N_{1},N_{2})$ (see
(2.10)) of (1.4) to a positive lower bound of $k$ that satisfies
$\mathrm{R}(N_{1},N_{2})>0$. On the major arcs, we establish a detailed
numerical estimate of the singular series on average by a meticulous
calculation (see Lemma 3.3). In order to handle the minor arcs, we prove a new
estimate for the integrals involving exponential sums (see Lemma 3.8). Also
the new value of $\lambda$ in the estimate of the Lebesgue measure of the set
$\mathscr{E}_{\lambda}$ in Lemma 3.10 plays an important role.

######  Notation.

Throughout this paper, the letter $p$, with or without subscripts, always
represents a prime. We write $e(x)=e^{2\pi ix}$, and $n\sim N$ means $N<n\leq
2N$. The letter $\epsilon$ denotes an arbitrarily small positive constant,
whose value may not be the same at different occurrences.

##  2 Outline of the proof

In this section, we give the outline of the proof of Theorem 1 by applying the
Hardy-Littlewood method. Throughout this paper, we always take the subscript
$i=1,2$. Let

$P_{i}=N_{i}^{\frac{1}{9}-2\epsilon},\quad
Q_{i}=N_{i}^{\frac{8}{9}+\epsilon},\quad L=\frac{\log(N_{1}/\log N_{1})}{\log
2}.$ (2.1)

Then we define the major arcs $\mathfrak{M}_{i}$ and the minor arcs
$\mathfrak{m}_{i}$ as

$\mathfrak{M}_{i}=\bigcup_{1\leq q_{i}\leq
P_{i}}\bigcup_{\begin{subarray}{c}1\leq a_{i}\leq q_{i}\\\
\left(a_{i},q_{i}\right)=1\end{subarray}}\mathfrak{M}_{i}\left(a_{i},q_{i}\right),\quad\mathfrak{m}_{i}=[0,1]\backslash\mathfrak{M}_{i},$
(2.2)

where

$\mathfrak{M}_{i}\left(a_{i},q_{i}\right)=\left\\{\alpha_{i}\in[0,1]:\left|\alpha_{i}-\frac{a_{i}}{q_{i}}\right|\leq\frac{1}{q_{i}Q_{i}}\right\\}$

and

$1\leq a_{i}\leq q_{i}\leq Q_{i},\ \ (a_{i},q_{i})=1.$

Further, by a similar argument in Kong and Liu [5] we define

$\mathfrak{M}=\mathfrak{M}_{1}\times\mathfrak{M}_{2}=\left\\{\left(\alpha_{1},\alpha_{2}\right)\in[0,1]^{2}:\alpha_{1}\in\mathfrak{M}_{1},\alpha_{2}\in\mathfrak{M}_{2}\right\\}$
(2.3)

and

$\mathfrak{m}=[0,1]^{2}\backslash\mathfrak{M}.$ (2.4)

Let

$U_{i}=\frac{1}{2}\left((1-\eta)N_{i}\right)^{\frac{1}{3}},\quad
V_{i}=\frac{1}{2}(\eta N_{i})^{\frac{1}{3}},\quad W_{i}=U_{i}^{\frac{5}{18}},$
(2.5)

where $\eta$ is a sufficiently small positive constant. We set

$f\left(\alpha_{i},N_{i}\right)=\sum_{p\leq N_{i}}(\log
p)e\left(p\alpha_{i}\right),$ (2.6)
$S_{3}\left(\alpha_{i},U_{i}\right)=\sum_{p\sim U_{i}}(\log
p)e\left(p^{3}\alpha_{i}\right),$ (2.7)
$S_{3}\left(\alpha_{i},V_{i}\right)=\sum_{p\sim V_{i}}(\log
p)e\left(p^{3}\alpha_{i}\right),$ (2.8)
$S_{3}\left(\alpha_{i},W_{i}\right)=\sum_{p\sim W_{i}}(\log
p)e\left(p^{3}\alpha_{i}\right),$ (2.9) $G\left(\alpha_{i}\right)=\sum_{4\leq
v\leq
L}e\left(2^{v}\alpha_{i}\right),\quad\mathscr{E}_{\lambda}=\left\\{(\alpha_{1},\alpha_{2})\in[0,1]^{2}:|G(\alpha_{1}+\alpha_{2})|\geq\lambda
L\right\\}.$

Then we let

$\mathrm{R}(N_{1},N_{2})=\sum(\log p_{1})(\log p_{2})\cdots(\log p_{10})$
(2.10)

denote the number of solutions of (1.4), which are weighted by $(\log
p_{1})(\log p_{2})\cdots(\log p_{10})$, in
$(p_{1},p_{2},\ldots,p_{10},v_{1},v_{2},\ldots,v_{k})$ such that

$\displaystyle p_{1}\leq N_{1},\quad p_{2}\sim U_{1},\quad p_{3}\sim
V_{1},\quad p_{4},p_{5}\sim W_{1},$ $\displaystyle p_{6}\leq N_{2},\quad
p_{7}\sim U_{2},\quad p_{8}\sim V_{2},\quad p_{9},p_{10}\sim W_{2},$
$\displaystyle 4\leq v_{1},v_{2},\ldots,v_{k}\leq L.$

Thus by the definitions of $\mathfrak{M},\mathfrak{m}$,
$\mathscr{E}_{\lambda}$ and the orthogonality, we can write (2.10) as

$\displaystyle\mathrm{R}$ $\displaystyle\left(N_{1},N_{2}\right)$ (2.11)
$\displaystyle=$
$\displaystyle\left(\iint\limits_{\mathfrak{M}}+\iint\limits_{\mathfrak{m}\cap\mathscr{E}_{\lambda}}+\iint\limits_{\mathfrak{m}\backslash\mathscr{E}_{\lambda}}\right)f\left(\alpha_{1},N_{1}\right)S_{3}\left(\alpha_{1},U_{1}\right)S_{3}\left(\alpha_{1},V_{1}\right)S_{3}^{2}\left(\alpha_{1},W_{1}\right)f\left(\alpha_{2},N_{2}\right)$
$\displaystyle\times
S_{3}\left(\alpha_{2},U_{2}\right)S_{3}\left(\alpha_{2},V_{2}\right)S_{3}^{2}\left(\alpha_{2},W_{2}\right)G^{k}\left(\alpha_{1}+\alpha_{2}\right)e\left(-\alpha_{1}N_{1}-\alpha_{2}N_{2}\right)\mathrm{d}\alpha_{1}\mathrm{d}\alpha_{2}$
$\displaystyle:=$
$\displaystyle\mathrm{R}_{1}\left(N_{1},N_{2}\right)+\mathrm{R}_{2}\left(N_{1},N_{2}\right)+\mathrm{R}_{3}\left(N_{1},N_{2}\right).$

In the following sections, we shall give the desired estimates for these three
terms $\mathrm{R}_{r}\left(N_{1},N_{2}\right),r=1,2,3$ at the right side of
(2.11) and thus determine the acceptable value of $k$.

##  3 Auxiliary lemmas

In this section, we give some auxiliary lemmas which will be used in the proof
of Theorem 1. Let $j$ be a positive integer throughout this section. Let also

$C_{j}(q,a)=\sum_{\begin{subarray}{c}m=1\\\
(m,q)=1\end{subarray}}^{q}e\left(\frac{am^{j}}{q}\right),\
A(n,q)=\frac{1}{\varphi^{5}(q)}\sum_{\begin{subarray}{c}a=1\\\
(a,q)=1\end{subarray}}^{q}C_{1}(q,a)C_{3}^{4}(q,a)e\left(-\frac{an}{q}\right)$
(3.1)

and

$\mathfrak{S}(n)=\sum_{q=1}^{\infty}A(n,q).$ (3.2)

By direct calculation, we have $C_{1}(q,a)=\mu(q)$.

######  Lemma 3.1.

Let $\mathfrak{M}_{i}$, $f(\alpha_{i},N_{i})$,
$S_{3}\left(\alpha_{i},U_{i}\right)$, $S_{3}\left(\alpha_{i},V_{i}\right)$ and
$S_{3}\left(\alpha_{i},W_{i}\right)$ be defined as in (2.2), (2.6), (2.7),
(2.8) and (2.9), respectively. Then for $2\leq n_{i}\leq N_{i}$, we have

$\int\limits_{\mathfrak{M}_{i}}f(\alpha_{i},N_{i})S_{3}(\alpha_{i},U_{i})S_{3}(\alpha_{i},V_{i})S_{3}^{2}(\alpha_{i},W_{i})e\left(-n_{i}\alpha_{i}\right)\mathrm{d}\alpha_{i}=\frac{1}{3^{4}}\mathfrak{S}(n_{i})\mathfrak{J}(n_{i})+O\left(U_{i}V_{i}W_{i}^{2}L^{-1}\right),$

where $\mathfrak{S}\left(n_{i}\right)$ is defined as (3.2) and satisfies
$\mathfrak{S}\left(n_{i}\right)\gg 1$ for $n_{i}\equiv 1\pmod{2}$, and
$\mathfrak{J}\left(n_{i}\right)$ is defined as

$\mathfrak{J}(n_{i}):=\sum_{\begin{subarray}{c}m_{1}+m_{2}+\cdots+m_{5}=n_{i}\\\
U_{i}^{3}<m_{2}\leq 8U_{i}^{3}\\\ V_{i}^{3}<m_{3}\leq 8V_{i}^{3}\\\
W_{i}^{3}<m_{4},m_{5}\leq
8W_{i}^{3}\end{subarray}}\left(m_{2}m_{3}m_{4}m_{5}\right)^{-\frac{2}{3}}$

and satisfies $U_{i}V_{i}W_{i}^{2}\ll\mathfrak{J}\left(n_{i}\right)\ll
U_{i}V_{i}W_{i}^{2}$.

###### Proof.

The proof of this lemma is a standard application of the iterative argument
developed by Liu and Zhan (see [8, 12], etc.). Thus we omit its proof here. ∎

######  Lemma 3.2.

For $(1-\eta)N_{i}\leq n_{i}\leq N_{i}$, we have

$\mathfrak{J}(n_{i})\geq 3^{4}(\sqrt[3]{7}-1)(1-\eta)^{4}U_{i}V_{i}W_{i}^{2}.$

###### Proof.

The domain of the sum $\mathfrak{J}(n_{i})$ can be written as

$\mathfrak{D}=\left\\{\left(m_{1},m_{2},\ldots,m_{5}\right):\begin{array}[]{l}m_{1}\leq
N_{i},U_{i}^{3}<m_{2}\leq 8U_{i}^{3},V_{i}^{3}<m_{3}\leq 8V_{i}^{3},\\\
W_{i}^{3}<m_{4},m_{5}\leq
8W_{i}^{3},m_{1}=n_{i}-m_{2}-m_{3}-m_{4}-m_{5}\end{array}\right\\}.$

Let

$\mathfrak{D}^{*}=\left\\{\left(m_{1},m_{2},\ldots,m_{5}\right):\begin{array}[]{l}U_{i}^{3}<m_{2}\leq
7U_{i}^{3},V_{i}^{3}<m_{3}\leq 8V_{i}^{3},\\\ W_{i}^{3}<m_{4},m_{5}\leq
8W_{i}^{3},m_{1}=n_{i}-m_{2}-m_{3}-m_{4}-m_{5}\end{array}\right\\}.$

For $(m_{1},m_{2},\ldots,m_{5})\in\mathfrak{D}^{*}$, we deduce from
$(1-\eta)N_{i}\leq n_{i}\leq N_{i}$ that

$m_{1}=n_{i}-m_{2}-m_{3}-m_{4}-m_{5}\leq N_{i}.$

Thus $\mathfrak{D}^{*}$ is a subset of $\mathfrak{D}$. Then we have

$\displaystyle\mathfrak{J}(n_{i})$
$\displaystyle\geq\sum_{(m_{2},m_{3},m_{4},m_{5})\in\mathfrak{D}^{*}}(m_{2}m_{3}m_{4}m_{5})^{-\frac{2}{3}}$
$\displaystyle\geq\sum_{U_{i}^{3}<m_{2}\leq
7U_{i}^{3}}m_{2}^{-\frac{2}{3}}\sum_{V_{i}^{3}<m_{3}\leq
8V_{i}^{3}}m_{3}^{-\frac{2}{3}}\sum_{W_{i}^{3}<m_{4},m_{5}\leq
8U_{i}^{3}}(m_{4}m_{5})^{-\frac{2}{3}}$ $\displaystyle\geq
3^{4}(\sqrt[3]{7}-1)(1-\eta)^{4}U_{i}V_{i}W_{i}^{2},$

which completes the proof of this lemma. ∎

######  Lemma 3.3.

Let $\Xi(N_{i},k)=\\{n_{i}\geq
2:n_{i}=N_{i}-2^{v_{1}}-2^{v_{2}}-\cdots-2^{v_{k}},4\leq
v_{1},v_{2},\ldots,v_{k}\leq L\\}$ with $k\geq 45$. Then for $N_{1}\equiv
N_{2}\equiv 1\pmod{2}$, we have

$\sum_{\begin{subarray}{c}n_{1}\in\Xi\left(N_{1},k\right)\\\
n_{2}\in\Xi\left(N_{2},k\right)\\\ n_{1}\equiv n_{2}\equiv
1\pmod{2}\end{subarray}}\mathfrak{S}\left(n_{1}\right)\mathfrak{S}\left(n_{2}\right)\geq
3.71280584L^{k}.$ (3.3)

###### Proof.

From (3.11) in Liu and Lü [15], we know that $A(n_{i},p)$ is multiplicative
and

$\mathfrak{S}(n_{i})=\prod_{p\geq 2}(1+A(n_{i},p)).$ (3.4)

With the help of computer, we have

$\displaystyle 1+A(n_{i},3)\geq 0.9375,\ 1+A(n_{i},5)\geq 0.99609375,\
1+A(n_{i},7)\geq 0.72916666,$ $\displaystyle 1+A(n_{i},11)\geq 0.9999,\
1+A(n_{i},13)\geq 0.93098958,\ 1+A(n_{i},17)\geq 0.99998474,$ $\displaystyle
1+A(n_{i},19)\geq 0.98225308,\ 1+A(n_{i},23)\geq 0.99999573,\
1+A(n_{i},29)\geq 0.99999837,$ $\displaystyle 1+A(n_{i},31)\geq 0.99303333,\
1+A(n_{i},37)\geq 0.99387538,\ 1+A(n_{i},41)\geq 0.9999996,$
$\displaystyle\cdots\cdots$ $\displaystyle 1+A(n_{i},193)\geq 0.99982076,\
1+A(n_{i},197)\geq 0.99999999,\ 1+A(n_{i},199)\geq 0.99983815.$

Thus, we can find that when $3\leq p\leq 200$ and $p\neq 3,7,13,19$, the value
of $1+A(n_{i},p)$ is very close to 1. In addition, we can obtain

$(1+A(n_{i},5))(1+A(n_{i},11))(1+A(n_{i},17))\prod_{23\leq p\leq
200}1+A(n_{i},p)\geq 0.96976071.$ (3.5)

From (3.15) and (3.17) in Liu and Lü [15], we note that if $p\geq 5$, $p\equiv
2\pmod{3}$ and $(a,p)=1$, then

$1+A(n_{i},p)=\begin{cases}1-\frac{1}{(p-1)^{4}},&p\mid n_{i},\\\
1+\frac{1}{(p-1)^{5}},&p\nmid n_{i},\end{cases}$

and if $p\geq 13$ and $p\equiv 1\pmod{3}$, then

$1+A(n_{i},p)>1-\frac{(2\sqrt{p}+1)^{4}}{(p-1)^{4}}.$

Then with the help of computer again we get

$\displaystyle\prod_{\begin{subarray}{c}200\leq
p<10^{6}\end{subarray}}(1+A(n_{i},p))$ (3.6)
$\displaystyle\geq\prod_{\begin{subarray}{c}200\leq p<10^{6}\\\ p\equiv
1\pmod{3}\end{subarray}}\left(1-\frac{(2\sqrt{p}+1)^{4}}{(p-1)^{4}}\right)\prod_{\begin{subarray}{c}200\leq
p<10^{6}\\\ p\equiv 2\pmod{3}\\\ p\mid
n\end{subarray}}\left(1-\frac{1}{(p-1)^{4}}\right)\prod_{\begin{subarray}{c}200\leq
p<10^{6}\\\ p\equiv 2\pmod{3}\\\ p\nmid
n\end{subarray}}\left(1+\frac{1}{(p-1)^{5}}\right)$
$\displaystyle\geq\prod_{\begin{subarray}{c}200\leq p<10^{6}\\\ p\equiv
1\pmod{3}\end{subarray}}\left(1-\frac{(2\sqrt{p}+1)^{4}}{(p-1)^{4}}\right)\prod_{\begin{subarray}{c}200\leq
p<10^{6}\\\ p\equiv
2\pmod{3}\end{subarray}}\left(1-\frac{1}{(p-1)^{4}}\right)$ $\displaystyle\geq
0.99351588.$

From Liu and Lü [15, p. 726], we have that if $p\geq 1138$ and $p\equiv
1\pmod{3}$, then

$1-\frac{(2\sqrt{p}+1)^{4}}{(p-1)^{4}}\geq\left(1-\frac{1}{(p-1)^{2}}\right)^{17}.$

Then we get

$\displaystyle\prod_{p\geq 10^{6}}(1+A(n_{i},p))$
$\displaystyle\geq\prod_{\begin{subarray}{c}p\geq 10^{6}\\\ p\equiv
1\pmod{3}\end{subarray}}\left(1-\frac{1}{(p-1)^{2}}\right)^{17}\prod_{\begin{subarray}{c}p\geq
10^{6}\\\ p\equiv 2\pmod{3}\end{subarray}}\left(1-\frac{1}{(p-1)^{4}}\right)$
(3.7) $\displaystyle>\prod_{m\geq
10^{6}+1}\left(1-\frac{1}{(m-1)^{2}}\right)^{17}\geq 0.999983.$

Form (3.5), (3.6) and (3.7), we have

$(1+A(n_{i},5))(1+A(n_{i},11))(1+A(n_{i},17))\prod_{p\geq
23}(1+A(n_{i},p))\geq 0.96345628:=C.$ (3.8)

Let $q=3\times 7\times 13\times 19=5187$, by (3.4) and (3.8) we get

$\displaystyle\sum_{\begin{subarray}{c}n_{1}\in\Xi\left(N_{1},k\right)\\\
n_{2}\in\Xi\left(N_{2},k\right)\\\ n_{1}\equiv n_{2}\equiv
1\pmod{2}\end{subarray}}\mathfrak{S}\left(n_{1}\right)\mathfrak{S}\left(n_{2}\right)$
(3.9)
$\displaystyle\geq\left(2C\right)^{2}\sum_{\begin{subarray}{c}n_{1}\in\Xi\left(N_{1},k\right)\\\
n_{2}\in\Xi\left(N_{2},k\right)\\\ n_{1}\equiv n_{2}\equiv
1\pmod{2}\end{subarray}}\prod_{1\leq i\leq
2}\prod_{p_{i}=3,7,13,19}\left(1+A\left(n_{i},p_{i}\right)\right)$
$\displaystyle\geq\left(2C\right)^{2}\sum_{\begin{subarray}{c}1\leq j\leq
q\end{subarray}}\sum_{\begin{subarray}{c}n_{1}\in\Xi\left(N_{1},k\right)\\\
n_{2}\in\Xi\left(N_{2},k\right)\\\ n_{1}\equiv n_{2}\equiv 1\pmod{2}\\\
n_{1}\equiv n_{2}\equiv j\pmod{q}\end{subarray}}\prod_{1\leq i\leq
2}\prod_{p_{i}=3,7,13,19}\left(1+A\left(j,p_{i}\right)\right)$
$\displaystyle\geq\left(2C\right)^{2}\sum_{1\leq j\leq
q}\prod_{p=3,7,13,19}(1+A(j,p))^{2}\sum_{\begin{subarray}{c}n_{1}\in\Xi\left(N_{1},k\right)\\\
n_{1}\equiv 1\pmod{2}\\\ n_{1}\equiv j\pmod{q}\end{subarray}}1.$

To estimate the innermost sum at the right side of (3.9), we take a similar
argument to Lemma 4.4 in Zhao [18]. We can deduce that

$S:=\sum_{\begin{subarray}{c}n_{1}\in\Xi\left(N_{1},k\right)\\\ n_{1}\equiv
1\pmod{2}\\\ n_{1}\equiv
j\pmod{q}\end{subarray}}1=\left(\frac{L}{\delta(q)}+O(1)\right)^{k}\sum_{\begin{subarray}{c}1\leq
v_{1},v_{2},\ldots,v_{k}\leq\delta(q)\\\
2^{v_{1}}+2^{v_{2}}+\cdots+2^{v_{k}}\equiv N-j\pmod{q}\end{subarray}}1,$

where $\delta(q)$ denotes the smallest positive integer $\delta$ such that
$2^{\delta}\equiv 1\pmod{q}$. Noting that

$S=\frac{1}{q}\left(\frac{L}{\delta(q)}+O(1)\right)^{k}\sum_{t=0}^{q-1}e\left(\frac{t(N-j)}{q}\right)\theta^{k}(t),$

we get

$\displaystyle S$
$\displaystyle\geq\frac{1}{q}\left(\frac{L}{\delta(q)}+O(1)\right)^{k}\left(\delta(q)^{k}-(q-1)\left(\max_{0<t\leq
q-1}\left|\theta(t)\right|\right)^{k}\right)$
$\displaystyle\geq\frac{L^{k}}{q}\left(1-(q-1)\left(\frac{\max\limits_{0<t\leq
q-1}\left|\theta(t)\right|}{\delta(q)}\right)^{k}\right)+O\left(L^{k-1}\right),$

where $\theta(t)=\sum\limits_{1\leq
s\leq\delta(q)}e\left(\frac{t2^{s}}{q}\right)$. Recalling the definition of
$\delta(q)$, we have

$\delta(q)=36\quad\text{and}\quad\max_{0<t\leq
q-1}|\theta(t)|=18.00001822\ldots.$

Therefore, we can get

$S\geq 0.00019278L^{k}.$

From (3.9) and

$\displaystyle\sum_{1\leq j\leq p}(1+A(j,p))^{2}$
$\displaystyle=p+2\sum_{1\leq j\leq p}A(j,p)+\sum_{1\leq j\leq p}(A(j,p))^{2}$
$\displaystyle=p+\sum_{1\leq j\leq p}(A(j,p))^{2}$ $\displaystyle\geq p,$

we have

$\begin{split}\sum_{\begin{subarray}{c}n_{1}\in\Xi\left(N_{1},k\right)\\\
n_{2}\in\Xi\left(N_{2},k\right)\\\ n_{1}\equiv n_{2}\equiv
1\pmod{2}\end{subarray}}\mathfrak{S}\left(n_{1}\right)\mathfrak{S}\left(n_{2}\right)\geq\left(2C\right)^{2}\cdot
0.00019278\cdot qL^{k}\geq 3.71280584L^{k},\end{split}$

which completes the proof of this lemma. ∎

######  Lemma 3.4.

Suppose that $\alpha_{i}$ is a real number, and that there exist integers
$a_{i}\in\mathbb{Z}$ and $q_{i}\in\mathbb{N}$ with

$(a_{i},q_{i})=1,\quad 1\leq q_{i}\leq
N_{i}^{\frac{1}{2}},\quad|q_{i}\alpha_{i}-a_{i}|\leq N_{i}^{-\frac{1}{2}}.$

Then we have

$S_{3}(\alpha_{i},X)\ll
X^{1-\frac{1}{12}+\varepsilon}+\frac{X^{1+\varepsilon}}{\sqrt{q_{i}\left(1+N_{i}\left|\alpha_{i}-\frac{a_{i}}{q_{i}}\right|\right)}},$
(3.10)

where $X$ can be taken as $U_{i}$ or $V_{i}$.

###### Proof.

This lemma is Lemma $2.3$ in Zhao [17]. ∎

######  Lemma 3.5.

Let $\mathfrak{m}_{i}$ be defined as in (2.2). Then we have

$\max_{\alpha_{i}\in\mathfrak{m}_{i}}|S_{3}(\alpha_{i},U_{i})|\ll
N_{i}^{\frac{11}{36}+\epsilon},$ (3.11)
$\max_{\alpha_{i}\in\mathfrak{m}_{i}}|S_{3}(\alpha_{i},V_{i})|\ll
N_{i}^{\frac{11}{36}+\epsilon}.$ (3.12)

###### Proof.

The proof of (3.12) is similar to that of (3.11), so we only present the proof
of (3.11). By Dirichlet’s lemma on rational approximations, we can deduce that
for any real number $\alpha_{i}\in\mathfrak{m}_{i}$, there exist integers
$a_{i}$ and $q_{i}$ such that

$\alpha_{i}=\frac{a_{i}}{q_{i}}+\lambda_{i},\ 1\leq
q_{i}\leq\mathscr{Q}_{i}=N_{i}^{\frac{1}{2}},\
|\lambda_{i}|\leq\frac{1}{q_{i}\mathscr{Q}_{i}},\ (a_{i},q_{i})=1.$

Since $\alpha_{i}\in\mathfrak{m}_{i}$, based on (2.1) and (2.2), we observe
that if $q_{i}\leq P_{i}=N_{i}^{\frac{1}{9}-2\epsilon}$, then
$|\lambda_{i}|>\frac{1}{q_{i}Q_{i}}$; otherwise $q_{i}>P_{i}$. In either case,
we have

$q_{i}^{\frac{1}{2}}(1+N_{i}|\lambda_{i}|)^{\frac{1}{2}}>\min(P_{i}^{\frac{1}{2}},N_{i}^{\frac{1}{2}}Q_{i}^{-\frac{1}{2}})=\min(N_{i}^{\frac{1}{18}-\epsilon},N_{i}^{\frac{1}{18}+\epsilon}).$

This in combination with Lemma 3.4 with $X=U_{i}$ leads to

$\begin{split}\max_{\alpha_{i}\in\mathfrak{m}_{i}}|S_{3}(\alpha_{i},U_{i})|&\ll
N_{i}^{\frac{1}{3}-\frac{1}{36}+\epsilon}+N_{i}^{\frac{1}{3}-\frac{1}{18}+\epsilon}\ll
N_{i}^{\frac{11}{36}+\epsilon}.\end{split}$

Thus we complete the proof of (3.11). ∎

######  Lemma 3.6.

For $k\geq 3$, let $\mathscr{M}$ be the union of intervals $\mathscr{M}(q,a)$
for

$1\leq a\leq q\leq P^{k2^{1-k}},\ \ (a,q)=1,$

where

$\mathscr{M}(q,a)=\\{\alpha:|q\alpha-a|\leq P^{k(2^{1-k}-1)}\\}.$

For $u\geq 0$, define

$\begin{split}\omega_{k}(p^{uk+v})=\begin{cases}kp^{-u-\frac{1}{2}},&v=1,\\\
p^{-u-1},&2\leq v\leq k,\end{cases}\end{split}$

and

$\mathscr{J}_{0}=\sup_{\beta\in[0,1)}\int_{\mathscr{M}}\frac{\omega_{k}^{2}(q)|h^{2}(\alpha+\beta)|}{(1+P^{k}|\alpha-\frac{a}{q}|)^{2}}\mathrm{d}\alpha.$

Suppose that $G(\alpha)$ and $h(\alpha)$ are integrable functions of period
one. Let

$g(\alpha)=g_{\mathcal{A}}(\alpha)=\sum_{x\in\mathcal{A}}e(x^{k}\alpha),\ \
\mathcal{A}\subseteq(P,2P]\cap\mathbb{N}$

and $\mathfrak{m}\subseteq[0,1)$ be a measurable set. Then we have

$\int_{\mathfrak{m}}g(\alpha)G(\alpha)h(\alpha)\mathrm{d}\alpha\ll
P\mathscr{J}_{0}^{\frac{1}{4}}\left(\int_{\mathfrak{m}}|G(\alpha)|^{2}\mathrm{d}\alpha\right)^{\frac{1}{4}}\mathscr{J}^{\frac{1}{2}}(m)+P^{1-2^{-k}+\varepsilon}\mathscr{J}(m),$

where

$\mathscr{J}(m)=\int_{\mathfrak{m}}|G(\alpha)h(\alpha)|\mathrm{d}\alpha.$

###### Proof.

This lemma is Lemma 3.1 in Zhao [19]. ∎

######  Lemma 3.7.

For $\gamma\in\mathbb{R}$, we define

$\mathcal{L}(\gamma)=\sum_{q\leq V_{i}}\sum_{\begin{subarray}{c}1\leq a\leq
q\\\ (a,q)=1\end{subarray}}\int_{|\alpha-\frac{a}{q}|\leq
V_{i}}\frac{\omega_{3}^{2}(q)d^{c}(q)|\sum_{V_{i}<p\leq
2V_{i}}e(p^{3}(\alpha+\gamma))|^{2}}{1+|\alpha-\frac{a}{q}|V_{i}^{3}}\mathrm{d}\alpha,$

we have uniformly for $\gamma\in\mathbb{R}$ that

$\mathcal{L}(\gamma)\ll V_{i}^{2}N_{i}^{-1+\epsilon}.$

Here $c$ is an absolute constant.

###### Proof.

We can deduce this lemma from Lemma $2.2$ with $k=3$ and $P=Q=V_{i}$ in Zhao
[19]. ∎

######  Lemma 3.8.

We have

$\int_{\mathfrak{m}_{i}}\left|S_{3}^{3}(\alpha_{i},U_{i})S_{3}^{9}(\alpha_{i},V_{i})\right|\mathrm{d}\alpha_{i}\ll
N_{i}^{\frac{103}{36}+\epsilon}.$

###### Proof.

Write

$\mathscr{J}(t)=\int_{\mathfrak{m}_{i}}\left|S_{3}^{t}(\alpha_{i},U_{i})S_{3}^{9}(\alpha_{i},V_{i})\right|\mathrm{d}\alpha_{i},\
\ 1\leq t\leq 3.$

By Lemma 3.6 with

$g(\alpha)=S_{3}(\alpha_{i},U_{i}),\ \ h(\alpha)=S_{3}(\alpha_{i},V_{i}),\ \
G(\alpha)=|S_{3}^{2}(\alpha_{i},U_{i})S_{3}^{8}(\alpha_{i},V_{i})|,$

we obtain

$\begin{split}\mathscr{J}(3)=N_{i}^{\frac{1}{3}}\mathscr{J}_{0}^{\frac{1}{4}}\left(\int_{\mathfrak{m}_{i}}|S_{3}^{4}(\alpha_{i},U_{i})S_{3}^{16}(\alpha_{i},V_{i})|\mathrm{d}\alpha_{i}\right)^{\frac{1}{4}}\mathscr{J}^{\frac{1}{2}}(2)+N_{i}^{\frac{7}{24}+\epsilon}\mathscr{J}(2).\end{split}$
(3.13)

Here

$\mathscr{J}_{0}=\sup_{\beta\in[0,1)}\sum_{q\leq
V_{i}^{\frac{3}{4}}}\sum_{\begin{subarray}{c}1\leq a\leq q\\\
(a,q)=1\end{subarray}}\int_{\mathscr{M}(q,a)}\frac{\omega_{3}^{2}(q)|h^{2}(\alpha+\beta)|}{(1+V_{i}^{3}|\alpha-\frac{a}{q}|)^{2}}\mathrm{d}\alpha$

and

$\mathscr{M}(q,a)=\left\\{\alpha:|q\alpha-a|\leq
V_{i}^{-\frac{9}{4}}\right\\}.$

We apply Lemma 3.7 and get

$\mathscr{J}_{0}\ll\mathcal{L}(\gamma)\ll V_{i}^{2}N_{i}^{-1+\epsilon}\ll
N_{i}^{-\frac{1}{3}+\epsilon}.$ (3.14)

For $\mathscr{I}(2)$, by Lemma 3.5, Cauchy’s inequality and Hua’s inequality,
we obtain

$\begin{split}\mathscr{J}(2)&\leq\mathscr{J}^{\frac{1}{2}}(3)\left(\int_{\mathfrak{m}_{i}}|S_{3}(\alpha_{i},U_{i})S_{3}^{9}(\alpha_{i},V_{i})|\mathrm{d}\alpha_{i}\right)^{\frac{1}{2}}\\\
&\ll
N_{i}^{\frac{11}{36}+\epsilon}\mathscr{J}^{\frac{1}{2}}(3)\left(\int_{\mathfrak{m}_{2}}|S_{3}^{8}(\alpha_{i},V_{i})|\mathrm{d}\alpha_{i}\right)^{\frac{1}{2}}\\\
&\ll N_{i}^{\frac{41}{36}+\epsilon}\mathscr{J}^{\frac{1}{2}}(3).\end{split}$
(3.15)

Also we apply Lemma 3.5 and get

$\begin{split}\int_{\mathfrak{m}_{i}}|S_{3}^{4}(\alpha_{i},U_{i})S_{3}^{16}(\alpha_{i},V_{i})|\mathrm{d}\alpha_{i}\ll
N^{\frac{22}{9}+\epsilon}\mathscr{J}(3).\end{split}$ (3.16)

Inserting (3.14), (3.15) and (3.16) into (3.13), we have

$\mathscr{J}(3)\ll N^{\frac{103}{72}+\epsilon}\mathscr{J}^{\frac{1}{2}}(3),$

from which we can get this lemma. ∎

######  Lemma 3.9.

We have

$\int_{0}^{1}|S_{3}^{2}(\alpha_{2},U_{i})S_{3}^{6}(\alpha_{i},W_{i})|\mathrm{d}\alpha_{i}\ll
N_{i}^{\frac{4}{3}+\epsilon}.$

###### Proof.

We can deduce this lemma from (5.6) and (5.9) in Brüdern [1]. ∎

######  Lemma 3.10.

Let $\operatorname{meas}(\mathscr{E}_{\lambda})$ denote the Lebesgue measure
of $\mathscr{E}_{\lambda}$. We have

$\operatorname{meas}\left(\mathscr{E}_{\lambda}\right)\ll N_{i}^{-E(\lambda)}$

with $E(0.87045114)>\frac{13}{18}+10^{-10}$.

###### Proof.

Taking $\xi=1.16$ and $h=28$ in Lemma 2.3 in Liu and Lü[11], we can get this
lemma. ∎

######  Lemma 3.11.

We have

$\iint\limits_{[0,1]^{2}}|f^{2}(\alpha_{1},N_{1})f^{2}(\alpha_{2},N_{2})G^{4}(\alpha_{1}+\alpha_{2})|\mathrm{d}\alpha_{1}\mathrm{d}\alpha_{2}\leq
305.8869N_{1}N_{2}L^{4},$ (3.17)
$\int_{0}^{1}\left|S_{3}^{2}(\alpha_{i},U_{i})S_{3}^{2}(\alpha_{i},V_{i})S_{3}^{4}(\alpha_{i},W_{i})\right|\mathrm{d}\alpha_{i}\leq
12.677988U_{i}^{-1}V_{i}^{2}W_{i}^{4}.$ (3.18)

###### Proof.

From the proof of Lemma 2.3 in Kong and Liu [5, p. 206], we can get (3.17).
The estimate (3.18) can be found in Lemma 3.6 of the authors [4]. ∎

##  4 Proof of Theorem 1

In this section, we complete the proof of Theorem 1 by showing desired
estimates for $\mathrm{R}_{r}\left(N_{1},N_{2}\right),r=1,2,3$. We first
estimate $\mathrm{R}_{1}(N_{1},N_{2})$. By Lemma 3.1, Lemma 3.2 and Lemma 3.3,
we have

$\begin{split}\mathrm{R}_{1}&(N_{1},N_{2})\\\
=&\iint\limits_{\mathfrak{M}}f(\alpha_{1},N_{1})S_{3}(\alpha_{1},U_{1})S_{3}(\alpha_{1},V_{1})S_{3}^{2}(\alpha_{1},W_{1})f(\alpha_{2},N_{2})S_{3}(\alpha_{2},U_{2})\\\
&\times
S_{3}(\alpha_{2},V_{2})S_{3}^{2}(\alpha_{2},W_{2})G^{k}(\alpha_{1}+\alpha_{2})e(-\alpha_{1}N_{1}-\alpha_{2}N_{2})\mathrm{d}\alpha_{1}\mathrm{d}\alpha_{2}\\\
\geq&\frac{1}{3^{8}}\sum_{\begin{subarray}{c}n_{1}\in\Xi(N_{1},k)\\\
n_{2}\in\Xi(N_{2},k)\\\ n_{1}\equiv n_{2}\equiv
1\pmod{2}\end{subarray}}\mathfrak{S}(n_{1})\mathfrak{S}(n_{2})\mathfrak{J}(n_{1})\mathfrak{J}(n_{2})\\\
\geq&\frac{3.71280584\cdot
3^{8}(\sqrt[3]{7}-1)^{2}(1-\eta)^{8}}{3^{8}}U_{1}U_{2}V_{1}V_{2}W_{1}^{2}W_{2}^{2}L^{k}\\\
\geq&3.09441331(1-\eta)^{8}U_{1}U_{2}V_{1}V_{2}W_{1}^{2}W_{2}^{2}L^{k}.\end{split}$
(4.1)

Next, we turn to handle $\mathrm{R}_{2}(N_{1},N_{2})$. By (2.2) and (2.4), we
obtain

$\displaystyle\mathfrak{m}\subset$
$\displaystyle\left\\{\left(\alpha_{1},\alpha_{2}\right):\alpha_{1}\in\mathfrak{m}_{1},\alpha_{2}\in[0,1]\right\\}\cup\left\\{\left(\alpha_{1},\alpha_{2}\right):\alpha_{1}\in[0,1],\alpha_{2}\in\mathfrak{m}_{2}\right\\}.$

From the trivial bound $G(\alpha_{1}+\alpha_{2})\ll L$, we have

$\displaystyle\mathrm{R}_{2}$ $\displaystyle\left(N_{1},N_{2}\right)$ (4.2)
$\displaystyle=$
$\displaystyle\iint\limits_{\mathfrak{m}\cap\mathscr{E}_{\lambda}}f(\alpha_{1},N_{1})S_{3}(\alpha_{1},U_{1})S_{3}(\alpha_{1},V_{1})S_{3}^{2}(\alpha_{1},W_{1})f(\alpha_{2},N_{2})S_{3}(\alpha_{2},U_{2})$
$\displaystyle\times
S_{3}(\alpha_{2},V_{2})S_{3}^{2}(\alpha_{2},W_{2})G^{k}(\alpha_{1}+\alpha_{2})e(-\alpha_{1}N_{1}-\alpha_{2}N_{2})\mathrm{d}\alpha_{1}\mathrm{d}\alpha_{2}$
$\displaystyle\ll$ $\displaystyle
L^{k}\left(\iint\limits_{\begin{subarray}{c}\left(\alpha_{1},\alpha_{2}\right)\in\mathfrak{m}_{1}\times[0,1]\\\
\left|G\left(\alpha_{1}+\alpha_{2}\right)\right|\geq\lambda
L\end{subarray}}+\iint\limits_{\begin{subarray}{c}\left(\alpha_{1},\alpha_{2}\right)\in[0,1]\times\mathfrak{m}_{2}\\\
\left|G\left(\alpha_{1}+\alpha_{2}\right)\right|\geq\lambda
L\end{subarray}}\right)|f(\alpha_{1},N_{1})S_{3}(\alpha_{1},U_{1})S_{3}(\alpha_{1},V_{1})S_{3}^{2}(\alpha_{1},W_{1})$
$\displaystyle\times
f(\alpha_{2},N_{2})S_{3}(\alpha_{2},U_{2})S_{3}(\alpha_{2},V_{2})S_{3}^{2}(\alpha_{2},W_{2})|\mathrm{d}\alpha_{1}\mathrm{d}\alpha_{2}$
$\displaystyle=$ $\displaystyle
L^{k}\left(\int_{0}^{1}\left|f(\alpha_{1},N_{1})S_{3}(\alpha_{1},U_{1})S_{3}(\alpha_{1},V_{1})S_{3}^{2}(\alpha_{1},W_{1})J_{1}(\alpha_{1})\right|\mathrm{d}\alpha_{1}\right.$
$\displaystyle\left.+\int_{0}^{1}\left|f(\alpha_{2},N_{2})S_{3}(\alpha_{2},U_{2})S_{3}(\alpha_{2},V_{2})S_{3}^{2}(\alpha_{2},W_{2})J_{2}(\alpha_{2})\right|\mathrm{d}\alpha_{2}\right),$

where

$\begin{split}J_{1}(\alpha_{1})&=\int\limits_{\begin{subarray}{c}\alpha_{2}\in\mathfrak{m}_{2}\\\
|G(\alpha_{1}+\alpha_{2})|\geq\lambda
L\end{subarray}}\left|f(\alpha_{2},N_{2})S_{3}(\alpha_{2},U_{2})S_{3}(\alpha_{2},V_{2})S_{3}^{2}(\alpha_{2},W_{2})\right|\mathrm{d}\alpha_{2},\\\
J_{2}(\alpha_{2})&=\int\limits_{\begin{subarray}{c}\alpha_{1}\in\mathfrak{m}_{1}\\\
|G(\alpha_{1}+\alpha_{2})|\geq\lambda
L\end{subarray}}\left|f(\alpha_{1},N_{1})S_{3}(\alpha_{1},U_{1})S_{3}(\alpha_{1},V_{1})S_{3}^{2}(\alpha_{1},W_{1})\right|\mathrm{d}\alpha_{1}.\end{split}$

It is easy to get that

$\int_{0}^{1}\left|f^{2}(\alpha_{i},N_{i})\right|\mathrm{d}\alpha_{i}\ll
N_{i}^{1+\epsilon}.$

Then we apply Lemma 3.8, Lemma 3.9, Hölder’s inequality, the periodicity of
the function $G(\alpha)$ and get

$\begin{split}J_{1}(\alpha_{1})\ll&\left(\int_{0}^{1}|f^{2}(\alpha_{2},N_{2})|\mathrm{d}\alpha_{2}\right)^{\frac{1}{2}}\left(\int_{\mathfrak{m}_{2}}|S_{3}^{3}(\alpha_{2},U_{2})S_{3}^{9}(\alpha_{2},V_{2})|\mathrm{d}\alpha_{2}\right)^{\frac{1}{9}}\\\
&\times\left(\int_{0}^{1}|S_{3}^{2}(\alpha_{2},U_{2})S_{3}^{6}(\alpha_{2},W_{2})|\mathrm{d}\alpha_{2}\right)^{\frac{1}{3}}\left(\int\limits_{\begin{subarray}{c}\alpha_{2}\in\mathfrak{m}_{2}\\\
|G(\alpha_{1}+\alpha_{2})|\geq\lambda
L\end{subarray}}1\mathrm{d}\alpha_{2}\right)^{\frac{1}{18}}\\\
\ll&N_{2}^{\frac{409}{324}+\epsilon}\left(\int\limits_{\begin{subarray}{c}\omega\in\left[\alpha_{2},1+\alpha_{2}\right]\\\
|G(\omega)|\geq\lambda
L\end{subarray}}1\mathrm{~{}d}\omega\right)^{\frac{1}{18}},\end{split}$ (4.3)

where $\omega=\alpha_{1}+\alpha_{2}$. By (3.18), (4.3), Lemma 3.10 and
Cauchy’s inequality, we have

$\begin{split}&\int_{0}^{1}\left|f(\alpha_{1},N_{1})S_{3}(\alpha_{1},U_{1})S_{3}(\alpha_{1},V_{1})S_{3}^{2}(\alpha_{1},W_{1})J_{1}(\alpha_{1})\right|\mathrm{d}\alpha_{1}\\\
\ll&N_{2}^{\frac{409}{324}+\epsilon}(\operatorname{meas}(\mathscr{E}_{\lambda}))^{\frac{1}{18}}\left(\int_{0}^{1}\left|f^{2}(\alpha_{1},N_{1})\right|\mathrm{d}\alpha_{1}\right)^{\frac{1}{2}}\\\
\times&\left(\int_{0}^{1}\left|S_{3}^{2}(\alpha_{1},U_{1})S_{3}^{2}(\alpha_{1},V_{1})S_{3}^{4}(\alpha_{1},W_{1})\right|\mathrm{d}\alpha_{1}\right)^{\frac{1}{2}}\\\
\ll&N_{1}^{\frac{11}{9}-10^{-12}}N_{2}^{\frac{11}{9}+\epsilon},\end{split}$
(4.4)

where $\lambda=0.87045114$ and $N_{1}\asymp N_{2}$ is used. Arguing similarly
we can also get

$\int_{0}^{1}\left|f(\alpha_{2},N_{2})S_{3}(\alpha_{2},U_{2})S_{3}(\alpha_{2},V_{2})S_{3}^{2}(\alpha_{2},W_{2})J_{2}(\alpha_{2})\right|\mathrm{d}\alpha_{2}\ll
N_{1}^{\frac{11}{9}+\epsilon}N_{2}^{\frac{11}{9}-10^{-12}}.$ (4.5)

Recalling (2.5) and inserting (4.4) and (4.5) into (4.2), we have

$\begin{split}\mathrm{R}_{2}(N_{1},N_{2})&\ll
L^{k}\left(N_{1}^{\frac{11}{9}-10^{-12}}N_{2}^{\frac{11}{9}+\epsilon}+N_{1}^{\frac{11}{9}+\epsilon}N_{2}^{\frac{11}{9}-10^{-12}}\right)\\\
&\ll U_{1}U_{2}V_{1}V_{2}W_{1}^{2}W_{2}^{2}L^{k-1}.\end{split}$ (4.6)

Finally, we handle $\mathrm{R}_{3}(N_{1},N_{2})$. By (2.5), Lemma 3.11,
Cauchy’s inequality and the definition of $\mathscr{E}_{\lambda}$, we get

$\displaystyle\mathrm{R}_{3}$ $\displaystyle\left(N_{1},N_{2}\right)$ (4.7)
$\displaystyle=$
$\displaystyle\iint\limits_{\mathfrak{m}\backslash\mathscr{E}_{\lambda}}f(\alpha_{1},N_{1})S_{3}(\alpha_{1},U_{1})S_{3}(\alpha_{1},V_{1})S_{3}^{2}(\alpha_{1},W_{1})f(\alpha_{2},N_{2})S_{3}(\alpha_{2},U_{2})$
$\displaystyle\times
S_{3}(\alpha_{2},V_{2})S_{3}^{2}(\alpha_{2},W_{2})G^{k}(\alpha_{1}+\alpha_{2})e(-\alpha_{1}N_{1}-\alpha_{2}N_{2})\mathrm{d}\alpha_{1}\mathrm{d}\alpha_{2}$
$\displaystyle\leq$ $\displaystyle(\lambda
L)^{k-2}\left(\iint\limits_{[0,1]^{2}}|f(\alpha_{1},N_{1})f(\alpha_{2},N_{2})G^{2}(\alpha_{1}+\alpha_{2})|^{2}\mathrm{d}\alpha_{1}\mathrm{d}\alpha_{2}\right)^{\frac{1}{2}}$
$\displaystyle\times\left(\iint\limits_{[0,1]^{2}}|S_{3}(\alpha_{1},U_{1})S_{3}(\alpha_{1},V_{1})S_{3}^{2}(\alpha_{1},W_{1})S_{3}(\alpha_{2},U_{2})S_{3}(\alpha_{2},V_{2})S_{3}^{2}(\alpha_{2},W_{2})|^{2}\mathrm{d}\alpha_{1}\mathrm{d}\alpha_{2}\right)^{\frac{1}{2}}$
$\displaystyle\leq$ $\displaystyle(\lambda
L)^{k-2}\left(\iint\limits_{[0,1]^{2}}|f^{2}(\alpha_{1},N_{1})f^{2}(\alpha_{2},N_{2})G^{4}(\alpha_{1}+\alpha_{2})|\mathrm{d}\alpha_{1}\mathrm{d}\alpha_{2}\right)^{\frac{1}{2}}$
$\displaystyle\times\left(\int_{0}^{1}\left|S_{3}^{2}(\alpha_{1},U_{1})S_{3}^{2}(\alpha_{1},V_{1})S_{3}^{4}(\alpha_{1},W_{1})\right|\mathrm{d}\alpha_{1}\right)^{\frac{1}{2}}\left(\int_{0}^{1}\left|S_{3}^{2}(\alpha_{2},U_{2})S_{3}^{2}(\alpha_{2},V_{2})S_{3}^{4}(\alpha_{2},W_{2})\right|\mathrm{d}\alpha_{2}\right)^{\frac{1}{2}}$
$\displaystyle\leq$ $\displaystyle
221.73322593\lambda^{k-2}N_{1}^{\frac{1}{2}}N_{2}^{\frac{1}{2}}U_{1}^{-\frac{1}{2}}U_{2}^{-\frac{1}{2}}V_{1}V_{2}W_{1}^{2}W_{2}^{2}L^{k}$
$\displaystyle\leq$ $\displaystyle
1773.86580744(1-\eta)^{-1}\lambda^{k-2}U_{1}U_{2}V_{1}V_{2}W_{1}^{2}W_{2}^{2}L^{k}.$

Inserting (4.1), (4.6) and (4.7) into (2.11) we have

$\displaystyle\mathrm{R}(N_{1},N_{2})$
$\displaystyle\geq\mathrm{R}_{1}(N_{1},N_{2})-\mathrm{R}_{3}(N_{1},N_{2})+O\left(U_{1}U_{2}V_{1}V_{2}W_{1}^{2}W_{2}^{2}L^{k-1}\right)$
$\displaystyle>\left(3.09441331(1-\eta)^{8}-1773.86580744(1-\eta)^{-1}\lambda^{k-2}\right)U_{1}U_{2}V_{1}V_{2}W_{1}^{2}W_{2}^{2}L^{k},$

where $\lambda=0.87045114$. Then we can deduce $k\geq 48$ from

$\mathrm{R}\left(N_{1},N_{2}\right)>0.$

Thus we complete the proof of Theorem 1.

## Acknowledgment

The authors would like to thank the referees for their many useful comments.
This work is supported by National Natural Science Foundation of China (Grant
No. 12171286).

## References

  * [1] J. Brüdern, A sieve approach to the Waring-Goldbach problem, I: sums of four cubes. Ann. Sci. ÉcoleNorm. Sup., 28 (1995), 461–476.
  * [2] X. Chen, On pairs of one prime, four prime cubes and powers of $2$. (2022), arXiv: 2203.02296.
  * [3] T.W. Ching and K.M. Tsang, Waring-Goldbach problem involving cubes of primes. Math. Z., 297 (2021), 1105–1117.
  * [4] X. Han and H.F. Liu, Powers of 2 in two Goldbach-Linnik type problems involving prime cubes. Discrete Math., 347 (2024), Paper No. 113674.
  * [5] Y.F. Kong and Z.X. Liu, On pairs of Goldbach-Linnik equations. Bull. Aust. Math. Soc., 95 (2017), 199–208.
  * [6] Yu.V. Linnik, Prime numbers and powers of two. Tr. Mat. Inst. Steklova, 38 (1951), 151–169. (in Russian)
  * [7] Yu.V. Linnik, Addition of prime numbers with powers of one and the same number. Mat. Sb. (N.S.), 32 (1953), 3–60. (in Russian)
  * [8] J.Y. Liu, Enlarged major arcs in additive problems II. Proc. Steklov Inst. Math., 276 (2012), 176–192.
  * [9] J.Y. Liu and M.C. Liu, Representation of even integers by cubes of primes and powers of 2. Acta Math. Hungar., 91 (2001), 217–243.
  * [10] J.Y. Liu, M.C. Liu and T.Z. Wang, The number of powers of $2$ in a representation of large even integers (II). Sci. China Ser. A, 41 (1998), 1255–1271.
  * [11] J.Y. Liu and G.S. Lü, Four squares of primes and 165 powers of 2. Acta Arith., 114 (2004), 55–70.
  * [12] J.Y. Liu and T. Zhan, Sums of five almost equal prime squares II. Sci. China Ser. A, 41 (1998), 710–722.
  * [13] M.C. Liu and K.M. Tsang, On pairs of linear equations in three prime variables and an application to Goldbach’s problem. J. Reine Angew. Math., 399 (1989), 109–136.
  * [14] Z.X. Liu and G.S. Lü, Eight cubes of primes and powers of $2$. Acta Arith., 145 (2010), 171–192.
  * [15] Z.X. Liu and G.S. Lü, Two results on powers of $2$ in Waring-Goldbach problem. J. Number Theory, 131 (2011), 716–736.
  * [16] J. Pintz and I.Z. Ruzsa, On Linnik’s approximation to Goldbach’s problem II. Acta Math. Hungar., 161 (2020), 569–582.
  * [17] L.L. Zhao, The additive problem with one cube and three cubes of primes. Michigan Math. J., 63 (2014), 763–779.
  * [18] L.L. Zhao, Four squares of primes and powers of 2. Acta Arith., 162 (2014), 255–271.
  * [19] L.L. Zhao, On the Waring-Goldbach problem for fourth and sixth powers. Proc. Lond. Math. Soc., 108 (2014), 1593–1622.


# The weighted Tower of Hanoi

El-Mehdi Mehiri
USTHB, Faculty of Mathematics
RECITS Laboratory
BP 32, El Alia 16111, Bab Ezzouar
Algiers, Algeria
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
Hacène Belbachir
USTHB, Faculty of Mathematics
RECITS Laboratory
BP 32, El Alia 16111, Bab Ezzouar
Algiers, Algeria
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>

###### Abstract

The weighted Tower of Hanoi is a new generalization of the classical Tower of
Hanoi problem, where a move of a disc between two pegs $i$ and $j$ is weighted
by a positive real $w_{ij}\geq 0$. This new problem generalizes the concept of
finding the minimum number of moves to solve the Tower of Hanoi, to find a
sequence of moves with the minimum total cost. We present an optimal dynamic
algorithm to solve the weighted Tower of Hanoi problem, we also establish some
properties of this problem, as well as its relation with the Tower of Hanoi
variants that are based on move restriction.
Key words : Tower of Hanoi, dynamic programming, weighted Tower of Hanoi,
Recursion.

##  1 Introduction

The Tower of Hanoi puzzle was introduced to the world by Edward Lucas in 1884
[10], since then those interested in the puzzle have created new variants in
order to raise its difficulty level and to study it more, sometimes by
increasing the number of pegs [4, 6, 12] or considering an arbitrary initial
and final states [8] (which can be considered as a generalization) and at
other times, by forbidding certain movements of discs between certain pegs
[12, 3, 11] (which is a kind of restriction of the problem), while others have
chosen to allow the discs to be placed on top of smaller discs [13] (which is
considered a relaxation of the problem). For more on the Tower of Hanoi
problem, we point the interested reader to [8].

The original Lucas’s Tower of Hanoi problem is stated as follows: Consider
three pegs, source peg, intermediate peg and destination peg; and
$n\in\mathbb{N}_{0}$ discs of distinct diameters. Initially, all discs are
stacked on the first peg (the source) ordered by their diameters, with the
smallest one on top and the largest one on the bottom. The goal is to transfer
the $n$ discs to the third peg (the destination) using the minimum number of
moves, and respecting the following rules:

  * $(i)$

at each step only one disc can be moved;

  * $(ii)$

the disc moved must be a topmost disc;

  * $(iii)$

a disc cannot reside on a smaller one.

Solving the problem requires exactly $2^{n}-1$ moves, which can be shown to be
optimal [8]. However, there has been continued interest in the problem from
several viewpoints and not just the minimum number of moves.

The Tower of Hanoi has its applications in many fields such as didactic of
mathematics, psychology, industry and logistics. The Tower of Hanoi and its
variants are used to introduce the concept of mathematical induction to
students in computer science, and discrete mathematics.

The Tower of Hanoi is a model commonly used in cognitive psychology and
neuropsychology to study and examine problem-solving skills which can be
tested by calculating moves and strategies while predicting possible outcomes,
we reefer to [9, 2, 5] for more information about the Tower of Hanoi
applications in psychology. The Tower of Hanoi puzzle can be used to model a
class of logistic problems which called Pile problems [7], in [1] authors
discussed the application of Towers of Hanoi in logistics management and in
Pile problems in particular. However, the Tower of Hanoi can be seen as a
scheduling problem, where the hand playing with discs is a machine or a crane
in a big harbor and discs are the containers in the harbor. Only three zones
in the harbor are used to stack containers which represents the three pegs,
the crane move the containers from a zone to another while respecting the
rules $(i-iii)$ of the Tower of Hanoi, where the discs in this case are the
containers of different sizes. Given an initial state of the containers in
harbor, the crane is asked to move containers to reach another state while
minimizing the number of moves of containers between the three zones, this
problem is an optimization problem.

In order to expand research on the Tower of Hanoi problem we present in this
paper a new optimization problem which is a new generalization of the Tower of
Hanoi problem that has never been considered before in the literature, in
which the movements of the discs between the pegs are weighted using a
definite weighting function of the set of pegs in the set of positive reals
$\mathbb{R}_{+}$, which makes the problem less trivial than the classical
version of the problem. We call this new problem by the weighted Tower of
Hanoi, this optimization problem models the harbor problem mentioned before
more effectively, because it is more realistic to assume that a movement of a
container from a zone to another have a cost, so the goal here is to minimize
the total cost and not the number of moves.

##  2 Description of the problem

Consider the same elements as the original Tower of Hanoi problem, three pegs
$i$, $j$ and $k$, and a set of $n\in\mathbb{N}_{0}$ discs of different
diameters, and the same $(i)-(iii)$ rules of the classical version. In this
new problem, a move from peg $i$ to peg $j$ is weighted by a cost
$w_{ij}\in\mathbb{R}^{+}$, where the objective is to transfer the tower of the
$n$ discs from the source peg to the destination peg by minimizing the total
cost (sum of costs) of the moves used in the solution.
The following digraph is called the weighted movement digraph, where the
vertices represent the pegs and the weighted arcs are the movements between
pegs with their costs.

$w_{13}$$w_{31}$$w_{12}$$w_{21}$$w_{23}$$w_{32}$$1$$3$$2$ Figure 1: The
weighted movement digraph

It is easy to see that the optimal solution is not necessarily unique, for
example, if we take the costs as follows $w_{13}=w_{12}+w_{23}$ then the
problem of transferring a tower of a single disc $n=1$ located on peg $1$
towards peg $3$, have two optimal solutions with the same cost
$w_{13}=w_{12}+w_{23}$, but they differ by the number of moves, one solution
solves the problem using one move, while the other solves it using two moves.

This last remark gives rise to a new question, what is the solution that costs
the minimum and solves the problem using the minimum number of moves? In this
case, the problem becomes a bi-objective optimization problem, in which the
two objectives are the minimization of cost and moves at the same time.
In the next section we present an optimal algorithm that solves the problem by
giving the priority to the minimum total cost where it searches among
solutions with the minimum total cost the one that have the minimum number of
moves.

##  3 A recursive formula for the optimal total cost and an optimal algorithm

Let $C_{n}^{i,j}$ be the total cost of the optimal solution(s) of a weighted
Tower of Hanoi with $n$ discs where $i$ is the source peg and $j$ the
destination peg with $i,j\in\\{1,2,3\\}$, $i\neq j$ and $k=6-i-j$ is the
intermediate peg.
The total cost $C_{n}^{i,j}$ of the optimal solution(s) can be calculated
recursively in terms of the number of discs $n$, the recursion formula is
given as follows.

######  Theorem 1.

For all $n\in\mathbb{N}$, and $i$, $j$ and $k$ are respectively the source,
destination and intermediate pegs,

$C_{n}^{i,j}=\begin{cases}\min\\{w_{ij},w_{ik}+w_{kj}\\}&if\;n=1,\\\
\min\\{C_{n-1}^{i,k}+C_{n-1}^{k,j}+w_{ij},2C_{n-1}^{i,j}+C_{n-1}^{j,i}+w_{ik}+w_{kj}\\}&otherwise.\end{cases}$
(1)

Note that for the trivial case $n=0$ we have $C_{0}^{i,j}=0$.

###### Proof.

Using induction on the number of discs $n\in\mathbb{N}$, we present the
following proof.
Consider $n$ discs, the source and destination pegs are $i$ and $j$
respectively, which implies that $k=6-i-j$ is the intermediate peg, the
objective is to find a recursive formula for $C_{n}^{i,j}$.
For $n=1$, we have two candidate solutions, which are either to move the
unique disc from peg $i$ directly to peg $j$ with a cost $w_{ij}$ or to move
it first to the intermediate peg $k$ then to peg $j$ with a total costs equal
to $w_{ik}+w_{kj}$, then we have $C_{1}^{i,j}=\min\\{w_{ij},w_{ik}+w_{kj}\\}$.
Induction hypothesis, suppose that the optimal solutions of any weighted Tower
of Hanoi having at most $k<n$ discs, have a cost equal to $C_{k}^{i,j}$, then
show that the weighted Tower of Hanoi with $n$ discs have optimal solutions
with total cost equals to $C_{n}^{i,j}$.
To solve this problem with more than one disc, we have to find a way to move
the biggest disc that have a diameter equal to $n$. To do this, we have two
ways, the first way is to move the biggest disc directly from source peg $i$
to the destination peg $j$ by transferring the $(n-1)$ smaller discs to the
intermediate peg $k$, then when the biggest disc is on the destination peg,
the smaller $(n-1)$ discs can be transferred from intermediate peg $k$ to
destination peg $j$, this solution costs $C_{n-1}^{i,k}+C_{n-1}^{k,j}+w_{ij}$
according to the induction hypothesis. The second way is to move the biggest
disc from source peg $i$ to intermediate peg $k$ and then to destination peg
$j$ by transferring the $(n-1)$ smaller discs from source peg $i$ to
destination peg $j$ which allows the biggest peg to be transferred from source
peg $i$ to intermediate peg $k$, and then transferring them (the $n-1$ smaller
discs) from destination peg $j$ to source peg $i$, which liberate the
destination peg $j$ so that the biggest disc can be moved there, and finally
moving the $(n-1)$ smaller discs from source peg $i$ to destination peg $j$,
this solution costs according to induction hypothesis
$2C_{n-1}^{i,j}+C_{n-1}^{j,i}+w_{ik}+w_{kj}$. The choice between these two
solutions depends on which one costs less, hence the optimal solution(s) have
a cost equal to
$C_{n}^{i,j}=\min\\{C_{n-1}^{i,k}+C_{n-1}^{k,j}+w_{ij},2C_{n-1}^{i,j}+C_{n-1}^{j,i}+w_{ik}+w_{kj}\\}$.
∎

The proof of Theorem 1, can be used to construct a recursive optimal algorithm
to solve the weighted Tower of Hanoi problem efficiently, the algorithm is
presented bellow.

Algorithm 1 The Weighted Tower of Hanoi dynamic programming algorithm

1:procedure WTHD($n,i,j$)

2: $k:=6-i-j;$

3: if $n=1$ then

4: if $w_{ij}\leq w_{ik}+w_{kj}$ then

5: move disc $d_{n}$ from peg $i$ to peg $j$;

6: else

7: move disc $d_{n}$ from peg $i$ to peg $k$;

8: move disc $d_{n}$ from peg $k$ to peg $j$;

9: end if

10: else

11: if $C_{n-1}^{i,k}+C_{n-1}^{k,j}+w_{ij}\leq
2C_{n-1}^{i,j}+C_{n-1}^{j,i}+w_{ik}+w_{kj}$ then

12: WTHD($n-1,i,k$);

13: move disc $d_{n}$ from peg $i$ to peg $j$;

14: WTHD($n-1,k,j$);

15: else

16: WTHD($n-1,i,j$);

17: move disc $d_{n}$ from peg $i$ to peg $k$;

18: WTHD($n-1,j,i$);

19: move disc $d_{n}$ from peg $k$ to peg $j$;

20: WTHD($n-1,i,j$);

21: end if

22: end if

23:end procedure

######  Corollary 1.

The optimal solution provided by the WTHD algorithm has the minimum number of
moves among the optimal solutions.

###### Proof.

Whenever having the situation $w_{ij}=w_{ik}+w_{kj}$, it is clear that
choosing to move the disc from peg $i$ to peg $j$ directly will generate fewer
moves then choosing to move it from peg $i$ to peg $k$ then to peg $j$. The
same thing in the situation where
$C_{n-1}^{i,k}+C_{n-1}^{k,j}+w_{ij}=2C_{n-1}^{i,j}+C_{n-1}^{j,i}+w_{ik}+w_{kj}$,
choosing to move discs according to the left side of the equality will
generate less number of moves, because the left side corresponds to moving the
biggest disc directly from source peg to destination peg using only one move
rather than moving it through intermediate peg as corresponds to the right
side of the equality where two moves are used to move the biggest disc to
destination peg. Whatever the situation, algorithm WTHD always takes the
choice with the least number of moves and this is due to the use of the
comparison operator $\leq$ when comparing between $w_{ij}$ and
$w_{ik}+w_{kj}$, and between $C_{n-1}^{i,k}+C_{n-1}^{k,j}+w_{ij}$ and
$2C_{n-1}^{i,j}+C_{n-1}^{j,i}+w_{ik}+w_{kj}$. ∎

Let $u_{n}^{i,j}$ be the number of moves of an optimal solution of the WTH
with $n$ discs, then we have the following result.

######  Proposition 1.

For all $n\geq 0$

$2^{n}-1\leq u_{n}^{i,j}\leq 3^{n}-1.$

###### Proof.

It is known that the shortest and the longest solution in terms of number of
moves are the solutions corresponding to the classical Tower of Hanoi and
linear variant of the Tower of Hanoi respectively [8], so it suffices to
notice that any solution of this problem must have a number of moves between
the number of moves of these two solutions, which are $2^{n}-1$ and $3^{n}-1$
respectively. ∎

Let $v_{n}$ denote the number of sub-problems needed to be solved by algorithm
WTHD to solve the weighted Tower of Hanoi of $n$ discs with two arbitrary
source and destination pegs. According to relation 1, to calculate
$C_{n}^{i,j}$ we need to calculate four sub-problems $C_{n-1}^{i,j}$,
$C_{n-1}^{i,k}$, $C_{n-1}^{j,i}$ and $C_{n-1}^{k,j}$. Figure 2 shows the
structure of search tree when applying relation 1.

$C_{n}^{i,j}$$C_{n-1}^{i,j}$$C_{n-1}^{j,i}$$C_{n-1}^{i,k}$$C_{n-1}^{k,j}$$C_{n-2}^{i,j}$$C_{n-2}^{i,k}$$C_{n-2}^{j,i}$$C_{n-2}^{j,k}$$C_{n-2}^{k,i}$$C_{n-2}^{k,j}$$C_{n-3}^{i,j}$$C_{n-3}^{i,k}$$C_{n-3}^{j,i}$$C_{n-3}^{j,k}$$C_{n-3}^{k,i}$$C_{n-3}^{k,j}$$C_{2}^{i,j}$$C_{2}^{i,k}$$C_{2}^{j,i}$$C_{2}^{j,k}$$C_{2}^{k,i}$$C_{2}^{k,j}$$C_{1}^{i,j}$$C_{1}^{i,k}$$C_{1}^{j,i}$$C_{1}^{j,k}$$C_{1}^{k,i}$$C_{1}^{k,j}$
Figure 2: The structure of the search tree.

######  Proposition 2.

For all $n\geq 3$ we have

$v_{n}=6^{n-2}+4,$ (2)

and $v_{0}=0$, $v_{1}=1$ and $v_{2}=4$.

###### Proof.

It is clear that $v_{0}=0$ and $v_{1}=1$, for case $n=2$, for any source and
destination pegs $i$ and $j$ we have
$C_{2}^{i,j}=\min\\{C_{1}^{i,k}+C_{1}^{k,j}+w_{ij},2C_{1}^{i,j}+C_{1}^{j,i}+w_{ik}+w_{kj}\\}$
which means that four sub-problems needed to be evaluated which are
$C_{1}^{i,j}$, $C_{1}^{i,k}$, $C_{1}^{j,i}$ and $C_{1}^{k,j}$, hence
$v_{2}=4$. For $n\geq 3$ we have

$C_{n}^{i,j}=\min\\{C_{n-1}^{i,k}+C_{n-1}^{k,j}+w_{ij},2C_{n-1}^{i,j}+C_{n-1}^{j,i}+w_{ik}+w_{kj}\\},$

where

$\displaystyle C_{n-1}^{i,j}$
$\displaystyle=\min\\{C_{n-2}^{i,k}+C_{n-2}^{k,j}+w_{ij},2C_{n-2}^{i,j}+C_{n-2}^{j,i}+w_{ik}+w_{kj}\\},$
$\displaystyle C_{n-1}^{i,k}$
$\displaystyle=\min\\{C_{n-2}^{i,j}+C_{n-2}^{j,k}+w_{ik},2C_{n-2}^{i,k}+C_{n-2}^{k,i}+w_{ij}+w_{jk}\\},$
$\displaystyle C_{n-1}^{j,i}$
$\displaystyle=\min\\{C_{n-2}^{j,k}+C_{n-2}^{k,i}+w_{ji},2C_{n-2}^{j,i}+C_{n-2}^{i,j}+w_{jk}+w_{ki}\\},$
$\displaystyle C_{n-1}^{k,j}$
$\displaystyle=\min\\{C_{n-2}^{k,i}+C_{n-2}^{i,j}+w_{kj},2C_{n-2}^{k,j}+C_{n-2}^{j,k}+w_{ki}+w_{ij}\\}.$

In total we have $4$ sub-problems of order $n-1$, $C_{n-1}^{i,j}$,
$C_{n-1}^{i,k}$, $C_{n-1}^{j,i}$ and $C_{n-1}^{k,j}$ and six sub-problems of
order $n-2$ which are $C_{n-2}^{i,j}$, $C_{n-2}^{i,k}$, $C_{n-2}^{j,i}$,
$C_{n-2}^{j,k}$, $C_{n-2}^{k,i}$ and $C_{n-2}^{k,j}$. To calculate the $6$
sub-problems of order $h$ we need to evaluate all the $6$ possible sub-
problems of order $h-1$ for all $2\leq h\leq n-2$. Therefor we have $6^{n-2}$
sub problems of order $h$ with $1\leq h\leq n-2$ in addition to the $4$ sub-
problems of order $n-1$. Hence in total we have $v_{n}=6^{n-2}+4$. ∎

This last result allows us to find the time complexity of the recursive
algorithm WTHD.

######  Corollary 2.

The WTHD algorithm solves an instances of the WTH problem on $n$ dics in a
time complexity $\mathcal{O}(6^{n-2})$.

###### Proof.

It is a direct result of Proposition 2. ∎

Here we list some direct results of Theorem 1, for symmetry reasons we have
the follwoing result which is more or less easy to see.

######  Corollary 3.

If $w_{ij}=w_{ji}$ for all $i,j\in\\{1,2,3\\}$, then

$C_{n}^{i,j}=C_{n}^{j,i}=\begin{cases}\min\\{w_{ij},w_{ik}+w_{kj}\\}&si\;n=1,\\\
\min\\{C_{n-1}^{i,k}+C_{n-1}^{k,j}+w_{ij},3C_{n-1}^{i,j}+w_{ik}+w_{kj}\\}&else.\end{cases}$
(3)

As we mentioned before in this paper, the classical Tower of Hanoi has a
solution with $2^{n}-1$ moves, which is the minimum number of moves needed to
transfer a whole tower of $n$ discs from a peg to another according to rules
$(i-iii)$. Using this fact, we find the following result.

######  Corollary 4.

If $w_{ij}=x\in\mathbb{R}$ for all $i,j\in\\{1,2,3\\}$, then

$C_{n}^{i,j}=(2^{n}-1)x.$

###### Proof.

When all weights are equal, the problem becomes the minimization of the number
of moves, and we know that the minimum number of moves to solve a Tower of
Hanoi on $n$ discs is equal to $2^{n}-1$. ∎

######  Example 1.

Consider a weighted Tower of Hanoi weighted problem, the associated weights
are given in the matrix bellow

$(w_{ij})_{1\leq i,j\leq 3}=\begin{pmatrix}0&3&15\\\ 8&0&2\\\
5&6&0\end{pmatrix}.$

The objective is to transfer a tower of $n=3$ discs from peg $i=1$ to peg
$j=3$ while minimizing the total cost. For all $n\geq 0$ we denote
$L_{n}^{i,j}=C_{n-1}^{i,k}+C_{n-1}^{k,j}+w_{ij}$ and
$R_{n}^{i,j}=2C_{n-1}^{i,j}+C_{n-1}^{j,i}+w_{ik}+w_{kj}$. The dynamic Table 1
shows the steps that the dynamic recursive relation 1 takes to find the
optimal value for $C_{n}^{i,j}$. The values with $*$ are optimal in accordance
with the corresponding source and destination pegs while the red color
corresponds to the selected sub-problems used to evaluate $C_{3}^{1,3}$.

|  1$\longrightarrow$2 |  1$\longrightarrow$3 |  2$\longrightarrow$1 |  2$\longrightarrow$3 |  3$\longrightarrow$1 |  3$\longrightarrow$2
---|---|---|---|---|---|---
n | $L_{n}^{1,2}$ | $D_{n}^{1,2}$ | $L_{n}^{1,3}$ | $R_{n}^{1,3}$ | $L_{n}^{2,1}$ | $R_{n}^{2,1}$ | $L_{n}^{2,3}$ | $R_{n}^{2,3}$ | $L_{n}^{3,1}$ | $L_{n}^{3,1}$ | $L_{n}^{3,2}$ | $R_{n}^{3,2}$
1 | 3* | 21 | 15 | 5* | 8 | 7* | 2* | 23 | 5* | 14 | 6* | 8
2 | 14* | 34 | 20* | 20* | 15* | 24 | 14* | 33 | 18* | 29 | 14* | 22
3 | 37* | 64 | 43* | 63 | 40* | 51 | 37* | 65 | 34* | 70 | 38* | 50
$\colon$ | $\colon$ | $\colon$ | $\colon$ | $\colon$ | $\colon$ | $\colon$ | $\colon$ | $\colon$ | $\colon$ | $\colon$ | $\colon$ | $\colon$
Table 1: The progress of calculating the total cost

So the optimal cost to transfer a tower of $n=3$ discs from peg $1$ to peg $3$
is $C_{3}^{1,3}=43$ where

$\displaystyle 43$ $\displaystyle=14+14+15=C_{2}^{1,2}+C_{2}^{2,3}+w_{1,3}$
$\displaystyle=(5+6+3)+(7+5+2)+15=(C_{1}^{1,3}+C_{1}^{3,2}+w_{1,2})+(C_{1}^{2,1}+C_{1}^{1,3}+w_{2,3})+w_{1,3}.$

##  4 The relationship to variants with restricted disc moves

Variants with restricted disc moves consists of forbidding some transitions
between certain pegs, for example, moves between pegs $1$ and $3$ are
forbidden, which implies that the only moves allowed are those between
adjacent pegs (if the pegs are aligned from the peg $1$ to peg $3$), this
variant is called the Linear Tower of Hanoi. For more information, see chapter
$8$ in [8].
It is proven that the only solvable variants based on disc movement
restrictions are those having a strongly connected movement digraph, which
consists of three vertices that represent the three pegs, and an arc from
vertex $u$ to vertex $v$ exists if and only if moves from peg $u$ to peg $v$
are allowed, Figure 3 shows the only five strongly connected digraphs on three
vertices. These are the only solvable variants that are based on restricting
disc movements on three pegs.

$1$$2$$3$$\stackrel{{\scriptstyle\leftrightarrow}}{{K}}_{3}$$1$$2$$3$$\stackrel{{\scriptstyle\leftrightarrow}}{{L}}_{3}$$1$$2$$3$$\overrightarrow{C_{3+}}$$1$$2$$3$$\stackrel{{\scriptstyle\leftrightarrow}}{{K}}_{3-}$$1$$2$$3$$\overrightarrow{C_{3}}$
Figure 3: Strongly connected digraphs on three vertices

Sapir in [11], proposed an algorithm that solves any such variant in a minimum
number of moves. By carefully choosing the weights on arcs, we can design a
class of WTH instances that corresponds to one of the five variants in such a
way that these instances have an optimal solution that respects the
restriction of disc moves of the corresponding variant; Which implies that
algorithm WTHD can be used to solve any variant with restricted disc moves.

Let
$X\in\\{\overleftrightarrow{K}_{3},\overleftrightarrow{L}_{3},\overrightarrow{C}_{3},\overleftrightarrow{K}_{3-},\overrightarrow{C}_{3+}\\}$
be a variant of the Tower of Hanoi with restricted disc moves and $A(X)$ its
digraph movement. To forbid movements from peg $i$ to peg $j$, it suffices to
choose $w_{ij}$ large enough so that the algorithm WTHD never chooses to move
a disc from peg $i$ to peg $j$. As the expression "large enough" is very
relative, we expand our study to search about the minimum value that can be
given to $w_{ij}$ so that there is at least one optimal solution without any
disc movement from peg $i$ to peg $j$. As a first observation, it is clear
that it is always sufficient to choose $w_{ij}=\infty$ so that the optimal
solution(s) does not admit movements from peg $i$ to peg $j$ simply because
$\infty$ is always large enough.

The following lemma characterize the condition that must be fulfilled so that
an instance of the WTH problem has an optimal solution with no disc moves from
certain peg to another.

######  Lemma 1.

A WTH instance of $n$ discs, has no optimal solution with movements of discs
from peg $i$ to peg $j$ if and only if

$\displaystyle w_{ij}$
$\displaystyle>w_{ik}+w_{kj}+\max\\{0,2C_{n-1}^{i,j}+C_{n-1}^{j,i}-C_{n-1}^{i,k}-C_{n-1}^{k,j}\\},\;and$
$\displaystyle C_{n}^{i,j}$
$\displaystyle=2C_{n-1}^{i,j}+C_{n-1}^{j,i}+w_{ik}+w_{kj}.$

###### Proof.

If no optimal solution has a disc movement from peg $i$ to peg $j$ then the
solution provided by Algorithm WTHD has also no disc movement from peg $i$ to
peg $j$ which implies $w_{ij}>w_{ik}+w_{kj}$ and

$C_{n-1}^{i,k}+C_{n-1}^{k,j}+w_{ij}>2C_{n-1}^{i,j}+C_{n-1}^{j,i}+w_{ik}+w_{kj}.$

Then $C_{n}^{i,j}=2C_{n-1}^{i,j}+C_{n-1}^{j,i}+w_{ik}+w_{kj}$ and

$w_{ij}>\max\\{w_{ik}+w_{kj},2C_{n-1}^{i,j}+C_{n-1}^{j,i}+w_{ik}+w_{kj}-C_{n-1}^{i,k}-C_{n-1}^{k,j}\\}.$

Thus,

$w_{ij}>w_{ik}+w_{kj}+\max\\{0,2C_{n-1}^{i,j}+C_{n-1}^{j,i}-C_{n-1}^{i,k}-C_{n-1}^{k,j}\\}.$

In the other side if

$\displaystyle w_{ij}$
$\displaystyle>w_{ik}+w_{kj}+\max\\{0,2C_{n-1}^{i,j}+C_{n-1}^{j,i}-C_{n-1}^{i,k}-C_{n-1}^{k,j}\\},\;and$
$\displaystyle C_{n}^{i,j}$
$\displaystyle=2C_{n-1}^{i,j}+C_{n-1}^{j,i}+w_{ik}+w_{kj}.$

We obtain

$\displaystyle w_{ij}$ $\displaystyle>w_{ik}+w_{kj},\;and$ $\displaystyle
C_{n-1}^{i,k}+C_{n-1}^{k,j}+w_{ij}$
$\displaystyle<2C_{n-1}^{i,j}+C_{n-1}^{j,i}+w_{ik}+w_{kj}.$

Therefor, Algorithm WTHD will never choose to move a disc from peg $i$ to peg
$j$. Hence no optimal solution will have a disc move from peg $i$ to peg $j$.
∎

The next theorem is a generalization of Lemma 1, it characterizes a class of
WTH instances that correspond to one of the five variants with restricted disc
moves, i.e. for each variant
$X\in\\{\overleftrightarrow{K}_{3},\overleftrightarrow{L}_{3},\overrightarrow{C}_{3},\overleftrightarrow{K}_{3-},\overrightarrow{C}_{3+}\\}$
it gives the characteristics of the weights $(w_{ij})_{1\leq i,j\leq 3}$ so
that at least one optimal solution is of the same type as the solution of
variant $X$.

######  Theorem 2.

Let $X$ be a variant of the Tower of Hanoi with restricted disc moves, and
$D=(V(D),A(D))\in\\{\overleftrightarrow{K}_{3},\overleftrightarrow{L}_{3},\overrightarrow{C}_{3},\overleftrightarrow{K}_{3-},\overrightarrow{C}_{3+}\\}$
its movement digraph. An instance of the WTH has an optimal solution
corresponds to the restriction on disc moves of variant $X$ if and only if for
all $(i,j)\notin A(D)$, $i\neq j$, we have

$w_{ij}>w_{ik}+w_{kj}+\max\\{0,2C_{n-1}^{i,j}+C_{n-1}^{j,i}-C_{n-1}^{i,k}-C_{n-1}^{k,j}\\},$

and $C_{n}^{i,j}=2C_{n-1}^{i,j}+C_{n-1}^{j,i}+w_{ik}+w_{kj}$.

###### Proof.

for each $(i,j)\notin A(D)$, $i\neq j$, we do the same reasoning as the
previous proof. ∎

We present bellow two direct results of Theorem 2 which are Corollaries 5 and
6 that characterize the class of WTH instances in which the optimal solution
respects the restrictions on disc moves of the linear variant and the cyclic
variant respectively.

######  Corollary 5.

An instance of the WTH, accepts the linear variant solution as an optimal
solution if and only if

$w_{13}>w_{12}+w_{23}+\max\\{0,2C_{n-1}^{1.3}+C_{n-1}^{3.1}-C_{n-1}^{1,2}-C_{n-1}^{2,3}\\}$

and

$w_{31}>w_{32}+w_{21}+\max\\{0,2C_{n-1}^{3.1}+C_{n-1}^{1.3}-C_{n-1}^{3,2}-C_{n-1}^{2,1}\\}.$

######  Corollary 6.

An instance of the WTH, accepts the cyclic variant solution as an optimal
solution if and only if

$w_{13}>w_{12}+w_{23}+\max\\{0,2C_{n-1}^{1.3}+C_{n-1}^{3.1}-C_{n-1}^{1,2}-C_{n-1}^{2,3}\\},$
$w_{32}>w_{31}+w_{12}+\max\\{0,2C_{n-1}^{3,2}+C_{n-1}^{2,3}-C_{n-1}^{3,1}-C_{n-1}^{1,3}\\},$
$w_{21}>w_{23}+w_{31}+\max\\{0,2C_{n-1}^{2,1}+C_{n-1}^{1,2}-C_{n-1}^{2,3}-C_{n-1}^{3,1}\\}.$

##  5 Conclusion

A new generalization of the Tower of Hanoi puzzle was presented in this paper,
in this generalization the moves between pegs are weighted and the objective
is to solve the puzzle while minimizing the total cost. The special thing
about this new generalization is that it generalize the concept of the minimum
number of moves in the classical Tower of Hanoi so that each move is measured
using a positive weight. We gave a recursive formula of the total cost in
terms of the number of discs, also we introduced an optimal algorithm to solve
this new optimization problem using dynamic programming. We established also
the relationship between the weighted Tower of Hanoi and its variants with
restricted disc moves. Furthermore, due to the complexity time of the
recursive algorithm proposed in this paper, one could think about using
heuristics and meta-heuristics to solve the WTH problem.

## References

  * [1] José Alberto Hernández Aguilar, Augusto Renato Pérez Mayo, Santiago Yip Ortuño, Alberto Ochoa-Zezzatti, and Julio César Ponce Gallegos.  The application of hanoi towers game in logistics management.  In Handbook of Research on Military, Aeronautical, and Maritime Logistics and Operations, pages 422–433. IGI Global, 2016.
  * [2] John R Anderson, Mark V Albert, and Jon M Fincham.  Tracing problem solving in real time: fmri analysis of the subject-paced tower of hanoi.  Journal of cognitive neuroscience, 17(8):1261–1274, 2005.
  * [3] MD Atkinson.  The cyclic towers of hanoi.  Information Processing Letters, 13(3):118–119, 1981.
  * [4] Henry Ernest Dudeney.  The Canterbury Puzzles.  Courier Corporation, 2002.
  * [5] Madison Fansher, Priti Shah, and Sébastien Hélie.  The effect of mode of presentation on tower of hanoi problem solving.  Cognition, 224:105041, 2022.
  * [6] James Sutherland Frame.  Solution to advanced problem 3918.  Amer. Math. Monthly, 48:216–217, 1941.
  * [7] Lorenz Hempel, Roland Schmiedel, and Lutz Kämmerer.  Pile problems and their mathematical treatment.  In Perspectives on Operations Research, pages 257–276. Springer, 2006.
  * [8] Andreas M Hinz, Sandi Klavar, and Ciril Petr.  The tower of hanoi myths and maths, 2018.
  * [9] Andreas M Hinz, Anton Kostov, Fabian Kneißl, Fatma Sürer, and Adrian Danek.  A mathematical model and a computer tool for the tower of hanoi and tower of london puzzles.  Information Sciences, 179(17):2934–2947, 2009.
  * [10] Édouard Lucas.  Récréations mathématiques, volume 2.  Gauthier-Villars et fils, 1883.
  * [11] Amir Sapir.  The tower of hanoi with forbidden moves.  The Computer Journal, 47(1):20–24, 2004.
  * [12] Paul K Stockmeyer.  Variations on the four-post tower of hanoi puzzle.  In Congress. Numer., volume 102, pages 3–12, 1994.
  * [13] Derick Wood.  The towers of Brahma and Hanoi revisited.  Unit for computer Science, McMaster University, 1980.