Any solution?

So nice, and so difficult. How many people did solve this in that test? Denote derivative of $p(x)$ by $p'(x)$. By Euclid's algorithm, there exists integer polynomial $A,B$ and integer $N$ such that $\deg B<\deg p$ and $A(x)p(x)+B(x)p'(x)=N$. Now since $p$ is irreducible and $\deg B,p'<\deg p$, for any root $\zeta$ of $p$, $B(\zeta),p'(\zeta)\neq 0$ holds. So $N=A(\zeta)p(\zeta)+B(\zeta)p'(\zeta)=B(\zeta)p'(\zeta)\neq 0$, so we can select a positive integer $R$ such that $q^R \not | N$. Now, for any $x$ satisfying $q^{R}|p(x)$, we get $q^{R}\not | A(x)p(x)+B(x)p'(x)$, hence $q^R\not|p'(x)$. For $n>R$, define \[S_{n}=\{ x | p(x)\equiv 0 \pmod{q^{n}}, 0\leq x<q^{n} \}\]So that $|S_{n}|=a_{n}$. Now construct a directed graph in $S_{R+1}\cup S_{R+2}\cup\cdots$ such that \[x \rightarrow y \Leftrightarrow \exists n, x\in S_{n}, y\in S_{n+1},x\equiv y \pmod{q^n}\]Also, we'll distinguish same number $x$ in $S_{n}$ and $x$ in $S_{m}$. Since $p(x)\equiv 0\pmod{q^{n}}$ implies $p(x)\equiv 0 \pmod {q^{n-1}}$, we get every element except of $S_{R+1}$ has at least 1 indegree, and therefore exactly 1 indegree, since $x$ doesn't have 2 different remainder $\mod q^{n}$. Also, applying mod $q^{R+1}$, every element is connected to exactly one element of $S_{R+1}$, and elements of $S_{R+1}$ are not connected with each other. Therefore, we can partition the graph into exactly $|S_{R+1}|$ components. Also, trivially each components become a tree, with each outdegrees at most $q$. We know that $p'(x+kq^n)\equiv p(x)\pmod{q^{n}}$, and for any $x\in S_{n}$, since $q^{R}|p(n)$, $q^{R}\not|p'(x)$. So for any edge $x\rightarrow y$, \[v_{q}(p'(x))=v_{q}(p'(y)\]where $v_{q}(x)$ is maximum $k$ which $q^{k}$ divides $x$. Therefore, if we fix a component $C$, then $v_{q}(p'(x))$ is constant for any $x\in C$. Therefore we can define $r=r(C)$ that $r=v_{q}(p'(x))$ for all $x\in C$. Also, we get $r<R$. Fix $C$. For $x\in C$ define $f(x)=v_{q}(p(x))-n$. Then we necessarily have $f(x)\geq 0$ for all $x\in C$. Color $x\in C$ blue, if and only if $f(x)\geq r$. Now, check the outdegree of each vertex. Above all, let $p(x)=\sum_{i=0}^{d} b_{i}x^{i}$. Then since \[p(x+kq^{n})=\sum_{i=0}^{d} b_{i}(x+kq^{n})^{i}\equiv \sum_{i=0}^{d} b_{i}(x^{i}+ikq^{n}x^{i-1})\equiv p(x)+kq^{n}p'(x) \pmod{q^{2n}}\]holds, and $n>R$, we get: For any $k$, there exists a $q\not |c$ such that \[p(x+kq^{n})\equiv p(x)+kcq^{n+r}\pmod{q^{n+R}}\]Case I: $f(x)<r$ Suppose $x\in S_{n}$ and $x\rightarrow y$ so that $y=x+kq^{n}$. (Remind that $0\leq x<q^{n}$.) Since $v_{q}(p(x))<n+r$, we get \[v_{q}(p(y))=v_{q}(p(x+kq^{n}))=v_{q}(p(x)+kcq^{n+r})=v_{q}(p(x))\]Therefore $f(y)=v_{q}(p(y))-(n+1)=f(x)-1$. This holds for all $x+kq^{n}$, hence the outdegree is - $q$ if $f(x)>0$ - 0 if $f(x)=0$ Moreover, since $f(y)=f(x)-1$, $f(y)<r$ holds, therefore we get if $x$ is not blue, any vertex that is reachable from $x$ is not blue. Case II: $f(x)\geq r$ Suppose $x\in S_{n}$ and $x\rightarrow y$ so that $y=x+kq^{n}$ and $0\leq k <q$. Now $p(y)\equiv p(x)+kcq^{n+r}\pmod{q^{n+R}}$ holds for some $q\not| c$, therefore there exists unique $k$ such that $v_{q}(p(y))>n+r$. (If $f(x)>r$, $k=0$ and if $f(x)=r$, $k=-p(x)/q^{n+r}\cdot c^{-1}$. For other $k$'s, we have to add some $aq^{n+r}$ where $q\not| a$, therefore the proposition.) Also, for other $k$'s, we get $f(y)=r-1$. Therefore we get about outdegree: - Exactly 1 blue vertex - Exactly $q-1$ non-blue vertex if $r>1$ - No further non-blue vertex if $r=0$ From Case I and II, we get any blue vertex $y\in S_{n}$ and $n>R+1$ has at least, and exactly 1 blue vertex $x\in S_{n}$ such that $x\rightarrow y$, and it goes up to an element of $S_{R+1}$, which is unique in the component. So if blue vertex exists, we can generate an unique infinite size route which only consists of blue vertices. Call it Grand Line. Also, from Case I and II, we got that if we go up from a non-blue vertex $x$, we reach a blue vertex or an element of $S_{R+1}$. And, since for non-blue vertices $f(x)$ decreases exactly 1, one will reach in at most $r$ steps. Therefore for $n>2R+1$, $S_{n}\cap C$ consists of elements like: - If $C$ doesn't have a grand line, no element Else: - 1 Blue vertex - $q-1$ non-blue vertices with distance 1 from grand line - $q(q-1)$ non-blue vertices with distance 2 from grand line - $q^{2}(q-1)$ non-blue vertices with distance 3 from grand line $\cdots$ - $q^{r-1}(q-1)$ non-blue vertices with distance $r$ from grand line Therefore, if $C$ has grand line and $n>2R+1$, $|S_{n}\cap C|=1+\sum_{i=1}^{r}q^{i-1}(q-1)=q^{r}$ holds. Now set $M=2R+2$. I'll prove $\{a_n\}_{n\ge M}$ is constant. Indeed, if we call components with grand line $C_{1},\cdots, C_{t}$, we get \[ a_{n}=|S_{n}|=\sum_{j=1}^{t}|C_{j}\cap S_{n}|=\sum_{j=1}^{t}q^{r(C_{j})}\]And the result doesn't depend on $n$, hence the desired result.

Denote by $\mathbb{Z}_q$ the set of $q$-adic integers. Assume $p(x)$ has no roots in $\mathbb{Z}_q$. In this case the equation \[p(x)\equiv 0 \pmod{q^n} \,\,\,\,\,\, (*)\]will stop to produce solutions from some place on. Suppose now $p(x)$ has roots in $\mathbb{Z}_q$. Then the solutions of $p(x)\equiv 0 \pmod{q^n}$ will tend to these roots in $q$-adic norm $|\cdot|_q$. Fix some $\alpha\in \mathbb{Z}_q\,,\, p(\alpha)=0$. Then $p'(\alpha)\neq 0$, since otherwise $p(x)$, having a same root with $p'(x)$, would be reducible over $\mathbb{Z}$. This is the only reason for which we need the irreducibility of $p$. Let $|p'(\alpha)|_q=q^{-r}\,,\,r\in \mathbb{Z},r\geq 0$. It just means $q^r$ is the greatest power that $q^r \mid p'(\alpha)$. We have $p'(x)=p'(\alpha)=q^{-r}$ in some neighbourhood of $\alpha$, or more precisely it holds when $x\in \mathbb{Z}_q\,,|x-\alpha|_q< p'(\alpha)=q^{-r}$. (see for example the proof of the Hansel's lemma, p-adic variant). Suppose now $x_n\in \mathbb{Z}_q$ is the first solution of $(*)$, such that $|x_n-\alpha|_q =q^{-n}\,, n>2r$. Then applying Hensel lemma(or some p-adic variant of it), we can get $x^*\in \mathbb{Z}_q$ in the same neighbourhood of $\alpha$, satisfying $x^* \equiv x_n \pmod{q^{n-r}}$ and $ q^{n+1} \mid p(x^*)$. It can be done applying Newton's approximation algorithm. In other words, starting from some "seed" $x_\in \mathbb{Z}_q$, close to $\alpha$, which satisfies (*), we can find $x^*=x_n + \ell q^{n-r}$, which satisfies \[p(x^*)\equiv 0 \pmod{q^{n+1}}\,\,\,\,\,\, (**)\]Using Taylor expansion around $x^*$, we see that $x_{n+1}^{(j)} := x^*+j\cdot q^{n+1-r}\,,j=0,1,2,\dots,q^r-1$ also satisfies $(**)$ and there are no more of them $\mod q^{n+1}$ in that neighbourhood of $\alpha$. That's, the seed $x_n$ spawns to $q^r$ solutions of $(**)$. Each of these solutions spawns to another $q^r$ solutions of (*) for $n+2$, but fortunately, it can be seen easily that $x_{n+1}^{(j)}$ and $x_{n+1}^{(i)}$ spawns to one and same set. Indeed the Newton's algorithm applied to $x_{n+1}^{(j)}$ and $x_{n+1}^{(i)}$ should generate one and the same $x^* \mod q^{n+2-r}$, since it's impossible for $x^*$ and $x^{**}$ with $|x^*-x^{**}|_q=q^{-(n+1-r)}$ to satisfy $q^{n+2}\mid p(x^*)-p(x^{**})$ (again by using the Taylor expansion). It means the number of solutions of $(*)$ stabilizes in that neighbouhood of $\alpha$. Since it's true for all $\mathbb{Z}_q$ roots of $p(x)=0$, the result follows. Comment: Apparently, this is a result strongly connected with the $p$-adic numbers and the Hensel's lemma, or some stuff around it, which was given on that competition to test about some more conventional proof.

