Proceedings of the Steklov Institute of Mathematics, Vol. 218, 1997, pp. 228–242. Translated from Trudy Matematicheskogo Instituta imeni V. A. Steklova, Vol. 218, 1997, pp. 233–247. Original Russian Text Copyright \begin{matrix}c \\ ◯ \end{matrix} 1997 by Kasim-Zadeh. English Translation Copyright \begin{matrix}c \\ ◯ \end{matrix} by ���� �����/Interperiodica Publishing (Russia).

The Complexity of Circuits of Unit Resistances and Some Properties of Fibonacci Numbers

O. M. Kasim-Zadeh

Received February, 1997

Given an unlimited reserve of electric resistances of the same nominal value, say 1 ohm (the unit of measurement is not essential, and we omit its notation in the sequel), series-parallel circuits of unit resistances are constructed. This is done according to the following rules:

(1) a single unit resistance is a series-parallel circuit with resistance 1;

(2) having constructed two series-parallel circuits with resistances r_{1} and r_{2}, we can connect them either in series and obtain a series-parallel circuit with resistance

r_{1} + r_{2},

or connect them in parallel and obtain a series-parallel circuit with resistance

\frac{1}{1/r_{1} + 1/r_{2}} .

What is the least number of unit resistances which suffices to construct a series-parallel circuit with a given resistance r?

This problem is well-known (see, e.g., [3, Problem 60]) but its complete solution has not been found.

For brevity, we shall use the notation

x ⊗ y = \frac{1}{1/x + 1/y} .

The “physical” aspect of the problem apart, we can clearly see that in the problem under consideration we deal with properties of numbers: using units, we can construct expressions with the aid of the operations x + y and x ⊗ y; we have to construct an expression for the number r using the minimal number of units.

In what follows, for brevity, the series-parallel circuits constructed from units will be called Π-circuits. Obviously, the resistance of any Π-circuit is expressed by a rational number, and, conversely, it is easy to show that any positive rational number expresses the resistance of a certain Π-circuit. For example, if m is a positive integer, then, in order to obtain a Π-circuit with resistance m, one must connect m unit resistances in series (see Fig. 1). In order to obtain a Π-circuit with resistance 1/m, one must connect m unit resistances in parallel (Fig. 2).

In general, in order to construct a Π-circuit with resistance r = p/q, where p, q are positive integers, it is sufficient to connect in parallel q equal Π-circuits, each of which consists of p unit

[figure: 1; 1; …; 1; m units; r = m; Fig. 1.; 1; 1; 1; ⋮; ⋮; m units; r = \frac{1}{m}; Fig. 2.]

[figure: 1; 1; …; 1; 1; 1; …; 1; 1; 1; …; 1; p units in a circuit; ⋮; ⋮; q circuits; r = \frac{p}{q}]

Fig. 3.

resistances connected in series (Fig. 3). In particular, this implies that in order to construct a Πcircuit with resistance p/q, it is sufficient to have pq unit resistances. In most cases, a considerably smaller number of resistances is necessary.

The number of unit resistances constituting a Π-circuit is called the comlexity of this circuit. We shall call the minimal number of unit resistances sufficient for constructing a Π-circuit with

resistance r the complexity of the number r in the class of Π-circuits and denote it by L(r).

If the number r is not too complex, then its exact value can be found by means of an exhaustive search, using all Π-circuits of complexity 1, 2, 3, …, which is performed up to the moment when a Π-circuit with the required resistance r is found. However, the possibility of such an approach is limited since the total number of Π-circuits increases exponentially with an increase in their complexity. We need a different approach which will allow us to find the complexity of an arbitrary number r working within an appropriate bounds of resourses, or at least estimate the complexity of numbers with a sufficient accuracy.

Until recently, except for a small number of specific rationals, the exact values of complexity were known only for two infinite sequences of rationals, namely, for all positive integers and the inverses of positive integers. In [4], a new approach to the solution of the problem under consideration was proposed that allows one to find the exact values of complexity for a few more infinite sequences of rational numbers. Recently, the author strengthened the main result of [4]. This is subject-matter of the present paper.

The paper is organized as follows. First, we give a brief overview of the known simple methods for obtaining the bounds for the complexity of numbers from the class of Π-circuits and of the main results of [4]. Then we present the main results of this paper and their proofs. In conclusion, we consider certain applications of the obtained results.

1. THE SIMPLEST BOUNDS

The simplest complexity lower bound of rational numbers from the class of Π-circuits connects the complexity of a number with its absolute value: it states that the inequality

L(r) ≥ max(r, \frac{1}{r})  (1)

holds for any rational r > 0. The meaning of this inequality is quite clear. It is easy to prove (say, by induction on l) that the maximal resistance that can be obtained with the use of l unit resistances is equal to l and is attained when all of them are connected in series. Similarly, the minimal resistance of a Π-circuit of complexity l is equal to 1/l and is attained when all l unit resistances are connected in parallel. This implies that the complexity of the number r must satisfy the inequalities 1/L(r) ≤ r ≤ L(r), and this gives the above-mentioned lower bound of the value L(r) (see [4] for details).

