Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

EDIT (By Tara B): I'd still be interested in a reference to a proof of this, as I had to prove it myself for my own paper.

I'm looking for the proof of Theorem 4 that appears in this paper:

An Infinite Hierarchy of Intersections of Context-Free Languages by Liu and Weiner.

Theorem 4: An $n$-dimensional affine manifold is not expressible as a finite union of affine manifolds each of which is of dimension $n-1$ or less.

  1. Does anyone knows a reference to the proof?
  2. If the manifold is finite and we define a natural order on the elements, is there any similar statement in terms of lattices?

Some background to understand the theorem:

Definition: Let $\mathbb{Q}$ be the set of rational numbers. A subset $M\subseteq \mathbb{Q}^n$ is an affine manifold if $(\lambda x+(1-\lambda)y)\in M$ when $x\in M$, $y\in M$, and $\lambda\in\mathbb{Q}$.

Definition: An affine manifold $M'$ is said to be parallel to an affine manifold $M$ if $M'=M+a$ for some $a\in \mathbb{Q}^n$.

Theorem: Each non-empty affine manifold $M\subseteq \mathbb{Q}^n$ is parallel to a unique subspace $K$. This $K$ is given by $K=\{x-y:x,y\in M\}$

Definition: The dimension of a non-empty affine manifold is the dimension of the subspace parallel to it.


share|improve this question
    
I know this is quite an old question, but I just happened across it today, and just wanted to ask whether you were reading that paper for any particular reason? (It happens to be very closely related to some of my research.) –  Tara B Feb 16 '13 at 14:16

2 Answers 2

up vote 5 down vote accepted

Intuitively, the theorem says that a line is not a finite union of points, a plane is not a finite union of lines, etc. The simplest proof is to observe, for example, that a finite union of lines has zero area, whereas a plane does not.

More concretely, observe that it is enough to prove the claim for manifolds on $\mathbb{R}^n$ by passing to their closures. Consider an affine manifold $M\subseteq \mathbb{Q}^n$ given by the set of solutions to the linear system $A x = b$; its closure will be precisely the set of solutions to the same system over $\mathbb{R}^n$, hence this step does not affect the dimension of the manifolds involved. Also, the closure of a finite union equals the union of the closures.

Now note that the $d$-dimensional Lebesgue measure of a manifold of dimension $\le d - 1$ is null. Therefore the $d$-dimensional Lebesgue measure of a finite union of such manifolds is still zero. But the $d$-dimensional measure of an $d$-dimensional manifold is infinite, hence non-zero.

As for your second question, I'm not quite sure what you mean. But if the base field $\mathbb{F}$ is finite, then any $d$-dimensional affine manifold over $\mathbb{F}^n$ contains $|\mathbb{F}|^d$ points. So by a similar counting argument, you need at least $|\mathbb{F}|^d/|\mathbb{F}|^{d-1}=|\mathbb{F}|$ affine spaces of dimension $\le d - 1$ to cover an affine space of dimension $d$.

share|improve this answer
    
thanks!! this answers both questions. What I've (very unclearly) meant in the second question was "what would happen if instead of an affine manifold we had a finite convex set". But still, your answer cleared my doubts. –  Marcos Villagra Feb 8 '12 at 1:50

Here is a measure-free proof which works for affine manifolds over an arbitrary infinite field $\mathbb F$ (the result is false for finite fields).

By induction on $n\ge0$, we will show that an affine manifold $A\subseteq\mathbb F^m$ of dimension $n$ is not a finite union of affine manifolds of dimension less than $n$.

The statement is clear for $n=0$: a point is not a (finite) union of empty sets.

Assume the statement holds for $n$, we will show it for $n+1$. Let $A=\bigcup_{i<k}A_i$, where $\dim(A)=n+1$ and $\dim(A_i)\le n$. Consider an arbitrary affine submanifold $B\subset A$ of dimension $n$. Since $B=\bigcup_i(B\cap A_i)$, the induction hypothesis implies that $\dim(B\cap A_i)=n$ for some $i<k$, i.e., $B=A_i$. Since there are only $k$ sets $A_i$, and $B$ was arbitrary, it follows that $A$ has only finitely many submanifolds of dimension $n$. However, this is a contradiction: if we fix any such submanifold $B_0$ and a vector $v$ parallel to $A$ but not to $B_0$, there are infinitely many affine submanifolds of $A$ of the form $B_0+av$, where $a\in\mathbb F$.

share|improve this answer
    
nice alternative proof! –  Marcos Villagra Feb 8 '12 at 1:48
2  
No, this is the proof and the other one is alternative because it drags in measure theory :-) –  Andrej Bauer Feb 8 '12 at 7:49
    
Ahhh I see, good point –  Marcos Villagra Feb 8 '12 at 10:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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