$50 and an ice cream cake that Navid Safaei wrote this

I don’t think a lot of contestants solved the problem today, I wonder if there are any easy partial points they can get.

Follows from Theorem 2 here

DottedCaculator wrote: Follows from Theorem 2 here The original paper in which theorem 2 is discussed is Michael Filaseta and Sergei Konyagin, Squarefree values of polynomials all of whose coefficients are 0 and 1, Acta Arith., 74(3): 191-205, 1996. See here: https://eudml.org/doc/206847.

djmathman wrote: $50 and an ice cream cake that Navid Safaei wrote this Can I have the ice cream if you are wrong

djmathman wrote: $50 and an ice cream cake that Navid Safaei wrote this Yeap , he wrote!

Here's a solution that is entirely $2$-adic in nature. The choice of $2^k$ as a modulus later is not that important - any large number will work. Let $D$ and $k$ be positive integers to be determined later. We bound non-squarefree polynomials $P \in P_n$ in two cases: Case 1. $P$ is divisible by $Q^2$ with $\deg Q > D$. For any such $Q$, $P$ is divisible by $Q^2$ over $\mathbb{F}_2$. Since $\deg (P/Q^2) \leq n - 2\deg Q$, there are at most $2^{n - 2\deg Q+1}$ such $P$ for any given $Q$, so summing over all $Q$ we get at most \[2^n \sum_{d > D} 2^d \cdot 2^{-2d+1} = 2^{n-D+1}\]polynomials $P$. (Note that we can assume $Q$ is monic, so the degree of $Q$ does not change under the $\mathbb{F}_2$-reduction.) Case 2. $P$ is divisible by $Q^2$ with $\deg Q \leq D$. In this part, we work over $\mathbb{Z}/2^k\mathbb{Z}$. Specifically, we claim that for a given monic $Q \in \mathbb{Z}/2^k\mathbb{Z}$ of degree $d$ with $Q(0)$ odd, the proportion of polynomials in $P_n$ divisible by $Q^2$ approaches $2^{-2kd}$ as $n \to \infty$. By summing over the finitely many possible $Q$, we get at most \[(1 + o(1))2^n \sum_{d \leq D} 2^{kd}\cdot 2^{-2kd} < (1 + o(1)) \frac{2^n}{2^k - 1}\]bad polynomials $P$. Note that by combining the two cases, we can get the bad polynomials to be an arbitrarily small proportion of $P_n$ if we set $D$ and $k$ to be sufficiently large at the start and let $n$ go to infinity. The key claim in Case 2 is actually a corollary of a much more general result: Lemma. Let $G$ be a finite abelian group, and let $a_1, a_2, \ldots \in G$ be a periodic sequence such that the $a_i$ generate $G$. Then, if $S$ is a uniformly random subset of $[n]$ and $a \in G$, then \[\lim_{n \to \infty} \mathbb{P}\left[\sum_{i \in S} a_i = a\right] = \frac{1}{\lvert G\rvert}.\] Proof. Let $g_i\colon G \to \mathbb{C}$ be the function that is $\tfrac{1}{2}$ on $0$ and $\tfrac{1}{2}$ on $a_i$, and let $f_n = g_1 * \cdots * g_n$ be the probability distribution of $\textstyle \sum_{i \in S} a_i$. Then, by Fourier inversion, we may write \[f_n(a) = \frac{1}{\lvert G \rvert} \sum_{\chi \in \hat G} \chi(a) \prod_{i \in [n]} \hat g_i(\chi).\]Note that $\lvert \hat g_i(\chi) \rvert = \lvert 1 + \chi(a_i)\rvert/2$ is bounded by $1$, with equality if $\chi = 1$. Thus the $\chi = 1$ term above is just $1/\lvert G \rvert$. For all other $\chi$, the only way for the corresponding term to not undergo exponential decay is if $\lvert \hat g_i(\chi) \rvert = 1$ for all $i$ (recall that the $a_i$ and hence the $g_i$ are periodic). But this implies that $\chi(a_i) = 1$ for all $i$, meaning that all the $a_i$ live in the proper subgroup $\ker \chi$. This contradicts the fact that the $a_i$ generate $G$. $\blacksquare$ To finish Case 2, apply the claim with $G = \mathbb{Z}/2^k\mathbb{Z}[x]/(Q(x)^2)$, $a = -1$, and $a_i = x^i$. It is obvious that the $a_i$, along with $1$, generate $G$, so both the periodicity and generation conditions follow from the claim that some power of $x$ is $1$. Since $G$ is finite, it suffices to show that $x$ is not a zero divisor in $\mathbb{Z}/2^k\mathbb{Z}[x]/(Q(x)^2)$. Indeed, if $xP(x) = Q(x)^2R(x)$ in $\mathbb{Z}/2^k\mathbb{Z}$, then by looking at constant terms we find that $R(x)$ is divisible by $x$ as $Q(0)$ is odd. Thus $P(x)$ is divisible by $Q(x)^2$ too.

