Изучаем гипотезы о сумме-произведения

Журнал Quanta опубликовал вчера статью о проблеме суммарных произведений Пола Эрдоса и Эндре Семереди. Эта проблема начинается с конечного набора действительных чисел A, а затем так же рассматривается размер множеств A + A и A * A. То есть, если мы добавим каждый элемент A к каждому другому элементу A, сколько будет разных сумм? Если вместо этого мы возьмем продукты, сколько будет различных продуктов?

Проверенные результаты

Эрдёш и Семереди доказали, что существуют такие константы c и ε> 0, что

max {| A + A |, | A * A |} ≥ c | A | 1 + ε  

Другими словами, либо A + A, либо A * A существенно больше, чем A. Erdős и Szemerédi только доказали, что существует некоторое положительное значение ε, но они подозревали, что можно выбрать такое ε, значение которого будет близким к 1, то есть, получается, что либо | A + A | или | A * A | ниже ограничен фиксированным кратным| A |². Джордж Шакан позже показал, что можно принять ε за любое значение меньше

1/3 + 5/5277 = 0,3342899…

но остается предположение, что верхний предел ε равен 1.

Код на Python

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

 from numpy.random import choice

    def trial(R, N):
        # R = integer range, N = sample size
        x = choice(R, N, replace=False)
        s = {a+b for a in x for b in x}
        p = {a*b for a in x for b in x}
        return (len(s), len(p))

Когда я впервые запустил этот код, я подумал, что в нем есть ошибка. Я 10 раз вызывал метод trial и получал каждый раз те же значения для | A + A | и | A * A |. Все из-за того, что я выбрал R большим относительно N. В этом случае вполне вероятно, что каждая сумма и каждый продукт будут уникальными, за исключением избыточности от коммутативности. То есть, если R >> N, вполне вероятно, что | A + A | и | A * A | будут равны N(N + 1)/2. А вот когда N стремиться ближе к R  становится интереснее.

Вероятность против комбинаторики

Проблема Эрдеша-Семереди - это проблема комбинаторики, которая ищет детерминированные нижние оценки. Но кажется естественным рассмотреть вероятностное расширение. Вместо того, чтобы спрашивать о нижних оценках | A + A | и | A * A |, вы можете попросить распределение | A + A | и | A * A | когда множества A взяты из некоторого распределения вероятностей.

Если множество A взято из непрерывного распределения, то | A + A | и | A * A | оба равны N(N + 1)/2 с вероятностью 1. Только осторожный выбор, который может произойти случайно с нулевой вероятностью, может помешать суммам и произведениям стать уникальными по модулю коммутативности, как в случае R >> N выше.

Если множество A является арифметической последовательностью, то | A + A | маленькое значение, а| A * A | будет большим. Так же и имеет место и обратное, если A является геометрической последовательностью. Поэтому может быть интересно взглянуть на соотношение | A + A | и | A * A |, когда A исходит из дискретного распределения, например, выбирая N целых чисел равномерно из [1, R], когда N/R не слишком мало.