http://www.ega-math.narod.ru/Quant/
| | Ю. В. Матиясевич
 |
Что требуется?
Простые числа разбросаны в натуральном ряду очень прихотливым образом, и не удивительно, что издревле математики стремились найти «формулу для простых чисел». Такими формулами можно называть формулы, обладающие разными свойствами, и здесь очень важно понять, что нам требуется на самом деле.
Самая простая формула для простых чисел выглядит, по-видимому, так:
где pn обозначает n-е простое число. Чем же эта формула не устраивает нас? Дело в том, что правая часть этого равенства вычисляется слишком сложным образом — попробуйте, например, самостоятельно найти p1975! Мы же хотим получить аналогичную формулу с возможно более простым способом вычисления правой части (однако, как мы увидим, простота вычислений — понятие совсем не очевидное). Это, так сказать, программа-максимум.
Ради простоты формулы можно отказаться от требования явной зависимости от номера n и искать формулы, дающие простые числа, быть может, не по порядку. Далее, можно отказаться от желания задать одной формулой сразу все простые числа и требовать только того, чтобы формула давала бесконечно много простых чисел. Можно, наконец, допустить, чтобы эта формула давала наряду с бесконечно многими простыми числами и некоторые составные числа. Это — программа-минимум.
Формулы, кажущиеся очень простыми, на деле могут оказаться не лучше формулы (1). Именно к таким примерам мы сейчас и переходим.
Теорема Е. М. Райта
В 1947 году В. X. Миллс опубликовал следующий результат:
Существует вещественное число λ такое, что при любом n = 1, 2, ... число
Впоследствии появился ещё ряд формул такого же типа. Однако все это были результаты, формулировка которых выглядит заманчивой и многообещающей, но доказательство разочаровывает. Тому, кто хочет понять, почему это так, мы предлагаем разобраться в доказательстве следующей теоремы Е. М. Райта:
Существует вещественное число μ такое, что всякое число вида
является простым.
Ключевым пунктом в доказательстве теоремы Райта является так называемый
постулат Бертрана. Согласно этому постулату при
x≥4 между
x и
2x–2 всегда есть простое число. Эту гипотезу впервые высказал французский математик Бертран: доказать её он не смог, а потому использовал в своих рассуждениях в качестве недоказуемого постулата. Доказательство гипотезы Бертрана было найдено впоследствии выдающимся русским математиком П. Л. Чебышёвым
2.
Чтобы найти нужное число μ выберем сначала последовательность простых чисел q1, q2, ..., такую, что при любом n=1, 2, ...
(В качестве q1 можно взять любое простое число, возможность же неограниченного продолжения последовательности {qn} с соблюдением неравенства (4) гарантирует постулат Бертрана.)
Обозначим для краткости число
где берётся n возведений в степень, через exp2nα, a обратную функцию,
log2 log2 ... log2 β
— через log 2nβ.
Попробуем выбрать число μ так, чтобы при n=1, 2, ...
Согласно определению целой части числа равенство (5) эквивалентно неравенству
qn ≤ exp2nμ < qn + 1.
Прологарифмировав его n раз по основанию 2, получим ещё одно двойное неравенство, эквивалентное (5):
| log 2nqn ≤ μ < log 2n(qn + 1). | (6) |
Проверьте сами, что из (4) следует
log 21q1 < log 22q2 < ... < log 2nqn < log 2n+1qn+1 < ...
... < log 2n+1(qn+1 + 1) < log 2n(qn + 1) < ... < log 22(q2 + 1) < log 21(q1 + 1).
Таким образом, последовательность
log 21q1, log 22q2, ..., log 2nqn, ...
строго возрастает и ограничена сверху; следовательно, она имеет предел. Его-то мы и возьмём в качестве числа μ; докажите, что так выбранное μ удовлетворяет даже более сильному, чем (6),неравенству
| log 2nqn < μ < log 2n(qn + 1), | (7) |
и, следовательно, равенство (5) справедливо. Теорема Райта доказана.
Основным недостатком формул (2) и (3) является то, что они (точнее, их доказательства) не дают никакого способа находить новые простые числа, ибо чтобы вычислить какое-либопростое число по формулам (2) или (3), нужно числа λ и μ знать с достаточной точностью. Таким образом, формулы (2) и (3) в некотором смысле являются всего лишь замаскированными (и ухудшенными) вариантами формулы (1). Кроме того, вид формул (2) и (3) на самом деле почти ничего не говорит именно о множестве простых чисел. Из доказательства теоремы Райта видно, что формулы, аналогичные (2), (3), можно указать для любого «достаточно густого» множества.
Недостатки формул (2) и (3) порождены тем, что в них входят вещественные числа λ и μ, задаваемые неким косвенным образом. В дальнейшем мы будем рассматривать лишь формулы, в которые входят только целочисленные коэффициенты. Такие формулы обладают важным преимуществом: они могут быть (в принципе) выписаны явно.
Простые числа Мерсенна и Ферма
Формулы Миллса, Райта и другие подобные формулы остались изолированными фактами, не приведшими к новым результатам. Однако в других случаях возможность представить некоторые простые числа в том или ином специальном виде имеет неожиданные и глубокие следствия.
Рассмотрим сейчас две формулы, имеющие совсем простой вид:
| p = 2n – 1, | (8) |
| p = 2n + 1. | (9) |
Очевидно, что формула (8) не всегда даёт простые числа; например, если n — составное число, n = kl, k>1, l>1, то p делится на 2k — 1 и на 2l — 1. Но и при простом n получающееся поформуле (8) число может оказаться составным:
211 – 1 = 2047 = 23 · 89.
Простые числа, получающиеся по формуле (8), называются числами Мерсенна в честь Марена Мерсенна, который ещё в 1664 году указал все простые значения n, не превосходящие 257, для которых, по его мнению, формула (8) даёт простые числа. Однако Мерсенн не дал доказательства; впоследствии выяснилось, что его предсказание было частично ошибочным.
Интерес к числам Мерсенна вызван их связью с так называемыми совершенными числами — числами, равными сумме всех своих делителей, отличных, конечно, от самого числа. Ещё Евклид доказал (докажите и вы), что если простое число p имеет вид, указанный в формуле (8), то число p(p+1)/2 является совершенным. Например,
3 = 22 – 1, 7 = 23 – 1
простые числа, и соответственно
| 6 = | (3 · 4)/2 = 1 + 2 + 3, |
| 28 = | (7 · 8)/2 = 1 + 2 + 4 + 7 + 14 |
— совершенные числа. Спустя несколько столетий Леонард Эйлер доказал (попробуйте и здесь свои силы), что все
чётные совершенные числа имеют вид, указанный Евклидом. Таким образом, вопрос, конечно или бесконечно множество чётных совершенных чисел, свёлся к вопросу, конечно или бесконечно множество простых чисел Мерсенна, то есть к вопросу, реализует ли
формула (8) нашу программу-минимум. Ответ на этот вопрос не известен до сих пор
3.
Формула (9) также не всегда даёт простые числа, например, если n имеет простой нечётный делитель m, то p делится на 2n/m + 1, а если n само нечётно, то p делится на 3. Таким образом, вместо n в формулу (9) имеет смысл подставлять только 0 и степени числа 2. При n=0, 20, 21, 22, 23 и 24 формула (9) действительно даёт простые числа, и Пьер Ферма, живший в XVII веке, высказал предположение, что и при любом n вида 2k формула (9) даёт простое число; в его честь простые числа вида 22k + 1 получили название чисел Ферма. Гипотезу Ферма опроверг Эйлер, указавший, что число 225 + 1 делится на 641. В настоящее время известно несколько значений n вида 2k, при которых по формуле (9) получаются составные числа, но не найдено ни одного нового простого числа Ферма, отличного от указанных выше.
Простые числа Ферма обнаруживают неожиданную связь с геометрией. Выдающийся немецкий математик Карл Фридрих Гаусс доказал, что правильный
p-угольник можно построить циркулем и линейкой при
простом p в том и только том случае, когда
p — число Ферма
4. Более общий результат таков: правильный
m-угольник допускает построение циркулем и линейкой тогда и только тогда, когда
m = 2s· p1 p2 ...pk , где
p1,
p2, ..., pk — попарно различные простые числа Ферма.
Скатерть Улама
Формулы (8) и (9) содержат возведение в степень. А нельзя ли для задания бесконечно многих простых чисел обойтись лишь сложением, вычитанием и умножением? Поищем ответ на этот вопрос.
Начнём с рассмотрения многочленов от одной переменной с натуральными коэффициентами; посмотрим, какие многочлены будут своими значениями иметь простые числа и в каком количестве.
Возьмём вначале многочлены первой степени (то есть линейные многочлены). Очевидно, что тривиальный многочлен x задаёт бесконечно много простых чисел, более того, все простые числа, но это неинтересный случай. А что можно сказать о многочлене ax+b (где a, b и x — натуральные числа)? Ясно, что если a и b имеют общий делитель, отличный от 1, то значение многочлена ax+b — число составное, кратное этому делителю. Случай же, когда a и b взаимно просты, гораздо менее очевиден.
Французский математик Лежандр (живший в XVIII веке) высказал гипотезу, что если a и b взаимно просты, то в арифметической прогрессии с первым членом b и разностью a встречается бесконечно много простых чисел. Эта гипотеза была доказана лишь в XIX столетии немецким математиком Леженом Дирихле.
Перейдём теперь к квадратным многочленам. Среди них есть «рекордсмены», например, многочлен x2 + x + 41 — его изучал ещё Леонард Эйлер. Этот многочлен принимает простые значения при x = 1, 2, ..., 40. При x = 41 его значение — составное.
Доказано, что никакой многочлен (отличный, разумеется, от константы) не может иметь в качестве значений только простые числа, но до сих пор не известно, существует ли многочлен (кроме линейного), среди значений которого встречается бесконечно много простых чисел.
Интерес к представлению простых чисел в виде значений квадратных многочленов недавно возродился в связи с неожиданным наблюдением С. М. Улама
5. Начав на спирали из всех натуральных чисел (рис. 1) отмечать простые числа, Улам с удивлением обнаружил, что простые числа выстраиваются по диагоналям, образуя довольно длинные цепочки. (Докажите, что числа, расположенные вдоль
какой-либо диагонали в пределах, ограниченных на рис. 1 красными линиями — это значения некоторого квадратного многочлена с целыми коэффициентами).
| 197 | 196 | 195 | 194 | 193 | 192 | 191 | 190 | 189 | 188 | 187 | 186 | 185 | 184 | 183 |
| 198 | 145 | 144 | 143 | 142 | 141 | 140 | 139 | 138 | 137 | 136 | 135 | 134 | 133 | 182 |
| 199 | 146 | 101 | 100 | 99 | 98 | 97 | 96 | 95 | 94 | 93 | 92 | 91 | 132 | 181 |
| 200 | 147 | 102 | 65 | 64 | 63 | 62 | 61 | 60 | 59 | 58 | 57 | 90 | 131 | 180 |
| 201 | 148 | 103 | 66 | 37 | 36 | 35 | 34 | 33 | 32 | 31 | 56 | 89 | 130 | 179 |
| 202 | 149 | 104 | 67 | 38 | 17 | 16 | 15 | 14 | 13 | 30 | 55 | 88 | 129 | 178 |
| 203 | 150 | 105 | 68 | 39 | 18 | 5 | 4 | 3 | 12 | 29 | 54 | 87 | 128 | 177 |
| 204 | 151 | 106 | 69 | 40 | 19 | 6 | 1 | 2 | 11 | 28 | 53 | 86 | 127 | 176 |
| 205 | 152 | 107 | 70 | 41 | 20 | 7 | 8 | 9 | 10 | 27 | 52 | 85 | 126 | 175 |
| 206 | 153 | 108 | 71 | 42 | 21 | 22 | 23 | 24 | 25 | 26 | 51 | 84 | 125 | 174 |
| 207 | 154 | 109 | 72 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 83 | 124 | 173 |
| 208 | 155 | 110 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 123 | 172 |
| 209 | 156 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 171 |
| 210 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 |
| 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |
Рис. 1.
Ещё более удивительным оказалось то, что закономерность эта наблюдалась и тогда, когда спираль была продолжена (с помощью компьютера) до больших чисел — на рис. 2 светлыми точками отмечены простые числа на спирали из первых 10 000 чисел. Узор, изображённый на рис. 2, получил название «скатерть Улама».
Рис. 2.
Чтобы отмеченная закономерность проявилась, не обязательно начинать спираль с единицы. Например, значения многочлена x2 + x + 41 выстраиваются по диагоналям у спирали, начинающейся с числа 41 (рис. 3).
| 57 | 56 | 55 | 54 | 53 |
| 58 | 45 | 44 | 43 | 52 |
| 59 | 46 | 41 | 42 | 51 |
| 60 | 47 | 48 | 49 | 50 |
| 61 | 62 | 63 | 64 | 65 |
Рис. 3.
Возможно, что читатели «Кванта», проявив изобретательность и должное терпение, смогут найти новые красивые «геометрические» закономерности расположения простых чисел среди множества всех чисел.
Феномен со стремлением простых чисел располагаться в цепочки вдоль диагоналей был обнаружен сравнительно недавно и ещё не получил какого-либо математического объяснения.
О представлении простых чисел с помощью многочленов от многих переменных мы скажем в конце статьи.
Экспоненциальный многочлен Джулии Робинсон
Экспоненциальные многочлены отличаются от обычных тем, что в них показателями степени могут быть не только конкретные натуральные числа, но и линейные многочлены от переменных с натуральными коэффициентами, то есть многочлены вида
a1x1 + a2x2 + ... + ak xk + b,
где a1, a2, ..., ak , b — целые неотрицательные числа.
Простейшими примерами экспоненциальных многочленов от переменной n являются правые части формул (8) и (9).
В дальнейшем мы всегда будем предполагать, что все встречающиеся у нас переменные принимают целые положительные значения.
В 1952 году американский математик Джулия Робинсон
6 опубликовала следующий замечательный результат:
Существует экспоненциальный многочлен R(x0, ..., xk ), такой, что
- любое его положительное значение при целых положительных значениях переменных является простым числом;
- любое простое число можно представить в таком виде.
В результате получается такая «формула для простых чисел»:
| p = R(x0, ..., xk ). | (10) |
Эта формула замечательна вот чем.
Во-первых, в неё входят только целые числа, и потому, в отличие от формул Миллса, Райта и им подобных, формула Джулии Робинсон может быть выписана явно.
Во-вторых, она задаёт все простые числа, а не только
какие-то избранные из них, в отличие от всех рассмотренных выше формул.
В-третьих, хотя
формула (10) задаёт и не только простые числа, у нас есть очень простой способ отсеивания «лишних» чисел: каждое не простое
значение R при целых положительных значениях неизвестных не превосходит нуля. Этим формула Джулии Робинсон выгодно отличается от
формул (8) и (9), а также и от только что рассмотренных
полиномиальных формул 7.
Доказательство Джулии Робинсон совершенно элементарно. Ниже излагаются его основные идеи; доведение же доказательства до формальной строгости мы оставляем читателям: все промежуточные результаты сформулированы в виде пяти лемм, — их-то и нужно доказать. Как мы увидим, из этих лемм следует не только существование экспоненциального многочлена R, но и его явный вид.
Что мы должны сделать?
Чтобы доказать теорему Джулии Робинсон, мы, очевидно, должны указать экспоненциальный многочлен R такой, что уравнение (10) разрешимо в натуральных числах относительно переменных x0, ..., xk тогда и только тогда, когда выполнено следующее условие:
Это — пример условия на переменную p.
Приведём ещё несколько примеров условий на набор переменных
| λ1, ..., λn, x0, ..., xk . | (11′) |
Если мы потребуем, чтобы набор чисел (11) удовлетворял системе уравнений вида
| Fi(λ1, ..., λn, x0, ..., xk ) = 0 (i = 1, ..., s), | (11″) |
или допустим словесное описание типа: «все λi — простые числа», или «λ1 — простое число, x0, ..., xk — чётные числа» и т.д., то тем самым мы из множества всех наборов (11′) выделимнекоторые, подчиняющиеся наложенному на них условию.
Мы не станем точно определять, условия какого вида являются для нас допустимыми. Приведённое описание примеров условий достаточно для оправдания того способа действий, которым мы в дальнейшем будем пользоваться.
В последующем изложении мы будем различать переменные, называя некоторые из них параметрами, так что деление переменных на параметры и неизвестные у нас является чисто условным.
Если все левые части системы уравнений (11″) являются экспоненциальными многочленами от λ1, ..., λn, x0, ..., xk , и решения этой системы ищутся в целых положительных числах, то такая система называется экспоненциально диофантовой; если Fi — обыкновенные многочлены, то система уравнений (11″) называется просто диофантовой.
Уравнение (10) является примером экспоненциально диофантова уравнения относительно переменных p, x0, ..., xk .
Мы будем говорить, что две системы условий, имеющие одни и те же параметры, эквивалентны друг другу относительно этих параметров, если множество тех значений параметров, при которых имеет решение одна из этих систем, совпадает со множеством тех значений параметров, при котором имеет решение и другая система. (Обратите внимание, что в этом определении ничего не говорится о связи значений неизвестных — для наших целей это неважно, эквивалентные в нашем понимании системы могут вообще не иметь общих неизвестных.)
Примером эквивалентных условий относительно параметра λ, могут служить неравенство
2n < λ < 2n+1
и равенство
λ = (2x0 + 1)·x1.
Ясно, что каждое из этих условий имеет решение тогда и только тогда, когда параметр λ принадлежит множеству чисел, не являющихся целыми степенями числа 2.
В этой терминологии наша цель формулируется так: найти экспоненциальный многочлен R(x0, ..., xk ), такой, что условие (10) эквивалентно условию (11) относительно параметра p.
Однако требование, чтобы параметр p стоял только в левой части равенства (10), является, как мы сейчас увидим, излишне жёстким.
Пусть удалось найти экспоненциальный многочлен Q(p, x1, ..., xk ), такой, что экспоненциально диофантово уравнение (условие на p, x1, ..., xk )
| Q(p, x1, ..., xk ) = 0 | (12) |
эквивалентно условию (11).
Положим
| R(x0, ..., xk ) = x0·(1 – Q 2(x0, ..., xk )). | (13) |
Лемма 1. Если экспоненциальные многочлены R и Q связаны соотношением (13), то уравнения (10) и (12) эквивалентны относительно параметра p.
Нам достаточно даже найти не уравнение, а хотя бы систему экспоненциально диофантовых уравнений
|
|
| Q1( p, x1, ... , xk ) = 0, |
| · · · · · · · · · · |
| Ql( p, x1, ... , xk ) = 0, |
|
| (14) |
эквивалентную условию (11) относительно p.
Лемма 2. Если
| l | |
| Q( p, x1, ... , xk ) = | ∑ | Qi2( p, x1, ... , xk ), |
| i=1 | |
то система (14) эквивалентна уравнению (12).
Именно поиском системы экспоненциально диофантовых уравнений, эквивалентной условию (11), мы и будем заниматься.
Что такое простое число?
«Странный вопрос, — удивится читатель. — Каждый знает, что простое число — это число, большее единицы, которое делится только на единицу и на себя». Конечно, это так, но с таким определением работать нелегко — ведь оно предполагает, что проверка простоты числа состоит в переборе бесконечного числа потенциальных делителей — всех натуральных чисел,
кроме 1 и самого числа. Лучше сказать так:
число p является простым, если p>1 и p не делится ни на какое число, меньшее p и отличное от 1. Для наших же целей больше подходит следующее определение:
число p является простым, если p>1, и для любого числа q, меньшего p, Н.О.Д.(q, p) = 1. 8
В этом определении нет ограничения q ≠ 1 и, что более важно, оно позволяет переменное число условий Н.О.Д.(1, p) = 1, Н.О.Д.(2, p) = 1, ..., Н.О.Д.(p–1, p) = 1 свести в одно условие:
Н.О.Д.((p–1)!, p) = 1.
Сделанное замечание позволяет нам написать первую систему условий, эквивалентную условию (11) относительно параметра p:
|
|
p = r + 1,
s = r!,
Н.О.Д.(s, p) = 1. |
|
| (15) |
| (16) |
| (17) |
Первое из этих условий имеет искомый вид экспоненциально диофантова (более того, диофантова) уравнения, а третье легко приводится к такому же виду за счёт введения двух новых неизвестных:
Лемма 3.
Условие (17)
эквивалентно относительно параметров p,
s условию 9
Так как уравнение (18) экспоненциально диофантово, то нам осталось лишь найти систему экспоненциально диофантовых уравнений, эквивалентную относительно параметров r и sусловию (16).
Как вычислить факториал?
В условие (16) входит
r!; этот-то факториал и «мешает» нам. Вспомним, что факториал фигурирует в выражении для биномиальных коэффициентов
10:
при t ≥ r
|
| t(t – 1) ... (t – r + 1)
r!
| , |
то есть
| r! = | t(t – 1) ... (t – r + 1)
(tr)
| . |
Многочлен, стоящий в числителе, имеет довольно сложную структуру. Попытаемся заменить его более простым — а именно, многочленом tr. При t ≥ r имеем:
| tr
(tr)
| = | tr
t(t – 1) ... (t – r + 1)
| · r! = |
| = | ( | 1 + | 1
t – 1
| )( | 1 + | 2
t – 2
| ) | · ... · | ( | 1 + | r – 1
t – r + 1
| ) | · r! ≥ r!. |
| (19) |
Легко видеть, что
однако эта запись факториала нам ничего не даст, поскольку t, будучи параметром в искомой системе уравнений, сможет принимать любые, сколь угодно большие, но конечные значения. Но мы и не будем переходить к пределу, а воспользуемся целочисленностью r! — из (19) и (20) следует, что при достаточно больших t
Лемма 4. Формула (21) верна как только t≥2rr+2.
Лемма 4 позволяет преобразовать условие (16) в эквивалентную ему относительно параметров r и s систему (проверьте эквивалентность!)
|
|
| t = 2rr+2, |
| c = (tr), |
| tr = s · c + (x3 – 1), |
| (x3 – 1) + x4 = c. |
|
|
|
Здесь условия (22), (24) и (25) имеют требуемый вид, и нам остаётся лишь найти систему экспоненциально диофантовых уравнений, эквивалентных условию (23) относительно параметровr, t и c.
Итак, нам осталось «избавиться» от биномиального коэффициента.
Биномиальные коэффициенты — это коэффициенты бинома!
Только что мы использовали выражение биномиальных коэффициентов через факториал; но биномиальные коэффициенты имеют много и других определений. Воспользуемся теперь тем, что
| t | |
| (u + 1)t = | ∑ | (ti) | ui. |
| i=0 | |
| (26) |
Эта формула является определением биномиальных коэффициентов, если рассматривать её как тождество относительно u. Но нам нужно, чтобы u было неизвестной, принимающей в каждом конкретном решении искомой системы лишь одно значение.
Заметим, что
| t | |
| (ti) | ≤ | ∑ | (ti) | = (1 + 1)t = 2t, |
| i=0 | |
| (27) |
и, таким образом, если
то (t0), (t1), ..., (tt) — это цифры в записи числа (u+1)t в позиционной системе счисления с основанием u. Следовательно, биномиальные коэффициенты однозначно определяются тем условием, что равенство (26) и неравенства (27) и (28) одновременно выполнены хотя бы при одном значении u.
Лемма 5. Условие (23) эквивалентно относительно параметров r, t, c системе условий
|
|
| u = 2t + 1, |
| x5 = u + 1, |
| x5t = x6ur+1 + cur + x7, |
| x7 + x8 = ur, |
| c + x9 = u. |
|
| (29)
(30)
(31)
(32)
(33) |
Здесь все условия уже имеют необходимый нам вид.
Итак, мы показали, что условие (11) эквивалентно относительно параметра p системе, состоящей из экспоненциально диофантовых уравнений (15), (18), (22), (24), (25), (29)–(33). Чтобы получить требуемый экспоненциальный многочлен, осталось переименовать переменные r, s, t, c и u в x10, x11, x12, x13, x14, объединить по лемме 2 все уравнения в одно и преобразовать по лемме 1это уравнение к искомому виду (10).
Дальнейшие шаги
Формула (10) не содержит явно номера задаваемого ею простого числа. Описанный выше способ построения экспоненциального многочлена R не даёт прямого пути для включения номера простого числа в формулу (10). Используя существенно более сложную технику, Мартин Дейвис, Хилэри Патнам и Джулия Робинсон в 1961 году доказали одну очень сильную теорему, которая имеет такое следствие.
Существует экспоненциальный многочлен P(n, x0, ..., xk ) такой, что при каждом фиксированном значении параметра n и произвольных значениях остальных переменных, многочлен Pпринимает ровно одно положительное значение, и этим значением является n-е простое число.
В 1970 году автору этой статьи удалось, используя другие результаты Джулии Робинсон, построить такое диофантово уравнение:
| M(a, b, c, z1, ..., zm) = 0, | (34) |
которое разрешимо тогда и только тогда, когда параметры a, b и c связаны соотношением a = bc. Этот результат позволяет опустить в формулировке предыдущей теоремы слово «экспоненциальный», то есть позволяет построить многочлен, задающий простые числа. Об этом, однако, мы поговорим в другой раз. Те же читатели, кого заинтересовала подобная тематика и кого не страшат трудности, могут попробовать самостоятельно разобраться в статье автора «Диофантовы множества», опубликованной в журнале «Успехи математических наук», т. XXVII, № 5, 1972 год.
Темы для размышлений
| 1. |
Докажите, что в арифметических прогрессиях 3, 7, 11, ... и 5, 11, 17, ... бесконечно много простых чисел.
|
| 2. |
Каково множество тех многочленов, значения которых лежат вдоль диагонали, если спираль (см. рис. 1)
• начата с 1?
• начата с некоторого числа u?
• начата с некоторого числа u, и по спирали стоят члены арифметической прогрессии u, u + v, u + 2v, ...?
|
| 3. |
Теорема Вильсона утверждает, что если p — простое число, то (p–1)! + 1 делится на p. Как можно использовать этот результат, чтобы уменьшить число неизвестных в экспоненциальноммногочлене R, задающем простые числа?
|
| 4. |
Постройте экспоненциальный многочлен S(x0, ..., xk ), который задаёт множество полусумм простых чисел-близнецов, т.е. такой многочлен, что если S(x0, ..., xk ) > 0, то оба числаS(x0, ..., xk ) – 1 и S(x0, ..., xk ) + 1 являются простыми, и наоборот, если s – 1 и s + 1 — простые числа, то S(x0, ..., xk ) = s при некоторых x0, ..., xk .
|
| 5. |
Постройте экспоненциальный многочлен T(q, x0, ..., xm ), такой, что
• если q — простое число, то существуют числа x0, ..., xm такие, что T(q, x0, ..., xm ) > 0;
• если q — простое число и T(q, x0, ..., xm ) > 0, то T(q, x0, ..., xm ) — простое число, следующее за q;
• если q не является простым числом, то всегда T(q, x0, ..., xm ) ≤ 0.
Этот экспоненциальный многочлен даёт «формулу для следующего простого числа».
|
Примечания
| 1. |
Здесь и далее [α] обозначает целую часть числа α, то есть наибольшее целое число, не превосходящее α. назад к тексту
|
| 2. |
Прочитать об этом доказательстве можно в статье М. И. Башмакова, «Квант», 1971, № 5, или в заметке С. Б. Стечкина «Простое доказательство теоремы Чебышёва о простых числах» (УМН, 1968, № 5, с. 221–222, DjVu, 17 Кб).— E.G.A.. назад к тексту
|
| 3. |
Об истории и современном состоянии исследований по совершенным числам и простым числам Мерсенна вы можете прочитать в статье И. Я. Депмана, «Квант», 1971, № 8, или в обзорной статье Вальтера Боро «Дружественные числа» из книги «Живые числа» (М., «Мир», 1985, DjVu, 1875 Кб). См. также с. 132–134 в книге Р. Грэхема, Д. Кнута и О. Паташника «Конкретная математика» (М., «Мир», 1998) и цитируемую там литературу. — E.G.A.. назад к тексту
|
| 4. |
Подробнее об этом открытии тогда ещё совсем молодого Гаусса рассказано в статье С. Г. Гиндикина, «Квант», 1972, № 1, или в книге «Рассказы о физиках и математиках» (М., МЦНМО, 2001, PDF, 7275 Кб) того же автора, в главе, посвящённой Гауссу. — E.G.A.. назад к тексту
|
| 5. |
Как было сделано это наблюдение, красочно рассказывает М. Гарднер в «Математических досугах» (М., «Мир», 1972). Вот этот кусочек (с. 413–417):
В зависимости от расположения целых чисел простые числа могут образовывать тот или иной узор. Однажды математику Станиславу М. Уламу пришлось присутствовать на одном очень длинном и очень скучном, по его словам, докладе. Чтобы как-то развлечься, он начертил на листке бумаги вертикальные и горизонтальные линии и хотел было заняться составлением шахматных этюдов, но потом передумал и начал нумеровать пересечения, поставив в центре 1 и двигаясь по спирали против часовой стрелки. Без всякой задней мысли он обводил все простые числа кружками. Вскоре, к его удивлению, кружки с поразительным упорством стали выстраиваться вдоль прямых. На рис. 203 показано, как выглядела спираль со ста первыми числами (от 1 до 100). [Это усечённая на два оборота версия вышеприведённого рисунка 1, поэтому я его не привожу. — E.G.A.] Для удобства числа вписаны в клетки, а не стоят на пересечении линий.
Вблизи центра выстраивания простых чисел вдоль прямых ещё можно было ожидать, поскольку плотность простых чисел вначале велика и все они, кроме числа 2, нечётны. Если клетки шахматной доски перенумеровать по спирали, то все нечётные числа попадут на клетки одного и того же цвета. Взяв 17 пешек (соответствующих 17 простым числам, не превосходящим числа 64) и расставив их наугад на клетки одного цвета, вы обнаружите, что пешки выстроились вдоль диагональных прямых. Однако не было оснований ожидать, что и в области больших чисел, где плотность простых чисел значительно меньше, те также будут выстраиваться вдоль прямых. Улама заинтересовало, как же будет выглядеть его спираль, если её продолжить до нескольких тысяч простых чисел.
В вычислительном отделе Лос-Аламосской лаборатории, где работал Улам, имелась магнитная лента, на которой было записано 90 млн. простых чисел. Улам вместе с Майроном Л. Стейном и Марком Б. Уэллсом составили программу для вычислительной машины MANIAC, позволившую нанести на спираль последовательные целые числа от 1 до 65 000. Получившийся при этом узор (иногда его называют «скатертью Улама») изображён на рис. 204. [А это уже расширенная версия вышеприведённого рисунка 2, поэтому я его привожу. — E.G.A.] Обратите внимание на то, что даже у края картины простые числа продолжают послушно укладываться на прямые.
Рис. 204. Фотографии нарисованного компьютером узора («скатерти Улама»), на которых видно, чтопростые числа выстраиваются вдоль прямых: |
|
|
Прежде всего бросаются в глаза скопления простых чисел на диагоналях, но вполне ощутима и другая тенденция простых чисел — выстраиваться вдоль вертикальных и горизонтальных линий, на которых все клетки, свободные от простых чисел, заняты нечётными числами. Простые числа, попадающие на прямые, продолженные за отрезок, который содержит последовательные числа, лежащие на каком-то витке спирали, можно считать значениями некоторых квадратичных выражений, начинающихся с члена 4x². Например, последовательность простых чисел 5, 19, 41, 71, стоящих на одной из диагоналей на рис. 204, — это значения, принимаемые квадратичным трёхчленом4x² + 10x + 5 при x, равном 0, 1, 2 и 3. Из рис. 204 видно, что квадратичные выражения, принимающие простые значения, бывают «бедными» (дающими мало простых чисел) и «богатыми» и что на «богатых» прямых наблюдаются целые «россыпи» простых чисел.
Начав спираль не с 1, а с какого-нибудь другого числа, мы получим другие квадратичные выражения для простых чисел, выстраивающихся вдоль прямых. Рассмотрим спираль, начинающуюся с числа 17 (рис. 205, слева). Числа вдоль главной диагонали, идущей с «северо-востока» на «юго-запад», порождаются квадратичным трёхчленом 4x² + 2x + 17. Подставляя положительные значения x, мы получаем нижнюю половину диагонали, подставляя отрицательные значения — верхнюю. Если рассмотреть всю диагональ и переставить простые числа в порядке возрастания, то окажется (и это приятный сюрприз), что все числа описываются более простой формулой x² + x + 17. Это одна из многих «производящих» формул для простых чисел, открытых ещё в XVIII веке великим математиком Леонардом Эйлером. При x, принимающем значения от 0 до 15, она даёт только простые числа. Следовательно, продолжив диагональ до тех пор, пока она не заполнит квадрат 16×16, мы увидим, что вся диагональ заполнена простыми числами.
Самый знаменитый квадратичный трёхчлен Эйлера, производящий простые числа, x² + x + 41, получится, если начать спираль с числа 41 (рис. 205, справа). Этот трёхчлен позволяет получить 40 последовательных простых чисел, заполняющих всю диагональ квадрата 40×40! Давно известно, что из 2398 первых значений, принимаемых этим трёхчленом, ровно половина простые. Перебрав все значения знаменитого трёхчлена, не превышающие 10 000 000, Улам, Стейн и Уэллс обнаружили, что доля простых чисел среди них составляет 0,475... . Математикам очень бы хотелось открыть формулу, позволяющую получать при каждом целом x различные простые числа, но пока такой формулы обнаружить не удалось. Может быть, её и не существует.
| 33 | 32 | 31 | 30 | 29 |
| 34 | 21 | 20 | 19 | 28 |
| 35 | 22 | 17 | 18 | 27 |
| 36 | 23 | 24 | 25 | 26 |
| 37 | 38 | 39 | 40 | 41 |
| |
| 57 | 56 | 55 | 54 | 53 |
| 58 | 45 | 44 | 43 | 52 |
| 59 | 46 | 41 | 42 | 51 |
| 60 | 47 | 48 | 49 | 50 |
| 61 | 62 | 63 | 64 | 65 |
|
| Рис. 205. Диагонали, заполненные простыми числами, порождаемыми квадратичными трёхчленамиx² + x + 17 (слева) и x² + x + 41 (справа). |
Спираль Улама подняла много новых вопросов, относящихся к закономерностям и случайностям в распределении простых чисел. Существуют ли прямые, на которых лежит бесконечно много простых чисел? Какова максимальная плотность распределения простых чисел вдоль прямых? Существенно ли различаются плотности распределения простых чисел в квадрантах «скатерти» Улама, если считать, что она продолжается неограниченно? Спираль Улама — забава, но её следует принимать всерьёз.
|
