1. complete sets

Definition. A set \(S\) is \(r\)-complete if, for any \(r\)-coloring of \(S\) there is a monochromatic set of numbers in \(S\) summing to all sufficiently large values.

Definition. A set is \(\varepsilon\)-complete if, for any subset \(S'\) of \(S\) with size at least \(\varepsilon|S|\) there is a subet of \(S'\) summing to all sufficiently large values.

Theorem. There are \(\varepsilon\)-complete sets of size approx \(\varepsilon^{-1}\log^2 n\).

First need key lemma. Theorem follows immediately from lemma.

Lemma. Fix \(\varepsilon>0, n\in \mathbb{N}\). There is a set of \(\varepsilon^{-1}\log n\) many integers whose set of subsets contains an interval of size \(n\log n\) and starts at \(n/2\) or something.

Proof. Here we highlight the general technique that seems to be powering a lot of their results.

  1. Randomly sample numbers with no prime divisors smaller than \((\log n)/2\) (iirc)
  2. For the first little while, whenever you add a number it is quite likely to double the interval of attainable sums.
  3. Then once your interval is rather large and you’ve drawn a bunch of elements you can extend the interval by the size of the drawn elements each time.

TODO: figure out details?

Proof of theorem from lemma:

Proof. Dyadically apply the lemma

Theorem. There are no \(\epsilon\)-complete sets of size smaller than \(\log^2 n\)

2. avoiding a specific sum

Theorem. We say a coloring of \([n]\) is good if there is no monochromatic set of integers summing to \(n\).

I ignore log factors in following statement.

You need about \(n^{1/3}\) colors to be good. There exists a good coloring using \(n^{1/3}\) colors.

Proof.

We split our colors up into several types:

  1. big elements
  2. multiples of primes not dividing \(n\)
  3. everything else, grouped into groups with sums smaller than \(n\).

It turns out that after handling 1,2 there is not so much stuff left for 3, and what’s left is pretty small. So this ends up being a pretty efficient coloring.

3. \(r\)-complete sets

Proposition. \(\left\{ p^{i}q^{j}\right\}\) is not \(2\)-complete, but it is \(1\)-complete.

Proof. Here is a 2-coloring that demonstrates the set is not 2-complete. Color powers of \(p^{i}\) Red. Color everything else Blue. Then all Blue numbers are multiples of \(q\). So both blue and red and severely limited in the numbers they can achieve.

TODO1: prove it is 1-complete

Remark. As far as I know it is not known whether \(\left\{ p^{i}q^{j}r^{k}\right\}\) is \(2\)-complete or not.

TODO2: solve

4. subset-sum free set

Proposition. The set \(1,2,4,\ldots, 2^{k-1}\) has the property that all of its subset sums are distinct.

Theorem. Let \(a_1<a_2<\cdots <a_k\) be positive integers such that all subset sums of \(\left\{ a_i\right\}\) are distinct. Then \(a_k \ge 2^{k}/\sqrt{k}\).

Proof.

First we give an easy argument to show \(a_k \ge 2^{k}/k\). If \(a_k<2^{k}/k\) then all subset sums would be contained in \([2^{k}-1]\). But there are \(2^{k}\) subset sums so they could then not all be distinct.

To prove \(2^{k}/\sqrt{k}\) we use second moment method. If you take a random sum it is tightly concentrated.

TODO3: figure this out more

Fox talked about how they did something fancy isoperimetric inequality boolean cube to get a better constant.

TODO4: upper or lower bounds is a kind of fun openq to think about

UPDATE The most obvious way to get a subsetsum free set is greedily forwards: repeatedly pick the largest number that is still available. This gives powers of \(2\). Another idea is greedy backwards: start by picking the largest number, and then go backwards, selecting at each step the largest number which is still available.

Turns out the greedy backwards approach gives a neat sequence, and \(\approx 0.235\cdot 2^{n-1}\). This is not SotA. SotA is \(.202\cdot 2^{n-1}\) or something.

"""
this is code for erdos distinct sums problem 

OEIS this
[13, 12, 11, 9, 6]                              **** 1 1 2 3
[24, 23, 22, 20, 17, 11]                        **** 1 1 2 3 6
[44, 43, 42, 40, 37, 31, 20]                    **** 1,1,2,3,6,11
[84, 83, 82, 80, 77, 71, 60, 40]                **** 1 1 2 3 6 11 20
[161, 160, 159, 157, 154, 148, 137, 117, 77]    **** 1 1 2 3 6 11 20 40
[309, 308, 307, 305, 302, 296, 285, 265, 225, 148]

"""

from itertools import combinations

def has_distinct_subset_sums(nums, printit=False):
    subset_sums = set()
    for i in range(1 << len(nums)):
        subset_sum = sum(nums[j] for j in range(len(nums)) if (i >> j) & 1)
        if subset_sum in subset_sums:
            return False
        subset_sums.add(subset_sum)
    if printit:
        print(subset_sums)
        print(len(subset_sums))
    return True

n = 24
m = 6
for subset in combinations(list(range(1,n+1)), m):
    if has_distinct_subset_sums(subset):
        print(subset)

def greedy(big):
    X = [big]
    subsetsums = {0, big}
    for i in range(big,1,-1):
        compatible = True
        for s in subsetsums:
            if s+i in subsetsums:
                compatible = False
                break
        if compatible:
            X.append(i)
            Y = [s+i for s in subsetsums]
            for y in Y:
                subsetsums.add(y)
    return X

record = 1
for i in range(1,500):
    score = i / 2**(len(greedy(i))-1)
    if score < record:
        print(greedy(i))
        record = score
        print(round(100*score, 2))