- #1
snoble
- 127
- 0
This is a solution to a problem I posed in the Q&A thread
I can't seem to get to sleep and I promised a proof of no finite paired sets with containing an irrational. So I might as well be semi-productive and type one up. There are several proofs but in my mind the following is the slickest.
Assume for contradiction that P is a finite paired set and x\in P where x is irrational. Take B=\{b_0, b_1, \ldots , b_n\} to be a \mathbb{Q}-linearly independent set that spans P and such that b_0=1, b_1=x. In other words if \sum_{i=0}^n q_ib_i = 0 and all the q_i's are rational then all the q_i's equal 0. And the fact that it spans P means for y\in P there exists y_0,\ldots ,y_n \in \mathbb{Q} such that \sum_{i=0}^n y_ib_i =y. For any finite set of reals such a "basis" is always constructible. The important thing to notice is that because of the linear independence of the base the choice of coefficients is unique.
Now you are going to map all the y\in P to \mathbb{R}\times\mathbb{R} where the first coordinate is y_1 and the second is y-y_1b_1. Let's call this map f. For example x gets mapped to f(x) =(1,x-1\times b_1)= (1,x-x) = (1,0) and 1 gets mapped to f(1)=(0,1). In general f(\sum y_ib_i) = (y_1, y-y_1b_1). Notice that for any p,q \in P that p-q is also in the span of B. But more importantly
f(p-q) = f(\sum p_ib_i - \sum q_ib_i) = f(\sum (p_i-q_i)b_i) = (p_1-q_1, p-q-(p_1-q_1)b_1) = (p_1, p-p_1b_1) - (q_1, q-q_1b_1)= f(p)-f(q)
So the difference between two elements, p and q, gets mapped to the difference vector f(p)-f(q). And it is pretty clear f is one to one since it is invertible. Now I claim that a difference vector of longest length in \mathbb{R}\times\mathbb{R} is only the difference vector for one pair of elements and it is longer than f(1-0) (which is the difference vector that is allowed only exist once).
First to show it is longer than f(1-0) I just need to show that there is a difference vector longer than f(1-0). |f(1-0)|=|(0,1)|=1. Remember that x is in P so we have difference vector
|f(1-x)| = |f(1) -f(x)| = |(0,1)-(1,0)| = |(-1,1)| >1.
Now to show that a difference vector of longest length is only the difference vector for one pair of elements. Take a difference vector of longest length. Say it does appear for another pair of elements. Then you have the same difference vector in two different places on the graph. same vector means same length and same direction, ie parallel. If you connect the end points you get a parallelogram. Well any parallelogram has at least one diagonal that is longer than all of the sides. So you have a new difference vector that is longer so the original wasn't the longest.
So since a difference vector of longest length only occurs once, and that vector isn't f(1-0), then P cannot be paired which is our contradiction.
(note there may be several difference vectors with the longest length in \mathbb{R}\times\mathbb{R} but that does not mean they are the same difference in P. for example
|f( (1+b_1) - (1 +b_2))|= |f(b_1-b_2)| = |(1,-b_2)| = |(1,b_2)| = |f(b_1+b_2)|=|f( (1+b_1) - (1 -b_2))|
but (1+b_1) - (1 +b_2)\ne (1+b_1) - (1 -b_2)
)
Perhaps this problem was a little too hard to post but don't get thrown off by the length of the proof. I'm being much more verbose than necessary since I can't sketch a graph in this medium. Also the arguments used don't use any math that is really too fancy. And the argument may seem hard to come up with but that's just because it is in cleaned up form. The crux of the argument is really finding some measure for the differences such that any pair with the same measure induces a difference with a longer measure. This is a natural thing to do when trying to show things are not paired.
Again I apologize for posting such a silly problem.
Steven
I can't seem to get to sleep and I promised a proof of no finite paired sets with containing an irrational. So I might as well be semi-productive and type one up. There are several proofs but in my mind the following is the slickest.
Assume for contradiction that P is a finite paired set and x\in P where x is irrational. Take B=\{b_0, b_1, \ldots , b_n\} to be a \mathbb{Q}-linearly independent set that spans P and such that b_0=1, b_1=x. In other words if \sum_{i=0}^n q_ib_i = 0 and all the q_i's are rational then all the q_i's equal 0. And the fact that it spans P means for y\in P there exists y_0,\ldots ,y_n \in \mathbb{Q} such that \sum_{i=0}^n y_ib_i =y. For any finite set of reals such a "basis" is always constructible. The important thing to notice is that because of the linear independence of the base the choice of coefficients is unique.
Now you are going to map all the y\in P to \mathbb{R}\times\mathbb{R} where the first coordinate is y_1 and the second is y-y_1b_1. Let's call this map f. For example x gets mapped to f(x) =(1,x-1\times b_1)= (1,x-x) = (1,0) and 1 gets mapped to f(1)=(0,1). In general f(\sum y_ib_i) = (y_1, y-y_1b_1). Notice that for any p,q \in P that p-q is also in the span of B. But more importantly
f(p-q) = f(\sum p_ib_i - \sum q_ib_i) = f(\sum (p_i-q_i)b_i) = (p_1-q_1, p-q-(p_1-q_1)b_1) = (p_1, p-p_1b_1) - (q_1, q-q_1b_1)= f(p)-f(q)
So the difference between two elements, p and q, gets mapped to the difference vector f(p)-f(q). And it is pretty clear f is one to one since it is invertible. Now I claim that a difference vector of longest length in \mathbb{R}\times\mathbb{R} is only the difference vector for one pair of elements and it is longer than f(1-0) (which is the difference vector that is allowed only exist once).
First to show it is longer than f(1-0) I just need to show that there is a difference vector longer than f(1-0). |f(1-0)|=|(0,1)|=1. Remember that x is in P so we have difference vector
|f(1-x)| = |f(1) -f(x)| = |(0,1)-(1,0)| = |(-1,1)| >1.
Now to show that a difference vector of longest length is only the difference vector for one pair of elements. Take a difference vector of longest length. Say it does appear for another pair of elements. Then you have the same difference vector in two different places on the graph. same vector means same length and same direction, ie parallel. If you connect the end points you get a parallelogram. Well any parallelogram has at least one diagonal that is longer than all of the sides. So you have a new difference vector that is longer so the original wasn't the longest.
So since a difference vector of longest length only occurs once, and that vector isn't f(1-0), then P cannot be paired which is our contradiction.
(note there may be several difference vectors with the longest length in \mathbb{R}\times\mathbb{R} but that does not mean they are the same difference in P. for example
|f( (1+b_1) - (1 +b_2))|= |f(b_1-b_2)| = |(1,-b_2)| = |(1,b_2)| = |f(b_1+b_2)|=|f( (1+b_1) - (1 -b_2))|
but (1+b_1) - (1 +b_2)\ne (1+b_1) - (1 -b_2)
)
Perhaps this problem was a little too hard to post but don't get thrown off by the length of the proof. I'm being much more verbose than necessary since I can't sketch a graph in this medium. Also the arguments used don't use any math that is really too fancy. And the argument may seem hard to come up with but that's just because it is in cleaned up form. The crux of the argument is really finding some measure for the differences such that any pair with the same measure induces a difference with a longer measure. This is a natural thing to do when trying to show things are not paired.
Again I apologize for posting such a silly problem.
Steven