2
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Beautiful, thanks! Am I correct in saying that we can use the Hyperplane Separation Theorem instead of the more general Hahn-Banach? $\endgroup$
    – Shaull
    Mar 22 at 19:43
  • 2
    $\begingroup$ 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$). $\endgroup$ Mar 22 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.