A slightly different approach, that doesn't use anything about squarefree-ness after establishing that Q has low degree. As with the above post, we can reduce to the case where $\mathrm{deg} Q \le d$, by factoring over $\mathbb{F}_2$. Claim 1: There are finitely many $Q$ with $\mathrm{deg} Q \le d$ that divide any $P$ with $\{0, 1\}$ coefficients. Proof: Note that all roots $r$ of $P$ satisfy $|r| < 2$. Indeed, if $P$ is degree $n$, and $|r| \ge 2$, then $|P(r)| \ge |r|^n - (|r|^{n-1} + \dots + 1) > 0$. Thus, all roots of $Q$ have magnitude less than $2$. Let $Q$ have degree $d$, and roots $r_1, \dots, r_d$ -- then the $x^k$ coefficient is a symmetric sum over $\binom{d}{k}$ terms, each of which has magnitude at most $2^k$. Thus, the coefficients of $Q$ are bounded. Because the coefficients are integers, there are finitely many such $Q$. Combining this with the next claim finishes the problem. Claim 2: For a fixed polynomial $Q$, the probability that $Q | P$ over $P = 1 + \sum_{i=1}^n a_i x^i$ is at most $O(n^{-1/2}) = o(1)$. Proof: Let $r$ be a root of $Q$. Then, we wish to understand: how many choices $(a_1, \dots, a_n) \in \{0, 1\}^n$ satisfy that $\sum_{i=1}^n a_i r^i = -1$? This is called the Littlewood-Offord problem, and the bound can be shown via a simple Sperner's lemma argument.

