Let $q$ be a positive integer which is not a perfect cube. Prove that there exists a positive constant $C$ such that for all natural numbers $n$, one has $$\{ nq^{\frac{1}{3}} \} + \{ nq^{\frac{2}{3}} \} \geq Cn^{-\frac{1}{2}}$$where $\{ x \}$ denotes the fractional part of $x$.
Problem
Source: China Mathematical Olympiad 2018 Q3
Tags: number theory, approximation, Inequality, fractional part, diophantine approximation
15.11.2017 19:52
It seems to be a known result (and an interesting generalization) that
This would immediately solve the problem (as it's just a specific case) however it is definite overkill. I don't have any idea how to solve this elementarily though.
15.11.2017 20:59
A somewhat involved but natural solution: Let $x = \lfloor nq^{\frac{1}{3}} \rfloor$ and $y = \lfloor nq^{\frac{2}{3}} \rfloor$. Write \[ qn^3 = x^3 + \alpha, \quad q^2n^3 = y^3 + \beta. \]We need to show, roughly, that $\alpha + \beta \geq cn^{1.5}$. Now comes the key step: write $x^2 = ny + \delta$ with $\delta$ an integer (possibly negative). Then, \[ n^3y^3 = (x^2 - \delta)^3 = x^6 - 3 \delta x^4 + 3 \delta^2 x^2 - \delta^3 = (qn^3 - \alpha)^2 - 3\delta (qn^3 - \alpha) x + 3 \delta^2 x^2 - \delta^3 \]where we substitute in $x^3 = qn^3 - \alpha$. Rearranging, we have \[ n^3 (y^3 - q^2n^3 + 2q\alpha - 3q \delta) = \alpha^2 + 3\delta \alpha x + 3\delta^2 x^2 - \delta^3. \]Assume first that $\lvert \delta \rvert \leq c' n^{0.5}$ for some small constant $c'$. Then, the RHS above is at least $0.75 \delta^2 x^2 - \delta^3 > 0$. But since the LHS above is a multiple of $n^3$, the size of the RHS must be at least $n^3$. That implies $\alpha \geq cn^{1.5}$ for some smaller constant $c$. If instead $\lvert \delta \rvert > c' n^{0.5}$, we have \[ \beta n^3 = q^2n^6 - (ny)^3 = (x^3 + \alpha)^2 - (x^2 - \delta)^3. \]That is, \[ \beta n^3 - 2\alpha x^3 - \alpha^2 = x^6 - (x^2 - \delta)^3. \]The absolute value of the RHS is at least $c' n^{4.5}$, and so the LHS must be as large. This again implies $\max\{\alpha, \beta\} > cn^{1.5}$.
16.11.2017 15:57
Nice problem
16.11.2017 16:09
2017 CMO question 3
24.11.2017 10:31
This result can be generalised to $q^{1/n}$ using a similar method, but I wonder how the proof goes for general $\alpha$ algebraic with degree $n$.
05.12.2017 22:03
I love this question
13.01.2018 10:33
CactusYang wrote: A solution by a contestant of CMO 2017.
03.08.2018 18:13
@CeuAzul Where you get Fu's solve?
04.11.2020 23:44
Solved with nukelauncher. Let \(A=\left\lfloor nq^{1/3}\right\rfloor\), \(B=\left\lfloor nq^{2/3}\right\rfloor\). Observe since \(nq\ge Aq^{2/3}\) and \(nq\ge Bq^{1/3}\) that \[\left(nq-Aq^{2/3}\right)^2+\left(nq-Bq^{1/3}\right)^2\ge\left(Aq^{2/3}-Bq^{1/3}\right).\] It follows that \begin{align*} \left(2nq-Aq^{2/3}-Bq^{1/3}\right)^2 &\ge\left(nq-Aq^{2/3}\right)^2+\left(nq-Bq^{1/3}\right)^2\\ &\ge\frac12\left[\left(nq-Aq^{2/3}\right)^2+\left(nq-Bq^{2/3}\right)^2+\left(Aq^{2/3}-Bq^{1/3}\right)^2\right] \end{align*}By \(x^3+y^3+z^3-3xyz=(x+y+z)\left(\frac12[(x-y)^2+(y-z)^2+(z-x)^2]\right)\), \begin{align*}&=\frac{A^3q^2+B^3q+n^3q^3-3ABnq^2}{Aq^{2/3}+Bq^{1/3}+nq}\\ &\ge\frac1{3n}\end{align*}since the numerator is a positive integer multiple of \(q\) and the denominator is at most \(nq+nq+nq\). Finally, \begin{align*} \left\{nq^{1/3}\right\}+\left\{nq^{2/3}\right\}&=\frac{nq-Aq^{2/3}}{q^{2/3}}+\frac{nq-Bq^{1/3}}{q^{1/3}}\\ &>\frac{2nq-Aq^{2/3}-Bq^{1/3}}{q^{2/3}}\ge\frac1{3^{1/2}q^{2/3}\sqrt n}, \end{align*}as desired.
01.07.2021 17:05
Let's try to prove the general version, that is given a real algebraic field of degree $n+1$, and linearly independent elements $1,\theta_1,\ldots,\theta_n$, then there exists a constant $C > 0$ such that $\max ||m \theta_i || \geq Cm^{-1/n}$ for any integer $m$ where $|| \cdot ||$ is the distance to the nearest integer. The main idea is that there is a link between finding $m$ such that $\max ||m \theta_i || \leq Cm^{-1/n}$ and finding $c_i$'s such that $||c_1 \theta_1 + \cdots + c_n \theta_n|| \leq D \max |c_i|^{-n}$. For the second expression, it is easy to show the existence of $D$ such that there are no integer solutions. Indeed it is equivalent to having $|c_0 + c_1\theta_1 + \cdots + c_n \theta_n| \leq D \max|c_i|^{-n}$. Now we can scale to assume $\theta_i$ are algebraic integers, and then multiplying over its conjugates multiplies by at most $O(\max |c_i|^n)$. Hence if we choose $D$ small enough, the RHS would be $< 1$ but the LHS is a non-zero integer so is at least $1$ which is a contradiction. Now assume that for any $C > 0$, we can find $m$ such that $||m \theta_i|| \leq Cm^{-1/n}$. We will show the existence of $c_i$'s such that $||\sum c_i \theta_i|| \leq D \max|c_i|^{-n}$ for any $D> 0$. We will be using Minkowski's theorem on linear forms. We can find integers $y_i$ such that $|m \theta_i + y_i| < Cm^{-1/n}$ and by scaling $\theta_i$, we may assume that $|y_i| \leq m$. Consider the $n+1$ linear forms in the variables $u_1,\ldots,u_n,v_1$ given by $$L_1 = \sum_{i=1}^{n} (m \theta_i + y_i)u_i - x_1(v_1 + \sum u_i \theta_i ), L_2 = u_2, \ldots, L_n = u_n, L_{n+1} = v_1 + \sum u_i \theta_i.$$WLOG lets assume that $|m \theta_1 + y_1|$ is maximal over all $i$. The determinant of this system is simply $|m \theta_1 + y_1| \leq Cm^{-1/n}$. Hence by Minkowski, we can find integers $u_1,\ldots,u_n,v_1$ such that $$|L_1| < 1, |L_2|,\ldots,|L_n| \leq m^{1/n}, |L_{n+1}| \leq Cm^{-1}.$$Hence we have $u_2,\ldots,u_n $ with size $m^{1/n}$ but $|\sum c_i u_i| \leq Cm^{-1}$ which is what we want. It suffices to show $u_1$ has size $O(m^{1/n})$ too and this follows from $|L_1| < 1$. Observe that $L_1$ is actually an integer and so we must have $L_1 = 0$. Then as $m\theta_1 + y_1$ was chosen as maximal, it would follow that $u_1$ has size $m^{1/n}$ too.
16.10.2021 05:06
Assume for contradiction there is a bad $n$. Define the integers \begin{align*} A &= nq^{1/3} - \delta \\ B &= nq^{2/3} - \varepsilon \end{align*}for small $\delta$ and $\varepsilon$ in $(0, Cn^{-1/2})$. First, note that we have \begin{align*} {\mathbb Z} \ni A^3 - n^3q &= {\color{red} - 3n^2q^{2/3} \delta} + 3nq^{1/3} \delta^2 - \delta^3 \\ {\mathbb Z} \ni B^3 - n^3q^2 &= {\color{red} - 3n^2q^{4/3} \varepsilon} + 3nq^{2/3} \varepsilon^2 - \varepsilon^3 \\ {\mathbb Z} \ni AB - n^2q &= {\color{red}-n q^{2/3} \delta - n q^{1/3} \varepsilon} + \delta \varepsilon. \\ \end{align*}(For clarity, we highlighted in red terms which are bigger than $O(1)$.) Now we define two integers $X$ and $Y$ such that \begin{align*} X &= (A^3-n^3q) - 3n(AB-n^2q) \\ &= 3nq^{1/3} \delta^2 - \delta^3 + {\color{red} 3n^2 q^{1/3} \varepsilon} - 3n \delta \varepsilon. \\ Y &= qX + (B^3-n^3q) \\ &= 3nq^{4/3} \delta^2 - q \delta^3 - 3nq\delta\varepsilon + 3nq^{2/3} \varepsilon^2 - \varepsilon^3 \\ &= 3n \left( q^{4/3} \delta^2 - q\delta\varepsilon + q^{2/3}\varepsilon^2 \right) - \varepsilon^3 - q \delta^3. \end{align*}Because $\delta$ and $\varepsilon$ are $O(n^{-1/2})$, it is evident that $Y < 1$ for sufficiently large $n$. However, we contend $Y > 0$ for sufficiently large $n$ as well: \begin{align*} Y &= 3n \left( q^{4/3} \delta^2 - q\delta\varepsilon + q^{2/3}\varepsilon^2 \right) - \varepsilon^3 - q \delta^3. \\ &\overset{\text{AMGM}}{\ge} \frac32 n (q^{4/3} \delta^2 + q^{2/3} \varepsilon^2) - \varepsilon^3 - q \delta^3 \\ &= \delta^2\left( \frac 32 n q^{4/3} - q \delta \right) + \varepsilon^2 \left( \frac 32 n q^{2/3} - \varepsilon \right) \end{align*}which is positive for large $n$.
16.10.2021 07:26
I'm not sure. But someone told me that UNKNOWN wrote: if \(q\in\mathbb{N_+}\) and \(\sqrt[r]{q}\not\in\mathbb{N_+}\) (\(r\in{\mathbb{N_+}\mathop{\mspace{-1.75mu}\setminus\mspace{-1.25mu}}\left\{1\right\}}\)), then \[\left\{q^{\frac1r}n\right\}+\left\{q^{\frac2r}n\right\}+\dotsb+\left\{q^{1-\frac1r}n\right\}\overset{?}{\geqslant}\frac1{r^{\frac1{r-1}}q^{\frac{r-1}r}}n^{\frac1{1-r}}\textit{,}\quad\forall{n\in\mathbb{N_+}}\textnormal{.}\]
16.10.2021 08:20
Interesting
02.01.2022 05:12
Let $A = \lfloor nq^{\frac{1}{3}} \rfloor$ and $B = \lfloor nq^{\frac{2}{3}} \rfloor.$ We have that \begin{align*} \{ nq^{\frac{1}{3}} \} + \{ nq^{\frac{2}{3}} \} &= \frac{nq-Aq^{2/3}}{q^{2/3}}+\frac{nq-Bq^{1/3}}{q^{1/3}} \\ &= \frac{nq+nq^{4/3}-Aq^{2/3}-Bq^{2/3}}{q^{2/3}} \\ &> \frac{2nq-Aq^{2/3}-Bq^{1/3}}{q^{2/3}}, \\ \end{align*}noting that $nq^{4/3} - Bq^{2/3} > nq^{3/3} - Bq^{1/3}.$ It suffices to find a constant $C$ where $$2nq-Aq^{2/3}-Bq^{1/3} \ge \frac{C}{\sqrt{n}}.$$From there, note \begin{align*} (2nq-Aq^{2/3}-Bq^{1/3})^2 &> (nq - Aq^{2/3})^2 + (nq-Bq^{1/3})^2 \\ &> \frac{1}{2} \left( (nq - Aq^{2/3})^2 + (nq-Bq^{1/3})^2+(Aq^{2/3}-Bq^{1/3})^2 \right) \\ \end{align*}noting that $(x+y)^2 > x^2+y^2 > \frac{1}{2} (x^2+y^2+(x-y)^2)$ for positive $x,y$ since $nq > Aq^{2/3}, Bq^{1/3}.$ Then \begin{align*} \frac{1}{2} \left( (nq - Aq^{2/3})^2 + (nq-Bq^{1/3})^2+(Aq^{2/3}-Bq^{1/3})^2 \right) &= \frac{(nq)^3 + A^3q^2 + B^3q-3ABnq^2}{Aq^{2/3}+Bq^{1/3}+nq}\\ &> \frac{(nq)^3 + A^3q^2 + B^3q-3ABnq^2}{3nq} \\ &\ge \frac{1}{3n}\\ \end{align*}which is a lower bound for $2nq-Aq^{2/3}-Bq^{1/3}$ as desired, noting that $(nq)^3 + A^3q^2 + B^3q-3ABnq^2$ is an integer multiple of $q$ and is also positive by the AM-GM inequality. $\square$