0

Consider a polynomial, with positive integer coefficients and exponents, which is deficient in some powers. Further assume that it has a constant term and the $gcd$ of the exponents present is 1. When that polynomial is raised to some positive power, $n$, it may or may not be deficient in some powers. e.g. $1+x+x^3+x^4$ is missing a square term, but after squaring all terms through order 8 will be present.

It is my observation that if $x$ is present in the polynomial then deficiencies will persist until the polynomial is raised to the power of $n=e_2-1$ where $e_2$ is the 2nd largest exponent after 1, e.g. in $(1+x)(1+x^6)(1+x^{11})$ all powers will be present after raising to the 5th power (since $e_2=6$).

But for a polynomial that does not contain an $x$ term, there will be persistent (but predictable) deficiencies past a given value of $n$. e.g. for $(1+x^2)(1+x^7)(1+x^{11})$ at $n=6$ the 115 powers present are {0; 2; 4; 6-114; 116; 118; 120} and at $n=7$ there are 20 more powers present, their values being {0; 2; 4; 6-134; 136; 138; 140}; there are 20 more added in a regular way for each larger value of $n$.

The binomial and multinomial coefficients $c_k$ can be computed easily to give the coefficient of a given power $x^k$, but is there a way to know if a given power will be present in the exponentiated polynomial? (This is similar to the question posed here about polynomial multiplication. Lacking that, is there a way to predict the minimum value of $n$ from which the the powers present in the exponentiated polynomial is predictable? I am guessing that there is no way to know what powers are present below this threshold since this is related to the subset-sum problem to which I added related comments here. More specific descriptions of this general problem are also welcome -- I am not sure what to call this branch of inquiry.

smichr
  • 359
  • Suppose that your polynomial looks like $f(x)=1+c_1x^{e_1}+c_2x^{e_2}+\dots+c_kx^{e_r}$, for certain integers $1\le e_1<e_2<\dots<e_r$, and arbitrary positive constants $c_1,\dots,c_r$. Determining whether $x^n$ appears in $[f(x)]^k$ is equivalent to asking if you can make change for $n$ cents in a money system with coins in denominations $e_1,e_2,\dots,e_r$. Therefore, your problem is related to the Frobenius coin problem. – Mike Earnest Jun 07 '22 at 19:08
  • The difference that I see is that the FCP will answer what the largest sum that cannot be made. I think this will give the last gap that appears before the largest continuous range in the "stable exponent structure" which occurs at minimum n that I discussed at the link. So if I could relate FCP with minimum n, that would be very close to the answer because the structure of the exponents is symmetric, so if we know how the head of the sequence (below the continuous region) we would also know the tail. – smichr Jun 07 '22 at 20:18

1 Answers1

1

Let $s$ be the sum of the number of times each exponent must be used to make a given value -- the coin change problem as pointed out by Mike. For example, making 40 from exponents in [5,7,13] can be done in 4 ways: [[0, 2, 2], [1, 5, 0], [4, 1, 1], [8, 0, 0]]; the first case, [0,2,2], represents getting 40 as $2 \cdot 7 + 2 \cdot 13$ and has $s = 2 + 2 = 4$. All the values of $s$ for this case of 40 are [4,6,6,8]. So, the term $x^{40}$ will not appear until $n=4$ in $(a + bx^5 + c x^7 + x^{13})^n$. A fourth order polynomial describes the coefficient of $x^{40}$ for $n \in {4,5}$, then a 6th order polynomial describes it for $n \in {6,7}$ and then an 8th order polynomial describes the coefficient for $n \ge 8$. Let $c_{40,n}$ be the coefficient of $x^{40}$ in $f = (2 + 3x^5 + x^7 + x^{13})^n$; $c_{40,n \lt 4} = 0$; $c_{40,n\in{4,5}} = 2^n n(n - 3)(n - 2)(n - 1)/64$; $c_{40,n\in{6,7}} = c_{40,n\in{4,5}}(17n^2 - 153n + 345)/5$; and, finally, $c_{40,n \ge 8}=c_{40,n\in{4,5}}(729n^4 - 16038n^3 + 191419n^2 - 1013454n + 1848840)/17920$. e.g. for $n=100$ the coefficient of $x^{40}$ is 6103517920798768523028054546878748111667200.

So the "coin problem" is a guide for the missing exponents problem

  • an exponent will be missing if it's value cannot be made from any combination of the exponent "coins" in the base being raised to the power of $n$; the largest small missing exponent will have value equal to the Frobenius number of the exponents (and each small missing exponent $e$ will have a missing large value that is $dn - e$ where $d$ is the degree of the polynomial being raised to the $n$th power
  • an exponent will first appear when $n$ is equal to the smallest number of exponents needed to make its value (4 for the case of 40 given above)
  • a polynomial in $n$ giving the coefficient of $x^m$ will be fixed for $n$ greater than the largest number of exponents needed to make $m$ (8 for the case of 40 above)

I am not yet sure of the criteria to give the value of $n$ at which the structure of the exponents becomes predictable (as present in the Question).

smichr
  • 359