1

I am asked to show that for any $A\subset \mathbf{R}\setminus \{0\}$ with $|A| = n$, there is a subset $B\subset A$ of more than $n/3$ numbers such that no $a_1,a_2,a_3\in B$ satisfy $a_1+a_2=a_3$. I am aware of this question, indeed I managed to prove this part using the probabilistic method. However I have no idea how to extend this property to irrational numbers.

I tried to slightly perturb every $a\in A$ by a tiny number to produce a set of rational for which the result then holds. But then a subset of those rationals that is sum free does not necessarily map back to a set of the irrationals that is sum free.

Maybe we can partition $A$ into sets $A_1,\ldots, A_k$ such that elements in $A_i$ have rational ratios with each other and then.... ?

Any ideas? Thanks!

Update I think we might be able to do it as follows. If $a_i+a_j - a_k\neq 0$ then it exceeds in magnitude some rational number $q_{ijk}$. For $ijk$ such that $a_i+a_j -a_k = 0$, set $q_{ijk} = 0$. Then define the set of conditions on a set $B = \{b_1,\ldots, b_n\}$:

\begin{align} b_i + b_j + b_k = 0 &\iff q_{ijk} = 0,\\ b_i + b_j + b_k \geq q_{ijk} &\iff q_{ijk} \neq 0.\\ \end{align} This is a set of $3^n$ conditions. It seems like a linear programming question without any optimization part. I know little about these kinds of problems but maybe there is some theorem that we may use to show that the above has a solution with rational $b_1,\ldots, b_n$. Then we would be done as $b_i+b_j = b_k$ then implies $a_i + a_j = a_k$.

nonuser
  • 90,026
Slugger
  • 5,556
  • I think actually allowing non-integers and irrationals makes this less restrictive and easier. In proving it for the natural numbers you essentially proved there can not be a set of natural numbers, $A$, that "forces" two numbers to add to a third. Well if a set of natural numbers can't force that than surely a set or real numbers can't either.... I think. – fleablood Jul 18 '19 at 17:11
  • But the natural numbers cant force two numbers $a$, $b$ to exist so that their ratio $a/b = \sqrt{2}$ but the reals can. So this ad-hoc reasoning doesn't really do the trick I think. Allowing the irrationals to join the party clearly gives a lot more freedom for maybe weird sets to exist – Slugger Jul 19 '19 at 12:10
  • Right... But it allows more weird sets to exist. It doesn't prevent sets not to exist. Still, I dont know. I haven't looked too hard. – fleablood Jul 19 '19 at 16:34

1 Answers1

1

The real line $\mathbb{R}$ is a infinite-dimensional $\mathbb{Q}$-vector space. You can let $A=\{\alpha_1, \dotsc, \alpha_n\}$, and $\ell$ be any "rational line" (i.e. $\ell = \{q \cdot r \mid q \in \mathbb{Q} \}$ for some $r \in \mathbb{R}$), and consider $A'$ the set obtained by projecting every $\alpha_i$ in this line. To construct the projection, start with the set $\{ r\}$ and add vectors until it becomes a basis $\mathcal{B}$, similarly to the finite-dimensional case (well, it is not obvious you can do it, since it requires the Axiom of Choice). Define $Pr=r$ and $Pt=0$ for any $t \in \mathcal{B}$ different from $r$. By a famous result from linear algebra (which generalizes to infinite-dimensional spaces) every linear transformation is uniquely determined by its values on the basis, therefore $P$ defined above extends to a unique linear transformation in $\mathbb{R}$ as a $\mathbb{Q}$-vector space. Since this set is isomorphic to the rational number, we can use the result previously prove for rational numbers to conclude there exists a $B'$ such that $\lvert B' \rvert > n/3$ and $B'$ is sum-free. Let $B$ be the pre-image of $B'$ by the projection. If $b \in (B + B) \cap B$, then there exists $b_1$, $b_2 \in B$ such that $b_1 + b_2 = b$. Applying the projection $P$, this means $Pb_1 + Pb_2 = Pb_3$. However $Pb_1$, $Pb_2$, $Pb \in B'$. Contradiction, since this set is sum-free.

Thiago Landim
  • 381
  • Hi thanks a lot for your answer. I am not sure what an infinite dimensional $\mathbb{Q}$--vector space is. Could you elaborate some more? – Slugger Jul 18 '19 at 17:25
  • @Slugger I think it has something to do with Hamel basis, you could google, or see https://en.wikipedia.org/wiki/Basis_(linear_algebra)#Analysis and http://mathworld.wolfram.com/HamelBasis.html Though I have to think what a projection on a rational line would mean. Linear combinations have coefficients that have to be rational numbers only – Mirko Jul 18 '19 at 18:03
  • An infinite dimensional $\mathbb{Q}$-vector space means if you see $\mathbb{R}$ as a vector space and $\mathbb{Q}$ as the field of scalars, then there is no finite set of real numbers generating the whole space. These is a very simple way to prove it. If $\mathbb{R}$ had dimension $n$, then $\mathbb{R} \cong \mathbb{Q}^n $, but this cannot happen since $\mathbb{R}$ is uncountable. – Thiago Landim Jul 18 '19 at 18:29
  • I still do not understand what you mean then by a rational line. Simply $ax$ where $a$ is rational? Or what is $r$ in ${q\cdot r |q\in \mathbb{Q}}$. Sorry for the questions, just trying to disect what you mean :) – Slugger Jul 18 '19 at 18:37
  • $r$ is any real number. The "rational line" is the set composed by the rational multiples of some real number. It might be sometimes denoted by $\mathbb{Q}\cdot r$, as $\mathbb{R}\cdot v$ means a real line in some real vector space and $\mathbb{C} \cdot w$ means a complex line in some complex vector space (what, for us, is more like a plane). – Thiago Landim Jul 18 '19 at 18:39
  • I honestly think this doesn't work, because the projection of a bunch of irrationals to get rationals somehow, probably wont be invertible. So then the projections being sum free does not tell us anything about the original numbers right? If not, please consider expanding your answer a bit – Slugger Jul 18 '19 at 18:55
  • Looking at this again, I think i now understand what you are doing! So we build a basis for $\mathbb{R}$ and a projection that maps to the rationals as you said. But isn't it true then that under this projection, some of the elements in my original set will be mapped to zero, in which case I cannot apply the previous result? – Slugger Sep 03 '19 at 11:36