Using bound (1), it is easy to find the exact values of the complexity of all positive integers and that of inverses of positive integers: the relations

L(m) = L(\frac{1}{m}) = m  (2)

hold for any positive integer m. The upper bounds are obvious, and (1) implies the lower ones.

Relation (2) illustrates the general law which holds for all rationals r: inverse numbers have the same complexity, i.e., the relation

L(r) = L(\frac{1}{r})  (3)

holds for any rational r > 0. This relation can be easily proved by induction on the complexity of the number r (see [4] for details). This relation can also be derived from the “duality principle” which is well known in electrical engineering and holds for any planary circuits (see, e.g., [1]).

In many cases, an appropriate upper bound for the complexity of a rational number r can be obtained using the expansion of r into a continued fraction: for any rational r > 0 which is expressed by a continued fraction,

r = a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2} + \frac{1}{a_{3} + ... +\frac{1}{a_{s}}}}} ,

the inequality

L(r) ≤ a_{0} + a_{1} + a_{2} + a_{3} + ⋯ + a_{s}  (4)

holds true. In other words, the complexity of any rational number does not exceed the sum of all partial quotients of a continued fraction expressing this number. It is easy to derive bound (4) using relation (3), but this bound can also be obtained directly according to the obvious relation

r = a_{0} + (\frac{1}{a_{1}} ⊗ (a_{2} + (\frac{1}{a_{3}} ⊗ ⋯ ⊗ a_{s}))).

[figure: 1; 1; 1; 1; 1; r = \frac{5}{6}] Fig. 4.

In some cases, the method of continued fractions gives the exact values of complexity; however, it is not a general rule. For example, the sum of partial quotients of the continued fraction

\frac{5}{6} = \frac{1}{1 + \frac{1}{5}}

for the number 5/6 is equal to 6 and the Π-circuit constructed by the method of continued fractions has complexity 6, whereas the relation

\frac{5}{6} = \frac{1}{2} + \frac{1}{3}

allows us to construct a Π-circuit of complexity 5 (see Fig. 4) for this number. It can be shown that the complexity of the number 5/6 is, in fact, equal to 5.

The question of the extent to which the upper bounds obtained by the method of continued fractions differ from the true complexity of the numbers and of the cases in which this method gives the exact values of complexity is far from being answered. Some results in this direction were obtained in [4].

With the aid of the method of continued fractions, it is easy to obtain one general upper bound of complexity of rational numbers which will be used in the sequel. Let the number r be represented by a continued fraction p/q, where p and q are positive integers. By induction on the number of partial quotients of the continued fraction which expresses the number r, it is easy to show that the sum of these partial quotients does not exceed the value max(p, q) (see [4] for a detailed proof). This implies that

L(r) ≤ max(p, q).  (5)

2. A NEW APPROACH

The lower bounds of the complexity of rational numbers in the class of Π-circuits based on relation (1) and the upper bounds which can be derived by the method of continued fractions are obviously of a different nature. Relation (1) does not take into account the arithmetical properties of the numbers under consideration, whereas these properties are essential for the method of continued fractions.

Relation (1) also has other deficiencies. For example, it is clear that the number of Π-circuits whose complexity is bounded from above by a certain number l is finite. On the other hand, the amount of rational numbers on any open interval of the real axis is infinite. Hence, on any open interval of the semi-axis r > 0, there exist rational numbers of an arbitrary high complexity. Bound (1) which relates the complexity of a number only to its absolute value does not, in principle, take this fact into account. For example, for all numbers r in the interval 1 < r < 2, relation (1) only gives the inequality L(r) > 1, which is obvious without any additional considerations.

In [4], a different approach for obtaining lower bounds of the complexity of rational numbers in the class of Π-circuits was proposed; in this approach, the complexity of a number is related to the values of the numerator and denominator of the reduced common fraction which expresses this number.

Let u_{n} denote the nth term of the sequence of Fibonacci numbers 1, 1, 2, 3, 5, 8, 13, 21, … which is defined by the initial conditions u_{1} = u_{2} = 1 and by the recurrence relation

u_{n} = u_{n−1} + u_{n−2}

for all n ≥ 3.

It is established in [4] that for any positive integer n and any rational number r > 0 of complexity L(r) ≤ n, the numerator and denominator of the reduced common fraction p/q that represents the number r satisfy the system of inequalities

p + q ≤ u_{n+2},  max(p, q) ≤ u_{n+1},  |p − q| ≤ u_{n}.  (6)

This implies an obvious consequence, namely, if two positive integers p and q are relatively prime and do not satisfy al least one of the inequalities of system (6), then the number r = p/q is of the complexity L(r) > n.

In many cases, it is more convinient to use a simplified form of this consequence, namely, if two positive integers p and q are relatively prime and the inequality

max(p, q) > u_{n}  (7)

holds for a certain n, then the number r = p/q is of the complexity L(r) ≥ n.

With the use of these results, the exact values of the complexity of rational numbers from several infinite sequences were found in [4]. In particular, it was proved that for every positive integer n, the number u_{n+1}/u_{n}, which is equal to the ratio of the adjacent Fibonacci numbers, is of the complexity

L(\frac{u_{n+1}}{u_{n}} ) = n.

