Ah, fair enough, thanks everyone. So basically the argument is if that we have a deterministic function taking a pair (x_1, x_2) with x_i in X with |X| = M, then the function can produce at most M^2 outputs. And knowing that the function is symmetric cuts it down to M(M+1)/2. (Which is still far bigger than the 2M in my addition analogy.) Cheers.

Except the perfect squares don't reduce by half, so it's not quite 50% but it's very close.