The Bruck-Ryser-Chowla Theorem

So far we have looked at a wide variety of $(v, k, \lambda)$ difference sets. Of course, there exists ordered triples $(v, k, \lambda)$ which do not yield any difference sets. The famous Bruck-Ryser-Chowla theorem gives us a criterion for determining whether a set of parameters $(v, k, \lambda)$ will NOT yield a difference set on a group $(G, +)$ of order $v$. We state this important theorem below.

Theorem 1 (The Bruck-Ryser-Chowla Theorem): Let $v$, $k$, and $\lambda$ be positive integers such that $2 \leq k < v$. Assume that there exists a symmetric $(v, k, \lambda)$-BIBD. Then: a) If $v$ is even then $k - \lambda$ is a perfect square. b) If $v$ is odd then there exists a nonzero integer solution $(x, y, z)$ to the equation $\displaystyle{x^2 = (k - \lambda) y^2 + (-1)^{\frac{v-1}{2}} \lambda z^2}$.

Recall that the first few perfect squares are $1$, $4$, $9$, $16$, …

The Bruck-Ryser-Chowla theorem tells us that the existence of a symmetric $(v, k, \lambda)$-BIBD restricts the values of the parameters $(v, k, \lambda)$. From The Development of a Difference Set page, we know that if we have a finite abelian group, $(G, +)$ and a $(v, k, \lambda)$-difference set $D \subset G$, then the set $G$ with the set of translates of $G$, $\mathrm{dev} (G)$, i.e., $(G, \mathrm{dev} (G))$, is a symmetric $(v, k, \lambda)$-BIBD.

Therefore if a $(v, k, \lambda)$-difference set exists in $(G, +)$, a symmetric $(v, k, \lambda)$-BIBD exists on $G$ and the Bruck-Ryser-Chowla theorem says that in the assumption that such a symmetric $(v, k, \lambda)$-BIBD exists, the parameters, $v$, $k$, and $\lambda$ must satisfy the conclusions of the theorem.

The Bruck-Ryser-Chowla theorem is rather simple to apply, especially when $v$ is even.

For example, consider the set of parameters $(v, k, \lambda) = (32, 9, 2)$. Does there exist a $(32, 9, 2)$-difference set? Notice that since $v = 32$ is even and $k - \lambda = 9 - 2 = 7$ is NOT a perfect square, we can conclude that a $(32, 9, 2)$-difference set does not exist.

In general, for odd $v$, it can be rather difficult to determine whether an integer solution $(x, y, z)$ exists to the equation:

(1)

\begin{align} \quad \displaystyle{x^2 = (k - \lambda) y^2 + (-1)^{\frac{v-1}{2}} \lambda z^2} \end{align}

The following theorem known as Legendre's theorem gives us a necessary condition for when such equations have integer solutions.

Theorem 2 (Legendre's Theorem): Let $a, b \in \mathbb{Z}$ be integers that are not divisible by any perfect square except $1$ and let $d = \mathrm{gcd} (a, b)$. Then there exists an integer solution $(x, y, z)$ to the equation $x^2 = ay^2 + bz^2$ if and only if all three of the following conditions are satisfied: a) $a$ is a square modulo $\mid b \mid$. b) $b$ is a square modulo $\mid a \mid$. c) $\displaystyle{-\left (\frac{ab}{d} \right)}$ is a square modulo $d$.

For example, consider the set of parameters $(v, k, \lambda) = (37, 13, 7)$. We would like to determine whether there exists a $(37, 14, 8)$ difference set. We have that:

(2)

\begin{align} \quad a &= k - \lambda = 13 - 7= 6 \\ \quad b &= (-1)^{\frac{v - 1}{2}} \lambda = (-1)^{18} 7 = 7 \\ \quad d &= \mathrm{gcd} (a, b) = \mathrm{gcd} (6, 7) = 1 \end{align}

Notice that $a$ and $b$ are not divisible by any perfect square except $1$.

The squares modulo $\mid b \mid = 7$ are $\{ 0, 1, 2, 4 \}$, and $6 \equiv 6 \pmod 7$, so condition (a) is not satisfied.

Hence we can immediately conclude from Legendre's theorem that there exists no integer solutions $(x, y, z)$ to the equation:

(3)

\begin{align} \quad x^2 = 6y^2 + 7z^2 \quad \Leftrightarrow \quad x^2 = (k - \lambda)y^2 + (-1)^{\frac{v-1}{2}} \lambda z^2 \end{align}

So by the Bruck-Ryser-Chowla theorem, there does not exist a $(37, 13, 7)$-difference set.