The upper bound of the complexity of numbers of this kind follows from the method of continued fractions. It is known that the number u_{n+1}/u_{n} can be expressed by the continued fraction

\frac{u_{n+1}}{u_{n}} = 1 + \frac{1}{1 + \frac{1}{1 + ... +\frac{1}{1}}} ,

which has n equal partial quotients, each of which is equal to 1. The lower bound can be derived from (7) with due account of the fact that the adjacent Fibonacci numbers are relatively prime [2].

In a similar way, it was proved that for each n ≥ 2 the relation

L(\frac{u_{n+1}}{u_{n−1}} ) = n

holds for the ratio of the Fibonacci numbers taken every other number.

In the above examples, the exact values of the complexity were obtained on Π-circuits constructed by the method of continued fractions. An example of a different type is given by the sequence of numbers

r_{n} = 1 + \frac{1}{s_{n}} ,

where s_{n} = u_{m}u_{m+1} for n = 2m − 1, and s_{n} = u_{m}u_{m+2} for n = 2m. It is shown in [4] that for any n ≥ 3, the number r_{n} is of the complexity

L(r_{n}) = n.

However, it was found out in [4] that the inequality s_{n} ≥ u_{n} was satisfied for any n. This implies that the method of continued fractions would give a Π-circuit of the complexity not lower than u_{n} + 1 for the number r_{n}. On the other hand, it was shown in [4] that the method of continued fractions gave a Π-circuit of the comlexity not exceeding u_{n+1} for any number which complexity did not exceed n. This bound is almost attainable for the numbers r_{n}.

A number of other results were also obtained in [4]. We will not enlarge the number of examples. They can be found in [4] on the will of the reader.

3. THE MAIN RESULTS

A key result of [4] consisted in finding the system of inequalities (6) that connected the numerators and denominators of the reduced fractions p/q of complexity L(p/q) ≤ n. The later studies allowed the author to strengthen this result by extending system (6) through the addition of new relations. Note that system (6) is equivalent to the system of linear inequalities

p + q ≤ u_{n+2},  p ≤ u_{n+1},  q ≤ u_{n+1},  p − q ≤ u_{n},  q − p ≤ u_{n}.

It seems to be natural to seek new relations also in the form of linear inequalities αp + βq ≤ γ with real coefficients α, β and γ. In the present paper, we find a complete system of linear inequalities of the indicated form that connect the numerators and denominators of reduced common fractions of complexity n. The following assertion constitutes the basis of this result.

Theorem 1. For any positive integer n and any rational number r of complexity L(r) ≤ n, the numerator and denominator of the reduced common fraction p/q which represents the number r satisfy the system of linear inequalities

p − (k − 1)q ≤ u_{n−k+2},  q − (k − 1)p ≤ u_{n−k+2},  (8)

where k = 0 for n = 1, 2 and k = 0, 1, …, n − 2 for n ≥ 3.

Note that for any n, the inequalities of system (8) corresponding to the value k = 0 actually coincide and are equivalent to the inequality p + q ≤ u_{n+2}. In the sequel, when speaking of system (8), we shall consider this pair of inequalities as one inequality.

It is easy to verify that for any n, system (6) is a consequence of system (8). Thus, relations (8) generalize relations (6).

We will prove Theorem 1 later, and now we shall derive certain consequences from this theorem.

Theorem 2. If two positive integers p and q are relatively prime and do not satisfy at least one of the inequalities of system (8), then the number r = p/q is of the complexity L(r) > n.

[figure: 1; 1; q; p; Ψ_{1}; q; p; 1; 1; 2; 2; Ψ_{2}; q; p; 1; 1; 2; 2; 3; 3; Ψ_{3}; q; p; 1; 1; 2; 2; 3; 3; 4; 4; 5; 5; Ψ_{4}]

[figure: q; p; 1; 1; 2; 2; 3; 3; 4; 4; 5; 5; 6; 6; 7; 7; 8; 8; Ψ_{5}; q; p; 1; 1; 2; 2; 3; 3; 4; 4; 5; 5; 6; 6; 7; 7; 8; 8; 9; 9; 10; 10; 11; 11; 12; 12; 13; 13; Ψ_{6}]

Fig. 5.

Theorem 1 has an interesting geometrical interpretation. Let us depict the common fractions p/q by points of an Euclidean plane with Cartesian coordinates (p, q). We add the inequalities

p ≥ 1, q ≥ 1

to system (8). The obtained system of linear inequalities defines, in an obvious way, a certain convex polygon Ψ_{n} in the plane of variables p and q. It is easy to show that for any n ≥ 1, the polygon Ψ_{n} lies in the first quadrant of the coordinate system p, q, it is symmetric with respect to the line p = q, and has 2n − 1 vertices. Note that the polygon Ψ_{n} degenerates into the point (1, 1) for n = 1. For any n ≥ 2, the vertices of the polygon Ψ_{n} are at the integer points with coordinates (1, 1) and (p_{n,k}, q_{n,k}), (q_{n,k}, p_{n,k}), where

p_{n,k} = u_{n−k}  and  q_{n,k} = (k − 1)u_{n−k} + u_{n−k+2},

