[math-fun] iterated integer part
On 5/24/08, Fred lunnon <fred.lunnon@gmail.com> wrote:
[There must be something about this expression --- the version below is/was wrong in OEIS too!]
Apologies to OEIS --- the Fibonacci formula _is_ correct there --- I just need a new pair of spectacles --- or maybe a new pair of eyes --- new brain --- witter, witter ... Speaking of which --- coincidentally with RCS revealing unsuspected depths in the intger part function --- I've turned up a number of apparently elementary identities for which I can discover no obvious proof technique. The following example [occurring in the investigation of the "shifted down 2" variation of the Knuth circle product] is typical: for integer x, x - [[x/tau^2 + 1/tau^2]*tau^2 + 1/tau] = ( - ([(x+3)*tau^2] - 2*[(x+2)*tau^2] + [(x+1)*tau^2]) )mod 3 - 1 The sequence concerned, starting from x = 0, is 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, 0, 1, ... The second expression is much easier to deal with than the first, since the iterated integer part has been eliminated. But why are the two equal? Fred Lunnon
On 5/25/08, Fred lunnon <fred.lunnon@gmail.com> wrote:
Speaking of which --- coincidentally with RCS revealing unsuspected depths in the intger part function --- I've turned up a number of apparently elementary identities for which I can discover no obvious proof technique. The following example [occurring in the investigation of the "shifted down 2" variation of the Knuth circle product] is typical: for integer x,
x - [[x/tau^2 + 1/tau^2]*tau^2 + 1/tau]
= ( - ([(x+3)*tau^2] - 2*[(x+2)*tau^2] + [(x+1)*tau^2]) )mod 3 - 1
The sequence concerned, starting from x = 0, is
0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, 0, 1, ...
The second expression is much easier to deal with than the first, since the iterated integer part has been eliminated. But why are the two equal?
PS As previously, tau = (1 + sqrt(5))/2 and [...] denotes floor function. WFL
You might begin by changing powers of tau into a*tau+b, and moving everything that identifiably an integral term outside the floor brackets. I doubt that's the whole answer, but it could simplify your problem. Rich ---------- Quoting Fred lunnon <fred.lunnon@gmail.com>:
On 5/25/08, Fred lunnon <fred.lunnon@gmail.com> wrote:
Speaking of which --- coincidentally with RCS revealing unsuspected depths in the intger part function --- I've turned up a number of apparently elementary identities for which I can discover no obvious proof technique. The following example [occurring in the investigation of the "shifted down 2" variation of the Knuth circle product] is typical: for integer x,
x - [[x/tau^2 + 1/tau^2]*tau^2 + 1/tau]
= ( - ([(x+3)*tau^2] - 2*[(x+2)*tau^2] + [(x+1)*tau^2]) )mod 3 - 1
The sequence concerned, starting from x = 0, is
0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, 0, 1, ...
The second expression is much easier to deal with than the first, since the iterated integer part has been eliminated. But why are the two equal?
PS As previously, tau = (1 + sqrt(5))/2 and [...] denotes floor function. WFL
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Fred Lunnon wrote:
for integer x,
x - [[x/tau^2 + 1/tau^2]*tau^2 + 1/tau]
= ( - ([(x+3)*tau^2] - 2*[(x+2)*tau^2] + [(x+1)*tau^2]) )mod 3 - 1
The sequence concerned, starting from x = 0, is
0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, 0, 1, ...
The second expression is much easier to deal with than the first, since the iterated integer part has been eliminated. But why are the two equal?
PS As previously, tau = (1 + sqrt(5))/2 and [...] denotes floor function. WFL
I'm not sure whether Fred's saying "I believe this but don't have a proof" or "I have a proof but it doesn't give any insight". In case it's the former, here's a proof that doesn't give very much insight. I suspect there's some coincidence at work here. So, the mod 3 thing is happening (in some sense) because 1/tau^2 = 3-tau^2, which lets us convert between tau^2 and 1/tau^2 at the cost of working mod 3. Let's deal with that bit first. For brevity write T for tau and y = x+1. So your identity is y - [T^2[y/T^2]+1/T] = - [T^2(y+2)] + 2[T^2(y+1)] - [T^2y] (mod 3). Since T^2 = 3-1/T^2, the RHS is congruent mod 3 to - [(3-1/T^2)(y+2)] + 2[(3-1/T^2)(y+1)] - [(3-1/T^2)y] or to - [-(y+2)/T^2] + 2[-(y+1)/T^2] - [-y/T^2] or to - [-(y+2)/T^2] - [-(y+1)/T^2] - [-y/T^2]. So much for the RHS, for now. We've made everything on both sides involve terms like y/T^2, and made the RHS more uniform. Now, what about the LHS? Since 1/T = T^2-2 it equals y - [T^2[y/T^2]+T^2] + 2 = y - [T^2(y/T^2-{y/T^2})+T^2] + 2 = y - [y-T^2{y/T^2}+T^2] + 2 = - [T^2-T^2{y/T^2}] + 2 = - [T^2{-y/T^2}] + 2 and now it looks like we no longer care that y is an integer and should write z = -y/T^2, so that we're trying to prove - [T^2{z}] + 2 = - [z-2/T^2] - [z-1/T^2] - [z] (mod 3) or, reducing the number of minus signs, [T^2{z}] - 2 = [z-2/T^2] + [z-1/T^2] + [z] (mod 3). This is now routine. The RHS is clearly unaltered when z changes by an integer, so let's write h = {z}, so that 0 <= h < 1, and the identity is now [T^2h] - 2 = [h-2/T^2] + [h-1/T^2] + [h] (mod 3). So now: 0 <= h < 1/T^2: LHS = -2; RHS = -1+-1+0 = -2 1/T^2 <= h < 2/T^2: LHS = -1; RHS = -1+0+0 = -1 2/T^2 <= h < 1: LHS = 0; RHS = 0+0+0 = 0 as required. (In some woolly sense the RHS is three terms of an infinite series but we don't need any more terms because h is always rather small. Or something like that.) -- g
On 5/26/08, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
Fred Lunnon wrote:
for integer x,
x - [[x/tau^2 + 1/tau^2]*tau^2 + 1/tau]
= ( - ([(x+3)*tau^2] - 2*[(x+2)*tau^2] + [(x+1)*tau^2]) )mod 3 - 1
The sequence concerned, starting from x = 0, is
0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, -1, 0, 1, 0, 1, -1, 0, 1, 0, 1, ...
The second expression is much easier to deal with than the first, since the iterated integer part has been eliminated. But why are the two equal?
PS As previously, tau = (1 + sqrt(5))/2 and [...] denotes floor function. WFL
I'm not sure whether Fred's saying "I believe this but don't have a proof" or "I have a proof but it doesn't give any insight". In case it's the former, here's a proof that doesn't give very much insight. I suspect there's some coincidence at work here.
The proof I had relied on background "physics" which seemed to me unecessarily indirect. I had this feeling that there ought to be some method of dealing with such expressions that didn't rely on the special properties of tau. But I think your heroic computation confirms that these identities really are special, and there is (probably) no simple-minded algorithm for them. Sadly, in this particular case it eventually dawned on me to desist from trying to iterate the floor function, and instead replace [(x+1)/tau^2] by another variable --- at which point everything in my top-level expression cancels nicely, without any misdirected attempt at "simplification". C'est la vie. WFL
Fred Lunnon wrote:
But I think your heroic computation confirms that these identities really are special, and there is (probably) no simple-minded algorithm for them.
Yes, I agree.
Sadly, in this particular case it eventually dawned on me to desist from trying to iterate the floor function, and instead replace [(x+1)/tau^2] by another variable --- at which point everything in my top-level expression cancels nicely, without any misdirected attempt at "simplification".
That's pretty much what I ended up doing too :-). -- g
On 5/26/08, Fred lunnon <fred.lunnon@gmail.com> wrote:
On 5/26/08, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
I'm not sure whether Fred's saying "I believe this but don't have a proof" or "I have a proof but it doesn't give any insight". In case it's the former, here's a proof that doesn't give very much insight. I suspect there's some coincidence at work here.
The proof I had relied on background "physics" which seemed to me unecessarily indirect. I had this feeling that there ought to be some method of dealing with such expressions that didn't rely on the special properties of tau. But I think your heroic computation confirms that these identities really are special, and there is (probably) no simple-minded algorithm for them.
Looking at my notes, I realise this claim was false --- the background had merely enabled me to guess the identity --- I had no proof, and no idea how to go about finding one. [But now I do --- just ask Gareth!] WFL
participants (3)
-
Fred lunnon -
Gareth McCaughan -
rcs＠xmission.com