Freshman's Dream

A Freshman’s Dream

While I was reading some tropical geometry (not to be confused with topological geometry), I stumbled across the Freshman’s Dream, which states that $(x+y)^n=x^n+y^n.$ In standard mathematics, this is, of course, false. We know that in general $(x+y)^n= \sum _{k=0}^n \binom n k x^{k}y^{n-k}.$ The Binomial Theorem. However, I wanted to take a closer look at this false identity.

Warning (Freshman's Dream (generally false))

For all $x,y \in \Reals$

\begin{equation} (x+y)^n=x^n+y^n, \end{equation}

where $n\geq 0.$ This (false) identity only holds for $n=1.$

This leads to the question of which algebraic structures admit an analogue of the Freshman’s Dream? There’s many actually, but we’ll take a look at tropical geometry, of course.

Tropical Geometry

We will start by defining the elementary operations of tropical geometry.

Definition (Tropical arithmetic (addition and multiplication))

The main object of study is the tropical semiring $\mathbb{T} = (\R \cup \{\infty\},\oplus, \odot).$ Here addition and multiplication of real numbers are defined as

\begin{equation} x \oplus y \coloneqq \min (x,y), \end{equation}

and

\begin{equation} x \odot y \coloneqq x+y. \end{equation}

The $\textit{tropical sum}$ of two numbers is the minimum of $x$ and $y$ and the $\textit{tropical product}$ of two numbers is the sum of both numbers.

Example (Arithmetic)

The tropical sum of $2$ and $7$ is $2$ . This is written as

2 \oplus 7 = 2.

The tropical product of $4$ and $8$ is $12$ . We write this as

4 \odot 8 = 12.

Lemma (Basic tropical rules)

Now you may have noticed that a lot of the standard rules of arithmetic also hold in tropical arithmetic. For example

\begin{equation} x \oplus y = y \oplus x, \end{equation}

and

\begin{equation} x \odot y = y \odot x. \end{equation}

That is, commutativity in tropical addition and tropical multiplication. There’s also distributivity:

\begin{equation} x \odot (y \oplus z) = x \odot y \oplus x\odot z. \end{equation}

We have an identity element for $\oplus,$ namely, $\infty.$ And an identity element for $\odot,$ namely, $0.$

\begin{equation} x \oplus \infty = x. \end{equation}

\begin{equation} x \odot 0 = x. \end{equation}

The identities involving the two identities are:

\begin{equation} x \odot \infty = \infty. \end{equation}

\begin{equation} x \oplus 0 = \begin{dcases} 0 &\text{if } x\geq 0, \\ x &\text{if } x<0. \end{dcases} \end{equation}

Proof

Soon.

Now this is about enough information. Yes, we can still extend this for polynomials and vectors, etc., but for our purposes, that isn’t necessary. We will now define tropical powers and the binomial expansion in $\mathbb{T}$ then prove the Freshman’s Dream in a tropical universe.

Definition (Tropical powers)

Let $\N=\{0,1,2,\dots$ }. For $x\in\mathbb{T}$ define

x^0 \coloneqq 0,

and for $n\ge 1$ define

x^n \coloneqq \underbrace{x \odot \dots \odot x}_{n\text{ times}}.

In particular, if $x\in\R,$ then $x^n = nx$ (usual sum), and if $x=\infty$ then $x^n=\infty$ for all $n\ge 1$ .

Definition (Binomial expansion in

\mathbb{T}

)

Define, for $n\in\N$ ,

\begin{equation} B_n(x,y)\coloneqq \bigoplus_{k=0}^n \left(x^{\,n-k}\odot y^{\,k}\right). \end{equation}

Proposition (

(x\oplus y)^n = B_n(x,y)

in tropical arithmetic)

\begin{equation} (x\oplus y)^n = B_n(x,y). \end{equation}

Proof (Induction)

For $n=0$ , the claim is trivial: by Definition 1.6, $(x\oplus y)^0=0$ and

B_0(x,y)=\bigoplus_{k=0}^0\left(x^{\,0-k}\odot y^{\,k}\right)=x^0\odot y^0=0\odot 0=0,

so $(x\oplus y)^0=B_0(x,y)$ . Now we will induct on $n$ . For the base case $n=1$ , we have:

\begin{aligned} B_1(x,y) &=(x^1\odot y^0)\oplus(x^0\odot y^1). \end{aligned}

By Definition 1.6 again, we take $x^0=y^0=0$ , so

\begin{aligned} x^1\odot y^0 &= x\odot 0 = x,\\ x^0\odot y^1 &= 0\odot y = y. \end{aligned}

Hence

B_1(x,y)=x\oplus y=(x\oplus y)^1,

so eqref12 holds for $n=1$ .

Suppose $(x\oplus y)^n = B_n(x,y)$ . Then

(x\oplus y)^{n+1}=(x\oplus y)^n\odot(x\oplus y)=B_n(x,y)\odot(x\oplus y).

Now expanding $B_n(x,y)\odot(x\oplus y)$ using commutativity eqref5 and distributivity eqref6, we have:

B_n(x,y)\odot(x\oplus y)=\bigoplus_{k=0}^n\left(\left(x^{\,n-k}\odot y^{\,k}\right)\odot(x\oplus y)\right).

Using eqref6 again inside each term we get:

\left(x^{\,n-k}\odot y^{\,k}\right)\odot(x\oplus y) = \left(x^{\,n-k}\odot y^{\,k}\odot x\right)\ \oplus\ \left(x^{\,n-k}\odot y^{\,k}\odot y\right).

Therefore

(x\oplus y)^{n+1} = \left(\bigoplus_{k=0}^n x^{\,n-k}\odot y^{\,k}\odot x\right) \ \oplus\ \left(\bigoplus_{k=0}^n x^{\,n-k}\odot y^{\,k}\odot y\right).

By the definition of tropical powers, for any $m\ge 0$ we have

x^{m}\odot x = x^{m+1} \quad\text{and}\quad y^{m}\odot y = y^{m+1}.

Hence

x^{\,n-k}\odot y^{\,k}\odot x=x^{\,n-k+1}\odot y^{\,k}, \qquad x^{\,n-k}\odot y^{\,k}\odot y=x^{\,n-k}\odot y^{\,k+1}.

(x\oplus y)^{n+1} = \left(\bigoplus_{k=0}^n x^{\,n+1-k}\odot y^{\,k}\right) \ \oplus\ \left(\bigoplus_{k=0}^n x^{\,n-k}\odot y^{\,k+1}\right).

Reindexing the second sum with $j=k+1$ , so $j=1,\dots,n+1$ :

\bigoplus_{k=0}^n x^{\,n-k}\odot y^{\,k+1} = \bigoplus_{j=1}^{n+1} x^{\,n+1-j}\odot y^{\,j}.

We’re left with

(x\oplus y)^{n+1} = \left(\bigoplus_{k=0}^n x^{\,n+1-k}\odot y^{\,k}\right) \ \oplus\ \left(\bigoplus_{j=1}^{n+1} x^{\,n+1-j}\odot y^{\,j}\right).

This is the $\oplus$ -sum of all terms $x^{\,n+1-\ell}\odot y^{\,\ell}$ for $\ell=0,1,\dots,n+1$ ; this might look a little strange because the middle terms $\ell=1,\dots,n$ appear twice, but duplicates do not change the tropical sum since $u\oplus u=u$ . Therefore

(x\oplus y)^{n+1} = \bigoplus_{\ell=0}^{n+1} x^{\,n+1-\ell}\odot y^{\,\ell} = B_{n+1}(x,y).

\begin{aligned} \text{This closes the induction.} \tag*{$\blacksquare$} \end{aligned}

Theorem (Freshman's Dream (tropical version))

For all $x,y \in \mathbb{T}$ and $n \in N$ we have

\begin{equation} (x \oplus y)^n=x^n \oplus y^n. \end{equation}

Proof

$n=0$ follows trivially, $(x\oplus y)^0=0$ and $x^0\oplus y^0=0\oplus 0=0.$ $\newline$ Now let $n\ge 1$ . $\newline$ Case 1: $x,y\in\R$ .
From Proposition 1.8 and Definition 1.7 eqref11,

(x\oplus y)^n=\bigoplus_{k=0}^n \left(x^{\,n-k}\odot y^{\,k}\right).

Computing one general term using Definition 1.6 and eqref3 we get:

x^{\,n-k}\odot y^{\,k}=(n-k)x+ky.

(x\oplus y)^n=\bigoplus_{k=0}^n \left((n-k)x+ky\right).

Rewriting this in terms of eqref2 from Definition 1.2,

(x\oplus y)^n=\min_{0\le k\le n}\left((n-k)x+ky\right).

Setting $f(k)\coloneqq (n-k)x+ky$ . We’ll evaluate the discrete difference (ordinary subtraction in $\R$ ).

\begin{aligned} f(k+1)-f(k) &=\left((n-k-1)x+(k+1)y\right)-\left((n-k)x+ky\right)\\ &=y-x. \end{aligned}

So $f$ is monotone in $k$ :

If $y\ge x$ , then $y-x\ge 0$ , hence $f(k+1)\ge f(k)$ for all $k$ , so the minimum occurs at $k=0$ :

\min_{0\le k\le n} f(k)=f(0)=nx.

If $y\le x$ , then $y-x\le 0$ , hence $f(k+1)\le f(k)$ for all $k$ , so the minimum occurs at $k=n$ :

\min_{0\le k\le n} f(k)=f(n)=ny.

In either case,

\min_{0\le k\le n} f(k)=\min(nx,ny)=nx\oplus ny

(using eqref2 in the last equality). Finally, by Definition 1.6, $nx=x^n$ and $ny=y^n$ . Therefore

(x\oplus y)^n = nx\oplus ny = x^n\oplus y^n.

Case 2: $x=\infty$ or $y=\infty$ .
WLOG $x=\infty$ . By tropical addition eqref2,

x\oplus y=\min(\infty,y)=y,

hence

(x\oplus y)^n=y^n.

Also, by Definition 1.6, $x^n=\infty$ (since $x=\infty$ and $n\ge 1$ ). So using tropical addition again eqref2,

x^n\oplus y^n = \infty\oplus y^n = \min(\infty,y^n)=y^n.

Thus $(x\oplus y)^n=x^n\oplus y^n$ in this case as well.

\begin{aligned} \text{This completes both cases.} \tag*{$\blacksquare$} \end{aligned}

Now there is a way shorter proof of this (because you can prove $(x \oplus y)^n=x^n \oplus y^n$ directly from the definition), but I wanted to see how the tropical binomial expansion pedagogically collapsed.

References

Maclagan, D., & Sturmfels, B. (2015). Introduction to tropical geometry (Graduate Studies in Mathematics, Vol. 161). American Mathematical Society.