Диофантова задача о "рациональном кубоиде"

Автор:Казаков Ю.В.
Сибирский государственный технологический университет, г. Красноярск

В настоящее время в математике уже утвердилось новое направление, которое можно обозначить, как компьютерная математика. В математических дисциплинах по аналогии с другими научными дисциплинами стала использоваться технология численного эксперимента. В связи развитием вычислительной техники это дает возможность проанализировать серьезные теоретические проблемы. Известно достаточно большое количество работ в алгебре и в теории чисел, где применение компьютеров позволило получить новые результаты. В качестве примеров можно привести хотя бы задачу о плотности распределения простых чисел, где на основе численных экспериментов были проанализированы распределения нескольких десятков миллионов простых чисел и получены результаты, подтверждающие известные теоретические гипотезы. При использовании компьютерных методов решения подобных задач встают вопросы корректности, оптимизации используемых алгоритмов и естественно «конечности» используемых алгоритмов.

Среди всех геометрических диофантовых задач, решение которых не найдено до сих пор, одной из самых трудных и наиболее известных является задача о «целочисленном кирпиче» или задачи о «рациональном кубоиде». Суть которой состоит в том, что бы найти минимальный прямоугольный параллелепипед у которого все стороны и диагонали (включая главную диагональ) являются целыми числами.

В настоящей работе проведен анализ алгоритмов решения задачи. Предложенные алгоритмы реализованы на языке Турбо Паскаль. Известны другие языки программирования, которые позволяют использовать «длинную целочисленную математику», однако их использование на задачах с большим перебором значений приводит к большим временным затратам при проведении вычислений. Проведены оценки параметров, позволяющие уменьшить трудоемкость и время проведения расчета. При этом используются результаты теории чисел о разложения целого числа на сумму двух квадратов. Показано, что в диапазоне длин главной диагонали параллелепипеда до значения d= 2147483648 задача решения не имеет.

Постановка задачи. Найти целочисленное решение системы уравнений (1-4).

	x2+y2=n2
	y2+z2=m2
	z2+x2=k2
	x2+y2+z2=d2

Алгоритм 1. "Тупой до безобразия" алгоритм для "очень быстрых" компьютеров с "длинной целочисленной математикой". Естественно, что достаточно рассматривать только положительные решения для (x,y,z). Если нам удастся найти хотя бы одно решение, то в силу симметрии задачи будет существовать еще 47 целочисленных решений, включая отрицательные значения параметров. Существование решения (x,y,z) можно проверять внутри области (x > 0, y > 0, z > 0) образованной плоскостями x=0, y=x, z=y.Заметим, что в этой задаче невозможны равенства, каких либо двух параметров из (x,y,z). На каждом шаге алгоритма меняем значение параметра x в сторону увеличения, начиная, например, со значения х=3. Параметр у меняем в пределах у=1...x, и соответственно параметр z меняем в пределах z=1...y. При этом проверяем выполнение равенств (1-4). Если решение существует, то рано или поздно оно будет найдено.

Алгоритм 2. Предлагаемый ниже алгоритм имеет некоторые элементы оптимизации по сравнению с алгоритмом 1. Алгоритм строится таким образом, что бы избавить пользователя от вычисления квадратов больших величин и уменьшить перебор за счет использования условия разложения целого числа на сумму двух целых квадратов.

Заметим, что если решение существует, то в соответствии с равенствами (1-4) должно существовать шесть пифагоровых троек

(x,m,d), (y,k,d), (z,n,d), (x,y,n), (x,z,k), (y,z,m)

(5)

Параметром, по которому ведется поиск, является параметр d. Начальное значение d равно 65. При этом необходимо проводить поиск только среди тех d, для которых существует три или более разложения квадрата d на сумму двух квадратов.

Условие существования разложения квадрата d на сумму двух целых квадратов

d2=ai2+bi2, (i=1...n(d))

(6)

требует, чтобы в разложении числа d на множители присутствовало хотя бы два различных простых числа вида (4*t+1). То есть должно иметь место представление:

(7)

где множитель s не содержит простых сомножителей вида (4*t+1).

Если в разложении присутствует только одно число указанного вида, то N(d)=1. А если число d представляется в виде:

	N(d)=4 k1 k2+2(k1+k2)

Если число d представляется в виде

	N(d)=4 (2 k1 k2+(k1+k2))k3+4 k1 k2+2(k1+k2)+2k3