I think only 1 or 2 solved it in the test. (I spent time on the wrong #2 and didn't have time to do this. ) But it's apparent that setting $ aP-bP'=c $ and using Hensel's Lemma is what this problem wanted us to do.

Hmm, this seems like a very nice problem, only that I am not fully sure if I understand it completely. If $q$ does not divide $P'(n)$ but does divide $P(n)$ then by Hensel's Lemma, $a_n=\infty$, is that what it means?

I think this solution is a bit shorter (edit, upon reading the other solutions, they seem to be essentially the same). Note $P(x+tq^n)=P(x)+tq^nP'(x)$ mod $q^{n+1}$. Fix $M$ to be massive, so that $GCD(P(x),P'(x))<q^{.01M}$. The $.01$ can be replaced with $.499$ (there are annoying edge effects with $.5$). Lemma: Fix some $n>M$, and look at the set of values $0 \le x< q^n$ where $q^n|P(x)$ and $q^k|P'(x)$ for $k \ge 1$. I claim on exactly $\frac{1}{q}$ of these values we have $q^{n+1}|P(x)$. Note this is trivial for all $k \ge .01n \ge .01M$. For a fixed $n$, assume this was false for some $k$, and pick the maximal such $k$. So we have $P(x+tq^{n-k})=P(x)+tq^{n-k}P'(x)$ mod $q^{n+1}$ by Hensel, and noting that $2n-2k>n+1$ due to $k<.01n$. Great. If $q^k||P'(x)$, then as $x$ ranges over residues mod $q^n$ which are $Y$ mod $q^{n-k}$ for a fixed $Y$ we have $q^k||P'(x)$ is preserved because of $k \le n-k$. Also among these we have $P(x+tq^{n-k})=P(x)+tq^{n-k}P'(x)$ mod $q^{n+1}$, so exactly $\frac{1}{q}$ of them are divisible by $q^{n+1}$. Hence, examining the set of $x$ such that $q^k|P'(x)$, $q^n|P(x)$ we have the ones with $q^k||P'(x)$ can be split into equivalence classes mod $q^{n-k}$, in each of which $\frac{1}{q}$ of the elements have $q^{n+1}|P(x)$. By the maximality of $k$, also we have that among the elements $q^{k+1}|P'(x)$, $q^n|P(x)$, $\frac{1}{q}$ of them have $q^{n+1}|P(x)$. But this is a contradiction, so the lemma is true. Now, fix $n>M$. Say a residue $x$ mod $q^n$ generates ${x,x+q^n,...x+(q-1)q^n}={x_0,x_1,...x_{q-1}}$ mod $q^{n+1}$. We have that $P(x+tq^n)=P(x)+tq^nP'(x)$. If $q$ does not divide $P'(x)$ and $q^n|P(x)$, then $x$ generates $q$ residues mod $q^{n+1}$, and there is a unique $x_j$ for which $P(x_j)=0$ mod $q^{n+1}$. If $q^n|P(x)$ and $q|P(x)$, all of the residues generated by $x$ are congruent to $P(x)$ mod $q^{n+1}$. Since $\frac{1}{q}$ of all choices of residues mod $q^n$ with $q^n|P(x)$ and $q|P'(x)$ have $q^{n+1}|P(x)$ (lemma for $k=1$), we have that $\frac{1}{q}$ of residues $y$ generated by $x$ with $q^n|P(x)$ and $q|P'(x)$ have $q^{n+1}|P(y)$. So some residues mod $q^n$ generate $1$ solution, and among the rest, $\frac{1}{q}$ of them generate $q$ solutions while the rest generate no solutions. So on average a generator generates one solution, and we have an equal number of solutions mod $q^n$ and $q^{n+1}$. The main part of the solution is the lemma. This is quite naturally motivated, or at least was in my solution. You want to just say $P(x+tq^n)=P(x)+tq^nP'(x)$ yields that if $x$ works mod $q^n$ exactly one of ${x,x+q^n,...x+(q-1)q^n}$ does. But you cannot say that when $q|P'(x)$. But looking at those cases, you can do something else, first adding $q^{n-1}$, unless $q^2|P'(x)$. But in that case you instead work with $q^{n-2}$. And so on and so forth.

