Graph theoretic proof: For six irrational numbers, there are three among them such that the sum of any two of them is irrational.

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.


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.


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.
(a) If one of the following conditions holds:

  • $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}$$
  • $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$.
(b) If one of the following conditions holds:

  • $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}$$
  • 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?


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.


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.