Is number of different sums monotone?

Question

Suppose you have a set $S$ consisting of $n$ different integers. Let $$W_k = \#\biggl\{x\in\Bbb Z\colon \text{there exists } T \subseteq S,\, \#T=k,\, \sum_{a \in T} a = x\biggr\}.$$

My question is: is it always the case that $W_\ell \leq W_k$ if $\ell \leq k \leq n/2$?

Answer 1

This looks to be a surprisingly delicate problem. Some comments:

1. There is an easy lower bound $(n-k) W_k \leq n W_{k+1}$ for any $1 \leq k < n$. Indeed, any element $x$ of $W_k$ can contribute at least $n-k$ elements to $W_{k+1}$ by adding an element $a$ of $S$ to $x$ that is not in a specific representation of $x$ as a sum of $k$ distinct elements of $S$, and each element of $W_{k+1}$ will be represented at most $n$ times in this fashion. So in particular, for fixed $k$ we at least have $(1-o(1)) W_k \leq W_{k+1}$ as $n \to \infty$.

2. In characteristic 2, the claim $W_1 \leq W_2$ can fail. Indeed, take $S = {\bf F}_2^d$, then $W_1 = 2^d$ and $W_2 = 2^d-1$ because one cannot represent $0$ as the sum of two distinct elements of $S$. So if the conjecture is true, it has to use the fact that the characteristic is not $2$.

3. But returning to the integers, we do have $2W_1-3 \leq W_2$, and hence $W_1 \leq W_2$ for $n \geq 3$, because if we order the elements of $S$ as $a_1 < \dots < a_n$, the elements $a_i+a_n$ for $1 \leq i < n$ as well as $a_1+a_j$ for $2 \leq j \leq n$ are distinct and each contribute to $W_2$. (As a side note: the analogous statement in ${\bf Z}/p{\bf Z}$ was a conjecture of Erdos and Heilbronn, first solved by da Silva and Hamiduone.)

4. The ratio $W_{k+1}/W_k$ can be as small as $\frac{2^k}{2^k-1}+o(1)$ in the asymptotic limit $n \to \infty$, as can be seen by the example $S := \{0,\dots,m\} \cup \{ m, 2m, 2^2 m, \dots 2^{k-1} m\}$, where one can check that $n = (1+o(1))m$, $W_k = (2^k-1+o(1))m$, and $W_{k+1} = (2^k+o(1)) m$ as $m \to \infty$. So there is only an exponentially small amount of room (in $k$) to play with here. To me, this indicates that some induction on $k$ may be needed.

