Positive Solutions to Some Systems of Diophantine Equations

Christopher Briggs Department of Mathematics

Embry-Riddle Aeronautical University

Prescott, AZ 86301 USA

Christopher.Briggs@erau.edu

Yasuyuki Hirano

School of Natural and Living Sciences Education

Naruto University of Education 772-0051 Tokushima Prefecture, Naruto

Japan

yahirano@naruto-u.ac.jp

Hisaya Tsutsui Department of Mathematics

Embry-Riddle Aeronautical University

Prescott, AZ 86301 USA

Hisaya.Tsutsui@erau.edu

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.

1 Introduction

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·3 and 1 · 5 = 2 + 3. That is, the cab number was a solution to the system of nonlinear Diophantine equations

\begin{aligned}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{aligned}  (1)

The authors quickly decided that the system (1) 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

a_{1,1} + a_{1,2} = a_{2,1}a_{2,2} ; a_{2,1} + a_{2,2} = a_{3,1}a_{3,2} ; ⋮ ; 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}  (2)

have finitely many positive solutions? It turns out that it does; proving this fact is the content of Section 2. This fact is derived from a more general result, which is that the system of nonlinear Diophantine equations

∑_{j=1}^{m} a_{1,j} = ∏_{j=1}^{m} a_{2,j} ; ∑_{j=1}^{m} a_{2,j} = ∏_{j=1}^{m} a_{3,j} ; ⋮ ; ∑_{j=1}^{m} a_{n−1,j} = ∏_{j=1}^{m} a_{n,j} ; ∑_{j=1}^{m} a_{n,j} = ∏_{j=1}^{m} a_{1,j}  (3)

has finitely many positive solutions.

Having established that the number of solutions to (2) 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 [5]. We defined the sequence \underline{A275234} [7] as the number of positive solutions to (2). We provide a 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 \underline{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 [6] and Mason [3, 4]. A modern exposition on the application of the Coates graph to solutions of systems of linear equations can be found in [2], [1, Sec. 3.1], and [8, Sec. 6.11].

2 Finiteness of terms

Remark 1. In any solution to Equations (3), replacing a_{i+1,j} with a_{i,j} and a_{1,j} with a_{m,j} for all 1 ≤ i < n and 1 ≤ j ≤ m results in another solution. So does permuting the a_{i,j} with i fixed. We consider two solutions to Equations (3) to be distinct if one cannot be gotten from the other by these transformations.

Remark 2. For the remainder of this presentation, unless otherwise stated, we will only consider solutions to the systems (1), (2), and (3) over the positive integers.

We begin with a result on solutions to Equations (3) over ℂ, then narrow our focus to positive solutions to Equations (2). As a first step to showing that the number of positive solutions to (3) is finite, we find an upper bound on the smallest-normed element of any solution to (3).

Proposition 3. For any solution to Equations (3) over ℂ we have min_{i,j}\{|a_{i,j}|\} ≤ m^{\frac{1}{m−1}} , with equality if and only if |a_{i,j}| = m^{\frac{1}{m−1}} for all i, j.

Proof. We assume min_{i,j}\{|a_{i,j}|\} ≥ m^{\frac{1}{m−1}} and show equality. Under the hypotheses, for each i, | ∏_{j=1}^{m} a_{i,j}| ≥ (min_{j}\{|a_{i,j}|\})^{m−1} max_{j}\{|a_{i,j}|\} ≥ (m^{\frac{1}{m−1}} )^{m−1} max_{j}\{|a_{i,j}|\} = m max_{j}\{|a_{i,j}|\}.

We have

| ∑_{j=1}^{m} a_{1,j}| = | ∏_{j=1}^{m} a_{2,j}| ≥ m max_{j}{|a_{2,j}|} ≥ ∑_{j=1}^{m} |a_{2,j}| ≥ | ∑_{j=1}^{m} a_{2,j}|

| ∑_{j=1}^{m} a_{2,j}| = | ∏_{j=1}^{m} a_{3,j}| ≥ m max_{j}{|a_{3,j}|} ≥ ∑_{j=1}^{m} |a_{3,j}| ≥ | ∑_{j=1}^{m} a_{3,j}|
⋮
| ∑_{j=1}^{m} a_{n−1,j}| = | ∏_{j=1}^{m} a_{n,j}| ≥ m max_{j}{|a_{n,j}|} ≥ ∑_{j=1}^{m} |a_{n,j}| ≥ | ∑_{j=1}^{m} a_{n,j}|

| ∑_{j=1}^{m} a_{n,j}| = | ∏_{j=1}^{m} a_{1,j}| ≥ m max_{j}{|a_{1,j}|} ≥ ∑_{j=1}^{m} |a_{1,j}| ≥ | ∑_{j=1}^{m} a_{1,j}|

Hence all terms above are equal, and m max_{j}{|a_{i,j}|} = ∑_{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}} .

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

