Tag Archives: dense set

An Irrationality Criterion

Recall Corollary 4 from this post:

Corollary 4. If S is a subgroup of (\mathbb R,+), then the following are equivalent:

(i) S is well-ordered;

(ii) S is not dense;

(iii) S is cyclic.

Let \alpha be a non-zero real number and take S=\langle 1,\alpha\rangle to be the subgroup of (\mathbb R,+) generated by 1 and \alpha. This is a cyclic group if and only if \exists \beta, \langle 1,\alpha\rangle=\langle \beta\rangle
\Leftrightarrow 1=m\beta', \alpha=n\beta' for some m,n\in\mathbb Z and \beta'
\Leftrightarrow \alpha/1=n/m, i.e. \alpha is rational.

Now by the above corollary, S is dense iff it is not well-ordered, i.e. iff

(*)\qquad\forall\varepsilon>0,\exists m,n\in\mathbb Z, 0<m\alpha-n<\varepsilon.

So we have the following criterion for irrationality:

Criterion 1. \alpha is irrational if and only if (*) holds.

Note that S is dense in \mathbb R iff S/\mathbb Z=\{\{n\alpha\}:=n\alpha-\lfloor n\alpha\rfloor : n\in\mathbb Z\} is dense in (0,1). So we deduce:

Criterion 2. \alpha is irrational \Leftrightarrow\forall\varepsilon>0,\exists n\in\mathbb Z, 0<\{n\alpha\}<\varepsilon.

We demonstrate how this may be useful by proving that certain types of numbers are irrational.

Proposition 1. Let a_1,a_2,\dots be a sequence of non-zero integers such that

(\dagger)\qquad\displaystyle S=\frac{1}{a_1}+\frac{1}{a_1a_2}+\frac{1}{a_1a_2a_3}+\dots exists, and

(\ddagger)\qquad\displaystyle\frac{1}{a_{n+1}}+\frac{1}{a_{n+1}a_{n+2}}+\frac{1}{a_{n+1}a_{n+2}a_{n+3}}+\dots\to 0 as n\to\infty.

Then S is irrational.

Proof. We have

\displaystyle \left\{a_1\cdots a_nS\right\}=\left\{\frac{1}{a_{n+1}}+\frac{1}{a_{n+1}a_{n+2}}+\frac{1}{a_{n+1}a_{n+2}a_{n+3}}+\dots\right\}.

Multiplying by -1 if necessary, we can take the expression in brackets on the right to be positive and it tends to 0 as n\to \infty. Moreover, if




which cannot happen infinitely often as the left hand side tends to zero. So the conclusion follows by Criterion 2. \square

Proposition 2. If a_1,a_2,\dots is a sequence of non-zero integers such that |a_1|\le |a_2|\le\dots and \displaystyle\lim_{n\to\infty}|a_n|=\infty, then

\displaystyle S=\frac{1}{a_1}+\frac{1}{a_1a_2}+\frac{1}{a_1a_2a_3}+\dots

exists and is irrational.

Proof. It suffices to show that (\dagger) and (\ddagger) above hold.

Convergence follows easily from the ratio test, so (\dagger) holds. Now




\displaystyle =\frac{1}{|a_{n+1}|-1}\to 0 as n\to \infty,

i.e. (\ddagger) holds. \square

Some special cases of Proposition 2 are particularly interesting:

Corollary 1. \displaystyle \sum_{n=0}^\infty\frac{1}{(n!)^k} is irrational for all positive integers k.

Proof. Take a_n=n^k. \square.

Corollary 2. e is irrational.

Proof. Take k=1 in Corollary 1. \square

Corollary 3. \sin 1 and \cos 1 are irrational.

Proof. Take a_1=1 and for n>1, a_n=-(2n-2)(2n-1) for sine, a_n=-(2n-3)(2n-2) for cosine. \square

Corollary 4. I_0(2) and I_1(2) are irrational, where I_\alpha(x) is the modified Bessel function of the first kind.

Proof. Taking k=2 in Corollary 1 shows that I_0(2) is irrational. Taking a_n=n(n+1) shows that I_1(2) is irrational. \square

Corollary 5. e^{\sqrt{2}} is irrational.

Proof. If it is rational, then so is e^{-\sqrt{2}}, and so is

