Balancing sets of vectors

Publication date 25 February 2011

Abstract: Let

n

be an arbitrary integer, let

p

be a prime factor of

n

. Denote by

o m e g a_{1}

the

p^{t h}

primitive unity root,

o m e g a_{1} := e^{f r a c 2 p i i p}

. Define

o m e g a_{i} := o m e g a_{1}^{i}

for

0 l e q i l e q p - 1

and

B := {1, o m e g a_{1}, ..., o m e g a_{p - 1}}^{n}

. Denote by

K (n, p)

the minimum

k

for which there exist vectors

v_{1}, ..., v_{k} i n B

such that for any vector

w i n B

, there is an

i

,

1 l e q i l e q k

, such that

v_{i} c d o t w = 0

, where

v c d o t w

is the usual scalar product of

v

and

w

. Gr"obner basis methods and linear algebra proof gives the lower bound

K (n, p) g e q 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, ..., 4 n

with

| A_{i} | = 2 n

for each

1 l e q i l e q n

, such that for any subset

B s u b s e t e q [4 n]

with

2 n

elements there is at least one

i

,

1 l e q i l e q m

, with

A_{i} c a p B

having

n

elements. We obtain here the result

m (p) g e q p

in the case of

p > 3

primes.

Recommendations

Cited in

(18)

This page was built for publication: Balancing sets of vectors