# show that $\{ nq^{\frac{1}{3}} \} + \{ nq^{\frac{2}{3}} \} \geq Cn^{-\frac{1}{2}}$

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$

We prove a somewhat stronger result where the fractional part $\{ x \}$ is replaced by the distance from $x$ to the nearest integer, call it $\|x\|$. Since $\|x\| \leq \{ x \}$ for all $x$, an inequality $\|n q^{1/3}\| + \|nq^{2/3}\| \geq C n^{-1/2}$ will imply the desired $\{n q^{1/3}\} + \{nq^{2/3}\} \geq C n^{-1/2}$.

We shall need the following estimate:

Lemma 1: There exists a constant $c>0$ such that $$|a_0 + a_1 q^{1/3} + a_2 q^{2/3}| \geq c / A^2$$ for all nonzero $(a_0,a_1,a_2) \in {\bf Z}^3$, where $A = |a_0| + |a_1| + |a_2|.$

(Explicitly we may take $c = q^{-4/3}$.)

Proof: Consider $$N := \prod_{r^3 = q} (a_0 + a_1 r + a_2 r^2) = a_0^3 + q a_1^3 + q^2 a_2^3 - 3 q a_0 a_1 a_2,$$ the product taken over the three complex cube roots $r$ of $q$. The factor for $r = q^{1/3}$ is $a_0 + a_1 q^{1/3} + a_2 q^{2/3}$. Because $q$ is a not cube and $(a_0,a_1,a_2) \neq (0,0,0)$, the integer $N$ must be nonzero: else one of the factors $a_0 + a_1 r + a_2 r^2$ would vanish, which is not possible because the polynomial $X^3-q$ is irreducible. Hence $|N| \geq 1$. Each of the complex factors has absolute value at most $|a_0| + q^{1/3} |a_1| + q^{2/3} |a_2| \leq q^{2/3} A$ (using $1 \leq q^{1/3} \leq q^{2/3}$). Therefore $|a_0 + a_1 q^{1/3} + a_2 q^{2/3}| \geq (q^{2/3} A)^{-2}$, QED.

Now suppose $n$ is any positive integer, and let $m_1,m_2$ be the integers nearest $nq^{1/3}$ and $nq^{2/3}$ respectively, so that $\| n q^{1/3} \| = |m_1 - n q^{1/3}|$ and $\| n q^{2/3} \| = |m_2 - n q^{2/3}|$. Let $a_0, a_1, a_2$ be any integers, not all zero, such that $n a_0 + m_1 a_1 + m_2 a_2 = 0$; and set $A = |a_0| + |a_1| + |a_2|$. Then $$0 = n a_0 + m_1 a_1 + m_2 a_2 = n (a_0 + a_1 q^{1/3} + a_2 q^{2/3}) + a_1 (m_1 - n q^{1/3}) + a_2 (m_2 - n q^{2/3}).$$ Then the first term has absolute value at least $cn/A^2$ by Lemma 1. Thus $$cn / A^2 \leq |a_1| |m_1 - n q^{1/3}| + |a_2| |m_2 - n q^{2/3}| \leq A ( \| n q^{1/3} \| + \| n q^{2/3} \|),$$ whence $\| n q^{1/3} \| + \| n q^{2/3} \| \geq cn / A^3$.

This will prove a lower bound of the desired form $C / n^{1/2}$ provided we can show that the $|a_i|$, and thus also $A$, can be bounded above by some multiple of $n^{1/2}$. This follows by taking $n = m_0$ in the following estimate, which is a special case of Siegel's Lemma on small solutions of underdetermined linear systems.

Lemma 2: Let $m_0, m_1, m_2$ be integers, not all zero. Then there exist integers $a_0, a_1, a_2$, not all zero, such that $a_0 m_0 + a_1 m_1 + a_2 m_2 = 0$ and each $|a_i| \leq (|m_0|+|m_1|+|m_2|)^{1/2}$.