while k runs through the values k = 0, …, n − 2. In Fig. 5, we show the poligons Ψ_{n} for values n ≤ 6.

Theorem 1 asserts that every point (p, q) which corresponds to the reduced fraction p/q of complexity not exceeding n lies in the polygon Ψ_{n} (i.e., in the interior of this polygon or on its boundary).

Let us now define one more family of polygons by extending the system of inequalities (8) in a different manner, namely, by adding to system (8) the inequality

p + q ≥ n + 1.

The obtained system of linear inequalities defines a convex polygon Φ_{n} in the plane of variables p, q which also lies in the first quadrant of the coordinate system and is symmetric with respect to the line p = q. The vertices of the polygon Φ_{n} are at integer points with coordinates (p_{n,k}, q_{n,k}) and (q_{n,k}, p_{n,k}), where k = 0 for n = 1 and k = 0, …, n − 2 for n ≥ 2. For n = 1, the polygon Φ_{n} degenerates into the point (1, 1), and for n = 2, this polygon degenerates into a segment connecting the points (1, 2) and (2, 1). For all n ≥ 3, the polygon Φ_{n} has 2n − 2 vertices and is obtained from the polygon Ψ_{n} by deleting the vertex (1, 1) together with the sides adjacent to this vertex and by adding the segment connecting the vertices (1, n) and (n, 1) as a new side. The polygon Φ_{n} for n = 7 is shown in Fig. 6.

[figure: q; p; 1; 1; 2; 2; 3; 3; 4; 4; 5; 5; 6; 6; 7; 7; 8; 8; 9; 9; 10; 10; 11; 11; 12; 12; 13; 13; 14; 14; 15; 15; 16; 16; 17; 17; 18; 18; 19; 19; 20; 20; 21; 21; Φ_{7}] Fig. 6.

Note that by the known properties of the Fibonacci numbers [2], the numbers p_{n,k} and q_{n,k} are relatively prime for any n and k, and therefore the fractions

\frac{p_{n,k}}{q_{n,k}}  and  \frac{q_{n,k}}{p_{n,k}}  (9)

are irreducible. Using Theorem 2, it is easy to show that the complexity of each of the numbers (9) is not lower than n. On the other hand, using the relations

\frac{q_{n,k}}{p_{n,k}} = k + \frac{u_{n−k+1}}{u_{n−k}}  and  \frac{p_{n,k}}{q_{n,k}} = \frac{1}{k + \frac{u_{n−k+1}}{u_{n−k}}}

and the method of continued fractions, it is easy to verify that the complexity of these numbers does not exceed n. Thus, the following assertion is valid.

Theorem 3. The equalities

L(\frac{p_{n,k}}{q_{n,k}} ) = L(\frac{q_{n,k}}{p_{n,k}} ) = n

hold true for any positive integer n and for any k, where k = 0 for n = 1, 2 and k = 0, 1, . . . . . . , n−2 for n ≥ 3.

Theorem 3 shows that the complexity of the reduced fractions corresponding to the vertices of the polygon Φ_{n}, is equal to n.

We have established with the use of the method of continued fractions that the relation L(p/q) ≤ max(p, q) holds for every common fraction p/q (see (5)). This relation and the obvious inequality max(p, q) ≤ p + q − 1, which holds for any positive integers p and q, imply that the inequality p + q ≥ n + 1 holds for any reduced fraction p/q of complexity L(p/q) = n. In turn, this and Theorem 1 imply that every point (p, q) corresponding to the reduced fraction p/q of complexity n belongs to the intersection of the half-plane defined by the inequality p + q ≥ n + 1 and the polygon Ψ_{n}, i.e., lies in the polygon Φ_{n}. Together with Theorem 3, this gives the following assertion.

Theorem 4. For any n, the polygon Φ_{n} is the convex hull of the set of all integer points (p, q) corresponding to the reduced fractions p/q of complexity n.

In particular, it follows from Theorem 4 that for any n the system of inequalities obtained from (8) by adding the inequality p + q ≥ n + 1 is a complete system of linear inequalities that connects the numerators and denominators of reduced common fractions of complexity n. Any other linear inequality of the form αp + βq ≤ γ with real coefficients α, β, and γ (a strict one inclusive) that holds for all reduced fractions p/q of complexity n is a consequence of this system.

The regularities of the distribution of points of complexity n in the polygon Φ_{n} are not clear so far. Numerical experiments give a rather intricate picture. It would be interesting to reveal these regularities at least in an asymptotic form.

It remains to prove Theorem 1. This proof is presented below. It is based on a series of auxiliary assertions which are formulated in the form of lemmas.

4. PROOF OF THEOREM 1

We shall compute the resistances of Π-circuits in a formal way, i.e., by following the ordinary rules of fundamental operations with common fractions, but we shall not cancel the numerators and denominators of the resulting fraction by their common divisors.

It is convinient to write formal fractions as pairs of positive integers, for instance, the fraction a/b is written as the pair (a, b). Two pairs (a, b) and (c, d) are considered to be equal if and only if a = c and b = d. The equality of pairs is written as (a, b) = (c, d). We introduce two operations ⊙ and ⊗ for pairs of numbers assuming that

