Math vs. Computer Science

What actually separates math from computer science? Obviously there is a large intersection between the two, but each of them has a distinctive feel. Is it just a “you know it when you see it” kind of distinction?

I don’t think so. And I think knowing what characterizes the two actually helps you become better at both, in particular because you know what broad class of techniques you should be focusing on.

Math and computer science, broadly speaking, both ask questions about the solutions to a certain problem. “What are the objects $X$ that satisfy some property $P$?”

1. Math is focused on studying the space of solutions, without necessarily providing a way to construct or explicitly understand individual instances of solutions.
2. Computer science is focused on studying procedures to construct solutions, without necessarily providing you with a broad understanding of the space of solutions.

I think this is best explained through example.

Math: Borsuk-Ulam

Assume the Earth is a perfect sphere and temperature/air pressure vary continuously across its surface. There exist two diametrically opposed points with identical temperature and air pressure.

We will prove a simpler theorem. Consider the circle $S^1$ of radius $1$ in $\mathbb{C}$ and a continuous function $f : S^1 -> \mathbb{R}$. Then there is a point $x \in S^1$ such that $f(x) = f(-x)$.

Proof: Consider the function $g(x) = f(x) - f(-x)$. Observe $g(-x) = -g(x)$. Pick any $x$; either $g(x) = 0$, in which case we are done, or not, in which case the Intermediate Value Theorem provides us with some $y$ between $x$ and $-x$ such that $g(y) = 0$.

(Note the zeroes of $g$ are precisely the points which $f(x) = f(-x)$.)

The Borsuk-Ulam theorem gives us insight into the solution space (i.e. that it is non-empty). This is a typical example of a “non-constructive proof”, where we learn that a solution exists, but the proof is no use for actually finding the solution.

Computer Science: The non-decreasing multiples of $N$

The source is AtCoder ABC 443 Task F.

A number is called non-decreasing if its digits don’t decrease, e.g. $1123$. What is the smallest non-decreasing multiple of $N$?

We can easily modify this solution to yield all non-decreasing multiples of $N$ (just don’t terminate) in increasing order. So we have a reasonably fast way to generate all such multiples of $N$.

Yet this solution provides no insight into what properties these non-decreasing multiples of $N$ have. How many of them are there? How quickly do they grow? We have no idea.