Polynomials with small coefficients

(David here!)

I wanted to talk about a problem I encountered in 2020 during Putnam seminar, and the subsequent exploration I did on it. It's still unresolved but I hope my thought processes could help those who are interested in understanding how to propose problems.

(IMC 2001/4) A polynomial is bipolar if its non-zero cofficients are $\pm 1$. Suppose $(x-1)^k$ divides a bipolar polynomial of degree $n-1$. Show that for any prime $q$ where \[\frac{q}{\log q} < \frac{k}{\log n},\] $x^q-1$ also divides the polynomial.

Let's dissect what this says. For any $q$, once a high enough power of $(x-1)$ divides our bipolar polynomial, then we are forced to also have $x^q-1$ divide it. As an example, when $q=2$, if $(x-1)^{10}$ divides a bipolar polynomial of degree at most 30, then it forces $x^2-1$ to also divide it. Spooky!

Solution Sketch. As with any problem with integer restrictions, it turns out that the culprit is something number-theoretic.

Let our bipolar polynomial be $P(x)$. Substitute $x=\omega$, a $q$-th root of unity $\omega$. Then, the divisibility tells us that \[(1-\omega)^k | P(\omega).\] It seems like there's nothing wong here, but let's think about these values as numbers (well, we're already saying that one's divisible by the other). If $(1-\omega)$ were a prime, then this forces $P(\omega)$ to be somewhat large.

We can make this rigorous by defining the norm of a number (denoted $N(x)$), which is the number multiplied by all of its conjugates. We need a few facts about the norm: - The norm is multiplicative. (This follows from conjugation is multiplicative.) - Norms (of what?) are integers. Thus, if $a\mid b$, then $N(a) \mid N(b)$, so we can use it to properly book-keep divisibility.

Putting it all together: - $N(1-\omega) = q$, and thus $(1-\omega)^k$ has norm $q^k$. - On the other hand, we note that $P(\omega)$ has absolute value at most $n$, and so does its conjugates, so their product is at most $n^{q-1}$. - So we must have the relation \[q^k \le n^{q-1} < n^q\] as desired.

Discussion

In this solution, something fundamental was completely skipped - do there exist bipolar polynomials divisible by $(x-1)^k$ in the first place? (You know, so that the statement is not vacuously true...)

It's not too difficult to eventually invent the following example: \[P(x) = (x-1)(x^2-1)\cdots (x^{2^{k-1}} - 1).\]

So in this case, $n = 2^k$. But this is still terrible, since \[\frac{k}{\log n} = \frac{k}{k\log 2} = \frac{1}{\log 2} < \frac{q}{\log q}\] which still doesn't give us a non-trivial statement for any prime $q$. To regain some hope, what we would really like is for there to be some examples where $n=2^{o(k)}$.

So indirectly, we end up asking the folloing question:

If $(x-1)^k$ divides a bipolar polynomial, how low can its degree be?

A first attempt

Here's a counting argument that shows that $n = O(k^2 \log k)$ is possible.

The main idea is that any bipolar polynomial is the difference between two $\{0,1\}$-polynomials. Then, if two $\{0,1\}$-polynomials have the same remainder mod $(x-1)^k$, their difference is bipolar and divisible by $(x-1)^k$, as desired. This isn't immediately helpful (since there are infinitely many remainders mod $(x-1)^k$), but we can note that a "Taylor expansion" about $x=1$ gives \[f(x) \equiv \sum_{j=0}^{k-1} \frac{f^{(j)}(1)}{j!} x^j \pmod{(x-1)^k}\] and then now we can do a size bound: $f^{(j)} (1) / j! \le \binom{n}{j+1}$, just by working termwise with the formula for the $j$-th derivative and then using Pascal's identity. Thus, the number of possibilities is at most \[\prod_{j=0}^{k-1} \left(2 \binom{n}{j+1} + 1\right)\lesssim O(n^{k^2})\] then we just pick $n$ such that $O(n^{k^2}) < 2^n$ to conclude.

As for a lower bound, the original problem gives us one: if $\log n = O(\log k)$, then for all primes up to $q=O(k)$, $x^q-1$ must divide the bipolar polynomial. The sum of primes up to $k$ is roughly $O(k^2/\log k)$. So we've narrowed the value of $n$ down to a logarithmic gap - not bad foor a first attempt!

Looking at small cases

