82
$\begingroup$

Let there be six irrational numbers. Prove that there exists three irrational numbers among them such that the sum of any two of those irrational numbers is also irrational.

I have tried to prove it in the following way, but I am not sure whether it is watertight or not as I have just started learning graph theory.

Let there be a graph with $6$ vertices. We assign a weight equal to those six irrational numbers to each of the vertices. We join all the vertices with edges and color the edges in the following way:

  • Edge is colored red if the sum of the weights of its end points is irrational.

  • Edge is colored blue if the sum of the weights of its end points is rational.

We know that when we color a $6$-vertex graph with $2$ colors then there must be a monochromatic triangle.

  • If the triangle is red then we are done.

  • If it is blue, then let the irrational numbers be $a$, $b$ and $c$. Therefore $a+b$, $b+c$ and $c+a$ are all rational. Which implies $2(a+b+c)$ and $a+b+c$ is rational. As $a+b$ is rational and hence $c$ is also rational. But this is a contradiction.

Hence, our original statement is proved.

$\endgroup$
26
$\begingroup$

Your proof is OK.

But more easily we can prove more strong and general claim. Assume we have a collection of $n$ irrational numbers. We shall call numbers $a$ and $b$ equivalent if the difference $a-b$ is rational. So we can partition our collection into equivalence classes. We shall call classes $C$ and $C’$ complementary if $c+c’$ is rational for any $c\in C$ and $c’\in C’$. From our partition we can choose such classes which contain in total at least $n/2$ elements and no two complementary classes are chosen. It remains to remark that a sum of any two chosen elements is irrational. In particular, among $5$ irrational numbers we can choose $3$ with all mutual sums are irrational. From the other hand, a collection consisting of $n/2$ numbers $\sqrt{2}$ and $n/2$ numbers $2-\sqrt{2}$ witnesses that the bound $n/2$ is strict.

$\endgroup$
  • 1
    $\begingroup$ Thank you for verifying my proof. Encouraged by your affirmation I have tried to give a different argument for the lower bound you have derived here through a graph theoretic way.See my answer below. $\endgroup$ – Arpon Basu Jul 31 '16 at 15:01
  • $\begingroup$ @ArponBasu Thanks. I’ll read your proof later, because now I’m to tired to read long texts, so I’ll propose to you new and short graph theoretic proof. :-) $\endgroup$ – Alex Ravsky Jul 31 '16 at 15:32
  • $\begingroup$ This answer shows that the problem can be solved without graph theory. I added a kind of meta-answer showing that every graph theory solution is a more complicated version of this solution, because there is no genuine graph structure, only the partition of the vertex set. $\endgroup$ – zyx Jul 31 '16 at 16:46
  • $\begingroup$ @zyx Nevertheless, a graph theory solution which I unexpectedly found a hour ago, is the shortest so far. $\endgroup$ – Alex Ravsky Jul 31 '16 at 17:02
  • 1
    $\begingroup$ I think it becomes longer (or collapses to the same thing) if you write the complete proof that there are no odd cycles. The simplest proof of that is probably to color each vertex by its class in R/Q so that edges are multiplication by (-1). But then you could simplify the proof by starting from a bipartition by R/Q classes and directly writing down a maximum independent set. Which is essentially your first answer! $\endgroup$ – zyx Jul 31 '16 at 17:34
21
$\begingroup$

Even more simple but not elementary proof can be given as follows. The set $\mathbb R$ of reals is a linear space over the field $\Bbb Q$ of rationals. There exists a homomorphism $h:\Bbb R\to \Bbb R$ such that $\ker h=\Bbb Q$ (the image $h(x)$ of the real number $x$ can be easily constructed from a decomposition of $x$ via basis of $\Bbb R$ over $\Bbb Q$ containing $1$). Now, let $K$ be any collection of irrational numbers. Since $h(x)\ne 0$ for any number $x\in K$, there exist a subcollection $K’$ of $K$ of size at least half of size $K$, such that all elements $h(x)$ for $x\in K’$ have the same sign. Now let $x$ an $y$ be any elements of $K’$. Then $h(x+y)=h(x)+h(y)\ne 0$. Thus $x+y\not\in\ker h=\Bbb Q$. Similarly we can show that any sum of elements of $K'$ is irrational.