5. I can show with a complicated argument that inequality $W_2 \leq W_3$ holds for sufficiently large $n$. Sketch of proof: write $k^* S$ for the set of sums of distinct $k$-tuples in $S$, so that $W_k = |k^* S|$. The double counting argument gives $$ \{ (x,y) \in S \times 2^* S: x+y \in 3^* S \} \geq W_2 (n-2).$$ If $W_3 \leq W_2$, one can show after some calculation using Pollard's inequality (Pollard, J. M., A generalisation of the theorem of Cauchy and Davenport, J. Lond. Math. Soc., II. Ser. 8, 460-462 (1974). ZBL0322.10024.) that this forces $W_2 \gg n^2$ (here is where we use the fact that we do not have small characteristic). On the other hand, from Cauchy-Schwarz it also forces $$ \sum_{a,a' \in S} r_{2^* S}(a-a') \geq W_2 (n-2)^2$$ where $r_{2^* S}(x)$ is the number of representations $x=b-b'$ with $b,b' \in 2^* S$. This implies that $a-a' \in \mathrm{Sym}_{1-1/100}(2^* S)$ for $1-O(1/n)$ of the pairs $a,a' \in S$, where $\mathrm{Sym}_\delta(2^* S)$ denotes those shifts $h$ with $|2^* S \cap (2^* S-h)| \geq \delta |2^* S|$. A triangle inequality argument then implies that all but $O(1/n)$ of the sums $a+a'$ that could lie in $2^* S$ lie in a translate of $\mathrm{Sym}_{1-1/10}(2^* S)$ (say), which has size at most $|2^* S|/2$ by another application of Pollard's inequality. But then we have $W_2 \leq \frac{1}{2} W_2 + O(n)$ which contradicts $W_2 \gg n^2$ for $n$ large enough.

EDIT: With a variant of the argument in point 5, I can now show that for any given $k$, one has $W_{k+1} \geq W_k$ for all sufficiently large $n$.

It is convenient to use the formalism of nonstandard analysis to avoid some tedious "epsilon management". Suppose for contradiction that the claim is false for some (standard) $k$, then there exists a hyperfinite set $S$ of nonstandard integers such that $W_{k+1} < W_k$, with $S$ having unbounded cardinality. For each standard $i$, if we assign to each element $x$ of $i^* S$ a specific representation as the sum of $i$ distinct elements of $S$, we see that for a randomly chosen $s_0 \in S$, that $s_0$ will avoid this representation (and hence $x+s_0 \in (i+1)^* S$ with probability $1-i/n = 1-o(1)$. Hence by double counting, with probability $1-o(1)$, $$ |(i^* S + s_0) \backslash (i+1)^* S| = o(|i^* S|)$$ and so by saturation we can find an $s_0$ such that the above claim holds for all standard $i$. Translating $s_0$ to the origin, we now have that the $i^* S$ are essentially monotone increasing in the sense that $$ |i^* S \backslash (i+1)^* S| = o(|i^* S|) = o(W_i) \tag{1}$$ for all standard $i$. Since we are assuming $W_{k+1} \leq W_k$, we conclude in particular that $$ |(k+1)^* S \Delta k^* S| = o(W_k) \tag{2}.$$ If we call any set of size $o(W_k)$ negligible, we now see that the $i^* S$ are increasing modulo negligible sets for $i \leq k$, and that $(k+1)^* S$ and $k^* S$ are equal modulo negligible sets.

By double counting, we have $$ |\{ (x,y) \in S \times k^* S: x+y \in (k+1)^* S\}| \geq (n-k) W_k$$ and hence $$ \sum_{x \in S} (W_k - |\{ y \in k^* S: x+y \in (k+1)^* S\}|) \leq k W_k.$$ The summands are non-negative. By Markov's inequality, we conclude that for every standard $\varepsilon > 0$ that $$ |\{ y \in k^* S: x+y \in (k+1)^* S\}| \geq (1-\varepsilon) W_k$$ for all but a bounded number of elements $x$ of $S$; by (2) this implies that $$ x \in \mathrm{Sym}_{1-\varepsilon+o(1)}(k^* S) \tag{3}$$ for all such $x$. In particular, setting $\varepsilon = 1/100k$ and using the triangle inequality, we can cover $2k^* S$ by a bounded number of translates of $\mathrm{Sym}_{1/2}(k^* S)$, which implies that $k^* S$ has bounded doubling (since $|\mathrm{Sym}_{1/2}(k^* S)| \ll |k^* S|$). By Freiman's theorem, one may then place $k^* S$ in a bounded rank generalized arithmetic progression $$ P := \{ n_1 v_1 + \dots + n_d v_d: |n_i| \leq N_i \forall i=1,\dots,d\}$$ of cardinality $O(W_k)$, which we can take to be infinitely proper ($t$-proper for any standard $t$) by well-known arguments. By enlarging $P$ slightly if necessary we may also assume that $P$ contains $S$ (since from (3), $P$ already contained all but a bounded number of elements of $S$ anyways).

For any standard $\varepsilon > 0$, let $m$ denote the number of elements of $S$ lying outside of the dilate $\varepsilon P$. From (3) we know that $m$ is bounded (with a bound depending on $\varepsilon$). On the other hand, $k^* S$ is contained in $O((1+m)^k)$ translates of $k \varepsilon P$ (where the implied constant doesn't depend on $\varepsilon$ or $m$). Since $|k^* S| \gg |P|$ and $|k \varepsilon P| \ll k \varepsilon |P|$, we conclude that $$ (1+m)^k (k \varepsilon) \gg 1$$ and hence $$ 1+m \gg \varepsilon^{-1/k}$$ (where again constants don't depend on $\varepsilon,m$). Making $\varepsilon$ small enough, and using the pigeonhole principle, and relabeling and reflecting as necessary, we can then find $k$ elements $x_1,\dots,x_k$ of $S$ such that if we expand $$ x_i = n_{1,i} v_1 + \dots + n_{d,i} v_d$$ then $n_{i,1}$ is positive with $n_{i,1} \gg N_1$. We may order the $x_i$ in decreasing order of $n_{i,1}$, thus $$ N_1 \geq n_{1,1} \geq n_{2,1} \geq \dots \geq n_{k,1} \gg N_1,$$ and we may assume that any other $x \in S$ has a smaller value of $n_1$ than $n_{k,1}$.

Let $\varepsilon>0$ be a sufficiently small standard real. By previous discussion, $k^* S$ can be covered by a bounded number of translates of $\mathrm{Sym}_{1-\varepsilon}(k^* S)$, hence the latter set is not negligible. Hence $k^* S \cap \varepsilon P$ is not negligible either. Now let $1 \leq i \leq k$ be the first $i$ for which $i^* S \cap \varepsilon P$ is not negligible. Then the set $$ x_1 + \dots + x_{k+1-i} + (i^* S \cap \varepsilon P) \tag{4}$$ is non-negligible and contained in $(k+1)^* S$. On the other hand, we claim that it has a negligible intersection with $k^* S$, which will contradict (2). Indeed, note that $k^* S$ consists of the union of boundedly many sets of the form $$ y_1 + \dots + y_{k-j} + j^* (S \cap \frac{\varepsilon}{k} P) \tag{5}$$ where $0 \leq j \leq k$, and $y_1,\dots,y_{k-j}$ are distinct elements drawn from the bounded number of elements of $S$ lying outside of $\frac{\varepsilon}{k} P$. By construction of $i$, these sets (5) are negligible for $j<i$ (since $j^* (S \cap \frac{\varepsilon}{k} P) \subset j^* S \cap \varepsilon P$), so we may assume $j \geq i$. But then the $n_1$ coordinate of $y_1 + \dots + y_{k-j}$ is less than that of $x_1+\dots+x_{k+1-i}$ by an amount that is $\gg N_1$, thanks to the construction of the $x_i$ so this set (5) will be disjoint from (4) in these cases if we choose $\varepsilon$ small enough. The claim follows.

Answer 2

A counterexample for the exact inequality: $S = \{1,2,3,4,7,8,9,10\}$. Then $W_3 = 22$ (we get the numbers $6, 7, \dotsc, 27$) and $W_4 = 21$ (we get $10$, $34$, and the numbers $13, 14, \dotsc, 31$).