Lemma 4. If m ≥ 2, a_{i} ∈ ℕ for 1 ≤ i ≤ m, and a_{1} ≤ ⋯ ≤ a_{m}, then ∑_{j=1}^{m} a_{j} ≤ m − 1 + ∏_{j=1}^{m} a_{j}, with equality if and only if a_{m−1} = 1. In the case of equality, we have ∑_{j=1}^{m} a_{j} = m − 1 + a_{m}.

Proof. Define g : ℝ^{m} → ℝ by g(x_{1}, …, x_{m}) = ∏_{j=1}^{m} x_{j} − ∑_{j=1}^{m} x_{j}. We have g(1, …, 1) = 1 − m. Also, \frac{∂g}{∂x_{k}} (r_{1}, …, r_{m}) > 0 whenever r_{j} ≥ 1 for each j and r_{l} > 1 for some l ≠ k. In particular, \frac{∂g}{∂x_{k}} (r_{1}, …, r_{m}) > 0 if r_{j} ≥ 1 for each j and r_{j} > 1 for at least two distinct j. Thus g(a_{1}, …, a_{m}) > 1 − m if a_{m−1} > 1. For the converse, if a_{m−1} = 1, then ∑_{j=1}^{m} a_{j} = m − 1 + a_{m} = m − 1 + ∏_{j=1}^{m} a_{j}.

Since the sums in the rows of (3) 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}, …, a_{i,m}.

Lemma 5. Fix m ≥ 2 and B > 0. Let a_{i} ∈ ℕ for 1 ≤ i ≤ m and a_{1} ≤ ⋯ ≤ a_{m}. If ∏_{j=1}^{m} a_{j} is sufficiently large (depending on B), then either ∑_{j=1}^{m} a_{j} = a_{m} + m − 1 or B + ∑_{j=1}^{m} a_{j} < ∏_{j=1}^{m} a_{j}.

Proof. Assume ∑_{j=1}^{m} a_{j} ≠ a_{m} + m − 1. By Lemma 4, a_{m−1} ≥ 2. Let g be as in the proof of Lemma 4. We have \frac{∂g}{∂x_{j}} (a_{1}, …, a_{m}) ≥ 1, so

g(a_{1}, …, a_{m}) ≥ g(1, …, 1, 2, 2) + (a_{m} − 2) + (a_{m−1} − 2) + ∑_{j=1}^{m−2}(a_{j} − 1).

Reorganizing terms, and noting g(1, …, 1, 2, 2) = 4 − (1 + … 1 + 2 + 2) = 2 − m, we have

\begin{aligned}∏_{j=1}^{m} a_{j} − ∑_{j=1}^{m} a_{j} & ≥ (2 − m) + (a_{m} − 2) + (a_{m−1} − 2) + ∑_{j=1}^{m−2}(a_{j} − 1) \\ ∏_{j=1}^{m} a_{j} − ∑_{j=1}^{m} a_{j} & ≥ −2 − m + a_{m} + a_{m−1} + ∑_{j=1}^{m−2}(a_{j}) + ∑_{j=1}^{m−2}(−1) \\ ∏_{j=1}^{m} a_{j} − ∑_{j=1}^{m} a_{j} & ≥ −2 − m + a_{m} + a_{m−1} + ∑_{j=1}^{m−2}(a_{j}) + 2 − m \\ ∏_{j=1}^{m} a_{j} & ≥ −2m + 2 ∑_{j=1}^{m} a_{j} \\ ∑_{j=1}^{m} a_{j} & ≤ m + \frac{1}{2} ∏_{j=1}^{m} a_{j}. \end{aligned}

We want m + \frac{1}{2} ∏_{j=1}^{m} a_{j} < −B + ∏_{j=1}^{m} a_{j}, which is true if ∏_{j=1}^{m} a_{j} > 2(m + B).

Corollary 6. If m ≥ 2 and B > 0 then B + ∑_{j=1}^{m} a_{j} < ∏_{j=1}^{m} a_{j} for all but finitely many choices of a_{1}, …, a_{m} ∈ ℕ.

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

Theorem 7. There are finitely many positive solutions to Equations (3).

