andreybrylb Jul 2 at 19:11

Сложение с подвохом: что мы до сих пор не понимаем в 1 + 1? Гипотеза Эрдеша о множествах без суммы

Easy

8 min

6.2K

Mathematics*Popular scienceReading room

Translation

+18

Comments 15

Tarson Jul 2 at 21:01

Медаль Филдса ему дадут?

Mitya78 Jul 2 at 22:30

Только Эрдёш всё же Пал, а не Пол. Там явный долгий звук А в имени.

avshkol Jul 2 at 22:34

Первый раз слышу про бессумные множества. Уточнил у перплексити, можно ли их применить в моделировании. Ответ интересный:

Можно ли применять бессумные множества для моделирования социальных или экономических систем

Бессумные множества могут быть применены для моделирования социальных и экономических систем, особенно в тех случаях, когда важно учитывать ограничения на взаимодействия или объединения элементов системы, чтобы избежать нежелательных "перекрытий" или конфликтов.

В частности:

В социальных системах бессумные множества могут моделировать группы или сообщества, в которых взаимодействия (например, объединение ресурсов или идей) не приводят к появлению новых членов или состояний, уже присутствующих в группе. Это помогает анализировать устойчивость и структуру социальных сетей без избыточных пересечений.
В экономике бессумные множества могут использоваться для моделирования систем с ограничениями на совокупные ресурсы или сделки, где сумма двух экономических показателей не должна попадать в определённый нежелательный диапазон, что позволяет избегать конфликтов интересов или избыточной конкуренции.
Такие модели могут служить в управлении рисками и предотвращении кризисных ситуаций, когда важно контролировать, чтобы комбинации факторов не приводили к критическим состояниям.
В более общем смысле, бессумные множества помогают формализовать и анализировать системы с ограничениями на суммы элементов, что полезно при построении алгоритмов и стратегий в социальных и экономических контекстах.

Хотя прямых примеров применения именно бессумных множеств в социально-экономических моделях в литературе немного, их свойства хорошо сочетаются с задачами, связанными с устойчивостью, предотвращением конфликтов и управлением сложными системами, что подтверждается исследованиями в области сложных систем и эргатических моделей.

Jijiki Jul 2 at 23:30

спасибо очень интересно, поначалу даже растерялся, но сейчас чутка понял в чем суть) посмотрел что есть ) Задача_о_рюкзаке

Spaceoddity Jul 3 at 04:20

В самом начале сразу же спотыкаюсь на абсолютно размазанной формулировке:

В 1965 году математик Пол Эрдёш задал на первый взгляд скромный вопрос: насколько часто встречаются такие бессумные множества?

Насколько часто ГДЕ встречаются? Без какой-либо конкретики на этот счёт вопрос не имеет смысла ;)

Ну и сразу же:

И вот — прорыв. В феврале этого года, спустя почти 60 лет после того, как Эрдёш впервые сформулировал задачу, Бенджамин Бедерт её решил. Он доказал, что любое множество целых чисел — как положительных, так и отрицательных — обязательно содержит крупное подмножество, в котором никакая пара не складывается в третий элемент.

Ага, уже "целых" ;) Т.е. с вещественными ничего не понятно?))

И что это за "крупное подмножество"? [1, 1, 2] - достаточно крупное подмножество? ;)

misha_erementchouk Jul 3 at 08:57

Т.е. с вещественными ничего не понятно?

С вещественными (должно быть) тривиально: любое конечное множество вещественных чисел, случайно выбранных из некоторого интервала с однородным распределением, - бессумно. Более того, такое множество линейно-независимо над рациональными числами с вероятностью единица. Действительно, рассмотрим всевозможные линейные комбинации $p_1 x_1 + p_2 x_2 + \ldots$ , где $p_k \in \mathbb{Q}$ - рациональные коэффициенты и - элементы исходного множества. Поскольку $\mathbb{Q}$ счетно, множество возможных сумм тоже счетно и, следовательно, нулевой меры. Вероятность того, что оно содержит 0 равна нулю.

Таким образом, бессумные множества действительных чисел встречаются очень часто: "все" (т.е. за исключением меры нуль, что может приводить к забавным чудовинкам с точки зрения конструирования) множества бессумны.

Бессумные множества целых чисел несложно конструировать. Скажем, любое множество составленное из кубов или четвертых степеней и т.д. по теореме Ферма бессумно.

Поэтому вопрос: а можно ли конструировать сумные множества? Например, с квадратами уже трюк не проходит из-за пифагоровых троек. Результат, о котором рассказывает заметка, говорит, что как бы мы ни изгалялись, всегда будет бессумное подмножество с как минимумом $N/3 + \log \log N$ элементов. Какие-то варианты этого результата должны переноситься и на вещественные числа, а может даже и он сам в чистом виде.

Jijiki Jul 3 at 09:11

а если просто запустить монтекарло симуляцию по производству последовательности чисел

misha_erementchouk Jul 3 at 09:50

Понятия не имею, для меня вся эта проблематика бесконечно далека. По (очень натянутой) аналогии с другими областями, на случайных последовательностях вполне может достигаться как раз нижний предел размера бессумных подмножеств. Однако, если читать между строк то, что говорили интервьюируемые, вероятно есть ожидание, что настоящий нижний предел больше того, что было доказано. Из заметки статус нового результата, кроме того, что он значительно улучшает предыдущие оценки, про которые сразу (?) было понятно, что они очень пессимистичные, непонятен.