$\endgroup$
  • 3
    $\begingroup$ beautiful proof $\endgroup$ – Mariah Jul 31 '16 at 15:47
  • 1
    $\begingroup$ Can you please explain more on why that homomorphism exists? $\endgroup$ – Sandeep Silwal Jul 31 '16 at 19:40
  • 2
    $\begingroup$ @SandeepSilwal Just take a homomorphism to R/Q, there is no need for a basis. Q is a normal subgroup because R is abelian, so the quotient exists. For application to this problem, one needs also to prove that R/Q has no 2-torsion which is the same as Q admitting division by 2. $\endgroup$ – zyx Aug 1 '16 at 0:49
  • $\begingroup$ @zyx Here it is essential not only that $h$ is a homomorphism with the kernel $\Bbb Q$, but also that $h(\Bbb R)\setminus\{0\}$ is a union of two disjoint semigroups. This is why I used a basis to construct $h$ such that $ h(\Bbb R)\subset \Bbb R$. $\endgroup$ – Alex Ravsky Aug 1 '16 at 3:35
  • 2
    $\begingroup$ Am I correct in assuming we only need a homomorphism from $\langle K\rangle$ to $\Bbb R$? (This eliminates the need for the axiom of choice, since $\langle K\rangle$ has a finite basis.) -- On a side note, it feels like this "switches around quantifiers": your version uses a single homomorphism that works for every $K$, while this version notes that, for every $K$, we can find a suitable homomorphism. I've noticed this sort of switching of quantifiers happening in other places in mathematics as well. $\endgroup$ – Akiva Weinberger Jul 9 '17 at 11:35
9
$\begingroup$

Theorem: Let $G$ be a group with a normal subgroup $H$. A positive integer $k$ and a sequence $\left(a_i\right)_{i=1}^k$ of elements of $G$ are given. A pair product of the $a_i$'s is an element of the form $a_ia_j$ for $i,j\in\{1,2,\ldots,k\}$ with $i\neq j$. Denote by $\ell$ the cardinality of the set of elements of order $2$ of the factor group $G/H$, and let $p$ and $q$ be positive integers. If $p\geq 3$, $q\geq 2$, $G/H$ has an element of order not equal to $1$ or $2$, and $$k\geq\min\big\{(p-3)\ell+(p+2q-4),pq-p-q+2\big\}\,,\tag{1}$$ or if $q\geq 2$ and all non-identity elements of $G/H$ are of order $2$ and $$k\geq\min\big\{(p-1)\ell+p,pq-p-q+2\big\}\,,\tag{2}$$ then there exists a subsequence of $\left(a_i\right)_{i=1}^k$ of length $p$ with all pair products in $H$ or a subsequence of length $q$ with all pair products not in $H$. In addition, if $p\geq 3$, $q\geq 2$, $a_1,a_2,\ldots,a_k\notin G\setminus H$, and $$k\geq \min\big\{(p-3)\ell+(2q-1),pq-p-q+2\big\}\,,\tag{3}$$ or if all non-identity elements of $G/H$ are of order $2$ and $$k\geq\min\big\{(p-1)\ell+1,pq-p-q+2\big\}\,,\tag{4}$$ then there exists a subsequence of $\left(a_i\right)_{i=1}^k$ of length $p$ with all pair products in $H$ or a subsequence of length $q$ with all pair products not in $H$.

Sharpness: The bounds above are sharp. If $\ell\geq q-1$, then take $g_1,g_2,\ldots,g_{q-1}\notin H$ such that the elements $g_iH\in G/H$ are pairwise distinct and of order $2$. Let $$a_{(p-1)\mu+\nu+1}:=g_{\mu+1}$$ for each $\mu=0,1,2,\ldots,q-2$ and $\nu=0,1,2,\ldots,p-2$. Then, it is easy to see that the sequence $\left(a_1,a_2,\ldots,a_{pq-p-q+1}\right)$ has no desired subsequences.

From now on, we assume that $\ell<q-1$. Then, take $g_1,g_2,\ldots,g_\ell\notin H$ such that the elements $g_iH\in G/H$ are pairwise distinct and of order $2$. If $a_1,a_2,\ldots,a_k\notin H$ is required, then we can take $$a_{(p-1)\mu+\nu+1}:=g_{\mu+1}$$ for all $\mu=0,1,2,\ldots,\ell-1$ and $\nu=0,1,\ldots,p-2$. This shows that (4) is sharp. If $G/H$ has an element $xH$ with $x\in G$ such that $xH$ is non-identity and not of order $2$ in $G/H$, then we can also further add $$a_{(p-1)\ell+2j-1}:=x\text{ and }a_{(p-1)\ell+2j}:=x^{-1}$$ for $j=1,2,\ldots,q-1-\ell$. Ergo, (3) is sharp.

Now, we allow $a_1,a_2,\ldots,a_k$ to be in $H$. Then, we let $a_1,a_2,\ldots,a_{(p-1)\ell}$ be as in the paragraph above. If $G/H$ has no elements of order not equal to $1$ or $2$, then set $$a_{(p-1)\ell+j}:=1_G$$ for $j=1,2,\ldots,p-1$. Thus, (2) is sharp. If $G/H$ has an element $xH$ of order not equal to $1$ or $2$, then we further take $$a_{(p-1)(\ell+1)+2j-1}:=x\text{ and }a_{(p-1)(\ell+1)+2j}:=x^{-1}$$ for $j=1,2,\ldots,q-2-\ell$. Thence, (1) is sharp.

