4. Реализация задачи на ЭВМ

1. Построение группы коллинеаций проходило в следующем порядке. В машину заложили базовые коллинеации e, A, W_{0, 2} и r в виде подстановок из 91 точки, а также правило композиции таких подстановок. При помощи этого правила получили коллинеацию r^-1 и степени A^m (m = 2,..., 12)коллинеации A. Затем по формулам (6) и (7) были найдены остальные 8 гомологий W_{0, k} с осью a₀. Трансформированием этих гомологий по правилу (4) найдены все 117 гомологий. После этого, учитывая сказанное выше, были перебраны все упорядоченные тройки из 118 подстановок (для 117 полученных гомологий и коллинеации e), если результат композиции тройки оказывался отличным от уже полученных, то он запоминался. В итоге получилось 5616 подстановок (вся группа G₀).

Группу Г построили, используя базовые подстановки u₀, u₁ и формулы (3).

В дальнейшем, при необходимости воспользоваться любой
коллинеацией из группы G, выражаемой в виде композиции гомологий (не более трех гомологий) и коллинеации из группы Г, программой находилась композиция соответствующих подстановок.

2. Опишем алгоритм получения неизоморфных типов k-дуг при k $\geq$ 2 (пример его применения можно посмотреть в Приложении 1).

1) Задаются основные прямые плоскости по точкам (2), по правилу (1) определяются остальные прямые, задаются опорные (неизоморфные) (k - 1)-дуги в лексикографическом порядке.

2) Для каждой (k - 1)-дуги находится множество допустимых точек для расширения этой дуги до k-дуги (из множества всех точек плоскости выбрасываются точки, лежащие на прямых этой (k - 1)-дуги).

3) Множество допустимых точек разбивается на упорядоченные в лексикографическом порядке классы эквивалентности относительно группы автоморфизмов для выбранной опорной (k - 1)-дуги. При этом строится и сама группа автоморфизмов этой опорной дуги (из всех коллинеаций плоскости Хьюза выбираются те, при которых эта (k - 1)-дуга преобразуется сама в себя).

4) Присоединяя по первому представителю от каждого класса эквивалентности к опорной (k - 1)-дуге, получаем k-дуги. Присоединяемая точка должна быть после последней точки опорной (k - 1)-дуги с учетом лексикографического порядка. После обработки всех опорных (k - 1)-дуг в массиве полученных k-дуг могут быть изоморфные.

5) Отождествляем k-дуги из указанного массива: пытаемся преобразовать каждую в каждую с помощью какой-нибудь коллинеации группы G. Если такую коллинеацию найти удалось, значит эти дуги изоморфны, и в дальнейшем процессе отождествления будет участвовать только первая из них в лексикографическом порядке.

6) Неизоморфные k-дуги - искомые. Они могут быть использованы для поиска опорных дуг следующего порядка посредством этого же алгоритма.

3. После предварительной оценки сверху времени построения группы G и выполнения всех 9 шагов вышеописанного алгоритма (если начинать с 1-дуг или 1-наборов точек) для реализации основных операций перебора был выбран язык программирования Assembler, а для организации ввода/вывода информации - Pascal. В таблице Приложения 2 указаны результаты работы программ. Получение всех чисел в этой таблице заняло около 36 часов непрерывной работы машины IBM PS/1 486sx-25MHz. В частности, группа G была построена примерно за 9 минут (с учетом того, что общее число коллинеаций группы G₀ было известно заранее, и при достижении этого значения программа прекращала свою деятельность).

4. Замечания к машинному варианту представления информации, который используется в приложении 1:

а) индексы точек и коллинеаций обозначаются большими цифрами,

б) гомологии представляется в виде Wm, k + m (a_m - ось, A_{k + m} - центр).

Приложение 1.
Пример выполнения одного шага алгоритма расширения опорных дуг

1) Исходный файл с опорными 2-дугами.
A0 A1
A0 B0
A0 B1
B0 B1
B0 C0
B0 E0

2) Файл с разбиением множества допустимых точек (для расширения каждой опорной 2-дуги) на классы C_i эквивалентности относительно группы автоморфизмов этой дуги (| C_i| - число элементов в классе C_i).

