Теорема Фолкманса - Википедия - Folkmans theorem

Теорема Фолкмана это теорема в математике, и особенно в арифметическая комбинаторика и Теория Рамсея. Согласно этой теореме, когда натуральные числа находятся разделенный на конечное множество подмножеств, существуют сколь угодно большие наборы чисел, все суммы которых принадлежат одному и тому же подмножеству разбиения.^[1] Теорема была открыта и доказана независимо несколькими математиками,^[2]^[3] прежде, чем она была названа "теоремой Фолкмана", как памятник Джон Фолкман, к Грэм, Ротшильд, и Спенсер.^[1]

Формулировка теоремы

Позволять N - набор {1, 2, 3, ...} натуральных чисел, и предположим, что N разделен на k разные подмножества N₁, N₂, ... N_k, куда k любое положительное целое число. Тогда теорема Фолкмана утверждает, что для любого положительного целого числа м, существует множество S_м и индекс я_м такой, что S_м имеет м элементов и такие, что каждая сумма непустого подмножества S_м принадлежит N_{я_м}.^[1]

Связь с теоремой Радо и теоремой Шура

Теорема Шура в теории Рамсея утверждает, что для любого конечного разбиения натуральных чисел существуют три числа Икс, у, и Икс + у все принадлежат к одному набору разделов. То есть это частный случай м = 2 теоремы Фолкмана.

Теорема Радо в теории Рамсея касается аналогичной постановки задачи, в которой целые числа разбиваются на конечное число подмножеств; теорема характеризует целочисленные матрицы А с тем свойством, что система линейных уравнений А Икс = 0 можно гарантировать наличие решения, в котором каждая координата вектора решения Икс принадлежит к тому же подмножеству раздела. Система уравнений называется обычный всякий раз, когда он удовлетворяет условиям теоремы Радо; Теорема Фолкмана эквивалентна регулярности системы уравнений

{ Displaystyle х_ {T} = сумма _ {я in T} х _ { {я }},}

куда Т пробегает по каждому непустому подмножеству множества {1, 2, ..., м}.^[1]

Умножение против сложения

В теореме Фолкмана можно заменить сложение умножением: если натуральные числа конечно разделены, существуют сколь угодно большие множества S такие, что все произведения непустых подмножеств S принадлежат к одному набору разделов. Действительно, если ограничить S состоять только из силы двух, то этот результат немедленно следует из аддитивной версии теоремы Фолкмана. Однако остается открытым вопрос о том, существуют ли сколь угодно большие множества такие, что все суммы и все произведения непустых подмножеств принадлежат одному множеству разбиений. Первый пример нелинейности в теории Рамсея, который не состоит из одночленов, был независимо дан Фюрстенбергом и Саркози в 1977 году с семьей {Икс, Икс + у²}, результат, который был дополнительно улучшен Бергельсоном в 1987 году. В 2016 году Дж. Морейра доказал, что существует множество вида {Икс, Икс + у, ху} содержится в элементе раздела^[4] Однако даже не известно, обязательно ли должно существовать множество вида {Икс, у, Икс + у, ху}, для которого все четыре элемента принадлежат одному набору разбиения.^[1]

Каноническая теорема Фолькмана

Позволять ${ displaystyle FS ( {x_ {i} } _ {i = 1} ^ {n})}$ обозначим множество всех конечных сумм элементов ${ Displaystyle {х_ {я} } _ {я = 1} ^ {п}}$ . Позволять ${ displaystyle C}$ - раскраска (возможно бесконечная) натуральных чисел, и пусть ${ displaystyle n}$ - произвольное натуральное число. Существует ${ Displaystyle {х_ {я} } _ {я = 1} ^ {п}}$ такое, что выполняется хотя бы одно из следующих 3 условий.

1) ${ displaystyle FS ( {x_ {i} } _ {i = 1} ^ {n})}$ - монохроматический набор.

2) ${ displaystyle FS ( {x_ {i} } _ {i = 1} ^ {n})}$ это набор радуги.

3) Для любого ${ displaystyle B substeq [1, n]}$ , цвет ${ Displaystyle сумма _ {я in B} x_ {я}}$ определяется исключительно ${ Displaystyle мин (В)}$ .

Предыдущие результаты

Варианты теоремы Фолкмана были доказаны Ричард Радо и Дж. Х. Сандерсом.^[2]^[3]^[1] Теорема Фолкмана названа в память о Джон Фолкман к Рональд Грэм, Брюс Ли Ротшильд, и Джоэл Спенсер в своей книге о Теория Рамсея.^[1]