(a, b) ⊙ (c, d) = (ad + bc, bd)  and  (a, b) ⊗ (c, d) = (ac, ad + bc)

for any pairs (a, b) and (c, d). The operation ⊙ describes the operation of addition of formal fractions a/b and c/d according to the rule

\frac{a}{b} ⊙ \frac{c}{d} = \frac{ad + bc}{bd},

and the operation ⊗ is defined in accordance with the relations

\frac{a}{b} ⊗ \frac{c}{d} = \frac{1}{b/a + d/c} = \frac{ac}{ad + bc}.

(The use of the symbol ⊙ to denote the operation of addition of pairs allows us to avoid some undesirable ambiguities.)

In what follows, we shall use one more operation for pairs of numbers, namely, the addition of pairs. This operation is denoted by the symbol ⊕. The pair

(a, b) ⊕ (c, d) = (a + c, b + d)

is called the sum of the pairs of numbers (a, b) and (c, d). The operation of addition of pairs corresponds to taking the mediant of formal fractions. Recall that the fraction (a + c)/(b + d) is the mediant of the common fractions a/b and c/d; for formal fractions the operation of taking the mediant corresponds to their term-by-term addition without a subsequent cancellation of the numerator and demoninator by common divisors.

It is easy to verify that each of the operations ⊙, ⊗, and ⊕ is associative and commutative; moreover, each of the operations ⊙ and ⊗ is distributive with respect to the addition of pairs, i.e.,

(a, b) ⊙ ((c_{1}, d_{1}) ⊕ (c_{2}, d_{2})) = ((a, b) ⊙ (c_{1}, d_{1})) ⊕ ((a, b) ⊙ (c_{2}, d_{2}))

and

(a, b) ⊗ ((c_{1}, d_{1}) ⊕ (c_{2}, d_{2})) = ((a, b) ⊗ (c_{1}, d_{1})) ⊕ ((a, b) ⊗ (c_{2}, d_{2}))

for any three pairs (a, b), (c_{1}, d_{1}), and (c_{2}, d_{2}).

It is natural to associate every Π-circuit with a pair of numbers (a formal fraction) as a formal resistance. We assign the formal resistance (1, 1) to a unit resistance, and the formal resistance (a, b) ⊙ (c, d) ((a, b) ⊗ (c, d), resp.) to the Π-circuit obtained by connecting two Π-circuits with formal resistances (a, b) and (c, d) in series (in parallel, resp.).

A pair of positive integers (a, b) is said to be admissible if there exists a Π-circuit with a formal resistance (a, b). Not every pair of positive integers is admissible. For example, the pair (2, 2) is not admissible.

For every admissible pair (a, b), the complexity of this pair is the minimal number of unit resistances which is sufficient for constructing a Π-circuit with the formal resistance (a, b). The complexity of the pair (a, b) will be denoted by L(a, b).

It is easy to show that for any relatively prime p and q, there exists a positive integer t such that the pair of numbers (a, b) = (tp, tq) is admissible and

L(a, b) = L(\frac{p}{q}).

It suffices to take the formal resistance of any Π-circuit with ordinary (not necessary formal) resistance p/q of complexity L(p/q) as such a pair (a, b). This fact will be used in the sequel.

In the subsequent constructions, we shall use a certain extremal property of the function L(a, b).

Lemma 1. For any admissible pair (a, b) ≠ (1, 1), there exist admissible pairs (c, d) and (g, h) such that (a, b)=(c, d) ⊙ (g, h) or (a, b)=(c, d) ⊗ (g, h); in both cases, L(a, b)=L(c, d) + L(g, h).

Proof. Consider an arbitrary Π-circuit S with a formal resistance (a, b) of the complexity L(a, b). Since (a, b) ≠ (1, 1), this Π-circuit contains at least two unit resistances, and, hence, is a result of either a series or a parallel connection of two Π-circuits S_{1} and S_{2} of a lower complexity. We denote by (c, d) and (g, h) the formal resistances of the Π-circuits S_{1} and S_{2}, respectively. Then (a, b) = (c, d) ⊙ (g, h) or (a, b) = (c, d) ⊗ (g, h) depending on the construction of the initial Π-circuit S. It is obvious that in this case the Π-circuit S_{1} with the formal resistance (c, d) must be of comlexity L(c, d) (otherwise, the complexity of the initial Π-circuit S could be diminished by replacing S_{1} by a Π-circuit of a lower complexity with the same formal resistance (c, d)). Similarly, the complexity of S_{2} is equal to L(g, h). This implies that L(a, b) = L(c, d) + L(g, h). The lemma is proved.

The pair of numbers (a, b) is said to be primitive if a = 1 or b = 1; otherwise, this pair is nonprimitive.

Lemma 2. Every primitive pair is admissible, and for any m the complexity of the primitive pairs (1, m) and (m, 1) is given by the relations

L(1, m) = L(m, 1) = m.

Proof. The admissibility of the pair (1, 1) is obvious. For m ≥ 2, the admissibility of (1, m) and (m, 1) follows from the relations (1, m) = (1, 1) ⊗ (1, m − 1) and (m, 1) = (1, 1) ⊙ (m − 1, 1) by induction.

