Теорема Брука — Райзера — Човла

Теорема Брука[англ.]—Райзера[англ.]—Човла[англ.] — это результат в комбинаторике блок-схем. Теорема утверждает, что если (v, b, r, k, λ)-схема существует с v = b (симметичная блок-схема), то:

  • если v чётно, то k − λ является квадратом;
  • если v нечётно,то следующее диофантово уравнение имеет нетривиальное решение:
    .

Теорему доказали для случая проективных плоскостей Брук и Райзер[1]. Теорему расширили на симметричные схемы Райзер и Човла[2].

Проективные плоскости

В специальном случае симметричных схем с , то есть проективных плоскостей, теорему (которая в этом случае известна как теорема Брука —Райзера) можно сформулировать следующим образом: Если конечная проективная плоскость порядка q существует и q сравнимо с 1 или 2 (mod 4), то q должно быть суммой двух квадратов. Заметим, что для проективной плоскости для параметров схемы выполняется . Таким образом, в этом случае v всегда нечётно.

Теорема, например, исключает существование проективных плоскостей порядков 6 и 14, но позволяет существование плоскостей порядков 10 и 12. Поскольку было показано с помощью комбинации теории кодирования с крупномасштабным компьютерным поиском, что проективная плоскость порядка 10 не существует[3], условие теоремы очевидно не достаточно для существования схемы. Однако не известно критерия несуществования.

Связь с матрицами инцидентности

Существование симметрической (v, b, r, k, λ)-схемы эквивалентно существованию v × v матрицы инцидентности R с элементами 0 и 1, удовлетворяющей условию

,

где E является v × v единичной матицей, а J — v × v матрицей, в которой все элементы равны 1. По существу, теорема Брука — Райзера — Човла является утверждением о необходимых условиях существования рациональной v × v матрицы R, удовлетворяющей этому уравнению. Фактически, условия, заключённые в теореме Брука — Райзера — Човла, являются не просто необходимыми, но также и достаточны для существования таких рациональных матриц R. Они могут быть выведены из теоремы Минковского — Хассе о рациональной эквивалентности квадратичных форм.

Примечания

  1. ↑ Bruck, Ryser, 1949.
  2. ↑ Chowla, Ryser, 1950.
  3. ↑ Browne, 1988.

Литература

  • Malcolm W. Browne. Is a Math Proof a Proof If No One Can Check It? // The New York Times. — 1988. — 1 декабря.
  • Bruck R.H., Ryser H.J. The nonexistence of certain finite projective planes // Canadian J. Math.. — 1949. — Т. 1. — С. 88–93. — doi:10.4153/cjm-1949-009-2.
  • Chowla S., Ryser H.J. Combinatorial problems // Canadian J. Math.. — 1950. — Т. 2. — С. 93–99. — doi:10.4153/cjm-1950-009-8.
  • C. W. H. Lam. The Search for a Finite Projective Plane of Order 10 // American Mathematical Monthly. — 1991. — Т. 98, вып. 4. — С. 305–318. — doi:10.2307/2323798.
  • van Lint J. H., Wilson R.M. A Course in Combinatorics. — Cambridge: Cambridge University Press, 1992.

Ссылки