Trivial Cases: If $p=1$ or $q=1$, then we have the obvious bound $k\geq 1$. If $p=2$ and $q\geq 2$, then (1) should be replaced by $k\geq q+1$ and (2) by $k\geq \min\{\ell+2,q\}$, whereas (3) should be replaced by $k\geq q$ and (4) by $k\geq\min\{\ell+1,q\}$. These trivial bounds are clearly sharp.

Proof of the Theorem: Here, we assume that $p\geq 3$ and $q\geq 2$. Let $$u:=\Big|\big\{i\in\{1,2,\ldots,k\}\,|\,a_i\in H\big\}\Big|\,,$$ $$v:=\Big|\big\{i\in\{1,2,\ldots,k\}\,|\,a_i\notin H\text{ and }a_i^2\in H\big\}\Big|\,,$$ and $$w:=k-u-v=\Big|\big\{i\in\{1,2,\ldots,k\}\,|\,a_i^2\notin H\big\}\Big|\,.$$ Suppose that the sequence $a_1,a_2,\ldots,a_k$ has neither a subsequencs of length $p$ with pair products in $H$ nor a subsequence of length $q$ with pair products not in $H$. The proof is done via contrapositivity.
We shall first prove the claim when $a_1,a_2,\ldots,a_k\notin H$ (i.e., when $u=0$). Then, it is clear that $$\left\lceil\frac{v}{p-1}\right\rceil+\left\lceil\frac{w}{2}\right\rceil\leq q-1\text{ and }\left\lceil\frac{v}{p-1}\right\rceil\leq \min\{\ell,q-1\}\,.$$ Consequently, if $t:=\left\lceil\frac{v}{p-1}\right\rceil$, then $w\leq 2(q-1-t)$ and $t\leq \min\{\ell,q-1\}$, so that, if $p\geq 3$, we have $$\begin{align}k&=v+w\leq (p-1)t+2(q-1-t)=(p-3)t+2q-2\\&<\min\big\{(p-3)\ell+(2q-1),pq-p-q+2\big\}\\&\leq \min\big\{(p-3)\ell+(p+2q-4),pq-p-q+2\big\}\,.\end{align}$$ If $G/H$ has no non-identity element of order not equal to $2$, then $w=0$, whence $$\begin{align}k&=v\leq (p-1)t\\&<\min\big\{(p-1)\ell+1,pq-p-q+2\big\}\\&\leq \min\big\{(p-1)\ell+p,pq-p-q+2\big\}\,.\end{align}$$
From now on, we assume that $u> 0$. Then, it is obvious that $u\leq p-1$. Also, we have $$\left\lceil\frac{v}{p-1}\right\rceil+\left\lceil\frac{w}{2}\right\rceil\leq q-2\text{ and }\left\lceil\frac{v}{p-1}\right\rceil\leq \min\{\ell,q-2\}\,,$$ provided that $q\geq 2$. Let $t$ be as defined before. Then, $$\begin{align}k&=u+v+w\leq (p-1)+(p-1)t+2(q-2-t)=(p-3)t+(p+2q-5)\\&<\min\big\{(p-3)\ell+(p+2q-4),pq-p-q+2\big\}\,.\end{align}$$ Finally, if all non-identity elements of $G$ have order $2$, then $w=0$ and $$k=u+v\leq (p-1)+(p-1)t<\min\big\{(p-1)\ell+p,pq-p-q+2\big\}\,.$$

In particular, let $G$ be a group with a proper normal subgroup $H$ such that, for all $g\in G$, $g^2\in H$ implies $g\in H$. For any integer $n\geq 3$ and for a sequence $\left(a_i\right)_{i=1}^k$ of elements in $G$, if $$k\geq 3n-4\,,$$ then either there exists a subsequence of length $n$ such that the product of any two entries is in $H$, or a subsequence of length $n$ such that the product of any two entries is not in $H$. Furthermore, if $a_1,a_2,\ldots,a_k\in G\setminus H$ and $$k\geq 2n-1\,,$$ then there exists a subsequence of length $n$ such that the product of any two terms is not in $H$. Both bounds are sharp.

P.S.: For a fixed integer $d\geq 3$, what would happen if pair products are replaced by $d$-ary products $a_{i_1}a_{i_2}\ldots a_{i_d}$ where $i_1,i_2,\ldots,i_d\in\{1,2,\ldots,k\}$ are pairwise distinct?

