Computerizing the Andrews-Fraenkel-Sellers Proofs on the Number of m-ary partitions mod m (and doing MUCH more!)

By Shalosh B. EKHAD and Doron ZEILBERGER

VERY IMPORTANT

As in all our joint papers, the main point is not the article, but the accompanying Maple package, that for the present article happens to be AFS.txt. It may be downloaded, free of charge, from the webpage of this article

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/afs.html ,

where the readers can also find sample input and output files, that they are welcome to extend using their own computers.

A Concise Rendition of the Work of Andrews, Fraenkel, and Sellers on the number of m-ary partitions mod m

In two delightful articles ([AFS1],[AFS2]), George Andrews, Aviezri Fraenkel, and Jim Sellers prove two results that are trivially equivalent to the following two propositions.

Proposition A ([AFS1], Theorem 2.1) Fix a positive integer m larger than 1. Let

B(q) = ∑_{i=0}^{∞} b(i) q^{i} ,

be the unique formal power series satisfying the functional equation

B(q) = \frac{1}{1 − q} B(q^{m}) ,  (F E1)

and let

b_{0}(n) := b(m n) .

Then b_{0}(n)(mod m) can be computed in logarithmic time via the recurrence (recall that, thanks to Euclid, every integer n can be written as n = mi + j, where i is the quotient and j (0 ≤ j < m) is the remainder)

b_{0}(mi + j) ≡ (j + 1) b_{0}(i) (mod m) .

Proposition B ([AFS2], Theorem 2.1) Fix a positive integer m larger than 1. Let

C(q) = ∑_{i=0}^{∞} c(i) q^{i} ,

be the unique formal power series satisfying the functional equation

C(q) = 1 + \frac{q}{1 − q} C(q^{m}) ,  (F E2)

and let

c_{1}(n) := c(mn + 1) .

Then c_{1}(n) (mod m) can be computed in logarithmic time via the recurrence (recall, that thanks to Euclid, every integer n can be written as n = mi + j, where i is the quotient and j (0 ≤ j < m) is the remainder)

c_{1}(mi + j) ≡ 1 + j c_{1}(i) (mod m) .

Comment: The original statement in [AFS2] regarded c_{0}(n) = c(mn) (rather than c_{1}(n) = c(mn + 1)) and was rather complicated. Since it is readily seen that c_{0}(n) = c_{1}(n − 1), our formulation is simpler.

The basic idea behind the proofs of these two propositions is brilliant, but the way the proofs are presented there are unnecessarily long. We will first present new renditions of their nice proofs, in a form that would make them amenable to formulate a general algorithm that can handle many other cases.

Definition: The m-sections of a formal power series, f(q), are the unique formal power series f_{0}(q), …, f_{m−1}(q) such that

f(q) = ∑_{i=0}^{m−1} q^{i} f_{i}(q^{m}) .

Remark: It is an elementary exercise in Linear Algebra to prove that if f(q) is a rational function, so are all the f_{i}(q)’s and it is routine to find them. Of course, one can use “averaging” over roots of unity, but it is not necessary.

Proof of Proposition A ([AFS1], streamlined by DZ) : Let us m-sect both sides of the defining functional equation and extract the part consisting of powers that are multiples of m

B_{0}(q^{m}) = [(\frac{1}{1 − q} )_{0} (q^{m})] · B(q^{m}) .  (F E1′)

But

(\frac{1}{1 − q} )_{0} (q^{m}) = ∑_{i=0}^{∞} q^{im} = \frac{1}{1 − q^{m}} .

Hence

B_{0}(q^{m}) = \frac{1}{1 − q^{m}} B(q^{m}) .  (F E1′)

Replacing q^{m} by q we get

B_{0}(q) = \frac{1}{1 − q} B(q) .  (F E1′′)

Plugging B(q) = (1 − q)B_{0}(q) into (F E1), we get

(1 − q)B_{0}(q) = \frac{1}{1 − q} (1 − q^{m})B_{0}(q^{m}) ,

and we get a functional equation for B_{0}(q)

B_{0}(q) = \frac{1 − q^{m}}{(1 − q)^{2}} B_{0}(q^{m}) .

Now take the partial fraction decomposition