It helps to also just use Python to brute force looking for the lowest degree bipolar polynomial divisible by $(x-1)^k$ for small $k$. (It's totally doable using the criteria we had just now - I used to have the code for this but I've lost it...)

For $k=3$, we have \[P(x) = (1-x)(1-x^2)(1-x^3).\] This is weird, because compared to $Q(x) = (1-x)(1-x^2)(1-x^4)$, there isn't a clear reason why $P$ is still bipolar (but it is).

Continuing, for $k=4$ we try \[(1-x)(1-x^2)(1-x^3)(1-x^5)\] and it still works.

Does the pattern work, with \[P(x) = (1-x) \prod_{p\le N} (1-x^p)?\] Unfortunately, it doesn't, and for a good reason.

A tangent

Turns out we missed something - we could have ran this theorem with things that were not primes! Indeed, we can re-run the argument with any primitive root of unity to get that $\Phi_m(x) | P $ so long as

\[\frac{\phi(m)}{\log \phi(m)} < \frac{k}{\log n}.\]

I think it's pretty cool that this is precisely the obstruction to the pattern earlier failing: for instance, \[P(x) = (1-x) \prod_{p\le N} (1-x^p)\] could never work because eventually you are forced to also have $\Phi_4(x) = x^2+1$ as a divisor.

POST-EDIT 1: (from Jeck) The argument actually only works for prime powers $m$. If we plug in the $m$-th root of unity as $\omega$, then the norm of $(1-\omega)$ is now $\Phi_m(1)$, and \[\Phi_m(1) = \begin{cases} p & \text{if }m=p^\ell, \\ 1 & \text{otherwise}.\end{cases}\]

So, for prime powers $m=p^\ell$, we must also have

\[\frac{p^{\ell-1}(p-1)}{\log p} < \frac{k}{\log n}.\]

I think it's a really interesting question whether e.g. $\Phi_6(x)=x^2-x+1$ can be made to work in another way.

POST-EDIT 2: (from Jit Wu and Yan Sheng) The above can be done by first showing that if $(1-x)^k$ divides $P$, then roughly $(1+x)^{k/\log n}$ divides $P$. Then we're home free because $\Phi_6(x) = \Phi_3(-x)$. The question is still open for general cyclotomic polynomials.

Another idea: if we're looking for a construction of the form \[\prod (1-x^{a_i})\] then we can think directly about size. If we plug $x=e^{2\pi i \theta}$, then the size of $(1-x^{a_i})$ is related to the size of $\|a_i\theta\|_{\mathbb Z}$ - the distance from $a_i \theta$ to the nearest integer. So if among the $a_i$'s we avoided $m$ mod $p$, then we could set $\theta = m/p$ and maybe will be huge.

Interesting directions: - Can we make a bipolar polynomial divisible by any polynomial we want? - Find larger degree bipolar polynomials which vanish to high degree for $x=1$. - Explore the connection between the size of the coefficients and the values of $P$ on the unit circle. - The problem statement fails for large enough $n$ (with $k,q$ fixed) - but what does a construction look like? - Try to close the logarithmic gap. This is also related to... - Were we lucky, or does multiplying $(x^n-1)$'s (or cyclotomic factors) naturally give us bipolar polynomials? (This seems related to the phenomenon that the first cyclotomic polynomial with a coefficient that is not $\pm 1$ is $n=105$...)

POST-EDIT 3: (from Yan Sheng) This problem shows up in Borwein, Edelyi and Kos 1998, Theorem 2.7.

POST-EDIT 4: (from Yan Sheng) If we're thinking about which polynomials can have arbitrarily high powers divide a bipolar polynomial, the answer is (at most) cyclotomic polynomials. I'm lazy, so here's the transcript from Discord.

> Thinking about non-cyclotomic factors
> Fun fact: if p has ±1,0 coeffs and x^2-x-1 divides p(x) then p(x)/(x^2-x-1) also has ±1,0 coeffs
> From this it's easy to show that (x^2-x-1)^2 never divides a bipolar polynomial
> Actually the more general method is to use Jensen's formula to bound number of roots that are in discs of radius <1
> So I guess any polynomial with not all roots on the unit circle can only appear as factors of bipolar polynomials to bounded multiplicity
> Ah but Kronecker says monic integer coeffs with all roots on unit circle must be product of cyclotomics so there's nothing else that's interesting

Search This Blog

SIMO Retiree Blog