Дуга	i	\| C_i\|	C_i
A0 A1	1	9	A2 A4 A5 A6 A7 A8 A10 A11 A12
	2	36	B1 B4 B5 B10 B11 B12 C1 C4 C5 C10 C11 C12 D1 D4 D5 D10 D11 D12 E1 E4 E5 E10 E11 E12 F1 F4 F5 F10 F11 F12 G1 G4 G5 G10 G11 G12
	3	36	B2 B3 B6 B7 B8 B9 C2 C3 C6 C7 C8 C9 D2 D3 D6 D7 D8 D9 E2 E3 E6 E7 E8 E9 F2 F3 F6 F7 F8 F9 G2 G3 G6 G7 G8 G9

Дуга	i	\| C_i\|	C_i
A0 B0	1	9	A2 A4 A5 A6 A7 A8 A10 A11 A12
	2	54	B1 B2 B3 B5 B6 B7 B8 B9 B11 C1 C2 C3 C5 C6 C7 C8 C9 C11 D1 D2 D3 D5 D6 D7 D8 D9 D11 E1 E2 E3 E5 E6 E7 E8 E9 E11 F1 F2 F3 F5 F6 F7 F8 F9 F11 G1 G2 G3 G5 G6 G7 G8 G9 G11
	3	18	B4 B10 B12 C4 C10 C12 D4 D10 D12 E4 E10 E12 F4 F10 F12 G4 G10 G12

A0 B1	1	4	A1 A2 A4 A10
	2	8	A3 A5 A6 A7 A8 A9 A11 A12
	3	24	B0 B4 B10 B12 C0 C4 C10 C12 D0 D4 D10 D12 E0 E4 E10 E12 F0 F4 F10 F12 G0 G4 G10 G12
	4	24	B2 B5 B6 C2 C5 C6 D2 D5 D6 E3 E7 E8 E9 E11 F3 F7 F8 F9 F11 G3 G7 G8 G9 G11
	5	16	B3 B7 B9 B11 C3 C8 C11 D7 D8 D9 F2 F5 F6 G2 G5 G6
	6	2	C1 D1
	7	3	E1 F1 G1
B0 B1	1	6	A0 A2 A3 A4 A9 A10
	2	1	A1
	3	2	A5 A6
	4	3	A7 A11 A12
	5	12	B2 B6 C2 C3 C4 C9 D3 D4 D6 D9 E10 F10
	6	6	B3 B4 B9 C6 D2 G10
	7	6	B5 C5 D5 E5 F5 G5
	8	12	B7 B12 C8 C12 D7 D8 E7 E8 E12 F7 F8 F12
	9	6	B8 C7 D12 G7 G8 G12
	10	3	B11 C11 D11
	11	4	C0 C1 D0 D1
	12	12	C10 D10 E2 E4 E6 F3 F6 F9 G2 G3 G4 G9
	13	6	E0 E1 F0 F1 G0 G1
	14	2	E11 F11
B0 C0	1	9	A2 A4 A5 A6 A7 A8 A10 A11 A12
	2	72	B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 D11 D12 E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 G1 G2 G3 G4 G5 G6 G7 G8 G9 G10 G11 G12
B0 E0	1	9	A2 A4 A5 A6 A7 A8 A10 A11 A12
	2	72	B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 D11 D12 E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 G1 G2 G3 G4 G5 G6 G7 G8 G9 G10 G11 G12

6 - число обработанных опорных 2-дуг.

3) Файл, содержащий расширенные опорные дуги, подлежащие отождествлению.

4) Файл с отчетом по отождествлению дуг (дуги сгруппированы; если указана коллинеация, то дуга преобразуется с помощью нее в дугу без коллинеации, ближайшую выше по списку). Было загружено для обработки 19 3-дуг.