$\endgroup$
  • $\begingroup$ In fact you deal with the quotient group $G/H$ which has no elements of order $2$. $\endgroup$ – Alex Ravsky Jul 30 '16 at 19:18
  • $\begingroup$ @ Batominovski Thanks. I am yet to learn Group theory , but surely I will come back here once I learn group theory to understand this proof. $\endgroup$ – Arpon Basu Jul 31 '16 at 15:04
  • $\begingroup$ @zyx Thanks. It was indeed misplaced when I tried to edit the text using an iPad (which was quite tedious). Also, the bound $3n-2$ was incorrect (mis-calculation). $\endgroup$ – Batominovski Jul 31 '16 at 22:02
  • $\begingroup$ Thanks. Very nice analysis. I would be interested to read more about this if you ever have time to add the proofs or a description of the critical cases for the bounds. $\endgroup$ – zyx Aug 1 '16 at 0:44
  • $\begingroup$ Does the same method give the sharp bounds for the more general problem of either a subsequence of length $p$ with all pair products in $H$, or a subsequence of length $q$ with all pair products not in $H$? $\endgroup$ – zyx Aug 2 '16 at 3:55
4
$\begingroup$

Let we have $n$ vertices instead of six and consider only blue edges in the graph. Similarly to the proof from the question, we can show that the graph contains no (blue) cycles of odd length. Hence it (vertex set) is two-colorable. Thus it has an independent set of vertices of size at least $n/2$, and sum of any two numbers from this set is irrational.

$\endgroup$
3
$\begingroup$

I have tried to prove Alex Ravsky's first proof in the following way. Once again I want to emphasize that I am just learning Graph theory and not very confident about the watertightness of my proof.I will appreciate any improvement.

Let $T$ be a graph with $V$ vertices. We divide it into $\left\lfloor\frac{n}{2}\right\rfloor$ subsets such that the number of vertices in each subset is equal or differs from each other by atmost 1 (Turan's condition).Let $r$ be minimum number of vertices in the subsets, thus $r+1$ is the maximum number of vertices.
Therefore $(\left\lfloor\frac{n}{2}\right\rfloor)r \leq V < (\left\lfloor\frac{n}{2}\right\rfloor)(r+1) $
By joining the vertices of different subsets in blue and same subsets in red we form a Turan graph (example of such a set of irrational numbers is given by Alex Ravsky for example $\left\lfloor \frac{n}{2} \right\rfloor \sqrt{2}$ s and $\left\lfloor \frac{n}{2} \right\rfloor 2-\sqrt{2}$ s),and we can conclude by the property of Turan graph that there is no $(\left\lfloor \frac{n}{2} \right\rfloor+1)$ clique in $T$.
Now $r \geq 1$ implying V is greater than or equal to $\left\lfloor \frac{n}{2} \right\rfloor$.
If $V=\left\lfloor\frac{n}{2}\right\rfloor$ then it is obvious that there can be no $(\left\lfloor\frac{n}{2}\right\rfloor+1)$ clique. If $r=2$ then $V \geq (n-1)$.
Thus $T$ is the graph with maximum vertices that contains a $\left\lfloor\frac{n}{2}\right\rfloor$ clique but not a $\left\lfloor\frac{n}{2}\right\rfloor +1$ clique. At the same time $r<3$ because otherwise there will be a monochromatic red triangle within the subsets. Thus putting the possible values of $r$ we get that

$(n-1) \leq V < 3\left\lfloor\frac{n}{2}\right\rfloor => (n-1) \leq V \leq 3\left\lfloor\frac{n}{2}\right\rfloor -1$

For all $V$ satisfying above condition has a strict bound of $\left\lfloor\frac{n}{2}\right\rfloor$ for its maximum sized clique.

$\endgroup$
3
$\begingroup$

It's actually possible to demonstrate that this is NOT a graph-theoretic problem.

The graph-theoretic condition equivalent to having a finite collection of irrational numbers as vertices, and recording (with edges) which pairs have rational sums is

Graph that is a disjoint union of complete bipartite graphs $K_{m,n}$.

The graph has that structure for any finite collection of irrational numbers, and every such finite graph can be realized by some irrational numbers.

All of the binary relation structure of the graph is an encoding of a simpler unary structure, the partition of the vertex set into pairs of subsets (the mod $\mathbb{Q}$ equivalence classes of the numbers, and their negatives). To answer any question about the graph one looks at the partition, not the edges.

A maximum edge-free subset (independent set) in such a graph is a union of the larger half of each partition-pair. The cardinality is $\sum \max(m,n)$ which is always at least $\lceil V/2 \rceil$ if the graph has $V$ vertices.

So the first answer by @AlexRavsky, that used the partition directly without introducing a graph, seems to be the optimal argument.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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