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)