Е. Л. Тарунин
28
ВЕСТНИК ПЕРМСКОГО УНИВЕРСИТЕТА
2010 Математика. Механика. Информатика Вып. 2(2)
15
Пермский государственный университет
Возможности вычислительных методов в проблемах теории чисел
Е.Л. Тарунин
Аннотация
Показано применение персональных компьютеров к решению двух проблем: выявлению закономерности распределения простых чисел и подтверждению гипотезы Эйлера-Гольдбаха.
Ключевые слова: теория простых чисел; численные методы; распределение простых чисел; проблема Гольбаха.
Annotation
Possibilities of numerical methods for problems of number theory
E. L. Tarunin Perm State University
A theory of numbers is famed for using of analytical methods. Grate mathematicians call the theory as a pearl of mathematics. Numerical methods and computers were used in the theory only in the second half of the 20 century. But I dare say that computers may be used more widely. The main aim of the article is to give impulse in that direction. Classical analytical methods deal with smooth functions but the real distribution of simple numbers is a discrete function. So it is more suitable for computers. It was shown that computers permit to find "optimal" parameters of different functions (Chebishev, Lagrange, integral logarithm) that can describe the real distribution of simple numbers more exactly. It was found also new properties of a distribution for so called wins. Corrections of the results will be done by next investigators by expansion of the tested table of simple numbers.
Key wоrds: simple numbers; numerical methods; displasment of simple numbers; goldbods problem.
Основная часть
В теории чисел применяются тонкие аналитические методы [1-3]. Несмотря на малость практических приложений, выдающиеся математики называют эту теорию "жемчужиной математики". Со второй половины XX в. для изучения теории чисел стали применять вычислительную технику. И все же возможности вычислительной техники в этой области используются недостаточно. Перечисление 18 задач теории, которые еще ждут своего решения, содержится в последней главе книги [2].
С помощью ПК удалось подкорректировать коэффициенты в оценках распределения простых чисел и найти новые закономерности. Что касается бинарной гипотезы Гольдбаха (любое четное число может быть представлено суммой двух простых чисел), то следует отметить, что новым результатом в этой области будет доказательство выполнимости гипотезы для чисел более 1010. Такая проверка потребует значительных усилий от опытного программиста. Но игра стоит свеч. За решение проблемы обещан миллион долларов. Правда, в Интернете есть непроверенная информация о том, что условие о награде отменено в 2002 г. Кроме того, там же сказано, что будто бы минский математик доказал гипотезу, но пока его доказательство не проверено. Но даже если премии нет, решение этой проблемы (ей более 3 столетий) даст большое моральное удовлетворение и славу. Достаточно вспомнить, что теорией чисел занимались такие математики, как Ферми, Гаусс, Эйлер, Лагранж, Риман, Дирихле, Чебышев, Виноградов и другие. Отметим, что И.М.Виноградов работал в Пермском университете в 1918-1920 гг. вначале доцентом, а затем профессором.
В Интернете есть предупреждение для тех, кто думает, что проблему можно просто решить. Это предупреждение звучит такУ "Не пытайтесь решать великие проблемы, не поняв теории, которые их окружают. Сэкономьте нервы и себе, и окружающим". Невозможно не согласиться с этим предупреждением. И все же мы полагаем, что у прикладников больше возможностей подступиться к штурму проблем теории чисел, несмотря на то, что им (в отличие от математиков) теорию чисел не излагают. Для ознакомления с теорией чисел существует много учебников [1-5].
В статье содержится 8 разделов. В первых трех разделах приводятся в основном сведения из теории простых чисел, которые будут анализироваться в следующих разделах.
1. Распределение простых чисел
Существование бесконечного множества простых чисел доказывается просто. Однако вопрос о том, как часто среди натуральных чисел встречаются простые и как простые числа распределены среди натуральных, оказывается весьма сложным. Отметим, что в данной статье мы касаемся лишь элементарных методов исследования. Так называются [6] все методы, которые не опираются на применение принципа Римана о нулях дзета-функции или на положения теории функций комплексных переменных.
Число простых чисел, меньших или равных х, как это принято, будем обозначать функцией . Этой функции приписывают гладкость, что не соответствует действительности. Для того чтобы подчеркнуть целочисленные свойства соответствующей функции, в нашей работе будем использовать следующие обозначенияУ i - номер простого числа, а N[i] - значение этого числа. При этом будем считать, что первое простое число равно двум, т.е. N(1)=2, N(2)=3, N(3)=5 и т.д. Функции распределения при этом соответствует ступенчатая функция i(N). Производная этой ступенчатой функции изменяется в широких пределахУ от 1/2 на близнецах до 1/ ( - максимальное расстояние между соседними простыми числами).
Поиск формул, порождающих простые числа, предпринимал еще Ферма (1601-1665). Он высказал предположение, что все числа вида (n - натуральное число) являются простыми [1]. Его предположение оказалось неверным. В 1732 г. Эйлер показал, что при n=5 число является составным. В 1875 г. И.М.Первушин обнаружил, что при n=12 и n=23 также получаются составные числа. В 1837 г. Лежен-Дирихле доказал, что среди членов арифметической прогрессии вида с взаимно простыми числами имеется бесконечное множество простых чисел [1]. Доказывается теорема, что в качестве формулы, порождающей все простые числа, не может быть полином с целыми коэффициентами.
Оценку роста функции распределения получали и уточняли многие ученые. Коснемся лишь тех оценок, которые будут проанализированы. К простейшим оценкам относятся неравенства [5]
Первое неравенство является одним из доказательств бесконечности простых чисел. Последнее неравенство вытекает как следствие гипотезы Бертрана о существовании простого числа на интервале . Справедливость этой гипотезы доказал Чебышев. Расширением гипотезы Бертрана является гипотеза о существовании определенного числа простых чисел на интервале () при 2.
В 1808 г. Лежандр опубликовал эмпирическую формулу [1, 2], предложенную для больших значений x (от 104 до 106)У
(1)
Позднее Чебышевым было указано, что более близкое значение к реальному распределению простых чисел дают функции
(2)
(3)
Обрабатывая имеющиеся таблицы, Гаусс еще в юношеские годы нашел, что функция (3) хорошо аппроксимирует зависимость , но опубликовал этот результатов значительно позднее. Функция в (3) называется интегральным логарифмомУ
Так как [5] и в теории интересуются большими значениями х, то обычно не делают различия между интегральным логарифмом и , при этом функцию также называют интегральным логарифмом.
В 1848-50 гг. были опубликованы работы П.Л.Чебышева, касающиеся роста функции . Чебышев доказал, что при достаточно больших справедливы неравенства
(4)
Для множителей в этих оценках он предложил значения [5]. В [14] указаны более грубые значения для коэффициентов , полученные Чебышевым, видимо, в предварительных оценках. Доказательство П.Л.Чебышева о существовании коэффициентов , обеспечивающих выполнение неравенств (4), содержится, например, в [2]. Значения множителей позднее уточнялись. Уточняются они и в нашей работе. Из теоремы Чебышева, в частности, следует, что при увеличении отношение. Чебышевым было высказано утверждение о существовании асимптотической формулы при
. (5)
Считается, что Чебышевым был решен вопрос о существовании простой функции, предложенной еще Гауссом, которая служит наилучшим приближением для У
Существование предела (5) или, точнее, его следствия при дает утверждение
,
которое было доказано в 1896 г. независимо друг от друга Адамаром и Вале-Пуссеном. Представление о скорости приближения к единице дают полученные значения для номеров и У 1.0992 и 1.09314 соответственно. К сожалению, вычислить значение для известного большого простого числа, например [1], невозможно, так как неизвестен его номер.
Доказательства Адамара и Вале-Пуссена были основаны на рассмотрении дзета-функции Римана. Идея такого подхода к проблеме распределения простых чисел была дана Б. Риманом в 1859 г. Работы этих авторов показали, что функция (3), предложенная Гауссом, дает более точное приближение к , чем функция
. (7)
Отличие функции (3) от функции (7)
, (8)
анализировалось многими математиками. Последователями И.М. Виноградова методом тригонометрических сумм получены оценки модуля , содержащие функции с параметрами. Для существующих таблиц простых чисел обычно величина положительна. Этот факт следует из разложения (3). Из него следует, что относительная ошибка вычисления
(9)
становится менее 5% при
В 1914 г. Литллвуд доказал, что величина принимает бесконечно много значений, как положительных, так и отрицательных. Анализ этой величины на РС (см. ниже) вызывает сомнение в правильности утверждения Литллвуда.
Кроме неравенств Чебышева (4) в теории чисел предлагались следующие неравенства:
. (10)
При решении проблемы распределения простых чисел часто выясняют, на каком интервале от до существует хотя бы одно простое число. В качестве рассматривались, например, значения с параметром . Для этого параметра была получена оценка , а позднее: . Существует недоказанное предположение Лежандра [5] о том, что (). Ответы на указанные вопросы могут быть получены с помощью анализа большой таблицы простых чисел на вычислительной машине.
В качестве примера рассмотрим вопрос о справедливости предположения Дебова (Desboves) [1, с.20]: на интервале от до находится не менее двух простых чисел. Имея таблицу простых чисел, легко убедиться в справедливости предположения и, кроме того, выяснить, как часто появляется число простых чисел 2 и более, находящихся на указанном интервале. При числе простых чисел максимально возможное для проверки значение
Программа выяснила, что два простых числа находятся лишь на двух интервалах с . Далее встречаются числа 3,4,5 с постепенным (не монотонным, как обычно) увеличением числа простых чисел. Расширение интервала, равного , и увеличение простых чисел на них не оставляют сомнений в справедливости предположения. В этих вычислительных экспериментах обнаружился любопытный факт - чаще всего (14 раз, что составляет 2.37% от общего числа рассмотренных интервалов) на интервалах Дебова размещается 74 простых числа. То есть интервалы с меньшим числом простых чисел встречались реже. Например, меньшее число простых чисел равное двум, встретилось лишь три раза при n =2, 3, 5. Максимальное число простых чисел на интервалах Дебова при n590 равнялось 98.
2. Разность между простыми числами
Существует много вопросов, касающихся разности между простыми числами [3]. Среди них выделяются вопросы поведения - разности между соседними простыми числами; количество и распределение близнецов, для которых , или, более общо, пар с разностью равной . С помощью гипотезы Римана доказано, что
(11)
Эвристические рассуждения показывают, что, вероятно, справедлива оценка
(12)
Согласно [3, 6] лучшей к 1983 г. являлась оценка, полученная M.N.Huxley (1973) по методу большого решета:
Вычислительные эксперименты дают поправочные коэффициенты к функциям (11)-(13) и позволяют расставить соответствующие функции в следующем порядке (при достаточно больших ):
,
из которого следует, что лучшей является оценка (12), а не (13).
3. Проблема Гольдбаха
В 1742 г. прусский математик Кристиан Гольдбах в письме Л. Эйлеру высказал предположениеУ "Каждое нечетное число больше 5 можно представить в виде суммы трех простых чисел". По этому поводу Эйлер выдвинул более сильную гипотезуУ "Каждое четное число больше двух можно представить в виде суммы двух простых чисел". Первое утверждение называют тернарной проблемой Гольдбаха, а второе - бинарной проблемой Гольдбаха или Гольдбаха-Эйлера. Из справедливости бинарной проблемы автоматически следует справедливость тернарной проблемы. Действительно, если четное число есть сумма двух простых чисел (m=p1+p2), то, добавляя к каждому четному числу 3, можно получить все нечетные числа, равные сумме трех простых чисел (m+3=p1+p2+3).
Коротко осветим историю вопроса. В 1923 г. Харди и Литлвуд показали, что из справедливости обобщенной гипотезы Римана [3] следует справедливость гипотезы Гольдбаха для всех достаточно больших значений нечетных чисел . В 1937 г. Виноградов, не используя гипотезу Римана, а используя метод тригонометрических сумм, доказал существование . Последователь Виноградова дал оценку для , содержащую 6 млн цифр. В 1989 г. Ванг и Чен опустили нижнюю грань до числа, содержащего 43 тысячи цифр. В 1997 г. четверо ученых показали, что справедливость гипотезы Римана обусловливает справедливость тернарной проблемы Гольдбаха для . Если предыдущие оценки практически не позволяли убедиться в справедливости гипотезы до указанных значений , то последняя оценка дает такую надежду при использовании современной вычислительной техники. Как следует из сказанного, последняя оценка получена из предположения справедливости гипотезы Римана, которая не доказана. Мы не будем останавливаться на обсуждении этой гипотезы, сформулированной в 1859 г. Подтвердим лишь ее сложность и значимость историческими фактами. Однажды Гильберта спросили, чем бы он поинтересовался в первую очередь, если бы проспал 500 лет. Гильберт сказалУ "Я бы спросилУ "Доказана ли гипотеза Римана?" Гипотеза входит в список 7 проблем тысячелетия, за решение каждой из которых Математический институт Кембриджа обещал приз в 1 млн долларов США.