\displaystyle \cosh(\sqrt 2)=\frac{e^{\sqrt{2}}+e^{-\sqrt 2}}{2}=\sum_{n=0}^\infty\frac{2^n}{(2n)!}.

Taking a_n=n(2n-1) in the above shows that this is false. \square

Corollary 6. Let k>1 be an integer and F_0,F_1,F_2,\dots the Fibonacci sequence. Then

(i) \displaystyle \sum_{n=0}^\infty\frac{1}{k^{F_n}} is irrational.

(ii) \displaystyle \sum_{n=0}^\infty\frac{1}{F_{k^n}} is irrational.

Proof. (i) Take a_n=k^{F_n} and use F_0+F_1+\dots+F_n=F_{n+2}-1.

(ii) Take a_n=F_{k^n}/F_{k^{n-1}}. \square

1 Comment

Filed under Analysis, Number Theory

A Generalisation of Pell’s Equation

We want to find the solutions to

(*)\qquad x^2+mxy+ny^2=1

over the integers, where m,n\in\mathbb Z.

Let \alpha and \bar\alpha be the roots of x^2+mx+n=0. We can factorise (*) as (x-y\alpha)(x-y\bar\alpha)=1. If \alpha is rational, it must be an integer and then it is easy to find all solutions. So let us consider the more interesting case where \alpha is not rational (i.e. \sqrt{m^2-4n}\not\in\mathbb Z).

Now a solution in the form z=x-y\alpha to (*) is a unit in the ring \mathbb Z[\alpha]. For z=x-y\alpha\in\mathbb Z[\alpha], denote its conjugate by \bar z=x-y\bar\alpha. Then we have the multiplicative norm

N(z)=N(x-y\alpha)=z\bar z=x^2+mxy+ny^2.

It follows that the solutions to (*) form a subgroup S of the multiplicative group of units of \mathbb Z[\alpha].

Case 1: m^2< 4n. Then (*) defines an ellipse, so there are at most finitely many solutions, i.e. S is a finite subgroup of \mathbb C^\times. Hence S is cyclic and every solution is of the form

\displaystyle x-y\alpha=\cos\frac{2\pi t}{k}+i\sin\frac{2\pi t}{k},\quad x-y\bar\alpha=\cos\frac{2\pi t}{k}-i\sin\frac{2\pi t}{k}

\displaystyle \Rightarrow 2x+my=2\cos\frac{2\pi t}{k}\in [-2,2]\cap\mathbb Z\Rightarrow \cos\frac{2\pi t}{k}\in\{0,\pm\frac 12,\pm1\}

\displaystyle\Rightarrow x-y\alpha\in\{\pm 1,\pm i, \frac{1\pm i\sqrt 3}{2}, \frac{-1\pm i\sqrt 3}{2}\}.

Case 2: m^2>4n. Now \alpha is real, so S is a subgroup of \mathbb R^\times.

Claim. S is not dense.

Proof. WLOG S\neq\{\pm 1\}. Then for z=x-y\alpha\in S\backslash\{\pm 1\} we have

\displaystyle \left |z-\frac 1z\right |=|y(\alpha-\bar\alpha)|\ge |\alpha-\bar\alpha|=\sqrt{m^2-4n}=:\varepsilon> 1.

Suppose that 1<z<\varepsilon is a solution. Then

\displaystyle \left |z-\frac 1z\right |=z-\frac 1z<\varepsilon-\frac 1\varepsilon<\varepsilon,

impossible. Thus S\cap (1,\varepsilon)=\emptyset, i.e. S is not dense. \square

It follows that S is either \{\pm 1\} or \langle\delta\rangle\cup -\langle\delta\rangle for some \delta>1 (cf. ordering in groups, corollary 4). Therefore all solutions (x,y) to (*) are either just (\pm 1,0), or are given by

\boxed{x-y\alpha=\pm (x_0-y_0\alpha)^k,\; k\in\mathbb Z}

where x_0-y_0\alpha is the least solution >1.

Corollary. (Dirichlet’s unit theorem for a real quadratic field) If K is a real quadratic field, then \mathcal O_K^*=\{\pm\varepsilon^n: n\in\mathbb Z\} for some \varepsilon\ge 1.

Leave a comment

Filed under Algebra, Number Theory

Ordering in Groups

This idea first came to my mind a long time ago when I was trying to generalise the application of the division algorithm. All I came up with is the following:

