Let $e=[1,1,\ldots,1]\in\mathbb{Z}^n$. I am looking for a way to find a vector $a\in\mathbb{Z}^n$ such that:

  1. $\langle a,e\rangle=0$ and
  2. for every nonnegative $v\in\mathbb{Z}^n$ such that $\langle e,v\rangle=n$ and $v\neq e$ we have $\langle a,v\rangle\neq 0$

Here the vector $v$ is nonnegative if it has nonnegative entries. The $\langle a,v\rangle$ denotes the standard scalar product. I am looking for the $a$'s whose lengths would polynomially depend on $n$ (actually my cost is the maximum of the absolute values $|\langle a,v\rangle|$ over all $v$'s as above).

The question is motivated by my attempts to find a convenient way to cancel out, in calculations, the inputs of nontrivial partitions, leaving only the one coming from $1+1+\ldots+1=n$.


There is no chance you can keep $a$ of polynomial size. Indeed, let $a$ be any vector with the sum of absolute values less than ${n\choose [n/2]}/2$. Then among the sums $\sum_{k\in I}a_k$ where $I\subset\{1,\dots,n\}$, $|I|=[n/2]$ there are two equal, meaning that there is a non-trivial vector $w$ consisting of $0,\pm1$ such that $\langle a,w\rangle=\langle e,w\rangle=0$. Then $v=e+w$ is your killer.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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