Arithmetic Progression-Free Subset-Sum Sets

Abstract

For a finite set $A$ of positive integers, let $H(A)$ be its set of subset sums, including the empty sum, and let $g_k(n)$ be the least $N$ for which some $n$-element set $A\subseteq [N]$ has $H(A)$ free of nonconstant $k$-term arithmetic progressions. The problem of determining $g_k(n)$ was posed by Erdős and Sárkőzy. In the three-term case, we prove a lower bound equal to the exact bandwidth of the ternary grid. If $T_m=[x^m](1+x+x^2{)}^m$ is the central trinomial coefficient, then \[ g_3(n)\ge \frac{T_n-1}{2}+\sum_{j=0}^{n-1}T_j =\left(\frac{\sqrt{3}}{2\sqrtπ}+o(1)\right)\frac{3^n}{\sqrt{n}}. \] For general $k\ge 4$ we show \[ g_k(n)\gg_k \left(\frac{k-1}{k-2}\right)^n n^{-\log_2((k-1)/(k-2))} \] In the opposite direction, a carry-free digit construction based on nearly-regular graphs gives \[ \limsup_{n\to\infty}g_k(n)^{1/n} \le \min_{p\ \mathrm{prime},\ p\ge3}p^{2/(\min\{p,k\}-1)}. \] Consequently, as $k\to \infty$, the logarithm of the lower exponential rate is at least $(1+o(1))/k$, while the logarithm of the upper exponential rate is at most $(2+o(1))\log k/k$.