ON A DIOPHANTINE EQUATION RELATED TO SYMMETRIC DESIGN

H. W. Lu, Harold Bowman, and Peter J.–S. Shiue

We investigate the following Diophantine equation

(1)  k(k − 1) = λ(v − 1),

where λ, k and v are positive integers, and 0 < λ < k < v − 1. This Diophantine equation arises in cyclic difference set and symmetric design ([1, 3]). We prove a result which allows us to efficiently determine solutions of the equation (Theorem 1). We also provide some applications.

\underline{Lemma 1}. There is a simple parametric representation for the solutions of (1). For all positive integers n ≥ 2 and all divisors λ of n(n − 1) we have

(2)  λ | n(n − 1), and let k − λ = n, and v = 2n + λ + \frac{n(n − 1)}{λ}.

\underline{Proof}. See Assmus and Key [1].

\underline{Theorem 1}. There exists a one–to–one mapping from the set

(3)  C = {(v, k, λ) | k^{2} = k + λ(v − 1), 0 < λ < k < v − 1, v, k, λ ∈ ℕ}

onto the set

(4)  SL_{2}(ℕ) = \{ ( \begin{matrix}a & b \\ c & d \end{matrix} ) | ad − bc = 1, a, b, c, d ∈ ℕ\}.

\underline{Proof}. For (v, k, λ) ∈ C, with n = k − λ ≥ 2. The mapping ϕ: C → SL_{2}(ℕ) is defined in the following manner. Let

(5) a = gcd(λ, k − λ), b = gcd(λ, k − λ − 1), d = \frac{k − λ}{a}, c = \frac{k − λ − 1}{b}

then we have

(6)  a, b, c, d ∈ ℕ and ad − bc = 1,

