The following is from Clark Kimberling’s problems page.

17. Special M

Let r denote the golden ratio, (1+sqrt(5))/2, and let [ ] denote the floor function. For fixed n, let u(k)=[k*r^n], and let v(k)=[k*r]^n. Obviously, v grows faster than u. Let w(k)=[v(k)/k^(n-1)]. We can expect w to lag behind u but have about the same growth-rate. Prove or disprove that for every fixed n > 0, as k ranges through all the positive integers, there is a number M such that u(k)-w(k) takes each of the values 1,2,...,M infinitely many times, and u(k)-w(k) <= M. (Can you formulate M as a function of n? Generalize for other numbers r?)

Accepted solution

It is proved below that the conjecture is true, but the generalization to all real r>1 is false.

At first, try generalizing to any r>1 and replace xn (n>0) by any function ƒ(x) such that

Generalize u and w to:


and write Δ(k) for u(k)w(k).

Although the conjecture in this more general form turns out to be false (see below) the discussion will throw light on the proof of the original conjecture.

Define ξk={kr}, where {} denotes the fractional part. Define gk by

gk= [ƒ(r)ƒ(rξk/k)]/k/k)  if ξk>0
  ƒ′(r)  if ξk=0.

Then gkƒ′(r) as k. We have


and hence

u(k)=kƒ(r),    w(k)=kƒ(r)gkξk.

Define ηk={kƒ(r)}. By hypothesis gk>0 and hence

Δ(k)=0  iff0<gkξkηk
Δ(k)=1  iffηk<gkξkηk+1
Δ(k)=2  iffηk+1<gkξkηk+2
Δ(k)=3  iffηk+2<gkξkηk+3

etc.  In general, Δ(k)=gkξkηk. For m=0,1,,gk let R(k,m) be the set of ,η) such that

0ξ<1, 0η<1,gkξη=m. (1)

Then Δ(k)=m  iff  ({kr},{kƒ(r)})R(k,m). Figures 1a, 1b show examples of the regions R(k,m), with the values of m, for gk>1 and gk<1 respectively.

Figure 1a Figure 1b

Recalling that gkƒ′(r)=g, say, define R(,m) as in (1) with gk changed to g. The basic idea is:

Lemma 1. Suppose R(,m) has a subset S such that

(i)S lies at a strictly positive distance from the bounding lines of R(,m);
(ii)S contains infinitely many of the points ({kr},{kƒ(r)}).

Then Δ(k)=m for infinitely many k.

Proof. Since gkg, (i) implies that SR(k,m) for all sufficiently large k. Hence for infinitely many k we have ({kr},{kƒ(r)})R(k,m), that is, Δ(k)=m. ■

Setting s=ƒ(r), we are therefore led to look at the distribution of ({kr},{ks}) within the unit square, where r and s are fixed real numbers and k runs through the positive integers.

What complicates the proof, and causes the generalized conjecture to fail, is the possibility that r and s are linearly dependent over the integers. i.e. that there exists a relation

arbs+c=0 (a,b,c)(0,0,0) (2)

for some integers a,b,c. If no such relation exists (which implies that r and s are both irrational) then the ({kr},{ks}) are uniformly distributed in the unit square (J.W.S. Cassels, An Introduction to Diophantine Approximation, Cambridge University Press, 1957, p. 60).

If r and s are both rational then clearly the ({kr},{ks}) consist of a finite set of points, which occur equally often. The remaining case requires more work.

Lemma 2. Suppose that r,s are not both rational and are linearly dependent over the integers, i.e. there exist integers a,b,c satisfying (2). Assume w.l.o.g. that a,b,c have no common factor. Then the points ({kr},{ks}) are uniformly distributed on a set of parallel line segments, namely the set of ,η) such that

0ξ<1, 0η<1,aξbη=h, (3)

where h is an integer and b+1ha1.

Remark. Figures 2a, 2b illustrate the cases a=8, b=12 and a=8, b=−12 respectively. The points ({kr},{ks}) are uniformly distributed on the set of blue lines.

Figure 2a Figure 2b

