Skip to main content

Section 17.3 Fisher's Inequality

There is one more important inequality that is not at all obvious, but is necessary for the existence of a BIBD\((v,k,\lambda)\text{.}\) This is known as Fisher's Inequality, since it was proven by Sir Ronald Aylmer Fisher (1890—1962). The proof we will give is somewhat longer than the standard proof. This is because the standard proof uses linear algebra, which we do not expect to be required background for this course.

Before proving this fact, let's observe the consequences in terms of the usual parameters: \(v\text{,}\) \(k\text{,}\) and \(\lambda\text{.}\) We know from Equation (17.1.2) that

\begin{equation*} b=\frac{\lambda v(v-1)}{k(k-1)}\text{,} \end{equation*}

so \(b \ge v\) implies

\begin{equation*} \frac{\lambda v(v-1)}{k(k-1)}\ge v\text{.} \end{equation*}

Since \(v\) is the number of points of a design, it must be positive, so dividing through by \(v\) does not reverse the inequality. Thus,

\begin{equation*} \frac{\lambda (v-1)}{k(k-1)}\ge 1\text{.} \end{equation*}

Since \(k\) is the number of points in each block, both \(k\) and \(k-1\) must be positive (we are ignoring the trivial case \(k=1\)), so multiplying through by \(k(k-1)\) does not reverse the inequality. Thus,

\begin{equation*} \lambda (v-1) \ge k(k-1)\text{.} \end{equation*}

Suppose we have an arbitrary BIBD\((v,k,\lambda)\text{.}\) Let \(B\) be an arbitrary block of this design. For each value of \(i\) between \(0\) and \(k\) (inclusive), let \(n_i\) denote the number of blocks \(B'\neq B\) such that \(|B'\cap B|=i\text{.}\) (When we say \(B' \neq B\) we allow the blocks to be equal as sets if the block \(B\) is a repeated block of the design; we are only insisting that \(B'\) not be the exact same block of the design as \(B\text{.}\))

The following equations involving \(n_i\) are consequences of easy combinatorial proofs, together with the definition of \(n_i\text{:}\)

\begin{equation} \sum_{i=0}^k n_i = b-1\text{,}\label{eqn_Fisher1}\tag{17.3.1} \end{equation}

because both sides of this equation count every block except \(B\text{.}\)

\begin{equation} \sum_{i=0}^k in_i = k(r-1)\text{,}\label{eqn_Fisher2}\tag{17.3.2} \end{equation}

because both sides of this equation count the number of times elements of \(B\) appear in some other block of the design.

\begin{equation*} \sum_{i=2}^k i(i-1)n_i =k(k-1)(\lambda-1)\text{,} \end{equation*}

because both sides of this equation count the number of times all of the ordered pairs of elements from \(B\) appear together in some other block of the design. Note that when \(i=0\) or \(i=1\text{,}\) we have \(i(i-1)n_i=0\text{,}\) so in fact

\begin{equation} \sum_{i=0}^k i(i-1)n_i =\sum_{i=2}^k i(i-1)n_i =k(k-1)(\lambda-1)\text{.}\label{eqn_Fisher3}\tag{17.3.3} \end{equation}

Adding Equations (17.3.2) and (17.3.3) gives

\begin{equation} \sum_{i=0}^k i^2n_i = k(k-1)(\lambda-1)+k(r-1)\text{.}\label{eqn_Fisher4}\tag{17.3.4} \end{equation}

Now comes the part of the proof where something mysterious happens, and for reasons that are not at all apparent, the result we want will emerge. To fully understand a proof like this one requires deeper mathematics, but even seeing a proof is useful to convince ourselves that the result is true.

Take the polynomial in \(x\) given by

\begin{equation*} \sum_{i=0}^k (x-i)^2 n_i = \sum_{i=0}^k (x^2-2xi+i^2)n_i= x^2\sum_{i=0}^k n_i-2x\sum_{i=0}^k in_i+\sum_{i=0}^k i^2n_i\text{.} \end{equation*}

Using Equations (17.3.1),  (17.3.2), and (17.3.4), we see that this is equal to

\begin{equation*} x^2(b-1)-2xk(r-1)+k(k-1)(\lambda-1)+k(r-1)\text{.} \end{equation*}