A0 A1 A2	A0 A1 A2
A0 A1 B1	A0 A1 B1
A0 A1 B2	A0 A1 B2
A0 B0 B1	A0 B0 B1
A0 B0 B4	A0 B0 B4
A0 B1 B2	A0 B1 B2
A0 B1 B3	A0 B1 B3
A0 B1 C1	A0 B1 C1
A0 B1 E1	A0 B1 E1
B0 B1 B2	B0 B1 B2
B0 B1 B3	B0 B1 B7	W11,7+11 W6,7+6 W0,4+0 u2
B0 B1 B5	B0 B1 C10	W6,5+6 W3,5+3 W0,5+0
B0 B1 B7	B0 B1 B3
B0 B1 B8	B0 B1 B5
B0 B1 B11	B0 B1 B11	W1,10+1 W0,10+0 u1
B0 B1 C0	B0 B1 B8
B0 B1 C10	B0 B1 C0
B0 B1 E0	B0 B1 E0
B0 B1 E11	B0 B1 E11

В процессе обработки получено 16 типов 3-дуг.

5) Файл, содержащий результаты отождествления (суть опорные 3-дуги для следующего шага).

A0 A1 A2	A0 B0 B4	A0 B1 E1	B0 B1 B8
A0 A1 B1	A0 B1 B2	B0 B1 B2	B0 B1 C0
A0 A1 B2	A0 B1 B3	B0 B1 B3	B0 B1 E0
A0 B0 B1	A0 B1 C1	B0 B1 B5	B0 B1 E11

Приложение 2.
Общие результаты поиска типов k-дуг

В следующей таблице:
m - число особенных точек в составе дуги; N - число типов k-дуг для всех k = 3, 4,..., 10 при каждом m = 0, 1, 2, 3, 4; n - число типов полных k-дуг для всех k = 6,..., 10 при каждом m = 0, 1, 2, 3, 4. Понятно, что в каждой пустой клетке можно было бы записать число "0". Жирным шрифтом выделены новые результаты.

m	4	4	3	3	2	2	1	1	0	0	Всего	Всего
											типов	типов
k	N	n	N	n	N	n	N	n	N	n	дуг	полных
												дуг
3			1		2		6		7		16
4	1		2		12		31		46		92
5	2		14		72		202		230		520
6	9		66	1	305		665		677	1	1722	2
7	11	2	96	8	332	32	647	97	539	59	1625	198
8	7	5	30	29	81	72	110	104	112	106	340	316
9	1		1		2	2	1	1	2		7	3
10	1	1							1	1	2	2

Приложение 3.
Некоторые конкретные результаты исследования

Для каждой опорной k-дуги получены группа автоморфизмов G_i^k, порядок этой группы и число N_i^k дуг, изоморфных данной относительно группы G. Кроме того, выделены и образующие элементы групп G_i^k.


k-дуга	N_i^k	\| G_i^k\|	Образующие G_i^k
Полные 6-дуги:
A₀ A₁ A₂ B₂ C₃ D₇	8424	4	W_{0, 2} u₀; $\enskip$ W_{6, 3} u₀
B₀ B₁ B₅ F₀ F₁ F₅	2808	12	W_{0, 12}; $\enskip$ W_{5, 7} u₁
Неполные 8-дуги:
A₀ A₁ A₂ A₅ B₃ C₇ D₈ E₃	8424	4	W_{12, 6} u₀; $\enskip$ W_{5, 12}
A₀ A₁ A₂ A₅ B₃ C₇ E₃ F₇	2106	16	u₀; $\enskip$ W_{0, 11} u₀; $\enskip$ W_{2, 9}; $\enskip$ W_{3, 8}
A₀ A₁ A₂ B₃ B₈ B₉ G₃ G₈	16848	2	W_{4, 10} u₂
A₀ A₁ B₁ B₂ C₄ D₈ E₁₁ F₁₀	33696	1	e
A₀ A₁ B₁ B₂ C₄ D₈ E₁₁ G₂	33696	1	e
A₀ A₁ B₁ B₂ C₄ E₁₁ F₁₀ G₂	16848	2	W_{8, 3}
A₀ A₁ B₁ B₂ C₅ D₉ F₂ G₄	33696	1	e
A₀ A₁ B₁ B₃ B₁₀ D₆ D₁₂ F₅	33696	1	e
A₀ A₁ B₁ B₃ B₁₀ D₆ D₁₂ G₃	33696	1	e
A₀ A₁ B₁ B₃ B₁₀ D₆ F₅ G₃	33696	1	e
A₀ A₁ B₁ B₃ B₁₀ D₁₂ F₅ G₃	16848	2	W_{6, 3}
A₀ A₁ B₂ B₃ C₉ F₂ F₃ G₉	4212	8	W_{0, 10}; $\enskip$ u₁; $\enskip$ W_{9, 3} u₁
A₀ B₀ B₁ B₂ B₁₂ C₆ D₈ G₂	33696	1	e
A₀ B₀ B₁ B₂ C₅ E₁₁ F₁₀ G₅	33696	1	e
A₀ B₀ B₁ B₅ B₇ C₅ D₇ F₁	33696	1	e
A₀ B₀ B₁ B₅ B₇ C₅ D₇ F₁₀	33696	1	e
A₀ B₀ B₁ B₅ B₇ C₅ F₁ F₁₀	33696	1	e
A₀ B₀ B₁ B₅ B₇ D₇ F₁ F₁₀	33696	1	e
B₀ B₁ B₂ B₃ C₁ D₀ D₁₂ E₂	16848	2	W_{11, 5}
B₀ B₁ B₂ B₇ C₃ E₂ E₇ F₀	33696	1	e
B₀ B₁ B₂ B₇ C₃ E₂ E₇ G₁	16848	2	W_{7, 2}
B₀ B₁ B₂ B₇ C₃ E₂ F₀ G₁	33696	1	e