Spaceoddity Jul 3 at 09:34

Так. Непонятные моменты:

С вещественными (должно быть) тривиально: любое конечное множество вещественных чисел, случайно выбранных из некоторого интервала с однородным распределением, - бессумно.

Ну сразу ловите контрпример: {0.(3), 0.(6), 1.0} ;)

Поэтому вопрос: а можно ли конструировать сумные множества? Например, с квадратами уже трюк не проходит из-за пифагоровых троек.

Странно, мне вот почему-то кажется что именно пифагоровыми тройками такое и можно конструировать...

Или мы по разному понимаем трактовку? Надо чтобы вообще любая, случайно взятая, тройка чисел могла быть представлена в виде суммы и результата?

Как по мне, это вообще теорвер какой-то... Всё зависит от выборки...

Quintanar Jul 3 at 10:33

Этот контрпример по сути сведение к проблеме целых чисел. Ничего нового он не дает. Я так понимаю, смысл поста был в том, что вещественные числа "неинтересны", их вещественность не добавляет ничего ценного.

misha_erementchouk Jul 3 at 10:40

Никто же не говорит, что не существует действительных чисел, сумма которых равна третьему действительному числу. Но если взять открытый интервал ненулевой меры и на нем ввести однородное распределие, то вероятность выбора конечной линейно независимой выборки равна единице.

Это, в частности, означает, что множество действительных чисел, содержащее сумму, должно специально конструироваться, вроде того, как Вы сконструировали свой пример. Вот из-за того, что такое конструирование вводит некую структуру целых чисел, мне и кажется, что результат из заметки переносится один в один на множества действительных чисел. Но это надо у числовиков спрашивать.

В заметке, на мой взгляд, проблема недостаточно хорошо поставлена. Вопрос насколько часто встречаются бессумные множества совсем неинтересен. Они появляются налево-направо: множество нечетных чисел, множество кубов и т.д. Но если мы посмотрим на множество квадратов, то из-за пифагоровых троек такое множество может и не быть бессумным. Досада! Вопрос, а сколько нужно выкинуть элементов из такого суммосодержащего множества, чтобы оно стало бессумным? Результат из заметки говорит, что не больше 2/3 элементов (и даже меньше на двойной логарифм), как бы хитро мы ни конструировали наше множество. Из множества квадратов, вероятно, одной трети было бы достаточно, но надо думать, нельзя ли там хитрые конструкции реализовать.

Spaceoddity Jul 3 at 17:07

Из множества квадратов, вероятно, одной трети было бы достаточно, но надо думать, нельзя ли там хитрые конструкции реализовать.

Ну как квадраты между собой связаны - рядом нечётных чисел ;)

Ну и блин, это как бы очевидно - что таких чисел будет немного... Я вон, нейросети постоянно донимаю вопросами - "а не слишком ли много в природе (законах физики) всяких квадратов и кубов? умножение числа на самое себя - не самая вероятная операция для независимого рандома".

eyeDM Jul 3 at 09:04

насколько часто встречаются такие бессумные множества?

Интересно, какие есть практические применения ответа на этот вопрос.

bt2901 Jul 3 at 14:14

Такое ощущение, будто из этого можно построить какой-то чудной криптографический протокол а-ля proof of work. Берём некоторое множество специальной структуры (чтобы исключить лёгкие тривиальные ответы типа "все нечётные элементы") и просим вторую сторону предъявить бессумное подмножество размера в хотя бы N/3 + 10 элементов. Благодаря описываемому результату мы точно знаем, что решение существует и увеличение N позволяет регулировать вычислительную сложность задачи.

Аналог криптографии с открытым ключом тоже возможен: юзер генерирует большое бессумное множество размера N (это пароль), к нему как-то хитро добавляется 2N случайных чисел, при аутентификации мы показываем это большое множество размера 3N и просим предъявить его бессумное подмножество размера N. Это скорее всего не очень надёжно и не очень эффективно, но в областях типа защиты от спама или криптовалют может иметь смысл.

Proscrito Jul 4 at 18:43

Практического применения не находится для большей части того, чем занимается современная математика. Естественные науки обычно эксплуатируют уже существующий математический аппарат, и часто существующий уже очень давно, а большая часть математики и вовсе не востребована в материальном мире. Из этого правила существуют редкие исключения, когда другим дисциплинам не хватает математического аппарата, но честно говоря ближайшее что пришло в голову это Ньютон. Когда он единолично разработал дифференциально-интегральное счисление, только чтобы объяснить эллиптичность орбит планет. Наверняка кто-то сможет найти примеры поближе, но факт остается фактом: сегодня математика нужна в основном для другой математики. Это не делает ее менее ценной конечно, в науке вообще заранее обычно неизвестно найдется ли новым открытиям практическое применение, и если найдется то в каком столетии. Но практическое применение не вопрос и не задача науки, ее цель найти ответы. И любой заполненный пробел в знаниях когда-нибудь будет частью фундамента для чего-то еще.