Let us prove the relations describing the complexity of primitive pairs. For example, consider pairs of the form (1, m) (pairs of the form (m, 1) can be considered by analogy). We again use induction on m (this time, the induction is complete). The basis of induction (m = 1) is obvious: the complexity of the pair (1, 1) is equal to 1. Let m ≥ 2. If there existed pairs (a, b) and (c, d) such that (1, m) = (a, b) ⊙ (c, d), then the equality ad + bc = 1 would hold, but this is impossible for positive integers a, b, c, and d. Hence, the pair (1, m) admits only a representation of the form (1, m) = (a, b) ⊗ (c, d) for certain admissible pairs (a, b) and (c, d). Relying on Lemma 1, we choose these pairs such that the following equality holds: L(1, m) = L(a, b) + L(c, d). Noting that ac = 1, we have a = c = 1, and as a consequence, b + d = m. Thus, (a, b) = (1, b) and (c, d) = (1, d), and both pairs (a, b) and (c, d) are primitive. By the inductive assumption, L(1, b) = b and L(1, d) = d; this implies L(1, m) = b + d = m. The lemma is proved.

It is easy to verify that all pairs of complexity 1 and 2 reduce to the following ones: (1, 1), (1, 2) and (2, 1). This implies that the complexity of every nonprimitive pair is not lower than 3.

The following assertion plays a key role in the proof of Theorem 1.

Lemma 3. For any n ≥ 3, every nonprimitive admissible pair (a, b) of complexity L(a, b) = n can be represented in the form of a sum

(a, b) = (a_{1}, b_{1}) ⊕ (a_{2}, b_{2})

of certain admissible pairs (a_{1}, b_{1}) and (a_{2}, b_{2}) of complexities L(a_{1}, b_{1}) ≤ n−1 and L(a_{2}, b_{2}) ≤ n−2, respectively.

Proof. We use induction on n. For n = 3 (the basis of induction), the assertion being proved is straightforward if we take into account that there exist only two nonprimitive admissible pairs of complexity 3, namely, (3, 2) and (2, 3).

Let n > 3, and let (a, b) be a nonprimitive admissible pair of complexity L(a, b) = n. Then, by Lemma 1, there exist admissible pairs (c, d) and (g, h) such that either (a, b) = (c, d) ⊙ (g, h) or (a, b) = (c, d) ⊗ (g, h); in both cases, L(a, b) = L(c, d) + L(g, h). Let, for definiteness,

(a, b) = (c, d) ⊙ (g, h)

(the second operation can be considered by analogy). Generally speaking, the following two cases are possible.

Case 1: at least one of the pairs, (c, d) or (g, h), is nonprimitive. Since the operation ⊙ is commutative, we can assume, without loss of generality, that the pair (g, h) is nonprimitive. Then the complexity of this pair is not lower than 3, and we can apply the inductive assumption to this pair; according to this assumption, there exist admissible pairs (g_{1}, h_{1}) and (g_{2}, h_{2}) of complexities L(g_{1}, h_{1}) ≤ L(g, h) − 1 and L(g_{2}, h_{2}) ≤ L(g, h) − 2, respectively, such that

(g, h) = (g_{1}, h_{1}) ⊕ (g_{2}, h_{2}).

By the distributivity of the operation ⊙ with respect to the addition of pairs, we have

(a, b) = (c, d) ⊙ (g, h) = (c, d) ⊙ ((g_{1}, h_{1}) ⊕ (g_{2}, h_{2})) = ((c, d) ⊙ (c_{1}, h_{1})) ⊕ ((c, d) ⊙ (g_{2}, h_{2})).

We set (a_{1}, b_{1}) = (c, d) ⊙ (g_{1}, h_{1}) and (a_{2}, b_{2}) = (c, d) ⊙ (g_{2}, h_{2}). Then, obviously, the pairs (a_{1}, b_{1}) and (a_{2}, b_{2}) are admissible, and the following relations hold:

\begin{matrix}(a, b) = (a_{1}, b_{1}) ⊕ (a_{2}, b_{2}), \\ L(a_{1}, b_{1}) ≤ L(c, d) + L(g_{1}, h_{1}) ≤ L(a, b) − 1 and L(a_{2}, b_{2}) ≤ L(c, d) + L(g_{2}, h_{2}) ≤ L(a, b) − 2; \end{matrix}

and this allows us to perform the inductive step.

Case 2: here, both pairs (c, d) and (g, h) are primitive. Since dh = b and b ≥ 2 by the nonprimitivity of the pair (a, b), at least one of the numbers, d or h, is not less than 2. By the commutativity of the operation ⊙, we can assume, without loss of generality, that h ≥ 2. Since the pair (g, h) is primitive, we have g = 1, and therefore this pair has the form (1, h). Then the pair (a, b) can be represented in the form

(a, b) = (c, d) ⊙ (g, h) = (c, d) ⊙ (1, h) = (ch + d, dh) = (c(h − 1) + d, d(h − 1)) ⊕ (c, d)
= ((c, d) ⊙ (1, h − 1)) ⊕ (c, d).

