РАЗНОСТНОЕ МНОЖЕСТВО

совершенное разностное множество,- множество D, состоящее из kвычетов но модулю некрого натурального числа , причем для каждого , , существует точно l упорядоченных пар (d_i, d_j).элементов из Dтаких, что числа наз. п а р а м е т р а м и Р. м. Напр., множество D = {1, 3, 4, 5, 9} вычетов по модулю 11 есть Р. м. с l= 2.

Р. м. тесно связаны с блок-схемами, аименно: существование Р. м. равносильно существованию симметричной блок-схемы с параметрами , обладающей циклич. группой автоморфизмов порядка (блоки такой схемы суть множества ). Идея Р. м. обобщается следующим образом: множество D, состоящее из kразличных элементов d₁,. . ., группы G порядка , наз. -разностным множеством в G, если для любого , , существует в точности l упорядоченных пар (d_i, d_j),, таких, что (или, что то же, l. пар (d_i, d_j) с d^-1_i d_j=a). Тогда определенное выше Р. м. наз. ц и к л и ч е с к и м Р. м. (т. к. группа классов вычетов по mod есть циклич. группа). Существование -разностных множеств в группе Gпорядка равносильно существованию симметричной блок-схемы с параметрами , допускающей G в качестве регулярной (т. е. без неподвижных элементов) группы автоморфизмов (эта схема получается отождествлением элементов блок-схемы с элементами группы и блоков - с множествами , где gпробегает G).

Основным в теории Р. м. является вопрос о существовании и построении Р. м. с заданными параметрами.

При его изучении оказывается полезным понятие множителя Р. м.: автоморфизм группы G наз. множителем -разностного множества Dв G, если он является также автоморфизмом блок-схемы, определяемой Р. м. D. Для циклического Р. м. множитель - это число t, взаимно простое с и с тем свойством, что

для нек-рого i, . Множители циклического Р. м. образуют группу. Справедливо утверждение: если D - циклическое -разностное множество и если р - простое число, делящее k-l и такое, что и , то р-множитель D(т е о р е м а о м н о ж и т е л е Р. м.). При построении Р. м. полезен следующий результат: для любого множителя -разностного множества Dв абелевой группе Gпорядка в блок-схеме, определяемой D, существует блок, фиксируемый этим множителем; при существует блок, фиксируемый любым множителем.

Р. м. обычно строятся прямыми методами с использованием свойств конечных полей, полей деления круга (см. Круговое поле), а также конечных геометрий. Известно несколько бесконечных семейств Р. м., напр. следующие типы Sи Q.

Тип S (р а з н о с т н ы е м н о ж е ст в а З и нг е р а): это - гиперплоскости в n-мерной проективной геометрии над полем из элементов; параметры:

тип Q:квадратичные вычеты в поле при ( р - простое число); параметры:

Другие бесконечные семейства Р. м. см. р [1]-[3]. Наряду с Р. м. часто рассматриваются обобщенные P.M., или р а з н о с т н ы е с е м е й с т в а,- это множества D₁,. . ., D_r, состоящие из. вычетов по и такие, что для любого существует точно l упорядоченных пар ,

c

для нек-рого

Имеются также другие обобщения Р. м.

Лит.:[1] Х о л л М., Комбинаторика, пер. с англ., М., 1970; [2] В a u m е г t L. D., Cyclic difference sets, В.- Hdlb.-N.Y., 1971; [3] Н а 1 1 M., "Math. Centre Tracts", 1974, v. 57, p. 1-26.

В. Е. Тараканов.