Claim 2 from the above post (mathocean97) can be proved with a bit different idea. Take the set $S=\{r^i: i=1,2,\dots,n\}$. If $|S|=n$, i.e. $r$ is not a root of unity, then the probability that the sum of elements of a random subset of $S$ is $-1$ is less than $\frac{1}{n+1}$. It is proved in this blog post, and the idea is simple. For any binary vector $b$ that corresponds to a bad subset,( i.e., with sum of elements equal to $-1$) we consider the unit ball (by Hamming distance) centered at $b$, that is, all binary vectors that differ at exactly $1$ bit from $b$. Their number is $n$ and non of them is a bad binary vector. A bit care is needed to ensure that the unit spheres corresponding to distinct bad vectors do not intersect - see the link. So, the estimate follows. Now, it remains to consider the case when $S$ is a multiset. Let $k$ be he the smallest number with $r^k=1$. We have a multiset $S$ with $k$ groups, each one with consists of (almost) $n/k$ equal values. If $k$ is large (e.g. $k>\sqrt{n}$), we can do the same trick as above (flipping the bit of the first element of each group - we can number them) and obtain that the probability to take a bad binary vector is less than $\frac{1}{k}\le \frac{1}{\sqrt n}$. In case $k$ is small ($k<\sqrt n$), we take the group $G$ with the largest number of elements, say $m, m\ge n/k$. Take a bad binary vector $b$ and let the number of chosen elements that are in $G$ is $s$. Since all the elements in $G$ are the same (have the same value), every binary vector with the same bits as $b$ outside $G$, and such that the number of 1's bits corresponding to the elements of $G$ is different from $s$ is not bad. So, the portion of the bad vectors for a fixed binary values corresponding to elements outside $G$ is at most $\displaystyle \frac{\binom{m}{s}}{2^{m}}$. Since $\frac{\binom{m}{s}}{2^m}\le \frac{C}{\sqrt m}$, where $C$ is a constant, we obtain that the probability to take a bad binary vector is less than $\frac{C}{\sqrt m}\le \frac{C}{\sqrt[4]{n}}$ This means that for a fixed polynomial $Q$, the portion of the binary polynomials $P$ of degree $n$ with $Q\mid P$ is $O(n^{-1/4})$. Remark. In my opinion this problem is not appropriate for high school Olympiad level, although I like it. This is what real math is. Maybe it is ok for Miklos Schweitzer, but on the other hand it's a known result of Konyagin, so it can be easily found searching the net. It has several crucial moments. The most difficult part (in my opinion) is to see that the probability of a binary polynomial $P$ to be multiple of $Q^2$ where $Q$ is an integer polynomial of some large degree, is small (it's o(1)). It involves a reduction modulo $2$. The second part is to see that the polynomials $Q$ with small degrees that divide a binary polynomial $P$ are finitely many, since their coefficients are bounded. This is not hard to see, but it's meaningful only if you got the first idea. In the third place comes the idea that for any fixed $Q$, the portion of the binary polynomials multiple of $Q$ tends to $0$ as $n\to \infty$. I would say that it's doable in real time, but only if you get to that point. Let me point out a very similar problem - RMM Shortlist 2020, A1, maybe of the same author. I think with a similar difficulty. EDIT: In this blogpost I posted a full solution and some comments on the original problem. The ideas from the above posts are used.

Although post #4 contains it, nobody has written out the official method of dealing with $\deg Q$ small. If I understand correctly, it's similar in idea to #10, but uses the fact that we have $Q^2$ rather than $Q$ to finish more cleanly (and yields a portion of $O(n^{-1})$). For reference, in the rubric for this problem, dealing with $\deg Q$ large was worth $3$ points, dealing with $\deg Q$ small was worth $3$ points (with $1$ point for the root magnitude/Vieta's idea and $2$ for the "coefficient flipping" step), and $1$ point was given for putting everything together. Apparently there is different, rather heavy/ugly way to deal with $\deg Q$ large, which a couple contestants were on the path to doing; I found the mod 2 idea, giving me $3$ points and exactly enough to make the gold medal cut Fix a large choice of $n$. Obviously there are $2^n$ polynomials in $P_n$. We upper bound the number of polynomials in $P_n$ that are divisible by $Q^2$ for some $Q$. It suffices to show that the sum of the number of elements divisible by $Q^2$ across all monic (WLOG; $Q$ with leading coefficient $-1$ are identical) nonconstant integer polynomials $Q$ is "small", whence we may finish by union bound. We split into two cases. Case 1: $\deg Q > 1000$. We work modulo $2$, with the key insight being that $Q^2$ will be of the form $x^{2a_1}+\cdots+x^{2a_k}$ for some nonnegative integers $\deg Q=a_1>\cdots>a_k$. Note that the value of an element of $P_n$ modulo $2$ uniquely determines the element. For each choice of $Q^2 \bmod{2}$, observe that there are clearly at most $2^{n+1-2a_1}$ choices for $R \bmod{2}$, corresponding to selecting $x^i \in \{0,1\}$ for $0 \leq i \leq n-2a_1$ (obviously not all of these work, but it doesn't matter). On the other hand, if we fix $a_1$ there are a total of $2^{a_1}$ ways to select $Q^2 \bmod{2}$, so there are at most $2^{n+1-a_1}$ possibilities for $P \bmod{2}$. Summing over all $a_1$ yields a total of $$\sum_{d=1000}^{\infty} 2^{n+1-d}<0.001\cdot 2^n$$possible $P$. Case 2: $\deg Q \leq 1000$. We will need the following claim first. Claim: Let $r$ be a root of some polynomial in $P_n$. Then $|r|<2$. Proof: Suppose there exists $|r| \geq 2$ for some choice of $P$ and let $d$ be the maximal index such that $a_d=1$. Then $$|r^d|>|r^{d-1}|+\cdots+|r^1|+|1| \geq |a_{d-1}r^{d-1}|+\cdots+|a_1r^1|+|1| \geq |P(x)-r^d|$$by the triangle inequality, which is absurd. $\blacksquare$ Now by Vieta's formulae, if we fix $\deg Q$ then each of the coefficients of $Q$ must be bounded, and since $Q \in \mathbb{Z}[x]$ it follows that (independently of $n$) we have a bounded number—say, $M$—of $Q$ that could possibly divide an element of $P_n$. Now fix a choice of $Q$; note that $Q$ obviously has constant term $\pm 1$. Consider two polynomials $P_1, P_2 \in P_n$ which are both divisible by $Q^2$. Then $P_1-P_2$ is also divisible by $Q^2$, and has all coefficients in $\{-1,0,1\}$. Observe now that $P_1-P_2$ must have at least three nonzero coefficients: the only squared polynomials dividing $\pm x^a$ or $\pm x^a \pm x^b$ (for $a \neq b$) are of the form $x^{\bullet}$, which $Q$ cannot possibly be; this is obvious for $x^a$ and follows for $x^a \pm x^b$ from examining the roots, which are distinct roots of unity, along with $0$ which we may ignore. Thus, for each element $P \in P_n$ divisible by $Q^2$, let $S(P)$ denote the set of all $n$ polynomials (also in $P_n$) obtained by "flipping" exactly one choice of $a_i$ between $0$ and $1$. The above fact implies that for any distinct $P_1,P_2$ divisible by $Q^2$ we have $S(P_1) \cap S(P_2) = \emptyset$, so the total number of $P$ is at most $n^{-1}2^n$. Summing over all $D$ choices of $Q$, we have at most $Dn^{-1}2^n$ choices in total for $P$. Finally, for all $n$ sufficiently large we have $$0.001\cdot 2^n+Dn^{-1}2^n<0.01\cdot 2^n,$$finishing the problem. $\blacksquare$