Proof. Let {a_{i,j}} ⊂ ℕ satisfy Equations (3). Assume a_{i,j} ≤ a_{i,j+1} for each 1 ≤ i ≤ n and 1 ≤ j < m. Solving for 0 in each equation in (3) and summing the results yields

∑_{i=1}^{n} ( ∑_{j=1}^{m} a_{i,j} − ∏_{j=1}^{m} a_{i,j}) = 0.  (4)

By Lemma 4, for each i we have ∑_{j=1}^{m} a_{i,j} − ∏_{j=1}^{m} a_{i,j} ≤ m − 1, so Equation (4) is impossible if ∏_{j=1}^{m} a_{i,j} − ∑_{j=1}^{m} a_{i,j} > (m − 1)(n − 1) for any i. Then by Corollary 6, for each i there are finitely many choices a_{i,1}, …, 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.

4 5 6 7 8 9 10 11 12 13 14 15 16 . . . . . .

Figure 1: an infinite directed graph

Suppose a_{i,m−1} = 1 and a_{i+1,m−1} > 1. Because a_{i,m} = 1 − m + ∏_{j=1}^{m} a_{i+1,j}, if a_{i,m} is sufficiently large, then by Lemma 5 we have ∏_{j=1}^{m} a_{i+1,j} −∑_{j=1}^{m} a_{i+1,j} > (m−1)(n−1). That contradicts Equation (4), so there are finitely many choices for a_{i,m}.

By Lemma 4 and Equation (4), a_{l,m−1} > 1 for some l. So the final case is a_{i,m−1} = ⋯ = 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}.

Corollary 8. The sequence \underline{A275234} defined by the number of positive solutions to Equations (2) has finite terms.

3 Finding the terms

The authors created a Python script which computes the n^{th} term of the subject sequence \underline{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

1, 2, 2, 3, 3, 5, 4, 7, 7, 12, 12, 21, 22, 37, 47, 72, 93, 145, 198, 303, 427, …

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 1. 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 · 1 = 5 and 5 + 1 = 6. There is an edge from 6 to 5 because 2 · 3 = 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} (\underline{A038548}), and the number of edges terminating at a node n is equal to ⌊\frac{n}{2}⌋ (\underline{A004526}). We call an edge from m to m − k with k > 0 a 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} (\underline{A038548}).

The significance of the graph is that every closed walk of length n constitutes a solution to Equations (2). For example, with n = 5 the closed walk 6 → 7 → 8 → 6 → 5 → 6 corresponds to the solution

\begin{matrix}6 + 1 = 7 · 1 \\ 7 + 1 = 2 · 4 \\ 2 + 4 = 2 · 3 \\ 2 + 3 = 1 · 5 \\ 1 + 5 = 1 · 6 \end{matrix}

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^{th} row is the i^{th} term of \underline{A038548}, and the sum of the j^{th} column is ⌊\frac{j}{2}⌋ (\underline{A004526}). The matrix A^{k} has as its n^{th} diagonal entry the number of closed walks starting at the node n. In light of the proof of Lemma 5, in computing the number of closed walks of length k it suffices to find the k^{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 (2), and so we have only upper bounds on the terms of \underline{A275234}. The authors remain interested in finding a combinatorial argument which bridges the adjacency matrix and the terms of \underline{A275234}.

4 Acknowledgments

We would like to thank the referee for helpful comments which improved the exposition of this paper.

References

[1] W. K. Chen, Graph Theory and its Engineering Applications, World Scientific, 1997.

[2] C. Coates, Flow-graph solutions of linear algebraic equations, IRE Trans. Circuit Theory 6 (1959), 170–187.

[3] S. J. Mason, Feedback theory — some properties of signal flow graphs, Proc. IRE 41 (1953), 1144–1156.

[4] S. J. Mason, Feedback theory — further properties of signal flow graphs, Proc. IRE 44 (1956), 920–926.

[5] W. H. Mills, A system of quadratic Diophantine equations, Pacific J. Math. 3 (1953), 209–220

[6] C. E. Shannon, The Theory and Design of Linear Differential Equation Machines, Fire Control of the US National Defense Research Committee, Report 411, Section D-2, 1942.

[7] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[8] K. Thulasiraman and M. N. S. Swamy, Graphs: Theory and Algorithms, Wiley, 1992.

2010 Mathematics Subject Classification: Primary 11D45; Secondary 11D72, 05C38. Keywords: system of Diophantine equations.

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

Received July 29 2016; revised versions received September 23 2016; October 4 2016. Published in Journal of Integer Sequences, October 10 2016.

Return to Journal of Integer Sequences home page.