Proof: we may assume without loss of generality that each $m_i \geq 0$ (by changing some $a_i, m_i$ to $-a_i, -m_i$ if necessary). Let $H = \lfloor (m_0+m_1+m_2)^{1/2} \rfloor$, which is positive because $(m_0,m_1,m_2) \neq (0,0,0)$. There are $(H+1)^3$ triples $(\alpha_0,\alpha_1,\alpha_2)$ with $0 \leq \alpha_i \leq H$ for each $i=0,1,2$. Each yields a nonnegative integer $\alpha_0 m_0 + \alpha_1 m_1 + \alpha_2 m_2 \leq (m_0+m_1+m_2)H < (H+1)^2 H$. Thus $\alpha_0 m_0 + \alpha_1 m_1 + \alpha_2 m_2$ assumes at most $(H+1)^2 H$ distinct values; because $(H+1)^3 > (H+1)^2 H$, there must be two triples, say $(\alpha_0,\alpha_1,\alpha_2)$ and $(\alpha'_0,\alpha'_1,\alpha'_2)$, that yield the same value: $$\alpha_0 m_0 + \alpha_1 m_1 + \alpha_2 m_2 = \alpha'_0 m_0^\phantom{.} + \alpha'_1 m_1^\phantom{.} + \alpha'_2 m_2^\phantom{.}.$$ Setting $a_i = \alpha_i - \alpha_i'$ for each $i=0,1,2$, we therefore obtain a nonzero solution of $a_0 m_0 + a_1 m_1 + a_2 m_2 = 0$ with each $|a_i| \leq H$, QED.

The argument applies more generally to prove the same bound $\|n r\| + \|n r^2\| \geq C n^{-1/2}$ (possibly with a different constant $C$) for any cubic irrationality $r$; more generally yet, $\sum_{i=1}^k \|n r^i\| \geq C_r n^{-1/k}$ for any irrational $r$ of degree $k+1$. The bounds are sharp (up to changing the constant $C_r$), as can be seen by the same kind of pigeonhole argument that we used to prove Lemma 2.

P.S. I see that Phil. Z already gave an AoPS link (in a comment to a now-deleted answer) to the source of the problem in this year's China National Olympiad; one of the comments there (by "talkon") gives a reference to page 79 of Cassels' Introduction to Diophantine Approximation for the general result. P.P.S. I tried to compute small values of $n^{1/2} \|n q^{1/3}\| + \|nq^{2/3}\|$ for $q=2$ (which is the smallest $q$ possible given that $q^{1/3} \notin \bf Z$), first by exhaustive search up to $10^9$ and then using lattice reduction in ${\bf R}^3$ to go well beyond that. There was no evident pattern, but the OEIS recognized a few of the large values of $n$ as terms in the sequence (A108368) of coefficients, call them $c_k$, of the generating function $$\sum_{k=0}^\infty c_k x^k = \frac{x}{1-3x-3x^2-x^3} = \frac1{2-(1+x)^3}.$$ In retrospect this makes sense because $c_k$ is also the $2^{2/3}$ coefficient of the $k$-th power of the fundamental unit $(2^{1/3} - 1)^{-1} = 1 + 2^{1/3} + 2^{2/3}$ of ${\bf Z}[2^{1/3}]$. Curiously this sequence first appeared in a rather different context (though still tenuously related): as Dickson reports on p.562 of History of the Theory of Numbers, Vol. II: Diophantine Analysis:

Solution of $2(x^3+z^3)=y^3+t^3$

R. Amsler$^{106}$ noted the solutions $x = u_{n+1}, \; z = v_n, \; y = u_n + u_{n+1}, \; t = v_n + v_{n+1}$, where $u_n$ and $v_n$ are the $n$th coefficients of the developments of $$(1-3x-3x^2-x^3)^{-1}, \qquad (1+3x+3x^2-x^3)^{-1}.$$

Footnote 106 is "Nouv. Ann. Math., (4), 7, 1907, 335. Proof by L. Chanay, (4), 16, 1916, 282-5; same in Sphinx-Oedipe, 9, 1914, 93-4."

For example, taking $n=8$ we have $(u_n, u_{n+1}, v_n, v_{n+1}) = (38781, 149203, -279, 217)$, and indeed $2(149203^3 - 279^3) = 187984^3 - 62^3$; also $38781^{1/2} \bigl(\|2^{1/3} 38781 \| + \| 2^{2/3} 38781\|\bigr) < 0.386061$.

• It's very very nice!+1,and I want to known this more generally have elementary number theory methods to solve it? – function sug Nov 24 '17 at 3:37
• You're welcome. The solution I gave is elementary, though its generalizations may require some more background in abstract algebra than can be assumed in an "Olympiad" for high school students. Lemma 1 can be made a bit more elementary by letting $p$ be a prime that divides $q$ to a power $3k+1$ or $3k+2$, and checking that for any nonzero choice of $(a_0,a_1,a_2)$ exactly one of the terms $a_0^3, q a_1^3, q^2 a_2^3, -3 q a_0 a_1 a_2$ in $N$ has minimal valuation (exponent) at $p$, so $N \neq 0$. But that relies on knowing the specific and somewhat exotic form for $N$. – Noam D. Elkies Nov 24 '17 at 4:40
• Nice proof, I read it entirely and would like to suggest small improvements in the places I asked myself "why ?". First a typo, in Lemma 1, line $cn/A^2\le ...$ there should be $|a_1|,|a_2|$ instead of $a_1,a_2$. Then still in lemma 1, would not it be simple to say that if $q=p^3$ then $a_0=0,a_1=p,a_2=-1$ would annulate one of the factor, instead of making it implicit ? In addition by the time I figured that out, I had forgotten that $N$ was a non-zero integer and "Hence $|N|\ge 1$" seemed to appear out of nowhere. This property is also used in showing $H\ge 1$ in a more subtle way. – zwim Nov 24 '17 at 12:30
• Finally you used implicitely $q\ge 1\implies 1,q^{\frac 13}\le q^{\frac 23}$ first in bound $q^{\frac 23}A$ in lemma 1 but also in unwritten the conclusion after lemma 2 which would gain to be explicited: $A\le 3H\le 3(n+|m_1|+|m_2|)^{\frac 12}\le 3n^{\frac 12}(1+q^{\frac 13}+1+q^{\frac 23}+1)^\frac 12\le 3n^{\frac 12}(5q^{\frac 23})^{\frac 12}$. Nevertheless, except these minor obscure points, it was easy to follow. – zwim Nov 24 '17 at 12:30
• Pretty impressive. Elementary and non-elementary are relative in mathematics. There was a time when the irrational nature of $\sqrt2$ was non-elementary. – Piquito Nov 24 '17 at 13:43

This in not an answer but is too big for a comment to Noam Elkies' beautiful answer. What follows is a simple way of finding the small values in the P.P.S.

Let $a=[1,1,1;2,1,1;2,2,1]$, $c_i=a^i$, $n_i=c_i[1,3]$ and $f(n)=n^{1/2}( \|n 2^{1/3}\| + \|n2^{2/3}\|)$.

The first few values of $f(n_i)$ are:

1 0.67251999792667369002

2 0.79333763029795146209

3 0.58150218789189747742

4 0.43461235216989424483

5 0.47947613209641674474

Note $n_9=38781$. For $i<=100000$ the smallest value of $f(n_i)$ occurs at $i=86880$ where $f(n_{86880})$ is approximately 0.36372453.

Two references for scaled error geometry type problems are:

Hensley, D., 2005. “Simultaneous diophantine approximation.

Hinkel, D., 2014. Constructing Simultaneous Diophantine Approximations of Certain Cubic Numbers. arXiv preprint arXiv:1412.3936.

The latter seems particularly appropriate here.

• The lim inf of the possible ratios is $2^{-2/3} 3^{-1/2} = 0.36370787865724 \ldots\ .$ – Noam D. Elkies Dec 5 '17 at 19:35
• @NoamD.Elkies So if I understand correctly, which is unlikely, $C=2^{-2/3}3^{-1/2}$. This makes sense given the equation of the inner most ellipse. But then it seems there should be some $i$ such that $f(n_i)=C$ (as the inequality is not strict). I would feel better if I knew how to compute even one such $i$. – O. S. Dawg Dec 8 '17 at 3:31
• Sorry, you can come arbitrarily close but not exactly, for the same kind of reason that the imaginary part of $((3+4i)/5)^n$ can get arbitrarily close to $1$ but never equals $1$ exactly for any integer $n$. – Noam D. Elkies Dec 8 '17 at 5:19
• Got it. Snipe hunt avoided. Thanks! – O. S. Dawg Dec 9 '17 at 17:01