Proposition 0. Let S be a subgroup of (\mathbb R,+). If S has a least positive element, then S is cyclic. Otherwise S has arbitrarily small positive elements.

A few days ago, in a Number Theory lecture, we proved that the minimal solution to Pell’s equation generates all solutions. It reminded me of the division algorithm again, so it was time again to try to generalise this, because now I have a few more tools in hand!

Let’s say S is a set where the division algorithm applies. We definitely need some sort of partial order in S to say that the ‘remainder’ must be ‘less than’ the ‘divisor’. We might want S to be closed under some operation (so that we can repeatedly ‘subtract’ the ‘divisor’ from the ‘dividend’) and we also need an inverse operation (i.e. the ‘subtraction’).

So first of all, we need S to be a poset. In addition, the closure and inverse operations suggest that we want S to be a group. How should the order behave under the group operation? Clearly we want it to be compatible with the operation. We also probably want the inverse of a ‘positive’ element to be ‘negative’, and vice-versa. Do we need the group to be abelian? Maybe, but let’s not impose that condition yet.

So to put our ideas into work, let (G,+) be a group with a partial order \le such that for all g,g_1,g_2\in G, g_1\le g_2\Rightarrow g+g_1\le g+g_2 and g_1+g\le g_2+g. We say that an element g\in G is positive if 0\le g, where 0 is the identity element of G. Define the positive cone of G to be the set G^+:=\{g\in G:0\le g\} of all positive elements.

Okay now we hopefully have all the necessary definitions in place. Let’s see if we can prove anything using these. The first thing that we want is probably: if 0\le g, then -g\le 0. This follows easily: 0\le g, add -g to both sides and we are done. It works the other way around as well, so in fact we have proved:

Lemma 1. 0\le g\Leftrightarrow -g\le 0.

That was good. We wanted the inverse of positive elements to be negative and it just followed from the definition. But we want more! So take a non-zero element g\in G. By Lemma 1 we can take g to be positive without loss of generality. How about adding something to both sides of 0\le g again? Last time we added -g. We can add 0, but that doesn’t change anything. So the only obvious choice left is to add g: g\le g+g=2g. Now what? Let’s add g again! g+g\le 2g+g, i.e. 2g\le 3g. Combining the last two gives 0\le g\le 2g\le 3g. It follows by induction that mg\le ng for all integers 0\le m\le n (note: here ng=g+\dots+g, n times). This looks promising.

What about ‘negative’ elements? Note that by Lemma 1, -g\le 0. Adding -g to both sides yields -2g\le -g, and so on. So we have another nice result:

Lemma 2. mg\le ng for all integers m\le n and g\in G^+.

It seems that this is all we can derive from our first principles. So let’s apply more restrictions on G. Let a,b\in G be positive with b\le a. As in the division algorithm, let’s look at a-b,a-2b,\dots etc. We want this sequence to stop as soon as a-nb becomes negative. How do we do this? In other words, we want the set \{a-nb:n\in\mathbb Z\} to have a least positive element. Did something just pop up in your mind? A set having a least element must have reminded you of something like… the well-ordering principle! So how about we impose the extra condition that \le is a well-order on G? Well, that’s clearly absurd, because for any positive g the set \{ng:n\in\mathbb Z\} has no least element. How about least positive element then? In other words, let’s say G^+ is well-ordered under \le.

Now G has quite a few nice properties: it is a group under +, \le is an order on G preserving +, and its positive cone is well-ordered. Let’s see if our ideas work now.

Let \varepsilon be the least non-zero element in G^+ and g\in G be any non-zero element. Without loss of generality, 0<g. Then g\in G^+ so \varepsilon\le g. Consider the elements n\varepsilon for n\in\mathbb Z. We want n\varepsilon\le g<(n+1)\varepsilon for some n. Can we achieve this? We certainly have n\varepsilon\le g for n=1, so we need g<n'\varepsilon for some n'. By Lemma 2 n' must be greater than n. How do we know that n' exists?

Suppose it doesn’t. Then n\varepsilon\le g for all n\in\mathbb Z by totality (recall that a well-order is a total order) and Lemma 2. Then 0\le g+n\varepsilon\;\forall n, so g+n\varepsilon\in G^+\;\forall n. Hence \{g+n\varepsilon:n\in\mathbb Z\}\subset G^+, so it has a least element g+m\varepsilon. Then g+m\varepsilon\le g+n\varepsilon\;\forall n which implies 0\le n\varepsilon for all n\in\mathbb Z, a contradiction.