Proof. Assume w.l.o.g. that b is irrational. Then a0 and w.l.o.g. a>0. Replacing s by s if necessary we may assume b0. Define d=HCF(a,b); then HCF(c,d)=1. Define a=a/d, b=b/d. We first replace the parallel line segments (3) by another set

0y<a,axby=l (4)

where l is an integer and 0l<d. See Figure 3, drawn with the same parameters as Figure 2a, i.e. a=8, b=12, whence d=4, a=2, b=3.

Figure 3

Figures 2a and 3 show that the original line segments (3) are the line segments (4) taken modulo the unit square. To prove this formally, define a map μ from the set of line segments (3) to the set of line segments (4) as follows. Given ,η) in (3), there are unique integers l,m such that h=md+l,0l<d. Since a,b are coprime there are then unique integers p,q such that m=ap+bq,0q<a′. Define μ(ξ,η)=(x,y) where x=ξ+p, y=η+q. We check that 0y<a and


so that (x,y) does lie on one of the segments (4). We show that μ is a bijection.

If (x,y)=μ(ξ,η) then ,η)=({x},{y}). Hence μ is (1–1).

Given any (x,y) satisfying (4) define ξ={x} and η={y}. Clearly aξbη=h where h is an integer, and b+1ha+1 since ξ,η[0,1], so ,η) satisfies (3). Define p=xξ, q=yη, m=ap+bq. Then


Since 0l<d it follows from the definition of μ that (x,y)=μ(ξ,η). Hence μ is onto.

For positive integer k define k,ηk)=({kr},{ks}) and (xk,yk)=μ(ξk,ηk). To show that k,ηk) is uniformly ditributed on the set (3), it suffices to show that (xk,yk) is uniformly distributed on (4). In the following, hk etc. are the values of h etc. derived from k,ηk).

Since d divides a we have axkaξk=a{kr}akr (mod d), and similarly bykbks (mod d). Hence

lk=axkbykakrbks=kc(mod d)

Recall c and d are coprime; hence as k runs through the positive integers, lk cycles through the values 0,1,,d1 in some order, with ld=0. So (xk,yk) visits each line segment in (4) at intervals of d. Given k, define integers uk, vk by


We have a{kr}b{ks}=hk=mkd+lk and similarly for the suffixes k+d, d. Since lk+d=lk and ld=0 this implies


Substituting mk=apk+bqk etc. and dividing by d gives


Since a and b are coprime, a divides (vk+qk+dqkqd). On any line segment in (4), the change in y on successive visits of (xk,yk) is

 {ds}+qd  (mod a).

Hence yk increases by a constant irrational amount (mod a) at each visit. Hence the distribution of (xk,yk) along each line segment is uniform. ■

Counterexample to the generalization

Before discussing the case r=Φ=(1+5)/2, it may be helpful to see why the conjecture is false for some values of r. Consider the case r=2, ƒ(x)=x3. Here s=ƒ(r)=22, so r and ƒ(r) are dependent over the integers: equation (2) holds with a=2, b=1, c=0. We have g=ƒ′(r)=6. Figure 4a shows (red) the regions R(k,m) for a typical k, and Figure 4b the regions R(,m). The points ({kr},{kƒ(r)}) lie on the blue lines.

Figure 4a Figure 4b

It can be seen that the only possible values of Δ(k) are 1, 2, 3, 4, 5 and that each of 1, 2, 4, 5 occurs infinitely often. It will be shown that Δ(k)=3 only if k=2, so that the generalized conjecture fails in this case.

In Figure 4a the left-hand boundary of R(k,3) meets the top of the square at (3/gk,1). Since ƒ is here a convex function, gk<g=6 for all k. Hence 3/gk>1/2, and the left-hand blue line does not intersect R(k,3). So if Δ(k)=3 then ({kr},{kƒ(r)}) lies on the right-hand blue line: say


where h is an integer and 0<ε<1/2.

Clearly u(k)=kƒ(r)=2h+1 and w(k)=k(kr/k)3=h3/k2, so that Δ(k)=3 iff


Define t=8k2(2h+1)2. Then t>0 and t1 (mod 8), so t7. A routine calculation shows that


