Notes on the Fibonacci circle and arroba products
_________________________________________________
THEOREM: (*)
Let x o y denote "circle" Fibonacci product (see A101330, A135090); then
x o y = 3 x y - x [(y+1)/phi^2] - y [(x+1)/phi^2]
where phi = (1 + \sqrt 5)/2, psi = (1 - \sqrt 5)/2,
[...] denotes floor function.
Proof:
Supposing x fixed and y varying, consider the forward differences
f(y) = x o z - x o y with z = y+1,
x o y = \sum_{i,j} x_i y_j F_{i+j},
x o z = \sum_{i,j} x_i z_j F_{i+j}.
Case y_2 = 0: for some k >= 0,
y = F_3 + F_5 + ... + F_{2k+1} + w,
z = F_2 + F_3 + F_5 + ... + F_{2k+1} + w = F_{2k+2} + w,
where w_i = 0 for i < 2k+4;
f(y) = \sum_{i,j} x_i (z_j - y_j) F_{i+j}
= \sum_i x_i (F_{2k+2+i} - F_{3+i} - F_{5+i} - ... - F_{2k+1+i})
= \sum_i x_i F_{2+i} = x o 1.
Case y_2 = 1: for some k >= 0,
y = F_2 + F_4 + ... + F_{2k} + w,
z = 2 F_2 + F_3 + F_5 + ... + F_{2k} + w = F_{2k+2} - F_1 + w,
where w_i = 0 for i < 2k+3;
f(y) = \sum_{i,j} x_i (z_j - y_j) F_{i+j}
= \sum_i x_i (F_{2k+2+i} - F_{1+i} - 2 F_{2+i} - F_{4+i} - ... - F_{2k+i})
= \sum_i x_i (F_{3+i} - F_{2+i}) = x o 2 - x o 1
Summing and collecting,
x o y = \sum_{0 < z < y} f(y)
= \sum_{0 < z < y} (1 - z_2)(x o 1) + (z_2)(x o 2 - x o 1)
= (y - g(y))(x o 1) + g(y)(x o 2 - x o 1)
= y (x o 1) + g(y)(x o 2 - 2(x o 1)),
where we define g(z) = \sum_{0 < z < y} z_2.
This is further simplified by iteration on x o 2 and x o 1 thus
x o 1 = 1 o x = x 1o1 + g(x)(1o2 - 2 1o1) = 3 x - g(x),
x o 2 = 2 o x = x 2o1 + g(x)(2o2 - 2 2o1) = 5 x - 2 g(x)
(see A026274, A101345); substituting above,
x o y = 3 x y - x g(y) - y g(x)
[note the expected symmetry in x,y].
To eliminate g(z), it is shown in the lemma (*****) below that
z_2 = [(z+2)/phi^2] - [(z+1)/phi^2],
where z_2 denotes the least significant base-F digit of z;
summing,
g(z) = \sum_{0 < z < y} z_2 = [(z+1)/phi^2]
(see A003849, A060144: final digit and sum properties omitted from OEIS!);
substituting, finally
x o y = 3 x y - x [(y+1)/phi^2] - y [(x+1)/phi^2], QED.
A related operation is obtained by dropping the two initial zeros (see A101646),
christened here the "arroba" product
x @ y = \sum_{i,j} x_i y_j F_{i+j-2} .
THEOREM: (**)
x @ y = x y - [(y+1)/phi^2] [(x+1)/phi^2] .
Proof: Along the same lines as the proof of (*), except that F_k etc. is
replaced in the products by F_{k-2}. Redefining the forward difference
f(y) = x @ (y+1) - x @ y
we find similarly
f(y) = x @ 1 when y_2 = 0,
f(y) = (x @ 2) - (x @ 1) when y_2 = 1;
x @ y = y (x @ 1) + g(y)(x @ 2 - 2(x @ 1))
with g(y) as before; in particular
x @ 1 = x 1@1 + g(x)(1@2 - 2 1@1) = x,
x @ 2 = x 2@1 + g(x)(2@2 - 2 2@1) = 2 x - g(x);
substituting in the above,
x @ y = x y - g(x) g(y), QED.
Notice that the rows (or columns) of the table for x o y constitute a subset
of those for x @ y, in view of the relation x o y = w @ y where
w = (x o 1) = (x @ 3),
x = g(w),
and
g(y) = \sum_{z < y} z_2 = [(y+1)/phi^2] = \sum y_k F_{k-2};
these matters are explicated in the proof of lemma (*****).
Also immediately from this last and the definitions
x @ y = g(x o y) .
A short table of these relations:
g(w) = 0__0__1__1__1__2__2__3__3__3__4__4__4__5__5__6__6__6__7__7__8
w = 0__1__2__3__4__5__6__7__8__9_10_11_12_13_14_15_16_17_18_19_20
w o 1 = 0__3__5__8_11_13_16_18_21_24_26_29_32_34_37_39_42_45_47_50_52
Knuth [Knu88] shows that
x o y o z = \sum_{i,j,k} x_i y_j z_k F_{i+j+k},
irrespective of intermediate reductions to base-F (Zeckendorf) form taking
place during the computation; by symmetry, this property implies associativity
(x o y) o z = x o (y o z).
However associativity fails for x @ y --- for instance at
x = 7, y = 4, z = 4,
we find the three possible products take distinct values
(x @ y) @ z = 91, x @ (y @ z) = 87, x @ y @ z = 90.
[Knu88]
D. E. Knuth, Fibonacci multiplication, Appl. Math. Lett. 1 (1988), 57-60.
A symmetric expression analogous to (*) for (x o y) o z would provide an
alternative proof of Knuth's associativity. Rather surprisingly --- given
the impossibility of any such analogue for x @ y --- we have
THEOREM: (***)
(x o y) o z = x o (y o z) = x o y o z = 8 x y z
- 3 (x' y z + x y' z + x y z') + (x y' z' + x' y z' + x' y' z)
where
x' = g(x) = [(x+1)/phi^2],
y' = g(y) = [(y+1)/phi^2],
z' = g(z) = [(z+1)/phi^2].
Proof: by (*)
x o y = 3 x y - x y' - y x' ;
iterating,
(x o y) o z = (3 x y - x y' - y x')(3 z - z') - z g(x o y)
= 9 x y z - 3 y z x' - 3 x z y' - 3 x y z'
+ x y' z' + y x' z' - z (x @ y)
since g() downshifts by two base-F places, as mentioned earlier
= 9 x y z - 3 y z x' - 3 x z y' - 3 x y z'
+ x y' z' + y x' z' - x y z + z x' y'
by (**), and the result follows by symmetry, QED.
Having nothing better to do, we might now continue in a similar way, computing
x o y o z o w = 21 (x y z w) - 8 (x y z w' + ...)
+ 3 (x y z' w' + ...) - 1 (x y' z' w' + ...) + 0 (x' y' z' w');
x o y o z o w o v = 55 (x y z w v) - 21 (x y z w v' + ...)
+ 8 (x y z w' v' + ...) - 3 (x y z' w' v' + ...)
+ 1 (x y' z' w' v' + ...) - 0 (x' y' z' w' v');
and in general for the circle product of n variables x^1, ..., x^n,
THEOREM: (****)
x^1 o x^2 o ... o x^n = \sum_{0 <= m <= n} (-1)^(n-m) F_{2m}
\sum_{n_C_m} x^1 x^2 ... x^m x^{m+1}' ... x^n'
where the inner sum ranges over all monomials with m undashed and n-m dashed
variables; and the coefficients are alternate Fibonacci numbers depending
(apart from sign) only on m.
Proof by induction: already known for n = 0,1,2; assuming for n variables,
x^1 o ... o x^n
= \sum_m (-1)^(n-m) F_{2m} \sum x^1 x^2 ... x^m x^{m+1}' ... x^n'
= \sum_m [(-1)^(n-m-1) F_{2m+2} x^n + (-1)^(n-m) F_{2m} x^n']
\sum x^1 x^2 ... x^m x^{m+1}' ... x^{n-1}'
Replacing via (*) and (**) each occurrence of
x^n by y o z = 3 y z - y z' - y' z,
x^n' by y @ z = y z - y' z',
where finally y = x^n, z = x^{n+1}:
x^1 o ... o x^n o x^{n+1} = x^1 o ... o (y o z)
= \sum_m [(-1)^(n-m-1) F_{2m+2} (3 y z - y z' - y' z)
+ (-1)^(n-m) F_{2m} (y z - y' z')]
\sum x^1 x^2 ... x^m x^{m+1}' ... x^{n-1}'
= \sum_m (-1)^(n+1-m)(3 F_{2m-2} - F_{2m-4})
\sum x^1 x^2 ... x^m x^{m+1}' ... x^{n+1}'
= \sum_m (-1)^(n+1-m) F_{2m} \sum x^1 x^2 ... x^m x^{m+1}' ... x^{n+1}'
as required, noticing that terms in y', z', y'z' previously missing from the
inner sum have explicitly been supplied. QED.
LEMMA: (*****)
x_2 = [(x+2)/phi^2] - [(x+1)/phi^2] = RP(x) say,
where x_2 denotes the least-significant nontrivial digit of x in base-F.
Proof: Note that
phi + psi = - phi psi = 1;
phi^k = F_k phi + F_{k-1} .
The explicit formula below for Fibonacci numbers should be well known:
F_k = (phi^k - psi^k)/sqrt5
[proved by showing that the RHS also satisfies F_{k+2} - F{k+1} - F_k = 0, etc].
So F_k/phi^2 - F_{k-2}
= (phi^{k-2} - psi^{k+2} - phi^{k-2} + psi^{k-2})/sqrt5
= psi^k (phi^2 - phi^{-2})/sqrt5 = psi^k;
and letting x = \sum_{k>=2} x_k F_k as usual,
x/phi^2 - \sum x_k F_{k-2}
= \sum x_k (F_k/phi^2 - F_{k-2})
= \sum x_k psi^k = e(x), say
which lies in the range
-1/phi^2 <= e(x) <= 1/phi .
[The extreme values occur when x_k = 1,0 for k odd,even, or vice-versa;
then sum the geometric progressions.
Incidentally, the integer term here is
\sum x_k F_{k-2} = [(x+1)/phi^2] = g(x)
above; similarly it may be shown that
x*phi^2 - \sum x_k F_{k+2} = -e(x);
\sum x_k F_{k-1} = [(x+1)/phi] = x - g(x),
although we don't need these here.]
Now we have x/phi^2 = g(x) + e(x), where g(x) is a non-decreasing integer
function, and e(x) lies in a unit interval. So RP(x) will be 1 just when
e(x+1) < 0 and e(x+2) > 0; and e(x) will be positive when the least k for
which x_k = 1 is even, negative when odd, zero when x = 0.
[Base-F representations are rendered x = (x_0 x_1) x_2 x_3 ... below.]
Case x_2 = 0, x_3 = 1:
x = (00)0101...0100...,
x+1 = (00)0000...0010...,
x+2 = (00)1000...0010...;
so e(x+1) > 0, e(x+2) > 0, and RP(x) = 0.
Case x_2 = 0, x_3 = 0:
x = (00)001010...100...,
x+1 = (00)101010...100...,
x+2 = (00)000000...010...;
so e(x+1) > 0, e(x+2) < 0, and RP(x) = 0.
Case x_2 = 1, x_3 = 0:
x = (00)1010...100...,
x+1 = (00)0000...010...,
x+2 = (00)1000...010...;
so e(x+1) < 0, e(x+2) > 0, and RP(x) = 1.
This covers all nonzero cases; the case x = 0 being trivial, we have shown
that x_2 = RP(x) for all natural x, QED.
Fred Lunnon (28 May 2008)