<![CDATA[Symmetry]]>As a general rule, when trying to understand or prove something, symmetry is a big help. If something has obvious symmetries, or can be brought into a symmetric form, doing so is usually worth trying. One example of this is my old post on index determination for DXT5/BC3 alpha blocks. But a while ago I ran into something that makes for a really nice example: consider the expression

|a + b| + |a - b|

If these were regular parentheses, this would simply evaluate to 2a, but we’re taking absolute values here, so it’s a bit more complicated than that. However, the expression does look pretty symmetric, so let’s see if we can do something with that. Name and conquer, so let’s define:

f(a,b) := |a + b| + |a - b|

This expression looks fairly symmetric in a and b, so what happens if we switch the two?

f(b,a) = |b + a| + |b - a| = |a + b| + |-(a - b)| = \\ |a + b| + |a - b| = f(a,b)

So it’s indeed symmetric in the two arguments. Another candidate to check is sign flips – we’re taking absolute values here, so we might find something interesting there as well:

f(a,-b) = |a + (-b)| + |a - (-b)| = |a - b| + |a + b| = f(a,b)

And because we already know that f is symmetric in its arguments, this gives us f(-a,b) = f(a,b) for free – bonus! Putting all these together, we now know that

f(a,b) = f(b,a) = f(|a|,|b|) = | |a| + |b| | + | |a| - |b| |

which isn’t earth-shattering but not obvious either. You could prove this directly from the original expression, but I like doing it this way (defining a function f and poking at it) because it’s much easier to see what’s going on.

But we’re not quite done yet: One final thing you can do with absolute values is figure out what needs to happen for the expression to be non-negative and see if you can simplify it further. Now, both |a| and |b| are always non-negative, so in fact we have

f(a,b) = |a| + |b| + | |a| - |b| |.

Now suppose that |a| \ge |b|. In that case, we know the sign of the expression on the right and can simplify further:

f(a,b) = |a| + |b| + (|a| - |b|) = 2 |a|

and similarly, when |b| \ge |a|, we get f(a,b) = 2 |b|. Putting the two together, we arrive at the conclusion

|a + b| + |a - b| = f(a,b) = 2 \max(|a|,|b|)

which I think is fairly cute. (This expression comes up in SATD computations and can be used to save some work in the final step.)

]]>