Notice that the format in which this polynomial started was a sum of squares times non-negative integers, so its value must be non-negative for any \(x \in \mathbb R\text{.}\)

Using the quadratic formula, \(ax^2+b'x+c=0\) has roots at

\begin{equation*} \frac{-b'\pm\sqrt{(b')^2-4ac}}{2a}\text{.} \end{equation*}

If a quadratic polynomial has two real roots, then there is a region in which its values are negative. Since this polynomial is non-negative for every \(x \in \mathbb R\text{,}\) it can have at most one real root, so \((b')^2-4ac \le 0\text{.}\) Substituting the actual values from our polynomial, this means that

\begin{equation*} (-2k(r-1))^2-4(b-1)(k(k-1)(\lambda-1)+k(r-1)) \le 0\text{.} \end{equation*}

Hence,

\begin{equation*} k^2(r-1)^2-k(b-1)((k-1)(\lambda-1)+r-1) \le 0\text{.} \end{equation*}

Let's rewrite the \(b\) in terms of \(v, r\text{,}\) and \(k\text{.}\) By Theorem 17.1.7, we have \(bk=vr\text{,}\) so

\begin{equation*} k(b-1)=bk-k=vr-k\text{.} \end{equation*}

Hence

\begin{equation*} k^2(r-1)^2-(vr-k)((k-1)(\lambda-1)+r-1) \le 0\text{.} \end{equation*}

Expand the second term slightly, and multiply both sides of the inequality by \(v-1\text{:}\)

\begin{equation*} k^2(r-1)^2(v-1)-(vr-k)(k-1)(\lambda-1)(v-1)-(vr-k)(r-1)(v-1) \le 0\text{.} \end{equation*}

In the middle expression, we have \((\lambda-1)(v-1)\text{.}\) By Theorem 17.1.7, we know that \(\lambda=r(k-1)/(v-1)\text{,}\) so

\begin{equation*} \lambda-1=\frac{r(k-1)-(v-1)}{v-1}\text{.} \end{equation*}

Therefore,

\begin{equation*} (\lambda-1)(v-1)=r(k-1)-v+1\text{.} \end{equation*}

Thus, we have

\begin{equation*} k^2(r-1)^2(v-1)-(vr-k)(k-1)(rk-r-v+1)-(vr-k)(r-1)(v-1) \le 0\text{.} \end{equation*}

The next step is a lot of work to do by hand. Fortunately there is good math software that can perform routine tasks like this quickly. If we expand this inequality fully, remarkably it has a nice factorisation:

\begin{equation*} r(k-r)(v-k)^2 \le 0\text{.} \end{equation*}

Now, \(r >0\) for any design, and \((v-k)^2\) is a square, so must be nonnegative. Therefore, this inequality forces \(k-r \le 0\text{,}\) so \(k \le r\text{.}\) Hence \(r/k\ge 1\text{.}\) Using Theorem 17.1.7, we have

\begin{equation*} b=vr/k\ge v\text{,} \end{equation*}

as desired.

⬛

Notice that if \(k\) is fixed, then only finitely many values of \(v\) do not meet Fisher's Inequality, so satisfying this inequality did not need to be added as a condition to Wilson's Theorem.

  1. Find values for \(v\text{,}\) \(k\) and \(\lambda\) that satisfy Theorem 17.1.9 but do not satisfy Fisher's Inequality. What can you say about the existence of a design with these parameters?

  2. Suppose that \(\lambda=1\) and \(k=20\text{.}\) How big must \(v\) be to satisfy Fisher's Inequality? What is the smallest value for \(v\) that satisfies all of the necessary conditions?

  3. Suppose that \(\lambda=2\) and \(k=20\text{.}\) How big must \(v\) be to satisfy Fisher's Inequality? What is the smallest value for \(v\) that satisfies all of the necessary conditions?

  4. Explain how you know there does not exist a BIBD with \(v = 46\text{,}\) \(b = 23\text{,}\) and \(k = 10\text{.}\)

  5. Explain how you know there does not exist a BIBD with \(v = 8\text{,}\) \(b = 10\text{,}\) \(k = 4\text{,}\) and \(r = 5\text{.}\)

  6. If \(\bibd\) is a BIBD with \(v = 22\text{,}\) then what can you say about the value of \(b\text{?}\)