Comments 14
Медаль Филдса ему дадут?
Только Эрдёш всё же Пал, а не Пол. Там явный долгий звук А в имени.
Первый раз слышу про бессумные множества. Уточнил у перплексити, можно ли их применить в моделировании. Ответ интересный:
Можно ли применять бессумные множества для моделирования социальных или экономических систем
Бессумные множества могут быть применены для моделирования социальных и экономических систем, особенно в тех случаях, когда важно учитывать ограничения на взаимодействия или объединения элементов системы, чтобы избежать нежелательных "перекрытий" или конфликтов.
В частности:
В социальных системах бессумные множества могут моделировать группы или сообщества, в которых взаимодействия (например, объединение ресурсов или идей) не приводят к появлению новых членов или состояний, уже присутствующих в группе. Это помогает анализировать устойчивость и структуру социальных сетей без избыточных пересечений.
В экономике бессумные множества могут использоваться для моделирования систем с ограничениями на совокупные ресурсы или сделки, где сумма двух экономических показателей не должна попадать в определённый нежелательный диапазон, что позволяет избегать конфликтов интересов или избыточной конкуренции.
Такие модели могут служить в управлении рисками и предотвращении кризисных ситуаций, когда важно контролировать, чтобы комбинации факторов не приводили к критическим состояниям.
В более общем смысле, бессумные множества помогают формализовать и анализировать системы с ограничениями на суммы элементов, что полезно при построении алгоритмов и стратегий в социальных и экономических контекстах.
Хотя прямых примеров применения именно бессумных множеств в социально-экономических моделях в литературе немного, их свойства хорошо сочетаются с задачами, связанными с устойчивостью, предотвращением конфликтов и управлением сложными системами, что подтверждается исследованиями в области сложных систем и эргатических моделей.
спасибо очень интересно, поначалу даже растерялся, но сейчас чутка понял в чем суть) посмотрел что есть ) Задача_о_рюкзаке
В самом начале сразу же спотыкаюсь на абсолютно размазанной формулировке:
В 1965 году математик Пол Эрдёш задал на первый взгляд скромный вопрос: насколько часто встречаются такие бессумные множества?
Насколько часто ГДЕ встречаются? Без какой-либо конкретики на этот счёт вопрос не имеет смысла ;)
Ну и сразу же:
И вот — прорыв. В феврале этого года, спустя почти 60 лет после того, как Эрдёш впервые сформулировал задачу, Бенджамин Бедерт её решил. Он доказал, что любое множество целых чисел — как положительных, так и отрицательных — обязательно содержит крупное подмножество, в котором никакая пара не складывается в третий элемент.
Ага, уже "целых" ;) Т.е. с вещественными ничего не понятно?))
И что это за "крупное подмножество"? [1, 1, 2] - достаточно крупное подмножество? ;)
Т.е. с вещественными ничего не понятно?
С вещественными (должно быть) тривиально: любое конечное множество вещественных чисел, случайно выбранных из некоторого интервала с однородным распределением, - бессумно. Более того, такое множество линейно-независимо над рациональными числами с вероятностью единица. Действительно, рассмотрим всевозможные линейные комбинации 
, где 
- рациональные коэффициенты и 
- элементы исходного множества. Поскольку 
счетно, множество возможных сумм тоже счетно и, следовательно, нулевой меры. Вероятность того, что оно содержит 0 равна нулю.
Таким образом, бессумные множества действительных чисел встречаются очень часто: "все" (т.е. за исключением меры нуль, что может приводить к забавным чудовинкам с точки зрения конструирования) множества бессумны.
Бессумные множества целых чисел несложно конструировать. Скажем, любое множество составленное из кубов или четвертых степеней и т.д. по теореме Ферма бессумно.
Поэтому вопрос: а можно ли конструировать сумные множества? Например, с квадратами уже трюк не проходит из-за пифагоровых троек. Результат, о котором рассказывает заметка, говорит, что как бы мы ни изгалялись, всегда будет бессумное подмножество с как минимумом 
элементов. Какие-то варианты этого результата должны переноситься и на вещественные числа, а может даже и он сам в чистом виде.
а если просто запустить монтекарло симуляцию по производству последовательности чисел
Понятия не имею, для меня вся эта проблематика бесконечно далека. По (очень натянутой) аналогии с другими областями, на случайных последовательностях вполне может достигаться как раз нижний предел размера бессумных подмножеств. Однако, если читать между строк то, что говорили интервьюируемые, вероятно есть ожидание, что настоящий нижний предел больше того, что было доказано. Из заметки статус нового результата, кроме того, что он значительно улучшает предыдущие оценки, про которые сразу (?) было понятно, что они очень пессимистичные, непонятен.
Так. Непонятные моменты:
С вещественными (должно быть) тривиально: любое конечное множество вещественных чисел, случайно выбранных из некоторого интервала с однородным распределением, - бессумно.
Ну сразу ловите контрпример: {0.(3), 0.(6), 1.0} ;)
Поэтому вопрос: а можно ли конструировать сумные множества? Например, с квадратами уже трюк не проходит из-за пифагоровых троек.
Странно, мне вот почему-то кажется что именно пифагоровыми тройками такое и можно конструировать...
Или мы по разному понимаем трактовку? Надо чтобы вообще любая, случайно взятая, тройка чисел могла быть представлена в виде суммы и результата?
Как по мне, это вообще теорвер какой-то... Всё зависит от выборки...
Этот контрпример по сути сведение к проблеме целых чисел. Ничего нового он не дает. Я так понимаю, смысл поста был в том, что вещественные числа "неинтересны", их вещественность не добавляет ничего ценного.
Никто же не говорит, что не существует действительных чисел, сумма которых равна третьему действительному числу. Но если взять открытый интервал ненулевой меры и на нем ввести однородное распределие, то вероятность выбора конечной линейно независимой выборки равна единице.
Это, в частности, означает, что множество действительных чисел, содержащее сумму, должно специально конструироваться, вроде того, как Вы сконструировали свой пример. Вот из-за того, что такое конструирование вводит некую структуру целых чисел, мне и кажется, что результат из заметки переносится один в один на множества действительных чисел. Но это надо у числовиков спрашивать.
В заметке, на мой взгляд, проблема недостаточно хорошо поставлена. Вопрос насколько часто встречаются бессумные множества совсем неинтересен. Они появляются налево-направо: множество нечетных чисел, множество кубов и т.д. Но если мы посмотрим на множество квадратов, то из-за пифагоровых троек такое множество может и не быть бессумным. Досада! Вопрос, а сколько нужно выкинуть элементов из такого суммосодержащего множества, чтобы оно стало бессумным? Результат из заметки говорит, что не больше 2/3 элементов (и даже меньше на двойной логарифм), как бы хитро мы ни конструировали наше множество. Из множества квадратов, вероятно, одной трети было бы достаточно, но надо думать, нельзя ли там хитрые конструкции реализовать.
Из множества квадратов, вероятно, одной трети было бы достаточно, но надо думать, нельзя ли там хитрые конструкции реализовать.
Ну как квадраты между собой связаны - рядом нечётных чисел ;)
Ну и блин, это как бы очевидно - что таких чисел будет немного... Я вон, нейросети постоянно донимаю вопросами - "а не слишком ли много в природе (законах физики) всяких квадратов и кубов? умножение числа на самое себя - не самая вероятная операция для независимого рандома".
насколько часто встречаются такие бессумные множества?
Интересно, какие есть практические применения ответа на этот вопрос.
Такое ощущение, будто из этого можно построить какой-то чудной криптографический протокол а-ля proof of work. Берём некоторое множество специальной структуры (чтобы исключить лёгкие тривиальные ответы типа "все нечётные элементы") и просим вторую сторону предъявить бессумное подмножество размера в хотя бы N/3 + 10 элементов. Благодаря описываемому результату мы точно знаем, что решение существует и увеличение N позволяет регулировать вычислительную сложность задачи.
Аналог криптографии с открытым ключом тоже возможен: юзер генерирует большое бессумное множество размера N (это пароль), к нему как-то хитро добавляется 2N случайных чисел, при аутентификации мы показываем это большое множество размера 3N и просим предъявить его бессумное подмножество размера N. Это скорее всего не очень надёжно и не очень эффективно, но в областях типа защиты от спама или криптовалют может иметь смысл.
Сложение с подвохом: что мы до сих пор не понимаем в 1 + 1? Гипотеза Эрдеша о множествах без суммы