Заметим, что число s, которое входит в разложение не оказывает влияния на количество допустимых пар разложения. И если существует набор пар при s=1, то естественно будет существовать набор и для любого другого s, только каждый элемент пары разложения будут умножен на s. Поэтому нам достаточно перебрать только те значения d, для которых s=1. Как показывают расчеты, плотность таких чисел на "начальном участке" натурального ряда составляет примерно 1/20. Понятие "начальный участок" очень относительное – здесь говорится об участке натуральных чисел, с которым работал автор в процессе реализации алгоритма.

Далее для каждого d, для которого N(d) > 2 ищутся все пары (a,b). Заметим, что для существования разложения необходимо найти три числа (w,r,q), такие что

	d=w(r2+q2)

	(ai,bi), i=1...N(d)

Заметим, что при поиске этих пар нет необходимости возводить в квадрат числа (a_i,b_i,d), так как они составляют пифагорову тройку. В геометрической интерпретации элементы этих троек представляют – первые два элемента это длина стороны искомого параллелепипеда и длина диагонали его боковой грани, последний элемент длина главной диагонали.

Далее, после того как все пары найдены, необходимо проверить существование трех пифагоровых троек (последние три тройки в (5)), которые составлены из элементов множества D (содержащего 2*N(d) элементов)

	D={ai,bi}, i=1...N(d)

Предложенный алгоритм позволяет, не используя "длинную целочисленную математику", значительно расширить диапазон проверенных чисел по сравнению с алгоритмом типа 1. Для каждого значения d анализируются все возможные варианты.

Алгоритм 3. В алгоритме 2 реализована процедура сканирования по параметру d. Однако возможен подход, позволяющий параметризовать задачу таким образом, что будут автоматически выполняться условия целочисленности главной диагонали и целочисленности диагонали одной из граней. При этом остается проверить целочисленность двух оставшихся диагоналей двух боковых граней. Очевидно, что можно рассмотреть задачу в терминах рациональных чисел – и тогда задача сводится к поиску точек с рациональными координатами на сфере единичного радиуса. Положение любой точки на сфере единичного радиуса однозначно описывается двумя углами, а ее декартовы координаты, представляются комбинацией функций синусов и косинусов этих углов. Выбирая значения тригонометрических функций таким образом, чтобы они были рациональными числами, получаем определенные условия, обеспечивающие выполнение (1-4). При определенном выборе параметров, такая параметризация полностью представит все рациональные точки поверхности единичной сферы. Достаточно рассматривать в силу симметрии задачи только 1/48 поверхности сферы. После приведения всех рациональных дробей к общему знаменателю легко получить решение исходной задачи в целых числах.

Такая параметризация имеет вид

	x=4mnrq
	y=2rq(m2-n2)
	z=(m2+n2)(r2-q2)
	d=(m2+n2)(r2+q2)

	(4mnrq)2+((m2+n2)(r2-q2))2=k2
	((m2+n2)(r2-q2))2+(2rq(m2-n2))2=l2

	2FTS=4mnqr
	F(T2-S2)=(m2+n2)(r2-q2)
	2GHE=(m2+n2)(r2-q2)
	G(H2-E2)=2rq(m2-n2)

Перебор вариантов реализуется следующим образом: выбирается начальное значение параметра m, затем параметр n варьируется в пределах от 1 до m-1, далее выбираем параметры r, q - r варьируется в пределах от 1 до m-1, q варьируется в пределах от 1 до r-1. При этом каждый получающийся набор (m, n, r, q) будет уникален.

Можно потребовать выполнения ограничений на величину z

	z < x, z < y.

Это позволяет ограничить количественно варианты перебора возможных значений параметров сверху. Однако поскольку все наборы параметров (m, n, r, q) уникальны – то вопрос целесообразности таких условий необходимо анализировать.

Алгоритм реализован на языке Турбо-Паскаль и расчеты проведены до значения r = 100. В этом диапазоне параметров предлагаемый алгоритм также не дал результатов. Хотя было найдено достаточно много значений параметров, для которых только одна из диагоналей боковых граней нецелое число. Примеры приведены ниже:

Литература. 1. R.K. Guy Unsolved Problems in Number Theory. – Springer Verlag, 1981, p. 97-101.
2. J. Leech "The rational cuboid revisited", Amer. Math. Monthly 84 (1977), p. 518-533

Бочканов Сергей, Быстрицкий Владимир
Copyright © 1999-2004
При поддержке проекта MANUAL.RU