The following is from Clark Kimberling’s problems page.
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?)
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 x^{n} (n>0) by any function ƒ(x) such that
Generalize u and w to:
u(k)=⌊kƒ(r)⌋, w(k)=⌊kƒ(⌊kr⌋/k)⌋, |
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 g_{k} by
g_{k}= | [ƒ(r)−ƒ(r−ξ_{k}/k)]/(ξ_{k}/k) | if ξ_{k}>0 |
ƒ′(r) | if ξ_{k}=0. |
Then g_{k}→ƒ′(r) as k→∞. We have
ƒ(⌊kr⌋/k)=ƒ((kr−ξ_{k})/k)=ƒ(r−ξ_{k}/k)=ƒ(r)−g_{k}(ξ_{k}/k), |
and hence
u(k)=⌊kƒ(r)⌋, w(k)=⌊kƒ(r)−g_{k}ξ_{k}⌋. |
Define η_{k}={kƒ(r)}. By hypothesis g_{k}>0 and hence
Δ(k)=0 iff | 0 | <g_{k}ξ_{k}≤η_{k} |
Δ(k)=1 iff | η_{k} | <g_{k}ξ_{k}≤η_{k}+1 |
Δ(k)=2 iff | η_{k}+1 | <g_{k}ξ_{k}≤η_{k}+2 |
Δ(k)=3 iff | η_{k}+2 | <g_{k}ξ_{k}≤η_{k}+3 |
etc. In general, Δ(k)=⌈g_{k}ξ_{k}−η_{k}⌉. For m=0,1,…,⌈g_{k}⌉ let R(k,m) be the set of (ξ,η) such that
0≤ξ<1, 0≤η<1, ⌈g_{k}ξ−η⌉=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 g_{k}>1 and g_{k}<1 respectively.
Recalling that g_{k}→ƒ′(r)=g, say, define R(∞,m) as in (1) with g_{k} 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 g_{k}→g, (i) implies that S⊂R(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
ar−bs+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+1≤h≤a−1.
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.
Proof. Assume w.l.o.g. that b is irrational. Then a≠0 and w.l.o.g. a>0. Replacing s by −s if necessary we may assume b≥0. 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
0≤y<a′, ax−by=l | (4) |
where l is an integer and 0≤l<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.
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,0≤l<d. Since a′,b′ are coprime there are then unique integers p,q such that m=−a′p+b′q,0≤q<a′. Define μ(ξ,η)=(x,y) where x=ξ+p, y=η+q. We check that 0≤y<a′ and
ax−by=aξ−bη+ap−bq=h+(a′p−b′q)d=md+l−md=l, |
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+1≤h≤a+1 since ξ,η∈[0,1], so (ξ,η) satisfies (3). Define p=x−ξ, q=y−η, m=−a′p+b′q. Then
h=aξ−bη=a(x−p)−b(y−q)=l−ap+bq=md+l. |
Since 0≤l<d it follows from the definition of μ that (x,y)=μ(ξ,η). Hence μ is onto.
For positive integer k define (ξ_{k},η_{k})=({kr},{ks}) and (x_{k},y_{k})=μ(ξ_{k},η_{k}). To show that (ξ_{k},η_{k}) is uniformly ditributed on the set (3), it suffices to show that (x_{k},y_{k}) is uniformly distributed on (4). In the following, h_{k} etc. are the values of h etc. derived from (ξ_{k},η_{k}).
Since d divides a we have ax_{k}≡aξ_{k}=a{kr}≡akr (mod d), and similarly by_{k}≡bks (mod d). Hence
l_{k}=ax_{k}−by_{k}≡akr−bks=−kc (mod d) |
Recall c and d are coprime; hence as k runs through the positive integers, l_{k} cycles through the values 0,1,…,d−1 in some order, with l_{d}=0. So (x_{k},y_{k}) visits each line segment in (4) at intervals of d. Given k, define integers u_{k}, v_{k} by
u_{k}={(k+d)r}−{kr}−{dr}, v_{k}={(k+d)s}−{ks}−{ds} |
We have a{kr}−b{ks}=h_{k}=m_{k}d+l_{k} and similarly for the suffixes k+d, d. Since l_{k}_{+d}=l_{k} and l_{d}=0 this implies
au_{k}−bv_{k}=(m_{k}_{+d}−m_{k}−m_{d})d. |
Substituting m_{k}=−a′p_{k}+b′q_{k} etc. and dividing by d gives
a′(u_{k}+p_{k}_{+d}−p_{k}−p_{d})=b′(v_{k}+q_{k}_{+d}−q_{k}−q_{d}). |
Since a′ and b′ are coprime, a′ divides (v_{k}+q_{k}_{+d}−q_{k}−q_{d}). On any line segment in (4), the change in y on successive visits of (x_{k},y_{k}) is
y_{k}_{+d}−y_{k} | ={(k+d)s}+q_{k}_{+d}−{ks}−q_{k} |
={ds}+v_{k}+q_{k}_{+d}−q_{k} | |
≡{ds}+q_{d} (mod a′). |
Hence y_{k} increases by a constant irrational amount (mod a′) at each visit. Hence the distribution of (x_{k},y_{k}) along each line segment is uniform. ■
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)=x^{3}. Here s=ƒ(r)=2√2, 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.
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/g_{k},1). Since ƒ is here a convex function, g_{k}<g=6 for all k. Hence 3/g_{k}>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
kr=k√2=h+1/2+ε |
kƒ(r)=k2√2=2h+1+2ε |
where h is an integer and 0<ε<1/2.
Clearly u(k)=⌊kƒ(r)⌋=2h+1 and w(k)=⌊k(⌊kr⌋/k)^{3}⌋=⌊h^{3}/k^{2}⌋, so that Δ(k)=3 iff
2h−2≤h^{3}/k^{2}<2h−1. | (8) |
Define t=8k^{2}−(2h+1)^{2}. Then t>0 and t≡−1 (mod 8), so t≥7. A routine calculation shows that
4[(2h−2)k^{2}−h^{3}]=t(h−1)−3h−1≥7(h−1)−3h−1=4h−8, |
so the first inequality in (8) implies 4h−8≤0. Since h=⌊k√2⌋, 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)=x^{3}, 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.
Write Φ for (1+√5)/2. We now have ƒ(x)=x^{n} 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 n≠1, then the gradient nΦ^{n}^{−1} 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Φ^{n}^{−1} is rational.
If c=0 then Φ^{n}^{−1}=a/b is rational, hence n is rational; say n−1=p/q, where p,q are integers and by hypothesis p≠0. Then Φ ^{p}=(a/b)^{q} is rational. This is a contradiction, since Φ ^{p} is irrational for integer p≠0. (Note here the difference between r=Φ and the counterexample r=√2.)
If c≠0, then a+cΦ^{−}^{1} is irrational and algebraic. Since n(a+cΦ^{−}^{1})=bnΦ^{n}^{−1} 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 n^{−}^{1}, nΦ^{n}^{−1}, Φ: 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Φ^{n}^{−1}⌉ 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Φ^{n}^{−1}, 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).
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,…,⌈g⌉−1 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,…,⌈g⌉−1 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 x^{n} is a convex function for n>1, so that for all k we have g_{k}≤g 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 ⌈g⌉−1 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Φ^{n}^{−1}<1. Further, since ƒ(Φ)<Φ and ƒ is a concave function, g_{k}<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Φ^{n}^{−1}/2.
Suppose Φ and Φ^{n} are linearly dependent, i.e.
aΦ−bΦ^{n}+c=0 (a,b,c)≠(0,0,0), | (9) |
where b≠0 (since Φ is irrational) and w.l.o.g. a≥0. 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.
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 g≠1/b by Lemma 3, it remains to deal with the case a=1, g<1/b (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 x^{n} 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+t^{−}^{1})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)−t^{2}/(2×3)+t^{3}/(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 b≥2. Next, b−c<bΦ^{n}−c=Φ, hence b−c≤1 (since b,c are integers), hence c≥b−1. We show that, for a given b, the condition nΦ^{n}^{−1}=g<1/b is satisfied only when c=b−1. Since n, and therefore nΦ^{n}^{−1}, increases with c, it suffices to show that nΦ^{n}^{−1}>1/b when c=b. In this case
Φ^{n}^{−1}=1/b+1/Φ, n=ln(1+Φ/b)/lnΦ, |
so we have to prove (1+b/Φ)ln(1+Φ/b)>lnΦ. Since lnΦ<1, this follows from Lemma 4 with t=Φ/b.
Conversely, suppose c=b−1. To show that nΦ^{n}^{−1}<1/b, note that
Φ^{n}^{−1}=(Φ−1+b)/bΦ, n=ln(1+(Φ−1)/b)/lnΦ. |
Set t=(Φ−1)/b. Another short calculation shows that nΦ^{n}^{−1}<1/b is equivalent to λ(t)<ΦlnΦ/(Φ−1) = 1.2598…. Since t≤(Φ−1)/2 and λ((Φ−1)/2)=1.1406…, the result follows from Lemma 4.
Assuming then that Φ−bΦ^{n}+b−1=0, with 0<n<1 and b≥2, we have to show the Δ(k) are all 0. For k≥2 we have 1/k<Φ−1 and therefore, since ƒ(x)=x^{n} is a concave function when 0<n<1,
g_{k}<[ƒ(Φ)−ƒ(Φ−1/k)]/(1/k)<[ƒ(Φ)−ƒ(1)]/(Φ−1)=1/b. |
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.
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
kr=k√3=h+1/3+ε |
kƒ(r)=k3√3=3h+1+3ε |
where h is an integer and 0<ε<1/3.
We have u(k)=⌊kƒ(r)⌋=3h+1 and w(k)=⌊k(⌊kr⌋/k)^{3}⌋=⌊h^{3}/k^{2}⌋, so that Δ(k)=3 iff
3h−2≤h^{3}/k^{2}<3h−1. | (10) |
Define t=27k^{2}−(3h+1)^{2}. Then t>0 and t≡2 (mod 3). A routine calculation shows that the left-hand inequality in (10) is equivalent to
3(t−3)h≤2(t−1). |
If t≠2 then t≥5, hence h≤1, hence k√3<5/3, a contradiction. Hence if Δ(k)=3 then t=2.
Conversely, given positive integers h,k such that 27k^{2}−(3h+1)^{2}=2, it is easy to verify that ⌊k√3⌋=h, ⌊k3√3⌋=3h+1, and ⌊h^{3}/k^{2}⌋=3h−2, whence Δ(k)=3. To find such h,k consider the diophantine equation
27k^{2}−l^{2}=2. |
This has the obvious solution (k_{1},l_{1})=(1,5). From this and the solution to the Pell equation p^{2}−27q^{2}=1, viz. (p,q)=(26,5), one can generate all solutions in the usual way, by setting
(k_{i}_{+1},l_{i}_{+1})=(pk_{i}+ql_{i},27qk_{i}+pl_{i})=(26k_{i}+5l_{i},135k_{i}+26l_{i}). |
Clearly l_{i}_{+1}≡−l_{i} (mod 3), with l_{1}≡−1, so when i is even l_{i} has the form 3h+1 and Δ(k_{i})=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