Littlewood's conjecture and Zeckendorf representations

Abstract

Littlewoodformodningen hevder at \(\liminf_{n\to \infty }n \langle n \alpha \rangle \langle n \beta \rangle = 0\) for alle reelle tall \(\alpha, \beta\), der \(\langle x\rangle = \min_{n \in \mathbb{Z}} |x - n|\). I denne oppgaven undersøker vi oppførselen til funksjonen \(\langle n x \rangle\) ved å bruke Zeckendorf-representasjoner.

Zeckendorf beviste av man kan skrive \(n\) som en sum av ikke-etterfølgende Fibonacci-tall. Hoggatt generaliserte dette teoremet til blant annet Pell-tallene. Vi oppdager at vi kan utvide teoremene og definere Zeckendorf-representasjoner med hensyn på enhver følge \(B_n\) av delkjedebrøknevnere. Da tolkes Fibonacci-tallene \(F_n\) og Pell-tallene \(P_n\) som delkjedebrøknevnerne som hører til det gyldne snittet \(\phi\) og \(\sqrt 2\).

Vi beviser noen ulikheter som kobler det første leddet i \(B_n\)-Zeckendorf-representasjonen av \(n\) med størrelsen på funksjonen \(\langle n x \rangle\), der \(B_n\) er delkjedebrøksnevnerne til \(x\). Med dette kan vi for eksempel anslå at \(\langle3194\phi\rangle \langle 3194\sqrt 2\rangle\) er liten. Dette er fordi hvis vi ser på \(F_n\)- og \(P_n\)-Zeckendorf-representasjonene til \(3194 = F_{15} + F_{18} = 2P_{8} + P_{10}\), så ser vi at de første leddene \(F_{15}\) og \(P_{8}\) er store.

Vi har da kun skarpe ulikheter for tilfellene \(x=\phi\) og \(x = \sqrt 2\). Ulikhetene i det generelle tilfellet er ikke så skarpe og har sine begrensinger, så det er forbedringspotensial.

Til slutt anvender vi disse ulikhetene til å utvikle og implementere en algoritme som beregner \(\min_{1 \leq n \leq N} n \langle n\phi \rangle \langle n \sqrt 2 \rangle\) med tidkompleksitet lik \(\mathcal O (\sqrt N \log^3 N)\). Vi beregnet dette for \(N=F_{102}\), og fant ut at minimumet oppnås når \(n = 195418 = F_{26} = P_8 + P_9 + P_{15}\).

Vi konkluderer at Zeckendorf-representasjoner gir en praktisk framgangsmåte for å søke etter simultane rasjonelle approksimasjoner, som vi håper kan gi mer innsikt i \newline Littlewoodformodningen.

Littlewood's conjecture poses that \(\liminf_{n\to \infty }n \langle n \alpha \rangle \langle n \beta \rangle = 0\) for all real \(\alpha, \beta\), where \(\langle x\rangle = \min_{n \in \mathbb{Z}} |x - n|\). This thesis explores the behaviour of the function \(\langle n x \rangle\) using Zeckendorf representations.

Zeckendorf proved that any number \(n\) can be expressed as a sum of non-consecutive Fibonacci numbers. Hoggatt generalised this to Pell numbers and more. We discover that with minor modification, we can define Zeckendorf representations with respect to any sequence of partial denominators \(B_n\) of a continued fraction. In this context, Fibonacci numbers \(F_n\) and Pell numbers \(P_n\) are just partial denominators of the continued fractions of the golden ratio \(\phi\) and \(\sqrt 2\).

We prove some bounds that connect the first term of the \(B_n\)-Zeckendorf representation of \(n\), to the size of the function \(\langle n x \rangle\), where \(B_n\) are the partial denominators of \(x\). For example, we can predict that \(\langle 3194 \phi \rangle\langle 3194 \sqrt 2 \rangle\) is small, by seeing that in both Zeckendorf representations, \(3194 = F_{15} + F_{18} = 2P_{8} + P_{10}\), the first terms \(F_{15}\) and \(P_{8}\) are large.

We note that we only have sharp bounds for the cases \(x=\phi\) and \(x=\sqrt 2\). The bounds in the general case are unwieldy and not as sharp, so there is room for improvement.

Finally, we apply these bounds to design and implement an algorithm for calculating a special case of a finite version of Littlewood's conjecture, \(\min_{1 \leq n \leq N} n \langle n\phi \rangle \langle n \sqrt 2 \rangle\), in \(\mathcal O (\sqrt N \log^3 N)\) time. We find that for \(N=F_{102}\), the minimum is achieved by \(n = 196418 = F_{26} =P_8 + P_{9} + P_{15}\).

We conclude that Zeckendorf representations make it easier to practically search for simultaneous rational approximations. We hope that this helps build further understanding of Littlewood's conjecture.