2.2. ГРАНИЦА ПЛОТКИНА
Теорема 1. (Граница Плоткина.) Для любого 
-кода при 
справедливо неравенство
Доказательство. Вычислим сумму
двумя способами. Во-первых, так как при 
расстояние 
то сумма не меньше чем 
. С другой стороны, пусть А обозначает 
-матрицу, строками которой являются все кодовые слова. Предположим, что 
столбец А содержит 
нулей и 
единиц. Тогда вклад этого столбца в нашу сумму равен 
и поэтому эта сумма равна
Если число 
четное, то максимум этого выражения достигается при 
для всех 
и поэтому сумма не превышает 
Таким образом, мы имеем:
или
Но число 
четное, и поэтому
С другой стороны, если число 
нечетное, то сумма не превышает 
и вместо (2.2) получим
Отсюда следует, что
(4). Предполагая, что 
-матрица Адамара существует, показать, что
[Указание. Использовать коды 
из гл. 2 на с. 57].
(5). Показать, что
(6). Показать, что
причем равенство достигается тогда и только тогда, когда существует система Штейнера 
до, 
(ср. § 2.5).
Таким образом, из известных фактов о системах Штейнера (см. Чин [277], Колленс [300], Дембовский [370], Деннистон [372], Дуайен и Роза [386], Ханани [595—600], Ди Паола и др. [1020], Вигт [1423, 1424]) вытекают соответствующие результаты о величине 
. Так, например, системы Штейнера 
существуют для всех 
равных степени простого числа [370, гл. 6], и поэтому
Аналогично унитарные поляры проективных геометрий [370, с. 104] дают равенство
Упражнение (6) показывает также, что определение величины 
является в общем случае очень трудной проблемой. Так, например, из (17.10) следует, что 
причем равенство достигается тогда и только тогда, когда существует проективная плоскость порядка 10.
Следующие результаты приводятся без доказательств.
Теорема 6. (Шонхейм [1158]; см. также Форт и Хедлунд [446], Шонхейм [1161], Спенсер [1259] и Свифт (1294].)
Если существуют матрицы Адамара всех возможных порядков (что, однако, до сих пор еще не доказано), то на самом деле в уравнениях (2.3) — (2.6) выполняются равенства. Таким образом, граница Плоткина является точной в том смысле, что существуют коды, достигающие этой границы. В этом и заключается теорема Левенштейна, которая доказывается в следующем параграфе.
