# Equal subset-sums of bounded vectors

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).

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)$$).
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.)
• There are many versions of separation theorem all of which I call Hahn—Banach. Here it is enough to strictly separate two disjoint convex compact sets (the sections of corresponding cones by the plane $\sum x_i=1$). Mar 22 at 20:09