k-дуга	N_i^k	\| G_i^k\|	Образующие G_i^k
B₀ B₁ B₂ B₇ E₂ E₇ F₀ G₁	8424	4	W_{0, 4}; $\enskip$ W_{1, 3}
B₀ B₁ B₅ B₁₁ E₁ E₁₁ G₀ G₅	2106	16	W_{0, 6}; $\enskip$ W_{5, 7} W_{0, 7} W_{0, 2} u₁
Полные 9-дуги:
A₀ A₁ B₁ B₂ C₄ D₈ E₁₁ F₁₀ G₂	16848	2	W_{8, 3}
A₀ A₁ B₁ B₃ B₁₀ D₆ D₁₂ F₅ G₃	16848	2	W_{6, 3}
A₀ B₀ B₁ B₅ B₇ C₅ D₇ F₁ F₁₀	16848	2	W_{12, 4}
Неполные 9-дуги:
A₀ A₁ A₂ A₅ B₃ C₇ D₈ E₃ F₇	4212	8	W_{0, 11} u₀; $\enskip$ W_{2, 9} u₀; $\enskip$ W_{3, 8} u₀
A₀ A₁ A₂ B₃ B₈ B₉ G₃ G₈ G₉	2808	12	u₂; $\enskip$ W_{4, 10} u₂; $\enskip$ W_{6, 3} u₂
B₀ B₁ B₂ B₇ C₃ E₂ E₇ F₀ G₁	16848	2	W_{3, 1}
B₀ B₁ B₂ B₇ C₃ E₂ E₇ F₀ G₃	4212	8	W_{3, 10} W_{0, 10} W_{0, 2} u₂
10-дуги:
A₀ A₁ A₂ A₅ B₃ C₇ D₈ E₃ F₇ G₈	702	48	u₀; $\enskip$ W_{0, 11}; $\enskip$ W_{4, 10}; $\enskip$ W_{2, 9}
B₀ B₁ B₂ B₇ C₃ E₂ E₇ F₀ G₁ G₃	2106	16	W_{0, 4}; $\enskip$ W_{3, 10} W_{0, 10} W_{0, 2} u₂

Группа автоморфизмов последней 9-дуги в явном виде

W_{3, 10} W_{0, 10} W_{0, 2} u₂	=	a - образующая
W_{7, 2} W_{0, 4}	=	a²
W_{3, 2} W_{0, 4} W_{0, 2} u₂	=	a³
W_{1, 3}	=	a⁴
W_{7, 4} W_{0, 10} W_{0, 2} u₂	=	a⁵
W_{2, 10} W_{0, 4}	=	a⁶
W_{2, 4} W_{0, 4} W_{0, 2} u₂	=	a⁷
e	=	a⁸