Modular and Submodular Properties of the Sum and Max Functions

1. Introduction

In optimization and combinatorics, set functions play a central role.
Given a finite ground set $N$, a set function is any mapping:

$$f: 2^N \to \mathbb{R}.$$

Two of the most common examples are:

• Sum function:
  $f_{\text{sum}}(S) = \sum_{i \in S} w_i$

• Max function:
  $f_{\text{max}}(S) = \max_{i \in S} w_i$

for some fixed weights $w_i \in \mathbb{R}$.

These functions exhibit interesting structural properties known as modularity and submodularity, which are fundamental concepts in combinatorial optimization.

---

2. Modularity and Submodularity

Definition

A function $f: 2^N \to \mathbb{R}$ is submodular if for all subsets $A, B \subseteq N$,

$$f(A) + f(B) \ge f(A \cup B) + f(A \cap B).$$

If equality always holds, then $f$ is modular.

---

2.1 The Sum Function is Modular

Consider

$$f_{\text{sum}}(S) = \sum_{i \in S} w_i.$$

Then for any $A, B \subseteq N$,

$$\begin{aligned} f(A) + f(B) &= \sum_{i \in A} w_i + \sum_{i \in B} w_i \\ &= \sum_{i \in A \cup B} w_i + \sum_{i \in A \cap B} w_i \\ &= f(A \cup B) + f(A \cap B). \end{aligned}$$

Thus, the sum function satisfies equality for all pairs $(A,B)$, and therefore it is modular.

---

2.2 The Max Function is Submodular

Now consider

$$f_{\text{max}}(S) = \max_{i \in S} w_i.$$

We must show that for all $A,B \subseteq N$,

$$f(A) + f(B) \ge f(A \cup B) + f(A \cap B).$$

Let

$$a = f(A) = \max_{i \in A} w_i, \quad b = f(B) = \max_{i \in B} w_i.$$

Then

$$f(A \cup B) = \max(a, b),$$
and
$$f(A \cap B) \le \min(a, b).$$

Hence,

$$f(A \cup B) + f(A \cap B) \le \max(a, b) + \min(a, b) = a + b = f(A) + f(B).$$

Therefore, the inequality holds for all $A,B$, so $f_{\text{max}}$ is submodular.

---

3. Summary

Function	Expression	Property	Reason
Sum	$f(S) = \sum_{i\in S} w_i$	Modular	Equality holds in the submodular inequality
Max	$f(S) = \max_{i\in S} w_i$	Submodular	Inequality holds, with possible strict inequality

Both functions are monotone (non-decreasing with respect to inclusion), but only the sum function is exactly modular.
The max function is strictly submodular unless the maximum element is shared across all subsets.

---

Keywords: modular function, submodular function, combinatorial optimization, set function, convexity