# How to prove that $n\log n$ is space constructible?

I'm trying to prove that $n\log n$ is space constructible. I've already managed to prove that $\log n$ is space constructible, but I cannot figure out how to prove the same about $n$. I assume, that if both $n$ and $\log n$ are space constructible, $n\log n$ will be space constructible as well.

I'm using Sipser's definition of space constructibility:

A function $f\colon N\to N$, where $f(n)$ is at least $O(\log ⁡n)$, is called space constructible if the function that maps the string $1^n$ to the binary representation of $f(n)$ is computable in space $O(f(n))$.

• Oh dear. Sipser really does say "at least $O(\log n)$". This is completely meaningless. Every function is at least as big as some function that's no more than $\log n$, since the constant zero function is $O(\log n)$. – David Richerby Mar 7 '18 at 13:20

You are right that if we can construct both $n$ and $\log n$ in $O(n\log n)$ space, we can construct $n\log n$ by multiplying these two values. I think constructing $\log n$ is actually the harder part here, which you seem to have already figured out. But let's go through it.
First, recall that a $k$-tape Turing Machine can be simulated on a single-tape Turing Machine by concatenating all the tapes onto a single tape. I am glossing over the details a bit here (but see Sipser for the details), but the key observation is that the space complexity can equivalently be viewed as the total space used across all tapes of a $k$-tape Turing Machine. So if we can construct a procedure for a $k$-tape Turing Machine that uses $O(n\log n)$ space across all tapes, then we have shown that $n\log n$ is space constructible.
We can construct $\log n$ through repeated halving of $n$. Specifically, we can copy $1^n$ from our initial tape containing the input to a second tape. Then, we can blank half of the ones on this second tape. Once we have blanked half of the ones, this tape will store $1^{n/2}$. We can repeat this halving process until there is only a single $1$ left. We count the number of halvings performed, in binary. We simply maintain a binary counter on a third tape, and perform a binary increment each time we perform a halving on $n$. At the end, the third tape will store the binary representation of $\log n$.
I am assuming that you already had figured the above out since you said you managed to prove $\log n$ is space constructible. And indeed you are correct that if we can independently construct $n$, we can multiply $n$ by $\log n$ in binary, using at most $n\log n$ space (in fact we will need less). All we really need then is to write out the binary representation of $n$ to another tape. Recall how we convert numbers to binary representation: the least significant bit of the binary representation of $n$ is $n\bmod 2$. Then, we can convert $\lfloor n/2\rfloor$ to binary (in a recursive manner) to compute the remaining bits. So, our Turing Machine will continue as follows: Copy $1^n$ to an available tape. Then, compute $n\bmod 2$. Note that we can do this fairly easily (If you are following Sipser, you should hopefully be comfortable with the fact that the set of all even-length strings is even a regular language). We write out the value of $n\bmod 2$ to another tape (call this the "$n$ tape"). Then, we perform the halving procedure on the $1^n$ again. Here, we should be careful about how we handle the case where $n$ is odd: we round down (For example, if $n=5$, after the halving procedure, the tape should contain $11$, the unary representation of $2$). This is to ensure the halving semantics are consistent with $\lfloor n/2 \rfloor$. Then, we move the head on the "$n$ tape" to the left one space, compute the mod once again, and write the result to the "$n$ tape" again. If we continue this modding and halving, writing the results of the modding to the left of the previously written bits on the "$n$" tape, we will eventually write out the binary representation of $n$ (once the working tape has only a single $1$ on it, the "$n$ tape" will contain the binary representation of $n$).
After these two procedures, we should have $\log n$ on one tape and $n$ on another tape, both in binary. Then, as you have already recognized, we can compute the product in $O(n\log n)$ space.