We set (a_{1}, b_{1}) = (c, d) ⊙ (1, h − 1) and (a_{2}, b_{2}) = (c, d). Then the pairs (a_{1}, b_{1}) and (a_{2}, b_{2}) are admissible and

(a, b) = (a_{1}, b_{1}) ⊕ (a_{2}, b_{2}).

Since by Lemma 2 the complexity of the primitive pair (1, h) is equal to h, we have L(a, b) = L(c, d) + h, and this shows that

L(a_{1}, b_{1}) ≤ L(c, d) + h − 1 = L(a, b) − 1 and L(a_{2}, b_{2}) = L(c, d) = L(a, b) − h ≤ L(a, b) − 2

(since h ≥ 2). Thus, in this case, the inductive step is also justified. The lemma is proved.

Lemma 4. Let n ≥ 2. Then, for the positive integers x and y, the validity of the inequality

x − (k − 1)y ≤ u_{n−k+2}  (10)

for k = n − 2 implies the validity of inequalities of this form also for k = n − 1, n, n + 1.

Proof. For k = n − 2, inequality (10) has the form

x − (n − 3)y ≤ u_{4}.

This inequality, together with the condition y ≥ 1, implies the inequality

x − (n − 3 + i)y ≤ u_{4} − i

for all i ≥ 0; in turn, this inequality implies the inequality

x − (n − 3 + i)y ≤ u_{4−i}

for any i, 1 ≤ i ≤ 3, by virtue of the obvious relation u_{4} − i ≤ u_{4−i}. The obtained inequalities corresponding to the values i = 1, 2, 3 coincide with inequalities (10) for k = n − 1, n, n + 1, respectively. The lemma is proved.

Lemma 5. For any positive integer n and any admissible pair (a, b) of complexity L(a, b) ≤ n, the numbers a and b satisfy the system of linear inequalities

a − (k − 1)b ≤ u_{n−k+2},  b − (k − 1)a ≤ u_{n−k+2}  (11)

for k = 0, 1, 2, …, n + 1.

Proof. Note, first of all, that the assertion being proved is valid for all primitive pairs (a, b). Any primitive pair of complexity not exceeding n has the form (m, 1) or (1, m) for certain m ≤ n. We shall show that such pairs satisfy the inequalities of system (11). By virtue of symmetry, it suffices to consider one of these pairs, say, (1, m). Setting a = 1 and b = m, we see that the inequality a − (k − 1)b ≤ u_{n−k+2} holds for 1 ≤ k ≤ n + 1 since a − (k − 1)b ≤ a = 1. The inequality b − (k − 1)a ≤ u_{n−k+2} also holds for 0 ≤ k ≤ n + 1 since b − (k − 1)a ≤ n − k + 1 and n − k + 1 ≤ u_{n−k+2} by the relation s ≤ u_{s+1} that holds for all positive integers s (the latter fact can be easily proved by induction on s).

Let us prove the assertion under consideration in its general form, i.e., for all admissible pairs (a, b). We use induction on n. The basis of induction (n ≤ 2) is obvious since all admissible pairs of complexities 1 and 2 are primitive.

Let n ≥ 3. We describe the inductive step from values not exceeding n − 1 to the value n. We can assume, without loss of generality, that the pair (a, b) is nonprimitive and has complexity n. Following Lemma 3, we represent the pair (a, b) in the form of the sum (a, b) = (a_{1}, b_{1}) ⊕ (a_{2}, b_{2}) of certain admissible pairs (a_{1}, b_{1}) and (a_{2}, b_{2}) of complexities L(a_{1}, b_{1}) ≤ n − 1 and L(a_{2}, b_{2}) ≤ n − 2, respectively.

By the inductive assumption, the pair (a_{1}, b_{1}) satisfies the system of inequalities

a_{1} − (k − 1)b_{1} ≤ u_{n−k+1}, b_{1} − (k − 1)a_{1} ≤ u_{n−k+1}

for k = 0, 1, …, n. Similarly, by the inductive assumption, the pair (a_{2}, b_{2}) satisfies the system of inequalites

a_{2} − (k − 1)b_{2} ≤ u_{n−k}, b_{2} − (k − 1)a_{2} ≤ u_{n−k}

for k = 0, 1, …, n − 1. Summing up the corresponding inequalities of these systems and taking into account that a = a_{1} + a_{2} and b = b_{1} + b_{2}, we have, after obvious transformations, the system of inequalities

a − (k − 1)b ≤ u_{n−k+2}, b − (k − 1)a ≤ u_{n−k+2}

for k = 0, 1, …, n − 1. By Lemma 4, this implies that inequalities of this form also hold for the values k = n, n + 1, and therefore the pair (a, b) satisfies all inequalities of system (11). The inductive step is justified. The lemma is proved.

Let us complete the proof of Theorem 1. Suppose that the rational number r of complexity L(r) ≤ n is expressed by the reduced common fraction p/q. Then there exists a positive integer t such that the pair of numbers (a, b) = (tp, tq) is admissible and L(a, b) = L(p/q). By Lemma 5, the numbers a and b satisfy the system of inequalities (11). The substitution of the values a = tp, b = tq into system (11) lead to the system of inequalities

