\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage{tikz}
\usepackage{tkz-graph}
\usetikzlibrary{arrows}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf
Positive Solutions to Some Systems \\
\vskip .11in
of Diophantine Equations
}
\vskip 1cm
\large
Christopher Briggs\\
Department of Mathematics\\
Embry-Riddle Aeronautical University\\
Prescott, AZ 86301\\
USA \\
\href{mailto:Christopher.Briggs@erau.edu}{\tt Christopher.Briggs@erau.edu}\\
\ \\
Yasuyuki Hirano\\
School of Natural and Living Sciences Education\\
Naruto University of Education\\
772-0051 Tokushima Prefecture, Naruto\\
Japan \\
\href{mailto:yahirano@naruto-u.ac.jp}{\tt yahirano@naruto-u.ac.jp} \\
\ \\
Hisaya Tsutsui\\
Department of Mathematics\\
Embry-Riddle Aeronautical University\\
Prescott, AZ 86301\\
USA \\
\href{mailto:Hisaya.Tsutsui@erau.edu}{\tt Hisaya.Tsutsui@erau.edu}\\
\end{center}

\begin{abstract}
We consider a sequence defined by the number of positive solutions to a
sequence of systems of Diophantine equations. We derive some bounds on
the solutions to demonstrate that the terms of the sequence are finite.
We develop an algorithm for computing an arbitrary term of the
sequence, and consider a graph-theoretic approach to computing the
same.
\end{abstract}

\section{Introduction}\label{sec:intro}

Solving Diophantine equations is a long-standing goal of number theorists. Many have studied the number of positive solutions to a finite system of Diophantine equations. In this paper we shall investigate a particular system of nonlinear Diophantine equations that accidentally arose to the authors: we shared a cab numbered $1523$ and noticed that $1+5=2\cdot 3$ and $1\cdot 5=2+3$. That is, the cab number was a solution to the system of nonlinear Diophantine equations
\begin{equation}
\label{eqs_two_by_two}
  \begin{split}
    a_{1,1}+a_{1,2} & = a_{2,1}a_{2,2} \\
    a_{2,1}+a_{2,2} & = a_{1,1}a_{1,2}
  \end{split}
\end{equation}
The authors quickly decided that the system \eqref{eqs_two_by_two} should have finitely many positive solutions, the only other one being $2, 2, 2, 2$. It was unclear that the number of positive solutions to the system would remain finite if the number of equations were increased. That is, does the system of nonlinear Diophantine equations
\begin{equation}
\label{eqs_n_by_two}
  \begin{split}
  a_{1,1}+a_{1,2} & = a_{2,1}a_{2,2} \\
  a_{2,1}+a_{2,2} & = a_{3,1}a_{3,2} \\
  & \vdots\\
  a_{n-1,1}+a_{n-1,2} & = a_{n,1}a_{n,2}\\
  a_{n,1}+a_{n,2} & = a_{1,1}a_{1,2} 
  \end{split}
\end{equation}
have finitely many positive solutions? It turns out that it does; proving this fact is the content of Section \ref{sec:finiteness}. This fact is derived from a more general result, which is that the system of nonlinear Diophantine equations
\begin{equation}
\begin{split}
\label{eqs_n_by_m}
  \sum_{j=1}^ma_{1,j} & = \prod_{j=1}^ma_{2,j} \\
  \sum_{j=1}^ma_{2,j} & = \prod_{j=1}^ma_{3,j} \\
  &\vdots \\
  \sum_{j=1}^ma_{n-1,j} & = \prod_{j=1}^ma_{n,j}\\
  \sum_{j=1}^ma_{n,j} & = \prod_{j=1}^ma_{1,j}
\end{split}
\end{equation}
has finitely many positive solutions.

