On the proof of $PP = P \iff \#P = FP$ in Arora & Barak (Lemma 17.7)

Question

Introduction

I am currently studying chapter 17 (of the famous textbook by Arora & Barak [1]) on the complexity of counting and got stuck on the proof of Lemma 17.7, which states $\mathrm{PP} = \mathrm{P} \iff \#\mathrm{P} = \mathrm{FP}$. I will first outline the proof and then formulate my question.

Proof Outline

The hard direction is proving $\mathrm{PP} = \mathrm{P} \implies \#\mathrm{P} = \mathrm{FP}$. In other words, given a function $f \in \#P$ we want to show the existence of a polynomial-time TM that computes $f$ using the assumption $\mathrm{PP} = \mathrm{P}$. Now since $f \in \#\mathrm{P}$, by definition there exists a TM $M$ (and polynomial $p$) such that $f(x) = |\{u \in \{0, 1\}^{p(|x|)} \, : \, M(x, u) = 1\}| := \#_M(x)$. The main idea of the proof in the book is now as follows: For any natural number $N$, we can build a polynomial-time TM $M'_N = M_N + M$ such that $\#_{M'_N}(x) := |\{u \in \{0, 1\}^{p(|x|) + 1} \, : \, M'_N(x, u) = 1\}| = N + \#_M(x)$. Moreover, the assumption $\mathrm{P} = \mathrm{PP}$ yields the existence of a polynomial-time TM to decide whether $\#_{M'_N}(x) \geq 2^{p(|x|)}$. Now if we find the smallest $N$ under which $\#_{M'_N}(x) \geq 2^{p(|x|)}$ is satisfied, we are done because we found $\#_M(x) = 2^{p(|x|)} - N$. In the proof it is now claimed that this can be done using binary search.

My struggles

What I struggle with in this argument is the following: The goal of the proof is to show the existence of a polynomial-time TM that computes $f$. According to the above proof, this TM works taking input $x$ and then running a binary search over $N \in \{0, \dots, 2^{p(|x|)} \}$. For every $N$ in the search, our TM would have to simulate another polynomial-time TM that decides whether $\#_{M'_N}(x) \geq 2^{p(|x|)}$ or not. But we only know of the existence of these other TM's and there is one for every distinct value $N$ can take. In other words, our final TM would have to be able to first find the TM it has to simulate in every step of the binary search. It is not clear to me how this can be done and in particular, I don't see how the proof is complete without this information.

Question

So I guess my question is: Am I missing some obvious reason why this still works or is my reasoning flawed at some point? If not, how can we get around this issue?

[1] Arora, Sanjeev; Barak, Boaz, Computational complexity. A modern approach., Cambridge: Cambridge University Press (ISBN 978-0-521-42426-4/hbk). xxiv, 579 p. (2009). ZBL1193.68112.

Answer 1

So I put my afterthought that Emil refers to in his comment to the question in this answer in order to close this thread:

Afterthoughts

So I had the following idea of how to get around this problem: Instead of working with one TM $M'_N$ for every value of $N \in \{0, \dots, 2^{p(|x|)}\}$ we can make $N$ part of the input. In other words, we work with the TM $M'$ that takes as input the tuple $(N, x, u)$. The language consisting of tuples $(N, x)$ where $|\{u \in \{0, 1\}^{p(|x| + 1)} : M'(N, x, u) = 1\}| \geq 2^{p(|x|)}$ is in $\mathrm{PP}$ and hence there is a polynomial-time TM for it assuming $\mathrm{PP} = \mathrm{P}$. This single TM can be hardcoded in the TM that computes $f$.