The multiple-free subset-sum conjecture for powers of two

Let zNz\in\mathbb{N} and let A={a1,,ak}[2z]A=\{a_1,\ldots,a_k\}\subseteq[2^z], where [2z]={1,2,,2z}[2^z]=\{1,2,\ldots,2^z\}. For each non-empty subset AiA_i of AA, write S(Ai)S(A_i) for the sum of its elements. Multiple-free subset-sum conjecture. If for every i,j2k1i,j\le 2^k-1 the quotient

S(Ai)S(Aj)\frac{S(A_i)}{S(A_j)}

is not a power of 22, then

k=z+O(1).k=z+O\left(1\right).

The condition says that the subset sums form a multiple-free sequence with respect to powers of 22. The conjecture is motivated by numerical data and would sharpen the known lower-bound constructions for this problem; the paper does not provide a proof or resolution.

Sources & referencesView supporting material

Primary source

Konstantinos Gaitanas, “Two divisibility problems on subset sums”, arXiv:1911.11097 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.