tp − (k − 1)tq ≤ u_{n−k+2}, tq − (k − 1)tp ≤ u_{n−k+2},

where k = 0, 1, …, n + 1. We cancel the left-hand sides of all indicated inequalities by the value t (this is admissible since, for any x and any y ≥ 0 and t ≥ 1, the inequality tx ≤ y implies x ≤ y). Deleting the inequalities corresponding to the values k = n − 1, n, n + 1 from the obtained system, we see that the numbers p and q satisfy system (8). Theorem 1 is proved.

5. CONCLUDING REMARKS

The problem under consideration is closely connected with various problems from the number theory and discrete geometry. In [4], a number of problems are presented that are equivalent to the problem of complexity of numbers in the class of Π-circuits. All the results of the present paper can be extended to these problems without essential changes.

Let us discuss one natural generalization of the problem being considered. Let the seriesparallel circuits be constructed not only from unit resistances but also from unit inductances and capacitances (with nominals 1 H and 1 F, resp.; the units of measurement of the inductances and capacitances are consistent is comparable with the unit of measurement of the resistance, and are, of course, conditional). Series-parallel circuits of this kind are called RLC-circuits. As is known [1], the total input resistance of any RLC-circuit is described by a certain rational function Z(s) of the complex variable s; this function is called the impedance of this RLC-circuit. It is defined by the following rules:

(1) the impedance of a unit resistance is equal to 1;

(2) the impedance of a unit inductance is equal to s;

(3) the impedance of a unit capacitance is equal to 1/s;

(4) for a series connection of RLC-circuits with impedances Z_{1}(s) and Z_{2}(s), one obtains a RLC-circuit with impedance

Z(s) = Z_{1}(s) + Z_{2}(s),

and for a parallel connection, one obtains a circuit with impedance

Z(s) = \frac{1}{1/Z_{1}(s) + 1/Z_{2}(s)}.

The RLC-circuits consisting of unit resistances alone will be called Π-circuits as before.

The least number of elements (unit resistances, inductances and capacitances) which is sufficient for constructing an RLC-circuit with impedance Z(s) is called the complexity of the impedance Z(s) and is denoted by L′(Z(s)).

Obviously, the impedance of any RLC-circuit can be written in the form of a ratio of two nonzero polynomials with nonnegative integer coefficients.

It is also obvious that when we replace all unit capacitances and inductances by unit resistances in an RLC-circuit with impedance Z(s), we obtain a Π-circuit with resistance Z(1). This implies that the inequality

L(Z(1)) ≤ L′(Z(s))  (12)

holds for any impedance Z(s).

Let Z(s) be the impedance of a certain RLC-circuit. We substitute the value s = 1 into the function Z(s) and express the number Z(1) by the reduced common fraction p/q. We see from inequality (12) that the inequality L(p/q) ≤ n holds for any n and for any impedance Z(s) of complexity L′(Z(s)) ≤ n. This and Theorem 1 imply that the numbers p and q satisfy the system of inequalities (8). If p and q do not satisfy at least one of the inequalities of this system, then L′(Z(s)) > n. In such a form, the assertions of Theorems 1 and 2 can be extended to the case of RLC-circuits. In a similar way, after the corresponding modification, we can also extend Theorem 3 and 4 to the case of impedances.

Relation (12) also implies the following. Let r be an arbitrary positive rational number. If we replace, in an arbitrary way, some (maybe, all) unit resistances by unit inductances or capacitances in any Π-circuit with the resistance r and complexity L(r), then the equality

L′(Z(s)) = L(r)  (13)

holds for the impedance Z(s) of the obtained RLC-circuit. Indeed, on one hand, we have L′(Z(s)) ≤ L(r) by construction, and, on the other hand, we have L′(Z(s)) ≥ L(r) by (12). For example, it follows from relation (13) that if in the Π-circuit of complexity n constructed for the number u_{n+1}/u_{n} by the method of continued fractions, we replace, in an arbitrary way, some (maybe, all) unit resistances by unit inductances or capacitances, then the impedance of the obtained RLCcircuit has precisely the same complexity n.

ACKNOWLEDGMENTS

This work was supported by the Russian Foundation for Fundamental Research (project 96-01-01068).

The author expresses his gratitude to Prof. O. B. Lupanov the attention he gave to this work, and also to R. M. Kolpakov for his valuable remarks.

REFERENCES

1. Bessonov, L. A., Teoreticheskie osnovy elektrotekhniki. Elektricheskie tzepi (Theoretical Foundation of Electrical Engineering. Electrical Circuits), Moscow: Vysshaya Shkola, 1984.

2. Vorob’ev, N. N., Chisla Fibonachchi (Fibonacci Numbers), Moscow: Nauka, 1978.

3. The Otto Dankel Memorial Problem Book, New York: Amer. Math. Monthly, 1974.

4. Kasim-Zadeh, O. M., On the Complexity of Series-Parallel Circuits of Unit Resistances and a Certain Property of the Fibonacci Numbers, Diskr. Mat., 1997, vol. 9, no. 4.

Translated by S. Vakhromeev