Те́ренс Чи Шен Тао (кит. ) (род. 17 июля 1975, Аделаида) — австралийский и американский математик,
работающий в основном в области гармонического анализа, дифференциальных уравнений в частных производных, комбинаторики, теории чисел и теории представлений.
Наиболее известной его работой является доказательство (совместно с британским математиком Беном Грином) существования неограниченно длинных арифметических прогрессий
простых чисел (теорема Грина — Тао). Сейчас Тао работает профессором математики в Калифорнийском университете в Лос-Анджелесе.
Подробнее можно почитать в Википедии.
Тао ведет блог,
где рассматривает самые разные разделы современной математики, занимаясь активной популяризаторской работой.
В этой статье рассматриваются некоторые из статей его блога, имеющие отношение к теории чисел.
СтатьяOpen question: The parity problem in sieve theory
является введением в sieve theory - раздел теории чисел, рссматривающий различные наборы целых чисел, в том числе простых.
Теория включает в себя:
1. общеизвестное сито Эратосфена для получения простых чисел в заданном диапазоне
2. сито Лежандра для оценки верхней или нижней границы числа простых чисел в заданном диапазоне:
если диапазон обозначим через X, μ - функция мебиуча, простые числа - p1, p2, p3, тогда
3. сито Бруна для вычисления размера наборов чисел, отвечающих определенным условиям.
Бруно в начале 20 века доказал знаменитую теорему о сходимости ряда величин, обратных т.н. простым числам-близнецам.
4. сито Сельберга
и другие.
Проблема четности - parity problem - которая рассматривается в этой статье, звучит так: на данный момент в общем случае теория неспособна
отличить числа, имеющие нечетное число делителей, от чисел, имеющих четное число делителей.
Как было известно еще Гауссу, число простых чисел в диапазоне 1...N равно
N / log N
Верхняя граница для числа простых чисел в диапазоне N ... 2N равна
N / log log N
Число пар близнецов в диапазоне N ... 2N равно
N (log log N / log N)2
СтатьяThe Lucas-Lehmer test for Mersenne primes
популярно обьясняет, какие алгоритмы лежат в основ теста простоты для чисел Мерсенна.
На википедии также есть хорошая статья.
Числа Мерсенна - это простые числа получаемые по формуле
2p - 1
где p - простое число.
Благодаря этому тесту самыми большими известными простыми числами почти всегда были простые числа Мерсенна,
причём даже до появления компьютеров; именно он лежит в основе проекта распределённых вычислений GIMPS, занимающегося поиском новых простых чисел Мерсенна.
Тест основан на следующем критерии простоты:
число Мерсенна является простым тогда и только тогда, когда оно делит без остатка p-1-й член следующей последовательности:
4, 14, 194, 37634б ...
где каждый последующий член получается из предыдущего по формуле:
Sk = S2k-1
Возможными значениями S1 являются: 4, 10, 52, 724, 970, 10084, ...
Следующий код проверяет на простоту числа Мерсенна:
Код
package main
import (
"math/big"
"time"
)
var primes = []uint{3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127}
var mersennes = []uint{521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689,
9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091,
756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917,
20996011, 24036583}
var t1 time.Time
func llTest(ps []uint) {
var s, m big.Int
one := big.NewInt(1)
two := big.NewInt(2)
for _, p := range ps {
m.Sub(m.Lsh(one, p), one)
s.SetInt64(4)
for i := uint(2); i < p; i++ {
s.Mod(s.Sub(s.Mul(&s, &s), two), &m)
}
if s.BitLen() == 0 {
t2 := time.Since(t1)
println("n=", p, "time=", t2.Seconds())
}
}
}
func main() {
t1 = time.Now()
llTest(primes)
llTest(mersennes)
}
Статья The AKS primality test
рассказывает об алгоритме, проверяющем числа на простоту. Подробнее можно почитать в википедии.
Это универсальный, полиномиальный, детерминированный и безусловный тест простоты чисел, основанный на обобщении малой теоремы Ферма на многочлены.
В основе этого алгоритма лежит малая теорема Ферма, которая гласит, что если p - простое число,
a - любое число, то
Сама по себе малая теорема Ферма не годится для теста чисел на простоту,
поскольку она не различает простые числа от псевдо-простых, т.н. чисел Кармайкла.
Существует полиномиальная версия теоремы Ферма:
Для уменьшения время вычислений применяется другая версия последней формулы
где r достаточно мало и лежит в пределах log(n).
Основная теорема AKS-теста:
если выполняется последняя формула, и a взаимно простое с n, тогда n - либо простое число, либо степень простого числа.
На практике тест AKS может быть использован для тестирования небольших чисел, с увеличением разрядности проверяемого
числа использование памяти резко возрастает и тест становится практически непригоден.
Статья On the number of solutions to 4/p = 1/n_1 + 1/n_2 + 1/n_3
рассматривает решения Диофантового уравнения
для натуральных n, x,y,z.
pdf-версию статьи можно посмотреть тут
Если через f(n) обозначить число решений, то получим ряд:
f(1)=0, f(2)=3, f(3)=12, f(4)=10, f(5)=12, f(6)=39, f(7)=36, f(8)=46, ...
Гипотеза Erdős-Straus утверждает, что f(n) > 0 для любого n.
Она проверена для всех n < 1014
В этой статье Тао выводит верхнюю и нижнюю границу f(n).
Были различные варианты решения этого вопроса, в частности, верхняя граница оценивалась как
N * exp(-c*log2/3N)
где c>0 и N достаточно велико.
Рассматриваются два варианта:
1. n делится на x, в то же время y и z взаимно просты с n - f1
1. n делится на y и z, , в то же время x взаимно простое с n - f2
Вместо n берется простое p. При этом
f(p) = 3*f1(p) + 3*f2(p)
Для нижней границы выводится теорема:
Для верхней границы:
Чжан Итан (Zhāng Yìtáng; род. 1955) — американский математик китайского происхождения, работающий в области теории чисел -
в 2013 году отправил в журнал Annals of Mathematics статью, в которой доказывалось, что существует бесконечно много пар последовательных простых чисел
с разностью не более 70 миллионов.
В блоге Теренса Тао в том же году появилась статья
The prime tuples conjecture, sieve theory, and the work of Goldston-Pintz-Yildirim, Motohashi-Pintz, and Zhang
Теренс Тао вскоре доказал, что граница может быть уменьшена до 4 982 086.
Впоследствии он предложил проекту
Polymath
совместными усилиями оптимизировать границу.
В ноябре 2013 года 27-летний британский математик Джэймс Мэйнард применил алгоритм, разработанный в 2005 году математиками Дэниелем Голдстоном,
Яношом Пинтцем и Семом Йилдиримом, под названием GPY , и доказал, что существует бесконечно много соседних простых чисел,
лежащих на расстоянии не более 600 друг от друга.
В день выхода препринта работы Джеймса Мэйнарда Теренс Тао опубликовал в личном блоге пост с предложением запустить новый проект, polymath8b,
Polymath8: Writing the paper
и уже через неделю оценка была снижена до 576, а 6 января 2014 — до 270.
Наилучший научно доказанный результат был достигнут в апреле 2014 года Пэйсом Нильсеном из университета Брайгама Янга в Юте — 246
Работу проекта Polymath Теренс Тао подробно коментировал на страницах своего блога:
Polymath8b, III: Numerical optimisation of the variational problem, and a search for new sieves Polymath8b: Bounded intervals with many primes, after Maynard Polymath8b, VIII: Time to start writing up the results?