10
$\begingroup$

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$

$\endgroup$
15
+25
$\begingroup$

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$.

$\endgroup$
  • 2
    $\begingroup$ It's very very nice!+1,and I want to known this more generally have elementary number theory methods to solve it? $\endgroup$ – function sug Nov 24 '17 at 3:37
  • 2
    $\begingroup$ 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$. $\endgroup$ – Noam D. Elkies Nov 24 '17 at 4:40
  • $\begingroup$ 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. $\endgroup$ – zwim Nov 24 '17 at 12:30
  • $\begingroup$ 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. $\endgroup$ – zwim Nov 24 '17 at 12:30
  • $\begingroup$ Pretty impressive. Elementary and non-elementary are relative in mathematics. There was a time when the irrational nature of $\sqrt2$ was non-elementary. $\endgroup$ – Piquito Nov 24 '17 at 13:43
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The lim inf of the possible ratios is $2^{-2/3} 3^{-1/2} = 0.36370787865724 \ldots\ .$ $\endgroup$ – Noam D. Elkies Dec 5 '17 at 19:35
  • $\begingroup$ @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$. $\endgroup$ – O. S. Dawg Dec 8 '17 at 3:31
  • $\begingroup$ 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$. $\endgroup$ – Noam D. Elkies Dec 8 '17 at 5:19
  • 1
    $\begingroup$ Got it. Snipe hunt avoided. Thanks! $\endgroup$ – O. S. Dawg Dec 9 '17 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.