Balancing Sets of Vectors

Abstract

Let $n$ be an arbitrary integer, let $p$ be a prime factor of $n$. Denote by ${\omega }_1$ the $p^{th}$ primitive unity root, ${\omega }_1:=e^{\frac{2\pi i}{p}}$. Define ${\omega }_i:={\omega }_1^i$ for $0\le i\le p-1$ and $B:=\{1,{\omega }_1,...,{\omega }_{p-1}{\}}^n$. Denote by $K(n,p)$ the minimum $k$ for which there exist vectors $v_1,...,v_k\in B$ such that for any vector $w\in B$, there is an $i$, $1\le i\le k$, such that $v_i\cdot w=0$, where $v\cdot w$ is the usual scalar product of $v$ and $w$. Gröbner basis methods and linear algebra proof gives the lower bound $K(n,p)\ge n(p-1)$. Galvin posed the following problem: Let $m=m(n)$ denote the minimal integer such that there exists subsets $A_1,...,A_m$ of $\{1,...,4n\}$ with $|A_i|=2n$ for each $1\le i\le n$, such that for any subset $B\subseteq [4n]$ with $2n$ elements there is at least one $i$, $1\le i\le m$, with $A_i\cap B$ having $n$ elements. We obtain here the result $m(p)\ge p$ in the case of $p>3$ primes.

arXiv commentappeared in Studia Sci. Math. Hung