Let $M$ be a subset of $\mathbb{R}$ such that the following conditions are satisfied: a) For any $x \in M, n \in \mathbb{Z}$, one has that $x+n \in \mathbb{M}$. b) For any $x \in M$, one has that $-x \in M$. c) Both $M$ and $\mathbb{R}$ \ $M$ contain an interval of length larger than $0$. For any real $x$, let $M(x) = \{ n \in \mathbb{Z}^{+} | nx \in M \}$. Show that if $\alpha,\beta$ are reals such that $M(\alpha) = M(\beta)$, then we must have one of $\alpha + \beta$ and $\alpha - \beta$ to be rational.
Problem
Source: China TSTST 2017 Test 2 Day 2 Q6
Tags: algebra, combinatorics, number theory
13.03.2017 16:04
The problem is actually about the "dimension" of $\{1,\alpha,\beta\}$ over $\mathbb{Z}$. We'll see why in a moment. We start of with a better way to interpret the problem conditions. Let's look at set $A$ formed by points of the form $(\{n\alpha\},\{n\beta\})$ for all $n\in \mathbb{Z}^+$. What "shape" does $A$ form? If we imagine $n$ to be continuous, then the answer is either: a) $A$ is dense on the entire square $[0,1)^2$ or b) $A$ is the union of some line segments (formed by taking a line mod 1). In the same way that we expect $\{na\}$ to be dense mod 1, perhaps if $n$ was discrete the answer is somewhat the same (except dottier). Now let's overlay this with our condition of $M(\alpha)=M(\beta)$. Consider the region $B$ formed by points of the form $(x,y)$, where both $0\le x,y<1$ are both in $M$ or both not in $M$. It's not difficult to visualise what $B$ looks like: it's a "checkerboard" pattern, symmetric (well almost) about $x=\frac{1}{2}$ and $y=\frac{1}{2}$. The most important thing about this is that $B$ has many square regions. Putting $A$ and $B$ together, the problem seems almost obvious. Since $A\subseteq B$, then if $A$ was dense on the square, immediately done. If $A$ was a "broken line" of gradient $\neq 1$, then it would intersect a square and cross-over into non-$B$ regions, and that would only happen when $\alpha-\beta$ is an integer. Wait a sec, what about all those other cases? It turns out the gradient of the line isn't always $\frac{\beta}{\alpha}$ as our heuristic would have led us to believe, and the problem is a little bit more difficult than this. The next step would be to open up our square into $\mathbb{R}^2$, and to consider the behaviour of the vectors $(1,0),(0,1),(\alpha,\beta)$, but I'll leave y'all to think about it.
19.07.2020 15:10
$\mathfrak{BUMP}$ Bump
17.06.2021 11:24
Anybody got the solution to this ?
14.01.2022 01:02
Hard problem. Lemma 1: for any irrational reals $a_1,a_2, \dots , a_k$ there exists an integer $n$ where $na_1,na_2, \dots na_k$ are all within an arbitrarily small distance $\epsilon$ away from an integer. Proof: Take a large positive integer $L.$ Divide $(0,1)$ into $L$ intervals $\left(0,\frac{1}{L} \right), \left(\frac{1}{L},\frac{2}{L} \right), \dots , \left(\frac{L-1}{L},1 \right),$ by PHP there are $n_1, n_2$ where $\{n_1a_i \}$ belongs to the same interval as $\{n_2a_{i}\}$ for all $i.$ Then just take $n = n_1-n_2.$ $\square$ Lemma 2: for any irrational real $a$ and a closed interval $\in(0,1)$, there exists an integer $n$ where $\{na\}$ is within that closed interval. Proof: By Lemma 1 there is an integer $n_1$ where $n_1a$ is within an arbitrarily small distance $\epsilon$ away from an integer. For small enough $\epsilon,$ one of $n_1a,2n_1a, 3n_1a, \dots$ can fit in the interval. $\square$ If $\alpha$ is a rational number $\frac{p}{q}$ then for any integer $n, n\alpha \in M$ iff $(n+q)\alpha \in M.$ If $q\beta$ is irrational, then there must be a $nq\beta$ inside any closed interval by Lemma 2, and there is a closed interval in both $M$ and $\mathbb{R} \setminus M,$ contradiction. From now on assume $\alpha, \beta \notin \mathbb{Q}.$ Given real numbers $\alpha$ and $\beta,$ adding a rational number to one of them or multiplying them both by the same rational number doesn't change whether one of $\alpha + \beta, \alpha - \beta$ is rational. This allows us to make simplifications: If $M(\alpha) = M(\beta),$ we have $M(\{\alpha\}) = M(\{\beta\}),$ and $M(N\alpha) = M(N\beta)$ for any integer $N.$ It follows from Lemma 1, that we can assume $\alpha, \beta$ are in $(0, \epsilon)$ or $(1- \epsilon, 1)$ for an arbitrarily small positive real $\epsilon.$ Note also that $M(\alpha) = M(-\alpha),$ and similarly for $\beta.$ So WLOG $\alpha,\beta \in (0, \epsilon).$ We claim $\alpha = \beta$ or we have contradiction. Suppose $\alpha \ne \beta.$ Let $(a,b)$ and $(c,d)$ be closed intervals in $M$ and $\mathbb{R} \setminus M$ respectively, where $0 < a,b,c,d < 1.$ Case 1: $\alpha = ps, \beta = qs$ for distinct positive integers $p,q$ and irrational $s.$ Assume WLOG $p>q.$ Take a large positive integer $t.$ There exists an integer $n$ where $\{ns\} \in \left(0, \frac{\epsilon}{(pq)^t} \right).$ So $$M(q\{ns\}) = M(\{qns\})= M(n\{qs\}) = M(n\{ps\}) = M(\{pns\}) = M(p\{ns\}),$$implying $M(q^{t}\{ns\}) = M(q^{t-1}p\{ns\}) = \dots = M(q^{1}p^{t-1}\{ns\}) = M(p^{t}\{ns\}).$ For large enough $t,$ there is an integer $m$ where $$\left(\frac{p}{q}\right)^t a < m + c < m+d < \left(\frac{p}{q}\right)^t b.$$As $t$ gets large $p^t\{ns\}$ gets arbitrarily small. So there is an integer $l$ where $m+c < lp^{t}\{ns\}< m+d.$ So $l \not\in M(p^{t}\{ns\}).$ But $$a < \left(\frac{q}{p}\right)^t \left(m+c \right) <q^{t}\{ns\} < \left(\frac{q}{p}\right)^t \left(m+d \right) < b$$so $l \in M(q^{t}\{ns\}),$ contradiction. Case 2: $\frac{\alpha}{\beta} = s$ for an irrational $s.$ Let $x$ and $y$ be arbitrary reals in $(a,b)$ and $(c,d)$ respectively. Take an integer $n$ where $|\{ns\} - \{x-ys\}| < \epsilon,$ so there is an integer $m$ where $|m-ns+x-ys| < \epsilon.$ Define \begin{align*} f(z) &= (m+x-\alpha z)^2 + (n+y-\beta z)^2 \\ &= (\alpha^2+\beta^2)z^2 -2(\alpha(m+x)+\beta(n+y))z+(m+x)^2+(n+y)^2.\\ \end{align*}Taking $z = \frac{\alpha(m+x)+\beta(n+y)}{\alpha^2+\beta^2}$ yields \begin{align*} f(z) &= (m+x)^2+(n+y)^2 - \frac{\left(\alpha(m+x)+\beta(n+y)\right)^2}{\alpha^2+\beta^2}\\ &= \frac{\left(\beta(m+x)-\alpha(n+y)\right)^2}{\alpha^2+\beta^2}\\ &= \frac{\left(\beta m+\beta x- \beta sn- \beta sy\right)^2}{\alpha^2+\beta^2}\\ &= \frac{\beta^2}{\alpha^2+\beta^2} \times (m-ns+x-ys)^2 < \epsilon^2 \end{align*}so $|m+x-\alpha z|, |n+y-\beta z| < \epsilon.$ Let $z'$ be the integer closest to $z.$ Since $\alpha, \beta \in (0, \epsilon),$ for arbitrarily small choices of $\epsilon$ we see $\{z' \alpha\}$ gets arbitrarily close to $x$ but $\{z' \alpha\}$ gets arbitrarily close to $y,$ contradiction.
06.06.2022 01:29
After doing China TST 2022 Test 3 Problem 2, this feels like a piece of cake because these two problems use almost the exact same approaches. The case where $\alpha\in \mathbb{Q}$ is very easy; just note $M$ is periodic which forces $\beta \in \mathbb{Q}$. From now on, assume $\alpha \notin \mathbb{Q}$ Claim: [Kronecker's Theorem]. If $\alpha, \beta, 1$ are linearly independent over $\mathbb{Z}$, then for any $[l_1,r_1], [l_2,r_2] \subseteq [0,1)$, there exists $n$ such that $\{na\}\in [l_1,r_1], \{nb\} \in [l_2,r_2]$ To prove this claim, we first prove a lemma. Lemma: For any $\epsilon > 0$, there exists $n$ such that $||n\alpha||, ||n\beta||<\epsilon$ Proof: Since $\epsilon>0$, there exists an integer $m$ such that $\epsilon > \frac 1m$. Divide $[0,1) \times [0,1)$ into $[\frac am, \frac{a+1}{m}) \times [\frac bm, \frac{b+1}{m}]$ where $0\le a,b<m$. Place points $(\{n\alpha\}, \{n\beta\})$. There are $m^2$ regions, so if there are sufficiently many points, two points will be in the same region, call $(\{x\alpha\}, \{x\beta\})$ and $(\{y\alpha\}, \{y\beta\})$. Then $x-y$ works. Pick $\epsilon < \frac{r_1-l_1}{1000}, \frac{r_2-l_2}{1000}, n$ st $||n\alpha||, ||n\beta||<\epsilon$. WLOG, $\{n\alpha\}, \{n\beta\} < \epsilon$, for the other cases are similar. Let $x=\{n\alpha\}$ and $y=\{n\beta\}$. Pick $k=\lceil \frac{A+l_1}{x} \rceil$, where $A$ is an integer to be determined later. Then $A+l_1 < kx < A+l_1+x$, so $\{kx\} \in (l_1,l_1+x)$. Also, $A\frac yx + \frac{l_1y}{x} < ky < A\frac yx + \frac{l_1y}{x}+y$. Since $\frac yx \notin \mathbb{Q}$, it follows that $\{A\frac yx\}$ is dense in $(0,1)$, so we can choose $k$ such that $\{ky\} \in [l_2,r_2]$. $nk$ satisfies the original criteria. Going back to the problem, if $\alpha, \beta, 1$ aren't linearly dependent over $\mathbb{Z}$, by the problem conditions, there exists $[l_1,r_1] \in M\cap [0,1)$ and $[l_2,r_2] \in (\mathbb{R} \backslash M) \cap [0,1)$. There exists $n$ such that $\{n\alpha\} \in [l_1,r_1] \subseteq M$ and $\{n\beta\} \in [l_2,r_2] \subseteq \mathbb{R}\backslash M$, which means $n\in M(\alpha) \backslash M(\beta)$. Therefore, there exists integers $m,n,k$ such that $m\alpha+n\beta=k$. Notice $M(\alpha)=M(\beta) \leftrightarrow M(m\alpha)=M(m\beta)$ since $x\in M(m\alpha) \leftrightarrow mx\alpha \in M \leftrightarrow xm\in M(\alpha)$. Thus, $M(m\beta) = M(m\alpha)= M(k-n\beta)=M(-n\beta)$. By condition b), $M(-n\beta)=M(n\beta)$, so WLOG $m,n,\beta >0$ and $\gcd(m,n)=1$ (otherwise we work with $m',n', \beta'$ where $m'=\frac{m}{\gcd(m,n)}, n'=\frac{n}{\gcd(m,n)}$ and $\beta'=\beta \gcd(m,n)$. WLOG $m<n$, then we will show there exists $\{m\beta\} \in M, \{n\beta\} \in [l_2,r_2]$ for any interval $[l_2,r_2]$. If $[l_1,r_1]\in M$ and $\{m\beta\} \in [l_1,r_1], \{n\beta\} \in M$. We consider $m\beta (\bmod\; m^t)$ instead for a finite but very large integer $t$. We know $M(m^t\beta)=M(m^{t-1}n\beta) = \cdots= M(mn^{t-1}\beta)=M(n^t\beta)$. Select $t$ such that $(r_1-m_1) (\frac nm)^t > 1$. Since $\{k\beta\}$ is dense in $[\frac{l_1}{m^t}, \frac{r_1}{m^t}]$, while $\{k\beta\} \in [\frac{l_1}{m^t}, \frac{r_1}{m^t}]$, $\{n^tk\beta\}$ is dense in $[0,1]$ because $(r_1-m_1) (\frac nm)^t > 1$. Therefore, there exists $k$ such that $\{n^tk\beta\} \in [l_2,r_2]$ and $\{m^tk\beta\} \in [l_1,r_1]$, so $M(m^t\beta) \ne M(n^t\beta)$ if $\beta\notin \mathbb{Q}$ and $m<n$. The end.