That was really good! Now we can take the maximal n such that n\varepsilon\le g. Then g<(n+1)\varepsilon. Then 0\le g-n\varepsilon<\varepsilon; the left inequality says g-n\varepsilon\in G^+, and the right inequality says g-n\varepsilon<\varepsilon. So g-n\varepsilon=0 and g=n\varepsilon. This is exactly what we wanted.

We have shown that G=\langle\varepsilon\rangle. In fact we can do more. Clearly G cannot be finite. Because otherwise \varepsilon must have finite order, i.e. k\varepsilon=0 for some positive integer k. Then 0\le\varepsilon\le 2\varepsilon\le\dots\le k\varepsilon=0 by Lemma 2. So all of these must be equalities (by antisymmetry), i.e. \varepsilon=0, a contradiction.

So our restrictions have not only worked, we’ve shown that all groups with these properties essentially have the same structure, that of the infinite cyclic group. Let’s give G a name: we say that the group G is well-ordered if the set G^+ is well-ordered under \le. We have thus proved:

Proposition 1. The only non-trivial well-ordered group is the group (\mathbb Z,+) of integers (up to isomorphism).

Now we can give one-line proofs of the following facts using our Proposition 1: (here any ordering is under the usual \le order in \mathbb R)

Corollary 1. The \gcd of two natural numbers exists, and is their least positive linear combination.

Proof. For a,b\in\mathbb N, the additive group G=\{ax+by:x,y\in\mathbb Z\} is well-ordered, and so is equal to \langle\varepsilon\rangle for \varepsilon the least positive element of G. \square

Corollary 2. \mathbb Z is a PID.

Proof. Any ideal in \mathbb Z is a well-ordered group, and so must be \langle d\rangle for some d. \square

Corollary 3. If x_0+y_0\sqrt d is the least solution >1 to Pell’s equation x^2-dy^2=1, then all solutions are given by x_n+y_n\sqrt d=(x_0+y_0\sqrt d)^n for n\in\mathbb Z.

Proof. The solutions x_n+y_n\sqrt d to Pell’s equation form a subgroup of the multiplicative group of units in the ring \mathbb Z[\sqrt d]. Since it is well-ordered, the conclusion follows. \square

We can even improve Proposition 0 a little:

Corollary 4. If S is a subgroup of (\mathbb R,+), then the following are equivalent:

(i) S is well-ordered;

(ii) S is not dense;

(iii) S is cyclic.

Proof. (i)\Leftrightarrow (iii) by Proposition 1. (iii)\Rightarrow (ii) is clear. Suppose that S is not dense. Then there exist a,b\in S with a<b such that (a,b)\cap S=\emptyset. Then (0,b-a)\cap S=\emptyset, because x\in (0,b-a)\cap S\Rightarrow a+x\in (a,b)\cap S. Therefore b-a is the minimal element in S^+\backslash\{0\}, i.e. S=\langle b-a\rangle. Thus (ii)\Rightarrow (iii). \square

A consequence of Corollary 4 is:

Corollary 5. Let G be a group. If G has a faithful one-dimensional real representation \rho: G\to\mathbb R^\times, then \rho(G) is dense if and only if G\not\cong\mathbb Z/\mathbb Z,\mathbb Z/2\mathbb Z, \mathbb Z.

Note that \rho(G) is dense if and only if it has two \mathbb Zlinearly independent elements; therefore G must be torsion-free. And since \rho is faithful, G must be abelian: \rho(ghg^{-1}h^{-1})=1\Rightarrow ghg^{-1}h^{-1}=e, i.e. gh=hg for all g,h\in G. Thus we get the following nice result:

Proposition 2. If G has a faithful one-dimensional real representation, then one of the following holds:

(i) G\cong\mathbb Z/\mathbb Z;

(ii) G\cong\mathbb Z/2\mathbb Z;

(iii) G\cong\mathbb Z;

(iv) G\triangleright\mathbb Z\oplus\mathbb Z.

Moreover, if |G|>2 and G is finitely generated, then G\cong\mathbb Z^n, for some n.


Filed under Algebra, Set Theory