Many of you may remember the spectacularly ill-conditioned "Filbert" matrix
pointed out to me by Peter ("Feathers") Groot in the late 60s: E.g.,
(c89) (genmatrix(lambda([i,j],1/fib(i+j+9)),3),%% = float(%%))
[ 1 1 1 ]
[ -- --- --- ]
[ 89 144 233 ]
[ ] [ 0.01124 0.00694 0.00429 ]
[ 1 1 1 ] [ ]
(d89) [ --- --- --- ] = [ 0.00694 0.00429 0.00265 ]
[ 144 233 377 ] [ ]
[ ] [ 0.00429 0.00265 0.00164 ]
[ 1 1 1 ]
[ --- --- --- ]
[ 233 377 610 ]
Contrary to appearance, this is good to six figures:
(c90) 1/%;
[ 89 144 233 ] [ 89.0 144.0 233.0 ]
[ ] [ ]
(d90) [ 144 233 377 ] = [ 144.0 233.0 377.0 ]
[ ] [ ]
[ 233 377 610 ] [ 233.0 377.0 610.0 ]
But
(c91) float(map('invert,d89))
[ 1.0019e+11 2.62304e+11 - 6.86715e+11 ]
[ ]
(d91) [ 2.62304e+11 6.86691e+11 - 1.79782e+12 ] =
[ ]
[ - 6.86715e+11 - 1.79782e+12 4.70676e+12 ]
[ 5.01351e+7 1.44257e+8 - 3.64668e+8 ]
[ ]
[ 1.3994e+8 3.67339e+8 - 9.60738e+8 ]
[ ]
[ - 3.57682e+8 - 9.72036e+8 2.50923e+9 ]
The disagreement is even *more* dramatic if the floating numbers on the rhs of
d89 are first converted to exact rationals, and the inversion performed exactly!
The reason is that the matrix is far closer than 10^-6 to being singular,
and truncation to six figures pushes it way over the brink. The true inverse
is symmetric and integer.
I tried substituting a couple of candidates for q-Fibonaccis to see if inverting
made huge q-polynomials. It is tempting to define
qib(0):=0, qib(1):=1,
n - 2
qib(n) = qib(n - 1) + q qib(n - 2)),
for then
n 1
floor(- - -)
2 2
==== 2
\ k
qib(n) = > qbn(n - k - 1, k) q
/
====
k = 0
where qbn is the q-binomial coefficient
(q; q)
n
qbn(n, k) = -------------------.
(q; q) (q; q)
k n - k
Then, thru qib(11)
0
1
1
1 + q
2
1 + q + q
2 3 4
1 + q + q + q + q
2 3 4 5 6
1 + q + q + q + 2 q + q + q
2 3 4 5 6 7 8 9
1 + q + q + q + 2 q + 2 q + 2 q + q + q + q
4 6 2 3 4 5 6
(1 + q + q ) (1 + q + q + q + q + q + q )
4 2 3 4 5 6 7 8 9 10
(1 + q ) (1 + q + q + q + q + q + 2 q + 2 q + 2 q + 2 q + q
11 12
+ q + q )
2 3 4 2 3 4
(1 - q + q - q + q ) (1 + q + q + q + q )
4 5 6 7 8 9 10 11 12
(1 + q + q + q + q + q + q + q + q + q + q )
2 3 4 5 6 7 8 9 10
1 + q + q + q + 2 q + 2 q + 3 q + 3 q + 4 q + 5 q + 5 q
11 12 13 14 15 16 17 18
+ 5 q + 6 q + 6 q + 6 q + 6 q + 6 q + 5 q + 5 q
19 20 21 22 23 24 25
+ 4 q + 4 q + 3 q + 2 q + q + q + q
and qib(oo) is defined and equal to
inf
====
\ A003114(n) 1
> q = -----------------------------------
/ oo
==== /===\
n = 0 | | 5 n + 1 5 n + 4
| | (1 - q ) (1 - q )
| |
n = 0
oo 2
==== n
\ q
= > -------,
/ (q; q)
==== n
n = 0
the famous Rogers-Ramanujan function. But this qib definition produces messy
denominators in the Filbert matrix, and worse, fails to distribute over gcd,
f(gcd(n,k)) = gcd(f(n),f(k)),
unlike f:= vanilla fib.
Defining instead qfb[0] := 0, qfb[1] := 1, qfb[n] := qfb[n-1] + q qfb[n-2]
(A011973) answers these objections:
0 0
1 1
2 1
3 1 + q
4 1 + 2 q
2
5 1 + 3 q + q
6 (1 + q) (1 + 3 q)
2 3
7 1 + 5 q + 6 q + q
2
8 (1 + 2 q) (1 + 4 q + 2 q )
2 3
9 (1 + q) (1 + 6 q + 9 q + q )
2 2
10 (1 + 3 q + q ) (1 + 5 q + 5 q )
2 3 4 5
11 1 + 9 q + 28 q + 35 q + 15 q + q
2
12 (1 + q) (1 + 2 q) (1 + 3 q) (1 + 4 q + q )
2 3 4 5 6
13 1 + 11 q + 45 q + 84 q + 70 q + 21 q + q
2 3 2 3
14 (1 + 5 q + 6 q + q ) (1 + 7 q + 14 q + 7 q )
Note that the degree of qfb[n] is floor((n-1)/2), and qfb[2 p] =
qfb[p] times a polynomial of equal degree which is 1 mod p.
We also have the pleasant addition formula
[ qfb qfb ] [ qfb qfb ]
[ k + 1 k ] [ 1 0 ] [ n + 1 n ]
[ ] . [ ] . [ ] =
[ qfb qfb ] [ 0 q ] [ qfb qfb ]
[ k k - 1 ] [ n n - 1 ]
[ qfb qfb ]
[ n + k + 1 n + k ]
[ ].
[ qfb qfb ]
[ n + k n + k - 1 ]
Note that this contradicts the assertion F(n+m,x) = F(m,x)*F(n,x)
+ F(m-1,x)*F(n-1,x) in the A011973 article.
And the q-Filbert inverse contains satisfyingly huge polynomials divided by
mere monomial powers of q. (It looks possible to guess the general form,
which will probably require q-"superfactorials", i.e. q-extensions of
1^1 2^2 3^3 ... n^n or 1! 2! 3! ... n!.)
Finally, analogous to the Stirling polynomials, one can form an interesting
sequence by dividing out the predictable (by gcd thm) factors of qfb[n]:
1 1
2 1
3 1 + q
4 1 + 2 q
2
5 1 + 3 q + q
6 1 + 3 q
2 3
7 1 + 5 q + 6 q + q
2
8 1 + 4 q + 2 q
2 3
9 1 + 6 q + 9 q + q
2
10 1 + 5 q + 5 q
2 3 4 5
11 1 + 9 q + 28 q + 35 q + 15 q + q
2
12 1 + 4 q + q
2 3 4 5 6
13 1 + 11 q + 45 q + 84 q + 70 q + 21 q + q
2 3
14 1 + 7 q + 14 q + 7 q
2 3 4
15 1 + 9 q + 26 q + 24 q + q
2 3 4
16 1 + 8 q + 20 q + 16 q + 2 q
2 3 4 5 6 7 8
17 1 + 15 q + 91 q + 286 q + 495 q + 462 q + 210 q + 36 q + q
2 3
18 1 + 6 q + 9 q + 3 q
2 3 4 5 6 7
19 1 + 17 q + 120 q + 455 q + 1001 q + 1287 q + 924 q + 330 q
8 9
+ 45 q + q
2 3 4
20 1 + 8 q + 19 q + 12 q + q
2 3 4 5 6
21 1 + 13 q + 64 q + 146 q + 148 q + 48 q + q
2 3 4 5
22 1 + 11 q + 44 q + 77 q + 55 q + 11 q
2 3 4 5 6 7
23 1 + 21 q + 190 q + 969 q + 3060 q + 6188 q + 8008 q + 6435 q
8 9 10 11
+ 3003 q + 715 q + 66 q + q
2 3 4
24 1 + 8 q + 20 q + 16 q + q
2 3 4 5 6 7
25 1 + 20 q + 170 q + 800 q + 2275 q + 4003 q + 4280 q + 2605 q
8 9 10
+ 775 q + 75 q + q
. . .
2 3 4
30 1 + 7 q + 14 q + 8 q + q
--rwg
PS: 4 2 %i %pi k
==== ----------
\ 1/5 5
> sqrt(8 - 7 %e )
/
====
k = 0
1 1/5 3/5 1 1/5 2/5
2 (------- + 1) 7 (7 + 3) (1 - -------) (7 + 2) 7
sqrt(5) sqrt(5) 2
= ------------------------------- + ----------------------------- + -
sqrt(5) sqrt(5) 5
~ 14.1420530099223
