[math-fun] even Q(n)

30 Jul 2005

      rcs>RWG: Can your matrices of Q-products explain why Unequal-Partitions(N)
    has so many powers of 2 divisors?
Probably not.
  The most egregious values (from A&S table 24.5 on page 836) are Q(20) = 64,
  Q(34) = 512, Q(45) = 2048.
And Q(29) = 256.
  There are occasional odd Q(N), but no apparent pattern.

Q(n) = Q_even(n) + Q_odd(n).  In generating functions,

           n (n + 1)
    inf    ---------    inf
    ====       2       /===\
    \     q             | |    n
     >    ---------- =  | |  (q  + 1),
    /      (q; q)       | |
    ====         n     n = 1
    n = 0

with alternate terms of the sum generating Q_even and Q_odd.  But

Q_even(n) - Q_odd(n) = 1,  - 1,  - 1, 0, 0, 1, 0, 1, 0, 0, 0 ... = A010815,
the coeffs of
                  n (n + 1)
    inf           ---------    inf
    ====       n      2       /===\
    \     (- 1)  q             | |        n
     >    ----------------- =  | |  (1 - q ) 
    /          (q; q)          | |
    ====             n        n = 1
    n = 0

              2    5    7    12    15    22    26    35    40            A001318
  =  1 - q - q  + q  + q  - q   - q   + q   + q   - q   - q   + . . . = q        .

So this explains one power of 2, since Q_even(n) and Q_odd(n) are usually equal
(and never differ by > 1).  Note that Q_odd(51) = 2048, but Q(51) = 4097, since
51 is a generalized pentagonal number.

Further bisecting the generating series into oddly evenly many parts, etc,
failed to produce the near-equalities that might explain one more factor of 2.

But before we can explain this phenomenon, we need to quantify it, and
with larger n, it seems to taper off.  Based on n<2049, I conjecture only
only finitely many Q(n) < T(n)^4, where T(n):= the largest power of 2
dividing Q(n).  So we need a more modest estimate for T(n), which, for
large enough n, might wind up completely unremarkable.

Finally, while
                   [ inf                inf              ]
 inf               [ ====               ====             ]
/===\ [      k ]   [ \               n  \              n ]
 | |  [ 1   q  ]   [  >    Q    (n) q    >    Q   (n) q  ]
 | |  [        ] = [ /      even        /      odd       ]
 | |  [  k     ]   [ ====               ====             ]
k = 1 [ q   1  ]   [ n = 0              n = 0            ]
                   [                                     ]
                   [       vice              versa       ]

computes both g.f.s at once, you need 1000 terms, e.g., for Q(1000),
whereas you need only 22 for
                                             [    inf              ]
 inf  [          4 n + 1                 ]   [    ====             ]
/===\ [         q                    q   ]   [    \              n ]
 | |  [ -------------------------  ----- ]   [ 0   >    Q   (n) q  ]
 | |  [       2 n        2 n + 1   1 - q ] = [    /      odd       ].
 | |  [ (1 - q   ) (1 - q       )        ]   [    ====             ]
n = 1 [                                  ]   [    n = 0            ]
      [             0                1   ]   [                     ]
                                             [ 0         1         ]
--rwg
PS, Correction:  in an unsuccessful attempt to confuse him, I said
  Neil, you might want to add these G.f.s (and yesterday's A027193,A027193)
meaning ...193,A027187.
PPS, did RSA200 protect any squeamish ossifrage type sentiments?

[math-fun] even Q(n)

R. William Gosper