Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have been looking at concise ways to represent irrational numbers using only integers.

I was thinking about base $\phi$ (golden ratio base) and how it can represent the quadratic extension of the rationals with $\sqrt 5$ (i.e. $\mathbb Q[\sqrt 5]$) in a finite (potentially infinite but periodic) representation. For example, $5 + \sqrt 5 = 10000.01$ exactly.

I also noticed that $\sqrt a$ always results in a periodic continued fraction (CF) when $a$ is a square-free integer. The golden ratio $\phi$ is the least accurate irrational number to approximate by truncating its continued fraction, as it is [1, 1, 1, ...] (see Hurwitz's theorem and the Wikipedia Continued Fractions page).

Since truncating $\phi$'s CF is not as accurate a rational approximation as for other irrationals, and given that base $\phi$ allows us to represent $\phi$ concisely ($\phi = 10$) and allows a representation of integers (e.g. $2 = 10.01$), which is what CF's already use,

  1. Are there any potential problems with using base $\phi$ as the base for a CF representation considering it gets around the accuracy issue for $\phi$ and allows continued fractions involving $\sqrt 5$ to be finite (I think)?

  2. Is the continued fraction of the square root of a base $\phi$ number periodic when the CF is expressed in base $\phi$, in much the same manner as a square free integer?

  3. Are there any other advantages/disadvantages to representing continued fractions in this base instead of another more typical base?

This is my first post, so please let me know if I need to correct anything.

share|improve this question
    
I'm not sure what you mean by "the base for a CF representation". In the most naive sense, continued fractions are completely independent of base. It sounds like you would like to allow the terms $[a_0,a_1,\ldots]$ to be finite $\phi$-ary expansions rather than just integers? –  Erick Wong Jul 16 '12 at 21:22
    
@Erick: That is what I had in mind, but as both Steven and you point out, continued fractions are independent of base. My mistake was that I wrongly understood independent of base to mean "compatible with any base that can represent integers" instead of "not using any base whatsoever". I am fairly new to number theory. –  hatch22 Jul 17 '12 at 3:03

2 Answers 2

up vote 4 down vote accepted

I'm not entirely sure what you mean by 'as the base for a CRF representation'; continued fraction representations, at heart, don't use bases at all - just integers.

Assuming that what you mean is allowing the coefficients of a standard continued fraction representation to be elements of $\mathbb{Z}[\phi]$ rather than just $\mathbb{Z}$, then you run into trouble of a different source: in that case, there's no canonical CF representatation! The usual algorithm for generating a canonical continued fraction uses the floor operation $\lfloor x\rfloor$ (that is, 'the largest integer less than $x$') : $a_0 = \lfloor x\rfloor, a_1=\lfloor\frac{1}{x-a_0}\rfloor$, etc. But this operation can't be defined in $\mathbb{Z}[\phi]$ because the values in that ring are dense in the reals; there's no 'largest member less than $x$' for any $x$.

On the other hand, if you're interested in generalizing some of the properties of continued fractions to the ring of 'golden integers', there's another approach you could investigate:

As I'm sure you're already aware, the sequence of partial convergents to a continued fraction for some irrational number $x$ offers the best approximations to $x$, in a very canonical sense: each term $\frac{p}{q}$ in the sequence is the best approximation to $x$ of height less than $q$, where we define the height of a fraction $\frac{c}{d}$ in simplest terms to be just the denominator of the fraction. In essence, the height represents the simplicity of the number, and the best rational approximation property says that no 'simpler' number than any of the partial convergents of the CF can be a better approximation.

You could try and generalize this property by defining a canonical height for golden integers (for instance, $\mathrm{ht}(a+b\phi) = \max(|a|, |b|)$ or even just $\mathrm{ht}(a+b\phi) = |b|$) and then studying the sequence of 'convergents' to a number $x$ using this height and the best-approximation property; this is in some sense similar to the continued fraction approach in that both are looking at the best approximation to $x$ of the form $f(a,b)$ for particular functions $f$ and integers $a,b$ less than some specified bound (and studying how that approximation changes as the bound moves) — in the case of continued fractions then $f(a,b) = \frac{a}{b}$ while here it's $f(a,b) = a+b\phi$. It's very possible that the similarity of the problem means that these convergents have some canonical structure (similar to the way that the continued-fraction structure unites the best rational approximations) which you could use to define a continued-fraction equivalent for the representation by golden integers. Speaking personally, I'd certainly be curious to see whether anything interesting came out of it!

share|improve this answer
    
Finding a continued fraction-like representation using an alternative definition of height is an interesting possibility that I'd like to explore, though I fear I lack the necessary expertise. I welcome input from anyone who'd like to attempt it or comment on how to go about it. On a related note, do continued fractions of square roots of a golden ratio base number (any or all) exhibit any sort of pattern (I know they're not periodic)? If this should be a new question let me know. –  hatch22 Jul 17 '12 at 3:11
    
So after doing a little more research, would a generalized continued fraction be able to represent the square root of a base-$\phi$ number in a periodic form? –  hatch22 Jul 17 '12 at 13:57
    
@user35941 No, for an interesting reason: generalized continued fractions (with constant coefficients) are still essentially projective linear transformations and so periodic GCFs can only represent quadratics. Basically, for a periodic GCF you'll still be left with an equation of the form $x=\frac{ax+b}{cx+d}$ for the value of the GCF, and that's a quadratic equation in $x$. –  Steven Stadnicki Jul 17 '12 at 17:21
    
Perhaps I am misunderstanding you, but are not quartic expressions like $x = \sqrt(5 + \sqrt 5)$ quadratic in base $\phi$ (e.g. $\sqrt(10000.01)$? From what I've read of generalized continued fractions, the values used for numerator and denominator can be any real value, even $\pi$. –  hatch22 Jul 17 '12 at 17:32
    
I think you're confusing a number with its representation - being quadratic isn't a property of a number with respect to some base(1); it's a property of the number itself (that it's the solution of a quadratic equation with integer coefficients). And while GCFs can use any coefficients, for concreteness you really want to restrict the coefficients to some particular meaningful set; otherwise CF representations are trivial. (1) : one can talk meaningfully about quadratic extensions, but that's another matter.) –  Steven Stadnicki Jul 17 '12 at 17:48

Steven has given an excellent answer, but I fear many people will not read all the comments and decide that the answer is basically no instead of yes due to the loss of a canonical form of continued fractions.

I will now try to demonstrate how to go about finding a good representation for base-$\phi$ square roots and why this might be useful.

It turns out that the sine or cosine of any integer multiple of $\pi/60$ can be represented as a linear combination of the following 6 factors (see Exact Trigonometric Constants):
$1$
$\sqrt 2$
$\sqrt 3$
$\sqrt 5$
$\sqrt{5+\sqrt 5}$
$\sqrt{5-\sqrt 5}$

Except for 1, these are basically quadratic extensions of $\mathbb Q$.

I want to represent a subset of the constructable numbers that use only sines and cosines of angles $\dfrac{n\pi}{60}$ where $n \in \mathbb Z$.

Generalized continued fractions (GCF) allow me to represent square roots using the following formula (see Methods of Computing Square Roots):
$\sqrt z = \sqrt{x^2 + y} = x + \dfrac{y}{2x + \dfrac{y}{2x + \dfrac {y}{2x + \dfrac{y}{\ddots}}}}$

where $x$ and $y$ are positive real numbers, thus guaranteeing convergence as long as the product of successive $2x$'s grows faster than the product of successive $y$'s (see the Convergence Problem). Generally we want $x$ to be as large as possible and $y$ to be as small as possible for faster convergence.

For $\sqrt 2$, $x = 1$ and $y = 1$.

For $\sqrt 3$, x = 1 and $y = 2$ does not converge quickly. Let's take a look in base-$\phi$.
$3 = 100.01 = \phi^2 + \phi^{-2}$ so $x = \phi$ and $y = \phi^{-2}$ will give much faster convergence. You might wonder if $\sqrt 2$ has a similar faster convergence, but as $2 = 10.01 = \phi + \phi^{-2}$ we don't have an easy way to represent $x$ as $\sqrt \phi$. If we re-write it as $2 = 1.11 = 1 + \phi^{-1} + \phi^{-2}$ we can take the $1$ for $x$ leaving $y = 0.11 = 1.00 = 1$ for $y$, which simply recovers $x = 1$ and $y = 1$.

$\sqrt 5$ is already directly representable in base-$\phi$, but if we wanted to use integers, $x = 2$ and $y = 1$ works just fine, and base-$\phi$ for $5$ doesn't give us a better convergence.

Now for the fun part.
$5 + \sqrt 5 = 10000.01 = \phi^4 + \phi^{-2}$, so $x = \phi^2$ and $y = \phi^{-2}$ will give good convergence, and
$5 - \sqrt 5 = 100.0001 = \phi^2 + \phi^{-4}$, so $x = \phi$ and $y = \phi^{-4}$ will give good convergence, both in a finitely representable periodic form.

Combinations of these factors like $\sqrt 6 = \sqrt 2\sqrt 3$ (for $15^\circ$) and $\sqrt 2\sqrt{5 + \sqrt 5}$ (for $12^\circ$) are also periodic GCF's.

This gives us a nice finite way to represent vectors made from sines and cosines of integer multiples of $3^\circ$.

So to answer my original questions:

  1. Yes. One problem is that uniqueness is lost for CF representations. There are infinitely many ways to represent the same CF. This is related to the problem base-$\phi$ has in that there are infinitely many finite ways to represent the same number (using the 100 = 011 conversion). This is not a problem as long as we can find a consistent representation for numbers we are interested in.
  2. Yes, at the cost of uniqueness.
  3. One advantage is potentially faster convergence of a GCF than with only integers. Another is the ability to represent quadratic extensions (square roots) of $\mathbb Z[\phi]$ in a periodic form.
share|improve this answer
    
@Steven, please let me know if I missed anything important or made any serious mistakes. –  hatch22 Jul 18 '12 at 17:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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