From: Martin <ae53@rz.uni-karlsruhe.de>
Subject: Re: Problem with linear combinations of convex sets
Date: 2 Jan 2000 13:24:41 -0600
Newsgroups: sci.math,sci.math.research,sci.math.symbolic
Summary: Rusin goofs again

Happy new year and thank you for your answer!

But I think it is not correct.

Dave Rusin wrote:
> 
> In article <386A17DD.167EB0E7@rz.uni-karlsruhe.de>,
> Martin  <ae53@rz.uni-karlsruhe.de> wrote:
> >Given $n-1$ convex compact subsets $K_i,\ i=1,\ldots,n-1$
> >of $\R^n$ with the property that
> >$$\forall (x_1,\ldots,x_{n-1})\in K_1\times\ldots\times K_{n-1}:
> >\{x_1,\ldots,x_{n-1}\} \mbox{ is linearly independent.}
> >$$
> >
> >Can I always find a fixed $x_n\in\R^n$ such that
> >$$\forall (x_1,\ldots,x_{n-1})\in K_1\times\ldots\times K_{n-1}:
> >\{x_1,\ldots,x_{n-1},x_n\}\mbox{ is linearly independent?}
> >$$
> >
> >For $n=2$ and $n=3$ I could prove that such an $x_n$ exists,
> 
> Let's try n=4, then. I think I have a counterexample for the simplest case,
> in which the  K_i  are just line segments. That situation can, except in
> degenerate cases, be reduced to one like this:
>  K1  is the set of vectors [1,0,u,0]  with |u| <= 1;
>  K2  is the set of vectors [0,1,0,v]  with |v| <= 1;
>  K3  is the set of vectors [a,b,c,d]+t[e,f,g,h]  with |t| <= 1.
> There are some conditions to be satisfied by abcdefgh to guarantee linear
> independence. I hope I have worked them out properly (I used techniques as
> below); I think it's sufficient to have |g+-e| < |c+-a| and |h+-f| < |d+-b|.
> Anyway, I chose a = 12, b = 7, c = 8, d = 4, e = 1, f = 5, g = 2, h = 3.
> 

I'm afraid (or perhaps relieved because I would prefer a POSITIVE answer
to my problem;-)) that these sets are not linearly independent.
Take u=2/3, v=4/7, t=0. Then
12*(1,0,2/3,0)+7*(0,1,0,4/7)=(12,7,8,4).

I think that the condition for linear independence is that not all 3x3
sub-determinants of 
|1	0	u	0   |
|0	1	0	v   |
|a+te	b+tf	c+tg	d+th|
must vanish  for the same value (u,v,t)\in [-1,1]^3, and this leads to
the necessary and sufficient condition that the system
u(a+te)=c+tg
v(d+th)=b+tf
has no solution in [-1,1]^3. (This yields under additional assumptions
equations like |a+-e|<|c+-g|.)

It would be interesting to know if under these conditions there exists a
counterexample. But generally a counterexample with convex sets of
positive n-dimensional measure should be easier to find than with
straigth lines.

Martin