On 5/19/08, Fred lunnon <fred.lunnon@gmail.com> wrote:

CONJECTURE:

x o y = 3 x y - x [(y+1)/tau^2] - y [(x+1)/tau^2] .

PROOF: Presently skimped.

By overwhelming popular demand (thanks for the line in OEIS, NJAS!) I've finally been shamed into cobbling together a proof of the above --- spawning in the process another conjecture. Critical appraisal would be much appreciated, not to mention fulsome praise --- should any be forthcoming. WFL %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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 = x @ 3. 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 = \sum_i x_i F_{1+i} = x @ 2. 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. [The theorem proof depends implicitly upon the value of the circle product being independent of arbitrary redistribution of the coefficients, consistent with the Fibonacci reccurrence F_{k+2} - F{k+1} - F_k = 0, during computation --- see [Knu88]. This feature permits us temporarily to ignore the uniqueness constraint, and postponing consideration of the more significant parts w above, then simply cancelling them. By symmetry, it also implies associativity.] Is there a similar expression for x o y o z ? 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} . Conjecture: x @ y = x y - [(y+1)/phi^2] [(x+1)/phi^2] . (**) Via the relation x o y = (x o 1) @ y = (x @ 3) @ y the theorem above is implied easily by the conjecture. 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 [though evidently not by A000045, which --- amazingly --- gets it wrong]: 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]. Consequently d(x) = \sum x_k F_{k-2} represents the nearest integer to x/phi^2. Since d(x) is a non-decreasing integer function, the RHS 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. [Knu88] D. E. Knuth, Fibonacci multiplication, Appl. Math. Lett. 1 (1988), 57-60. Fred Lunnon (24 May 2008) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%