Equal subset-sums of bounded vectors

Question

Let $S\subseteq \{0,\ldots,n\}^d$ be a set of $d$-dimensional vectors of with bounded, natural, coordinates.

We are given that $$v'+v_1+\ldots+v_t=u'+u_1+\ldots+u_s$$ where $v_1,\ldots,v_t,u_1,\ldots,u_s,v',u'\in S$ (and the vectors are not necessarily distinct).

That is, two sets of vectors whose sums are equal.

I want to prove that, if $t$ and $s$ are large enough, then there exist subsets $I\subseteq \{1,\ldots,t\}$ and $J\subseteq \{1,\ldots > s\}$ such that $$\sum_{i\in I}v_i=\sum_{j\in J}u_j$$

Note that, without the assumption of the equal sum above, there may not be such sets (e.g., if all the $v_i$ are $(1,0)$, and all the $u_i$ are $(0,1)$). Also, for small $s,t$ there may not be such sets.

Some informal thoughts: My intuition is that for large enough $s,t$, we can force a lot of repetitions of vectors within the sets, and then we can ``tailor'' equal sums. This is somewhat akin to a vector version of Erdős-Ginzburg-Ziv (or the Van Emde Boas - Kruyswijk variation, which looks at vectors), but instead of looking at the finite abelian group, I have the sum above to bound the behaviour.

Also, I don't really care about tight bounds for $s,t$. They can be as large as needed (e.g., exponential, or even double exponential in $|S|,n$ is fine).

Answer 1

As I understand, your $n$ and $d$ are fixed, and you want to prove the existence of corresponding non-empty subsets $I$, $J$ provided that both $t$, $s$ are large enough (greater than some constant $C(n,d)$).

This is true.

We find a positive integer $M$ satisfying the following condition: whenever $U,V$ are finite subsets of $\{0,\ldots,n\}^d$ such that their conic hulls (convex cones generated by $U,V$ respectively) have a common non-zero point, we get $\sum_{i=1}^{M_1} v_i=\sum_{i=1}^{M_2} u_i$ for certain $M_1,M_2\in \{1,\ldots,M\}$ and $v_i\in V$, $u_i\in U$ (not necessarily distinct).

Now assume that $t,s$ are large enough and define $$V=\{v_i\,\text{which appear at least}\, M\,\text{times between}\,v_1,\ldots,v_t \},\\U=\{u_i\,\text{which appear at least}\, M\,\text{times between}\,u_1,\ldots,u_s \}.$$ If the conic hulls of $V$, $U$ have non-empty intersection, we are done. Otherwise by Hahn--Banach the sets $U$, $V$ are separated by a linear functional $f:\mathbb{R}^d\to \mathbb{R}$: $f(u)>0>f(v)$ for all non-zero $u\in U$, $v\in V$. This $f$ depends on $U$, $V$, fix it for each pair $U,V$. If both $U$, $V$ contain a zero vector, again we are done. Otherwise applying $f$ to both parts of the equality $v'+v_1+\ldots+v_t=u'+u_1+\ldots+u_s$ we see that LHS is much less than RHS if $t$, $s$ are large enough (because the number of $i$ for which $u_i\notin U$ or $v_i\notin V$ is bounded, and for other indices either $f(u_i)$ or $f(v_i)$ is bounded away from 0.)