If I multiply two integers $x, y $ in $[0,2^L)$, I get an integer in $[0,2^{2L})$. Clearly, this map from $[0,2^L) \times [0,2^L) \to [0,2^{2L})$ is not bijective.
I am interested in the size of the image. It is less $2^{2L}$. By a classical result from Erdös, the size of the image divided by $2^{2L}$ goes to zero.
A simple argument shows that it cannot be much larger than $2^{2L}/2$. Indeed, pick $z$ in the image of this map, if $z$ is not a square (and there are only $2^L$ squares), then there are at least two corresponding distinct pairs of $x,y$ mapping to $z$ since multiplication is commutative.
But, clearly, this bound is naive for $L$ large. We have that the size of the image is much less than $2^{2L}/2$ (it goes to zero). I am looking for a reasonably tight bound. For example, given $L=64$ or $L=128$, I would like to bound (above and below) the size of the image with actual numbers.
The exact answer is known for up to $L=25$: see the OEIS sequence A027417.