Having established that the number of solutions to \eqref{eqs_n_by_two} is finite, we turn our attention to finding the actual number of solutions given $n$. This task is not straightforward; the solution of systems of nonlinear Diophantine equations is difficult, and most results are fragmentary and isolated \cite{Mil}. We defined the sequence \seqnum{A275234} \cite{Slo} as the number of positive solutions to \eqref{eqs_n_by_two}. We provide a \href{http://oeis.org/A275234/a275234.txt}{Python script} which, given enough time and computing power, will find the user any desired term of the sequence.

In search of a better method of finding the terms of \seqnum{A275234}, we are led to consider a directed graph which naturally arises from the system of equations. The application of directed graphs to computing solutions to systems of equations first arose in the work of Shannon \cite{Sha} and Mason \cite{Mas53, Mas56}. A modern exposition on the application of the Coates graph to solutions of systems of linear equations can be found in \cite{Coa}, \cite[Sec.\ 3.1]{Che}, and \cite[Sec.\ 6.11]{ThSw}.

\section{Finiteness of terms}\label{sec:finiteness}

\begin{remark}
In any solution to Equations \eqref{eqs_n_by_m}, replacing $a_{i+1,j}$ with $a_{i,j}$ and $a_{1,j}$ with $a_{m,j}$ for all $1 \leq i < n$ and $1 \leq j \leq m$ results in another solution. So does permuting the $a_{i,j}$ with $i$ fixed. We consider two solutions to Equations \eqref{eqs_n_by_m} to be distinct if one cannot be gotten from the other by these transformations.
\end{remark}

\begin{remark}
For the remainder of this presentation, unless otherwise stated, we will only consider solutions to the systems \eqref{eqs_two_by_two}, \eqref{eqs_n_by_two}, and \eqref{eqs_n_by_m} over the positive integers.
\end{remark}

We begin with a result on solutions to Equations \eqref{eqs_n_by_m} over $\mathbb{C}$, then narrow our focus to positive solutions to Equations \eqref{eqs_n_by_two}. As a first step to showing that the number of positive solutions to \eqref{eqs_n_by_m} is finite, we find an upper bound on the smallest-normed element of any solution to \eqref{eqs_n_by_m}.

\begin{proposition}
\label{ceiling_Cn}
For any solution to Equations \eqref{eqs_n_by_m} over $\mathbb{C}$ we have $\min_{i,j}\{|a_{i,j}|\}\leq m^{\frac{1}{m-1}}$, with equality if and only if $|a_{i,j}|=m^{\frac{1}{m-1}}$ for all $i,j$.
\end{proposition}

\begin{proof}
We assume $\min_{i,j}\{|a_{i,j}|\}\geq m^{\frac{1}{m-1}}$ and show equality. Under the hypotheses, for each $i$, $|\prod_{j=1}^m a_{i,j}|\geq\left(\min_j\{|a_{i,j}|\}\right)^{m-1}\max_j\{|a_{i,j}|\}\geq(m^{\frac{1}{m-1}})^{m-1}\max_j\{|a_{i,j}|\}=m\max_j\{|a_{i,j}|\}$. We have
\begin{equation*}
  \begin{split}
  \Big|\sum_{j=1}^m a_{1,j}\Big|=\Big|\prod_{j=1}^m a_{2,j}\Big| \geq m\max_j&\{|a_{2,j}|\}\geq\sum_{j=1}^m|a_{2,j}|\geq\Big|\sum_{j=1}^ma_{2,j}\Big|\\
  \Big|\sum_{j=1}^m a_{2,j}\Big|=\Big|\prod_{j=1}^m a_{3,j}\Big| \geq m\max_j&\{|a_{3,j}|\}\geq\sum_{j=1}^m|a_{3,j}|\geq\Big|\sum_{j=1}^ma_{3,j}\Big|\\
  &\vdots\\
  \Big|\sum_{j=1}^m a_{n-1,j}\Big|=\Big|\prod_{j=1}^m a_{n,j}\Big| \geq m\max_j&\{|a_{n,j}|\}\geq\sum_{j=1}^m|a_{n,j}|\geq\Big|\sum_{j=1}^ma_{n,j}\Big|\\
  \Big|\sum_{j=1}^m a_{n,j}\Big|=\Big|\prod_{j=1}^m a_{1,j}\Big| \geq m\max_j&\{|a_{1,j}|\}\geq\sum_{j=1}^m|a_{1,j}|\geq\Big|\sum_{j=1}^ma_{1,j}\Big|\\
  \end{split}
\end{equation*}
Hence all terms above are equal, and $m\max_j\{|a_{i,j}|\}=\sum_{j=1}^m\{|a_{i,j}|\}$, implying $|a_{i,j}|=\max_{k,l}\{|a_{k,l}|\}$ for all $i,j$. Let $a=\max_{k,l}\{|a_{k,l}|\}$. We have $ma=a^m$, so $a=m^{\frac{1}{m-1}}$.
\end{proof}

The proof that the terms of \seqnum{A275234} are finite relies on the insight that, from each row to the next on the left side of the equations in the system \eqref{eqs_n_by_m}, the sum can increase by at most one. The following lemma establishes this fact.

\begin{lemma}
\label{lem_ineq_1}
If $m \geq 2$, $a_i \in \mathbb{N}$ for $1\leq i\leq m$, and $a_1 \leq \dots \leq a_m$, then $\sum_{j=1}^m a_j \leq m-1+\prod_{j=1}^ma_j$, with equality if and only if $a_{m-1}=1$. In the case of equality, we have $\sum_{j=1}^m a_j=m-1+a_m$.
\end{lemma}

\begin{proof}
Define $g:\mathbb{R}^m\to \mathbb{R}$ by $g(x_1,\ldots, x_m)=\prod_{j=1}^m x_j-\sum_{j=1}^m x_j$. We have $g(1,\ldots,1)=1-m$. Also, $\frac{\partial g}{\partial x_k}(r_1,\ldots,r_m)>0$ whenever $r_j\geq 1$ for each $j$ and $r_l>1$ for some $l\ne k$. In particular, $\frac{\partial g}{\partial x_k}(r_1,\ldots,r_m)>0$ if $r_j\geq 1$ for each $j$ and $r_j>1$ for at least two distinct $j$. Thus $g(a_1,\ldots,a_m)> 1-m$ if $a_{m-1}>1$. For the converse, if $a_{m-1}=1$, then $\sum_{j=1}^m a_j=m-1+a_m=m-1+\prod_{j=1}^ma_j$.
\end{proof}

Since the sums in the rows of \eqref{eqs_n_by_m} can increase by at most one from one row to the next, from no one row to the next can the decrease be as great as the number of rows in the system. The following two results show that, given this restriction, for each $i$ there are finitely many choices for $a_{i,1},\ldots,a_{i,m}$.

\begin{lemma}
\label{lem_ineq_2}
Fix $m \geq 2$ and $B>0$. Let $a_i \in \mathbb{N}$ for $1\leq i\leq m$ and $a_1 \leq \dots \leq a_m$. If $\prod_{j=1}^m a_j$ is sufficiently large (depending on $B$), then either $\sum_{j=1}^ma_j=a_m+m-1$ or $B+\sum_{j=1}^ma_j<\prod_{j=1}^ma_j$.
\end{lemma}

\begin{proof}
Assume $\sum_{j=1}^ma_j \ne a_m+m-1$. By Lemma \ref{lem_ineq_1}, $a_{m-1}\geq 2$. Let $g$ be as in the proof of Lemma \ref{lem_ineq_1}. We have $\frac{\partial g}{\partial x_j}(a_1,\ldots,a_m) \geq 1$, so
\begin{equation*}
g(a_1,\ldots,a_m) \geq g(1,\ldots,1,2,2)+(a_{m}-2)+(a_{m-1}-2)+\sum_{j=1}^{m-2}(a_j-1).
\end{equation*}
Reorganizing terms, and noting $g(1,\ldots,1,2,2)=4-(1+\dots 1+2+2)=2-m$, we have
\begin{equation*} 
  \begin{split}
  \prod_{j=1}^ma_j-\sum_{j=1}^ma_j&\geq (2-m)+(a_m-2)+(a_{m-1}-2)+\sum_{j=1}^{m-2}(a_j-1)\\
  \prod_{j=1}^ma_j-\sum_{j=1}^ma_j&\geq -2-m+a_m+a_{m-1}+\sum_{j=1}^{m-2}(a_j)+\sum_{j=1}^{m-2}(-1)\\
  \prod_{j=1}^ma_j-\sum_{j=1}^ma_j&\geq -2-m+a_m+a_{m-1}+\sum_{j=1}^{m-2}(a_j)+2-m\\
  \prod_{j=1}^ma_j &\geq -2m+2\sum_{j=1}^ma_j\\
  \sum_{j=1}^ma_j &\leq m+\frac{1}{2}\prod_{j=1}^ma_j.
  \end{split}
\end{equation*}  
We want $m+\frac{1}{2}\prod_{j=1}^ma_j<-B+\prod_{j=1}^ma_j$, which is true if $\prod_{j=1}^ma_j>2(m+B)$.
\end{proof}

\begin{corollary}
\label{cor_ineq_1}
If $m \geq 2$ and $B>0$ then $B+\sum_{j=1}^ma_j<\prod_{j=1}^ma_j$ for all but finitely many choices of $a_1,\ldots,a_m \in \mathbb{N}$.
\end{corollary}

We now unite the preliminary results to prove the main result of the section.

\begin{theorem}
\label{thm_m_by_n_finite_over_N}
There are finitely many positive solutions to Equations \eqref{eqs_n_by_m}.
\end{theorem}

\begin{proof}
Let $\{a_{i,j}\}\subset \mathbb{N}$ satisfy Equations \eqref{eqs_n_by_m}. Assume $a_{i,j}\leq a_{i,j+1}$ for each $1\leq i\leq n$ and $1 \leq j < m$. Solving for $0$ in each equation in \eqref{eqs_n_by_m} and summing the results yields
\begin{equation}
  \label{eq_sum}
  \sum_{i=1}^n\Big(\sum_{j=1}^ma_{i,j}-\prod_{j=1}^ma_{i,j}\Big)=0.
\end{equation}
By Lemma \ref{lem_ineq_1}, for each $i$ we have $\sum_{j=1}^ma_{i,j}-\prod_{j=1}^ma_{i,j} \leq m-1$, so Equation \eqref{eq_sum} is impossible if $\prod_{j=1}^ma_{i,j}-\sum_{j=1}^ma_{i,j}>(m-1)(n-1)$ for any $i$. Then by Corollary \ref{cor_ineq_1}, for each $i$ there are finitely many choices $a_{i,1}, \ldots, a_{i,m}$ with $a_{i,m-1}>1$. To complete the proof we show that there are finitely many choices with $a_{i,m-1}=1$.

Suppose $a_{i,m-1}=1$ and $a_{i+1,m-1}>1$. Because $a_{i,m}=1-m+\prod_{j=1}^ma_{i+1,j}$, if $a_{i,m}$ is sufficiently large, then by Lemma \ref{lem_ineq_2} we have $\prod_{j=1}^ma_{i+1,j}-\sum_{j=1}^ma_{i+1,j}>(m-1)(n-1)$. That contradicts Equation \eqref{eq_sum}, so there are finitely many choices for $a_{i,m}$.

By Lemma \ref{lem_ineq_1} and Equation \eqref{eq_sum}, $a_{l,m-1}>1$ for some $l$. So the final case is $a_{i,m-1}= \dots =a_{i+k-1,m-1}=1$ and $a_{i+k,m-1}>1$. We know $a_{i+k-1,m}$ is bounded above. Since $a_{i+k-1,m}=(k-1)(m-1)+a_{i,m}$, the same bound applies to $a_{i,m}$.
\end{proof}

\begin{corollary}
\label{seq_well_def}
The sequence \seqnum{A275234} defined by the number of positive solutions to Equations \eqref{eqs_n_by_two} has finite terms.
\end{corollary}

\section{Finding the terms}
\label{sec:finding_terms}

The authors created a \href{http://oeis.org/A275234/a275234.txt}{Python script} which computes the $n^{\rm th}$ term of the subject sequence \seqnum{A275234} (or, at the user's option, a list of the solutions). While the script was created with performance in mind, there is no guarantee of optimum performance. The first several terms are
\begin{equation*} 
1, 2, 2, 3, 3, 5, 4, 7, 7, 12, 12, 21, 22, 37, 47, 72, 93, 145, 198, 303, 427,\ldots
\end{equation*}  
Computation time becomes an issue soon after this point.

We discuss a potential efficient alternate approach to finding larger terms. Consider the infinite directed graph in Figure~\ref{fig:dir_graph}. The nodes are the positive integers, and there is an edge from $m$ to $n$ whenever there exists a pair of positive integers $a,b$ such that $ab=m$ and $a+b=n$. For example, there is an edge from $5$ to $6$ because $5\cdot 1=5$ and $5+1=6$. There is an edge from $6$ to $5$ because $2\cdot3=6$ and $2+3=5$. The number of edges originating at a node $n$ is the number of divisors of $n$ which are less than or equal to $\sqrt n$ (\seqnum{A038548}), and the number of edges terminating at a node $n$ is equal to $\lfloor \frac n 2 \rfloor$ (\seqnum{A004526}). We call an edge from $m$ to $m-k$ with $k>0$ a \emph{chute} (of length $k$) (in analogy with the board game Chutes and Ladders). The number of chutes of length $k$ is equal to the number of divisors of $k+1$ which are less than or equal to $\sqrt{k+1}$ (\seqnum{A038548}).

\begin{figure}
\begin{center}
\begin{tikzpicture}[thick,scale=0.8, every node/.style={scale=0.6}]
\begin{scope}[shift={(15,0)}]
\tikzset{vertex/.style = {shape=circle,draw,minimum size=1.5em}}
\tikzset{edge/.style = {->,> = latex'}}
\node[vertex] (nD) at (3,0)  {4};
\node[vertex] (nE) at (4,0)  {5};
\node[vertex] (nF) at (5,0)  {6};
\node[vertex] (nG) at (6,0)  {7};
\node[vertex] (nH) at (7,0)  {8};
\node[vertex] (nI) at (8,0)  {9};
\node[vertex] (nJ) at (9,0)  {10};
\node[vertex] (nK) at (10,0)  {11};
\node[vertex] (nL) at (11,0)  {12};
\node[vertex] (nM) at (12,0)  {13};
\node[vertex] (nN) at (13,0)  {14};
\node[vertex] (nO) at (14,0)  {15};
\node[vertex] (nP) at (15,0)  {16};
\node at (2,0) (nY) {\ldots};
\node at (16,0) (nZ) {\ldots};
\Loop[dist=1cm,dir=NO,labelstyle=above](nD)  
\foreach \from/\to in {nY/nD,nD/nE,nE/nF,nF/nG,nG/nH,nH/nI,nI/nJ,nJ/nK,nK/nL,nL/nM,nM/nN,nN/nO,nO/nP,nP/nZ}
\draw[edge] (\from) to (\to);
\foreach \from/\to in {nF/nE, nI/nF, nL/nG,nN/nI,nP/nH}
\draw[edge] (\from) to [bend left] (\to);
\foreach \from/\to in {nH/nF, nJ/nG, nL/nH,nO/nH,nP/nJ}
\draw[edge] (\from) to [bend right] (\to);
\end{scope}
\end{tikzpicture}
\end{center}
\caption{an infinite directed graph}
\label{fig:dir_graph}
\end{figure}

The significance of the graph is that every closed walk of length $n$ constitutes a solution to Equations \eqref{eqs_n_by_two}. For example, with $n=5$ the closed walk $6 \to 7 \to 8 \to 6 \to 5 \to 6$ corresponds to the solution
\begin{equation*}
  \begin{split}
  &6 + 1 = 7 \cdot 1\\
  &7 + 1 = 2 \cdot 4\\
  &2 + 4 = 2 \cdot 3\\
  &2 + 3 = 1 \cdot 5\\
  &1 + 5 = 1 \cdot 6
  \end{split}
\end{equation*}

One may consider the infinite adjacency matrix $A$ corresponding to the graph. The matrix is sparse in the sense that all but finitely many entries in each row and column are 0. In particular, the sum of the $i^{\rm th}$ row is the $i^{\rm th}$ term of \seqnum{A038548}, and the sum of the $j^{\rm th}$ column is $\lfloor \frac j 2 \rfloor$ (\seqnum{A004526}). The matrix $A^k$ has as its $n^{\rm th}$ diagonal entry the number of closed walks starting at the node $n$. In light of the proof of Lemma \ref{lem_ineq_2}, in computing the number of closed walks of length $k$ it suffices to find the $k^{\rm th}$ power of the upper-left square submatrix of dimension $2k+4$. Unfortunately, the walks counted in this way are not necessarily distinct in the sense of distinct solutions to Equations \eqref{eqs_n_by_two}, and so we have only upper bounds on the terms of \seqnum{A275234}. The authors remain interested in finding a combinatorial argument which bridges the adjacency matrix and the terms of \seqnum{A275234}.

\section{Acknowledgments}
We would like to thank the referee for helpful comments which improved the exposition of this paper.

\begin{thebibliography}{9}

\bibitem{Che}
W.~K.~Chen, {\it Graph Theory and its Engineering Applications}, World
Scientific, 1997.

\bibitem{Coa}
C.~Coates, Flow-graph solutions of linear algebraic equations, {\it IRE Trans.\ Circuit Theory} \textbf{6} (1959), 170--187.

\bibitem{Mas53}
S.~J.~Mason, Feedback theory --- some properties of signal flow graphs, {\it Proc.\ IRE} \textbf{41} (1953), 1144--1156.

\bibitem{Mas56}
S.~J.~Mason, Feedback theory --- further properties of signal flow graphs, {\it Proc.\ IRE} \textbf{44} (1956), 920--926.

\bibitem{Mil}
W.~H.~Mills, A system of quadratic Diophantine equations, {\it Pacific\ J. Math.} \textbf{3} (1953), 209--220

\bibitem{Sha}
C.~E.~Shannon, {\it The Theory and Design of Linear Differential
Equation Machines}, Fire Control of the US National Defense Research
Committee, Report 411, Section D-2, 1942.

\bibitem{Slo}
N.~J.~A.~Sloane, The On-Line Encyclopedia of Integer Sequences,
\url{http://oeis.org}.

\bibitem{ThSw}
K.~Thulasiraman and M.~N.~S.~Swamy, {\it Graphs: Theory and
Algorithms}, Wiley, 1992.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 11D45;
Secondary 11D72, 05C38.

\noindent \emph{Keywords: } system of Diophantine equations.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000010},
\seqnum{A000041},
\seqnum{A004526},
\seqnum{A038548}, and
\seqnum{A275234}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received July 29 2016;
revised versions received  September 23 2016; October 4 2016.
Published in {\it Journal of Integer Sequences}, October 10 2016.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}