Теорема Эрдеша–Тетали

В теории аддитивных чисел , области математики , теорема Эрдёша–Тетали является теоремой существования, касающейся экономичных аддитивных базисов любого порядка. Более конкретно, она утверждает, что для каждого фиксированного целого числа существует подмножество натуральных чисел, удовлетворяющее${\displaystyle h\geq 2}$${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$

$${\displaystyle r_{{\mathcal {B}},h}(n)\asymp \log n,}$$где обозначает количество способов, которыми натуральное число n может быть выражено как сумма h элементов B. ^[1]${\displaystyle r_{{\mathcal {B}},h}(n)}$

Теорема названа в честь Пола Эрдёша и Прасада В. Тетали , которые опубликовали ее в 1990 году.

Первоначальная мотивация этого результата приписывается проблеме, поставленной С. Сидоном в 1932 году по экономичным базисам . Аддитивный базис называется экономичным ^[2] (или иногда тонким ^[3] ), когда он является аддитивным базисом порядка h и${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$

${\displaystyle r_{{\mathcal {B}},h}(n)\ll _{\varepsilon }n^{\varepsilon }}$

для каждого . Другими словами, это аддитивные базы, которые используют как можно меньше чисел для представления заданного n , и при этом представляют каждое натуральное число. Связанные концепции включают -последовательности ^[4] и гипотезу Эрдёша–Турана об аддитивных базах .${\displaystyle \varepsilon >0}$${\displaystyle B_{h}[г]}$

Вопрос Сидона был в том, существует ли экономический базис порядка 2. Положительный ответ был дан П. Эрдёшем в 1956 году, ^[5] разрешив случай h = 2 теоремы. Хотя общая версия считалась верной, до статьи Эрдёша и Тетали в литературе не появилось никакого полного доказательства. ^[6]

Доказательство является примером вероятностного метода и может быть разделено на три основных шага. Во-первых, начинается с определения случайной последовательности${\displaystyle \omega \subseteq \mathbb {N} }$

${\displaystyle \Pr(n\in \omega )=C\cdot n^{{\frac {1}{h}}-1}(\log n)^{\frac {1}{h}},}$

где — некоторая большая действительная константа, — фиксированное целое число, а n достаточно велико, чтобы приведенная выше формула была хорошо определена. Подробное обсуждение вероятностного пространства, связанного с этим типом построения, можно найти в Halberstam & Roth (1983). ^[7] Во-вторых, затем показывают, что ожидаемое значение случайной величины имеет порядок log . То есть,${\displaystyle С>0}$${\displaystyle h\geq 2}$ ${\displaystyle r_{\omega ,h}(n)}$

${\displaystyle \mathbb {E} (r_ {\omega,h}(n))\asymp \log n.}$

Наконец, один показывает, что почти наверняка концентрируется вокруг своего среднего значения. Более явно:${\displaystyle r_{\omega ,h}(n)}$

${\displaystyle \Pr {\big (}\exists c_{1},c_{2}>0~|~{\text{для всех больших }}n\in \mathbb {N} ,~c_{1}\mathbb {E} (r_{\omega ,h}(n))\leq r_{\omega ,h}(n)\leq c_{2}\mathbb {E} (r_{\omega ,h}(n)){\big )}=1}$

Это критический шаг доказательства. Первоначально он решался с помощью неравенства Янсона , типа неравенства концентрации для многомерных полиномов. Тао и Ву (2006) ^[8] представляют это доказательство с более сложным двусторонним неравенством концентрации В. Ву (2000), ^[9] , тем самым относительно упрощая этот шаг. Алон и Спенсер (2016) классифицируют это доказательство как пример парадигмы Пуассона. ^[10]

Нерешенная задача по математике :

Пусть будет целым числом. Если — бесконечное множество, такое, что для каждого n , означает ли это, что:${\textstyle h\geq 2}$${\textstyle {\mathcal {B}}\subseteq \mathbb {N} }$${\textstyle r_{{\mathcal {B}},h}(n)>0}$

${\displaystyle \limsup _{n\to \infty }{\frac {r_{{\mathcal {B}},h}(n)}{\log n}}>0}$?

(еще нерешенные проблемы по математике)

Первоначальная гипотеза Эрдёша–Турана об аддитивных базисах в наиболее общей форме гласит, что если — аддитивный базис порядка h , то${\textstyle {\mathcal {B}}\subseteq \mathbb {N} }$

${\displaystyle \limsup _{n\to \infty }r_{{\mathcal {B}},h}(n)=\infty ;}$

то есть, не может быть ограничен. В своей статье 1956 года П. Эрдёш ^[5] задался вопросом, может ли быть так, что ${\textstyle r_{{\mathcal {B}},h}(n)}$

${\displaystyle \limsup _{n\to \infty }{\frac {r_{{\mathcal {B}},2}(n)}{\log n}}>0}$

всякий раз, когда является аддитивным базисом порядка 2. Другими словами, это означает, что не только неограничен, но и что никакая функция, меньшая, чем log, не может доминировать . Вопрос естественным образом распространяется на , что делает его более сильной формой гипотезы Эрдёша–Турана об аддитивных базисах. В некотором смысле, предполагается, что не существует аддитивных базисов, существенно более экономичных, чем те, существование которых гарантировано теоремой Эрдёша–Тетали.${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$${\textstyle r_{{\mathcal {B}},2}(n)}$${\textstyle r_{{\mathcal {B}},2}(n)}$${\displaystyle h\geq 3}$

Все известные доказательства теоремы Эрдёша–Тетали являются, по природе бесконечного вероятностного пространства, неконструктивными доказательствами . Однако Колоунцакис (1995) ^[11] показал существование рекурсивного множества, удовлетворяющего такому, что для вычисления требуется полиномиальное время от n . Вопрос для остается открытым.${\displaystyle {\mathcal {R}}\subseteq \mathbb {N} }$${\displaystyle r_{{\mathcal {R}},2}(n)\asymp \log n}$${\displaystyle {\mathcal {R}}\cap \{0,1,\ldots ,n\}}$${\displaystyle h\geq 3}$

При наличии произвольного аддитивного базиса можно спросить, существует ли такой, что является экономичным базисом. В. Ву (2000) ^[12] показал, что это имеет место для базисов Варинга , где для каждого фиксированного k существуют экономичные подбазисы порядка для каждого , для некоторой большой вычислимой константы .${\displaystyle {\mathcal {A}}\subseteq \mathbb {N} }$${\displaystyle {\mathcal {B}}\subseteq {\mathcal {A}}}$${\displaystyle {\mathcal {B}}}$ ${\displaystyle \mathbb {N} ^{\wedge }k:=\{0^{k},1^{k},2^{k},\ldots \}}$${\displaystyle \mathbb {N} ^{\wedge }k}$${\displaystyle s}$${\displaystyle s\geq s_{k}}$${\displaystyle s_{k}}$

Другой возможный вопрос заключается в том, применимы ли аналогичные результаты для функций, отличных от log. То есть, фиксируя целое число , для каких функций f мы можем найти подмножество натуральных чисел, удовлетворяющее ? Из результата C. Táfula (2019) ^[13] следует , что если f является локально интегрируемой , положительной действительной функцией, удовлетворяющей${\displaystyle h\geq 2}$${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$${\displaystyle r_{{\mathcal {B}},h}(n)\asymp f(n)}$

• ${\displaystyle {\frac {1}{x}}\int _{1}^{x}f(t)\,\mathrm {d} t\asymp f(x)}$, и
• ${\displaystyle \log x\ll f(x)\ll x^{\frac {1}{h-1}}(\log x)^{-\varepsilon }}$для некоторых ,${\displaystyle \varepsilon >0}$

тогда существует аддитивный базис порядка h, который удовлетворяет . Минимальный случай f ( x ) = log x восстанавливает теорему Эрдёша–Тетали.${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$${\displaystyle r_{{\mathcal {B}},h}(n)\asymp f(n)}$

• Теорема Эрдёша–Фукса : Для любого ненулевого числа не существует множества , удовлетворяющего .${\displaystyle C\in \mathbb {R} }$${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$${\displaystyle \textstyle {\sum _{n\leq x}r_{{\mathcal {B}},2}(n)=Cx+o\left(x^{1/4}\log(x)^{-1/2}\right)}}$
• Гипотеза Эрдёша–Турана об аддитивных базисах : Если — аддитивный базис порядка 2, то .${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$${\displaystyle r_{{\mathcal {B}},2}(n)\neq O(1)}$
• Проблема Варинга , проблема представления чисел в виде сумм k -степеней, при фиксированном .${\displaystyle k\geq 2}$

• Erdős, P. ; Tetali, P. (1990). «Представление целых чисел в виде суммы k членов». Случайные структуры и алгоритмы. 1 (3): 245–261. doi :10.1002/rsa.3240010302.
• Халберстам, Х.; Рот , К.Ф. (1983). Последовательности . Springer New York. ISBN 978-1-4613-8227-0 . OCLC  840282845. 
• Алон, Н .; Спенсер, Дж. (2016). Вероятностный метод (4-е изд.). Wiley. ISBN 978-1-1190-6195-3 . OCLC  910535517. 
• Тао, Т .; Ву, В. (2006). Аддитивная комбинаторика . Издательство Кембриджского университета. ISBN 0521853869. OCLC  71262684 .