i.e. ( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ SL_{2}(ℕ) is the image of (v, k, λ) ∈ C in SL_{2}(ℕ) under the mapping

ϕ.

Now let ( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ SL_{2}(ℕ). Since gcd(k − λ, k − λ − 1) = 1, using Lemma 1,

we get

(7) λ = ab, k = a(b + d) = b(a + c) + 1, v = 2ad + ab + cd = (a + c)(b + d) + 1.

Thus showing that (v, k, λ) is determined uniquely by its image in SL_{2}(ℕ). There-

fore, the mapping ϕ is one–to–one. On the other hand, for a given ( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈

SL_{2}(ℕ), let (v, k, λ) be given by (7), then we have λ(v − 1) − k(k − 1) = ab(a + c)(b + d) − a(b + d)b(a + c) = 0, which shows that (v, k, λ) is a solution of (1). Therefore, the mapping ϕ is from C onto SL_{2}(ℕ).

\underline{Remark}. Theorem 1 gives a very effective way to find solutions of (1). We first take any pair of relatively prime natural numbers a and b. Since (a, b) = 1, there exists c and d ∈ ℕ such that ad − bc = 1. By substituting a, b, c and d into (7), we have a solution (λ, k, v) of (1). Another approach for the solutions of (1) can be found in Assmus [2].

\underline{Example}. Let a = 5, b = 3. Then there exists d = 2, c = 3 such that 5 · 2 − 3 · 3 = 1.

Thus,

\begin{aligned}λ & = ab = 15 \\ k & = a(b + d) = 5 · (3 + 2) = 25 \\ v & = 2ad + ab + cd = 2 · 5 · 2 + 5 · 3 + 3 · 2 = 41 \end{aligned}

is a solution of (1).

The following simple corollary is an immediate consequence of Theorem 1.

\underline{Corollary 1}. Let (v_{i}, k_{i}, λ_{i}) (i = 1, 2) be two solutions of the following Diophantine equation

(8)  k^{2} = k + λ(v − 1), 0 < λ < k < v − 1, v, k, λ ∈ ℕ.

Then we can generate a third solution (v, k, λ) of (1) from (v_{i}, k_{i}, λ_{i}) (i = 1, 2) by the following method. Let

a_{i} = gcd(λ_{i}, k_{i} − λ_{i}), b_{i} = gcd(λ_{i}, k_{i} − λ_{i} − 1),

d_{i} = \frac{k_{i} − λ_{i}}{a_{i}} , c_{i} = \frac{k_{i} − λ_{i} − 1}{b_{i}}, i = 1, 2, (9)

then a_{i}, b_{i}, c_{i}, d_{i} ∈ ℕ and a_{i}d_{i} − b_{i}c_{i} = 1, i = 1, 2. Let

(10)  ( \begin{matrix}a & b \\ c & d \end{matrix} ) = ( \begin{matrix}a_{1} & b_{1} \\ c_{1} & d_{1} \end{matrix} ) ( \begin{matrix}d_{2} & b_{2} \\ c_{2} & a_{2} \end{matrix} ) .

Define:

(11) λ = ab, k = a(b + d) = b(a + c) + 1, v = (a + c)(b + d) + 1 = 2ad + ab + cd.

This gives a third solution (v, k, λ) of (1).

\underline{Proof}. Since a_{i}d_{i} −b_{i}c_{i} = 1 for i = 1, 2. Then ad−bc = 1. k^{2} = a^{2}b^{2} +2a^{2}bd+ a^{2}d^{2} and λ(v − 1) = ab(ab + ad + cb + cd) by direct substitution we can see this is a solution for (1).

\underline{Definition 1}. We call the solution (v, k, λ) of (1) generated by (v_{i}, k_{i}, λ_{i}) (i = 1, 2) according to Corollary 1 as the multiplication of (v_{1}, k_{1}, λ_{1}) and (v_{2}, k_{2}, λ_{2}), and is denoted by

(v, k, λ) = (v_{1}, k_{1}, λ_{1}) ∘ (v_{2}, k_{2}, λ_{2}).

\underline{Corollary 2}.
(v, k, λ)^{2} = (v, k, λ) ∘ (v, k, λ) =
(12) (2(v − 1)(2(k − λ) − 1), (2k − 1)(2(k − λ) − 1), 2λ(2(h − λ) − 1))

is also a solution of (1).

\underline{Proof}. In this case, a_{2} = a_{1} = a, b_{2} = b_{1} = b, c_{2} = c_{1} = c, d_{2} = d_{1} = d. So we get

( \begin{matrix}a_{1} & b_{1} \\ c_{1} & d_{1} \end{matrix} ) ( \begin{matrix}d_{2} & b_{2} \\ c_{2} & a_{2} \end{matrix} ) = ( \begin{matrix}a & b \\ c & d \end{matrix} ) ( \begin{matrix}d & b \\ c & a \end{matrix} ) = ( \begin{matrix}ad + bc & 2ab \\ 2cd & ad + bc \end{matrix} ) ,

which yields

(v, k, λ)^{2} = (v, k, λ) ∘ (v, k, λ) = (v̂, k̂, λ̂).

Using (11), we have

λ̂ = 2ab(ad + bc) = 2ab(2ad − 1) = 2λ(2(k − λ) − 1),
k̂ = (ad + bc)(ad + bc + 2ab) = (2(k − λ) − 1)(2(k − λ) − 1 + 2λ)
= (2(k − λ) − 1)(2k − 1),
v̂ = 2(ad + bc)^{2} + (ad + bc)(2ab + 2cd)
= 2(ad + bc)(ad + bc + ab + cd)
= 2(2ad − 1)(2ad − 1 + ab + cd) = 2(2(k − λ) − 1)(v − 1).

Thus, we have proved the corollary.

\underline{Examples}.

1. (4t−1, 2t−1, t−1)^{2} = (4(2t−1)^{2}, (4t−3)(2t−1), 2(t−1)(2t−1)), 2 ≤ t ∈ ℕ.

2. (4s − 1, 2s − 1, s − 1) ∘ (4t − 1, 2t − 1, t − 1) = (4(T − 1)^{2}, (T − 1)(2T − 3), (T − 1)(T − 2)), T = s + t, 2 ≤ s, t ∈ ℕ.

3. (n^{2} + n + 1, n + 1, 1)^{2} = (2(2n − 1)(n + 1)n, 4n^{2} − 1, 4n − 2), 2 ≤ n ∈ ℕ.

4. (n^{2} +n+1, n+1, 1)∘(m^{2} +m+1, m+1, 1) = (m(2n+1)^{2} −(2n+3)n, (2m− 1)(2n + 1), 2(2m − 1)).

\underline{Proposition 1}. The complement of (v, k, λ) denoted by (v′, k′, λ′) is defined to be

v′ = v, k′ = v − k, λ′ = v − 2k + λ (k′ − λ′ = k − λ),

and when

(v, k, λ) ↦^{ϕ} ( \begin{matrix}a & b \\ c & d \end{matrix} ) with det ( \begin{matrix}a & b \\ c & d \end{matrix} ) = M,

then

(v′, k′, λ′) ↦^{ϕ} ( \begin{matrix}d & c \\ b & a \end{matrix} ) = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) M ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) .

\underline{Proof}. It is easy to see that

a′ = gcd(λ′, k′ − λ′) = gcd(cd, ad) = d,
b′ = gcd(λ′, k′ − λ′ − 1) = gcd(cd, bc) = c,
c′ = b, and d′ = a,

which proves Proposition 1.

\underline{Proposition 2}. Let

(v, k, λ) ↦^{ϕ} ( \begin{matrix}a & b \\ c & d \end{matrix} ) .

For a design (v, k, λ), if b = c, then v is odd.

\underline{Proof}. We know that for a design (v, k, λ) and an even v, k − λ must be a perfect square. If b = c and v is even, then there is a positive integer A such that ad = A^{2}, hence we get

A^{2} − b^{2} = 1,

so we have A = 1 and b = 0, it is impossible.

\underline{Proposition 3}. If (v′_{i}, k′_{i}, λ′_{i}) are the complements of (v_{i}, k_{i}, λ_{i}), (i = 1, 2), then (v′_{1}, k′_{1}, λ′_{1}) ∘ (v′_{2}, k′_{2}, λ′_{2}) is the complement of (v_{1}, k_{1}, λ_{1}) ∘ (v_{2}, k_{2}, λ_{2}).

\underline{Proof}. Let

(v_{i}, k_{i}, λ_{i}) ↦^{ϕ} ( \begin{matrix}a_{i} & b_{i} \\ c_{i} & d_{i} \end{matrix} ) , (i = 1, 2), with det ( \begin{matrix}a_{i} & b_{i} \\ c_{i} & d_{i} \end{matrix} ) = M.

Then, using Proposition 1, we get

(v′_{i}, k′_{i}, λ′_{i}) ↦^{ϕ} ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) M_{i} ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) , i = 1, 2.

