17.3: Desigualdad de Fisher

Hay una desigualdad más importante que no es para nada obvia, pero que es necesaria para la existencia de un BIBD\((v, k, λ)\). Esto se conoce como Fisher's Inequality ya que fue probado por Fisher. La prueba que daremos es algo más larga que la prueba estándar. Esto se debe a que la prueba estándar utiliza álgebra lineal, que no se requiere de antecedentes para este curso.

Teorema\(\PageIndex{1}\)

Para cualquier BIBD\((v, k, λ)\), debemos tener\(b ≥ v\).

Antes de probar este hecho, observemos las consecuencias en términos de los parámetros habituales:\(v\),\(k\), y\(λ\). Sabemos por la Ecuación 17.1.5 que

\[b = \dfrac{λv(v − 1)}{k(k − 1)}, \label{17.3.1}\]

por lo que\(b ≥ v\) implica

\[\dfrac{λv(v − 1)}{k(k − 1)} ≥ v. \label{17.3.2}\]

Ya que\(v\) es el número de puntos de un diseño, debe ser positivo, por lo que dividirlo por\(v\) no revierte la desigualdad. Por lo tanto,

\[\dfrac{λ(v − 1)}{k(k − 1)} ≥ 1. \label{17.3.3}\]

Ya que\(k\) es el número de puntos en cada bloque, ambos\(k\) y\(k−1\) deben ser positivos (estamos ignorando el caso trivial\(k = 1\)), por lo que multiplicar por\((k−1)\) no revierte la desigualdad. Por lo tanto,

\[λ(v − 1) ≥ k(k − 1). \label{17.3.4}\]

Prueba

Supongamos que tenemos un BIBD arbitrario\((v, k, λ)\). Dejemos\(B\) ser un bloque arbitrario de este diseño. Por cada valor de\(i\) entre\(0\) y\(k\) (inclusive), vamos a\(n_i\) denotar el número de bloques\(B' \neq B\) tal que\(|B' ∩ B| = i\). (Cuando decimos\(B' \neq B\) permitimos que los bloques sean iguales como conjuntos si el bloque\(B\) es un bloque repetido del diseño; sólo estamos insistiendo en que\(B'\) no sea exactamente el mismo bloque del diseño que\(B\).)

Las siguientes ecuaciones que involucran\(n_i\) son consecuencias de pruebas combinatorias fáciles, junto con la definición de\(n_i\):

\[ \sum_{i=0}^{k} n_i = b − 1, \label{17.3.5}\]

porque ambos lados de esta ecuación cuentan cada bloque excepto\(B\).

\[ \sum_{i=0}^{k} in_i = k(r − 1), \label{17.3.6}\]

porque ambos lados de esta ecuación cuentan el número de veces que los elementos de\(B\) aparecen en algún otro bloque del diseño.

\[ \sum_{i=2}^{k} i(i-1)n_i = k(k − 1)(λ − 1), \label{17.3.7}\]

porque ambos lados de esta ecuación cuentan el número de veces que todos los pares ordenados de elementos\(B\) aparecen juntos en algún otro bloque del diseño. Tenga en cuenta que cuando\(i = 0\) o\(i = 1\), tenemos\(i(i − 1)n_i = 0\), así que de hecho

\[ \sum_{i=0}^{k} i(i-1)n_i = \sum_{i=2}^{k} i(i-1)n_i = k(k − 1)(λ − 1). \label{17.3.8}\]

Añadiendo ecuaciones\ ref {17.3.6} y\ ref {17.3.8} da

\[ \sum_{i=0}^{k} i^2 n_i = k(k − 1)(λ − 1) + k(r − 1). \label{17.3.9}\]

Ahora viene la parte de la prueba donde sucede algo misterioso, y por razones que no son para nada aparentes, surgirá el resultado que queremos. Para entender completamente una prueba como esta se requiere matemáticas más profundas, pero incluso ver una prueba es útil para convencernos de que el resultado es cierto.

\[ \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} i n_i + \sum_{i=0}^{k} i^2 n_i \label{17.3.10}\]

Usando ecuaciones\ ref {17.3.5},\ ref {17.3.6}, y\ ref {17.3.9}, vemos que esto es igual a

\[x^2 (b − 1) − 2xk(r − 1) + k(k − 1)(λ − 1) + k(r − 1).\]

Observe que el formato en el que comenzó este polinomio era una suma de cuadrados por enteros no negativos, por lo que su valor debe ser no negativo para cualquiera\(x ∈ \mathbb{R}\).