\frac{1 − q^{m}}{(1 − q)^{2}} = \frac{m}{1 − q} + ∑_{j=0}^{m−1}(j + 1 − m)q^{j} .

Hence

B_{0}(q) ≡ ( ∑_{j=0}^{m−1}(j + 1)q^{j}) B_{0}(q^{m}) (mod m) ,

that is equivalent to the stated recurrence, by extracting the coefficient of q^{mi+j} = q^{j} · (q^{m})^{i} from both sides.

Proof of Proposition B ([AFS2], streamlined by DZ) : Now we take the f_{1}(q) part of both sides of (F E2), getting

q C_{1}(q^{m}) = (1)_{1} + q [ (\frac{q}{1 − q} )_{1} (q^{m}) ] · C(q^{m}) .  (F E2′)

Since (1)_{1} = 0 and (\frac{q}{1−q} )_{1} = ∑_{i=0}^{∞} q^{i} = \frac{1}{1−q}, we get

C_{1}(q^{m}) = \frac{1}{1 − q^{m}} C(q^{m}) .

Replacing q^{m} by q, we get

C_{1}(q) = \frac{1}{1 − q} C(q) ,

hence

C(q) = (1 − q) C_{1}(q) ,

that leads to the functional equation for C_{1}(q):

C_{1}(q) = \frac{1}{1 − q} + \frac{q(1 − q^{m})}{(1 − q)^{2}} C_{1}(q^{m}) .

Now take the partial fraction decomposition

\frac{q(1 − q^{m})}{(1 − q)^{2}} = \frac{m}{1 − q} + ∑_{j=0}^{m−1}(j − m)q^{j} .

Hence, taking it modulo m, we get,

C_{1}(q) ≡ \frac{1}{1 − q} + ( ∑_{j=0}^{m−1} j q^{j}) C_{1}(q^{m}) (mod m) ,

that is equivalent to the stated recurrence, by extracting the coefficient of q^{mi+j} = q^{j} · (q^{m})^{i} from both sides.

Let’s Generalize!

The Andrews-Fraenkel-Sellers method of proof (once compactified, as above) suggests an algorithm that tries to find poly-logarithmic-time (i.e. polynomial in the bit-size) schemes for the congruence class modulo m for the i-part in the m-section of any formal power series satisfying a functional equation of the form

f(q) = S(q) + R(q)f(q^{m}) ,

for any given rational functions S(q) and R(q) (whose denominators do not vanish at q = 0 so they are bona-fide formal power series, and R(0)S(0) = 0, in order there to be a solution) and any i between 0 and m − 1. Of course, now m, and i have to be specific, i.e. numeric, but if in luck, one can easily detect the general pattern in m (that can be conjectured and proved automatically).

The reason that things worked out so well in Propositions A and B above was that after the partial fraction decomposition, taking it modulo m, the rational function part disappeared and we were left with a polynomial on the right side of the functional equation for B_{0}(q) and C_{1}(q) modulo m. But why not try, and look for more miracles?

Algorithm

Inputs

• A positive integer m > 1 and a non-negative integer i, 0 ≤ i < m .

• Rational functions S(q) and R(q) whose denominators do not vanish at q = 0, and R(0)S(0) = 0.

Let F (q) be the unique formal power series that satisfies

F (q) = S(q) + R(q) F (q^{m}) .  (F E3)

Let F_{i}(q) be the i-th part in the m-section

F (q) = ∑_{i=0}^{m−1} q^{i}F_{i}(q^{m}) .

Output: A rational function E(q) and polynomial P (q) such that F_{i}(q) satisfies the fast functional equation, modulo m

F_{i}(q) ≡ E(q) + P (q) F_{i}(q^{m}) (mod m).

or else FAIL.

[Note that one can compute the coefficients of rational functions, modulo m, in logarithmic time.] Description First m-sect the functional equation (F E3) and extract the i-part

q^{i} F_{i}(q^{m}) = q^{i}S_{i}(q^{m}) + q^{i}R_{i}(q^{m}) F (q^{m}) .  (F E3′)

Note that the computer can easily compute the rational functions S_{i}(q), R_{i}(q), by the m-section procedure (implemented in procedure mSectR in BFF.txt). Divide by q^{i} and replace q^{m} by q, getting

