Теорема Ґріна — Тао

Теорема Ґріна — Тао — теоретико-числове твердження, яке 2004 року довели Бен Ґрін і Теренс Тао, згідно з яким послідовність простих чисел містить арифметичні прогресії довільної довжини. Іншими словами, існують арифметичні прогресії простих чисел, що складаються з k членів, де k може бути будь-яким натуральним числом. Доведення полягає в розширенні теореми Семереді.

Формулювання

Хоча теорема відома лише доведенням самого факту наявності як завгодно довгих прогресій у множині простих чисел, проте є значні посилення цього твердження: по-перше, твердження залишається істинним для довільної множини простих чисел додатної щільності (відносно множини всіх простих чисел); по-друге, є окремі верхні оцінки того, наскільки великими можуть бути елементи найменшої прогресії у множині.

Далі у формулюваннях $\mathbb {P}$ означає множину простих чисел. Запис $\log _{[k]}x$ означає $\log \log \dots \log x$, де логарифм береться $k$ разів.

Теорема Ґріна — Тао Нехай $A$ — множина простих чисел, і її щільність відносно простих $\delta _{\mathbb {P} }(A)=\lim \sup _{N\to \infty }{\frac {|A\cap \{1,\dots ,N\}|}{|\mathbb {P} \cap \{1,\dots ,N\}|}}$ строго додатна. Тоді для довільного $k\geqslant 2$ множина $A$ містить арифметичну прогресію довжини $k$.

У своїй окремій ранішій праці Ґрін довів результат, що стосується функції розподілу множини $A$, але тільки для окремого випадку тричленної прогресії.

Існує стала $c$ така, що якщо для множини простих чисел $A\subset \{1,\dots ,N\}$ виконано $|A|>c{\frac {N{\sqrt {\log _{[5]}N}}}{\log {N}{\sqrt {\log _{[4]}N}}}}$, то вона містить тричленну арифметичну прогресію.

Оскільки необхідна функція асимптотично менша від кількості простих чисел на відрізку $[1,n]$, то теорема залишається істинною для нескінченних множин додатної щільності, коли $|A\cap \{1,\dots ,N\}|>\delta {\frac {N}{\log N}}$, $\delta >0$. Таким чином, можна переформулювати останню теорему для фіксованої щільності.

Існує стала $c$ така, що для довільної множини простих чисел $A\subset \{1,\dots ,N\}$ та її щільності $\delta ={\frac {|A\cap \{1,\dots ,N\}|}{|\mathbb {P} \cap \{1,\dots ,N\}|}}$ виконуватиметься наслідок: якщо $N\geqslant e^{e^{e^{\left(\left(c/\delta ^{2}\right)^{c/\delta ^{2}}\right)}}}$, то $A$ містить тричленну арифметичну прогресію.

приклади

• 18 січня 2007 року Ярослав Вроблевський знайшов перший випадок арифметичної прогресії з 24 простих чисел:

  468 395 662 504 823 + 205 619 · 223 092 870 · n, від n = 0 до 23.

Тут стала 223 092 870 — це добуток простих чисел, не більших 23 (див. прайморіал).

• 17 травня 2008 року Вроблевський та Раанан Чермоні знайшли послідовність із 25 простих чисел:

  6 171 054 912 832 631 + 366 384 · 223 092 870 · n, від n = 0 до 24.

• 12 квітня 2010 року Бенуа Перішон, користуючись програмою Вроблевського та Джефа Рейнолдса в проекті розподілених обчислень PrimeGrid, знайшов арифметичну прогресію з 26 простих чисел:

  43 142 746 595 714 191 + 23 681 770 · 223 092 870 · n, від n = 0 до 25 (послідовність A204189 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).

Варіації та узагальнення

2006 року Тао і Тамар Ціґлер узагальнили результат до поліноміальних прогресій. Точніше, для будь-яких даних многочленів із цілими коефіцієнтами P₁, …, P_k однієї змінної m із нульовим сталим членом є нескінченно багато цілих x, m таких, що x + P₁(m), …, x + P_k(m) — прості числа. Особливий випадок, коли поліноми — це m, 2m, …, km, тягне за собою попередній результат (існують арифметичні прогресії простих чисел довжини k).

Див. також

• Гіпотеза Ердеша про арифметичні прогресії
• Теорема Діріхле про прості числа в арифметичній прогресії
• Арифметична комбінаторика
• Теорема Семереді

Посилання

• MathWorld news article on proof(англ.)
• Primes in Arithmetic Progression Records(англ.)