Usando la fórmula cuadrática,\(ax^2 + b'x + c = 0\) tiene raíces en

\[\dfrac{−b' ± \sqrt{(b')^2 − 4ac}}{2a}\]

Si un polinomio cuadrático tiene dos raíces reales, entonces hay una región en la que sus valores son negativos. Dado que este polinomio no es negativo para cada uno\(x ∈ \mathbb{R}\), puede tener como máximo una raíz real, entonces\((b')^2 − 4ac ≤ 0\). Sustituyendo los valores reales de nuestro polinomio, esto significa que

\[−2k(r − 1))^2 − 4(b − 1)(k(k − 1)(λ − 1) + k(r − 1)) ≤ 0.\]

Por lo tanto,

\[k^2 (r − 1)^2 − k(b − 1)((k − 1)(λ − 1) + r − 1) ≤ 0.\]

Vamos a reescribir el\(b\) en términos de\(v\),\(r\), y\(k\). Por el Teorema 17.1.1, tenemos\(bk = vr\), entonces

\[k(b − 1) = bk − k = vr − k.\]

De ahí

\[k^2 (r − 1)^2 − (vr − k)((k − 1)(λ − 1) + r − 1) ≤ 0.\]

Expandir ligeramente el segundo término y multiplicar ambos lados de la desigualdad por\(v − 1\):

\[k^2 (r − 1)^2 (v − 1) − (vr − k)(k − 1)(λ − 1)(v − 1) − (vr − k)(r − 1)(v − 1) ≤ 0\]

En la expresión media, tenemos\((λ − 1)(v − 1)\). Por el Teorema 17.1.1, lo sabemos\(λ = \dfrac{r(k − 1)}{(v − 1)}\), entonces

\[λ − 1 = \dfrac{r(k − 1) − (v − 1)}{v-1} \]

Por lo tanto,

\[(λ − 1)(v − 1) = r(k − 1) − v + 1.\]

Por lo tanto, tenemos

\[k^2 (r − 1)^2 (v − 1) − (vr − k)(k − 1)(rk − r − v + 1) − (vr − k)(r − 1)(v − 1) ≤ 0. \]

El siguiente paso es mucho trabajo por hacer a mano. Afortunadamente hay un buen software matemático que puede realizar tareas rutinarias como esta rápidamente. Si ampliamos completamente esta desigualdad, notablemente tiene una buena factorización:

\[r(k − r)(v − k)^2 ≤ 0\]

Ahora,\(r > 0\) para cualquier diseño, y\((v − k)^2\) es un cuadrado, por lo que debe ser no negativo. Por lo tanto, esta desigualdad obliga\(k − r ≤ 0\), entonces\(k ≤ r\). De ahí\(\dfrac{r}{k} ≥ 1\). Usando el Teorema 17.1.1, tenemos

\[b = \dfrac{vr}{k} ≥ v,\]

según se desee.

Observe que si\(k\) es fijo, entonces solo finitamente muchos valores de\(v\) no cumplen con la Desigualdad de Fisher, por lo que satisfacer esta desigualdad no necesitó agregarse como condición al Teorema de Wilson.

Ejercicio\(\PageIndex{1}\)

1) Encontrar valores para\(v\)\(k\), y\(λ\) que satisfagan el Teorema 17.1.3 pero que no satisfagan la Desigualdad de Fisher. ¿Qué se puede decir de la existencia de un diseño con estos parámetros?

2) Supongamos que\(λ = 1\) y\(k = 20\). ¿Qué tan grande debe\(v\) ser para satisfacer la Desigualdad de Fisher? ¿Cuál es el valor más pequeño para\(v\) que satisfaga todas las condiciones necesarias?

3) Supongamos que\(λ = 2\) y\(k = 20\). ¿Qué tan grande debe\(v\) ser para satisfacer la Desigualdad de Fisher? ¿Cuál es el valor más pequeño para\(v\) que satisfaga todas las condiciones necesarias?

4) Explique cómo sabe que no existe un BIBD con\(v = 46\),\(b = 23\), y\(k = 10\).

5) Explica cómo sabes que no existe un BIBD con\(v = 8\),\(b = 10\),\(k = 4\), y\(r = 5\).

6) Si\(\mathcal{B}\) es un BIBD con\(v = 22\), entonces ¿qué se puede decir sobre el valor de\(b\)?