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)