so the first inequality in (8) implies 4h80. Since h=k2, the only possibilities are (h,k)=(1,1) or (2,2); and only the second of these satisifies the second inequality in (8).

Remark. It’s interesting to compare this with what happens if, keeping ƒ(x)=x3, we take r=3. Although the proportion of k such that Δ(k)=3 tends to 0, there are now infinitely many such k. See the appendix for details.

Proof of the conjecture when r=(1+5)/2

Write Φ for (1+5)/2. We now have ƒ(x)=xn where n>0. To cope with the possibility that Φ and Φn are linearly dependent over the integers, we need, in addition to Lemma 2:

Lemma 3. If Φ and Φn are linearly dependent over the integers, and n1, then the gradient nΦn1 is irrational.

Proof. Suppose aΦbΦn+c=0 where a,b,c are integers not all 0, and suppose, for a contradiction, that nΦn1 is rational.

If c=0 then Φn1=a/b is rational, hence n is rational; say n1=p/q, where p,q are integers and by hypothesis p0. Then Φ p=(a/b)q is rational. This is a contradiction, since Φ p is irrational for integer p0. (Note here the difference between r=Φ and the counterexample r=2.)

If c0, then a+cΦ1 is irrational and algebraic. Since n(a+cΦ1)=bnΦn1 is rational, n is also irrational and algebraic. Then since Φ is algebraic, Φn is transcendental by the Gelfond–Schneider theorem. But Φn is the product of the algebraic numbers n1, nΦn1, Φ: contradiction. ■

The cases n=1, n>1, n<1 will now be considered separately.

Case n = 1. This is trivial: Δ(k)=0 for all k, so the result holds vacuously with M=0.

Case n > 1. If Φ and Φn are linearly independent over the integers, then the points ({kΦ},{kΦn}) are distributed uniformly in the unit square, so every value of Δ(k) from 0 to g=nΦn1 occurs infinitely often. Further, as k, the proportion of k for which Δ(k)=m tends to the area of R(,m).

Figure 5 shows some examples of what happens if Φ and Φn are linearly dependent. As before, the red lines mark the regions R(,m) and the points ({kΦ},{kΦn}) lie on the blue lines. The red lines have gradient g=nΦn1, which is irrational by Lemma 3; hence a red line and a blue line never meet a side of the square at the same point (other than the origin).

Figure 5a Figure 5b Figure 5c Figure 5d

If a and b have the same sign (Figures 5a, 5b, 5c), consider tracing the blue line upwards from (0, 0). It starts in the region R(,0) or R(,1). If it hits the top of the square in the region R(,m) it wraps round to a point in R(,m+1). Hence, each R(,m) for m=1,,g1 contains a non-zero segment of blue line. In Lemma 1 we can take S to be (say) the middle third of this segment and conclude that each value Δ(k)=1,,g1 occurs for infinitely many k.

If R(,g) is cut by a blue line, then Δ(k)=g also occurs for infinitely many k. Else note that xn is a convex function for n>1, so that for all k we have gkg and hence R(k,g)R(,g). So no R(k,g) is cut by a blue line, and Δ(k)=g does not occur at all. The conjecture holds in either case, with M=g or g1 respectively.

(We have not discussed how often Δ(k)=0 occurs, but the conjecture as stated does not require this.)

If a and b have opposite signs (Figure 5d) the argument is similar, but now the values Δ(k)=0,g necessarily occur. The conjecture holds with M=g.

Case n < 1. Here g=ƒ′(Φ)=nΦn1<1. Further, since ƒ(Φ)<Φ and ƒ is a concave function, gk<1 for each k. Hence the only possible values of Δ(k) are 0 and 1. We need to show that the value 1 occurs infinitely often or not at all.

If Φ and Φn are linearly independent over the integers, then the points ({kΦ},{kΦn}) are uniformly distributed in the unit square and each value Δ(k)=0,1 occurs infinitely often. Further, as k, the proportion of k for which Δ(k)=1 tends to the area of R(,1), i.e. nΦn1/2.

Suppose Φ and Φn are linearly dependent, i.e.

aΦbΦn+c=0 (a,b,c)(0,0,0), (9)