F_{i}(q) = S_{i}(q) + R_{i}(q) F (q) .

Hence

F (q) = \frac{F_{i}(q) − S_{i}(q)}{R_{i}(q)} .

Plug this into (F E3), and get a brand-new functional equation for F_{i}(q). Suppose it is

F_{i}(q) = A(q) + G(q) F_{i}(q^{m}) ,  (F E4)

for some rational functions A(q) and G(q) that the computer can easily find. To wit:

A(q) = \frac{S (q) R_{i} (q) R_{i} (q^{m}) − R (q) R_{i} (q) S_{i} (q^{m}) + R_{i} (q^{m}) S_{i} (q) R_{i} (q^{m})}{R_{i} (q^{m})} ,

G(q) = \frac{R (q) R_{i} (q)}{R_{i} (q^{m})} .

Next perform the partial fraction decomposition of G(q):

G(q) = P urelyRationalP art(q) + P olynomialP art(q) .

If a miracle does happen, in other words, P urelyRationalP art(q) is a multiple of m, then, we get

F_{i}(q) ≡ A(q) + P olynomialP art(q) F_{i}(q^{m}) (mod m) ,

and we get a poly-logarithmic time way to compute the coefficients of F_{i}(q) modulo m. If the miracle does not happen, then we return FAIL. Another Miracle Proposition C Let c(n) be the number of partitions of n into parts that are either powers of m or twice powers of m, so the generating function

C(q) = ∑_{n=0}^{∞} c(n)q^{n} = ∏_{i=0}^{∞} \frac{1}{(1 − q^{m^{i}})(1 − q^{2m^{i}})} ,

satisfies the functional equation

C(q) = \frac{1}{(1 − q)(1 − q^{2})}C(q^{m}) .

Let d(n) := c(mn + m − 1) = c(m(n + 1) − 1), and let D(q) = ∑_{n=0}^{∞} d(n)q^{n} be its generating function. Then d(n) ( mod m) can be computed in logarithmic time, via

D(q) ≡ Nes(q)D(q^{m}) (mod m) ,

where, Nes(q) is the polynomial of q defined as follows. If m is odd, then

Nes(q) := (1 + q) ∑_{j=0}^{m−2} \binom{j + 2}{2}q^{2j} (mod m) ,

while if m is divisible by 4, then

Nes(q) := ∑_{j=0}^{m−3} A002623(j)(q^{j} + q^{2m−4−j})(mod m) ,

where (see [S]) A002623(j) = ⌊\frac{(j+2)(j+4)(2j+3)}{24}⌋. There are no miracles when m ≡ 2 (mod 4). Infinitely more miracles The reader can find a few more miracles in the sample output files given in the front of this article, mentioned above:

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/afs.html ,

and potentially infinitely more, by playing with the accompanying Maple package AFS.txt available from the above page, or directly from

http://www.math.rutgers.edu/~zeilberg/tokhniot/AFS.txt .

Conclusion Thomas Edison said that genius is %1 inspiration and %99 perspiration. Now that we have computers, they can do the perspiration part for us, but we need meta-inspiration, meta-geniuses, and meta-perspiration, to teach the human inspiration to our silicon colleagues. Sooner or later, computers will also do the inspiration part, but let humans enjoy the remaining fifty (or whatever) years left for them, and focus on inspiration, meta-inspiration, and meta-perspiration, and leave the actual perspiration part to their much faster- and much more reliable- machine friends.

Acknowledgment

We wish to thank Aviezri Fraenkel and George Andrews for stimulating conversations.

References

[AFS1] G.E. Andrews, A. S. Fraenkel, and J. A. Sellers, Characterizing the number if m-ary partitions modulo m, American Mathematical Monthly (2016), forthcoming.

[AFS2] G.E. Andrews, A. S. Fraenkel, and J. A. Sellers, m-ary partitions with no gaps: A characterization modulo m, Discrete Mathematics 339(2016), 283-287.

[S] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, www.oeis.org .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

zeilberg at math dot rutgers dot edu ; http://www.math.rutgers.edu/~zeilberg/ .

Shalosh B. Ekhad, c/o D. Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Exclusively published in The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger

( http://www.math.rutgers.edu/~zeilberg/pj.html) and arxiv.org .

Nov. 20, 2015