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.
(x-posted from SIMO XMen blog.)
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:
Putting it all together:
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?
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!
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.
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.
This actually let’s us get rid of log term in the lower bound! Since $\Phi_m(x)$ are coprime to each other, thus $P$ is divisible by $\prod_{m\le N} \Phi_m(x)$, which has degree
$$\sum_{m\le N} \phi(m) \sim N^2$$
so we get that $n = \Omega(k\log k/\log n)^2$ (assuming $\log n = o(k)$), so $n =\Omega(k^2)$.
An idea:
We can “go between” the coefficients and the values of $P$ on the unit circle as follows: $$[x^n] P = \frac{1}{2\pi i} \int_{|z| = 1} z^{-n}P(z^n) \cdot \frac{dz}{z}.$$
I think having $[x^n]P$ be at most 1 gives pretty severe constraints to the size of $P(z)$ on the unit circle. In the reverse direction, if $[x^n]P$ is ever large, then some point on the unit circle must capture it.
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:
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