where b0 (since Φ is irrational) and w.l.o.g. a0. The value Δ(k)=1 occurs infinitely often if R(,1) (the triangle below the red line in Figures 6 and  7) is cut by a blue line.

Figure 6a Figure 6b Figure 6c Figure 6d

Thus Δ(k)=1 occurs infinitely often if a=0 (Figure 6a), or b<0 (6b). Suppose now that a,b>0. Then Δ(k)=1 occurs infinitely often if a>1 (6c), or a=1 and g>1/b (6d). Since g1/b by Lemma 3, it remains to deal with the case a=1, g<1/b (Figure 7).

Figure 7

Here Δ(k)=0 for all large enough k. We need to show that Δ(k)=1 never occurs at all. The proof is more complicated than for n>1, since xn is now a concave function and the relation R(k,g)R(,g) used for n>1 is reversed.

Lemma 4. For real t>0 define λ(t)=(1+t1)ln(1+t), and define λ(0) by continuity. Then λ(t) is an increasing function of t with λ(0)=1.

Proof. For small t>0 we have λ(t)=1+t/(1×2)t2/(2×3)+t3/(3×4), so λ(0)=1. A routine calculation shows that λ′(t)>0 is equivalent to the well-known inequality exp(t)>1+t. ■

With a=1, (9) gives ΦbΦn+c=0. Since 0<n<1, so 1<Φn<Φ. If b=1 this gives 1Φ<c<0, a contradiction since c is an integer. Hence b2. Next, bc<bΦnc=Φ, hence bc1 (since b,c are integers), hence cb1. We show that, for a given b, the condition nΦn1=g<1/b is satisfied only when c=b1. Since n, and therefore nΦn1, increases with c, it suffices to show that nΦn1>1/b when c=b. In this case


so we have to prove (1+b/Φ)ln(1+Φ/b)>l. Since l<1, this follows from Lemma 4 with t=Φ/b.

Conversely, suppose c=b1. To show that nΦn1<1/b, note that


Set t=1)/b. Another short calculation shows that nΦn1<1/b is equivalent to λ(t)<Φl/1) = 1.2598…. Since t1)/2 and λ((Φ1)/2)=1.1406…, the result follows from Lemma 4.

Assuming then that ΦbΦn+b1=0, with 0<n<1 and b2, we have to show the Δ(k) are all 0. For k2 we have 1/k<Φ1 and therefore, since ƒ(x)=xn is a concave function when 0<n<1,


Hence R(k,1) lies below all the blue lines in Figure 7, and Δ(k)=0.

For k=1 we have u(1)=Φn=1 and w(1)=Φn=1, so Δ(1)=0. This completes the proof.

Appendix: the case ƒ(x)=x3,  r=3

This looks at first very similar to the counterexample with the same ƒ and r=2. The possible values for Δ(k) are 1,,8. The proportion of k for which Δ(k)=3 or 6 tends to 0 as k. If Δ(k)=3 then, similarly to the case r=2, we have


where h is an integer and 0<ε<1/3.

We have u(k)=kƒ(r)=3h+1 and w(k)=k(kr/k)3=h3/k2, so that Δ(k)=3 iff

3h2h3/k2<3h1. (10)

Define t=27k2(3h+1)2. Then t>0 and t2 (mod 3). A routine calculation shows that the left-hand inequality in (10) is equivalent to


If t2 then t5, hence h1, hence k3<5/3, a contradiction. Hence if Δ(k)=3 then t=2.

Conversely, given positive integers h,k such that 27k2(3h+1)2=2, it is easy to verify that k3=h, k33=3h+1, and h3/k2=3h2, whence Δ(k)=3. To find such h,k consider the diophantine equation


This has the obvious solution (k1,l1)=(1,5). From this and the solution to the Pell equation p227q2=1, viz. (p,q)=(26,5), one can generate all solutions in the usual way, by setting


Clearly li+1li (mod 3), with l11, so when i is even li has the form 3h+1 and Δ(ki)=3. Hence there are infinitely many k such that Δ(k)=3, though they are scarce: the first three are 51, 137801, 372338251.

The case Δ(k)=6 is probably similar, but hasn’t yet been analyzed.

Michael Behrend  18 June 2012