wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Powers approximating integers.
        
(Message started by: Icarus on Mar 12^th, 2006, 3:29pm)

Title: Powers approximating integers.
Post by Icarus on Mar 12^th, 2006, 3:29pm

The golden ratio http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif = 1.6180..., has an unusual property: (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gifⁿ --> 0) mod 1 as n --> http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif.

Which real numbers have this property?

Of course, the Integers themselves do, and almost as trivially, all x with |x| < 1 satisfy the condition.

What other numbers have approximately integral powers?

[ I have only a partial answer for this. ]

Title: Re: Powers approximating integers.
Post by towr on Mar 13^th, 2006, 12:37am

There's a large range of numbers that can easily be identified.
Namely if you have x and x', both roots of a the same quadratic equation, such that |x'| < 1 and xⁿ + x'ⁿ is integer. Of which we can generate a good number from second order recurrences. (Because, obviously x'ⁿ goes to 0, so xⁿ must converge to an integer)

One might ask whether all numbers fall under this, but that's probably not the case. I'd imagine you could have a third order recurrence that gives (nonzero) y, y', and y'' such that the latter two are smaller in magnitude than 1, and yⁿ + y'ⁿ + y''ⁿ being integer. (And similarly for higher order recurrences)

Title: Re: Powers approximating integers.
Post by Icarus on Mar 13^th, 2006, 3:40pm

That is, effectively, my partial answer. Algebraic integers all of whose conjugates have magnitude < 1 should satisfy the property.

I'm curious if there is another approach that might shine more light on the matter though. And what about transcendental numbers? Can any of them satisfy the property? I'm not even examined the question of whether or not any rationals might work.

Title: Re: Powers approximating integers.
Post by Barukh on Mar 14^th, 2006, 12:22am

Icarus, I think the following recent paper (http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6WKD-4H6PM0N-1-H&_cdi=6904&_user=852645&_orig=browse&_coverDate=03%2F31%2F2006&_sk=998829998&view=c&wchp=dGLbVzb-zSkWb&md5=0de49d6653809ad19822d661cea01912&ie=/sdarticle.pdf) may partially answer one of your questions.

Title: Re: Powers approximating integers.
Post by Icarus on Mar 14^th, 2006, 5:31am

Possibly - but I'm too chintzy to spring for the $30 it would cost to find out for sure.

Title: Re: Powers approximating integers.
Post by towr on Mar 14^th, 2006, 5:54am

You need to pay to see it?
I'll send you a copy

Title: Re: Powers approximating integers.
Post by Icarus on Mar 14^th, 2006, 3:06pm

The link takes me to a log-in screen with a second panel telling me that if I don't have a log-in, I can purchase the article for $30. There is a link to the abstract, so I can read that, but the article itself requires payment.

Title: Re: Powers approximating integers.
Post by Eigenray on Mar 15^th, 2006, 9:51pm

on 03/13/06 at 15:40:43, Icarus wrote:

That is, effectively, my partial answer. Algebraic integers all of whose conjugates have magnitude < 1 should satisfy the property.

These are known as [link=http://mathworld.wolfram.com/PisotNumber.html]Pisot Numbers[/link], and they indeed satisfy the property. For, the sum of the n-th powers of all conjugates of any algebraic integer x is always an integer: it can be expressed as a polynomial (with coefficients in Z) in the elementary symmetric polynomials (cf. e.g. Newton's Identities), which are the coefficients of the minimal polynomial of x, and therefore integers.

As a partial converse, these are the only such algebraic x>1. Let ||x|| denote the distance from x to the nearest integer. I follow an argument in Algebraic Numbers and Harmonic Analysis, by Yves Meyer.

Theorem: If x>1 is algebraic, and ||x^k|| -> 0, then x is Pisot: it is an algebraic integer, whose other conjugates are all < 1 in magnitude.

Proof (sketch): Write

x^k = p_k + r_k,

where p_k is an integer, and r_k -> 0. If

P(t) = c_n tⁿ + c_n-1t^n-1 + . . . + c₀ = c_n(t-x₁)(t-x₂)...(t-x_n)

is the minimal polynomial of x=x₁ (note the {x_i} are distinct, Q being perfect), with integer coefficients, then x^k*P(x) = 0 gives

c_nr_k+n + ... + c₀r_k = -c_np_k+n - ... - c₀p_k.

Since the LHS goes to 0, but the RHS is an integer, it follows that the above quantity is identically 0 for k>K sufficiently large. That is, {r_k} satisfies a linear recurrence with characteristic polynomial P, and therefore we can write

r_k = a₁x₁^k + . . . + a_n x_n^k, k>K,

for some complex numbers a_i. It is left as an exercise to the reader to show that

r_k -> 0 implies that a_i=0 whenever |x_i| >1.

In particular, a₁=0. Renumbering if necessary, we may also assume, for some 2<m<n, that

r_k = a₂x₂^k + ... + a_mx_m^k for k>K,

where a₂,...,a_m are non-zero, and hence |x_i|<1 for 2<i<m. Now, the power series

[sum]_k>K p_kt^k = [sum] (x^k-r_k)t^k
= x^Kt^K/(1-xt) - a₂x₂^Kt^K/(1-x₂t) - . . . - a_mx_m^Kt^K/(1-x_mt)
= F(t)/G(t),

where G(t) = (1-tx₁)...(1-tx_m), and F is a polynomial relatively prime to G. Since F/G has integer coefficients, and G(0)=1, it follows from a "well-known result" (Meyer calls it Fatou's lemma) that in fact G has integer coefficients. Then t^mG(1/t) is a monic integral polynomial of degree m, with x as a root. It follows that m=n, and that x is Pisot.

Quote:

I'm curious if there is another approach that might shine more light on the matter though. And what about transcendental numbers? Can any of them satisfy the property?

As far as I know, this is unknown, but conjectured to be "no". What is known is the following (again from Meyer):

If x>1, and c>0 is such that [sum] ||c xⁿ||² is finite, then x is Pisot.

Quote:

I'm not even examined the question of whether or not any rationals might work.

The case of x rational is covered by the above Theorem (and has come up [link=http://www.ocf.berkeley.edu/%7Ewwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1077786604]before[/link]), but the proof can be simplified. For, if x > 1 is rational, then arguing as above, writing x^k = p_k + r_k, and taking n=1, we find simply r_k = a x^k for k sufficiently large. Since this goes to 0, either a=0, in which case x is an integer, or |x|<1.

Exercise: For any integers a>2, and n>1, there is a Pisot number x satisfying xⁿ(x-a)=1. Hence a is a limit point of the set of Pisots.

In fact, it can be shown that the set of Pisots is closed. Also of note: if K is a number field of degree n, discriminant d, with r real embeddings and 2s complex ones, then any real interval of length T contains
2^r-1[pi]^s/|d| T + o(T)
Pisot numbers of degree n, lying in K.

But as to what Pisot numbers have to do with harmonic analysis, I really don't know enough to say.