anantmudgal09 wrote: Hmm, this seems like a very nice problem, only that I am not fully sure if I understand it completely. If $q$ does not divide $P'(n)$ but does divide $P(n)$ then by Hensel's Lemma, $a_n=\infty$, is that what it means? We're talking about solutions mod $q^n$. So $0 \le a_n \le q^n$ a priori.

There is a very nice solution using the fact that the $q$-adic norm on $\mathbb{Q}_q$ can be extended to its algebraic closure $\overline{\mathbb{Q}}_q$. (See, for instance, http://wstein.org/129/projects/hamburg/Project.pdf for reference.) This was one of the official solutions. Factorize the polynomial as \[ p(x) = c (x-\lambda_1) (x-\lambda_2) \cdots (x - \lambda_d), \]where $c \in \mathbb{Z}$ and $\lambda_1, \dots, \lambda_d \in \overline{\mathbb{Q}}_q$. Because $p(x)$ is irreducible and the characteristic of our field is zero, all the roots $\lambda_1, \dots, \lambda_d$ are distinct. This means that \[ m = \min\{ \lVert \lambda_i - \lambda_j \rVert\} > 0. \] Next we observe that \[ m \le \lVert \lambda_i - \lambda_j \rVert \le \max\{ \lVert x - \lambda_i \rVert, \lVert x - \lambda_j \rVert \} \]for any $i \neq j$. Hence for any given $x$, there can be at most one $i$ such that $\lVert x - \lambda_i \rVert \le m$. Moreover, if $\lVert x - \lambda_i \rVert < m$, then all the other terms $x - \lambda_j$ must have norm \[ \lVert x - \lambda_j \rVert = \lVert (x - \lambda_i) + (\lambda_i - \lambda_j) \rVert = \lVert \lambda_i - \lambda_j \rVert \]because $\lVert x - \lambda_i \rVert < m \le \lVert \lambda_i - \lambda_j \rVert$. In this case, \[ \lVert p(x) \rVert = \lVert x - \lambda_i \rVert \cdot \lVert c \rVert \prod_{j \neq i} \lVert \lambda_i - \lambda_j \rVert \]depends only on the norm $\lVert x - \lambda_i \rVert$. We conclude that for any given $t < \lVert c \rVert m^d$, the set \[ \{x : \lVert p(x) \rVert \le t \} \]is the disjoint union \[ \bigcup_{i=1}^{d} \Big\{ x : \lVert x - \lambda_i \rVert \le \frac{t}{\lVert c \rVert \prod_{j \neq i} \lVert \lambda_i - \lambda_j \rVert }\Big\}. \] Noting that $p(x) \equiv 0 \pmod{q^n}$ is equivalent to $\lVert p(x) \rVert \le q^{-n}$, we count the number of solutions among the set $\{1, 2, \dots, q^n\}$. If $n$ is sufficiently large, we may apply our observation above, and say that \[ \#\{ 0 < x \le q^n : \lVert p(x) \rVert \le q^{-n} \} = \sum_{i=1}^{d} \#\Big\{ 0 < x \le q^n : \lVert x - \lambda_i \rVert \le \frac{q^{-n}}{\lVert c \rVert \prod_{j \neq i} \lVert \lambda_i - \lambda_j \rVert }\Big\}. \]If $\lambda_i$ is in $\mathbb{Z}_p$, then looking at the expansion, it becomes clear that the summand on the right hand side is constant. If $\lambda_i$ is not in $\mathbb{Z}_p$, we see that the summand eventually becomes zero, because $\mathbb{Z}_p$ is the topological completion of $\mathbb{Z}$.

Since $p(x)$ is irreducible, for any other $q(x)\in \mathbb{Z}[x]$, either $\gcd(q(x),p(x))$ divides a constant of $p(x)|q(x)$. Since we are not working with corner cases, $\deg(p')=\deg p-1$ so $\gcd(p(x),p'(x))$ is bounded by a constant. We consider the possibilities for $p(x), p(x+q^{n-1}), \cdots, p(x+(q-1)q^{n-1})$. We know this is either injective or constant mod $q^n$. For each residue mod $q$, let $x_{n,r}$ be the number of solutions to $p(t)\equiv 0(\bmod\; q^n)$ where $0\le t\le q^n-1$ and $t\equiv r(\bmod\; q)$. If $q\nmid p'(r)$ then $p(x), p(x+q^{n-1}), \cdots, p(x+(q-1)q^{n-1})$ is injective mod $q^n$, so we can see that $x_{n,r}=x_{n+1,r}$. The other case is $q\mid p'(r), p(r)$. To prove this, note we say $n$ is large enough such that if $t$ mod $q^n$ is fixed then $\nu_q(p'(t))$ is a fixed value (since it's bounded anyways), call $C$, which is independent of $n$. If $q\nmid k$, then $p(x+kq^n)-p(x)\equiv kq^n p'(x) (\bmod\; q^{k})$ where $k<2n-1$ Thus, $p(x), p(x+q^n), \cdots, p(x+(q-1)q^n)$ are injective mod $q^{n+c+1}$, so at most one of these work. This works only if $x$ is one of the $x_{n+c,r}$ residues mod $q^{n+c}$ such that $q^{n+c} \mid p(x)$. Therefore, $x_{n+c,r}=x_{n+c+1,r}$ for every residue $r$ mod $q$, as needed.

Post #4, which I did about 7 years ago, uses $ p$-adic numbers. What follows is much simpler. The proof is based on Hensel's lemma. First, let us see that for sufficiently large $ N$ if $$ \displaystyle P(x_0)\equiv 0\pmod{q^N}$$then $$ \displaystyle P'(x_0)\not\equiv 0\pmod{q^N}$$Indeed, since $ P$ is irreducible $ P$ and $ P'$ are coprime as polynomials, hence $$ \displaystyle a(x)P(x)+b(x)P'(x)=c$$where $ a(x),b(x)\in \mathbb{Z}[X], c\in \mathbb{Z}, c\neq 0.$ We take $ N$ so that $ q^N>|c|.$ So, if $ q^N\mid P(x_0)$ it follows $ q^N\nmid P'(x_0).$ Now, let $ x_1,x_2,\dots,x_M$ be the roots of $$ \displaystyle P(x)\equiv 0\pmod{q^N}.$$It follows by Hensel's lemma that for any $ m\ge N$ each of $ x_i, i=1,2,\dots,x_M$ is lifted uniquely to a root $ x'_i$ modulo $ q^m$ with $ x'_i\equiv x_i\pmod {q^N}$ and these are the only roots of $ P(x)\equiv\pmod {q^m}.$

This is a wonderful problem, albeit in some sense more analytic than number-theoretic. There are two key insights that, once realized, render it quite tractable. The first, as utilized by many of the solutions above, is to view the situation in its full \(\left(q\right)\)-adic context. The second, of which I'm surprised to see little discussion, is that the irreducibility condition on \(f\) is needlessly strict. Indeed, even when \(p\left(x\right)\) is not irreducible or even squarefree, its number of solutions modulo a sufficiently high power of \(q\) is not much harder to count, just of different (nonconstant) asymptotic behavior. Denote by \(\widehat{\mathbb{Z}}_{\left(q\right)}\) the \(\left(q\right)\)-adic integers, equipped with the usual \(\left(q\right)\)-adic valuation and norm. Let \(\varphi\left(x\right)\in\widehat{\mathbb{Z}}_{\left(q\right)}\left[x\right]\) be a nonzero polynomial with \(\left(q\right)\)-adic coefficients. By that \(\widehat{\mathbb{Z}}_{\left(q\right)}\) is an integral domain, we have that \(\varphi\) enjoys a unique, up to permutation of the indices \(\text{i}\colon\text{k}\), factorization \[\varphi\left(x\right)\ =\ \left(x-\rho_{0}\right)^{e_{0}}\cdots\left(x-\rho_{\text{k}-1}\right)^{e_{\text{k}-1}}\psi\left(x\right)\]with \(\left(\rho_{\text{i}}\right)_{\text{i}\colon\text{k}}\in\widehat{\mathbb{Z}}_{\left(q\right)}\), the \(\left(\rho_{\text{i}}\right)_{\text{i}\colon\text{k}}\) pairwise distinct, and \(\psi\left(x\right)\) nonvanishing on \(\widehat{\mathbb{Z}}_{\left(q\right)}\). By the topological compactness of \(\widehat{\mathbb{Z}}_{\left(q\right)}\) and the \(\left(q\right)\)-adic continuity of \(\psi\) and the \(\left(q\right)\)-adic valuation away from \(0\), we have that \[\sup_{x\ \in\ \widehat{\mathbb{Z}}_{\left(q\right)}}\mathfrak{v}_{\left(q\right)}\left(\psi\left(x\right)\right)\ <\ \infty\text{.}\]By that \(\delta\left(\varepsilon\right)=\varepsilon\) is a \(\left(q\right)\)-adic modulus of continuity of any polynomial with coefficients in \(\widehat{\mathbb{Z}}_{\left(q\right)}\), we have for all \(x\in\widehat{\mathbb{Z}}_{\left(q\right)}\) and for all \(\text{i}\colon\text{k}\) that \begin{align*} &\mathfrak{v}_{\left(q\right)}\left(x-\rho_{\text{i}}\right)\ >\ \underbrace{\max\left(\sup_{x\ \in\ \widehat{\mathbb{Z}}_{\left(q\right)}}\mathfrak{v}_{\left(q\right)}\left(\psi\left(x\right)\right),\ \sup_{\text{i}'\colon\text{k},\ \text{i}'\neq\text{i}}\mathfrak{v}_{\left(q\right)}\left(\rho_{\text{i}}-\rho_{\text{i}'}\right)\right)}_{<\ \infty}\\ &\implies\ \mathfrak{v}_{\left(q\right)}\left(\varphi\left(x\right)\right)\ =\ e_{\text{i}}\cdot\mathfrak{v}_{\left(q\right)}\left(x-\rho_{\text{i}}\right)\ +\ \underbrace{\mathfrak{v}_{\left(q\right)}\left(\psi\left(\rho_{\text{i}}\right)\right)\ +\ \sum_{\text{i}'\colon\text{k},\ \text{i}'\neq\text{i}} e_{\text{i}'}\cdot\mathfrak{v}_{\left(q\right)}\left(\rho_{\text{i}}-\rho_{\text{i}'}\right)}_{<\ \infty\text{, independent of }x} \end{align*}As \[\mathcal{X}_{\varphi}\ :=\ \bigsqcup_{\text{i}\colon\text{k}}\left\{x\in\widehat{\mathbb{Z}}_{\left(q\right)}\text{ such that }\mathfrak{v}_{\left(q\right)}\left(x-\rho_{\text{i}}\right)\ >\ \max\left(\sup_{x\ \in\ \widehat{\mathbb{Z}}_{\left(q\right)}}\mathfrak{v}_{\left(q\right)}\left(\psi\left(x\right)\right),\ \sup_{\text{i}'\colon\text{k},\ \text{i}'\neq\text{i}}\mathfrak{v}_{\left(q\right)}\left(\rho_{\text{i}}-\rho_{\text{i}'}\right)\right)\right\}\ \subseteq\ \widehat{\mathbb{Z}}_{\left(q\right)}\]is manifestly a disjoint union of opens—whence its complement topologically compact—in \(\widehat{\mathbb{Z}}_{\left(q\right)}\), and as \(\varphi\) is manifestly nonvanishing on said complement, it follows that \[\sup_{x\ \in\ \widehat{\mathbb{Z}}_{\left(q\right)}\setminus\mathcal{X}_{\varphi}}\mathfrak{v}_{\left(q\right)}\left(\psi\left(x\right)\right)\ <\ \infty\text{.}\]We conclude that if \[\text{L}\ >\ \sup_{x\ \in\ \widehat{\mathbb{Z}}_{\left(q\right)}\setminus\mathcal{X}_{\varphi}}\mathfrak{v}_{\left(q\right)}\left(\psi\left(x\right)\right)\text{,}\]then \begin{align*} &\left\{x\in\widehat{\mathbb{Z}}_{\left(q\right)}\text{ such that }\mathfrak{v}_{\left(q\right)}\left(\varphi\left(x\right)\right)\geq\text{L}\right\}\ =\ \bigsqcup_{\text{i}\colon\text{k}}\left\{x\in\widehat{\mathbb{Z}}_{\left(q\right)}\text{ such that }\mathfrak{v}_{\left(q\right)}\left(x-\rho_{\text{i}}\right)\geq e_{\text{i}}^{-1}\cdot\left(\text{L}-\mathfrak{v}_{\left(q\right)}\left(\psi\left(\rho_{\text{i}}\right)\right)-\sum_{\text{i}'\colon\text{k},\ \text{i}'\neq\text{i}} e_{\text{i}'}\cdot\mathfrak{v}_{\left(q\right)}\left(\rho_{\text{i}}-\rho_{\text{i}'}\right)\right)\right\}\\ &\implies\ \left|\left\{x\in\mathbb{Z}/\left(q\right)^{\text{L}+\ell}\text{ such that }\varphi\left(x\right)=0\text{ in }\mathbb{Z}/\left(q\right)^{\text{L}}\right\}\right|\ =\ \sum_{\text{i}\colon\text{k}} q^{\ell\ +\ \left\lfloor\left(1-e_{\text{i}}^{-1}\right)\text{L}\ +\ e_{\text{i}}^{-1}\cdot\mathfrak{v}_{\left(q\right)}\left(\psi\left(\rho_{\text{i}}\right)\right)\ +\ \sum_{\text{i}'\colon\text{k},\ \text{i}'\neq\text{i}} e_{\text{i}}^{-1}e_{\text{i}'}\cdot\mathfrak{v}_{\left(q\right)}\left(\rho_{\text{i}}-\rho_{\text{i}'}\right)\right\rfloor}\text{.} \end{align*}The original problem is just a particular case in which \(\ell=0\) and \(\left(e_{\text{i}}=1\right)_{\text{i}\colon\text{k}}\), so that the latter sum is constant in \(\text{L}\). \(\blacksquare\) Note that (in spite of our arguments' double-invocation of topological compactness), our lower bound on \(\text{L}\) that when satisfied guarantees the above equality is not only effective, but in principle computable for a given \(\varphi\) as soon as we know the corresponding \(\left(\rho_{\text{i}}\right)_{\text{i}\colon\text{k}}\).