### How Much Work Can It Be To Add Some Things Up?

#### Posted by Tom Leinster

Here’s a puzzle for you. Calculating anything takes work. How *much*
work? Well, obviously it depends how you’re doing the calculating. But
let’s make some assumptions.

Imagine we have a machine that can add up any finite sequence $x_1, \ldots, x_n$ of nonnegative reals. Doing so costs $W(x_1, \ldots, x_n) \in \mathbb{R}$ units of work — maybe measured in electricity, or potatoes, or whatever our machine uses as fuel. What could the function $W$ reasonably be?

Let’s make two assumptions.

The first is about adding up in stages. If you had a book filled with numbers, and you were given the dreary task of adding them all up, you might take a page by page approach: first you add up the numbers on each page, writing the total at the bottom of the page, then you add up all the page totals to give the final answer.

Obviously the two-stage approach gives the same *result*, but we’ll assume that in terms of
work done, it’s a perfectly efficient *strategy*. To take a simple
example (a two-page book), obviously

$v + w + x + y + z = (v + w + x) + (y + z),$

and we’re assuming that

$W(v,w,x,y,z) = W(v,w,x) + W(y,z) + W(v+w+x,y+z).$

The first term on the right-hand side indicates the work done to add up the three numbers $v, w, x$ on the first page. The second measures the work done to get the total of the numbers $y, z$ on the second page. The third term gives the work done in adding up the page totals to obtain the grand total. And in general, the equation is

$W(x_{11}, \ldots, x_{1 k_1}, \ldots, x_{n 1}, \ldots, x_{n k_n}) = \sum_{i = 1}^n W(x_{i 1}, \ldots, x_{i k_i}) + W\biggl( \sum_{j = 1}^{k_1} x_{1 j}, \ldots, \sum_{j = 1}^{k_n} x_{n j} \biggr)$

for any $x_{i j} \geq 0$.

For our second assumption, we imagine that our machine is really doing some
*work*, shifting around those numbers $x_i$ like they were physical
objects. I’m imagining something like one of those problems about piles of
earth that optimal transport people talk about: $x_i$ is the size of
the $i$th pile, and adding them together involves *moving* them.

On that basis, if the piles are all twice as big, then the process of adding them together take twice as much work. Generally:

$W(c x_1, \ldots, c x_n) = c W(x_1, \ldots, x_n)$

for any $c, x_i \geq 0$.

And that’s it. Under these two assumptions, there’s basically only one function $W$ that will do — only one way to measure the work needed to add some things up. The challenge is to find it.

## Re: How Much Work Can It Be To Add Some Things Up?

Just to get the ball rolling, I’m going to pessimistically guess $W=0$.