Functions with and without distinction of cases

Question

Consider computable functions $f: \mathbb{N} \rightarrow \mathbb{N}$, given as formulas. I assume that it is clear for at least some of them whether they contain a distinction of cases:

$$f(n) = n$$

obviously does not contain a distinction of cases (i.e. is d.c.-free),

$$ g(n) = \begin{cases} 1 & \text{for } n = 0 \\ n & \text{otherwise} \end{cases} $$

obviously does, at least at the face of it.

What is not clear is whether there is a d.c.-free function $g'$ that is equivalent with $g$, is it?

What I believe to know:

1. It is not decidable whether there is a d.c.-free function equivalent with a given one (unless one can prove that there is one for every computable function!)

2. Especially, a d.c.-free function $g'$ is not "computable" (as a formula) from a given one $g$

3. Even when you are given one (by an oracle): showing the equivalence of $g'$ and $g$ is not decidable.

Nevertheless there are at least some trivial cases where a d.c.-free formula exists, e.g. for

$$ g(n) = \begin{cases} 0 & \text{for } n = 0 \\ n & \text{otherwise} \end{cases} $$

Can anyone provide a non-trivial example?

Answer 1

The answer to this question heavily depends on what functions are allowed as building blocks for non d.c. functions. A little thought shows that if it's somehow possible to construct a step function using non d.c. functions, then any d.c. function can in principle be rewritten using these step functions - admittedly, not in a particularly nice way.

If we assume that $x\rightarrow x^2$ and $x\rightarrow \sqrt x$ are allowed as non-d.c. functions, then we can construct the absolute value function as $|x| = \sqrt{x^2}$, and using the absolute value function, we can then construct the max and min functions as

$$ \max(a,b) = \frac{|a - b| + a + b}{2}\\ \min(a,b) = \frac{|a - b| - a - b}{2}$$

Using these functions, we can first construct $f(x) = \max(x+1,0)$ and $g(x) = \max(x,0)$. When restricted to the natural numbers, we see that $h = f - g$ is equivalent to $$ h(n) = \begin{cases} 1&n \geq 0\\ 0 &n < 0\\ \end{cases}.$$

This step function can be translated to anywhere on the number line by defining $$h_a(n) = \max(n+1-a,0)-\max(n-a,0) = \begin{cases} 1 & n \geq a \\ 0 & n < a\end{cases}.$$

We can then get a generalized filter function by the product $h_a(1-h_b)$.

Any d.c. function can therefore be rewritten in terms of these products. For example, the function $$ f = \begin{cases} 1 & n = 0 \\ 0 & \mathrm{otherwise} \end{cases} $$ can be written as $h_0\cdot(1- h_1)$.

Writing $f$ out explicitly (only in terms of abs!), we have

$f(n) = \frac 14 \left[\left(1-|n|\right)\left(1-|n| +|n-1| + |n+1|\right) + |n^2-1| \right]$

Checking, we see that $$f(0) = \frac 14 \left[1\cdot(1 + 1 +1) + 1\right] = 1,$$ while $$\begin{align}f(n)|_{n \geq 1} &= \frac 14 \left[(1-n)(1-n+n-1+n+1)+n^2-1\right]\\ &= \frac 14 (1-n^2 + n^2 -1) = 0\end{align},$$ and $$\begin{align}f(n)|_{n \leq -1} &= \frac 14 \left[(1+n)(1+n-n+1-n-1)+n^2-1\right]\\ &= \frac 14 (1-n^2 + n^2 -1) = 0\end{align},$$

exactly as desired. This also shows that the construction in terms of cases is a great deal more succinct (and clear) than the one presented here.