So we have

(v_{1}, k_{1}, λ_{1}) ∘ (v_{2}, k_{2}, λ_{2}) ↦^{ϕ}M_{1} ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) M_{2}^{T} ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} )
(v′_{1}, k′_{1}, λ′_{1}) ∘ (v′_{2}, k′_{2}, λ′_{2}) ↦^{ϕ} ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} )M_{1} ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} )

M_{2}^{T} ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} )

(13)  = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} )M_{1} ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) M_{2}^{T} ,

but ϕ maps the complement of (v_{1}, k_{1}, λ_{1}) ∘ (v_{2}, k_{2}, λ_{2}) to

(14) ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) M_{1} ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) M_{2}^{T} ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) M_{1} ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) M_{2}^{T} .

Hence, from (13) and (14), the proposition is proved.

Applying Proposition 3, we have

\underline{Corollary 1}. If (v′, k′, λ′) is the complement of (v, k, λ), then (v′, k′, λ′)^{2} is the complement of (v, k, λ)^{2}.

\underline{Proof}. Obvious.

\underline{References}

1. E. F. Assmus, Jr. and D. D. Key, Designs and Their Codes, Cambridge Univ. Press, Cambridge, 1992.

2. E. F. Assmus, Jr., “On the Theory of Designs,” Surveys in Combinatorics, London Mathematical Society Lecture Note Series 141, J. Siemons, editor, Cambridge University Press, Cambridge, 1989, 1–21.

3. M. Hall, Jr., Combinatorial Theory, 2nd edition, Wiley–Interscience, 1986.

H. W. Lu Department of Mathematics Tongji University Peoples Republic of China

Harold Bowman Department of Mathematical Sciences University of Nevada Las Vegas, NV 89154–4020 email: bowman@nevada.edu

Peter J.–S. Shiue Department of Mathematical Sciences University of Nevada Las Vegas, NV 89154–0001 email: shiue@nevada.edu

æ