3
$\begingroup$

Does there exist some method for finding an analytic expression for the coefficient of $z_1^kz_2^kz_3^k$ in:

$$[(1+z_1)(1+z_2)(1+z_3)(1+z_1z_2)(1+z_1z_3)(1+z_2z_3)(1+z_1z_2z_3)]^{k}$$

or is it hopeless?

I can't think of any other method than trying to expand each factor.

Background: the above polynomial is the generating function for a system of linear equations in binary values (see this question).

For the simplest case of the coefficient of $z_1^kz_2^k$ in $[(1+z_1)(1+z_2)(1+z_1z_2)]^k$ I found the formula $\sum_{j=0}^k \binom{k}{j}^3$ at OEIS A000172.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ Taylor coefficient doesn't help? $\endgroup$
    – Ben McKay
    Commented Mar 26, 2022 at 16:51
  • 2
    $\begingroup$ $z_1=x,z_2=x^{12k},z_3=x^{(12k)^2}$ you must find the coeff of $x^{k+k\times 12k+k\times (12k)^2}$ $\endgroup$
    – Dattier
    Commented Mar 26, 2022 at 17:20
  • 3
    $\begingroup$ Note that if you can solve it without the last factor, then you can solve it with the last factor as well. The former starts as {4, 84, 2353, 74644, 2570504, 93417141, 3526418676, 136938227092} if my Mathematica is correct. $\endgroup$
    – Per Alexandersson
    Commented Mar 26, 2022 at 18:11
  • 1
    $\begingroup$ The OEIS Superseeker has no suggestions whatsoever, which is fairly discouraging. $\endgroup$
    – Peter Taylor
    Commented Mar 27, 2022 at 0:13
  • 1
    $\begingroup$ 5, 125, 4217, 163373, 6873505, 305304605, 14090295602, 669067354925, 32476460956025, 1604222480193625. Probably the asymptotic behaviour can be found. $\endgroup$
    – Brendan McKay
    Commented Mar 27, 2022 at 8:32

1 Answer 1

Reset to default
2
$\begingroup$

I was coming to the same conclusion that Brendan McKay posted in the comments at about the same time: the efficient way to calculate this is the direct approach $$\sum_{r,s,t,u} \binom{k}{r} \binom{k}{s} \binom{k}{t} \binom{k}{u} \binom{k}{k-r-s-u} \binom{k}{k-r-t-u} \binom{k}{k-s-t-u}$$ where the sum is over the support implicit in the binomial coefficients. (The way I conceptualise this sum is that if you expand $[(1+z_1z_2)(1+z_1z_3)(1+z_2z_3)]^k$ first as $\sum_{r,s,t} \binom{k}{r} \binom{k}{s} \binom{k}{t} (z_1 z_2)^r (z_1 z_3)^s (z_2 z_3)^t$ then you must take individual terms $z_1$, $z_2$, $z_3$ from the $(1+z_i)^k$ to balance them before you consider $(1+z_1 z_2 z_3)^k$.)

I've used the first 300 terms to do a brute-force search for a D-finite recurrence without finding one, so if there is a recurrence then either it's non-linear, it has non-polynomial coefficients, or it's enormous.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I also looked for a recurrence using 250 terms but no luck. $\endgroup$
    – Brendan McKay
    Commented Mar 30, 2022 at 5:22
  • $\begingroup$ Actually, there is a further space-time tradeoff: by pushing in e.g. the sum over $t$ a precalculation in $O(k^3)$ bigint multiplications of a table of $O(k^2)$ values allows the main calculation to be reduced to $O(k^3)$ bigint multiplications. $\endgroup$
    – Peter Taylor
    Commented Mar 30, 2022 at 12:01
  • $\begingroup$ I just multiplied the polynomials keeping only the terms needed. The $O(k^4)$ steps needed for particular $k=n$ gives all the answers for $k\le n$, so it isn't slower than $O(k^3)$ for each $k$ except by a constant. The method of summing over roots of unity modulo primes needs $O(k)$ small integers space and $O(k^4/\log k)$ operations (for one $k$). It has the advantage that all the operations are with small integers except for one application of CRT at the end, so it is hard to predict if it will be faster or slower. $\endgroup$
    – Brendan McKay
    Commented Mar 31, 2022 at 0:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .